3.4 Reed Solomon碼

3.4.1 RS碼原理與能力

RS碼是1960年由Irving S.Reed和Gustave Solomon提出的編碼方法，簡稱RS碼，它有很強的檢錯和糾錯能力。有相對簡單的解碼算法。由于這些原因，RS碼已經在很多領域得到應用，例如，音頻CD的差錯校正，在移動通信、數字視頻廣播（DVB）和DAB/DMB也得到應用。按照DVB標準發射的電視信號應用RS碼，可使接收機接收的信號的比特差錯率改善大于106（例如，由10-3變為10-9）。設計一個數字通信系統，使其能達到10-9的比特差錯率，即接收109個比特，發生錯誤的比特數量不得不多于1個，便可以通過附加應用RS碼來實現。RS碼在解碼后的數據中剩余比特差錯的概率，一般來說要比不用RS碼時下降很多，這通常稱為編碼增益。

RS碼是以很多符號組成塊來工作的，符號一般來說由8比特構成。因此，RS碼屬于典型的以符號為基礎的塊碼。

如果RS碼有n個符號，校正在一個塊中k/2個有差錯的符號，就必須附加k個校驗符號。Reed Solomon編碼在時域和頻域都是可能的。

在編碼器中信息符號這樣安排，即它們處在傳輸的碼字的最初的m位。這些碼字通過一個特有的碼字生成多項式除。這個多項式有這樣的特點，它的零位在分布譜中有連續的k位零。這種按模計算結果的k位附加在傳輸的碼字m位的后面。這些這樣結合在一起的字c（x）具有n=m+k位。如果在傳輸后喪失了這種特點，解碼器知道發生了差錯。它可以借助不同的算法和在頻域中的運算產生出差錯碼字 E（Z），這樣就能重新恢復出原始的信息R（Z）=C（Z）-E（Z）。在反變換到時域之后在輸出端提供原始的信息r（x）。

如圖3-4-1所示是Reed Solomon編碼與解碼原理。

一個有m信息字節（這里1符號=1字節）和k校驗字節的RS碼稱為RS（m+k，m）碼。一個這樣的碼可以最多校正每個碼字k/2個有差錯的符號，識別k個有差錯的符號。

【例3-1】RS（255，239）碼表示碼塊長度共239+16=255個符號，其中信息字的長度為239個符號，校驗字的長度為16個符號。這樣一個由255個符號組成的碼塊中，最多可以糾正在這個碼塊中出現的8個分散的、或者8個連續的符號錯誤，最多識別出16個有差錯的符號。

【例3-2】一個常用的RS（255，223）碼，每個符號8比特。每個碼字包含255個碼字字節，其中223個數據字節，32個校驗字節。對于這種碼來說n=m+k=255，m=223，k=32，k/2=16解碼器可以消除在碼字中16個符號所有可能的干擾：也就是說，在所有的碼字中最多16個符號中的干擾都可以自動消除。

如果給出了每個符號有多少比特的話，那么RS碼最大的碼字長度為2s-1。例如，一個符號為8比特（s=8），一個碼的最大碼長為28-1=255字節。

RS碼的碼長可以縮短，這時，不傳輸的數據符號的數量在編碼器中用0來構成，在解碼器中重新插入。

例如，RS（255，223）碼可將其縮短為RS（200，168），編碼器取168 數據字節的一個塊，再與55個0字節相加，形成一個（255，223）的碼字，但是僅僅傳輸168個數據字節與32個校驗字節。

RS碼對編碼器與解碼器要求的處理能力，取決于每個碼字的校驗符號的數量。k的值越大，意味著很多干擾都可以消除，但是，要求的計算能力要比k值小時大。

如果在一個符號中出現1比特的差錯，就是出現了一個符號干擾，或者在一個符號中所有的比特都發生了錯誤，這也是符號干擾。例如，RS（255，223）可以消除16個符號干擾。在最壞的情況下，可能出現16比特干擾，每個可能在不同的符號（字節）中，因此解碼器可以消除16個比特干擾。在最好的情況下，出現16個整個字節干擾，這樣，解碼器消除16×8個比特干擾。

如圖3-4-2所示是不同的RS碼的剩余比特差錯概率。

3.4.2 生成多項式校驗符號

在一個RS（n，k）碼中，有2k個不同的碼字，所有有效的碼字正好是能被生成多項式除盡的。因此，RS碼字可以通過一個特有的多項式（生成多項式）產生。生成多項式的一般形式是

式中a為GF（2m）的本原元素。GF（2m）是由2m個元素組成的有限域（或稱伽羅華域），在M進制分組碼中，其元素為0，1，…，（M-1），例如M=4進制碼，其元素為0，1，2，3；對應的二進制數為00，01，10，11。對于M進制RS碼，M=2m，其元素0，1，…，（2m-1）。

編碼后得到的有效碼字c（x）是

這里g（x）是生成多項式，i（x）是信息塊，c（x）是一個有效碼字。

在一個系統RS碼字中的k個校驗符號為

3.4.3 RS碼與卷積碼的級聯

為了提高編碼效率，有這樣的可能性，將不同的編碼器一個跟一個級聯起來。第一個編碼器（編碼率為R1）稱為外編碼器，而第二個編碼器（編碼率為R2）稱為內編碼器，圖3-4-3所示是級聯編解碼器原理方框圖。當傳輸的源數據率為Ru時，那么在信道上傳輸的總數據率R0為

如果選擇外編碼器為塊碼編碼器（例如RS編碼器），而內編碼器是卷積碼編碼器，那么內編碼器可以校正單個的比特差錯，外編碼器可以校正較短的塊差錯。為了能夠校正較長的塊差錯，可在兩個編碼器之間接入內交織器。內交織器不是添加新的數據冗余，而是對數據重新整理，使原來一個挨著一個的比特相互離開一個交織深度I。