第7章_信道編碼

1、第7章 信 道 編 碼 教學目標 通過本章的學習，熟悉信道編碼的概念，了解信道編碼 的目的及意義；掌握差錯控制編碼的基本原理，熟悉差 錯控制的工作方式及幾種常用的差錯控制編碼，了解其 性能優(yōu)劣；熟悉碼距、碼重對編碼器檢糾錯能力的影響； 掌握如何利用線性分組碼實現(xiàn)糾檢錯，熟悉生成矩陣和 監(jiān)督矩陣的概念，了解漢明碼的基本構成；理解循環(huán)碼 的概念，掌握其編解碼過程及如何用電路實現(xiàn)循環(huán)碼的 編解碼；了解卷積碼的概念及其代數(shù)表示方式。 清華大學出版社 第七章 信道編碼 7.1 信道編碼的基本概念 7.1.1 差錯控制編碼基本方式和類型 1. 常用差錯控制工作方式 按照噪聲或干擾所引起的錯碼分布規(guī)律的不同

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

3、控制編碼常稱為糾錯編碼。不同的編碼方式有 不同的檢錯或糾錯能力。有的編碼方法只能檢錯，不能 糾錯。一般來說，付出的代價越大，檢糾錯的能力就越 強。這里所指的代價，就是指增加的監(jiān)督碼元位數(shù)，它 通常用冗余度或多余度來衡量。設編碼序列中信息碼元 位數(shù)為 ，監(jiān)督碼元位數(shù)為 ，碼字位數(shù)為 ，則比 值 稱為編碼效率簡稱碼率又稱編碼速率，比值 稱為冗余度，比值 稱為多余度。 kr rkn nk /kr / nr / 清華大學出版社 第七章 信道編碼 2. 差錯控制編碼分類 差錯控制系統(tǒng)中使用的信道編碼可以有很多種。 (1)按照信息碼元和監(jiān)督碼元之間的函數(shù)關系可以分為線 性碼和非線性碼。 (2)按照信息碼元

4、和監(jiān)督碼元之間的約束關系涉及的范圍 可以分為分組碼和卷積碼。 (3)按照糾錯碼組中信息碼元是否隱蔽，可劃分為系統(tǒng)碼 和非系統(tǒng)碼。 (4)按照糾正錯誤的類型不同，可以分為糾正隨機錯誤的 碼和糾正突發(fā)錯誤的碼。 (5)按照構造差錯控制編碼的數(shù)學方法來分類，又可以分 為代數(shù)碼、幾何碼和算術碼。 清華大學出版社 第七章 信道編碼 7.1.2 碼重、碼距與檢錯、糾錯能力 差錯控制編碼的基本思想是在被傳輸?shù)男畔⒋a元中增加 一些監(jiān)督碼元，在兩者之間建立某種校驗關系，呈現(xiàn)某 種關聯(lián)性。當這種校驗關系因傳輸錯誤而受到破壞時， 可以被發(fā)現(xiàn)并予以糾正。這種檢錯和糾錯能力是用信息 量的冗余度來換取的。 清華大學出版社

5、 第七章 信道編碼 在信道編碼中，定義碼組中非零碼元的數(shù)目為碼組 的重量，簡稱碼重。 把兩個碼組中對應碼元位置上具有不同二進制碼元的 位數(shù)定義為兩個碼組的距離，稱為漢明距離，簡稱碼距。 一種編碼的最小碼距的大小直接關系著這種編碼的檢錯 和糾錯能力： (1) 為檢測 個錯碼，要求最小碼距為 (7-1) (2) 為了糾正 個錯碼，要求最小碼距為 (7-2) (3)為了糾正 個錯碼同時檢測 個錯碼，要求最小碼距 為 (7-3) 1 min ed 12 min td e t t e 1 min etd 清華大學出版社 第七章 信道編碼 7.1.3 幾種常用的差錯控制碼 1. 奇偶監(jiān)督碼 奇偶監(jiān)督碼又稱

6、奇偶校驗碼，分為奇數(shù)監(jiān)督和偶數(shù)監(jiān)督 兩種，兩者的原理相同，都是在原信息碼后面附加1個監(jiān) 督元，使得碼組中“1”的個數(shù)是奇數(shù)或者偶數(shù)。無論信 息位是多少位，監(jiān)督位或校驗位都只有1位。 清華大學出版社 第七章 信道編碼 2. 行列奇偶監(jiān)督碼 奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個錯誤。為了改善這種情況， 引入行列奇偶監(jiān)督碼，又稱二維奇偶監(jiān)督碼。這種編碼 不僅對水平方向的碼元，而且對垂直方向的碼元實施監(jiān) 督。行列奇偶監(jiān)督碼先把上述奇偶監(jiān)督碼的若干碼組， 每個寫成一行，然后再按列的方向增加每一列的監(jiān)督位， 如圖7.3所示。 清華大學出版社 第七章 信道編碼 圖7.5 行列奇偶監(jiān)督碼 3. 恒比碼 恒比碼又稱等重碼或

7、定“1”碼，它是從某確定碼長的碼 組中挑選那些“1”和“0”的比例為恒定值的碼組作為許 用碼組，即碼組中“1”和“0”的位數(shù)保持恒定的比例。 清華大學出版社 第七章 信道編碼 4. 群計數(shù)碼 群計數(shù)碼是將信息碼元分組后，計算每組碼元中“1”的 個數(shù)，然后將這個數(shù)目的二進制表示作為監(jiān)督碼元附加 在信息碼元之后組成碼字。 5重復碼 一種k=1的(n, k)分組碼，其編碼規(guī)則是n-1個監(jiān)督碼元均 是信息碼元的重復。 清華大學出版社 第七章 信道編碼 7.2 線性分組碼 7.2.1 線性分組碼的定義及性質 1定義 線性分組碼是一種同時具有分組特性和線性特性的糾錯 碼。 所謂分組特性是指將信碼進行分組，

8、并為每組信碼附加 若干監(jiān)督碼。分組碼一般用符號( )表示，其中 是一 個碼字(又稱碼組、碼矢)的總位數(shù)，又稱為碼組的長度， 是碼組中信息碼元的數(shù)目， 為碼組中監(jiān)督碼元的 數(shù)目。 kn,n rkn k 清華大學出版社 第七章 信道編碼 因此，分組碼的任一碼字A可表示為 其中 為信息碼元， 為監(jiān)督碼元。 在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。 所謂線性特性是指信息碼元與監(jiān)督碼元之間的關系 可以用一組線性方程式來表示，任一監(jiā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 清華大學出版社 第七章 信道編碼 (7-4) 3460 3561 4562 aaaa aaaa aaaa 清華大學出版社 第七章 信道編碼 從生成線性分組碼各碼字的角度看，可將(n,k)線性分組 碼的每一個碼字看成n維線性空間中的一個矢量。長為n 的碼字共有 個，它們組成一個n維的線性空間；而(n,k) 線性分組碼只有 個許用碼字( )，它們構成一個k維 的線性子空間。由此定義： (n,k)線性分組碼C是碼字A的n維向量的集合 (

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

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

12、 7.3.1 循環(huán)碼的含義與特點 線性分組碼中，有一種重要的碼稱為循環(huán)碼。它是 在嚴密的代數(shù)學理論基礎上建立起來的，是目前研究得 最成熟的一類碼。循環(huán)碼的編碼和解碼設備都不太復雜 (由循環(huán)性決定)，而且檢糾錯能力較強。循環(huán)碼還具有易 于實現(xiàn)的特點，很容易用帶反饋的移位寄存器實現(xiàn)其硬 件，而且性能較好，不但可用于糾正獨立的隨機錯誤， 也可以用于糾正突發(fā)錯誤。 清華大學出版社 第七章 信道編碼 7.3.2 循環(huán)碼的生成多項式、生成矩陣和 監(jiān)督矩陣 1生成多項式 循環(huán)碼完全由其碼組長度 及生成多項式 所決 定。對于(n,k)循環(huán)碼，可以證明， 具有以下性質： )(xg n )(xg )(xg 清華大

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

14、第七章 信道編碼 7.3.3 循環(huán)碼的編譯碼方法 1編碼過程及實現(xiàn) 生成循環(huán)碼的碼字有兩種方法：一種是利用生成矩 陣產(chǎn)生，一種是利用多項式除法產(chǎn)生。前者電路實現(xiàn)難 度較大，后者編碼電路實現(xiàn)比較簡單，且編碼沒有延遲。 下面介紹利用多項式除法產(chǎn)生碼字的原理及實現(xiàn)方法。 清華大學出版社 第七章 信道編碼 2譯碼過程及實現(xiàn) 循環(huán)碼的糾錯過程可按以下步驟進行： (1) 用生成多項式 去除接收碼組 ，得出 余式 。 (2) 按余式 用查表的方法或通過某種運算得到錯誤圖 樣 ，就可以確定錯碼位置。 (3) 從 中減去，便得到已糾正錯誤的原發(fā)送碼組 。 )(xg)()()(xExAxB )(xr )(xr )

15、(xE )(xE )(xB)(xA 7.4 卷 積 碼 7.4.1 卷積碼的基本原理 卷積碼編碼器一般原理框圖 清華大學出版社 第七章 信道編碼 7.4.2 卷積碼的代數(shù)表示 一個線性碼可以由一個監(jiān)督矩陣H或生成矩陣G所確 定。首先設在第一個信息位 進入編碼器之前，各級移 存器多處于“0”狀態(tài)，則監(jiān)督位 、 和信息位 之間 的關系可寫為 (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 清華大學出版社 第七章 信道編碼 7.4.3 卷積碼的圖形表示 卷積碼的譯碼方式中其大數(shù)邏

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

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

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