通信原理第九章課件

第九章差錯(cuò)控制編碼主要內(nèi)容：糾錯(cuò)編碼的原理線性分組碼循環(huán)碼重點(diǎn)：檢錯(cuò)、糾錯(cuò)的概念分組碼的結(jié)構(gòu)漢明碼循環(huán)碼9.1引言9.2糾錯(cuò)編碼的原理9.3常用的簡單編碼9.4線性分組碼9.5循環(huán)碼9.1引言檢錯(cuò)重發(fā)法9.1.2差錯(cuò)控制的方法9.1.1編碼的目的：提高信號抗加性干擾的能力干擾種類：加性克服方法：差錯(cuò)控制編碼加性干擾的特征：突發(fā)信道：出現(xiàn)錯(cuò)碼成串集中?；旌闲诺溃呵皟烧咧泻?。乘性克服方法：均衡器隨機(jī)信道：出現(xiàn)錯(cuò)碼是隨機(jī)的，相互間統(tǒng)計(jì)獨(dú)立。（白噪聲）反饋校驗(yàn)法前向糾錯(cuò)方法定義誤碼率標(biāo)準(zhǔn)檢錯(cuò)重發(fā)法：在接收端檢測出錯(cuò)碼時(shí)，通知發(fā)端重發(fā)信號，直到接收正確為止。此方法只能判斷是否有錯(cuò)碼，不能判斷具體的錯(cuò)碼位置。所以，只能檢錯(cuò)不能糾錯(cuò)，且需要雙向通道。前向糾錯(cuò)方法：在收端檢測出錯(cuò)碼時(shí)，可以確定錯(cuò)碼的位置，并予糾正。此方法只需要單向通道。實(shí)時(shí)性好，但設(shè)備復(fù)雜。反饋校驗(yàn)法：接收端將收到的信號原封不動(dòng)的發(fā)回發(fā)端，由發(fā)端將其與原發(fā)信號相比較，如果有錯(cuò)則重發(fā)。這種方法需雙向通道，效率低，但設(shè)備簡單。在信息碼序列中加監(jiān)督碼元（也稱糾錯(cuò)碼）自動(dòng)請求重發(fā)系統(tǒng)（ARQ）9.1.3差錯(cuò)控制編碼的原理：不同的編碼方法，有不同的檢錯(cuò)或糾錯(cuò)能力，監(jiān)督碼元越多，檢、糾錯(cuò)能力越強(qiáng)。由于信息碼元是隨機(jī)序列，收端無法預(yù)知信號狀態(tài)，因而無法判別接收碼是否有錯(cuò)。增加了監(jiān)督碼元之后，監(jiān)督碼和信息碼之間存在一種邏輯關(guān)系，因此，收端可以利用這種邏輯關(guān)系發(fā)現(xiàn)或糾正存在的錯(cuò)碼。自動(dòng)請求重發(fā)系統(tǒng)（ARQ）工作過程：3）重發(fā)控制器收到重發(fā)命令時(shí)，控制輸入緩沖儲(chǔ)存器重發(fā)一次當(dāng)前碼組，否則發(fā)送后一碼組。2）收端解碼器檢測出錯(cuò)碼時(shí)由指令發(fā)生器產(chǎn)生重發(fā)命令傳給發(fā)端，同時(shí)發(fā)出刪除命令，刪除輸出緩沖器內(nèi)容。1）收發(fā)正常時(shí)，重發(fā)控制與指令發(fā)生器不工作。重發(fā)控制信源雙向通道指令發(fā)生器解碼器輸出緩存器收信者錯(cuò)誤時(shí)刪除編碼輸入緩存器優(yōu)點(diǎn)：1）監(jiān)督碼少，占總碼的(20%)2）對各種信道有一定的適應(yīng)能力。3）成本及復(fù)雜性低。缺點(diǎn)：1）需要雙向通道2）干擾大時(shí)系統(tǒng)可能處于重發(fā)循環(huán)中，效率降低3）實(shí)時(shí)性差例：天氣預(yù)報(bào)9.2.1分組碼的概念特征：分組碼中的監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。分組碼定義：將信息碼分組，為每組信息碼后附加若干監(jiān)督碼元形成的碼集合。分組碼檢錯(cuò)、糾錯(cuò)能力的體現(xiàn)信源發(fā)送信息碼晴00云01陰10雨11接收信息碼判別01云10陰00晴10陰結(jié)論：雖然接收碼組有錯(cuò)，但接收端無法識別。討論信源發(fā)送信息碼監(jiān)督碼晴000云011陰101雨110接收碼組判別001、010、100010、001、111100、111、001111、100、010建立分組碼A錯(cuò)1位接收碼組判別011、110、101云、雨、陰000、101、110晴、陰、雨110、000、011雨、晴、云101、000、011陰、晴、云錯(cuò)2位結(jié)論：只能檢測出1位錯(cuò)碼，但不能糾正。禁用碼組：非信息碼組許用碼組：有效信息碼組結(jié)論：能糾正1位錯(cuò)碼，或檢測出2位錯(cuò)碼。信源發(fā)送信息碼監(jiān)督碼晴00000云01011陰10101雨11110接收碼組判別00001、00010、00100、01000、1000001010、01001、01111、00011、1101110100、10111、10001、11101、0010111111、11100、11010、10110、01110建立分組碼B錯(cuò)1位接收碼組判別11000、10100、10010、10001、01100、01010、01001、00110、00101、0001110011、11111、11001、11010、00111、00001、00010、01101、01110、0101001101、00001、00111、00110、11001、11110、11101、10011、10000、1010000110、01010、01100、01111、10010、10100、10111、11000、11011、11111錯(cuò)2位例：碼組（a2a1a0）=110（b2b1b0）=011碼距的幾何概念碼距是2最小碼距

d0

：碼集合中任意兩兩碼組間距離的最小值（010）（110）（000）（100）（101）（001）（011）（111）a1a0a2選許用碼組：000011110101令n=3,共有8個(gè)碼組沿立方體各邊行走，4個(gè)碼組的距離均為2個(gè)邊長

d0

=2∵∴

檢測e個(gè)錯(cuò)碼，要求最小碼距

糾正t個(gè)錯(cuò)碼，要求最小碼距糾正t個(gè)錯(cuò)碼、同時(shí)檢測e個(gè)錯(cuò)碼，要求最小碼距碼距與碼集合檢、糾錯(cuò)能力的關(guān)系A(chǔ)B例：

A=(00000)、B=(11111)，d0

=5

結(jié)論：e=4或

t=2或e=3、t=1d=1d=2d=39.3常用的簡單編碼9.3.1

奇偶監(jiān)督碼9.3.2

正反碼例:信源發(fā)送信息碼a2a1監(jiān)督碼a0晴000云011陰101雨110一維偶數(shù)監(jiān)督碼接收碼組判別001、010、100010、001、111100、111、001111、100、010錯(cuò)1位滿足：檢驗(yàn)不滿足只能檢錯(cuò)，不能糾錯(cuò)2）當(dāng)同時(shí)出錯(cuò)，則按行按列均不能檢測出有錯(cuò)。

能檢測部分偶數(shù)個(gè)錯(cuò)碼適用于突發(fā)信道。

若僅一行有奇數(shù)個(gè)錯(cuò)碼時(shí)，可通過列確定錯(cuò)碼位置并糾正。1）設(shè)和發(fā)生錯(cuò)碼，按行無法檢測出有錯(cuò)，而按列可檢測。a2a1a0000011101110000例：二維偶數(shù)監(jiān)督碼通式結(jié)論：

方陣碼除對構(gòu)成矩形四角的錯(cuò)碼無法檢測外，其余均能檢測。特征：具有糾正

1

位錯(cuò)碼、檢測

2位和大部分

2位以上錯(cuò)碼的能力定義：信息碼位數(shù)與監(jiān)督碼位數(shù)相同

編碼規(guī)則：1）當(dāng)信息位中有奇數(shù)個(gè)“1”時(shí)，監(jiān)督位是信息位的重復(fù)。2）當(dāng)信息位中有偶數(shù)個(gè)“1”時(shí)，監(jiān)督位是信息位的反碼。10001例：若信息碼為11001

9.3.2

正反碼則正反碼為110011100110001011101）將接收碼組中信息碼和監(jiān)督碼對應(yīng)按位模2加，得合成碼組2）根據(jù)接收碼組中信息碼含

“1”的奇偶情況，由合成碼組生成校驗(yàn)碼組

3）根據(jù)校驗(yàn)碼組的組成，依表判斷錯(cuò)碼情況，并予檢錯(cuò)與糾錯(cuò)譯碼規(guī)則：“1”為奇校驗(yàn)=合成“1”為偶校驗(yàn)=例9.4線性分組碼9.4.1漢明碼的編碼原理9.4.2一般線性分組碼的編碼原理9.4.3線性碼分組碼的數(shù)學(xué)描述9.4.1漢明碼的編碼原理定義：能糾正一位錯(cuò)碼，且編碼效率較高的線性分組碼問題：在正反碼中，為糾正一位錯(cuò)碼，其監(jiān)督碼位數(shù)與信息碼位數(shù)一樣多，能否減少監(jiān)督碼位數(shù)但糾錯(cuò)能力不變？如何實(shí)現(xiàn)糾錯(cuò)？思路：分組碼(n,k)只可能出現(xiàn)

n個(gè)一位錯(cuò)碼事件，若某種邏輯組合具有n個(gè)狀態(tài)，就能利用這種邏輯組合描述一位錯(cuò)碼事件并予糾正。例：分析偶數(shù)監(jiān)督碼，尋找邏輯組合漢明碼∵

監(jiān)督方程則接收時(shí)解碼是在計(jì)算0無錯(cuò)1有錯(cuò)定義：校正子

S=只能表示出錯(cuò)不能描述錯(cuò)碼位置一位監(jiān)督碼對應(yīng)一個(gè)監(jiān)督方程結(jié)論：若增加監(jiān)督碼元，建立多個(gè)監(jiān)督方程，多個(gè)校正子就能形成邏輯組合描述錯(cuò)碼位置漢明碼確定監(jiān)督碼元位數(shù)r確定監(jiān)督關(guān)系表建立監(jiān)督方程建立編碼方程∵分組碼(n,k)共需n+1個(gè)狀態(tài)描述無錯(cuò)及n個(gè)有錯(cuò)事件∴為提高編碼效率，r取最小值例：已知(7,4)碼，r=3∴共有3個(gè)監(jiān)督方程，構(gòu)成3個(gè)校正子S1S2S3S1S2S3000無錯(cuò)001a0錯(cuò)010a1錯(cuò)100a2錯(cuò)110a3錯(cuò)011a4錯(cuò)111a5錯(cuò)101a6錯(cuò)例例：∵漢明碼的監(jiān)督方程為∴矩陣表達(dá)式9.4.2一般線性分組碼的編碼原理（矩陣方程）記為：H：監(jiān)督矩陣A：碼組向量當(dāng)稱H為典型矩陣（含單位陣）思路：確定編碼矩陣方程，構(gòu)造生成矩陣又∵根據(jù)監(jiān)督方程確定了編碼方程∴兩邊同取轉(zhuǎn)置構(gòu)造生成矩陣稱G為典型生成矩陣（含單位陣）∴編碼矩陣方程特點(diǎn)：信息位不變，監(jiān)督位附加于其后。定義系統(tǒng)碼：由典型生成矩陣得出的碼組A發(fā)碼組A=1100010收碼組B=1000010∴譯碼運(yùn)算例：(7,4)漢明碼,S1S2S3000無錯(cuò)001a0錯(cuò)010a1錯(cuò)100a2錯(cuò)110a3錯(cuò)011a4錯(cuò)111a5錯(cuò)101a6錯(cuò)∴a5錯(cuò)含義：錯(cuò)碼圖樣E=（0100000）只有一位錯(cuò)碼定義：線性碼中任意兩個(gè)碼組之和仍為這種碼中的一個(gè)碼組證：設(shè)A1、

A2為線性碼中兩個(gè)許用碼組兩式相加∴是許用碼組推廣：1）兩個(gè)碼組間的距離必是另一碼組的重量2）除

0碼組之外，碼組的最小重量是碼集合的最小距離。線性分組碼具有封閉性9.5循環(huán)碼9.5.1碼多項(xiàng)式9.5.2循環(huán)碼的特性9.5.3循環(huán)碼的編碼方法碼多項(xiàng)式的按模運(yùn)算：9.5.1碼多項(xiàng)式碼多項(xiàng)式定義：以碼組中各碼元為系數(shù)的多項(xiàng)式T(x)=an-1xn-1+an-2xn-2+...+a1x+a0設(shè)多項(xiàng)式F(x)、除數(shù)為N(x)記：模N(x)注：多項(xiàng)式按模N(x)運(yùn)算過程中，其系數(shù)按模2加運(yùn)算（系數(shù)為二進(jìn)制，只能取0或1，系數(shù)的相減均為模2加）。x僅為碼元位置的標(biāo)記例R(x)：余式例：(1100101)T(x)=x6+x5+x2+1例：解：記為：余式定理：若T(x)對應(yīng)一個(gè)碼長為n的許用碼組，證：令∴T′(x)的系數(shù)是T(x)中系數(shù)向左循環(huán)移位i次的結(jié)果9.5.2循環(huán)碼的特性碼集合中任意一個(gè)碼組，左移或右移一位得到的新碼組必是該碼集合中另一碼組循環(huán)碼的定義循環(huán)碼的碼多項(xiàng)式則xi

T(x)按模xn

+1運(yùn)算后余式T′(x)

仍為許用碼組。∴∵例例：(7,3)循環(huán)碼,碼組為(1100101)，求碼多項(xiàng)式T(x)。

驗(yàn)證x3

T(x)按模x7

+1運(yùn)算后余式仍是一個(gè)許用碼組。解：

∵

T(x)=an-1xn-1+an-2xn-2+...+a1x+a0∴T(x)=x6+x5+x2+1∵x3

T(x)=x9+x8+x5+x3∴∴余式T′(x)對應(yīng)碼組為(0101110)是T(x)碼組左移三位循環(huán)碼的生成矩陣G9.5.3循環(huán)碼的編碼方法思路：確定編碼矩陣方程，構(gòu)造生成矩陣碼生成多項(xiàng)式g(x)的定義循環(huán)碼的監(jiān)督矩陣H碼生成多項(xiàng)式g(x)的求解例G是G(x)的系數(shù)矩陣循環(huán)碼的檢、糾錯(cuò)能力與n、k的值相關(guān)循環(huán)碼生成矩陣G

的數(shù)學(xué)描述已知(7,4)漢明碼G中每行均為一個(gè)碼組，且線性無關(guān)是線性分組碼的共性。循環(huán)碼是線性分組碼成員之一，其G除滿足上述特性外，每行之間必須滿足循環(huán)性?！哐h(huán)碼每個(gè)碼組對應(yīng)一個(gè)碼多項(xiàng)式∴以最簡方式尋找k個(gè)線性無關(guān)的碼多項(xiàng)式就能建立G(x)碼生成多項(xiàng)式g(x)的定義定義：冪次為(n-k)的碼多項(xiàng)式。（具有唯一性）分析循環(huán)碼：循環(huán)碼(n,k)的形成方法是在信息碼后加監(jiān)督碼且保持移位循環(huán)的特征。除全零碼組外，權(quán)值最小的信息碼組為00...001

，且監(jiān)督位a0

不可能為零，否則循環(huán)數(shù)次后碼組前k

位均為零，而監(jiān)督位不為零的情況，這不符合監(jiān)督碼的定義結(jié)論：信息碼組

00...001

對應(yīng)的碼多項(xiàng)式必為(n-k)

次冪，且常數(shù)項(xiàng)不等于零∵信息碼組

00...001

唯一∴碼多項(xiàng)式唯一，且冪次最低，記為g(x)∴與g(x)線性無關(guān)的

k-1個(gè)碼多項(xiàng)式為xg(x)、...xk-1g(x)，可組成生成矩陣G(x)

碼生成多項(xiàng)式g(x)的求解定理：循環(huán)碼(n,k)的g(x)是

xn

+1的一個(gè)(n-k)次因子。證：∵g(x)是冪次最低的碼多項(xiàng)式∴任意一個(gè)碼多項(xiàng)式T(x)都是g(x)倍數(shù)令T(x)=h(x)g(x)余式為碼組∵∴xkg(x)=xn

+1+T(x)∴xn

+1

=

xkg(x)+T(x)模2加=

xkg(x)+h(x)g(x)=[xk+h(x)]

g(x)得證例：已知(7,3)循環(huán)碼