مرکز منطقه ای اطلاع رساني علوم و فناوري - The fast decoding of Reed-Solomon codes using Fermat transforms (Corresp.)

DocumentCode :

928707

Title :

The fast decoding of Reed-Solomon codes using Fermat transforms (Corresp.)

Author :

Reed, I. ; Treiu-Kien Truong ; Welch, L.

Volume :

Issue :

fYear :

1978

fDate :

7/1/1978 12:00:00 AM

Firstpage :

497

Lastpage :

499

Abstract :

It is shown that $\\sqrt [8]{2}$ is an element of order $2^{n+4}$ in $GF(F_{n})$ , where $F_{n}=2^{2^{n}}+1$ is a Fermat prime for $n=3,4$ . Hence it can be used to define a fast Fourier transform (FFT) of as many as $2^{n+4}$ symbols in $GF(F_{n})$ . Since $\\sqrt [8]{2}$ is a root of unity of order $2^{n+4}$ in $GF(F_{n})$ , this transform requires fewer muitiplications than the conventional FFT algorithm. Moreover, as Justesen points out [1], such an FFT can be used to decode certain Reed-Solomon codes. An example of such a transform decoder for the case $n=2$ , where $\\sqrt {2}$ is in $GF(F_{2})=GF(17)$ , is given.

Keywords :

Decoding; Number-theoretic transforms; Reed-Solomon codes; Contracts; Decoding; Error correction codes; Fast Fourier transforms; Galois fields; Information science; Linear code; Mathematics; Probes; Reed-Solomon codes;

fLanguage :

English

Journal_Title :

Information Theory, IEEE Transactions on

Publisher :

ieee

ISSN :

0018-9448

Type :

jour

DOI :

10.1109/TIT.1978.1055902

Filename :

1055902

Link To Document :

https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=928707