Automatic synchronization recovery for data systems utilizing burst-error-correcting cyclic codes

Claim 2

In combination in a data communication system: a source of data signals; means for encoding said signals in a burst-error-correcting cyclic code capable of correcting error burst of b symbols in length; means for adding to each encoded word a predetermined digital sequence; means for applying the digital sequences obtained from said addition to one end of a communication channel; means connected to the other end of said channel for subtracting from each received sequence the said predetermined digital sequence; means for decoding the sequence obtained from said subtraction to obtain error patterns indicating the occurrence of errors at each end of said received sequences; and synchronization recovery means responsive to the generation of said error patterns for correcting loss of synchronization of b-2 symbols in said communication system.

Claim 3

A combination as in claim 1 in which said decoding means further comprises means for generating error patterns indicating the occurrence of error bursts of length i in said received sequences, where i is any integer b.

Claim 4

A combination as in claim 2 further comprising means responsive to the generation of said burst-error patterns for correcting the errors in said received sequences.

Claim 5

In combination in a data communication system; a source of data signals; means for encoding said signals in an (n,k) burst-error-correcting cyclic code capable of correcting error bursts of b symbols in length; means for adding to each encoded word a preselected digital sequence represented by P(x) Alpha + Beta xn 1, where Alpha and Beta are code symbols 0; means for applying the sequences obtained from said addition to one end of a transmission channel; receiving means connected to the other end of said channel for receiving said sequences means connected to said receiving means for subtracting said preselected digital sequence from each received digital sequence; error locator means for processing the digital sequences obtained from said subtraction to obtain error pattern words for each of said received sequences; and synchronization correcting means responsive to said error locator means determining that the positions represented by xn 1 of a received digital sequence contains the symbol - Beta and that the next higher order position xr which contains a nonzero symbol contains the symbol Alpha , where r b-2, for advancing the synchronization of said data communication system r symbols, and responsive to said error locator means determining that the positions represented by x0 contains the symbol -Alpha and that the next lower order position xn r 1 which contains a nonzero symbol contains the symbol Beta , for back-setting the synchronization of said system r symbols.

Claim 6

In combination in a data communication system; a source of data signals; means for encoding said signals in an (n,k) burst-error-correcting cyclic code capable of correcting error bursts of b symbols in length; means for adding to each encoded word a preselected digital sequence represented by P(x) Alpha + Beta xn 1, where Alpha and Beta are code symbols 0; means for applying the sequences obtained from said addition to one end of a transmission channel; receiving means connected to the other end of said channel for receiving said sequences means connected to said receiving means for subtracting said preselected digital sequence from each received digital sequence; error locator means for processing the digital sequences obtained from said subtraction to obtain error pattern words for each of said received sequences; and synchronization correcting means responsive to said error locator means determining that the positions represented by xn 1 of a received digital sequence contains the symbol - Beta and that the next higher order position xr which contains a nonzero symbol contains the symbol Alpha , where r b-2, for advancing the synchronization of said data communication system r symbols, and responsive to said error locator means determining that the positions represented by x0 contains the symbol -Alpha and that the next lower order position xn r 1 which contains a nonzero symbol contains the symbol Beta , for back-setting the synchronization of said system r symbols.

Claim 7

A combination as in claim 4 further comprising means connected to said adding means for interleaving said encoded words before applying said words to said transmission channel, and means connected to said receiving means for deinterleaving the received interleaved sequences before applying said sequences to said subtracting means.

Claim 8

A data communication system including a transmitting and receiving terminal interconnected by a transmission channel, said transmitting terminal comprising: a source of data signals; means for encoding said signals in a burst-error-correcting binary cyclic code capable of correcting error bursts of b bits; means for generating a predetermined binary sequence; means for adding by addition modulo-2 said predetermined binary sequence to each of the code words generated by said encoding means; and means for transmitting the words obtained from said addition to said receiving terminal; and said receiving terminal comprising: means for receiving said transmitted words; means for generating said predetermined binary sequence; means for adding said predetermined binary sequence to each received word by addition modulo-2; means for simultaneously applying each binary word obtained from said addition to a buffer register storing means for temporarily storing said word and to an error locator means for generating the error pattern of said word; and means responsive to the generation of certain end-around burst error patterns for automatically correcting synchronization slippages of b-2 bits between said transmitting and receiving terminals.

Claim 9

A data communication system including a transmitting and receiving terminal interconnected by a transmission channel, said transmitting terminal comprising: a source of data signals; means for encoding said signals in a burst-error-correcting binary cyclic code capable of correcting error bursts of b bits; means for generating a predetermined binary sequence; means for adding by addition modulo-2 said predetermined binary sequence to each of the code words generated by said encoding means; and means for transmitting the words obtained from said addition to said receiving terminal; and said receiving terminal comprising: means for receiving said transmitted words; means for generating said predetermined binary sequence; means for adding said predetermined binary sequence to each received word by addition modulo-2; means for simultaneously applying each binary word obtained from said addition to a buffer register storing means for temporarily storing said word and to an error locator means for generating the error pattern of said word; and means responsive to the generation of certain end-around burst error patterns for automatically correcting synchronization slippages of b-2 bits between said transmitting and receiving terminals.

Claim 10

A combination as in claim 6 wherein said predetermined binary sequences generated by each of said sequence generating means are equal to the binary sequence represented by P(x) 1+ xn 1, where n is the length of said code words.

Claim 11

A combination as in claim 7 wherein said error locator means comprises logic means for generating a firSt error pattern represented by a(x)+ xr+ xn 1, where a(x) represents any binary sequence of degree r-1, upon the occurrence of an r-bit synchronization loss, and for generating a second error pattern represented by x0+ xn r 1+ xn ra(x) upon the occurrence of an r-bit synchronization gain.

Claim 12

A combination as in claim 8 wherein said synchronization correcting means includes means responsive to said logic means generating said first error pattern for advancing the word framing of said data communication system r bits, and responsive to said logic means generating said second error pattern for back-setting said word framing r bits.

Claim 13

A combination as in claim 7 in which said error locator means comprises a feedback shift register and associated logic for shifting and circulating said applied words to obtain said error patterns, counting means for maintaining a count of the number shifts performed by said shift register upon each of said words, and means responsive to said shift register and said counting means for signaling said synchronization correcting means to advance the word framing of said data communication system upon determining that the positions xr and xn 1 of a received word are in error, and for signaling said synchronization correcting means to back-set the word framing of said system upon determining that the positions x0 and xn r 1 are in error.

Claim 14

A combination as in claim 10 in which said synchronization correcting means comprises a binary counting circuit and associated logic for reducing the word-framing period of said data communication system in response to an ''''advance'''' signal from said error locator, and for extending the word-framing period of said system in response to a ''''back-set'''' signal from said error locator means.

Claim 15

A combination as in claim 6 further comprising means responsive to the generation of error patterns indicating the occurrence of error bursts in said received code words of length i, where i is any integer b, for automatically correcting said error bursts.

Claim 16

A combination as in claim 6 wherein said transmitting terminal further comprises means connected to said adding means for interleaving said words obtained from said subtraction and for applying said interleaved words to said transmitting means, and wherein said receiving terminal further comprises means connected to said receiving means for deinterleaving said received words and for applying said deinterleaved words to the adding means of said receiving terminal.

Claim 17

In a data communication system, a transmitting terminal comprising: a source of data signals; encoding means for encoding said data signals into a burst-error-correcting cyclic code; means for modifying the code words of said cyclic code by addition of a predetermined digital sequence, said predetermined sequence chosen such that the modified code words are processable to obtain an end-around burst error pattern when a synchronization slippage occurs between said transmitting terminal and the receiving terminal; and means for applying said modified words to one end of a communication channel.

Claim 18

In a data communication system, a transmitting terminal comprising: a source of data signals; encoding means for encoding said data signals into a burst-error-correcting cyclic code; means for modifying the code words of said cyclic code by addition of a predetermined digital sequence, said predetermined sequence chosen such that the modified code words are processable to obtain an end-around burst error pattern when a synchronization slippage occurs between said transmitting terminal and the receiving terminal; and means for applying said modified words to one end of a communication channel.

Claim 19

A system as in claim 14 wherein said predetermined sequence is P(x) Alpha + Beta xn 1, where n is the length of said code words, and Alpha and Beta are code symbols 0.

Claim 20

In a data communication system, a receiving terminal comprising: means for receiving incoming data sequences encoded in a b-burst-error-correcting cyclic code and modified by addition of a predetermined digital sequence; means for subtracting said predetermined sequence from each received data sequence; means for decoding the sequence obtained from said subtraction to obtain end-around burst error patterns; and synchronization recovery means responsive to the generation of said error patterns for readjusting synchronization of said system.

Claim 21

In a data communication system, a receiving terminal comprising: means for receiving incoming data sequences encoded in a b-burst-error-correcting cyclic code and modified by addition of a predetermined digital sequence; means for subtracting said predetermined sequence from each received data sequence; means for decoding the sequence obtained from said subtraction to obtain end-around burst error patterns; and synchronization recovery means responsive to the generation of said error patterns for readjusting synchronization of said system.

Claim 22

A system as in claim 16 wherein said predetermined sequence is P(x) Alpha + Beta xn 1, where n is the length of said received sequences and Alpha and Beta are code symbols 0.

Claim 23

A system as in claim 17 wherein said synchronization recovery means comprises apparatus responsive to said decoding means determining that the xn 1 position of a received sequence contains the symbol - Beta and that the next higher order position xr which contains a nonzero symbol contains the symbol Alpha , where r b-2, for advancing the synchronization of said system r symbols, and responsive to said decoding means determining that the x0 position of a received sequence contains the symbol - Alpha and that the next lower order position xn r 1 which contains a nonzero symbol contains the symbol Beta , for back-setting the synchronization of said system r symbols.