Applied sciences

Bulletin of the Polish Academy of Sciences Technical Sciences

Content

Bulletin of the Polish Academy of Sciences Technical Sciences | 2025 | 73 | 4

Download PDF Download RIS Download Bibtex

Abstract

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.
Go to article

Authors and Affiliations

Marina Polyakova
1
ORCID: ORCID
Anna Witenberg
2
ORCID: ORCID
Aleksandr Cariow
3
ORCID: ORCID

  1. Institute of Computer Systems, Odesa Polytechnic National University, Shevchenko 1, Odesa, 65044, Ukraine
  2. Institute of Telecommunications and Computer Science, University of Science and Technology, al. prof. S. Kaliskiego 7, 85-796 Bydgoszcz, Poland
  3. Faculty of Computer Science and Information Technology, West Pomeranian University of Technology in Szczecin, Żołnierska 49, 71-210 Szczecin, Poland

Instructions for authors

Guide for Authors

https://www.editorialsystem.com/bpasts/journal/for_authors/

As of January 1st, 2025, there are changes in the fees for open access publications in Bulletin of the Polish Academy of Sciences Technical Sciences: 2000 PLN (approx. 500 EUR) - up to 8 pages of the journal format and mandatory over-length charges of 250 PLN (approx. 60 EUR) per page (see the above link with instructions for Authors for details)

Guide for Reviewers

https://www.editorialsystem.com/bpasts/journal/for_reviewers/

Call for Papers

https://www.editorialsystem.com/bpasts/journal/call_for_papers/

Guide for Guest Editors

https://www.editorialsystem.com/editor/bpasts/journal/page1/

Additional info

NEW PUBLICATION FEES
Articles submitted by December 31st, 2024: existing fee: 1500 PLN (and mandatory over-length charges of 230 PLN per page)
Articles submitted from January 1st, 2025: new fee: 2000 PLN (approx. 500 EUR- depending on the exchange rate) - a flat fee per paper up to 8 pages of the journal format (each additional page will be charged an additional 250 PLN).

This page uses 'cookies'. Learn more