# A Novel Low-Complexity and Parallel Algorithm for DCT IV Transform and Its GPU Implementation
## 1 Introduction  
In 1972, [PERSON] proposed the discrete cosine transform for the first time [1]. It is well known under the abbreviation DCT. DCT plays a crucial role in the digital world, being used in data compression and coding for digital images (DCT is the base of the JPEG 1 standard--ISO/IEC 10918 [2]) [3, 4], digital audio (used in modern audio coding standards like Dolby Digital, WMA, MP3, HDC, MPEG-H 3D Audio or AAC) [5], speech coding (such as AAC-LD, Siren, G.722.1, G.729.1 and Opus) [6, 7], digital radio (such as AAC+ and DAB+) [8], digital video (such as H.261, H.263, H.264 (AVC or MPEG-4), H.265 (HEVC or MPEG-H Part 2) and H.266) [9, 10], or digital television (in video coding standards for SDTV, HDTV, and VOD) [9, 10].  
The acronyms used in this manuscript can be found in Table 1 in Appendix 1.  
In 2017, internet video traffic was 73% of all worldwide consumer traffic. Right now, this percentage is more than 80% [11]. The pandemic outbreak reinforced and supported this growth and the necessity of users to use video material. Moreover, a gradual transition from the SD (standard-definition) video format to the HD (high-definition) video format is observed, moving now towards the UHD (ultra-high-definition) video format [9, 10].  
From all of these, we have observed that DCT and its variants are extensively used in all modern audio, image, and video compression standards [4, 7]. There are several types of DCT transforms, but the most known ones are DCT II, DCT III, and DCT IV. The DCT IV and DST IV were first introduced by [PERSON] [12] and have some important applications, such as spectral analysis, audio and image coding, and signal processing [13, 14, 15].  
Both DCT IV and DST IV are computationally intensive, and, for real-time applications, fast software [16; 17; 18; 19] and even more parallel software implementations or hardware implementations [20; 21] are required. In order to obtain efficient parallel software implementations, some efficient restructuring solutions to put in evidence parallel structures with reduced arithmetic complexity are required. But, until now, there have only been a few parallel software implementations for DCT IV, and how to obtain an efficient parallel decomposition with reduced arithmetic complexity is a challenging problem.  
For an efficient VLSI implementation, it was shown that using regular and modular structures such as cycle convolution and circular correlation [22; 23] and efficient restructuring methods can lead to some optimal concurrent solutions.  
In this study, using some similar ideas, we decomposed the computation of DCT IV into parallel structures and, using the sub-expression sharing technique, we obtained an efficient parallel implementation with reduced arithmetic complexity.  
In conclusion, the primary goal of this study is to develop, implement, and test a specific implementation of the DCT IV algorithm that is very fast and very \"light\"--with minimal memory accesses. Of course, such an algorithm will also consume less energy. We chose the GPU architecture for the parallel implementation as it has been proved to be an excellent platform for the parallel implementation of numerical and DSP algorithms [24; 25; 26; 27; 28; 29].  
This study proposes a novel parallel implementation of the DCT IV algorithm that was implemented on a GPU architecture, but it can be run on different parallel architectures with at least four or eight cores. The novel algorithm was tested and analyzed using two development boards, Jetson AGX Xavier and Jetson Orin Nano.