AN IFORMATION THEORETIC APPROACH TO BIT 课件.ppt

AN IFORMATION THEORETIC APPROACH TO BIT STUFFING FOR NETWORK PROTOCOLS Jack Keil Wolf Center for Magnetic Recording Research University of California, San Diego La Jolla, CA DIMACS Workshop on Network Information Theory Rutgers University March 17-19, 2003 精品文档 Acknowledgement Some of this work was done jointly with: Patrick Lee Paul Bender Sharon Aviran Jiangxin Chen Shirley Halevy (Technion) Paul Siegel Ron Roth (Technion) 精品文档 Constrained Sequences and Network protocols In many protocols, specific data patterns are used as control signals. These prohibited patterns must be prevented from occurring in the data. In any coding scheme that prohibits certain patterns from occurring, the number of constrained (or coded) bits must exceed the number of data bits. 精品文档 Relationship to Information Theory The average number of data bits per constrained bit is called the rate of the code. The Shannon capacity is the maximum rate of any code. Practical codes usually have rates strictly less than the Shannon capacity. 精品文档 Bit Stuffing Bit stuffing is one coding technique for preventing patterns from occurring in data. The code rate for bit stuffing is always less than the Shannon capacity. Here we show how to make the code rate for bit stuffing equal to the Shannon capacity. 精品文档 Bit Stuffing and Protocols Definition from Webopedia: (/TERM/B/bit_stuffing.html) “bit stuffing-The practice of adding bits to a stream of data. Bit stuffing is used by many network and communication protocols for the following reasons: To prevent data being interpreted as control information. For example, many frame-based protocols, such as X.25, signal the beginning and end of a frame with six consecutive 1’s. Therefore, if the actual data has six consecutive 1 bits in a row, a zero is inserted after the first 5 bits… Of course, on the receiving end, the stuffed bits must be discarded…” data: 01111110111110101010… This won’t work: