李梅李亦農(nóng)《信息論基礎(chǔ)教程》課件教案第六章有噪信道編碼.ppt

《李梅李亦農(nóng)《信息論基礎(chǔ)教程》課件教案第六章有噪信道編碼.ppt》由會員分享，可在線閱讀，更多相關(guān)《李梅李亦農(nóng)《信息論基礎(chǔ)教程》課件教案第六章有噪信道編碼.ppt（135頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第六章：有噪信道編碼,一、信道編碼的相關(guān)概念,二、有噪信道編碼定理,三、糾錯(cuò)編碼,,第六章：有噪信道編碼,信道編碼的目標(biāo)：提高通信的可靠性。,1. 信道編碼概述,信道編碼，就是按照一定的規(guī)則給信源編碼后的碼符號序列增加一些冗余信息，使其變成具有一定數(shù)學(xué)規(guī)律的碼符號序列。,信道譯碼，就是按與信道編碼器相同的數(shù)學(xué)規(guī)律去掉接收到的碼符號序列中的冗余符號。,通常來說，增加的冗余符號越多，檢錯(cuò)和糾錯(cuò)能力就越強(qiáng)。但是，增加的冗余符號越多，傳輸效率就越低。,信道編碼的相關(guān)概念,,信道編碼器： 將信源編碼后的符號加上冗余符號，提高傳輸?shù)目煽啃浴?,第六章：有噪信道編碼,1. 信道編碼概述（續(xù)1）,信道編碼的相

2、關(guān)概念,,,第六章：有噪信道編碼,1. 信道編碼概述（續(xù)2）,信道編碼的相關(guān)概念,圖1 編碼信道模型,,,,,,,,信道 編碼器,信道 譯碼器,信道,,,第六章：有噪信道編碼,2. 譯碼規(guī)則對錯(cuò)誤概率的影響,例1：,二進(jìn)制對稱信道,信道編碼的相關(guān)概念,,第六章：有噪信道編碼,2. 譯碼規(guī)則對錯(cuò)誤概率的影響（續(xù)1）,譯碼規(guī)則1：,信道譯碼器收到符號“0”譯為“0” 信道譯碼器收到符號“1”譯為“1” 正確譯碼概率0.1，錯(cuò)誤譯碼概率,信道編碼的相關(guān)概念,,第六章：有噪信道編碼,2. 譯碼規(guī)則對錯(cuò)誤概率的影響（續(xù)2）,譯碼規(guī)則2：,信道譯碼器收到符號“0”譯為“1” 信道譯碼器收到符號“1”譯為“

3、0”,信道編碼的相關(guān)概念,正確譯碼概率0.9，錯(cuò)誤譯碼概率,,第六章：有噪信道編碼,定義6.1 設(shè)信道的輸入符號集為 ，輸出符號集為 。若對每一個(gè)輸出符號都有一個(gè)確定的函數(shù) ，使對應(yīng)于唯一的一個(gè)輸入符號 ，則稱這樣的一個(gè)函數(shù)為譯碼規(guī)則，記為,3. 譯碼規(guī)則,信道編碼的相關(guān)概念,,第六章：有噪信道編碼,3. 譯碼規(guī)則（續(xù)1）,,,,信道,,共有rs 種譯碼規(guī)則,,信道編碼的相關(guān)概念,譯碼規(guī)則,例：,3. 譯碼規(guī)則（續(xù)2）,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,,第六章：有噪信道編碼,3. 譯碼規(guī)則（續(xù)3）,,例2：設(shè)一個(gè)信道的信道矩陣為 ，根據(jù)

4、此信道矩陣，設(shè)計(jì)譯碼規(guī)則。,解：,,,,,譯碼規(guī)則A,,,,,譯碼規(guī)則B,信道編碼的相關(guān)概念,對于有r個(gè)輸入符號，s個(gè)輸出符號的信道，總共可以設(shè)計(jì)出 種譯碼規(guī)則，到底哪一種譯碼規(guī)則最好？依據(jù)什么標(biāo)準(zhǔn)來選擇譯碼規(guī)則？,問題：,3. 譯碼規(guī)則（續(xù)4）,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,4. 錯(cuò)誤譯碼概率,,設(shè)譯碼規(guī)則為,,,當(dāng)輸入符號是xi時(shí)，,譯碼正確,當(dāng)輸入符號為除xi以外的(r-1)種符號時(shí)，,譯碼錯(cuò)誤,正確譯碼的概率：,錯(cuò)誤譯碼的概率：,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,4. 錯(cuò)誤譯碼概率（續(xù)1）,平均正確譯碼概率：,平均錯(cuò)誤譯碼概率：,,第六章：有噪信道編碼,,信

5、道編碼的相關(guān)概念,5. 兩種重要的譯碼規(guī)則,為提高規(guī)則通信的可靠性，所采用的譯碼應(yīng)當(dāng)使平均錯(cuò)誤譯碼概率最小。---- 最大后驗(yàn)概率譯碼規(guī)則 最常用的譯碼規(guī)則，包括：,極大似然譯碼規(guī)則,最大后驗(yàn)概率譯碼規(guī)則,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,5. 兩種重要的譯碼規(guī)則（續(xù)1）,(1) 最大后驗(yàn)概率譯碼規(guī)則,已知：,當(dāng)求和項(xiàng)中的每一項(xiàng)都達(dá)到最小值時(shí)， 就最小。,要最小。,要最大。,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,定義6. 2 令 ， ，而 應(yīng)滿足條件,5. 兩種重要的譯碼規(guī)則（續(xù)2）,稱滿足上述條件的譯碼函數(shù)對應(yīng)的譯碼規(guī)則為最大后驗(yàn)概率譯碼規(guī)則。,,第

6、六章：有噪信道編碼,,信道編碼的相關(guān)概念,5. 兩種重要的譯碼規(guī)則（續(xù)3）,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,,,,5. 兩種重要的譯碼規(guī)則（續(xù)4）,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,,,,5. 兩種重要的譯碼規(guī)則（續(xù)5）,問題：,最大后驗(yàn)概率 通常是未知的，使用不方便。我們能否推導(dǎo)出更便于使用的譯碼規(guī)則?,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,5. 兩種重要的譯碼規(guī)則（續(xù)6）,當(dāng)輸入符號等概分布時(shí),(2) 極大似然譯碼規(guī)則,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,,第六章：有噪信道編碼,5. 兩種重要的譯碼規(guī)則（續(xù)7）,1)當(dāng)輸入符號等概分布時(shí)，

7、采用極大似然譯碼準(zhǔn)則等價(jià)于最大后驗(yàn)概率準(zhǔn)則。,2)當(dāng)輸入符號不等概分布或先驗(yàn)概率未知時(shí)，采用極大似然譯碼準(zhǔn)則不一定使 最小。,關(guān)于極大似然譯碼準(zhǔn)則：,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,5. 兩種重要的譯碼規(guī)則（續(xù)8）,當(dāng)輸入符號等概分布時(shí),,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,,,,5. 兩種重要的譯碼規(guī)則（續(xù)9）,例3： 設(shè)信道矩陣為 ，且輸入符號等概分布，即 ，求譯碼規(guī)則和平均錯(cuò)誤譯碼概率。,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,5. 兩種重要的譯碼規(guī)則（續(xù)10）,解： 因?yàn)檩斎敕枮榈雀欧植?，所以由最大似然譯碼規(guī)則可得,,,,

8、,譯碼規(guī)則,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,5. 兩種重要的譯碼規(guī)則（續(xù)11）,,,,,譯碼規(guī)則 A,,,,,譯碼規(guī)則 B,例 6.3 假設(shè)輸入等概，求以下兩種 譯碼規(guī)則的平均錯(cuò)誤譯碼概率。,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,5. 兩種重要的譯碼規(guī)則（續(xù)12）,,,,,,,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,5. 兩種重要的譯碼規(guī)則（續(xù)13）,,,,,,,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,5. 兩種重要的譯碼規(guī)則（續(xù)14）,,,,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,6. Fano不等式,定理6.1 平均錯(cuò)誤概率與信道疑義度H(X|Y)滿

9、足不等式：,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,7. 簡單重復(fù)編碼,,,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,7. 簡單重復(fù)編碼（續(xù)1）,,,,二元對稱信道 的三次擴(kuò)展信道,M =2,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,,,,,,,,,由最大似然譯碼規(guī)則，可得,7. 簡單重復(fù)編碼（續(xù)2）,自動糾正一位錯(cuò),,,,,,,,,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,7. 簡單重復(fù)編碼（續(xù)3）,在輸入符號集（M個(gè)符號）等概的條件下，每個(gè)符號平均攜帶的最大信息量是 。 當(dāng)用n個(gè)碼元符號來傳輸M個(gè)信源符號時(shí)，每個(gè)碼符號攜帶的平均信息量，即信道信息傳輸率為：,不重復(fù)編碼

10、時(shí)(n=1)， 重復(fù)編碼時(shí)(n=3)，,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,n =1, R=1, n =3, R=1/3, n =5, R =1/5, n =7, R =1/7, n =9, R =1/9, n =11, R =1/11, 增加重復(fù)次數(shù)n，可使 減小很多，但信息傳輸率R也減少很多。,7. 簡單重復(fù)編碼（續(xù)4）,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,7. 簡單重復(fù)編碼（續(xù)5）,,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,,,,,,,,如果在擴(kuò)展信源的 個(gè)碼符號序列中任意選擇M個(gè)序列作為信道的輸入，以代表M個(gè)信源消息。,因此若選擇“000”和“001”代

11、表消息“0”和“1”，則,7. 簡單重復(fù)編碼（續(xù)6）,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,有沒有一種很簡便的方法，幫我們選擇平均錯(cuò)誤概率最小的M個(gè)序列？,7. 簡單重復(fù)編碼（續(xù)7）,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,8. 漢明距離,1）漢明距離,2）碼的最小距離,3）漢明距離與極大似然譯碼準(zhǔn)則,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,8. 漢明距離（續(xù)1）,定義6.4 設(shè) 和 表示兩個(gè)長度為n的碼符號序列，定義,稱 為碼字 和 之間的漢明距離。,1）漢明距離,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,8. 漢明距離（續(xù)2）,例4：

12、求下面兩個(gè)碼字之間的漢明距離。,解：,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,8. 漢明距離（續(xù)3）,定義6.5 在二元碼C中，任意兩個(gè)碼字之間的漢明距離的最小值，被稱為碼C的最小距離：,2）碼的最小距離,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,8. 漢明距離（續(xù)4）,例5：設(shè)有n=3的兩組碼，分別求它們的最小漢明距離。,解：,碼 的最小漢明距離為,碼 的最小漢明距離為,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,8. 漢明距離（續(xù)5）,,8. 漢明距離（續(xù)7）,結(jié)論：,碼的最小距離越大，平均譯碼錯(cuò)誤概率越小。,,第六章：有噪信道編碼

13、,,信道編碼的相關(guān)概念,設(shè) 和 表示兩個(gè)長度為n的碼符號序列， 為信道的輸入， 為信道的輸出。 和 的漢明距離為D。,8. 漢明距離（續(xù)8）,3) 漢明距離與極大似然譯碼準(zhǔn)則,對于離散平穩(wěn)無記憶二元對稱信道，有,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,通常情況下， ， ，D越小， 就越大。,8. 漢明距離（續(xù)9）,根據(jù)極大似然譯碼準(zhǔn)則，,極大似然譯碼準(zhǔn)則就等價(jià)于，當(dāng)接收到一個(gè)長為n的碼符號序列 時(shí)，在輸入碼字集中尋找一個(gè) ，使,,第六章：有噪信道編碼,,信道編碼的相關(guān)概念,最小距離譯碼準(zhǔn)則,,1. 有噪信道編碼定理,定理6.2 （香農(nóng)第二定理） 設(shè)有一

14、離散無記憶平穩(wěn)信道，其信道容量為C，只要待傳送的信息傳輸率R

15、編碼定理,1. 有噪信道編碼定理（續(xù)3）,信道容量是在信道中可靠傳輸信息的最大信息傳輸率。,結(jié)論：,,第六章：有噪信道編碼,,有噪信道編碼定理,2. 錯(cuò)誤概率的上界,,第六章：有噪信道編碼,,有噪信道編碼定理,,,糾錯(cuò)編碼,1 糾錯(cuò)碼的分類,2 糾錯(cuò)碼的基本概念,3 線性分組碼,4 漢明碼,5 循環(huán)碼,*6 卷積碼,概述,香農(nóng)第二定理證明，當(dāng) 時(shí) 的碼存在。 證明過程采用的是隨機(jī)編碼的方法： 隨機(jī)編碼所得的碼集很大，通過搜索得到好碼的方法在實(shí)際上很難實(shí)現(xiàn)； 即使找到了好碼，這種碼的碼字也沒有規(guī)律，不便于譯碼。 真正實(shí)用的信道編碼方法還需要通過各種數(shù)學(xué)工具來構(gòu)造，使碼具有好的結(jié)構(gòu)性以便于譯碼

16、。,近世代數(shù)是信道編碼理論用到的最重要的數(shù)學(xué)工具，它包括群論、環(huán)論、域論、格論、線性代數(shù)等許多分支。 廣義信道編碼包括：調(diào)制、成形濾波、擴(kuò)頻、上下變頻等。 糾錯(cuò)編碼是提高傳輸可靠性的最主要的措施之一。,概述,糾錯(cuò)編碼的基本思路： 根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加入一些冗余碼元，這些冗余碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）。 在接收端按照既定的規(guī)則檢驗(yàn)信息碼元與監(jiān)督碼元之間的關(guān)系。如果傳輸過程出錯(cuò)，則信息碼元與監(jiān)督碼元之間的關(guān)系將受到破壞，從而可以發(fā)現(xiàn)錯(cuò)誤乃至糾正錯(cuò)誤。,概述,,,,,E,,概述,,m msg,C code,R noisycode

17、,newmsg,干擾一般分為兩種形式： 一是隨機(jī)噪聲，它主要來源于設(shè)備的熱噪聲和散彈噪聲以及傳播媒介的熱噪聲，它是通信系統(tǒng)中的主要噪聲； 二是脈沖干擾和信道衰落，它的特點(diǎn)是突發(fā)出現(xiàn)，主要來源于雷電、通電開關(guān)、負(fù)荷突變或設(shè)備故障等。,概述,信道可分為三類： 1. 只產(chǎn)生隨機(jī)錯(cuò)誤的信道稱為隨機(jī)信道。比如衛(wèi)星信道、同軸電纜、光纜信道以及大多數(shù)微波中繼信道。 2. 產(chǎn)生突發(fā)錯(cuò)誤的信道稱為突發(fā)信道。實(shí)際的短波信道、移動通信信道、由于擦傷造成成串差錯(cuò)的光盤和磁盤，均為這一類信道。 3. 有些實(shí)際信道既有隨機(jī)錯(cuò)誤又有突發(fā)錯(cuò)誤，稱為混合信道。,根據(jù)不同的信道類型設(shè)計(jì)的信道編碼分為糾隨機(jī)錯(cuò)誤碼、糾突發(fā)錯(cuò)誤碼和糾

18、混合錯(cuò)誤碼。,概述,在通信系統(tǒng)中，糾檢錯(cuò)的工作方式有： (1) 反饋重傳(ARQ) (2) 前向糾錯(cuò)(FEC) (3) 混合糾錯(cuò),概述,發(fā)送端經(jīng)編碼后發(fā)出能夠發(fā)現(xiàn)錯(cuò)誤的碼，接收端收到后經(jīng)檢驗(yàn)，如果發(fā)現(xiàn)傳輸中有錯(cuò)誤，則通過反饋系統(tǒng)把這一判斷結(jié)果反饋回發(fā)端，然后發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認(rèn)為正確地收到信息為止。,(1) 反饋重傳(ARQ),,,,,,,,,,,檢錯(cuò) 編碼,信道,檢錯(cuò) 譯碼,反饋,概述,(2) 前向糾錯(cuò)(FEC),,,,,,,,糾錯(cuò) 編碼,信道,糾錯(cuò) 譯碼,發(fā)送端發(fā)出的是具有糾錯(cuò)能力的糾錯(cuò)碼，接收端根據(jù)譯碼規(guī)則進(jìn)行譯碼。當(dāng)誤碼個(gè)數(shù)在碼的糾錯(cuò)能力范圍內(nèi)時(shí)，譯碼器可以

19、自動糾正錯(cuò)誤。,概述,特點(diǎn)：,1）前向糾錯(cuò)方式不需要反饋信道，特別適合于只能 提供單向信道的場合。 2）由于能自動糾錯(cuò)，不要求檢錯(cuò)重發(fā)，因而延時(shí)小， 實(shí)時(shí)性好。 3）隨著糾錯(cuò)能力的增強(qiáng)，譯碼設(shè)備也變得復(fù)雜。,概述,(3) 混合糾錯(cuò),對發(fā)送端進(jìn)行適當(dāng)?shù)木幋a。當(dāng)錯(cuò)誤不嚴(yán)重，在碼的糾錯(cuò)能力范圍之內(nèi)時(shí)，采用自動糾錯(cuò)；當(dāng)產(chǎn)生的差錯(cuò)超出碼的糾錯(cuò)能力范圍時(shí)，通過反饋系統(tǒng)要求發(fā)端重發(fā)。,概述,(1) 按功能分： 檢錯(cuò)碼：僅能檢測誤碼 糾錯(cuò)碼：可糾正誤碼 糾刪碼：兼糾錯(cuò)和檢錯(cuò)能力 (2) 按信息碼元與監(jiān)督碼元之間的檢驗(yàn)關(guān)系分： 線性碼：滿足線性關(guān)系 非線性碼：不存在線性關(guān)系,,,糾錯(cuò)碼,1 糾錯(cuò)碼的分類,(3)

20、 按信息碼元與監(jiān)督碼元之間的約束方式不同分：,分組碼：本碼組的監(jiān)督碼元僅和本碼組的信息元相關(guān)。,樹碼：本碼組的監(jiān)督碼元不僅和本碼組的信息元相關(guān)，而且與前面碼組的信息碼元有關(guān)。如果是線性關(guān)系則稱為卷積碼。,(4) 按信息碼元在編碼后是否保持原形式不變：,系統(tǒng)碼：信息碼元與監(jiān)督碼元在分組內(nèi)有確定位置， 編碼后的信息碼元保持不變；,非系統(tǒng)碼：信息位打亂，與編碼前不同。,1 糾錯(cuò)碼的分類,(5)按糾正差錯(cuò)的類型可分為： 糾隨機(jī)錯(cuò)誤碼 糾突發(fā)錯(cuò)誤碼 糾隨機(jī)和突發(fā)錯(cuò)誤碼,1 糾錯(cuò)碼的分類,,糾錯(cuò)碼按結(jié)構(gòu)分類如下：,1 糾錯(cuò)碼的分類,分組碼的表示方法： （二元分組碼） 信息碼組由 k 個(gè)信息碼元（信息位

21、）組成，共有 2k 個(gè)不同的信息碼組； 附加 個(gè)校驗(yàn)碼元（校驗(yàn)位或監(jiān)督位），每個(gè)校驗(yàn)碼元是該信息碼組的某些信息碼元模2和； 編碼器輸出長度為n的碼字； 碼字的數(shù)目共有 2k ； 這2k 個(gè)碼字的集合稱為 (n,k) 分組碼；,2 糾錯(cuò)碼的基本概念,對 二進(jìn)制(n, k)線性分組碼，合法碼字?jǐn)?shù)為2k，可用編碼空間的序列數(shù)為2n個(gè)。許用序列 ，禁用序列 任一種2k信息集合到二進(jìn)制序列集合(2n)的映射都是一種(n, k)碼 ，因此總共可能的編碼方案有 種。,2 糾錯(cuò)碼的基本概念,信息傳輸率（碼率） 編碼效率,發(fā)現(xiàn)或構(gòu)造好碼是信道編碼研究的主要問題。,線性分組碼是最具實(shí)用價(jià)值的一類碼，比如

22、漢明碼、循環(huán)碼、BCH碼、RS碼等。,2 糾錯(cuò)碼的基本概念,2 糾錯(cuò)碼的基本概念,對信道編碼的一般要求是： 糾錯(cuò)檢錯(cuò)能力強(qiáng)； 信息傳輸率高； 編碼規(guī)律簡單，實(shí)現(xiàn)設(shè)備簡單且費(fèi)用合理； 與信道的差錯(cuò)統(tǒng)計(jì)特性相匹配。,漢明距離,,,,,漢明距離滿足距離公理 (1)非負(fù)性 對稱性 (3) 三角不等式,,,,2 糾錯(cuò)碼的基本概念,漢明重量,,碼C 的最小距離,線性分組碼的最小距離等于非零碼字的最小重量。,2 糾錯(cuò)碼的基本概念,2 糾錯(cuò)碼的基本概念,3 線性分組碼,,,,,,,3.1 校驗(yàn)矩陣與生成矩陣,(1) 校驗(yàn)矩陣,,3 線性分組碼,,被稱為校驗(yàn)矩陣。 對 線性分組碼，校驗(yàn)矩陣為 維

23、矩陣。 對于系統(tǒng)碼，校驗(yàn)矩陣可以表示為,其中 為 維矩陣， 為 維單位矩陣。,3 線性分組碼,,,,由校驗(yàn)方程，得到,(2) 生成矩陣,3 線性分組碼,,令,,3 線性分組碼,其中 為 維矩陣， 為 維單位矩陣。,被稱為生成矩陣。 對 線性分組碼，生成矩陣為 維矩陣。 對于系統(tǒng)碼，生成矩陣可以表示為,3 線性分組碼,,把生成矩陣的每一行用一個(gè)行向量 來表示，則生成矩陣可以表示為,令 ，則,3 線性分組碼,由于生成矩陣G的每一行都是一個(gè)碼字，所以G 的每行都滿足 ，則有 對于標(biāo)準(zhǔn)形式的校驗(yàn)矩陣和監(jiān)督矩陣，有,(3) 校驗(yàn)矩

24、陣和生成矩陣的關(guān)系,3 線性分組碼,線性分組碼的封閉性：線性分組碼中任意兩個(gè)碼字之和仍然是該碼的碼字。,證明：設(shè) 和 分別是碼 中的兩個(gè)碼字，因此有,即 滿足監(jiān)督方程，所以是碼 中的一個(gè)碼字。,3 線性分組碼,例1：3重復(fù)碼是一個(gè)（3,1）線性分組碼。其生成矩陣為,,,,3 線性分組碼,例2：（4,3）偶校驗(yàn)碼是一個(gè)（4,3）線性分組碼，其生成矩陣為,3 線性分組碼,例3： 已知生成矩陣為 求生成的線性分組碼及由H 生成的線性 分組碼。,,,3 線性分組碼,3 線性分組碼,,1111111,1111,1001110,1110,0011101,1101,0101100,1100,0001

25、011,1011,0111010,1010,1101001,1001,1011000,1000,0100111,0111,0010110,0110,1000101,0101,1110100,0100,1010011,0011,1100010,0010,0110001,0001,0000000,0000,C,m,3 線性分組碼,3.2 線性分組碼的糾、檢錯(cuò)能力,對于一個(gè)二進(jìn)制對稱信道，當(dāng)輸入為2k個(gè)等可能的n長碼字，則最大后驗(yàn)概率準(zhǔn)則等效于最小漢明距離譯碼準(zhǔn)則。,,,,,3 線性分組碼,關(guān)于碼的最小距離與糾、檢錯(cuò)能力的關(guān)系有以下結(jié)論：對于（n，k）線性分組碼，設(shè) 為碼的最小距離則 （）這組碼

26、有糾正 u 個(gè)錯(cuò)誤的充要條件是,,,,,,,,,u,u,,,,,2u+1,3 線性分組碼,,,,,,,,,,l,l,,,,,l+1,,（）具有檢測l個(gè)錯(cuò)誤的充要條件是,3 線性分組碼,,,,,,,,,,,u,l,,,,,u+l+1,（）具有糾正 u 個(gè)錯(cuò)誤，同時(shí)可以發(fā)現(xiàn)l個(gè)錯(cuò)誤的充分必要條件為,3 線性分組碼,,,碼的糾錯(cuò)能力u與碼字的長度n和消息數(shù)M滿足以下關(guān)系：,3 線性分組碼,3.3 校驗(yàn)矩陣與碼的最小距離的關(guān)系,對于（n，k）線性分組碼： 校驗(yàn)矩陣H中的任意t列線性無關(guān)而t+1列線 性相關(guān)，則碼的最小距離(碼字的最小重量) 為t+1。 反過來說，若碼的最小距離(碼字的最小重量) 為t+

27、1則H 的任意t列線性無關(guān)而t+1列線性相關(guān)。,3 線性分組碼,3.4 線性分組碼的伴隨式,,,R=C+E E=e1 e2 en,,1) ，說明R 是一個(gè)碼字; 2) ，說明R 不是碼字，傳輸過程產(chǎn)生了誤碼。,3 線性分組碼,例：某（5,2）系統(tǒng)線性碼的生成矩陣是 設(shè)收碼是 ，問它是否是碼字。,3 線性分組碼,令,則,（其中 表示 的列向量）,3 線性分組碼,結(jié)論：,1) 當(dāng)傳輸過程沒有錯(cuò)誤時(shí) ，即 ， 2)當(dāng)發(fā)生一位錯(cuò)誤時(shí)， 是校驗(yàn)矩陣的某一列。 3)當(dāng)發(fā)生多個(gè)錯(cuò)誤時(shí)， 為校驗(yàn)矩陣對應(yīng)列的模2和。,例： 設(shè)(7,3)線性分組碼的校驗(yàn)矩陣為,3 線性

28、分組碼,（1）接收碼字R=(1010011)，,傳輸過程中沒有誤碼，,3 線性分組碼,（2）接收碼字R=(1110011)，,，第2位出錯(cuò)，,3 線性分組碼,（3）接收碼字R=(0011011)，,與 中的任一列都不相同，,不能確定到底是哪兩位出錯(cuò)，不能正確譯碼。,3 線性分組碼,線性分組碼的伴隨式譯碼,,,3 線性分組碼,3 線性分組碼,,若（n，k）線性分組碼能夠糾正 u 個(gè)錯(cuò)誤，則其校驗(yàn)位的數(shù)目必須滿足,4 漢明碼,上式等號成立則稱為完備碼,如果是能糾正一位錯(cuò)誤的完備碼則,完備碼具有下述特性： （1）以每個(gè)發(fā)送碼字為球心，以u為半徑畫一個(gè)球，那么每一個(gè)接收碼字都落在其中一個(gè)球中，因此接

29、收碼字與發(fā)送碼字的距離至多為u； （2）所有差錯(cuò)數(shù)小于等于u的接收碼字都能得到糾正； （3）差錯(cuò)數(shù)大于等于u+1的接收碼字，因?yàn)槁湓诹硪粋€(gè)球內(nèi)被糾正為其他的發(fā)送碼字。 完備碼并不多見，我們知道的有u=1的漢明碼、u=3的高萊碼，以及(n,1)中n為奇數(shù)的重復(fù)碼等。,4 漢明碼,完備碼,非完備碼,000,111,,,000,001,010,100,111,110,101,011,00000,01101,,00000,00001,00010,00100,01000,10000,00011,10011,,01101,01100,01111,01001,00101,11101,01110,11100

30、,10111,,10111,. . .,11010,,11010,. . .,4 漢明碼,,,,漢明碼是一種能夠糾正單個(gè)錯(cuò)誤的完備碼。 漢明碼最小碼距 設(shè)監(jiān)督碼共有r 位，對于漢明碼必然有 。 通常漢明碼可以表示成 。,4 漢明碼,在同樣的糾錯(cuò)能力下，漢明碼的碼率是最高的,漢明碼監(jiān)督矩陣構(gòu)成的兩種方式： 按 r 位的二進(jìn)制數(shù)的自然順序從左到右排列（不包括全0列）。當(dāng)發(fā)生可糾的單個(gè)錯(cuò)誤時(shí)，伴隨式為 H 陣中對應(yīng)的列，譯碼比較方便。 構(gòu)成 H 陣的標(biāo)準(zhǔn)形式， 。非標(biāo)準(zhǔn)形式的監(jiān)督矩陣可以通過列置換變成標(biāo)準(zhǔn)形式的監(jiān)督矩陣，糾錯(cuò)能力保持不變。,4 漢明碼,例：構(gòu)造一個(gè)r=3的

31、二元（7,4）漢明碼,解：r=3的漢明碼，,,列置換,,4 漢明碼,,4 漢明碼,4 漢明碼,如果給漢明碼添加一位奇偶校驗(yàn)位，可得到擴(kuò)展?jié)h明碼： 信息位保持不變，監(jiān)督位增加一位。 最小碼距 ， 可糾正一位錯(cuò)誤，同時(shí)發(fā)現(xiàn)兩位錯(cuò)誤。,擴(kuò)展?jié)h明碼的監(jiān)督方程：,4 漢明碼,,,5 循環(huán)碼,循環(huán)碼是線性分組碼的一個(gè)重要子集。,循環(huán)碼除了具有線性分組碼的一般性質(zhì)外，還具有循環(huán)性：循環(huán)碼中任一碼字經(jīng)過循環(huán)移位后，所得到的碼字仍然是該碼的碼字。,循環(huán)碼有嚴(yán)密的代數(shù)學(xué)理論基礎(chǔ)，檢錯(cuò)和糾錯(cuò)能力較強(qiáng)，而且編碼和解碼設(shè)備都不太復(fù)雜。,5 循環(huán)碼,5 循環(huán)碼,,,,,,1)對于二進(jìn)制碼，碼多項(xiàng)式的

32、每個(gè)系數(shù)不是0就是1。 2) 僅是碼元位置的標(biāo)記。我們并不關(guān)心 的取值。,設(shè)循環(huán)碼的碼字為 ，用碼多項(xiàng)式表示為,碼字（1100101）可以表示為：,,5 循環(huán)碼,循環(huán)碼的循環(huán)特性可以用碼多項(xiàng)式來證明：,在整數(shù)運(yùn)算中，有模n運(yùn)算。若一個(gè)整數(shù)m可以表示為:,則,在模n運(yùn)算下，一整數(shù)m等于其被n除所得的余數(shù)。,5 循環(huán)碼,在碼多項(xiàng)式運(yùn)算中也有類似的按模運(yùn)算法則。 若一任意多項(xiàng)式 M(x)被一個(gè)n次多項(xiàng)式 N(x) 除，得到商式 Q(x)和一個(gè)次數(shù)小于 n 的余式 P(x) ，也就是： 則可以寫為：,在循環(huán)碼中，若 是一個(gè)長為n的許用碼字，則 在模 運(yùn)算下，也是一個(gè)許用碼字。,

33、5 循環(huán)碼,例: 某循環(huán)碼的一個(gè)碼字為1100101，則 若將此碼左移一位，得： 對應(yīng)的碼字為1001011(即將碼字1100101循環(huán)左移一位）。,5 循環(huán)碼,5 循環(huán)碼,從碼中取出一個(gè)前面k-1位都是0的碼字，定義這個(gè)碼字的碼多項(xiàng)式為生成多項(xiàng)式 。,在 循環(huán)碼中，除了全0碼字以外，其他碼字的連0個(gè)數(shù)最多只有k-1個(gè)。,生成多項(xiàng)式的次數(shù)為 ，且常數(shù)項(xiàng)不為0。,5 循環(huán)碼,為了保證構(gòu)成的生成矩陣G的各行線性不相關(guān)，通常用 這樣來構(gòu)造生成矩陣。,5 循環(huán)碼,,,k-1 個(gè) 0,,,5 循環(huán)碼,設(shè)信息碼元為 時(shí)，由生成矩陣得到相應(yīng)碼字的碼多項(xiàng)式：,所有碼多項(xiàng)式必定為 的倍式。,5 循環(huán)碼,5 循環(huán)碼,一致校驗(yàn)多項(xiàng)式,,,,,,,5 循環(huán)碼,循環(huán)碼的伴隨多項(xiàng)式 就是用接收碼多項(xiàng)式除以生成多項(xiàng)式 所得的余式。,譯碼可分為三步：,1)由接收到的碼多項(xiàng)式 計(jì)算伴隨多項(xiàng)式 ； 2)由伴隨多項(xiàng)式 確定錯(cuò)誤圖樣 ； 3)將錯(cuò)誤圖樣 與 相加，糾正錯(cuò)誤。,5 循環(huán)碼,,,,,,信息序列 碼序列,6 卷積碼,,,,6 卷積碼,,,,,,6 卷積碼,,,,,,6 卷積碼,,6 卷積碼,,R=C+E E=e1 e2 en,6 卷積碼,