ERROR-CORRECTING SYSTEMS UTILIZING RATE 1/2 DIFFUSE CODES

• US 3,728,678 A
• Filed: 09/03/1971
• Issued: 04/17/1973
• Est. Priority Date: 09/03/1971
• Status: Expired due to Term

• Current Assignee: Shih Yung Tong
• Original Assignee: Shih Yung Tong
• Inventors: Tong, Shih Yung
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US05/177,686
• Time in Patent Office: 592 Days
• Field of Search: 340/146.1AQ
• US Class Current: 714/787
• CPC Class Codes: H03M 13/43 Majority logic or threshold decoding
• CPC Class Codes: H04L 1/0059 Convolutional codes

Abstract

Sequences of information bits, encoded in an orthogonalizable convolutional code of rate 1/2 and transmitted via a communication channel, are decoded to correct t random errors and bursts of B blocks where each block is 2 bits in length. The interconnections between an information bit shift register in the encoder and decoder and their respective parity check bit generating circuits and between a syndrome register and a majority logic circuit in the decoder are specified by relatively simple formulas which are functions of t and B.

Claims

1. In a data communication system for correcting t-random errors and B-burst errors in accordance with a specified code, said system including a transmitter, a receiver, a channel interconnecting said transmitter and receiver, and a source of information signals at said transmitter, a check-signal generating circuit in said transmitter comprising a. an exclusive-OR adder, b. an encoder information shift register for storing signals from said source of information signals having as many stages as there are terms in the generator polynomial characterizing said code, each of said shift register stages being associated with a particular term of said generator polynomial, and c. means for connecting selected stages of said information shift register to said exclusive-OR circuit to derive check signals, said selected stages being specified by the terms of the noniterative formula g(x) 0, a1, a1+ a2, . . . , B + V, 2B + Alpha + V, 2B + Alpha + V + D11, . . . , 2B + Alpha + V + Dr1, 3B + Alpha + Dr1 + 2V11, 3B + Alpha + Dr1 + 2V11 + E11, . . . , 3B + Alpha + Dr1 + 2V11 + Es1 where

2. Apparatus as in claim 1 further comprising a check-signal generating circuit aT said receiver including a. a decoder information shift register having as many stages as said encoder information shift register, b. a decoder exclusive-OR adder, c. means for connecting selected stages of said decoder shift register to said decoder exclusive-OR adder, said decoder shift register stages corresponding to said selected stages of said encoder information register to derive locally generated check signals, d. means for applying information signals received from said channel to said decoder information shift register, and e. logic means for logically combining check signals received from said channel with signals generated by said decoder exclusive-OR adder whereby syndrome signals of a first logic level are generated by said logic means when said received and locally generated check signals are the same and whereby syndrome signals of a second logic level are generated when said received and locally generated check signals are different.

3. Apparatus as in claim 2 wherein said receiver further includes a syndrome shift register for storing said syndrome signals generated by said logic means and wherein said syndrome register includes as many stages as said encoder information shift register.

4. Apparatus as in claim 3 wherein said receiver further includes a majority logic circuit responsive to signals from said syndrome shift register.

5. Apparatus as in claim 4 further including means for connecting designated stages of said syndrome register to said majority logic circuit and wherein said designated stages include stages corresponding to said selected stages of said encoder and decoder information shift registers.

6. Apparatus as in claim 5 wherein said means for connecting further includes at least one exclusive-OR adder.

7. Apparatus as in claim 5 further including feedback means responsive to signals from said majority logic circuit for inverting signals stored in said selected stages of said syndrome register.

8. Apparatus as in claim 7 further including means responsive to signals from said majority logic circuit for correcting incorrectly received signals stored in said decoder information shift register.

9. Apparatus as in claim 8 wherein said means for correcting includes an exclusive-OR adder for inverting selected signals at the output of said decoder information shift register in response to said signals from said majority logic circuit.

10. Apparatus as in claim 9 wherein said means for connecting said designated stages of said syndrome register to said majority logic circuit includes a number of exclusive-OR circuits the input signals of which are determined in accordance with the following rules:

a. Signals from syndrome register stage numbered (2B+ Alpha +Dr1+V), i 1, 2 . . . r are applied to a first connecting exclusive-OR circuit along with signals from stages numbered b. Signals from syndrome stage numbered (3B+ Alpha +Dr2+2V+1) are applied to a second connecting exclusive-OR circuit along with signals from stages numbered c. Signals from syndrome stages, numbered (3B+ Alpha +Ei1Dr1+2V+1), i 1,2 . . . r are applied to a third exclusive-OR circuit along with signals from stages numbered where Dr0 is defined to be 0, wherein the number designation of each of said syndrome register stages is the nonzero term of said generator polynomial to which said syndrome stage corresponds.

11. A method for detecting and correcting errors in accordance with a specified code in a data stream processed by a data transmission system including a transmitter, a receiver and a noisy interconnecting channel comprising the steps of a. generating at said transmitter a first set of check signals from said data strEam by logically combining selected ones of said data signals, said selected ones of said data stream signals being specified by the nonzero terms of the generator polynomial for said code determined as follows:

0, a1, a1 + a2, . . . , B + V, 2B + Alpha + V, 2B + Alpha + V + D11, . . . , 2B + Alpha + V + Dr1, 3B + Alpha + Dr1 + (2V11) 2V11, 3B + Alpha + Dr1 + ( 2V11) 2V11 + E11, . . . , 3B + Alpha + Dr1 + ( 2V11) 2V11 + Es1 where

12. A method for correcting t-random errors and B-burst errors in a stream of data signals processed by a data transmission system having a transmitter, a receiver and an interconnecting channel, a. specifying the nonzero terms of the generator polynomial as follows:

0, a1, a1 + a2, . . . , B + V, 2B + Alpha + V, 2B + Alpha + V + D11, . . . , 2B + Alpha + V + Dr1, 3B + Alpha + Dr1 +( 2V11) 2V11, 3B + Alpha + Dr1 + ( 2V11) 2V11 + E11, . . . , 3B + Alpha + Dr1 +( 2V11) 2V11 + Es1 where