基于可變擬陣搜索算法構造碼率為1/p的二進制系統準循環碼

張水平 林平平 巫光福 江林偉

?

基于可變擬陣搜索算法構造碼率為1/的二進制系統準循環碼

張水平 林平平 巫光福*江林偉

(江西理工大學信息工程學院 贛州 341000)

該文針對擬陣搜索算法復雜度高以及局部擬陣搜索算法無法搜索到全部最優碼的問題，通過研究擬陣搜索算法，提出可變擬陣搜索算法，并用于搜索準循環碼。該算法通過減少重復搜索從而降低運算復雜度；基于該算法構造碼率為1/的二進制系統準循環碼，隨著整數的變化，生成矩陣減少或者增加一個循環矩陣，產生碼率均為1/的最優碼。通過實驗得到兩個最小距離比現有最優碼更大的準循環碼，表明算法的可行性和優越性。

擬陣理論；準循環碼；最小距離；可變擬陣搜索算法

1 引言

1967年，Townsend和Weldon[1]發現準循環碼，二進制系統準循環碼由于循環性、電路實現簡單、良好的代數結構和糾錯能力，受到廣大研究學者的關注，并取得許多研究成果。提出計算機組合優化搜索算法[2]、局部搜索算法[3]、等差數列算法[4]搜索最優碼，許多性能良好的準循環碼被收集在數據庫[5]。文獻[6,7]研究準循環碼在無線傳感器網絡和淺海水聲信道中的應用，文獻[8]對其譯碼器電路實現進行相關研究，使得準循環碼在實際環境中得到廣泛應用。

擬陣理論與編碼的結合，指明準循環碼研究的新方向。1935年，Whitney[9]提出擬陣理論。之后，文獻[10]第1次把擬陣與編碼結合起來，推導出著名的MacWilliams等式。1997年，文獻[11]得到更一般化的漢明重量分布的MacWilliams等式。2008年，文獻[12]系統地把擬陣引入編碼中，指出二進制碼可以對應于二進制的向量擬陣；反之，二進制向量擬陣也對應于二進制碼。在此基礎上，文獻[13]基于擬陣理論構造一種短的高碼率LDPC碼，表明擬陣理論用于編碼領域的可行性和高效性。最近，文獻[14]基于擬陣理論，根據生成矩陣和最小距離的聯系，發現構造二進制線性碼的最小距離定理，提出擬陣搜索算法，構造一類好的二進制系統線性分組碼。文獻[15]進一步探究生成矩陣和最小距離的聯系，發現構造二進制準循環碼的最小距離定理，提出擬陣搜索算法，構造碼率為1/的二進制系統準循環碼。擬陣搜索算法可以降低運算的復雜度，能搜索更大的最優碼，且屬于全局搜索，能夠保證最優碼。但只能構造14的二進制系統準循環碼，之后因運算量大無法繼續搜索。為了克服這種局限性，文獻[16]提出局部擬陣搜索算法，構造15的碼率為1/的二進制系統準循環碼，通過實驗得到20多個最優碼。該算法可以搜索15的準循環碼，但無法保證最優碼。基于擬陣理論構造二進制系統準循環碼，因運算量大產生的局限性，無法繼續搜索,更大的最優碼。

本文在擬陣搜索算法的基礎上，提出可變擬陣搜索算法。首先利用擬陣搜索算法構造高碼率最優碼，輸出所有生成矩陣到文本；然后對每個生產矩陣，遍歷二進制準循環碼的子集，組合低碼率的生產矩陣，結合二進制準循環碼的關系矩陣，通過擬陣搜索算法求得最小距離；最后比較所有最小距離，得到低碼率最優碼，將所有最優碼的生產矩陣輸出到文本。為了構造更低碼率的最優碼，重復上述步驟，直到滿足碼率即可。該算法既可搜索15的準循環碼，降低運算的復雜度，又可搜索最優碼。基于該算法構造=12～18,=20，二進制系統準循環碼，實驗結果得到兩個最小距離比現有最優碼更大的準循環碼，同時具有碼率可變性。

2 可變擬陣搜索算法

2.1算法分析

擬陣理論經過許多學者的研究，已經得到充分的發展和應用，擬陣理論已被廣泛用于組合優化、網絡理論和編碼理論，Oxley在文獻[17]中詳細闡述了擬陣的定義和定理。擬陣與編碼之間的聯系，最重要在于構造與二進制線性分組碼相對應的向量擬陣，通過向量擬陣的性質，得到生成矩陣與最小距離的聯系，降低求解最小距離的復雜度。文獻[14]提出擬陣聯接度的定義，通過建立一系列擬陣與單個集合的關系，重新定義新的擬陣獨立性，發現基于擬陣理論構造二進制線性分組碼的最小距離定理，提出擬陣搜索算法，基于該算法構造二進制線性分組碼。文獻[15]將擬陣理論用于構造準循環碼，將分解為子集的集合，每個子集中的元素個數作為向量的元素，，序號作為向量的元素。根據子集與擬陣的基的交集個數，得到二進制線性分組碼的關系矩陣。構造準循環碼，中元素個數必須等于，組成序號集合，根據得到準循環碼的關系矩陣，發現基于擬陣理論構造準循環碼的最小距離定理，提出構造準循環碼的擬陣搜索算法。該算法是一種全局遍歷算法，當,已知時，復雜度為,大于14時，由于擬陣數量過多，導致處理的數據量非常大，無法繼續進行搜索。文獻[16]通過隨機產生向量，利用擬陣理論構造準循環碼的最小距離定理，提出局部擬陣搜索算法，搜索大于14的最優碼。該算法搜索最優碼具有隨機性，無法保證最優碼。當搜索更大的最優碼時，處理的數據量亦非常大。

當搜索碼率為1/的二進制系統準循環碼，擬陣搜索算法和局部擬陣搜索算法需要對個循環矩陣進行遍歷，局部擬陣搜索算法非全局搜索，次數較少。搜索碼率為1/(+1)的二進制系統準循環碼時，生成矩陣和前個循環矩陣可能相同，且都能構造最優碼。如果基于生成矩陣，對第(+1)個循環矩陣遍歷，尋找最優碼，既能減少重復搜索，降低復雜度，還可得到最優碼。基于此思想，本文提出可變擬陣搜索算法，構造碼率為1/的二進制系統準循環碼，只對第個循環矩陣遍歷，前個循環矩陣為生成矩陣，生成矩陣能構造最優碼。可變擬陣搜索算法，上一步的輸出是下一步的輸入，對上一步的輸出進行搜索遍歷，求解最小距離，尋找最優碼，將結果輸出到文本。搜索最優碼是一個循序漸進過程，首先讀取所有最優碼的生成矩陣，利用擬陣搜索算法遍歷循環矩陣，組合生成矩陣，求解最小距離，尋找最優碼，然后將最優碼的生成矩陣輸出到文本。然后重復上述操作，直到滿足需要的值。

例如當= 14，已知碼率為1/5的二進制系統準循環最優碼的生成矩陣為，為了構造碼率為1/4的二進制系統準循環最優碼，只需把中的循環矩陣刪除，得。為了構造碼率為1/6的二進制系統準循環最優碼，只需在生成矩陣末端加上循環矩陣，得到，然后進行擬陣搜索算法遍歷，得到合適的循環矩陣。

2.2算法設計

首先，利用構造準循環碼的擬陣搜索算法，構造碼率為1/2的系統準循環碼。即先將分解成子集的集合，篩選滿足條件的，得到序號集合，求解與構造準循環碼有關的關系矩陣。根據基于擬陣理論構造準循環碼的最小距離定理，尋找最優碼，將最優碼的所有生成矩陣輸出到文本。假設生成矩陣,,,,，根據最小距離定理，,,，因為構造系統碼，所以。如果是生成矩陣的一部分，則,，否則。根據生成矩陣可知。為了得到最小距離，根據最小距離定理，求得。是一個的矩陣，是一個的矩陣，可知是一個的矩陣。與其它擬陣的聯系度為一個行向量，因此生成矩陣的對應中的某一行，同時決定中對應位置元素的取值，根據矩陣相乘原理，中的對應中的所有行向量相加得到。碼的最小距離，為了得到更大的，所以只要得到更小的，同時因為=，因此碼的最小距離

最后，根據碼率為1/的所有系統準循環碼的生成矩陣，按照構造碼率為1/3的準循環碼步驟，構造碼率為1/(+1)的系統準循環碼，直到滿足給定的參數。生成矩陣首先是碼率為1/(+1)的生成矩陣前個循環矩陣，然后遍歷所有的循環矩陣，得到最后一個循環矩陣，組成生成矩陣。根據最小距離定理求得最小距離，如果是滿足這一特性的最大值，則是碼率的生成矩陣前個循環矩陣，且和組成生成矩陣，否則不是。可變搜索算法是在生成矩陣的基礎上進行的擬陣搜索算法，構造準循環碼是一個循環漸進過程。

圖1 可變擬陣搜索算法流程圖

可變擬陣搜索算法，上一步的輸出是下一步的輸入，在前面基礎上進行的擬陣搜索，構造準循環碼是一個循序漸進過程。首先構造=2的滿足這一特性的準循環碼，得到與之相對應的所有生成矩陣，然后通過程序讀取這些生成矩陣，對每個生成矩陣進行擬陣搜索算法遍歷，構造= 3的準循環碼，尋找最大的最小距離。構造更大的準循環碼時，重復上述步驟，直到構造滿足要求的準循環碼。即首先構造高碼率的二進制系統循環碼，然后在上一步輸出的基礎上構造較低碼率的二進制系統準循環碼，追求碼率可變和最小距離的最大值。當已知,時，復雜度為，其中是碼率為1/(-1)的最優碼生成矩陣的個數，而是關系矩陣的行數，都是常數。擬陣搜索算法的復雜度為，局部搜索算法的復雜度為，顯然可變擬陣搜索算法的復雜度更低。該算法通過減少重復搜索降低復雜度，可以搜索更長的碼字，尋找最優碼。美中不足的是，當已知,時，前面高碼率最優碼的生成矩陣必須全部求解出來，利用已知高碼率最優碼搜索低碼率最優碼。擬陣搜索算法和局部擬陣搜索算法跟前面高碼率最優碼的生成矩陣沒有聯系，可以直接求解。

可變擬陣搜索算法步驟(如圖1所示)：

(1)給定兩個參數和，計算關系矩陣,,,。

(3)讀取碼率為1/的二進制系統準循環碼的所有生成矩陣，利用步驟(2)中的擬陣搜索算法思想計算最小距離，構造碼率為1/(+1)的最優系統準循環碼。

例如，當=4,=2時，,，即滿足的子集有,,，與準循環碼有關的關系矩陣：

首先構造碼率為1/2的二進制系統準循環最優碼，其結果唯一，生產矩陣為，最小距離=4。現在需要構造碼率為1/3的二進制系統準循環最優碼，只需在生成矩陣的末端加上循環矩陣，根據碼率可變擬陣搜索算法，循環矩陣有3種情況，我們對其進行擬陣搜索算法遍歷，找到最優碼。

通過碼率可變擬陣搜索算法，我們得到碼率為1/3的最優系統準循環碼生成矩陣為。當已知碼率為1/3的最優系統準循環碼的生成矩陣為，我們可知滿足這一特性的碼率為1/2的最優系統準循環碼的生成矩陣為，最小距離= 4。如果需要構造碼率為1/4的最優系統準循環碼，在生成矩陣的基礎上進行碼率可變擬陣搜索算法即可。

3 實驗結果

基于可變擬陣搜索碼算法，構造一類特殊碼率為1/的二進制系統準循環碼，具備碼率可變性，伴隨著的變化，生成矩陣減少或者增加一個循環矩陣，產生碼率均為1/的最優碼。本文所指得最優碼，是滿足這一特性的生成矩陣所能得到的最大的最小距離，并非廣義上的最優碼。通過對比文獻[16,19]和兩個數據庫[5,20]，得到最小距離見表1。其中，粗體的最小距離和現有最優準循環碼的最小距離相同，粗體加*號的最小距離比現有最優準循環碼的最小距離大, 即碼(182, 14, 77)和(340, 17, 146)。

表1 (kp, p)碼的最小距離

表2中列出碼率為1/20即=20的最優碼的生成矩陣代表，根據準循環碼的定義以及可變擬陣搜索算法，驗證碼率可變性，隨著的變化，生成矩陣增加或者減少一個循環矩陣，產生均為最優碼。例(240, 12, 108)碼生成矩陣=[1 379 29 311 749 137 447 989 1371 199 661 35 53 861 893 73 83 235 349 663]，根據準循環碼的定義，其中“1”表示12×12循環矩陣，首列為[1 0 0 0 0 0 0 0 0 0 0 0]T，其他數字同樣表示循環矩陣，首列為其二進制表示，因此是由20個循環矩陣組成的12×240生成矩陣。根據可變擬陣搜索算法，在碼率為1/的生成矩陣上增加一個循環矩陣，組成碼率為生成矩陣，兩個生成矩陣產生的均為最優碼。所以減少“663”表示的循環矩陣，由=[ 1 379 29 311 749 137 447 989 1371 199 661 35 53 861 893 73 83 235 349]亦產生最優碼。根據表1可知，它是(228, 12, 102)碼，增加一個循環矩陣亦是如此。從表2可知= 20的最優準循環碼的生成矩陣，亦知的最優準循環碼的生成矩陣，即=[1 379]，以此類推。根據= 20的最優碼生成矩陣可以構造= 21的最優碼，以此類推，得到更大的最優碼。

碼的重量分布定義為：設為上的線性碼，分別為中重量為0,1,,碼字的個數，為的重量分布，設,為變元，稱次齊次多項式為的重量計算子。根據二進制線性碼最小距離定義，等于非零碼字的最小重量，而表示線性碼重量為的碼字個數，因此根據最優碼的重量分布可以驗證表1的最小距離。查看(240, 12, 108)碼的重量分布可知，非零碼字的最小重量的數量為，因此最小距離= 108，符合表1列出的數值。根據表2中的生成矩陣代表亦可驗證表1的最小距離。二進制線性碼表示成向量形式為=，由于本文構造的是系統碼，而系統碼具有前位是信息位的特點，因此碼的重量為wt()=wt()+ wt()，其中是生成矩陣刪除單位矩陣后的矩陣。例，(240, 12, 108)碼的生成矩陣=[ 1 379 29 311 749 137 447 989 1371 199 661 35 53 861 893 73 83 235 349 663]，可以驗證=12,=2~20時準循環碼的最小距離。當= 12,= 2時，=[1 379],“1”,“379”表示12×12循環矩陣，首列為[1 0 0 0 0 0 0 0 0 0 0 0]T和[1 1 0 1 1 1 1 0 1 0 0 0]T，是“379”表示的循環矩陣。根據wt()=wt()+ wt()，求得重量計算子為，非零碼字的最小重量的數量為，因此= 8，符合表1中當= 12,= 2時的最小距離。

上標代表重量，下標代表數量，則由表2中生成矩陣生成的最優碼重量分布如下：

(1)新準循環碼(340,17,146)的重量分布為：

10, 272146, 867148, 1258150, 2091152, 2941154, 3723156, 4743158, 6171160, 7259162, 8942164, 10370166, 10421168, 11408170, 11526172, 10778174, 9367176, 8007178, 6290180, 4335182, 3485184, 2380186, 1530188, 1377190, 748192, 323194, 289196, 51198, 51200, 17202, 17204, 17208, 17210。

(2)新準循環碼(182,14,77)的重量分布為：

10, 28277, 25278, 39280, 67281, 43482, 63084, 135885, 65886, 82688, 182089, 88290, 84092, 87594, 74996, 124697, 63098, 518100, 574101, 294102, 98104, 280105, 70106, 28108, 70109, 14112, 14113, 1126。

4 結束語

本文主要研究如何利用擬陣理論構造二進制系統準循環碼，搜索,更大的最優碼。在基于擬陣理論的擬陣搜索算法和局部擬陣搜索算法的基礎上，提出可變的擬陣搜索算法。該算法可搜索15的準循環碼，減少重復搜索，降低運算復雜度，亦可得到最優碼。算法構造一類特殊的碼率為1/的二進制系統準循環碼，該碼有碼率可變性。實驗結果相比現有的最優準循環碼，大部分最小距離與現有最優碼的最小距離相差不大，多數與現有最優碼的最小距離相等，關鍵得到兩個準循環碼(182, 14, 77)和(340, 17, 146)比現有的準循環碼的最小距離更大。算法特點和實驗結果表明算法的可行性和優越性。實際通信系統中，在保證良好糾錯能力的前提下，采用本文所構造的編碼，生成矩陣減少或者增加循環矩陣即可滿足變換碼率的需求，操作方便，具有一定的應用價值。

表2碼率可變的最優碼

(n, k, d)生成矩陣代表 (240,12,108)1,379,29,311,749,137,447,989,1371,199,661,35,53,861,893,73,83,235,349,663. (260,13,114)1,427,1727,141,941,83,463,853,677,151,723,1023,159,1245,743,2037,3519,1277,1227,5. (280,14,123)1,471,2411,905,1335,931,1981,1013,1325,2455,1653,3387,2893,1993,997,1519,5983,443,2869,665. (300,15,131)1,6127,5789,271,1891,1177,2013,5287,3295,6879,189,6775,3903,823,1353,4015,525,671,2661,3367. (320,16,138)1,695,4007,4393,1711,4029,3273,1871,333,2029,1405,1689,3951,1215,15997,1783,11053,5939,743,4775. (340,17,146)1,1911,10815,179,77,3915,5861,24503,30701,11237,1599,91,1241,13469,1423,7053,4667,1733,5405,3215. (360,18,150)1,379,11595,1823,933,32205,1075,1403,5437,3687,57211,837,1205,3045,38367,211,1847,2671,2415,6099.

[1] TOWNSEND R and WELDON E. Self-orthogonal quasi-cyclic codes[J]., 1967, 13(2): 183-195.doi: 10.1109/TIT.1967. 1053974.

[2] CHEN Z. New results on binary quasi-cyclic codes[C]. Proceedings of IEEE International Symposium on Information Theory, Sorrento Italy, 2000: 151-154.

[3] HEIJNEN P, VAN T H, VERHOEFF T,. Some new binary quasi-cyclic codes[J]., 1998, 44(5): 1994-1996.doi: 10.1109/ 18.705580.

[4] 張軼, 達新宇, 蘇一棟. 利用等差數列構造大圍長準循環低密度奇偶校驗碼[J]. 電子與信息學報, 2015, 37(2): 394-398. doi: 10.11999/JEIT140538.

ZHANG Yi, DA Xinyu, and SU Yidong. Construction of quasi-cyclic low-density parity-check codes with a large girth based on arithmetic progression[J].&, 2015, 37(2): 394-398. doi: 10.11999/JEIT140538．

[5] CHEN Z. Database of quasi-twisted codes[OL]. http:// moodle. tec.hkr.se/~chen/research/codes, 2015.9.

[6] 郭銳, 劉春于, 張華, 等. 分簇無線傳感器網絡中根校驗全分集LDPC碼設計與能效分析[J]. 電子與信息學報, 2015, 37(7): 1580-1585. doi: 10.11999/JEIT141294.

GUO Rui, LIU Chunyu, ZHANG Hua,. Full diversity LDPC codes design and energy efficiency analysis for clustering wireless sensor networks[J].&, 2015, 37(7): 1580-1585. doi: 10.11999/JEIT141294.

[7] 陳震華, 許肖梅, 陳友淦, 等. 淺海水聲信道中原模圖LDPC碼的設計及性能分析[J]. 電子與信息學報, 2016, 38(1): 153-159. doi:10.11999/JEIT150415．

CHEN Zhenhua, XU Xiaomei, CHEN Yougan,. Design and analysis of Protograph-based LDPC codes in shallow water acoustic channels[J].&, 2016, 38(1): 153-159. doi: 10.11999/ JEIT150415.

[8] 蘭亞柱, 楊海鋼, 林郁. 動態自適應低密度奇偶校驗碼譯碼器的FPGA實現[J]. 電子與信息學報, 2015, 37(8): 1937-1943. doi: 10.11999/JEIT141609.

LAN Yazhu, YANG Haigang, and LIN Yu. Design of dynamic adaptive LDPC decoder based on FPGA[J].&, 2015, 37(8): 1937-1943. doi: 10.11999/JEIT141609.

[9] WHITNEY H. On the abstract properties of linear dependence[J]., 1935, 57(1): 509-533. doi: 10.1007/978-1-4612-2972-8_10.

[10] GREENE C. Weight enumeration and the geometry of linear codes[J]., 1976, 55(55): 119-128. doi: 10.1002/sapm1976552119.

[11] BARG A. The matroid of supports of a linear code[J].&, 1997, 8(2): 165-172. doi: 10.1007/s 002000050060.

[12] KASHYAP N. A decomposition theory for binary linear codes[J]., 2008, 54(7): 3035-3058.doi: 10.1109/TIT.2008.924700.

[13] 巫光福, 王琳. 一種短的高碼率LDPC碼設計[J].應用科學學報, 2013, 31(6): 559-563. doi: 10.3969/j.issn.0255-8297. 2013.06.002.

WU Guangfu and WANG Lin.Design of a short high rate LDPCcode[J]., 2013, 31(6): 559-563. doi: 10.3969/j.issn.0255-8297.2013.06.002.

[14] WU Guangfu, WANG Lin, and TRUONG T K. Use of matroid theory to construct a class of good binary linear codes[J]., 2014, 8(6): 893-898. doi: 10.1049/iet-com.2013.0671.

[15] WU Guangfu, Chang H C, WANG Lin,. Constructing rate 1/p systematic binary quasi-cyclic codes based on the matroid theory[J]., 2014, 71(1): 47-56. doi: 10.1007/s10623-012-9715-1.

[16] WU Guangfu, LI Yong, ZHANG Shuiping,. A random local matroid search algorithm to construct good rate 1/systematic binary Quasi-Cyclic codes[J]., 2015, 19(5): 699-702.doi: 10.1109/ LCOMM.2015.2401572.

[17] OXLEY J. Matroid Theory [M]. Oxford U K, Oxford University Press, 2011: 5-26．

[18] TILBURG H C A V. On quasi-cyclic codes with rate 1/[J]., 1978, 24(5): 628-629.doi: 10.1109/TIT.1978.1055929.

[19] GULLIVER T A and BHARGAVA V K. An updated table of rate 1/binaryuasi-yclic codes[J]., 1995, 8(5): 81-86. doi: 10.1016/0893-9659 (95)00071-W.

[20] GRASSL M. Tables of linear codes and quantum codes [OL]. http://www.codetables.de, 2015.9.

Construct the Systematic Binary Quasi-cyclic Codes with Rate 1/ased on Variable Matroid Search Algorithm

ZHANG Shuiping LIN Pingping WU Guangfu JIANG Linwei

(,,341000,)

Because the matroid search algorithm is very complicated and the local matroid search algorithm can not search all optimal codes, this paper proposesa variable matroid search algorithm to search the quasi-cyclic codes by researching matroid search algorithm. The algorithm reduces the computational complexity by reducing the repeated search. Based on this algorithm, the systematic binary quasi-cyclic codes of which the rate is 1/are constructed. With the change of integer, the optimal codes of rate 1/can be obtained by the generator matrix reducing or adding a loop matrix. Through experiments, two new codes of which the minimum distance is larger than the existing optimal codes are worked out, which indicate the feasibility and superiority of the algorithm.

Matroid theory; Quasi-cyclic codes; Minimum distance; Variable matroid search algorithm

TN911.22

A

1009-5896(2016)11-2916-06

10.11999/JEIT160074

2016-01-19；改回日期：2016-06-15；

2016-09-01

巫光福 wuguangfu@126.com

國家自然科學基金(11461031, 61562037)，江西省自然科學基金(20151BAB217016)

The National Natural Science Foundation of China (11461031, 61562037), The Natural Science Foundation of Jiangxi Province (20151BAB217016)

張水平： 男，1965年生，教授，研究方向為安全技術及工程、計算機應用技術、云計算.

林平平： 男，1991年生，碩士生，研究方向為信息論與編碼.

巫光福： 男，1977年生，講師，研究方向為信息論與編碼、密碼學、組合設計、概率統計.