實(shí)時(shí)LZW壓縮算法的FPGA實(shí)現(xiàn)-論文.pdf

《實(shí)時(shí)LZW壓縮算法的FPGA實(shí)現(xiàn)-論文.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、算法分析實(shí)時(shí)LZW壓縮算法的FPGA實(shí)現(xiàn)耿贊薄保林(中國(guó)電子科技集團(tuán)公司第五十四研究所河北石家莊050081)摘要：為降低數(shù)據(jù)傳輸?shù)臄?shù)據(jù)量提高傳輸速度，提出了一種用FPGA實(shí)現(xiàn)Lzw無損壓縮算法的設(shè)計(jì)方案。字典存儲(chǔ)形式~_LZW算法中的關(guān)鍵，用內(nèi)容可尋址存儲(chǔ)器構(gòu)建字典可大大提高字典查詢速度。仿真分析了字典容量與壓縮率間的關(guān)系，使用較少的FPGA資源就能達(dá)到較好的壓縮效果。關(guān)鍵詞：無損壓縮LZW算法內(nèi)容可尋址存儲(chǔ)器FPGA中圖分類號(hào)：TN958．98文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1007—9416(2014)0

2、4—0135—02在某工程應(yīng)用中需要將前端大量的采樣數(shù)據(jù)傳輸?shù)胶蠖诉M(jìn)行與壓縮流程類似，區(qū)別在于解壓縮查詢字典時(shí)輸出的不是匹配地址處理，為實(shí)現(xiàn)高效快速的數(shù)據(jù)傳輸，可利用數(shù)據(jù)壓縮技術(shù)減少數(shù)據(jù)而是匹配字符或字符串，解壓縮算法可從壓縮數(shù)據(jù)中重構(gòu)出與壓縮量和傳輸時(shí)間。系統(tǒng)要求壓縮數(shù)據(jù)必須能完全恢復(fù)為原始數(shù)據(jù)，且算法相同的字典，并且壓縮與解壓縮都不用存儲(chǔ)字典，易于工程實(shí)處理時(shí)間不能過長(zhǎng)，LZw壓縮算法是一種常用的無損壓縮算法，具現(xiàn)。LZW算法充分利用了數(shù)據(jù)的重復(fù)性，只需掃描一次數(shù)據(jù)就可以有較好的實(shí)時(shí)性，本文利用FP

3、GA的高速并行處理特點(diǎn)，提出了一完成壓縮，能夠?qū)崟r(shí)處理數(shù)據(jù)。種實(shí)時(shí)LZW壓縮算法的實(shí)現(xiàn)方案。2FPGA構(gòu)建CAM字典1LzW算法LZW算法的關(guān)鍵在于構(gòu)建字典和讀寫操作時(shí)間。傳統(tǒng)的LZWLZW算法使用一種類似查字典的方式來進(jìn)行壓縮，通常針對(duì)算法實(shí)現(xiàn)中多使用RAM(隨機(jī)存儲(chǔ)器)來存儲(chǔ)字典，查找詞條時(shí)需逐計(jì)算機(jī)系統(tǒng)中的8位ASCII字符進(jìn)行壓縮?；驹硎菍⑤斎氲淖謧€(gè)查詢從而造成壓縮時(shí)間過長(zhǎng)。建立字典地址與輸入數(shù)據(jù)的哈希函符累積為字符串，把已出現(xiàn)的字符串作為詞條存入字典，對(duì)重復(fù)出數(shù)可提高查詢速度，但為解決地址

4、沖突問題還要增加額外的開銷?，F(xiàn)的字符串輸出其在字典中的位置而不是字符串來達(dá)到壓縮數(shù)據(jù)本文將CAM(內(nèi)容可尋址存儲(chǔ)器)用于存儲(chǔ)字典，CAM的原理是將的目的。輸人數(shù)據(jù)與存儲(chǔ)的數(shù)據(jù)進(jìn)行比較，給出是否匹配以及匹配地址，這LZW算法流程主要是字典的維護(hù)和查詢，字典包含D項(xiàng)詞條，與LZW算法的字典查詢是相符的，利用CAM構(gòu)建字典簡(jiǎn)化了對(duì)字每項(xiàng)詞條由m位前綴和n位后綴組成，后綴位寬與輸入數(shù)據(jù)位寬相典的讀寫操作。等，且滿足D=2m。壓縮算法流程如下：(1)字典的前256項(xiàng)初始化為本文使用Virtex系列FPGA基于BR

5、AM(塊存儲(chǔ)器)的實(shí)現(xiàn)方法8位ASCII字符集，(2)將第一個(gè)字符作為后綴與前綴0組成待查數(shù)據(jù)來構(gòu)建CAM，這種方法讀寫時(shí)間都只需一個(gè)時(shí)鐘周期，適合存儲(chǔ)字進(jìn)行查詢，必與字典初始化項(xiàng)中的某一詞條匹配，將前綴更新為匹典。CAM16x8表示可存儲(chǔ)16項(xiàng)8bit數(shù)據(jù)，實(shí)現(xiàn)框圖如圖1所示。圖中配地址；(3)將下一個(gè)輸入字符作為后綴與前綴組成待查數(shù)據(jù)進(jìn)行RAM_Dual為BRAM，將端lzlA配置成4096項(xiàng)lbit數(shù)據(jù)，端EIB配置查詢，如果不匹配則將待查數(shù)據(jù)作為新詞條寫入到字典中，將前綴成256項(xiàng)16bit數(shù)據(jù)

6、，RAM_Erase由8個(gè)分布式RAM構(gòu)成，存儲(chǔ)CAM輸出并更新前綴為后綴的匹配地址，如果匹配則將前綴更新為匹配中每個(gè)地址已存的內(nèi)容。地址，(4)依次輸入字符并按上步進(jìn)行處理。LZW算法的解壓縮流程CAM16x8的寫操作分為擦除和寫入兩個(gè)步驟。擦除是從RAM—Erase模塊中讀出地址addri中已存的數(shù)據(jù)，作為RADualWriteReadPortAPortB模塊端口A寫地址addra的高8位，addra的低4位為addri，數(shù)據(jù)dia寫0x4096)(16x256)0表示這一地址存儲(chǔ)的數(shù)據(jù)已清零；下一

7、時(shí)鐘周期再進(jìn)行寫操作，將dia【0】dobD5：D]datai與addri組合為addra，數(shù)據(jù)dia寫1表示這一地址已存儲(chǔ)數(shù)據(jù)，addm[11：O]addrb[7：0]同時(shí)更新RAM_EFase中地址addri存儲(chǔ)的數(shù)據(jù)為datai。當(dāng)查詢數(shù)據(jù)圖1CAM16x8實(shí)現(xiàn)框圖datam在CAM中的地址時(shí)，將datam作為RAM_Dual模塊端口B的表1字典容量與BRAM數(shù)量關(guān)系讀地址，可讀取數(shù)據(jù)dob，將dob進(jìn)行按位或運(yùn)算，如為1則表示匹配，為0則不匹配，并按照one—hot形式對(duì)d0b進(jìn)行解碼，獲得實(shí)際

8、匹容量基本CAM單元BRAM數(shù)量1024x18bitCAM16x8+CAMl6xlO128配的地址addrm。one-hot是一種數(shù)據(jù)編碼方式，例~N4bit十六進(jìn)制2o48xl9bitCAM16x10+CAMl6xl0256數(shù)據(jù)0x7可表示為16bit_--進(jìn)制數(shù)據(jù)0000000010000000，CAM就是利4096x2ObitCAM16x10+CAM16xl0512用這種方式實(shí)現(xiàn)的。8l92x2lbitCAMl6xll+CAM16x1