REVERSE CYCLIC CODE ERROR CORRECTION

• US 3,811,108 A
• Filed: 05/29/1973
• Issued: 05/14/1974
• Est. Priority Date: 05/29/1973
• Status: Expired due to Term

• Current Assignee: Thomas Harold Howell
• Original Assignee: Thomas Harold Howell
• Inventors: Howell, Thomas Harold
• Primary Examiner(s): Morrison, Malcolm A.
• Assistant Examiner(s): Dildine, Jr., R. Stephen
• Application Number:
  US05/364,782
• Time in Patent Office: 350 Days
• Field of Search: 340/146.1AL
• US Class Current: 714/785
• CPC Class Codes: H03M 13/175 Error trapping or Fire codes
• CPC Class Codes: H03M 13/618 Shortening and extension of codes
• CPC Class Codes: H03M 13/6516 Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields

Abstract

A method and apparatus is disclosed in which reversible cyclic encoding is used to enable reverse error identification. Encoding and decoding is performed in essentially a conventional manner, except that the coding conforms to a reversible cyclic generator polynomial. In the preferred embodiment, a linear feedback shift register is augmented with logic gates which enables the reversing of syndrome bits for subsequent error identification cycling in the event an error is detected.

Claims

1. A method of identifying errors in a set of information bits comprising:

A. applying said set of information bits to an encoder which generates check bits in accordance with a reversible cycle code and appending the generated check bits to the set of information bits to form a codeword;

B. applying the word to an error detector so as to generate a syndrome in accordance with the reversible cyclic code;

C. reversing the order of the syndrome bits; and

D. cycling the reversed syndrome bits until an error pattern is generated for identifying the error.

2. An encoder/decoder, for generating check bits, for detecting an error syndrome and for developing an error pattern, comprising:

A. a linear feedback shift register including;

i. a set of shift register stages suitable for storing the syndrome bits of a cyclic codeword, ii. a set of logic gates interconnecting said shift register stages for receiving a set of input information bits and for realizing a linear feedback shift register which is capable of decoding a reversible cyclic code;

B. a set of reversing gates, interconnecting said shift register stages so as to enable said linear feedback shift register to selectively reverse the order of the syndrome bits in said register;

C. control circuits, connected to said shift register stages and said reversing gates, to selectively provide a decoding mode in which the information bits are decoded into an error syndrome and, when an error is detected, causing said linear feedback shift register to perform an error identification operation.

3. A reversible cyclic code encoder/decoder for encoding, decoding, and error identification of any shortened codeword, comprising:

A. a set of shift register stages of sufficient length to store the syndrome bits of the encoded information bits;

B. a set of mod 2 summation gates interconnecting said shift register stages so as to implement a feedback shift register realizing the reversible cyclic code encoder;

C. upper and lower zero detector means, connected to said shift register stages in such a manner that a zero syndrome is detected for an error decoding operation and error identification pattern location is detected for an error identification operation;

D. a counter responsive to the linear feedback shift register for counting the cycles during an operation;

E. a set of reversing gates interconnecting said shift register stages so as to enable reversing of the codeword bits in the register;

F. a control circuit, connected to each of said shift register stages for cycle control, connected to said counter for terminating an error identification operation after a maximum number of cycles have been performed, and connected to said error detectors and reversing gates for actuating the syndrome reversal.