ch8 信道與差錯(cuò)控制

第8章信道與差錯(cuò)控制內(nèi)容8.1概述8.2糾錯(cuò)編碼的基本原理8.3常用的簡(jiǎn)單編碼8.4線性分組碼8.5循環(huán)碼8.6漢明碼的SystemView仿真實(shí)例8.1概述

差錯(cuò)控制編碼的目的常用的差錯(cuò)控制方法差錯(cuò)控制的任務(wù)是發(fā)現(xiàn)所產(chǎn)生的錯(cuò)誤、并指出發(fā)生錯(cuò)誤的信號(hào)或者校正錯(cuò)誤差錯(cuò)控制是采用可靠、有效的信道編碼方法來實(shí)現(xiàn)的。

從差錯(cuò)控制角度看，按加性干擾引起錯(cuò)碼分布規(guī)律的不同，信道可以分為三類：即隨機(jī)信道、突發(fā)信道和混合信道。隨機(jī)信道——在隨機(jī)信道中、錯(cuò)碼的出現(xiàn)是隨機(jī)的，且錯(cuò)碼之間是統(tǒng)計(jì)獨(dú)立的。突發(fā)信道——錯(cuò)碼是成串集中出現(xiàn)的。產(chǎn)生突發(fā)錯(cuò)碼的主要原因之一是脈沖干擾，而信道中的衰落現(xiàn)象也是產(chǎn)生突發(fā)錯(cuò)碼的另一主要原因?；旌闲诺馈嬖陔S機(jī)和突發(fā)兩種錯(cuò)碼，且隨機(jī)錯(cuò)誤和突發(fā)錯(cuò)誤都占有相當(dāng)比例的信道。短波信道和對(duì)流層散射信道是混合信道的典型例子一、差錯(cuò)控制編碼的目的二、

常用的差錯(cuò)控制方法自動(dòng)請(qǐng)求重發(fā)方式(ARQ，Automatic-Repeat-reQuest)。

前向糾錯(cuò)方式(FEC，F(xiàn)orward-errorcontrol)。混合糾錯(cuò)(HEC，HybridErrorCorrection)。停發(fā)等候重發(fā)系統(tǒng)、返回重發(fā)系統(tǒng)選擇重發(fā)系統(tǒng)。三種ARQ:8.2糾錯(cuò)的編碼基本原理差錯(cuò)控制編碼的基本概念分組碼的概念碼距與糾錯(cuò)能力的關(guān)系糾錯(cuò)編碼的分類一、差錯(cuò)控制編碼的基本概念在信息碼元序列中按某種規(guī)律加入監(jiān)督碼元就稱為差錯(cuò)控制編碼，有時(shí)也稱為糾錯(cuò)編碼。（晴）000（云）001（陰）010（雨）011（雪）100（霜）101（霧）110（雹）111差錯(cuò)控制編碼原則上是用增加碼元數(shù)，利用“冗余”來提高抗干擾的能力，即是以降低信息傳輸速率為代價(jià)來換取傳輸可靠性的提高，或者說是用削弱有效性來增強(qiáng)可靠性。（晴）00（云）01（陰）10（雨）110110（晴）000（雨）111二、分組碼的概念

我們把這種將信息碼分組，為每組信碼附加若干監(jiān)督碼的編碼集合，稱為分組碼。（晴）00（云）01（陰）10（雨）110110監(jiān)督位信息位分組碼的結(jié)構(gòu)an-1an-2ar…………ar-1a0k位信息位r位監(jiān)督位n=k+r時(shí)間

符號(hào)(n，k)表示分組碼

k——信息碼元數(shù)

n——碼組長度(碼長)n-k——監(jiān)督碼元數(shù)碼長、碼重與碼距碼長——碼字中碼元的個(gè)數(shù)稱為碼字的長度，用n表示碼重——“1”的數(shù)量稱為碼組的重量，記作W

碼距——兩個(gè)碼組對(duì)應(yīng)位上數(shù)字不同的位數(shù)稱為碼組的距離，簡(jiǎn)稱碼距。又稱漢明(Hamming)距離。最小碼距——某種編碼中各個(gè)碼組間距離的最小值稱為最小碼距(dmin)。

例如碼字“110000”，其碼長n=6，碼重W=2

對(duì)于n=3的編碼組，可以在三維空間中說明碼距的幾何意義。（晴）000（云）011（陰）101（雨）110碼組之間的距離均為2定理：若糾錯(cuò)碼的最小距離為dmin

，那么如下三個(gè)結(jié)論的任何一個(gè)結(jié)論獨(dú)立成立：①若要發(fā)現(xiàn)e

個(gè)獨(dú)立差錯(cuò)，則要求最小碼距；②若要糾正t

個(gè)獨(dú)立差錯(cuò)，則要求最小碼距；③若要求發(fā)現(xiàn)e

個(gè)同時(shí)又糾正t個(gè)獨(dú)立差錯(cuò)，則；這里說的“同時(shí)”是指在譯碼過程中，若錯(cuò)誤個(gè)數(shù)≤t

，則能糾正；若錯(cuò)誤個(gè)數(shù)＞t

，但≤e（e>t），則能檢測(cè)這些錯(cuò)誤，但不能糾正?；蛘哒f能檢測(cè)e

個(gè)錯(cuò)誤，其中t

個(gè)錯(cuò)誤可以糾正。三、碼距與糾錯(cuò)能力的關(guān)系檢糾錯(cuò)能力的幾何說明定理說明，碼的最小距離dmin越大，碼的糾(檢)錯(cuò)誤的能力越強(qiáng)。但是，隨著多余碼元的增多，信息傳輸速率會(huì)降低得越多。通常用η=k/n

來表示碼字中信息碼元所占的比例，稱為編碼效率，簡(jiǎn)稱碼率，它是衡量碼性能的又一個(gè)重要參數(shù)碼率越高，信息傳輸率就越高，但此時(shí)糾錯(cuò)能力要降低，若η=1

時(shí)就沒有糾錯(cuò)能力了?？梢姡a率與糾錯(cuò)能力之間是有矛盾的。編碼效率根據(jù)碼的用途，差錯(cuò)編碼分為檢錯(cuò)碼和糾錯(cuò)碼根據(jù)信息碼元與監(jiān)督碼元之間的關(guān)系，糾錯(cuò)碼分為線性碼和非線性碼。線性碼——信息碼元與監(jiān)督碼元之間呈線性關(guān)系，它們的關(guān)系可用一組線性代數(shù)方程聯(lián)系起來。非線性碼——信息碼元與監(jiān)督校元之間不存在線性關(guān)系。四、糾錯(cuò)編碼的分類按照對(duì)信息碼元處理的方法的不同，糾錯(cuò)碼分為分組碼和卷積碼。分組碼----把信息序列以每k個(gè)碼元分組，然后把每組k個(gè)信息元按一定規(guī)律產(chǎn)生r個(gè)多余的監(jiān)督碼元，輸出序列每組長為n=k+r，則每一碼字的r個(gè)校驗(yàn)元只與本碼字的k個(gè)信息位有關(guān)，與別的碼字的信息位無關(guān)，通常記分組碼為（n，k）。其中分組碼又可分循環(huán)碼和非循環(huán)碼：對(duì)循環(huán)碼而言，其碼組的特點(diǎn)是，若將其全部碼字分成若干組，則每組中任一碼字中碼元循環(huán)移位后仍是這組的碼字；對(duì)非循環(huán)碼來說，任一碼字中的碼元循環(huán)移位后不一定再是該碼組中的碼字。卷積碼----把信息序列以每k0(通常較小)個(gè)碼元分段，編碼器輸出該段的監(jiān)督碼元r=n-k0不但與本段的k0個(gè)信息元有關(guān)，而且還與其前面L段的信息碼元有關(guān)，故記卷積碼為（n，k0，L）。糾正隨機(jī)錯(cuò)誤碼和糾正突發(fā)錯(cuò)誤碼。顧名思義，前者用于糾正因信道中出現(xiàn)的隨機(jī)獨(dú)立干擾引起的誤碼，后者主要對(duì)付信號(hào)道中出現(xiàn)的突發(fā)錯(cuò)誤。按照每個(gè)碼元的取值來分，可有二元碼和多元碼。由于目前的傳輸或存儲(chǔ)系統(tǒng)大都采用二進(jìn)制的數(shù)字系統(tǒng)，所以一般提到的糾錯(cuò)碼都是指二元碼。

8.3常用的簡(jiǎn)單編碼奇偶校驗(yàn)碼二維奇偶校驗(yàn)碼恒比碼

一、奇偶校驗(yàn)碼奇校驗(yàn)---偶校驗(yàn)----缺點(diǎn)：無法檢測(cè)偶數(shù)個(gè)錯(cuò)碼優(yōu)點(diǎn)：效率高水平垂直奇偶校驗(yàn)碼：在二維空間上進(jìn)行奇校驗(yàn)碼元---偶校驗(yàn)碼元---碼元位分組偶校驗(yàn)位12345678910110001110011201101000111300010111000410001000000500011011011601110010000701101010011偶校驗(yàn)位01111010100二、二維奇偶校驗(yàn)碼

水平垂直奇偶校驗(yàn)的編碼效率k為待發(fā)送信號(hào)序列的分組數(shù)；p為每一分組中的比特?cái)?shù)水平垂直奇偶校驗(yàn)的檢錯(cuò)能力：這種方法能檢測(cè)出所有3位或3位以下的錯(cuò)誤，因?yàn)樵谶@種情況下，至少會(huì)在某一行或某一列上出現(xiàn)一位錯(cuò)，這時(shí)錯(cuò)誤就能被檢測(cè)到；還能檢測(cè)出奇數(shù)位錯(cuò)以及很大一部分偶數(shù)位錯(cuò)。一些試驗(yàn)測(cè)量表明，這種方式的編碼可使誤碼率降至原始誤碼率的百分之一到萬分之一。另外，水平垂直奇偶校驗(yàn)不僅可檢錯(cuò)，還可用來糾正部分差錯(cuò)，但多數(shù)情況下只用于檢錯(cuò)。三、恒比碼恒比碼---每個(gè)碼組的數(shù)目“1”(和“0”)都保持固定的比例，故得此名。檢錯(cuò)原理---只要計(jì)算接收到的碼組中“1”的數(shù)目是否對(duì)就知道有無錯(cuò)誤。在我國用電傳機(jī)傳輸漢字時(shí)，只使用阿拉伯?dāng)?shù)字代表漢字。每個(gè)漢字用4位阿拉伯?dāng)?shù)字表示，每個(gè)阿拉伯?dāng)?shù)字又用5位二進(jìn)制符號(hào)構(gòu)成的碼組表示。這時(shí)采用的所謂“保護(hù)電碼”就是“3∶2”或稱“5中取3”的恒比碼，即每個(gè)碼組的長度為5，其中“1”的個(gè)數(shù)總是3，而“0”的個(gè)數(shù)總是2。數(shù)字字符普通的五單位碼恒比碼數(shù)字字符普通的五單位碼恒比碼11110101011610101101012110011100171110011100310000101108011000111040101011010900011100115000010011100110101101本來以5位碼元組成的碼組總共可以有32種，而恒比碼規(guī)定只取含有3個(gè)“1”，2個(gè)“0”的那些碼組為準(zhǔn)用碼組，而有3個(gè)“1”，2個(gè)“0”的5位碼組共有多少？這是“5中取3”求組合的算法，組合數(shù)為10。8.4線性分組碼線性分組碼的概念線性分組碼的編碼線性分組碼的譯碼完備碼與漢明碼

一、線性分組碼的概念回顧偶校驗(yàn)方法:偶校驗(yàn)----在接收端解碼時(shí)，我們實(shí)際上是在計(jì)算:若S=0，就認(rèn)為無錯(cuò)碼。若S=1，就認(rèn)為有錯(cuò)碼。上式就是一致監(jiān)督關(guān)系式S稱為“校驗(yàn)子”由于校驗(yàn)子的取值只有這樣兩種，它就只能代表有錯(cuò)和無錯(cuò)兩種信息，而不能指出錯(cuò)碼的位置。不難推想，如監(jiān)督位增加一位，變成兩位，能增加一個(gè)監(jiān)督關(guān)系式。兩個(gè)校驗(yàn)子的可能值有4種組合00，01，10，11。故能表示4種不同的信息，其中一種表示無錯(cuò)，其余三種就有可能用來指示一位錯(cuò)碼的3種不同位置。同理，r個(gè)監(jiān)督關(guān)系式能指示一位錯(cuò)碼的2r-1個(gè)可能位置。一般說來，若碼長為n，信息碼為k，則監(jiān)督碼數(shù)。若希望用r個(gè)監(jiān)督碼構(gòu)造出r個(gè)監(jiān)督關(guān)系式來指示一位錯(cuò)碼的n種可能位置，則要求或二、線性分組碼的編碼線性分組碼的編碼：就是根據(jù)一致校驗(yàn)矩陣H或生成矩陣G將長度為k的信息碼元變換成長度為n的碼字。這里以（7，3）線性分組碼為例來說明構(gòu)造編碼電路的方法。生成矩陣生成矩陣：式中:或監(jiān)督矩陣監(jiān)督矩陣式中:而:要找到G矩陣或H矩陣，便解決了編碼問題。經(jīng)編碼后發(fā)送的碼字，由于信道干擾可能出錯(cuò)，接收方怎樣發(fā)現(xiàn)或糾正錯(cuò)誤呢，這就是譯碼要解決的問題。譯碼過程：先計(jì)算下式三、線性分組碼的譯碼

或

判斷S是否為零。若S=0，則正確?？筛鶕?jù)S來檢錯(cuò)和糾錯(cuò)或

S為線性分組碼的伴隨式【例】已知（8，4）線性分組碼，其一致監(jiān)督方程為其中信息碼元為：（1）求該分組碼的監(jiān)督矩陣和生成矩陣。（2）寫出信碼（0011）和（1010）的系統(tǒng)碼組。（3）若接收的碼字為（01010100）和（01110001），判斷他們是否為錯(cuò)碼，并指出錯(cuò)在哪一位？題意分析：由一致監(jiān)督方程可以寫出其監(jiān)督矩陣，由監(jiān)督矩陣和生成矩陣的轉(zhuǎn)換關(guān)系可以求出生成矩陣，由信碼與生成矩陣相乘方可求出系統(tǒng)碼。由接收的碼字通過監(jiān)督矩陣求出伴隨式，由伴隨式所對(duì)應(yīng)的錯(cuò)誤圖案即可以找出錯(cuò)在哪一位。解：（1）監(jiān)督矩陣由一致監(jiān)督方程可直接寫出

（2）系統(tǒng)碼（3）接收碼字正誤判斷此碼正確此碼錯(cuò)誤錯(cuò)C1位糾錯(cuò)能力t=1的完備碼稱為漢明碼。漢明碼屬于線性分組碼，1950年由美國人漢明提出。漢明碼具有編碼效率高，譯碼簡(jiǎn)單等特點(diǎn)，在實(shí)際中得到了廣泛應(yīng)用。二元(n,k)漢明碼滿足關(guān)系式四、完備碼與漢明碼

當(dāng)輸入信息碼元為(1001)，即，設(shè)循環(huán)碼的生成多項(xiàng)式，由系統(tǒng)碼生成規(guī)則：其運(yùn)算過程為：

一、循環(huán)碼的編碼方法8.5循環(huán)碼二、循環(huán)碼的編碼器

漢明碼是線性分組碼的一個(gè)子類型，利用監(jiān)督碼與信息碼之間的線性關(guān)系，可以完成漢明碼的編碼。漢明碼的譯碼可以先計(jì)算校正子，然后按校正圖樣加以糾正。

8.6漢明碼的Syste