Parallel bit stuffing for a serial data transfer protocol

[0002] 1. Field of the Invention

[0003] The present invention relates to bit stuffing in serial data transfer protocols, and more particularly, to a method for bit stuffing in parallel.

[0004] 2. Background Information

[0005] The Universal Serial Bus (USB) is a cable bus that supports data exchange between a host computer (USB host) and a wide range of simultaneously accessible peripherals (USB devices). The USB physical interconnect is a tiered star topology. A hub is at the center of each star. Each wire segment is a point-to-point connection between the USB host and a hub or USB device, or a USB hub connected to another hub or USB device. The USB host contains host controllers that provide access to the USB devices in the system.

[0006] The current USB specification employs non-return to zero invert (NRZI) data encoding when transmitting packets. In NRZI encoding, a “1” is represented by no change in voltage level and a “0” is represented by a change in voltage level. Thus, a string of zeros causes the NRZI data to toggle each bit time. A string of ones causes long periods with no transitions in the data.

[0007] In order to ensure adequate signal transitions, bit stuffing is employed by the transmitting device when sending a packet on USB. A zero is inserted after every six consecutive ones in the data stream before the data is NRZI encoded, to force a transition in the NRZI data stream. This gives the receiver logic a data transition at least once every seven bit times to guarantee the data and clock lock. Bit stuffing is enabled beginning with the synchronization pattern and throughout the entire transmission.

[0008] The receiver of the data must decode the NRZI data, recognize the stuffed bits and discard them. If the receiver sees seven consecutive ones anywhere in the data packet then a bit stuffing error has occurred and the packet should be ignored.

[0009] Bit stuffing is inherently serial in nature. This makes it difficult to implement bit stuffing at high data rates. Currently, the USB serial data rate is specified to be 12 Mb/sec. Under a contemplated revision to USB (USB 2.0) this data rate may increase by forty. This makes it difficult for prior art bit stuffing methods to be effective. What is needed is a new method of bit stuffing that can handle high data rates.

[0010] A parallel bit stuffing method acting on a stream of serial data is disclosed. The method receives an input data segment of a predetermined bit length from the stream of serial data. Next, an address field is formed by appending to the input data segment a carryover segment. Using a look-up table stored in read only memory (ROM), the address field is used to correlate to an output field. The output field includes a stuffed data portion and a carryover segment portion. The carryover segment portion is used in a next cycle as the carryover segment. Finally, the stuffed data portion is output as output data segments of predetermined bit length.

[0011] The present invention will be described in conjunction with the FIGURES, wherein:

[0012] FIG. 1 is a schematic diagram illustrating an apparatus for parallel bit stuffing in accordance with the present invention;

[0013] FIG. 2 illustrates the format of the output of the read only memory for the bit stuffing apparatus of the present invention;

[0014] FIG. 3 is a table showing the processing of an example series of input bytes during bit stuffing by the present invention;

[0015] FIG. 4 is a schematic diagram illustrating an apparatus for parallel bit unstuffing in accordance with the present invention

[0016] FIG. 5 illustrates the format of the output of the read only memory for the bit unstuffing apparatus of in the present invention;

[0017] FIG. 6 is a table showing the processing of an example series of input bytes during bit unstuffing by the present invention; and

[0018] FIG. 7 is a schematic diagram illustrating an apparatus for parallel bit stuffing using two read only memory devices each acting on four bits in accordance with the present invention.

[0019] FIG. 1 shows a schematic diagram of an apparatus 101 used for implementing parallel bit stuffing in accordance with the present invention. The bit stuffing apparatus 101 includes a read only memory (ROM) 103, a shift unit 105, a first register 107, and a second register 109. The bit stuffing apparatus 101 operates on a byte of data in every clock cycle. It can be appreciated that each of the components noted above includes a synchronous clock input that is used to regulate the timing of the bit stuffing operation. For simplicity, the clock input lines are not shown in FIG. 1.

[0020] Data that is to be processed by bit stuffing is provided on an input line 111. The data is provided in parallel as an 8-bit byte. Each byte of data is input on input line 111 to the read only memory 103. Also provided as an input to the ROM 103 is a 3-bit data signal from the first register 107. The 3-bit data signal is carried along data line 113. The combination of the 3-bit data signal from the first register 107 and the 8-bit byte carried along input line 111 form an 11-bit input address. As will be seen in greater detail below, the 3-bit data signal along data line 113 correlates to the number of “1”'s that follow the last “0” in the preceding byte that was processed.

[0021] The ROM 103 is simply a large look-up table that uniquely correlates each distinctive 11-bit input address with a 15-bit output. The 15-bit output is comprised of three portions. Specifically, turning to FIG. 2, the 15-bit output from the ROM 103 comprises a 10-bit data portion 201, a 2-bit valid data length portion 203, and a 3-bit carryover portion 205.

[0022] The 3-bit carryover portion 205 is provided as the input to the first register 107. The first register 107 simply is a delay register which outputs a 3-bit data signal on line 113 that is the carryover portion 205 received from ROM 103 in the previous clock cycle.

[0023] The valid data length portion 203 is provided to the shift unit 105 and is a signal that indicates to the shift unit 105 how many of the bits in the 10-bit data portion 201 are valid. As will be seen with further detail below, of the 10 bits that are output by the ROM 103, either 8 bits, 9 bits, or 10 bits may be valid data. The 2-bit valid data length portion 203 can provide a digital representation as to whether or not 8 bits, 9 bits, or 10 bits are valid for the shift unit 105. For example, if the 2-bit valid data length portion 203 is “00” in the preferred embodiment, this means that 8 bits of the data portion 201 received from the ROM 103 are valid. If the 2-bit valid data length portion 203 is “01”, in the preferred embodiment, this means that 9 bits of the data portion 201 received from the ROM 103 are valid. Finally, if the 2-bit valid data length portion 203 is “10” in the preferred embodiment, this means that all 10 bits of the data portion 201 received from the ROM 103 are valid.

[0024] To see how the ROM 103 translates and performs the bit stuffing procedure, FIG. 3 shows examples of bytes of input data that are provided to the ROM 103. Specifically, FIG. 3 shows a sequence of bytes numbered 1-6 that are input into the ROM 103. The bytes shown in FIG. 3 are arbitrary and are chosen only to illustrate the present invention.

[0025] As noted above, the input address that is input into the ROM 103 is a combination of the 3-bit data signal on line 113 concatenated with the input byte. In FIG. 3, the first byte input into the ROM 103 is a series of eight “1”'s. The ROM input address is thus the 3-bit data signal carried on data line 113 combined with the input byte data carried on input line 111. In this particular case, because this is the first byte to be processed, the first register 107 places three ‘0’s on the data line 113. The input byte is appended verbatim to the ROM input address. Thus, the input address to the ROM is “00011111111”. The ROM 103 includes a look-up table that contains a unique 15-bit output for every unique 11-bit input address. The data portion 201 of the 15-bit output is determined by the bit stuffing algorithm. In the case of USB, a zero is inserted after every series of six consecutive ones. Thus, the data portion 201 of the 15-bit output must be designed with this bit stuffing algorithm in mind.

[0026] In this case, because the ROM input address is 3 ‘0’s followed by 8 ‘1’s, the ROM 15-bit output has a data portion 201 that comprises 6 ‘1’s, followed by a bit stuffed ‘0’, followed by 2 ‘1’s and a don't care (X) bit. This comprises the data portion 201 of the ROM output. Also provided in the ROM 15-bit output is the 2 bit valid data length portion 203. As noted above, this indicates how many of the 10-bits of data portion 201 contain valid data. In this case, nine of the bits are valid data and the tenth field is a “don't care” (denoted by “X” in FIG. 3). Therefore, the valid data length portion 203 includes the data “01” that indicates that 9 bits are to be considered valid.

[0027] As noted above, the data pattern “01” is arbitrarily chosen to represent that 9-bits are valid. If 8 bits are valid in the data portion 201, then the valid data length portion 203 would contain “10” and if all ten bits are valid, then the valid data length field 203 would contain “10”. The foregoing is exemplary only and it can be appreciated by those skilled in the art that the valid data length portion 203 may contain any combination of 2 bits to associate with the validity of 8, 9, and 10 bits, respectively.

[0028] Finally, the 15-bit output from the ROM includes the carryover portion 205. This field indicates how many ‘1’s are present at the end of the data portion 201 that follow the last ‘0’. In this case, the data portion 201 includes two ‘1’s that follow a ‘0’. This is represented in the carryover portion 205 as the binary number “010”. If there were no ‘1’s following a ‘0’ at the end of the data portion, i.e., no carryover ‘1’s, then the carryover portion 205 would read “000”. If there were six ‘1’s at the end of the data portion 201 following a ‘0’, then the carryover portion 205 would read “110”.

[0029] The 15-bit output of the ROM is parsed to deliver the data portion 201 and the valid data length portion 203 to the shift unit 105. The carryover portion 205 is passed to the first register 107. The first register 107 stores the carryover portion 205 for one cycle and outputs the same carryover portion 205 onto data line 113 for the next input byte to be processed. Thus, in FIG. 3, note that the carryover portion 205 of the 15-bit output is always identical to the first 3-bits of the ROM input address for the next input byte.

[0030] The data portion 201 (which carries the bit stuffed byte) is carried on a parallel 10-bit line to the shift unit 105. The valid data length portion 203 is carried on a parallel 2-bit line to the shift unit 105. The shift unit 105 operates on the stuffed data portion 201 as follows. The shift unit 105 receives the data portion 201 and based upon the signal along the valid data length portion 203, processes either 8, 9, or 10 bits of the data portion 201. In the case of the first processed data portion 201 in FIG. 3, the valid data length field contains “01”, which indicates that 9 bits of the data portion 201 is valid. Therefore, the shift unit 105 will process only 9 of the bits in the data portion 201. The shift unit 105 is operative to receive the first 8 bits of the data portion 201 and output those 8 bits to the second register 109. The 9^thbit is placed in a queue for output during the next cycle. In this case, the shift unit 105 would output the 8-bit byte “11111101” and store a “1” in the queue.

[0031] When the second processed data portion 201 shown in FIG. 3 is output by the ROM 103 during the next clock cycle, the valid data bits of the second processed data portion 201 are sequentially added to the queue until a complete 8-bit byte is formed. Continuing the example of above, 1 bit is stored in the queue of the shift unit 105 from the first cycle, and thus, the next 7 bits from the second data portion 201 from the ROM 103 is loaded into the queue. Those 8 bits are then output to the second shift register 109. In the specific example shown in FIG. 3, the second byte output by the shift unit 105 would consist of the following byte: “11001011”. The 8^thbit of the second 10-bit data portion 201 (which is a “1”) would be stored in the queue.

[0032] Continuing with the example, the third data portion 201 output by the ROM 103 consists of 9 bits. Seven of those bits are provided to the queue of the shift unit 105. Thus, the shift unit 105 would output an 8-bit byte comprising: “11110101”. The remaining last 2 bits of the third data portion 201 would be stored in the queue as “10”. This process continues indefinitely while the parallel bit stuffing apparatus 101 processes the input bytes.

[0033] Importantly, when the shift unit 105 has 8 bits stored in it's queue, a hold signal is transmitted by the shift unit 105 along a hold line 115 to the circuitry that provides the input bytes to the ROM 103. This hold signal holds the input of data for one clock cycle allowing the shift unit to clear it's queue of the 8 bit byte that has been stored in the queue. After this has been accomplished, additional input bytes may be processed by the bit stuffing apparatus 101.

[0034] Finally, the second register 109 receives the output byte from the shift unit 105 and outputs the byte to a transceiver (not shown) for transmission along the serial data bus. The transceiver converts the 8-bit byte from parallel format into serial data that can be passed onto a serial bus.

[0035] The creation of the programming of the ROM 103 is straightforward. Because the ROM input address is comprised of 11 bits total, the total number of entries in the look-up table stored by the ROM 103 is 2¹¹or 2,048 entries. For each entry, there is a 15-bit output. Therefore, the total number of bits required for the ROM is on the order of 33,000 or 33K of ROM.

[0036] Note that the ROM 103 has a predetermined 15-bit output associated with every ROM input address. For example, in entries 1 and 4 of FIG. 3, the ROM input address is precisely the same and the 15-bit output is precisely the same in both cases. This despite the fact that two intermediate bytes were processed by the bit stuffing apparatus 101. Additionally, as can be seen, when a series of input bytes all containing ‘1’s are provided to the bit stuffing apparatus 101 (as seen in input bytes 4, 5, and 6 of FIG. 3), the 15-bit output for input byte number 6 contains the full 10 bits and each bit of the data portion 201 is valid. Therefore, the valid data length portion 203 for the 15-bit output for row 6 is “10”.

[0037] Next, turning to FIG. 4, an apparatus 401 for unstuffing bits from a serial data stream is shown. Note that the unstuffing apparatus 401 operates on bytes of data input in parallel. Therefore, a receiver (not shown) must be provided for converting a serial data stream into a parallel stream.

[0038] The unstuffing apparatus 401 architecturally looks very similar to the bit stuffing apparatus 101 of FIG. 1. As the bytes are input in parallel into a ROM 403, a 3-bit data signal is provided from a first register 407. Thus, the input to the ROM 403 is once again an 11-bit input address. The 11-bit address comprises the 3-bits from the first register 407 and the 8-bit byte being processed. The ROM 403 is simply a large look-up table that uniquely correlates each distinctive 11-bit input address with a 13-bit output.

[0039] The ROM 403 provides a 13-bit output. The 13-bit output comprises three portions as shown in FIG. 5. The 13-bit output includes an 8-bit data portion 501, a 2-bit valid data portion 503, and a 3-bit carryover portion 505.

[0040] The 3-bit carryover portion 505 is provided as the input to the first register 407. The first register 407 simply is a delay register which outputs a 3-bit data signal to the ROM 403 that is the carryover portion 505 received from ROM 403 in the previous clock cycle.

[0041] The valid data portion 503 is provided to a shift unit 405 and is a signal that indicates to the shift unit 405 how many of the bits in the 8-bit data portion 501 are valid. As will be seen with further detail below, of the 8 bits that are output by the ROM 403, either 6 bits, 7 bits, or 8 bits may be valid data. The 2-bit valid data length portion 503 can provide a digital representation as to whether or not 6 bits, 7 bits, or 8 bits are valid for the shift unit 405. For example, if the 2-bit valid data length portion 503 is “00”, in the preferred embodiment, this means that 6 bits of the data portion 501 received from the ROM 403 are valid. If the 2-bit valid data length portion 503 is “01”, in the preferred embodiment, this means that 7 bits of the data portion 501 received from the ROM 403 are valid. Finally, if the 2-bit valid data length portion 503 is “10”, in the preferred embodiment, this means that all 8 bits of the data portion 501 received from the ROM 403 are valid.

[0042] To see how the ROM 403 translates and performs the bit stuffing procedure, FIG. 6 shows examples of bytes of input data that are provided to the ROM 403. Specifically, FIG. 6 shows a sequence of bytes numbered 1-6 that are input into the ROM 403. Like the bytes shown in FIG. 3 above, the bytes shown in FIG. 6 are arbitrary and are chosen only to illustrate the present invention.

[0043] The input address that is input into the ROM 403 is a combination of the 3-bit data signal concatenated with the input byte. In FIG. 6, the first byte input into the ROM 403 is “11111101”. The ROM input address is thus the 3-bit data signal from first register 407 combined with the input byte data. In this particular case, because this is the first byte to be processed, the first register 407 places outputs “000”. The input byte is appended verbatim to the ROM input address. Thus, the first input address to the ROM 403 is “00011111101”. The ROM 403 includes a look-up table that contains a unique 13-bit output for every unique 11-bit input address.

[0044] The data portion 501 of the 13-bit output is determined by the bit unstuffing algorithm. In the case of USB, a zero that follows six consecutive ones is removed or deleted. Thus, the data portion 501 of the 13-bit output must be designed with this bit stuffing algorithm in mind.

[0045] In this case, because the ROM input address is 3 ‘0’s followed by “11111101”, the ROM 13-bit output has a data portion 501 that comprises seven consecutive ‘1’s followed by a don't care (X) bit. In other words, the ROM 403 recognizes that the zero in the input byte was bit stuffed and should be removed. This comprises the data portion 501 of the ROM output.

[0046] Also provided in the ROM 13-bit output is the 2 bit valid data portion 503. As noted above, this indicates how many of the 8-bits of data portion 501 contain valid data. In this case, seven of the bits are valid data and the eighth field is a “don't care” (denoted by “X” in FIG. 6). Therefore, the valid data length portion 503 includes the data “01” that indicates that 7 bits are to be considered valid.

[0047] As noted above, the data pattern “01” is arbitrarily chosen to represent that 7 bits are valid. If 6 bits are valid in the data portion 501, then the valid data portion 503 would contain “00” and if all 8 bits are valid, then the valid data portion 503 would contain “10”. The foregoing is exemplary only and it can be appreciated by those skilled in the art that the valid data portion 503 may contain any combination of 2 bits to associate with the validity of 6, 7, and 8 bits, respectively.

[0048] Finally, the 13-bit output from the ROM includes the carryover portion 505. This field indicates how many ‘1’s are present at the end of the data portion 501 that follow the last ‘0’. In this case, the data portion 501 includes a single ‘1’ that follows a ‘0’. This is represented in the carryover portion 505 as the binary number “001”. If there were no ‘1’s following a ‘0’ at the end of the data portion, i.e., no carryover ‘1’s, then the carryover portion 505 would read “000”. If there were six ‘1’s at the end of the data portion 501 following a ‘0’, then the carryover portion 505 would read “110”.

[0049] The 13-bit output of the ROM 403 is parsed to deliver the data portion 501 and the valid data portion 503 to the shift unit 405. The carryover portion 505 is passed to the first register 407. The first register 407 stores the carryover portion 505 for one cycle and outputs the same carryover portion 505 to the ROM 403 for use with the next input byte to be processed. Thus, in FIG. 6, note that the carryover portion 505 of the 13-bit output is always identical to the first 3-bits of the ROM input address for the next input byte.

[0050] The data portion 501 (which carries the unstuffing data) is carried on a parallel 8-bit line to the shift unit 405. The valid data portion 503 is carried on a parallel 2-bit line to the shift unit 405. The shift unit 405 operates on the stuffed data portion 501 as follows. The shift unit 405 receives the data portion 501 and based upon the signal along the valid data length portion 503, processes either 6, 7, or 8 bits of the data portion 501. In the case of the first processed data portion 501 in FIG. 6, the valid data length field contains “01”, which indicates that 7 bits of the data portion 501 is valid. Therefore, the shift unit 405 will process only 7 of the bits in the data portion 501. The shift unit 405 is operative to receive the 7 bits of the data portion 501 and stores these bits into a queue for output during the next cycle. In this case, the shift unit would store “1111111” in the queue.

[0051] Importantly, when the shift unit 405 does not have the full 8 bits stored in it's queue to form a byte, a hold signal is transmitted by the shift unit 405 along a hold line 415 to the circuitry that processes the output bytes of the receiver. This hold signal holds the output of the data for one clock cycle allowing the shift unit 405 to fill it's queue of the 8 bit byte. After this has been accomplished, additional output bytes may be pulled from the bit unstuffing apparatus 401.

[0052] When the second processed data portion 501 is output by the ROM 403 during the next clock cycle, the valid data bits of the second processed data portion 501 are sequentially added to the queue until a complete 8-bit byte is formed. Continuing the example of above, seven bits are stored in the queue of the shift unit 405 from the first cycle, and thus, the first bit from the second processed data portion 501 from the ROM 403 is loaded into the queue. Those 8 bits are then output to the second shift register 409. In the specific example shown in FIG. 6, the first byte to be output by the shift unit 405 would consist of the following byte: “11111111”. The next seven bits of the second 8-bit data portion 501 (which is “1011111”) would be stored in the queue.

[0053] Continuing with the example, the third processed data portion 501 output by the ROM 503 consists of 7 bits. The first of those bits is provided to the queue of the shift unit 405 to complete a byte (coupled from the 7 bits already stored in the queue). Thus, the shift unit 405 would output an 8-bit byte comprising: “10111111”. The remaining last 6 bits of the third data portion 501 would be stored in the queue as “100111”. This process continues indefinitely while the parallel bit stuffing apparatus 101 processes the input bytes.

[0054] Finally, the second register 409 receives the output byte from the shift unit 405 and outputs the byte to circuitry (not shown) for processing.

[0055] The creation of the programming of the ROM 403 is straightforward. Because the ROM input address is comprised of 11 bits total, the total number of entries in the look-up table stored by the ROM 103 is 2¹¹or 2,048 entries. For each entry, there is a 13-bit output. Therefore, the total number of bits required for the ROM is on the order of 28,000 or 28K of ROM. Note that the ROM 503 has a predetermined 13-bit output associated with every ROM input address.

[0056] Turning next to FIG. 7, an alternative embodiment of a bit stuffing apparatus 701 is shown. The operation of this embodiment is substantially similar to that shown in FIGS. 1-3, except that two ROMs are provided 703 and 705, each ROM operating on 4-bits of an 8-bit byte. The advantage of this embodiment is that the size of each ROM may be reduced. Specifically, the input address of each ROM is 7-bits long and the output of the ROM is 9-bits long. Thus, the total number of entries in the look-up table stored by the ROMs 703 and 705 are 2⁷or 128 entries. For each entry, there is a 9-bit output. Therefore, the total number of bits required for each ROM is only about 1,300 or 1.3K of ROM, giving a total ROM capacity of 2.6K for both ROMs.

[0057] The operation of the embodiment of FIG. 7 is substantially the same as that for the preferred embodiment of FIG. 1. Specifically, the input data byte is separated into the four most significant bits (MSB) and the four least significant bits (LSB). The four MSBs are input into the first ROM 703 and the four LSBs are input into the second ROM 705.

[0058] The first ROM 703 also has as an input a 3-bit data signal from a first register 707. The combination of the 3-bit data signal from the first register 707 and the 4-bit byte form a 7-bit input address. As will be seen in greater detail below, the 3-bit data signal correlates to the number of “1”'s that follow the last “0” in the four LSBs processed by second ROM 705 during the preceding clock cycle.

[0059] The first ROM 703 is simply a look-up table that uniquely correlates each distinctive 7-bit input address with a 9-bit output. The 9-bit output is comprised of three portions. Specifically, the 9-bit output from the first ROM 703 comprises a 5-bit data portion, a 1-bit valid data length portion, and a 3-bit carryover portion. The 3-bit carryover portion is provided as an input to the second ROM 705.

[0060] The valid data length portion is provided to a shift unit 709 and is a signal that indicates to the shift unit 709 how many of the bits in the 5-bit data portion are valid. As will be seen with further detail below, of the 5 bits that are output by the first ROM 703, either 4 bits or 5 bits may be valid data. The 1-bit valid data portion can provide a digital representation as to whether or not 4 bits or 5 bits are valid for the shift unit 709. For example, if the 1-bit valid data portion is “0”, in the preferred embodiment, this means that 4 bits of the data portion received from the first ROM 705 are valid. If the 1-bit valid data portion is “1”, in the preferred embodiment, this means that 5 bits of the data portion received from the first ROM 705 are valid.

[0061] The ROM 705 translates and performs the bit stuffing procedure the same as in the preferred embodiment and that description will not be repeated.

[0062] The 9-bit output from the first ROM 703 includes a carryover portion. This field indicates how many ‘1’s are present at the end of the data portion that follow the last ‘0’. If there were no ‘1’s following a ‘0’ at the end of the data portion, i.e., no carryover ‘1’s, then the carryover portion would read “000”. If there were four ‘1’s at the end of the data portion, then the carryover portion would read “100”.

[0063] The 9-bit output of the ROM is parsed to deliver the data portion and the valid data portion to the shift unit 709. The carryover portion is passed to the second ROM 705.

[0064] The second ROM 705 operates substantially similar to the first ROM 703. Specifically, the second ROM 705 also has as an input a 3-bit carryover portion from the first ROM 703. The combination of the 3-bit carryover portion from the first ROM 703 and the 4-bit LSB form a 7-bit input address. As noted above, the 3-bit carryover portion correlates to the number of “1”'s that follow the last “0” in the four MSBs processed by first ROM 703.

[0065] The second ROM 705 is simply a look-up table that uniquely correlates each distinctive 7-bit input address with a 9-bit output. Like the first ROM 703, the 9-bit output is comprised of three portions. Specifically, the 9-bit output from the second ROM 705 comprises a 5-bit data portion, a 1-bit valid data portion, and a 3-bit carryover portion. The 3-bit carryover portion is provided as an input to the first register 707.

[0066] The valid data length portion is provided to the shift unit 709 and is a signal that indicates to the shift unit 709 how many of the bits in the 5-bit data portion are valid. As will be seen with further detail below, of the 5 bits that are output by the second ROM 705, either 4 bits or 5 bits may be valid data. The 1-bit valid data portion can provide a digital representation as to whether or not 4 bits or 5 bits are valid for the shift unit 709. For example, if the 1-bit valid data portion is “0”, in the preferred embodiment, this means that 4 bits of the data portion received from the second ROM 705 are valid. If the 1-bit valid data portion is “1”, in the preferred embodiment, this means that 5 bits of the data portion received from the second ROM 703 are valid.

[0067] The ROM 703 translates and performs the bit stuffing procedure similarly as in the preferred embodiment and that description will not be repeated.

[0068] The 9-bit output from the second ROM 705 includes a carryover portion. This field indicates how many ‘1’s are present at the end of the data portion that follow the last ‘0’. If there were no ‘1’s following a ‘0’ at the end of the data portion, i.e., no carryover ‘1’s, then the carryover portion would read “000”. If there were four ‘1’s at the end of the data portion, then the carryover portion would read “100”.

[0069] The 9-bit output of the ROM is parsed to deliver the data portion and the valid data portion to the shift unit 709. The carryover portion is passed to the first register 707. The first register 707 stores the carryover portion from the second ROM 707 for one cycle and outputs the same carryover portion for input into the first ROM 703 for the next input byte to be processed. Thus, the first register 707 simply is a delay register.

[0070] Thus, the data portion from both the first and second ROMs are provided to the shift unit 709. The shift unit 709 operates on the data portions the same as in the preferred embodiment and that will not be described again.

[0071] While the preferred embodiment of the invention has been illustrated and described, it will be appreciated that various changes can be made therein without departing from the spirit and scope of the invention. For example, although in the two embodiments described above, one or two ROMs are used, four or even eight ROMs may be used, each acting on 2-bits and 1-bit, respectively. Further, the data output by the ROMs may be examined to determine if there has been a bit stuffing error by looking for predetermined patterns.