第十六章錯誤檢測和校正

1、第第十六十六章章 錯誤檢測和校正錯誤檢測和校正 16.1 CRC錯誤檢測原理 16.2 RS編碼和糾錯算法 16.3 CIRC糾錯技術(shù) 16.4 RSPC碼 本章要點本章要點由于激光盤存儲器存在較大的誤碼率，因此，它采用了功能強大的錯誤碼檢測和糾正措施。采用的具體對策歸納起來有三種：(1) 錯誤檢測：采用CRC(Cyclic Redundancy Code)檢測讀出數(shù)據(jù)是否有錯。(2) 錯誤校正碼： 采用里德索洛蒙碼(ReedSolomon Code)，簡稱為RS碼，進行糾錯。 (3) 交叉交插里德索洛蒙碼CIRC(Cross Interleaved ReedSolomon Code), 在用

2、RS編譯碼前后，對數(shù)據(jù)進行交插處理和交叉處理。 一個二進制數(shù)字串可以用一個多項式表示。如二進制數(shù)字序列10101111，用多項式可以表示成：= 式中的xi表示代碼的位置，或某個二進制數(shù)位的位置，xi前面的系數(shù)ai表示二進制碼的值，取值是0或1。 0011223344556677aaaaaaaa)(xxxxxxxxxM112357xxxxx16.1 CRC錯誤檢測原理錯誤檢測原理16.1 CRC16.1 CRC錯誤檢測原理錯誤檢測原理模2多項式代數(shù)運算中定義的運算規(guī)則有：模2多項式的加減法 iiiixxxx1101116.1 CRC16.1 CRC錯誤檢測原理錯誤檢測原理模2運算的多項式除法：

3、16.1 CRC16.1 CRC錯誤檢測原理錯誤檢測原理對于K位二進制串，假設其對應的多項式為M(x)。為了檢測該二進制串在存儲或傳輸過程中是否出錯，需要增加一個(n-k)的二進制串作為校驗碼，形成如下所示的二進制串： 16.1 CRC16.1 CRC錯誤檢測原理錯誤檢測原理 使用一個校驗碼生成多項式G(x)去模2除代碼多項式xn-kM(x) 因為模2多項式的加法和減法運算結(jié)果相同，所以又可把上式寫成： )()()()()(xGxRxQxGxMxkn)()()()(xRxGxQxMxkn)()()()(xGxQxRxMxkn 是能夠被校驗碼生成多項式G(x)除盡的，即它的余項為0。 因此檢驗位

4、組成的多項式是xn-kM(x)除以G(x)后的余數(shù)。 16.1 CRC16.1 CRC錯誤檢測原理錯誤檢測原理)()(xRxMxkn16.1 CRC16.1 CRC錯誤檢測原理錯誤檢測原理例：生成多項式： 即G(x)=10001000000100001(B) =11021(H) 假定要寫到盤上的信息代碼為M(x)=4D6F746F (H) x16M(x)= 4D6F746F0000(H) 1)(51216xxxxG16.1 CRC16.1 CRC錯誤檢測原理錯誤檢測原理16.1 CRC16.1 CRC錯誤檢測原理錯誤檢測原理因此寫到盤上的信息代碼和CRC碼是4D6F746F B994,從盤上把

5、這塊數(shù)據(jù)讀出時，用同樣的CRC碼生成多項式去除這塊數(shù)據(jù)，相除后得到的兩種可能結(jié)果是：余數(shù)為0，表示數(shù)據(jù)沒有出現(xiàn)錯誤；余數(shù)不為0，表示數(shù)據(jù)有錯。 4D6F746FB994信息代碼CRC碼16.1 CRC16.1 CRC錯誤檢測原理錯誤檢測原理CD-ROM扇區(qū)方式01中，有一個4字節(jié)共32位的EDC字域，它就是用來存放CRC碼。不過，CD-ROM采用的CRC校驗碼生成多項式與軟磁盤采用的生成多項式不同，它是一個32階的多項式： 計算CRC碼時用的數(shù)據(jù)塊是從扇區(qū)的開頭到用戶數(shù)據(jù)區(qū)結(jié)束為止的數(shù)據(jù)字節(jié)，即字節(jié)02063共2064個字節(jié)。在EDC中存放的CRC碼的次序如下： ) 1)(1()(216215

6、16xxxxxxxGEDC：x24x31x16x23x8x15x0 x7字節(jié)號：206420652066206716.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法 一、一、GF(2GF(2m m) )域域RS(Reed-Solomon)碼是在伽羅華域(Galois Field，GF)中運算的。CD-ROM中的數(shù)據(jù)、地址、校驗碼等都可以看成是屬于GF(2m) = GF(28)中的元素或稱符號。GF(28)表示域中有256個元素，除0，1之外的254個元素由本原多項式P(x)生成。 本原多項式的特性是 得到的余式等于0。 )(112xPxm16.2 RS16.2 RS編碼和糾錯算法編碼和糾錯

7、算法 CD-ROM用來構(gòu)造GF(28)域的是 而GF(28)域中的本原元素為 = (0 0 0 0 0 0 1 0) 1)(2348xxxxxP16.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法 例例 構(gòu)造GF(23)域的本原多項式假定為 定義為P(x) = 0的根，即 31=0和 3 = 1GF(23)中的元素可計算如下：1)(3xxxP 0 mod(31) = 00mod(31) = 0 = 11mod(31) = 12mod(31) = 23 mod(31) = 14 mod(31) = 25 mod(31) = 2116 mod(31) = 217 mod(31) = 08 mo

8、d(31) = 116.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法GF(23)域元素二進制對代碼 0 (000)0 (001)1 (010)2 (100)3 (011)4 (110)5 (111)6 (101)GF(23)域中元素與二進制代碼對照表 16.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法糾錯編碼運算過程中，加、減、乘和除的運算是在伽羅華域中進行。現(xiàn)仍以GF(23)域中運算為例：加法例：03 = 001011 = 010 = 1減法例：與加法相同乘法例：54 = (54) mod7 = 2除法例：5/3 = 2 3/5 = 2 = (27) = 5取對數(shù)：log(5)

9、= 5這些運算的結(jié)果仍然在GF(23)域中。 16.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法二、二、RSRS的編碼算法的編碼算法 在GF(2m)域中，能糾正t個錯誤的符號(n，k)RS的含義如下：m 表示符號的大小，如m=8表示符號 由8位二進制數(shù)組成n表示碼塊長度 k 表示碼塊中的信息長度 K=nk = 2t表示校驗碼的符號數(shù) t 表示能夠糾正的錯誤數(shù)目 16.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法對一個信息碼符多項式M(x)，RS校驗碼生成多項式的一般形式為其中，K0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)2t (t為要校正的錯誤符號數(shù))。 10)()

10、(0KiiKxxG16.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法 例例16.2 16.2 設在GF(23)域中的元素對應表如表16 01所示。假設(6，4)RS碼中的4個信息符號為m3、m2、m1和m0，信息碼符多項式為并假設RS校驗碼的2個符號為Q1和Q0，的剩余多項式為當K0 = 1，t = 1，RS校驗碼生成多項式就為： 012233mmmm)(xxxxM01QQ)(xxR)()()(2100 xxxxGKiiK16.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法m3x5m2x4m1x3m0 x2Q1xQ0 = (x ) (x2)Q(x)當x = 和 2 時有方程組：求解方

11、程組就可得到校驗符號： 16.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法在讀出時的校正子為 即判斷s0和s1是否為0。16.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法 例例16.3 16.3 在例16.2中，如果K0 = 0，t = 1，由式(132)導出的RS校驗碼生成多項式就為：因此有：m3x5m2x4m1x3m0 x2Q1xQ0 = (x 0) (x)Q(x)得到方程組：)()()(10100 xxxxGKiiK求解方程組可以得到RS校驗碼的2個符號為Q1和Q0， 如果mi取下列值m3 = 0 = 001m2 = 6 = 101m1 = 3 = 011m0 = 2 = 1

12、0016.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法可求得校驗符號：Q1 = 6 = 101Q0 = 4 = 110 16.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法三、三、RSRS碼的糾錯算法碼的糾錯算法 RS碼的錯誤糾正過程分三步： (1)計算校正子(syndrome)；(2)計算錯誤位置；(3)計算錯誤值。 以例16.3為例介紹RS碼的糾錯算法。校正子使用下面的方程組來計算：假定假定存入光盤的信息符號m3、m2、m1、m0和由此產(chǎn)生的檢驗符號Q1、Q0，而讀出的符號為m3、m2、m1、m0、Q1和Q0。 如果計算得到的s0和s1不全為0，則說明有差錯。 16.2 RS16

13、.2 RS編碼和糾錯算法編碼和糾錯算法16.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法如果只有一個錯誤，則問題比較簡單。假設錯誤的位置為x，錯誤值為mx，則可通過求解下面的方程組： 得知錯誤的位置和錯誤值。例如：如果計算得到s0 = 2和s1 = 5，可求得x = 3和mx = 2，說明m1出了錯，它的錯誤值是2。校正后的m1 = m1mx ，本例中m1=0。 16.2 RS16.2 RS編碼和糾錯算法編碼和糾錯算法如果計算得到s0 = 0，而s10，那基本可斷定至少有兩個錯誤，當然出現(xiàn)兩個以上的錯誤不一定都是s0 = 0和s10。如果出現(xiàn)兩個錯誤，而又能設法找到出錯的位置，那么這兩個

14、錯誤也可以糾正。如已知兩個錯誤mx1和mx2的位置x1和x2，那么求解方程組：就可知道這兩個錯誤值。 16.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù) 光盤存儲器和其它的存儲器一樣，經(jīng)常遇到的錯誤有兩種。隨機錯誤：干擾產(chǎn)生突發(fā)錯誤 ：盤片本身 CIRC(C Cross I Interleaved R Reed S Solomon)糾錯碼綜合了交插、延時交插、交叉交插等技術(shù)，不僅能糾隨機錯誤，而且對糾突發(fā)錯誤特別有效。 16.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù)一、一、交插技術(shù)交插技術(shù) 對糾錯來說，分散的錯誤比較容易得到糾正，但出現(xiàn)一長串的錯誤時，就較麻煩。 在光盤上記錄數(shù)據(jù)時，如

15、果把本該連續(xù)存放的數(shù)據(jù)錯開放，那么當出現(xiàn)一片錯誤時，這些錯誤就分散到各處數(shù)據(jù)中，錯誤就容易得到糾正，這種技術(shù)就稱為交插(interleaving)技術(shù)。 16.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù)3個(5，3)碼塊： B1 = (a2，a1，a0，P1，P0)B2 = (b2，b1，b0，Q1，Q0)B3 = (c2，c1，c0，R1，R0)連續(xù)排列：a2 a1 a0 P1 P0 b2 b1 b0 Q1 Q0 c2 c1 c0 R1 R0 交插排列： a2 b2 c2 a1b1 c1 a0 b0 c0 P1 Q1 R1 P0 Q0 R0 連續(xù)錯3個： a2 b2 c2 a1b1 c1

16、 a0 X X X X X X Q1 R1 P0 Q0 R0 讀出后重新排列： a2 a1 a0 X XP0b2b1X XQ1Q0c2c1X XR1R0 16.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù) 可以看到，對連續(xù)排列(5，3)碼塊 ，每個碼塊中只能出現(xiàn)一個錯誤才能糾正。而交插記錄后，讀出的3個連續(xù)錯誤經(jīng)還原后可把它們分散到3個碼塊中，每個碼塊可以糾正1個錯誤，總計可以糾正3個連續(xù)的錯誤。 一般來說，如果有r個(n，k)碼，排成rn矩陣，按列交插后存儲或傳送，讀出或接收時恢復成原來的排列，若(n，k)碼能糾正t個錯誤，那么這樣交插后就可以糾正rt個突發(fā)錯誤。 16.3 CIRC16.

17、3 CIRC糾錯技術(shù)糾錯技術(shù)二、交叉交插技術(shù)二、交叉交插技術(shù)(crossinterleaving) 以簡單的例子說明這種技術(shù)思想 ：(1) 用(5，3)碼編碼器C2生成的4個碼塊為: B1=(a2a1a0P1P0)B2=(b2b1b0Q1Q0)B3=(c2c1c0R1R0)B4=(d2d1d0S1S0)16.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù) (2) 交插后再用(6，4)碼編碼器C1生成5個碼塊為: a2b2c2d2T1T0a1b1c1d1U1U0a0b0c0d0V1V0P1Q1R1S1W1W0P0Q0R0S0X1X016.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù)(3) 再交

18、插，交插的碼塊數(shù)可以是2、3、4或5。以交插2個碼塊為例： (4) 最后一個碼塊不配對，可以和下一個碼塊配對。 a2a1b2b1c2c1d2d1T1U1T0U0a0P1b0Q1c0R1d0S116.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù) 這種編碼技術(shù)用了兩個編碼器C2和C1。C2對原碼塊進行編碼得到(5，3)碼塊，交插后生成由4個符號組成的碼塊，碼塊中的符號是交叉存放的，然后再用(6，4)編碼器C1去編碼。 設連續(xù)系列碼符中，每n個碼符構(gòu)成一個碼塊，其中第i塊碼符記為： Ci=（Ci,1, Ci,2, Ci,n),(in)交插陣列為 Ci-(n-1),1 Ci-2,1 Ci-1,1 C

19、i,1 Ci+1,1 Ci-(n-1),2 Ci-2,2 Ci-1,2 Ci,2 Ci+1,2 . . . . . . . . . . . . . . . Ci-(n-1),n-1 Ci-2,n-1 Ci-1,n-1 Ci,n-1 Ci+1,n-1 Ci-(n-1),n Ci-2,n Ci-1,n Ci,n Ci+1,n 16.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù)16.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù)一種延時方案可考慮為每高一行，多延時一個碼符，那末采用這種方案延時后的陣列為 Ci-(n-1),1 Ci-2,1 Ci-1,1 Ci,1 Ci+1,1 Ci-(n-1),2

20、 Ci-2,2 Ci-1,2 Ci,2 Ci+1,2 . . . . . . . . . . . . Ci-(n-1),n-1 Ci-(n-2),n-1 Ci-(n-1),n Ci-(n-2),n 16.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù) 這樣延時后一個碼塊中的碼符分布在斜線上，所以這個陣列的開始部分和最后部分缺少碼符。對沒有碼符的地方應填充碼符，以保證構(gòu)成完整的陣列。一般可用0來填充。 經(jīng)過這樣延時交插后，每個碼塊中的連續(xù)碼相隔開一個碼塊。如果把碼塊看成一幀，那末就稱這種延時交插為延時一幀交插。如果每個碼塊可以糾正單個錯誤，那末延時一幀交插可以糾正一幀連續(xù)的突發(fā)錯誤。根據(jù)需要可以

21、采延時d(d1)幀交插，這樣可以這樣可以糾正更長的突發(fā)錯誤。16.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù)16.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù)在CD-DA中每次采樣有兩個16比特的樣本，一個來自左聲道，一個來自右聲道，每個樣本用兩個GF(28)域中的符號表示，因此每次采樣共有4個符號。 每6次采樣共24個符號構(gòu)成1幀，稱為F1幀(F1Frame)。用一個稱為C2的編碼器對這24個符號產(chǎn)生4個Q Q校驗校驗符號： Q0，Q1，Q2和Q3。 24個聲音數(shù)據(jù)加上4個Q校驗符號共28個符號，用稱為C1編碼器對這28個符號產(chǎn)生4個P P校驗校驗符號： P0，P1，P2和P3。 16

22、.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù) 28個符號加上4個P校驗符號共32個符號構(gòu)成的幀稱為F2幀(F2Frame)。F2幀加上1個字節(jié)(即1個符號)的子碼共33個符號構(gòu)成的幀稱為F3幀(F3Frame)。 16.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù) 在實際應用中，執(zhí)行交插時不是交插包含有k個校驗符的碼塊，而是交插一個連續(xù)系列中的碼符，這種交插技術(shù)稱為延時交插。延時交插之后還可用交叉技術(shù)，稱為延時交叉交插技術(shù)。 例如CD存儲器中的CIRC編碼器采用了4F1幀的延時交插方案。 1幀延時交插可糾正連續(xù)4F1幀的突發(fā)錯誤。4F2幀的延時交插可糾正連續(xù)16F2幀突發(fā)錯誤，相當于大約14F3幀的突發(fā)錯誤。1F3幀經(jīng)過EFM編碼后產(chǎn)生588位通道位。1位通道位的長度折合成0.277m的光道長度。14F3幀突發(fā)錯誤長度相當于 (16(244)/335880.2772.2 mm換句話說，CIRC能糾正在2.2 mm光道上連續(xù)存放的448個錯誤符號! 相當于連續(xù)224個漢字錯誤可以得到糾正。16.3 CIRC16.3 CIRC糾錯技術(shù)糾錯技術(shù)16.4 RSPC碼碼 CD-ROM扇區(qū)中的ECC碼采用GF(28)域上的RS