湯 敏

(江蘇第二師范學(xué)院 物理與信息工程學(xué)院，江蘇 南京 210000)

0 引言

在計(jì)算機(jī)文件中，會重復(fù)出現(xiàn)某些符號，相較于其他符號，這些符號的出現(xiàn)頻率較高或者字符在各個(gè)數(shù)據(jù)塊可預(yù)見的位置中出現(xiàn)，這些都屬于冗余部分，采用數(shù)據(jù)編碼的方式可將冗余部分去除、減少，也就是進(jìn)行壓縮。冗余度壓縮具有可逆性，所以也被稱為無失真壓縮、無損壓縮。數(shù)據(jù)之間存在相關(guān)性，相鄰數(shù)據(jù)的相關(guān)性更加明顯。例如，圖片中的背景色彩均勻、電視信號相鄰兩幀的數(shù)據(jù)變化并不大，但呈現(xiàn)出的影響有很大不同，諸如此類都可以體現(xiàn)出數(shù)據(jù)之間的相關(guān)性。本研究采用變換方式將相關(guān)性去掉，達(dá)到壓縮的效果。

1 數(shù)據(jù)壓縮技術(shù)的發(fā)展

1.1 早期發(fā)展

計(jì)算機(jī)中常用的數(shù)據(jù)壓縮主要發(fā)揮節(jié)省空間和減少帶寬占用的作用。該技術(shù)的研究早在18世紀(jì)就已經(jīng)開始，“實(shí)數(shù)舍入為十進(jìn)制數(shù)”就是數(shù)據(jù)壓縮的基礎(chǔ)理論。19世紀(jì)對數(shù)據(jù)壓縮進(jìn)行了初次嘗試，也就是莫爾斯代碼的出現(xiàn)。1939年，西方學(xué)者Dudey[1]研究制作了聲碼器，對聲音頻譜進(jìn)行能量劃分，使其成為數(shù)目有限的頻帶，在各個(gè)頻帶中傳輸對應(yīng)能級，以此達(dá)到壓縮的效果，但此時(shí)的研究還比較片面。在20世紀(jì)40年代才開始對數(shù)據(jù)壓縮進(jìn)行系統(tǒng)性地研究，信息論逐漸有了雛形。早期，信息論研究以“已知消息中各個(gè)符號出現(xiàn)頻率”為主，嘗試對編碼進(jìn)行架構(gòu)，降低信息占用的空間。在數(shù)字計(jì)算機(jī)還沒有研發(fā)前就已經(jīng)有很多相關(guān)研究，對當(dāng)前的數(shù)字壓縮技術(shù)有很大的影響。

1.2 衍生算法

以各類研究結(jié)果、理論分析為基礎(chǔ)，衍生出了各種算法，如霍夫曼編碼等，在現(xiàn)代技術(shù)研究中依舊有很大的應(yīng)用價(jià)值。數(shù)據(jù)壓縮技術(shù)主要有兩個(gè)研究方向：一是建立信源和數(shù)據(jù)模型，以此為基礎(chǔ)探索衡量數(shù)據(jù)壓縮質(zhì)量和性能的技術(shù)指標(biāo)；二是從工程技術(shù)研究的角度著手，構(gòu)建可以發(fā)揮數(shù)據(jù)壓縮技術(shù)優(yōu)勢的系統(tǒng)，為工程應(yīng)用提供服務(wù)，分析數(shù)據(jù)壓縮系統(tǒng)，了解具體的性能指標(biāo)。簡而言之，就是從理論和實(shí)踐兩方面進(jìn)行研究，但不論是哪一種，都是信息論研究中的重要組成部分，以信息熵研究為主，深入分析壓縮比、編碼方法，利用具體的方法編碼源數(shù)據(jù)，使數(shù)據(jù)流占據(jù)更少的空間。隨著計(jì)算機(jī)技術(shù)的發(fā)展，數(shù)據(jù)壓縮技術(shù)可以為信息存儲、傳輸提供技術(shù)支持，所以研究愈加深入和廣泛。隨著技術(shù)的發(fā)展和研究的深入，數(shù)字圖像信號、語音信號等信號技術(shù)在各個(gè)領(lǐng)域中廣泛應(yīng)用。由于圖像信息會占用大量存儲空間，但該通信方式為非話業(yè)務(wù)的主要內(nèi)容，所以要在圖像通信中廣泛應(yīng)用數(shù)據(jù)壓縮技術(shù)，解決通信問題。

2 LZSSB算法在數(shù)字信號處理器中的應(yīng)用

2.1 數(shù)字信號處理器的選擇

2.1.1 DSP應(yīng)用優(yōu)勢

與普通的科學(xué)計(jì)算相比，數(shù)字信號處理有其獨(dú)特性，注重運(yùn)算處理的實(shí)時(shí)性，為實(shí)現(xiàn)處理要求，研發(fā)了數(shù)字信號處理器(DSP)。DSP不僅具備微處理器的高速運(yùn)算能力和控制功能，還可以更好地實(shí)現(xiàn)數(shù)字信號實(shí)時(shí)處理的目標(biāo)，改動(dòng)了處理器的結(jié)構(gòu)，調(diào)整了指令系統(tǒng)和流程。DSP的數(shù)據(jù)總線與程序總線相互分離，采用哈弗和改進(jìn)哈弗結(jié)構(gòu)，相較于傳統(tǒng)結(jié)構(gòu)形式，其指令執(zhí)行速度更高。DSP主要運(yùn)用流水技術(shù)，各個(gè)指令利用片內(nèi)多個(gè)功能單元執(zhí)行，具體包括獲取指令、譯碼、取數(shù)等步驟環(huán)節(jié)，可以提升時(shí)鐘頻率，使各個(gè)指令的執(zhí)行時(shí)間減少[2-4]。片內(nèi)有很多條總線，取指令、數(shù)據(jù)存儲操作可以同步進(jìn)行，采用輔助寄存器可以同時(shí)完成尋址任務(wù)，在尋址訪問后對內(nèi)容進(jìn)行自動(dòng)修改，并且指向后續(xù)要訪問的地址。針對需要乘法累加運(yùn)算的情況，DSP普遍配備獨(dú)立的乘法器、加法器。在相同時(shí)，鐘周期中可以完成兩種運(yùn)算，既可以相乘，也可以累加。ADSP2106X等新型DSP在乘和加的基礎(chǔ)上，還可以進(jìn)行減的運(yùn)算，運(yùn)算速度有了明顯的提升。很多DSP配備DMA通道控制器，同時(shí)采用串行通信口，與片內(nèi)多總線結(jié)構(gòu)形成良好的配合關(guān)系，極大地提升了數(shù)據(jù)塊的傳送速度。中斷處理器、定時(shí)控制器便于構(gòu)成小規(guī)模系統(tǒng)，具有軟件和硬件的等待功能，可以匹配各類存儲器接口。

2.1.2 DSP與MPU，MCU的區(qū)別

DSP，MPU，MCU有明顯的使用區(qū)別。DSP的性能比較高，具有數(shù)值運(yùn)算密集型的特點(diǎn)，滿足實(shí)時(shí)處理的要求；MPU在計(jì)算機(jī)中的應(yīng)用比較廣泛；MCU主要對處理過程進(jìn)行控制[5]。DSP的功能性較強(qiáng)，可以實(shí)時(shí)進(jìn)行數(shù)字信號處理，在實(shí)際應(yīng)用的過程中，可以對周期的乘和加的操作下達(dá)單獨(dú)指令。DSP采用比較獨(dú)特的尋址方式，在其他操作執(zhí)行的同時(shí)也可以修改地址寄存器的指針，既可以循環(huán)尋址，也可以進(jìn)行位反序?qū)ぶ罚哂休^強(qiáng)的功能性。在FIR濾波器中采用循環(huán)尋址的功能，可以將數(shù)據(jù)移動(dòng)數(shù)量減少，在FFT中采用緊湊的存放旋轉(zhuǎn)因子表[6-7]。

2.1.3 位反序功能

為了使FFT快速完成，可以采用位反序功能。存儲器接口根據(jù)實(shí)時(shí)處理的需求設(shè)計(jì)，在單指令時(shí)間內(nèi)可以訪問多次存儲器或訪問I/O設(shè)備。采用專門的指令控制，具有無附加開銷的循環(huán)功能，可以對指令進(jìn)行延遲跳轉(zhuǎn)。指令字采用指令集和較長的專門指令，一個(gè)指令字可以對多個(gè)功能單元進(jìn)行控制和操作。在小型化設(shè)計(jì)中，可以采用單片系統(tǒng)，具有明顯的應(yīng)用優(yōu)勢。DSP的功耗比較低，通常在0.5～4 W。如果采用低功耗的設(shè)計(jì)模式，則功耗只有0.1 W，可以采用電池供電的方式，便于應(yīng)用在嵌入式系統(tǒng)中。MPU的功耗相對較高，Power PC等功耗甚至超過20 W。

通過對比可以看出，DSP有更高的運(yùn)算速度，處理速度明顯高于MPU，甚至達(dá)到10倍以上，并且可以無間斷地實(shí)時(shí)輸入和輸出數(shù)據(jù)。DSP具有結(jié)構(gòu)單一的特點(diǎn)，采用匯編語言編程，可以預(yù)測任務(wù)完成時(shí)間，與結(jié)構(gòu)和指令比較復(fù)雜的MPU相比，DSP的性能明顯跟高。例如，F(xiàn)IR濾波器應(yīng)用DSP。FIR輸入一個(gè)數(shù)據(jù)對應(yīng)各階段的濾波器系數(shù)都需要進(jìn)行乘和加，不僅要進(jìn)行取值和取數(shù)，還要采取專門的數(shù)據(jù)移動(dòng)操作。DSP應(yīng)用之后，可以在單周期中完成各個(gè)操作[8]。

2.2 數(shù)字信號處理器的應(yīng)用

2.2.1 bit位轉(zhuǎn)換

壓縮算法的處理單元普遍為8 bit，在輸出的過程中，每次輸出都是8 bit。ADSP21065L芯片的片內(nèi)存儲器可以設(shè)置的訪問形式有三種，分別是16位、32位和48位。因此不單純采用8位訪問的方式，要變換存儲器中的數(shù)據(jù)，確保數(shù)據(jù)與壓縮算法相符。如果采用32位字符，則每次輸入/輸出都是32 bit，通過改進(jìn)算法適應(yīng)DSP芯片，減小匹配長度，達(dá)到降低壓縮率的效果。

例如，輸入信息流：ABCDEFGABCDEEFGABC。設(shè)置4個(gè)緩沖區(qū)在編碼算法中，如果in_buffer1[]為1K，則in_buffer2[]為4K；out_buffer1[]為1K，則out_buffer2[]為4K。在讀取in_buffer1[]的1K數(shù)據(jù)時(shí)，將in_buffer1[]的數(shù)據(jù)向in_buffer2[]轉(zhuǎn)入。在轉(zhuǎn)移數(shù)據(jù)的過程中，需要在in_buffer1[]讀取數(shù)據(jù)，如果讀出in_buffer1[0]，則數(shù)據(jù)為32位，可以將該數(shù)據(jù)低8位在in_buffer2[0]中存儲，次低8位則在in_buffer2[1]中存儲，次高位在in_buffer2[2]中存入，高位在in_buffer2[3]中存入，以此類推。選擇8位處理單元作為壓縮編碼，已經(jīng)編碼的數(shù)據(jù)向out_buffer2[]流放，緩沖區(qū)中低8位數(shù)據(jù)有效。在填滿緩沖區(qū)的情況下，應(yīng)該向out_buffer1[]轉(zhuǎn)入數(shù)據(jù)，out_buffer2[0]低8位放入out_buffer1[0]的低8位，可以結(jié)合輸入原理和過程進(jìn)行類推分析。在解壓處理的過程中，原理和流程基本相似。

2.2.2 處理數(shù)據(jù)流結(jié)束標(biāo)志

在比較C語言算法的過程中，將文件中的數(shù)據(jù)讀取，再進(jìn)行處理。采用EOF(-1)判斷文件結(jié)束是否可行，在讀入字符為-1的情況下，表示讀入的并不是正常字符，也就是文件結(jié)束符。在對二進(jìn)制文件進(jìn)行處理的過程中，將某字節(jié)中的二進(jìn)制數(shù)據(jù)值讀入，結(jié)果如果是-1，同時(shí)為EOF值，則讀入的有用數(shù)據(jù)會依據(jù)“文件結(jié)束”的情況來處理。如果采用其他判斷方式，使用函數(shù)feof對文件是否結(jié)束進(jìn)行判斷，能夠有效解決此類問題。如果已經(jīng)結(jié)束，則feof(fp)的值為1(真)；反之為0(假)。在壓縮的過程中，可以通過函數(shù)計(jì)算的方式進(jìn)行判斷分析，確定數(shù)據(jù)是否完成處理，斷定程序是否已經(jīng)終止。

2.2.3 字典處理

字典更新可以采用2種方式：(1)在數(shù)據(jù)處理的過程中對字典進(jìn)行更新，同時(shí)改變二叉樹，直到完成所有數(shù)據(jù)流處理；(2)緩沖區(qū)的數(shù)據(jù)處理完成之后，全部重新建立字典、二叉樹，以此來降低壓縮率，但可能會改變某些程序，造成系統(tǒng)開銷。在比較壓縮算法的過程中，可以編寫LZSSB程序。字典從current_position=1開始進(jìn)行逐個(gè)增加，在達(dá)到buffer_size的情況下，數(shù)值為0，那么就從0開始增加。由此可以看出，程序中通常存在計(jì)算位置模的宏，這個(gè)宏可以在0～511區(qū)間循環(huán)。在數(shù)據(jù)處理的同時(shí)更新字典，二叉樹也隨之變化，這個(gè)過程主要依據(jù)函數(shù)delete_tree0實(shí)現(xiàn)，該函數(shù)的功能比較明顯。在字典中存入c字符的時(shí)候，widow[k]不是空的，而是已經(jīng)存儲了字符old_c，此時(shí)需要從二叉樹中將節(jié)點(diǎn)k刪除，為字符c的處理奠定基礎(chǔ)，k的插入代表字符的更新。如果每次處理buffer_size字符結(jié)束后，都把壓縮數(shù)據(jù)傳輸出去，同時(shí)對字典、二叉樹進(jìn)行重建，則以此為基礎(chǔ)修改LZSSB程序。也就是在current_position=0的情況下開始，到達(dá)511即處理完了所有緩沖區(qū)的數(shù)據(jù)，結(jié)束程序，可以將MOD_WINDOW去掉。因?yàn)椴恍枰谔幚淼耐瑫r(shí)對二叉樹進(jìn)行修改，可以將delete_tree()子程序去掉，相關(guān)函數(shù)也可以去掉。如果每次處理完buffer_size個(gè)字符，壓縮數(shù)據(jù)都會傳出，并且對字典和二叉樹進(jìn)行重新構(gòu)建和初始化設(shè)置。例如，修改之前程序處理512個(gè)字符需要周期為65CA8(H)，進(jìn)行修改之后，周期會縮短到5BDOB(H)。

3 結(jié)語

綜上所述，結(jié)合通信的特點(diǎn)對壓縮算法以及改進(jìn)方式進(jìn)行分析，在計(jì)算機(jī)中應(yīng)用模擬，對比各個(gè)算法的壓縮率。雖然LZSSB算法可以滿足系統(tǒng)對壓縮率和實(shí)時(shí)性的要求，但在信息時(shí)代背景下，技術(shù)在不斷的發(fā)展，人們的使用需求也日益提升，傳輸信息的數(shù)量會保持上漲的狀態(tài)，所以必須繼續(xù)研究壓縮算法。不僅如此，在數(shù)據(jù)處理技術(shù)日臻完善的情況下，應(yīng)該擴(kuò)大處理空間，縮減系統(tǒng)開銷，使數(shù)據(jù)壓縮技術(shù)可以在通信中充分發(fā)揮作用。