數(shù)字通信原理 糾錯(cuò)編碼

數(shù)字通信原理糾錯(cuò)編碼第一頁(yè)，共八十七頁(yè)，2022年，8月28日本章內(nèi)容在數(shù)字通信系統(tǒng)中所處的位置：第二頁(yè)，共八十七頁(yè)，2022年，8月28日

差錯(cuò)控制編碼，又稱信道編碼、可靠性編碼、抗干擾編碼或糾錯(cuò)碼，它是提高數(shù)字信號(hào)傳輸可靠性的有效方法之一。它產(chǎn)生于20世紀(jì)50年代初，發(fā)展到70年代趨向成熟。本章將主要分析信道編碼的基本原理、介紹常用的檢錯(cuò)碼、線性分組碼及卷積碼的構(gòu)造原理及其應(yīng)用。10.1概述第三頁(yè)，共八十七頁(yè)，2022年，8月28日一、信源編碼和信道編碼

在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。

信源編碼是為了提高數(shù)字通信的有效性以及使模擬信號(hào)數(shù)字化而采取的編碼技術(shù)。

信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。

10.1概述第四頁(yè)，共八十七頁(yè)，2022年，8月28日數(shù)字信號(hào)在傳輸過程中受到干擾的影響，使信號(hào)波形變壞，發(fā)生誤碼，可以采用一些方法解決。差錯(cuò)出現(xiàn)原因外界噪聲傳輸中碼間串?dāng)_解決方法合理地設(shè)計(jì)基帶信號(hào)，選擇調(diào)制、解調(diào)方式，采用均衡技術(shù)，提高發(fā)送功率等因素，使誤比特率降低。差錯(cuò)控制編碼。第五頁(yè)，共八十七頁(yè)，2022年，8月28日

差錯(cuò)控制的基本原理

在信息碼上附加一定位數(shù)的監(jiān)督碼元，使其與信息位按某種規(guī)則相互關(guān)聯(lián)；若數(shù)據(jù)在傳輸過程中發(fā)生差錯(cuò)，關(guān)聯(lián)關(guān)系被破壞，從而可檢出和/或糾正錯(cuò)誤。第六頁(yè)，共八十七頁(yè)，2022年，8月28日差錯(cuò)控制編碼的分類

線性碼：信息碼與監(jiān)督碼之間的關(guān)系為線性關(guān)系；

非線性碼：信息碼與監(jiān)督碼之間的關(guān)系為非線性關(guān)系。

分組碼：監(jiān)督碼只與本組信息碼有系；

卷積碼：監(jiān)督碼與本組和前面碼組中的信息碼有關(guān)。

系統(tǒng)碼：編碼后碼組中信息碼保持原圖樣順序不變；

非系統(tǒng)碼：編碼后碼組中原信息碼原圖樣發(fā)生變化。第七頁(yè)，共八十七頁(yè)，2022年，8月28日誤碼的主要形式

隨機(jī)錯(cuò)誤：誤碼的位置隨機(jī)（誤碼間無(wú)關(guān)聯(lián)），隨機(jī)誤碼主要由白噪聲引起。

突發(fā)錯(cuò)誤：誤碼成串出現(xiàn)，主要由強(qiáng)脈沖及雷電等突發(fā)的強(qiáng)干擾引起。

混合錯(cuò)誤：以上兩種誤碼及產(chǎn)生原因的組合。第八頁(yè)，共八十七頁(yè)，2022年，8月28日10.1.2差錯(cuò)控制類型1、檢錯(cuò)重發(fā)（ARQAutomaticRepeatRequest）:在發(fā)送端采用具有檢錯(cuò)功能的編碼，接收端發(fā)現(xiàn)出錯(cuò)后自動(dòng)請(qǐng)求重發(fā).有以下三種方式：停止---等待ARQ第九頁(yè)，共八十七頁(yè)，2022年，8月28日具有回拉功能的連續(xù)ARQ

具有選擇性重發(fā)功能的連續(xù)ARQ特點(diǎn)：設(shè)備較簡(jiǎn)單；傳輸序列中冗余量較??；需要有反向信道支持；出錯(cuò)后重傳造成延時(shí)較大。第十頁(yè)，共八十七頁(yè)，2022年，8月28日2、前向糾錯(cuò)方式（FECForwardErrorCorrection)發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼，收端收到信碼后自動(dòng)地糾正傳輸中的錯(cuò)誤特點(diǎn)：無(wú)需反饋信道，無(wú)需重傳，延時(shí)?。粋鬏斝蛄兄腥哂嗔枯^大。運(yùn)用在移動(dòng)通信系統(tǒng)、軍事系統(tǒng)通信中。3、混合糾錯(cuò)方式HEC(HybridErrorCorrection)混合糾錯(cuò)方式記作是FEC和ARQ方式的結(jié)合。出錯(cuò)較少時(shí)FEC起作用；出錯(cuò)較多時(shí)ARQ起作用第十一頁(yè)，共八十七頁(yè)，2022年，8月28日?qǐng)D10-1差錯(cuò)控制方式總結(jié)：第十二頁(yè)，共八十七頁(yè)，2022年，8月28日信道編碼的核心問題發(fā)現(xiàn)錯(cuò)誤糾正錯(cuò)誤第十三頁(yè)，共八十七頁(yè)，2022年，8月28日碼長(zhǎng)：碼字中碼元的個(gè)數(shù)，通常用n表示。碼重：碼字中非零碼元的個(gè)數(shù)定義為該碼字的重量，簡(jiǎn)稱碼重。如“10011”碼字的碼重為3。碼距：兩個(gè)等長(zhǎng)碼字之間對(duì)應(yīng)碼元不同的數(shù)目，通常用d表示。兩個(gè)碼字對(duì)應(yīng)位模2相加得到的新碼組的重量就是這兩個(gè)碼字之間的距離。

（1）幾個(gè)概念第十四頁(yè)，共八十七頁(yè)，2022年，8月28日編碼效率：信息碼元數(shù)與碼長(zhǎng)之比，通常用表示，其中k為信息碼元的數(shù)目，n為碼長(zhǎng)。最小碼距：在一個(gè)碼字集合中，任意兩個(gè)碼字間距離的最小值，即碼字集合中任意兩元素間的最小距離，記為dmin或d0糾錯(cuò)碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說(shuō)明碼字間的最小差別越大，抗干擾能力就越強(qiáng)。第十五頁(yè)，共八十七頁(yè)，2022年，8月28日舉例說(shuō)明：假如要傳送A、B兩個(gè)消息編碼一：消息A----“0”；消息B----“1”最小碼距1若傳輸中產(chǎn)生錯(cuò)碼（“0”錯(cuò)成“1”或“1”錯(cuò)成“0”）收端無(wú)法發(fā)現(xiàn)，該編碼無(wú)檢錯(cuò)糾錯(cuò)能力。第十六頁(yè)，共八十七頁(yè)，2022年，8月28日編碼二：消息A----“00”；消息B----“11”最小碼距2若傳輸中產(chǎn)生一位錯(cuò)碼，則變成“01”或“10”，收端判決為有錯(cuò)（因“01”“10”為禁用碼組），但無(wú)法確定錯(cuò)碼位置，不能糾正，該編碼具有檢出一位錯(cuò)碼的能力。這表明增加一位冗余碼元后碼具有檢出一位錯(cuò)碼的能力第十七頁(yè)，共八十七頁(yè)，2022年，8月28日編碼三：消息A----“000”；消息B----“111”最小碼距3傳輸中產(chǎn)生一位即使兩位錯(cuò)碼，都將變成禁用碼組，收端判決傳輸有錯(cuò)。該編碼具有檢出兩位錯(cuò)碼的能力。在產(chǎn)生一位錯(cuò)碼情況下，收端可根據(jù)“大數(shù)”法則進(jìn)行正確判決，能夠糾正這一位錯(cuò)碼。例如收到110，認(rèn)為是111。這表明增加兩位冗余碼元后碼具有檢出兩位錯(cuò)碼及糾正一位錯(cuò)碼的能力。第十八頁(yè)，共八十七頁(yè)，2022年，8月28日一個(gè)碼能檢測(cè)e個(gè)錯(cuò)碼，則要求其最小碼dmin≥e+1一個(gè)碼能糾正t個(gè)錯(cuò)碼，則要求其最小dmin≥2t+1一個(gè)碼能糾正t個(gè)錯(cuò)碼，同時(shí)能檢測(cè)e個(gè)錯(cuò)碼，則要求其最小碼距 dmin≥e+t+1(e>t)（2）最小碼距與檢錯(cuò)和糾錯(cuò)能力的關(guān)系第十九頁(yè)，共八十七頁(yè)，2022年，8月28日奇偶監(jiān)督碼二維奇偶監(jiān)督碼（略，見附錄）恒比碼10.2常用的幾種簡(jiǎn)單分組碼第二十頁(yè)，共八十七頁(yè)，2022年，8月28日10.2.1奇偶監(jiān)督碼奇偶監(jiān)督碼：在信息碼元后附加一位監(jiān)督位，使得碼組中奇偶監(jiān)督碼“1”的個(gè)數(shù)為偶數(shù)或奇數(shù)。第二十一頁(yè)，共八十七頁(yè)，2022年，8月28日序號(hào)碼長(zhǎng)為4的奇監(jiān)督碼序號(hào)碼長(zhǎng)為4的偶監(jiān)督碼信息碼元監(jiān)督碼元信息碼元監(jiān)督碼元00001000001001010011201002010130111301104100041001510115101061101611007111071111表：碼長(zhǎng)為4的奇、偶監(jiān)督碼第二十二頁(yè)，共八十七頁(yè)，2022年，8月28日只能檢測(cè)出單個(gè)或奇數(shù)個(gè)錯(cuò)誤，不能檢測(cè)偶數(shù)個(gè)錯(cuò)誤不能糾錯(cuò)。應(yīng)用：以隨機(jī)錯(cuò)誤為主的計(jì)算機(jī)通信系統(tǒng)，難于對(duì)付突發(fā)錯(cuò)誤編碼效率=k/n=k/(k+1)，是一種高效率碼。10.2.2二維奇偶監(jiān)督碼見附錄第二十三頁(yè)，共八十七頁(yè)，2022年，8月28日表10-13∶2恒比碼（是一種五中取三碼）10.2.3恒比碼碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。又稱等重碼，定1碼。這種碼在檢測(cè)時(shí)，通過計(jì)算接收碼元中1的數(shù)目是否正確，就知道有無(wú)錯(cuò)誤。第二十四頁(yè)，共八十七頁(yè)，2022年，8月28日

線性分組碼：先將信息碼分組，然后給每組信碼附加若干監(jiān)督碼的編碼稱為分組碼。若附加的監(jiān)督碼和信息碼由一些線性代數(shù)方程相則稱為線性分組碼。用符號(hào)(n,k)表示，k是信息碼的位數(shù)，n是編碼組總位數(shù)，又稱為碼長(zhǎng)，r=n-k為監(jiān)督位數(shù)。1、基本概念10.3線性分組碼（重點(diǎn)）第二十五頁(yè)，共八十七頁(yè)，2022年，8月28日現(xiàn)以(7,4)分組碼為例來(lái)說(shuō)明線性分組碼的特點(diǎn)。設(shè)其碼字為A=［a6

a5

a4

a3

a2

a1

a0］，其中前4位是信息元，后3位是監(jiān)督元，可用下列線性方程組來(lái)描述該分組碼，產(chǎn)生監(jiān)督元。第二十六頁(yè)，共八十七頁(yè)，2022年，8月28日表10-2(7,4)碼的碼字表第二十七頁(yè)，共八十七頁(yè)，2022年，8月28日2、線性分組碼的性質(zhì)任意兩個(gè)許用碼組之和（逐位模2和）仍為一許用碼組，即具有封閉性。最小碼距=非零碼的最小碼重（1的個(gè)數(shù)）。第二十八頁(yè)，共八十七頁(yè)，2022年，8月28日10.3.2監(jiān)督矩陣H和生成矩陣G

第二十九頁(yè)，共八十七頁(yè)，2022年，8月28日其中,P為r×k階矩陣，Ir為r×r階單位矩陣?？梢詫懗蒆=［PIr］形式的矩陣稱為典型監(jiān)督矩陣。HAT=0T，說(shuō)明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來(lái)作為判斷接收碼字A是否出錯(cuò)的依據(jù)。并簡(jiǎn)記為第三十頁(yè)，共八十七頁(yè)，2022年，8月28日r×n階矩陣監(jiān)督矩陣H確定了編碼時(shí)監(jiān)督碼元與信息碼元的關(guān)系把具有[P·Ir]形式的H矩陣稱為典型形式的監(jiān)督矩陣，其中P為r×k階矩陣,Ir為r×r階單位方陣H矩陣的各行應(yīng)線性無(wú)關(guān)。矩陣若能寫成典型形式，則其各行一定線性無(wú)關(guān)監(jiān)督矩陣H特點(diǎn)第三十一頁(yè)，共八十七頁(yè)，2022年，8月28日若把監(jiān)督方程補(bǔ)充為下列方程第三十二頁(yè)，共八十七頁(yè)，2022年，8月28日可改寫為矩陣形式第三十三頁(yè)，共八十七頁(yè)，2022年，8月28日第三十四頁(yè)，共八十七頁(yè)，2022年，8月28日k×n階矩陣把具有[Ik·Q]形式的G矩陣稱為典型形式的生成矩陣，其中，Ik為k×k階單位方陣，Q為k×r階矩陣由典型生成矩陣產(chǎn)生的分組碼一定是系統(tǒng)碼G矩陣的各行應(yīng)線性無(wú)關(guān)，每行均為許用碼組生成矩陣G特點(diǎn)第三十五頁(yè)，共八十七頁(yè)，2022年，8月28日已知（6，3）漢明碼(能糾正單個(gè)錯(cuò)誤的線性分組碼)的生成矩陣如下，(1)列出所有許用碼組;(2)最小碼距d0;(3)檢錯(cuò)糾錯(cuò)能力(4)編碼效率第三十六頁(yè)，共八十七頁(yè)，2022年，8月28日（1）信息碼編碼碼字碼重00000000000010011103010010011301101110141001001013101101011411011011041111110003第三十七頁(yè)，共八十七頁(yè)，2022年，8月28日（3）（4）（2）第三十八頁(yè)，共八十七頁(yè)，2022年，8月28日設(shè)（7,4）線性碼的生成矩陣G為：當(dāng)信息位為0001時(shí)，（1）試求其后的監(jiān)督位。（2）監(jiān)督矩陣H第三十九頁(yè)，共八十七頁(yè)，2022年，8月28日解：（1）第四十頁(yè)，共八十七頁(yè)，2022年，8月28日（2）監(jiān)督矩陣H根據(jù)生成矩陣和監(jiān)督矩陣的關(guān)系： G=[Ik·Q]，H=[P·Ir]其中P=QT，可得監(jiān)督矩陣H為：第四十一頁(yè)，共八十七頁(yè)，2022年，8月28日錯(cuò)誤矩陣/錯(cuò)誤圖樣E：設(shè)發(fā)送碼組為A，接收碼組為B，則錯(cuò)誤矩陣10.3.3伴隨式(校正子)S

第四十二頁(yè)，共八十七頁(yè)，2022年，8月28日接收端計(jì)算校正子S，即S=BHT=(A+E)HT=AHT+EHT=0+EHT=EHT

校正子只與E有關(guān)，即錯(cuò)誤圖樣與校正子之間有確定的關(guān)系.確定錯(cuò)誤圖樣與校正子的關(guān)系表?？蓮谋碇姓业缅e(cuò)碼位置，加以糾正。第四十三頁(yè)，共八十七頁(yè)，2022年，8月28日表10-3(7,4)碼S與E的對(duì)應(yīng)關(guān)系第四十四頁(yè)，共八十七頁(yè)，2022年，8月28日以（7，4）漢明碼為例設(shè)發(fā)送碼組A=（0001011）接收碼組B=（0000011）則收端譯碼過程如下：①計(jì)算校正子②查表得b3為錯(cuò)誤位置，即可糾正（0001011）第四十五頁(yè)，共八十七頁(yè)，2022年，8月28日10.4循環(huán)碼循環(huán)碼是一種重要的線性分組碼。這種碼的編碼和解碼設(shè)備都不太復(fù)雜，且有較強(qiáng)的檢（糾）錯(cuò)能力。共n位，通常前k位為信息位，后r位為監(jiān)督位。10.4.1循環(huán)碼的編碼原理第四十六頁(yè)，共八十七頁(yè)，2022年，8月28日循環(huán)碼的特點(diǎn)：

封閉性；

循環(huán)性；即碼中任一碼組循環(huán)一位(將最右端的碼元移到左端或反之）以后，仍為該碼中的一個(gè)碼組。第四十七頁(yè)，共八十七頁(yè)，2022年，8月28日若(an-1,an-2……,a1,a0)是一(n,k)循環(huán)碼的碼組，則(an-2,an-3,……,a1,a0,an-1)(an-3,an-4,……,a0,an-1,an-2)…………(a0,an-1,an-2,an-3,……,a2,a1)也都是該循環(huán)碼的碼組。第四十八頁(yè)，共八十七頁(yè)，2022年，8月28日表一種（7，3）循環(huán)碼的全部碼字序號(hào)碼字

序號(hào)碼字信息位a6a5a4監(jiān)督位a3a2a1a0信息位a6a5a4監(jiān)督位a3a2a1a010

0

00

0

0

051

0

01

0

1

120

0

10

1

1

161

0

11

1

0

030

1

01

1

1

071

1

00

1

0

140

1

11

0

0

181

1

10

0

1

0第四十九頁(yè)，共八十七頁(yè)，2022年，8月28日把碼長(zhǎng)為n的碼組中的各碼元當(dāng)作n-1次多項(xiàng)式的系數(shù)若碼組A=（an-1，an-2，……，a1，a0)，則其相應(yīng)的碼多項(xiàng)式為(以降冪順序排列)：

A(x)=an-1xn-1+an-1xn-2+……+a1x+a0對(duì)于（7，3）循環(huán)碼的任意碼組可表示為：A(x)=a6x6+a5x5+a4x4+a3x3+a2x2+a1x+a0如碼組（1100101）對(duì)應(yīng)的碼多項(xiàng)式可表示為A7(x)=1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1=x6+x5+x2+11、碼多項(xiàng)式A(x)第五十頁(yè)，共八十七頁(yè)，2022年，8月28日表10-4(7,3)循環(huán)碼寫出各個(gè)碼字多項(xiàng)式？最低次多項(xiàng)式的次數(shù)是多少？第五十一頁(yè)，共八十七頁(yè)，2022年，8月28日10.4.1生成多項(xiàng)式及生成矩陣如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式g(x)的倍式，則稱g(x)為該碼的生成多項(xiàng)式。在(n,k)循環(huán)碼中任意碼多項(xiàng)式A(x)都是最低次(r次)碼多項(xiàng)式的倍式。如表10-4的(7,3)循環(huán)碼中，第五十二頁(yè)，共八十七頁(yè)，2022年，8月28日其它碼多項(xiàng)式都是g(x)的倍式，即第五十三頁(yè)，共八十七頁(yè)，2022年，8月28日可以證明生成多項(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òu)造出兩種循環(huán)碼組；它們的d0、檢錯(cuò)、糾錯(cuò)能力相同第五十四頁(yè)，共八十七頁(yè)，2022年，8月28日g(x)，……，xk-1g(x)都是許用碼組，連同g(x)共k個(gè)許用碼組，構(gòu)成碼的生成矩陣G(x)注：該生成矩陣并不是典型形式的，但可通過線性變換變換成典型的生成矩陣。循環(huán)碼的生成矩陣常用多項(xiàng)式的形式來(lái)表示第五十五頁(yè)，共八十七頁(yè)，2022年，8月28日例如(7,3)循環(huán)碼，n=7,k=3,r=4,其生成多項(xiàng)式及生成矩陣分別為第五十六頁(yè)，共八十七頁(yè)，2022年，8月28日例：已知（7，4）循環(huán)碼的全部碼組為：試寫出該循環(huán)碼的生成多項(xiàng)式g(x)和生成矩陣G，并將G化成典型矩陣。第五十七頁(yè)，共八十七頁(yè)，2022年，8月28日解：n=7，k=4，n-k=3上述碼組中的(n-k)=3次碼多項(xiàng)式為第2組，它所對(duì)應(yīng)的碼多項(xiàng)式g(x)即為生成多項(xiàng)式：g(x)=x3+x+1。生成矩陣為：第五十八頁(yè)，共八十七頁(yè)，2022年，8月28日10.4.2監(jiān)督多項(xiàng)式及監(jiān)督矩陣其中g(shù)(x)是常數(shù)項(xiàng)為1的r次多項(xiàng)式，是生成多項(xiàng)式；h(x)是常數(shù)項(xiàng)為1的k次多項(xiàng)式，稱為監(jiān)督多項(xiàng)式。同理，可得監(jiān)督矩陣H

第五十九頁(yè)，共八十七頁(yè)，2022年，8月28日是h(x)的逆多項(xiàng)式。例如(7，3)循環(huán)碼，g(x)=x4+x3+x2+1，則其中第六十頁(yè)，共八十七頁(yè)，2022年，8月28日第六十一頁(yè)，共八十七頁(yè)，2022年，8月28日10.4.3編碼方法和電路

思路：在編碼時(shí)，首先要根據(jù)給定的(n,k)值選定生成多項(xiàng)式g(x)，即應(yīng)在xn+1的因式中選一r=n-k次,常數(shù)項(xiàng)為1的多項(xiàng)式作為g(x)。設(shè)編碼前的信息多項(xiàng)式m(x)為循環(huán)碼的碼多項(xiàng)式可表示為用xr乘m(x)，相當(dāng)于把信息碼后附加上r個(gè)“0”第六十二頁(yè)，共八十七頁(yè)，2022年，8月28日用g(x)除xrm(x)，得到商式Q(x)和余式為R(x)編出碼組為：A(x)=xrm(x)+R(x)第六十三頁(yè)，共八十七頁(yè)，2022年，8月28日即余式r(x)=x2+1于是，對(duì)應(yīng)碼組A(x)=xn-km(x)+r(x）=x6+x5+

x2+1編碼為1100101[例題]設(shè)（7，3）循環(huán)碼的生成多項(xiàng)式為g(x)=x4+x2+x+1，待編碼信息位為110，求對(duì)應(yīng)循環(huán)碼碼組。解：m(x)=x2+x，xn-km(x)=x4(x2+x)=x6+x5第六十四頁(yè)，共八十七頁(yè)，2022年，8月28日編碼電路：由除法電路和適當(dāng)?shù)目刂齐娐窐?gòu)成。除法電路：由移位寄存器和加法器構(gòu)成。第六十五頁(yè)，共八十七頁(yè)，2022年，8月28日?qǐng)D10-3(7,3)循環(huán)碼編碼電路編碼電路：由除法電路和適當(dāng)?shù)目刂齐娐?用一雙刀雙擲開關(guān)K代替)構(gòu)成。1、g(x)的次數(shù)為移位寄存器的級(jí)數(shù)。2、g(x)的非零系數(shù)對(duì)應(yīng)于移位寄存器的反饋抽頭。信碼第六十六頁(yè)，共八十七頁(yè)，2022年，8月28日1、圖中有4級(jí)移存器，分別用a,b,c,d表示。2、當(dāng)信息位輸入時(shí)，開關(guān)K倒向下，輸入信碼一方面送入除法器進(jìn)行運(yùn)算，另一方面直接輸出，當(dāng)k個(gè)移位脈沖后，移位寄存器中的數(shù)據(jù)即為除法余數(shù)，即監(jiān)督碼元。3、在信息位全部進(jìn)入除法器后，開關(guān)轉(zhuǎn)向上，這時(shí)輸出端接到移存器，將移存器存儲(chǔ)的除法余項(xiàng)依次取出，同時(shí)切斷反饋線。4、用這種方法編出的碼組，前面是原來(lái)的k個(gè)信息位，后面是n-k個(gè)監(jiān)督位。因此它是系統(tǒng)分組碼。第六十七頁(yè)，共八十七頁(yè)，2022年，8月28日表10-5(7,3)循環(huán)碼的編碼過程開關(guān)接2開關(guān)接1abcd1110100110100101010110.4.4譯碼方法和電路(略)第六十八頁(yè)，共八十七頁(yè)，2022年，8月28日10.6卷積碼10.6.1基本概念1、卷積碼：用(n,k,m)表示，每個(gè)(n,k)碼段(字碼)中的n個(gè)碼元不僅與該碼段內(nèi)的k個(gè)信息元有關(guān)，而且與前面m個(gè)信息元有關(guān)（有記憶性）。2、編碼器：由k個(gè)輸入，n個(gè)輸出，m個(gè)移位寄存器和一些輔助電路構(gòu)成的有記憶系統(tǒng)。第六十九頁(yè)，共八十七頁(yè)，2022年，8月28日例：卷積碼(2,1,2)編碼器起始狀態(tài)，各級(jí)移位寄存器清零，即S2S3為00。

S1等于當(dāng)前輸入數(shù)據(jù)，移位寄存器狀態(tài)S2S3存儲(chǔ)以前的數(shù)據(jù)，輸出碼字C由下式確定：第七十頁(yè)，共八十七頁(yè)，2022年，8月28日表(2,1,2)編碼器的工作過程第七十一頁(yè)，共八十七頁(yè)，2022年，8月28日編碼約束度：每1位數(shù)據(jù)，將影響(m+1)個(gè)輸出字碼，稱(m+1)為編碼約束度。例（2，1，2）編碼約束度為3。約束長(zhǎng)度：每個(gè)子碼有n個(gè)碼元，在卷積碼中有約束關(guān)系的最大碼元長(zhǎng)度為(m+1).n，稱為約束長(zhǎng)度。例（2，1，2）約束長(zhǎng)度為6。第七十二頁(yè)，共八十七頁(yè)，2022年，8月28日10.6.2卷積碼的描述（用圖解法）1.樹圖圖7-6(2,1,2)碼的樹圖第七十三頁(yè)，共八十七頁(yè)，2022年，8月28日2．狀態(tài)圖用狀態(tài)圖來(lái)描述。下圖就是該（2，1，2）卷積碼編碼器的狀態(tài)圖。在圖中有4個(gè)節(jié)點(diǎn)a、b、c、d，同樣分別表示S3S2的4種可能狀態(tài)。每個(gè)節(jié)點(diǎn)有兩條線離開該節(jié)點(diǎn)，實(shí)線表示輸入數(shù)據(jù)為0，虛線表示輸入數(shù)據(jù)為1，線旁的數(shù)字即為輸出碼字。圖（2，1，2）卷積碼的狀態(tài)圖第七十四頁(yè)，共八十七頁(yè)，2022年，8月28日3.格圖圖(2,1,2)碼的格圖10.5.3卷積碼的譯碼（概率譯碼，略）第七十五頁(yè)，共八十七頁(yè)，2022年，8月28日3．格圖

格圖也稱網(wǎng)絡(luò)或籬笆圖，它由狀態(tài)圖在時(shí)間上展開而得到，如圖所示。圖中畫出所有可能數(shù)據(jù)輸入時(shí)，狀態(tài)轉(zhuǎn)移的全部可能軌跡，實(shí)線表示數(shù)據(jù)為0，虛線表示數(shù)據(jù)為1，線旁數(shù)字為輸出碼字，節(jié)點(diǎn)表示狀態(tài)。

以上的3種卷積碼的描述方法，不但有助于求解輸出碼字，了解編碼工作過程，而且對(duì)研究解碼方法也很有用。圖（2，1，2）卷積碼的格圖第七十六頁(yè)，共八十七頁(yè)，2022年，8月28日三、卷積碼的譯碼（略）

卷積碼的譯碼可分為代數(shù)譯碼和概率譯碼兩大類。代數(shù)譯碼是利用生成矩陣和監(jiān)督矩陣來(lái)譯碼，最主要的方法是大數(shù)邏輯譯碼。概率譯碼比較實(shí)用的有兩種：維特比譯碼和序列譯碼。目前，概率譯碼已成為卷積