光盤、磁盤和磁帶一類的數(shù)據(jù)記錄媒體一樣,，由于盤的制作材料的性能,、盤制造生產(chǎn)技術(shù)水平的限制、驅(qū)動(dòng)器的性能以及使用不當(dāng)?shù)戎T多原因,，從盤上讀出的數(shù)據(jù)不可能完全正確,。據(jù)有關(guān)廠家的測試和統(tǒng)計(jì)，一片未使用過的只讀光盤,，某原始誤碼率約為3×10^－4,；沾有指紋的盤的誤碼率約為6×10^－4；有傷痕的盤的誤碼率約為5×10^－３,。針對這種情況,，激光盤存儲(chǔ)器采用了功能強(qiáng)大的錯(cuò)誤碼檢測和糾正措施。采用的具體對策歸納起來有三種：
　　(1) 錯(cuò)誤檢測：采用CRC(Cyclic Redundancy Code)檢測讀出數(shù)據(jù)是否有錯(cuò),。
　　(2) 錯(cuò)誤校正碼： 采用里德－索洛蒙碼(Reed－Solomon Code),，簡稱為RS碼,，進(jìn)行糾錯(cuò)。RS碼被認(rèn)為是性能很好的糾錯(cuò)碼,。
　　(3) 交叉交插里德－索洛蒙碼CIRC(Cross Interleaved Reed－Solomon Code), 這個(gè)碼的含義可理解為在用RS編譯碼前后,，對數(shù)據(jù)進(jìn)行交插處理和交叉處理。
　　對這些碼的理論分析和計(jì)算有許多專著作了詳盡的深入論述,，對不需要開發(fā)糾錯(cuò)技術(shù)的讀者僅需要了解錯(cuò)誤檢測和校正的一些基本概念即可,。

13.1 CRC錯(cuò)誤檢測原理

　　在糾錯(cuò)編碼代數(shù)中，把以二進(jìn)制數(shù)字表示的一個(gè)數(shù)據(jù)系列看成一個(gè)多項(xiàng)式,。例如,，二進(jìn)制數(shù)字序列10101111，用多項(xiàng)式可以表示成：
　　　　M(x) = a₇x⁷ + a₆x⁶ + a₅x⁵ + a₄x⁴ + a₃x³ + a₂x² + a₁x¹ + a₀x⁰
　　　　　　 = x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x¹ + 1
式中的xⁱ表示代碼的位置,，或某個(gè)二進(jìn)制數(shù)位的位置,，xⁱ前面的系數(shù)a_i表示碼的值。若a_i是一位二進(jìn)制代碼,，則取值是0或1,。M(x)稱為信息代碼多項(xiàng)式。
　　在模2多項(xiàng)式代數(shù)運(yùn)算中定義的運(yùn)算規(guī)則有：
　　　　1xⁱ + 1xⁱ = 0
　　　　-1xⁱ = 1xⁱ
　　例如,，模2多項(xiàng)式的加法和減法：
　　　　
　　從這兩個(gè)例子中可以看到,，對于模2運(yùn)算來說，代碼多項(xiàng)式的加法和減法運(yùn)算所得的結(jié)果相同,。所以在做代碼多項(xiàng)式的減法時(shí),，可用做加法來代替做減法。
　　代碼多項(xiàng)式的除法可按長除法做,。例如：
　　　　

　　如果一個(gè)k位的二進(jìn)制信息代碼多項(xiàng)式為 M(x)，再增加(n－k)位的校驗(yàn)碼,，那么增加(n－k)位之后,，信息代碼多項(xiàng)式在新的數(shù)據(jù)塊中就表示成 x^n-kM(x) ，如圖13-01所示,。

圖13-01 信息代碼結(jié)構(gòu)

如果用一個(gè)校驗(yàn)碼生成多項(xiàng)式 G(x) 去除代碼多項(xiàng)式 x^n-kM(x),，得到的商假定為 Q(x) ，余式為 R(x)　,，則可寫成
　　　
　　　x^n-kM(x) = Q(x)G(x) + R(x)
　　因?yàn)槟?多項(xiàng)式的加法和減法運(yùn)算結(jié)果相同,，所以又可把上式寫成：
　　　x^n-kM(x) + R(x) = Q(x)G(x)
 G(x) 稱為校驗(yàn)碼生成多項(xiàng)式。從該式中可以看到,，代表新的代碼多項(xiàng)式 x^n-kM(x) + R(x) 是能夠被校驗(yàn)碼生成多項(xiàng)式 G(x) 除盡的,，即它的余項(xiàng)為0。
　　例如,，CD盤中的q通道和軟磁盤存儲(chǔ)器中使用的CRC校驗(yàn)碼生成多項(xiàng)式是
　　　G(x) = x¹⁶ + x¹² + x⁵ + 1
　　若用二進(jìn)制表示,，則為
　　　G(x) = 100010000000100001(B) = 11021(H)
　　假定要寫到盤上的信息代碼 M(x) 為
　　　M(x) = 4D6F746F (H)
　　由于增加了2個(gè)字節(jié)共16位的校驗(yàn)碼,，所以信息代碼變成 x¹⁶M(x): 4D6F746F0000(H)。 CRC檢驗(yàn)碼計(jì)算如下：

　　兩數(shù)相除的結(jié)果,，其商可不必關(guān)心,，其余數(shù)為B994(H)就是CRC校驗(yàn)碼。把信息代碼寫到盤上時(shí),，將原來的信息代碼和CRC碼一起寫到盤上,。在這個(gè)例子中，寫到盤上的信息代碼和CRC碼是4D6F746FB994,

　　這個(gè)碼是能被11021(H)除盡的,。
　　從盤上把這塊數(shù)據(jù)讀出時(shí),，用同樣的CRC碼生成多項(xiàng)式去除這塊數(shù)據(jù)，相除后得到的兩種可能結(jié)果是：　?、儆鄶?shù)為0,，表示讀出沒有出現(xiàn)錯(cuò)誤；
　?、谟鄶?shù)不為0,，表示讀出有錯(cuò)。
　　CD-ROM中也采用了相同的CRC檢錯(cuò),。CD-ROM扇區(qū)方式01中,，有一個(gè)4字節(jié)共32位的EDC字域，它就是用來存放CRC碼,。不過,，CD-ROM采用的CRC校驗(yàn)碼生成多項(xiàng)式與軟磁盤采用的生成多項(xiàng)式不同，它是一個(gè)32階的多項(xiàng)式,
　　　P(x) = (x¹⁶ + x¹⁵ + x² + 1)(x¹⁶ + x² + x + 1) 
　　計(jì)算CRC碼時(shí)用的數(shù)據(jù)塊是從扇區(qū)的開頭到用戶數(shù)據(jù)區(qū)結(jié)束為止的數(shù)據(jù)字節(jié),，即字節(jié)0～2063共2064個(gè)字節(jié),。在EDC中存放的CRC碼的次序如下：

13.2 RS編碼和糾錯(cuò)算法

13.2.1. GF(2^m)域

　　RS(Reed-Solomon)碼在伽羅華域(Galois Field，GF)中運(yùn)算的,，因此在介紹RS碼之前先簡要介紹一下伽羅華域,。
　　　CD-ROM中的數(shù)據(jù)、地址,、校驗(yàn)碼等都可以看成是屬于GF(2^m) = GF(2⁸)中的元素或稱符號(hào),。GF(2⁸)表示域中有256個(gè)元素，除0,，1之外的254個(gè)元素由本原多項(xiàng)式P(x)生成,。本原多項(xiàng)式P(x)的特性是，得到的余式等于0,。CD-ROM用來構(gòu)造GF(2⁸) 域的P(x)是
　　　　P(x) = x⁸ + x⁴ +x³ + x² + 1 (13－1)
　　　而GF(2⁸)域中的本原元素為
　　　　α = (0 0 0 0 0 0 1 0)
　　　下面以一個(gè)較簡單例子說明域的構(gòu)造,。
　　　[例13.1] 構(gòu)造GF(2³)域的本原多項(xiàng)式P(x)假定為
　　　　P(x) = x³ + x + 1
　　　　α定義為P(x) = 0的根，即
　　　　α³＋α＋1 = 0
　　　　和 α³ = α＋1
　　　GF(2³)中的元素可計(jì)算如下：

　　用二進(jìn)制數(shù)表示域元素得到表13-01所示的對照表

表13-01 GF(2³)域中與二進(jìn)制代碼對照表,P(x) =  

　　這樣一來就建立了GF(2³)域中的元素與3位二進(jìn)制數(shù)之間的一一對應(yīng)關(guān)系,。用同樣的方法可建立GF(2⁸)域中的256個(gè)元素與8位二進(jìn)制數(shù)之間的一一對應(yīng)關(guān)系,。在糾錯(cuò)編碼運(yùn)算過程中,，加、減,、乘和除的運(yùn)算是在伽羅華域中進(jìn)行?，F(xiàn)仍以GF(2³)域中運(yùn)算為例：
　　　加法例：α⁰＋α³ = 001＋011 = 010 = α¹
　　　減法例：與加法相同
　　　乘法例：α⁵·α⁴ = α^{(5＋4) mod7} = α²
　　　除法例：α⁵/α³ = α²
　　　　　　　α³/α⁵ = α^-2 = α^(－2＋7) = α⁵
　　　取對數(shù)：log(α⁵) = 5
　　　這些運(yùn)算的結(jié)果仍然在GF(2³)域中。

13.2.2 RS的編碼算法

　　RS的編碼就是計(jì)算信息碼符多項(xiàng)式M(x)除以校驗(yàn)碼生成多項(xiàng)式之后的余數(shù),。
　　在介紹之前需要說明一些符號(hào),。在GF(2^m)域中，符號(hào)(n,，k)RS的含義如下：
　　m　　　　　　表示符號(hào)的大小,，如m = 8表示符號(hào)由8位二進(jìn)制數(shù)組成
　　n　　　　　　表示碼塊長度
　　k　　　　　　表示碼塊中的信息長度
　　K=n－k = 2t　表示校驗(yàn)碼的符號(hào)數(shù)
　　t　　　　　　表示能夠糾正的錯(cuò)誤數(shù)目

　　例如，(28,，24)RS碼表示碼塊長度共28個(gè)符號(hào),，其中信息代碼的長度為24，檢驗(yàn)碼有4個(gè)檢驗(yàn)符號(hào),。在這個(gè)由28個(gè)符號(hào)組成的碼塊中,，可以糾正在這個(gè)碼塊中出現(xiàn)的2個(gè)分散的或者2個(gè)連續(xù)的符號(hào)錯(cuò)誤，但不能糾正3個(gè)或者3個(gè)以上的符號(hào)錯(cuò)誤,。
　　對一個(gè)信息碼符多項(xiàng)式M(x),，RS校驗(yàn)碼生成多項(xiàng)式的一般形式為
　　　 (13－2)
式中，m₀是偏移量,，通常取K₀ = 0或K₀= 1,，而(n-k)≥2t　(t為要校正的錯(cuò)誤符號(hào)數(shù))。
　　下面用兩個(gè)例子來說明RS碼的編碼原理,。
　　[例13.2] 設(shè)在GF(2³)域中的元素對應(yīng)表如表13-01所示,。假設(shè)(6，4)RS碼中的4個(gè)信息符號(hào)為,，信息碼符多項(xiàng)式M(x)為
　　　M(x) = m₃x³ + m₂x^２ + m₁x + m₀　(13－3)
　　并假設(shè)RS校驗(yàn)碼的2個(gè)符號(hào)為Q₁和Q₀,，的剩余多項(xiàng)式R(x)為
　　　R(x) = Q₁(x) + Q₀
　　這個(gè)多項(xiàng)式的階次比G(x)的階次少一階。
　　如果K₀ = 1,，t = 1,，由式(13－2)導(dǎo)出的RS校驗(yàn)碼生成多項(xiàng)式就為
　　　 = (x－α)(x－α²)　(13－4)
　　根據(jù)多項(xiàng)式的運(yùn)算,，由式(13－3)和式(13－4)可以得到
　　　m₃x⁵＋m₂x⁴＋m₁x³＋m₀x²＋Q₁x＋Q₀ = (x－α)(x－α²)Q(x)
　　當(dāng)用x = α和x = α²代入上式時(shí),，得到下面的方程組，
　　　
　　經(jīng)過整理可以得到用矩陣表示的(6,，4)RS碼的校驗(yàn)方程：
　　　
　　求解方程組就可得到校驗(yàn)符號(hào)：
　　　
　　在讀出時(shí)的校正子可按下式計(jì)算：
　　　
　　[例13.3] 在例13.2中,，如果K₀ = 0，t = 1,，由式(13－2)導(dǎo)出的RS校驗(yàn)碼生成多項(xiàng)式就為
　　　 = (x－α⁰)(x－α¹) (13－5)
　　根據(jù)多項(xiàng)式的運(yùn)算,，由(13－3)和(13－5)可以得到下面的方程組：
　　　
　　方程中的αⁱ也可看成符號(hào)的位置,，此處i = 0，1,，…,，5。
　　求解方程組可以得到RS校驗(yàn)碼的2個(gè)符號(hào)為Q₁和Q₀,，
　　　 (13－6)
　　假定m_i為下列值：

　　代入(13－6)式可求得校驗(yàn)符號(hào)：
　　Q₁ = α⁶ = 101
　　Q₀ = α⁴ = 110

13.2.3 RS碼的糾錯(cuò)算法

　　RS碼的錯(cuò)誤糾正過程分三步： (1)計(jì)算校正子(syndrome),，(2)計(jì)算錯(cuò)誤位置，(3)計(jì)算錯(cuò)誤值?，F(xiàn)以例13.3為例介紹RS碼的糾錯(cuò)算法,。
　　校正子使用下面的方程組來計(jì)算：
　　　
　　為簡單起見，假定存入光盤的信息符號(hào)m₃,、m₂,、m₁、m₀和由此產(chǎn)生的檢驗(yàn)符號(hào)Q₁,、Q₀均為0,，讀出的符號(hào)為m₃′、m₂′,、m₁′,、m₀′、Q₁′和Q₀′,。
　　如果計(jì)算得到的s₀和s₁不全為0,，則說明有差錯(cuò)，但不知道有多少個(gè)錯(cuò),，也不知道錯(cuò)在什么位置和錯(cuò)誤值,。如果只有一個(gè)錯(cuò)誤，則問題比較簡單,。假設(shè)錯(cuò)誤的位置為α_x,，錯(cuò)誤值為m_x，那么可通過求解下面的方程組：
　　
　　得知錯(cuò)誤的位置和錯(cuò)誤值,。
　　如果計(jì)算得到s₀ = α²和s₁ = α⁵,，可求得α_x= α³和m_x = α²，說明m₁出了錯(cuò),，它的錯(cuò)誤值是α²,。校正后的m₁= m₁′＋m_x ，本例中m₁=0,。
　　如果計(jì)算得到s₀ = 0,，而s₁≠0，那基本可斷定至少有兩個(gè)錯(cuò)誤，當(dāng)然出現(xiàn)兩個(gè)以上的錯(cuò)誤不一定都是s₀ = 0和s₁≠0,。如果出現(xiàn)兩個(gè)錯(cuò)誤,，而又能設(shè)法找到出錯(cuò)的位置，那么這兩個(gè)錯(cuò)誤也可以糾正,。如已知兩個(gè)錯(cuò)誤m_x1和m_x2的位置α_x1和α_x2,，那么求解方程組：
　　　
　　就可知道這兩個(gè)錯(cuò)誤值。
　　CD-ROM中的錯(cuò)誤校正編碼CIRC和里德-索洛蒙乘積碼(Reed Solomon Product－like Code,，RSPC)就是采用上述方法導(dǎo)出的,。

13.3 CIRC糾錯(cuò)技術(shù)

　　光盤存儲(chǔ)器和其它的存儲(chǔ)器一樣，經(jīng)常遇到的錯(cuò)誤有兩種,。一種是由于隨機(jī)干擾造成的錯(cuò)誤,，這種錯(cuò)誤稱隨機(jī)錯(cuò)誤。它的特點(diǎn)是隨機(jī)的,、孤立的,，干擾過后再讀一次光盤，錯(cuò)誤就可能消失,。另一種錯(cuò)誤是連續(xù)多位出錯(cuò),，或連續(xù)多個(gè)符號(hào)出錯(cuò)，如盤片的劃傷,、沾污或盤本身的缺陷都可能出現(xiàn)這種錯(cuò)誤,，一錯(cuò)就錯(cuò)一大片。這種錯(cuò)誤稱為突發(fā)錯(cuò)誤,。CIRC(Cross Interleaved Reed Solomon)糾錯(cuò)碼綜合了交插,、延時(shí)交插、交叉交插等技術(shù),，不僅能糾隨機(jī)錯(cuò)誤,，而且對糾突發(fā)錯(cuò)誤特別有效。

13.3.1 交插技術(shù)

　　對糾錯(cuò)來說,，分散的錯(cuò)誤比較容易得到糾正,，但出現(xiàn)一長串的錯(cuò)誤時(shí)，就較麻煩,。正如我們讀書看報(bào),，如果文中在個(gè)別地方出錯(cuò)，根據(jù)前后文就容易判斷是什么錯(cuò),。如果連續(xù)錯(cuò)好多字,，就很難判斷該處寫的是什么。
　　例如,，用X表示出現(xiàn)的錯(cuò)字,，一種錯(cuò)誤形式為“獨(dú)在異鄉(xiāng)XXX，每逢佳節(jié)倍思親”,，這是連續(xù)出現(xiàn)的錯(cuò)誤,，另一種錯(cuò)誤形式為“獨(dú)在異鄉(xiāng)X異客，每X佳節(jié)倍思X”,，這是分散出現(xiàn)的錯(cuò)誤,。這兩種錯(cuò)誤形式相比，同樣是3個(gè)錯(cuò)誤,，但人們更容易更正后一種形式的錯(cuò)誤,，更正之后為“獨(dú)在異鄉(xiāng)為異客，每逢佳節(jié)倍思親”,。
　　這個(gè)道理很簡單,，把這種思想用在數(shù)字記錄系統(tǒng)中對突發(fā)錯(cuò)誤的更正非常有效。在光盤上記錄數(shù)據(jù)時(shí),，如果把本該連續(xù)存放的數(shù)據(jù)錯(cuò)開放,，那么當(dāng)出現(xiàn)一片錯(cuò)誤時(shí)，這些錯(cuò)誤就分散到各處,，錯(cuò)誤就容易得到糾正,，這種技術(shù)就稱為交插(interleaving)技術(shù)。例如,，
　　3個(gè)(5,，3)碼塊： B₁ = (a_2，a₁,，a₀,，P₁，P₀)
　　　　　　　　　　B₂ = (b₂,，b₁,，b₀，Q₁,，Q₀)
　　　　　　　　　　B₃ = (c₂,，c₁，c₀,，R₁,，R₀)

　　排成3行：
　　　a₂ a₁ a₀ P₁ P₀
　　　b₂ b₁ b₀ Q₁ Q₀
　　　c₂ c₁ c₀ R₁ R₀

　　從這個(gè)例子中可以看到，對連續(xù)排列,，每個(gè)碼塊中只能出現(xiàn)一個(gè)錯(cuò)誤才能糾正,。而交插記錄后，讀出的3個(gè)連續(xù)錯(cuò)誤經(jīng)還原后可把它們分散到3個(gè)碼塊中,，每個(gè)碼塊可以糾正1個(gè)錯(cuò)誤,，總計(jì)可以糾正3個(gè)連續(xù)的錯(cuò)誤。
　　一般來說，如果有r個(gè)(n,，k)碼,，排成r×n矩陣，按列交插后存儲(chǔ)或傳送,，讀出或接收時(shí)恢復(fù)成原來的排列,，若(n，k)碼能糾正t個(gè)錯(cuò)誤,，那么這樣交插后就可以糾正rt個(gè)突發(fā)錯(cuò)誤,。

13.3.2 交叉交插技術(shù)

　　交叉交插(cross－interleaving)編碼是交插的一種變型。在實(shí)際應(yīng)用中,，也是一種重要的技術(shù)?，F(xiàn)仍以簡單的例子說明這種技術(shù)思想。
　　(1) 用(5,，3)碼編碼器C₂生成的4個(gè)碼塊為:
　　　B₁=(a₂ a₁ a₀ P₁ P₀)
　　　B₂=(b₂ b₁ b₀ Q₁ Q₀)
　　　B₃=(c₂ c₁ c₀ R₁ R₀)
　　　B₄=(d₂ d₁ d₀ S₁ S₀)
　　(2) 交插后再用(6,，4)碼編碼器C₁生成5個(gè)碼塊為:
　　　a₂ b₂ c₂ d₂ T₁ T₀
　　　a₁ b₁ c₁ d₁ U₁ U₀
　　　a₀ b₀ c₀ d₀ V₁ V₀
　　　P₁ Q₁ R₁ S₁ W₁ W₀
　　　P₀ Q₀ R₀ S₀ X₁ X₀
　　(3) 再交插，交插的碼塊數(shù)可以是2,、3,、4或5。以交插2個(gè)碼塊為例：
　　　a₂ a₁ b₂ b₁ c₂ c₁ d₂ d₁ T₁ U₁ T₀ U₀ a₀ P₁ b₀ Q₁ c₀ R₁ d₀ S₁ …
　　(4) 最后一個(gè)碼塊不配對,，可以和下一個(gè)碼塊配對,。
　　這種編碼技術(shù)用了兩個(gè)編碼器C₂和C₁。C₂對原碼塊進(jìn)行編碼得到(5,，3)碼塊,，交插后生成由4個(gè)符號(hào)組成的碼塊，碼塊中的符號(hào)是交叉存放的,，然后再用(6,，4)編碼器C₁去編碼。
　　有關(guān)CIRC詳細(xì)的實(shí)現(xiàn)方法請參看文獻(xiàn)[7],。
　　CIRC首先應(yīng)用在激光唱盤系統(tǒng)中,。音頻信號(hào)的采樣率為44.1 kHz，而每次采樣有兩個(gè)16比特的樣本,，一個(gè)來自左聲道,，一個(gè)來自右聲道，每個(gè)樣本用兩個(gè)GF(2⁸)域中的符號(hào)表示,，因此每次采樣共有4個(gè)符號(hào),。
　　為了糾正可能出現(xiàn)的錯(cuò)誤，每6次采樣共24個(gè)符號(hào)構(gòu)成1幀,，稱為F₁幀(F₁－Frame),。用一個(gè)稱為C₂的編碼器對這24個(gè)符號(hào)產(chǎn)生4個(gè)Q校驗(yàn)符號(hào)： Q₀,，Q₁，Q₂和Q₃,。24個(gè)聲音數(shù)據(jù)加上4個(gè)Q校驗(yàn)符號(hào)共28個(gè)符號(hào),，用稱為C₁編碼器對這28個(gè)符號(hào)產(chǎn)生4個(gè)P校驗(yàn)符號(hào)： P₀，P₁,，P₂和P₃。28個(gè)符號(hào)加上4個(gè)P校驗(yàn)符號(hào)共32個(gè)符號(hào)構(gòu)成的幀稱為F₂幀(F₂－Frame),。F₂幀加上1個(gè)字節(jié)(即1個(gè)符號(hào))的子碼共33個(gè)符號(hào)構(gòu)成的幀稱為F₃幀(F₃－Frame),。
　　在實(shí)際應(yīng)用中可對前面介紹的交插技術(shù)略加修改，執(zhí)行交插時(shí)不是交插包含有k個(gè)校驗(yàn)符的碼塊,，而是交插一個(gè)連續(xù)系列中的碼符,，這種交插技術(shù)稱為延時(shí)交插。延時(shí)交插之后還可用交叉技術(shù),，稱為延時(shí)交叉交插技術(shù),。CD存儲(chǔ)器中的CIRC編碼器采用了4×F₁幀的延時(shí)交插方案。1幀延時(shí)交插可糾正連續(xù)4×F₁幀的突發(fā)錯(cuò)誤,。4×F₂幀的延時(shí)交插可糾正連續(xù)16×F₁幀突發(fā)錯(cuò)誤,，相當(dāng)于大約14×F₃幀的突發(fā)錯(cuò)誤。1×F₃幀經(jīng)過EFM編碼后產(chǎn)生588位通道位,。1位通道位的長度折合成0.277μm的光道長度,。14×F₃幀突發(fā)錯(cuò)誤長度相當(dāng)于
　　［(16×(24＋4))/33］×588×0.277≈2.2 mm
換句話說,，CIRC能糾正在2.2 mm光道上連續(xù)存放的448個(gè)錯(cuò)誤符號(hào)!相當(dāng)于連續(xù)224個(gè)漢字錯(cuò)誤可以得到糾正,。

13.4 RSPC碼

　　按ISO/IEC10149的規(guī)定，CD-ROM扇區(qū)中的ECC碼采用GF(2⁸)域上的RSPC碼產(chǎn)生172個(gè)字節(jié)的P校驗(yàn)符號(hào)和104個(gè)字節(jié)的Q校驗(yàn)符號(hào),。RS碼采用本原多項(xiàng)式
　　　P(x) = x⁸ + x⁴ +x³ + x² + 1
和本原元
　　　α = (00000010)
構(gòu)造GF(2⁸)域,，這已經(jīng)在上節(jié)作了介紹。
　　第12章已經(jīng)介紹了CD-ROM的扇區(qū)結(jié)構(gòu),。在每個(gè)扇區(qū)中,，字節(jié)12～2075和ECC域中的字節(jié)2076到2351共2340個(gè)字節(jié)組成1170個(gè)字(word)。每個(gè)字s(n)由兩個(gè)字節(jié)B組成,，一個(gè)稱為最高有效位字節(jié)MSB,，另一個(gè)叫做最低有效位字節(jié)LSB。第n個(gè)字由下面的字節(jié)組成,，
　　s(n) = MSB[B(2n + 13)] + LSB[B(2n + 12)]
其中n = 0,，1，2,，…,，1169,。
　　從字節(jié)12開始到字節(jié)2075共2064個(gè)字節(jié)組成的數(shù)據(jù)塊排列成24×43的矩陣，如圖13-02所示,。

圖13－02 RSPC碼計(jì)算用數(shù)據(jù)陣列

　　矩陣中的元素是字,。這個(gè)矩陣要把它想象成兩個(gè)獨(dú)立的矩陣才比較好理解和分析，一個(gè)是由MSB字節(jié)組成的24×43矩陣,，另一個(gè)是由LSB字節(jié)組成的24×43矩陣,。
　　(1) P校驗(yàn)符號(hào)用(26，24)RS碼產(chǎn)生
　　43列的每一列用矢量表示,，記為V_p,。每列有24個(gè)字節(jié)的數(shù)據(jù)再加2個(gè)字節(jié)的P校驗(yàn)字節(jié)，用下式表示：
　　　
其中：
　　　N_p =  0,，1,，2，……,，42
　　　M_p =  0,，1，2,，……,，25
　　　s(43*24+N_p)和s(43*25+N_p)是P校驗(yàn)字節(jié)
　　對這列字節(jié)計(jì)算得到的是兩個(gè)P校驗(yàn)字節(jié)，稱為P校驗(yàn)符號(hào),。兩個(gè)P校驗(yàn)字節(jié)加到24行和25行的對應(yīng)列上,，這樣構(gòu)成了一個(gè)26×43的矩陣，并且滿足方程
　　　H_p × V_p = 0
　　其中H_P校驗(yàn)矩陣為
　　　
　　(2) Q校驗(yàn)符號(hào)用(45,，43)RS碼產(chǎn)生
　　增加P校驗(yàn)字節(jié)之后得到了一個(gè)26×43矩陣,，該矩陣的對角線元素重新排列后得到一個(gè)新的矩陣，其結(jié)構(gòu)如圖13-03所示,。

(ISO/IEC 10149∶1989)
圖13-03 Q校驗(yàn)符號(hào)計(jì)算用數(shù)據(jù)陣列

　　每條對角線上的43個(gè)MSB字節(jié)和LSB字節(jié)組成的矢量記為V_Q,。V_Q在26×43矩陣中變成行矢量。第N_Q行上的V_Q矢量包含的字節(jié)如下：
　　　　
其中：
　　　N_Q = 0,，1,，2，…,，25
　　　M_Q = 0,，1，2,，…,，42
　　s(43*26+N_q)和s(44*25+N_q)和是Q校驗(yàn)字節(jié)
　　V_Q中的(44*M_Q＋43*N_Q)字節(jié)號(hào)運(yùn)算結(jié)果要做mod(1118)運(yùn)算。用(45,，43)RS碼產(chǎn)生的兩個(gè)Q校驗(yàn)字節(jié)放到對應(yīng)V_Q矢量的末端,，并且滿足下面的方程：
　　　H_Q × V_Q = 0
其中H_Q校驗(yàn)矩陣為
　　　
　　(26,，24)RS碼和(45，43)RS碼可以糾正出現(xiàn)在任何一行和任何一列上的一個(gè)錯(cuò)誤,，并且能相當(dāng)可靠地檢測出行,、列中的多重錯(cuò)誤。如果在一個(gè)陣列中出現(xiàn)多重錯(cuò)誤,，Reference Technology公司提供有一種名叫Layered ECC的算法,，它可以取消多重錯(cuò)誤。它的核心思想是交替執(zhí)行行糾錯(cuò)和列糾錯(cuò),。
　　例如,，假設(shè)錯(cuò)誤分布如圖13-04所示。ECC算法首先計(jì)算MSB矩陣和LSB矩陣中每一行的校正子S_ri(i = 0,，1,，…,，25),，以及每一列的校正子S_cj(j = 0，1,，…,，44)。因?yàn)橛?45,，43)RS碼,，所以每一個(gè)S_ri和每一個(gè)S_cj都有兩個(gè)校正子分量。如果S_ri = 0,，則說明第i行無錯(cuò),；如S_cj = 0，說明第j行無錯(cuò),。

圖13-04 錯(cuò)碼分布舉例

　　ECC算法首先糾正行1,、3、17,、19和22上分別只有一個(gè)的錯(cuò)誤,。這些錯(cuò)誤取消后就糾正列5、9,、15和35上分別只有一個(gè)的錯(cuò)誤,。經(jīng)過一次行列交替糾錯(cuò)后，只剩下C_4,，25,、C_7，20,、C_7,，25和C_9,，20這四個(gè)錯(cuò)誤。再進(jìn)行一次行列交替糾錯(cuò)后,，就可以消除全部錯(cuò)誤,。
　　對于象下面這樣分布的錯(cuò)誤，ECC算法也可以糾正,。
　　　
　　因?yàn)镽S碼糾錯(cuò)算法本身包含找錯(cuò)誤的位置和錯(cuò)誤值,，而錯(cuò)誤位置已經(jīng)由校正子S_r(i－k)、S_ri,、S_r(i＋m)和S_cj,、S_c(j＋l)確定，所以只剩下求錯(cuò)誤值的問題,。這個(gè)問題在討論RS碼時(shí)已經(jīng)解決,。
　　對CD-ROM存儲(chǔ)器的數(shù)據(jù)，經(jīng)CIRC校正后可以使以字節(jié)做單位的誤碼率小于10^-9,，再經(jīng)RSPC進(jìn)行糾錯(cuò)后,，字節(jié)誤碼率可以小于10^-13，這樣就滿足了計(jì)算機(jī)要求誤碼率小于10^-12的要求,。

練習(xí)與思考題

1. CRC用于檢測錯(cuò)誤還是校正錯(cuò)誤,？
2. 用自己的語言說明錯(cuò)誤檢測的思想。
3. 什么叫做突發(fā)錯(cuò)誤,？
4. 碼塊長度為n,，碼塊中的信息長度為k，問(n,，k)RS碼本身能糾正多少個(gè)錯(cuò)誤,？
5. 要糾正1個(gè)符號(hào)的錯(cuò)誤，至少需要附加多少個(gè)校驗(yàn)符,？
6. 目前CD存儲(chǔ)器中使用的CIRC編碼技術(shù)能夠糾正突發(fā)錯(cuò)誤的最大長度是多少(按漢字字符數(shù)估算),？

• ISO/IEC 908. Compact Disc Digital Audio System. 1987.
• ISO 9660. Volume and File structure of CD-ROM for Information Interchange. 1988.
• ISO/IEC 10149. Data Interchange on Read Only 120 mm Optical Data Disks(CD-ROM). 1989
• Scott A.Vanstone and Paul C. van Oorcshot. An Introducton Error Correcting Codes with Application. Kluwer, Academic Publishers, 1989
• Philips and Sony. System Description CD-ROM XA Compact Disk Read Only Memory extended Architecture. May, 1991
• Philips and Sony Corporation. CD-I Full Functional Specification. 1993.
• 林福宗, 陸 達(dá). 多媒體與CD-ROM. 北京：清華大學(xué)出版社, 1995.3.