What is Reed–Solomon Code?

先備知識

「錯誤更正碼」， Error–Correcting Codes， 通常縮寫成 ECC。 在日常生活中，我們經常可以遇到 ECC 的應用，譬如在買電腦的時候，老闆說他的 RAM 是 ECC RAM， 也就是說他的 RAM 有錯誤更正碼在裡面。

這錯誤更正碼到底是做什麼用? 通常是應用在通訊的過程中， 實際上通訊分很多種， 平常想像 到的是在空間中做通訊， 譬如從地球的某一點傳資料到地球的另外一點。 另外還有一種通訊的情況， 就是在時間上做通訊， 像平常看到電腦裡的磁帶 (magnetic tape)、 磁碟 (magnetic disk); 又譬如雷射唱片 (compact disk， CD) 也是， 它在製造的時候把音樂寫進去， 然後再把它放到雷射唱盤 (CD player) 讀出來， 這也是一個在時間上做通訊的例子。 通常我們可以把通訊過程變成下面這個模型 (model)。

就是說有一些資料 (data) 經過一個東西叫做通道 (channel)， 因為通道會有許多干擾或雜訊， 比方說你把音樂寫在 CD 片上， 不小心刮了一塊， 讀出來的時候那地方就錯了，或是當我們透過網路傳輸一些資料時，資料可能會因某些網路問題而損壞。由於幹擾或某些網路問題，資料內部的位元可能會被損壞，所以，經過通道之後， 就會變成有雜訊的資料 (noisy data)， 而基本上錯誤更正碼就是要對付雜訊或干擾， 把錯誤改正回來。

原來 我們是從資料到通道這樣直接過來， 現在我們讓資料在傳出前先經過一個編碼器 ( encoder )

經過編碼器之後， 傳出來的東西除了原始的資料之外， 又加了一些多餘的資料 (redundant bits)， 使得裡面有一個數學的結構存在， 當經過通道以後不論是原始的資料或多餘的資料都可能有錯， 可是因為它裡面有數學結構， 就可以經由解碼器 (decoder)， 依原有的數學結構把錯誤的東西改回來， 這就是錯誤更正碼的基本構想。

Reed-Solomon codes

Reed-Solomon codes 是由 Irving S. Reed 和 Gustave Solomon 提出的一種碼。Reed-Solomon code 是 non-binary BCH codes 的子分類。 The encoder of Reed-Solomon codes 與 binary encoder 不同之處在於，它對多個位元 ( multiple bits ) 而不是單一位元 ( individual bits ) 進行編碼。

因此，從根本上說，Reed-Solomon codes 有助於恢復透過網路傳輸的損壞訊息。 在 Reed-Solomon codes 中，有分 :

• Encoder
• Decoder

Reed-Solomon codes encoder 接收資料後，在透過網路傳輸資料之前，會在原始資料位元上添加一些 parity bits ( 奇偶校驗位 )。

另一方面，Reed-Solomon codes decoder，它能偵測出損壞的訊息，並從錯誤中恢復它們。

Representation of n-bits Reed-Solomon codes

Parameters of Reed-Solomon code:

• (n， k) code is used to encode m-bit symbols.
• Block length(n) is given by 2m-1 symbols.
• In Reed-Solomon codes， message size is given by (n-2t) where t= number of errors corrected.
• Parity check size is given by = (n-k) or 2t symbols.
• Minimum distance(a) is given by = (2t+1).
• Message size is of k bits.