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

1.引言

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

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

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

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

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

首先,考慮下式

                （2-1）

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

                       （2-2）

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

                       （2-3）

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

      （2-4）

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

                            （2-5）

中我們令

                                     （2-6）

則：

            （2-8）

當(dāng)u=1時(shí)

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

                  （2-9）

                （2-10）

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

3.一維DCT的算式分析

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

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

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

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

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

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

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

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

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

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

接下來(lái)，我們?cè)俜治鲆幌碌谌?jí)加法器都做了什么運(yùn)算及各對(duì)應(yīng)的DCT變換系數(shù)。

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

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

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

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

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

    第三級(jí)加法器的設(shè)計(jì)。首先，我們要輸出的是F0，所以，我們用一個(gè)加減可控制的簡(jiǎn)單ALU計(jì)算出了D0716 +D2534，再在下一個(gè)時(shí)鐘周期計(jì)算出 D0716 -D2534，同時(shí)，另一個(gè)加法器將D_0716+D_34，D_0716+D_25，D_16+D_2345依次計(jì)算出來(lái)，我們的輸出順序?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。我們這種輸出順序是方便讀者理解整個(gè)流程，其實(shí)，我們很容易發(fā)現(xiàn)第三個(gè)數(shù)據(jù)輸出后，所有的項(xiàng)其實(shí)都已經(jīng)被計(jì)算出來(lái)了，所以，我們后面的順序是什么樣的都是不重要的 (如果我們能曾加兩個(gè)時(shí)鐘的延時(shí)，也可以按順序輸出數(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完成第一級(jí)加法，Addmat2完成一維DCT變換的其余工作。

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

　　圖2是我們的一維DCT（13個(gè)加法器）的仿真時(shí)序圖。可以發(fā)現(xiàn)，我們的8個(gè)數(shù)據(jù)輸入完成同時(shí)就可以有一維DCT變換系數(shù)持續(xù)輸出?？梢钥吹轿覀兊牡谝唤M輸入數(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的仿真時(shí)序圖

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

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

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

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

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

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

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

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

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

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

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

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

7. 結(jié)語(yǔ)

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

參考文獻(xiàn)

[1]N.Ahmed, T.Natrajan and K.R.Rao, “Discrete cosine transform”,IEEE trans. Computers, January 1974.
[2]歐陽(yáng)合，韓軍，“視頻編解碼器設(shè)計(jì)_開(kāi)發(fā)圖像與視頻壓縮系統(tǒng)”，國(guó)防科技大學(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