Truong et al., 2002 - Google Patents
Fast algorithm for computing the roots of error locator polynomials up to degree 11 in Reed-Solomon decodersTruong et al., 2002
View PDF- Document ID
- 5349538485502327629
- Author
- Truong T
- Jeng J
- Reed I
- Publication year
- Publication venue
- IEEE Transactions on Communications
External Links
Snippet
The central problem in the implementation of a Reed-Solomon code is finding the roots of the error locator polynomial. In 1967, Berlekamp et al. found an algorithm for finding the roots of an affine polynomial in GF (2/sup m/) that can be used to solve this problem. In this …
Classifications
-
- H—ELECTRICITY
- H03—BASIC ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/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
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/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/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
- H03M13/1515—Reed-Solomon codes
-
- H—ELECTRICITY
- H03—BASIC ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/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
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/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/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
- H03M13/1525—Determination and particular use of error location polynomials
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/724—Finite field arithmetic
- G06F7/726—Inversion; Reciprocal calculation; Division of elements of a finite field
-
- H—ELECTRICITY
- H03—BASIC ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/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
- H03M13/29—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
- H03M13/2906—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
- H03M13/2909—Product codes
-
- H—ELECTRICITY
- H03—BASIC ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/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
- H03M13/29—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
- H03M13/2906—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
- H03M13/2927—Decoding strategies
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
-
- H—ELECTRICITY
- H03—BASIC ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/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
- H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
- H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
- H03M13/3966—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes based on architectures providing a highly parallelized implementation, e.g. based on systolic arrays
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L1/00—Arrangements for detecting or preventing errors in the information received
- H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
- H04L1/0056—Systems characterized by the type of code used
- H04L1/0057—Block codes
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Truong et al. | Fast algorithm for computing the roots of error locator polynomials up to degree 11 in Reed-Solomon decoders | |
| Fedorenko et al. | Finding roots of polynomials over finite fields | |
| Jeng et al. | On decoding of both errors and erasures of a Reed-Solomon code using an inverse-free Berlekamp-Massey algorithm | |
| US7219289B2 (en) | Multiply redundant raid system and XOR-efficient method and apparatus for implementing the same | |
| Chang et al. | Algebraic decoding of (71, 36, 11),(79, 40, 15), and (97, 49, 15) quadratic residue codes | |
| US6550035B1 (en) | Method and apparatus of Reed-Solomon encoding-decoding | |
| Wachter-Zeh et al. | Decoding interleaved Reed–Solomon codes beyond their joint error-correcting capability | |
| Chang et al. | New serial architecture for the Berlekamp-Massey algorithm | |
| KR20180085651A (en) | Application-specific integrated circuit to perform a method for fast polynomial updates in bm-based fast chase decoding of binary bch codes through degenerate list decoding | |
| Xie et al. | Fast nested key equation solvers for generalized integrated interleaved decoder | |
| Zhang | VLSI architectures for Reed–Solomon codes: Classic, nested, coupled, and beyond | |
| US7458007B2 (en) | Error correction structures and methods | |
| US20040078747A1 (en) | Generalized forney algorithm circuit | |
| Truong et al. | A new decoding algorithm for correcting both erasures and errors of Reed-Solomon codes | |
| Fedorenko | A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch-Berlekamp algorithm | |
| US8335808B2 (en) | Method and apparatus for processing multiple decomposed data for calculating key equation polynomials in decoding error correction code | |
| US20030131308A1 (en) | Method and apparatus for solving key equation polynomials in decoding error correction codes | |
| US6421807B1 (en) | Decoding apparatus, processing apparatus and methods therefor | |
| US20030159103A1 (en) | Efficient method for fast decoding of BCH binary codes | |
| Byrne | Lifting decoding schemes over a Galois ring | |
| US6971056B1 (en) | Decoder-usable syndrome generation with representation generated with information based on vector portion | |
| Lin et al. | Algebraic decoding of cyclic codes without error-locator polynomials | |
| US6598201B1 (en) | Error coding structure and method | |
| EP4576586B1 (en) | Hardware efficient syndrome calculation for out-of-order arriving reed-solomon codeword symbols | |
| US10623026B2 (en) | Error correction |