Winograd’s algorithms are an effective tool for calculating the discrete Fourier transform (DFT). These algorithms described in well-known articles are traditionally represented either with the help of sets of recurrent relations or with the help of products of sparse matrices obtained on the basis of various methods of the DFT matrix factorization. Unfortunately, in the mentioned papers, it is not shown how the described relations were obtained or how the presented factorizations were found. In this paper, we use a simple, understandable and fairly unified approach to the derivation of the Winograd-type DFT algorithms for the cases N = 8, N = 16 and N = 32. It is easy to verify that algorithms for other lengths of sequences that are powers of two can be synthesized in a similar way.
The subject of this work is the development of fast algorithms for the discrete sinusoidal transformation of the second type (DST-II) for sequences of input data of small length N = 2, 3, 4, 5, 6, 7, 8. The starting point for the development of algorithms is the well-known possibility of representing any discrete transformation in the form of a matrix–vector product. Due to the remarkable structural properties of the matrices of the DST-II transformation base, these matrices can be successfully factorized, which should lead to a reduction in the computational complexity of the procedure as a whole. You can factorize matrices in different ways. The art of designing fast algorithms is to find the factorization that produces the maximum effect. We justified the correctness of the obtained algorithmic solutions theoretically, using strict mathematical derivations of each of them. The developed algorithms were then further tested using MATLAB R2023b software to finally confirm their performance. Finally, we presented estimates of the computational complexity for each solution obtained and compared them with direct computational methods that rely on the direct calculation of matrix–vector products.
Discrete cosine transforms (DCTs) are widely used in intelligent electronic systems for storing, processing, and transmitting data. Their popularity stems, on the one hand, from their unique properties and, on the other hand, from the availability of fast algorithms that minimize the computational and hardware complexity of their implementation. Until recently, the Type VIII DCT had been one of the least studied variants, with virtually no publications addressing fast algorithms for its implementation. However, this situation has changed, making the development of efficient implementation methods for this transform a timely and important research problem. In this paper, several algorithmic solutions for implementing the Type VIII DCT are proposed. A set of Type VIII DCT algorithms for small lengths N = 3, 4, 5, 6, 7 is presented. The effectiveness of the proposed solutions is due to the possibility of successful factorization of small-sized DCT-VIII matrices, leading to a reduction in the computational complexity of implementing transforms of this type. Compared with direct matrix–vector computation, the proposed algorithms achieve an approximate 53% reduction in the number of multiplications, at the cost of an increase of about 21% in the number of additions. This work continues a series of previously published studies aimed at creating a library of small-sized algorithms for discrete trigonometric transforms.
Winograd discrete Fourier transform algorithm (WDFT) is an effective tool for calculating the discrete Fourier transform (DFT). These algorithms described in well-known articles are traditionally represented either with the help of sets of recurrent relations or with the help of products of sparse matrices obtained on the basis of various methods of the DFT matrix factorization. Unfortunately, in the mentioned papers it is not shown how the described relations were obtained or how the presented factorizations were found. In this paper, we use a simple, understandable and fairly unified approach to the derivation of the Winograd DFT algorithms for the case N = 8. It is easy to verify that algorithms for other lengths of sequences that are powers of two can be synthesized in a similar way.
The subject of this paper is the development of rationalized algorithms of discrete sinusoidal transform of type I for short sequences of length N = 2, 3, 4, 5, 6, 7, and 8. Here, by the word “rationalization”, we mean the reduction of the number of arithmetic operations required to implement the algorithms. The arithmetic complexity of the developed algorithms is presented in the final table. For each algorithm, we also provide data flow graphs demonstrating the space–time structure of the computational processes. The algorithms were tested to verify their validity using MATLAB software (version R2023).