Forward error correction using coding and redundant transmission

Abstract

A forward error correcting digital transmission system having two separate transmission channels carrying redundant information. The signal on the first channel is encoded by combining each present bit with itself delayed m bits in time. The signal on the second channel may be encoded in the same manner only with a delay of n bits in time, or left without coding, i.e., n=0, in any case m and n are unequal integers. Both first and second channels are transmitted over separate transmission paths to the receiving terminal where each is independently decoded to obtain the original binary information from each received encoded signal. If an error is introduced into one of the channels during transmission, the encoded information necessarily contains an error in the present bit and its associated m or n delayed bit. Upon detection of an error by simple bit comparisons between the two decoded channels, the present decoded bit and its associated delayed decoded bit, if any, are changed in the apropriate channel in order to correct for the error.

What is claimed is: 
     
       1. In a digital data transmission system having a transmitting terminal, a receiving terminal, a transmission path connecting the two terminals, and a source of binary data at said transmitting terminal, apparatus for performing forward error correction, which comprises: means for converting said binary data into redundant first and second binary pulse trains;   encoding means adapted to accept said first and second binary pulse trains for independently encoding said binary data in said first and second binary pulse trains to obtain first and second encoded binary pulse trains that provide different error propagation intervals in each encoded pulse train;   means, at said receiving terminal, for separately decoding said first and second encoded binary pulse trains to obtain third and fourth binary pulse trains, each of which contains the original binary data absent the effect of path error introduction in said transmission path;   means for comparing bit occurrences in said third and fourth decoded binary pulse trains to determine if an error has occurred;   means responsive to a detected error and to subsequently detected errors occurring at said error propagation intervals to determine in which said data channel said path error occurred; and   means for correcting the bits in the decoded pulse train in which said errors have occurred.   
     
     
       2. In a digital data transmission system having a two-channel transmitter, a two-channel receiver, a transmission path for interconnecting said transmitter to said receiver, and a source of binary data, apparatus for performing forward error correction, comprising: means for converting said binary data into redundant first and second binary pulse trains;   encoding means coupled to said converting means and to said two-channel transmitter for encoding independently said first and second binary pulse trains, said encoding means generating a first encoded pulse train by combining said first binary pulse train with said first encoded pulse train delayed m bits in time, where m equals a non-zero integer, and said encoding means also generating a second encoded pulse train by combining said second binary pulse train with said second encoded pulse train delayed n bits in time, where n is an integer different from m;   decoding means coupled to said two-channel receiver for independently decoding the encoded binary data, said decoding means generating separate third and fourth binary pulse trains;   comparison means for comparing each binary pulse in said third binary pulse train with a corresponding binary pulse in said fourth binary pulse train and generating an error signal when there is a lack of correspondence between said third and fourth binary pulse trains;   detection means responsive to said error signal and to a delay interval between successive error signals for determining which binary pulse train contains an error; and   means for selectively correcting errors in said third and fourth binary pulse trains in response to said detection means and thereby producing a received pair of binary pulse trains free of errors in transmission.   
     
     
       3. In a digital system which has first and second parallel transmission channels, thus permitting simultaneous redundant transmission of serial binary data, from a data source, between transmitting and receiving ends of said system, apparatus for performing forward error correction, which comprises: an encoder which accepts the binary information for processing at an input terminal from which said information is simultaneously applied to two divergent paths, in which only one of the paths includes a coding device in which the present digit is combined with its previously encoded digit delayed by m bits, the information processed in said first and second paths appearing at first and second output terminals;   transmission means having first and second input terminals adapted for connection to said first and second encoder output terminals, for conditioning said processed information for simultaneous transmission over separate channels to a receiving terminal;   receiving means, having an input connected to receive said conditioned information, for providing at first and second output terminals, respectively the original binary information and the encoded information, absent errors introduced in transmission between said transmitting and receiving ends;   a decoder having first and second input terminals connected, respectively, to the first and second output terminals of said receiving means, said decoder including a device in one path decoding means in which a present encoded digit is combined with its own encoded digit delayed by m bits so as to provide, at first and second output terminals, signals which are identical to the original binary information, absent errors introduced in transmission;   storage means having first and second input terminals connected, respectively, to the first and second output terminals of said decoder, for storing at least (m+1) bits from said first path in a first storage element and a like number of bits from said second path in a second storage element, said storage means having third and fourth input terminals connected to the first and (m+1) cell of first storage element, and a fifth input terminal connected to the (m+1) cell of said second storage element;   means connected to said storage means for detecting error occurrences in said first and second paths and providing an error signal at an output when errors occur; and   means responsive to said error signal for applying error correction signals to said third, fourth and fifth terminals to correct error appearances in the appropriate one of said paths.   
     
     
       4. In a digital data system for the transmission of binary information, apparatus for correcting errors, comprising: an encoder which accepts the binary information at an input terminal and provides at a first output terminal a first encoded binary signal in which the present digit is combined with a past encoded digit delayed by m bits and at a second output terminal a second encoded binary signal in which the present digit is combined with a past encoded digit delayed by n bits; where m and n are unequal integers and either m or n may be 0;   a transmitter which accepts said first and second encoded binary signals and conditions them for simultaneous transmission to a receiving terminal;   a receiver having an input connected to receive said conditioned signals and providing at first and second output terminals the first and second encoded binary signals;   a decoder, having first and second input terminals connected, respectively, to the first and second output terminals of said receiver, and providing at first and second output terminals of said decoder decoded signals which are identical to the transmitted data absent errors introduced in transmission or recovery;   storage means having first and second input terminals connected, respectively, to the first and second output terminals of said decoder, for storing at least (n+1) bits from said first output terminal of said decoder in a first storage element, and at least (n+1) bits from said second output terminal of said decoder in a second storage element, said storage means having third and fourth input terminals connected to the first and (m+1) cells of said first storage element, and fifth and sixth input terminals connected to the first and (n+1) cells of said second storage element;   means connected to said storage means for detecting error occurrences appearing at said decoder first and second output terminals and providing an error signal at an output when errors occur; and   means responsive to said error signal for applying error correction signals to said third and fourth, and fifth and sixth input terminals of said storage means as appropriate to correct error appearances in the appropriate one of said storage elements.   
     
     
       5. Apparatus as set forth in claim 4 wherein said means for detecting comprises: a comparator having first and second input terminals connected, respectively, to said first and second output terminals of said decoder, said comparator provided said error signal at said output of said detecting means only when the binary states simultaneously appearing on the two decoder output terminals are unlike.   
     
     
       6. Apparatus as set forth in claim 5 wherein said means responsive comprises: a third storage element having an input terminal connected to the output terminal of said comparator, said third storage element having at least either (m+1) or (n+1) cells, whichever is larger;   a first logic circuit having first and second input terminals connected to the first and (m+1) cells of said third storage element, and having an output terminal connected to the first and (m+1) cells of said first storage element; and   a second logic circuit having first and second input terminals connected to the first and (n+1) cells of said third storage element, and having an output terminal connected to the first and (n+1) cells of said second storage element.   
     
     
       7. Apparatus as in claim 4 wherein said encoder comprises: a first exclusive-OR gate having one input connected to the encoder input terminal, having an m bit delay element connected between the output and a second input of said first exclusive-OR gate and providing a first encoded binary signal at said first output terminal; and     a second exclusive-OR gate having one input connected to the encoder input terminal, having an n bit delay element connected between the output and a second input of said second exclusive-OR gate and providing a second encoded binary signal at said second output terminal.   
     
     
       8. Apparatus as in claim 4 wherein said decoder comprises: a third exclusive-OR gate having one input connected directly to the first decoder input terminal, having an m bit delay connected between said first encoder input terminal and a second input to said third exclusive-OR gate, and having the output of said third exclusive-OR gate connected to the decoder first output terminal; and   a fourth exclusive-OR gate having one input connected directly to the second decoder input terminal, having an n bit delay connected between said decoder second input and a second input to said fourth exclusive-OR gate, and having the output of said fourth exclusive-OR gate connected to the decoder second output terminal.   
     
     
       9. In a digital transmission system adapted to accept and condition serial binary data from a data source for transmission over an appropriate transmission path, said system having a transmitting and receiving terminal end interconnected by said transmission path, apparatus for performing forward error correction, which comprises: an encoder adapted to accept, at an input terminal, said serial binary data and first to convert said data into redundant first and second binary pulse trains, respectively, and then separately converting said first and second binary pulse trains into first and second encoded binary pulse trains which appear at first and second output terminals, each of said encoded pulse trains containing the same information as was contained in said serial binary data, and said encoder introducing a different predetermined error propagation interval in each of said encoded pulse trains which will affect any error introduced following encoding of the encoded pulse train;   a decoder, at the receiving terminal end, having first and second input terminals adapted to accept said first and second encoded binary pulse trains and to provide, at first and second output terminals, respectively, first and second decoded binary pulse trains containing the original binary data from said data source and transmission errors, said transmission errors causing an error at the bit time slot of the error occurrence and at said predetermined error propagation interval only for the pulse train in which the error occurs; and   an error corrector having first and second input terminals connected, respectively, to the first and second output terminals of said decoder, said error corrector being responsive to the error occurrences and to each predetermined error propagation interval of the decoded binary pulse trains so as to determine in which pulse train an error was introduced and to effect correction of the detected error.   
     
     
       10. Apparatus as set forth in claim 9 wherein said encoder comprises: means for separating the serial binary data into redundant first and second binary pulse trains which are available, respectively, at first and second output terminals of said separating means;   an m digit delay circuit having an input terminal and an output terminal;   an exclusive-OR gate having one input terminal connected to the first output terminal of said separating means, having an output terminal connected to the first output terminal of said encoder and to the input terminal of said m delay circuit, and having a second input terminal connected to the output terminal of said m delay circuit, whereby an encoded binary pulse train is provided at said exclusive-OR gate output terminal; and   a through path between said second output terminal of said separating means and the second output terminal of said encoder, whereby the second binary pulse train is not encoded.   
     
     
       11. Apparatus as set forth in claim 10 wherein said error corrector comprises: first and second storage elements each having (m+1) cells, numbered from 1 to (m+1) from the input terminal, the input to the first storage element being connected to the decoder first output terminal and the input to the second storage element being connected to the decoder second output terminal;   a second exclusive-OR gate having first and second inputs connected respectively to the first and second output terminals of said decoder, said second gate providing a pulse at its output when the inputs are of unlike states indicating an error occurrence;   a third storage element having (2m+1) cells numbered consecutively from 1 to (2m+1) from the input, said input being connected to the output of said second exclusive-OR gate, and the state of the output of said second gate being stepped through said third storage element at the binary data rate;   a first logic circuit having first and second inputs, respectively, connected to the first and (m+1) cell outputs of said third storage element and having an output connected to both the first and (m+1) inputs of said first storage element, said first logic circuit complementing the bits stored in said first and (m+1) cells of said first storage element when an error pulse appears in both the first and (m+1) cells of said third storage element; and   a second logic circuit having first, second and third inputs, respectively, connected to the first, (m+1) and (2m+1) cell outputs of said third storage element and having an output connected to the (m+1) cell input of said second storage element, said second logic circuit complementing the bit stored in said (m+1) cell of said second storage element when a pulse appears in the (m+1) cell and the first and (2m+1) cells are pulse free.   
     
     
       12. Apparatus as set forth in claim 9 wherein said encoder comprises: means for separating the serial binary data into said first and second binary pulse trains which are available, respectively, at first and second output terminals;   a delay circuit having p storage cells and having an input terminal connected to the first cell, a first output terminal connected to the pth cell, and having a second output terminal connected to the qth cell, where q is an integer less than p;   a first exclusive-OR gate having a first input terminal connected to the first output terminal of said separating means, having a second input terminal connected to the first output terminal of said delay circuit, and having an output terminal;   a second exclusive-OR gate having a first input terminal connected to the output terminal of said first exclusive-OR gate, having a second input terminal connected to the second output terminal of said delay circuit and providing an encoded binary signal at an output terminal; and   a through path between said second output terminal of said separating means and the second output terminal of said encoder, whereby the second binary pulse train is not encoded.   
     
     
       13. Apparatus as set forth in claim 12, wherein said error corrector comprises: first and second storage elements each having at least (p+3) cells, numbered from 1 to (p+3) from the input terminal, the input to the first storage element being connected to the decoder first output terminal, and the input to the second storage element being connected to the decoder second output terminal;   a third exclusive-OR gate having first and second inputs connected, respectively, to the first and second output terminals of said decoder, said third gate providing a pulse at its output when the inputs are of unlike states indicating an error occurrence;   a third storage element having at least (p+3) cells numbered consecutively from 1 to (p+3) from the input, said input being connected to the output of said third exclusive-OR gate, and the state of the output of said third gate being stepped through said third storage element at the binary data rate;   a first logic circuit having first, second and third inputs, respectively, connected to the first, (q+1) and (p+1) cell outputs of said third storage element, having a first output terminal connected to the inputs of the first, (q+1) and (p+1) cells of said first storage element, said logic circuit complementing the bits stored in said first, (q+1) and (p+1) cells when an error pulse appears in the first, (q+1) and (p+1) cells of said third storage element, and a second output terminal connected to the second, (q+2) and (p+2) cells of said third storage element, a clearing pulse being provided following the detection of an error in said first path, whereby the error pulses are deleted from the cells of the third storage element.   
     
     
       14. Apparatus as set forth in claim 13 wherein said first logic circuit comprises: an AND-gate having first, second and third inputs connected, respectively, to said first, (q+1) and (p+1) cells of said third storage element and having an output; and   a one bit delay circuit having an input connected to the output of said AND-gate and having an output connected to the input of the second, (q+2) and (p+2) cells of said third storage element, whereby the detection of an error by correspondence of these error pulses at the inputs to AND-gate provides a clearing signal to eliminate these error pulses as they are transferred to the next cell.   
     
     
       15. Apparatus as in claim 9 wherein said error corrector comprises: a comparator having first and second inputs connected, respectively, to the first and second input terminals of said error corrector, said comparator providing an error signal to an output terminal when bits in corresponding time slots of the decoded binary pulse trains are unlike;   a first storage means including a plurality of storage cells for temporarily storing a predetermined number of bits obtained from the output terminal of said comparator, said bits being shifted from cell to cell at the binary rate, and having a first and second set of parallel output terminals each set being separately connected to appropriate cells of said first storage means so that each set has their connections spaced apart by the appropriate predetermined error propagation intervals, respectively, for said first and second pulse trains;   a first error correction circuit having a first input terminal connection to the first input terminal of said error corrector, having second and third input terminals connected to said first set of output terminals from said first storage means, and having an output terminal;   a second error correction circuit having a first input terminal connected to the second input terminal of said error corrector, having second and third input terminals connected to said second set of output terminals of said first storage means, and having an output terminal.