Marina Polyakova
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Marina Polyakova has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Aleksandr Cariow
Faculty of Computer Science and Information Technology, West Pomeranian University of Technology in Szczecin, Żołnierska 49, 71-210 Szczecin, Poland
11 shared publications - Anna Witenberg
Faculty of Telecommunications, Computer Science and Electrical Engineering, Bydgoszcz University of Science and Technology, Bydgoszcz, Poland
3 shared publications - Janusz Piotr Paplinski
West Pomeranian University of Technology in Szczecin
2 shared publications Aleksandr Cariow
Faculty of Computer Science and Information Technology, West Pomeranian University of Technology in Szczecin, Szczecin, Poland
1 shared publication- Dmytro Kolodochka1 shared publication
- Jekatierina Sklyar
West Pomeranian University of Technology in Szczecin
1 shared publication
Latest Publications
- 9 September 2026
- Published by PIAP - Industrial Research Institute for Automation and Measurements in Pomiary Automatyka Robotyka
- Vol. 30 (3) , 109-116
A Fast Algorithm for Quaternion Multiplication
Quaternion algebra is used in many fields, including electrical engineering, robotics, computer graphics, navigation systems, and image and signal processing. In these applications, reducing computational complexity is particularly important, especially by limiting the number of real multiplications required to compute quaternion products. This paper proposes fast quaternion multiplication algorithms that reduce the number of real multiplications compared with the classical direct method while preserving computational correctness.
- 9 September 2026
- Published by PIAP - Industrial Research Institute for Automation and Measurements in Pomiary Automatyka Robotyka
- Vol. 30 (3) , 109-116
A Fast Algorithm for Quaternion Multiplication
Quaternion algebra is used in many fields, including electrical engineering, robotics, computer graphics, navigation systems, and image and signal processing. In these applications, reducing computational complexity is particularly important, especially by limiting the number of real multiplications required to compute quaternion products. This paper proposes fast quaternion multiplication algorithms that reduce the number of real multiplications compared with the classical direct method while preserving computational correctness.
- Open Access
- 24 August 2026
- Published by Springer Nature in Scientific Reports
- Vol. 16 (1)
A new discrete Tchebichef-like transform and its application in speech denooising
- 24 August 2026
- Published by Springer Nature in Scientific Reports
- Vol. 16 (1)
Open AccessA new discrete Tchebichef-like transform and its application in speech denooising
- Open Access
- 5 February 2026
- Published by MDPI AG in Electronics
- Vol. 15 (3) , 699
Fast Algorithms for Short-Length Type VI Discrete Cosine Transform
In this paper, new fast algorithms for computing the discrete cosine transform type VI (DCT-VI) are proposed, with a special emphasis on short input sequences of three to eight samples. Fast algorithms for small discrete trigonometric transformations are directly used for efficient processing of small data sets and also serve as fundamental building blocks for constructing algorithms for larger trigonometric transforms. By exploiting the intrinsic structural properties of the DCT-VI matrices of different sizes, the proposed methods significantly reduce arithmetic complexity compared to the conventional matrix–vector multiplication approach. The paper presents a detailed mathematical formulation of the algorithms, supported by data-flow graphs that illustrate the computational structure and facilitate the precise estimation of arithmetic operations. Optimized pseudocode implementations incorporating variable reuse are also introduced to facilitate practical realization in software environments. Performance analysis demonstrates a substantial reduction in the number of multiplications (up to 66%) and a slight decrease in additions (approximately 9%) for input sizes ranging from three to eight, thereby improving the execution speed of the considering transform. The proposed algorithms are well-suited for applications in video coding, data compression, and digital signal processing, where computational efficiency is critical.
- 5 February 2026
- Published by MDPI AG in Electronics
- Vol. 15 (3) , 699
Open AccessFast Algorithms for Short-Length Type VI Discrete Cosine Transform
In this paper, new fast algorithms for computing the discrete cosine transform type VI (DCT-VI) are proposed, with a special emphasis on short input sequences of three to eight samples. Fast algorithms for small discrete trigonometric transformations are directly used for efficient processing of small data sets and also serve as fundamental building blocks for constructing algorithms for larger trigonometric transforms. By exploiting the intrinsic structural properties of the DCT-VI matrices of different sizes, the proposed methods significantly reduce arithmetic complexity compared to the conventional matrix–vector multiplication approach. The paper presents a detailed mathematical formulation of the algorithms, supported by data-flow graphs that illustrate the computational structure and facilitate the precise estimation of arithmetic operations. Optimized pseudocode implementations incorporating variable reuse are also introduced to facilitate practical realization in software environments. Performance analysis demonstrates a substantial reduction in the number of multiplications (up to 66%) and a slight decrease in additions (approximately 9%) for input sizes ranging from three to eight, thereby improving the execution speed of the considering transform. The proposed algorithms are well-suited for applications in video coding, data compression, and digital signal processing, where computational efficiency is critical.
- Open Access
- 1 January 2026
- Published by MDPI AG in Electronics
- Vol. 15 (1) , 207
Fast DCT-VIII Algorithms for Short-Length Input Sequences
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.
- 1 January 2026
- Published by MDPI AG in Electronics
- Vol. 15 (1) , 207
Open AccessFast DCT-VIII Algorithms for Short-Length Input Sequences
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.
- Open Access
- 24 December 2025
- Published by MDPI AG in Electronics
- Vol. 15 (1) , 98
Fast Algorithms for Small-Size Type VII Discrete Cosine Transform
This paper presents new fast algorithms for the type VII discrete cosine transform (DCT-VII) applied to input data sequences of lengths ranging from 3 to 8. Fast algorithms for small-sized trigonometric transforms enable the processing of small data blocks in image and video coding with low computational complexity. To process the information in image and video coding standards, the fast DCT-VII algorithms can be used, taking into account the relationships between the DCT-VII and the type II discrete cosine transform (DCT-II). Additionally, such algorithms can be used in other digital signal processing tasks as components for constructing algorithms for large-sized transforms, leading to reduced system complexity. Existing fast odd DCT algorithms have been designed using relationships among discrete cosine transforms (DCTs), discrete sine transforms (DSTs), and the discrete Fourier transform (DFT); among different types of DCTs and DSTs; and between the coefficients of the transform matrix. However, these algorithms require a relatively large number of multiplications and additions. The process of obtaining such algorithms is difficult to understand and implement. To overcome these shortcomings, this paper applies a structural approach to develop new fast DCT-VII algorithms. The process begins by expressing the DCT-VII as a matrix-vector multiplication, then reshaping the block structure of the DCT-VII matrix to align with matrix patterns known from the basic papers in which the structural approach was introduced. If the matrix block structure does not match any known pattern, rows and columns are reordered, and sign changes are applied as needed. If this is insufficient, the matrix is decomposed into the sum of two or more matrices, each analyzed separately and transformed similarly if required. As a result, factorizations of DCT-VII matrices for different input sequence lengths are obtained. Based on these factorizations, fast DCT-VII algorithms with reduced arithmetic complexity are constructed and presented with pseudocode. To illustrate the computational flow of the resulting algorithms and their modular design, which is suitable for VLSI implementation, data-flow graphs are provided. The new DCT-VII algorithms reduce the number of multiplications by approximately 66% compared to direct matrix-vector multiplication, although the number of additions decreases by only about 6%.
- 24 December 2025
- Published by MDPI AG in Electronics
- Vol. 15 (1) , 98
Open AccessFast Algorithms for Small-Size Type VII Discrete Cosine Transform
This paper presents new fast algorithms for the type VII discrete cosine transform (DCT-VII) applied to input data sequences of lengths ranging from 3 to 8. Fast algorithms for small-sized trigonometric transforms enable the processing of small data blocks in image and video coding with low computational complexity. To process the information in image and video coding standards, the fast DCT-VII algorithms can be used, taking into account the relationships between the DCT-VII and the type II discrete cosine transform (DCT-II). Additionally, such algorithms can be used in other digital signal processing tasks as components for constructing algorithms for large-sized transforms, leading to reduced system complexity. Existing fast odd DCT algorithms have been designed using relationships among discrete cosine transforms (DCTs), discrete sine transforms (DSTs), and the discrete Fourier transform (DFT); among different types of DCTs and DSTs; and between the coefficients of the transform matrix. However, these algorithms require a relatively large number of multiplications and additions. The process of obtaining such algorithms is difficult to understand and implement. To overcome these shortcomings, this paper applies a structural approach to develop new fast DCT-VII algorithms. The process begins by expressing the DCT-VII as a matrix-vector multiplication, then reshaping the block structure of the DCT-VII matrix to align with matrix patterns known from the basic papers in which the structural approach was introduced. If the matrix block structure does not match any known pattern, rows and columns are reordered, and sign changes are applied as needed. If this is insufficient, the matrix is decomposed into the sum of two or more matrices, each analyzed separately and transformed similarly if required. As a result, factorizations of DCT-VII matrices for different input sequence lengths are obtained. Based on these factorizations, fast DCT-VII algorithms with reduced arithmetic complexity are constructed and presented with pseudocode. To illustrate the computational flow of the resulting algorithms and their modular design, which is suitable for VLSI implementation, data-flow graphs are provided. The new DCT-VII algorithms reduce the number of multiplications by approximately 66% compared to direct matrix-vector multiplication, although the number of additions decreases by only about 6%.
- Open Access
- 8 October 2025
- Published by MDPI AG in Electronics
- Vol. 14 (19) , 3958
Fast Discrete Krawtchouk Transform Algorithms for Short-Length Input Sequences
This paper presents new fast discrete Krawtchouk transform (DKT) algorithms for input sequences of length 3 to 8. Small-sized DKT algorithms can be utilized in image processing applications to extract local image features formed by a sliding spatial window, and they can also serve as building blocks for developing larger-sized algorithms. Existing strategies to reduce the computational complexity of DKT mainly focus on modifying the recurrence relations for Krawtchouk polynomials, dividing the input signals into blocks or layers, or using different methods to approximate the coefficient values. Algorithms developed using the first two strategies are computationally intensive, which introduces a significant time delay in the computation process. Algorithms based on the approximation of polynomial coefficient values reduce computation time but at the expense of reduced accuracy. We use a different approach based on reducing the block structure of the matrix to one of the previously developed block-structural patterns, which allows us to factorize the resulting matrix in such a way that it leads to a reduction in the computational complexity of the synthesized algorithm. We describe the algorithmic solutions we have obtained through data flow graphs. The proposed DKT algorithms reduce the number of multiplications, additions, and shifts by an average of 58%, 27%, and 68%, respectively, compared to the direct computation of DKT via matrix-vector product. These characteristics were averaged across the considered input sizes (from 3 to 8).
- 8 October 2025
- Published by MDPI AG in Electronics
- Vol. 14 (19) , 3958
Open AccessFast Discrete Krawtchouk Transform Algorithms for Short-Length Input Sequences
This paper presents new fast discrete Krawtchouk transform (DKT) algorithms for input sequences of length 3 to 8. Small-sized DKT algorithms can be utilized in image processing applications to extract local image features formed by a sliding spatial window, and they can also serve as building blocks for developing larger-sized algorithms. Existing strategies to reduce the computational complexity of DKT mainly focus on modifying the recurrence relations for Krawtchouk polynomials, dividing the input signals into blocks or layers, or using different methods to approximate the coefficient values. Algorithms developed using the first two strategies are computationally intensive, which introduces a significant time delay in the computation process. Algorithms based on the approximation of polynomial coefficient values reduce computation time but at the expense of reduced accuracy. We use a different approach based on reducing the block structure of the matrix to one of the previously developed block-structural patterns, which allows us to factorize the resulting matrix in such a way that it leads to a reduction in the computational complexity of the synthesized algorithm. We describe the algorithmic solutions we have obtained through data flow graphs. The proposed DKT algorithms reduce the number of multiplications, additions, and shifts by an average of 58%, 27%, and 68%, respectively, compared to the direct computation of DKT via matrix-vector product. These characteristics were averaged across the considered input sizes (from 3 to 8).
- Open Access
- 15 July 2025
- Published by MDPI AG in Electronics
- Vol. 14 (14) , 2841
Fast Algorithms for the Small-Size Type IV Discrete Hartley Transform
This paper presents new fast algorithms for the fourth type discrete Hartley transform (DHT-IV) for input data sequences of lengths from 3 to 8. Fast algorithms for small-sized trigonometric transforms can be used as building blocks for synthesizing algorithms for large-sized transforms. Additionally, they can be utilized to process small data blocks in various digital signal processing applications, thereby reducing overall system latency and computational complexity. The existing polynomial algebraic approach and the approach based on decomposing the transform matrix into cyclic convolution submatrices involve rather complicated housekeeping and a large number of additions. To avoid the noted drawback, this paper uses a structural approach to synthesize new algorithms. The starting point for constructing fast algorithms was to represent DHT-IV as a matrix–vector product. The next step was to bring the block structure of the DHT-IV matrix to one of the matrix patterns following the structural approach. In this case, if the block structure of the DHT-IV matrix did not match one of the existing patterns, its rows and columns were reordered, and, if necessary, the signs of some entries were changed. If this did not help, the DHT-IV matrix was represented as the sum of two or more matrices, and then each matrix was analyzed separately, if necessary, subjecting the matrices obtained by decomposition to the above transformations. As a result, the factorizations of matrix components were obtained, which led to a reduction in the arithmetic complexity of the developed algorithms. To illustrate the space–time structures of computational processes described by the developed algorithms, their data flow graphs are presented, which, if necessary, can be directly mapped onto the VLSI structure. The obtained DHT-IV algorithms can reduce the number of multiplications by an average of 75% compared with the direct calculation of matrix–vector products. However, the number of additions has increased by an average of 4%.
- 15 July 2025
- Published by MDPI AG in Electronics
- Vol. 14 (14) , 2841
Open AccessFast Algorithms for the Small-Size Type IV Discrete Hartley Transform
This paper presents new fast algorithms for the fourth type discrete Hartley transform (DHT-IV) for input data sequences of lengths from 3 to 8. Fast algorithms for small-sized trigonometric transforms can be used as building blocks for synthesizing algorithms for large-sized transforms. Additionally, they can be utilized to process small data blocks in various digital signal processing applications, thereby reducing overall system latency and computational complexity. The existing polynomial algebraic approach and the approach based on decomposing the transform matrix into cyclic convolution submatrices involve rather complicated housekeeping and a large number of additions. To avoid the noted drawback, this paper uses a structural approach to synthesize new algorithms. The starting point for constructing fast algorithms was to represent DHT-IV as a matrix–vector product. The next step was to bring the block structure of the DHT-IV matrix to one of the matrix patterns following the structural approach. In this case, if the block structure of the DHT-IV matrix did not match one of the existing patterns, its rows and columns were reordered, and, if necessary, the signs of some entries were changed. If this did not help, the DHT-IV matrix was represented as the sum of two or more matrices, and then each matrix was analyzed separately, if necessary, subjecting the matrices obtained by decomposition to the above transformations. As a result, the factorizations of matrix components were obtained, which led to a reduction in the arithmetic complexity of the developed algorithms. To illustrate the space–time structures of computational processes described by the developed algorithms, their data flow graphs are presented, which, if necessary, can be directly mapped onto the VLSI structure. The obtained DHT-IV algorithms can reduce the number of multiplications by an average of 75% compared with the direct calculation of matrix–vector products. However, the number of additions has increased by an average of 4%.
- Open Access
The Fast Discrete Tchebichef Transform Algorithms for Short-Length Input Sequences
In this article, the fast algorithms for the discrete Tchebichef transform (DTT) are proposed for input sequences of lengths in the range from 3 to 8. At present, DTT is widely applied in signal processing, image compression, and video coding. The review of the articles related to fast DTT algorithms has shown that such algorithms are mainly developed for input signal lengths 4 and 8. However, several problems exist for which signal and image processing with different apertures is required. To avoid this shortcoming, the structural approach and a sparse matrix factorization are applied in this paper to develop fast real DTT algorithms for short-length input signals. According to the structural approach, the rows and columns of the transform matrix are rearranged, possibly by changing the signs of some rows or columns. Next, the matched submatrix templates are extracted from the matrix structure and decomposed into a matrix product to construct the factorization of an initial matrix. A sparse matrix factorization assumes that the butterfly architecture can be extracted from the transform matrix. Combining the structural approach with a sparse matrix factorization, we obtained the matrix representation with reduced computational complexity. Based on the obtained matrix representation, the fast algorithms were developed for the real DTT via the data flow graphs. The fast algorithms for integer DTT can be easily obtained using the constructed data flow graphs. To confirm the correctness of the designed algorithms, the MATLAB R2023b software was applied. The constructed factorizations of the real DTT matrices reduce the number of multiplication operations by 78% on average compared to the direct matrix-vector product at signal lengths in the range from 3 to 8. The number of additions decreased by 5% on average within the same signal length range.
Open AccessThe Fast Discrete Tchebichef Transform Algorithms for Short-Length Input Sequences
In this article, the fast algorithms for the discrete Tchebichef transform (DTT) are proposed for input sequences of lengths in the range from 3 to 8. At present, DTT is widely applied in signal processing, image compression, and video coding. The review of the articles related to fast DTT algorithms has shown that such algorithms are mainly developed for input signal lengths 4 and 8. However, several problems exist for which signal and image processing with different apertures is required. To avoid this shortcoming, the structural approach and a sparse matrix factorization are applied in this paper to develop fast real DTT algorithms for short-length input signals. According to the structural approach, the rows and columns of the transform matrix are rearranged, possibly by changing the signs of some rows or columns. Next, the matched submatrix templates are extracted from the matrix structure and decomposed into a matrix product to construct the factorization of an initial matrix. A sparse matrix factorization assumes that the butterfly architecture can be extracted from the transform matrix. Combining the structural approach with a sparse matrix factorization, we obtained the matrix representation with reduced computational complexity. Based on the obtained matrix representation, the fast algorithms were developed for the real DTT via the data flow graphs. The fast algorithms for integer DTT can be easily obtained using the constructed data flow graphs. To confirm the correctness of the designed algorithms, the MATLAB R2023b software was applied. The constructed factorizations of the real DTT matrices reduce the number of multiplication operations by 78% on average compared to the direct matrix-vector product at signal lengths in the range from 3 to 8. The number of additions decreased by 5% on average within the same signal length range.
- Open Access
- 28 February 2025
- Published by MDPI AG in Electronics
- Vol. 14 (5) , 996
Fast Algorithms for Short-Length Odd-Time and Odd-Frequency Discrete Hartley Transforms
This paper proposes fast algorithms for odd-time and odd-frequency discrete Hartley transforms (DHTs) with normalization if the size of the input sequence ranges from 2 to 8. Fast algorithms for small-sized inputs can be included as modules in fast algorithms for discrete transforms of large-length input sequences. The existing fast odd-time DHT and odd-frequency DHT algorithms are primarily radix-type algorithms, specifically, radix-2 and prime factor algorithms. However, the algorithms in the literature do not normalize the initial transform. This means that after applying such algorithms, additional N multiplications are required. In this paper, the structural approach is exploited supposing that the starting point to design the fast algorithms is a matrix vector product expression. The factorization of the matrices of DHT coefficients is produced to reduce computational complexity taking into account the repetition and arranging of the matrix entries. The strict mathematical background proves the correctness of the obtained algorithmic solutions. Also, the MATLAB R2023b environment was applied for testing of the performance of the proposed algorithms. The obtained factorizations of the odd-time DHT and odd-frequency DHT matrices allow us to reduce the number of multiplications by 69%, while the amount of additions is decreased by about of 5% for odd-time DHTs and 8% for odd-frequency DHTs if the length of input data is in the range from 2 to 8. A comparison is provided with the direct calculation of the matrix vector product. Additionally, the computational complexity for each obtained solution is compared with the computational complexity of the existing fast algorithms for odd-time DHTs and odd-frequency DHTs. In addition, data flow graphs have been created for the proposed odd-time DHT and odd-frequency DHT algorithms. The modular space–time structure of the resulting data flow graphs is suitable for VLSI implementation.
- 28 February 2025
- Published by MDPI AG in Electronics
- Vol. 14 (5) , 996
Open AccessFast Algorithms for Short-Length Odd-Time and Odd-Frequency Discrete Hartley Transforms
This paper proposes fast algorithms for odd-time and odd-frequency discrete Hartley transforms (DHTs) with normalization if the size of the input sequence ranges from 2 to 8. Fast algorithms for small-sized inputs can be included as modules in fast algorithms for discrete transforms of large-length input sequences. The existing fast odd-time DHT and odd-frequency DHT algorithms are primarily radix-type algorithms, specifically, radix-2 and prime factor algorithms. However, the algorithms in the literature do not normalize the initial transform. This means that after applying such algorithms, additional N multiplications are required. In this paper, the structural approach is exploited supposing that the starting point to design the fast algorithms is a matrix vector product expression. The factorization of the matrices of DHT coefficients is produced to reduce computational complexity taking into account the repetition and arranging of the matrix entries. The strict mathematical background proves the correctness of the obtained algorithmic solutions. Also, the MATLAB R2023b environment was applied for testing of the performance of the proposed algorithms. The obtained factorizations of the odd-time DHT and odd-frequency DHT matrices allow us to reduce the number of multiplications by 69%, while the amount of additions is decreased by about of 5% for odd-time DHTs and 8% for odd-frequency DHTs if the length of input data is in the range from 2 to 8. A comparison is provided with the direct calculation of the matrix vector product. Additionally, the computational complexity for each obtained solution is compared with the computational complexity of the existing fast algorithms for odd-time DHTs and odd-frequency DHTs. In addition, data flow graphs have been created for the proposed odd-time DHT and odd-frequency DHT algorithms. The modular space–time structure of the resulting data flow graphs is suitable for VLSI implementation.
- Open Access
- 19 February 2025
- Published by Polish Academy of Sciences Chancellery in Bulletin Of The Polish Academy Of Sciences-Technical Sciences
- p. 153827
The fast type-IV discrete sine transform algorithms for short-length input sequences
The fast algorithms of discrete sinusoidal transform of the fourth type (DST-IV) for small-length input data in the range of lengths from 2 to 9 are developed. Fast algorithms for short input data sequences are subsequently used as building blocks for designing fast algorithms of large-sized discrete transforms. Applying the fast DST-IV algorithms for small-size block processing can reduce overall system complexity and delay, allowing detailed signal processing. As a result of the literature review, two main approaches to developing fast discrete sine transform (DST) algorithms were identified, namely, the polynomial algebraic approach and the matrix factorization approach. In the paper, the last approach is exploited. A matrix-vector product expression of the DST-IV is the starting point for designing the fast algorithms. Then based on the repetition and arranging of the matrix elements, the factorisation of the matrices of coefficients of DST-IV is produced to reduce computational complexity. The correctness of the obtained algorithmic solutions was justified theoretically using a strict mathematical background of each of them. The elaborated algorithms were then further tested using MATLAB R2023b software to finally confirm their performance. The resulting factorizations of the DST-IV matrices reduce the number of multiplications by 63% but increase the number of additions by 8% on average in the range of signal sample numbers from 3 to 9. It has been observed that for even-length input sequences, the reduction in the number of multiplications is not as significant as for odd-length sequences. For some other well-known discrete trigonometric transforms (discrete Fourier transform, discrete Hartley transform) the opposite situation holds. The proposed DST-IV fast algorithms do not limit the length of the input data sequence to powers of two or three. The data flow graphs constructed for the proposed algorithms reveal their modular space-time structure suitable for VLSI implementation. Keywords: discrete sine transform; matrix factorization; fast algorithms; computational complexity; digital signal processing.
- 19 February 2025
- Published by Polish Academy of Sciences Chancellery in Bulletin Of The Polish Academy Of Sciences-Technical Sciences
- p. 153827
Open AccessThe fast type-IV discrete sine transform algorithms for short-length input sequences
The fast algorithms of discrete sinusoidal transform of the fourth type (DST-IV) for small-length input data in the range of lengths from 2 to 9 are developed. Fast algorithms for short input data sequences are subsequently used as building blocks for designing fast algorithms of large-sized discrete transforms. Applying the fast DST-IV algorithms for small-size block processing can reduce overall system complexity and delay, allowing detailed signal processing. As a result of the literature review, two main approaches to developing fast discrete sine transform (DST) algorithms were identified, namely, the polynomial algebraic approach and the matrix factorization approach. In the paper, the last approach is exploited. A matrix-vector product expression of the DST-IV is the starting point for designing the fast algorithms. Then based on the repetition and arranging of the matrix elements, the factorisation of the matrices of coefficients of DST-IV is produced to reduce computational complexity. The correctness of the obtained algorithmic solutions was justified theoretically using a strict mathematical background of each of them. The elaborated algorithms were then further tested using MATLAB R2023b software to finally confirm their performance. The resulting factorizations of the DST-IV matrices reduce the number of multiplications by 63% but increase the number of additions by 8% on average in the range of signal sample numbers from 3 to 9. It has been observed that for even-length input sequences, the reduction in the number of multiplications is not as significant as for odd-length sequences. For some other well-known discrete trigonometric transforms (discrete Fourier transform, discrete Hartley transform) the opposite situation holds. The proposed DST-IV fast algorithms do not limit the length of the input data sequence to powers of two or three. The data flow graphs constructed for the proposed algorithms reveal their modular space-time structure suitable for VLSI implementation. Keywords: discrete sine transform; matrix factorization; fast algorithms; computational complexity; digital signal processing.