數(shù)據(jù)通信技術(shù)與應(yīng)用

會(huì)計(jì)學(xué)1數(shù)據(jù)通信技術(shù)與應(yīng)用數(shù)據(jù)通信技術(shù)與應(yīng)用第八章第八章 差錯(cuò)控制技術(shù)差錯(cuò)控制技術(shù)OUTLINE8.1 概述8.2 差錯(cuò)控制方法8.3 常用檢錯(cuò)碼8.4 線性分組碼8.5 循環(huán)碼8.6 卷積碼第1頁(yè)/共65頁(yè)8.1 概述概述n n由于信道特性的不理想和信道中存在噪聲，數(shù)據(jù)信號(hào)在傳輸過(guò)程中不可避免地會(huì)發(fā)生差錯(cuò)。n n引起誤碼的原因n n乘性噪聲乘性噪聲n n加性噪聲加性噪聲 隨機(jī)噪聲（隨機(jī)噪聲（隨機(jī)差錯(cuò)隨機(jī)差錯(cuò)：錯(cuò)碼互相：錯(cuò)碼互相獨(dú)立）獨(dú)立）脈沖噪聲（脈沖噪聲（突發(fā)差錯(cuò)突發(fā)差錯(cuò)：成串集中：成串集中的差錯(cuò)）的差錯(cuò)）第2頁(yè)/共65頁(yè)提高數(shù)據(jù)通信可靠性的提高數(shù)據(jù)通信可靠性的途徑途徑應(yīng)用不同，誤碼率要求不同，方法不同n n改善傳輸信道電氣特性 抗干擾 能力強(qiáng)的傳輸介質(zhì)n n差錯(cuò)控制技術(shù)n n編碼技術(shù)編碼技術(shù)n n差錯(cuò)控制方法差錯(cuò)控制方法第3頁(yè)/共65頁(yè)差錯(cuò)控制的基本概念差錯(cuò)控制的基本概念核心：差錯(cuò)控制編碼，即在信息碼元序列中加入監(jiān)督碼元n n差錯(cuò)控制編碼：在發(fā)送端通過(guò)對(duì)信源輸出的二進(jìn)制信息序列作某種變換，使原來(lái)彼此獨(dú)立、互不相干的信息碼元序列產(chǎn)生一定的相關(guān)性，變成具有一定規(guī)律的數(shù)據(jù)序列，從而在接收端能根據(jù)這種規(guī)律性來(lái)檢查，進(jìn)而檢錯(cuò)或糾正傳輸信號(hào)中的差錯(cuò)。n n奇偶校驗(yàn)第4頁(yè)/共65頁(yè)差錯(cuò)控制編碼類(lèi)型差錯(cuò)控制編碼類(lèi)型n n檢錯(cuò)碼n n 在一定程度上發(fā)現(xiàn)傳輸錯(cuò)誤但不能自動(dòng)在一定程度上發(fā)現(xiàn)傳輸錯(cuò)誤但不能自動(dòng)糾正糾正n n 反饋重傳反饋重傳n n糾錯(cuò)碼n n自動(dòng)糾正傳輸差錯(cuò)自動(dòng)糾正傳輸差錯(cuò)第5頁(yè)/共65頁(yè)差錯(cuò)控制的基本原理差錯(cuò)控制的基本原理p原理原理 許用碼字許用碼字 禁用碼字禁用碼字第6頁(yè)/共65頁(yè)差錯(cuò)控制編碼的特性和差錯(cuò)控制編碼的特性和能力能力n n差錯(cuò)控制編碼的特性 碼元碼字碼組 碼長(zhǎng)：碼字的碼元個(gè)數(shù)n n漢明重量漢明重量n n碼間距離碼間距離n n最小碼距最小碼距第7頁(yè)/共65頁(yè)差錯(cuò)控制編碼的特性和差錯(cuò)控制編碼的特性和能力（能力（cont.）n n最小碼距最小碼距n n碼組的最小碼距不同，抗干擾碼組的最小碼距不同，抗干擾能力也不同能力也不同n n碼組的最小碼距越大，抗干擾碼組的最小碼距越大，抗干擾能力越強(qiáng)能力越強(qiáng)第8頁(yè)/共65頁(yè)差錯(cuò)控制編碼的特性和差錯(cuò)控制編碼的特性和能力（能力（cont.）n n最小碼距與編碼的檢錯(cuò)糾錯(cuò)能力的關(guān)系定理1定理2定理3第9頁(yè)/共65頁(yè)差錯(cuò)控制編碼的特性和差錯(cuò)控制編碼的特性和能力（能力（cont.）第10頁(yè)/共65頁(yè)差錯(cuò)控制編碼的特性和差錯(cuò)控制編碼的特性和能力（能力（cont.）編碼效率n n監(jiān)督碼元：為了減少傳輸差錯(cuò)，在用戶信息序列中插入一定數(shù)量的新碼元第11頁(yè)/共65頁(yè)第八章第八章 差錯(cuò)控制技術(shù)差錯(cuò)控制技術(shù)OUTLINE8.1 概述8.2 差錯(cuò)控制方法8.3 常用檢錯(cuò)碼8.4 線性分組碼8.5 循環(huán)碼8.6 卷積碼第12頁(yè)/共65頁(yè)8.2 差錯(cuò)控制方法差錯(cuò)控制方法n n定義：利用差錯(cuò)控制編碼來(lái)控制傳輸系統(tǒng)的傳輸差錯(cuò)的方法 檢錯(cuò)碼、糾錯(cuò)碼n n基本思想:在所傳送的相互獨(dú)立無(wú)關(guān)的數(shù)字信號(hào)中，人為地按一定規(guī)律假如一定的多余碼元，使所傳輸?shù)拇a字的前后碼元產(chǎn)生一定的相關(guān)性，從而具有一定的監(jiān)督關(guān)系。接收端就可以利用這種監(jiān)督關(guān)系來(lái)檢測(cè)、糾正錯(cuò)誤。第13頁(yè)/共65頁(yè)差錯(cuò)控制方法分類(lèi)差錯(cuò)控制方法分類(lèi)n n自動(dòng)請(qǐng)求重發(fā)（Automatic Repeat Request,ARQ）n n前向糾錯(cuò)（Forward Error Correction,FEC）n n混合糾錯(cuò)（Hybrid Error Correction,HEC）n n信息反饋（Information Repeat Request,IRQ）第14頁(yè)/共65頁(yè)數(shù)據(jù)請(qǐng)求重發(fā)方式數(shù)據(jù)請(qǐng)求重發(fā)方式(ARQ)n n停等式ARQn n連續(xù)式ARQn n回退回退NN幀幀ARQARQn n選擇性重發(fā)選擇性重發(fā)ARQARQ第15頁(yè)/共65頁(yè)停等式停等式ARQn n數(shù)據(jù)鏈路層、確認(rèn)信息、超時(shí)定時(shí)器第16頁(yè)/共65頁(yè)連續(xù)式連續(xù)式ARQ 停等式ARQ缺點(diǎn)：發(fā)送端每發(fā)送一個(gè)信息幀都要停下來(lái)等待接收端的確認(rèn)信息，信道的利用率很低n n連續(xù)式ARQ：不等待前幀確認(rèn)便發(fā)下一幀n n問(wèn)題：接收端如何對(duì)待出錯(cuò)幀之后所接收到的正確幀？n n回退回退NN幀幀ARQARQn n選擇性重發(fā)選擇性重發(fā)ARQARQ第17頁(yè)/共65頁(yè)回退回退N幀幀ARQn n工作過(guò)程n n可能出現(xiàn)的問(wèn)題（1）數(shù)據(jù)幀和確認(rèn)幀都不發(fā)生差錯(cuò)和丟失（2）數(shù)據(jù)幀出現(xiàn)差錯(cuò)（3）數(shù)據(jù)幀正確，確認(rèn)幀出現(xiàn)差錯(cuò)第18頁(yè)/共65頁(yè)回退回退N幀幀ARQ（cont.）n n工作過(guò)程n當(dāng)線路傳播質(zhì)量很差，誤碼率較大時(shí)，回退當(dāng)線路傳播質(zhì)量很差，誤碼率較大時(shí)，回退N幀幀ARQ方案不一定優(yōu)于等停式方案不一定優(yōu)于等停式ARQ。n在長(zhǎng)傳播延時(shí)鏈路上回退在長(zhǎng)傳播延時(shí)鏈路上回退N幀幀ARQ的傳輸效率也較低的傳輸效率也較低。第19頁(yè)/共65頁(yè)選擇性重發(fā)選擇性重發(fā)ARQ 發(fā)送端收到包含出錯(cuò)幀序號(hào)的NAK后，據(jù)此序號(hào)從重發(fā)表中選出相應(yīng)的幀的備份，插入到發(fā)送幀隊(duì)列前面予以重發(fā)n n缺點(diǎn)：接收端需要更大的緩沖區(qū)存放繼出錯(cuò)幀之后到達(dá)的正確的數(shù)據(jù)幀n n實(shí)際應(yīng)用的選擇n n發(fā)送端和接收端處理機(jī)的處理速度n n緩沖器大小第20頁(yè)/共65頁(yè)選擇性重發(fā)選擇性重發(fā)ARQ（cont.）第21頁(yè)/共65頁(yè)ARQ的特點(diǎn)的特點(diǎn)第22頁(yè)/共65頁(yè)差錯(cuò)控制方法分類(lèi)差錯(cuò)控制方法分類(lèi)n n自動(dòng)請(qǐng)求重發(fā)（Automatic Repeat Request,ARQ）n n前向糾錯(cuò)（Forward Error Correction,FEC）n n混合糾錯(cuò)（Hybrid Error Correction,HEC）n n信息反饋（Information Repeat Request,IRQ）第23頁(yè)/共65頁(yè)前向糾錯(cuò)方式（前向糾錯(cuò)方式（FEC）n n工作過(guò)程利用糾錯(cuò)編碼，接收端譯碼器能發(fā)現(xiàn)錯(cuò)誤并能準(zhǔn)確地判斷差錯(cuò)的位置，從而自動(dòng)糾正錯(cuò)誤n n特點(diǎn)第24頁(yè)/共65頁(yè)混合糾錯(cuò)方式混合糾錯(cuò)方式（HEC）n nFEC和ARC方式的結(jié)合 能糾則糾，不能糾則重發(fā)n n特點(diǎn)第25頁(yè)/共65頁(yè)信息反饋方式（信息反饋方式（IRQ）在發(fā)送端檢測(cè)錯(cuò)誤n n工作過(guò)程n n特點(diǎn)第26頁(yè)/共65頁(yè)第八章第八章 差錯(cuò)控制技術(shù)差錯(cuò)控制技術(shù)OUTLINE8.1 概述8.2 差錯(cuò)控制方法8.3 常用檢錯(cuò)碼8.4 線性分組碼8.5 循環(huán)碼8.6 卷積碼第27頁(yè)/共65頁(yè)8.3 常用檢錯(cuò)碼常用檢錯(cuò)碼n n奇偶校驗(yàn)碼n n恒比碼n n矩陣校驗(yàn)碼n n正反碼第28頁(yè)/共65頁(yè)(1)奇偶校驗(yàn)碼奇偶校驗(yàn)碼n n偶校驗(yàn)n n奇校驗(yàn)n n優(yōu)點(diǎn)：簡(jiǎn)單、冗余度低、效率高 缺點(diǎn)：奇偶校驗(yàn)不能檢查出偶數(shù)個(gè)錯(cuò)第29頁(yè)/共65頁(yè)(2)恒比碼恒比碼n n碼字中1和0的個(gè)數(shù)是恒定的n n“保護(hù)電碼”“5中取3的恒比碼”第30頁(yè)/共65頁(yè)恒比碼（恒比碼（cont.）p“5中取中取3”的恒比碼的編碼效率？的恒比碼的編碼效率？p國(guó)際無(wú)線電報(bào)碼國(guó)際無(wú)線電報(bào)碼“7取取3”恒比碼的編碼效率？恒比碼的編碼效率？第31頁(yè)/共65頁(yè)恒比碼（恒比碼（cont.）n n優(yōu)點(diǎn) 簡(jiǎn)單，適合傳輸電傳機(jī)或其他鍵盤(pán)設(shè)備產(chǎn)生的字母或符號(hào)n n缺點(diǎn)n n不適用隨機(jī)二進(jìn)制數(shù)字序列的編碼n n不能發(fā)現(xiàn)的錯(cuò)誤：1錯(cuò)成0的數(shù)目=0錯(cuò)成1的數(shù)目第32頁(yè)/共65頁(yè)(3)矩陣校驗(yàn)碼矩陣校驗(yàn)碼第33頁(yè)/共65頁(yè)矩陣校驗(yàn)碼矩陣校驗(yàn)碼(cont.)第34頁(yè)/共65頁(yè)矩陣校驗(yàn)碼矩陣校驗(yàn)碼(cont.)第35頁(yè)/共65頁(yè)矩陣校驗(yàn)碼矩陣校驗(yàn)碼(cont.)n n編碼特點(diǎn)第36頁(yè)/共65頁(yè)（4）正反碼）正反碼編碼方法n n每個(gè)正反碼字由10個(gè)碼元組成，信息位5位，監(jiān)督位5位n n當(dāng)信息碼中1的個(gè)數(shù)為奇數(shù)時(shí)，監(jiān)督碼元與信息碼元相同n n當(dāng)信息碼中1的個(gè)數(shù)為偶數(shù)時(shí)，監(jiān)督碼元是信息碼元的反碼第37頁(yè)/共65頁(yè)正反碼正反碼(cont.)校驗(yàn)方法n n先將接收碼字中信息位和監(jiān)督位按對(duì)應(yīng)位模2相加，得到一個(gè)5位的合成碼n n用合成嗎生成校驗(yàn)碼n n當(dāng)接收碼字中當(dāng)接收碼字中1 1的個(gè)數(shù)為奇數(shù)時(shí)，的個(gè)數(shù)為奇數(shù)時(shí)，合成碼字就作為校驗(yàn)碼字合成碼字就作為校驗(yàn)碼字n n當(dāng)接收碼字中當(dāng)接收碼字中1 1的個(gè)數(shù)為偶數(shù)時(shí)，的個(gè)數(shù)為偶數(shù)時(shí)，校驗(yàn)碼字就是合成碼的反碼校驗(yàn)碼字就是合成碼的反碼n n觀察校驗(yàn)碼字中1的個(gè)數(shù)，進(jìn)行判決和糾正錯(cuò)誤第38頁(yè)/共65頁(yè)正反碼正反碼(cont.)校驗(yàn)方法n n先將接收碼字中信息位和監(jiān)督位按對(duì)應(yīng)位模2相加，得到一個(gè)5位的合成碼n n用合成嗎生成校驗(yàn)碼n n當(dāng)接收碼字中當(dāng)接收碼字中1 1的個(gè)數(shù)為奇數(shù)時(shí)，的個(gè)數(shù)為奇數(shù)時(shí)，合成碼字就作為校驗(yàn)碼字合成碼字就作為校驗(yàn)碼字舉例舉例n n發(fā)送碼字10101 10101，接收碼字10101 10101n n發(fā)送碼字10101 10101，接收碼字11101 10101n n發(fā)送碼字10101 10101，接收碼字10101 00101n n發(fā)送碼字10101 10101，接收碼字00001 10101第39頁(yè)/共65頁(yè)第八章第八章 差錯(cuò)控制技術(shù)差錯(cuò)控制技術(shù)OUTLINE8.1 概述8.2 差錯(cuò)控制方法8.3 常用檢錯(cuò)碼8.4 線性分組碼8.5 循環(huán)碼8.6 卷積碼第40頁(yè)/共65頁(yè)8.4 線性分組碼線性分組碼Linear Block Codes，數(shù)碼，系統(tǒng)碼、群碼、塊碼n n（n,k）碼n n監(jiān)督碼元與信息碼元的關(guān)系為線性關(guān)系n n特點(diǎn)n n封閉性：任意2個(gè)碼字之和（模2和）仍為一個(gè)碼字n n碼的最小距離等于非零碼的最小重量第41頁(yè)/共65頁(yè)線性分組碼的編碼線性分組碼的編碼n n（7，4）碼，第42頁(yè)/共65頁(yè)線性分組碼的編碼線性分組碼的編碼第43頁(yè)/共65頁(yè)線性分組碼的監(jiān)督矩陣線性分組碼的監(jiān)督矩陣和生成矩陣和生成矩陣監(jiān)督矩陣監(jiān)督矩陣第44頁(yè)/共65頁(yè)線性分組碼的生成矩陣線性分組碼的生成矩陣生成矩陣生成矩陣第45頁(yè)/共65頁(yè)線性分組碼的檢錯(cuò)和糾線性分組碼的檢錯(cuò)和糾錯(cuò)錯(cuò)監(jiān)督關(guān)系式、校正子n n奇偶校驗(yàn)n n若碼長(zhǎng)為n，信息位數(shù)為k，則監(jiān)督位數(shù)為r=n-k 如果希望用r個(gè)監(jiān)督位構(gòu)造出r個(gè)監(jiān)督關(guān)系式來(lái)指示一位錯(cuò)碼的n種可能位置，則要求第46頁(yè)/共65頁(yè)線性分組碼的檢錯(cuò)和糾線性分組碼的檢錯(cuò)和糾錯(cuò)錯(cuò)(cont.)第47頁(yè)/共65頁(yè)線性分組碼的檢錯(cuò)和糾線性分組碼的檢錯(cuò)和糾錯(cuò)錯(cuò)(cont.)第48頁(yè)/共65頁(yè)線性分組碼的檢錯(cuò)和糾線性分組碼的檢錯(cuò)和糾錯(cuò)錯(cuò)(cont.)要點(diǎn)：要點(diǎn)：第49頁(yè)/共65頁(yè)線性分組碼的檢錯(cuò)和糾線性分組碼的檢錯(cuò)和糾錯(cuò)錯(cuò)(cont.)第50頁(yè)/共65頁(yè)第八章第八章 差錯(cuò)控制技術(shù)差錯(cuò)控制技術(shù)OUTLINE8.1 概述8.2 差錯(cuò)控制方法8.3 常用檢錯(cuò)碼8.4 線性分組碼8.5 循環(huán)碼8.6 卷積碼第51頁(yè)/共65頁(yè)8.5 循環(huán)碼循環(huán)碼循環(huán)冗余校驗(yàn)碼（CRC）n n定義 線性分組碼中各碼字中的碼元循環(huán)左移位（或右移位）所形成的碼字仍然是碼組中的一個(gè)碼字（除全零碼外）第52頁(yè)/共65頁(yè)循環(huán)碼（循環(huán)碼（cont.）n n碼多項(xiàng)式n n100111，101010n n二進(jìn)制碼多項(xiàng)式的加減運(yùn)算實(shí)際上是邏輯上的異或運(yùn)算第53頁(yè)/共65頁(yè)循環(huán)碼（循環(huán)碼（cont.）(n,k)循環(huán)碼的生成多項(xiàng)式g(x)的性質(zhì)第54頁(yè)/共65頁(yè)循環(huán)碼（循環(huán)碼（cont.）循環(huán)碼的性質(zhì)第55頁(yè)/共65頁(yè)循環(huán)碼（循環(huán)碼（cont.）循環(huán)碼的性質(zhì)第56頁(yè)/共65頁(yè)循環(huán)碼（循環(huán)碼（cont.）循環(huán)碼的編碼和譯碼第57頁(yè)/共65頁(yè)循環(huán)碼（循環(huán)碼（cont.）循環(huán)碼的編碼和譯碼第58頁(yè)/共65頁(yè)循環(huán)碼的生成和校驗(yàn)循環(huán)碼的生成和校驗(yàn)（1）循環(huán)碼的生成第59頁(yè)/共65頁(yè)循環(huán)碼的生成和校驗(yàn)循環(huán)碼的生成和校驗(yàn)（2）循環(huán)碼的校驗(yàn)第60頁(yè)/共65頁(yè)循環(huán)碼（循環(huán)碼（cont.）第61頁(yè)/共65頁(yè)循環(huán)碼（循環(huán)碼（cont.）第62頁(yè)/共65頁(yè)第八章第八章 差錯(cuò)控制技術(shù)差錯(cuò)控制技術(shù)OUTLINE8.1 概述8.2 差錯(cuò)控制方法8.3 常用檢錯(cuò)碼8.4 線性分組碼8.5 循環(huán)碼*8.6 卷積碼第63頁(yè)/共65頁(yè)8.6 卷積碼卷積碼第64頁(yè)/共65頁(yè)