燕 威 薛長斌

?

高效低功耗低并行度LDPC編碼方法

燕 威*薛長斌

(中國科學(xué)院國家空間科學(xué)中心 北京 100190)(中國科學(xué)院復(fù)雜航天系統(tǒng)綜合電子與信息技術(shù)重點(diǎn)實(shí)驗(yàn)室 北京 100190)

低密度奇偶校驗(yàn)碼(LDPC)是最接近香農(nóng)極限的糾錯(cuò)碼之一，具有優(yōu)良的性能且被國際通信標(biāo)準(zhǔn)組織廣泛采納為信道編碼。CCSDS推薦使用LDPC碼作為近地空間和深空探測(cè)的信道編碼方案。該文提出高效，低功耗，低并行度的LDPC編碼方法。該方法通過采用插“0”和改變循環(huán)矩陣的結(jié)構(gòu)實(shí)現(xiàn)了對(duì)CCSDS標(biāo)準(zhǔn)中推薦的校驗(yàn)矩陣子矩陣大小為奇數(shù)的LDPC碼的低并行度編碼。通過分析編碼過程，提出了只對(duì)輸入信息中的“1”有效信息位進(jìn)行編碼的方案，減少了編碼中移位寄存器的移位次數(shù)，大幅度地降低了編碼器功耗。文中采用FPGA實(shí)現(xiàn)了(8176, 7154)78LDPC碼的編碼器，結(jié)果顯示在硬件開銷略有增加的情況下，編碼功耗大幅度下降，編碼速率接近低并行度編碼方案。

差錯(cuò)控制編碼；低并行度；低功耗；QC-LDPC；VLSI設(shè)計(jì)

1 引言

1962年，MIT的GALLAGER首次提出了低密度奇偶校驗(yàn)碼[1](LDPC碼)，但是受限于編譯碼算法的復(fù)雜性和當(dāng)時(shí)的集成電路制造水平，GALLAGER博士的發(fā)現(xiàn)沒有引起人們的重視。直到1993年，法國學(xué)者BERROU等人[2]提出了具有接近Shannon極限的Turbo碼之后。劍橋大學(xué)的MACKAY等人[3]重新對(duì)GALLAGER提出的LDPC碼進(jìn)行了深入的研究，并提出了采用了BP算法進(jìn)行譯碼的方案。2001年，MIT的CHUNG等人[4]提出了一類LDPC碼性能距離Shannon極限僅僅只有0.0045 dB，引起了編碼領(lǐng)域?qū)W者的極大研究熱情。

目前，LDPC的編解碼已進(jìn)入應(yīng)用研究階段。國際空間科學(xué)咨詢委員會(huì)(CCSDS)采納LDPC碼為近地空間和深空探測(cè)的信道編碼標(biāo)準(zhǔn)并給出了LDPC碼在遙控鏈路中的研究報(bào)告。標(biāo)準(zhǔn)中推薦7/8碼率(8176, 7154) LDPC碼作為近地空間信道編碼方案。這種LDPC碼生成矩陣具有準(zhǔn)循環(huán)的特點(diǎn)，可以方便地使用循環(huán)移位寄存器來實(shí)現(xiàn)編碼[5,12]。但是這種LDPC碼的生成矩陣校驗(yàn)位子矩陣為大小，如果要進(jìn)行并行編碼提高編碼效率，則只能按子矩陣并行編碼，需要緩存前級(jí)的輸入數(shù)據(jù)。對(duì)于宇航系統(tǒng)中的應(yīng)用非常不便，文獻(xiàn)[13]中提出了一種7/8碼率(8176, 7154)LDPC碼的低并行度編碼，通過采用插“0”和拆分子矩陣結(jié)構(gòu)，只需額外增加很少的硬件開銷就能實(shí)現(xiàn)該標(biāo)準(zhǔn)LDPC碼的按位低并行度編碼。但是并行編碼帶來的另外一個(gè)問題是對(duì)于宇航應(yīng)用中的器件，并行編碼結(jié)構(gòu)帶來的工作功耗的增加相當(dāng)驚人。文獻(xiàn)[14-16]提出了可配置循環(huán)移位的思想。本文通過研究了編碼器編碼運(yùn)算過程，提出了一種高效，低功耗，低并行度的編碼方案。

本文的第1節(jié)為引言部分；第2節(jié)說明本文需要用到的預(yù)備知識(shí)；第3節(jié)闡述具體的高效，低功耗，低并行度編碼的方案；第4節(jié)比較本文提出的方案和文獻(xiàn)中提出的串行和低并行編碼方案，并作分析；第5節(jié)為結(jié)論。

2 預(yù)備知識(shí)

2.1 編碼原理

LDPC的編碼運(yùn)算為矩陣的乘法運(yùn)算和GF(2)域的加法運(yùn)算[2]。以CCSDS推薦7/8碼率近地空間(8176, 7154)LDPC碼[9]為例，該7/8碼為系統(tǒng)碼，碼字長度為8176位，其中前面7154位為待編碼信息位，后面1022位為校驗(yàn)位。

CCSDS推薦7/8碼率LDPC碼的系統(tǒng)碼向量：

(3)

所以編碼的數(shù)學(xué)表達(dá)式為

=(4)

為了簡化編碼器的結(jié)構(gòu)設(shè)計(jì)，CCSDS推薦的生成矩陣校驗(yàn)矩陣部分(=1,2,,14;=1,2)為循環(huán)矩陣

這種循環(huán)移位的設(shè)計(jì)可以簡化矩陣的電路結(jié)構(gòu)，在實(shí)現(xiàn)中只需要保存校驗(yàn)矩陣中每個(gè)循環(huán)子矩陣各自的第1行資料(=1,2,,14;=1,2)即可，簡化了存儲(chǔ)結(jié)構(gòu)。

2.2 低并行度編碼方案

文獻(xiàn)[13]提出了CCSDS推薦近地空間LDPC碼低并行度編碼的方案。

該低并行度編碼方案使用在待編碼信息位數(shù)據(jù)中插“0”和改變校驗(yàn)矩陣結(jié)構(gòu)的方法，使得LDPC碼校驗(yàn)矩陣大小為的子矩陣可以兩位并行的進(jìn)行編碼運(yùn)算。

(7)

(8)

編碼運(yùn)算所得校驗(yàn)位結(jié)果為

3 高效低功耗方案

3.1 高效低功耗串行編碼方法

本文提出的高效低功耗編碼原理圖如圖1所示，以串行的CCSDS標(biāo)準(zhǔn)7/8碼率(8176, 7154) LDPC碼為例。在串行編碼器的結(jié)構(gòu)原理上，增加了移位控制器和改變了循環(huán)移位寄存器設(shè)計(jì)。串行輸入的待編碼信息位數(shù)據(jù)，首先輸入到移位控制器，移位控制器判斷輸入的數(shù)據(jù)為“1”或者“0”。

圖1 高效低功耗串行編碼結(jié)構(gòu)設(shè)計(jì)

如果輸入數(shù)據(jù)為“1”，則移位控制器輸出一個(gè)移位值給對(duì)應(yīng)的循環(huán)移位寄存器；同時(shí)輸出一個(gè)為“1”的高電平到循環(huán)移位寄存器的每位對(duì)應(yīng)的與門，此時(shí)循環(huán)移位寄存器根據(jù)移位控制器送過來的移位值進(jìn)行移位運(yùn)算，并將運(yùn)算后的結(jié)果從與門送到異或器，和累加器中的數(shù)值進(jìn)行異或操作，完成一次編碼運(yùn)算。

如果輸入數(shù)據(jù)為“0”，則移位控制器輸出為“0”的移位值給對(duì)應(yīng)的循環(huán)移位寄存器；同時(shí)輸出一個(gè)為“0”的低電平到循環(huán)移位寄存器的每位對(duì)應(yīng)的與門，此時(shí)循環(huán)移位寄存器不進(jìn)行移位運(yùn)算。

方案需要設(shè)計(jì)一個(gè)按照移位控制器的輸出值來進(jìn)行循環(huán)移位的循環(huán)移位器，當(dāng)校驗(yàn)位子矩陣較大時(shí)，這個(gè)想法難以實(shí)現(xiàn)，因?yàn)檎{(diào)度的復(fù)雜度會(huì)變得很大。所以我們需要根據(jù)應(yīng)用需求選擇合理的參數(shù)，用來限制移位值的最大值，當(dāng)輸入信息位中兩個(gè)最接近的“1”的距離超過了這個(gè)最大值，就將從移位值輸出，循環(huán)移位器做一次移位距離為的循環(huán)移位操作，然后從“0”開始重新計(jì)算移位值，這樣可以設(shè)計(jì)出較小規(guī)模的，復(fù)雜度可以接受的移位網(wǎng)絡(luò)。

考慮到輸入信息位是隨機(jī)的分布，假設(shè)信息位中連續(xù)“0”的個(gè)數(shù)分布應(yīng)該滿足近似的高斯分布，則可以根據(jù)輸入資料的分布概率選擇合適的值，這樣采用設(shè)定最大移位值得方法可以在移位網(wǎng)絡(luò)復(fù)雜度和設(shè)計(jì)需求之間取得折中。

移位值的計(jì)算算法如下：

若輸入待編碼信息位為“0”，則移位值為“0”；

若輸入待編碼信息位為“1”，且是輸入的第1個(gè)信息位，則移位值為“0”；

若輸入待編碼信息位為“1”，且不是輸入的第1個(gè)信息位，則移位控制器根據(jù)離這個(gè)信息位最近的為“1”的信息位的距離來計(jì)算移位值，并輸出控制信號(hào)“1”；若計(jì)算出的移位值達(dá)到了設(shè)定的最大移位值，則移位值輸出，并輸出一個(gè)為“0”的控制信號(hào)，同時(shí)再從“0”開始計(jì)算移位值，這樣循環(huán)移位器會(huì)進(jìn)行一次的循環(huán)移位操作，但不會(huì)進(jìn)行其他計(jì)算操作。

例如輸入待編碼信息位的前10位輸入數(shù)據(jù)為“1000100110”，則輸出的移位值依次為“1000400310”。控制信號(hào)為“1000100110”。

例如輸入待編碼信息位的前+3位輸入數(shù)據(jù)為“100…001”中間間隔+1個(gè)“0”，則輸出的移位值依次為“100…0K1”。控制信號(hào)為“100…001”。

以7/8碼率LDPC碼為例，循環(huán)移位寄存器的長度應(yīng)為校驗(yàn)矩陣子矩陣的大小值，也就是511位。移位值范圍從0到(可以取1到510之間的數(shù))。循環(huán)移位寄存器根據(jù)移位控制器輸送來的移位值進(jìn)行循環(huán)移位，根據(jù)移位控制器輸出的控制信息進(jìn)行乘加操作。這樣可以實(shí)現(xiàn)我們?cè)O(shè)想的只對(duì)待編碼信息位中的“1”進(jìn)行編碼的方案，能夠?qū)崿F(xiàn)編碼器功耗的大幅度降低。

3.2 高效低功耗低并行編碼結(jié)構(gòu)方案

因?yàn)榈筒⑿卸鹊木幋a方案具有較快的編碼速率和適中的硬件開銷。所以更適合CCSDS推薦的近地空間的7/8碼率LDPC碼編碼，所以本文提出了高效低功耗低并行度的編碼結(jié)構(gòu)方案。

如圖2所示，以CCSDS標(biāo)準(zhǔn)推薦深空探測(cè)7/8碼率LDPC(8176, 7154)碼為例。我們將7154位待編碼數(shù)據(jù)按照校驗(yàn)矩陣子矩陣的大小分為14組，每組511位待編碼信息位。采用文獻(xiàn)[13]中提出的待編碼數(shù)據(jù)輸入前插“0”的方案，對(duì)待編碼信息數(shù)據(jù)每隔511位插入一位“0”，這樣7154位信息位變?yōu)?168位信息位，即14組信息位，每組512位待編碼數(shù)據(jù)。為了簡化編碼時(shí)鐘同步，在7168位信息位后填充1008位“0”，使得待編碼信息位的總長為8176。

圖2 高效低功耗低并行度編碼結(jié)構(gòu)

高效低功耗低并行編碼采用4個(gè)子矩陣處理單元，如圖3所示。

圖3 子矩陣處理單元

編碼過程如下：

初始時(shí)刻，子矩陣處理單元1_1中的初始值為第1組循環(huán)校驗(yàn)矩陣的第1個(gè)循環(huán)校驗(yàn)矩陣的第1行的資料，即式(3)中子矩陣的第1行數(shù)據(jù)；子矩陣處理單元1_2中的初始值為第1組循環(huán)校驗(yàn)矩陣的第2個(gè)循環(huán)校驗(yàn)矩陣的第1行的資料，即式(3)中子矩陣的第1行數(shù)據(jù)；子矩陣處理單元2_1中的初始值為子矩陣處理單元1_1中的數(shù)據(jù)循環(huán)右移1位，即式(3)中子矩陣的第2行數(shù)據(jù)；子矩陣處理單元2_2中的初始值為子矩陣處理單元1_2中的數(shù)據(jù)循環(huán)右移1位，即式(3)中子矩陣的第2行數(shù)據(jù)。累加器初始值都為1022個(gè)“0”。待編碼數(shù)據(jù)串行輸入到編碼器，將待編碼數(shù)據(jù)分為14個(gè)512位向量,,,。

在第1個(gè)時(shí)鐘周期內(nèi)，如果移位控制器1輸入的待編碼信息位奇位數(shù)據(jù)odd_1為“1”，則輸出相應(yīng)的移位值到子矩陣處理單元1_1和子矩陣處理單元1_2，進(jìn)行循環(huán)移位操作，并輸出相應(yīng)的開關(guān)信息“1”到與循環(huán)移位單元每位對(duì)應(yīng)的與門，然后將循環(huán)移位操作后的數(shù)據(jù)輸入到累加器中進(jìn)行模2加操作。如果移位控制器1輸入的待編碼信息位奇位數(shù)據(jù)odd_1為“0”，則輸出相應(yīng)的移位值為“0”，子矩陣處理單元1_1和子矩陣處理單元1_2不進(jìn)行移位操作，并輸出相應(yīng)的開關(guān)信息“0”到與循環(huán)移位單元每位對(duì)應(yīng)的與門，停止累加操作。同理，將偶位數(shù)據(jù)even_1待編碼信息位輸入到移位控制器2，進(jìn)行相同的操作。

在第2到第256個(gè)時(shí)鐘周期內(nèi)，分別對(duì)輸入的奇偶位待編碼信息位數(shù)據(jù)執(zhí)行與第1個(gè)時(shí)鐘周期相同的操作。

第256個(gè)時(shí)鐘周期后，第1組循環(huán)校驗(yàn)矩陣結(jié)束。然后將子矩陣處理單元1_1中的數(shù)據(jù)更換為第2組循環(huán)校驗(yàn)矩陣的第1個(gè)循環(huán)校驗(yàn)矩陣的第1行的資料，即式(3)中子矩陣的第1行數(shù)據(jù)；子矩陣處理單元1_2中的數(shù)據(jù)更換為第2組循環(huán)校驗(yàn)矩陣的第2個(gè)循環(huán)校驗(yàn)矩陣的第1行的資料，即式(3)中子矩陣的第1行數(shù)據(jù)，子矩陣處理單元2_1中的數(shù)值更換為子矩陣處理單元1_1循環(huán)左移1位的數(shù)據(jù)，即式(3)中子矩陣的第2行數(shù)據(jù)，子矩陣處理單元2_2中的數(shù)值更換為子矩陣處理單元1_2循環(huán)左移1位的數(shù)據(jù)，即式(3)中子矩陣的第2行數(shù)據(jù)。對(duì)到向量，重復(fù)與輸入的處理相同的過程。

4 實(shí)現(xiàn)分析和比較

本文中提出的高效，低功耗，低并行度編碼器方案相比于文獻(xiàn)[13]中提出的低并行度編碼方案，最大的特點(diǎn)是在信息數(shù)據(jù)輸入循環(huán)矩陣之前加入了一個(gè)移位控制器并將固定次數(shù)的循環(huán)移位寄存器改變成可選移位次數(shù)的循環(huán)移位器。

從圖1中可以看出，編碼的過程本質(zhì)上是向量的乘加運(yùn)算，輸入的帶編碼信息位與對(duì)應(yīng)的循環(huán)移位寄存器中的每位數(shù)據(jù)相乘，在所有的帶編碼數(shù)據(jù)輸入完成后，將相乘的結(jié)果進(jìn)行模2加運(yùn)算，即可得編碼的校驗(yàn)位數(shù)據(jù)。因?yàn)榫幋a的過程本質(zhì)是乘加運(yùn)算，所以對(duì)于輸入的為“0”的帶編碼信息位，進(jìn)行乘加運(yùn)算對(duì)于最后的校驗(yàn)結(jié)果生成沒有影響。所以對(duì)輸入的“0”信息位時(shí)，停止編碼過程的矩陣的運(yùn)算，這樣會(huì)減小編碼功耗，而且輸入的信息位中的“0”的個(gè)數(shù)越多，這種功耗的降低越明顯。而在實(shí)際的工程應(yīng)用中“0”的位數(shù)甚至經(jīng)常超過一半，特別在有實(shí)時(shí)圖像數(shù)據(jù)和視頻數(shù)據(jù)傳輸?shù)膽?yīng)用場(chǎng)合。

為方便比較，設(shè)定該編碼方案取最大移位值為=8在Xilinx公司的XC4VLX80-12ff1148型FPGA上實(shí)現(xiàn)(與文獻(xiàn)[7]中所用器件相同)。開發(fā)環(huán)境為ISE13.2版本。結(jié)果顯示見表1。

表1兩種低并行度編碼結(jié)構(gòu)實(shí)現(xiàn)情況

表1中可以看出由于采用狀態(tài)機(jī)來實(shí)現(xiàn)多種不同移位值得循環(huán)移位器，所以相比于低并行結(jié)構(gòu)，高效低功耗低并行結(jié)構(gòu)有較多的LUT查找表資源開銷，這種開銷與設(shè)計(jì)者設(shè)定的最大移位值成相關(guān)關(guān)系，需要大量的模擬決定適合的值大小。

5 結(jié)論

本文提出的一種高效，低功耗，低并行度編碼結(jié)構(gòu)設(shè)計(jì)方案。在文獻(xiàn)[13]提出的低并行度編碼結(jié)構(gòu)設(shè)計(jì)的基礎(chǔ)上深入分析了編碼過程中的矩陣運(yùn)算和影響整個(gè)編碼結(jié)構(gòu)的功耗的關(guān)鍵點(diǎn)。提出了一種只對(duì)輸入待編碼信息位為“1”的有效信息位進(jìn)行編碼的方案，并給出了控制其中循環(huán)移位器的進(jìn)行移位的規(guī)則，在只增加部分多路選擇邏輯的基礎(chǔ)上實(shí)現(xiàn)了編碼電路工作功率的大幅度下降，而編碼器性能基本上沒受影響。文中提出的移位控制器可以普遍地用于類似使用循環(huán)矩陣進(jìn)行編碼的場(chǎng)合，對(duì)于降低類似編碼器的工作功耗具有重要意義。

[1] GALLAGER R G. Low-density parity-check codes[J]., 1962, 8(1): 21-28. doi: 10.1109/TIT.1962.1057683.

[2] 袁東風(fēng), 張海剛. LDPC碼理論與應(yīng)用[M]. 北京: 人民郵電出版社, 2008: 20-25.YUAN Dongfeng and ZHANG Haigang. LDPC Code Theory and Applications[M]. Beijing: Post and Telecom Press, 2008: 20-25.

[3] MACKAY D C. Good error-correcting codes based on very sparse matrices[J]., 1999, 45(2): 399-431. doi: 10.1109/18.748992.

[4] CHUNG S Y. On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit[J]., 2001, 5(2): 58-60. doi: 10.1109/ 4234.905935.

[5] MAHDI A and PALIOURAS V. A low complexity-high throughput QC-LDPC encoder[J]., 2014, 62(10): 2696-2708. doi: 10.1109/tsp. 2014.2314435.

[6] 欒志斌, 裴玉奎, 葛寧. 低存儲(chǔ)高速可重構(gòu)LDPC碼譯碼器設(shè)計(jì)及ASIC實(shí)現(xiàn)[J]. 電子與信息學(xué)報(bào), 2014, 36(10): 2287-2292. doi: 10.3724/SP.J.1146.2013.01939.

LUAN Zhibin, PEI Yukui, and GE Ning. Design and ASIC implementation of low memory high throughput reconfigurable LDPC decoder[J].&, 2014, 36(10): 2287-2292. doi: 10.3724/SP.J.1146.2013.01939.

[7] 蘇和光, 夏樹濤. 一種新的碼率兼容LDPC碼打孔方案[J]. 電子與信息學(xué)報(bào), 2011, 33(10): 2334-2339. doi: 10.3724/SP.J. 1146.2010.01202.SU Heguang and XIA Shutao. A novel puncturing scheme for rate-compatible LDPC codes[J].&, 2011, 33(10): 2334-2339. doi: 10. 3724/SP.J.1146.2010.01202.

[8] CCSDS. CCSDS 131.0-B-2-TM synchronization and channel coding[S]. Washington, DC, USA, 2011.

[9] CCSDS. CCSDS 131.1-O-2-low density parity check codes for use in near-earth and deep space applications[R]. Washington, DC, USA, 2007.

[10] CCSDS. CCSDS 230.2-G-1-next generation uplink[R]. Washington, DC, USA, 2014.

[11] CCSDS. CCSDS 231.1-O-1-short block length LDPC codes for TC synchronization and channel coding[R]. Washington, DC, USA, 2015.

[12] 張浩, 殷柳國. 星地高速數(shù)傳系統(tǒng)LDPC編碼器ASIC集成芯片設(shè)計(jì)[J]. 宇航學(xué)報(bào), 2015, 36(1): 96-102.ZHANG Hao and YIN Liuguo. ASIC design of an LDPC encoder for satellite-ground high-speed data transmission system[J]., 2015, 36(1): 96-102.

[13] 燕威, 楊雙, 薛長斌. 一種CCSDS標(biāo)準(zhǔn)低并行度高速LDPC編碼方案[R]. 中國科學(xué)院國家空間科學(xué)中心, 2015.YAN Wei, YANG Shuang, and XUE Changbin. An encoder architecture scheme with low parallel and high speed for LDPC codes based CCSDS standard[R]. National Space Science Center,Chinese Academy of Science, 2015.

[14] MCGUIRE M, SIMA M, and MILLER S. VLSI implementation of a shift-enabled reconfigurable array[C]. 2008 IEEE International Symposium on Circuits and Systems, 2008, 1(10): 1360-1363.

[15] PARHI K K and OH D. Area efficient controller design of barrel shifters for reconfigurable LDPC decoders[C]. 2008 IEEE International Symposium on Circuits and Systems, Seattle, WA, USA, 2008: 240-243.

[16] PARHI K K and OH D. Low-complexity switch network for reconfigurable LDPC decoders[J].(), 2010, 18(1): 85-94.doi: 10.1109/TVLSI.2008.2007736.

An Efficient LDPC Encoder Scheme with Low-power Low-parallel

YAN Wei XUE Changbin

(National Space Science Center, Chinese Academy of Sciences, Beijing 100190, China)(Key Laboratory of Integrated Avionics and Information Technology for Complex Aerospace Systems, Chinese Academy of Sciences, Beijing 100190, China)

Low-density parity-check code is the one of error-correction codes most approaching Shannon limit, which is adopted as a standard for channel coding by many international communication standard organizations. CCSDS recommends LDPC as channel coding scheme in near earth space and deep space communication. An efficient LDPC coding scheme with low power and low parallel is presented in this paper. By filling “0” and changing the cyclic-matrix structure, the proposed scheme implements a low parallel coding for the LDPC, which is recommended by CCSDS, and of which the size of submatrix of check matrices is odd. By analyzing the coding process, the valid bit “1” among input information bits is coded only, and it decreases obviously the code power. The encoder architecture for 7/8 LDPC is implemented in FPGA. The result shows that encoder achieves a high encoding speed approaching low parallel encoder scheme and a much lower encoding power while increases few hardware overhead.

Error-correction codes; Low parallel; Low power; QC-LDPC; VLSI design

TN911.22

A

1009-5896(2016)09-2268-06

10.11999/JEIT151362

2016-05-10；

2016-07-04

燕威 yanwei_nssc@163.com

燕 威： 男，1989年生，博士生，研究方向?yàn)樾诺谰幾g碼技術(shù)及大規(guī)模集成電路設(shè)計(jì).

薛長斌： 男，1972年生，研究員，研究方向?yàn)樾盘?hào)與信息處理技術(shù).