RS碼的基礎(chǔ)知識(shí)PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1RS碼的基礎(chǔ)知識(shí)碼的基礎(chǔ)知識(shí)代數(shù)引論代數(shù)引論RSRS碼的譯碼碼的譯碼近期的工作安排近期的工作安排第1頁(yè)/共19頁(yè)aaeea *eaaaa *a第2頁(yè)/共19頁(yè)cabacba)(域域設(shè)F為一組元素的集合，在其上定義了加法“+”和乘法“ .”兩種運(yùn)算。如果滿(mǎn)足下列條件，則集合F與這兩種運(yùn)算一起成為域：i.在加法下F是一個(gè)交換群。中的非零元素在乘法下構(gòu)成一個(gè)交換群。iii.乘法對(duì)加法滿(mǎn)足分配率，即對(duì)F中任意的三個(gè)元素a，b和c，有伽羅華域（伽羅華域（GF（q）有限域也稱(chēng)為伽羅華域第3頁(yè)/共19頁(yè)1na1nX12mn第4頁(yè)/共19頁(yè)0ll2l2定理：設(shè)f(x)是一個(gè)以GF(2)中元素為系數(shù)的多

2、項(xiàng)式， 是GF(2)擴(kuò)域中的一個(gè)元素。如果 是f(X)的一個(gè)根，則對(duì)任意 , 也是f(X)的根。元素 稱(chēng)為 的一個(gè)共軛。最小多項(xiàng)式最小多項(xiàng)式 為GF( )中的任意元素，令 為GF(2)上滿(mǎn)足 的最低次數(shù)多項(xiàng)式，則多項(xiàng)式 稱(chēng)為的 最小多項(xiàng)式m2)(X0)()(X第5頁(yè)/共19頁(yè) 共軛根 最小多項(xiàng)式 842,14 XX01X1X12963,1234XXXX105,12 XX1413117,134XX由 生成的GF( )中元素的最小多項(xiàng)式1)(34XXXp42第6頁(yè)/共19頁(yè)生成多項(xiàng)式生成多項(xiàng)式在（n，k）的RS中，存在唯一的n-k次多項(xiàng)式g(x)，使得每一個(gè)碼多項(xiàng)式c(x)都是g(x)的倍式.g(

3、x)稱(chēng)為RS碼的生成多項(xiàng)式。其中：n為碼長(zhǎng)，k為信息位一般情況下：).()()(22txxxxg是本原多項(xiàng)式p(x)的根第7頁(yè)/共19頁(yè)分組長(zhǎng)度： n=q-1奇偶校驗(yàn)符號(hào)數(shù)：n-k=2t最小距離：12min td第8頁(yè)/共19頁(yè)er jSjS)(X)(X由接收的r(x)求得伴隨多項(xiàng)式由 求得錯(cuò)誤位置多項(xiàng)式用錢(qián)搜索解出 的根，得到錯(cuò)誤位置數(shù)，確定錯(cuò)誤位置。 由錯(cuò)誤位置數(shù)求得錯(cuò)誤值，從而得到錯(cuò)誤圖樣完成糾錯(cuò)第9頁(yè)/共19頁(yè)校驗(yàn)矩陣接收值1）求伴隨多項(xiàng)式第10頁(yè)/共19頁(yè))(),.(),(22tTRRRRHS所以：或表示為tjRSjj2,.,2 , 1),(2）BM迭代算法求錯(cuò)誤位置多項(xiàng)式 BM迭代

4、算法利用S伴隨矩陣得到錯(cuò)誤多項(xiàng)式迭代步驟如下：a 由初始值 10)0(1) 1(, 0)0(, 1)(1, 0) 1(, 1)(SdDxdDx開(kāi)始迭代其中: 是錯(cuò)誤位置多項(xiàng)式 的次數(shù)， 為第j步和第j+1步的差值 )(jD)()(xjjd)(1)()(1)(2)(11.jDjjjDjjjjjjSSSSd)()()(2)(2)(1)(.1)(jDjjDjjjXXXX第11頁(yè)/共19頁(yè)0jd)()()() 1(xxjj1jd0jd0id)()()()(1)() 1(xxddxxiijijjj計(jì)算)()1(xj這就是第 步的解 c 計(jì)算 ，重復(fù) 步進(jìn)行下一步迭代，這樣迭代 次后得到的 即為所求的 。

5、 1jd)()2(xt)(x)( jDi ijj1jt2b第12頁(yè)/共19頁(yè)3）用錢(qián)搜索解出 的根，得到錯(cuò)誤位置數(shù)。（上一步已經(jīng)求得 ） 。)(x)(x下面介紹錢(qián)搜索錯(cuò)誤位置數(shù)的步驟：對(duì)接收向量112210.)(nnXrXrXrrXr進(jìn)行逐比特譯碼。最高位比特被首先譯碼。為了譯 ，譯碼器檢驗(yàn) 是否是錯(cuò)誤位置數(shù)；也就等價(jià)于檢驗(yàn)于檢驗(yàn)它的倒數(shù) 是否是 的根。如果是，則：1nr1n)(X0.1221vv第13頁(yè)/共19頁(yè)因此，為了譯 ，譯碼器需要構(gòu)造 ， , 。如果 ，則 是錯(cuò)誤位置數(shù)，并且是錯(cuò)誤位，否則， 是正確位。 1nr122vv0.1221vv1n1nr1nr為了譯 ，譯碼器需要構(gòu)造 ， ， 并校驗(yàn)和式：lnrl1l 22vlvvlvll.1221如果和式為0，則 是 的根，且 是錯(cuò)誤位；否則， 是正確位。 l)(Xlnrlnr第14頁(yè)/共19頁(yè)求出0)( xike)()(11kkikXXe)(x為的導(dǎo)數(shù)形式)(x)(mod()()(2txxxSx被稱(chēng)為錯(cuò)誤估值函數(shù))(x為錯(cuò)誤位置數(shù)kX