(海軍航空工程學(xué)院,山東煙臺(tái)264001)

0 引言

船用導(dǎo)航雷達(dá)是一種用于船體探測(cè)周?chē)繕?biāo),以便及時(shí)進(jìn)行避讓,進(jìn)行自身定位等用的雷達(dá),它能獲得目標(biāo)的距離、方位等基本信息[1]。為了實(shí)現(xiàn)雷達(dá)的遠(yuǎn)程顯控,將其應(yīng)用于無(wú)人值守雷達(dá)并實(shí)現(xiàn)雷達(dá)數(shù)據(jù)的入網(wǎng)共享功能,需要采集的雷達(dá)數(shù)據(jù)主要包括視頻信號(hào)、觸發(fā)脈沖、方位脈沖和船首脈沖四路信號(hào)。導(dǎo)航雷達(dá)掃描一幀所產(chǎn)生的數(shù)據(jù)量很大,要想實(shí)現(xiàn)雷達(dá)圖像遠(yuǎn)程顯示,需要將采集到的雷達(dá)數(shù)據(jù)實(shí)時(shí)回傳給服務(wù)器,在服務(wù)器上進(jìn)行實(shí)時(shí)圖像顯示,但由于網(wǎng)絡(luò)傳輸帶寬有限,直接進(jìn)行數(shù)據(jù)傳輸效率低下,無(wú)法滿足實(shí)時(shí)性要求,因此需要在數(shù)據(jù)傳輸前對(duì)其進(jìn)行有效的壓縮[2]。

針對(duì)實(shí)際雷達(dá)數(shù)據(jù)噪聲和雜波多,數(shù)據(jù)熵值較大,且相鄰幀之間相關(guān)性較高,采用LZW字典算法能達(dá)到很好的效果。但由于經(jīng)典LZW壓縮算法是基于字典的壓縮算法,使用固定長(zhǎng)度的碼字對(duì)相繼出現(xiàn)的、由單個(gè)信源符號(hào)所構(gòu)成的、長(zhǎng)度可變的符號(hào)序列進(jìn)行編碼,而不依賴(lài)于帶編碼信源符號(hào)出現(xiàn)的先驗(yàn)概率,因此在壓縮比和壓縮速率上還有很大提升空間。本文在原有LZW壓縮算法的基礎(chǔ)上,改變了字典查詢(xún)的方式,通過(guò)空間換時(shí)間提升壓縮速率,已達(dá)到數(shù)據(jù)實(shí)時(shí)傳輸?shù)囊蟛M足無(wú)線網(wǎng)絡(luò)帶寬的限制。

1 實(shí)際雷達(dá)數(shù)據(jù)分析

在雷達(dá)天線獲得的回波信號(hào)中,有需要的目標(biāo)信號(hào),為了方便雷達(dá)圖像進(jìn)行顯示,需要將視頻回波信號(hào)進(jìn)行采集,同時(shí)包括觸發(fā)脈沖、船首脈沖和方位脈沖三路同步信號(hào)。利用AD芯片,設(shè)計(jì)數(shù)據(jù)采集電路,將上述四路信號(hào)同時(shí)進(jìn)行采集,使模擬信號(hào)轉(zhuǎn)換為數(shù)字信號(hào)。本文主要以JMA2254雷達(dá)為研究對(duì)象,分析采集到的實(shí)際數(shù)據(jù),其天線掃描周期是2 s,每個(gè)周期內(nèi)完成2 048個(gè)方位的掃描,每個(gè)掃描線上采集2 000個(gè)點(diǎn),那么通過(guò)計(jì)算可知其產(chǎn)生的數(shù)據(jù)率需要2 000×2 048×8/2=15.625 Mbit/s,保存一幀的雷達(dá)圖像需要4 MB。對(duì)于現(xiàn)有的幾種無(wú)線民用網(wǎng)絡(luò)而言,只有4G網(wǎng)絡(luò)才能勉強(qiáng)完成實(shí)時(shí)傳輸任務(wù),但傳輸代價(jià)太大,且4G網(wǎng)絡(luò)的傳輸距離有限,不適合遠(yuǎn)程傳輸工作,因此需要在進(jìn)行數(shù)據(jù)傳輸前對(duì)其進(jìn)行高效的壓縮。

通過(guò)分析實(shí)際采集的雷達(dá)數(shù)據(jù)可知,相鄰方位、相鄰幀之間的雷達(dá)數(shù)據(jù)具有很高的相關(guān)性,從數(shù)據(jù)特點(diǎn)來(lái)講具有很大的壓縮空間。針對(duì)這種較高的數(shù)據(jù)相關(guān)性,LZW字典查詢(xún)算法比較適合這類(lèi)數(shù)據(jù)的壓縮。圖1是選取的任意兩個(gè)相鄰方位的數(shù)據(jù)進(jìn)行的圖像顯示,以及兩個(gè)方位相應(yīng)距離點(diǎn)上的信號(hào)回波差值。從圖1可以看出,方位間的數(shù)據(jù)相關(guān)性較大,對(duì)數(shù)據(jù)進(jìn)行壓縮前的預(yù)處理可以進(jìn)一步提高壓縮比。

通過(guò)對(duì)圖1的分析可知,對(duì)雷達(dá)數(shù)據(jù)進(jìn)行相關(guān)性處理,以其中一個(gè)方位為參考,其他方位可以用與參考方位的差值來(lái)表示。這樣,原本需要8位二進(jìn)制來(lái)表示一個(gè)距離點(diǎn)的數(shù)據(jù),現(xiàn)在只需6位二進(jìn)制來(lái)表示即可,經(jīng)過(guò)預(yù)處理之后數(shù)據(jù)量會(huì)壓縮到原來(lái)的75%,提高了壓縮比。

圖1 相鄰方位間的數(shù)據(jù)對(duì)比

2 LZW壓縮算法

2.1 算法原理

LZW算法屬于字典編碼,根據(jù)數(shù)據(jù)本身包含重復(fù)代碼的特性,用前面已經(jīng)出現(xiàn)的字符串的代碼來(lái)代替后面相同字符串的內(nèi)容,從而實(shí)現(xiàn)數(shù)據(jù)壓縮。由于該算法的壓縮器不輸出單個(gè)字符,只輸出詞典字符串中的代碼,因此字典在開(kāi)始時(shí)不能是空的,應(yīng)該包含可能在字符流中出現(xiàn)的所有單個(gè)字符[3]。

該算法的基本思想是用簡(jiǎn)單的代碼來(lái)代替復(fù)雜的字符串以實(shí)現(xiàn)數(shù)據(jù)的壓縮,在壓縮的過(guò)程中自適應(yīng)建立一個(gè)字典,反映字符串與代碼之間的對(duì)照關(guān)系,通過(guò)查詢(xún)字典來(lái)確定字符串壓縮代碼的輸出。

LZW編碼能夠有效地利用字符出現(xiàn)的頻率冗余度、字符重復(fù)性和高使用率模式冗余度,不需要提前預(yù)測(cè)字符的概率分布,只要掃描一次字符,無(wú)需有關(guān)輸入數(shù)據(jù)統(tǒng)計(jì)量的先驗(yàn)信息,并且運(yùn)算時(shí)間和文件的長(zhǎng)度成正比。

LZW壓縮算法有3個(gè)重要的對(duì)象:數(shù)據(jù)流、編碼流和編譯表。在編碼時(shí),數(shù)據(jù)流是輸入對(duì)象,編碼流是輸出對(duì)象;在解碼時(shí),編碼流是輸入對(duì)象,數(shù)據(jù)流是輸出對(duì)象;編譯表是在編碼和解碼時(shí)都要借助的對(duì)象。當(dāng)編碼的信源序列較短時(shí),LZW編碼性能將會(huì)有所下降,但當(dāng)序列增長(zhǎng)時(shí),編碼效率會(huì)提高,平均碼長(zhǎng)也會(huì)逼近信源熵[4]。LZW解碼也比較簡(jiǎn)單,可以一邊解碼一邊建立字典,只需要傳輸字典的大小,無(wú)需傳輸字典本身。

設(shè)長(zhǎng)為L(zhǎng)的信源序列μ分為M(μ)段碼段,每段短語(yǔ)的二元碼符號(hào)長(zhǎng)度為[lgM(μ)+lgK],因此,μ編碼后總碼元長(zhǎng)度為M(μ)·([lgM(μ)+lgK]),每個(gè)源符號(hào)的平均碼長(zhǎng)為

去掉向上取整符號(hào),有下面不等式:

長(zhǎng)度為l的段有K l種。若把長(zhǎng)為L(zhǎng)的信源序列μ分為M(μ)段碼段之后,設(shè)最長(zhǎng)段的長(zhǎng)度為lmax,而且包含各種長(zhǎng)度的所有段型,則

當(dāng)lmax足夠大時(shí),式(3)和式(4)近似為M(μ)≈代入式(2),得到

設(shè)信源為平穩(wěn)無(wú)記憶信源,信源符號(hào)的分布概率為P(a k),k=1,2,…,k,當(dāng)lmax足夠大時(shí),典型的段中a k出現(xiàn)的次數(shù)接近lmaxP(a k)。這種段型的數(shù)目為Mlmax種,則

取對(duì)數(shù),得

設(shè)較短的段型可以忽略不計(jì),得

即總段數(shù)M(μ)≈M lmax,得到

將解碼的信源序列趨于無(wú)窮時(shí),lmax也趨于無(wú)窮,平均碼長(zhǎng)趨近于信源熵[5]。

2.2 算法實(shí)現(xiàn)

LZW是一種基于字典的算法。所謂字典算法,即認(rèn)為信源輸出的信息序列是由一本“字典”中的各種“詞條”構(gòu)成的。顯然,該字典的詞條應(yīng)由信源符號(hào)的不同排列組合產(chǎn)生。但是該字典不是固定不變的,而是根據(jù)信源發(fā)出的編碼動(dòng)態(tài)地建立的。編碼過(guò)程也就是建立字典的過(guò)程[6]。如果接收端建立的字典與發(fā)送端一樣,就達(dá)到了正確的信息傳送目的。LZW算法是圍繞字典建立起來(lái)的一種壓縮算法。通過(guò)字典,把輸入的字符串映射成等長(zhǎng)碼字輸出。LZW算法的字典具有前綴特性,這樣就使得任何一個(gè)字典中字符串的前綴也一定在字典中。

LZW算法對(duì)每個(gè)輸入字符串進(jìn)行逐個(gè)字符檢查,試圖找到和字典已有字符串匹配的最長(zhǎng)字符串并進(jìn)行解析,這樣字典內(nèi)的編碼項(xiàng)會(huì)越來(lái)越多,匹配幾率也會(huì)隨之增大,從而達(dá)到壓縮目的。每個(gè)被解析了的字符串通過(guò)下一個(gè)輸入字符擴(kuò)展,這樣形成的新字符串會(huì)被存入字典,新字符串會(huì)有一個(gè)新的標(biāo)示符,稱(chēng)為編碼值,并且同時(shí)輸出前綴碼的編碼值。雖然LZW編碼方式能夠不依賴(lài)于數(shù)據(jù)的概率統(tǒng)計(jì)特征,但是會(huì)涉及到字典查找問(wèn)題[7]。算法流程圖如圖2所示。

由于傳統(tǒng)查找方式的查找效率太慢,故引入哈希函數(shù)[8],把哈希函數(shù)和傳統(tǒng)LZW算法結(jié)合起來(lái)就形成了哈希和LZW的結(jié)合算法。此算法使得字典查找效率大大提高,由此增加了數(shù)據(jù)的壓縮效率。

在編程實(shí)現(xiàn)過(guò)程中,用于壓縮的哈希函數(shù)采用移位和基本算數(shù)運(yùn)算來(lái)構(gòu)造[9],這樣哈希函數(shù)不僅運(yùn)算速度快,易于硬件實(shí)現(xiàn),而且比特之間的異或運(yùn)算和位移運(yùn)算能夠提高哈希值的隨機(jī)特性[10]。

圖2 LZW壓縮算法流程圖

將前綴W和后綴K加在一起形成新的字符串value,其中前綴W為字典中的編碼,后綴K為新進(jìn)的字符,將value通過(guò)上述位移運(yùn)算生成一個(gè)key值,通過(guò)二叉樹(shù)法對(duì)產(chǎn)生的key值進(jìn)行查找對(duì)比,若已經(jīng)存在,則原查找表中的key值對(duì)應(yīng)的value中的前綴W即為新字符的字典編碼;若不存在,則用新的編碼來(lái)代替value中的前綴,繼續(xù)進(jìn)行上述查找過(guò)程[11]。

在查找過(guò)程中會(huì)不可避免地產(chǎn)生沖突以及哈希性能問(wèn)題,需要對(duì)其進(jìn)行不斷的改進(jìn)。

3 改進(jìn)型LZW壓縮算法

在基本LZW壓縮算法的基礎(chǔ)上,可以通過(guò)改變字典查找方式,加快查找速度,提高壓縮效率。第2節(jié)介紹了通過(guò)引入哈希函數(shù)對(duì)字符串進(jìn)行哈希變換,從而提高壓縮效率的方法,但這種方法會(huì)涉及到哈希函數(shù)的選擇以及產(chǎn)生沖突的問(wèn)題,對(duì)于編程實(shí)現(xiàn)較復(fù)雜。

現(xiàn)對(duì)字典查找方式進(jìn)行適當(dāng)改變,利用“空間換時(shí)間”的思維進(jìn)行查找[12]。

建立一個(gè)數(shù)組,大小是:字典大小×根字符數(shù)×字節(jié)數(shù)。在本次實(shí)際應(yīng)用中,選擇建立字典的大小為4 096,根字符數(shù)為256個(gè),每個(gè)數(shù)據(jù)為2個(gè)字節(jié),那么建立的數(shù)組大小為4 096×256×2=2 MB。將數(shù)組定義為uint8 dict[4 096][256],具體流程如圖3所示。

圖3 改進(jìn)LZW字典查找算法流程圖

從上述算法流程圖可以看出,改進(jìn)的算法每一步只需一次查找,查找速度非常快,但這個(gè)高速查找是通過(guò)大量消耗內(nèi)存為代價(jià)的,這就是所謂的“空間換時(shí)間”算法[13]。隨著科技的不斷進(jìn)步,幾兆內(nèi)存對(duì)于計(jì)算機(jī)而言非常小,不會(huì)影響其正常工作,而且對(duì)于FPGA、ARM等嵌入式系統(tǒng)和芯片來(lái)說(shuō),隨著技術(shù)的不斷改進(jìn),其內(nèi)存也不斷增大,開(kāi)辟幾兆內(nèi)存供壓縮使用提高壓縮效率也是值得的。

4 壓縮結(jié)果分析

以實(shí)際采集到的雷達(dá)數(shù)據(jù)為壓縮對(duì)象,運(yùn)用基本遍歷查找的LZW壓縮算法、哈希函數(shù)查找的LZW壓縮算法、改進(jìn)的空間換時(shí)間LZW壓縮算法,以及WinRAR軟件四種方式對(duì)同一數(shù)據(jù)進(jìn)行壓縮,通過(guò)對(duì)比,體現(xiàn)改進(jìn)算法的優(yōu)勢(shì)。表1是4種方法對(duì)30 MB雷達(dá)數(shù)據(jù)進(jìn)行壓縮的效率對(duì)比。

表1 不同算法壓縮效率對(duì)比

通過(guò)對(duì)表1壓縮效率對(duì)比分析可以看出,基本遍歷算法的壓縮效率是30/739.516≈0.04 MB/s,哈希函數(shù)算法的壓縮效率是30/134.643≈0.22 MB/s,本文算法的壓縮效率是30/3.898≈7.69 MB/s,Win RAR軟件的壓縮效率是30/5=6.00 MB/s。對(duì)于同一數(shù)據(jù),壓縮效率差距很大,而本文在第1節(jié)中就對(duì)實(shí)際雷達(dá)數(shù)據(jù)進(jìn)行分析,雷達(dá)一幀的數(shù)據(jù)是4 MB,掃描周期是2 s,也就是說(shuō)每秒要壓縮至少2 MB才能滿足實(shí)時(shí)傳輸?shù)囊?而基本遍歷算法和哈希函數(shù)算法都不能達(dá)到這個(gè)要求,這就會(huì)引起數(shù)據(jù)堆積,占用大量的緩存,不適合實(shí)時(shí)傳輸;本文的算法和Win RAR都能很好地達(dá)到2 MB/s的速率要求,實(shí)現(xiàn)傳輸?shù)膶?shí)時(shí)性,且本文提出的算法還略勝于Win RAR軟件。

表2是4種方法的壓縮比對(duì)比,以及其實(shí)時(shí)傳輸所需的傳輸帶寬。

表2 不同算法壓縮比結(jié)果對(duì)比

通過(guò)對(duì)表2壓縮比對(duì)比分析可知,經(jīng)過(guò)預(yù)處理后的空間換時(shí)間算法大大提高了壓縮比,且對(duì)于第1節(jié)提供的實(shí)際雷達(dá)數(shù)據(jù),數(shù)據(jù)率是15.6 Mbit/s,本文相對(duì)于其他方法,壓縮程度更大,所需的傳輸帶寬更小,更容易實(shí)現(xiàn)無(wú)線網(wǎng)絡(luò)的實(shí)時(shí)傳輸,從而進(jìn)一步提高了壓縮效率,使其更加符合實(shí)時(shí)性傳輸?shù)囊蟆?/p>

從表1、表2的分析中可以看出,本文提出的空間換時(shí)間算法在壓縮效率和壓縮比上更具有明顯的優(yōu)勢(shì),更能實(shí)現(xiàn)數(shù)據(jù)的實(shí)時(shí)傳輸。

由于LZW壓縮算法是一種無(wú)損壓縮算法,通過(guò)反向解壓,可以將數(shù)據(jù)完整地解壓出來(lái),與原始數(shù)據(jù)保持一致。而本文提供的空間換時(shí)間算法也是在LZW的基礎(chǔ)上進(jìn)行的改進(jìn),其解壓后的數(shù)據(jù)也保持了一致性。

利用空間換時(shí)間的算法對(duì)實(shí)際雷達(dá)數(shù)據(jù)進(jìn)行壓縮,達(dá)到了實(shí)時(shí)性的要求,通過(guò)圖像顯示,使采集后的數(shù)據(jù)能經(jīng)過(guò)傳輸后實(shí)時(shí)顯示出來(lái),顯示效果如圖4所示。

圖4 雷達(dá)圖像實(shí)時(shí)顯示圖

這是在某海邊的一部導(dǎo)航雷達(dá)所收到的回波信號(hào),將數(shù)據(jù)采集、壓縮、傳輸以及顯示實(shí)時(shí)同步,并與實(shí)際地圖結(jié)合。從圖4可以看出,對(duì)應(yīng)回波有船只、島嶼、建筑物等,很好地反映了實(shí)際的情況,從而也說(shuō)明達(dá)到了實(shí)時(shí)的要求。

5 結(jié)束語(yǔ)

本文所涉及到的空間換時(shí)間的改進(jìn)LZW算法是為了更進(jìn)一步提高壓縮的效率,在基本LZW算法的基礎(chǔ)上,通過(guò)分析哈希函數(shù)算法的優(yōu)缺點(diǎn),從消耗內(nèi)存、提高速度的角度提出的。

為了將采集到的雷達(dá)數(shù)據(jù)能進(jìn)行實(shí)時(shí)傳輸并進(jìn)行實(shí)時(shí)顯示,需要對(duì)其進(jìn)行實(shí)時(shí)壓縮,這就需要壓縮比高且壓縮速度快的壓縮算法。在壓縮前對(duì)雷達(dá)數(shù)據(jù)進(jìn)行相關(guān)性預(yù)處理,可以大大提高壓縮比;空間換時(shí)間的算法在原有LZW壓縮算法的基礎(chǔ)上,通過(guò)消耗2 MB內(nèi)存,使壓縮速度提高了2～3個(gè)數(shù)量級(jí),對(duì)于壓縮效果而言,性能非常好。將該方法運(yùn)用到實(shí)際雷達(dá)數(shù)據(jù)中,實(shí)現(xiàn)了數(shù)據(jù)采集、壓縮、傳輸和顯示的實(shí)時(shí)同步。

該算法實(shí)現(xiàn)較簡(jiǎn)單,且不易出現(xiàn)沖突的情況,性能較穩(wěn)定,其最大的特點(diǎn)就是通過(guò)消耗內(nèi)存來(lái)提高速度。如果壓縮的數(shù)據(jù)很大,建立的字典也隨之增大,那么所消耗的內(nèi)存也會(huì)不斷增大,這對(duì)于FPGA、ARM等嵌入式系統(tǒng)和芯片而言會(huì)影響到其他功能的實(shí)現(xiàn),因此對(duì)于內(nèi)存的消耗還有進(jìn)一步的改進(jìn)空間,在內(nèi)存與速度之間要找到一個(gè)平衡點(diǎn),以同時(shí)滿足兩方面要求。

通過(guò)對(duì)壓縮算法的改進(jìn),滿足了實(shí)時(shí)傳輸?shù)囊?為實(shí)現(xiàn)雷達(dá)實(shí)時(shí)顯示來(lái)提供數(shù)據(jù),完成對(duì)雷達(dá)的遠(yuǎn)程顯控功能,實(shí)現(xiàn)了雷達(dá)數(shù)據(jù)的入網(wǎng)共享等應(yīng)用。

[1]徐龍飛.基于FPGA的數(shù)據(jù)采集系統(tǒng)[D].太原:中北大學(xué),2014.

[2]LI Leiding,MA Tiehua.FPGA-Based Implementation of LZW Algorithm[J].Electronic Measurement Technology,2008,31(10):170-172.

[3]韓慧.一種易于硬件實(shí)現(xiàn)的LZW算法的應(yīng)用[J].電子技術(shù)應(yīng)用,2015,41(2):68-71.

[4]王育民,李暉,梁傳甲.信息論與編碼理論[M].北京:高等教育出版社,2005.

[5]王智.LZW字典壓縮改進(jìn)算法研究及FPGA硬件實(shí)現(xiàn)[D].南京:南京師范大學(xué),2012.

[6]王懷光,張培林,吳定海,等.基于動(dòng)態(tài)LZW與算術(shù)編碼的緩變信號(hào)無(wú)損壓縮[J].計(jì)算機(jī)應(yīng)用研究,2015,32(9):2742-2745.

[7]常傳文,茅文深.雷達(dá)數(shù)據(jù)無(wú)損壓縮研究[J].艦船電子工程,2008,28(4):103-105.

[8]劉林.基于LZW優(yōu)化算法的雷達(dá)數(shù)據(jù)壓縮技術(shù)[J].艦船科學(xué)技術(shù),2015,37(11):120-123.

[9]TRAPPE W,WASHINGTON L C.Introduction to Cryptography with Coding Theory[M].2nd ed.India:Pearson Education,2006.

[10]馮振.基于LZW的數(shù)據(jù)壓縮硬件系統(tǒng)設(shè)計(jì)[D].荊州:長(zhǎng)江大學(xué),2013.

[11]耿赟,薄保林.實(shí)時(shí)LZW壓縮算法的FPGA實(shí)現(xiàn)[J].數(shù)字技術(shù)與應(yīng)用,2014(4):135,137.

[12]程光,龔儉,丁偉,等.面向IP流測(cè)量的哈希算法研究[J].軟件學(xué)報(bào),2005,16(5):652-658.

[13]王孔華,李若仲,丁浩,等.LZW算法的優(yōu)化及其在FPGA上的實(shí)現(xiàn)[J].空軍工程大學(xué)學(xué)報(bào):自然科學(xué)版,2015,16(3):41-44.