[發明專利]一種可容錯的RS碼碼長起點識別方法

有效

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

1.一種可容錯的RS碼碼長起點識別方法，通過計算機內用C語言仿真算法進行識別，該方法包括參數初始化、碼長識別以及起點識別三個步驟，其具體步驟如下：

1)參數初始化

設置RS碼的最大可能碼長nmax，主要識別階數m為3到9的RS碼的起點和碼長，所以將最大可能碼長設為2⁹-1，即nmax=511；設置所需碼字個數codenum，根據經驗值令codenum=200；

2)碼長識別，按如下步驟進行：

a)碼長n從1開始遍歷，每次遍歷都依次進行(b)到(g)步的操作，找到真實碼長后，結束遍歷；

b)生成長度為n*codenum的0、1隨機碼字序列；

c)以碼長n為間隔劃分隨機碼字序列得到codenum個碼長為n的隨機碼字，計算兩兩隨機碼字間漢明距離，并統計不同漢明距離出現的次數，若碼長為n，碼字個數為codenum，則一共有(codenum²-codenum)/2種兩兩組合的隨機碼字，可能出現的隨機碼字漢明距離集為{0,1,2,…,n}，設distance1為與隨機碼字漢明距離集相對應的各個元素出現的次數集合，即dis?tan?ce1＝{dis?tan?ce1[0],dis?tan?ce1[1],...,dis?tan?ce1[n]}，distance1[i]表示漢明距i在(codenum²-codenum)/2種組合中出現的次數，i＝0,1,...,n，兩個碼字間漢明距的計算方法為計算兩個碼字相應位置元素不同的個數；

d)計算隨機碼字序列漢明距離出現概率集合P′＝{P′[0],P′[1],...,P′[n]}，計算方法如(1)式所示：

P′[i]＝dis?tan?ce1[i]/((codenum²-codenum)/2),i＝0,1,...,n???(1)

其中：P′[0]、P′[1]……P′[n]分別是隨機碼字序列的漢明距離0,1,…,n在(codenum²-codenum)/2種組合中出現的概率，運算符號[]表示其內元素為漢明距離，{}表示集合，P′[i]是集合P′中的第i個元素；

e)以碼長n為間隔劃分待識別碼字序列得到codenum個碼長為n的碼字，計算兩兩隨機碼字間漢明距離，并統計不同漢明距離出現的次數，若碼長為n，碼字個數為codenum，則一共有(codenum²-codenum)/2種兩兩組合的待識別碼字，可能出現的待識別碼字序列漢明距離集為{0,1,2,…,n}，設distance為與待識別碼字漢明距離集相對應的各個元素出現的次數集合，即dis?tan?ce＝{dis?tan?ce[0],dis?tan?ce[1],...,dis?tan?ce[n]}，distance[i]表示漢明距i在(codenum²-codenum)/2種組合中出現的次數，i＝0,1,...,n，兩個碼字間漢明距的計算方法為計算兩個碼字相應位置元素不同的個數；

f)計算待識別碼字序列漢明距離出現概率集合P＝{P[0],P[1],...,P[n]}，計算方法如(2)式所示：

P[i]＝dis?tan?ce[i]/((codenum²-codenum)/2),i＝0,1,...,n???(2)

其中：P[0]、P[1]……P[n]分別是待估計碼字序列的漢明距離0,1,…,n在(codenum²-codenum)/2種組合中出現的概率，運算符號[]表示其內元素為漢明距離、{}表示集合，P[i]是集合P中的第i個元素；

g)計算待識別碼字序列漢明距離出現概率P與隨機碼字序列漢明距離出現概率P′的偏移量E_n，按式(3)計算：

En=Σi=0n|Pi-Pi′|2---(3)]]>

其中：P_i表示待估計碼子序列中漢明距離i在(codenum²-codenum)/2種組合中出現的概率,表示隨機碼字序列中漢明距離i在(codenum²-codenum)/2種組合中出現的概率,||²表示對其內部元素計算模的平方；

h)若n＜nmax，則n=n+1,轉入步驟b)；否則若n＝nmax，則轉入下一步；

i)至此，每一個碼長n都有一個E_n與之對應，令偏移量矢量集合E＝{E₁,E₂,...,E_nmax}，求E的一次差序列，一次差序列的表達式如(4)式所示：

E1_i＝E_i+1-E_i,i＝0,1,...,n-1???(4)

其中：E_i表示偏移量矢量集合E中的第i個值，E_i+1表示偏移量矢量集合E中的第i+1個值，E1表示偏移量矢量集合E的一次差序列集合，E1_i表示E1的第i個值；

j)找出E1中最大的元素，并記錄最大元素的下標imax，設E1_2i表示E1的第2*i個元素值，E1_3i表示E1的第3*i個元素值,若E1_2i＞E1_i/10且E1_3i＞E1_i/10，則imax=i即為真實碼長，碼長識別成功；若E1_2i≤E1_i/10或E1_3i≤E1_i/10，則i不是真實碼長；

3)起點識別

因為只有當識別時選取的待識別序列起點為完整碼字的首個比特且識別出的碼長為真實碼長時，E_i的值明顯大于其左邊n-1個值E_i-1,E_i-2,...,E_i-(n-1)和右邊n-1個值E_i+1,E_i+2,...,E_i+(n-1)，E_ki的值明顯大于其左邊n-1個值E_ki-1,E_ki-2,...,E_ki-(n-1)和右邊n-1個值E_ki+1,E_ki+2,...,E_ki+(n-1)，2≤k≤3，當k>3時，E_ki的值明顯大于其左邊n-1個值E_ki-1,E_ki-2,...,E_ki-(n-1)和右邊n-1個值E_ki+1,E_ki+2,...,E_ki+(n-1)的規律將會變弱或消失，且此時隨著i的增大，E_i成平緩遞增趨勢，所以采取同時遍歷起點start和碼長的方法來識別起點和碼長，start由0到nmax遍歷，每一次遍歷都轉入步驟2)開始碼長識別的所有操作，直到碼長識別正確時，此時的起點即為真實起點。