第9章差錯控制編碼第9章

差錯控制編碼

9.1

引言9.2

常用簡單分組碼9.3

線性分組碼9.4

循環碼糾錯編碼的分類

（1）按照信道編碼的不同功能，可以將它分為檢錯碼和糾錯碼。（2）按照信息碼元和監督碼元之間的檢驗關系，可以將它分為線性碼和非線性碼。

（3）按照信息碼元和監督碼元之間的約束方式不同，可以將它分為分組碼和卷積碼。

（4）按照信息碼元在編碼后是否保持原來的形式，可以將它分為系統碼和非系統碼。（5）按照糾正錯誤的類型不同，可以將它分為糾正隨機錯誤碼和糾正突發錯誤碼。1.分組碼分組碼一般可用(n,k)表示。其中，k是每組二進制信息碼元的數目，n是編碼碼組的碼元總位數，又稱為碼組長度，簡稱碼長。

n－k＝r為每個碼組中的監督碼元數目。簡單地說，分組碼是對每段k位長的信息組以一定的規則增加r個監督元，組成長為n的碼字。

在二進制情況下，共有2k個不同的信息組，相應地可得到2k個不同的碼字，稱為許用碼組。其余2n－2k個碼字未被選用，稱為禁用碼組。

在分組碼中，非零碼元的數目稱為碼字的漢明(Hamming)重量，簡稱碼重。

例如，碼字10110，碼重w=3。兩個等長碼組之間相應位取值不同的數目稱為這兩個碼組的漢明(Hamming)距離，簡稱碼距。

例如11000

與10011之間的距離d=3。

碼組集中任意兩個碼字之間距離的最小值稱為碼的最小距離，用d０表示。最小碼距是碼的一個重要參數，它是衡量碼檢錯、糾錯能力的依據。

糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強。

分組碼的最小漢明距離d0與檢錯和糾錯能力之間滿足下列關系：

（1）當碼字用于檢測錯誤時，如果要檢測e個錯誤，則d0≥e+1；（2）當碼字用于糾正錯誤時，如果要糾正t個錯誤，則d0≥2

t+1；

（3）若碼字用于糾t個錯誤，同時檢e個錯誤時（e>t），則

d

0≥t+e+1

。

2.編碼效率

用差錯控制編碼提高通信系統的可靠性，是以降低有效性為代價換來的。我們定義編碼效率

來衡量有效性:η

＝

k

/

n

其中,k是信息元的個數，n為碼長。對糾錯碼的基本要求是:檢錯和糾錯能力盡量強；編碼效率盡量高；編碼規律盡量簡單。

實際中要根據具體指標要求，保證有一定糾、檢錯能力和編碼效率，并且易于實現。

假設在隨機信道中，“1”、“0”發送等概，誤碼率相同為p，且p?1，則容易證明，在碼長為n的碼組中正好發生r的錯碼概率為

。

例如，當碼長n=7，p=10－3時，則有

P7(1)≈7p=7×10-3

P7(2)≈21p2=2.1×10-5

P7(3)≈35p3=3.5×10-8

可見采用差錯控制編碼，若能糾正1~2個誤碼，就可使誤碼率下降幾個數量級。

差錯控制的作用（效果）9.4

線性分組碼

1基本概念

分組碼

將信息碼分組，每組由信碼附加若干監督碼組成。分組碼一般用符號（n,k）表示，k為每組信碼位數；n為每組編碼總位數，又稱為碼長；r＝n-k為每組中監督碼元數。

代數碼

建立在代數學基礎上的編碼稱為代數碼

線性碼碼組的信息碼和監督碼間約束關系按一組線性代數方程組構成。線性碼是一種代數碼。由此可見，將分組碼和線性碼的概念結合一起，即為線性分組碼。2線性分組碼的編碼原理

用特定的代數方程描述信息碼

與

監督碼之間的約束關系，稱該方程為監督方程。

接收端依照監督方程式進行計算，計算結果稱“校正子”，或“伴隨式”。

編碼的每個監督位對應一個監督方程和一個校正子。對（n,k）碼，由r＝n－k個監督方程計算得到的校正子有r位碼元，可給出2r－1種誤碼圖樣。

當出現一位誤碼時，會有2r－1種錯誤位置，由r位校正子取值會確定誤碼的確切位置，從而能糾錯。

顯然，當以（7,4）碼討論線性分組碼的構造

即n=7,k=4,r=3，編碼后7位碼組為A=(a6,a5,a4,a3,a2,a1,a0),其中a6,a5,a4,a3為信息碼，a2,a1,a0為監督碼，必存在三個

校正子S2,S1,S0。

校正子碼組

(S2,S1,S0)與

誤碼位置如表9-4所示由表可得出如下結論時，有可能構造出糾正一位甚至一位以上誤碼的線性分組碼。

①當a0、a3、a4或a6位置誤碼時，S2=1，否則S2=0；②當a1、a3、a5或a6位置誤碼時，S1=1，否則S1=0；③當a2、a4、a5或a6位置誤碼時，S0=1，否則S0=0；④表中共列出23－1＝7種誤碼位置，而當S2,S1,S0均為0時，表示無誤碼。由上述結論可得三個校正子計算方程：

S2S1S0誤碼位置S2S1S0誤碼位置100a0101a4010a101

1a5001a21

1

1a61

10a3000無誤碼表9-4S0=a6+a5+a4+a2,S1=a6+a5+a3+a1,S2=a6+a4+a3+a0

進而得到下面的方程組形式：

(9.4-7)式為監督碼生成方程組，在發端可利用該方程組構造(7,4)碼。接收端收到每個碼組后，計算出S3、S2和S1，如不全為0，則無誤碼。否則，可按表9-4確定誤碼的位置，并予以糾正。(9.4-7)3監督矩陣H和生成矩陣G

將（7,4）碼的三個監督方程式可重新改寫為如下形式：上式可以記作：HAT＝0

T

或AH

T

＝0

，其中也可用

矩陣形式

來表示：或

表示為：監督矩陣

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

＝

P

T，如果在Q矩陣的左邊再加上一個k×k的單位矩陣，就形成了一個新矩陣G：

4校正子S

設發送組碼A，在傳輸過程中有可能出現誤碼，這時接收到的碼組為B。則收發碼組之差為：則接收端利用接收到的

碼組B計算校正子：

S=B

H

T=(A+E)

H

T=A

H

T+E

H

T=E

H

T

因此，校正子僅與E有關，即錯誤圖樣與校正子之間有確定的關系。

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

（1）任意兩

許用碼

之和仍為一許用碼，也就是說，線性分組碼具有封閉性；（2）碼組間的

最小碼距等于非零碼

的

最小碼重

奇偶校驗

時

的

監督關系，在接收端解碼時，實際上就是在計算：

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

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

有錯。例設一線性碼生成矩陣確定(

n

,

k

)碼

中

的n

和k

值，并求出監督矩陣H

寫出監督碼位

的

關系式，以及該

(

n

,

k

)

碼

的所有

可用碼組

。確定該

線性碼

的最小碼距。解：1從已知的生成矩陣的行列數可知：n

=

6，k

=

3；將生成矩陣化成典型矩陣監督矩陣為：

2

由H

矩陣可確定監督關系：由3由于線性碼的最小碼距就是非0碼的

最小碼重，所以該分組碼的最小碼距為d0=3。

可得許用碼組為：9.5

循環碼

循環碼仍然是一種線性分組碼

。是研究最成熟的一種編碼；是建立在嚴密代數編碼理論基礎上；糾、檢錯能力強；編、譯碼方法和電路都不太復雜。

循環碼除有線性分組碼一般性質外，還有兩個主要特征。

1．封閉性循環碼的碼組中任意兩個

碼組之和（模2和）仍為一準用碼組。

2．循環性設一個（n,k）循環碼為

（an-1，an-2，…a1，a0），

在n

次左移

或

右移

的

循環

中形成的編碼，仍然是準用循環碼。在代數理論中，為了便于計算，常用碼多項式

表示

碼字。

(n

,

k)循環碼的碼字，其

碼多項式以

降冪順序排列

為循環碼T=（an-1，an-2，…a1，a0）左移一位，變成T(1)=（an-2，an-3，…a0，an-1），用多項式表示有

T(1)

(x)

＝

an－2

xn－1+an－3xn－2+，…+a0

x

1+a

n－1x

0

表中N＝6碼組可表示為

x6+x5+x2+1左移i

位

后的碼多項式有

碼多項式的按模運算性質整數運算中，若一整數m表示為

則在模n運算下，有m≡p（模n）。

任一多項式F(x)除以一個n次多項式N(x)，可得到商式Q(x)，和一個階數

小于n

的余式R(x)，即：F(x)/N(x)=Q(x)+R(x)/N(x)

記為：F

(x)≡

R

(x)[模N

(x)]

碼多項式T(x)左移i位后的結果。實際上，利用碼多項式的

xi

T(x)≡T(i)(x)[模

(xn+1)]該式說明，欲使碼多項式左移i位，可將被移碼多項式T(x)左乘xi，對其取模

(xn+1)即可。現以簡單地左移一位為例

xT(x)=an-1xn+an-2xn-1+，…+a1x2+a0x≡an-2xn-1+an-3xn-2+，…+a1x2+a0x+an-1x0=T(1)(x)[模(xn+1)]長度為n的許用碼組，必是按模(xn+1)運算的余式。

例

某循環碼T=（1100101），將其表示為碼多項式，并寫出左移2位后的碼多項式。

解：T(x)=x6+x5+x2+1x2T(x)=x8+x7+x4+x2=Q(x)(x7+1)+T(2)(x)則Q(x)=x+1

T(2)(x)=x4+x2+x+1即

T(2)=（0010111）

利用帶余除法循環碼的生成多項式和生成矩陣

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

g(x)是前k－1位為“0”的碼組。循環碼中，除全“0”碼外，連續“0”最多是k－1位，否則循環將得到k位為“0”；

g(x)是（n，k）碼中次數為n－k的唯一多項式，否則，兩個相加會出現連續“0”多于k位；

g(x)稱為碼生成多項式。

一旦

生成多項式g(x)確定

后，該循環碼的生成矩陣就可以確定。顯然，上式不符合形式，所以此生成矩陣不是

典型形式。當n=7,k=3,r=4,g(x)=x4+x2+x+1.可以得到整個碼組.T(x)可以被

g(x)整除

.循環碼的編、譯碼方法

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

（1）用x

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

（2）用g(x)除x

n－k.m(x),求商Q(x)和余式r(x)，也就是這樣我們就得到了余式r(x)。（3）編碼輸出循環碼多項式T(x)為：

這是由于循環碼多項式T(x)都可以被g(x)整除例如，（7，3）若選定g(x)=x4+x2+x+1，m(x)=x2+x,則

上式相當于

T(x)=1100000+101=1100101編碼輸出為

2、譯碼過程接收端譯碼要求有二:檢錯和糾錯。檢錯為目的，譯碼較簡單,糾錯較復雜.

檢錯譯碼任一碼組多項式T(x)都應能被生成多項式g(x)整除。

故只需對接收碼組R(x)用原生成多項式g(x)去除，若能整除（余數為0），接收碼無誤碼，R(x)=T(x)；若不能整除（余數不為0），接收碼有誤碼，R(x)≠T(x)。糾錯譯碼為了糾錯要求每個可糾正的錯誤圖樣必須與一個特定余式有一一對應關系。因此，糾錯可按如下步驟進行：

(1)

用生成多項式g(x)除接收碼組R(x)=T(x)+E(x)，得出余式r(x)，這一步與檢錯譯碼相同；

(2)

按余式r(x)用查表法或某種運算得到錯誤圖樣E(x)