第16章錯誤檢測和校正

第16章錯誤檢測和校正2/3/2023116.1CRC錯誤檢測原理在糾錯編碼代數(shù)中，把以二進(jìn)制數(shù)字表示的一個數(shù)據(jù)系列看成一個多項式。例如，二進(jìn)制數(shù)字序列10101111，用多項式可以表示成：式中的xi表示代碼的位置，或某個二進(jìn)制數(shù)位的位置，xi前面的系數(shù)ai表示碼的值。若ai是一位二進(jìn)制代碼，則取值是0或1。稱M(x)為信息代碼多項式。

=2/3/20232在模2多項式代數(shù)運算中定義的運算規(guī)則有：例如，模2多項式的加法和減法：****結(jié)論：對于模2運算來說，代碼多項式的加法和減法運算所得的結(jié)果相同。在做代碼多項式的減法時，可用做加法來代替做減法。2/3/20233代碼多項式的除法可按長除法做。例如2/3/20234如果一個k位的二進(jìn)制信息代碼多項式為M(x)，再增加(n－k)位的校驗碼，那么增加(n－k)位之后，信息代碼多項式在新的數(shù)據(jù)塊中就表示成xn-kM(x)，如圖16-01所示。圖16-01信息代碼結(jié)構(gòu)(n－k)(n－k)2/3/20235如果用一個校驗碼生成多項式G(x)去除代碼多項式，得到的商假定為Q(x)，余式為R(x)，則可寫成因為模2多項式的加法和減法運算結(jié)果相同，所以又可把上式寫成：

G(x)稱為校驗碼生成多項式。從該式中可以看到，代表新的代碼多項式xn-kM(x)+R(x)是能夠被校驗碼生成多項式除盡的，即它的余項為0。

2/3/20236例如，CD盤中的q通道和軟磁盤存儲器中使用的CRC校驗碼生成多項式是: G(x)=x16+x12+x5+1若用二進(jìn)制表示，則為: G(x)=10001000000100001(B) =11021(H)假定要寫到盤上的信息代碼M(x)為 M(x)=4D6F746F(H)由于增加了2個字節(jié)共16位的校驗碼，所以信息代碼變成x16M(x):4D6F746F0000(H)。2/3/20237CRC檢驗碼計算如下：兩數(shù)相除的結(jié)果，其商可不必關(guān)心，其余數(shù)為B994(H)就是CRC校驗碼。把信息代碼寫到盤上時，將原來的信息代碼和CRC碼一起寫到盤上。在這個例子中，寫到盤上的信息代碼和CRC碼是4D6F746FB994,4D6F746FB994信息代碼CRC碼這個碼是能被11021(H)除盡的。從盤上把這塊數(shù)據(jù)讀出時，用同樣的CRC碼生成多項式去除這塊數(shù)據(jù)，相除后得到的兩種可能結(jié)果是：①余數(shù)為0，表示讀出沒有出現(xiàn)錯誤；②余數(shù)不為0，表示讀出有錯。

73

92/3/20238 CD-ROM中也采用了相同的CRC檢錯。CD-ROM扇區(qū)方式01中，有一個4字節(jié)共32位的EDC字域，它就是用來存放CRC碼。 P(x)=(x16+x15+x2+1)(x16+x2+x+1) 計算CRC碼時用的數(shù)據(jù)塊是從扇區(qū)的開頭到用戶數(shù)據(jù)區(qū)結(jié)束為止的數(shù)據(jù)字節(jié)，即字節(jié)0～2063共2064個字節(jié)。在EDC中存放的CRC碼的次序如下：EDC：x24－x31x16－x23x8－x15x0－x7字節(jié)號：20642065206620672/3/2023916.2RS編碼和糾錯算法16.2.1.GF(2m)域****伽羅華域(GaloisField，GF)

CD-ROM中的數(shù)據(jù)、地址、校驗碼等都可以看成是屬于GF(2m)=GF(28)中的元素或稱符號。GF(28)表示域中有256個元素，除0，1之外的254個元素由本原多項式P(x)生成。本原多項式P(x)的特性是 得到的余式等于0。CD-ROM用來構(gòu)造GF(28)域的是 P(x)=x8+x4+x3+x2+1而GF(28)域中的本原元素為:

α＝（00000010）2/3/202310[例13.1]構(gòu)造GF(23)域的本原多項式P(x)假定為 P(x)=x3+x+1 α定義為P(x)=0的根，即 α3＋α＋1=0

和 α3=α＋1x7+1/P(x)=？？？2/3/2023110mod(α3＋α＋1)=0α0mod(α3＋α＋1)=α0=1α1mod(α3＋α＋1)=α1α2mod(α3＋α＋1)=α2α3

mod(α3＋α＋1)=α＋1α4

mod(α3＋α＋1)=α2＋αα5mod(α3＋α＋1)=α2＋α1＋1α6mod(α3＋α＋1)=α2＋1α7mod(α3＋α＋1)=α0α8mod(α3＋α＋1)=α1……

GF(23)中的元素可計算如下：

2/3/202312表16-01GF(23)域中與二進(jìn)制代碼對照表,P(x)=x3+x+1GF(23)域元素二進(jìn)制對代碼0(000)α0

(001)α1

(010)α2

(100)α3

(011)α4

(110)α5

(111)α6

(101) 建立了GF(23)域中的元素與3位二進(jìn)制數(shù)之間的一一對應(yīng)關(guān)系。 用同樣的方法可建立GF(28)域中的256個元素與8位二進(jìn)制數(shù)之間的一一對應(yīng)關(guān)系。2/3/202313現(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)域中。2/3/20231416.2.2RS的編碼算法RS的編碼就是計算信息碼符多項式M(x)除以校驗碼生成多項式G(x)之后的余數(shù)。在GF(2m)域中，符號(n，k)RS的含義如下：m 表示符號的大小，如m=8表示符號由8 位二進(jìn)制數(shù)組成n 表示碼塊長度，k表示碼塊中的信息長 度K=n－k=2t 表示校驗碼的符號數(shù)t 表示能夠糾正的錯誤數(shù)目例如，(28，24)RS碼表示碼塊長度共28個符號，其中信息代碼的長度為24，檢驗碼有4個檢驗符號。2/3/202315對一個信息碼符多項式M(x)，RS校驗碼生成多項式的一般形式為: (16-2) 式中，K0是偏移量，通常取K0=0或K0=1， 而K=(n-k)≥2t(t為要校正的錯誤符號數(shù))。2/3/202316[例13.2]設(shè)在GF(23)域中的元素對應(yīng)表如表16-01所示。假設(shè)(6，4)RS碼中的4個信息符號為m3、m2、m1和m0，信息碼符多項式M(x)為 M(x)=m3x3+m2x2+m1x+m0 (16－3)

并假設(shè)RS校驗碼的2個符號為Q1和Q0，

的剩余多項式為 R(x)=Q1x+Q0這個多項式的階次比G(x)的階次少一階。2/3/202317 如果K0=1，t=1，由式(16－2)導(dǎo)出的RS校驗碼生成多項式就為(16-4) 根據(jù)多項式的運算，由式(16－3)和式(16－4)可以得到 m3x5＋m2x4＋m1x3＋m0x2＋Q1x＋Q0

=(x－α)(x－α2)Q(x) 當(dāng)用x=α和x=α2代入上式時，得到下面的方程組， m3α5＋m2α4+m1α3+Q1α+Q0=0 m3(α2)5+m2(α2)4+m1(α2)3+m0(α2)2+Q1α2+Q0=02/3/202318 經(jīng)過整理可以得到用矩陣表示的(6，4)RS碼的校驗方程： 求解方程組就可得到校驗符號： Q1=m3α5+m2α5+m1α0+m0α4 Q0=m3α+m2α3+m1α0+m0α3 在讀出時的校正子可按下式計算：2/3/202319[例16.3] 在例16.2中，如果K0=0，t=1，由式(16－2)導(dǎo)出的RS校驗碼生成多項式就為。注：前為K0=1（16－5）

根據(jù)多項式的運算，由(16－3)和(16－5)可以得到下面的方程組：方程中的αi也可看成符號的位置，此處i=0，1，…，5。

2/3/202320 求解方程組可以得到RS校驗碼的2個符號為Q1和Q0，（16-6） 假定mi為下列值： 代入(16－6)式可求得校驗符號： Q1=α6=101 Q0=α4=110信息符號m3=α0=001m2=α6=101m1=α3=011m0=α2=100校驗符號Q1=α6=101Q0=α4=110校正子s0=0s1=02/3/20232116.2.3RS碼的糾錯算法RS碼的錯誤糾正過程分三步：(1)計算校正子(syndrome)；(2)計算錯誤位置；(3)計算錯誤值。2/3/202322以例16.3為例介紹RS碼的糾錯算法。校正子使用下面的方程組來計算： 為簡單起見，假定存入光盤的信息符號m3、m2、m1、m0和由此產(chǎn)生的檢驗符號Q1、Q0均為0，讀出的符號為m3′、m2′、m1′、m0′、Q1′和Q0′。如果只有一個錯誤，假設(shè)錯誤的位置為αx，錯誤值為mx，那么可通過求解下面的方程組：

得知錯誤的位置和錯誤值。2/3/202323如果計算得到s0=α2和s1=α5，可求得αx=α3和mx=α2，說明m1出了錯，它的錯誤值是α2（見表）。校正后的m1=m1′＋mx，本例中m1=0。如果計算得到s0=0，而s1≠0，那基本可斷定至少有兩個錯誤如已知兩個錯誤明顯mx1和mx2的位置αx1和αx2，那么求解方程組： 就可知道這兩個錯誤值。2/3/20232416.3CIRC糾錯技術(shù)經(jīng)常遇到的兩種錯誤：隨機(jī)錯誤：由于隨機(jī)干擾造成的錯誤；特點是隨機(jī)的、孤立的，干擾過后再讀一次光盤，錯誤就可能消失。突發(fā)錯誤：連續(xù)多位出錯，或連續(xù)多個符號出錯；如盤片的劃傷、沾污或盤本身的缺陷都可能出現(xiàn)這種錯誤，一錯就錯一大片。2/3/20232516.3.1交插技術(shù)交插(interleaving)技術(shù)在光盤上記錄數(shù)據(jù)時，如果把本該連續(xù)存放的數(shù)據(jù)錯開放，那么當(dāng)出現(xiàn)一片錯誤時，這些錯誤就分散到各處，錯誤就容易得到糾正。 例如，3個(5，3)碼塊：B1=(a2，a1，a0，P1，P0)B2=(b2，b1，b0，Q1，Q0)B3=(c2，c1，c0，R1，R0)排成3行：a2 a1 a0 P1 P0b2 b1 b0 Q1 Q0c2 c1 c0 R1 R0連續(xù)排列a2a1a0

P1P0b2b1b0

Q1Q0c2c1c0

R1R02/3/202326一般來說，如果有r個(n，k)碼，排成r×n

矩陣，按列交插后存儲或傳送，讀出或接收時恢復(fù)成原來的排列，若(n，k)碼能糾正t個錯誤，那么這樣交插后就可以糾正rt個突發(fā)錯誤。交插排列：a2b2c2a1b1c1a0b0c0P1Q1R1P0Q0R0連續(xù)錯3個：a2b2c2a1b1c1a0XXXQ1R1P0Q0R0讀出后重新排列：a2a1a0XP0b2b1XQ1Q0c2c1XR1R0從這個例子中可以看到，對連續(xù)排列，每個碼塊中只能出現(xiàn)一個錯誤才能糾正。而交插記錄后，讀出的3個連續(xù)錯誤經(jīng)還原后可把它們分散到3個碼塊中，每個碼塊可以糾正1個錯誤，總計可以糾正3個連續(xù)的錯誤。2/3/20232716.3.2交叉交插(cross－interleaving)技術(shù)例子說明(1)用(5，3)碼編碼器C2生成的4個碼塊為:B1=(a2a1a0P1P0)B2=(b2b1b0Q1Q0)B3=(c2c1c0R1R0)B4=(d2d1d0S1S0)(2)交插后再用(6，4)碼編碼器C1生成5個碼塊為:a2 b2 c2 d2 T1 T0a1 b1 c1 d1 U1 U0a0 b0 c0 d0 V1 V0P1 Q1 R1 S1 W1 W0P0 Q0 R0 S0 X1 X02/3/202328(3)再交插，交插的碼塊數(shù)可以是2、3、4或5。以交插2個碼塊為例： a2 a1 b2 b1 c2 c1 d2 d1 T1 U1 T0 U0 a0 P1 b0 Q1 c0 R1 d0 S1 …(4)最后一個碼塊不配對，可以和下一個碼塊配對。這種編碼技術(shù)用了兩個編碼器C2和C1。C2對原碼塊進(jìn)行編碼得到(5，3)碼塊，交插后生成由4個符號組成的碼塊，然后再用(6，4)編碼器C1去編碼。2/3/202329F1幀(F1－Frame)：每6次采樣共24個符號構(gòu)成1幀。用一個稱為C2的編碼器對這24個符號產(chǎn)生4個Q校驗符號：Q0，Q1，Q2和Q3。24個聲音數(shù)據(jù)加上4個Q校驗符號共28個符號，用稱為C1編碼器對這28個符號產(chǎn)生4個P校驗符號：P0，P1，P2和P3。F2幀(F2－Frame)：28個符號加上4個P校驗符號共32個符號構(gòu)成的幀。F3幀(F3－Frame)：F2幀加上1個字節(jié)(即1個符號)的子碼共33個符號構(gòu)成的幀。延時交插執(zhí)行交插時不是交插包含有k個校驗符的碼塊，而是交插一個連續(xù)系列中的碼符。2/3/202330CD存儲器中的CIRC編碼器采用了4×F1幀的延時交插方案。1幀延時交插可糾正連續(xù)4×F1幀的突發(fā)錯誤。4×F2幀的延時交插可糾正連續(xù)16×F1幀突發(fā)錯誤，相當(dāng)于大約14×F3幀的突發(fā)錯誤。1×F3幀經(jīng)過EFM編碼后產(chǎn)生588位通道位。1位通道位的長度折合成0.277μm的光道長度。14×F3幀突發(fā)錯誤長度相當(dāng)于［(16×(24＋4))/33］×588×0.277≈2.2mm CIRC能糾正在2.2mm光道上連續(xù)存放的448個錯誤符號! 相當(dāng)于連續(xù)224個漢字錯誤可以得到糾正。2/3/20233116.4RSPC碼每個字s(n)由兩個字節(jié)B組成，一個稱為最高有效位字節(jié)MSB，另一個叫做最低有效位字節(jié)LSB。 第n個字由下面的字節(jié)組成，其中n=0，1，2，…，1169。 從字節(jié)12開始到字節(jié)2075共2064個字節(jié)組成的數(shù)據(jù)塊排列成24×43的矩陣，如圖16-02所示。2/3/202332

NP

0123

…

4142

000000010002………00410042

1004300440045………00840085HEADER

2008600870088………01270128+…

P

Q

用戶數(shù)據(jù)

＋MP22094609470948………09870988部分輔助數(shù)據(jù)

23098909900991………10301031

24103210331034

10731074P-校驗

25107510761077………11161117

26111811191120…1143

Q-校驗

27114411451146…1169

012…25

(ISO/IEC1049）圖16－02RSPC碼計算用數(shù)據(jù)陣列2/3/202333(1)P校驗符號用(26，24)RS碼產(chǎn)生 43列的每一列用矢量表示，記為Vp。每列有24個字節(jié)的數(shù)據(jù)再加2個字節(jié)的P校驗字節(jié)，用下式表示：其中：

Np=0,1,2,,42 Mp=0,1,2,,25s(43*24+Np)和s(43*25+Np)是P校驗字節(jié)；對這列字節(jié)計算得到的是兩個P校驗字節(jié)，稱為P校驗符號。2/3/202334

兩個P校驗字節(jié)加到24行和25行的對應(yīng)列上，這樣構(gòu)成了一個26×43的矩陣，并且滿足方程

Hp×Vp=0其中HP校驗矩陣為

2/3/202335(2)Q校驗符號用(45，43)RS碼產(chǎn)生增加P校驗字節(jié)之后得到了一個26×43矩陣，該矩陣的對角線元素重新排列后得到一個新的矩陣，其結(jié)構(gòu)如圖16-03(Q校驗符號計算用數(shù)據(jù)陣列)所示。

MQ

012

404142Q0Q10000000440088……06420686073011181144

1004300870131……06850729077311191145

2008601300147……07280772081611201146

3012901370217……07710815085911211147

4017202160260……08140858090211221148

22094609901034……04700514055811401166NQ23098910331077……05130557060111411167

24103210760002……05560600064411421168