RS碼的基礎知識

1、 報告人：李睿 報告時間：2013年10月12日桂林電子科技大學 信息安全研究所目錄目錄 代數(shù)引論代數(shù)引論RSRS碼的譯碼碼的譯碼近期的工作安排近期的工作安排群一個定義了二院運算*的集合G如果滿足一下的條件，則稱其為群：i.二元運算*滿足結合律；ii.G中包含一個元素e，使得對G中任意元素a，有 iii.對G中任意元素a，在G中存在另一個元素 ,滿足 交換群 如果群G二元運算同時滿足下面的條件，則稱群G是交換群：對G中任意的a和b，有 a*b=b*a aaeea *eaaaa *acabacba)(域域設F為一組元素的集合，在其上定義了加法“+”和乘法“ .”兩種運算。如果滿足下列條件，則集合

2、F與這兩種運算一起成為域：i.在加法下F是一個交換群。ii.F中的非零元素在乘法下構成一個交換群。iii.乘法對加法滿足分配率，即對F中任意的三個元素a，b和c，有伽伽羅華羅華域（域（GFGF（q q）有限域也稱為伽羅華域域元素的階必然存在一個使得 的最小正整數(shù)n，這個n就稱為域元素a的階。本原元在有限域GF（q）中，如果a的階為q-1，則非零元素a被稱為本原元。性質：本原元的冪生成了GF(q)中的所有的非零元素。本原多項式GF(2)上的m次多項式p(x)若不能被GF(2)上任意次數(shù)小于m且大于0的多項式整除，則稱p(x)在GF(2)上是不可約的。M次不可約多項式p(x)若滿足能被p(x)整除

3、的 的最小正整數(shù)n為 ，則稱p(x)為本原多項式。1na1nX12mn0ll2l2定理：設f(x)是一個以GF(2)中元素為系數(shù)的多項式， 是GF(2)擴域中的一個元素。如果 是f(X)的一個根，則對任意 , 也是f(X)的根。元素 稱為 的一個共軛。最小多最小多項項式式 為GF( )中的任意元素，令 為GF(2)上滿足 的最低次數(shù)多項式，則多項式 稱為的 最小多項式m2)(X0)()(X 共軛根 最小多項式 842,14 XX01X1X12963,1234XXXX105,12 XX1413117,134XX由 生成的GF( )中元素的最小多項式1)(34XXXp42生成多生成多項項式式在（n

4、，k）的RS中，存在唯一的n-k次多項式g(x)，使得每一個碼多項式c(x)都是g(x)的倍式.g(x)稱為RS碼的生成多項式。其中：n為碼長，k為信息位一般情況下：).()()(22txxxxg是本原多項式p(x)的根2 RS碼的譯碼BCH碼BCH碼是一種獲得廣泛應用的能夠糾正多個錯碼的循環(huán)碼。RS碼RS碼是一類具有很強糾錯能力的多進制BCH碼。符號取自GF(q)，糾t個錯誤的RS碼具有以下參數(shù)： 分組長度： n=q-1奇偶校驗符號數(shù)：n-k=2t最小距離：12min tdRS譯碼譯碼RS碼的譯碼分成以下5步： er jSjS)(X)(X由接收的r(x)求得伴隨多項式由 求得錯誤位置多項式用

5、錢搜索解出 的根，得到錯誤位置數(shù)，確定錯誤位置。 由錯誤位置數(shù)求得錯誤值，從而得到錯誤圖樣完成糾錯校驗矩陣接收值1 1）求伴隨多項式)(),.(),(22tTRRRRHS所以：或表示為tjRSjj2,.,2 , 1),(2 2）BM迭代算法求錯誤位置多項式 BM迭代算法利用S伴隨矩陣得到錯誤多項式迭代步驟如下：a a 由初始值 10)0(1) 1(, 0)0(, 1)(1, 0) 1(, 1)(SdDxdDx開始迭代其中: 是錯誤位置多項式 的次數(shù)， 為第j步和第j+1步的差值 )(jD)()(xjjd)(1)()(1)(2)(11.jDjjjDjjjjjjSSSSd)()()(2)(2)(1

6、)(.1)(jDjjDjjjXXXXb 若 則有 并計算 ，再進行下一次迭代 若 ，則找出 之前的某一行 ，它在所有 行之前各行中的 最大，且 ，于是按 0jd)()()() 1(xxjj1jd0jd0id)()()()(1)() 1(xxddxxiijijjj計算)()1(xj這就是第 步的解 c c 計算 ，重復 步進行下一步迭代，這樣迭代 次后得到的 即為所求的 。 1jd)()2(xt)(x)( jDi ijj1jt2b3 3）用錢搜索解出 的根，得到錯誤位置數(shù)。（上一步已經求得 ） 。)(x)(x下面介紹錢搜索錯誤位置數(shù)的步驟：對接收向量112210.)(nnXrXrXrrXr進行逐

7、比特譯碼。最高位比特被首先譯碼。為了譯 ，譯碼器檢驗 是否是錯誤位置數(shù)；也就等價于檢驗于檢驗它的倒數(shù) 是否是 的根。如果是，則：1nr1n)(X0.1221vv因此，為了譯 ，譯碼器需要構造 ， , 。如果 ，則 是錯誤位置數(shù)，并且是錯誤位，否則， 是正確位。 1nr122vv0.1221vv1n1nr1nr為了譯 ，譯碼器需要構造 ， ， 并校驗和式：lnrl1l 22vlvvlvll.1221如果和式為0，則 是 的根，且 是錯誤位；否則， 是正確位。 l)(Xlnrlnr 4）由錯誤位置數(shù)求得錯誤值，從而得到錯誤圖樣。 RS碼錯誤值（ ） 計算公式： 求出0)( xike)()(11kkikXXe)(