A pipeline design of a fast prime factor DFT on a finite field

A conventional prime factor discrete Fourier transform (DFT) algorithm of the Winograd type is used to realize a discrete Fourier-like transform on the finite field GF(q/sup /n). A pipeline structure is used to implement this prime-factor DFT over GF(q/sup /n). This algorithm is developed to compute...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1988-03, Vol.37 (3), p.266-273
Main Authors: Truong, T.K., Reed, I.S., Hsu, I.-S., Shyu, H.-C., Shao, H.M.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Convolutional codes
Cybernetics
Decoding
Discrete Fourier transforms
Exact sciences and technology
Fast Fourier transforms
Fourier transforms
Galois fields
Pipelines
Reed-Solomon codes
Systolic arrays
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A conventional prime factor discrete Fourier transform (DFT) algorithm of the Winograd type is used to realize a discrete Fourier-like transform on the finite field GF(q/sup /n). A pipeline structure is used to implement this prime-factor DFT over GF(q/sup /n). This algorithm is developed to compute cyclic convolutions of complex numbers and to aid in decoding the Reed-Solomon codes. Such a pipeline fast prime-factor DFT algorithm over GF(q/sup /n) is regular, simple, expandable, and naturally suitable for most implementation technologies. An example illustrating the pipeline aspect of a 30-point transform over GF(q/sup /n) is presented.< >
ISSN:0018-9340
1557-9956
DOI:10.1109/12.2163