Efficient maximum-likelihood decoder for the golay (24,12) code

• US 4,901,317 A
• Filed: 08/11/1988
• Issued: 02/13/1990
• Est. Priority Date: 08/11/1988
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Unisys Corporation
• Inventors: Abbaszadeh, Ayyoob D., Rushforth, Craig K.
• Primary Examiner(s): Fleming, Michael R.
• Application Number:
  US07/231,125
• Time in Patent Office: 551 Days
• Field of Search: 371/37.1, 371/37.2, 371/37.4, 371/37.5, 371/37.7, 371/38.1, 371/39.1, 371/44, 371/40.1, 371/40.3
• US Class Current: 714/783
• CPC Class Codes: H03M 13/1505 Golay Codes
• CPC Class Codes: H03M 13/45 Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence

Abstract

A novel maximum likeihood decoder for the Golay (24,12) code is provided. Instead of decoding the received dimensional vector (X) is a systolic array, the vector is mapped into a (24,5) subcode with an index 128 which is easily decoded. The decoder employs a plurality of precomputational circuits cooperating with a similar plurality of inner product circuits which compute the 128 inner product values and select the maximum inner product value from each inner product circuit. The maximum inner product value from each circuit is loaded into a select logic circuit for selecting the maximum inner product value and its corresponding code word closest to the received vector (X).

Claims

1. An efficient maximum likelihood decoder for the Golay (24,12) code comprising:

precomputational circuit means for receiving a dimensional vector (X) to be decoded,

register means comprising a plurality of sets of storage registers for dividing said dimensional vector information into sets of information,

bit serial adder means coupled to said individual sets of said registers for producing precomputed SG_K values representative of said sets of information,

random access (RAM) storage means for storing said SG_K values,

inner product circuit means comprising a plurality of processing elements,

each of said processing elements being coupled to a part of said RAM storage means representative of sets of said SG_K values,

means for addressing and sequentially reading said precomputed SG_K values out of said random access storage means into said inner product circuit means,

means for comparing said SG_K values and for determining a minimum SG_K values and the subcode values for the SG_K values,

means for determining the sign of the SG_K subcode values,

means for calculating and selecting the largest inner product values for said subcode values,

select means for determining the single subcode value whose inner product with the received dimensional vector (X) is the largest, and

means for presenting said subcode value as information bits associated with said subcode value to a utilization device.

2. An efficient maximum likelihood decoder as set forth in claim 1 wherein said dimension vector (X) is represented by a twenty-four dimensional vector equal (X₂₄ . . ., X₂, X₁).

3. An efficient maximum likelihood decoder as set forth in claim 2 wherein said register means comprises six sets of eight registers for storing SG_K values.

4. An efficient maximum likelihood decoder as set forth in claim 3 wherein said precomputational circuit means, said register means and said bit serial adder means compute 128 sets of SG_K values where SG_K =X_4K ±

X_4K-1 ±

X_4K-2 ±

X_4K-3 for each of the six sets of registers.

5. An efficient maximum likelihood decoder as set forth in claim 1 wherein said inner product circuit means comprises a plurality of sets of processing elements for receiving said SG_K values from said random storage means.

6. An efficient maximum likelihood decoder as set forth in claim 5 wherein said processing elements each comprise means for checking parity of said SG_K values.

7. An efficient maximum likelihood decoder as set forth in claim 5 wherein said processing elements each comprise means for comprising SG_K values and determining the minimum magnitude SG_K value.

8. An efficient maximum likelihood decoder as set forth in claim 7 wherein said processing elements each comprise means for determining a subcode value associated with each minimum magnitude SG_K value.

9. An efficient maximum likelihood decoder as set forth in claim 5 wherein said processing elements each comprise means for determining an inner product (IP) value equal to the sum of the absolute values of the SG_K values.

10. An efficient maximum likelihood decoder as set forth in claim 9 wherein said inner product value IP=|SG₁.sup.(j) |+---+|SG₆.sup.(j) where K=1 to 6 and j=0 to 127.

11. An efficient maximum likelihood decoder as set forth in claim 10 wherein said processing elements each comprise means for determining the maximum inner product (IP) value and the (24,5) subcode having the maximum inner product value.

12. An efficient maximum likelihood decoder as set forth in claim 10 wherein said dimensional vector (X) is decoded as a (24,5) subcode to find the maximum inner product and the corresponding code word closest to the received vector (X).

13. An efficient maximum likelihood decoder as set forth in claim 5 wherein said processing elements each comprise bit serial adders and parity checkers coupled to a subcode decoder for determining a subcode value.

14. An efficient maximum likelihood decoder as set forth in claim 13 which further comprises a subcode latch for storing said subcode value.

15. An efficient maximum likelihood decoder as set forth in claim 14 which further comprises a main decoder coupled to said subcode latch and to said means for calculating and selecting the largest inner product value.

16. An efficient maximum likelihood decoder as set forth in claim 15 wherein said main decoder decodes said subcode value as a (24,5) subcode value.

17. An efficient maximum likelihood decoder as set forth in claim 15 wherein said select logic circuit coupled to said main decoder and to said means for calculating and selecting the largest inner product value is decoded as a (24,5) code word.

18. An efficient maximum likelihood decoder as set forth in claim 17 wherein said Golay (24,12) dimensional vector (X) is selected from the decoded (24,5) code word.