信息理論與編碼課后答案第5章

1、第5章 有噪信道編碼5.1 基本要求通過本章學(xué)習(xí)，了解信道編碼的目的，了解譯碼規(guī)則對(duì)錯(cuò)誤概率的影響，掌握兩種典型的譯碼規(guī)則：最佳譯碼規(guī)則和極大似然譯碼規(guī)則。掌握信息率與平均差錯(cuò)率的關(guān)系，掌握最小漢明距離譯碼規(guī)則，掌握有噪信道編碼定理（香農(nóng)第二定理）的基本思想，了解典型序列的概念，了解定理的證明方法，掌握線性分組碼的生成和校驗(yàn)。5.2 學(xué)習(xí)要點(diǎn)5.2.1 信道譯碼函數(shù)與平均差錯(cuò)率5.2.1.1 信道譯碼模型從數(shù)學(xué)角度講，信道譯碼是一個(gè)變換或函數(shù)，稱為譯碼函數(shù)，記為F。信道譯碼模型如圖5.1所示。DMC信道譯碼圖5.1 信道譯碼模型5.2.1.2 信道譯碼函數(shù)信道譯碼函數(shù)是從輸出符號(hào)集合到輸入符號(hào)

2、集合的映射：，其含義是：將接收符號(hào)譯為某個(gè)輸入符號(hào)。譯碼函數(shù)又稱譯碼規(guī)則。5.2.1.3 平均差錯(cuò)率在信道輸出端接收到符號(hào)時(shí)，按譯碼規(guī)則將譯為，若此時(shí)信道輸入剛好是，則稱為譯碼正確，否則稱為譯碼錯(cuò)誤。的譯碼正確概率是后驗(yàn)概率： （5.1）的譯碼錯(cuò)誤概率： （5.2）平均差錯(cuò)率是譯碼錯(cuò)誤概率的統(tǒng)計(jì)平均，記為： （5.3）5.2.2 兩種典型的譯碼規(guī)則兩種典型的譯碼規(guī)則是最佳譯碼規(guī)則和極大似然譯碼規(guī)則。5.2.2.1 最佳譯碼規(guī)則使達(dá)到最小的譯碼規(guī)則稱為最佳譯碼規(guī)則。這種規(guī)則是按后驗(yàn)概率最大原則定出的，所以又稱最大后驗(yàn)概率譯碼規(guī)則。 （5.4）上式中最大后驗(yàn)概率條件可等價(jià)成最大聯(lián)合概率條件。將兩邊

3、乘以，變換為。因此，最佳譯碼規(guī)則又可表示成： （5.5）因?yàn)槭褂米畲舐?lián)合概率條件，所以又稱為最大聯(lián)合概率譯碼規(guī)則。5.2.2.2 極大似然譯碼規(guī)則按最大轉(zhuǎn)移概率條件來確定的譯碼規(guī)則，稱為極大似然譯碼規(guī)則： （5.6）雖然極大似然譯碼規(guī)則的平均差錯(cuò)率不是最小，不是最佳的，但最易找出。可以證明，當(dāng)信道輸入等概時(shí)，極大似然譯碼規(guī)則與最大聯(lián)合概率譯碼規(guī)則等價(jià)，此時(shí)極大似然譯碼規(guī)則也是最佳的。5.2.3 信道編碼對(duì)平均差錯(cuò)率和信息率的影響信道編碼（或稱糾錯(cuò)編碼）是靠增加冗余碼元來克服或減輕噪聲影響的。冗余是相對(duì)于信息的表示而言，但是對(duì)提高傳送可靠性來說，冗余碼元卻提供了極寶貴的可靠性信息。以下以兩種簡單

4、信道編碼方法來說明信道編碼對(duì)平均差錯(cuò)率和信息率的影響。5.2.3.1 “簡單重復(fù)”編碼日常中人們可以通過重復(fù)某句話使別人聽得更清楚。數(shù)字通信中，將符號(hào)重復(fù)傳幾次，也會(huì)提高傳送可靠性。例如，“重復(fù)2次”編碼，如圖5.2所示。信道譯碼信道譯碼圖5.2 “重復(fù)2次”編碼編碼規(guī)則為擴(kuò)展信道的轉(zhuǎn)移矩陣為按極大似然譯碼規(guī)則得譯碼函數(shù)：即信道編碼之后的信息率為 /碼元 （5.7）若信源等概率分布，則 /碼元 （5.8）其中代表信源消息（符號(hào)）個(gè)數(shù)。無編碼 /碼元 “重復(fù)2次”編碼 /碼元 /碼元 /碼元 隨著“重復(fù)”次數(shù)的增加，下降，但也跟著下降。即信息傳輸?shù)挠行院涂煽啃允敲艿摹?.2.3.2 對(duì)符號(hào)串

5、編碼對(duì)信源的符號(hào)串進(jìn)行編碼，即增多消息個(gè)數(shù)，同時(shí)增大碼長，有可能使平均差錯(cuò)率降低到要求的范圍以內(nèi)，而又能使信息率降低得不多。例如，取（2次擴(kuò)展信源）、。4個(gè)消息記為編碼函數(shù)為譯碼采用極大似然規(guī)則。編譯碼示意圖見圖5.3所示。圖5.3 、 的編譯碼示意圖5次擴(kuò)展信道編碼后的信息率和平均差錯(cuò)率分別為 /碼元與“重復(fù)2次”編碼相比，略有增加，處在同一數(shù)量級(jí)。因此，增大碼長和適當(dāng)增多消息個(gè)數(shù)，對(duì)兼顧（可靠性）和（有效性）的要求是有效的。5.2.4 最小漢明距離譯碼規(guī)則5.2.4.1漢明距離兩個(gè)等長符號(hào)序列和之間的漢明距離，記為，是與之間對(duì)應(yīng)位置上不同符號(hào)的個(gè)數(shù)，用來定量描述符號(hào)序列之間的“相似”程度。

6、5.2.4.2漢明距離與信道編碼性能的關(guān)系碼是碼字的集合，碼字則是由碼元組成的符號(hào)序列。假如是等長碼，則中任意兩個(gè)不同碼字之間的漢明距離或碼間距離為碼的最小碼間距離定義為最小碼間距離是衡量碼的性能的重要參數(shù)，碼的小，說明其中有些碼字受干擾后容易變?yōu)榱硪淮a字，譯碼時(shí)就會(huì)出錯(cuò)。因此，信道編碼在選擇碼字時(shí)，應(yīng)盡量使碼的最小碼間距離大一些為好。對(duì)于二元對(duì)稱信道，設(shè)信源有個(gè)消息，輸入和輸出符號(hào)集分別為和，其次擴(kuò)展信道的入口符號(hào)集和出口符號(hào)集中都含有個(gè)長二元符號(hào)串，即從中選擇個(gè)符號(hào)串當(dāng)作碼字組成碼：按極大似然譯碼規(guī)則進(jìn)行譯碼時(shí)，可以推導(dǎo)出等價(jià)于以下規(guī)則，稱為最?。h明）距離譯碼規(guī)則： （5.9）其含意是：

7、將接收序列譯為與之最相似的輸入序列（碼字）。5.2.5有噪信道編碼定理（香農(nóng)第二定理）5.2.5.1有噪信道編碼定理若信道是離散、無記憶、平穩(wěn)的，且信道容量為，只要待傳送的信息率，就一定能找到一種信道編碼方法，使得碼長足夠大時(shí)，平均差錯(cuò)率任意接近于零。有噪信道編碼定理實(shí)際上是一個(gè)存在性定理，它指出：在時(shí)，肯定存在一種好的信道編碼方法，用這種好碼來傳送消息可使逼近零。但香農(nóng)并沒有給出具體編碼方法。對(duì)有噪信道編碼定理的證明要用到聯(lián)合典型序列。所謂典型序列，是指那些平均自信息量逼近熵的序列。聯(lián)合典型序列，是指那些平均聯(lián)合自信息量逼近聯(lián)合熵的序列。離散無記憶信源發(fā)出長序列，若 （5.10）則稱為的典型

8、序列，否則稱為的非典型序列。若和分別是和的長典型序列，且 （5.11）則稱序列對(duì)為與的聯(lián)合典型序列，否則稱為非聯(lián)合典型序列。5.2.5.2有噪信道編碼逆定理若信道是離散、無記憶、平穩(wěn)的，且信道容量為，如果信息率，則肯定找不到一種信道編碼方法，使得碼長足夠大時(shí)，平均差錯(cuò)率任意接近于零。對(duì)有噪信道編碼逆定理的證明，要用到Fano不等式。Fano不等式： （5.12）式中是信道輸入符號(hào)個(gè)數(shù)。5.2.6 線性分組碼5.2.6.1 基本概念信道編碼的目的是為了降低平均差錯(cuò)率。糾錯(cuò)編碼理論幾乎與信息論同時(shí)創(chuàng)立，創(chuàng)始人是漢明（R.W.Hamming），他與信息論創(chuàng)始人香農(nóng)都在貝爾實(shí)驗(yàn)室工作。糾錯(cuò)編碼的基本思

9、路是在信息序列中引入可控冗余，或稱校驗(yàn)碼元，組成一個(gè)相關(guān)的碼元序列碼字，譯碼時(shí)利用碼元之間的相關(guān)性質(zhì)來檢測錯(cuò)誤和糾正錯(cuò)誤。分組碼：先將信息序列分成個(gè)符號(hào)一組，稱為信息組，然后在信息組中加入一些校驗(yàn)碼元組成長碼字，由此得到的碼稱為分組碼，校驗(yàn)位數(shù)目為。線性碼：線性碼滿足線性特性，即碼中任意兩個(gè)碼字的和仍為碼字。否則為非線性碼。循環(huán)碼：循環(huán)碼是線性碼的一個(gè)子集。循環(huán)碼中任一碼字循環(huán)移位后仍為該碼的碼字。否則為非循環(huán)碼。5.2.6.2 生成矩陣和校驗(yàn)矩陣編碼函數(shù)可用矩陣表示成 （5.13）其中是K維信息組行矩陣，是N維碼字行矩陣，是碼的生成矩陣。 （5.14） （5.15）通過生成矩陣，可將信息組變

10、換為相應(yīng)的碼字。如果碼字的前（或后）位照搬信息組的個(gè)信息元，這樣形成的碼稱為系統(tǒng)碼。對(duì)于前位為信息元的系統(tǒng)碼，生成矩陣可分塊成 （5.16）校驗(yàn)方程的矩陣形式則為或 （5.17）式中為一致性校驗(yàn)矩陣，為校驗(yàn)位數(shù)目。5.2.6.3 漢明距離和碼的糾檢錯(cuò)能力的關(guān)系(1) 一個(gè)碼能夠檢測出個(gè)錯(cuò)誤的充要條件是；(2) 一個(gè)碼能夠糾正個(gè)錯(cuò)誤的充要條件是；(3) 一個(gè)碼能夠糾正個(gè)錯(cuò)誤，同時(shí)又能夠檢測出個(gè)錯(cuò)誤的充要條件是和。其中，表示碼的最小漢明距離，是衡量其糾、檢錯(cuò)能力的重要參數(shù)。5.2.6.4 伴隨式與伴隨式譯碼用一致性校驗(yàn)矩陣對(duì)接收序列進(jìn)行檢驗(yàn)，檢驗(yàn)結(jié)果記為，則 （5.18）式中為發(fā)送碼字。如果，則表

11、明有錯(cuò)誤存在。是傳輸是否出錯(cuò)的標(biāo)志，稱為伴隨式。稱為差錯(cuò)圖樣。當(dāng)碼字第位發(fā)生錯(cuò)誤時(shí)，否則。通過接收序列可以確定發(fā)送碼字的估計(jì)值： （5.19）教材習(xí)題參考答案5.1 譯碼規(guī)則與錯(cuò)誤概率5.1.1 （陳杰，紅皮書，p139，例5.1）例5.1 已知信道矩陣，求。 解：根據(jù)極大似然譯碼準(zhǔn)則選擇譯碼函數(shù)B B： 又設(shè)輸入符號(hào)為等概率分布 則有 =0.567 若按下述譯碼函數(shù)A計(jì)算平均錯(cuò)誤概率 得 可見 (平均錯(cuò)誤概率)，即得以下結(jié)論：（1） 平均錯(cuò)誤概率與譯碼規(guī)則有關(guān)；（2） 極大似然譯碼準(zhǔn)則B優(yōu)于A。5.1.2（原5.3）設(shè)碼為，用2元對(duì)稱信道傳送（錯(cuò)誤概率）。如果碼字概率為，試找出一種譯碼規(guī)則，

12、使平均差錯(cuò)率最小。 答案：王虹老師 5.2 兩種典型的譯碼規(guī)則5.2.1 （原5.1） 設(shè)有DMC其轉(zhuǎn)移矩陣如下 若信道輸入概率為，試確定最佳譯碼規(guī)則和極大似然譯碼規(guī)則并計(jì)算出相應(yīng)的平均差錯(cuò)率。答案：王虹老師解：， 信道的聯(lián)合概率矩陣為根據(jù)最小錯(cuò)誤概率準(zhǔn)則（其實(shí)就是最大聯(lián)合概率譯碼準(zhǔn)則），在聯(lián)合概率矩陣中，每列選一最大值（矩陣中帶下劃線的值），譯為平均錯(cuò)誤概率若根據(jù)最大似然概率譯碼準(zhǔn)則，在矩陣每列中選一最大值，譯為平均錯(cuò)誤概率5.2.2（陳杰，140頁）例5.3 設(shè)一離散無記憶信道的輸入符號(hào)集為，輸出符號(hào)集為，信道轉(zhuǎn)移概率為，；，。若譯碼器以概率（，；，）對(duì)收到的判決為，試證明對(duì)于給定的輸入分

13、布，任何隨即判決方法得到的錯(cuò)誤概率不低于最大后驗(yàn)概率譯碼時(shí)的平均譯碼錯(cuò)誤概率。證明：根據(jù)最大后驗(yàn)概率譯碼準(zhǔn)則，有，且 ，所以有 最大后驗(yàn)概率譯碼的錯(cuò)誤概率為： 隨即判決法譯碼的錯(cuò)誤概率為： 所以，得證。5.3平均差錯(cuò)率與信道編碼5.3.1（原5.2）設(shè)信源有M個(gè)消息符號(hào)，將每個(gè)符號(hào)編碼成N長的二進(jìn)制碼字，碼字從個(gè)N長二進(jìn)制序列中獨(dú)立、等概地選出，若采用極大似然譯碼規(guī)則，試分別求取在以下三種信道下的平均差錯(cuò)率。 答案：王虹老師5.3.2（傅詳，p192） 6-8設(shè)一離散無記憶信道，其信道矩陣為 （1） 計(jì)算信道容量C。（2） 找出一個(gè)碼長為2的重復(fù)碼，其信息傳輸率為（即5個(gè)碼字）。如果按最大似然

14、譯碼準(zhǔn)則設(shè)計(jì)譯碼器，求譯碼器輸出端的平均錯(cuò)誤概率（輸入碼字為等概率分布）。（3） 有無可能存在一個(gè)碼長為2的碼而使 即使，如存在的話請(qǐng)找出來。解：（1） 因?yàn)檩斎氪a字等概率分布，這重復(fù)碼，因此滿足信息傳輸率 此信道是無記憶信道，滿足 ， =1，2，25， =1，2，5解：（1）根據(jù)信道矩陣P，可知其是一對(duì)稱信道，所以信道容量為 比特符號(hào)（3） 設(shè)信道的輸入符號(hào)集，輸出符號(hào)集，其傳遞信道矩陣為P，任選碼長為2的重復(fù)碼： ：, 因?yàn)檩斎氪a字等概率分布，這重復(fù)碼，因此滿足信息傳輸率 此信道是無記憶信道，滿足 ， ， ， ， =1，2，25， =1，2，5下面給出傳遞概率的矩陣為：根據(jù)最大似然譯碼準(zhǔn)則

15、，確定的譯碼規(guī)則是譯成 00，譯成 11，譯成 22 譯成 33，譯成 44在選擇碼C重復(fù)碼的情況下，因?yàn)閷?duì)于其他，所以其他在輸出端不會(huì)出現(xiàn)?？捎?jì)算得 （3）存在碼長為2的碼，它使，也就是它使。這種碼共有10種。這是因?yàn)檫@個(gè)離散無記憶信道具有特殊的傳輸概率，輸入符號(hào)“0”只傳輸?shù)捷敵龇?hào)“0”和“1”；輸入符號(hào)“1”只傳輸?shù)捷敵龇?hào)“1”和“2”；輸入符號(hào)“4”只傳輸?shù)捷敵龇?hào)“4”和“0”。因此，從（2）題的傳遞概率矩陣中可以看出，它可使有些 。也就是選擇碼長的序列作為碼字時(shí)，它只傳輸?shù)捷敵龆巳舾蓚€(gè)序列，而使其他傳輸概率為零。如（2）題中碼字只傳輸?shù)?；只傳輸?shù)?；等等。為此，我們只要適當(dāng)?shù)剡x擇

16、碼長為2的5個(gè)碼字，它們將輸出端可能出現(xiàn)的25個(gè)碼長為2的接受序列分割成五個(gè)互不相交的子集，每個(gè)碼字只傳輸?shù)剿鶎?duì)應(yīng)的子集，這樣就可使等于零。 能使，碼長為2的十種可選的碼是：從上面碼字選擇的規(guī)律可以看出，當(dāng)選定某一二位長序列為碼字，其他碼字是將第一位碼元的符號(hào)增加1，第二位的碼元的符號(hào)增加2而獲得；或者其他碼字是將第一位碼元的符號(hào)增加2，而第二位碼元的讀好增加1而獲得。 我們也可以類似卡諾圖來排列，將25個(gè)的序列排列成一方塊圖。由于00只傳輸?shù)?0，01，10，11；01只傳輸?shù)?1，02，11，12；等等。所以圖中每一序列只可能向右一格，向下一格的含四個(gè)序列的方框內(nèi)傳輸（如箭圖所示）；隔行、

17、隔列或反向的傳輸都為零。只要找出不相交的五個(gè)子集（即五個(gè)含四個(gè)序列的方框），選取方框左上角的序列作為碼字，就可以找出這個(gè)碼組。如果所選方框相交，這就不是所需的碼。上述十種碼中任一種碼都滿足如此劃分的條件。00 0110 1112 1322 2331 3241 4243 4403 0424 2034 3014 1002 03 04 0020304000 01 02 334000上面種所選的碼是：。我們也可以用上圖來檢驗(yàn)所選的碼是否正確。5.4 漢明距離5.4.1（原5.4）碼為。（1）求該碼的最小漢明距離；（2）假設(shè)碼字等概率分布，該碼的碼率；（3）若采用最小距離譯碼規(guī)則，那么，當(dāng)接收到“100

18、00”、“01100”以及“00100”時(shí)，別譯為什么碼字。（4）該碼能檢出幾位錯(cuò)誤？能糾正幾位錯(cuò)誤？解：（1）此二元碼的最小距離 （2）此二元碼的碼字個(gè)數(shù)，碼長所以，碼率 比特/碼符號(hào)（4） 采用最小距離譯碼準(zhǔn)則（即將接收序列譯成與其碼距為最小的碼字）,接收序列10000與碼字10010距離為1，與其碼字的距離都大于1，所以 10000 譯成 10010同理 01100 譯成 11100 00100 譯成 11100 或 00111任一個(gè)（4）因此此碼，即，所以，此碼能糾正所有發(fā)生一位碼元的隨機(jī)錯(cuò)誤。5.4.2（傅詳，186）【6-2】計(jì)算碼長的二元重復(fù)碼的譯碼錯(cuò)誤概率。假設(shè)無記憶二元對(duì)稱信

19、道中正確傳遞概率，錯(cuò)誤傳遞概率。此碼能檢測出多少錯(cuò)誤？又能糾正多少錯(cuò)誤。若，譯碼錯(cuò)誤概率是多大？解：碼長二元重復(fù)碼的碼字是（00001，11111）。這碼的最小距離。因?yàn)?所以此碼用于檢測錯(cuò)誤能檢測出所有發(fā)生小于等于4位碼元的隨機(jī)錯(cuò)誤。 又因?yàn)?所以此碼用于糾正錯(cuò)誤能糾正出所有發(fā)生小于等于2位碼元的隨機(jī)錯(cuò)誤。 可以根據(jù)最大似然譯碼準(zhǔn)則的譯碼規(guī)律或擇多譯碼的譯碼規(guī)則來計(jì)算這的二元重復(fù)碼的錯(cuò)誤概率，這兩種計(jì)算結(jié)果是一致的。所以，采用擇多譯碼的譯碼規(guī)則來計(jì)算，得 若，則 5.5有噪信道編碼定理5.5.1（傅精，171頁）【5.1】某信源按的概率產(chǎn)生統(tǒng)計(jì)獨(dú)立的二元序列。（1）試求，使當(dāng)時(shí)有 其中是信源

20、的熵。（2）試求當(dāng)時(shí)典型序列集中含有的信源序列個(gè)數(shù)。解：（1）本題信源是一個(gè)二元信源 得 比特符號(hào)根據(jù)契比雪夫不等式，對(duì)于任意，當(dāng)時(shí)有 現(xiàn) ，得根據(jù)信源，其 所以 （2）序列集是所有長的典型序列的集合，根據(jù)的特性有是序列中含有的典型序列的個(gè)數(shù)。 所以當(dāng)時(shí)中含有的信源序列個(gè)數(shù)為或者 5.7線性分組碼5.7.1 （原5.5） 設(shè)二元線性碼的生成矩陣為（1）將生成矩陣化為的形式；（2）求校驗(yàn)矩陣；答案：王虹老師5.7.2 （原5.6）試證線性碼的最小漢明距離不大于。答案：王虹老師5.7.3 （傅詳，P198）【6-12】下面是某線性二元碼的全部碼字： （1） 求，為何值；（2） 構(gòu)造這碼的生成矩陣；

21、（3） 構(gòu)造這碼的一致校驗(yàn)矩陣。解：（1）因?yàn)榇a字?jǐn)?shù)，所以為碼線性分組碼（2）生成矩陣為列的矩陣，由個(gè)線性獨(dú)立的碼字組成。 故 (3)設(shè)信息位，則碼字 所以所以 本章測驗(yàn)題一、填空題1. 信息傳遞系統(tǒng)的基本功能是在系統(tǒng)輸出端準(zhǔn)確地再現(xiàn)系統(tǒng)輸入端發(fā)送的信息。但是會(huì)受到客觀限制，首先_受_的限制；其次，由于_的干擾，_不可避免。2. 衡量信息傳輸速度大小的指標(biāo)是信道的信息（傳輸）率，其最大值就是_，衡量信息傳輸可靠性的指標(biāo)是_。3. 為了降低平均差錯(cuò)率，可先對(duì)消息_再送入信道傳送，這種為降低_而進(jìn)行的編碼稱為信道編碼。4. 信道輸出它與信道輸入既有聯(lián)系又有區(qū)別，聯(lián)系的程度和區(qū)別的大小取決于_或者說

22、取決于_。5. 信道譯碼函數(shù)是從_到_的映射：其含義是將_譯為_。譯碼函數(shù)又稱_。二、判斷題1. 譯碼規(guī)則取決于信道，一個(gè)信道的譯碼規(guī)則是唯一的。（）2. 在信道輸出端接收到符號(hào)時(shí)，按譯碼規(guī)則將譯為，若此時(shí)信道輸入剛好是，則稱為譯碼正確。（）3. 若按譯碼規(guī)則將譯為，則平均譯碼錯(cuò)誤概率是的加權(quán)平均值。（）4. 最“好”的譯碼規(guī)則必然使最小。（）5. 最大后驗(yàn)概率譯碼規(guī)則是最佳譯碼規(guī)則。（）三、選擇題1. 譯碼規(guī)則不能由_確定A后驗(yàn)概率 B. 聯(lián)合概率 C. 轉(zhuǎn)移概率 D. 邊緣概率2. 假設(shè)，信道線圖如下圖所示，相應(yīng)的最佳譯碼規(guī)則為_A. B. C. D. 3. 下列說法不正確的是_A. 信道

23、輸入等概時(shí)，極大似然譯碼規(guī)則也是最佳的B. 最大后驗(yàn)概率條件可無條件等價(jià)成最大聯(lián)合概率條件C. 當(dāng)信源統(tǒng)計(jì)特性未知的時(shí)候，可以使用極大似然譯碼規(guī)則作為譯碼規(guī)則D應(yīng)用極大似然譯碼規(guī)則總可以確定譯碼的平均差錯(cuò)率4. 關(guān)于“重復(fù)N次”編碼，說法不正確的是_。AN越大，信息傳輸率越高B“重復(fù)N次”是定長碼C采用擇多譯碼策略D能減低平均差錯(cuò)率5. 對(duì)信源的2元符號(hào)串進(jìn)行編碼，取碼長為，則_A. 可供選擇的碼字有4個(gè)B信息率C共有4832種不同的編碼方法。D繼續(xù)增加消息個(gè)數(shù)，可以降低平均差錯(cuò)率四、計(jì)算題1、（傅詳，p191）【6-7】考慮一個(gè)碼長為4的二元碼，其碼字為，。假設(shè)碼字送入一個(gè)二元對(duì)稱信道（其單

24、符號(hào)的錯(cuò)誤概率為，并），而碼字輸入是不等概率分布的，其概率為 ，試找出一種譯碼規(guī)則使平均錯(cuò)誤概率為最小。2、（傅詳，p188）【6-5】對(duì)于離散無記憶強(qiáng)對(duì)稱信道，信道矩陣為 試證明對(duì)于此信道，最小距離譯碼準(zhǔn)則等價(jià)于最大似然譯碼準(zhǔn)則。3、（傅詳，p197）【6-11】設(shè)無記憶二元對(duì)稱信道的正確傳遞概率為，錯(cuò)誤傳遞概率為，對(duì)于（7，4）漢明碼（如參考書1中表6.2）（1） 若碼字都是等概率分布，試問什么是其最佳的譯碼規(guī)則。（2） 在接收端，128個(gè)接收的二元序列應(yīng)該對(duì)應(yīng)譯成什么碼字。并說明其能糾正一個(gè)碼元的隨機(jī)錯(cuò)誤。（3） 在最佳譯碼規(guī)則下，計(jì)算此碼的平均錯(cuò)誤概率。（4） 若p=0.01,從和碼率

25、R上將（7，4）漢明碼與n=7的重復(fù)碼進(jìn)行比較。4、（傅詳，P200） 【6-14】有一組碼將二位信息位編成五位長的碼字，其規(guī)則如下： 信息序列 碼字 00 00000 01 01101 10 10111 11 11010（1）證明此碼是系統(tǒng)一致效驗(yàn)碼；（2）找出其生成矩陣和一致效驗(yàn)矩陣；（3）對(duì)于無記憶二元對(duì)稱信道（），列出其最大似然譯碼的譯碼表；（4）計(jì)算正確譯碼概率。5、（傅精，P203）【6-16】設(shè)一分組碼具有一致效驗(yàn)矩陣 （1）求這分組碼，共有多少個(gè)碼字；（2）此分組碼的生成矩陣；（3）矢量101010是否是碼字；（4）設(shè)發(fā)送碼字C=（001111），但接收到的序列為R=（0000

26、10），其伴隨式S是什么，這伴隨式指出已發(fā)生的錯(cuò)誤在什么地方，為什么與實(shí)際錯(cuò)誤不同。五、實(shí)驗(yàn)題試編程實(shí)現(xiàn)線性分組碼的編譯碼本章測驗(yàn)題參考答案一、填空題1. 傳輸速度 信道容量 信道噪聲 傳輸錯(cuò)誤2. 信道容量 平均差錯(cuò)率3. 編碼 平均差錯(cuò)率4. 噪聲的影響情況 信道的統(tǒng)計(jì)特性5. 輸出符號(hào)集合 輸入符號(hào)集合 接收符號(hào) 某個(gè)輸入符號(hào) 譯碼規(guī)則二、判斷題1. ；2. ；3. ；4. ；5. 三、選擇題1、D 2、C 3、D 4、A 5、B四、計(jì)算題1、 解：在二元對(duì)稱信道中最小距離譯碼準(zhǔn)則等價(jià)于最大似然譯碼準(zhǔn)則。但是，碼字輸入不是等概率分布，所以最大似然譯碼準(zhǔn)則不能使平均錯(cuò)誤概率為最小。要使譯碼

27、后平均錯(cuò)誤概率最小只有選擇最小錯(cuò)誤概率準(zhǔn)則進(jìn)行譯碼。也就是比較來決定譯碼規(guī)則。我們將的矩陣如下列出：根據(jù)最小錯(cuò)誤概率譯碼準(zhǔn)則將接收序列譯成在矩陣的每一列中為最大的那個(gè)碼字。所以，得譯碼規(guī)則為（因?yàn)椋┤舭醋畲笏迫蛔g碼準(zhǔn)則來選擇譯碼規(guī)則的話，如；也可譯成或或；也可譯成；等等。但其并沒有將矩陣中每一列的最大元素除去，所以余下元素之和就不是最小的了，不能為最小。2、證明：設(shè)碼C為M個(gè)碼長為n的r元碼，其碼字，接收的序列為。碼字與接收序列的距離仍是二序列之間對(duì)應(yīng)碼位上不同碼元的個(gè)數(shù)。因?yàn)槭菑?qiáng)對(duì)稱信道，只要與()不相同就引起錯(cuò)誤，而其傳遞概率都相等，即 而且強(qiáng)對(duì)稱信道是無記憶的，所以 一般。所以當(dāng)接收序列

28、與碼字的距離越大，即越大，越小時(shí)，和越小，也越小，則越小。當(dāng)與的距離越小，即越小，越大，則越大。所以滿足 則滿足 所以最小距離譯碼準(zhǔn)則是選擇譯碼函數(shù) 使?jié)M足 則等價(jià)于最大似然譯碼準(zhǔn)則是選擇譯碼函數(shù) 使?jié)M足 證畢3、 解：（1）在無記憶二元對(duì)稱信道中，所以最小距離譯碼準(zhǔn)則等價(jià)于最大似然譯碼準(zhǔn)則。而且碼字是等概率分布，所以最大似然譯碼準(zhǔn)則能使譯碼的平均錯(cuò)誤概率最小。因此，此時(shí)最佳譯碼規(guī)則應(yīng)采用最小距離譯碼準(zhǔn)則。（2）根據(jù)最小距離譯碼準(zhǔn)則，因?yàn)椋?，4）漢明碼共有16個(gè)碼字，而接收端共有128個(gè)7位長的二元序列，正好分成16個(gè)集合。每個(gè)集合都有8個(gè)二元接收序列，都是由碼字 發(fā)生一位碼元錯(cuò)位所變成的接

29、收序列（共7個(gè)二元序列）和完全正確傳遞的一個(gè)接收序列組成。而且任一碼字發(fā)生一位碼元錯(cuò)位所變成的接收序列都不會(huì)進(jìn)入其它的集合。又在這16個(gè)集合中也沒有相同的接收序列，即這16個(gè)集合是不相交的。因此，采用最小距離譯碼就能糾正一位碼元的隨即錯(cuò)誤。具體的譯碼見譯碼表。（3） （4）若p=0.01，則 碼率 比特/碼元而（7，1）重復(fù)碼 碼率 比特/碼元 可見，（7，1）重復(fù)碼雖然能糾正3個(gè)碼元發(fā)生的隨機(jī)錯(cuò)誤，其平均錯(cuò)誤概率減少。但同時(shí)碼率（信息傳輸率）也減小很多。譯碼表接收序列 碼字 接收序列 碼字 接收序列 碼字 接收序列 碼字4、解：（1）設(shè)碼字，信息位為。根據(jù)碼字可得 可見，碼字的后三位都由其前

30、二位線性組合得到。因此，此碼是（5，2）一致效驗(yàn)碼。（2）由碼字可得 故，此碼是系統(tǒng)一致效驗(yàn)碼。（3）列出下列最大似然譯碼表 伴隨式 錯(cuò)誤圖樣 000 00000 111 10000 101 01000 100 00100 010 00010 001 00001 011 10100（或00011） 110 10001（或00110）因?yàn)榇a的最小距離，所以能糾正一位碼元的錯(cuò)誤。從譯碼表中可以看出所有一位碼元發(fā)生錯(cuò)誤的錯(cuò)誤圖樣能被糾錯(cuò)，而且還有二種發(fā)生二位碼元錯(cuò)誤的錯(cuò)誤圖樣能被糾錯(cuò)。（4）根據(jù)譯碼表及無記憶二元信道，所以正確譯碼概率 5、解：（1）設(shè)碼字，有 故得 所以n=6，r=3，k=3，為（

31、6，3）分組碼。碼字共有個(gè)。（2）由（1）式得 所以，為信息位。設(shè)，信息位，故生成矩陣 （3）這（6，3）分組碼的所有許用碼字是 000000 101100 011010 111001 001111 110110 100011 010101可見矢量101010不是碼字（4）因?yàn)?伴隨式正好是H矩陣中第5列。根據(jù)伴隨式就判斷碼字中發(fā)生了錯(cuò)誤，則E=（000010）。但實(shí)際錯(cuò)誤圖樣E為 C + E = R E = R + C E = （000010）+（001111）=（001101）是碼字傳送中發(fā)生了三位碼元錯(cuò)誤。因?yàn)榇耍?，3）碼，所以，得e = 1。根據(jù)（6，3）碼伴隨式所判斷的錯(cuò)誤是能糾正

32、一位碼元發(fā)生錯(cuò)誤的錯(cuò)誤圖樣。若此（6，3）碼用于檢測錯(cuò)誤，也只能檢測出二位碼元發(fā)生錯(cuò)誤。因此，當(dāng)傳輸過程中碼字發(fā)生了三位以上碼元的錯(cuò)誤也就無法檢測出來了。五、（1）編碼過程G=1 0 0 1 0 1; 0 1 0 1 1 1; 0 0 1 1 1 0; % 生成矩陣K,N=size(G); % 確定生成矩陣的大小% 下面生成所有可能的信息組：% m=zeros(K,2K); % 信息組初始化for i=0:2K-1 seq=dec2bin(i,K); for j=1:K m(i+1,j)=str2num(seq(j); endendc=mod(m*G,2); 生成所有信息組對(duì)應(yīng)的碼字程序說明：

33、（5） 生成矩陣G和信息組m是已知的（6） 本程序?qū)λ械男畔⒔M進(jìn)行了編碼，如果只需要對(duì)特定信息組進(jìn)行編碼，修改m即可（7） str2num：實(shí)現(xiàn)字符串向數(shù)字的轉(zhuǎn)換（8） mod：求模函數(shù)運(yùn)行結(jié)果：所有可能的信息組為:m = 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1生成所有信息組對(duì)應(yīng)的碼字為：c = 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 0（2）譯碼過程function codeword=lincoder(H,y)% H:校驗(yàn)矩陣% y：接收到的矢量% codeword：估計(jì)發(fā)送的矢量，返回值r,N=size(H); % 確定校驗(yàn)位個(gè)數(shù)和碼長s=mod(H*y,2); % 確定伴隨式k=N-r; % 確定信息位個(gè)數(shù)e_common=zeros(N,k);bas=eye(k);