一種基於完備循環差集的可快速編碼的Type‑IIQC‑LDPC碼構造方法與流程
2023-06-20 11:37:01
本發明屬於信號處理領域，涉及信道編碼，尤其是一種基於完備循環差集的可快速編碼的type-IIQC-LDPC碼構造方法。
背景技術：
：通信系統設計的目的在於能夠保證信息有效可靠地傳輸，但傳輸過程中存在噪聲等幹擾。信道編碼技術是通過在有效信息中添加少量的冗餘信息來發現並糾正傳輸過程中噪聲導致的誤碼，其本質是在有效性和可靠性之間找到合適的折中點。信道編碼技術歷經幾代的發展，現已確定了以低密度奇偶校驗(Low-DensityParity-paritycheck,LDPC)碼為主的技術路線。LDPC碼作為一種具有稀疏校驗矩陣的線性分組碼，當採用置信度傳播(BeliefPropagation,BP)算法迭代解碼時，其性能十分逼近Shannon限。準循環低密度奇偶校驗(Quasi-CyclicLow-DensityParity-paritycheck,QC-LDPC)碼是一種結構型LDPC碼，其校驗矩陣具有準循環特性，可由簡單的線性移位寄存器實現編碼，減少了所需存儲空間，降低了硬體實現的複雜度，已成為了編碼界的研究焦點。通常，QC-LDPC的校驗矩陣H是由循環子矩陣組成。當校驗矩陣H中僅包含循環置換矩陣(CirculantPermutationMatrices,CPM)或零矩陣(ZeroMatrices，ZM)這兩種形式的循環子矩陣時，對應的碼字為type-IQC-LDPC碼，目前大多數文獻所構造的QC-LDPC碼都是屬於type-IQC-LDPC碼。而type-IIQC-LDPC碼校驗矩陣H包括CMP、ZM和權重為2的循環矩陣(Weight-2CirculantMatrices,W2CM)，與type-IQC-LDPC碼相比，它具有更大的最小距離上界值，最小距離與碼糾錯性能直接相關，最小距離值越大，碼的抗幹擾性越好，檢錯糾錯能力也越強。經查閱文獻可知，在目前僅有的少數研究type-IIQC-LDPC碼的文獻中，其中有兩篇構造的type-IIQC-LDPC碼屬於規則碼，其校驗矩陣H中僅包含W2CM，更容易導致Tanner圖中短環的產生，且校驗矩陣H不是滿秩的；還有一篇構造的type-IIQC-LDPC碼的校驗矩陣H是滿秩的且其子矩陣包含ZM、CPM和W2CM三種形式，但除理論分析外並無仿真結果說明。因此，目前尚未存在對非規則type-IIQC-LDPC碼的確定性構造的研究。除此之外，雖然上述type-IIQC-LDPC碼一定程度上降低了存儲複雜度，但是編碼複雜度過高的問題還是沒有得到有效解決。目前存在的type-IIQC-LDPC碼的編碼是將校驗矩陣H轉換成生成矩陣，利用生成矩陣進行編碼的過程，編碼複雜度與碼長的平方成正比，當碼長較長時，如此高的複雜度不容小覷。完備循環差集(CyclicDifferenceSets,CDS)是組合數學中一類十分重要的設計理論，其主要性質是集合中任意兩個不同元素之差也是各不相同的，將完備CDS引入到type-IIQC-LDPC碼的構造中可有效避免四環的產生。因此，本發明利用完備CDS，提出了一種可快速編碼的非規則type-IIQC-LDPC碼構造方法。該方法不僅提升了碼字的糾錯性能，且有效地減低了編碼複雜度。技術實現要素：有鑑於此，本發明的目的在於提供一種基於完備循環差集的可快速編碼的type-IIQC-LDPC碼構造方法，通過對碼字的權重矩陣和移位矩陣的巧妙設計，從而達到提升糾錯性能、減小編碼複雜度的目的，為達到上述目的，本發明提供如下技術方案：一種基於完備循環差集的可快速編碼的type-IIQC-LDPC碼構造方法，包括：1.設計一個3×L的權重矩陣Awt，Awt中的元素aij(0≤i≤2,0≤j≤J-1,aij∈{0,1,2})表示type-IIQC-LDPC碼的校驗矩陣H中循環子矩陣對應的權重。設計的權重矩陣Awt如下式所示。式(1)中的Awt虛線左半部分第一列的元素為(x2+y2)mod3，餘下每一列的元素為[(x2+y2)+w1/w2/w3]mod3，x與y為對應元素所在位置的行列坐標值。第一行對應的w1在第3ib(2≤ib≤kb)列取值為2，其餘列取值為0；第二行對應的w2取值為1；第三行對應的w3取值為1，保證了Awt中組成矩行的四個位置上元素不都為1。Awt虛線右半部分具有準雙對角線的形式，保證了Awt是滿秩的，那麼這個權重矩陣對應的校驗矩陣H也具有準雙對角線的形式且滿秩的，即rank(H)＝pJ，該校驗矩陣H的零空間定義的碼字C的碼率為R＝1-J/L。2.根據(1)式給出的權重矩陣Awt來確定移位矩陣S(H)的每個條目的元素的個數，Awt中非零元素的值對應於S(H)中相應條目的元素的個數，Awt中0元素的值對應於S(H)中元素為∞。S(H)如式(2)所示。其中，L≥3，對任意0≤j≤2,0≤l≤L-1,i∈{1,2},表示單位矩陣的每行向右循環移位的次數。3.將S(H)中除∞外僅包括一個元素的條目的元素值確定為0，即對應H中權重為1的循環子矩陣均確定為單位矩陣。由於Awt中組成矩陣的四個位置上元素不都為1，那麼單位矩陣在H中不會參與構成四環；根據完備CDS的性質，令p＝v＝k2-k+1，將完備CDS中的元素按升序方式從左到右從上到下分配在根據Awt構造的S(H)中除0元素和∞外的條目中。然後將移位矩陣S(H)擴展為校驗矩陣H，即0元素用單位矩陣去替換，∞用零矩陣去替換，其餘元素用對應的CPM去替換，得到最終的校驗矩陣H，若(3)式所示。當時，I(∞)代表一個p×p零矩陣0，當時，I(0)是一個p×p單位矩陣I，當時，表示一個p×p的單位矩陣每行向右移位所得的CPM。根據式(1)構造的權重矩陣可知，校驗矩陣H包括下面三種形式：權重為0的ZM、權重為1的CPM和權重為2的循環矩陣其中4.快速編碼迭代算法本發明所構造的大小為3p×(kb+3)p的校驗矩陣H可分為兩部分，即H＝[H1H2]，其中大小為3p×kbp的H1為信息子矩陣，大小為3p×3p的H2為校驗子矩陣，H2為準雙對角線結構的形式，是實現快速編碼的基礎部分。因此本發明構造的碼字可基於校驗矩陣H利用編碼原理等式HcT＝0直接進行快速編碼後得到碼字c。假設將長度為(kb+3)p的碼向量分成(kb+3)段，每段長度為p，表示為記為信息碼向量，p＝[p1Tp2Tp3T]為校驗碼向量，其中si＝[s((i-1)p+1)s((i-1)p+2)…s(iz)]T，i＝1,2,…,kb(5)pi＝[p((i-1)p+1)p((i-1)p+2)…p(ip)]T，i＝1,2,3(6)將各個si和pi縱向拼接起來可得根據編碼算法的原理等式HcT＝0可得將(8)式用線性方程組的形式表示其中，X1＝Φ1+Φ2，X2＝Φ3+Φ4。令可將(9)式化簡為由消元法可得校驗碼向量p1＝(X1+X2+I)-1·(q1+q2+q3)(11)p2＝q1+X1·p1(12)p3＝q3+p1(13)式(11)～式(13)的線性方程組就是本發明提出的type-IIQC-LDPC碼的快速迭代編碼算法，當已知信息碼向量和校驗矩陣H時，便可由式(11)～式(13)得到校驗向量p＝[p1Tp2Tp3T]，最終得到碼向量本發明的有益效果在於：構造的type-IIQC-LDPC碼的校驗矩陣具有準雙對角線結構，省去了將校驗矩陣轉H換成生成矩陣的過程，可利用H直接進行快速編碼，本發明也給出了type-IIQC-LDPC碼的具體快速編碼算法，該算法綜合了稀疏矩陣和迭代兩方面的優勢，因此編碼複雜度僅與碼長呈線性比例關係，有效地降低了編碼複雜度。就存儲方面而言，本發明構造的type-IIQC-LDPC碼採用的是準循環構造法，校驗矩陣H可由移位矩陣S(H)確定，所以只需對移位矩陣S(H)中的元素進行儲存，存儲量非常小。就糾錯性能而言，W2CM的引入可使碼字之間的最小距離具有更大的值，增大了碼的糾錯能力；Tanner圖中無四環，解碼時能快速收斂，且構造的是一種非規則type-IIQC-LDPC碼，在同等條件下，本發明基於完備CDS構造的非規則type-IICDSQC-LDPC碼的糾錯性能優於基於完備CDS造的規則type-IICDSQC-LDPC碼及基於等差數列(ArithmeticProgressionSequence,APS)構造的type-IAPS-QC-LDPC碼。綜上所述，本發明所提供的一種基於完備循環差集的可快速編碼的非規則type-IIQC-LDPC碼構造方法比相關傳統方法在淨編碼增益、編碼複雜度及存儲所需空間等方面均有優勢，能更好地滿足通信系統的要求。附圖說明為了使本發明的目的、技術方案和有益效果更加清楚，本發明提供如下附圖進行說明：圖1為本發明方法的技術路線圖；圖2為實施例1所構造的碼率為0.5的非規則type-IICDSQC-LDPC(1098,549)碼與其他碼的性能比較圖；圖3為實施例2所構造的碼率為0.67的非規則type-IICDSQC-LDPC(4977,3318)碼與其他碼的性能比較圖。具體實施方式下面將結合附圖，對本發明的優選實施例進行詳細的描述。1.結合附圖1說明，對於一個v階的加法群Zv＝{0,1,2…,v-1}，D＝{d1,d2,...,dk}為Zv的含有k個元素的子集，Zv中的每個非零元素在(di-dj)modv運算的結果中恰好出現λ次，則D稱作Zv的一個(v,k,λ)循環差集。由定義可得循環差集的參數滿足：λ＝k(k-1)/(v-1)。當λ＝1時，v＝k2-k+1，稱這樣的循環差集為完備循環差集，完備循環差集D中任意兩個元素di，dj的模v差集(di-dj)modv運算結果各不相同。對於任意素數冪q＝pm，p為一個素數，m為任意的正整數，v＝q2+q+1，對於加法群存在一個(q2+q+1,q+1,1)完備循環差集。表1中列出了部分完備循環差集。表1部分(v,k,1)完備循環差集(4≤k≤30)2.結合附圖1說明，設計一個3×L的權重矩陣Awt，Awt中的元素aij(0≤i≤2,0≤j≤J-1,aij∈{0,1,2})表示type-IIQC-LDPC碼的校驗矩陣H中循環子矩陣對應的權重。設計的權重矩陣Awt如下式所示。式(1)中的Awt虛線左半部分第一列的元素為(x2+y2)mod3，餘下每一列的元素為[(x2+y2)+w1/w2/w3]mod3，x與y為對應元素所在位置的行列坐標值。第一行對應的w1在第3ib(2≤ib≤kb)列取值為2，其餘列取值為0；第二行對應的w2取值為1；第三行對應的w3取值為1，保證了Awt中組成矩行的四個位置上元素不都為1。Awt虛線右半部分具有準雙對角線的形式，保證了Awt是滿秩的，那麼這個權重矩陣對應的校驗矩陣H也具有準雙對角線的形式且滿秩的，即rank(H)＝pJ，該校驗矩陣H的零空間定義的碼字C的碼率為R＝1-J/L。3.結合附圖1說明，根據(1)式給出的權重矩陣Awt來確定移位矩陣S(H)的每個條目的元素的個數，Awt中非零元素的值對應於S(H)中相應條目的元素的個數，Awt中0元素的值對應於S(H)中元素為∞。S(H)如式(2)所示。其中，L≥3，對任意0≤j≤2,0≤l≤L-1,i∈{1,2},表示單位矩陣的每行向右循環移位的次數。4.結合附圖1說明，將S(H)中除∞外僅包括一個元素的條目的元素值確定為0，即對應H中權重為1的循環子矩陣均確定為單位矩陣。由於Awt中組成矩陣的四個位置上元素不都為1，那麼單位矩陣在H中不會參與構成四環；根據完備CDS的性質，令p＝v＝k2-k+1，將完備CDS中的元素按升序方式從左到右從上到下分配在根據Awt構造的S(H)中除0元素和∞外的條目中。然後將移位矩陣S(H)擴展為校驗矩陣H，即0元素用單位矩陣去替換，∞用零矩陣去替換，其餘元素用對應的CPM去替換，得到最終的校驗矩陣H，若(3)式所示。當時，I(∞)代表一個p×p零矩陣0，當時，I(0)是一個p×p單位矩陣I，當時，表示一個p×p的單位矩陣每行向右移位所得的CPM。根據式(1)構造的權重矩陣可知，校驗矩陣H包括下面三種形式：權重為0的ZM、權重為1的CPM和權重為2的循環矩陣其中5.快速編碼迭代算法結合附圖1說明，本發明所構造的大小為3p×(kb+3)p的校驗矩陣H可分為兩部分，即H＝[H1H2]，其中大小為3p×kbp的H1為信息子矩陣，大小為3p×3p的H2為校驗子矩陣，H2為準雙對角線結構的形式，是實現快速編碼的基礎部分。因此本發明構造的碼字可基於校驗矩陣H利用編碼原理等式HcT＝0直接進行快速編碼後得到碼字c。假設將長度為(kb+3)p的碼向量分成(kb+3)段，每段長度為p，表示為記為信息碼向量，p＝[p1Tp2Tp3T]為校驗碼向量，其中si＝[s((i-1)p+1)s((i-1)p+2)…s(iz)]T，i＝1,2,...,kb(5)pi＝[p((i-1)p+1)p((i-1)p+2)…p(ip)]T，i＝1,2,3(6)將各個si和pi縱向拼接起來可得根據編碼算法的原理等式HcT＝0可得將(8)式用線性方程組的形式表示其中，X1＝Φ1+Φ2，X2＝Φ3+Φ4。令可將(9)式化簡為由消元法可得校驗碼向量p1＝(X1+X2+I)-1·(q1+q2+q3)(11)p2＝q1+X1·p1(12)p3＝q3+p1(13)式(11)～式(13)的線性方程組就是本發明提出的type-IIQC-LDPC碼的快速迭代編碼算法，當已知信息碼向量和校驗矩陣H時，便可由式(11)～式(13)得到校驗向量p＝[p1Tp2Tp3T]，最終得到碼向量6.編碼複雜度分析編碼複雜度分析主要是對編碼過程的運算量，運算複雜度和編碼所需存儲的參數的分析。運算量可定義為運算過程中乘法和加法的次數，運算複雜度可定義為碼長的變化所引起的運算量的變化之間的關係。由於本發明提出的type-IIQC-LDPC碼的直接快速迭代編碼算法中的各個子矩陣都是稀疏矩陣，所以按照稀疏矩陣的方式來計算，其運算量能被很大程度地減小。本發明的快速編碼算法的運算量精確值如表2所示。表2本發明構造的type-IIQC-LDPC碼的快速編碼算法的運算量乘法次數加法次數p13RN/p3Rn+2p2-pp2RN+pRNp3RNRN顯然，從表2可以看出，計算校驗碼向量p的運算複雜度與碼長成線性關係，即運算複雜度為O(N)，這是因為該LDPC編碼算法綜合了稀疏矩陣和迭代兩方面的優勢。就參數存儲方面而言，本發明構造的type-IIQC-LDPC碼採用的是準循環構造法，校驗矩陣H可由移位矩陣S(H)確定，所以只需對移位矩陣S(H)中的元素進行儲存，存儲量非常小。通過對本發明提出的編碼算法的運算量，運算複雜度和編碼所需存儲空間的綜合分析，可知該算法有效地降低了編碼複雜度。7.誤比特性能分析下面將給出兩個實施例來說明並分析本發明所構造的非規則type-IICDS-QC-LDPC碼的性能，仿真環境採用的是加性白噪聲高斯(AWGN)信道下的二進位相移鍵控(BPSK)調製，置信度傳播(BP)迭代解碼，最大迭代次數取50次。並與基於完備CDS構造的規則type-IIQC-LDPC碼以及基於等差數列(ArithmeticProgressionSequence,APS)構造的規則type-IQC-LDPC碼進行性能比較。實施例1：取(183,14,1)-CDSD＝{1,2,4,25,42,53,58,67,71,97,103,150,165,177}，令p＝v＝183，kb＝3，根據式(1)可得到一個3×6的權重矩陣Awt如式(14)所示。根據(183,14,1)-CDS和(14)式的權重矩陣Awt可得移位矩陣S(H)，S(H)擴展後的校驗矩陣H的零空間可定義碼率為0.5的非規則type-IICDSQC-LDPC(1098,549)碼，糾錯性能仿真結果和數據分別如圖2和表3所示。從圖2和表3可以看出，當誤比特率(BitErrorRate,BER)為10-6時，本發明所構造的非規則type-IICDSQC-LDPC(1098,549)碼的淨編碼增益(NetCodingGain,NCG)為7.82dB，且在同等條件下與規則type-IICDSQC-LDPC(1092,546)碼和type-IAPS-QC-LDPC(1096,548)碼相比，NCG分別提升了0.42dB和0.68dB。另外，本發明所構造的非規則type-IICDSQC-LDPC(1098,549)碼在信噪比為2.8dB時，BER可達到10-7，說明解碼時具有較好的收斂特性，且在BER低至10-7無錯誤平層現象。表3實施例1中構造的碼型與其他碼型的性能比較碼型碼長信息位碼率BER＝10-6的NCG非規則type-IICDSQC-LDPC碼10985490.57.82dB規則type-IICDSQC-LDPC碼10925460.57.40dB規則type-IAPS-QC-LDPC碼10965480.57.14dB實施例2：取(553,24,1)-CDSD＝{1,2,4,18,37,43,65,94,132,150,162,194,205,215,220,228,265,274,314,401,449,453,473,480},令p＝v＝553，kb＝6，根據式(1)可得到一個3×9的權重矩陣Awt如式(15)所示。根據(553,24,1)-CDS和(15)式的權重矩陣Awt可得移位矩陣S(H)，最終擴展後的校驗矩陣H的零空間可定義碼率為0.67的type-IICDSQC-LDPC(4977,3318)碼，糾錯性能仿真結果如圖3所示。從圖3可以看出，當BER為10-6時，本發明所構造的非規則type-IICDSQC-LDPC(4977,3318)碼的NCG為8.18dB，且在同等條件下與規則type-IICDSQC-LDPC(5226,3486)碼相比具有0.38dB左右的NCG改善，比type-IAPS-QC-LDPC(4980,3320)碼NCG提高了0.28dB左右，且當BER接近10-7時無錯誤平層現象。表4實施例2中構造的碼型與其他碼型的性能比較碼型碼長信息位碼率BER＝10-6的NCG非規則type-IICDSQC-LDPC碼497733180.678.18dB規則type-IICDSQC-LDPC碼498033200.677.80dB規則type-IAPS-QC-LDPC碼522634860.677.90dB最後說明的是，以上優選實施例僅用以說明本發明的技術方案而非限制，儘管通過上述優選實施例已經對本發明進行了詳細的描述，但本領域技術人員應當理解，可以在形式上和細節上對其作出各種各樣的改變，而不偏離本發明權利要求書所限定的範圍。當前第1頁1 2 3