徐勇 李珂 馮國平 陶利民 龐波

(北京空間飛行器總體設(shè)計部，北京 100094)

?

一種FPGA在軌重構(gòu)配置數(shù)據(jù)壓縮算法

徐勇 李珂 馮國平 陶利民 龐波

(北京空間飛行器總體設(shè)計部，北京 100094)

對現(xiàn)場可編程門陣列(FPGA)在軌重構(gòu)配置文件壓縮，可以大大減少遙控上注時間。為此，文章利用FPGA配置文件中0值較多的特點，結(jié)合游程編碼(RLC)及字典編碼的優(yōu)勢，提出一種FPGA在軌重構(gòu)配置數(shù)據(jù)壓縮算法，即結(jié)合零游程(Zeros Run Length，ZRL)編碼的VLZW壓縮算法(簡稱為ZRL-VLZW算法)。為減小航天器載計算機(jī)內(nèi)存開銷，使用索引迭代方式存儲字典并限制字典長度。采用航天器常用FPGA多種資源占用比的配置文件，利用ZRL-VLZW、LZW和VLZW算法進(jìn)行壓縮測試比較。結(jié)果表明：ZRL-VLZW算法性能優(yōu)于LZW算法和VLZW算法，可有效進(jìn)行配置文件的壓縮，使在軌重構(gòu)注入數(shù)據(jù)上注時間減少為原來的1/20～1/3。

現(xiàn)場可編程門陣列；在軌重構(gòu)；配置數(shù)據(jù)壓縮

1 引言

隨著空間技術(shù)的發(fā)展，航天器體積、質(zhì)量不斷縮小，計算速度越來越快，功能越來越多，傳統(tǒng)分立電路及小容量反熔絲現(xiàn)場可編程門陣列(FPGA)已經(jīng)不能滿足航天器設(shè)計的要求[1]。因此，靜態(tài)隨機(jī)存儲器(SRAM)型FPGA在航天器設(shè)計中的應(yīng)用越來越多，主要完成計算機(jī)接口、存儲器管理、信號處理和通信協(xié)議處理等功能?；赟RAM型的航天器載FPGA在軌重構(gòu)技術(shù)，在提高航天器功能靈活性及可升級特性的同時，也能用于在軌修復(fù)FPGA局部永久損傷和設(shè)計錯誤等缺陷[2]，因此越來越多的航天器載FPGA板級電路具備在軌可重構(gòu)功能[3-4]。然而，用于FPGA重構(gòu)的配置文件數(shù)據(jù)量較大，以300萬門中等規(guī)模FPGA為例，其數(shù)據(jù)量為10.495 Mbit，航天器測控信道有限的帶寬使得FPGA重構(gòu)程序上注需要漫長的時間，浪費航天器寶貴的可見觀測弧段時間，且當(dāng)可見觀測弧段時間短時，則需要多次可見弧段時間續(xù)傳才能完成一個重構(gòu)配置文件的上注，成為影響在軌重構(gòu)計算機(jī)系統(tǒng)使用效率的一個重要因素。

在無法大幅提高遙控帶寬的前提下，減小重構(gòu)配置數(shù)據(jù)量成為解決上述難題的最佳選擇。目前，數(shù)據(jù)壓縮算法主要包括算術(shù)編碼、可變長編碼(如Golomb、Huffman)及字典編碼。算術(shù)編碼算法依賴于數(shù)據(jù)的實時概率統(tǒng)計，計算量大，速度慢，不適合在航天器上應(yīng)用?？勺冮L編碼算法比較適合于符合高斯分布的樣本，而FPGA的配置文件拆分為字節(jié)樣本時并不符合高斯分布特性。因此，F(xiàn)PGA配置文件壓縮經(jīng)常使用字典編碼算法。然而，單純字典編碼算法在進(jìn)行FPGA配置文件壓縮時，未充分利用FPGA配置文件中連續(xù)0數(shù)據(jù)區(qū)域較多的特點，導(dǎo)致壓縮效率較低。為此，本文在字典編碼算法VLZW(Variable Lempel Ziv Welch)[5]的基礎(chǔ)上，考慮了航天器計算機(jī)系統(tǒng)內(nèi)存資源緊張的情況，根據(jù)航天器FPGA配置文件的數(shù)據(jù)分布特點，給出一種結(jié)合零游程(Zeros Run Length，ZRL)編碼的VLZW壓縮算法(簡稱為ZRL-VLZW算法)，并將其應(yīng)用于航天器常用FPGA配置文件的壓縮中。驗證結(jié)果表明，ZRL-VLZW算法性能優(yōu)于LZW(Lempel Ziv Welch)算法和VLZW算法，可用于航天器可重構(gòu)系統(tǒng)的在軌重構(gòu)配置數(shù)據(jù)壓縮。

2 ZRL-VLZW壓縮算法

2.1 SRAM型FPGA配置文件介紹

SRAM型FPGA的可編程特性，包括邏輯真值表、互聯(lián)、IP核參數(shù)、IO屬性、RAM參數(shù)等配置信息，是由內(nèi)部的配置存儲器控制的[6]。該配置存儲器可由JTAG鏈寫入，由FPGA上電主動加載，由外部SelectMap口被動寫入，甚至可以在工作過程中進(jìn)行寫入刷新，以糾正單粒子翻轉(zhuǎn)造成的影響。寫入/加載入配置存儲器的數(shù)據(jù)即為配置文件，該文件的組成主要包含若干幀的數(shù)據(jù)，還包含同步頭、寫入命令、寫入地址、校驗、復(fù)位命令等諸多控制FPGA啟動信息幀。

2.2 自適應(yīng)零游程預(yù)壓縮

在航天器計算機(jī)中，存儲資源是非常有限的，VLZW算法中使用字符串的方式存儲字典，不僅字典項的長度信息需要存儲，而且字典項中的字符串長度還不固定，實現(xiàn)時需要復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，并占用大量的內(nèi)存資源。另外，在FPGA配置文件中存在大片連續(xù)的零數(shù)據(jù)(圖1中藍(lán)色部分)，針對這部分?jǐn)?shù)據(jù)，可采用比VLZW算法效率更高的零游程(ZRL)編碼進(jìn)行預(yù)壓縮?；诖?，本文對VLZW算法進(jìn)行改進(jìn)，包括利用游程編碼提高連續(xù)‘0’區(qū)域的編碼效率及使用迭代字典存儲方法。

圖1 FPGA配置文件數(shù)據(jù)內(nèi)容Fig.1 Contents of FPGA configuration file

(1)首先使用一種僅針對0系數(shù)進(jìn)行游程編碼的自適應(yīng)零游程編碼[7]進(jìn)行數(shù)據(jù)預(yù)壓縮，獲得零游程數(shù)據(jù)DataA和非零數(shù)據(jù)DataB。自適應(yīng)零游程(如圖2所示)包含普通和零游程2種模式：編碼時做前向自適應(yīng)建模，并在2種模式中轉(zhuǎn)換。其規(guī)則比較簡單：初始模式為普通模式，該模式下直接將輸入樣本輸出，若連續(xù)輸入0達(dá)到2個，進(jìn)入零游程模式；在零游程模式無輸出，只計0個數(shù)，直到輸入非0時退回普通模式，并輸出0游程個數(shù)和該非0樣本。

圖2 前向自適應(yīng)零游程編碼示例Fig.2 An instance of forward adaptive zeros run length coding

(2)限制字典長度，當(dāng)字典長度達(dá)到設(shè)定邊界Nmax時，初始化字典，重新建立字典。

(3)提出迭代式的字典存儲方式，減少字典存儲規(guī)模。本文的字典中，每個索引項的內(nèi)容不再使用字符串+長度的方式存儲，而是存儲為前綴Prefix索引號+后綴字符Suffix的方式(Pre_Index，Suff_Symb)。其中：Pre_Index為字典索引，取值范圍為1～Nmax；Suff_Symb為數(shù)據(jù)符號。因此，每個字典的位數(shù)是固定的，有利于CPU或者FPGA實現(xiàn)本文算法時簡單地管理數(shù)據(jù)，同時內(nèi)存開銷也隨之減小。

2.3 ZRL-VLZW算法流程

ZRL-VLZW算法的計算流程如下。

(1)開始數(shù)據(jù)壓縮，使用自適應(yīng)零游程編碼對配置文件進(jìn)行預(yù)壓縮，獲得兩部分?jǐn)?shù)據(jù)，即零游程數(shù)據(jù)DataA和非零數(shù)據(jù)DataB。

(2)對DataB采用字典編碼進(jìn)行編碼。

(2.1)進(jìn)行算法的初始化，以8 bit/Symbol為例，按照迭代式字典的格式，建立初始字典為D={(0，i)|i=1～256}；此時字典中僅包含256個索引項，每項的第1個元素Pre_Index為0，解壓縮迭代查字典時表示迭代查詢到了盡頭，停止一個索引的解碼。初始化時令計算前綴Pre=0。

(2.2)讀入符號C，與當(dāng)前前綴Pre組成查詢項(Pre，C)，到字典中查詢是否存在與(Pre，C)一致的索引項。如果存在，則跳到①執(zhí)行，否則跳到②執(zhí)行。①將前綴Pre賦值為新查詢到的字典索引CAM(Pre，C)，并判斷編碼是否結(jié)束：是，則輸出Code(Pre)；否則，跳到(2.2)繼續(xù)編碼。②判斷字典長度是否小于Nmax：是，則初始化字典；否則，將(Pre，C)加入字典，輸出Code(Pre)，并令Pre=CAM(0，C)。然后，判斷編碼是否結(jié)束：是，則輸出Code(Pre)；否則，跳到(2.2)繼續(xù)編碼。

(3)將字典編碼后碼流Code與游程編碼碼流DataA一起作為壓縮后數(shù)據(jù)上注。

上述流程中，Code(N)定義為當(dāng)前字典長度下N所需bit的最小位寬二進(jìn)制編碼，CAM(A，B)定義為字典中(A,B)向量的存儲位置。

迭代字典的解壓縮算法為壓縮過程的逆過程，邊解壓邊建立解壓字典，解壓時根據(jù)壓縮數(shù)據(jù)中的索引號Index查詢當(dāng)前字典，而基于迭代字典的解壓縮算法在查詢某個索引號Index時，要以迭代的方式將查詢到的索引項中Pre_Index賦值給Index并輸出符號C，直到Pre_Index為0為止，即為該索引號Index解碼完成。

3 基于壓縮的在軌FPGA重構(gòu)流程

基于壓縮的在軌FPGA重構(gòu)流程如下。

(1)首先，將FPGA配置文件切分為若干編碼保護(hù)段，防止誤碼擴(kuò)散效應(yīng)。

(2)每個段單獨進(jìn)行壓縮。

(3)壓縮后碼流進(jìn)一步按照航天器上注格式拆分打包為若干遙控幀向航天器上發(fā)送。遙控信道鏈路層采取數(shù)據(jù)完整性校驗及差錯重傳機(jī)制保障數(shù)據(jù)的無誤傳輸。

(4)由于航天器上計算機(jī)內(nèi)存有限，航天器上的解碼過程為漸進(jìn)性解碼：在接收到第1幀數(shù)據(jù)時，就開始解碼，內(nèi)存中僅緩存當(dāng)前遙控幀及動態(tài)重建的字典，解碼出的數(shù)據(jù)實時寫入FPGA外部的非易失性配置存儲器。解碼用完的遙控幀即可丟棄，因此內(nèi)存中僅須要開辟較小的內(nèi)存來存儲字典。

(5)在所有壓縮數(shù)據(jù)注入完成后，F(xiàn)PGA外部的非易失性配置存儲器中就包含了解壓后的完整配置文件，發(fā)送FPGA重加載指令，即可實現(xiàn)FPGA的在軌重構(gòu)。

4 試驗數(shù)據(jù)及分析

為驗證ZRL-VLZW算法的有效性，開發(fā)了ZRL-VLZW、LZW、VLZW的Matlab驗證程序，以常用的Xilinx SRAM型FPGA XQR2V3000及XC4VSX55的實際工程設(shè)計配置文件為例進(jìn)行壓縮測試，字典深度為16 384項。2種FPGA在不同資源占用比時的壓縮比，見表1和表2。

在對XQR2V3000及XC4VSX55兩款常用FPGA的多種資源占用比的比特文件進(jìn)行壓縮試驗中可以看出：ZRL-VLZW算法均高于經(jīng)典LZW算法及VLZW算法的性能，且當(dāng)資源占用比越低時，優(yōu)勢越明顯。ZRL-VLZW算法可以將配置文件數(shù)據(jù)壓縮至1/20～1/3，壓縮比的大小取決于FPGA的資源占用比，這主要是由于在FPGA的配置文件中，當(dāng)資源占用比較低時，存在大片連續(xù)零數(shù)據(jù)，ZRL-VLZW算法中自適應(yīng)零游程編碼對這部分?jǐn)?shù)據(jù)進(jìn)行編碼的效率高于LZW算法，除連續(xù)零數(shù)據(jù)以外的其他數(shù)據(jù)的壓縮比等同于VLZW算法，從而達(dá)到更高的壓縮比。

表1 XQR2V3000 FPGA不同資源占用比時的3種算法壓縮效果對比

表2 XC4VSX55 FPGA不同資源占用比時的3種算法壓縮效果對比

5 結(jié)束語

使用壓縮算法對FPGA在軌重構(gòu)上注配置文件壓縮，可以大大縮短航天器在軌重構(gòu)數(shù)據(jù)的上注時間，提高航天器可重構(gòu)系統(tǒng)的應(yīng)用效率。本文提出一種航天器FPGA在軌重構(gòu)配置數(shù)據(jù)壓縮算法ZRL-VLZW，利用FPGA配置文件中0值數(shù)據(jù)較多的特點，并結(jié)合了游程編碼及字典編碼的優(yōu)勢。同時，為盡量減小航天器計算機(jī)的內(nèi)存開銷，將VLZW算法進(jìn)行字典長度限制，并使用索引迭代方式存儲字典。試驗中采用航天常用FPGA的多種資源占用比的配置文件進(jìn)行壓縮測試，并與LZW算法和VLZW算法進(jìn)行比較，結(jié)果表明：ZRL-VLZW算法可以有效進(jìn)行配置文件的壓縮，且性能優(yōu)于LZW算法和VLZW算法,可使在軌重構(gòu)數(shù)據(jù)上注時間減少至1/20～1/3。

References)

[1]楊孟飛，郭樹玲，孫增圻．航天器控制應(yīng)用的星載計算機(jī)技術(shù)[J]．航天控制，2005，23(2)：78-84

Yang Mengfei,Guo Shuling,Sun Zengqi.On-board computer techniques for spacecraft control[J].Aerospace Control，2005，23(2)：78-84 (in Chinese)

[2]劉源，孫兆偉，沈毅，等.可重構(gòu)星載信息處理系統(tǒng)FPGA預(yù)規(guī)劃技術(shù)[J].哈爾濱工程大學(xué)學(xué)報,2013,34(7)：878-888

Liu Yuan,Sun Zhaowei,Shen Yi,et al.FPGA pre-layout plan for reconfigurable on-board information processing system[J].Journal of Harbin Engineering University,2013,34(7)：878-888 (in Chinese)

[3]孫兆偉，劉源，邢雷，等.面向多任務(wù)的可重構(gòu)星載計算機(jī)設(shè)計[J].系統(tǒng)工程與電子技術(shù)，2011，33(6)：1407-1414

Sun Zhaowei,Liu Yuan,Xing Lei，et al.Design of reconfigurable on-board computer for multitask[J].Systems Engineering and Electronics，2011,33(6)：1407-1414 (in Chinese)

[4]Williams J A，Dawood A S，Visser S J，et al． Reconfigurable on board processing and real-time remote sensing [J]．IEEE Trans． on Information and Systems，2003，86(5)：819-829

[5]邢虹.FPGA位流生成及其壓縮[D].上海：復(fù)旦大學(xué)，2008

Xing Hong.Generation and compression of FPGA bit-stream [D].Shanghai：Fudan University,2008 (in Chinese)

[6]Xilinx Inc.Xapp779-correcting single-event upsets in Virtex-II platform FPGA configuration memory[R].San Jose,California：Xilinx Inc.,2007

[7]徐勇，徐智勇，張啟衡，等.適于硬件實現(xiàn)的低復(fù)雜度圖像壓縮[J].光學(xué)精密工程，2009，17(9)：2262-2268

Xu Yong,Xu Zhiyong，Zhang Qiheng，et al.Low complexity image compression scheme for hardware implementation [J].Optics and Precision Engineering,2009，17(9)：2262-2268 (in Chinese)

(編輯：夏光)

Configuration Data Compression Algorithm for FPGA On-orbit Reconfiguration

XU Yong LI Ke FENG Guoping TAO Limin PANG Bo

(Beijing Institute of Spacecraft System Engineering,Beijing 100094,China)

The time for uploading FPGA on-orbit reconfiguration file can be reduced multiple times by using compression technology,so an algorithm called ZRL-VLZW (Zero Run Length VLZW) is proposed.It takes character of continues 0 data in configuration file to play the advantage of run length coding.In order to minimize the memory overhead of satellite computer,the entry number of words dictionary is limited and iterative dictionary is employed. In the experiments,the performances of proposed algorithm are compared with LZW (Lempel Ziv Welch) and VLZW (Variable Lempel Ziv Welch) algorithm in compression configuration file of typical FPGAs. The results show that the proposed algorithm ZRL-VLZW can obtain higher compression ratio than that of LZW and VLZW. The time for uploading FPGA on-orbit reconfiguration file can be reduced to 1/20～1/3 by using the proposed algorithm.

FPGA；on-orbit reconfiguration；configuration data compression

2015-02-28；

2015-05-20

國家重大科技專項工程

徐勇，男，博士，研究方向為星載電子系統(tǒng)、星載圖像信息處理。Email：andrexu@163.com。

TP332.1

A

10.3969/j.issn.1673-8748.2015.06.013