【正文】 錯(cuò)誤碼 ? 糾隨機(jī)和突發(fā)錯(cuò)誤碼 1 糾錯(cuò)碼的分類 ???????????? ?????????非線性卷積碼線性樹碼非線性非循環(huán)碼循環(huán)碼線性分組碼糾錯(cuò)碼糾錯(cuò)碼按結(jié)構(gòu)分類如下： 1 糾錯(cuò)碼的分類 l 分組碼的表示方法： （ 二元分組碼） ?信息碼組由 k 個(gè)信息碼元（ 信息位） 組成，共有 2k 個(gè)不同的信息碼組； ?附加 個(gè)校驗(yàn)碼元（ 校驗(yàn)位或監(jiān)督位） ，每個(gè)校驗(yàn)碼元是該信息碼組的某些信息碼元模 2和； ?編碼器輸出長(zhǎng)度為 n的碼字； ?碼字的數(shù)目共有 2k ； ?這 2k 個(gè)碼字的集合稱為 (n,k) 分組碼； r n k??2 糾錯(cuò)碼的基本概念 ? 對(duì) 二進(jìn)制 (n, k)線性分組 碼，合法碼字?jǐn)?shù)為 2k，可用編碼空間的 序列 數(shù)為 2n個(gè)。如果是線性關(guān)系則稱為卷積碼。 概述 (1) 按功能分： ? 檢錯(cuò)碼：僅能檢測(cè)誤碼 ? 糾錯(cuò)碼：可糾正誤碼 ? 糾刪碼：兼糾錯(cuò)和檢錯(cuò)能力 (2) 按信息碼元與監(jiān)督碼元之間的檢驗(yàn)關(guān)系分： ? 線性碼：滿足線性關(guān)系 ? 非線性碼：不存在線性關(guān)系 糾錯(cuò)碼 1 糾錯(cuò)碼的分類 (3) 按信息碼元與監(jiān)督碼元之間的約束方式不同分： ? 分組碼：本碼組的監(jiān)督碼元僅和本碼組的信息元相關(guān)。 概述 (3) 混合糾錯(cuò) 對(duì)發(fā)送端進(jìn)行適當(dāng)?shù)木幋a。 2）由于能自動(dòng)糾錯(cuò)，不要求檢錯(cuò)重發(fā)，因而延時(shí)小， 實(shí)時(shí)性好。當(dāng)誤碼個(gè)數(shù)在碼的糾錯(cuò)能力范圍內(nèi)時(shí)，譯碼器可以自動(dòng)糾正錯(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)為正確地收到信息為止。 3. 有些實(shí)際信道既有隨機(jī)錯(cuò)誤又有突發(fā)錯(cuò)誤，稱為混合信道。 2. 產(chǎn)生突發(fā)錯(cuò)誤的信道稱為突發(fā)信道 。 概述 信道可分為三類： 1. 只產(chǎn)生隨機(jī)錯(cuò)誤的信道稱為隨機(jī)信道 。如果傳輸過程出錯(cuò)，則信息碼元與監(jiān)督碼元之間的關(guān)系將受到破壞，從而可以發(fā)現(xiàn)錯(cuò)誤乃至糾正錯(cuò)誤。 概述 l 糾錯(cuò)編碼的 基本思路 ： 根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加入一些 冗余碼元， 這些 冗余 碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）。 l 廣義信道編碼包括：調(diào)制、成形濾波、擴(kuò)頻、上下變頻等。 l 真正實(shí)用的信道編碼方法還需要通過各種數(shù)學(xué)工具來構(gòu)造，使碼具有好的結(jié)構(gòu)性以便于譯碼。 結(jié)論： 第六章：有噪信道編碼 有噪信道編碼定理 )](e x p [ RnEP rE ??2. 錯(cuò)誤概率的上界 第六章：有噪信道編碼 有噪信道編碼定理 糾錯(cuò)編碼 1 糾錯(cuò)碼的分類 2 糾錯(cuò)碼的基本概念 3 線性分組碼 4 漢明碼 5 循環(huán)碼 *6 卷積碼 概述 l 香農(nóng)第二定理證明，當(dāng) 時(shí) 的碼存在。 l o g MRn? 比 特 / 碼 符 號(hào)第六章：有噪信道編碼 有噪信道編碼定理 1. 有噪信道編碼定理（續(xù) 2） 定理 （有噪信道編碼逆定理） 設(shè)有一離散無(wú)記憶平穩(wěn)信道，其信道容量為 C，如果信息傳輸率 RC，即 ，則無(wú)論碼長(zhǎng) n 取多大，也不可能使譯碼錯(cuò)誤概率任意小。 ? ? ( | )jip yx8. 漢明距離（續(xù) 9） 根據(jù)極大似然譯碼準(zhǔn)則， *( | ) ( | )j j ip p i??y x y x? 極大似然譯碼準(zhǔn)則就等價(jià)于，當(dāng)接收到一個(gè)長(zhǎng)為 n的碼符號(hào)序列 時(shí)，在輸入碼字集中尋找一個(gè) ，使 jy*x第六章：有噪信道編碼 信道編碼的相關(guān)概念 *)( xy ?jF ),(),( * jij DD yxyx ?最小距離譯碼準(zhǔn)則 1. 有噪信道編碼定理 定理 （香農(nóng)第二定理） 設(shè)有一離散無(wú)記憶平穩(wěn)信道，其信道容量為 C，只要待傳送的信息傳輸率 RC，當(dāng)碼長(zhǎng) n 足夠大時(shí)，則至少存在一種編碼，使譯碼錯(cuò)誤概率任意小。 和 的漢明距離為 D。 0000111011100000010101001C 2Cmin 2D ?解： 碼 的最小漢明距離為 1Cmin 1D ?碼 的最小漢明距離為 2C第六章：有噪信道編碼 信道編碼的相關(guān)概念 碼 1 碼 2 碼 3 碼 4 碼 5 碼 6 000 111 000 001 000 011 101 110 000 001 100 010 00000 01101 10111 11010 000 001 010 011 100 101 110 111 第六章：有噪信道編碼 信道編碼的相關(guān)概念 8. 漢明距離（續(xù) 5） 碼 1 碼 2 碼 3 碼 4 碼 5 碼字 000 111 000 011 101 110 000 001 100 010 00000 01101 10111 11010 000 001 010 011 100 101 110 111 消息數(shù)M 2 4 4 4 8 信息傳輸率 R 1/3 2/3 2/3 2/5 1 碼的最小距離 3 2 1 3 1 平均 錯(cuò)誤概率 （ 最大似 然譯碼 ） 43 10??mindEP22 10?? 22 .2 8 1 0 ?? 47 .8 1 0 ?? 23 10??8. 漢明距離（續(xù) 7） 結(jié)論： 碼的最小距離越大，平均譯碼錯(cuò)誤概率越小。 ix jy1）漢明距離 ( , )ijD xy第六章：有噪信道編碼 信道編碼的相關(guān)概念 8. 漢明距離（續(xù) 2） 例 4：求下面兩個(gè)碼字之間的漢明距離。 7. 簡(jiǎn)單重復(fù)編碼（續(xù) 4） 210EP ??43 1 0EP ???51 1 0EP ???74 1 0EP ???81 1 0EP ???105 1 0EP ???EP第六章：有噪信道編碼 信道編碼的相關(guān)概念 7. 簡(jiǎn)單重復(fù)編碼（續(xù) 5） 3 2 2 2 2 2 2 32 3 2 2 2 2 3 2000001p p p p p p p p p p p p p pp p p p p p p p p p p p p p???????P12( 0 0 0 ) ( 0 1 0 ) ( 1 0 0 ) ( 1 1 0 ) 0 0 0( 0 0 1 ) ( 0 1 1 ) ( 1 0 1 ) ( 1 1 1 ) 0 0 1F F F FF F F F? ? ? ? ??? ? ? ? ? ??xx0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 12*1 ( | ) 1 . 0 1 1 0E j iY X xPpM ??? ? ??? yx第六章：有噪信道編碼 信道編碼的相關(guān)概念 l 如果在擴(kuò)展信源的 個(gè)碼符號(hào)序列中任意選擇 M個(gè)序列作為 信道的輸入，以代表 M個(gè)信源消息 。 第六章：有噪信道編碼 信道編碼的相關(guān)概念 ???????????P???????????P5. 兩種重要的譯碼規(guī)則（續(xù) 12） 第六章：有噪信道編碼 信道編碼的相關(guān)概念 1 [ ( 0 . 2 0 . 3 ) ( 0 . 3 0 . 3 ) ( 0 . 2 0 . 5 ) ] 0 . 63EP ? ? ? ? ? ? ?1 [ ( 0 .2 0 .3 ) ( 0 .3 0 .3 ) ( 0 .2 0 .4 ) ] 0 .5 6 73EP ? ? ? ? ? ? ????????????P???????????P5. 兩種重要的譯碼規(guī)則（續(xù) 13） 第六章：有噪信道編碼 信道編碼的相關(guān)概念 1 1 1( 0 .3 0 .2 ) ( 0 .2 0 .5 ) ( 0 .3 0 .3 ) 0 .64 4 2EP ? ? ? ? ? ? ?1 2 311( ) ( ) , ( )42p x p x p x? ? ?如 果111( 0 . 3 0 . 2 ) ( 0 . 2 0 . 3 ) ( 0 . 3 0 . 4 ) 0 . 6442EP ? ? ? ? ? ? ?1 * 1 *( ) ( ) ( | )ssE i j i j ij i j iP p x y p x p y x? ? ? ???? ? ? ????????????P XY?????????P5. 兩種重要的譯碼規(guī)則（續(xù) 14） 第六章：有噪信道編碼 信道編碼的相關(guān)概念 1*()( 0 .1 2 5 0 .0 5 ) ( 0 .0 7 5 0 .0 7 5 ) ( 0 .0 5 0 .1 2 5 )0 .5sE i jjiP p x y???? ? ? ? ? ????1 2 311( ) ( ) , ( )42p x p x p x? ? ?如 果6. Fano不等式 l 定理 平均錯(cuò)誤概率與信道疑義度 H(X|Y)滿足不等式： ( | ) ( ) l o g ( 1 )EEH X Y H P P r? ? ?第六章：有噪信道編碼 信道編碼的相關(guān)概念 0 1 0 1 ?p?pp7. 簡(jiǎn)單重復(fù)編碼 ???????pppp1010P?????1)1(0)0(FF*1 ( | )E j iY XxP p y xr?? ?? )(21 pp ?? 210??第六章：有噪信道編碼 信道編碼的相關(guān)概念 7. 簡(jiǎn)單重復(fù)編碼（續(xù) 1） 000000001010011100101110111二元對(duì)稱信道 的三次擴(kuò)展信道 1113 2 2 2 2 2 2 33 2 2 2 2 2 2 3000111p p p p p p p p p p p p p pp p p p p p p p p p p p p p???????P0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1? ?pp??82 3 ??Nr M =2 328Ns ??第六章：有噪信道編碼 信道編碼的相關(guān)概念 ????????? 322222233222222321ppppppppppppppppppppppppppppxxP12( 0 0 0 ) ( 0 0 1 ) ( 0 1 0 ) ( 1 0 0 ) 0 0 0( 0 1 1 ) ( 1 0 1 ) ( 1 1 0 ) ( 1 1 1 ) 1 1 1F F F FF F F F? ? ? ? ???? ? ? ? ??xx由最大似然譯碼規(guī)則，可得 7. 簡(jiǎn)單重復(fù)編碼（續(xù) 2） 自動(dòng)糾正一位錯(cuò) 23 3 ppp ??4103 ???? ?? ??sj iijE pMP1 *m i n )|(1 xy1y 2y 8y3y 4y 5y 6y 7y第六章：有噪信道編碼 信道編碼的相關(guān)概念 7. 簡(jiǎn)單重復(fù)編碼（續(xù) 3） l 在輸入符號(hào)集（ M個(gè)符號(hào)）等概的條件下，每個(gè)符號(hào)平均攜帶的最大信息量是 。 l 關(guān)于 極大似然譯碼準(zhǔn)則 ： EP信道編碼的相關(guān)概念 5. 兩種重要的譯碼規(guī)則（續(xù) 8） 當(dāng)輸入符號(hào)等概分布時(shí) ??????????