錯(cuò)誤檢測(cè)和校正詳解演示文稿

錯(cuò)誤檢測(cè)和校正詳解演示文稿第一頁(yè)，共三十六頁(yè)。2/5/20231優(yōu)選錯(cuò)誤檢測(cè)和校正第二頁(yè)，共三十六頁(yè)。2/5/20232在模2多項(xiàng)式代數(shù)運(yùn)算中定義的運(yùn)算規(guī)則有：例如，模2多項(xiàng)式的加法和減法：****結(jié)論：對(duì)于模2運(yùn)算來(lái)說(shuō)，代碼多項(xiàng)式的加法和減法運(yùn)算所得的結(jié)果相同。在做代碼多項(xiàng)式的減法時(shí)，可用做加法來(lái)代替做減法。第三頁(yè)，共三十六頁(yè)。2/5/20233代碼多項(xiàng)式的除法可按長(zhǎng)除法做。例如第四頁(yè)，共三十六頁(yè)。2/5/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)第五頁(yè)，共三十六頁(yè)。2/5/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。

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

73

9第八頁(yè)，共三十六頁(yè)。2/5/20238 CD-ROM中也采用了相同的CRC檢錯(cuò)。CD-ROM扇區(qū)方式01中，有一個(gè)4字節(jié)共32位的EDC字域，它就是用來(lái)存放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é)號(hào)：2064206520662067第九頁(yè)，共三十六頁(yè)。2/5/2023916.2RS編碼和糾錯(cuò)算法16.2.1.GF(2m)域****伽羅華域(GaloisField，GF)

CD-ROM中的數(shù)據(jù)、地址、校驗(yàn)碼等都可以看成是屬于GF(2m)=GF(28)中的元素或稱符號(hào)。GF(28)表示域中有256個(gè)元素，除0，1之外的254個(gè)元素由本原多項(xiàng)式P(x)生成。本原多項(xiàng)式P(x)的特性是 得到的余式等于0。CD-ROM用來(lái)構(gòu)造GF(28)域的是 P(x)=x8+x4+x3+x2+1而GF(28)域中的本原元素為: α＝（00000010）第十頁(yè)，共三十六頁(yè)。2/5/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)=？？？第十一頁(yè)，共三十六頁(yè)。2/5/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ì)算如下：

第十二頁(yè)，共三十六頁(yè)。2/5/202312表16-01GF(23)域中與二進(jìn)制代碼對(duì)照表,P(x)=x3+x+1GF(23)域元素二進(jìn)制對(duì)代碼0(000)α0

(001)α1

(010)α2

(100)α3

(011)α4

(110)α5

(111)α6

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

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

的剩余多項(xiàng)式為 R(x)=Q1x+Q0這個(gè)多項(xiàng)式的階次比G(x)的階次少一階。第十七頁(yè)，共三十六頁(yè)。2/5/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=0第十八頁(yè)，共三十六頁(yè)。2/5/202318 經(jīng)過(guò)整理可以得到用矩陣表示的(6，4)RS碼的校驗(yàn)方程： 求解方程組就可得到校驗(yàn)符號(hào)： Q1=m3α5+m2α5+m1α0+m0α4 Q0=m3α+m2α3+m1α0+m0α3 在讀出時(shí)的校正子可按下式計(jì)算：第十九頁(yè)，共三十六頁(yè)。2/5/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也可看成符號(hào)的位置，此處i=0，1，…，5。

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

得知錯(cuò)誤的位置和錯(cuò)誤值。第二十三頁(yè)，共三十六頁(yè)。2/5/202323如果計(jì)算得到s0=α2和s1=α5，可求得αx=α3和mx=α2，說(shuō)明m1出了錯(cuò)，它的錯(cuò)誤值是α2（見(jiàn)表）。校正后的m1=m1′＋mx，本例中m1=0。如果計(jì)算得到s0=0，而s1≠0，那基本可斷定至少有兩個(gè)錯(cuò)誤如已知兩個(gè)錯(cuò)誤明顯mx1和mx2的位置αx1和αx2，那么求解方程組： 就可知道這兩個(gè)錯(cuò)誤值。第二十四頁(yè)，共三十六頁(yè)。2/5/20232416.3CIRC糾錯(cuò)技術(shù)經(jīng)常遇到的兩種錯(cuò)誤：隨機(jī)錯(cuò)誤：由于隨機(jī)干擾造成的錯(cuò)誤；特點(diǎn)是隨機(jī)的、孤立的，干擾過(guò)后再讀一次光盤，錯(cuò)誤就可能消失。突發(fā)錯(cuò)誤：連續(xù)多位出錯(cuò)，或連續(xù)多個(gè)符號(hào)出錯(cuò)；如盤片的劃傷、沾污或盤本身的缺陷都可能出現(xiàn)這種錯(cuò)誤，一錯(cuò)就錯(cuò)一大片。第二十五頁(yè)，共三十六頁(yè)。2/5/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

R1R0第二十六頁(yè)，共三十六頁(yè)。2/5/202326一般來(lái)說(shuō)，如果有r個(gè)(n，k)碼，排成r×n

矩陣，按列交插后存儲(chǔ)或傳送，讀出或接收時(shí)恢復(fù)成原來(lái)的排列，若(n，k)碼能糾正t個(gè)錯(cuò)誤，那么這樣交插后就可以糾正rt個(gè)突發(fā)錯(cuò)誤。交插排列：a2b2c2a1b1c1a0b0c0P1Q1R1P0Q0R0連續(xù)錯(cuò)3個(gè)：a2b2c2a1b1c1a0XXXQ1R1P0Q0R0讀出后重新排列：a2a1a0XP0b2b1XQ1Q0c2c1XR1R0從這個(gè)例子中可以看到，對(duì)連續(xù)排列，每個(gè)碼塊中只能出現(xiàn)一個(gè)錯(cuò)誤才能糾正。而交插記錄后，讀出的3個(gè)連續(xù)錯(cuò)誤經(jīng)還原后可把它們分散到3個(gè)碼塊中，每個(gè)碼塊可以糾正1個(gè)錯(cuò)誤，總計(jì)可以糾正3個(gè)連續(xù)的錯(cuò)誤。第二十七頁(yè)，共三十六頁(yè)。2/5/20232716.3.2交叉交插(cross－interleaving)技術(shù)例子說(shuō)明(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 X0第二十八頁(yè)，共三十六頁(yè)。2/5/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è)碼塊不配對(duì)，可以和下一個(gè)碼塊配對(duì)。這種編碼技術(shù)用了兩個(gè)編碼器C2和C1。C2對(duì)原碼塊進(jìn)行編碼得到(5，3)碼塊，交插后生成由4個(gè)符號(hào)組成的碼塊，然后再用(6，4)編碼器C1去編碼。第二十九頁(yè)，共三十六頁(yè)。2/5/202329F1幀(F1－Frame)：每6次采樣共24個(gè)符號(hào)構(gòu)成1幀。用一個(gè)稱為C2的編碼器對(duì)這24個(gè)符號(hào)產(chǎn)生4個(gè)Q校驗(yàn)符號(hào)：Q0，Q1，Q2和Q3。24個(gè)聲音數(shù)據(jù)加上4個(gè)Q校驗(yàn)符號(hào)共28個(gè)符號(hào)，用稱為C1編碼器對(duì)這28個(gè)符號(hào)產(chǎn)生4個(gè)P校驗(yàn)符號(hào)：P0，P1，P2和P3。F2幀(F2－Frame)：28個(gè)符號(hào)加上4個(gè)P校驗(yàn)符號(hào)共32個(gè)符號(hào)構(gòu)成的幀。F3幀(F3－Frame)：F2幀加上1個(gè)字節(jié)(即1個(gè)符號(hào))的子碼共33個(gè)符號(hào)構(gòu)成的幀。延時(shí)交插執(zhí)行交插時(shí)不是交插包含有k個(gè)校驗(yàn)符的碼塊，而是交插一個(gè)連續(xù)系列中的碼符。第三十頁(yè)，共三十六頁(yè)。2/5/202330CD存儲(chǔ)器中的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)過(guò)EFM編碼后產(chǎn)生588位通道位。1位通道位的長(zhǎng)度折合成0.277μm的光道長(zhǎng)度。14×F3幀突發(fā)錯(cuò)誤長(zhǎng)度相當(dāng)于［(16×(24＋4))/33］×588×0.277≈2.2mm CIRC能糾正在2.2mm光道上連續(xù)存放的448個(gè)錯(cuò)誤符號(hào)! 相當(dāng)于連續(xù)224個(gè)漢字錯(cuò)誤可以得到糾正。第三十一頁(yè)，共三十六頁(yè)。2/5/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所示。第三十二頁(yè)，共三十六頁(yè)。2/5/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ù)陣列第三十三頁(yè)，共三十六頁(yè)。2/5/202333(1)P校驗(yàn)符號(hào)用(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=