第16章錯(cuò)誤檢測和校正

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

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

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

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

73

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

CD-ROM中的數(shù)據(jù)、地址、校驗(yàn)碼等都可以看成是屬于GF(2m)=GF(28)中的元素或稱符號。GF(28)表示域中有256個(gè)元素，除0，1之外的254個(gè)元素由本原多項(xiàng)式P(x)生成。本原多項(xiàng)式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)域的本原多項(xiàng)式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)中的元素可計(jì)算如下：

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

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

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

=(x－α)(x－α2)Q(x) 當(dāng)用x=α和x=α2代入上式時(shí)，得到下面的方程組， 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碼的校驗(yàn)方程： 求解方程組就可得到校驗(yàn)符號： Q1=m3α5+m2α5+m1α0+m0α4 Q0=m3α+m2α3+m1α0+m0α3 在讀出時(shí)的校正子可按下式計(jì)算：2/3/202319[例16.3] 在例16.2中，如果K0=0，t=1，由式(16－2)導(dǎo)出的RS校驗(yàn)碼生成多項(xiàng)式就為。注：前為K0=1（16－5）

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

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

得知錯(cuò)誤的位置和錯(cuò)誤值。2/3/202323如果計(jì)算得到s0=α2和s1=α5，可求得αx=α3和mx=α2，說明m1出了錯(cuò)，它的錯(cuò)誤值是α2（見表）。校正后的m1=m1′＋mx，本例中m1=0。如果計(jì)算得到s0=0，而s1≠0，那基本可斷定至少有兩個(gè)錯(cuò)誤如已知兩個(gè)錯(cuò)誤明顯mx1和mx2的位置αx1和αx2，那么求解方程組： 就可知道這兩個(gè)錯(cuò)誤值。2/3/20232416.3CIRC糾錯(cuò)技術(shù)經(jīng)常遇到的兩種錯(cuò)誤：隨機(jī)錯(cuò)誤：由于隨機(jī)干擾造成的錯(cuò)誤；特點(diǎn)是隨機(jī)的、孤立的，干擾過后再讀一次光盤，錯(cuò)誤就可能消失。突發(fā)錯(cuò)誤：連續(xù)多位出錯(cuò)，或連續(xù)多個(gè)符號出錯(cuò)；如盤片的劃傷、沾污或盤本身的缺陷都可能出現(xiàn)這種錯(cuò)誤，一錯(cuò)就錯(cuò)一大片。2/3/20232516.3.1交插技術(shù)交插(interleaving)技術(shù)在光盤上記錄數(shù)據(jù)時(shí)，如果把本該連續(xù)存放的數(shù)據(jù)錯(cuò)開放，那么當(dāng)出現(xiàn)一片錯(cuò)誤時(shí)，這些錯(cuò)誤就分散到各處，錯(cuò)誤就容易得到糾正。 例如，3個(gè)(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個(gè)(n，k)碼，排成r×n

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

25107510761077………11161117

26111811191120…1143

Q-校驗(yàn)

27114411451146…1169

012…25

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

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

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

Hp×Vp=0其中HP校驗(yàn)矩陣為

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

MQ

012

404142Q0Q10000000440088……06420686073011181144

1004300870131……06850729077311191145

2008601300147……07280772081611201146

3012901370217……07710815085911211147

4017202160260……08140858090211221148

22094609901034……04700514055811401166NQ23098910331077……05130557060111411167

24103210760002……05560600064411421168