第11章差錯控制編碼本章知識點:1、了解差錯控制技術種類

2、掌握糾錯編碼原理、最小碼距和檢錯、糾錯之間關系；了解奇偶監督碼、恒比碼編碼方法。

3、掌握線性分組碼編碼和譯碼方法

4、掌握循環碼編碼和譯碼方法11.1

概述11.2

糾錯編碼的基本原理11.3

糾錯編碼的性能11.4

簡單的實用編碼11.5

線性分組碼11.6

循環碼11.7

卷積碼11.8Turbo碼11.9

低密度奇偶校驗碼11.10

網格編碼調制11.11

小結第11章差錯控制編碼2023年7月29日3為保證運送途中不出現打碎燈泡的情況——有效性——可靠性11.1概述2023年7月29日4

通信中的情況：針對乘性干擾針對加性干擾合理選擇調制/解調方法，增大發射功率—采用均衡等措施11.1概述2023年7月29日511.1概述

差錯控制編碼2023年7月29日611.1概述信道分類(從差錯控制角度看)：隨機信道：錯碼的出現是隨機的。突發信道：錯碼是成串集中出現的。混合信道：既存在隨機錯碼又存在突發錯碼。差錯控制技術的種類：檢錯重發前向糾錯反饋校驗檢錯刪除信道編碼分類：線性碼和非線性碼分組碼和卷積碼系統碼和非系統碼2023年7月29日711.1概述不同的編碼方法，有不同的檢錯或糾錯能力。多余度：就是指增加的監督碼元多少。例如，若編碼序列中平均每兩個信息碼元就添加一個監督碼元，則這種編碼的多余度為1/3。編碼效率(簡稱碼率)：設編碼序列中信息碼元數量為k，總碼元數量為n，則比值k/n就是碼率。冗余度：監督碼元數(n-k)和信息碼元數k之比。理論上，差錯控制以降低信息傳輸速率為代價換取提高傳輸可靠性。監督碼元：在4種差錯控制技術中除第3種外，都是在接收端識別有無錯碼。所以在發送端需要在信息碼元序列中增加一些差錯控制碼元，它們稱為監督碼元。2023年7月29日811.2糾錯編碼的基本原理1、分組碼基本原理

將信息碼分組，為每組信息碼附加若干監督碼的編碼稱為分組碼。在分組碼中，監督碼元僅監督本碼組中的信息碼元。

卷積碼又稱連環碼。卷積碼編碼器把k比特信息段編成n比特的碼組，但所編的n長碼組不僅同當前的k比特信息段有關，而且還同前面的(N-1)個(N>1,整數)信息段有關聯。分組碼卷積碼2023年7月29日911.2糾錯編碼的基本原理1、分組碼基本原理規則：使碼組中“1”的個數為偶數情形1：沒有冗余——不能發現錯誤情形2：加入冗余

——可以發現錯誤

冗余?另外4個碼組許用碼組禁用碼組2023年7月29日1011.2糾錯編碼的基本原理1、分組碼基本原理規則：使碼組中“1”的個數為偶數情形1：沒有冗余——不能發現錯誤情形2：加入冗余

——可以發現錯誤

冗余?另外4個碼組許用碼組禁用碼組

只能檢出一個碼組中1個和3個(奇數)錯碼的情況，不能發現2個(偶數)錯碼的情況，也不能糾正錯誤。2023年7月29日1111.2糾錯編碼的基本原理1、分組碼基本原理情形1：沒有冗余——不能發現錯誤情形2：加入冗余

——可以發現錯誤許用禁用2023年7月29日1211.2糾錯編碼的基本原理1、分組碼基本原理這時，能夠發現2個以下錯碼，或者糾正

1位錯碼。2023年7月29日1311.2糾錯編碼的基本原理1、分組碼基本原理綜上所述不同的編碼方法，檢錯或糾錯能力也不同。2023年7月29日1411.2糾錯編碼的基本原理1、分組碼基本原理分組碼的一般結構：分組碼的符號：(n,k)n－碼組的總位數，又稱為碼組的長度(碼長);k－碼組中信息碼元的數目;n–k＝r－碼組中的監督碼元數目，或稱監督位數目。2023年7月29日1511.2糾錯編碼的基本原理2、碼重和碼組碼重(w)：碼距(d)：把碼組中“1”的個數目，簡稱碼重。把兩個碼組中對應位上數字不同的位數，即兩個碼組對應位模2和的重量，稱為碼組的距離，簡稱碼距。碼距又稱漢明距離。碼長(n)：碼組(碼字)中的碼元個數。“011011”

的距離為

3

碼重為

32023年7月29日1611.2糾錯編碼的基本原理2、碼重和碼組碼重(w)：碼距(d)：最小碼距(d0)：把碼組中“1”的個數目，簡稱碼重。把兩個碼組中對應位上數字不同的位數，即兩個碼組對應位模2和的重量，稱為碼組的距離，簡稱碼距。碼距又稱漢明距離。把某種編碼中各個碼組之間距離的最小值稱為最小碼距(d0)。若是線性碼，d0就等于(非全零)碼組的最小重量。一種編碼的檢錯和糾錯能力決定于最小碼距d0

。碼長(n)：碼組(碼字)中的碼元個數。2023年7月29日1711.2糾錯編碼的基本原理3、最小碼距與糾檢錯能力(n,k)分組碼，糾(檢)錯能力為：

(1)為檢測e個錯碼，要求最小碼距d0

e+1(2)為了糾正t個錯碼，要求最小碼距d0

2t+1(3)為糾正t個錯碼，同時檢測e個錯碼，要求最小碼距2023年7月29日1811.2糾錯編碼的基本原理3、最小碼距與糾檢錯能力(n,k)分組碼，糾(檢)錯能力為：

(1)為檢測e個錯碼，要求最小碼距d0

e+1(2)為了糾正t個錯碼，要求最小碼距d0

2t+1(3)為糾正t個錯碼，同時檢測e個錯碼，要求最小碼距2023年7月29日1911.2糾錯編碼的基本原理4、編碼效率和編碼增益編碼效率簡稱碼率：冗余度：編碼增益：監督碼元數(n-k)和信息碼元數k的比值，即(n-k)/k。

信息碼元數k與編碼組的總碼元數(即碼長)n的比值。

在保持誤碼率恒定條件下，采用糾錯編碼所節省的信噪比稱為編碼增益。2023年7月29日2011.4簡單的實用編碼11.4.1奇偶監督碼

奇偶監督碼是最簡單的檢錯碼，監督位只有1位，因此碼率Rc=(n-1)/n很高。設編碼組為，其中前n-1位為信息碼，第n位為監督碼a0。

若a0的加入使碼組中的“1”的數目為偶數，即滿足條件：，則稱為偶數監督碼。

若a0的加入使碼組中的“1”的數目為奇數，即滿足條件：，則稱為奇數監督碼。

這種編碼能夠檢測奇數個錯碼。但對突發差錯的漏檢率接近于1/2。監督關系式校正子2023年7月29日2111.4簡單的實用編碼11.4.1奇偶監督碼

奇偶監督碼是最簡單的檢錯碼，監督位只有1位，因此碼率Rc=(n-1)/n很高。設編碼組為，其中前n-1位為信息碼，第n位為監督碼a0。

若a0的加入使碼組中的“1”的數目為偶數，即滿足條件：，則稱為偶數監督碼。

若a0的加入使碼組中的“1”的數目為奇數，即滿足條件：，則稱為奇數監督碼。

適用：檢測隨機出現的零星差錯。很高（因為只有一位監督位）。

碼率：2023年7月29日2211.4簡單的實用編碼11.4.2二維奇偶監督碼（方陣碼）

先把上述奇偶監督碼的若干碼組排成矩陣，每一碼組寫成一行，然后再按列的方向增加第二維監督位。糾檢能力：有較強的檢錯能力，并有一定的糾錯能力。適用：適于檢測長度不大于行數(或列數)的突發錯誤。2023年7月29日2311.4簡單的實用編碼11.4.3恒比碼

檢測方法：計算接收碼組中“1”的數目，就可知是否有錯。適用：用于電報傳輸系統或其他鍵盤設備產生的字母和符號。編碼規則：個許用碼組，可分別用來代表26個英文字母及其他符號。2023年7月29日2411.5線性分組碼代數碼：建立在代數學基礎上的編碼。具有封閉性，即任意兩個許用碼組之和(逐位模2加)仍為一許用碼組。它的最小碼距等于非全零碼組的最小重量。線性碼：按照一組線性方程構成的代數碼。在線性碼中信息位和監督位是由一些線性代數方程聯系著的。線性分組碼：按照一組線性方程構成的分組碼。線性分組碼的性質：2023年7月29日2511.5線性分組碼1、漢明碼若要構造具有糾錯能力的（n，k）碼，則需增加督元的數目。

當“=”成立時，構造的線性分組碼稱為漢明碼

漢明碼是一種能夠糾正1位錯碼，且編碼效率較高的一種線性分組碼。

其特點是d0=3(能夠糾正一個錯碼或檢兩個錯碼)，碼長n與監督位數r＝n－k滿足關系式n=2r-1。2023年7月29日2611.5線性分組碼1、漢明碼(7,4)漢明碼例

在(7,4)碼中，n=7，k=4，r＝n－k=3。設碼組為a6

a5

a0，其中信息碼元為a6

a5

a4

a3

，監督碼元為a2

a1a0

。用S1、S2和S3表示3個監督關系式中的校正子(又稱校驗子、伴隨式)。若S=0就認為無錯碼；若S=1就認為有錯碼。2023年7月29日2711.5線性分組碼1、漢明碼(7,4)漢明碼例

僅當一位錯碼的位置在a2

、a4、a5或a6

時，校正子S1為1；否則S1為

0。同理：2023年7月29日2811.5線性分組碼1、漢明碼(7,4)漢明碼例(A)2023年7月29日2911.5線性分組碼1、漢明碼(7,4)漢明碼例(A)2023年7月29日3011.5線性分組碼1、漢明碼(7,4)漢明碼例接收端譯碼——檢錯糾錯過程2023年7月29日3111.5線性分組碼1、漢明碼

一般來說，若碼長為n，信息位數為k，則監督位數r＝n－k。如果希望用r個監督位構造出r個監督關系式來指示1位錯碼的n種可能位置，則要求：

對于漢明碼，上式取等號。這表明用來糾正單個錯誤時，漢明碼所用的監督位最少。與碼長相同的其他糾正單個錯誤的碼相比，其碼率最高。

表中所列的(7,4)漢明碼的最小碼距d0=3。因此，這種碼能夠糾正1個錯碼或檢測2個錯碼。由于碼率k/n=(n-r)/n=1–r/n，故當n很大和r很小時，碼率接近1。可見，漢明碼是一種高效碼。2023年7月29日3211.5線性分組碼2、監督矩陣（H矩陣）

監督碼元和信息碼元之間的關系稱為監督方程。將它改寫為：可以表示成矩陣形式：簡記為：HAT=0T

或AHT=0A=[a6

a5

a4

a3

a2

a1

a0]0=[000]右上標“T”表示將矩陣轉置。將H稱為監督矩陣。2023年7月29日3311.5線性分組碼2、監督矩陣（H矩陣）討論：(1)監督矩陣H是一個r×n階(r行n列)矩陣。(2)任一發送碼組A都滿足式HAT=0T的關系。也就是說只要監督矩陣H給定，編碼時監督位和信息位的關系就完全確定了。

H的每行中的“1”的位置表示相應碼元之間存在的監督關系。例如，H的第一行1110100表示監督位a2是由a6

a5

a4

之和決定的。

(n,k)碼的H矩陣必須有r=n-k行，且各行必須是線性無關的。2023年7月29日3411.5線性分組碼2、監督矩陣（H矩陣）討論：(3)H矩陣可以分成兩部分：(4)典型H矩陣的各行一定是線性無關的。非典型形式的監督矩陣可以經過初等行運算化為典型陣。式中，P為r

k階矩陣，Ir為r

r階單位方陣。具有[PIr]形式的H矩陣稱為典型監督矩陣。由典型監督矩陣及信息碼元很容易算出各監督碼元。(7，4)碼r=32023年7月29日3511.5線性分組碼3、生成矩陣（G矩陣）漢明碼例子中的監督位公式為：也可以改寫成矩陣形式：或者寫成：式中，Q為一個k

r階矩陣，它為P的轉置，即：

上式表示，在信息位給定后，用信息位的行矩陣乘矩陣Q就產生出監督位。P陣Q陣

Q=PT

2023年7月29日3611.5線性分組碼3、生成矩陣（G矩陣）將Q的左邊加上1個kk階單位方陣，就構成1個矩陣G。G稱為生成矩陣，因為由它可以產生整個碼組，即有：或者2023年7月29日3711.5線性分組碼3、生成矩陣（G矩陣）討論：(1)生成矩陣G是一個k×n階矩陣。(2)具有[IkQ]形式的生成矩陣稱為典型生成矩陣，由它產生的分組碼稱為系統碼。

(3)典型生成矩陣G和典型監督矩陣H之間由Q=PT或P=QT相聯系。即：若知H=[PIr]，則由Q=PT

，可得G=[IkQ]

若知G=[IkQ]，則由P=QT

，可得H=[PIr]2023年7月29日3811.5線性分組碼3、生成矩陣（G矩陣）討論：(4)任一碼組A都是G的各行的線性組合。G的各行本身就是一個許用碼組。(5)非典型形式的生成矩陣經過初等行運算也一定可以化為典型陣。(6)注意：H矩陣、G矩陣的各行應該線性無關的。2023年7月29日3911.5線性分組碼4、校正子S與譯碼錯誤圖樣

若ei=0，表示該接收碼元無錯；若ei=1，則表示該接收碼元有錯。設發送碼組A=[a6

a5

a4

a3

a2

a1

a0]，接收碼組，則錯誤圖樣(收發碼組之差)為：B–A=E(模2)式中2023年7月29日4011.5線性分組碼4、校正子S與譯碼S和E的關系接收端計算校正子為：可以改寫成

B=A+E(模2)S=BHT=

(A+E)HT

=A

HT+E

HT=E

HT由于AHT=0，所以校正子S只E與有關，即S和錯碼E之間有確定的線性變換關系。2023年7月29日4111.5線性分組碼4、校正子S與譯碼譯碼

對接收碼組B計算校正子：S=BHT

；譯碼過程即糾錯和檢錯的過程。其步驟如下：

若S=0(全0陣)，表示接收碼組B無錯；若S≠0，則由S=E

HT解得錯誤圖樣E；

由B=A+E(模2)可得到糾錯后的碼組為A=B+E

。2023年7月29日4211.6循環碼

循環碼是(n,k)線性分組碼的一個重要子類。其編解碼設備簡單，檢(糾)錯能力較強。有RS、BCH等高效子類碼，實際應用廣泛。循環碼除了具有線性分組碼的一般性質外，還具有循環性。2023年7月29日4311.6循環碼循環性：是指任一碼組循環一位(即將最右端的一個碼元移至左端，或反之)以后，仍為該碼中的一個碼組。表中的第2

碼組向右移一位即得到第

5碼組；(7,3)循環碼表中的第6

碼組向右移一位即得到第3碼組。2023年7月29日4411.6循環碼1、碼多項式在代數編碼理論中為了便于運算，常以多項式來表示碼組。

碼字（1100101）的多項式可表示為：

多項式的系數就是碼組中的各碼元，x

僅是碼元位置標記。n=7時

一個長度為n的碼組A=[an-1

an-2

…a0]可以表示成多項式形式：2023年7月29日4511.6循環碼1、碼多項式碼多項式的按模運算若一個整數m可以表示為 （Q

為整數）

m

p

(模n)則在模n運算下，有2023年7月29日4611.6循環碼1、碼多項式碼多項式的按模運算或則式中，碼多項式系數之間的加法和乘法仍按模2運算。2023年7月29日4711.6循環碼1、碼多項式碼多項式的按模運算

解運算過程：即有則有2023年7月29日4811.6循環碼

在循環碼中，若A(x)是一個長為n的許用碼組，則xiA(x)在按模xn+1運算下，也是該編碼中的一個許用碼組，即若：則A(x)也是該編碼中的一個許用碼組。1、碼多項式2023年7月29日4911.6循環碼2、生成多項式g(x)1)存在性

在一個(n,k)循環碼中，有一個且僅有一個次數為(n–k)的多項式：

這唯一的(n–k)次多項式g(x)為碼的生成多項式。g(x)表示該循環碼的前(k-1)位皆為“0”的碼組。2023年7月29日5011.6循環碼(2)所有碼多項式A(x)都可被g(x)整除，而且任意一個次數不大于(k-1)的多項式乘g(x)都是碼多項式。

該條性質可用于編碼，還可用于驗證接收碼組是否出錯。2、生成多項式g(x)2)性質(1)g(x)是一個：常數項為1；最高次數為(n-k)次；是xn+1的一個因式。

該條性質給我們提供了一種對于給定的(n,k)循環碼，尋找或確定其生成多項式的方法。2023年7月29日5111.6循環碼3、生成矩陣G在循環碼中，一個(n,k)碼有2k個不同的碼組。若用g(x)表示其中前(k-1)位皆為“0”的碼組，則g(x)，xg(x)，x2g(x)，…，xk-1g(x)都是碼組，而且這k個碼組是線性無關的。因此它們可以用來構成此循環碼的生成矩陣G

。

由于此式不符合G=[IkQ]的形式，所以它不是典型陣。將其作線性變換，可化成典型陣。一旦確定g(x)，整個(n,k)循環碼就被確定了。g(x)是循環碼的核心。對于給定的k位信息碼，由g(x)構造出G(x)，從而產生(n,k)循環碼。2023年7月29日5211.6循環碼4、循環碼的編碼方法一：對于給定的信息碼m(x)，相應的碼多項式A(x)=m(x)g(x)，它是非系統碼。方法二：m(x)與G(x)相乘。此法得到的是非系統碼；若先將生成矩陣G(x)化為典型陣，則可得到系統碼。2023年7月29日5311.6循環碼4、循環碼的編碼方法三：A(x)=xn-km(x)+r(x)，屬系統碼。編碼步驟如下：(1)用xn-k乘m(x)。這一運算實際上是在信息碼后附加上(n–k)個“0”。(2)用g(x)除xn-km(x)，得到商Q(x)和余式r(x)，即：(3)編出的碼組T(x)為：A(x)=xn-km(x)+r(x)

由以上編碼步驟可見，編碼的核心是如何確定余式r(x)，找到后r(x)，可直接將所