国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

低存儲(chǔ)可線性編碼的QC-LDPC碼設(shè)計(jì)

2017-06-13 10:43孔令軍趙春明
關(guān)鍵詞:碼字校驗(yàn)復(fù)雜度

孔令軍 姜 明 趙春明

(1東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室, 南京 210096)(2南京郵電大學(xué)通信與信息工程學(xué)院, 南京 210003)

低存儲(chǔ)可線性編碼的QC-LDPC碼設(shè)計(jì)

孔令軍1,2姜 明1趙春明1

(1東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室, 南京 210096)(2南京郵電大學(xué)通信與信息工程學(xué)院, 南京 210003)

為了解決構(gòu)造任意長(zhǎng)度、無小停止集且無短環(huán)QC-LDPC碼的設(shè)計(jì)問題,研究了基于Tanner圖的停止集、圍長(zhǎng)和最小碼重三者之間的關(guān)系,提出了QC-LDPC碼無短停止距離且無短環(huán)的充要條件.在此基礎(chǔ)上,為了進(jìn)一步降低編碼復(fù)雜度并保留結(jié)構(gòu)化特性,提出了一種具有線性編碼復(fù)雜度的基于后向迭代的QC-LDPC碼.仿真結(jié)果表明:所構(gòu)造的QC-LDPC碼的糾錯(cuò)性能與IEEE 802.11n中QC-LDPC碼相近,與IEEE 802.16e中QC-LDPC碼相比,在誤碼率為10-6時(shí),可獲得0.15 dB的性能增益;此外,該碼字只需存儲(chǔ)移位因子和單位子矩陣的階數(shù),所占硬件存儲(chǔ)空間明顯小于另外2種QC-LDPC碼.

QC-LDPC碼;準(zhǔn)循環(huán)碼;停止集;停止距離;圍長(zhǎng)

近年來,LDPC碼[1-2]憑借其在AWGN等信道中具有接近香農(nóng)限的糾錯(cuò)性能且可實(shí)現(xiàn)的譯碼復(fù)雜度,成為當(dāng)今信道編碼領(lǐng)域的研究熱點(diǎn)之一[3-5].QC-LDPC碼是借用數(shù)學(xué)分析法(如幾何代數(shù)方法)來構(gòu)造的一類非常重要的LDPC碼,其校驗(yàn)矩陣具有類循環(huán)特性,實(shí)現(xiàn)復(fù)雜度低,可以采用簡(jiǎn)單的移位寄存器硬件來實(shí)現(xiàn)編碼器,易于硬件實(shí)現(xiàn)[6-7].

LDPC碼的校驗(yàn)矩陣主要基于停止集和圍長(zhǎng)來進(jìn)行構(gòu)造.停止集及其停止距離制約著迭代譯碼收斂速率;當(dāng)圍長(zhǎng)趨于無窮時(shí),和積譯碼算法近似為最優(yōu)譯碼算法.文獻(xiàn)[8]指出,經(jīng)過二進(jìn)制刪除信道或AWGN信道傳輸, 采用迭代譯碼算法時(shí)停止集具有重要的作用.文獻(xiàn)[9-10]指出,采用迭代譯碼算法時(shí)譯碼性能差的主要原因是LDPC碼對(duì)應(yīng)的Tanner圖中含有小的停止集.編碼復(fù)雜度是影響LDPC碼應(yīng)用的一個(gè)主要問題.通常采用生成矩陣的方法進(jìn)行編碼,編碼運(yùn)算復(fù)雜度為碼長(zhǎng)的平方.LDPC碼的碼長(zhǎng)往往多達(dá)數(shù)千比特,會(huì)影響編碼器的實(shí)現(xiàn).為此,需要回避生成矩陣,直接通過校驗(yàn)矩陣進(jìn)行編碼.在碼字性能允許的范圍內(nèi),校驗(yàn)矩陣結(jié)構(gòu)化能最大限度地降低編碼復(fù)雜度.IEEE 802.16e和IEEE 802.11n標(biāo)準(zhǔn)中均采用了可近似線性編碼的LDPC碼方案,雖然降低了編碼的復(fù)雜度,但破壞了LDPC碼校驗(yàn)矩陣的結(jié)構(gòu)特性,增加了編解碼器所占的硬件存儲(chǔ)資源.

為了在降低編碼復(fù)雜度的同時(shí)保留結(jié)構(gòu)化特性,本文提出了一種基于后向迭代的可線性編碼的QC-LDPC碼,綜合考慮了停止集、圍長(zhǎng)、最小碼重三者之間的關(guān)系,在增加圍長(zhǎng)和停止距離的同時(shí)盡可能提高最小碼重.仿真結(jié)果表明,所設(shè)計(jì)的碼字具有良好的誤碼率性能,更適于實(shí)際應(yīng)用.

1 QC-LDPC碼的停止集與圍長(zhǎng)

對(duì)于每個(gè)變量節(jié)點(diǎn)v∈V和校驗(yàn)節(jié)點(diǎn)c∈C,dv和dc分別表示v和c的度,dV(c)表示連接c到變量節(jié)點(diǎn)集合V的邊的數(shù)量.集合S為L(zhǎng)DPC碼對(duì)應(yīng)的Tanner圖的變量節(jié)點(diǎn)集合V的子集.如果集合S的所有鄰節(jié)點(diǎn)(與Tanner圖中集合S的變量節(jié)點(diǎn)相連的校驗(yàn)節(jié)點(diǎn))與S相連的次數(shù)不少于2,則稱S為停止集.停止集一般由多個(gè)環(huán)構(gòu)成.構(gòu)成停止集的變量節(jié)點(diǎn)分為2種:① 變量節(jié)點(diǎn)與其他變量節(jié)點(diǎn)構(gòu)成環(huán);② 變量節(jié)點(diǎn)連接不同的環(huán).

QC-LDPC碼的校驗(yàn)矩陣由單位陣的循環(huán)移位組合而成,其移位數(shù)由索引矩陣確定[6].索引矩陣P可表示為

(1)

式中,索引矩陣元素Px,y=aybx,其中0≤x≤j-1,0≤y≤k-1,j和k分別為矩陣的行數(shù)和列數(shù),a和b為移位因子.

QC-LDPC碼的校驗(yàn)矩陣H可由P得到,其元素IPx,y由m階單位陣I循環(huán)移位Px,y(modm)位構(gòu)成.

定理1 QC-LDPC碼的校驗(yàn)矩陣H含有停止距離為3的停止集的充要條件為:至少存在一組數(shù)(x,x′,x″,y,y′,y″)使得方程組

(2)

中至少一個(gè)方程成立,同時(shí)滿足

H(i,y)+H(i,y′)+H(i,y″)≠1

(3)

式中,0≤x≤j-3;1≤x′≤j-2;2≤x″≤j-1;x≠x′≠x″;0≤y≤k-3; 1≤y′≤k-2;2≤y″≤k-1;y≠y′≠y″;0≤i≤j-1;i≠x≠x′≠x″.

證明 至少存在一組數(shù)(x,x′,x″,y,y′,y″)使得方程組(2)中任意一方程成立時(shí),QC-LDPC碼的校驗(yàn)矩陣H含有6環(huán).定理1的證明等價(jià)于若校驗(yàn)矩陣H含有6環(huán),其6環(huán)所含有的3個(gè)變量節(jié)點(diǎn)構(gòu)成停止距離為3的停止集.由停止集定義可知,其鄰節(jié)點(diǎn)與本身連接邊的數(shù)目不少于2.構(gòu)成6環(huán)的3個(gè)鄰節(jié)點(diǎn)滿足定義,只要確保其他鄰節(jié)點(diǎn)也滿足定義即可.式(3)確保了其他校驗(yàn)節(jié)點(diǎn)與構(gòu)成6環(huán)的變量集合S連接次數(shù)不等于1.此時(shí),變量集合S構(gòu)成停止距離為3的停止集.

推論1 QC-LDPC碼校驗(yàn)矩陣H中無停止距離為3的停止集的必要條件為

(4)

式中, 1≤s≤k-2;2≤s′≤k-1;s

根據(jù)推論1,本文提出停止距離為3的停止集檢測(cè)方程組為

(5)

式中,1≤s≤k-2;2≤s′≤k-1;s

以列重為3、行重為6的(3,6)QC-LDPC碼為例,根據(jù)式(5)得出停止距離為3的停止集檢測(cè)矩陣F為

F=F1&F2&F3&F4&F5&F6

(6)

式中

(7)

式中,1≤v≤6.

設(shè)定移位因子a,b及最小單位子矩陣的階次m后,檢測(cè)矩陣F中非下三角矩陣的值是否無零元素,即可確定QC-LDPC碼是否含有停止距離為3的停止集. 根據(jù)式(5),可得出任意QC-LDPC碼的檢測(cè)矩陣,從而構(gòu)造出任意行重和列重的無停止距離為3的QC-LDPC碼,進(jìn)一步構(gòu)造出無停止距離為2的QC-LDPC碼.低碼重碼的存在使譯碼器糾錯(cuò)能力低下,不能糾正多個(gè)比特的錯(cuò)誤.根據(jù)最小碼重定義可知,生成矩陣行向量的最小碼重小于該碼字的最小碼重,可作為最小碼重的一個(gè)上界,從而為構(gòu)造無低碼重的LDPC碼提供依據(jù).

2 低存儲(chǔ)可線性編碼的QC-LDPC碼構(gòu)造算法

根據(jù)定理1及推論1,給定移位因子,計(jì)算其對(duì)應(yīng)的QC-LDPC碼停止集檢測(cè)矩陣,篩選出使碼字無停止距離為2和3的移位因子.為進(jìn)一步降低編碼復(fù)雜度,令所構(gòu)造LDPC碼的校驗(yàn)矩陣Hd為

Hd=[HtHbs]

(8)

式中,Ht和Hbs分別表示具有準(zhǔn)循環(huán)結(jié)構(gòu)的子矩陣和后向迭代的雙對(duì)角矩陣,且Ht的索引矩陣滿足式(1).由式(1)可知,只需確定移位因子a和b、單位子矩陣階數(shù)p以及列重cw,即可得出校驗(yàn)矩陣Ht.

低存儲(chǔ)可線性編碼的QC-LDPC碼構(gòu)造算法步驟如下:

①κ=1,根據(jù)Tκ=(aκ,bκ)可得移位因子aκ和bκ,令a=aκ,b=bκ,根據(jù)式(1)可得到Htκ.

② 后向雙對(duì)角矩陣Hbsκ矩陣為

(9)

式中,I0表示無移位的單位矩陣.

④ 根據(jù)Tκ中的移位因子,構(gòu)造出無短環(huán)和無小停止集、具有線性編碼復(fù)雜度的QC-LDPC碼.

⑦ 得到最終所構(gòu)造碼字的最小漢明距離dmin≈wmin.

綜合考慮環(huán)、停止集以及最小碼重對(duì)LDPC碼性能的影響,進(jìn)行低存儲(chǔ)、可線性編碼的QC-LDPC碼設(shè)計(jì).此外,采用本文方法還可估算QC-LDPC碼的最小漢明距離.

3 性能分析與仿真比較

所構(gòu)造的QC-LDPC碼校驗(yàn)矩陣Hd為

(10)

式中,單位陣I的下標(biāo)根據(jù)式(1)確定.

表1 LDPC碼的參數(shù)

與IEEE 802.11n和IEEE 802.16e中QC-LDPC碼的校驗(yàn)矩陣相比,所提出的基于后向迭代的子矩陣結(jié)構(gòu)最為簡(jiǎn)單,IEEE 802.11n和IEEE 802.16e中碼字的校驗(yàn)矩陣只是具有近似的雙對(duì)角結(jié)構(gòu).此外,IEEE 802.11n和IEEE 802.16e中QC-LDPC碼的校驗(yàn)矩陣左邊子矩陣不具備準(zhǔn)循環(huán)特性,因此需要大量的硬件存儲(chǔ)資源存儲(chǔ)校驗(yàn)矩陣,而所構(gòu)造的校驗(yàn)矩陣只需存儲(chǔ)移位因子a和b.

圖1為本文構(gòu)造的QC-LDPC碼與其他LDPC碼的BER曲線比較.由構(gòu)造方法可知,所設(shè)計(jì)的碼字既不含停止距離為2和3的停止集,又有效避免了4環(huán)和6環(huán);同時(shí),所提方案確保碼字的最小碼重盡可能最大化.仿真結(jié)果證明,與等長(zhǎng)的隨機(jī)LDPC碼相比,基于后向迭代的不規(guī)則QC-LDPC碼具有較好的BER性能,在SNR<2 dB時(shí)能迅速收斂.本文構(gòu)造的QC-LDPC碼具有優(yōu)于IEEE 802.16e 中標(biāo)準(zhǔn)中等長(zhǎng)QC-LDPC碼的BER性能,當(dāng)BER=10-6時(shí),具有大約0.15 dB的增益;而與IEEE 802.11n中的QC-LDPC碼相比,兩者具有相近的糾錯(cuò)性能.此外,所構(gòu)造的QC-LDPC碼具有線性編碼復(fù)雜度,且在碼率和碼長(zhǎng)已知時(shí),只需存儲(chǔ)移位因子和單位子矩陣的階數(shù),因而存儲(chǔ)校驗(yàn)矩陣所占硬件存儲(chǔ)空間較小,而另外2種QC-LDPC碼為近似線性編碼,需要較大的存儲(chǔ)空間.

圖1 LDPC碼仿真誤碼率比較

4 結(jié)論

1)為了在降低編碼復(fù)雜度的同時(shí)保留結(jié)構(gòu)化特征,本文提出了一種基于后向迭代的可線性編碼的不規(guī)則QC-LDPC碼.該碼字具有良好的BER性能,既不含停止距離為2和3的停止集,又有效避免了4環(huán)和6環(huán);所提方案確保碼字的最小碼重盡可能最大化.

2)仿真結(jié)果表明,該碼字具有優(yōu)于IEEE 802.16e標(biāo)準(zhǔn)中等長(zhǎng)碼的BER性能,以及和IEEE 802.11n中碼字相近的誤碼率性能;所構(gòu)造的QC-LDPC碼具有線性編碼復(fù)雜度,且存儲(chǔ)校驗(yàn)矩陣所占的硬件存儲(chǔ)空間較小,因而實(shí)際應(yīng)用更加可行.

References)

[1]Gallager R. Low-density parity-check codes[J].IEEETransactionsonInformationTheory, 1962, 8(1): 21-28. DOI:10.1109/tit.1962.1057683.

[2]Richardson T J. LDPC design for high parallelism, low error floor, and simple encoding:US, US9306601[P]. 2016-04-05.

[3]Ganesan K, Grover P, Rabaey J, et al. On the total power capacity of regular-LDPC codes with iterative message-passing decoders[J].IEEEJournalonSelectedAreasinCommunications, 2016, 34(2): 375-396. DOI:10.1109/jsac.2015.2504276.

[4]Song L, Huang Q, Wang Z, et al. Two enhanced reliability-based decoding algorithms for nonbinary LDPC codes[J].IEEETransactionsonCommunications, 2016, 64(2): 479-489. DOI:10.1109/tcomm.2015.2512582.

[5]Tasdighi A, Banihashemi A H, Sadeghi M R. Efficient search of girth-optimal QC-LDPC codes[J].IEEETransactionsonInformationTheory, 2016, 62(4): 1552-1564. DOI:10.1109/tit.2016.2523979.

[6]Tanner R M, Sridhara D, Sridharan A, et al. LDPC block and convolutional codes based on circulant matrices[J].IEEETransactionsonInformationTheory, 2004, 50(12): 2966-2984. DOI:10.1109/tit.2004.838370.

[7]林炳, 姜明, 趙春明. 基于二維優(yōu)化的QC-LDPC碼構(gòu)造方法[J]. 東南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2010, 40(1): 6-10. DOI:10.3969/j.issn.1001-0505.2010.01.002. Lin Bing, Jiang Ming, Zhao Chunming. Construction of QC-LDPC codes based on two-dimentional optimization[J].JournalofSoutheastUniversity(NaturalScienceEdition), 2010, 40(1): 6-10. DOI:10.3969/j.issn.1001-0505.2010.01.002.(in Chinese)

[8]Di C A, Proietti D, Telatar I E, et al. Finite-length analysis of low-density parity-check codes on the binary erasure channel[J].IEEETransactionsonInformationTheory, 2002(6): 1570-1579. DOI:10.1109/tit.2002.1003839.

[9]Tian T, Jones C, Villasenor J D, et al. Construction of irregular LDPC codes with low error floors[C]//Proceedingsof2003IEEEInternationalConferenceonCommunications. Anchorage, Alaska, USA, 2003: 3125-3129.

[10]馬克祥. LDPC碼快速及低錯(cuò)誤平層譯碼算法研究[D]. 西安: 西安電子科技大學(xué)通信工程學(xué)院, 2014.

QC-LDPC code design with low hardware storage and linear encoding

Kong Lingjun1, 2Jiang Ming1Zhao Chunming1

(1National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China)(2College of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China)

To solve the design problem of constructing quasi-cyclic low-density parity-check (QC-LDPC) codes of any length without small stopping sets or small girth, the relationship among the stopping set, the girth and the minimum weight based on the Tanner graph is investigated. The necessary and sufficient conditions of the QC-LDPC codes without small stopping sets or small girth are proposed. To further reduce the encoding complexity and maintain the structural characteristics, the backward iteration based QC-LDPC code with linear encoding complexity is proposed. The simulation results show that the error correction performance of the constructed QC-LDPC code is similar to that of the QC-LDPC code in IEEE 802.11n. And the designed code achieves a performance gain of 0.15 dB at the bit error rate of 10-6compared with the QC-LDPC code in IEEE 802.16e. Meanwhile, the proposed code only needs to store the shift factor and the order of the unit sub-matrix, inducing that the hardware storage resource is obviously smaller than those of the other two QC-LDPC codes.

low-density parity-check (QC-LDPC) code; quasi-cyclic (QC) code; stopping set; stopping distance; girth

10.3969/j.issn.1001-0505.2017.03.001

2016-11-10. 作者簡(jiǎn)介: 孔令軍(1982—),男,博士,副教授,ljkong@njupt.edu.cn.

中國(guó)博士后科學(xué)基金資助項(xiàng)目(2015M581698)、國(guó)家自然科學(xué)基金青年基金資助項(xiàng)目(61501250)、教育部留學(xué)回國(guó)人員科研啟動(dòng)基金資助項(xiàng)目(BJ215002)、江蘇省博士后科研資助計(jì)劃資助項(xiàng)目(1501037B)、江蘇省自然科學(xué)基金青年基金資助項(xiàng)目(SJ214029)、江蘇省高校自然科學(xué)研究面上項(xiàng)目資助項(xiàng)目(14KJB510021)、南京郵電大學(xué)引進(jìn)人才科研啟動(dòng)基金資助項(xiàng)目(NY214015).

孔令軍,姜明,趙春明.低存儲(chǔ)可線性編碼的QC-LDPC碼設(shè)計(jì)[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2017,47(3):421-425.

10.3969/j.issn.1001-0505.2017.03.001.

TN911.22

A

1001-0505(2017)03-0421-05

猜你喜歡
碼字校驗(yàn)復(fù)雜度
一種低復(fù)雜度的慣性/GNSS矢量深組合方法
放 下
數(shù)據(jù)鏈系統(tǒng)中軟擴(kuò)頻碼的優(yōu)選及應(yīng)用
放下
爐溫均勻性校驗(yàn)在鑄鍛企業(yè)的應(yīng)用
求圖上廣探樹的時(shí)間復(fù)雜度
結(jié)合抓包實(shí)例分析校驗(yàn)和的計(jì)算
分析校驗(yàn)和的錯(cuò)誤原因
某雷達(dá)導(dǎo)51 頭中心控制軟件圈復(fù)雜度分析與改進(jìn)
出口技術(shù)復(fù)雜度研究回顧與評(píng)述
长沙县| 广平县| 黄平县| 葵青区| 湾仔区| 名山县| 界首市| 秦安县| 万州区| 锦州市| 随州市| 汪清县| 布拖县| 辛集市| 公安县| 衡阳县| 永州市| 长顺县| 临夏市| 大埔区| 蒲城县| 上思县| 万年县| 霍邱县| 太仆寺旗| 贵港市| 廊坊市| 兴文县| 白山市| 西藏| 明溪县| 麦盖提县| 湖南省| 军事| 丹阳市| 德江县| 平陆县| 岳阳县| 泸西县| 沙湾县| 镇巴县|