第十六章錯(cuò)誤檢測(cè)和校正

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

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

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

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

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

6、16xxxxxxxGEDC：x24x31x16x23x8x15x0 x7字節(jié)號(hào)：206420652066206716.2 RS16.2 RS編碼和糾錯(cuò)算法編碼和糾錯(cuò)算法 一、一、GF(2GF(2m m) )域域RS(Reed-Solomon)碼是在伽羅華域(Galois Field，GF)中運(yùn)算的。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)式的特性是 得到的余式等于0。 )(112xPxm16.2 RS16.2 RS編碼和糾錯(cuò)算法編碼和糾錯(cuò)

7、算法 CD-ROM用來(lái)構(gòu)造GF(28)域的是 而GF(28)域中的本原元素為 = (0 0 0 0 0 0 1 0) 1)(2348xxxxxP16.2 RS16.2 RS編碼和糾錯(cuò)算法編碼和糾錯(cuò)算法 例例 構(gòu)造GF(23)域的本原多項(xiàng)式假定為 定義為P(x) = 0的根，即 31=0和 3 = 1GF(23)中的元素可計(jì)算如下：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編碼和糾錯(cuò)算法編碼和糾錯(cuò)算法GF(23)域元素二進(jìn)制對(duì)代碼 0 (000)0 (001)1 (010)2 (100)3 (011)4 (110)5 (111)6 (101)GF(23)域中元素與二進(jìn)制代碼對(duì)照表 16.2 RS16.2 RS編碼和糾錯(cuò)算法編碼和糾錯(cuò)算法糾錯(cuò)編碼運(yùn)算過(guò)程中，加、減、乘和除的運(yùn)算是在伽羅華域中進(jìn)行?，F(xiàn)仍以GF(23)域中運(yùn)算為例：加法例：03 = 001011 = 010 = 1減法例：與加法相同乘法例：54 = (54) mod7 = 2除法例：5/3 = 2 3/5 = 2 = (27) = 5取對(duì)數(shù)：log(5)

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

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

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

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

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

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

15、果把本該連續(xù)存放的數(shù)據(jù)錯(cuò)開(kāi)放，那么當(dāng)出現(xiàn)一片錯(cuò)誤時(shí)，這些錯(cuò)誤就分散到各處數(shù)據(jù)中，錯(cuò)誤就容易得到糾正，這種技術(shù)就稱為交插(interleaving)技術(shù)。 16.3 CIRC16.3 CIRC糾錯(cuò)技術(shù)糾錯(cuò)技術(shù)3個(gè)(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ù)錯(cuò)3個(gè)： 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糾錯(cuò)技術(shù)糾錯(cuò)技術(shù) 可以看到，對(duì)連續(xù)排列(5，3)碼塊 ，每個(gè)碼塊中只能出現(xiàn)一個(gè)錯(cuò)誤才能糾正。而交插記錄后，讀出的3個(gè)連續(xù)錯(cuò)誤經(jīng)還原后可把它們分散到3個(gè)碼塊中，每個(gè)碼塊可以糾正1個(gè)錯(cuò)誤，總計(jì)可以糾正3個(gè)連續(xù)的錯(cuò)誤。 一般來(lái)說(shuō)，如果有r個(gè)(n，k)碼，排成rn矩陣，按列交插后存儲(chǔ)或傳送，讀出或接收時(shí)恢復(fù)成原來(lái)的排列，若(n，k)碼能糾正t個(gè)錯(cuò)誤，那么這樣交插后就可以糾正rt個(gè)突發(fā)錯(cuò)誤。 16.3 CIRC16.

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

18、插，交插的碼塊數(shù)可以是2、3、4或5。以交插2個(gè)碼塊為例： (4) 最后一個(gè)碼塊不配對(duì)，可以和下一個(gè)碼塊配對(duì)。 a2a1b2b1c2c1d2d1T1U1T0U0a0P1b0Q1c0R1d0S116.3 CIRC16.3 CIRC糾錯(cuò)技術(shù)糾錯(cuò)技術(shù) 這種編碼技術(shù)用了兩個(gè)編碼器C2和C1。C2對(duì)原碼塊進(jìn)行編碼得到(5，3)碼塊，交插后生成由4個(gè)符號(hào)組成的碼塊，碼塊中的符號(hào)是交叉存放的，然后再用(6，4)編碼器C1去編碼。 設(shè)連續(xù)系列碼符中，每n個(gè)碼符構(gòu)成一個(gè)碼塊，其中第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糾錯(cuò)技術(shù)糾錯(cuò)技術(shù)16.3 CIRC16.3 CIRC糾錯(cuò)技術(shù)糾錯(cuò)技術(shù)一種延時(shí)方案可考慮為每高一行，多延時(shí)一個(gè)碼符，那末采用這種方案延時(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糾錯(cuò)技術(shù)糾錯(cuò)技術(shù) 這樣延時(shí)后一個(gè)碼塊中的碼符分布在斜線上，所以這個(gè)陣列的開(kāi)始部分和最后部分缺少碼符。對(duì)沒(méi)有碼符的地方應(yīng)填充碼符，以保證構(gòu)成完整的陣列。一般可用0來(lái)填充。 經(jīng)過(guò)這樣延時(shí)交插后，每個(gè)碼塊中的連續(xù)碼相隔開(kāi)一個(gè)碼塊。如果把碼塊看成一幀，那末就稱這種延時(shí)交插為延時(shí)一幀交插。如果每個(gè)碼塊可以糾正單個(gè)錯(cuò)誤，那末延時(shí)一幀交插可以糾正一幀連續(xù)的突發(fā)錯(cuò)誤。根據(jù)需要可以

21、采延時(shí)d(d1)幀交插，這樣可以這樣可以糾正更長(zhǎng)的突發(fā)錯(cuò)誤。16.3 CIRC16.3 CIRC糾錯(cuò)技術(shù)糾錯(cuò)技術(shù)16.3 CIRC16.3 CIRC糾錯(cuò)技術(shù)糾錯(cuò)技術(shù)在CD-DA中每次采樣有兩個(gè)16比特的樣本，一個(gè)來(lái)自左聲道，一個(gè)來(lái)自右聲道，每個(gè)樣本用兩個(gè)GF(28)域中的符號(hào)表示，因此每次采樣共有4個(gè)符號(hào)。 每6次采樣共24個(gè)符號(hào)構(gòu)成1幀，稱為F1幀(F1Frame)。用一個(gè)稱為C2的編碼器對(duì)這24個(gè)符號(hào)產(chǎn)生4個(gè)Q Q校驗(yàn)校驗(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 P校驗(yàn)校驗(yàn)符號(hào)： P0，P1，P2和P3。 16

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