第9章差錯(cuò)控制編碼第9章差錯(cuò)控制編碼第9章差錯(cuò)控制編碼

9.1引言9.2常用簡(jiǎn)單分組碼9.3線性分組碼9.4循環(huán)碼第9章差錯(cuò)控制編碼9.1引言糾錯(cuò)編碼的分類(lèi)

（1）按照信道編碼的不同功能，可以將它分為檢錯(cuò)碼和糾錯(cuò)碼。（2）按照信息碼元和監(jiān)督碼元之間的檢驗(yàn)關(guān)系，可以將它分為線性碼和非線性碼。

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

（4）按照信息碼元在編碼后是否保持原來(lái)的形式，可以將它分為系統(tǒng)碼和非系統(tǒng)碼。（5）按照糾正錯(cuò)誤的類(lèi)型不同，可以將它分為糾正隨機(jī)錯(cuò)誤碼和糾正突發(fā)錯(cuò)誤碼。糾錯(cuò)編碼的分類(lèi)1.分組碼分組碼一般可用(n,k)表示。其中，k是每組二進(jìn)制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱(chēng)為碼組長(zhǎng)度，簡(jiǎn)稱(chēng)碼長(zhǎng)。

n－k＝r為每個(gè)碼組中的監(jiān)督碼元數(shù)目。簡(jiǎn)單地說(shuō)，分組碼是對(duì)每段k位長(zhǎng)的信息組以一定的規(guī)則增加r個(gè)監(jiān)督元，組成長(zhǎng)為n的碼字。

在二進(jìn)制情況下，共有2k個(gè)不同的信息組，相應(yīng)地可得到2k個(gè)不同的碼字，稱(chēng)為許用碼組。其余2n－2k個(gè)碼字未被選用，稱(chēng)為禁用碼組。1.分組碼

在分組碼中，非零碼元的數(shù)目稱(chēng)為碼字的漢明(Hamming)重量，簡(jiǎn)稱(chēng)碼重。

例如，碼字10110，碼重w=3。兩個(gè)等長(zhǎng)碼組之間相應(yīng)位取值不同的數(shù)目稱(chēng)為這兩個(gè)碼組的漢明(Hamming)距離，簡(jiǎn)稱(chēng)碼距。

例如11000與10011之間的距離d=3。

碼組集中任意兩個(gè)碼字之間距離的最小值稱(chēng)為碼的最小距離，用d０表示。最小碼距是碼的一個(gè)重要參數(shù)，它是衡量碼檢錯(cuò)、糾錯(cuò)能力的依據(jù)。在分組碼中，非零碼元的數(shù)目稱(chēng)為碼字的漢明(H

糾錯(cuò)碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說(shuō)明碼字間的最小差別越大，抗干擾能力就越強(qiáng)。

分組碼的最小漢明距離d0與檢錯(cuò)和糾錯(cuò)能力之間滿足下列關(guān)系：

（1）當(dāng)碼字用于檢測(cè)錯(cuò)誤時(shí)，如果要檢測(cè)e個(gè)錯(cuò)誤，則d0≥e+1；（2）當(dāng)碼字用于糾正錯(cuò)誤時(shí)，如果要糾正t個(gè)錯(cuò)誤，則d0≥2

t+1；糾錯(cuò)碼的抗干擾能力完全取決于許用碼字之間的距離，碼的

（3）若碼字用于糾t個(gè)錯(cuò)誤，同時(shí)檢e個(gè)錯(cuò)誤時(shí)（e>t），則

d

0≥t+e+1。（3）若碼字用于糾t個(gè)錯(cuò)誤，同時(shí)檢e個(gè)錯(cuò)誤時(shí)（

2.編碼效率

用差錯(cuò)控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價(jià)換來(lái)的。我們定義編碼效率來(lái)衡量有效性:η

＝

k

/

n

其中,k是信息元的個(gè)數(shù)，n為碼長(zhǎng)。對(duì)糾錯(cuò)碼的基本要求是:檢錯(cuò)和糾錯(cuò)能力盡量強(qiáng)；編碼效率盡量高；編碼規(guī)律盡量簡(jiǎn)單。

實(shí)際中要根據(jù)具體指標(biāo)要求，保證有一定糾、檢錯(cuò)能力和編碼效率，并且易于實(shí)現(xiàn)。

2.編碼效率對(duì)糾錯(cuò)碼的基本要求是:檢錯(cuò)和糾假設(shè)在隨機(jī)信道中，“1”、“0”發(fā)送等概，誤碼率相同為p，且p?1，則容易證明，在碼長(zhǎng)為n的碼組中正好發(fā)生r的錯(cuò)碼概率為

。

例如，當(dāng)碼長(zhǎng)n=7，p=10－3時(shí)，則有

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

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

P7(3)≈35p3=3.5×10-8可見(jiàn)采用差錯(cuò)控制編碼，若能糾正1~2個(gè)誤碼，就可使誤碼率下降幾個(gè)數(shù)量級(jí)。

差錯(cuò)控制的作用（效果）假設(shè)在隨機(jī)信道中，“1”、“0”發(fā)送等概，誤碼率相同為p9.4線性分組碼

1基本概念

分組碼

將信息碼分組，每組由信碼附加若干監(jiān)督碼組成。分組碼一般用符號(hào)（n,k）表示，k為每組信碼位數(shù)；n為每組編碼總位數(shù)，又稱(chēng)為碼長(zhǎng)；r＝n-k為每組中監(jiān)督碼元數(shù)。

代數(shù)碼

建立在代數(shù)學(xué)基礎(chǔ)上的編碼稱(chēng)為代數(shù)碼

線性碼碼組的信息碼和監(jiān)督碼間約束關(guān)系按一組線性代數(shù)方程組構(gòu)成。線性碼是一種代數(shù)碼。由此可見(jiàn)，將分組碼和線性碼的概念結(jié)合一起，即為線性分組碼。9.4線性分組碼1基本概念2線性分組碼的編碼原理

用特定的代數(shù)方程描述信息碼

與

監(jiān)督碼之間的約束關(guān)系，稱(chēng)該方程為監(jiān)督方程。

接收端依照監(jiān)督方程式進(jìn)行計(jì)算，計(jì)算結(jié)果稱(chēng)“校正子”，或“伴隨式”。

編碼的每個(gè)監(jiān)督位對(duì)應(yīng)一個(gè)監(jiān)督方程和一個(gè)校正子。對(duì)（n,k）碼，由r＝n－k個(gè)監(jiān)督方程計(jì)算得到的校正子有r位碼元，可給出2r－1種誤碼圖樣。

當(dāng)出現(xiàn)一位誤碼時(shí)，會(huì)有2r－1種錯(cuò)誤位置，由r位校正子取值會(huì)確定誤碼的確切位置，從而能糾錯(cuò)。

顯然，當(dāng)2線性分組碼的編碼原理以（7,4）碼討論線性分組碼的構(gòu)造

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

校正子S2,S1,S0。

校正子碼組(S2,S1,S0)與

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

以（7,4）碼討論線性分組碼的構(gòu)造

即n=7,k=4,①當(dāng)a0、a3、a4或a6位置誤碼時(shí)，S2=1，否則S2=0；②當(dāng)a1、a3、a5或a6位置誤碼時(shí)，S1=1，否則S1=0；③當(dāng)a2、a4、a5或a6位置誤碼時(shí)，S0=1，否則S0=0；④表中共列出23－1＝7種誤碼位置，而當(dāng)S2,S1,S0均為0時(shí)，表示無(wú)誤碼。由上述結(jié)論可得三個(gè)校正子計(jì)算方程：

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

1a5001a21

1

1a61

10a3000無(wú)誤碼表9-4①當(dāng)a0、a3、a4或a6位置誤碼時(shí)，S2=1，否則S0=a6+a5+a4+a2,S1=a6+a5+a3+a1,S2=a6+a4+a3+a0

進(jìn)而得到下面的方程組形式：(9.4-7)式為監(jiān)督碼生成方程組，在發(fā)端可利用該方程組構(gòu)造(7,4)碼。接收端收到每個(gè)碼組后，計(jì)算出S3、S2和S1，如不全為0，則無(wú)誤碼。否則，可按表9-4確定誤碼的位置，并予以糾正。(9.4-7)S0=a6+a5+a4+a2,S1=a6+3監(jiān)督矩陣H和生成矩陣G

將（7,4）碼的三個(gè)監(jiān)督方程式可重新改寫(xiě)為如下形式：上式可以記作：HAT＝0

T

或AH

T

＝0，其中3監(jiān)督矩陣H和生成矩陣G上式可以記作：HAT＝0也可用

矩陣形式

來(lái)表示：或

表示為：監(jiān)督矩陣

H也可用矩陣形式來(lái)表示：或表示為：監(jiān)督矩陣H這里G稱(chēng)為生成矩陣，利用它可產(chǎn)生整個(gè)碼組：這時(shí)Q

＝

P

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

這里G稱(chēng)為生成矩陣，利用它可產(chǎn)生整個(gè)碼組：4校正子S

設(shè)發(fā)送組碼A，在傳輸過(guò)程中有可能出現(xiàn)誤碼，這時(shí)接收到的碼組為B。則收發(fā)碼組之差為：則接收端利用接收到的

碼組B計(jì)算校正子：

S=B

H

T=(A+E)

H

T=A

H

T+E

H

T=E

H

T

因此，校正子僅與E有關(guān)，即錯(cuò)誤圖樣與校正子之間有確定的關(guān)系。

其中：4校正子S則接收端利用接收到的碼組B計(jì)算6線性分組碼的主要性質(zhì)如下：

（1）任意兩

許用碼

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

最小碼距等于非零碼

的

最小碼重

奇偶校驗(yàn)

時(shí)

的

監(jiān)督關(guān)系，在接收端解碼時(shí)，實(shí)際上就是在計(jì)算：

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

若S＝0，則無(wú)錯(cuò)；若S＝1就認(rèn)為

有錯(cuò)。6線性分組碼的主要性質(zhì)如下：奇偶校驗(yàn)時(shí)的監(jiān)例設(shè)一線性碼生成矩陣確定(

n

,

k

)碼

中

的n和k值，并求出監(jiān)督矩陣H寫(xiě)出監(jiān)督碼位

的

關(guān)系式，以及該

(

n

,

k

)

碼

的所有

可用碼組

。確定該

線性碼

的最小碼距。例設(shè)一線性碼生成矩陣確定(n,k)解：1從已知的生成矩陣的行列數(shù)可知：n

=

6，k

=

3；將生成矩陣化成典型矩陣監(jiān)督矩陣為：解：1從已知的生成矩陣的行列數(shù)可知：n=6，k=2

由H

矩陣可確定監(jiān)督關(guān)系：2

由H矩陣可確定監(jiān)督關(guān)系：由3由于線性碼的最小碼距就是非0碼的

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

可得許用碼組為：由3由于線性碼的最小碼距就是非0碼的最小碼重，所以該9.5循環(huán)碼

循環(huán)碼仍然是一種線性分組碼

。是研究最成熟的一種編碼；是建立在嚴(yán)密代數(shù)編碼理論基礎(chǔ)上；糾、檢錯(cuò)能力強(qiáng)；編、譯碼方法和電路都不太復(fù)雜。

循環(huán)碼除有線性分組碼一般性質(zhì)外，還有兩個(gè)主要特征。1．封閉性循環(huán)碼的碼組中任意兩個(gè)

碼組之和（模2和）仍為一準(zhǔn)用碼組。2．循環(huán)性設(shè)一個(gè)（n,k）循環(huán)碼為

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

在n

次左移

或

右移

的

循環(huán)

中形成的編碼，仍然是準(zhǔn)用循環(huán)碼。9.5循環(huán)碼循環(huán)碼仍然是一種在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式

表示

碼字。(n

,

k)循環(huán)碼的碼字，其

碼多項(xiàng)式以

降冪順序排列

為在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式表示碼循環(huán)碼T=（an-1，an-2，…a1，a0）左移一位，變成T(1)=（an-2，an-3，…a0，an-1），用多項(xiàng)式表示有

T(1)

(x)

＝

an－2

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

x

1+a

n－1x

0

表中N＝6碼組可表示為

x6+x5+x2+1左移i

位

后的碼多項(xiàng)式有

循環(huán)碼T=（an-1，an-2，…a1，a0）左移一位碼多項(xiàng)式的按模運(yùn)算性質(zhì)整數(shù)運(yùn)算中，若一整數(shù)m表示為

則在模n運(yùn)算下，有m≡p（模n）。

任一多項(xiàng)式F(x)除以一個(gè)n次多項(xiàng)式N(x)，可得到商式Q(x)，和一個(gè)階數(shù)

小于n

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

記為：F

(x)≡

R

(x)[模N

(x)]

碼多項(xiàng)式的按模運(yùn)算性質(zhì)則在模n運(yùn)算下，有m≡p（模n碼多項(xiàng)式T(x)左移i位后的結(jié)果。實(shí)際上，利用碼多項(xiàng)式的

xi

T(x)≡T(i)(x)[模(xn+1)]該式說(shuō)明，欲使碼多項(xiàng)式左移i位，可將被移碼多項(xiàng)式T(x)左乘xi，對(duì)其取模(xn+1)即可?，F(xiàn)以簡(jiǎn)單地左移一位為例

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

碼多項(xiàng)式T(x)左移i位后的結(jié)果。實(shí)際上例

某循環(huán)碼T=（1100101），將其表示為碼多項(xiàng)式，并寫(xiě)出左移2位后的碼多項(xiàng)式。

解：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）

利用帶余除法例某循環(huán)碼T=（1100101），將其表示為碼多項(xiàng)式，并循環(huán)碼的生成多項(xiàng)式和生成矩陣

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

g(x)是前k－1位為“0”的碼組。循環(huán)碼中，除全“0”碼外，連續(xù)“0”最多是k－1位，否則循環(huán)將得到k位為“0”；g(x)是（n，k）碼中次數(shù)為n－k的唯一多項(xiàng)式，否則，兩個(gè)相加會(huì)出現(xiàn)連續(xù)“0”多于k位；

g(x)稱(chēng)為碼生成多項(xiàng)式。

循環(huán)碼的生成多項(xiàng)式和生成矩陣g(x)是前k－1一旦

生成多項(xiàng)式g(x)確定

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

典型形式。一旦生成多項(xiàng)式g(x)確定后，該循環(huán)碼的生成矩陣就當(dāng)n=7,k=3,r=4,g(x)=x4+x2+x+1.可以得到整個(gè)碼組.T(x)可以被

g(x)整除.當(dāng)n=7,k=3,r=4,g(x)=循環(huán)碼的編、譯碼方法

1、編碼過(guò)程首先需要根據(jù)給定循環(huán)碼的參數(shù)確定生成多項(xiàng)式g(x)，然后，利用循環(huán)碼的編碼特點(diǎn)，即所有循環(huán)碼多項(xiàng)式T(x)都可以被g(x)整除，來(lái)定義碼多項(xiàng)式T(x)。下面就將以上各步處理加以解釋?zhuān)?/p>

（1）用x

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

（2）用g(x)除x

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

這是由于循環(huán)碼多項(xiàng)式T(x)都可以被g(x)整除這樣我們就得到了余式r(x)。（3）編碼輸出循例如，（7，3）若選定g(x)=x4+x2+x+1，m(x)=x2+x,則

上式相當(dāng)于

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

例如，（7，3）若選定g(x)=x4+x2+x+1，m2、譯碼過(guò)程接收端譯碼要求有二:檢錯(cuò)和糾錯(cuò)。檢錯(cuò)為目的，譯碼較簡(jiǎn)單,糾錯(cuò)較復(fù)雜.

檢錯(cuò)譯碼任一碼組多項(xiàng)式T(x)都應(yīng)能被生成多項(xiàng)式g(x)整除。

故只需對(duì)接收碼組R(x)用原生成多項(xiàng)式g(x)去除，若能整除（余數(shù)為0），接收碼無(wú)誤碼，R(x)=T(x)；若不能整除（余數(shù)不為0），接收碼有誤碼，R(x)≠T(x)。2、譯碼過(guò)程檢錯(cuò)譯碼任一碼組多項(xiàng)式T(x)都應(yīng)能糾錯(cuò)譯碼為了糾錯(cuò)要求每個(gè)可糾正的錯(cuò)誤圖樣必須與一個(gè)特定余式有一一對(duì)應(yīng)關(guān)系。因此，糾錯(cuò)可按如下步驟進(jìn)行：(1)

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

按余式r(x)用查表法或某種運(yùn)算得到錯(cuò)誤圖樣E(x)，例如，通過(guò)計(jì)算校正子S，確定誤碼位置。這是較復(fù)雜的一步，需要把接收碼組R(x)暫時(shí)緩存起來(lái)，對(duì)糾正突發(fā)錯(cuò)誤和單個(gè)錯(cuò)誤較簡(jiǎn)單，但對(duì)糾正多個(gè)隨機(jī)錯(cuò)誤的編碼確十分復(fù)雜。（3）從R(x)中減去E(x)便得到已糾正錯(cuò)誤的原發(fā)送碼組T(x)。

糾錯(cuò)譯碼為了糾錯(cuò)要求每個(gè)可糾正的錯(cuò)誤圖樣必須與一9.6卷積碼

9.6.1基本概念

卷積碼中編碼后的n個(gè)碼元不僅

與

當(dāng)前段的k

個(gè)信息

有關(guān)

，而且也

與

前面(N－1)段

的

信息有關(guān)

，編碼過(guò)程中相互關(guān)聯(lián)

的

碼元為n

N個(gè)。

因此，這N段時(shí)間內(nèi)的碼元數(shù)目

n

N

通常被稱(chēng)為這種碼的約束長(zhǎng)度

。

也常稱(chēng)N為約束長(zhǎng)度，它以碼組個(gè)數(shù)為單位，并用（n，k，N）表示卷積碼。9.6卷積碼9.6.1基本概念卷積碼中編圖9-8卷積碼(3,1,3)編碼器

起始狀態(tài)

，各級(jí)移位寄存器清零

，即M3M2M1為000。

M3等于當(dāng)前輸入數(shù)據(jù)

，而移位寄存器狀態(tài)M2M1存儲(chǔ)以前的數(shù)據(jù)；

輸出碼字

C

由下式確定圖9-8卷積碼(3,1,3)編碼器9.6.2卷積碼的描述1.樹(shù)圖圖9-10(3,1,3)碼的樹(shù)圖9.6.2卷積碼的描述1.樹(shù)圖圖9-10(3,2.網(wǎng)格圖

圖9-11(3,1,3)碼的格圖2.網(wǎng)格圖圖9-11(3,1,3)碼的格圖3.狀態(tài)圖

圖9-12(3,1,3)碼的狀態(tài)圖

3.狀態(tài)圖圖9-12(3,1,3)碼的狀態(tài)圖

思考題P318

9-1，9-5，9-6，9-10，9-11習(xí)題P319-320

9-5，9-7，9-8，9-12思考題P318第9章差錯(cuò)控制編碼第9章差錯(cuò)控制編碼第9章差錯(cuò)控制編碼

9.1引言9.2常用簡(jiǎn)單分組碼9.3線性分組碼9.4循環(huán)碼第9章差錯(cuò)控制編碼9.1引言糾錯(cuò)編碼的分類(lèi)

（1）按照信道編碼的不同功能，可以將它分為檢錯(cuò)碼和糾錯(cuò)碼。（2）按照信息碼元和監(jiān)督碼元之間的檢驗(yàn)關(guān)系，可以將它分為線性碼和非線性碼。

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

（4）按照信息碼元在編碼后是否保持原來(lái)的形式，可以將它分為系統(tǒng)碼和非系統(tǒng)碼。（5）按照糾正錯(cuò)誤的類(lèi)型不同，可以將它分為糾正隨機(jī)錯(cuò)誤碼和糾正突發(fā)錯(cuò)誤碼。糾錯(cuò)編碼的分類(lèi)1.分組碼分組碼一般可用(n,k)表示。其中，k是每組二進(jìn)制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱(chēng)為碼組長(zhǎng)度，簡(jiǎn)稱(chēng)碼長(zhǎng)。

n－k＝r為每個(gè)碼組中的監(jiān)督碼元數(shù)目。簡(jiǎn)單地說(shuō)，分組碼是對(duì)每段k位長(zhǎng)的信息組以一定的規(guī)則增加r個(gè)監(jiān)督元，組成長(zhǎng)為n的碼字。

在二進(jìn)制情況下，共有2k個(gè)不同的信息組，相應(yīng)地可得到2k個(gè)不同的碼字，稱(chēng)為許用碼組。其余2n－2k個(gè)碼字未被選用，稱(chēng)為禁用碼組。1.分組碼

在分組碼中，非零碼元的數(shù)目稱(chēng)為碼字的漢明(Hamming)重量，簡(jiǎn)稱(chēng)碼重。

例如，碼字10110，碼重w=3。兩個(gè)等長(zhǎng)碼組之間相應(yīng)位取值不同的數(shù)目稱(chēng)為這兩個(gè)碼組的漢明(Hamming)距離，簡(jiǎn)稱(chēng)碼距。

例如11000與10011之間的距離d=3。

碼組集中任意兩個(gè)碼字之間距離的最小值稱(chēng)為碼的最小距離，用d０表示。最小碼距是碼的一個(gè)重要參數(shù)，它是衡量碼檢錯(cuò)、糾錯(cuò)能力的依據(jù)。在分組碼中，非零碼元的數(shù)目稱(chēng)為碼字的漢明(H

糾錯(cuò)碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說(shuō)明碼字間的最小差別越大，抗干擾能力就越強(qiáng)。

分組碼的最小漢明距離d0與檢錯(cuò)和糾錯(cuò)能力之間滿足下列關(guān)系：

（1）當(dāng)碼字用于檢測(cè)錯(cuò)誤時(shí)，如果要檢測(cè)e個(gè)錯(cuò)誤，則d0≥e+1；（2）當(dāng)碼字用于糾正錯(cuò)誤時(shí)，如果要糾正t個(gè)錯(cuò)誤，則d0≥2

t+1；糾錯(cuò)碼的抗干擾能力完全取決于許用碼字之間的距離，碼的

（3）若碼字用于糾t個(gè)錯(cuò)誤，同時(shí)檢e個(gè)錯(cuò)誤時(shí)（e>t），則

d

0≥t+e+1。（3）若碼字用于糾t個(gè)錯(cuò)誤，同時(shí)檢e個(gè)錯(cuò)誤時(shí)（

2.編碼效率

用差錯(cuò)控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價(jià)換來(lái)的。我們定義編碼效率來(lái)衡量有效性:η

＝

k

/

n

其中,k是信息元的個(gè)數(shù)，n為碼長(zhǎng)。對(duì)糾錯(cuò)碼的基本要求是:檢錯(cuò)和糾錯(cuò)能力盡量強(qiáng)；編碼效率盡量高；編碼規(guī)律盡量簡(jiǎn)單。

實(shí)際中要根據(jù)具體指標(biāo)要求，保證有一定糾、檢錯(cuò)能力和編碼效率，并且易于實(shí)現(xiàn)。

2.編碼效率對(duì)糾錯(cuò)碼的基本要求是:檢錯(cuò)和糾假設(shè)在隨機(jī)信道中，“1”、“0”發(fā)送等概，誤碼率相同為p，且p?1，則容易證明，在碼長(zhǎng)為n的碼組中正好發(fā)生r的錯(cuò)碼概率為

。

例如，當(dāng)碼長(zhǎng)n=7，p=10－3時(shí)，則有

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

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

P7(3)≈35p3=3.5×10-8可見(jiàn)采用差錯(cuò)控制編碼，若能糾正1~2個(gè)誤碼，就可使誤碼率下降幾個(gè)數(shù)量級(jí)。

差錯(cuò)控制的作用（效果）假設(shè)在隨機(jī)信道中，“1”、“0”發(fā)送等概，誤碼率相同為p9.4線性分組碼

1基本概念

分組碼

將信息碼分組，每組由信碼附加若干監(jiān)督碼組成。分組碼一般用符號(hào)（n,k）表示，k為每組信碼位數(shù)；n為每組編碼總位數(shù)，又稱(chēng)為碼長(zhǎng)；r＝n-k為每組中監(jiān)督碼元數(shù)。

代數(shù)碼

建立在代數(shù)學(xué)基礎(chǔ)上的編碼稱(chēng)為代數(shù)碼

線性碼碼組的信息碼和監(jiān)督碼間約束關(guān)系按一組線性代數(shù)方程組構(gòu)成。線性碼是一種代數(shù)碼。由此可見(jiàn)，將分組碼和線性碼的概念結(jié)合一起，即為線性分組碼。9.4線性分組碼1基本概念2線性分組碼的編碼原理

用特定的代數(shù)方程描述信息碼

與

監(jiān)督碼之間的約束關(guān)系，稱(chēng)該方程為監(jiān)督方程。

接收端依照監(jiān)督方程式進(jìn)行計(jì)算，計(jì)算結(jié)果稱(chēng)“校正子”，或“伴隨式”。

編碼的每個(gè)監(jiān)督位對(duì)應(yīng)一個(gè)監(jiān)督方程和一個(gè)校正子。對(duì)（n,k）碼，由r＝n－k個(gè)監(jiān)督方程計(jì)算得到的校正子有r位碼元，可給出2r－1種誤碼圖樣。

當(dāng)出現(xiàn)一位誤碼時(shí)，會(huì)有2r－1種錯(cuò)誤位置，由r位校正子取值會(huì)確定誤碼的確切位置，從而能糾錯(cuò)。

顯然，當(dāng)2線性分組碼的編碼原理以（7,4）碼討論線性分組碼的構(gòu)造

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

校正子S2,S1,S0。

校正子碼組(S2,S1,S0)與

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

以（7,4）碼討論線性分組碼的構(gòu)造

即n=7,k=4,①當(dāng)a0、a3、a4或a6位置誤碼時(shí)，S2=1，否則S2=0；②當(dāng)a1、a3、a5或a6位置誤碼時(shí)，S1=1，否則S1=0；③當(dāng)a2、a4、a5或a6位置誤碼時(shí)，S0=1，否則S0=0；④表中共列出23－1＝7種誤碼位置，而當(dāng)S2,S1,S0均為0時(shí)，表示無(wú)誤碼。由上述結(jié)論可得三個(gè)校正子計(jì)算方程：

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

1a5001a21

1

1a61

10a3000無(wú)誤碼表9-4①當(dāng)a0、a3、a4或a6位置誤碼時(shí)，S2=1，否則S0=a6+a5+a4+a2,S1=a6+a5+a3+a1,S2=a6+a4+a3+a0

進(jìn)而得到下面的方程組形式：(9.4-7)式為監(jiān)督碼生成方程組，在發(fā)端可利用該方程組構(gòu)造(7,4)碼。接收端收到每個(gè)碼組后，計(jì)算出S3、S2和S1，如不全為0，則無(wú)誤碼。否則，可按表9-4確定誤碼的位置，并予以糾正。(9.4-7)S0=a6+a5+a4+a2,S1=a6+3監(jiān)督矩陣H和生成矩陣G

將（7,4）碼的三個(gè)監(jiān)督方程式可重新改寫(xiě)為如下形式：上式可以記作：HAT＝0

T

或AH

T

＝0，其中3監(jiān)督矩陣H和生成矩陣G上式可以記作：HAT＝0也可用

矩陣形式

來(lái)表示：或

表示為：監(jiān)督矩陣

H也可用矩陣形式來(lái)表示：或表示為：監(jiān)督矩陣H這里G稱(chēng)為生成矩陣，利用它可產(chǎn)生整個(gè)碼組：這時(shí)Q

＝

P

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

這里G稱(chēng)為生成矩陣，利用它可產(chǎn)生整個(gè)碼組：4校正子S

設(shè)發(fā)送組碼A，在傳輸過(guò)程中有可能出現(xiàn)誤碼，這時(shí)接收到的碼組為B。則收發(fā)碼組之差為：則接收端利用接收到的

碼組B計(jì)算校正子：

S=B

H

T=(A+E)

H

T=A

H

T+E

H

T=E

H

T

因此，校正子僅與E有關(guān)，即錯(cuò)誤圖樣與校正子之間有確定的關(guān)系。

其中：4校正子S則接收端利用接收到的碼組B計(jì)算6線性分組碼的主要性質(zhì)如下：

（1）任意兩

許用碼

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

最小碼距等于非零碼

的

最小碼重

奇偶校驗(yàn)

時(shí)

的

監(jiān)督關(guān)系，在接收端解碼時(shí)，實(shí)際上就是在計(jì)算：

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

若S＝0，則無(wú)錯(cuò)；若S＝1就認(rèn)為

有錯(cuò)。6線性分組碼的主要性質(zhì)如下：奇偶校驗(yàn)時(shí)的監(jiān)例設(shè)一線性碼生成矩陣確定(

n

,

k

)碼

中

的n和k值，并求出監(jiān)督矩陣H寫(xiě)出監(jiān)督碼位

的

關(guān)系式，以及該

(

n

,

k

)

碼

的所有

可用碼組

。確定該

線性碼

的最小碼距。例設(shè)一線性碼生成矩陣確定(n,k)解：1從已知的生成矩陣的行列數(shù)可知：n

=

6，k

=

3；將生成矩陣化成典型矩陣監(jiān)督矩陣為：解：1從已知的生成矩陣的行列數(shù)可知：n=6，k=2

由H

矩陣可確定監(jiān)督關(guān)系：2

由H矩陣可確定監(jiān)督關(guān)系：由3由于線性碼的最小碼距就是非0碼的

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

可得許用碼組為：由3由于線性碼的最小碼距就是非0碼的最小碼重，所以該9.5循環(huán)碼

循環(huán)碼仍然是一種線性分組碼

。是研究最成熟的一種編碼；是建立在嚴(yán)密代數(shù)編碼理論基礎(chǔ)上；糾、檢錯(cuò)能力強(qiáng)；編、譯碼方法和電路都不太復(fù)雜。

循環(huán)碼除有線性分組碼一般性質(zhì)外，還有兩個(gè)主要特征。1．封閉性循環(huán)碼的碼組中任意兩個(gè)

碼組之和（模2和）仍為一準(zhǔn)用碼組。2．循環(huán)性設(shè)一個(gè)（n,k）循環(huán)碼為

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

在n

次左移

或

右移

的

循環(huán)

中形成的編碼，仍然是準(zhǔn)用循環(huán)碼。9.5循環(huán)碼循環(huán)碼仍然是一種在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式

表示

碼字。(n

,

k)循環(huán)碼的碼字，其

碼多項(xiàng)式以

降冪順序排列

為在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式表示碼循環(huán)碼T=（an-1，an-2，…a1，a0）左移一位，變成T(1)=（an-2，an-3，…a0，an-1），用多項(xiàng)式表示有

T(1)

(x)

＝

an－2

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

x

1+a

n－1x

0

表中N＝6碼組可表示為

x6+x5+x2+1左移i

位

后的碼多項(xiàng)式有

循環(huán)碼T=（an-1，an-2，…a1，a0）左移一位碼多項(xiàng)式的按模運(yùn)算性質(zhì)整數(shù)運(yùn)算中，若一整數(shù)m表示為

則在模n運(yùn)算下，有m≡p（模n）。

任一多項(xiàng)式F(x)除以一個(gè)n次多項(xiàng)式N(x)，可得到商式Q(x)，和一個(gè)階數(shù)

小于n

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

記為：F

(x)≡

R

(x)[模N

(x)]

碼多項(xiàng)式的按模運(yùn)算性質(zhì)則在模n運(yùn)算下，有m≡p（模n碼多項(xiàng)式T(x)左移i位后的結(jié)果。實(shí)際上，利用碼多項(xiàng)式的

xi

T(x)≡T(i)(x)[模(xn+1)]該式說(shuō)明，欲使碼多項(xiàng)式左移i位，可將被移碼多項(xiàng)式T(x)左乘xi，對(duì)其取模(xn+1)即可。現(xiàn)以簡(jiǎn)單地左移一位為例

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

碼多項(xiàng)式T(x)左移i位后的結(jié)果。實(shí)際上例

某循環(huán)碼T=（1100101），將其表示為碼多項(xiàng)式，并寫(xiě)出左移2位后的碼多項(xiàng)式。

解：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）

利用帶余除法例某循環(huán)碼T=（1100101），將其表示為碼多項(xiàng)式，并循環(huán)碼的生成多項(xiàng)式和生成矩陣

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

g(x)是前k－1位為“0”的碼組。循環(huán)碼中，除全“0”碼外，連續(xù)“0”最多是k－1位，否則循環(huán)將得到k位為“0”；g(x)是（n，k）碼中次數(shù)為n－k的唯一多項(xiàng)式，否則，兩個(gè)相加會(huì)出現(xiàn)連續(xù)“0”多于k位；

g(x)稱(chēng)為碼生成多項(xiàng)式。

循環(huán)碼的生成多項(xiàng)式和生成矩陣g(x)是前k－1一旦

生成多項(xiàng)式g(x)確定

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

典型形式。一旦生成多項(xiàng)式g(x)確定后，該循環(huán)碼的生成矩陣就當(dāng)n=7,k=3,r=4,g(x)=x4+x2+x+1.可以得到整個(gè)碼組.T(x)可以被

g(x)整除.當(dāng)n=7,k=3,r=4,g(x)=循環(huán)碼的編、譯碼方法

1、編碼過(guò)程首先需要根據(jù)給定循環(huán)碼的參數(shù)確定生成多項(xiàng)式g(x)，然后，利用循環(huán)碼的編碼特點(diǎn)，即所有循環(huán)碼多項(xiàng)式T(x)都可以被g(