1、第7章 信 道 編 碼 教學(xué)目標(biāo) 通過(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ù)表示方式。清華大學(xué)出版社第七章 信道編碼7.1 信道編碼的基本概念7.1.1 差錯(cuò)控制編碼基本方式和類(lèi)型 1. 常用差錯(cuò)控制工作方式 按照噪聲或干擾所引起的錯(cuò)碼分布規(guī)律的不同，信道可以分為三類(lèi)：隨

2、機(jī)信道、突發(fā)信道和混合信道。 差錯(cuò)控制的基本工作方式有檢錯(cuò)重發(fā)、前向糾錯(cuò)、反饋校驗(yàn)、混合糾錯(cuò)等四種。它們的基本構(gòu)成及工作原理如圖7.1所示。 清華大學(xué)出版社第七章 信道編碼圖7.1 差錯(cuò)控制工作方式(1)檢錯(cuò)重發(fā)(ARQ)方式又稱(chēng)自動(dòng)請(qǐng)求重傳。 (2)常用的檢錯(cuò)重發(fā)系統(tǒng)有三種，即停止等待ARQ系統(tǒng)、拉后ARQ系統(tǒng)和選擇重發(fā)ARQ系統(tǒng)，圖7.2中給出了這三種系統(tǒng)的工作原理圖。清華大學(xué)出版社第七章 信道編碼圖7.2 ARQ系統(tǒng)的工作原理(a) 停止等待ARQ系統(tǒng) (b) 拉后ARQ系統(tǒng) (c) 選擇重發(fā)ARQ系統(tǒng)清華大學(xué)出版社第七章 信道編碼 差錯(cuò)控制編碼常稱(chēng)為糾錯(cuò)編碼。不同的編碼方式有不同的檢錯(cuò)

3、或糾錯(cuò)能力。有的編碼方法只能檢錯(cuò)，不能糾錯(cuò)。一般來(lái)說(shuō)，付出的代價(jià)越大，檢糾錯(cuò)的能力就越強(qiáng)。這里所指的代價(jià)，就是指增加的監(jiān)督碼元位數(shù)，它通常用冗余度或多余度來(lái)衡量。設(shè)編碼序列中信息碼元位數(shù)為 ，監(jiān)督碼元位數(shù)為 ，碼字位數(shù)為 ，則比值 稱(chēng)為編碼效率簡(jiǎn)稱(chēng)碼率又稱(chēng)編碼速率，比值 稱(chēng)為冗余度，比值 稱(chēng)為多余度。 krrknnk /kr /nr /清華大學(xué)出版社第七章 信道編碼 2. 差錯(cuò)控制編碼分類(lèi) 差錯(cuò)控制系統(tǒng)中使用的信道編碼可以有很多種。 (1)按照信息碼元和監(jiān)督碼元之間的函數(shù)關(guān)系可以分為線(xiàn)性碼和非線(xiàn)性碼。 (2)按照信息碼元和監(jiān)督碼元之間的約束關(guān)系涉及的范圍可以分為分組碼和卷積碼。 (3)按照糾錯(cuò)

4、碼組中信息碼元是否隱蔽，可劃分為系統(tǒng)碼和非系統(tǒng)碼。 (4)按照糾正錯(cuò)誤的類(lèi)型不同，可以分為糾正隨機(jī)錯(cuò)誤的碼和糾正突發(fā)錯(cuò)誤的碼。 (5)按照構(gòu)造差錯(cuò)控制編碼的數(shù)學(xué)方法來(lái)分類(lèi)，又可以分為代數(shù)碼、幾何碼和算術(shù)碼。 清華大學(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取的。清華大學(xué)出版社第七章 信道編碼 在信道編碼中，定義碼組中非零碼元的數(shù)目為碼組的重量，簡(jiǎn)稱(chēng)碼重。 把兩個(gè)碼組中

5、對(duì)應(yīng)碼元位置上具有不同二進(jìn)制碼元的位數(shù)定義為兩個(gè)碼組的距離，稱(chēng)為漢明距離，簡(jiǎn)稱(chēng)碼距。 一種編碼的最小碼距的大小直接關(guān)系著這種編碼的檢錯(cuò)和糾錯(cuò)能力： (1) 為檢測(cè) 個(gè)錯(cuò)碼，要求最小碼距為 (7-1) (2) 為了糾正 個(gè)錯(cuò)碼，要求最小碼距為 (7-2) (3)為了糾正 個(gè)錯(cuò)碼同時(shí)檢測(cè) 個(gè)錯(cuò)碼，要求最小碼距為 (7-3)1min ed12min tdette1minetd清華大學(xué)出版社第七章 信道編碼7.1.3 幾種常用的差錯(cuò)控制碼 1. 奇偶監(jiān)督碼 奇偶監(jiān)督碼又稱(chēng)奇偶校驗(yàn)碼，分為奇數(shù)監(jiān)督和偶數(shù)監(jiān)督兩種，兩者的原理相同，都是在原信息碼后面附加1個(gè)監(jiān)督元，使得碼組中“1”的個(gè)數(shù)是奇數(shù)或者偶數(shù)。無(wú)論

6、信息位是多少位，監(jiān)督位或校驗(yàn)位都只有1位。清華大學(xué)出版社第七章 信道編碼 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.3所示。 清華大學(xué)出版社第七章 信道編碼圖7.5 行列奇偶監(jiān)督碼 3. 恒比碼 恒比碼又稱(chēng)等重碼或定“1”碼，它是從某確定碼長(zhǎng)的碼組中挑選那些“1”和“0”的比例為恒定值的碼組作為許用碼組，即碼組中“1”和“0”的位數(shù)保持恒定的比例。 清華大學(xué)出版社第七

7、章 信道編碼 4. 群計(jì)數(shù)碼 群計(jì)數(shù)碼是將信息碼元分組后，計(jì)算每組碼元中“1”的個(gè)數(shù)，然后將這個(gè)數(shù)目的二進(jìn)制表示作為監(jiān)督碼元附加在信息碼元之后組成碼字。 5重復(fù)碼 一種k=1的(n, k)分組碼，其編碼規(guī)則是n-1個(gè)監(jiān)督碼元均是信息碼元的重復(fù)。 清華大學(xué)出版社第七章 信道編碼7.2 線(xiàn)性分組碼 7.2.1 線(xiàn)性分組碼的定義及性質(zhì) 1定義 線(xiàn)性分組碼是一種同時(shí)具有分組特性和線(xiàn)性特性的糾錯(cuò)碼。 所謂分組特性是指將信碼進(jìn)行分組，并為每組信碼附加若干監(jiān)督碼。分組碼一般用符號(hào)( )表示，其中 是一個(gè)碼字(又稱(chēng)碼組、碼矢)的總位數(shù)，又稱(chēng)為碼組的長(zhǎng)度， 是碼組中信息碼元的數(shù)目， 為碼組中監(jiān)督碼元的數(shù)目。 k

8、n,nrknk清華大學(xué)出版社第七章 信道編碼因此，分組碼的任一碼字A可表示為 其中 為信息碼元， 為監(jiān)督碼元。在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。 所謂線(xiàn)性特性是指信息碼元與監(jiān)督碼元之間的關(guān)系可以用一組線(xiàn)性方程式來(lái)表示，任一監(jiān)督碼元都是本碼組中信息碼元的線(xiàn)性疊加(二進(jìn)制編碼是模2加)。如(7,4)線(xiàn)性分組碼的碼字為 ，前四位 是信息元，后三位 是監(jiān)督元，則監(jiān)督元的產(chǎn)生可用以下線(xiàn)性方程組描述012121aaaaaaaArrrnnrnnaaa210121aaaarr0123456aaaaaaaA 3456aaaa012aaa清華大學(xué)出版社第七章 信道編碼 (7-4)34603561456

9、2aaaaaaaaaaaa清華大學(xué)出版社第七章 信道編碼 從生成線(xiàn)性分組碼各碼字的角度看，可將(n,k)線(xiàn)性分組碼的每一個(gè)碼字看成n維線(xiàn)性空間中的一個(gè)矢量。長(zhǎng)為n的碼字共有 個(gè)，它們組成一個(gè)n維的線(xiàn)性空間；而(n,k)線(xiàn)性分組碼只有 個(gè)許用碼字( )，它們構(gòu)成一個(gè)k維的線(xiàn)性子空間。由此定義： (n,k)線(xiàn)性分組碼C是碼字A的n維向量的集合 (7-5) 其中m為任意的k維向量，稱(chēng)為信息向量。矩陣G稱(chēng)為生成矩陣，它有k行n列秩為k，記為n2k2nk CA AmG清華大學(xué)出版社第七章 信道編碼 (7-6)0,00,10,11,01,11,11,01,11,1k nnnkkknGggggggggg 2

10、性質(zhì)線(xiàn)性分組碼的主要性質(zhì)如下：(1) 任意兩許用碼組之和(逐位模2加)仍為一許用碼組，即線(xiàn)性碼具有封閉性。(2) 任一碼字是生成矩陣的行向量的線(xiàn)性組合。(3) 最小碼距等于碼組中非全零碼的最小碼重。清華大學(xué)出版社第七章 信道編碼 7.2.2 生成方程和生成矩陣G 描述監(jiān)督碼元和信息碼元之間相互關(guān)系的方程，稱(chēng)為生成方程，即 A=mG (7-7)7.2.3 監(jiān)督方程和監(jiān)督矩陣H7.2.4 線(xiàn)性分組碼的譯碼伴隨式(校正子)S7.2.5 漢明碼 能糾正單個(gè)錯(cuò)誤且對(duì)監(jiān)督位的利用最充分的線(xiàn)性分組碼稱(chēng)為漢明碼。漢明碼具有以下特點(diǎn)：清華大學(xué)出版社第七章 信道編碼(1) 監(jiān)督碼位數(shù)； (2) 信息碼位數(shù)；(3)

11、 碼長(zhǎng)；(4) 無(wú)論碼長(zhǎng)多少，最小碼距(又稱(chēng)漢明距離)；(5) 糾錯(cuò)能力。這里為不小于2的正整數(shù)。給定后，即可構(gòu)造出具體的漢明碼。清華大學(xué)出版社第七章 信道編碼7.2.6 線(xiàn)性分組碼的實(shí)現(xiàn)1編碼2譯碼清華大學(xué)出版社第七章 信道編碼 7.3 循 環(huán) 碼 7.3.1 循環(huán)碼的含義與特點(diǎn) 線(xiàn)性分組碼中，有一種重要的碼稱(chēng)為循環(huán)碼。它是在嚴(yán)密的代數(shù)學(xué)理論基礎(chǔ)上建立起來(lái)的，是目前研究得最成熟的一類(lèi)碼。循環(huán)碼的編碼和解碼設(shè)備都不太復(fù)雜(由循環(huán)性決定)，而且檢糾錯(cuò)能力較強(qiáng)。循環(huán)碼還具有易于實(shí)現(xiàn)的特點(diǎn)，很容易用帶反饋的移位寄存器實(shí)現(xiàn)其硬件，而且性能較好，不但可用于糾正獨(dú)立的隨機(jī)錯(cuò)誤，也可以用于糾正突發(fā)錯(cuò)誤。清華

12、大學(xué)出版社第七章 信道編碼 7.3.2 循環(huán)碼的生成多項(xiàng)式、生成矩陣和監(jiān)督矩陣 1生成多項(xiàng)式 循環(huán)碼完全由其碼組長(zhǎng)度 及生成多項(xiàng)式 所決定。對(duì)于(n,k)循環(huán)碼，可以證明， 具有以下性質(zhì)：)(xgn)(xg)(xg清華大學(xué)出版社第七章 信道編碼(1) 是一個(gè)能除盡的碼多項(xiàng)式。或者說(shuō)， 是 的一個(gè)因式。(2) 是一個(gè)r次多項(xiàng)式，常數(shù)項(xiàng)為1。即 (7-8)(3) 其它碼多項(xiàng)式都是 的倍式。假設(shè)信息碼多項(xiàng)式是 ，則碼多項(xiàng)式為 (7-9)(xg)(xg1nx)(xg1)(111xaxaxxgrrr)()()(xgxMxC)(xg)(xM清華大學(xué)出版社第七章 信道編碼2生成矩陣 和監(jiān)督矩陣 循環(huán)碼的生成

13、矩陣很容易由多項(xiàng)式得到，表示為 (7-10)(xG)(xHnkkkxgxxgxgxxgxxG)()()()()(21清華大學(xué)出版社第七章 信道編碼 7.3.3 循環(huán)碼的編譯碼方法1編碼過(guò)程及實(shí)現(xiàn) 生成循環(huán)碼的碼字有兩種方法：一種是利用生成矩陣產(chǎn)生，一種是利用多項(xiàng)式除法產(chǎn)生。前者電路實(shí)現(xiàn)難度較大，后者編碼電路實(shí)現(xiàn)比較簡(jiǎn)單，且編碼沒(méi)有延遲。下面介紹利用多項(xiàng)式除法產(chǎn)生碼字的原理及實(shí)現(xiàn)方法。清華大學(xué)出版社第七章 信道編碼2譯碼過(guò)程及實(shí)現(xiàn)循環(huán)碼的糾錯(cuò)過(guò)程可按以下步驟進(jìn)行：(1) 用生成多項(xiàng)式 去除接收碼組 ，得出余式 。(2) 按余式 用查表的方法或通過(guò)某種運(yùn)算得到錯(cuò)誤圖樣 ，就可以確定錯(cuò)碼位置。(3)

14、 從 中減去，便得到已糾正錯(cuò)誤的原發(fā)送碼組 。)(xg)()()(xExAxB)(xr)(xr)(xE)(xE)(xB)(xA 7.4 卷 積 碼7.4.1 卷積碼的基本原理卷積碼編碼器一般原理框圖 清華大學(xué)出版社第七章 信道編碼7.4.2 卷積碼的代數(shù)表示 一個(gè)線(xiàn)性碼可以由一個(gè)監(jiān)督矩陣H或生成矩陣G所確定。首先設(shè)在第一個(gè)信息位 進(jìn)入編碼器之前，各級(jí)移存器多處于“0”狀態(tài)，則監(jiān)督位 、 和信息位 之間的關(guān)系可寫(xiě)為 (7-11)ibidieib23442441233133122221111bbbebbdbbbebbdbbebdbebd清華大學(xué)出版社第七章 信道編碼 7.4.3 卷積碼的圖形表示

15、卷積碼的譯碼方式中其大數(shù)邏輯譯碼時(shí)給予卷積碼的代數(shù)表示之上的，而其維特比譯碼方式是基于卷積碼的幾何表述之上的。所以在介紹卷積碼的譯碼算法之前，先引入集中幾何表述方法。1. 樹(shù)形圖清華大學(xué)出版社第七章 信道編碼卷積碼樹(shù)形圖清華大學(xué)出版社第七章 信道編碼2. 狀態(tài)圖卷積碼狀態(tài)圖 清華大學(xué)出版社第七章 信道編碼3. 網(wǎng)格圖卷積碼網(wǎng)格圖 清華大學(xué)出版社第七章 信道編碼 7.4.4 卷積碼的譯碼方法 卷積碼的譯碼方式有三種：大數(shù)邏輯譯碼、維特比譯碼、門(mén)限譯碼。其中維特比譯碼具有最佳性能，但硬件實(shí)現(xiàn)復(fù)雜；大數(shù)邏輯譯碼性能最差，但硬件簡(jiǎn)單；序列譯碼在性能和硬件方面介于維特比譯碼和大數(shù)邏輯譯碼之間。清華大學(xué)出

16、版社第七章 信道編碼 1. 大數(shù)邏輯譯碼 大數(shù)邏輯譯碼又稱(chēng)門(mén)限譯碼，它曾經(jīng)是卷積碼最常用的譯碼方法，雖然現(xiàn)在維特比譯碼和序列譯碼已成為主要的譯碼方法，但是由于大數(shù)邏輯譯碼設(shè)備簡(jiǎn)單，譯碼速度快，并且適合于有突發(fā)錯(cuò)誤的信道，因此在某些情況下仍有實(shí)用價(jià)值。清華大學(xué)出版社第七章 信道編碼 2. 維特比譯碼 維特比譯碼算法是維特比于1967年提出的。由于這種譯碼方法比較簡(jiǎn)單，計(jì)算快，故得到廣泛應(yīng)用，特別是在衛(wèi)星通信和蜂窩通信系統(tǒng)中應(yīng)用。維特比譯碼是一種最大似然譯碼算法。最大似然譯碼算法的基本思路是：把接收碼字與所有可能的碼字比較，選擇一種碼距最小的碼字作為譯碼輸出。若發(fā)送一個(gè) 位序列，則有 種可能的發(fā)送

17、序列。計(jì)算機(jī)應(yīng)存儲(chǔ)這些序列，以便用于比較。當(dāng) 較大時(shí)，存儲(chǔ)量太大，使實(shí)用性受到限制。維特比算法對(duì)此做了簡(jiǎn)化，即把接收碼字分段累計(jì)處理，每接收一段碼字計(jì)算、比較一次，保留碼距最小的路徑，直至譯完整個(gè)序列。kk2k清華大學(xué)出版社第七章 信道編碼 3. 序列譯碼 在卷積碼 中 值很大的情況下，可以采用序列譯碼。序列譯碼早在維特比譯碼之前就已提出，它也是以最大似然譯碼原理為基礎(chǔ)。如同維特比譯碼，序列譯碼也是以漢明距離為準(zhǔn)則，選擇與接收序列最接近的路徑作為譯碼輸出。與維特比譯碼不同的是，序列譯碼只是延伸一條具有最小漢明距離的路徑，而不是把所有可能的路徑保留，然后進(jìn)行比較、選擇。計(jì)算，并建立一定的算法。)

18、,(NknN清華大學(xué)出版社第七章 信道編碼 由于序列譯碼中一次只搜索一條路徑，在有限搜索情況下，這條路徑并不能肯定是最好的，它只能認(rèn)為是一種尋找正確路徑的試探方法。它總是在一條單一的路徑上，以序列的方式進(jìn)行搜索。譯碼器每向前延伸已調(diào)支路就進(jìn)行一次判斷，選擇呈現(xiàn)出具有最大似然概率的路徑。如果所作的判決時(shí)錯(cuò)誤的，則以后的路徑就是錯(cuò)誤的。根據(jù)路徑量度變化，譯碼器最終可以識(shí)別路徑是否正確。當(dāng)譯碼器識(shí)別出路徑是錯(cuò)誤的時(shí)候，就后退搜索并試探其他路徑，知道選擇已一條正確的路徑位置。為了恢復(fù)正確路徑，需要進(jìn)行大量清華大學(xué)出版社第七章 信道編碼 本章 小 結(jié) 在數(shù)字信號(hào)傳輸過(guò)程中，為了提高信道的可靠性，常通過(guò)信道編碼的方式來(lái)實(shí)現(xiàn)差錯(cuò)控制。信道編碼即差錯(cuò)控制編碼，其基本原則是發(fā)送端在信息碼元中按照一定的規(guī)律加入一些冗余的碼元，這些冗余碼元被稱(chēng)為監(jiān)督碼。而接收端則利用監(jiān)督碼元與信息碼元之間的約束關(guān)系來(lái)進(jìn)行判斷，衡量傳輸過(guò)程中是否存在誤碼。利用這些差錯(cuò)控制編碼，接收端可以發(fā)現(xiàn)或糾正傳輸過(guò)程中的誤碼。清華大學(xué)出版社第七章 信道編碼 差錯(cuò)控制的方式一般有4種：檢錯(cuò)重發(fā)、前向糾錯(cuò)、反饋校驗(yàn)、混合糾錯(cuò)。檢錯(cuò)重發(fā)方式的通信系統(tǒng)需要有雙向信道傳送重發(fā)指令。常用的檢錯(cuò)重發(fā)系統(tǒng)