Patent Publication Number: US-4924463-A

Title: Data coding method for use in digital communication systems

Description:
BACKGROUND OF THE INVENTION 
     This application is a continuation-in-part of application Ser. No. 318,463, filed Mar. 2, 1989, now abandoned, which is a continuation of application Ser. No. 176,314, filed Mar. 31, 1988, now abandoned. 
    
    
     The present invention relates, in general, to a data coding technique for use with a digital communication system, such as a serial baseband data link. 
     In the transmission of digital data, coding schemes are often employed to improve the reliability, efficiency, and fault tolerance of the data transmission. In addition, coding schemes can be employed to aid in the synchronization of the data transmission and reception. Examples of such coding techniques are Manchester, Biphase and delay modulation. 
     Most of these prior coding techniques suffer from one or more drawbacks. For example, in the Manchester code, transitions are added to the data for clocking purposes. The result is that in a worst case data pattern, the encoded data contains twice as many transitions as the number of bits in the original data. This reduces the efficiency of the code to 50 percent, where efficiency is defined as the ratio of the number of bits in the original data word, to the number of transitions in the corresponding encoded data word. This is undesirable since the additional transitions add both cost and time to the transmission of the data. 
     The Manchester code does, however, provide a constant 50 percent duty cycle, where the duty cycle is defined as the ratio of the number of 1&#39;s in a data stream, to the total number of bits in the data stream. Control of the duty cycle is desirable for a number of reasons. For one thing, signal variances that may occur in the transmission medium from cable losses, or transmitter strength, for example, affect the signal strength at the receiver. If the duty cycle is relatively fixed, it is easier to pinpoint and compensate for these losses, and compensation can be achieved with simpler circuitry. Simpler circuitry in turn enables the transmission circuit to run at a higher bit rate, which reduces transmission cost and time. 
     Many other prior codes, in the interest of improving efficiency, do not provide control over the duty cycle, and, in view of the foregoing, are undesirable. Similarly, many of these codes do not provide sufficient information for reliable clock recovery for worst case data patterns, nor do they provide synchronizing words to enable the receiver circuitry&#39;s clock to detect loss of synchronization and to resynchronize with the incoming data stream in the event of an interference or fault induced break in a signal transmission. 
     Most of the prior coding techniques have thus provided an undesirable trade-off between efficiency, clocking information, and duty cycle control. 
     In an effort to provide a code which attempts to minimize the above drawbacks, Sperry/UNISYS recently developed a &#34;4B/5B&#34; NRZI code which encodes every four bits of data into a five bit code symbol. In addition, other &#34;out-of-band&#34; five bit code symbols that do not correspond to one of sixteen possible four bit words, are utilized for synchronization, control, or line indication. The resulting code has an efficiency of 80 percent (5 bit code for every 4 bit word), maintains the duty cycle between 40 and 60 percent (2 or 3 1&#39;s in every 5 bit code symbol), and includes sufficient clocking information for reliable clock recovery. The 4B/5B code works well, but provides only a single logical channel, and only one pair of out-of-band symbols for self synchronization. 
     SUMMARY OF THE INVENTION 
     The present invention is an improved digital data coding method, which provides high efficiency control over the duty cycle and a plurality of dual purpose synchronizing words. In addition, one embodiment of the invention provides plural data channels. Specifically, in a first embodiment of the present invention, a 4B/1/6B is provided which, like the Sperry 4B/5B code, maps every four bits of data into a five bit code symbol (but with a different map). Unlike the Sperry code, however, a second logical channel is provided which is composed of single bits that are placed after each five bit symbol (every sixth bit of the data stream). The data on the second channel can be arbitrarily selected as desired and can include, for example, information from additional communication sources, or control information between the various elements of a communication system. 
     Also, unlike the Sperry 4B/5B code, the 4B/1/6B code additionally includes a plurality of twelve bit out-of-band synchronizing words that are useful in establishing and maintaining the synchronization of a communication link. Each of these synchronizing words includes a pair of five bit symbols which are selected from the sixteen out-of-band five bit symbols that do not correspond to one of the sixteen possible four bit data words. The selection of the pairs of out-of-band symbols is such that the resulting bit sequences can only occur where they are placed in a data stream even when the symbol boundaries are not known. Thus, they are easily recognizable by computer circuitry, and so can be used for synchronization of a receiver with an incoming data stream. In the first embodiment there are four possible twelve bit synchronizing words that meet the above criteria. 
     By providing a plurality of self-synchronizing out-of-band synchronizing words, the versatility of the present coding method is substantially increased. Not only can the synchronizing words be utilized for synchronization, they can also be utilized for control information, as well. For example, a first of the synchronizing words can be used to initially synchronize a communication link&#39;s symbol boundary and control state; a second can be used to indicate that the link is idle; a third can be used to indicate that the link is waiting for a signal transmission; and, a fourth can be inserted into the data stream periodically to insure that synchronization is maintained. 
     Like the Sperry 4B/5B code, the efficiency of the 4B/1/6B code is 80 percent for channel one data. Since channel two data is arbitrarily selected, it can be set to an efficiency of 80 percent, which will make the combined efficiency of both channels, also 80 percent. Similarly, the duty cycle of the encoded channel one data, ranges between 40 and 60 percent (2 or 3 1&#39;s per 5 bit code symbol), and, by setting the duty cycle of the channel two data to be the same, the duty cycle of the combined channel one and two data stream will also be 40 to 60 percent. The 4B/1/6B code has the further advantage that the maximum consecutive number of either one&#39;s or zero&#39;s (run length) in the encoded signal is always limited to at most 5. This limit makes it easier for the receiver to synchronize to the signal and to recover clocking information than if no limit was imposed. 
     The second embodiment of the invention is a 4B/5B code like Sperry&#39;s code, and uses the same group of in-band symbols that the 4B/1/6B code uses. However, only a single channel of data is provided. Since it is a 4B/5B code, it too has an efficiency of 80%. The duty cycle varies between 40% and 60% and its maximum run length is 4 since there is no second channel of data. Unlike Sperry&#39;s 4B/5B code, this 4B/5B code is a NRZ code (Sperry&#39;s is a NRZI code). An NRZ code has the advantage that each bit is independently coded, whereas NRZI code bits are not. Hence, a single bit error can affect only one symbol in an NRZ code, but may affect two symbols in an NRZI code. The present 4B/5B code also has a much larger set of individual synchronizing words and mutually compatible sets of synchronizing words. The synchronizing words are formed from pairs of five bit symbols, and each pair includes at least one out-of-band five bit symbol. 
     The third embodiment of the invention is a &#34;balanced&#34; 4B/6B code having a fixed 50% duty cycle in which every four bits of data are mapped to a six bit code word. This balanced code is advantageous because it allows inexpensive code translation between links which require a 50% duty cycle, and those requiring a 40 to 60% duty cycle. The balanced 4B/6B code is derived from the two channel embodiment of the invention by choosing the second channel bits to provide a 50% duty cycle. The resulting code is advantageous in that it provides up to 70 synchronizing words. Its efficiency is 66.7%, and its maximum run length is 4 or 5, depending on which of the 70 synchronizing words are used. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The features and advantages of the present invention will become apparent to those of skill in the art from the following more detailed consideration thereof, taken in conjunction with the accompanying drawings, in which: 
     FIG. 1 is a table showing the five bit in-band code symbols which are used to encode each of sixteen possible four bit data words in the first and second embodiments of the invention; 
     FIG. 2 is an illustration of a sample data stream encoded in accordance with the first embodiment of the present invention; 
     FIGS. 3A and 3B are tables illustrating synchronizing words for the first embodiment of the invention that use out-of-band symbol pairs; 
     FIGS. 4A and 4B are tables illustrating control words for the first embodiment which are formed from other symbol pairs that can be utilized for miscellaneous control purposes; 
     FIG. 5 is a general block diagram of a digital communication system for implementing the disclosed coding methods; 
     FIG. 6 is a table of synchronizing words for a second embodiment of the present invention; 
     FIGS. 7A and 7B are tables of example sets of mutually compatible synchronizing words selected from the table of FIG. 6; 
     FIG. 8 is a table of in-band code symbols for a third embodiment of the present invention; 
     FIG. 9 is a table of synchronization words for the third embodiment; 
     FIG. 10 is a table of an example set of mutually compatible synchronizing words selected from the table of FIG. 9; and, 
     FIGS. 11A and 11B are tables of control words for the second and third embodiments of the invention, respectively. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Turning now to a more detailed consideration of the present invention, there is illustrated in FIG. 1, a table of sixteen five bit in-band code symbols that are utilized to encode each of sixteen possible four bit data words. As shown, there is no particular assignment of these code symbols to the individual data words, and such a selection can be arbitrarily made as desired (the decimal numbers to the left of each entry are for reference purposes only). 
     The key feature of these sixteen in-band symbols is that each of them includes either 2 or 3 1&#39;s, which means each of the code symbols has a duty cycle (ratio of 1&#39;s to total number of bits) of either 40 or 60 percent. This is significant because selection of the code symbols in this manner means that the duty cycle of an encoded data stream will be maintained close enough to 50 percent, that any significant variances in the received signal strength can be attributed to other factors such as transmission cable losses, variances in transmitter strength, etc. Being able to pinpoint the cause of signal strength variances enables the communication circuitry to be designed and operated more simply and efficiently, which in turn reduces cost. Also, a data transmission having a duty cycle which remains fairly close to 50 percent can be transmitted at a higher bit rate, which saves time, and again, reduces cost. 
     FIG. 2 illustrates a sample data stream that is encoded according to a first embodiment of the present invention, which can be termed a 4B/1/6B code. As shown, the data stream includes two channels (one and two) of data that are interleaved with one another in a time division multiplex manner. Channel one data includes five bit encoded symbols from the table in FIG. 1, while channel two includes single bits that are placed in the data stream every six bits, and are marked with an &#34;x&#34; to indicate that any arbitrary choice of a &#34;0&#34; or &#34;1&#34; can be placed at those positions. 
     As stated above, the duty cycle of the code symbols in FIG. 1, and therefore of the channel one data stream, varies between 40 and 60 percent. The efficiency of the channel one data stream is 80 percent, since every four bit data word is mapped to a five bit code symbol. From this, it is easy to see that the entire data stream can also have a duty cycle of 40 to 60 percent, and an efficiency of 80 percent, if the channel two data is also chosen to meet these criteria. This can easily be accomplished by encoding the channel two data with the same encoding scheme represented in the FIG. 1 table (every four bits of channel two data would be encoded as five bits in accordance with FIG. 1). 
     The two channel scheme illustrated in FIG. 2 can serve a number of useful purposes. Often times, a communication link requires more than one channel so that more than one source can transmit data over the same link. In other cases, the second channel is useful for transmitting control information between elements of a communication system without interfering with the data transmission. Examples of such control information include data requests, receiver connection or disconnection, flow control, etc. 
     Turning now to FIG. 3A, there is illustrated a table of ten twelve bit synchronizing words for the 4B/1/6B code. Each of these synchronizing words includes a pair of out-of-band five bit symbols (out-of-band meaning that they are not in the set of in-band symbols in FIG. 1 that are used for data encoding), and a pair of channel two data bits. The channel two bits can be arbitrarily chosen as indicated by the x&#39;s placed at the channel two positions in those words. These synchronizing words have the property that their bit patterns will only appear, regardless of symbol boundaries, where they are placed in a data steam if they are used individually. This is not necessarily the case, however, if more than one of the ten synchronizing words are placed in a data stream. 
     Turning now to FIG. 3B, there is illustrated a subset of four special &#34;mutually compatible&#34; twelve bit synchronizing words that are chosen from the set of FIG. 3A. Each of these synchronizing words, labeled S1, S2, S3, and S4, are termed &#34;mutually compatible&#34; because they are pairs that result in the synchronizing words having the following unique property. If SW represents any one of the four synchronizing words, then if an encoded data stream is constructed from exactly n occurrences of SW along with an arbitrary number and combination of any or all of the other symbols and symbol pairs from the tables illustrated in FIGS. 1, 3B, and either 4A or 4B, along with an arbitrary bit value every six bit positions for channel 2 (with the  exception of the fixed channel two bit values for S4), then the bit pattern SW will occur exactly n times in the resulting encoded string regardless of symbol boundaries. S1, S2, S3, and S4 can thus be easily recognized in a data stream and, as will be discussed in further detail below, employed to maintain synchronization of a receiving device with an incoming data stream. Also, the duty cycle of S1 and S2 will remain in the 40 to 60 percent range, regardless of the data on channel two. 
     The advantage of having a plurality of different synchronizing words is that they can also serve other purposes, as well. If the present invention is employed in a flow controlled full duplex data link for example, S4 can be utilized to initially synchronize the communication link&#39;s symbol boundary and control state. Since the channel two data in S4 is fixed, S4 can be used to reset the state on channel two when channel two is used as a control channel. 
     Of the remaining synchronizing words, one can be used to indicate that the link is idle; a second used to indicate that the link is waiting to receive requested data; and, a third can be placed periodically in the data stream to insure that synchronization can be quickly regained and maintained in case of loss due to noise induced transients, or the like. 
     FIGS. 4A and 4B illustrate two groups of other symbol pairs which form control words that can be utilized for miscellaneous communications link control. Again, as with FIG. 1, the decimal numbers to the left of each entry in these tables are for reference purposes only. The table in FIG. 4A is structured so that the entries in each subgroup have a common left symbol in channel one. These left symbols were selected from out-of-band symbols so that these entries can be easily recognized in a mixed stream of FIG. 1 data symbols. Similarly, the entries in each group in FIG. 4B have been selected for the same reason so that their right symbols in channel one are selected from out-of-band symbols. It is intended that control words be chosen either from FIG. 4A or from FIG. 4B, but not from both. 
     Turning now to FIG. 5, there is illustrated a general block diagram of a communications system and link that employs the present invention. Specifically, there is shown in FIG. 5, a communication system 10, which includes a transmitter and encoder circuit 12. Circuit 12 includes a four line input bus 14 for channel one data, which arrives from a source (not shown) in the form of four bit binary words, and is fed to an encoder 16. Encoder 16 includes a table lookup ROM or PLA (programmable logic array) for encoding each four bits of data into the corresponding five bit code symbol of FIG. 1. 
     Also fed to encoder 16 is the single bit channel two data which arrives on an input line 18. An optional encoder 20, which can be similar to encoder 16, can be provided if desired to encode the channel two data before it is fed to encoder 16. It should be noted that the channel two data passes through encoder 16 unaltered, and is only fed thereto, to enable it to be combined with the channel one data. 
     Similarly a third input is provided to encoder 16 in the form of a multiple line bus 17 so that synchronizing words S1, S2, S3, or S4, along with the control words illustrated in FIG. 4A or 4B, can be passed through encoder 16 for controlling and synchronizing the link. 
     The six bit output from encoder 16 is composed of five bit symbols for channel one data, synchronizing words, and control words in addition to the single bit for channel two. It is fed through a six line bus 22 to a parallel to serial converter 24. The output from converter 24 is a serial data stream like that shown in FIG. 2, and is transmitted via a serial communication link 26 to a receiver and decoder circuit 28. 
     Receiver and decoder circuit 28 includes a serial to parallel converter 30 which reconverts the incoming data stream into six bit words, and feeds them through a six line bus 32 to a decoder 34. The data stream arriving on link 26 is also fed to a comparator circuit 36, which monitors a 12 bit wide window of the incoming data to sense the synchronizing words, S1, S2, S3, and S4, that are illustrated in FIG. 3B. 
     A start of symbol control output 38 is fed, in response to detection of one of the synchronizing words, from comparator 36 to a sync input 40 on serial to parallel converter 30. This permits the operation of converter 30 to be properly synchronized with the incoming data stream so that it can determine the boundaries between each arriving code symbol. An output bus 41 is also provided on comparator 36 for outputting any received synchronizing words to an external device (not shown). 
     Decoder 34, like encoder 16, includes a table lookup ROM or PLA to permit the incoming five bit symbols to be reconverted to the original four bit data words, and fed via a four line output bus 42 to a data receiving element (not shown). Channel two data is fed through decoder 34 to a single output line 44, and through an optional decoder 46 if the channel two data has been previously encoded, to a data receiving element (not shown). 
     Another output bus 48 is provided on decoder 34 for outputting any of the control words in FIG. 4A or 4B that are received. This output is combined with the second output 41 from comparator 36, and can be fed to an external device (not shown) for control and synchronization purposes. 
     In a second embodiment of the invention, the second data channel is not employed, and the resulting code is a 4B/5B NRZ code. This code utilizes the in-band code symbols of FIG. 1, and up to thirty individual synchronizing words as illustrated in FIG. 6. These thirty synchronizing words can be used individually with any of the in-band code symbols of FIG. 1 and be recognized in the data stream, although they may not necessarily be used in combination with other synchronizing words of FIG. 6. 
     Turning now to FIGS. 7A and 7B, two sets of mutually compatible synchronizing words are illustrated, both of which are chosen from FIG. 6 as indicated by the entry numbers. The elements of these sets of synchronizing words can be used in combination with each other and have the same properties as the synchronizing words for the 4B/1/6B code illustrated in FIG. 3B. It should be understood that there are numerous other combinations of mutually compatible synchronizing words, and the sets illustrated in FIGS. 7A and 7B represent only two examples of these combinations. 
     The in-band code symbols for a third embodiment of the present invention are illustrated in FIG. 8. This code is a 4B/6B code and has a balanced 50% duty cycle. The code symbols are derived from those of FIG. 1 by simply adding a leading 0 or 1 as needed to make the number of 1&#39;s and 0&#39;s in each symbol equal. The resulting code is a specialization of the 4B/1/6B code where the second channel bit has been set to a specific value for all in-band channel one symbols. 
     The 4B/6B balanced code has 70 individual twelve bit synchronizing words which are illustrated in FIG. 9. From this set, a large number of mutually compatible sets of synchronizing words having the same properties of the synchronizing words in FIG. 3 for the 4B/1/6B code can be selected. An example of a mutually compatible set of synchronizing words is illustrated in FIG. 10. The number of synchronizing words in the set of FIG. 10 is larger than that of FIG. 3B because the second channel &#34;x&#34; bits now have specific values. Many other mutually compatible subsets of the FIG. 9 set exist including sets which contain more words than the set of FIG. 10. 
     As an example of a 4B/5B code set for use in a communications data link, the in-band symbols of FIG. 1 can be used with the following set of mutually compatible synchronizing words from FIG. 7B that are chosen to independently code 2 bits of additional control information, w and v, in a highly redundant manner: 
     
         ______________________________________                                    
w           v          Entry # from FIG. 7B                               
______________________________________                                    
w = 01111   01100 = v  15                                                 
w = 01111   00010 = vbar                                                  
                       13                                                 
wbar = 10000                                                              
            11101 = v  18                                                 
wbar = 10000                                                              
            10011 = vbar                                                  
                       16                                                 
______________________________________                                    
 
    
     Thus, w=01111, wbar=10000, v=x110x, and vbar=x001x. The w code has Hamming distance 5 which means 3 bit errors within the symbol can be corrected. The v code has Hamming distance 3 which means 1 bit errors within the symbol can be corrected. 
     In addition, the following out-of-band words can be used for control information without affecting the mutually compatible set properties: 
     
         ______________________________________                                    
Word                  Information Conveyed                                
______________________________________                                    
10111     00100       Start of Packet                                     
01000     11011       End of Packet                                       
10111     00010       Idle Channel                                        
01000     11101       Pad                                                 
______________________________________                                    
 
    
     The above control words, along with a number of other control words that are compatible with this example set of 4B/5B synchronizing words are illustrated in FIG. 11A. 
     As an example of a 4B/6B balanced code, the in-band symbols of FIG. 8 can be combined with the following mutually compatible synchronizing words chosen from FIG. 10 to also independently code 2 bits of additional code information, w and v, in a highly redundant manner: 
     
         ______________________________________                                    
w           v       Entry # from FIG. 10                                  
______________________________________                                    
001111      001100  11                                                    
001111      100010  14                                                    
110000      011101  57                                                    
110000      110011  60                                                    
______________________________________                                    
 
    
     These synchronizing words differ from those in the 4B/5B example above by the addition of the leading balance bit which provides the 50% duty cycle. As with the 4B/5B example above, the following other out-of-band words can be used for control information without affecting the mutually compatible set properties: 
     
         ______________________________________                                    
Word                  Information Conveyed                                
______________________________________                                    
010111    100100      Start of packet                                     
110111    000100                                                          
001000    111011      End of packet                                       
101000    011011                                                          
010111    100010      ldle Channel                                        
110111    000010                                                          
001000    111101      Pad                                                 
101000    011101                                                          
______________________________________                                    
 
    
     As illustrated, two different words are specified for each function. They differ from one another only by the leading balance bit in each of the two six bit symbols that make up the words. Either of the two words can be used for the specified functions. These control words, along with other control words that are compatible with the 4B/6B synchronizing words of this example are illustrated in FIG. 11B. 
     As thus can be seen from the foregoing, the present invention provides an improved data encoding method which possesses a high efficiency, has good duty cycle control, and is very versatile by virtue of the two channel scheme in the first embodiment, and multiple synchronizing words in all three embodiments that can be employed both for data synchronization and control information transmission. 
     Although the invention has been illustrated in terms of preferred embodiments, it will be understood that numerous variations and modifications can made by those of skill in the art without departing from the true spirit and scope thereof as set forth in the following claims.