[發明專利]一種二進制本原 BCH 碼盲識別方法

有效

• 申請號: 201310343717.1
• 申請日: 2013-08-08
• 公開（公告）號: CN103401567A
• 公開（公告）日: 2013-11-20
• 發明（設計）人: 馬丕明;王丹;楊勇
• 申請（專利權）人: 山東大學
• 主分類號: H03M13/15
• 分類號: H03M13/15
• 代理公司: 濟南金迪知識產權代理有限公司 37219
• 代理人: 許德山

1.一種二進制本原BCH碼盲識別方法，包括碼長識別、起點識別、生成多項式識別和本原多項式識別，其具體步驟如下：

〈1〉碼長識別

1)初始化參數，可能的起點：shiftg＝-1，取值范圍為[-1∞]，shiftg的類型gchoice＝-1，取值范圍為{-1,1}，識別的碼長：ng＝-1，取值范圍為[-1∞]，從本原多項式文件中讀入本原多項式表，接收到的碼字序列為R，長度為Rlength；

2)用線性矩陣分析法識別碼長是否小于等于15，定義q為3～50內的循環變量，將接收到的數據按行寫入50×q的矩陣M中，如果M的秩不等于q，則保留q，計算保留數即q在3～50的循環中保留的滿足上述條件的q的最大公因式作為識別的碼長ng，如果沒有保留數，則沒有識別出碼長；

3)判斷ng是否滿足下列兩個條件：ng+1是2的整數冪；ng＞0，如果ng不滿足這兩個條件，則進入步驟4），如果ng滿足這兩個條件，則識別到的碼長就是ng，碼長識別過程結束；

4)若ng+1不是2的整數冪并且ng≤0，碼長識別如下：

（a）定義階數m＝5，偏移量shift＝0，數據序列指針R0＝R；

（b）設碼長n＝2^m-1,R＝R0+shift，使用比特相關性算法判斷R中數據的碼長是否是n：

i.定義矩陣X_N×n，矩陣函數為X_N×n，將接受到的碼字序列R的前N*n比特按行寫入矩陣X_N×n，然后將矩陣X_N×n轉置得到Xt_n×N，Xt_n×N的列數集合為N＝{0,1,…,n-1}，Xt_n×N中信息集的列數集合為I_1×n，Xt_n×N冗余列數集合為J_1×(N-n)，計算得到的碼字個數num＝0，碼重分布向量為W_1×(N+1)，將其初始化為全0；

ii.尋找集合I_1×n，I∪J＝N,其中符號∪、∩、分別表示集合相加、取交集、空集合，I、J是兩個集合，集合元素是矩陣Xt_n×N的列數，Xt(I)表示I_1×n中的元素對應的列構成的方陣，Xt(J)表示J_1×(N-n)中元素對應的列構成的矩陣，如果Xt(I)能夠通過行化簡得到單位陣，則I_1×n為正確的信息集，記錄下Xt(I)的行化簡步驟，對Xt(J)實施相同的行化簡步驟，執行步驟iii；如果找不到I_1×n使得Xt(I)能夠通過行化簡得到單位陣，則認為n為接收到的碼字序列的碼長，ng＝n，gchoice＝1，shiftg＝shift；

iii.將{0,1,…,n-1}隨機平分成兩個向量Z₁(1×k₁)，Z₂(1×k₂)，k₁+k₂＝n，k₁、k₂分別是向量Z₁,Z₂的列數，Z₁中元素對應的行組成的矩陣為Λ1，Z₂中元素對應的行組成的矩陣為Λ2，定義sigma＝log(n)/log(2)，隨機選取sigma個J_1×(N-n)中的元素構成向量L，選取Λ1中的任意2行，共有種取法，對于遍取的所有的Λ1中的任意2行，將其在二元域上相加，得到向量Λ1|L，Λ1|(J/L)，其中Λ1|L表示L中的元素對應的Λ1的列構成的矩陣，J/L表示J-L,，L∈J,同樣計算Λ2|L，Λ2|(J/L)；

iv.比較所有的Λ1|L和Λ2|L，如果Λ1|L＝Λ2|L，則Λ1+Λ2的碼重為weight＝weight((Λ1+Λ2)|(J/L))+4，W(weight)＝W(weight)+1，num＝num+1;其中：(Λ1+Λ2)是將Λ1、Λ2兩個向量相加，(Λ1+Λ2)|(J/L)表示J/L中元素對應的列構成的向量、weight((Λ1+Λ2)|(J/L))表示(Λ1+Λ2)|(J/L)向量中1的個數、W（weight）表示重量為weight的向量Λ1+Λ2出現的次數；

v.如果num≥200，轉入下一步，如果num＜200，則轉入步驟iii；

vi.計算W的平方差為hsigma，如果hsigma＞30，則認為n是接受到的碼字序列的碼長，ng＝n,shiftg＝shift,gchoice＝1；

（c）判斷n是否為二進制本原BCH碼的碼長，如果n是接收到的碼字序列的碼長，則跳出循環，ng＝n，如果判斷n不是接收到的碼字序列的碼長且shift＜n，則shift＝shift+n/m，重新執行步驟（b）；如果判斷n不是接收到的碼字序列的碼長且shift≥n，則執行步驟（d）；

（d）使用碼根算法判斷碼長是否是接收到的碼字序列的碼長：

1〉根據階數m和本原多項式表中m對應的第1個本原多項式，計算本原關系表，定義偏移量shift＝0；

2〉定義碼字序列指針R＝R0+shift，對于一個長度為n個二進制序列(c₀,c₁,c₂,…,c_n-2,c_n-1)，可以將其每一項看作是一個碼字多項式c₀+c₁x+c₂x²+…+c_n-2x^n-2+c_n-1x^n-1中的各項的系數，將代入到碼字多項式c₀+c₁x+c₂x²+…+c_n-2x^n-2+c_n-1x^n-1中，其中符號表示任意、∈表示屬于、及式表示對于任意屬于集合[1,n-1]的元素x，x^l可以通過步驟1〉中的本原關系表找到，其中符號l表示冪次，最后在GF(2^m)上計算多項式的值，如果結果為0，表示x為這個多項式的根，將R中前1000*n個比特分割成1000個碼字，計算碼根分布，如果碼根出現的概率最大值小于0.9，則進入步驟3〉，統計碼根出現的概率與最大值相差小于0.1的碼根數目，如果該數目是m的整數倍，則判斷該碼長正確，識別碼長結束，shiftg＝shift,gchoice＝1；如果該數目不是m的整數倍，則進入步驟3〉；

3〉shift＝shift+1，如果shift＜n，則執行步驟2〉，如果shift≥n，n不是接收到的碼字序列的碼長；

（e）如果碼根特性算法判斷n是接收到的碼字序列的碼長，則識別得到的碼長為n，ng=n，否則m＝m+1，shift＝0，執行步驟（b）；

〈2〉起點識別

a〉識別的碼長為ng，定義起點偏移量為start，如果gchoice＝＝1，則R＝R0+shiftg-ng/m，shiftgmost＝3*ng/m,

Rlength＝Rlength-(shiftg-ng/m)，否則R＝R0，shiftgmost＝n；

b〉使用最大公因式算法進行起點識別：

①定義偏移量shift＝0,定義一個ng×ng的矩陣M，分配相應空間作為緩沖區1和緩沖區2，定義num1、num2作為循環變量，統計最小值：shiftmin＝200，統計最大值shiftmax＝0，統計最大值對應的偏移量shiftg1=0，統計最小值對應的偏移量shiftg2=0，公因式個數最大值的統計最大值對應的公因式總數sum1=0，公因式個數最大值的統計最小值對應的公因式總數sum2=0，公因式個數最大值為max，公因式個數總數為sum；

②定義數據序列指針R1＝R+shift，碼字序號num1＝0，碼字循環次數num2＝0；將R1前200*ng個比特分割成200個碼字；

③將第num1個碼字循環左移num2次，放入M的第num2行，num2＝num2+1.如果num2＝＝ng，則num2＝0，num1＝num1+1，使用歐幾里德算法計算M中所有行的公因式，將公因式及其階數放入緩沖區1中，如果num1＝＝200，則執行步驟④，如果num1≠200執行步驟③；

④統計公因式，首先將公因式按照階數由低到高排列，相同的公因式合并，次數相應增加，如果高次公因式可以被低次多項式整除，則刪除高次公因式，低次公因式次數增加，將統計后的結果放入緩沖區2中，max為公因式出現的次數最大值，sum為公因式次數的和；

⑤如果max大于shiftmax，則shiftg1=shift,shiftmax=shift,sum1=sum，如果max小于shiftmin，則shiftg2=shift,shiftmin=shift,sum2=sum，shift＝shift+1，如果shift＜ng，則執行步驟②，否則執行步驟⑥；

⑥如果sum1>sum2，則起點偏移量為start＝shiftg1，否則為start＝shiftg2，

c〉如果gchoice＝＝1，則start＝start+shiftg-ng/m，起點偏移量為start，起點識別完成；

〈3〉生成多項式識別

a）起點偏移量為start，碼長ng，階數m＝log2(ng+1)，偏移量為shift＝start，狀態變量flag＝0，碼字序列指針R=R0+shift；

b）根據階數m和本原多項式表中m對應的第1個本原多項式，計算本原關系表；

c）對于一個長度為ng個二進制序列(c₀,c₁,c₂,…,c_ng-2,c_ng-1)，可以將其每一項看作是一個碼字多項式c₀+c₁x+c₂x²+…+c_ng-2x^ng-2+c_ng-1x^ng-1中的各項的系數，將代入到碼字多項式中，x^l可以通過b）中本原關系表找到，最后在GF(2^m)上計算多項式的值，如果結果為0，表示x為這個多項式的根，將R中前1000*ng個比特分割成1000個碼字，計算碼根分布，如果碼根出現的概率最大值小于0.9，則進入步驟d），統計碼根出現的概率，統計碼根概率與概率最大值相差小于0.1的碼根數目rootnum，信息位長度y＝n-rootnum，如果此時起點偏移量和碼長都是接收到的碼字序列的真實起點和碼長，那么BCH碼字階數m、信息位長度k、糾錯能力t之間的關系表中必然存在一個糾錯能力t使得n＝2^m-1,y＝＝k，如果沒有t滿足條件，則進入步驟d），否則進入步驟e）；

d）如果flag＝0，則定義m＝2,shift＝0,flag＝1，R＝R0+shift，n＝2^m-1，執行步驟b），如果flag＝1且shift＜n，則shift＝shift+1，如果flag＝＝1且shift＝n，則m＝m+1,shift＝0，R＝R0+shift，執行步驟c）；

e）接收到的碼字序列的真實起點偏移量start＝shift，根據最大的前rootnum個碼根得到一個由rootnum個一元一次多項式，將這些多項式相乘、化簡，從而得到生成多項式G，G的階數degree=rootnum；

〈4〉本原多項式識別

a.定義碼字序列R＝R0+start，m＝log(ng)/log(2)，根據二進制本原BCH碼階數m、糾錯能力t和信息位長度k之間的對應關系得到信息位長度k，階數m共有prime_max個本原多項式，本原多項式序數primenum＝0，誤比特數Errorbits=0，最小無比特數Errormin=1e20，無法糾錯的次數Error＝0，最可能的本原多項式的序數posprimenum=0，譯碼再編碼后對比錯誤最小個數ErrorRmin=1e20；

b.根據階數m的第primenum個本原多項式，計算伽羅華域，對接收到的碼字序列R的前2000個碼字進行譯碼，Errorno是譯碼過程中不能糾正的錯誤個數；

c.根據生成多項式G將譯碼后的信息序列進行編碼，得到的碼字為code,將code與R的前2000個碼字進行對比，不相同的位數為ErrorR；

d.無法糾錯的次數Error＝Errorno*k+Errorbits，如果Error<Errormin,則Errormin＝Error，posprimenum=primenum，ErrorRmin=ErrorR；如果Error=Errormin且ErrorR<ErrorRmin，則Errormin＝Error，posprimenum=primenum，ErrorRmin=ErrorR；

e.本原多項式序數primenum＝primenum+1，如果primenum=prime_max，則執行步驟f，否則執行b；

f.根據階數m的第primenum個本原多項式，計算伽羅華域，對R的前2000個碼字進行譯碼，Errorno是譯碼過程中不能糾正的錯誤個數，Errorbits是譯碼糾正的錯誤個數，根據生成多項式G將譯碼后的信息序列進行編碼，得到的碼字為code,將code與R的前2000個碼字進行對比，不相同的位數為ErrorR；

g.第primenum個本原多項式就是接收到的碼字序列使用的本原多項式，置信度為：1-ErrorR/2000/ng。