High performance error control decoder

• US 5,968,199 A
• Filed: 12/18/1996
• Issued: 10/19/1999
• Est. Priority Date: 12/18/1996
• Status: Expired due to Term

• Current Assignee: Blackberry Limited
• Original Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Khayrallah, Ali S., Chennakeshu, Sandeep, Toy, Raymond L.
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US08/768,530
• Time in Patent Office: 1,035 Days
• Field of Search: 371/37.06, 371/37.4, 714/755, 714/780, 714/783
• US Class Current: 714/783
• CPC Class Codes: G10L 19/005 Correction of errors induced by the transmission channel, if related to the coding algorithm
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/1505 Golay Codes
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials
• CPC Class Codes: H03M 13/3738 with judging correct decoding
• CPC Class Codes: H03M 13/45 Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H03M 13/618 Shortening and extension of codes
• CPC Class Codes: H03M 13/6577 Representation or format of variables, register sizes or word-lengths and quantization
• CPC Class Codes: H03M 13/658 Scaling by multiplication or division

Abstract

An error control decoder receives a received vector to be decoded. The decoder then calculates, as an error estimate, the Euclidean distance between a codeword choice and the received vector. The output error estimate is appropriately scaled and quantized in accordance with the particular code being processed by the decoder. The efficient Conway-Sloane algorithm is extended for use in connection with the decoding of shortened Golay codes. A modification is made to the generator matrix for the Golay code to produce a modified generator matrix that is unique for each shortened code. The modified generator matrix is then implemented in the Conway-Sloane algorithm to identify the best codeword for conversion to its corresponding information bits for output.

Claims

1. A decoder receiving a received vector to be decoded, comprising:

means for determining a codeword choice closest to the received vector;

means for determining the Euclidean distance between the received vector and the codeword choice, the determined Euclidean distance output as an error estimate for the decoded received vector; and

means for scaling and quantizing the error estimate in accordance with a given type of code;

wherein the given type of code comprises a Golay code, and the error estimate is scaled and quantized to a value of either zero, one, two or three.

2. The decoder as in claim 1 wherein the Euclidean distance is calculated between the received vector in antipodal form and the codeword choice also in antipodal form.

3. A decoder for decoding a received vector encoded in accordance with an (n'"'"',k'"'"') shortened Golay code wherein the decoder executes a Conway-Sloane algorithm on the received vector to identify a codeword choice closest to the received vector, the executed Conway-Sloane algorithm utilizing a generator matrix G_m for the shortened Golay code, wherein the generator matrix G_m comprises a modification of a generator matrix G for an (n,k) Golay code, wherein n'"'"'<

n and k'"'"'<

k, and wherein the generator matrix G includes a plurality of rows and a plurality of columns, and wherein the modification of the generator matrix G to produce the generator matrix G_m comprises the removal of certain plural ones of both the rows and columns of the generator matrix G.

4. The decoder as in claim 3 wherein the (n,k) Golay code comprises a (24,12) Golay code, and wherein the (n'"'"',k'"'"') shortened Golay code comprises a (19,7) shortened Golay code.

5. The decoder as in claim 4 wherein the generator matrix G includes twelve rows and twenty-four columns, and wherein the modification producing the generator matrix G_m comprises the removal of columns twenty, twenty-one, twenty-two, twenty-three and twenty four, and the removal of rows four, five, ten, eleven and twelve.

6. The decoder as in claim 3 wherein the (n,k) Golay code comprises a (24,12) Golay code, and wherein the (n'"'"',k'"'"') shortened Golay code comprises an (18,6) shortened Golay code.

7. The decoder as in claim 6 wherein the generator matrix G includes twelve rows and twenty-four columns, and wherein the modification producing the generator matrix G_m comprises the removal of columns sixteen, twenty, twenty-one, twenty-two, twenty-three and twenty four, and the removal of rows three, four, five, ten, eleven and twelve.

8. The decoder as in claim 3 wherein the (n,k) Golay code comprises a (24,12) Golay code, and wherein the (n'"'"',k'"'"') shortened Golay code comprises an (18,7) shortened Golay code.

9. The decoder as in claim 8 wherein the generator matrix G includes twelve rows and twenty-four columns, and wherein the modification producing the generator matrix G_m comprises the removal of columns one, twenty, twenty-one, twenty-two, twenty-three and twenty four, and the removal of rows four, five, ten, eleven and twelve.

10. The decoder as in claim 8 wherein the generator matrix G includes twelve rows and twenty-four columns, and wherein the modification producing the generator matrix G_m comprises the removal of columns twenty, twenty-one, twenty-two, twenty-three and twenty four, and the removal of rows four, five, ten, eleven and twelve, and further including the appending of a zero to the received vector prior to execution of the Conway-Sloane algorithm.