差錯(cuò)控制解析

會(huì)計(jì)學(xué)1差錯(cuò)控制解析學(xué)習(xí)要求1.理解差錯(cuò)控制的基本概念及其原理等；2.掌握信道編碼的基本原理；3.了解常用檢錯(cuò)碼的特性；4.掌握線性分組碼的一般特性；5.掌握漢明碼以及循環(huán)碼的編譯碼及其實(shí)現(xiàn)原理；6.掌握卷積碼的編譯碼基本原理。第1頁(yè)/共72頁(yè)

10.1

差錯(cuò)控制的基本概念及原理1.差錯(cuò)分類10.1.1差錯(cuò)控制的基本概念隨機(jī)差錯(cuò)：又稱獨(dú)立差錯(cuò)，它是指那些獨(dú)立地、稀疏地和互不相關(guān)地發(fā)生的差錯(cuò)。

突發(fā)差錯(cuò)：是指一串串，甚至成片出現(xiàn)的差錯(cuò)，差錯(cuò)之間有相關(guān)性。目的：提高通信系統(tǒng)的可靠性噪聲分類：隨機(jī)噪聲和脈沖噪聲。誤碼產(chǎn)生原因：信道不理想造成的符號(hào)間干擾；噪聲對(duì)信號(hào)的干擾。重點(diǎn)討論由隨機(jī)噪聲引起由脈沖噪聲引起第2頁(yè)/共72頁(yè)2.錯(cuò)誤圖樣E中，“0”表示正確，“1”表示錯(cuò)誤第3頁(yè)/共72頁(yè)

隨機(jī)錯(cuò)誤錯(cuò)誤圖樣錯(cuò)誤圖樣

突發(fā)錯(cuò)誤錯(cuò)誤圖樣第4頁(yè)/共72頁(yè)2.差錯(cuò)控制的基本思路

發(fā)送端：將被傳送的信息碼（無規(guī)律）按照一定的規(guī)則加入監(jiān)督碼元后進(jìn)行傳輸，加入的監(jiān)督碼元與信息碼元存在某種確定的約束關(guān)系。

接收端：檢驗(yàn)信息碼元與監(jiān)督碼元之間的既定的約束關(guān)系，如關(guān)系被破壞，則傳輸中有錯(cuò)。差錯(cuò)控制也稱糾錯(cuò)編碼，信道編碼。

信息碼(k)+監(jiān)督碼(r)=碼組(n)第5頁(yè)/共72頁(yè)

信息碼元(k)+監(jiān)督碼元(r)=碼組(n)第6頁(yè)/共72頁(yè)3.差錯(cuò)控制方式（1）檢錯(cuò)重發(fā)（ARQ）

優(yōu)缺點(diǎn)——所需的監(jiān)督碼位數(shù)少，編碼效率比較高；——譯碼設(shè)備較簡(jiǎn)單；——接收端檢測(cè)到差錯(cuò)后，要通過反向信道發(fā)回NAK，要求發(fā)端重發(fā)，所以需要反向信道，實(shí)時(shí)性差A(yù)RQ有3種重發(fā)方式，即停發(fā)等候重發(fā)，返回重發(fā)和選擇重發(fā)。第7頁(yè)/共72頁(yè)a）停發(fā)等候重發(fā)b）返回重發(fā)c）選擇重發(fā)第8頁(yè)/共72頁(yè)（2）前向糾錯(cuò)（FEC）

優(yōu)缺點(diǎn)——

不需要反向信道，自動(dòng)糾錯(cuò)，不要求重發(fā)，因而實(shí)時(shí)性好；——

缺點(diǎn)是所選擇的糾錯(cuò)碼必須與信道的錯(cuò)碼特性密切配合，否則很難達(dá)到降低錯(cuò)碼率的要求；——

要糾正較多的錯(cuò)碼，譯碼設(shè)備復(fù)雜，且要求附加的監(jiān)督碼較多，編碼效率低。第9頁(yè)/共72頁(yè)（3）混合糾錯(cuò)檢錯(cuò)（HEC）是ARQ和FEC方式的折衷方案

優(yōu)缺點(diǎn)——

集合了ARQ和FEC的優(yōu)點(diǎn)，在保證系統(tǒng)較高的有效性的同時(shí),大幅度提高了整個(gè)系統(tǒng)的可靠性，但需要反向信道。第10頁(yè)/共72頁(yè)（4）信息反饋（IRQ）數(shù)據(jù)信息

數(shù)據(jù)信息

（d）信息反饋

優(yōu)缺點(diǎn)優(yōu)點(diǎn)是不需要糾錯(cuò)、檢錯(cuò)，設(shè)備簡(jiǎn)單；缺點(diǎn)是需要和前向信道相同的反向信道，實(shí)時(shí)性差，且發(fā)送端需要一定容量的存儲(chǔ)器。第11頁(yè)/共72頁(yè)10.1.2差錯(cuò)控制的基本原理1.差錯(cuò)控制的原理AB0

01

1010110準(zhǔn)用碼組禁用碼組無檢錯(cuò)能力無糾錯(cuò)能力可檢測(cè)1位錯(cuò)碼舉例說明信息位1無監(jiān)督位信息位1監(jiān)督位1方案1方案2第12頁(yè)/共72頁(yè)10.1.2差錯(cuò)控制的基本原理（續(xù)）1.差錯(cuò)控制的原理（續(xù)）AB0

001

11001010100011101110準(zhǔn)用碼組禁用碼組可檢測(cè)1到2位錯(cuò)碼，或糾1位錯(cuò)碼要想具有檢錯(cuò)和糾錯(cuò)能力，必須有禁用碼組。禁用碼組的獲得方法：加監(jiān)督位。方案3信息位1監(jiān)督位2第13頁(yè)/共72頁(yè)碼長(zhǎng)：碼組或碼字中編碼的總位數(shù)為碼組的長(zhǎng)度。2.漢明距離與檢錯(cuò)和糾錯(cuò)能力的關(guān)系（1）幾個(gè)概念碼重：碼組中非零碼元的數(shù)目為碼組的重量。例如“11010”的碼長(zhǎng)為5，碼重為3。碼距：兩個(gè)等長(zhǎng)碼組中對(duì)應(yīng)碼位上具有不同二進(jìn)制碼的數(shù)目稱為碼距。例如：碼組111010

碼組201101碼距：d0

=4漢明距離（最小碼距）：dmin

在一種編碼中，任意兩個(gè)許用碼組間距離的最小值。000001010100111011101110dmin

=1第14頁(yè)/共72頁(yè)（2）漢明距離和檢錯(cuò)和糾錯(cuò)能力的關(guān)系a)為了檢測(cè)e位錯(cuò)碼，要求最小碼距b)為了糾正t位錯(cuò)碼，要求最小碼距c)為了糾正t位錯(cuò)碼，同時(shí)檢測(cè)e(e>t)位錯(cuò)碼，要求最小碼距第15頁(yè)/共72頁(yè)3.糾錯(cuò)編碼的分類(1)按碼組的功能分，有檢錯(cuò)碼和糾錯(cuò)碼兩類。(2)按碼組中監(jiān)督碼元與信息碼元之間的關(guān)系分，有線性碼和非線性碼兩類。(3)按照信息碼元與監(jiān)督碼元的約束關(guān)系，可分為分組碼和卷積碼。(4)按照信息碼元在編碼前后是否保持原來的形式不變，可分為系統(tǒng)碼和非系統(tǒng)碼。(5)按糾正差錯(cuò)的類型可分為糾正隨機(jī)錯(cuò)誤的碼和糾正突發(fā)錯(cuò)誤的碼。(6)按照每個(gè)碼元取值來分，可分為二進(jìn)制碼與多進(jìn)制碼。第16頁(yè)/共72頁(yè)10.2.1奇偶監(jiān)督碼

10.2簡(jiǎn)單的差錯(cuò)控制編碼特點(diǎn)：只有一個(gè)監(jiān)督位。偶監(jiān)督：碼組中“1”的個(gè)數(shù)為偶數(shù)。信息位監(jiān)督位奇監(jiān)督：碼組中“1”的個(gè)數(shù)為奇數(shù)。只能檢出奇數(shù)位錯(cuò)碼。第17頁(yè)/共72頁(yè)10.2.2水平奇偶監(jiān)督碼

思想方法：將信息碼序列按行排成方陣，每行后面加一個(gè)奇或偶監(jiān)督碼，即每行為一個(gè)奇（偶）監(jiān)督碼組，但發(fā)送時(shí)則按列的順序傳輸：111011100110000…10101，接收端仍將碼元排成與發(fā)送端一樣的方陣形式，然后按行進(jìn)行奇偶校驗(yàn)。

信息碼元

監(jiān)督碼元11100110001101001101100001110100010000101100111011

10101水平偶監(jiān)督碼可以檢出奇數(shù)位錯(cuò)誤和長(zhǎng)度不大于方陣中行數(shù)的突發(fā)錯(cuò)誤。第18頁(yè)/共72頁(yè)10.2.3二維奇偶監(jiān)督碼（水平垂直奇偶監(jiān)督碼）

思想方法：在水平監(jiān)督基礎(chǔ)上對(duì)方陣中的每一列再進(jìn)行奇偶校驗(yàn)。發(fā)送時(shí)按行或按列的順序傳輸，接收端重新將碼元排成與發(fā)送時(shí)的方陣形式，然后每行、每列都進(jìn)行奇偶校驗(yàn)。二維偶監(jiān)督碼

信息碼元

監(jiān)督碼元1110011000110100110110000111010001000010110011101110101監(jiān)督碼元01101100011可以糾1位錯(cuò)碼；可以檢出某行或某列上的奇數(shù)位錯(cuò)碼和長(zhǎng)度不大于方陣中行數(shù)(列數(shù))的突發(fā)錯(cuò)碼；可以檢出一部分偶數(shù)位錯(cuò)碼；不能檢出錯(cuò)碼恰好分布在矩陣4個(gè)頂點(diǎn)上的偶數(shù)位錯(cuò)碼。第19頁(yè)/共72頁(yè)

10.3

漢明碼及線性分組碼漢明碼特點(diǎn)

可以糾正一位錯(cuò)碼，且d0=310.3.1漢明碼

1.碼長(zhǎng)和監(jiān)督位的關(guān)系：若使用偶監(jiān)督：只有一位監(jiān)督位接收端譯碼時(shí)，實(shí)際上就是計(jì)算：若無錯(cuò)；有錯(cuò)。奇監(jiān)督相反校正子1位監(jiān)督位，有1個(gè)校正子。只能表示有錯(cuò)和無錯(cuò)，不能指示錯(cuò)碼位置。第20頁(yè)/共72頁(yè)

碼長(zhǎng)和監(jiān)督位的關(guān)系2位監(jiān)督位，就有2個(gè)監(jiān)督關(guān)系式，也有2個(gè)校正子。如果無錯(cuò)指示錯(cuò)碼位置（n,k）漢明碼，監(jiān)督位r=n-k，可構(gòu)造出r個(gè)監(jiān)督關(guān)系式來指示一位錯(cuò)碼的n種可能位置，要求若為：第21頁(yè)/共72頁(yè)1.（7,4）漢明碼a6

a5

a4

a3：信息碼元；a2

a1

a0：監(jiān)督碼元信息碼元與監(jiān)督碼元的關(guān)系：第22頁(yè)/共72頁(yè)表10.3.1（7,4）漢明碼的許用碼組P322——假設(shè)發(fā)送端的碼字是A15=1111111，——傳輸過程中第4位a3出現(xiàn)了錯(cuò)誤，即接收的碼字是B=1110111

不是許用碼組。信息碼a6

a5

a4

a3碼組Aa6

a5

a4

a3

a2

a1

a0信息碼a6

a5

a4

a3碼組Aa6

a5

a4

a3

a2

a1

a0000000010010001101000101011001110000

0000001

0110010

1010011

1100100

110010

1

1010110

0110111

000100010011010101111001101111011111000

1111001

1001010

0101011

0011100

0011101

0101110

1001111

111第23頁(yè)/共72頁(yè)1.（7,4）漢明碼

s1s2s3

錯(cuò)碼位置

000

無錯(cuò)001a0

010a1

100a2

011a3

101a4

110a5

111a6

校正子與錯(cuò)碼位置的關(guān)系有3個(gè)校正子第24頁(yè)/共72頁(yè)例10-1

接收端收到某（7,4）漢明碼為1001010，問：此（7,4）漢明碼是否有錯(cuò)？錯(cuò)碼位置如何？解：計(jì)算校正子得校正子為110，碼組有錯(cuò)。正確碼組：1101010第25頁(yè)/共72頁(yè)2）（7,4）漢明碼的產(chǎn)生由監(jiān)督關(guān)系式：發(fā)端無錯(cuò)移項(xiàng)，解出監(jiān)督位：解決問題：由信息位計(jì)算監(jiān)督位第26頁(yè)/共72頁(yè)例10-2

已知信息碼為1101，求所對(duì)應(yīng)的（7,4）漢明碼。解：計(jì)算監(jiān)督位漢明碼碼組：1101010監(jiān)督位3）編碼效率（7,4）漢明碼的編碼效率：第27頁(yè)/共72頁(yè)10.3.2線性分組碼線性碼：監(jiān)督碼元與信息碼元之間滿足一組線性方程。分組碼：監(jiān)督碼元僅對(duì)本碼組中的碼元起監(jiān)督作用。1.監(jiān)督矩陣以（7,4）漢明碼為例改寫為簡(jiǎn)寫為+線性分組碼：既是線性碼又是分組碼。。第28頁(yè)/共72頁(yè)寫成矩陣形式監(jiān)督矩陣簡(jiǎn)寫為單位方陣P第29頁(yè)/共72頁(yè)用矩陣表示為

其中：

監(jiān)督位

信息位

監(jiān)督位與信息位的關(guān)系（矩陣表示）第30頁(yè)/共72頁(yè)2.生成矩陣用途：由信息位和生成矩陣可得出整個(gè)碼組。生成矩陣：以（7,4）漢明碼為例生成矩陣第31頁(yè)/共72頁(yè)如（7,4）漢明碼表中的第3個(gè)碼組P322信息碼a6

a5

a4

a3碼組Aa6

a5

a4

a3

a2

a1

a0信息碼a6

a5

a4

a3碼組Aa6

a5

a4

a3

a2

a1

a0000000010010001101000101011001110000

0000001

0110010

1010011

1100100

110010

1

1010110

0110111

000100010011010101111001101111011111000

1111001

1001010

0101011

0011100

0011101

0101110

1001111

111第32頁(yè)/共72頁(yè)求整個(gè)碼組注意：生成矩陣G各行本身就是一個(gè)碼組。加例題！二元域上只有兩種運(yùn)算：加和乘。運(yùn)算規(guī)則如下：加乘第33頁(yè)/共72頁(yè)3.監(jiān)督矩陣和生成矩陣的關(guān)系例10-3

（課后練習(xí)）某（7,4）線性分組碼，監(jiān)督方程如下，求監(jiān)督矩陣H和典型的生成矩陣G。如信息碼為0010，求整個(gè)碼組。解：監(jiān)督方程改寫為第34頁(yè)/共72頁(yè)得監(jiān)督矩陣：典型生成矩陣：如信息碼為0010，則整個(gè)碼組為第35頁(yè)/共72頁(yè)4.線性分組碼的主要性質(zhì)(1)封閉性是指一種線性分組碼中的任意兩個(gè)碼組之逐位模2和仍為這種碼中的另一個(gè)許用碼組。(2)碼的最小距離等于非零碼的最小重量。

5.線性分組碼的糾錯(cuò)能力第36頁(yè)/共72頁(yè)

10.4

循環(huán)碼循環(huán)碼是一種線性分組碼。10.4.1

循環(huán)碼的循環(huán)特性表10.4.1（7,3）循環(huán)碼的一種碼組P328

碼組編號(hào)信息位監(jiān)督位碼組編號(hào)信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010

循環(huán)碼的循環(huán)特性是指在循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后所得到的碼組仍為它的一個(gè)許用碼組。

第2碼組右移1位得到第5碼組；

第5碼組右移1位得到第7碼組。第37頁(yè)/共72頁(yè)2.碼多項(xiàng)式的表示及運(yùn)算規(guī)則例如，碼組為則碼多項(xiàng)式為：

碼多項(xiàng)式的運(yùn)算：加、減、乘、除運(yùn)算1）碼多項(xiàng)式的加法運(yùn)算：同冪次相加，系數(shù)進(jìn)行異或運(yùn)算2）碼多項(xiàng)式的減法運(yùn)算：同加法運(yùn)算碼組為則碼多項(xiàng)式為：第38頁(yè)/共72頁(yè)ABC0000111011103）異或運(yùn)算（邏輯加和邏輯減）的真值表4）碼多項(xiàng)式的乘法運(yùn)算：服從一般的代數(shù)規(guī)律5）碼多項(xiàng)式的除法運(yùn)算：服從一般的代數(shù)規(guī)律6）碼多項(xiàng)式的除法運(yùn)算簡(jiǎn)化表示例如上式還可表示為第39頁(yè)/共72頁(yè)10.4.2

循環(huán)碼的生成多項(xiàng)式和生成矩陣

1.生成多項(xiàng)式g(x)

生成多項(xiàng)式的尋找方法：

（n,k）循環(huán)碼的個(gè)碼組中，有一個(gè)碼組前k-1位碼元均為0，第k位碼元為1，最后一位為1，此碼組對(duì)應(yīng)的多項(xiàng)式為生成多項(xiàng)式。例10-5

求表10.4.1所示的（7,3）循環(huán)碼的生成多項(xiàng)式。碼組編號(hào)信息位監(jiān)督位碼組編號(hào)信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010解：生成多項(xiàng)式第40頁(yè)/共72頁(yè)

2.生成矩陣G

典型的生成矩陣

通過線性變換可將非典型的生成矩陣轉(zhuǎn)換為典型的生成矩陣單位方陣第41頁(yè)/共72頁(yè)例10-5（續(xù)）

求表10-6所示的（7,3）循環(huán)碼的典型生成矩陣G。解：

生成矩陣多項(xiàng)式

生成矩陣非典型矩陣典型矩陣第42頁(yè)/共72頁(yè)

3.生成多項(xiàng)式的另一種求法

（n,k）循環(huán)碼的生成多項(xiàng)式是的一個(gè)（n-k）次因式。例

求（7,3）循環(huán)碼的生成多項(xiàng)式。解：生成多項(xiàng)式有兩個(gè)：表10.4.1循環(huán)碼用生成多項(xiàng)式不同，產(chǎn)生出的循環(huán)碼碼組也不同。第43頁(yè)/共72頁(yè)10.4.3

循環(huán)碼的編碼方法步驟：信息位對(duì)應(yīng)的碼多項(xiàng)式：循環(huán)碼的碼多項(xiàng)式第44頁(yè)/共72頁(yè)10.4循環(huán)碼的編碼——當(dāng)M=110，所以——即所得的碼字為A=1100101。第45頁(yè)/共72頁(yè)10.4.4

循環(huán)碼的解碼方法1.檢錯(cuò)的實(shí)現(xiàn)無差錯(cuò)發(fā)送碼組接收碼組若碼組無錯(cuò)判別方法若碼組有錯(cuò)，則接收碼組若碼組無錯(cuò)檢測(cè)到差錯(cuò)解碼器的核心：除法器第46頁(yè)/共72頁(yè)10.4循環(huán)碼——r級(jí)線性移位寄存器的初始狀態(tài)為全零，所有開關(guān)均向下連通；——在寄存器時(shí)鐘的控制下進(jìn)行k次移位，輸出M(x)的系數(shù)(即信息碼組)，同時(shí)實(shí)現(xiàn)除法電路的功能；

編碼器工作過程第47頁(yè)/共72頁(yè)10.4循環(huán)碼——所有開關(guān)向下連通，輸入下一組信息重復(fù)上述過程。

實(shí)例分析——所有開關(guān)均倒向上方連通，在寄存器時(shí)鐘的控制下再經(jīng)過r=n-k

次移位，將監(jiān)督元輸出到信道；——本節(jié)前面給出的(7，3)循環(huán)碼生成多項(xiàng)式：g(x)=x4+x2+x+1

由其可得編碼電路如下圖所示：第48頁(yè)/共72頁(yè)10.4循環(huán)碼——假設(shè)M=110，編碼器工作過程如下表所示輸入移位寄存器狀態(tài)反饋輸出R1R2R3R4f0000000m2m1m0110111100101010111110信息元0000000010000100001001010101監(jiān)督元a6a5a4a3a2a1a0第49頁(yè)/共72頁(yè)循環(huán)碼的編碼器電路設(shè)計(jì)第50頁(yè)/共72頁(yè)2.糾錯(cuò)的實(shí)現(xiàn)概念：錯(cuò)誤圖樣發(fā)送碼組接收碼組錯(cuò)誤碼組錯(cuò)誤碼組的各種不同的具體采樣稱錯(cuò)誤圖樣糾錯(cuò)的步驟：得原發(fā)送碼組。第51頁(yè)/共72頁(yè)10.4循環(huán)碼

糾錯(cuò)譯碼原理——確定循環(huán)碼的糾錯(cuò)能力;——根據(jù)[模g(x)]計(jì)算伴隨式，若S(x)≠0則判定傳輸出錯(cuò)。——根據(jù)[模g(x)]找到校正子對(duì)應(yīng)的錯(cuò)誤圖樣——由A(x)=B(x)+E(x)糾錯(cuò)。第52頁(yè)/共72頁(yè)10.4循環(huán)碼——檢錯(cuò)譯碼原理圖：P334，335第53頁(yè)/共72頁(yè)10.4循環(huán)碼——寄存器置零，開關(guān)S向下連通；——在寄存器時(shí)鐘的控制下經(jīng)n次移位后將接收碼字B輸入，此時(shí)寄存器中存儲(chǔ)的即校正子(n，k)循環(huán)碼校正子計(jì)算電路

其工作過程如下：

——將開關(guān)向上打開，經(jīng)r=n-k次移位讀出校正子。第54頁(yè)/共72頁(yè)國(guó)際通信中常用的是循環(huán)冗余校驗(yàn)（CRC）生成多項(xiàng)式為：CRC--32CRCIS-95CDMA第55頁(yè)/共72頁(yè)10.6卷積碼本節(jié)內(nèi)容提要：——卷積碼是一類非線性有記憶編碼，本節(jié)將簡(jiǎn)要介紹卷積碼的編譯碼原理。

10.6.1卷積碼編碼器

10.6.2卷積碼的解析描述

10.6.3卷積碼的圖解描述

10.6.4維特比譯碼原理第56頁(yè)/共72頁(yè)

10.6

卷積碼卷積碼又稱連環(huán)碼，是非分組碼。沒有嚴(yán)格的代數(shù)結(jié)構(gòu)10.6.1

卷積碼的基本概念

卷積碼的監(jiān)督位不僅取決于這段時(shí)間的k個(gè)信息位，還取決于前N-1段規(guī)定時(shí)間內(nèi)的信息位。1.卷積碼的概念編碼效率：

即卷積碼的監(jiān)督位不僅對(duì)本碼組起監(jiān)督作用，對(duì)前N-1個(gè)碼組也起監(jiān)督作用。這N段時(shí)間內(nèi)的碼元數(shù)目nN稱為約束長(zhǎng)度。卷積碼的表示方式：(n,k,N)第57頁(yè)/共72頁(yè)10.6.1卷積編碼器(n，k，N)卷積編碼器結(jié)構(gòu)第58頁(yè)/共72頁(yè)10.6.1卷積編碼器——(3，1，3)卷積碼的兩種等效編碼器

實(shí)例分析3級(jí)編碼器n=3,k=1:每輸入一個(gè)信息比特，產(chǎn)生