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

10.1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（d）信息反饋

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

01

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

001

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

碼組201101碼距：d0

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

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

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

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

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

信息碼元

監(jiān)督碼元11100110001101001101100001110100010000101100111011

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

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

信息碼元

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

10.3

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

可以糾正一位錯碼，且d0=310.3.1漢明碼

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

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

a5

a4

a3：信息碼元；a2

a1

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

s1s2s3

錯碼位置

000

無錯001a0

010a1

100a2

011a3

101a4

110a5

111a6

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

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

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

其中：

監(jiān)督位

信息位

監(jiān)督位與信息位的關(guān)系（矩陣表示）第30頁/共72頁2.生成矩陣用途：由信息位和生成矩陣可得出整個碼組。生成矩陣：以（7,4）漢明碼為例生成矩陣第31頁/共72頁如（7,4）漢明碼表中的第3個碼組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頁/共72頁求整個碼組注意：生成矩陣G各行本身就是一個碼組。加例題！二元域上只有兩種運(yùn)算：加和乘。運(yùn)算規(guī)則如下：加乘第33頁/共72頁3.監(jiān)督矩陣和生成矩陣的關(guān)系例10-3

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

5.線性分組碼的糾錯能力第36頁/共72頁

10.4

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

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

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

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

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

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

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

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

1.生成多項式g(x)

生成多項式的尋找方法：

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

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

2.生成矩陣G

典型的生成矩陣

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

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

生成矩陣多項式

生成矩陣非典型矩陣典型矩陣第42頁/共72頁

3.生成多項式的另一種求法

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

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

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

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

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

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

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

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

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

其工作過程如下：

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

10.6.1卷積碼編碼器

10.6.2卷積碼的解析描述

10.6.3卷積碼的圖解描述

10.6.4維特比譯碼原理第56頁/共72頁

10.6

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

卷積碼的基本概念

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

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

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