第7章_信道編碼

1、第7章 信 道 編 碼 教學(xué)目標(biāo) 通過(guò)本章的學(xué)習(xí)，熟悉信道編碼的概念，了解信道編碼 的目的及意義；掌握差錯(cuò)控制編碼的基本原理，熟悉差 錯(cuò)控制的工作方式及幾種常用的差錯(cuò)控制編碼，了解其 性能優(yōu)劣；熟悉碼距、碼重對(duì)編碼器檢糾錯(cuò)能力的影響； 掌握如何利用線性分組碼實(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ī)律的不同

2、，信道可 以分為三類(lèi)：隨機(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ò)

3、控制編碼常稱(chēng)為糾錯(cuò)編碼。不同的編碼方式有 不同的檢錯(cuò)或糾錯(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)為多余度。 kr rkn nk /kr / nr / 清華大學(xué)出版社 第七章 信道編碼 2. 差錯(cuò)控制編碼分類(lèi) 差錯(cuò)控制系統(tǒng)中使用的信道編碼可以有很多種。 (1)按照信息碼元和監(jiān)督碼元之間的函數(shù)關(guān)系可以分為線 性碼和非線性碼。 (2)按照信息碼元

4、和監(jiān)督碼元之間的約束關(guān)系涉及的范圍 可以分為分組碼和卷積碼。 (3)按照糾錯(cuò)碼組中信息碼元是否隱蔽，可劃分為系統(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é)出版社

5、 第七章 信道編碼 在信道編碼中，定義碼組中非零碼元的數(shù)目為碼組 的重量，簡(jiǎn)稱(chēng)碼重。 把兩個(gè)碼組中對(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) 1 min ed 12 min td e t t e 1 min etd 清華大學(xué)出版社 第七章 信道編碼 7.1.3 幾種常用的差錯(cuò)控制碼 1. 奇偶監(jiān)督碼 奇偶監(jiān)督碼又稱(chēng)

6、奇偶校驗(yàn)碼，分為奇數(shù)監(jiān)督和偶數(shù)監(jiān)督 兩種，兩者的原理相同，都是在原信息碼后面附加1個(gè)監(jiān) 督元，使得碼組中“1”的個(gè)數(shù)是奇數(shù)或者偶數(shù)。無(wú)論信 息位是多少位，監(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)等重碼或

7、定“1”碼，它是從某確定碼長(zhǎng)的碼 組中挑選那些“1”和“0”的比例為恒定值的碼組作為許 用碼組，即碼組中“1”和“0”的位數(shù)保持恒定的比例。 清華大學(xué)出版社 第七章 信道編碼 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 線性分組碼 7.2.1 線性分組碼的定義及性質(zhì) 1定義 線性分組碼是一種同時(shí)具有分組特性和線性特性的糾錯(cuò) 碼。 所謂分組特性是指將信碼進(jìn)行分組，

8、并為每組信碼附加 若干監(jiān)督碼。分組碼一般用符號(hào)( )表示，其中 是一 個(gè)碼字(又稱(chēng)碼組、碼矢)的總位數(shù)，又稱(chēng)為碼組的長(zhǎng)度， 是碼組中信息碼元的數(shù)目， 為碼組中監(jiān)督碼元的 數(shù)目。 kn,n rkn k 清華大學(xué)出版社 第七章 信道編碼 因此，分組碼的任一碼字A可表示為 其中 為信息碼元， 為監(jiān)督碼元。 在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。 所謂線性特性是指信息碼元與監(jiān)督碼元之間的關(guān)系 可以用一組線性方程式來(lái)表示，任一監(jiān)督碼元都是本碼 組中信息碼元的線性疊加(二進(jìn)制編碼是模2加)。如(7,4) 線性分組碼的碼字為 ，前四位 是信息 元，后三位 是監(jiān)督元，則監(jiān)督元的產(chǎn)生可用以下 線性方程組

9、描述 012121 aaaaaaaA rrrnn rnn aaa 210121 aaaa rr 0123456 aaaaaaaA 3456 aaaa 012 aaa 清華大學(xué)出版社 第七章 信道編碼 (7-4) 3460 3561 4562 aaaa aaaa aaaa 清華大學(xué)出版社 第七章 信道編碼 從生成線性分組碼各碼字的角度看，可將(n,k)線性分組 碼的每一個(gè)碼字看成n維線性空間中的一個(gè)矢量。長(zhǎng)為n 的碼字共有 個(gè)，它們組成一個(gè)n維的線性空間；而(n,k) 線性分組碼只有 個(gè)許用碼字( )，它們構(gòu)成一個(gè)k維 的線性子空間。由此定義： (n,k)線性分組碼C是碼字A的n維向量的集合 (

10、7-5) 其中m為任意的k維向量，稱(chēng)為信息向量。矩陣G稱(chēng)為生 成矩陣，它有k行n列秩為k，記為 n 2 k 2 nk CA AmG 清華大學(xué)出版社 第七章 信道編碼 (7-6) 0,00,10,1 1,01,11,1 1,01,11,1 k n n n kkkn G ggg ggg ggg 2性質(zhì) 線性分組碼的主要性質(zhì)如下： (1) 任意兩許用碼組之和(逐位模2加)仍為一許用碼組，即線 性碼具有封閉性。 (2) 任一碼字是生成矩陣的行向量的線性組合。 (3) 最小碼距等于碼組中非全零碼的最小碼重。 清華大學(xué)出版社 第七章 信道編碼 7.2.2 生成方程和生成矩陣G 描述監(jiān)督碼元和信息碼元之間相

11、互關(guān)系的方程，稱(chēng)為生 成方程，即 A=mG (7-7) 7.2.3 監(jiān)督方程和監(jiān)督矩陣H 7.2.4 線性分組碼的譯碼伴隨式(校正 子)S 7.2.5 漢明碼 能糾正單個(gè)錯(cuò)誤且對(duì)監(jiān)督位的利用最充分的線性分 組碼稱(chēng)為漢明碼。漢明碼具有以下特點(diǎn)： 清華大學(xué)出版社 第七章 信道編碼 (1) 監(jiān)督碼位數(shù)； (2) 信息碼位數(shù)； (3) 碼長(zhǎng)； (4) 無(wú)論碼長(zhǎng)多少，最小碼距(又稱(chēng)漢明距離)； (5) 糾錯(cuò)能力。 這里為不小于2的正整數(shù)。給定后，即可構(gòu)造出具體的漢明 碼。 清華大學(xué)出版社 第七章 信道編碼 7.2.6 線性分組碼的實(shí)現(xiàn) 1編碼 2譯碼 清華大學(xué)出版社 第七章 信道編碼 7.3 循 環(huán) 碼

12、 7.3.1 循環(huán)碼的含義與特點(diǎ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ò)誤。 清華大學(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ì)： )(xg n )(xg )(xg 清華大

13、學(xué)出版社 第七章 信道編碼 (1) 是一個(gè)能除盡的碼多項(xiàng)式?；蛘哒f(shuō)， 是 的一 個(gè)因式。 (2) 是一個(gè)r次多項(xiàng)式，常數(shù)項(xiàng)為1。即 (7-8) (3) 其它碼多項(xiàng)式都是 的倍式。假設(shè)信息碼多項(xiàng)式是 ， 則碼多項(xiàng)式為 (7-9) )(xg)(xg 1 n x )(xg 1)( 1 1 1 xaxaxxg r r r )()()(xgxMxC )(xg )(xM 清華大學(xué)出版社 第七章 信道編碼 2生成矩陣 和監(jiān)督矩陣 循環(huán)碼的生成矩陣很容易由多項(xiàng)式得到，表示為 (7-10) )(xG)(xH nk k k xg xxg xgx xgx xG )( )( )( )( )( 2 1 清華大學(xué)出版社

14、第七章 信道編碼 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) 從 中減去，便得到已糾正錯(cuò)誤的原發(fā)送碼組 。 )(xg)()()(xExAxB )(xr )(xr )

15、(xE )(xE )(xB)(xA 7.4 卷 積 碼 7.4.1 卷積碼的基本原理 卷積碼編碼器一般原理框圖 清華大學(xué)出版社 第七章 信道編碼 7.4.2 卷積碼的代數(shù)表示 一個(gè)線性碼可以由一個(gè)監(jiān)督矩陣H或生成矩陣G所確 定。首先設(shè)在第一個(gè)信息位 進(jìn)入編碼器之前，各級(jí)移 存器多處于“0”狀態(tài)，則監(jiān)督位 、 和信息位 之間 的關(guān)系可寫(xiě)為 (7-11) i b i d i e i b 2344 244 1233 133 122 22 11 11 bbbe bbd bbbe bbd bbe bd be bd 清華大學(xué)出版社 第七章 信道編碼 7.4.3 卷積碼的圖形表示 卷積碼的譯碼方式中其大數(shù)邏

16、輯譯碼時(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ù)邏輯譯碼 之間

17、。 清華大學(xué)出版社 第七章 信道編碼 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)用。維特比譯碼是一種最 大似然譯碼算法。最大似然譯碼算法的基本思路是：把 接收碼字與所有可能的碼字比較，選擇一種碼距最小的 碼字作為譯碼輸出。

18、若發(fā)送一個(gè) 位序列，則有 種可 能的發(fā)送序列。計(jì)算機(jī)應(yīng)存儲(chǔ)這些序列，以便用于比較。 當(dāng) 較大時(shí)，存儲(chǔ)量太大，使實(shí)用性受到限制。維特比 算法對(duì)此做了簡(jiǎn)化，即把接收碼字分段累計(jì)處理，每接 收一段碼字計(jì)算、比較一次，保留碼距最小的路徑，直 至譯完整個(gè)序列。 k k 2 k 清華大學(xué)出版社 第七章 信道編碼 3. 序列譯碼 在卷積碼 中 值很大的情況下，可以采用序列譯 碼。序列譯碼早在維特比譯碼之前就已提出，它也是以 最大似然譯碼原理為基礎(chǔ)。如同維特比譯碼，序列譯碼 也是以漢明距離為準(zhǔn)則，選擇與接收序列最接近的路徑 作為譯碼輸出。與維特比譯碼不同的是，序列譯碼只是 延伸一條具有最小漢明距離的路徑，而不是把所有可能 的路徑保留，然后進(jìn)行比較、選擇。計(jì)算，并建立一定 的算法。 ),(Nkn N 清華大學(xué)出版社 第七章 信道編碼 由于序列譯碼中一次只搜索一條路徑，在有限搜索 情況下，這條路徑并不能肯定是最好的，它只能認(rèn)為是 一種尋找正確路徑的試探方法。它總是在一條單一的路 徑上，以序列的方式進(jìn)行搜索。譯碼器每向前延伸已調(diào) 支路就進(jìn)行一次判斷，選擇呈現(xiàn)出具有最大似然概率的 路徑。如果所作的判決時(shí)錯(cuò)誤的，則以后的路徑就是錯(cuò) 誤的。根據(jù)路徑量度變化，譯碼器最終可以識(shí)別路徑是 否正確。當(dāng)譯碼器識(shí)別出路徑是錯(cuò)誤的時(shí)候，就后退搜 索并試探其他路徑，知