改進(jìn)的一維DCT方案設(shè)計(jì)與實(shí)現(xiàn)

1.引言

    Ahmed，Natarajan 和Rao在1974年首先提出了DCT算法[1]。從那時開始，它成為了圖像和視頻編碼最流行的算法，并被廣泛應(yīng)用，這主要有兩個原因：首先，它把圖像數(shù)據(jù)轉(zhuǎn)變成容易壓縮的形式；第二，它能有效地用軟件和硬件實(shí)現(xiàn)[2]。至今，基于行列變換的DCT被應(yīng)用最廣泛，因些，有必要對一維DCT的硬件設(shè)計(jì)的改進(jìn)并使其硬件資源達(dá)到最簡。

    分布式算法自提出20年來一直被廣泛應(yīng)用于VLSI與DSP中[3-8]。在它的運(yùn)用過程中，大多數(shù)的運(yùn)算量集成在加法器或乘法。因此，減少加法器或乘法器成了一大批學(xué)者們研究對象。

    經(jīng)研究發(fā)現(xiàn)，目前所用的分布式算法大都是基于組合電路設(shè)計(jì)的，即三級加法在同一個時鐘周期完成，由于電路的最小時鐘周期取決于電路中所需處理時間最多的模塊，因此，基于組合電路的時鐘處理頻率必大大受影響，故，我們考慮用時序電路來完成基于分布式算法的一維DCT，并且，為了加快處理速度，我們對一維DCT的變換數(shù)據(jù)進(jìn)行了分析，發(fā)現(xiàn)如果改變對DCT各數(shù)據(jù)的處理順序，更是可大大加快一維DCT的處理速度。

    下面是我們對基于分布式算法的一維DCT的研究:

2.分布式算法的相關(guān)知識 [3]

首先,考慮下式

                （2-1）

這里， 是常數(shù)， 是輸入的數(shù)據(jù)，寫成矩陣形式為：

                       （2-2）

如果 是一個N比特的二進(jìn)制數(shù)，則 可表示為：

                       （2-3）

其中  or  1而 i = 0 ,1 , … , N-1； 表示 的最高比特位(符號位)， 表示它的最低比特位。于是：

      （2-4）

這里INV(.)表示求補(bǔ)。
    于是，在一維DCT變換公式式

                            （2-5）

中我們令

                                     （2-6）

則：

            （2-8）

當(dāng)u=1時

如果運(yùn)算精度取為13比特，則用二進(jìn)制表示為：

                  （2-9）

                （2-10）

從上述分析很容易發(fā)現(xiàn)一維DCT可以完全用加法器來實(shí)現(xiàn)。

3.一維DCT的算式分析

首先，讓我們看看一維DCT各項(xiàng)算術(shù)式子：

第一個一維DCT變換系數(shù)的各項(xiàng)：

第二個一維DCT變換系數(shù)的各項(xiàng)：

第四個一維DCT變換系數(shù)的各項(xiàng)：

第三個一維DCT變換系數(shù)的各項(xiàng)：

第五個一維DCT變換系數(shù)的各項(xiàng)：

第六個一維DCT變換系數(shù)的各項(xiàng)：

第七個一維DCT變換系數(shù)的各項(xiàng)：

現(xiàn)在，我們來分析一下，這些項(xiàng)中的共用項(xiàng)。首先，我們按如下式子所示，把上面的式子所用到的項(xiàng)提取出來：

現(xiàn)在，我們來分析一下各二級加法器的結(jié)果都被哪些DCT變換系數(shù)所用：

接下來，我們再分析一下第三級加法器都做了什么運(yùn)算及各對應(yīng)的DCT變換系數(shù)。

　　如此，我們就很容易發(fā)現(xiàn)，其實(shí)，我們并不需要每計(jì)算一個一維DCT變換系數(shù)都要用組合電路把所有的各項(xiàng)都重復(fù)的計(jì)算出來，我們只要在計(jì)算的過程中加入一些寄存器，把我們已經(jīng)計(jì)算出來的項(xiàng)存起來，等到用到的時候從里面取出來就直接可以用了，這樣，只要我們通過合理的布局布線，我們的一維DCT變換系數(shù)就可以很快的計(jì)算出來，這樣，功耗肯定也是會降低的。下面，我們設(shè)計(jì)了兩種基于時序電路的一維DCT。事實(shí)證明，我們這樣做，還可以大大減少加法器的數(shù)量。

4.DCT_13的設(shè)計(jì)

    僅用13個加法器的一維DCT（為方便起見，我們暫且稱之為DCT_13）設(shè)計(jì)：
在這個設(shè)計(jì)中，我們只用了13個加法器，就完成了一維DCT。我們的基本思路是這樣的：首先，A0，A1，A2，A3，A4，A5，A6，A7依次順序輸入，經(jīng)過一個8數(shù)據(jù)的串并轉(zhuǎn)換模塊，這8個數(shù)據(jù)同時輸入到第一級加法器，我們的第一級加法器共有4個加減可控制的簡單ALU，首先，我們當(dāng)然是讓這4個ALU做加法運(yùn)算，因?yàn)?，我們發(fā)現(xiàn)F0，F(xiàn)2并沒有用到這一級加法器所計(jì)算出來的D_07,D_16,D_25,D_34,而它們的輸出當(dāng)然也是需要一個時鐘周期的,于是,我們完全可以先讓這4個ALU做加法運(yùn)算，再在下一個周期讓它們做減法運(yùn)算，當(dāng)然，每次計(jì)算完的結(jié)果要保存在寄存器，于是，第一級的加法運(yùn)算是不會引起任何延時的。

    讓我們再來看第二級的加法器設(shè)計(jì)。通過對表2的研究，你發(fā)現(xiàn)什么了？是的，如同第一級加法器的設(shè)計(jì)一樣，我們同樣可以改變輸出的順序，來計(jì)算第二級加法器所需的各項(xiàng)。結(jié)合第一級加法器的設(shè)計(jì)，我們讓DCT變換系數(shù)的輸出變?yōu)檫@個順序吧：F0，F(xiàn)2，F(xiàn)6，F(xiàn)4，F(xiàn)5，F(xiàn)7，F(xiàn)1，F(xiàn)3。于是，我們可以先用兩個加減可控制的簡單的ALU計(jì)算出F0所需要的D0716，D2534，同時，我們在設(shè)計(jì)中也讓D07_34,D_2534也各用了一個加法器計(jì)算出來了D07_16，D25_34,當(dāng)然也在接在來的一個時鐘周期被前面所提到的ALU計(jì)算出來，接下來，我們再設(shè)計(jì)兩個加法可控制的簡單ALU來分別計(jì)算D_1625 ，D_1634 和D_0716 ，D_0725 ，D_0734，發(fā)現(xiàn)我們?yōu)槭裁催@么做了嗎？這是因?yàn)槿绱宋覀兙?/P>

    可以讓ALU的一個輸入固定下來，而不用再設(shè)計(jì)緩存器來緩存輸入。當(dāng)然，你也可以試試不把一個輸入端固定下來會是什么樣子。

    第三級加法器的設(shè)計(jì)。首先，我們要輸出的是F0，所以，我們用一個加減可控制的簡單ALU計(jì)算出了D0716 +D2534，再在下一個時鐘周期計(jì)算出 D0716 -D2534，同時，另一個加法器將D_0716+D_34，D_0716+D_25，D_16+D_2345依次計(jì)算出來，我們的輸出順序?yàn)椋篎0，F(xiàn)2，F(xiàn)6，F(xiàn)4，F(xiàn)5，F(xiàn)7，F(xiàn)1，F(xiàn)3。我們這種輸出順序是方便讀者理解整個流程，其實(shí)，我們很容易發(fā)現(xiàn)第三個數(shù)據(jù)輸出后，所有的項(xiàng)其實(shí)都已經(jīng)被計(jì)算出來了，所以，我們后面的順序是什么樣的都是不重要的 (如果我們能曾加兩個時鐘的延時，也可以按順序輸出數(shù)據(jù)，即：F0，F(xiàn)1，F(xiàn)2，F(xiàn)3，F(xiàn)4，F(xiàn)5，F(xiàn)6，F(xiàn)7) 。

    圖1是我們的DCT_13的結(jié)構(gòu)圖。其中，series_to_parallel完成八數(shù)據(jù)串并轉(zhuǎn)換，Addmat1完成第一級加法，Addmat2完成一維DCT變換的其余工作。

圖1 DCT_13的結(jié)構(gòu)圖

　　圖2是我們的一維DCT（13個加法器）的仿真時序圖?？梢园l(fā)現(xiàn)，我們的8個數(shù)據(jù)輸入完成同時就可以有一維DCT變換系數(shù)持續(xù)輸出。可以看到我們的第一組輸入數(shù)據(jù)A0—A7依次為：170，153，153，153，170，153，153，153，輸出的一維DCT變換系數(shù)F0—F7為：440，6，0，11，11，-4，0，9與理論值：444，6，0，11，12，-2，0，9基本相符，出現(xiàn)的差異是由于加法器的位數(shù)的有限性造成的，但它是可以滿足實(shí)際要求的。

圖2 DCT_13的仿真時序圖

   圖3是我們用Synplify綜合工具綜合后得到的一些數(shù)據(jù)，所選用的器件為APEX20KE160etc144-2x，可以看到在這個DCT_13中，我們僅用了1257個LUT。

圖3 DCT_13的一些綜合相關(guān)數(shù)據(jù)

5.DCT_11的設(shè)計(jì)

    僅用11個加法器的一維DCT（為方便起見，我們暫且稱之為DCT_11）設(shè)計(jì)。

    在這個設(shè)計(jì)中，我們改變了前面提到的13個加法器的一維DCT設(shè)計(jì)的串并轉(zhuǎn)換和第一級加法器。而第二級和第三級加法器與前面提到的是一樣的。

    在這里，我們讓輸入的順序改變一下，為A0，A7，A1，A6，A2，A5，A3，A4。發(fā)現(xiàn)什么沒有？是的，如此，我們可以讓串并轉(zhuǎn)換變?yōu)槎?shù)據(jù)的串并轉(zhuǎn)換，這樣對資源的節(jié)約是巨大的，讓兩個并行出來的數(shù)據(jù)輸入到第一級加法器。在這里，我們的第一級加法器就可以只用兩個加減可控制的簡單ALU。其中一個計(jì)算出D07，D_07 ，D25，D_25，另一個則計(jì)算出D16，D_16，D34，D_34并且，我們當(dāng)它們都被計(jì)算出來的時候，我們讓它們同時保存到另一組寄存器，再做接下來的運(yùn)算。

    圖4是我們的DCT_11的結(jié)構(gòu)圖。其中，SeriToPara完成二數(shù)據(jù)串并轉(zhuǎn)換，Addmat1完成第一級加法，Addmat2完成一維DCT變換的其余工作。

圖4        DCT_11的結(jié)構(gòu)圖

圖5是我們用Synplify綜合工具綜合后得到的一些數(shù)據(jù)，所選用的器件為APEX20KE160etc144-2x，可以看到在這個DCT_13中，我們僅用了1151個LUT。

圖5    DCT_11的一些綜合相關(guān)數(shù)據(jù)

6.方案設(shè)計(jì)比較

　　下面，我們將我們的設(shè)計(jì)與目前已有的一維DCT設(shè)計(jì)進(jìn)行了比較。通過比較可以看到我們的設(shè)計(jì)大大減少了一維DCT設(shè)計(jì)中所需要的加法器數(shù)。

7. 結(jié)語

　　我們舉了兩個例子，來說明基于時序電路的一維DCT。也許我們的設(shè)計(jì)還不是最簡，我們也只希望能起到一個拋磚引玉的作用，讓研究人員能夠設(shè)計(jì)出更節(jié)約硬件資源的一維DCT。

參考文獻(xiàn)

[1]N.Ahmed, T.Natrajan and K.R.Rao, “Discrete cosine transform”,IEEE trans. Computers, January 1974.
[2]歐陽合，韓軍，“視頻編解碼器設(shè)計(jì)_開發(fā)圖像與視頻壓縮系統(tǒng)”，國防科技大學(xué)出版社，2005.
[3] high performance distributed DCT architecture, " in Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI), Pittsburgh, Pennsylvania, April 2002. 
[4] A.Peled, B.Liu, "A new hardware realization of digital filters," IEEE Trans. ASSP, vol.ASSP-22,no.6, pp.456-462, Dec.1974. 
[5] D.F.Elliott (ed.), Handbook of Digital Signal Processing, Academic Press, pp.964-972, 1987. 
[6] S.A.White, "Applications of distributed arithmetic to digital signal processing: A tutorial review," IEEE ASSP Magazine, pp.4-19, July 1989. 
[7] G-K.Ma and F.J.Taylor, "Multiplier policies for digital signal processing," IEEE ASSP Magazine, pp.6-19, Jan.1990. 
[8] Iain E. G. Richardson, "Video Codec Design _ Developing Image and Video Compression Systems " The Robert Gordon University Aberdeen. UK