2023/9/151第7章差錯控制編碼7.1概述7.2簡單的差錯控制編碼7.3線性分組碼7.4循環(huán)碼7.5

卷積碼2023/9/1527.1概述

7.1.1信源編碼與信道編碼的基本概念

信源編碼：將模擬信息源的輸出轉化為數(shù)字信號的過程；可以提高數(shù)字信號傳輸?shù)挠行浴Ｐ诺谰幋a：在信息序列上附加一些監(jiān)督碼元，利用這些冗余的碼元，使原來不規(guī)律的或規(guī)律性不強的原始數(shù)字信號變?yōu)橛幸?guī)律的數(shù)字信號，差錯控制譯碼則利用這些規(guī)律性來鑒別傳輸過程是否發(fā)生錯誤，或進而糾正錯誤?？梢蕴岣邤?shù)字通信的可靠性。2023/9/153在差錯控制系統(tǒng)中，信道編碼存在著多種實現(xiàn)方式，同時信道編碼也有多種分類方法。①按照信道編碼的不同功能，可以將信道編碼分為檢錯碼和糾錯碼。糾正碼可以糾正誤碼，當然同時具有檢錯的能力，當發(fā)現(xiàn)不可糾正的錯誤時可以發(fā)出錯誤提示。②按照信息碼元和監(jiān)督碼元之間的檢驗關系，可以將信道編碼分為線性和非線性碼。若信息碼元與監(jiān)督碼元之間的關系為線性關系，即滿足一組線性方程式，稱為線性碼；否則，稱為非線性碼。7.1.2糾錯編碼的分類2023/9/154③按照信息碼元和監(jiān)督碼元之間的約束方式不同，可以將信道編碼分為分組碼和卷積碼。在分組碼中，編碼后的碼元序列每n位分為一組，其中k位信息碼元，r個監(jiān)督位，r=n-k。監(jiān)督碼元僅與本碼字中的信息碼元有關。卷積碼則不同，監(jiān)督碼元不但與本信息碼元有關，而且與前面碼字的信息碼元也有約束關系。④按照信息碼元在編碼后是否保持原來的形式，可以將信道編碼分為系統(tǒng)碼和非系統(tǒng)碼。在系統(tǒng)編碼中，編碼后的信息碼元保持原樣不變，而非系統(tǒng)碼中的信息碼元則發(fā)生了變化。7.1.2糾錯編碼的分類2023/9/155⑤按照糾正錯誤的類型不同，可以將信道編碼分為糾正隨機錯誤碼和糾正突發(fā)錯誤碼。前者主要用于發(fā)生零星獨立錯誤的信道，而后者用于對付以突發(fā)錯誤為主的信道。⑥按照信道編碼所采用的數(shù)學方法不同，可以將信道編碼分為代數(shù)碼、幾何碼和算術碼。7.1.2糾錯編碼的分類2023/9/1567.1.3差錯控制方式2023/9/1571、檢錯重發(fā)方式：檢錯重發(fā)（ARQ）的優(yōu)點主要表現(xiàn)在：

（1）只需要少量的冗余碼，就可以得到極低的輸出誤碼率；（2）有一定的自適應能力；

某些不足主要表現(xiàn)在：（1）需要反向信道，故不能用于單向傳輸系統(tǒng)，并且實現(xiàn)重發(fā)控制比較復雜；

（2）通信效率低，不適合嚴格實時傳輸系統(tǒng)。2023/9/1582、前向糾錯發(fā)送端經信道編碼后可以發(fā)出具有糾錯能力的碼字；接收端譯碼后不僅可以發(fā)現(xiàn)錯誤碼，而且可以判斷錯誤碼的位置并予以自動糾正。

3、混合糾錯方式混合糾錯方式是前向糾錯方式和檢錯重發(fā)方式的結合。2023/9/159信道編碼的基本思想是在被傳送的信息中附加一些監(jiān)督碼元，在兩者之間建立某種校驗關系，當這種校驗關系因傳輸錯誤而受到破壞時，可以被發(fā)現(xiàn)并予以糾正。這種檢錯和糾錯能力是用信息量的冗余度來換取的。7.1.4糾錯編碼的基本原理2023/9/1510

碼長：碼字中碼元的數(shù)目；

碼重：碼字中非0數(shù)字的數(shù)目；

碼距：兩個等長碼字之間對應位不同的數(shù)目，有時也稱作這兩個碼字的漢明距離。

最小碼距：在碼字集合中全體碼字之間距離的最小數(shù)值。糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強。

2023/9/1511

2023/9/15127.2簡單的差錯控制編碼

7.2.1奇偶監(jiān)督碼

可以表示成為（n，n-1）。如果是奇監(jiān)督碼，在附加上一個監(jiān)督元以后，碼長為n的碼字中“1”的個數(shù)為奇數(shù)個；如果是偶監(jiān)督碼，在附加上一個監(jiān)督元以后，碼長為n的碼字中“1”的個數(shù)為偶數(shù)個。

an-1+an-2+…

+

a1+a0=02023/9/1513

奇偶監(jiān)督碼的編碼可以用軟件實現(xiàn)，也可用硬件電路實現(xiàn)。

如果碼組B無錯，B＝A，則M＝0；如果碼組B有單個（或奇數(shù)個）錯誤，則M＝1。編碼效率:R=(n-1)/n2023/9/15147.2.2行列監(jiān)督碼行列監(jiān)督碼又稱水平垂直一致監(jiān)督碼或二維奇偶監(jiān)督碼，有時還被稱為矩陣碼。1100101000010000110101111000011001110000101010101000101110001111002023/9/1515

二維奇偶監(jiān)督碼適于檢測突發(fā)錯碼。二維奇偶監(jiān)督碼不僅可用來檢錯，還可用來糾正一些錯碼。

7.2.3恒比碼

恒比碼又稱等重碼，該碼的碼字中1和0的位數(shù)保持恒定的比例。

目前我國電傳通信中普遍采用3：2碼，國際上通用的ARQ電報通信系統(tǒng)中，采用3：4碼即7中取3碼。2023/9/15167.3線性分組碼

7.3.1線性分組碼的基本概念

分組碼是一組固定長度的碼組，可表示為（n,k），通常它用于前向糾錯。在編碼時，k個信息位被編為n位碼組長度，而n-k個監(jiān)督位的作用就是實現(xiàn)檢錯與糾錯。這樣，一個k比特信息的線性分組碼可以映射到一個長度為n碼組上。

2023/9/1517

線性分組碼的主要性質如下：

（1）任意兩許用碼之和仍為一許用碼，也就是說，線性分組碼具有封閉性；（2）碼組間的最小碼距等于非零碼的最小碼重。對偶校驗時的監(jiān)督關系。在接收端解碼時，實際上就是在計算：

S=bn-1+bn-2+…+b1+b0

若S＝0，則無錯；若S＝1就認為有錯。

2023/9/1518

以（7，4）碼為例進行分析，可以設碼字A=[a6,a5,

a4,a3a2,a1,a0]，其中[a6,a5,

a4,a3]為信息位，[a2,a1,a0]為監(jiān)督位，進而得到下面的方程組形式：不難看出，上述（7，4）碼的最小碼距dmin＝3。2023/9/1519

(1)監(jiān)督矩陣H和生成矩陣G

將（7，4）碼的三個監(jiān)督方程式可以重新改寫為如下形式：上式可以記作：HAT=0T或AHT=0

，其中2023/9/1520也可以用矩陣形式來表示：或表示成為：這時Q=PT，如果在Q矩陣的左邊在加上一個k×k的單位矩陣，就形成了一個新矩陣G：

2023/9/1521

這里G稱為生成矩陣，利用它可以產生整個碼組：

(2)校驗子S

設發(fā)送組碼A，在傳輸過程中有可能出現(xiàn)誤碼，這時接收到的碼組為B。則收發(fā)碼組之差為：2023/9/1522其中：則接收端利用接收到的碼組B計算校正子：S=BHT=(A+E)HT=AHT+EHT=EHT

因此，校正子僅與E有關，即錯誤圖樣與校正子之間有確定的關系。漢明碼就是一個線性分組碼。有以下特點：

（1）最小碼距dmin＝3，可糾正一位錯誤；（2）碼長n與監(jiān)督元個數(shù)r之間滿足2023/9/15237.3線性分組碼

2023/9/15247.4循環(huán)碼

循環(huán)碼是線性分組碼的一個重要子集，是目前研究得最成熟的一類碼，它有許多特殊的代數(shù)性質。

特點：循環(huán)碼中任一許用碼組經過循環(huán)移位后，所得到的碼組仍然是許用碼組。

描述：許用循環(huán)碼A=(an-1an-2…a1a0)，可以將它的碼多項式表示為：2023/9/1525若一個整數(shù)m可以表示為:

則在模n運算下，有m≡p（模n），同樣對于多項式而言：則可以寫為：F(x)≡R(x)（模N(x)）。在循環(huán)碼中，若A(x)是一個長為n的許用碼組，則在按模運算下，亦是一個許用碼組。2023/9/15267.4.1生成多項式及生成矩陣

循環(huán)碼中次數(shù)最低的碼多項式稱為生成多項式，用g(x)表示?？梢宰C明生成多項式g(x)具有以下特性：（1）g(x)是一個常數(shù)項為1的次多項式；（2）g(x)是的一個因式；（3）該循環(huán)碼中其它碼多項式都是g(x)的倍式。

2023/9/1527

為了保證構成的生成矩陣G的各行線性不相關，通常用g(x)來構造生成矩陣，顯然，上式不符合形式，所以此生成矩陣不是典型形式。

因此，一旦生成多項式g(x)確定以后，該循環(huán)碼的生成矩陣就可以確定。

2023/9/15287.4.2監(jiān)督多項式及監(jiān)督矩陣

利用循環(huán)碼的特點來確定監(jiān)督矩陣H：

由于（n,k）循環(huán)碼中g(x)是xn+1的因式，因此可令：

監(jiān)督矩陣表示為：其中：2023/9/15297.4.3循環(huán)碼的編碼與譯碼方法

1、編碼過程首先需要根據(jù)給定循環(huán)碼的參數(shù)確定生成多項式g(x)，然后，利用循環(huán)碼的編碼特點，即所有循環(huán)碼多項式A(x)都可以被g(x)整除，來定義生成多項式A(x)。下面就將以上各步處理加以解釋：

（1）用xn-k乘m(x)。這一運算實際上是把信息碼后附加上（n-k）個“0”。

2023/9/1530

（2）求R(x)。由于循環(huán)碼多項式A(x)都可以被g(x)整除，也就是：上式也等效于：這樣我們就得到了R(x)。（3）編碼輸出系統(tǒng)循環(huán)碼多項式A(x)為：

2023/9/1531

上述三步編碼過程，在硬件實現(xiàn)時，可以利用除法電路來實現(xiàn)。

循環(huán)碼的譯碼可以分三步進行：

（1）由接收到的碼多項式B(x)計算校正子（伴隨式）多項式S(x)；2023/9/1532

（2）由校正子S(x)確定錯誤圖樣E(x)；（3）將錯誤圖樣E(x)與B(x)相加，糾正錯誤。2023/9/15337.5卷積碼

卷積碼中編碼后的n個碼元不僅與當前段的k個信息有關，而且也與前面（N-1）段的信息有關，編碼過程中相互關聯(lián)的碼元為nN個。因此，這N段時間內的碼元數(shù)目nN通常被稱為這種碼的約束長度。由于與前面m段規(guī)定時間內的信息位有關，這里的m＝