第二節(jié)糾錯(cuò)編碼原理一、糾錯(cuò)編碼的原理一般來講，信源發(fā)出的消息均可用二進(jìn)制信號來表示。例如，要傳送的消息為A和B，則我們可以用1表示A，0表示B。在信道傳輸后產(chǎn)生了誤碼，0錯(cuò)為1，或1錯(cuò)為0，但接收端卻無法判斷這種錯(cuò)誤，因此這種碼沒有任何抗干擾能力。如果在0或1的后面加上一位監(jiān)督位（也稱校驗(yàn)位），如以00表示A，11表示B。長度為2的二進(jìn)制序列共有2=4種組合，即00、01、10、11。00和11是從這四種組合中選出來的，稱其為許用碼組，01、10為禁用碼。當(dāng)干擾只使其中一位發(fā)生錯(cuò)誤，例如00變成了01或10，接收端的譯碼器就認(rèn)為是錯(cuò)碼，但這時(shí)接收端不能判斷是哪一位發(fā)生了錯(cuò)誤，因?yàn)樾畔⒋a11也可能變?yōu)?1或10，因而不能自動(dòng)糾錯(cuò)。如果在傳輸中兩位碼發(fā)生了錯(cuò)誤，例如由00變成了11，譯碼器會將它判為B，造成差錯(cuò)，所以這種1位信息位，一位監(jiān)督位的編碼方式，只能發(fā)現(xiàn)一位錯(cuò)誤碼。按照這種思路，使碼的長度再增加，用000表示A，111表示B，這樣勢必會增強(qiáng)碼的抗干擾能力。長度為3的二進(jìn)制序列，共有8中組合：000、001、010、011、100、101、110、111。這8種組合中有三種編碼方案：第一種是把8種組合都作為碼字，可以表示8種不同的信息，顯然，這種編碼在傳輸中若發(fā)生一位或多位錯(cuò)誤時(shí)，都使一個(gè)許用碼組變成另一個(gè)許用碼組，因而接收端無法發(fā)現(xiàn)錯(cuò)誤，這種編碼方案沒有抗干擾能力；第二種方案是只選四種組合作為信息碼字來傳送信息，例如：000、011、101、110，其他4種組合作為禁用碼，雖然只能傳送4種不同的信息，但接收端有可能發(fā)現(xiàn)碼組中的一位錯(cuò)誤。例如，若000中錯(cuò)了一位，變?yōu)?00，或001或010，而這3種碼為禁用碼組。接收端收到禁用碼組時(shí)，就認(rèn)為發(fā)現(xiàn)了錯(cuò)碼，但不能確定錯(cuò)碼的位置，若想能糾正錯(cuò)誤就還要增加碼的長度。第三種方案中規(guī)定許用碼組為000和111兩個(gè)，這時(shí)能檢測兩位以下的錯(cuò)誤，或能糾正一位錯(cuò)碼。例如，在收到禁用碼組100時(shí)，若當(dāng)作僅有一位錯(cuò)碼，則可判斷出該錯(cuò)碼發(fā)生在“1”的位置，從而糾正為000，即這種編碼可以糾正一位差錯(cuò)。但若假定錯(cuò)碼數(shù)不超出兩位，則存在兩種可能性，000錯(cuò)一位及111錯(cuò)兩位都可能變?yōu)?00，因而只能檢錯(cuò)而不能糾錯(cuò)。從上面的例子可以得到關(guān)于“分組碼”的一般概念。如果不要求檢錯(cuò)或糾錯(cuò)，為了傳輸兩種不同的信息，只用1位碼就夠了，我們把代表所傳信息的這位碼稱為信息位。若使用了2位碼或3位碼，多增加的碼位數(shù)稱為監(jiān)督位。我們把每組信息碼附加若干監(jiān)督碼的編碼稱為分組碼。在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。2圖8-2分組碼的結(jié)構(gòu)其中k是每組碼中信息碼元的數(shù)目，n是碼組的總位數(shù)，分組碼一般用符號(n,k)表示，又稱為碼組的長度（碼長），nk=r為每碼組中的監(jiān)督碼元數(shù)目，或稱為監(jiān)督位數(shù)目。通常將分組碼規(guī)定為如圖8-2所示的結(jié)構(gòu)，圖中前面k位(an1,an2,...,ar)為信息位，后面附加r個(gè)監(jiān)督位(ar1,...,a0)，此碼又稱為系統(tǒng)碼。二、差錯(cuò)控制編碼的基本概念1、編碼效率設(shè)編碼后的碼組長度、碼組中所含信息碼元以及監(jiān)督碼元的個(gè)數(shù)分別為n,k和r，三者之間滿足n=k+r，編碼效率R=k/n=1r/n。R越大，說明信息位所占的比重越大，碼組傳輸信息的有效性越高。所以，R說明了分組碼傳輸信息的有效性。2、編碼分類①根據(jù)已編碼組中信息碼元與監(jiān)督碼元之間的函數(shù)關(guān)系，可分為線性碼和非線性碼。若監(jiān)督碼元與信息碼元之間的關(guān)系呈線性，即滿足一組線性方程式，稱為線性碼。②根據(jù)信息碼元與監(jiān)督碼元之間的約束方式不同，可分為分組碼和卷積碼。分組碼的監(jiān)督碼元僅與本碼組的信息碼元有關(guān)；卷積碼的監(jiān)督碼元不僅與本碼組的信息碼元有關(guān)，而且與前面碼組的信息碼元有約束關(guān)系。③根據(jù)編碼后信息碼元是否保持原來的形式，可分為系統(tǒng)碼和非系統(tǒng)碼。在系統(tǒng)碼中，編碼后的信息碼元保持原樣，而非系統(tǒng)碼中的信息碼元?jiǎng)t改變了原來的信號形式。④根據(jù)編碼的不同功能，可分為檢錯(cuò)碼和糾錯(cuò)碼。⑤根據(jù)糾、檢錯(cuò)誤類型的不同，可分為糾、檢隨機(jī)性錯(cuò)誤的碼和糾、檢突發(fā)性錯(cuò)誤的碼。⑥根據(jù)碼元取值的不同，可分為二進(jìn)制碼和多進(jìn)制碼。本章只介紹二進(jìn)制糾錯(cuò)碼和檢錯(cuò)碼。3、編碼增益由于編碼系統(tǒng)具有糾錯(cuò)能力，因此在達(dá)到同樣誤碼率要求時(shí)，編碼系統(tǒng)會使所要求的輸入信噪比低于非編碼系統(tǒng)，為此引入了編碼增益的概念。其定義為：對于相同的信息傳輸速。率，在給定誤碼率下，非編碼系統(tǒng)與編碼系統(tǒng)之間所需信噪比S0/N0之差（用dB表示）采用不同的編碼會得到不同的編碼增益，但編碼增益的提高要以增加系統(tǒng)帶寬或復(fù)雜度來換取。4、碼重和碼距對于二進(jìn)制碼組，碼組中“1”碼元的個(gè)數(shù)稱為碼組的重量，簡稱碼重，用W表示。例如碼組11001，它的碼重W=2兩個(gè)等長碼組之間對應(yīng)位不同的個(gè)數(shù)稱為這兩個(gè)碼組的漢明距離，簡稱碼距d。例如碼組10001和01101，有三個(gè)位置的碼元不同，所以碼距d=3。碼組集合中各碼組之間距離的最小值稱為碼組的最小距離，用d0表示。最小碼距d0是信道編碼的一個(gè)重要參數(shù)，它體現(xiàn)了該碼組的糾、檢錯(cuò)能力。d0越大，說明碼字間最小差別越大，抗干擾能力越強(qiáng)。但d0與所加的監(jiān)督位數(shù)有關(guān)，所加的監(jiān)督位越多，d0就越大，這又引起了編碼效率R的降低，所以編碼效率R與最小碼距d0是一對矛盾。根據(jù)編碼理論，一種編碼的檢錯(cuò)或糾錯(cuò)能力與碼字間的最小距離有關(guān)。在一般情況下，分組碼的最小漢明距離d0與檢錯(cuò)和糾錯(cuò)能力之間滿足下列關(guān)系：①當(dāng)碼字用于檢測錯(cuò)誤時(shí)，為了能檢測出任意≤e個(gè)錯(cuò)誤，最小碼距應(yīng)滿足：d0≥e+1（8-1）這可以用圖8-3(a)來說明。設(shè)一碼組A位于O點(diǎn)，另一碼組B與A最小碼距為d0。當(dāng)A碼組發(fā)生e個(gè)誤碼時(shí)，可以認(rèn)為A的位置將移動(dòng)到以O(shè)為圓心、以e為半徑的圓上，但其位置不會超出此圓。只要e比d0小1，發(fā)生e個(gè)錯(cuò)碼后錯(cuò)成的碼組不可能變成另一任何許用碼組，即有e≤d01。②當(dāng)碼字用于糾錯(cuò)時(shí)，為了能糾正任意≤t個(gè)錯(cuò)誤，最小碼距應(yīng)滿足：d0≥2t+1（8-2）這可以用圖8-3(b)來說明。若碼組A和碼組B發(fā)生不多于t位的錯(cuò)誤，則其位置均不超出以O(shè)1和O2為圓心，t為半徑的圓。只要這兩個(gè)圓不相交，則當(dāng)誤碼小于t時(shí)，根據(jù)它們落入哪個(gè)圓內(nèi)，就可以正確地判斷A或B，即可以糾正錯(cuò)誤。以O(shè)1和O2為圓心，t為半徑的兩圓不相交的最近圓心距離為2t+1，此即為糾正t個(gè)誤碼的最小碼距。③為了能糾正任意≤t個(gè)錯(cuò)誤，同時(shí)又能檢測出任意≤e個(gè)錯(cuò)誤，最小碼距應(yīng)滿足：d0≥e+t+1(e>t)（8-3）（簡稱糾檢在解釋此式之前，先來說明什么是“糾正t個(gè)錯(cuò)碼，同時(shí)又檢測e個(gè)錯(cuò)碼”結(jié)合）。在某些情況下，要求對于出現(xiàn)較頻繁但錯(cuò)碼數(shù)很少的碼組按前向糾錯(cuò)方式工作，以節(jié)省反饋重發(fā)時(shí)間，同時(shí)又希望對一些錯(cuò)碼數(shù)較多的碼組，在超過該碼的糾錯(cuò)能力時(shí)，能自動(dòng)按檢錯(cuò)重發(fā)方式工作，以降低系統(tǒng)的總誤碼率。這種工作方式就是“糾檢結(jié)合”。(a)(b)圖8-3碼距與檢錯(cuò)和糾錯(cuò)能力之間的關(guān)系(c)在上述“糾檢結(jié)合”系統(tǒng)中，差錯(cuò)控制設(shè)備按照接收碼組與許用碼組的距離自動(dòng)改變工則將按