DOI: https://doi.org/10.15588/1607-3274-2018-2-15

DEVELOPMENT OF WFTA BASED ON THE HASHING ARRAY

I. O. Prots’ko, V. M. Teslyuk

Abstract


Context. A method of efficient computation of DFT using cyclic convolutions for sizes of integer power of two has been considered.
The further development of Winograd Fourier transform algorithm based on a hashing array has been proposed. The research object is the
process of the reformulation the basis matrix of DFT into the block-cyclic structures. The research subject lays in the technique of the
reformulation the basis matrix of DFT for sizes of integer power of two into the block-cyclic structures.
Objective. The purpose of the work is the analysis of the structure specifics the left-circulant submatrices of the basis square matrix
WN for sizes of transform N = 2i using the hashing arrays.
Method. The article considers a technique for the efficient computation of DFT using cyclic convolutions for sizes of integer power
of two, which is based on the cyclic decomposition of substitution. A hashing array has been proposed for the compressed description of the
block-cyclic structure of discrete basis matrix and for the efficient computation of DFT for sizes of integer power of two.
Results. A generalized block-cyclic structure of discrete basis matrix for the efficient computation of DF using cyclic convolutions for
sizes of an integer power of two based on the hashing arrays has been determined. The proposed technique is relevant for concurrent
programming of DFT and for its implementation in parallel systems.
Conclusions. A general block-cyclic structure of basis matrix of DFT is regularly formed with an increase in the value of the exponent
of two and is recommended for use in practice when developing the efficient means of DFT. The prospects for further research will include
the formation of block-cyclic structure of basis matrix of DFT for arbitrary sizes.

Keywords


fast Fourier transform; Winograd Fourier transform algorithm; hashing array; block-cyclic structure; cyclic convolution

References


Duhamel P. Fast Fourier Transform: A tutorial Review and a State of the Art / P. Duhamel, M. Vitterli // Signal Processing. – 1990. – Vol.19. – P. 259-299. DOI: 10.1016/0165-1684(90)90158-U.

Chu E. Inside the FFT black box. Serial and Parallel Fast Fourier Transform Algorithms / E. Chu, A. George. – Boca Raton: CRC Press LLC, 2000.

Tolimiery R. Algorithms for Discrete Fourier Transform and

Convolution / R. Tolimiery, M. An, C. Lu. – New York : Springer-Verlag, (s.ed.), 1997. – 267 p. DOI: 10.1007/978-1-4757-2767-8.

Prots’ko I. Becoming of Discrete Harmonic Transform Using

Cyclic Convolutions / I. Prots’ko, R. Rykmas // American Journal of Circuits, Systems and Signal Processing. – 2015. – Vol. 1. – P.114–119.

Rader С. М. Discrete Fourier Transforms When the Number of Data Samples is Prime / С. М. Rader // Proceedings of IEEE. – 1968. – Vol. 56. – P. 1107–1108. DOI: 10.1109/

PROC.1968.6477.

Winograd S. On computing the discrete Fourier transform /

S. Winograd // Proceedings National Academy of Science USA,

Mathematics. – 1976. – Vol. 73, No. 4. – P. 1005–1006.

DOI: 10.1073/pnas.73.4.1005.

Winograd S. On computing the discrete Fourier transforms /

S. Winograd // Mathematics of Computation. – 1978. – Vol. 32. – P. 175–199. DOI: 10.1090/S0025-5718-1978-0468306-4.

Blahut R. E. Fast algorithms for signal processing / R. E. Blahut. – Cambridge : University Press, 2010. DOI: 10.1017/

CBO9780511760921.

Nussbaumer H. J. Fast Fourier Transform and Convolution

Algorithms / H. J. Nussbaumer. – Berlin, Heidelberg : Springer-

Verlag, 1982. DOI: 10.1007/978-3-642-81897-4.

Lu C. Extension of Winograd Multiplicative Algorithm to

Transform Size N = p2q, p2qr and Their Implementation.

Proceedings of International Conference on Acoustic / C. Lu, R.

Tolimieri. – Speech, Signal Processing (ICASSP 89). Scotland,

Silverman H. F. An introduction to Programming the Winograd Fourier Transform algorithm (WFTA) / H. F. Silverman // IEEE Transactions on Acoustic, Speech, Signal Processing (ASSP). – 1977. – Vol. 25, No. 2. – P. 152–165. DOI: 10.1109/TASSP.1977.1162924

Patterson R. W. Fixed Point Error Analysis of Winograd Fourier Transform Algorithms / R. W. Patterson, J. H. McClellan // IEEE Transactions on Acoustic, Speech, Signal Processing (ASSP). – 1978. – P. 447–455. DOI: 10.1109/TASSP.1978.1163134

Lavoie P. A high-speed CMOS implementation of the Winograd Fourier transform algorithm / P. Lavoie // IEEE Transactions of Signal Processing. – 1996. – Vol. 44, No. 8. – P. 2121–2126. DOI: 10.1109/78.533738


GOST Style Citations


1. Duhamel P. Fast Fourier Transform: A tutorial Review and a State
of the Art / P. Duhamel, M. Vitterli // Signal Processing. – 1990. –
Vol.19. – P. 259-299. DOI: 10.1016/0165-1684(90)90158-U.
2. Chu E. Inside the FFT black box. Serial and Parallel Fast Fourier
Transform Algorithms / E. Chu, A. George. – Boca Raton: CRC
Press LLC, 2000.
3. Tolimiery R. Algorithms for Discrete Fourier Transform and
Convolution / R. Tolimiery, M. An, C. Lu. – New York : Springer-
Verlag, (s.ed.), 1997. – 267 p. DOI: 10.1007/978-1-4757-2767-8.
4. Prots’ko I. Becoming of Discrete Harmonic Transform Using
Cyclic Convolutions / I. Prots’ko, R. Rykmas // American Journal
of Circuits, Systems and Signal Processing. – 2015. – Vol. 1. –
P.114–119.
5. Rader С. М. Discrete Fourier Transforms When the Number of
Data Samples is Prime / С. М. Rader // Proceedings of IEEE. –
1968. – Vol. 56. – P. 1107–1108. DOI: 10.1109/
PROC.1968.6477.
6. Winograd S. On computing the discrete Fourier transform /
S. Winograd // Proceedings National Academy of Science USA,
Mathematics. – 1976. – Vol. 73, No. 4. – P. 1005–1006.
DOI: 10.1073/pnas.73.4.1005.
7. Winograd S. On computing the discrete Fourier transforms /
S. Winograd // Mathematics of Computation. – 1978. – Vol. 32. –
P. 175–199. DOI: 10.1090/S0025-5718-1978-0468306-4.
8. Blahut R. E. Fast algorithms for signal processing / R. E. Blahut. –
Cambridge : University Press, 2010. DOI: 10.1017/
CBO9780511760921.
9. Nussbaumer H. J. Fast Fourier Transform and Convolution
Algorithms / H. J. Nussbaumer. – Berlin, Heidelberg : Springer-
Verlag, 1982. DOI: 10.1007/978-3-642-81897-4.
10. Lu C. Extension of Winograd Multiplicative Algorithm to
Transform Size N = p2q, p2qr and Their Implementation.
Proceedings of International Conference on Acoustic / C. Lu, R.
Tolimieri. – Speech, Signal Processing (ICASSP 89). Scotland,
1989.
11. Silverman H. F. An introduction to Programming the Winograd
Fourier Transform algorithm (WFTA) / H. F. Silverman // IEEE
Transactions on Acoustic, Speech, Signal Processing (ASSP). –
1977. – Vol. 25, No. 2. – P. 152–165. DOI: 10.1109/
TASSP.1977.1162924
12. Patterson R. W. Fixed Point Error Analysis of Winograd Fourier
Transform Algorithms / R. W. Patterson, J. H. McClellan // IEEE
Transactions on Acoustic, Speech, Signal Processing (ASSP). –
1978. – P. 447–455. DOI: 10.1109/TASSP.1978.1163134.
13. Lavoie P. A high-speed CMOS implementation of the Winograd
Fourier transform algorithm / P. Lavoie // IEEE Transactions of
Signal Processing. – 1996. – Vol. 44, No. 8. – P. 2121–2126.
DOI: 10.1109/78.533738






Copyright (c) 2018 I. O. Prots’ko, V. M. Teslyuk

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
Zaporizhzhya National Technical University, 
Zhukovskiy street, 64, Zaporizhzhya, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.