第7章_信道編碼

1、 通過(guò)本章的學(xué)習(xí)，熟悉信道編碼的概念，了解信道編碼的目的及意義；掌握差錯(cuò)控制編碼的基本原理，熟悉差錯(cuò)控制的工作方式及幾種常用的差錯(cuò)控制編碼，了解其性能優(yōu)劣；熟悉碼距、碼重對(duì)編碼器檢糾錯(cuò)能力的影響；掌握如何利用線(xiàn)性分組碼實(shí)現(xiàn)糾檢錯(cuò)，熟悉生成矩陣和監(jiān)督矩陣的概念，了解漢明碼的基本構(gòu)成；理解循環(huán)碼的概念，掌握其編解碼過(guò)程及如何用電路實(shí)現(xiàn)循環(huán)碼的編解碼；了解卷積碼的概念及其代數(shù)表示方式。第7章 信 道 編 碼教學(xué)目標(biāo)7.1 信道編碼的基本概念7.1.1 差錯(cuò)控制編碼基本方式和類(lèi)型1. 常用差錯(cuò)控制工作方式差錯(cuò)主要產(chǎn)生于信道。按錯(cuò)碼分布的規(guī)律，信道分為：隨機(jī)信道(random channel)：隨機(jī)出現(xiàn)

2、，統(tǒng)計(jì)獨(dú)立突發(fā)信道(burst channel)：成串集中出現(xiàn)混合信道(mixed channel)：隨機(jī)錯(cuò)碼+突發(fā)錯(cuò)碼 恒參高斯白噪聲信道是典型的隨機(jī)信道，差錯(cuò)的出現(xiàn)是隨機(jī)的，而且是統(tǒng)計(jì)獨(dú)立的。具有脈沖干擾的信道是典型的突發(fā)信道，錯(cuò)誤是成串成群出現(xiàn)的，即在短時(shí)間內(nèi)出現(xiàn)大量錯(cuò)誤。短波信道和對(duì)流層散射信道是混合信道的典型例子，隨機(jī)錯(cuò)誤和成串錯(cuò)誤都占有相當(dāng)比例。對(duì)于不同類(lèi)型的信道，應(yīng)采用不同的差錯(cuò)控制方式。清華大學(xué)出版社第7章 信道編碼差錯(cuò)控制的工作方式（技術(shù)類(lèi)型）前向糾錯(cuò)FEC：Forward Error Correction檢錯(cuò)重發(fā)ARQ：Automatic Repeat reQuest信息反

3、饋IF：Information Feedback混合糾錯(cuò)HEC：Hybrid Error Correction FEC：發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼，收端收到信碼后自動(dòng)地糾正傳輸中的錯(cuò)誤。其特點(diǎn)是單向傳輸，實(shí)時(shí)性好，但譯碼設(shè)備較復(fù)雜。 IF：收端把收到的消息原封不動(dòng)地送回發(fā)端，發(fā)端把反饋回來(lái)的信息與原發(fā)送信息進(jìn)行比較，并把二者不一致的部分重發(fā)到收端。 清華大學(xué)出版社第7章 信道編碼圖7.1 差錯(cuò)控制工作方式發(fā)端收端發(fā)端收端發(fā)端收端發(fā)端收端前向糾錯(cuò)FEC檢錯(cuò)重發(fā)ARQ信息反饋IF混合糾錯(cuò)HEC糾錯(cuò)碼檢錯(cuò)碼判決信號(hào)信息信號(hào)信息信號(hào)檢錯(cuò)和糾錯(cuò)碼判決信號(hào)清華大學(xué)出版社第7章 信道編碼 混合糾錯(cuò)方式記作HE

4、C（Hybrid Error Correction）是FEC和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動(dòng)糾錯(cuò)同時(shí)又具有檢錯(cuò)能力的碼。收端收到碼后，檢查差錯(cuò)情況，如果錯(cuò)誤在碼的糾錯(cuò)能力范圍以?xún)?nèi)，則自動(dòng)糾錯(cuò)，如果超過(guò)了碼的糾錯(cuò)能力， 但能檢測(cè)出來(lái)，則經(jīng)過(guò)反饋信道請(qǐng)求發(fā)端重發(fā)。這種方式具有自動(dòng)糾錯(cuò)和檢錯(cuò)重發(fā)的優(yōu)點(diǎn)，可達(dá)到較低的誤碼率，因此， 近年來(lái)得到廣泛應(yīng)用。清華大學(xué)出版社第7章 信道編碼糾錯(cuò)的基本思想 信道編碼是使不帶規(guī)律性或規(guī)律性不強(qiáng)的原始數(shù)字信號(hào)變?yōu)閹弦?guī)律性或加強(qiáng)了規(guī)律性的數(shù)字信號(hào)，信道譯碼器則利用這些規(guī)律性來(lái)鑒別是否發(fā)生錯(cuò)誤，或進(jìn)行糾正錯(cuò)誤。 差錯(cuò)控制編碼是在信息序列上附加上一些監(jiān)督碼元，利用這

5、些冗余的碼元，使原來(lái)不規(guī)律的或規(guī)律性不強(qiáng)的原始數(shù)字信號(hào)變?yōu)橛幸?guī)律的數(shù)字信號(hào)；差錯(cuò)控制譯碼則利用這些規(guī)律性來(lái)鑒別傳輸過(guò)程是否發(fā)生錯(cuò)誤，進(jìn)而糾正錯(cuò)誤。清華大學(xué)出版社第七章 信道編碼 差錯(cuò)控制編碼常稱(chēng)為糾錯(cuò)編碼。不同的編碼方式有不同的檢錯(cuò)或糾錯(cuò)能力。有的編碼方法只能檢錯(cuò)，不能糾錯(cuò)。一般來(lái)說(shuō)，付出的代價(jià)越大，檢糾錯(cuò)的能力就越強(qiáng)。這里所指的代價(jià)，就是指增加的監(jiān)督碼元位數(shù)，它通常用冗余度或多余度來(lái)衡量。設(shè)編碼序列中信息碼元位數(shù)為k，監(jiān)督碼元位數(shù)為r，碼字位數(shù)為n=k+r，則比值k/n稱(chēng)為編碼效率，簡(jiǎn)稱(chēng)碼率又稱(chēng)編碼速率，比值r/k稱(chēng)為冗余度，比值r/n 稱(chēng)為多余度。 對(duì)糾錯(cuò)碼的基本要求是： 糾錯(cuò)和檢錯(cuò)能力盡

6、量強(qiáng)； 編碼效率盡量高； 碼長(zhǎng)盡量短； 編碼規(guī)律盡量簡(jiǎn)單。2. 差錯(cuò)控制編碼分類(lèi)(1)根據(jù)信息碼元與監(jiān)督碼元之間的函數(shù)關(guān)系分線(xiàn)性碼：線(xiàn)性關(guān)系非線(xiàn)性碼：非線(xiàn)性關(guān)系(2)根據(jù)上述關(guān)系涉及的范圍分分組碼：本組中監(jiān)督碼元只與本碼組中的信息碼元有關(guān)卷積碼：監(jiān)督碼元與本碼組及前(N-1)個(gè)碼組的信息碼元有關(guān)(3)根據(jù)碼的用途分檢錯(cuò)碼：以檢錯(cuò)為目的，不一定能糾錯(cuò)糾錯(cuò)碼：以糾錯(cuò)為目的，一定能糾錯(cuò)清華大學(xué)出版社第7章 信道編碼 (5)按照糾正錯(cuò)誤的類(lèi)型不同，可以將它分為糾正隨機(jī)錯(cuò)誤碼和糾正突發(fā)錯(cuò)誤碼。 (6)按照信道編碼所采用的數(shù)學(xué)方法不同，可以將它分為代數(shù)碼、幾何碼和算術(shù)碼。 隨著數(shù)字通信系統(tǒng)的發(fā)展，可以將信

7、道編碼器和調(diào)制器統(tǒng)一起來(lái)綜合設(shè)計(jì)，這就是所謂的網(wǎng)格編碼調(diào)制(TCM)。(4)根據(jù)碼組中信息碼元是否隱蔽分系統(tǒng)碼：編碼后的信息碼元保持不變非系統(tǒng)碼：編碼后的信息碼元與編碼前的信息碼元不同清華大學(xué)出版社第七章 信道編碼7.1.2 碼重、碼距與檢錯(cuò)、糾錯(cuò)能力 差錯(cuò)控制編碼的基本思想：在被傳輸?shù)男畔⒋a元中增加一些監(jiān)督碼元，在兩者之間建立某種校驗(yàn)關(guān)系，呈現(xiàn)某種關(guān)聯(lián)性。當(dāng)這種校驗(yàn)關(guān)系因傳輸錯(cuò)誤而受到破壞時(shí)，可以被發(fā)現(xiàn)并予以糾正。這種檢錯(cuò)和糾錯(cuò)能力是用信息量的冗余度來(lái)?yè)Q取的。碼長(zhǎng)：碼組(碼字或碼矢)中碼元的數(shù)目即碼組的長(zhǎng)度。碼重：碼組中非0位的數(shù)目稱(chēng)為碼組的重量，簡(jiǎn)稱(chēng)碼重。例如，碼組11010，碼長(zhǎng)n=5，

8、碼重W=3。 碼距：兩個(gè)等長(zhǎng)碼組之間對(duì)應(yīng)位不同的數(shù)目稱(chēng)為這兩個(gè)碼組的的漢明距離，簡(jiǎn)稱(chēng)碼距。例如，碼組11000和10011之間的距離d=3。1min ed12min td1minetd清華大學(xué)出版社第七章 信道編碼 一種編碼的最小碼距的大小直接關(guān)系著這種編碼的檢錯(cuò)和糾錯(cuò)能力： (1) 為檢測(cè)e個(gè)錯(cuò)碼，要求最小碼距為(7-1)(2) 為了糾正t個(gè)錯(cuò)碼，要求最小碼距為(7-2)(3)為了糾正t個(gè)錯(cuò)碼同時(shí)檢測(cè)e個(gè)錯(cuò)碼，要求最小碼距為(7-3)最小碼距dmin：碼組集中任意2個(gè)碼字之間距離的最小值。它是糾錯(cuò)碼的一個(gè)重要參數(shù)，是衡量一種編碼檢錯(cuò)糾錯(cuò)能力的依據(jù)。清華大學(xué)出版社第7章 信道編碼【例】已知碼組

9、集中8個(gè)碼組為000000；001110；010101；011011；100011；101101；110110；111000。若用于檢錯(cuò)，能檢出幾位錯(cuò)誤？若用于糾錯(cuò)，能糾正幾位錯(cuò)誤？若同時(shí)用于檢錯(cuò)和糾錯(cuò)，檢糾錯(cuò)性能如何？解：最小碼距dmin=3。(1)僅用于檢錯(cuò)，由 得 ，故能檢出2位錯(cuò)誤。 1min ed2e(2)僅用于糾錯(cuò)，由 得 ，故能糾正1位錯(cuò)誤。 12min td1t(3)若同時(shí)用于檢錯(cuò)和糾錯(cuò)，由 得不到同時(shí)滿(mǎn)足要求的e和t ，故該碼組集不能同時(shí)用于檢錯(cuò)和糾錯(cuò)。 teted1min清華大學(xué)出版社第7章 信道編碼【例】一碼長(zhǎng)n=15的漢明碼，監(jiān)督位r應(yīng)為多少？編碼效率R=? 解：漢明碼

10、是一種能糾正單個(gè)錯(cuò)誤的完備碼。糾錯(cuò)能力t=1，故最小碼距dmin=3。 完備碼若 ，則稱(chēng)此(n，k)碼為能糾正t個(gè)錯(cuò)誤的完備碼。tiinknC02 漢明碼)12 , 12(rrr碼長(zhǎng)：n=2r-1信息位數(shù)：k=2r-1-r監(jiān)督位數(shù)：r=n-k故編碼效率為121rrnkR此題中1512rnr = 4故1511nrnnkR清華大學(xué)出版社第七章 信道編碼7.1.3 幾種常用的差錯(cuò)控制碼1. 奇偶監(jiān)督碼 在n-1個(gè)信息元后面附加一個(gè)監(jiān)督元，使得長(zhǎng)n的碼字中1的個(gè)數(shù)保持為奇數(shù)或偶數(shù)的碼稱(chēng)為奇偶監(jiān)督碼。序號(hào) 碼 字序號(hào) 碼 字信息碼元 監(jiān) 督 元信息碼元 監(jiān) 督 元 00 0 0 0 0 810001 1

11、0 0 0 11 91 0 0 10 20 0 1 01101 0 1 00 30 0 1 10111 0 1 11 40 1 0 01121 1 0 00 50 1 0 11131 1 0 11 60 1 1 00141 1 1 01 70 1 1 11151 1 1 10碼長(zhǎng)為5的偶監(jiān)督碼清華大學(xué)出版社第7章 信道編碼設(shè)碼字A=an-1,an-2,a1,a0，對(duì)偶監(jiān)督碼有 00121aaaann 奇監(jiān)督碼情況相似， 只是碼組中“1”的數(shù)目為奇數(shù)， 即滿(mǎn)足條件 1021aaann而檢錯(cuò)能力與偶監(jiān)督碼相同。 奇偶監(jiān)督碼的編碼效率R為 nnR/ ) 1( 清華大學(xué)出版社第7章 信道編碼a4a3a

12、2a1a0a4a3a2a1信息組編碼輸出b0b4b3b2b1接收碼組檢錯(cuò)信號(hào)SBAM 奇偶監(jiān)督碼的編碼可以用軟件實(shí)現(xiàn)，也可用硬件電路實(shí)現(xiàn)。 如果碼組B無(wú)錯(cuò)，BA，則M0；如果碼組B有單個(gè)（或奇數(shù)個(gè)）錯(cuò)誤，則M1。2. 行列(二維)奇偶監(jiān)督碼 奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤。為了改善這種情況，引入行列奇偶監(jiān)督碼，又稱(chēng)二維奇偶監(jiān)督碼。這種編碼不僅對(duì)水平方向的碼元，而且對(duì)垂直方向的碼元實(shí)施監(jiān)督。行列奇偶監(jiān)督碼先把上述奇偶監(jiān)督碼的若干碼組，每個(gè)寫(xiě)成一行，然后再按列的方向增加每一列的監(jiān)督位。圖7.5 行列奇偶監(jiān)督碼清華大學(xué)出版社第7章 信道編碼1 1 0 0 1 0 1 0 0 00 1 0 0 0 0

13、1 1 0 10 1 1 1 1 0 0 0 0 11 0 0 1 1 1 0 0 0 01 0 1 0 1 0 1 0 1 0001011 1 0 0 0 1 1 1 1 00L5，m10的行列監(jiān)督碼（偶）【例】二維奇偶監(jiān)督碼適于監(jiān)測(cè)突發(fā)錯(cuò)誤：q逐行傳輸時(shí)，能檢測(cè)長(zhǎng)度b m+1=11的突發(fā)錯(cuò)誤;q逐列傳輸時(shí),能檢測(cè)長(zhǎng)度bL+1=6的突發(fā)錯(cuò)誤；q還能糾正一些僅在一行中的單個(gè)錯(cuò)誤。清華大學(xué)出版社第7章 信道編碼3. 恒比碼數(shù)字碼 字012345678901101010111100110110110100011110101111000111010011 又稱(chēng)等重碼或定1碼，這種碼字中1和0的位數(shù)保

14、持恒定比例。3：2數(shù)字保護(hù)碼 目前我國(guó)電傳通信中普遍采用3：2碼，又稱(chēng)“5 中取 3”的恒比碼，即每個(gè)碼組的長(zhǎng)度為 5，其中 3 個(gè)“1”。這時(shí)可能編成的不同碼組數(shù)目等于從 5 中取 3 的組合數(shù) 10，這 10 個(gè)許用碼組恰好可表示 10 個(gè)阿拉伯?dāng)?shù)字，如表 所示。4重復(fù)碼 一種k=1的(n, k)分組碼，其編碼規(guī)則是n-1個(gè)監(jiān)督碼元均是信息碼元的重復(fù)。重復(fù)碼許用碼組禁用碼組最小碼距檢錯(cuò)糾錯(cuò)能力（2，1）00；1101；102發(fā)現(xiàn)1位錯(cuò)誤（3，1）000；111001；010；011；100；101；110；3糾正1位錯(cuò)誤或 檢出2位錯(cuò)誤 【例】清華大學(xué)出版社第7章 信道編碼 可用線(xiàn)性方程組

15、表述碼的規(guī)律性的分組碼稱(chēng)為線(xiàn)性分組碼。一種同時(shí)具有線(xiàn)性特性和分組特性的糾錯(cuò)碼。 漢明（Hamming）碼是一種能夠糾正一位錯(cuò)碼且編碼效率較高的線(xiàn)性分組碼。 漢明碼：一種高效率的能糾單個(gè)錯(cuò)誤的線(xiàn)性分組碼。其特點(diǎn)是dmin3，碼長(zhǎng)與監(jiān)督元個(gè)數(shù)r滿(mǎn)足關(guān)系式：n=2r 17.2 線(xiàn)性分組碼7.2.1 基本概念（定義） 所謂分組特性是指將信碼進(jìn)行分組，并為每組信碼附加若干監(jiān)督碼。分組碼一般用符號(hào)(n，k)表示，其中n 是一個(gè)碼字(又稱(chēng)碼組、碼矢)的總位數(shù)，又稱(chēng)為碼組的長(zhǎng)度，k是碼組中信息碼元的數(shù)目，r為碼組中監(jiān)督碼元的數(shù)目。簡(jiǎn)單地說(shuō)，分組碼是對(duì)每段k位長(zhǎng)的信息碼組以一定的規(guī)則增加r個(gè)監(jiān)督碼元， 組成長(zhǎng)為

16、n的碼字。 分組碼（n , k）是一組固定長(zhǎng)度的碼組，通常用于前向糾錯(cuò)。在編碼時(shí)，k個(gè)信息位被編為n位碼組長(zhǎng)度，而r=n-k個(gè)監(jiān)督位的作用就是實(shí)現(xiàn)檢錯(cuò)與糾錯(cuò)。在二進(jìn)制情況下，共有2k個(gè)不同的信息組，相應(yīng)地可得到2k個(gè)不同的碼字，稱(chēng)為許用碼組。其余 2n-2k個(gè)碼字未被選用，稱(chēng)為禁用碼組。 清華大學(xué)出版社第7章 信道編碼an-1 an-2 ar ar-1 a0 碼長(zhǎng) n=k+r k 個(gè)信息位 r 個(gè)監(jiān)督位 分組碼(n，k)的結(jié)構(gòu) 信息碼元監(jiān)督碼元在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。分組碼的任一碼字A可表示為：012121aaaaaaaArrrnn信息碼元監(jiān)督碼元 所謂線(xiàn)性特性是指信息碼

17、元與監(jiān)督碼元之間的關(guān)系可以用一組線(xiàn)性方程式來(lái)表示，任一監(jiān)督碼元都是本碼組中信息碼元的線(xiàn)性疊加（二進(jìn)制編碼是模2加）。如（7，4）線(xiàn)性分組碼的碼字為A=（a6a5a4a3a2a1a0 ），前四位a6a5a4a3是信息元，后三位a2a1a0是監(jiān)督元，則監(jiān)督元的產(chǎn)生（碼的規(guī)律性）可用以下線(xiàn)性方程組描述：346035614562aaaaaaaaaaaa(7-4)346035614562aaaaaaaaaaaa監(jiān)督方程式說(shuō)明：(1)該方程組的構(gòu)建必須滿(mǎn)足3個(gè)方程線(xiàn)性無(wú)關(guān)。(2)上述相加為模2加。(3)生成方法：生成矩陣。(4)根據(jù)以上監(jiān)督方程式可得(7，4)分組碼的全部碼字。清華大學(xué)出版社第7章 信道編

18、碼信息位監(jiān)督位信息位監(jiān)督位a6a5a4a300000001001000110100010101100111a2a1a0000011101110110101011000a6a5a4a310001001101010101100110111101111a2a1a0111100010001001010100111監(jiān)督位計(jì)算結(jié)果 經(jīng)分析，dmin=3，故能糾正1個(gè)錯(cuò)誤或檢測(cè)2個(gè)錯(cuò)誤。又稱(chēng)（7，4）漢明碼。清華大學(xué)出版社第7章 信道編碼線(xiàn)性分組碼定義的數(shù)學(xué)表述 將(n,k)線(xiàn)性分組碼每一個(gè)碼字可以看成n維線(xiàn)性空間中的一個(gè)矢量，長(zhǎng)為n的碼字共有2n個(gè)，共同組成一個(gè)n維的線(xiàn)性空間，而(n,k)線(xiàn)性分組碼只有2

19、k個(gè)許用碼字，它就是其k維的一個(gè)線(xiàn)性子空間。定義： (n,k)線(xiàn)性分組碼C是碼字A的n維向量集合mGAAC其中m為任意的k維向量，稱(chēng)為信息向量；矩陣G稱(chēng)為生成矩陣，它有k行n列秩為k ，記為nknkkknngggggggggG1, 11 , 10 , 11, 11 , 10 , 11, 01 , 00 , 0(7-6)清華大學(xué)出版社第7章 信道編碼【例】1:3重復(fù)碼是一個(gè)（3，1）線(xiàn)性分組碼，其生成矩陣為1 , 1 , 1G則由分組碼的定義得碼字為1 , 1 , 1,0012maaa分別令m0=0、1，即得碼字（0，0，0）和（1，1，1）。清華大學(xué)出版社第7章 信道編碼【例】(4,3)偶監(jiān)督

20、碼是一個(gè)(4,3)線(xiàn)性分組碼。其生成矩陣為110010101001G則由定義得碼字為110010101001,0120123mmmaaaa信息碼元m2m1m0監(jiān)督碼元00000011010101101001101011001111顯然，監(jiān)督碼元為012mmm清華大學(xué)出版社第7章 信道編碼 （1）任意兩許用碼之和（逐位模2加）仍為一許用碼，也就是說(shuō)，線(xiàn)性分組碼具有封閉性； （2）最小碼距等于碼組中非全零碼的最小碼重（重量）。 （3）生成矩陣G的每一行都是一個(gè)碼組，任意碼字A是生成矩陣G的行向量g0、g1、gk-1的線(xiàn)性組合，即7.2.2 線(xiàn)性分組碼的主要性質(zhì) MGA 碼字生成矩陣信息向量清華大學(xué)

21、出版社第7章 信道編碼7.2.3 生成方程和生成矩陣 生成方程：描述監(jiān)督碼元和信息碼元之間關(guān)系的方程即MGA 式中 稱(chēng)為生成矩陣，各行線(xiàn)性無(wú)關(guān)，它又可以分成兩部分：nkGTkkPIQIG說(shuō)明：說(shuō)明： (1) Ik為k階單位矩陣； (2) Qkr稱(chēng)為G的典型生成矩陣； (3) 由G和信息向量M即可產(chǎn)生全部碼字； (4) 信息向量M共有k個(gè)元素。清華大學(xué)出版社第7章 信道編碼7.2.4 監(jiān)督方程和監(jiān)督矩陣 將(7,4)碼的三個(gè)監(jiān)督方程式可以重新改寫(xiě)為如下形式010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa00010

22、01101010101100101110123456Taaaaaaa或HAT=0T或或AHT=0即H即為監(jiān)督矩陣（parity-check matrix)。A為碼矢。HAT=0T，說(shuō)明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來(lái)作為判斷接收碼字A是否出錯(cuò)的依據(jù)。清華大學(xué)出版社第7章 信道編碼rIPH1001101010101100101110000aaaaaaa0123456A監(jiān)督方程也可以用矩陣形式來(lái)表示：3456012110110110111aaaaaaa Q34563456012110101011111aaaaaaaaaaa其中H可以分成兩部分稱(chēng)為典型監(jiān)督矩陣 這時(shí)Q = PT，如果在Q矩陣的

23、左邊再加上一個(gè)kk的單位矩陣，就形成了一個(gè)新矩陣G或表示為：清華大學(xué)出版社第7章 信道編碼1101000101010001100101110001QIGkG即為生成矩陣，利用它可以產(chǎn)生整個(gè)碼組：GGMA3456aaaa監(jiān)督矩陣H應(yīng)用： HAT=0T，說(shuō)明H陣與碼字的轉(zhuǎn)置之乘積必為0，以此作為判斷接收碼字A是否出錯(cuò)的依據(jù)。清華大學(xué)出版社第7章 信道編碼例：已知某線(xiàn)性分組碼監(jiān)督矩陣為列出所有的許用碼組。100110101010110010111H分析：本題考查線(xiàn)性分組碼的監(jiān)督矩陣、生成矩陣和許用碼組之間的關(guān)系?？偨Y(jié)如下：(1) 都可以化成典型陣型式：nkTkPIGnrrIPH(2) 可由G寫(xiě)出H，

24、也可由H寫(xiě)出G。(3) 由下式得出許用碼組：GMA解：H本身是典型陣型式，直接得出P陣。故生成矩陣為1101000101010001100101110001nkTkPIG得許用碼組G),(,34560123456aaaaaaaaaaa清華大學(xué)出版社第7章 信道編碼7.2.5 線(xiàn)性分組碼的譯碼伴隨式(校正子)S 設(shè)發(fā)送組碼A，在傳輸過(guò)程中有可能出現(xiàn)誤碼，這時(shí)接收到的碼組為B。則收發(fā)碼組之差為： 021021021eeeaaabbbnnnnnnEABiiiiiababe10其中 則接收端利用接收到的碼組B計(jì)算校正子： S=BHT=(A+E)HT= AHT + EHT = EHT 因此，校正子S僅與

25、E有關(guān)，即錯(cuò)誤圖樣與校正子之間有確定的關(guān)系。 清華大學(xué)出版社第7章 信道編碼 設(shè)發(fā)送碼組為A，接收碼組為B，錯(cuò)誤圖樣 EBA中哪位出現(xiàn)1，就表示接收碼組B中相應(yīng)的碼元錯(cuò)了。接收端利用監(jiān)督矩陣來(lái)檢測(cè)接收碼組B中的錯(cuò)誤。S=BHT = EHT ，即稱(chēng)為伴隨式或校正子。接收端譯碼過(guò)程： (1) 從伴隨式確定錯(cuò)誤圖樣E； (2) 從接收碼字B中減去錯(cuò)誤圖樣，即為糾正后的碼字A。清華大學(xué)出版社第7章 信道編碼以（7，4）漢明碼為例的譯碼過(guò)程（1）構(gòu)建S與E、B的關(guān)系。錯(cuò)誤碼位E=(e6e5e4e3e2e1e0)S=(S1S2S3)正確0000000000b00000001001b10000010010b

26、20000100100b30001000011b40010000101b50100000110b61000000111由此可得：65421bbbbS65312bbbbS64303bbbbS清華大學(xué)出版社第7章 信道編碼 （2）接收端收到每個(gè)碼組后，計(jì)算出S3、S2和S1，如不全為0，則可按上表確定誤碼的位置，然后予以糾正。 一般說(shuō)來(lái)，(n,k)分組碼共r個(gè)監(jiān)督碼元，有r個(gè)校正子S1S2Sr，可以指示(2r-1)種錯(cuò)誤圖樣。當(dāng) 時(shí)，就可以糾正1位或1位以上的錯(cuò)誤。nr12清華大學(xué)出版社第7章 信道編碼7.2.6 線(xiàn)性分組碼的實(shí)現(xiàn)（以(7,4)漢明碼為例） 1、編碼，生成許用碼組。11010001

27、01010001100101110001nkTkPIGG),(,34560123456aaaaaaaaaaa34603561456233445566 , , ,aaaaaaaaaaaaaaaaaaaa清華大學(xué)出版社第7章 信道編碼（7，4）系統(tǒng)漢明碼的編碼器電路6a6a5a4a3a5a4a3a2a1a0a清華大學(xué)出版社第7章 信道編碼2、譯碼，對(duì)接收碼組B糾錯(cuò)恢復(fù)成發(fā)送碼組A。65421bbbbS65312bbbbS64303bbbbS(1)(2) 3-7線(xiàn)譯碼，由校正子S得到錯(cuò)誤圖樣E。(3) 糾錯(cuò)。A=B+E。電路如下。清華大學(xué)出版社第7章 信道編碼6b5b4b3b校正子計(jì)算器3-8 譯碼

28、器6a5a4a3a2b1b0b3S2S1S誤碼指示 （7，4）系統(tǒng)漢明碼的譯碼器電路清華大學(xué)出版社第7章 信道編碼7.3 循環(huán)碼(cyclic code) 1957年由Prange提出，此后幾十年通過(guò)充分研究、應(yīng)用和發(fā)展。 循環(huán)碼是線(xiàn)性分組碼的一個(gè)重要子集，是目前研究得最成熟的一類(lèi)碼，它有許多特殊的代數(shù)性質(zhì)。 對(duì)循環(huán)性的理解：（1）碼字向左或向右循環(huán)移位后仍然是許用碼字；（2）并非所有碼字都可由一個(gè)碼字循環(huán)而得。 清華大學(xué)出版社第7章 信道編碼 定義：若線(xiàn)性分組碼的任一碼組循環(huán)移位所得的碼組仍在該碼組集中，則此線(xiàn)性分組碼稱(chēng)為循環(huán)碼。碼組編號(hào) 信息位監(jiān)督位碼組編號(hào) 信息位監(jiān)督位a6a5a4a3a

29、2a1a0a6a5a4a3a2a1a01234000001010011000001111110100156781001011101111011110001010010表 (7，3)循環(huán)碼的全部碼組清華大學(xué)出版社第7章 信道編碼 循環(huán)特性是指：循環(huán)碼中任一許用碼組經(jīng)過(guò)循環(huán)移位后，所得到的碼組仍然是許用碼組。 數(shù)學(xué)基礎(chǔ)：代數(shù)理論。 為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項(xiàng)式來(lái)表示，這個(gè)多項(xiàng)式被稱(chēng)為碼多項(xiàng)式，對(duì)于許用循環(huán)碼組 A=(an-1 an-2 a1 a0)，可以將它的碼多項(xiàng)式表示為 012211axaxaxaxTnnnn 這里，x 僅是碼元位置的標(biāo)記，我們并不關(guān)心它的取值。如碼組00

30、10111對(duì)應(yīng) 。系數(shù)ai 取0或1。 1244xxxxT7.3.1 循環(huán)碼原理循環(huán)碼原理 清華大學(xué)出版社第7章 信道編碼 若一個(gè)整數(shù)m可以表示為則在模n運(yùn)算下，有mp（模n）。同樣對(duì)于多項(xiàng)式而言，有是整數(shù)QnpnpQnm xNxRxQxNxF則可以寫(xiě)為： F(x)R(x) （模N(x)）循環(huán)碼運(yùn)算：按模運(yùn)算清華大學(xué)出版社第7章 信道編碼碼組1100101是表中第7碼字，碼組0101110正是表中第3碼字。 1172353589256373xxxxxxxxxxxxxxAx模 在循環(huán)碼中，若A(x)是一個(gè)長(zhǎng)為n的許用碼組，則在按模xn+1運(yùn)算下，xi A(x)亦是一個(gè)許用碼組。例如:對(duì)應(yīng)碼組11

31、00101，(7,3)循環(huán)碼的一個(gè)碼字對(duì)應(yīng)碼組0101110，(7,3)循環(huán)碼的一個(gè)碼字清華大學(xué)出版社第7章 信道編碼結(jié)論： 對(duì)于一個(gè)(n，k)循環(huán)碼A(x) ，若已知其中某一碼字的碼多項(xiàng)式，則其它的碼多項(xiàng)式可通過(guò)將該已知的碼多項(xiàng)式逐次乘以x并除以xn+1，用所得的余數(shù)多項(xiàng)式來(lái)表示。即 循環(huán)碼的移位操作對(duì)應(yīng)于碼多項(xiàng)式乘以x后除以xn+1并求余的運(yùn)算。或者說(shuō)，一個(gè)長(zhǎng)為n的循環(huán)碼必定為按模(xn+1)運(yùn)算的一個(gè)余式。清華大學(xué)出版社第7章 信道編碼 （1） g(x)是一個(gè)常數(shù)項(xiàng)為1的r = n-k 次多項(xiàng)式； （2） g(x)是xn+1的一個(gè)因式；(整除xn+1 ) （3）該循環(huán)碼中其它碼多項(xiàng)式都是

32、g(x)的倍式。(整除其它碼組) （4）g(x)的碼重就是碼組的最小碼距。 7.3.2 循環(huán)碼的生成多項(xiàng)式和生成矩陣循環(huán)碼的生成多項(xiàng)式和生成矩陣 循環(huán)碼中次數(shù)最低的碼多項(xiàng)式稱(chēng)為生成多項(xiàng)式，用g(x)表示。 1111xaxaxxgrrr可以證明生成多項(xiàng)式g(x)具有以下特性：清華大學(xué)出版社第7章 信道編碼 xgxgxxgxxgxxkk21G 1111xaxaxxgrrr 為了保證構(gòu)成的生成矩陣G的各行線(xiàn)性無(wú)關(guān)，通常用g(x)來(lái)構(gòu)造生成矩陣生成矩陣G(x)，因此，一旦生成多項(xiàng)式g(x)確定以后，該循環(huán)碼的生成矩陣就可以確定。QIGk 顯然，上式不符合 形式，所以此生成矩陣不是典型陣形式。 清華大學(xué)

33、出版社第7章 信道編碼由于（n,k）循環(huán)碼中g(shù)(x)是xn +1的因式，因此可令 11111xhxhxxgxxhkkkn xhxhxxhxxhxxHrr21 監(jiān)督矩陣可表示為： 其中1 )(12211*xhxhxhxxhkkkk 稱(chēng)為h(x)的逆多項(xiàng)式。利用循環(huán)碼的特點(diǎn)來(lái)確定監(jiān)督矩陣H： 清華大學(xué)出版社第7章 信道編碼 【例1】已知(7，4)循環(huán)碼的全部碼字為0000000，0001011，0010110，0101100，1011000，0110001，1100010，1000101，1001110，0011101，0100111，1101001，1110100，0111010，1111111

34、。寫(xiě)出該循環(huán)碼的生成多項(xiàng)式g(x)和生成矩陣G(x)，并將生成矩陣化成典型陣。 解： g(x)是一個(gè)常數(shù)項(xiàng)為1的r次多項(xiàng)式，本題中n=7, k=4, 所以r=3。由碼組集可知生成多項(xiàng)式為g(x)=x3+x+1。 生成矩陣為1)()()()()(32423534623xxxxxxxxxxxxgxxgxgxxgxxG或1101000011010000110100001101G1101000011010011100101010001G典型陣（H1+3+4 1；H2+4 2）清華大學(xué)出版社第7章 信道編碼【例2】已知(7,3)循環(huán)碼的監(jiān)督關(guān)系式, 0 , 0 , 0 , 004515601251236

35、aaaaaaaaaaaaaa(1)求其典型監(jiān)督矩陣和典型生成矩陣；(2)輸入信息碼元為101001，求編碼后的信息碼(系統(tǒng)碼)。解： (1)由監(jiān)督關(guān)系式HAT=0T得監(jiān)督矩陣并化成典型監(jiān)督矩陣為1000110010001111100100111001HrIPH1000110010001100101110001101典型生成矩陣為101110011100100111001TkPIG清華大學(xué)出版社第7章 信道編碼解： (2)由典型生成矩陣得故生成多項(xiàng)式為 。101110001011100010111G+H2+H3+H3即)()()(1)(22343452456xgxxgxgxxxxxxxxxxxx

36、xG1)(234xxxxg輸入信息碼元101時(shí)，對(duì)應(yīng) 。1)(2 xxm xgxrxQxgxmxkn1)( xxr xrxmxxAkn1)(46xxxxA1010011同理可求得當(dāng)信息碼元為001時(shí)，對(duì)應(yīng)的循環(huán)碼為0011101。 故輸入信息碼元為101001時(shí)，編碼后的信息碼為1010011 0011101 。清華大學(xué)出版社第7章 信道編碼1、編碼過(guò)程 m(x)：信息多項(xiàng)式7.3.3 循環(huán)碼的編、譯碼方法 首先需要根據(jù)給定循環(huán)碼的參數(shù)確定生成多項(xiàng)式g(x) ，然后，利用循環(huán)碼的編碼特點(diǎn)，即所有循環(huán)碼多項(xiàng)式A(x)都可以被g(x)整除，來(lái)定義生成多項(xiàng)式A(x)。下面就將以上各步處理加以解釋?zhuān)?

37、（1）用 xn-k 乘 m(x)。這一運(yùn)算實(shí)際上是把信息碼后附加上r個(gè)“0”。清華大學(xué)出版社第7章 信道編碼（3）編碼輸出系統(tǒng)循環(huán)碼多項(xiàng)式A(x)為： xgxrxgxmxxgxrxmxxQxgxAknkn xgxrxQxgxmxkn xrxmxxAkn （2）求r(x)。循環(huán)碼多項(xiàng)式A(x)都可以被g(x)整除，也就是：上式也等效于：這樣就得到了r(x)。用g(x)除 xn-k m(x) ， r(x)是余式。清華大學(xué)出版社第7章 信道編碼 從編碼的步驟看，編碼的核心是如何確定式r(x) ，找到 r(x) 后可直接將 r(x) 所代表的編碼位附加到信息位之后，完成編碼。實(shí)際上， r(x) 所代表

38、的編碼位可以理解為監(jiān)督位。獲取 r(x) 可以采用除法電路。 下圖給出了(7，3)循環(huán)碼的編碼器原理圖。圖中有4級(jí)移存器，分別用 表示。另外，有一雙刀雙擲開(kāi)關(guān)K，當(dāng)信息位輸入時(shí)，開(kāi)關(guān)K倒向下，輸入信碼一方面送入除法器進(jìn)行運(yùn)算，另一方面直接輸出。在信息位全部進(jìn)入除法器后，開(kāi)關(guān)轉(zhuǎn)向上，這時(shí)輸出端接到移存器，將移存器存儲(chǔ)的除法余項(xiàng)依次取出，同時(shí)切斷反饋線(xiàn)。用這種方法編出的碼組，前面是原來(lái)的k個(gè)信息位，后面是r個(gè)監(jiān)督位。因此它是系統(tǒng)分組碼。 dcba,清華大學(xué)出版社第7章 信道編碼利用除法電路來(lái)實(shí)現(xiàn) (7,3)循環(huán)碼的編碼過(guò)程abcd1122輸出輸入mef輸入移存器反饋輸出mabcdef0000000

39、110111010011010111000001010010000100000101mf 011ef1010K清華大學(xué)出版社第7章 信道編碼 （2）由校正子S(x)確定錯(cuò)誤圖樣E(x)； （3）將錯(cuò)誤圖樣E(x)與B(x)相加，糾正錯(cuò)誤。校正子計(jì)算電路錯(cuò)誤圖樣識(shí)別k級(jí)緩存器輸入糾錯(cuò)后輸出12n-k （1）由接收到的碼多項(xiàng)式B(x)計(jì)算校正子（伴隨式）多項(xiàng)式S(x)； 2、譯碼過(guò)程清華大學(xué)出版社第7章 信道編碼清華大學(xué)出版社第7章 信道編碼 已知（7，4）循環(huán)碼的生成多項(xiàng)式g(x)= x3+x2+1，（1）寫(xiě)出（7，4）循環(huán)碼的生成矩陣和監(jiān)督矩陣；（2）輸入信息碼為11001011，求編碼后的系

40、統(tǒng)碼；（3） 求此循環(huán)碼的全部許用碼組。（4） 分析此循環(huán)碼的糾、檢錯(cuò)能力。（5）畫(huà)出編碼器電路圖。習(xí)題詳解清華大學(xué)出版社第7章 信道編碼解：（1）生成矩陣為：1)()()()()(233424535623xxxxxxxxxxxxgxgxxgxxgxxG故得：1011000010110000101100001011G化成典型生成矩陣即為：QIGk1011000111010011000100110001得：111001111101TQP故典型監(jiān)督矩陣為：100111001001110011101rIPH清華大學(xué)出版社第7章 信道編碼（2）輸入1100時(shí)，信息碼多項(xiàng)式m(x) 為：23)(xxxm求xn-km(x)：56233)()(xxxxxxmxkn求xn-km(x)/g(x)：)()()()()(xgxrxQxgxmxkn111123232356xxxxxxxx求碼組T(x)：)()()(xrxmxxTkn11)()(25622347xxxxxxxxT1100101 同理求得輸入信息為1011時(shí)的循環(huán)碼組為1011100，故對(duì)信息碼元11001011，編碼后的系統(tǒng)碼是11001011011100。清華大學(xué)出版社第7章 信道編碼（3）與g(x)對(duì)應(yīng)的碼組是0001101，將此碼組經(jīng)過(guò)循環(huán)移位得到7個(gè)許用碼組，碼重都是3，即0001101