用于雷達數據實時傳輸的LZW算法優化

(海軍航空工程學院,山東煙臺264001)

0 引言

船用導航雷達是一種用于船體探測周圍目標,以便及時進行避讓,進行自身定位等用的雷達,它能獲得目標的距離、方位等基本信息[1]。為了實現雷達的遠程顯控,將其應用于無人值守雷達并實現雷達數據的入網共享功能,需要采集的雷達數據主要包括視頻信號、觸發脈沖、方位脈沖和船首脈沖四路信號。導航雷達掃描一幀所產生的數據量很大,要想實現雷達圖像遠程顯示,需要將采集到的雷達數據實時回傳給服務器,在服務器上進行實時圖像顯示,但由于網絡傳輸帶寬有限,直接進行數據傳輸效率低下,無法滿足實時性要求,因此需要在數據傳輸前對其進行有效的壓縮[2]。

針對實際雷達數據噪聲和雜波多,數據熵值較大,且相鄰幀之間相關性較高,采用LZW字典算法能達到很好的效果。但由于經典LZW壓縮算法是基于字典的壓縮算法,使用固定長度的碼字對相繼出現的、由單個信源符號所構成的、長度可變的符號序列進行編碼,而不依賴于帶編碼信源符號出現的先驗概率,因此在壓縮比和壓縮速率上還有很大提升空間。本文在原有LZW壓縮算法的基礎上,改變了字典查詢的方式,通過空間換時間提升壓縮速率,已達到數據實時傳輸的要求并滿足無線網絡帶寬的限制。

1 實際雷達數據分析

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

通過分析實際采集的雷達數據可知,相鄰方位、相鄰幀之間的雷達數據具有很高的相關性,從數據特點來講具有很大的壓縮空間。針對這種較高的數據相關性,LZW字典查詢算法比較適合這類數據的壓縮。圖1是選取的任意兩個相鄰方位的數據進行的圖像顯示,以及兩個方位相應距離點上的信號回波差值。從圖1可以看出,方位間的數據相關性較大,對數據進行壓縮前的預處理可以進一步提高壓縮比。

通過對圖1的分析可知,對雷達數據進行相關性處理,以其中一個方位為參考,其他方位可以用與參考方位的差值來表示。這樣,原本需要8位二進制來表示一個距離點的數據,現在只需6位二進制來表示即可,經過預處理之后數據量會壓縮到原來的75%,提高了壓縮比。

圖1 相鄰方位間的數據對比

2 LZW壓縮算法

2.1 算法原理

LZW算法屬于字典編碼,根據數據本身包含重復代碼的特性,用前面已經出現的字符串的代碼來代替后面相同字符串的內容,從而實現數據壓縮。由于該算法的壓縮器不輸出單個字符,只輸出詞典字符串中的代碼,因此字典在開始時不能是空的,應該包含可能在字符流中出現的所有單個字符[3]。

該算法的基本思想是用簡單的代碼來代替復雜的字符串以實現數據的壓縮,在壓縮的過程中自適應建立一個字典,反映字符串與代碼之間的對照關系,通過查詢字典來確定字符串壓縮代碼的輸出。

LZW編碼能夠有效地利用字符出現的頻率冗余度、字符重復性和高使用率模式冗余度,不需要提前預測字符的概率分布,只要掃描一次字符,無需有關輸入數據統計量的先驗信息,并且運算時間和文件的長度成正比。

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

設長為L的信源序列μ分為M(μ)段碼段,每段短語的二元碼符號長度為[lgM(μ)+lgK],因此,μ編碼后總碼元長度為M(μ)·([lgM(μ)+lgK]),每個源符號的平均碼長為

去掉向上取整符號,有下面不等式:

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

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

設信源為平穩無記憶信源,信源符號的分布概率為P(a k),k=1,2,…,k,當lmax足夠大時,典型的段中a k出現的次數接近lmaxP(a k)。這種段型的數目為Mlmax種,則

取對數,得

設較短的段型可以忽略不計,得

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

將解碼的信源序列趨于無窮時,lmax也趨于無窮,平均碼長趨近于信源熵[5]。

2.2 算法實現

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

LZW算法對每個輸入字符串進行逐個字符檢查,試圖找到和字典已有字符串匹配的最長字符串并進行解析,這樣字典內的編碼項會越來越多,匹配幾率也會隨之增大,從而達到壓縮目的。每個被解析了的字符串通過下一個輸入字符擴展,這樣形成的新字符串會被存入字典,新字符串會有一個新的標示符,稱為編碼值,并且同時輸出前綴碼的編碼值。雖然LZW編碼方式能夠不依賴于數據的概率統計特征,但是會涉及到字典查找問題[7]。算法流程圖如圖2所示。

由于傳統查找方式的查找效率太慢,故引入哈希函數[8],把哈希函數和傳統LZW算法結合起來就形成了哈希和LZW的結合算法。此算法使得字典查找效率大大提高,由此增加了數據的壓縮效率。

在編程實現過程中,用于壓縮的哈希函數采用移位和基本算數運算來構造[9],這樣哈希函數不僅運算速度快,易于硬件實現,而且比特之間的異或運算和位移運算能夠提高哈希值的隨機特性[10]。

圖2 LZW壓縮算法流程圖

將前綴W和后綴K加在一起形成新的字符串value,其中前綴W為字典中的編碼,后綴K為新進的字符,將value通過上述位移運算生成一個key值,通過二叉樹法對產生的key值進行查找對比,若已經存在,則原查找表中的key值對應的value中的前綴W即為新字符的字典編碼;若不存在,則用新的編碼來代替value中的前綴,繼續進行上述查找過程[11]。

在查找過程中會不可避免地產生沖突以及哈希性能問題,需要對其進行不斷的改進。

3 改進型LZW壓縮算法

在基本LZW壓縮算法的基礎上,可以通過改變字典查找方式,加快查找速度,提高壓縮效率。第2節介紹了通過引入哈希函數對字符串進行哈希變換,從而提高壓縮效率的方法,但這種方法會涉及到哈希函數的選擇以及產生沖突的問題,對于編程實現較復雜。

現對字典查找方式進行適當改變,利用“空間換時間”的思維進行查找[12]。

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

圖3 改進LZW字典查找算法流程圖

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

4 壓縮結果分析

以實際采集到的雷達數據為壓縮對象,運用基本遍歷查找的LZW壓縮算法、哈希函數查找的LZW壓縮算法、改進的空間換時間LZW壓縮算法,以及WinRAR軟件四種方式對同一數據進行壓縮,通過對比,體現改進算法的優勢。表1是4種方法對30 MB雷達數據進行壓縮的效率對比。

表1 不同算法壓縮效率對比

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

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

表2 不同算法壓縮比結果對比

通過對表2壓縮比對比分析可知,經過預處理后的空間換時間算法大大提高了壓縮比,且對于第1節提供的實際雷達數據,數據率是15.6 Mbit/s,本文相對于其他方法,壓縮程度更大,所需的傳輸帶寬更小,更容易實現無線網絡的實時傳輸,從而進一步提高了壓縮效率,使其更加符合實時性傳輸的要求。

從表1、表2的分析中可以看出,本文提出的空間換時間算法在壓縮效率和壓縮比上更具有明顯的優勢,更能實現數據的實時傳輸。

由于LZW壓縮算法是一種無損壓縮算法,通過反向解壓,可以將數據完整地解壓出來,與原始數據保持一致。而本文提供的空間換時間算法也是在LZW的基礎上進行的改進,其解壓后的數據也保持了一致性。

利用空間換時間的算法對實際雷達數據進行壓縮,達到了實時性的要求,通過圖像顯示,使采集后的數據能經過傳輸后實時顯示出來,顯示效果如圖4所示。

圖4 雷達圖像實時顯示圖

這是在某海邊的一部導航雷達所收到的回波信號,將數據采集、壓縮、傳輸以及顯示實時同步,并與實際地圖結合。從圖4可以看出,對應回波有船只、島嶼、建筑物等,很好地反映了實際的情況,從而也說明達到了實時的要求。

5 結束語

本文所涉及到的空間換時間的改進LZW算法是為了更進一步提高壓縮的效率,在基本LZW算法的基礎上,通過分析哈希函數算法的優缺點,從消耗內存、提高速度的角度提出的。

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

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

通過對壓縮算法的改進,滿足了實時傳輸的要求,為實現雷達實時顯示來提供數據,完成對雷達的遠程顯控功能,實現了雷達數據的入網共享等應用。

[1]徐龍飛.基于FPGA的數據采集系統[D].太原:中北大學,2014.

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

[3]韓慧.一種易于硬件實現的LZW算法的應用[J].電子技術應用,2015,41(2):68-71.

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

[5]王智.LZW字典壓縮改進算法研究及FPGA硬件實現[D].南京:南京師范大學,2012.

[6]王懷光,張培林,吳定海,等.基于動態LZW與算術編碼的緩變信號無損壓縮[J].計算機應用研究,2015,32(9):2742-2745.

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

[8]劉林.基于LZW優化算法的雷達數據壓縮技術[J].艦船科學技術,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的數據壓縮硬件系統設計[D].荊州:長江大學,2013.

[11]耿赟,薄保林.實時LZW壓縮算法的FPGA實現[J].數字技術與應用,2014(4):135,137.

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

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