Consiglio Nazionale delle Ricerche

Tipo di prodottoArticolo in rivista
TitoloOn the Structure of Cyclotomic Fourier Transforms and Their Applications to Reed-Solomon Codes
Anno di pubblicazione2011
Autore/iS. Bellini, M. Ferrari, A. Tomasoni
Affiliazioni autoriCNR - IEIIT, Politecnico di Milano
Autori CNR e affiliazioni
AbstractThis paper is focused on cyclotomic Fourier transforms in GF(2^m), and on their applications to algebraic decoding of Reed-Solomon codes, like the evaluation of syndromes and of error locator (or evaluator) polynomials. Cyclotomic transforms are much more efficient than straightforward evaluation. In particular, the number of multiplications is quite small. In this paper it is shown that also the number of additions can be considerably reduced with respect to previous analyses. A simple interpretation of the cyclotomic Fourier transform best suited for the evaluation of syndromes allows to assemble the required matrix easily and quickly, even in large fields. Many equivalent matrices exist. Then, fast construction of such matrices is important to obtain the best results, since as many matrices as possible must be generated and compared. It is shown that also the structure of bilinear convolutions is to be exploited, to reduce complexity. For the costly part of cyclotomic Fourier transforms, which is a matrix-vector product, only heuristic algorithms are available. Since also these algorithms are to be run many and many times to obtain the best transform, execution times are important. It is shown that a very simple and fast heuristic algorithm gives satisfactory results.
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da2110
Pagine a2118
Pagine totali9
RivistaIEEE transactions on communications (Print)
Attiva dal 1972
Editore: Institute of Electrical and Electronics Engineers] - [New York,
Paese di pubblicazione: Stati Uniti d'America
Lingua: inglese
ISSN: 0090-6778
Titolo chiave: IEEE transactions on communications (Print)
Titolo proprio: IEEE transactions on communications. (Print)
Titolo abbreviato: IEEE trans. commun. (Print)
Titoli alternativi:
  • Transactions on communications (Print)
  • Communications (Print)
Numero volume della rivista59/8
Fascicolo della rivista-
Verificato da refereeSì: Internazionale
Stato della pubblicazione-
Indicizzazione (in banche dati controllate)
  • Scopus (Codice:2-s2.0-80052075682)
Parole chiavefourier transforms, Galois fields, Reed-Solomon codes, convolution
Link (URL, URI)-
Titolo parallelo-
Data di accettazione-
Note/Altre informazioni-
Strutture CNR
  • IEIIT — Istituto di elettronica e di ingegneria dell'informazione e delle telecomunicazioni
Moduli CNR
    Progetti Europei-
    Articolo pubblicato (documento privato )
    Tipo documento: application/pdf

    Dati storici
    I dati storici non sono modificabili, sono stati ereditati da altri sistemi (es. Gestione Istituti, PUMA, ...) e hanno solo valore storico.
    Area disciplinareComputer Science & Engineering
    Area valutazione CIVRIngegneria industriale e informatica