13.2 RS編碼和糾錯算法
13.2.1. GF(2m)域 RS(Reed-Solomon)碼在伽羅華域(Galois Field,GF)中運算的,因此在介紹RS碼之前先簡要介紹一下伽羅華域。 CD-ROM中的數(shù)據(jù)、地址、校驗碼等都可以看成是屬于GF(2m) = GF(28)中的元素或稱符號。GF(28)表示域中有256個元素,除0,1之外的254個元素由本原多項式P(x)生成。本原多項式的特性是得到的余式等于0。CD-ROM用來構(gòu)造GF(28)域的是 (13-1) α = (0 0 0 0 0 0 1 0) 下面以一個較簡單例子說明域的構(gòu)造。 [例13.1] 構(gòu)造GF(23)域的本原多項式假定為 α定義為 = 0的根,即 α3+α+1 = 0 GF(23)中的元素可計算如下:
用二進制數(shù)表示域元素得到表13-01所示的對照表 表13-01 GF(23)域中與二進制代碼對照表,
這樣一來就建立了GF(23)域中的元素與3位二進制數(shù)之間的一一對應(yīng)關(guān)系。用同樣的方法可建立GF(28)域中的256個元素與8位二進制數(shù)之間的一一對應(yīng)關(guān)系。在糾錯編碼運算過程中,加、減、乘和除的運算是在伽羅華域中進行?,F(xiàn)仍以GF(23)域中運算為例: 加法例:α0+α3 = 001+011 = 010 = α1 減法例:與加法相同 乘法例:α5·α4 = α(5+4) mod7 = α2 除法例:α5/α3 = α2 α3/α5 = α-2 = α(-2+7) = α5 取對數(shù):log(α5) = 5 這些運算的結(jié)果仍然在GF(23)域中。 13.2.2 RS的編碼算法 RS的編碼就是計算信息碼符多項式除以校驗碼生成多項式之后的余數(shù)。 在介紹之前需要說明一些符號。在GF(2m)域中,符號(n,k)RS的含義如下:
例如,(28,24)RS碼表示碼塊長度共28個符號,其中信息代碼的長度為24,檢驗碼有4個檢驗符號。在這個由28個符號組成的碼塊中,可以糾正在這個碼塊中出現(xiàn)的2個分散的或者2個連續(xù)的符號錯誤,但不能糾正3個或者3個以上的符號錯誤。 對一個信息碼符多項式,RS校驗碼生成多項式的一般形式為 (13-2) 下面用兩個例子來說明RS碼的編碼原理。 [例13.2] 設(shè)在GF(23)域中的元素對應(yīng)表如表13-01所示。假設(shè)(6,4)RS碼中的4個信息符號為m3、m2、m1和m0,信息碼符多項式為 (13-3)
如果K0 = 1,t = 1,由式(13-2)導(dǎo)出的RS校驗碼生成多項式就為 = (13-4) m3x5+m2x4+m1x3+m0x2+Q1x+Q0 = (x-α)(x-α2)Q(x) 當(dāng)用x = α和x = α2代入上式時,得到下面的方程組, 經(jīng)過整理可以得到用矩陣表示的(6,4)RS碼的校驗方程: 求解方程組就可得到校驗符號: 在讀出時的校正子可按下式計算:
[例13.3] 在例13.2中,如果K0 = 0,t = 1,由式(13-2)導(dǎo)出的RS校驗碼生成多項式就為 = (13-5)
求解方程組可以得到RS校驗碼的2個符號為Q1和Q0, (13-6) 假定mi為下列值:
代入(13-6)式可求得校驗符號: Q1 = α6 = 101 Q0 = α4 = 110 13.2.3 RS碼的糾錯算法 RS碼的錯誤糾正過程分三步: (1)計算校正子(syndrome),(2)計算錯誤位置,(3)計算錯誤值?,F(xiàn)以例13.3為例介紹RS碼的糾錯算法。 校正子使用下面的方程組來計算: 為簡單起見,假定存入光盤的信息符號m3、m2、m1、m0和由此產(chǎn)生的檢驗符號Q1、Q0均為0,讀出的符號為m3′、m2′、m1′、m0′、Q1′和Q0′。 如果計算得到的s0和s1不全為0,則說明有差錯,但不知道有多少個錯,也不知道錯在什么位置和錯誤值。如果只有一個錯誤,則問題比較簡單。假設(shè)錯誤的位置為αx,錯誤值為mx,那么可通過求解下面的方程組: 得知錯誤的位置和錯誤值。 如果計算得到s0 = α2和s1 = α5,可求得αx = α3和mx = α2,說明m1出了錯,它的錯誤值是α2。校正后的m1 = m1′+mx ,本例中m1=0。 如果計算得到s0 = 0,而s1≠0,那基本可斷定至少有兩個錯誤,當(dāng)然出現(xiàn)兩個以上的錯誤不一定都是s0 = 0和s1≠0。如果出現(xiàn)兩個錯誤,而又能設(shè)法找到出錯的位置,那么這兩個錯誤也可以糾正。如已知兩個錯誤和的位置和,那么求解方程組: 就可知道這兩個錯誤值。 CD-ROM中的錯誤校正編碼CIRC和里德-索洛蒙乘積碼(Reed Solomon Product-like Code,RSPC)就是采用上述方法導(dǎo)出的。 |
|