Apparatus and method for decoding error correction coded information

• US 4,648,091 A
• Filed: 07/02/1984
• Issued: 03/03/1987
• Est. Priority Date: 07/02/1984
• Status: Expired due to Term

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Gajjar, Jagdish T.
• Primary Examiner(s): Fleming, Michael R.
• Application Number:
  US06/627,368
• Time in Patent Office: 974 Days
• Field of Search: 371/39, 371/38, 371/37, 371/40, 371/41
• US Class Current: 714/783
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence

Abstract

A method for decoding error correction coded information having been encoded using a linear cyclic block code, such as a Golay (23,12) code, or an extended Golay (24,12) code, to form a message word, comprises serially examining each bit of the message word and forming another code word wherein the Hamming distance between the other code word and the sequential pattern of bits examined is not greater than the error correction capability of the message word. Apparatus for forming the other code word and for checking Hamming distances is described.

Claims

1. A tracking decoder for decoding a received message word into data word which has been encoded to form a first linear cyclic block code word including said data word and a parity word, comprising:

control means;

memory means coupled to said control means for storing a plurality of predetermined second linear cyclic block code words;

code word means coupled to said control means for storing a cyclicly shifting a selected one of said plurality of predetermined second linear cyclic block code words;

data means coupled to said control means for serially sequentially examining each bit of said received message word;

Hamming means coupled to said control means for storing the Hamming distance between the contents of said code word means and contents of said data means; and

scratch pad means coupled to said control means;

said control means operative to monitor continuously the Hamming distance between the contents of said code word means and said data means and store the said distance in said Hamming means, and when said Hamming distance is above a predetermined value, to logically exclusively OR the contents of said code word means and the contents of said data means and store the logical result of the ORing process in said scratch pad means, said control means operating in response to the contents of said Hamming means above a predetermined value and the contents of said scratch pad means to update said code word means to a code word corresponding to the contents of said data means, the contents of said code word means, after the receipt of said message word, being decoded by said control means to retrieve said data word.

2. The decoder as in claim 1 wherein each of said code word means, said data means and said scratch pad means comprises a register.

3. The decoder as in claim 1 wherein said control means comprises a general purpose microprocessor programmed to select a different one of said plurality of predetermined second linear cyclic block code words for said code word means when said Hamming means stores a Hamming distance greater than the maximum bit error correction capability of said first linear cyclic block code word.

4. The decoder as in claim 3 wherein said data word is encoded to form a Golay (23,12) code word, whereby the maximum bit error correction capability of said first linear cyclic block code word is 3.

5. A method for decoding a data word from a first binary message word, said first message word having been encoded to form a first linear cyclic block code word including said data word and a parity word, wherein fewer than a first predetermined number of bits of said first binary message word may have been corrupted after encoding, comprising:

(a) cyclicly shifting one bit of a predetermined second linear block code word one bit position, said second linear block code word consisting of the same number of bits as said first message word;

(b) logically comparing the first bit of said first message word with the first bit of a predetermined second binary message word;

(c) repeating steps a and b for each next respective sequential bit of said first and second message word, respectively, when comparison of step b determines that the respective bits of said first and second message word are logically equivalent;

(d) logically comparing the immediately preceding bit having been cyclicly shifted with the respective bit of said first message word when comparison of step b determines that the respective bits of said first and second message word are not logically equivalent;

(e) decreasing a second predetermined number by one when comparison of step d determines that the immediately preceding bit having been cyclicly shifted is logically equivalent to the respective bit of said first message word;

(f) increasing said second predetermined number by one when comparison of step d determines that the immediately preceding bit having been cyclically shifted is not logically equivalent to the respective bit of said first message word;

(g) comparing said second predetermined number with said first predetermined number and repeating steps a through f for each next respective sequential bit of said first and second message word, respectively, when comparison determines that said second predetermined number is less than said first predetermined number;

(h) exclusively ORing the present status of said second linear block code word with the respective sequence of bits of said first message word having already been compared by execution of step b when comparison of step g determines that said second predetermined number is equal to said first predetermined number;

(i) logically ANDing the result of step h with a plurality of predetermined third linear block code words;

(j) comparing the result of step h with the respective one of the plurality of third linear block code words having generated the result of step i;

(k) exclusively ORing the present status of said second linear block code word with the respective one of the plurality of third linear block code words having generated an equality for step j;

(l) substituting the result of step k for the present status of said second linear block code word; and

(m) repeating steps a through l until a third predetermined number of bits of said first message word have been examined.

6. The method as in claim 5, wherein said plurality of third linear block code words comprises words including a logical one in the least significant bit position and a total number of logical ones equal to one plus twice said second predetermined number.

7. The method as in claim 5, wherein said linear cyclic block code word comprises a Golay (23, 12) code word and said first predetermined number is 4 said second predetermined number is 3 and said third predetermined number is 23.

8. The method as in claim 5, further comprising obtaining the data word from the present status of said second linear block code word after said third predetermined number of bits of said first message word have been examined.

9. A method for decoding a data word from an extended Golay (24,12) code word, said extended Golay code word having been encoded to include said data word, a parity word and an overall parity bit, wherein fewer than a first predetermined number of bits of said first binary message word may have been corrupted after encoding, comprising:

(a) cyclicly shifting one bit of a predetermined first linear block code word one bit position, said first linear block code word consisting of one less than the number of bits of said extended Golay code word;

(b) logically comparing the first bit of said extended Golay code word with the first bit of a predetermined binary message word;

(c) repeating steps a and b for each next respective sequential bit of said extended Golay code word and binary message word, respectively, when comparison of step b determines that the respective bits of said extended Golay code word and binary message word are logically equivalent;

(d) logically comparing the immediately preceding bit having been cyclicly shifted with the respective bit of said extended Golay code word when comparison of step b determines that the respective bits of said extended Golay code word and said binary message word are not logically equivalent;

(e) decreasing a second predetermined number by one when comparison of step d determines that the immediately preceding bit having been cyclicly shifted is logically equivalent to the respective bit of said extended Golay code word;

(f) increasing said second predetermined number by one when comparison of step d determines that the immediately preceding bit having been cyclicly shifted is not logically equivalent to the respective bit of said extended Golay code word;

(g) comparing said second predetermined number with said first predetermined number and repeating steps a through f for each next respective sequential bit of said extended Golay code word and said binary message word, respectively, when comparison determines that said second predetermined number is less than said first predetermined number;

(h) exclusively ORing the present status of said first linear block code word with the respective sequence of bits of said extended Golay code word having already been compared by execution of step b when comparison of step g determines that said second predetermined number is equal to said first predetermined number;

(i) logically ANDing the result of step h with a plurality of a predetermined second linear block code word;

(j) comparing the result of step i with the respective one of the plurality of second linear block code words having generated the result of step i;

(k) exclusively ORing the present status of said first linear block code word with the respective one of the plurality of second linear block code words having generated an equality for step j;

(l) substituting the result of step k for the present status of said first linear block code word; and

(m) repeating steps a through l until a predetermined number of bits of said extended Golay code word have been examined.

10. The method as in claim 9, wherein said plurality of second linear block code words comprises words including a logical one in the least significant bit position and a total number of logical ones equal to one plus twice said second predetermined number.

11. The method as in claim 9 further comprising, exclusively ORing the present status of said first linear block code word with said extended Golay code word excluding the overall parity bit to generate a Hamming distance check result, after said predetermined number of bits of said extended Golay code word have been examined.

12. The method as in claim 11 further comprising, obtaining the data word from the present status of said first linear block code word when said Hamming distance check result includes less than three logical ones.

13. The method as in claim 11 further comprising, checking parity of said extended Golay code word with the overall parity bit when said Hamming distance check result includes exactly three logical ones and obtaining the data word from the present status of said first linear block code word when the parity check indicates a correct parity.

14. The method as in claim 11 further comprising, checking parity of said extended Golay code word with the overall parity bit when said Hamming distance check result includes exactly three logical ones and indicating an uncorrectable error in said extended Golay code word when the parity check indicates an incorrect parity.

15. A method of decoding a data word from a received binary message word, said received binary message word being associated with a transmitted code word of a linear cyclic block code, said transmitted code word including said data word and a parity word comprising the steps of:

(a) forming a data word, a poriton of said data word corresponding to previously received bits of said received binary message word;

(b) changing said data word in accordance with newly received bits of said received message word;

(c) generating a code word of said linear cyclic block code which continuously corresponds to said current data word by being within a Hamming distance equal to or less than the maximum error correction capability of said code; and

(d) extracting the data word associated with the code word corresponding to a fully received message word.

16. A method of decoding a data word from a received binary message word, said received binary message word being associated with a transmitted code word of a linear cyclic block code, said transmitted code word including said data word and a parity word comprising the steps of:

(a) generating in a first storage means a data word having a number of bits corresponding to the number of bits in the code words of said code;

(b) generating in a second storage means a code word corresponding to said data word, said code word being a Hamming distance from said data word which is within the error correction capability of said code;

(c) storing said Hamming distance in a third storage means;

(d) changing said data word in accordance with serially sequentially received bits of said received message word;

(e) changing said code word as needed to continuously be within a Hamming distance no greater than the error correction capability of the code; and

(f) extracting the data word associated with the code word contained in the second storage means when the received message word has been fully examined.