蔣覲陽(yáng)，曹 亮

蘭州大學(xué)信息科學(xué)與工程學(xué)院，甘肅蘭州 730000

電力線載波通信是利用已有的電力線路進(jìn)行數(shù)據(jù)傳輸?shù)囊环N通信方式，無(wú)需專門架設(shè)通信基礎(chǔ)設(shè)施并且具有相當(dāng)廣泛的網(wǎng)絡(luò)分布，具有投資小、設(shè)備簡(jiǎn)單、通信可靠性高等優(yōu)點(diǎn)。然而，由于電力線載波通信存在著一些技術(shù)難題，如傳輸信道間歇噪聲大、阻抗隨負(fù)載變化大、信號(hào)衰減大等問題，我們將數(shù)據(jù)壓縮技術(shù)引入電力線載波通信，在數(shù)據(jù)傳輸前進(jìn)行壓縮，這樣就可以盡可能在有限的帶寬內(nèi)傳輸盡可能多的數(shù)據(jù)。

1 數(shù)據(jù)壓縮原理

數(shù)據(jù)壓縮是指在不丟失信息的前提下，縮減數(shù)據(jù)量以減少存儲(chǔ)空間，提高其傳輸、存儲(chǔ)和處理效率的一種技術(shù)方法?；虬凑找欢ǖ乃惴▽?duì)數(shù)據(jù)進(jìn)行重新組織，減少數(shù)據(jù)的冗余和存儲(chǔ)的空間。壓縮的理論基礎(chǔ)是信息論[1]。從信息的角度來(lái)看，壓縮就是去除掉信息中的冗余，即去除掉確定的或可推知的信息，而保留不確定的信息，也就是用一種更接近信息本質(zhì)的描述來(lái)代替原有的冗余的描述，這個(gè)本質(zhì)的東西就是信息量。

關(guān)于數(shù)據(jù)壓縮有很多算法，針對(duì)不同特點(diǎn)的數(shù)據(jù)選擇不同的壓縮算法從而達(dá)到最優(yōu)的壓縮效果。LZW繼承了LZ77和LZ78壓縮效果好、速度快的優(yōu)點(diǎn)，且算法描述易于接受。該算法能在不了解數(shù)據(jù)統(tǒng)計(jì)特性前提下，使壓縮比接近已知統(tǒng)計(jì)特性時(shí)所能達(dá)到的壓縮比，且易于實(shí)現(xiàn)，是目前最常用的算法。

1.1 LZW算法基本原理

LZW壓縮算法是一種新穎的壓縮方法，Lemple-Ziv-Welch 三人共同創(chuàng)造，用他們的名字命名。它采用了一種先進(jìn)的串表壓縮，將每個(gè)第一次出現(xiàn)的串放在一個(gè)串表中，用一個(gè)數(shù)字來(lái)表示串，壓縮文件只存貯數(shù)字，則不存貯串，從而使圖像文件的壓縮效率得到較大的提高。奇妙的是，不管是在壓縮還是在解壓縮的過(guò)程中都能正確的建立這個(gè)串表，壓縮或解壓縮完成后，這個(gè)串表又被丟棄[2]。

LZW算法中，首先建立一個(gè)字符串表，把每一個(gè)第一次出現(xiàn)的字符串放入串表中，并用一個(gè)數(shù)字來(lái)表示，這個(gè)數(shù)字與此字符串在串表中的位置有關(guān)，并將這個(gè)數(shù)字存入壓縮文件中，如果這個(gè)字符串再次出現(xiàn)時(shí)，即可用表示它的數(shù)字來(lái)代替，并將這個(gè)數(shù)字存入文件中。壓縮完成后將串表丟棄。如"print" 字符串，如果在壓縮時(shí)用266表示，只要再次出現(xiàn)，均用266表示，并將"print"字符串存入串表中，在圖像解碼時(shí)遇到數(shù)字266，即可從串表中查出266所代表的字符串"print"，在解壓縮時(shí)，串表可以根據(jù)壓縮數(shù)據(jù)重新生成。

LZW算法流程：

1）初始化：將所有的單字符串放入串表；2）讀第一個(gè)輸入字符給前綴串ω；3）Step: 讀下一個(gè)輸入字符K。

if 沒有這樣的K(輸入已窮盡)：

碼字(ω) 輸出；結(jié)束。

If ωK 已存在于串表中：

ω:=ωK；repeat Step；

else ωK不在于串表中:

碼字 (ω) 輸出 ；

ωK加進(jìn)串表；

ω:=K；repeat Step.

例子：

input:ababcbababaaaaaaa

ω:a->ab->ba->ab->4c->cb->ba->5b->8a->aa->aa->10a->aa->11a->a#->#

串 表：1(a) 2(b) 3(c) 4(ab) 5(ba) 6(4c) 7(cb) 8(5b) 9(8a) 10(aa)11(10a) 12(11a)

output:a b 4 c 5 8 a 10 11 a

1.2 電力線通信報(bào)文壓縮算法設(shè)計(jì)

將LZW壓縮算法應(yīng)用在電力線通信中，數(shù)據(jù)采樣利用率提高了兩倍，使報(bào)文傳遞更可靠；通過(guò)控制信息位（bit）級(jí)檢錯(cuò)、數(shù)據(jù)信息分組檢錯(cuò)等手段，增強(qiáng)檢錯(cuò)能力，降低誤同步概率；數(shù)據(jù)信息分組檢測(cè)糾錯(cuò)，報(bào)文長(zhǎng)度不再受鏈路層程序邏輯限制；糾錯(cuò)方式不再是唯一的擴(kuò)頻，支持不同長(zhǎng)度的擴(kuò)頻編碼，速率的提高可減少報(bào)文沖突幾率，有利于并行路由的順暢運(yùn)行；報(bào)文壓縮后不僅可以提高傳輸速率，還可以提升數(shù)據(jù)傳輸成功機(jī)率[3]。

例如，報(bào)文原始數(shù)據(jù)為：255，24，54，255，24，255，255，24，5，123，45，255，24，5，24，54...如何對(duì)它進(jìn)行壓縮，因?yàn)樵紨?shù)據(jù)可以用8bit來(lái)表示，故清除標(biāo)志Clear=255+1 =256，結(jié)束標(biāo)志為End=256+1=257，目前標(biāo)號(hào)集為0 1 2 3......255 CLEAR END

第一步，讀取第一個(gè)字符為255，在標(biāo)記表里面查找，255已經(jīng)存在，不做處理；

第二步，取第二個(gè)字符，此時(shí)前綴為A，形成當(dāng)前的Entry為(255，24)，在標(biāo)記集合不存在，把它在標(biāo)記集合中標(biāo)記為258，然后輸出前綴A，保留后綴24，并作為下一次的前綴（后綴變前綴)；

第三步，取第三個(gè)字符為54，當(dāng)前Entry(24，54)，記錄(24，54)為標(biāo)號(hào)259，并輸出24，后綴變前綴；

第四步：取第四個(gè)字符255，Entry=(54，255)，記錄(54，255)為標(biāo)號(hào)260，輸出54，后綴變前綴。.......

一直處理到最后一個(gè)字符，用一個(gè)表記錄處理過(guò)程，CLEAR=256，END=257。

表1 LZW算法舉例

2 算法改進(jìn)

2.1 改進(jìn)思路

LZW方法簡(jiǎn)單易行，但是存在諸多不足，例如，對(duì)不同大小的文件，均使用12位輸出代碼。在壓縮的開始階段文件較小時(shí)，字典中的短語(yǔ)比較少，使用位數(shù)更少的壓縮代碼顯然能減少壓縮文件的大小[4]。當(dāng)“next code”的值在256到511之間時(shí)，9位輸出代碼就足以表示所有短語(yǔ)；另一個(gè)有待改進(jìn)的方面是壓縮率的監(jiān)測(cè)。在壓縮進(jìn)程中，當(dāng)字典空間被填滿、新的短語(yǔ)不能加入到字典中時(shí)，對(duì)隨后的字典中無(wú)定義的字符串就無(wú)法進(jìn)行壓縮，壓縮率將下降。

2.2 改進(jìn)方法

1）可變代碼長(zhǎng)度

發(fā)現(xiàn)字典填滿時(shí)，立即將字典清空，以便后續(xù)字符串能建立短語(yǔ)。首先在字典中設(shè)置清除標(biāo)志，當(dāng)字典填滿后，在進(jìn)行閾值判斷時(shí)，對(duì)每一個(gè)碼字(Code Word)的使用情況計(jì)數(shù)。當(dāng)進(jìn)行閾值判斷所得到的壓縮比小于指定的閾值時(shí)，發(fā)出清除標(biāo)志，這時(shí)根據(jù)字典中每一個(gè)碼字使用的計(jì)數(shù)值大小進(jìn)行排序，對(duì)字典進(jìn)行相應(yīng)的重構(gòu)，然后刪除排序靠后的若干項(xiàng)。這種方法較簡(jiǎn)單，也有效果[5]。

STEPl初始化，使開始詞典包含所有可能的根(Root)，當(dāng)前前綴P置空；

STEP2當(dāng)碼字流有碼字要譯時(shí)，反復(fù)執(zhí)行STEP3，STEP4，STEP5和STEP6；

STEP3讀入字符數(shù)據(jù)流中的下一個(gè)字符C；

STEP4如果字符串P+C在當(dāng)前詞典中，

a P置P+C（用字符C擴(kuò)展P）；

b 把代表當(dāng)前前綴P的碼字輸出到碼字流;

否則，

c 輸出表示P的碼字到編碼數(shù)據(jù)流；

d 把字符串P+C添加到詞典；

e P置C（此時(shí)P僅含一個(gè)字符C）；

STEP5若字典未滿，則執(zhí)行STEP3；

STEP6如果壓縮比小于指定闞值，則清除匹配率小的詞條，否則，返回STEPl;

STEP7結(jié)束。

2）監(jiān)測(cè)壓縮率

要監(jiān)控壓縮率的變化至少需要知道四個(gè)量。一是原始?jí)嚎s率，顯然壓縮率為100%。二是現(xiàn)在的壓縮率，由輸出壓縮代碼與輸入字符數(shù)的比值來(lái)確定，必須知道輸入字符數(shù)和輸出壓縮代碼。以上四個(gè)變量在程序中分別定義為ratio_old、ratio_new、bytes_in、bytes_out。其中

ratio_new=

當(dāng)程序通過(guò)ratio_new值發(fā)現(xiàn)壓縮率已經(jīng)低于100%，說(shuō)明字典中的短語(yǔ)已經(jīng)過(guò)時(shí)，不再適合壓縮之用，應(yīng)建立新的字典。這里選擇在輸入字符號(hào)每增加一百個(gè)時(shí)計(jì)算一次，用一個(gè)標(biāo)識(shí)通知還原算法原來(lái)的字典已經(jīng)不再使用，還原算法即可從此開始建立新字典。壓縮程序改進(jìn)如下：

while((character=getc(input))!=(unsigned)

EOF){

++bytes_in；／*計(jì)算輸入值*／

if(bytes_in>checkpoint){／*checkpoint初始值為100*／

if(num_bits==MAX_BITS){

ratio_new=bytes_out*100／bytes_in；∥計(jì)算新壓縮率

if(ratio_new>ratio_old){／壓縮率是否下降

OutputBits(output，CLEAR_TABLE，code_bits);／／輸出標(biāo)識(shí)

code_bits=9；／／壓縮代碼位數(shù)從9開始

next_code=258；∥短語(yǔ)從258開始編碼

dict_byte=511； ∥字典容量為512

bytes_in=bytes_out=0； ∥ 復(fù) 位 bytes_in、bytes_out ratio_old=100；

for(i=0；i

code_value[i]=一1；}

else／*壓縮率沒有下降*／

ratio_old=ratio_new；∥以ratio_new作為ratio_old，以便下次比較

還原程序改進(jìn)如下：

while((new_code=input_code(input))!=END_OF_STREAM)

{

if(new_code== CLEAR～TABLE){ ／*清空字典標(biāo)識(shí)*／

code_bits=9；∥壓縮代碼位數(shù)從9開始

next_code=258； ∥短語(yǔ)從258開始編碼

dict_byte=511； ∥字典容量為512

continue；

}……

3 改進(jìn)的LZW算法比較

給出算法比較圖

表2 LZW經(jīng)典算法與改進(jìn)算法壓縮性能比較

首先，由表中數(shù)據(jù)可以看出改進(jìn)的LZW算法對(duì)各種不同類型的文件壓縮率都有了很大的提高，特別是對(duì)位圖文件的壓縮率改善更加顯著。

其次，改進(jìn)的LZW算法不僅壓縮比較高，且壓縮用時(shí)也較短，在電力線載波通信中，報(bào)文數(shù)據(jù)經(jīng)過(guò)壓縮，可以讓出帶寬，達(dá)到最初設(shè)想。

[1]袁枚.數(shù)據(jù)壓縮技術(shù)及其應(yīng)用[M].北京：電子工業(yè)出社，1995.

[2]Mark Nelson.數(shù)據(jù)壓縮技術(shù)原理與范例[M].北京：科學(xué)出版社，1995.

[3]周天暉，王光.改進(jìn)的LZW壓縮算法在語(yǔ)音數(shù)據(jù)復(fù)接器中的應(yīng)用[J].電力系統(tǒng)通信，2002(12).

[4]劉萌，丁香乾.電力線窄帶通信報(bào)文壓縮算法研究[J].網(wǎng)絡(luò)與通信，2010(16).

[5]ZIV J，LEMPEL A.A universal algorithm for sequential data compression[J].IEEE Transactions on Information Theory，VOL.1T一23，NO.3，MAY 1977.