DECODING ALGORITHM FOR QUADRATIC RESIDUE CODES

• US 20100131807A1
• Filed: 11/26/2008
• Published: 05/27/2010
• Est. Priority Date: 11/26/2008
• Status: Abandoned Application

• Current Assignee: I-Shou University
• Original Assignee: I-Shou University
• Inventors: TRUONG, Trieu-Kien, SHIH, Pei-Yu, SU, Wen-Ku, LIN, Tsung-Ching
• Application Number:
  US12/323,504
• Publication Number:
  US 20100131807A1
• Time in Patent Office: Days
• US Class Current: 714/704
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials
• CPC Class Codes: H03M 13/153 using the Berlekamp-Massey algorithm
• CPC Class Codes: H03M 13/1545 Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial

Abstract

A decoding algorithm for quadratic residue codes applicable to the decoding of all quadratic residue codes is provided. The decoding algorithm employs digital signals to obtain a plurality of known syndromes. These known syndromes are used to calculate a plurality of unknown syndromes. The inverse-free Berlekamp-Massey algorithm is then used to calculate the error polynomial, after which the Chien search algorithm is used to determine the error locations. Adjustments can then be made to the digital signal bits corresponding to the error locations to obtain the correct code.

Claims

1. A quadratic residue code decoding algorithm comprising the steps of:

providing a digital signal to determine if an error is encountered and calculate a plurality of known syndromes and setting a number of errors and an error correction threshold;

using said known syndromes to calculate a plurality of unknown syndromes;

treating said unknown syndromes as known, and using said known syndromes and said unknown syndromes to calculate an error polynomial;

determining whether the highest dimension of said error polynomial matches said number of errors;

if said highest dimension of said error polynomial matches said number of errors, calculating at least one root and at least one root number for said error polynomial;

if said highest dimension of error polynomial does not match said number of errors, adding a specified value to said number of errors, and determining whether said number of errors now exceeds said error correction threshold;

if it is determined that said number of errors does not exceed said error correction threshold, then going back to the step of using said known syndromes to calculate a plurality of unknown syndromes;

determining whether said root number of said error polynomial matches said number of errors;

if said root number of said error polynomial matches said number of errors, determining at least one error location for said error polynomial, and adjusting the digital value corresponding to said error location; and

if said root number of said error polynomial does not match said number of errors, going back to the step of adding a specified value to said number of errors, and determining whether said number of errors now exceeds said error correction threshold.

2. The quadratic residue code decoding algorithm as claimed in claim 1 wherein said quadratic residue code decoding algorithm is applicable to all quadratic residue codes.

3. The quadratic residue code decoding algorithm as claimed in claim 1 wherein said quadratic residue code is applicable to the (89,45,17) quadratic residue code.

4. The quadratic residue code decoding algorithm of claim 1 wherein said number errors is initially set at 1, and said specified value is set at 1.

5. The quadratic residue code decoding algorithm as claimed in claim 1, wherein said unknown syndromes are treated as known and said known syndromes and said unknown syndromes are used to calculate said error polynomial, wherein said known syndromes and said unknown syndromes are entered into said error polynomial as known values, and the inverse-free Berlekamp-Massey algorithm is used to calculate said error polynomial.

6. The quadratic residue code decoding algorithm as claimed in claim 1, wherein the Chien search algorithm is used to calculate at least one root and at least one root number of said error polynomial.