信息論 基礎(chǔ)理論與應(yīng)用第三版(傅祖蕓)-第9章-講義

第9章信道的糾錯(cuò)編碼差錯(cuò)控制的基本形式糾錯(cuò)碼分類及其基本概念線性分組碼*循環(huán)碼*卷積碼香農(nóng)定理指出，只要信息傳輸率小于信道容量，通過適當(dāng)?shù)木幾g碼方法，就能以任意小的錯(cuò)誤概率傳輸信息。但從實(shí)際工程看，并沒有指出具體的編譯碼方法。這正是信道糾錯(cuò)編碼要解決的問題。2021/6/271

香農(nóng)第二定理指出，在信道中以信息傳輸率R小于信道容量條件下，使差錯(cuò)概率盡可能小的信道編譯碼原則是：編碼原則：

在n次擴(kuò)展信道輸入符號序列中選取M個(gè)作為碼字構(gòu)成一組碼C，并盡量使選取的M個(gè)碼字中兩兩不相同碼字的漢明距離盡可能地大；譯碼原則：當(dāng)收到符號序列后，翻譯成與之漢明距離最近的碼字（最大似然準(zhǔn)則）。幾十年來，基于香農(nóng)編碼定理和以上編譯碼原則，科技工作者們開發(fā)了很多具有糾錯(cuò)能力的信道編碼，如線性分組碼、循環(huán)碼、BCH碼、卷積碼、TCM碼、Tuobo碼等，在通信系統(tǒng)中得到了廣泛應(yīng)用。2021/6/2729.1差錯(cuò)控制的基本形式

現(xiàn)代數(shù)字通信系統(tǒng)中，利用檢錯(cuò)和糾錯(cuò)的編碼技術(shù)，使得信道編譯碼具備一定的差錯(cuò)控制能力。主要方式有：1、前向糾錯(cuò)(FEC)方式：

發(fā)送端信道編碼器將信息碼組編成具有一定糾錯(cuò)能力的碼。接收端信道譯碼器對接收碼字譯碼，若傳輸中產(chǎn)生的差錯(cuò)數(shù)目在碼的糾錯(cuò)能力之內(nèi)，譯碼器對差錯(cuò)進(jìn)行定位并加以糾正。發(fā)送端接收端可檢錯(cuò)糾錯(cuò)的碼FEC檢錯(cuò)、糾錯(cuò)2021/6/273FEC特點(diǎn)單向控制，不需要反饋信道；時(shí)延小，實(shí)時(shí)性好。為適應(yīng)較差信道，冗余碼元多，編碼效率低，譯碼設(shè)備復(fù)雜。有一定的糾錯(cuò)范圍限制。

適用于容錯(cuò)能力強(qiáng)的語音、圖像傳輸；不適合容錯(cuò)能力弱的數(shù)據(jù)通信網(wǎng)。2、反饋重發(fā)(ARQ)方式（檢錯(cuò)重發(fā)方式）：發(fā)送端發(fā)送的是能夠發(fā)現(xiàn)（檢測）錯(cuò)誤的碼；

接收端收到信道傳輸來的碼后，譯碼器依據(jù)該碼編碼規(guī)則，判決出當(dāng)前碼字傳輸是否出錯(cuò)，并把判決結(jié)果（應(yīng)答信號）反饋至發(fā)送端。發(fā)送端把接收端認(rèn)為有錯(cuò)的信息重新發(fā)出，直到接收端認(rèn)為正確為止。2021/6/274發(fā)送端接收端可檢錯(cuò)的碼ARQ應(yīng)答信號檢錯(cuò)、不糾錯(cuò)ARQ特點(diǎn)需要雙向控制和反饋信道。系統(tǒng)的控制設(shè)備和存儲(chǔ)設(shè)備復(fù)雜，但編譯碼設(shè)備較簡單。接收端檢錯(cuò)能力、系統(tǒng)糾錯(cuò)能力強(qiáng)，可大大降低系統(tǒng)誤碼率。具有自適應(yīng)性。但若重發(fā)頻繁，將使效率降低，甚至系統(tǒng)阻塞，使得連續(xù)性和實(shí)時(shí)性變差。

在短波、有線干擾情況復(fù)雜的信道，在計(jì)算機(jī)網(wǎng)絡(luò)、分組交換網(wǎng)、衛(wèi)星通信、移動(dòng)通信中廣泛應(yīng)用。2021/6/2753、混合糾錯(cuò)(HEC)方式：前向糾錯(cuò)FEC+反饋重發(fā)ARQ

發(fā)送端發(fā)送的是兼有檢錯(cuò)和糾錯(cuò)能力的碼；接收端收到碼字后，首先檢測錯(cuò)誤情況。當(dāng)差錯(cuò)在碼的糾錯(cuò)能力范圍內(nèi)，就自動(dòng)糾錯(cuò)；當(dāng)差錯(cuò)很多已經(jīng)超出了糾錯(cuò)能力，但能夠檢測到錯(cuò)誤，接收端就通過反饋信道，請求重發(fā)。發(fā)送端接收端可檢錯(cuò)和糾錯(cuò)的碼HEC應(yīng)答信號檢錯(cuò)、糾錯(cuò)HEC的特點(diǎn)總體性能介于FEC和ARQ之間，誤碼率低，但需要反饋信道。實(shí)時(shí)性和連續(xù)性好。設(shè)備不太復(fù)雜，應(yīng)用廣泛。2021/6/2764、信息反饋(IRQ)方式(回程校驗(yàn)方式):

接收端收到信道傳輸來的碼后，全部由反饋信道發(fā)回發(fā)送端；發(fā)送端將發(fā)送的碼與反饋回的碼進(jìn)行比較，發(fā)現(xiàn)錯(cuò)誤后，把出錯(cuò)的碼再次重發(fā)，直到接收端認(rèn)為正確為止。發(fā)送端接收端消息（不編碼）IRQ消息不檢錯(cuò)、糾錯(cuò)IRQ特點(diǎn)：需要雙向控制，需要反饋信道。系統(tǒng)的控制設(shè)備和存儲(chǔ)設(shè)備相對復(fù)雜。無需編譯碼設(shè)備，接收端不具備檢、糾錯(cuò)能力強(qiáng)，整體系統(tǒng)糾錯(cuò)能力強(qiáng)，可大大降低整個(gè)系統(tǒng)誤碼率。具有自適應(yīng)性，但若重發(fā)頻繁，將使傳輸效率降低，甚至系統(tǒng)阻塞，使得連續(xù)性和實(shí)時(shí)性變差。2021/6/2775、檢錯(cuò)刪除：

接收端發(fā)現(xiàn)錯(cuò)碼后，立即將其刪除。適用在發(fā)送碼元中有大量多余度，刪除部分接收碼元不影響應(yīng)用之處。6、差錯(cuò)隱藏：在某些應(yīng)用領(lǐng)域，如音樂、語音、圖像、視頻等領(lǐng)域，有差錯(cuò)或損失的部分?jǐn)?shù)據(jù)對人的主觀感受影響不大，此時(shí)，可根據(jù)已接收的數(shù)據(jù)采用內(nèi)插或外推的技術(shù)，得到滿足應(yīng)用的輸出數(shù)據(jù)。2021/6/2789.2糾錯(cuò)碼分類1、糾錯(cuò)碼的分類：按糾正錯(cuò)誤的類型分類：糾隨機(jī)差錯(cuò)碼：無記憶信道中，噪聲隨機(jī)獨(dú)立地影響每個(gè)碼元，造成了隨機(jī)差錯(cuò)；糾突發(fā)差錯(cuò)碼：有記憶信道中，突發(fā)噪聲可造成突發(fā)性的成群差錯(cuò)（如太陽黑子、雷電等引起）。糾混合差錯(cuò)碼按應(yīng)用目的分類：檢錯(cuò)碼——只能檢測錯(cuò)誤是否存在。糾錯(cuò)碼——能夠檢測錯(cuò)誤，并能夠自動(dòng)糾正錯(cuò)誤。糾刪碼——能夠糾正刪除（丟失）了的信息。2021/6/279按碼元取值分類：二元糾錯(cuò)碼——目前最常用模式多元糾錯(cuò)碼按碼的結(jié)構(gòu)中對信息序列的處理方式分類：分組碼（n,k）——將信息序列每k位分組，再增加入r=n-k個(gè)冗余碼元（校驗(yàn)元），校驗(yàn)元只由本組k個(gè)信息元按照一定規(guī)律產(chǎn)生，與其他信息組無關(guān)。卷積碼（n,k0,L）——將信息序列每k0位分組，編碼器輸出該段的r=n-k0個(gè)與本組和前L組信息元相關(guān)的校驗(yàn)元，得到n長的碼字。2021/6/2710按碼的數(shù)學(xué)結(jié)構(gòu)中校驗(yàn)元與信息元關(guān)系分類：線性碼——線性關(guān)系，如線性方程組非線性碼——非線性關(guān)系按碼的是否具有循環(huán)性分類：循環(huán)碼——分組碼中任一碼字的碼元經(jīng)過循環(huán)移位后，仍是本碼中的碼字。非循環(huán)碼——至少有一個(gè)碼字經(jīng)循環(huán)移位后，不再是本碼中的碼字。按構(gòu)造碼的數(shù)學(xué)理論分類：代數(shù)碼——近世代數(shù)，比較完善，如線性分組碼。幾何碼——投影幾何學(xué)算術(shù)碼——數(shù)論，高等算術(shù)組合碼——排列組合，數(shù)論2021/6/2711

實(shí)際的碼可能同時(shí)分別具備以上某些特征，比如：某一糾錯(cuò)碼可以同時(shí)是線性碼、分組碼、循環(huán)碼、糾隨機(jī)差錯(cuò)碼、二元碼、代數(shù)碼等。2021/6/27129.3糾錯(cuò)碼的概念及其糾錯(cuò)能力信息序列碼字序列接收序列譯碼后信息序列噪聲源E錯(cuò)誤圖樣2021/6/2713

對編碼器的輸入信息序列，每k個(gè)信息符號分成信息組：

m=（mk-1,mk-2,…,m0），mi為信息元（i=0,1,…k-1）。（在q元數(shù)字通信系統(tǒng)中，共有種信息組。）碼字：

為了糾錯(cuò)，編碼器按一定規(guī)則增加產(chǎn)生r個(gè)多余符號，形成長度為n=k+r的序列：

C=(cn-1,cn-2,…,c0),ci為碼元（i=0,1,…n-1）

校驗(yàn)元：增加的r=n-k位碼元。

n：碼長；k：信息組長度；r：校驗(yàn)元的位長。1、信息元、校驗(yàn)元、碼字：2021/6/2714碼C中的碼字個(gè)數(shù)（k為信息位數(shù)）：（n,k）分組碼：編碼器輸出為個(gè)碼字組成的序列；許用碼字：種碼符號序列中，取出個(gè)作為分組碼的碼字。禁用碼字：其余種碼符號序列。卷積碼（n,k0,L）:編碼器輸出的校驗(yàn)元不僅由本組信息元有關(guān)，也與其前面若干段的信息組所確定。k個(gè)信息位r個(gè)監(jiān)督位an-1an-2...arar-1an-2...a0t碼長n=k+r分組碼的結(jié)構(gòu)2021/6/27152、碼字的漢明重量：漢明距離D(C1,C2)：對應(yīng)位置上不同碼元的個(gè)數(shù)。碼的最小距離：dmin,d(C)漢明重量（漢明勢）：碼字中非零碼元的個(gè)數(shù)W(C)。對2元碼，漢明重量為碼字中的“1”的個(gè)數(shù)。因此，二元碼字的漢明重量和漢明距離為：模2加，若對應(yīng)位不同則為1；相同則為0。其重量即為不相同的總位數(shù)，也就是兩個(gè)碼字的漢明距離。2021/6/27163、錯(cuò)誤圖樣：碼字序列通過信道傳輸送入譯碼器之前，由于信道的噪聲干擾，使得接收序列中某些碼元發(fā)生差錯(cuò)，可用錯(cuò)誤圖樣（差錯(cuò)圖樣）定量描述：

E=(en-1en-2…e1e0)=C－R

二元數(shù)字通信系統(tǒng)中，碼元傳輸錯(cuò)誤圖樣：

E=(en-1en-2…e1e0),ei={0,1},i=0,1,…,n-1

若ei=0，第i位碼元無差錯(cuò)；若ei=1，第i位碼元發(fā)生差錯(cuò)；

2021/6/2717差錯(cuò)關(guān)系：接收序列=許用碼字+錯(cuò)誤圖樣

R=(rn-1rn-2…r1r0),ri={0,1},i=0,1,…,n-1

接收序列長度=碼字長度=錯(cuò)誤圖樣長度=n差錯(cuò)類型：隨機(jī)差錯(cuò)是相互獨(dú)立的、不相關(guān)，存在這種差錯(cuò)的信道是無記憶信道或隨機(jī)信道；突發(fā)差錯(cuò)指成串出現(xiàn)的錯(cuò)誤,錯(cuò)誤與錯(cuò)誤間有相關(guān)性,一個(gè)差錯(cuò)往往要影響到后面一串碼元。2021/6/2718例

發(fā)送碼字C=010110111,接收序列R=001110011,錯(cuò)誤圖樣E=C+R=011000100

若為隨機(jī)差錯(cuò)，錯(cuò)誤碼元為：2，3，7，錯(cuò)誤數(shù)量=W(E)=3；若為突發(fā)差錯(cuò)，錯(cuò)誤碼元串長度為：6；出錯(cuò)范圍：從錯(cuò)誤圖樣E中的第一個(gè)1到最后一個(gè)1，其錯(cuò)誤串中的0表示該位碼元未發(fā)生錯(cuò)誤。

2021/6/2719BSC（二元無記憶對稱信道）的錯(cuò)誤圖樣的出現(xiàn)概率設(shè)p為錯(cuò)誤概率(<<1),則n次無記憶擴(kuò)展信道中，隨機(jī)差錯(cuò)的某錯(cuò)誤圖樣E的出現(xiàn)概率為：

0位差錯(cuò)（全對）：W(E0)=0，1位隨機(jī)差錯(cuò)：W(E1)=1,2位隨機(jī)差錯(cuò)：W(E2)=2,……e位隨機(jī)差錯(cuò)：W(Ee)=e,……n位差錯(cuò)（全錯(cuò)）W(En)=n,差錯(cuò)圖樣數(shù)概率2021/6/2720錯(cuò)誤圖樣的總數(shù)：

發(fā)生多位錯(cuò)誤的概率小于較少位數(shù)隨機(jī)錯(cuò)誤的概率。因此，無記憶信道中，一般優(yōu)先糾正較少位數(shù)的隨機(jī)錯(cuò)誤，如1-2位，此時(shí)的誤碼率就可下降幾個(gè)數(shù)量級。錯(cuò)誤圖樣出現(xiàn)的概率關(guān)系（p<<1）：2021/6/27214、分組碼的糾錯(cuò)能力與碼最小距離的關(guān)系

一般地，分組碼的碼間最小距離dmin越大，意味著任意碼字間的差別越大，則碼的檢、糾錯(cuò)能力越強(qiáng)。檢錯(cuò)能力：如果一個(gè)分組碼能檢出總位數(shù)≤e個(gè)碼元的任何錯(cuò)誤圖樣，稱碼的檢錯(cuò)能力為e。糾錯(cuò)能力：如果分組碼能糾正總位數(shù)≤t個(gè)碼元的任意錯(cuò)誤圖樣，稱碼的糾錯(cuò)能力為t。2021/6/2722例重復(fù)碼（3，1）為：（000，111），最小碼間距為3。兩個(gè)碼字在傳輸后發(fā)生1位錯(cuò)誤的接收序列形成兩個(gè)互不相交的子集，按照最小距離譯碼準(zhǔn)則，就能糾正1位隨機(jī)錯(cuò)誤。若發(fā)生2-3位錯(cuò)誤，則接收序列進(jìn)入另一個(gè)子集內(nèi)，無法糾正。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a12021/6/2723定理：對于一個(gè)（n,k）分組碼C，最小距離為dmin，則：⑴若能檢測（發(fā)現(xiàn)）e個(gè)隨機(jī)錯(cuò)誤，則要求dmin≥e+1;

或：可檢測出任意小于等于e=dmin－1個(gè)隨機(jī)差錯(cuò)；

⑵若能糾正t個(gè)隨機(jī)錯(cuò)誤，則要求dmin≥2t+1;

或：可糾正任意小于等于t=INT[(dmin-1)/2]個(gè)隨機(jī)差錯(cuò)；

⑶若能糾正t個(gè)隨機(jī)錯(cuò)誤，同時(shí)能檢測e≥t個(gè)隨機(jī)錯(cuò)誤，則要求：dmin≥t+e+1。2021/6/2724

設(shè)V,U為距離最小的兩個(gè)許用碼字。若某碼字傳輸發(fā)生錯(cuò)誤，按最小距離準(zhǔn)則譯碼，為了檢測R=U+E：須dmin≥e+1，否則，會(huì)發(fā)生碼字譯碼混淆，如R+E=V。eVUdmin

dmin=4,碼距和檢錯(cuò)能力關(guān)系示意圖2021/6/2725tVUdmin圖

dmin=5,碼距和糾錯(cuò)能力關(guān)系示意圖

設(shè)V,U為距離最小的兩個(gè)許用碼字。若某碼字傳輸發(fā)生錯(cuò)誤，按最小距離準(zhǔn)則譯碼.

若R=V+E，W（E）=t，則若dmin<2t+1,則可能譯碼為U。錯(cuò)誤！

當(dāng)dmin≥2t+1，D（R，V）<D（R，U）譯碼為V。正確！2021/6/2726

設(shè)V,U為距離最小的兩個(gè)許用碼字。自接收序列中碼字分別發(fā)生t位錯(cuò)誤和e位錯(cuò)誤，要檢錯(cuò)、糾錯(cuò)，需要使得大球和小球不相交。故：須dmin≥e+t+1，否則，譯碼時(shí)引起碼字譯碼混淆。edmin圖

dmin=5,t=1,e=3碼距和糾檢錯(cuò)能力關(guān)系示意圖tVUet2021/6/27275、分組碼的碼率二元無記憶信道中，（n，k）分組碼個(gè)數(shù)為：也就是說，信道輸入的消息數(shù)目為M。信道輸入的信息流可以認(rèn)為是去除了信源剩余度的的無記憶等概分布的信息流，則信道信息傳輸率（碼率）：表示了信息位在分組碼碼字中所占比重，反映了每個(gè)碼元符號攜帶的信息量。是衡量其有效性的重要參數(shù)。2021/6/27289.4線性分組碼概念：

分組碼中的信息元和校驗(yàn)元是用線性方程聯(lián)系起來的一類差錯(cuò)控制碼。線性分組碼的編碼過程：把信息序列按一定長度分成若干長度為k位的信息碼組；編碼器按照預(yù)定的線性規(guī)則(可由線性方程組規(guī)定)，把信息碼組變換成n長(n>k)碼字，其中(n－k)個(gè)附加碼元是由信息碼元的線性運(yùn)算產(chǎn)生的。對于二元碼，信息碼組長k位，有2k個(gè)不同的信息碼組，則有2k個(gè)碼字與它們一一對應(yīng)。2021/6/27292、一致監(jiān)督（校驗(yàn)）方程編碼方法：已知信息碼組k位信息位，按預(yù)定規(guī)則生成r個(gè)監(jiān)督（校驗(yàn)）碼元，與信息位一起構(gòu)成碼字。要求：每個(gè)監(jiān)督元是其中某些信息元的運(yùn)算結(jié)果。（以下僅討論二元碼）例：k=3,r=4，構(gòu)成(7,3)線性分組碼。設(shè)碼字為(C6,C5,C4,C3,C2,C1,C0)其中，C6,C5,C4為信息元，C3,C2,C1,C0為監(jiān)督元，碼元取0或1。監(jiān)督元可按下面方程組計(jì)算2021/6/2730一致監(jiān)督（校驗(yàn)）方程

由確定信息元得到監(jiān)督元規(guī)則的一組方程。由于所有碼字都按同一規(guī)則確定，又稱為一致監(jiān)督（校驗(yàn)）方程。線性分組碼

若一致監(jiān)督方程是線性的，監(jiān)督元和信息元之間是線性運(yùn)算關(guān)系，所以由監(jiān)督方程所確定的分組碼是線性分組碼。前例2021/6/27313、一致監(jiān)督（校驗(yàn)）矩陣為了運(yùn)算方便，可將監(jiān)督方程寫成矩陣形式。前例：2021/6/2732推廣：一般情況，對(n,k)線性分組碼，每個(gè)碼字中的r(r=n－k)個(gè)監(jiān)督元與信息元之間的關(guān)系可由如下r*n階線性方程組確定：則：令：2021/6/2733若用hi(i=n-1,n-2,…,1,0)表示H矩陣中的列矢量，則H可寫為：H矩陣的每一行元素是線性方程組中一個(gè)方程的系數(shù)，由它來唯一確定每一個(gè)校驗(yàn)元。因此，H中每一行必須是線性無關(guān)的，且必定有：r=n－k

行。2021/6/27344、生成矩陣

根據(jù)（n,k）線性分組碼的一致監(jiān)督方程出發(fā)，將信息組信息位與生成的碼字之間的生成關(guān)系用矩陣來表示，就可得到生成矩陣。例前例中，2021/6/2735生成矩陣G1其各行為碼字，互不相關(guān)。其他碼字為此三個(gè)碼字的線性組合方式生成。2021/6/2736推廣：對一般(n,k)線性分組碼，設(shè)有一組k個(gè)線性獨(dú)立的碼字，由此一組線性獨(dú)立的碼字以行向量構(gòu)成的矩陣，稱為線性分組碼的生成矩陣G（k*n階）：滿足：2021/6/2737G中每一行及其線性組合都是許用碼字，故有：

線性分組碼的所有碼字都可由其生成矩陣或一致校驗(yàn)矩陣求得。當(dāng)已知G、H中的一個(gè)，就可求另一個(gè)。系統(tǒng)碼：信息元以不變形式出現(xiàn)在碼字的任意k位上。標(biāo)準(zhǔn)生成矩陣：生成矩陣能把信息元保留在各碼字的最左邊k位上。2021/6/2738

因此，標(biāo)準(zhǔn)系統(tǒng)生成矩陣G應(yīng)滿足如下形式：其與H矩陣之間的轉(zhuǎn)換關(guān)系：若非標(biāo)準(zhǔn)系統(tǒng)碼，則G與H之間元素需要由方程組確定。2021/6/2739(略)生成矩陣之間的關(guān)系對于二元（n,k）分組碼，在2k個(gè)碼字中，k個(gè)獨(dú)立碼字組不止一個(gè)。對于同一碼，選擇不同的獨(dú)立碼字組構(gòu)成生成矩陣G也不相同。但經(jīng)過若干次初等變換，可變成等價(jià)的標(biāo)準(zhǔn)生成矩陣。例一個(gè)二元（7，3）碼,生成矩陣為：生成的碼字為：2021/6/2740碼字集合完全相同。但生成矩陣G1、G2選取了不同的獨(dú)立碼字構(gòu)成。生成矩陣可以經(jīng)過初等行變換得到其標(biāo)準(zhǔn)生成矩陣。比較：生成矩陣G2產(chǎn)生的碼（非系統(tǒng)碼）比較：生成矩陣G1產(chǎn)生的碼（系統(tǒng)碼）2021/6/27412行+3行==〉2行1行+2行==〉3行標(biāo)準(zhǔn)生成矩陣2021/6/27425、線性分組碼性質(zhì)與糾錯(cuò)能力1）（n,k）線性分組碼由生成矩陣G或校驗(yàn)矩陣H確定。它們滿足：2）封閉性。（n,k）碼中任意兩個(gè)碼字之和仍為許用碼字，即：2021/6/27433）含有零碼字。

n位長的零矢量為（n,k）線性分組碼的許用碼字。（因?yàn)闈M足）4）所有許用碼字可由其中k個(gè)獨(dú)立碼字（基底）線性組合而成。在個(gè)許用碼字中，k個(gè)獨(dú)立許用碼字不止一組。它們可構(gòu)成生成矩陣G。5）碼的最小距離等于非零碼字的最小重量。即：因?yàn)椋?021/6/2744定理設(shè)（n,k）線性分組碼C的校驗(yàn)矩陣為H，則碼的最小距離為d的充要條件為：H中任意d-1個(gè)列向量線性無關(guān)，且有d個(gè)列向量線性相關(guān)。（提供了構(gòu)造最小距離為d的線性分組碼的思路。）任何3列相加均非0，而最少的相關(guān)列數(shù)為4：如：從右向左第0，1，2，5之和為0，相關(guān)。故，碼最小距離為：4由此可知：當(dāng)所有列向量相同，而排列位置不同的H矩陣所對應(yīng)的分組碼，具有相同的最小距離，則它們在糾錯(cuò)能力和碼率上等價(jià)。對于分組碼來說，由于可以進(jìn)行初等變換進(jìn)行等價(jià)變換，系統(tǒng)碼和非系統(tǒng)碼的糾錯(cuò)能力是相同的，而系統(tǒng)碼的編譯碼比非系統(tǒng)碼簡單，且G、H矩陣可方便互求，因此，一般只需討論系統(tǒng)碼。例2021/6/27456、線性分組碼的糾錯(cuò)與伴隨式：①接收到一個(gè)序列R后，校驗(yàn)H

RT=0T

是否成立：若關(guān)系成立，則認(rèn)為R是一個(gè)碼字；否則判為碼字在傳輸中發(fā)生了錯(cuò)誤；②伴隨式（/監(jiān)督子/校驗(yàn)子）：

S=R

HT

或

ST=H

RT③如何糾錯(cuò)？設(shè)發(fā)送碼矢C=(cn－1,cn－2,…,c0)信道錯(cuò)誤圖樣為E=(en－1,en－2,…,e0)，其中ei=0，表示第i位無錯(cuò)；ei=1，表示第i位有錯(cuò)。

i=n－1,n－2,…,0。2021/6/2746接收序列R：R=(rn－1,rn－2,…,r0)=C+E=(cn－1+en－1,cn－2+en－2,…,c0+e0)接收序列的伴隨式（接收字用監(jiān)督矩陣進(jìn)行檢驗(yàn)）

ST=H

RT=H

(C+E)T=H

CT+H

ET

由于H

CT=0T，所以

ST=H

ET

或

S=E

HT即：分析：2021/6/2747對于2元碼，ei=[0，1]，伴隨式是H矩陣中對應(yīng)若干列向量之和。（1位錯(cuò)，多位錯(cuò)）例：已知(7,3)碼的一致校驗(yàn)矩陣。①設(shè)發(fā)送碼矢C=1010011。若傳輸時(shí)沒有差錯(cuò)，E0=（0000000），則接收碼字R＝1010011=C，R與C相同：

S0=E0

HT=

（0000）沒有錯(cuò)誤；

若傳輸時(shí)差錯(cuò)圖樣為E00=C=1010011，則R＝0000000，S00=E00

HT=

（0000），無法發(fā)現(xiàn)此錯(cuò)誤；2021/6/2748②若發(fā)送碼矢C1=0100111，C2=1101001，錯(cuò)誤圖樣E1=（1000000），接收碼字R1＝1100111，R2＝0101001；伴隨式

S1=R1

HT=E1

HT

=

（1110），

S2=R2

HT=E2

HT

=

（1110），可見：S1=S2≠0；不為0，譯碼器判斷有錯(cuò)誤；第1位錯(cuò)誤，剛好對應(yīng)于H矩陣的第1列向量；伴隨式與發(fā)送碼字無關(guān)，只與錯(cuò)誤圖樣有關(guān)。2021/6/2749

當(dāng)錯(cuò)誤圖樣E3=（0010000），可得：S3=E3

HT=（1101），剛好為H矩陣的第3列向量。依此類推：當(dāng)發(fā)生1位錯(cuò)誤時(shí)，當(dāng)i位錯(cuò)誤發(fā)生在第i位，其伴隨式正好是H矩陣中的第i列向量。③若傳送時(shí)發(fā)送2位碼元錯(cuò)誤，設(shè)E=（1010000）=E1+E3

，伴隨式S

=E

HT=（E1+E3）

HT=

E1

HT+E3

HT=

（0011），

可見：

S不同于H中的任何一列，說明發(fā)生了不止一位錯(cuò)誤；可能是第1、第3位錯(cuò)誤；但若錯(cuò)誤圖樣E=（0100100）或（0000011），其伴隨式仍為（0011），譯碼器無法判斷錯(cuò)誤的位置，故無法糾正2位的隨機(jī)差錯(cuò)。2021/6/2750④若錯(cuò)誤圖樣E=（0110100），可得：S=EHT=（1110）=S1

，剛好為H矩陣的第1列向量。由此：此（7，3）碼可發(fā)現(xiàn)3位隨機(jī)錯(cuò)誤，但當(dāng)發(fā)生1位錯(cuò)誤時(shí)，無法糾正；或者相反。H矩陣：任意小于等于3列線性無關(guān)，而最少4列就線性相關(guān)，故其最小碼距dmin=4,故可糾正1位錯(cuò)誤的同時(shí)檢測出2位錯(cuò)誤，或檢測3位錯(cuò)誤。2021/6/2751本章習(xí)題

9-1

9-3

9-4

2021/6/27527、標(biāo)準(zhǔn)陣列譯碼傳輸中錯(cuò)誤圖樣E不同時(shí)，有可能對應(yīng)相同的伴隨式。當(dāng)信道譯碼器接收到接收序列R后，由下式求解E：

S

=R

HT=

E

HT

但是，此式中對應(yīng)的錯(cuò)誤圖樣可以有2k個(gè)解。一般采用最大似然準(zhǔn)則譯碼（輸入碼元等概分布），其譯碼錯(cuò)誤概率最小，正確譯碼概率最大。在BSC信道中，重量最小的E*，其發(fā)生的概率最大，則：P(C+E*|C)=P(E*)>P(C+E|C),E≠E*

因此，用伴隨式譯碼時(shí)就采用最大似然準(zhǔn)則（最小距離譯碼準(zhǔn)則），選取重量最輕的E作為譯碼的錯(cuò)誤圖樣。2021/6/2753

實(shí)際譯碼中，根據(jù)

R

HT=

S

=E

HT找出重量最輕的E的譯碼方法及其繁瑣。一般采用標(biāo)準(zhǔn)陣列譯碼方法。標(biāo)準(zhǔn)陣列譯碼方法：發(fā)送碼字：取自由2k個(gè)碼字構(gòu)成的集合{C}；接收序列：可以是2n個(gè)n長序列中任一個(gè)矢量；把2n個(gè)n長序列劃分為2k個(gè)互不相交的子集，并按照最大似然譯碼準(zhǔn)則，使得在每個(gè)子集對應(yīng)一個(gè)許用碼字；根據(jù)碼字和子集間一一對應(yīng)關(guān)系，若接收矢量R落在子集Dl中，就把Rl譯為子集Dl對應(yīng)的碼字Cl。因此當(dāng)接收序列R與實(shí)際發(fā)送碼字在同一子集中時(shí)，譯碼就是正確的。2021/6/2754標(biāo)準(zhǔn)陣列表的構(gòu)造：先將2k個(gè)許用碼字排成一行，作為標(biāo)準(zhǔn)陣列的第一行，并將全0碼矢C0=(00…0)放在最左面的位置上；然后在剩下的(2n－2k)

個(gè)n長序列中選取一個(gè)重量最輕的重E1放在全0碼矢C0下面，即第2行首位；再將E1分別和所有許用碼字相加：Ci+E1，放在對應(yīng)碼字下構(gòu)成陣列第二行；在第二次剩下的n長序列中，選取重量最輕的n重E2，放在E1下面，并將E2分別加到第一行各許用碼字上Ci+E2

，得到第三行；…，繼續(xù)這樣做下去，直到全部n重用完為止。得到(n,k)線性碼的標(biāo)準(zhǔn)陣列。2021/6/2755標(biāo)準(zhǔn)陣列表結(jié)構(gòu)伴隨式陪集首（表中每一行稱為陪集）2021/6/2756標(biāo)準(zhǔn)陣列表的特點(diǎn)：表中每一行稱為陪集，該行的首位元素Ei在為陪集首，各行元素都不同；如果把錯(cuò)誤圖樣作為陪集首，則同一個(gè)陪集中所有的元素都隊(duì)?wèi)?yīng)相同的伴隨式；表中各列以同一組許用碼字為基礎(chǔ)，將2n個(gè)接收序列劃分成不相交的子集合D0,D1,D2,…,D2k-1.每個(gè)子集合Dj對應(yīng)同一個(gè)許用碼字Cj，它是每列子集的子集首。2021/6/2757標(biāo)準(zhǔn)陣列的譯碼：列子集Dj各元素是同一許用碼字Cj在信道中發(fā)生若干錯(cuò)誤得到。同列中各元素對應(yīng)的是不同的錯(cuò)誤圖樣。而列子集Dj各元素是與許用碼字Cj距離最近的，與許用碼字的距離等于錯(cuò)誤圖樣Ej在的重量W(Ej).由建表過程中，選取的陪集首都是重量為最輕的錯(cuò)誤圖樣，所以，這樣的列子集Dj的劃分是滿足最大似然準(zhǔn)則的（最小距離準(zhǔn)則）.2021/6/2758標(biāo)準(zhǔn)陣列的譯碼方式：方式1：在表中查詢接收序列R，并把R所在列的子集首Cj作為R的譯碼。方式2：先求出伴隨式S,找出S所在的行中的R，以R所在列的子集首Cj作為R的譯碼。表較大時(shí)，兩種方式的搜索時(shí)間差別也較大。2021/6/2759例

設(shè)（5，2）系統(tǒng)線性碼的生成矩陣為構(gòu)造該碼的標(biāo)準(zhǔn)陣列譯碼表。信息組為（00）（01）（10）（11），由C=mG

可求出相應(yīng)碼字。同時(shí)，可得到校驗(yàn)矩陣（用于計(jì)算伴隨式）：伴隨式個(gè)數(shù)：(2n－2k)=8，標(biāo)準(zhǔn)陣列表應(yīng)有8行。按照重量選擇錯(cuò)誤圖樣，并計(jì)算其對應(yīng)伴隨式，填入表中。2021/6/2760重量為2的錯(cuò)誤圖樣的選擇：1、根據(jù)前面6行填滿后，選擇未出現(xiàn)的重量為2的二元序列；2、根據(jù)尚未出現(xiàn)的伴隨式，計(jì)算出對應(yīng)的錯(cuò)誤圖樣，并選用之。2021/6/2761若接收序列R=（10101）,可采用兩種譯碼方式：1、搜索全部碼表，在（5，2）位置，查詢到R，則其所在列子集首為碼字C1,則將此R譯碼為C1=10111；2、根據(jù)尚未出現(xiàn)的伴隨式，計(jì)算出對應(yīng)的錯(cuò)誤圖樣。

RHT=S=010=S4在S4所在行查找R，則其所在列子集首為碼字C1,則將此R譯碼為C1=10111。由陣列譯碼表知，此（5，2）碼能夠糾正所有的1位錯(cuò)誤，以及兩個(gè)2位發(fā)生圖樣。2021/6/2762簡化譯碼表：問題：利用標(biāo)準(zhǔn)陣列譯碼，需要將標(biāo)準(zhǔn)陣列的2n個(gè)接收序列R存入存儲(chǔ)器，譯碼器復(fù)雜度隨著n增大而成指數(shù)增大，限制了其適用性。簡化譯碼表：只構(gòu)造表的第0、第1列：即Si與Ei對照表，譯碼器只需要存儲(chǔ)2n-k個(gè)長度為（n-k）的向量Si與2n-k個(gè)長度為n的錯(cuò)誤圖樣Ei。大大減少了存儲(chǔ)量，簡化了譯碼器。譯碼方式：先由R計(jì)算伴隨式S=RHT,然后在簡化表中查找出S對應(yīng)的錯(cuò)誤圖樣E，最后計(jì)算：C=R+E，C作為譯碼輸出。2021/6/2763建立譯碼表的注意點(diǎn)：在構(gòu)造譯碼表時(shí)，當(dāng)不等式（r為錯(cuò)誤圖樣重量）成立時(shí)，在第1列中順序存入重量為0，1，2，…，r的錯(cuò)誤圖樣Ei,由EHT=S求出S，放入表的第0列。當(dāng)?shù)?列剩余位置少于個(gè)時(shí)，才需要由S解方程EHT=S,求出E，從中挑選重量為（r+1）的錯(cuò)誤圖樣填入第一列剩余位置。2021/6/2764線性碼可糾正的錯(cuò)誤圖樣若發(fā)送碼矢為Cj，信道干擾的錯(cuò)誤圖樣是陪集首，則接收矢量R必在Dj中；若錯(cuò)誤圖樣不是陪集首，則接收矢量R不在Dj中，則譯成其它碼字，造成錯(cuò)誤譯碼；當(dāng)且僅當(dāng)錯(cuò)誤圖樣為陪集首時(shí)，譯碼才是正確的?？杉m正的錯(cuò)誤圖樣：這2n－k個(gè)陪