A Study on the Implementation of Two-Dimensional Discrete Cosine Transform

[[abstract]]數位影像及視訊在日常生活中的應用可以說是日漸普及。而其中，離散餘弦轉換是最廣泛被利用在數位影像及視訊壓縮編碼標準中的轉換編碼法。通常一個視訊編碼器完成視訊編碼工作需要大量的計算量，而離散餘弦轉換以及反離散餘弦轉換更是其中兩個計算密集度非常高的單元。 在這篇論文中，對於一個二維離散餘弦轉換的實現，我們採用了分散式算術架構的構想來排除對於乘法器的使用需求。而我們更進一步的改進了原本在分散式算術架構中的ROM-Accumulator架構，設法去解決ROM在硬體實現中的因難和它所須花費的硬體代價。在我們的修改型ROM-Accumulator架構中，對於原本用來產生運算中所須固定餘弦函數之係數的硬體ROM，在我們的架構中可以輕易的採用一些簡單邏輯閘所組成邏輯區塊來取代。整個二維離散餘弦轉換架構的實現，我們利用行-列分解的方式，來對二維的影像資料分別作行向量方向及列向量方向的一維離散餘弦轉換，如此的架構方式一般來說較為規則且適合硬體的實現。而對每個一維離散餘弦轉換的實現，我們提出一個奇-偶頻率分離並配合二次及三次收斂分解的演算法，如此可以進一步的減少一維離散餘弦轉換的計算複雜度。最後，針對行-列分解架構中所須的轉置記憶體，我們也提出一個新的單一方向轉置記憶體架構。利用這個新的轉置記憶體架構，對每筆資料我們可以比傳統轉置記憶體節省一半的轉置時間。我們所提出的整個二維離散餘弦轉換架構完全適合管線化操作，並具有規則化及低硬體成本的特性，非常適合硬體實現。[[abstract]]Several digital image and video applications are becoming more popular in our everyday lives. The discrete cosine transform (DCT) is at present the most widely used transformation in the image and video compression algorithm. Image and video encoder/decoder (codec) require huge amounts of computation since the DCT and the inverse DCT (IDCT) are two of the components that are very computationally intensive in video encoder. In this thesis, we propose the multiplier-less distributed arithmetic (DA) architecture with the modified ROM-Accumulator (RAC) structures for the implementation of two-dimensional (2-D) DCT without any ROM area. In our modified RAC structures, the cosine function coefficients are generated by logical block which only need some logic gates instead of ROM area. We also use the row-column decomposition (RCD) method for computing the 2-D DCT so that our proposed structure has more regularity for hardware implementation. And, in the algorithm for computing each row-wise and each column-wise 1-D DCT, we use the even-odd frequency decomposition method with the second and third recursive iterations to further reduce the computational complexity. Final, we propose a new transposition memory architecture. In our proposed transposition memory architecture, half of the transposition time in the traditional architecture can be saved. The proposed two-dimensional DCT architecture is fully pipelining, keeps the regularity of the structure suitable for hardware implementation and has low hardware cost