基于可變擬陣搜索算法構(gòu)造碼率為1/p的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼

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

?

基于可變擬陣搜索算法構(gòu)造碼率為1/的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼

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

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

該文針對(duì)擬陣搜索算法復(fù)雜度高以及局部擬陣搜索算法無(wú)法搜索到全部最優(yōu)碼的問(wèn)題，通過(guò)研究擬陣搜索算法，提出可變擬陣搜索算法，并用于搜索準(zhǔn)循環(huán)碼。該算法通過(guò)減少重復(fù)搜索從而降低運(yùn)算復(fù)雜度；基于該算法構(gòu)造碼率為1/的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼，隨著整數(shù)的變化，生成矩陣減少或者增加一個(gè)循環(huán)矩陣，產(chǎn)生碼率均為1/的最優(yōu)碼。通過(guò)實(shí)驗(yàn)得到兩個(gè)最小距離比現(xiàn)有最優(yōu)碼更大的準(zhǔn)循環(huán)碼，表明算法的可行性和優(yōu)越性。

擬陣?yán)碚?；?zhǔn)循環(huán)碼；最小距離；可變擬陣搜索算法

1 引言

1967年，Townsend和Weldon[1]發(fā)現(xiàn)準(zhǔn)循環(huán)碼，二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼由于循環(huán)性、電路實(shí)現(xiàn)簡(jiǎn)單、良好的代數(shù)結(jié)構(gòu)和糾錯(cuò)能力，受到廣大研究學(xué)者的關(guān)注，并取得許多研究成果。提出計(jì)算機(jī)組合優(yōu)化搜索算法[2]、局部搜索算法[3]、等差數(shù)列算法[4]搜索最優(yōu)碼，許多性能良好的準(zhǔn)循環(huán)碼被收集在數(shù)據(jù)庫(kù)[5]。文獻(xiàn)[6,7]研究準(zhǔn)循環(huán)碼在無(wú)線傳感器網(wǎng)絡(luò)和淺海水聲信道中的應(yīng)用，文獻(xiàn)[8]對(duì)其譯碼器電路實(shí)現(xiàn)進(jìn)行相關(guān)研究，使得準(zhǔn)循環(huán)碼在實(shí)際環(huán)境中得到廣泛應(yīng)用。

擬陣?yán)碚撆c編碼的結(jié)合，指明準(zhǔn)循環(huán)碼研究的新方向。1935年，Whitney[9]提出擬陣?yán)碚?。之后，文獻(xiàn)[10]第1次把擬陣與編碼結(jié)合起來(lái)，推導(dǎo)出著名的MacWilliams等式。1997年，文獻(xiàn)[11]得到更一般化的漢明重量分布的MacWilliams等式。2008年，文獻(xiàn)[12]系統(tǒng)地把擬陣引入編碼中，指出二進(jìn)制碼可以對(duì)應(yīng)于二進(jìn)制的向量擬陣；反之，二進(jìn)制向量擬陣也對(duì)應(yīng)于二進(jìn)制碼。在此基礎(chǔ)上，文獻(xiàn)[13]基于擬陣?yán)碚摌?gòu)造一種短的高碼率LDPC碼，表明擬陣?yán)碚撚糜诰幋a領(lǐng)域的可行性和高效性。最近，文獻(xiàn)[14]基于擬陣?yán)碚?，根?jù)生成矩陣和最小距離的聯(lián)系，發(fā)現(xiàn)構(gòu)造二進(jìn)制線性碼的最小距離定理，提出擬陣搜索算法，構(gòu)造一類(lèi)好的二進(jìn)制系統(tǒng)線性分組碼。文獻(xiàn)[15]進(jìn)一步探究生成矩陣和最小距離的聯(lián)系，發(fā)現(xiàn)構(gòu)造二進(jìn)制準(zhǔn)循環(huán)碼的最小距離定理，提出擬陣搜索算法，構(gòu)造碼率為1/的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼。擬陣搜索算法可以降低運(yùn)算的復(fù)雜度，能搜索更大的最優(yōu)碼，且屬于全局搜索，能夠保證最優(yōu)碼。但只能構(gòu)造14的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼，之后因運(yùn)算量大無(wú)法繼續(xù)搜索。為了克服這種局限性，文獻(xiàn)[16]提出局部擬陣搜索算法，構(gòu)造15的碼率為1/的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼，通過(guò)實(shí)驗(yàn)得到20多個(gè)最優(yōu)碼。該算法可以搜索15的準(zhǔn)循環(huán)碼，但無(wú)法保證最優(yōu)碼?；跀M陣?yán)碚摌?gòu)造二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼，因運(yùn)算量大產(chǎn)生的局限性，無(wú)法繼續(xù)搜索,更大的最優(yōu)碼。

本文在擬陣搜索算法的基礎(chǔ)上，提出可變擬陣搜索算法。首先利用擬陣搜索算法構(gòu)造高碼率最優(yōu)碼，輸出所有生成矩陣到文本；然后對(duì)每個(gè)生產(chǎn)矩陣，遍歷二進(jìn)制準(zhǔn)循環(huán)碼的子集，組合低碼率的生產(chǎn)矩陣，結(jié)合二進(jìn)制準(zhǔn)循環(huán)碼的關(guān)系矩陣，通過(guò)擬陣搜索算法求得最小距離；最后比較所有最小距離，得到低碼率最優(yōu)碼，將所有最優(yōu)碼的生產(chǎn)矩陣輸出到文本。為了構(gòu)造更低碼率的最優(yōu)碼，重復(fù)上述步驟，直到滿(mǎn)足碼率即可。該算法既可搜索15的準(zhǔn)循環(huán)碼，降低運(yùn)算的復(fù)雜度，又可搜索最優(yōu)碼?；谠撍惴?gòu)造=12～18,=20，二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼，實(shí)驗(yàn)結(jié)果得到兩個(gè)最小距離比現(xiàn)有最優(yōu)碼更大的準(zhǔn)循環(huán)碼，同時(shí)具有碼率可變性。

2 可變擬陣搜索算法

2.1算法分析

擬陣?yán)碚摻?jīng)過(guò)許多學(xué)者的研究，已經(jīng)得到充分的發(fā)展和應(yīng)用，擬陣?yán)碚撘驯粡V泛用于組合優(yōu)化、網(wǎng)絡(luò)理論和編碼理論，Oxley在文獻(xiàn)[17]中詳細(xì)闡述了擬陣的定義和定理。擬陣與編碼之間的聯(lián)系，最重要在于構(gòu)造與二進(jìn)制線性分組碼相對(duì)應(yīng)的向量擬陣，通過(guò)向量擬陣的性質(zhì)，得到生成矩陣與最小距離的聯(lián)系，降低求解最小距離的復(fù)雜度。文獻(xiàn)[14]提出擬陣聯(lián)接度的定義，通過(guò)建立一系列擬陣與單個(gè)集合的關(guān)系，重新定義新的擬陣獨(dú)立性，發(fā)現(xiàn)基于擬陣?yán)碚摌?gòu)造二進(jìn)制線性分組碼的最小距離定理，提出擬陣搜索算法，基于該算法構(gòu)造二進(jìn)制線性分組碼。文獻(xiàn)[15]將擬陣?yán)碚撚糜跇?gòu)造準(zhǔn)循環(huán)碼，將分解為子集的集合，每個(gè)子集中的元素個(gè)數(shù)作為向量的元素，，序號(hào)作為向量的元素。根據(jù)子集與擬陣的基的交集個(gè)數(shù)，得到二進(jìn)制線性分組碼的關(guān)系矩陣。構(gòu)造準(zhǔn)循環(huán)碼，中元素個(gè)數(shù)必須等于，組成序號(hào)集合，根據(jù)得到準(zhǔn)循環(huán)碼的關(guān)系矩陣，發(fā)現(xiàn)基于擬陣?yán)碚摌?gòu)造準(zhǔn)循環(huán)碼的最小距離定理，提出構(gòu)造準(zhǔn)循環(huán)碼的擬陣搜索算法。該算法是一種全局遍歷算法，當(dāng),已知時(shí)，復(fù)雜度為,大于14時(shí)，由于擬陣數(shù)量過(guò)多，導(dǎo)致處理的數(shù)據(jù)量非常大，無(wú)法繼續(xù)進(jìn)行搜索。文獻(xiàn)[16]通過(guò)隨機(jī)產(chǎn)生向量，利用擬陣?yán)碚摌?gòu)造準(zhǔn)循環(huán)碼的最小距離定理，提出局部擬陣搜索算法，搜索大于14的最優(yōu)碼。該算法搜索最優(yōu)碼具有隨機(jī)性，無(wú)法保證最優(yōu)碼。當(dāng)搜索更大的最優(yōu)碼時(shí)，處理的數(shù)據(jù)量亦非常大。

當(dāng)搜索碼率為1/的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼，擬陣搜索算法和局部擬陣搜索算法需要對(duì)個(gè)循環(huán)矩陣進(jìn)行遍歷，局部擬陣搜索算法非全局搜索，次數(shù)較少。搜索碼率為1/(+1)的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼時(shí)，生成矩陣和前個(gè)循環(huán)矩陣可能相同，且都能構(gòu)造最優(yōu)碼。如果基于生成矩陣，對(duì)第(+1)個(gè)循環(huán)矩陣遍歷，尋找最優(yōu)碼，既能減少重復(fù)搜索，降低復(fù)雜度，還可得到最優(yōu)碼?；诖怂枷耄疚奶岢隹勺償M陣搜索算法，構(gòu)造碼率為1/的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼，只對(duì)第個(gè)循環(huán)矩陣遍歷，前個(gè)循環(huán)矩陣為生成矩陣，生成矩陣能構(gòu)造最優(yōu)碼?？勺償M陣搜索算法，上一步的輸出是下一步的輸入，對(duì)上一步的輸出進(jìn)行搜索遍歷，求解最小距離，尋找最優(yōu)碼，將結(jié)果輸出到文本。搜索最優(yōu)碼是一個(gè)循序漸進(jìn)過(guò)程，首先讀取所有最優(yōu)碼的生成矩陣，利用擬陣搜索算法遍歷循環(huán)矩陣，組合生成矩陣，求解最小距離，尋找最優(yōu)碼，然后將最優(yōu)碼的生成矩陣輸出到文本。然后重復(fù)上述操作，直到滿(mǎn)足需要的值。

例如當(dāng)= 14，已知碼率為1/5的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)最優(yōu)碼的生成矩陣為，為了構(gòu)造碼率為1/4的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)最優(yōu)碼，只需把中的循環(huán)矩陣刪除，得。為了構(gòu)造碼率為1/6的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)最優(yōu)碼，只需在生成矩陣末端加上循環(huán)矩陣，得到，然后進(jìn)行擬陣搜索算法遍歷，得到合適的循環(huán)矩陣。

2.2算法設(shè)計(jì)

首先，利用構(gòu)造準(zhǔn)循環(huán)碼的擬陣搜索算法，構(gòu)造碼率為1/2的系統(tǒng)準(zhǔn)循環(huán)碼。即先將分解成子集的集合，篩選滿(mǎn)足條件的，得到序號(hào)集合，求解與構(gòu)造準(zhǔn)循環(huán)碼有關(guān)的關(guān)系矩陣。根據(jù)基于擬陣?yán)碚摌?gòu)造準(zhǔn)循環(huán)碼的最小距離定理，尋找最優(yōu)碼，將最優(yōu)碼的所有生成矩陣輸出到文本。假設(shè)生成矩陣,,,,，根據(jù)最小距離定理，,,，因?yàn)闃?gòu)造系統(tǒng)碼，所以。如果是生成矩陣的一部分，則,，否則。根據(jù)生成矩陣可知。為了得到最小距離，根據(jù)最小距離定理，求得。是一個(gè)的矩陣，是一個(gè)的矩陣，可知是一個(gè)的矩陣。與其它擬陣的聯(lián)系度為一個(gè)行向量，因此生成矩陣的對(duì)應(yīng)中的某一行，同時(shí)決定中對(duì)應(yīng)位置元素的取值，根據(jù)矩陣相乘原理，中的對(duì)應(yīng)中的所有行向量相加得到。碼的最小距離，為了得到更大的，所以只要得到更小的，同時(shí)因?yàn)?，因此碼的最小距離

最后，根據(jù)碼率為1/的所有系統(tǒng)準(zhǔn)循環(huán)碼的生成矩陣，按照構(gòu)造碼率為1/3的準(zhǔn)循環(huán)碼步驟，構(gòu)造碼率為1/(+1)的系統(tǒng)準(zhǔn)循環(huán)碼，直到滿(mǎn)足給定的參數(shù)。生成矩陣首先是碼率為1/(+1)的生成矩陣前個(gè)循環(huán)矩陣，然后遍歷所有的循環(huán)矩陣，得到最后一個(gè)循環(huán)矩陣，組成生成矩陣。根據(jù)最小距離定理求得最小距離，如果是滿(mǎn)足這一特性的最大值，則是碼率的生成矩陣前個(gè)循環(huán)矩陣，且和組成生成矩陣，否則不是?？勺兯阉魉惴ㄊ窃谏删仃嚨幕A(chǔ)上進(jìn)行的擬陣搜索算法，構(gòu)造準(zhǔn)循環(huán)碼是一個(gè)循環(huán)漸進(jìn)過(guò)程。

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

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

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

(1)給定兩個(gè)參數(shù)和，計(jì)算關(guān)系矩陣,,,。

(3)讀取碼率為1/的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼的所有生成矩陣，利用步驟(2)中的擬陣搜索算法思想計(jì)算最小距離，構(gòu)造碼率為1/(+1)的最優(yōu)系統(tǒng)準(zhǔn)循環(huán)碼。

例如，當(dāng)=4,=2時(shí)，,，即滿(mǎn)足的子集有,,，與準(zhǔn)循環(huán)碼有關(guān)的關(guān)系矩陣：

首先構(gòu)造碼率為1/2的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)最優(yōu)碼，其結(jié)果唯一，生產(chǎn)矩陣為，最小距離=4?，F(xiàn)在需要構(gòu)造碼率為1/3的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)最優(yōu)碼，只需在生成矩陣的末端加上循環(huán)矩陣，根據(jù)碼率可變擬陣搜索算法，循環(huán)矩陣有3種情況，我們對(duì)其進(jìn)行擬陣搜索算法遍歷，找到最優(yōu)碼。

通過(guò)碼率可變擬陣搜索算法，我們得到碼率為1/3的最優(yōu)系統(tǒng)準(zhǔn)循環(huán)碼生成矩陣為。當(dāng)已知碼率為1/3的最優(yōu)系統(tǒng)準(zhǔn)循環(huán)碼的生成矩陣為，我們可知滿(mǎn)足這一特性的碼率為1/2的最優(yōu)系統(tǒng)準(zhǔn)循環(huán)碼的生成矩陣為，最小距離= 4。如果需要構(gòu)造碼率為1/4的最優(yōu)系統(tǒng)準(zhǔn)循環(huán)碼，在生成矩陣的基礎(chǔ)上進(jìn)行碼率可變擬陣搜索算法即可。

3 實(shí)驗(yàn)結(jié)果

基于可變擬陣搜索碼算法，構(gòu)造一類(lèi)特殊碼率為1/的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼，具備碼率可變性，伴隨著的變化，生成矩陣減少或者增加一個(gè)循環(huán)矩陣，產(chǎn)生碼率均為1/的最優(yōu)碼。本文所指得最優(yōu)碼，是滿(mǎn)足這一特性的生成矩陣所能得到的最大的最小距離，并非廣義上的最優(yōu)碼。通過(guò)對(duì)比文獻(xiàn)[16,19]和兩個(gè)數(shù)據(jù)庫(kù)[5,20]，得到最小距離見(jiàn)表1。其中，粗體的最小距離和現(xiàn)有最優(yōu)準(zhǔn)循環(huán)碼的最小距離相同，粗體加*號(hào)的最小距離比現(xiàn)有最優(yōu)準(zhǔn)循環(huán)碼的最小距離大, 即碼(182, 14, 77)和(340, 17, 146)。

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

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

碼的重量分布定義為：設(shè)為上的線性碼，分別為中重量為0,1,,碼字的個(gè)數(shù)，為的重量分布，設(shè),為變?cè)?，稱(chēng)次齊次多項(xiàng)式為的重量計(jì)算子。根據(jù)二進(jìn)制線性碼最小距離定義，等于非零碼字的最小重量，而表示線性碼重量為的碼字個(gè)數(shù)，因此根據(jù)最優(yōu)碼的重量分布可以驗(yàn)證表1的最小距離。查看(240, 12, 108)碼的重量分布可知，非零碼字的最小重量的數(shù)量為，因此最小距離= 108，符合表1列出的數(shù)值。根據(jù)表2中的生成矩陣代表亦可驗(yàn)證表1的最小距離。二進(jìn)制線性碼表示成向量形式為=，由于本文構(gòu)造的是系統(tǒng)碼，而系統(tǒng)碼具有前位是信息位的特點(diǎn)，因此碼的重量為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]，可以驗(yàn)證=12,=2~20時(shí)準(zhǔn)循環(huán)碼的最小距離。當(dāng)= 12,= 2時(shí)，=[1 379],“1”,“379”表示12×12循環(huán)矩陣，首列為[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”表示的循環(huán)矩陣。根據(jù)wt()=wt()+ wt()，求得重量計(jì)算子為，非零碼字的最小重量的數(shù)量為，因此= 8，符合表1中當(dāng)= 12,= 2時(shí)的最小距離。

上標(biāo)代表重量，下標(biāo)代表數(shù)量，則由表2中生成矩陣生成的最優(yōu)碼重量分布如下：

(1)新準(zhǔn)循環(huán)碼(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)新準(zhǔn)循環(huán)碼(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 結(jié)束語(yǔ)

本文主要研究如何利用擬陣?yán)碚摌?gòu)造二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼，搜索,更大的最優(yōu)碼。在基于擬陣?yán)碚摰臄M陣搜索算法和局部擬陣搜索算法的基礎(chǔ)上，提出可變的擬陣搜索算法。該算法可搜索15的準(zhǔn)循環(huán)碼，減少重復(fù)搜索，降低運(yùn)算復(fù)雜度，亦可得到最優(yōu)碼。算法構(gòu)造一類(lèi)特殊的碼率為1/的二進(jìn)制系統(tǒng)準(zhǔn)循環(huán)碼，該碼有碼率可變性。實(shí)驗(yàn)結(jié)果相比現(xiàn)有的最優(yōu)準(zhǔn)循環(huán)碼，大部分最小距離與現(xiàn)有最優(yōu)碼的最小距離相差不大，多數(shù)與現(xiàn)有最優(yōu)碼的最小距離相等，關(guān)鍵得到兩個(gè)準(zhǔn)循環(huán)碼(182, 14, 77)和(340, 17, 146)比現(xiàn)有的準(zhǔn)循環(huán)碼的最小距離更大。算法特點(diǎn)和實(shí)驗(yàn)結(jié)果表明算法的可行性和優(yōu)越性。實(shí)際通信系統(tǒng)中，在保證良好糾錯(cuò)能力的前提下，采用本文所構(gòu)造的編碼，生成矩陣減少或者增加循環(huán)矩陣即可滿(mǎn)足變換碼率的需求，操作方便，具有一定的應(yīng)用價(jià)值。

表2碼率可變的最優(yōu)碼

(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] 張軼, 達(dá)新宇, 蘇一棟. 利用等差數(shù)列構(gòu)造大圍長(zhǎng)準(zhǔn)循環(huán)低密度奇偶校驗(yàn)碼[J]. 電子與信息學(xué)報(bào), 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] 郭銳, 劉春于, 張華, 等. 分簇?zé)o線傳感器網(wǎng)絡(luò)中根校驗(yàn)全分集LDPC碼設(shè)計(jì)與能效分析[J]. 電子與信息學(xué)報(bào), 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碼的設(shè)計(jì)及性能分析[J]. 電子與信息學(xué)報(bào), 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] 蘭亞柱, 楊海鋼, 林郁. 動(dòng)態(tài)自適應(yīng)低密度奇偶校驗(yàn)碼譯碼器的FPGA實(shí)現(xiàn)[J]. 電子與信息學(xué)報(bào), 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碼設(shè)計(jì)[J].應(yīng)用科學(xué)學(xué)報(bào), 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

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

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

張水平： 男，1965年生，教授，研究方向?yàn)榘踩夹g(shù)及工程、計(jì)算機(jī)應(yīng)用技術(shù)、云計(jì)算.

林平平： 男，1991年生，碩士生，研究方向?yàn)樾畔⒄撆c編碼.

巫光福： 男，1977年生，講師，研究方向?yàn)樾畔⒄撆c編碼、密碼學(xué)、組合設(shè)計(jì)、概率統(tǒng)計(jì).