Reduced-Complexity Reed-Solomon Decoders Based on Cyclotomic FFTs

被引：15

作者：

Chen, Ning ^{[1
]}

Yan, Zhiyuan ^{[1
]}

机构：

[1] Lehigh Univ, Dept Elect & Comp Engn, Bethlehem, PA 18015 USA

来源：

IEEE SIGNAL PROCESSING LETTERS | 2009年 / 16卷 / 04期

基金：

美国国家科学基金会;

关键词：

Common subexpression elimination (CSE); decoding; discrete Fourier transforms; Galois fields; Reed-Solomon codes; FOURIER-TRANSFORM; POLYNOMIALS; COMPUTATION; ERASURES; ERRORS; ROOTS;

D O I：

10.1109/LSP.2009.2014292

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

In this paper, we reduce the computational complexities of partial and dual partial cyclotomic FFTs (CFFTs), which are discrete Fourier transforms where spectral and temporal components are constrained, based on their properties as well as a common subexpression elimination algorithm. Our partial CFFTs achieve smaller computational complexities than previously proposed partial CFFTs. Utilizing our CFFTs in both transform- and time-domain Reed-Solomon decoders, we achieve significant complexity reductions.

引用

页码：279 / 282

页数：4

共 12 条

[1]

Blahut R., 1983, Theory and Practice of Error Control Codes

[2]

CHEN N, IEEE SIGNAL PROCESS

[3]

CHEN N, IEEE T SIGNAL PROCES

[4] On computing the syndrome polynomial in Reed-Solomon decoder [J].

Costa, E ;

Fedorenko, SV ;

Trifonov, PV .

EUROPEAN TRANSACTIONS ON TELECOMMUNICATIONS, 2004, 15 (04) :337-342

[5] A Method for Computation of the Discrete Fourier Transform over a Finite Field [J].

Fedorenko, S. .

PROBLEMS OF INFORMATION TRANSMISSION, 2006, 42 (02) :139-151

[6] Finding roots of polynomials over finite fields [J].

Fedorenko, SV ;

Trifonov, PV .

IEEE TRANSACTIONS ON COMMUNICATIONS, 2002, 50 (11) :1709-1711

[7] On decoding of both errors and erasures of a Reed-Solomon code using an inverse-free Berlekamp-Massey algorithm [J].

Jeng, JH ;

Truong, TK .

IEEE TRANSACTIONS ON COMMUNICATIONS, 1999, 47 (10) :1488-1494

[8] A fast algorithm for the syndrome calculation in algebraic decoding of reed-solomon codes [J].

Lin, Tsung-Ching ;

Truong, T. K. ;

Chen, R. D. .

IEEE TRANSACTIONS ON COMMUNICATIONS, 2007, 55 (12) :2240-2244

[9] A Method for Fast Computation of the Fourier Transform over a Finite Field [J].

Trifonov, P. V. ;

Fedorenko, S. V. .

PROBLEMS OF INFORMATION TRANSMISSION, 2003, 39 (03) :231-238

[10] Fast transform for decoding both errors and erasures of Reed-Solomon codes over GF(2m) for 8≤m≤10 [J].

Truong, TK ;

Chen, RD ;

Wang, LJ ;

Cheng, TC .

IEEE TRANSACTIONS ON COMMUNICATIONS, 2006, 54 (02) :181-186

← 1 2 →