第7章_信道編碼

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

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

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

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

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

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

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

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

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

10、是一種能糾正單個錯誤的完備碼。糾錯能力t=1，故最小碼距dmin=3。 完備碼若 ，則稱此(n，k)碼為能糾正t個錯誤的完備碼。tiinknC02 漢明碼)12 , 12(rrr碼長：n=2r-1信息位數(shù)：k=2r-1-r監(jiān)督位數(shù)：r=n-k故編碼效率為121rrnkR此題中1512rnr = 4故1511nrnnkR清華大學(xué)出版社第七章 信道編碼7.1.3 幾種常用的差錯控制碼1. 奇偶監(jiān)督碼 在n-1個信息元后面附加一個監(jiān)督元，使得長n的碼字中1的個數(shù)保持為奇數(shù)或偶數(shù)的碼稱為奇偶監(jiān)督碼。序號 碼 字序號 碼 字信息碼元 監(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碼長為5的偶監(jiān)督碼清華大學(xué)出版社第7章 信道編碼設(shè)碼字A=an-1,an-2,a1,a0，對偶監(jiān)督碼有 00121aaaann 奇監(jiān)督碼情況相似， 只是碼組中“1”的數(shù)目為奇數(shù)， 即滿足條件 1021aaann而檢錯能力與偶監(jiān)督碼相同。 奇偶監(jiān)督碼的編碼效率R為 nnR/ ) 1( 清華大學(xué)出版社第7章 信道編碼a4a3a

12、2a1a0a4a3a2a1信息組編碼輸出b0b4b3b2b1接收碼組檢錯信號SBAM 奇偶監(jiān)督碼的編碼可以用軟件實現(xiàn)，也可用硬件電路實現(xiàn)。 如果碼組B無錯，BA，則M0；如果碼組B有單個（或奇數(shù)個）錯誤，則M1。2. 行列(二維)奇偶監(jiān)督碼 奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個錯誤。為了改善這種情況，引入行列奇偶監(jiān)督碼，又稱二維奇偶監(jiān)督碼。這種編碼不僅對水平方向的碼元，而且對垂直方向的碼元實施監(jiān)督。行列奇偶監(jiān)督碼先把上述奇偶監(jiān)督碼的若干碼組，每個寫成一行，然后再按列的方向增加每一列的監(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)測突發(fā)錯誤：q逐行傳輸時，能檢測長度b m+1=11的突發(fā)錯誤;q逐列傳輸時,能檢測長度bL+1=6的突發(fā)錯誤；q還能糾正一些僅在一行中的單個錯誤。清華大學(xué)出版社第7章 信道編碼3. 恒比碼數(shù)字碼 字012345678901101010111100110110110100011110101111000111010011 又稱等重碼或定1碼，這種碼字中1和0的位數(shù)保

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34、11。寫出該循環(huán)碼的生成多項式g(x)和生成矩陣G(x)，并將生成矩陣化成典型陣。 解： g(x)是一個常數(shù)項為1的r次多項式，本題中n=7, k=4, 所以r=3。由碼組集可知生成多項式為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 , 0045156012512

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

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

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

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

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

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