信息論課程設計報告實驗報告

..可修編.西噢■救女學《信息論課程設計》實驗報告題目1:實現(xiàn)香農(nóng)編碼及計算其編碼效率題目2： 實現(xiàn)有噪信道編碼中的循環(huán)碼 院系（部）： 計算機科學與技術學院 專業(yè)及班級： 信息與計算科學1301班 姓名：唐詩韻學 號： 1308060105日 期： 2016/01/10課題描述1信源編碼的相關介紹3香農(nóng)編碼（題目一）3香農(nóng)編碼算法3香農(nóng)編碼特點4香農(nóng)編碼的C++程序?qū)崿F(xiàn)4程序設計4運行結(jié)果6實現(xiàn)有噪信道中的循環(huán)碼編碼方法（題目二）6循環(huán)碼編碼算法6循環(huán)碼編碼特點7循環(huán)碼編碼的C++程序?qū)崿F(xiàn)7程序設計7運行結(jié)果9總結(jié)10參考文獻11課題描述信息論是一門理論和實踐相結(jié)合的專業(yè)，因此相關題目都是來自于實踐，同時具有上機練習的可操作性，此門科目是通信的基礎。香農(nóng)1984年發(fā)表的一篇論文標志著信息論誕生，在他的論文中主要用概率來描述有效傳輸信息的問題，用概率給予了信息的定量描述方法，并提出了信源熵的概念，在現(xiàn)實生活中，人們經(jīng)常把消息和信息分不清，認為消息就是信息，實則不是，消息是描述實物，而信息是定量描述一個消息所傳輸?shù)男畔⒘?，通常用自信息量來描述一個消息所傳達的信息量，它取值為此事件發(fā)生的概率的負對數(shù)，它表示一個事件發(fā)生之前此事件發(fā)生的不確定性大小，也表示一個事件發(fā)生后它所能提供的信息量，兩個相互獨立的消息所提供的信息量等于各自信息量之和。此外，還可用互信息來描述信息的傳達，為一個事件給出關于另一個事件的信息量，也表示事件丫出現(xiàn)后信宿獲得的關于x的信息量，互信息的引出，使信息的傳遞得到了定量的表示。如果事件是以序列的形式表示的，及事件集，則用平均自信息量來表示信源所傳遞的信息，平均信息量表示信源的平均不確定性，比如拋擲一枚硬幣的試驗所包含的平均信息量。要表示序列集的互信息量則用平均互信息來表示，是一個事件集所給出的關于另一個事件集的平均信息量，比如今天的天氣所給出關于明天的天氣的信息量。這些關于信息的定量度量方法可以用到離散隨機變量和連續(xù)信源的情況中去，以此來描述信息的傳達。信息論，顧名思義，是研究對信息的處理的課題，怎樣把信息通過一定的渠道傳給另一個機制，要首先選擇一個通道，及信道，然后將信息轉(zhuǎn)化成特定的數(shù)字信號即編碼，然后在傳輸信道末端將信號轉(zhuǎn)化為信息，即譯碼，這就把信息傳輸出去了。信源就是產(chǎn)生消息和消息序列的源，編碼器就是把消息變成適合在信道傳輸?shù)奈锢砹浚@種物理量成為信號，信號攜帶著消息，是消息的載體。信道是指通信系統(tǒng)把信號從發(fā)送端送到接收端的媒介通道，它還有儲存信號的作用。譯碼就是把信道輸出的已增加了干擾的信號進行反變換，使之變換成信宿能夠理解的消息，譯碼器需要盡可能準確的再現(xiàn)信源輸出的消息，就要求干擾盡可能小，而且譯碼盡可能準確。信宿就是消息傳送的對象，及接受消息的人、機器或其他事物。信息論就是用概率描述抽象的消息通過一定渠道傳輸?shù)搅硪粋€機制時的過程中的各種外部干擾或部干擾對于傳輸結(jié)果的影響，信息的傳遞效果有很多的具體度量方式，例如：離散信源和連續(xù)信源的信源熵、離散及連續(xù)信道信道容量等。為了使信源轉(zhuǎn)化為信號，就要對信源進行編碼，編碼效率與信源序列的平均碼長及信源熵有關，有各種編碼方法，如：香農(nóng)編碼、費諾編碼、哈夫曼編碼等。此外，還要對信道進行編碼，在信道上編碼會有錯誤，并且要設置編碼規(guī)則，所以糾錯編碼就顯得尤為重要，對信道的一般要，糾錯檢錯能力強，信息傳輸效率高。但消息在傳達過程中是不可能不會出現(xiàn)失真，所以就要對信源編碼進行限失真，以保證信息傳輸效率在一定圍。信源編碼的相關介紹信源來說，一個主要的問題是怎樣能合理的描述并表示信源的輸出，因為對方要接收到信源，就需要以一種特定的形式輸出，為了能讓輸出的消息更容易理解并應用，就需要對輸入的信源進行編碼，使之變換成適合信道傳輸?shù)姆栃蛄?，同時，為了盡量減少信源的失真度，應該盡可能減少碼符號，以便于提高傳輸效率。信源編碼是按照一定的規(guī)則將信源符號映射成數(shù)學符號，并進行傳輸?shù)囊环N編碼，完成編碼功能的器件成為編碼器，接收端的譯碼器完成相反的功能，為了使編碼效率更高，就要對碼字進行冗余度處理，去除冗余度有兩個方法，第一個方法是去除相關性，及使得各個信源之間獨立性提高，這一般是對信源序列進行編碼，第二種方法是使得各個信源出現(xiàn)的概率盡可能相等，使概率分布均勻，小概率消息對應長碼，大概率消息對應短碼，以此來去除冗余度，提高編碼效率。第一個完成的主要任務是實現(xiàn)香農(nóng)編碼，香農(nóng)編碼主要是對出現(xiàn)概率的信源符號進行編碼，而對出現(xiàn)概率較小的信源符號編長碼，從而使平均碼長最短，達到最佳的編碼目的，在編碼領域占有重要地位，屬于變長編碼方法，及在保證不失真的前提下對信源進行編碼，來提高編碼效率，此編碼方法依賴于信源的概率，每個信源的概率都不同，因此碼長也就不同，概率大的信源碼長短，概率小的信源碼長大，編碼時應該盡可能使平均碼長較小，能達到便于傳輸?shù)哪康?。線性分組碼是一種有實用價值的碼，屬于有噪信道編碼的一部分，信道輸出時要輸出結(jié)果為輸入時的結(jié)果，難免會出錯，發(fā)生錯誤的概率成為譯碼錯誤概率，這一錯誤概率取決于信道特性，且不可能為零，香農(nóng)的研究表明，如果將信源在傳入信道之前進行編碼，并在最后進行譯碼，有可能實現(xiàn)無誤的傳輸，及可以通過不可靠的信道對信源進行可靠性傳輸。線性分組碼是將信源分為信息位和監(jiān)督位，如，碼長為門，信息位為k,則監(jiān)督位為門*,以此為原型，寫出校驗矩陣，然后根據(jù)校驗矩陣和生成矩陣之間滿足的關系寫出生成矩陣，再用生成矩陣與信息序列異或相乘，則得到其線性分組碼。此課題完成的任務是循環(huán)碼編碼，循環(huán)碼是線性分組碼的一個子類，具有完整的代數(shù)結(jié)構，它滿足循環(huán)移位特性，碼中任何一個碼字的循環(huán)移位仍是碼中的一個碼字，一般("卜)線性分組碼的k個基底之間不存在規(guī)則的聯(lián)系，因此需要用卜個基底組成生成矩陣來表示一個碼的特征。而循環(huán)碼的卜個基底可以是同一個基底循環(huán)卜次得到，因此用一個基底就可以表示一個碼的特征，我們可以用不大于(n-1)次的碼多項式C(x)來表示：C(x)=cXn-1H Fcx2+CX1+Cn-1 2 1 0C(X)移門位后又回到C(X),一個碼字的移位最多能得到n個碼字，因此循環(huán)碼碼字的循環(huán)并不意味著循環(huán)碼可以僅從一個碼字循環(huán)而得，一個(門，卜)循環(huán)碼有2k個碼字，它們都是同一基底的線性組合根據(jù)線性碼空間的封閉性，碼字的線性組合仍是碼字。香農(nóng)編碼(題目一)香農(nóng)編碼算法香農(nóng)算法步驟如下：(1)將所有口個信源符號按其概率的遞減次序排列。P(s)NP(s)NP(s)N…NP(s)123 q例如，一組信源序列為0.18，0.20，0.19，0.17，0,15，0.10,，0,01則將其按從大到小的順序排列為0.20,0.19,0.18,0.17,0.15,0.10,0.01(2)按下式依次計算每個信源符號的二元碼碼長..可修編.- .- .可修編.l=log-r^i=12…qi P(s)i例如，自信息量為2.34的信源的碼長為3.(3)計算每個信源符號的累加概率F(s),并變換成二進制小數(shù)得到i其碼字。累加概率：F(s)=2p(s)i=1,2,?一qikk=1將累加概率F(s)變換成二進制小數(shù)，取小數(shù)點后l位數(shù)作為第iii個信源符號的碼字.3.2香農(nóng)編碼特點香農(nóng)編碼的特點是：它需要對信源符號概率進行排序，要計算累加概率，還要計算碼長。香農(nóng)編碼是對出現(xiàn)概率較高的信源符號編短碼，而對出現(xiàn)概率較小的信源符號編長碼，從而使平均碼長最短，達到最佳編碼的目的。它的缺點是需要對輸入的信源概率進行排序，而且計算結(jié)果和費諾編碼比起來不是很準確，但操作較簡單。4.香農(nóng)編碼的C++程序?qū)崿F(xiàn)4.1程序設計此題目是完成香農(nóng)編碼，設計的程序要完成的任務是：人工輸入信源個數(shù)及各個信源出現(xiàn)的概率(之和必須為1，如果不為1，則跳轉(zhuǎn)回重新輸入信源概率)、計算累加概率、計算各個信源的自信息量、由自信息量計算碼長、根據(jù)累加概率得出二元碼、求信源熵和平均碼長，然后求信源熵和平均碼長的商即為編碼效率。此程序就是按照求二元碼及其編碼效率的計算步驟一步一步設計，在設計過程中計算累加概率時看似簡單，只進行加運算，但要注意的是累加概率是對之前概率相加，不包括當前概率，這塊容易出錯，然后就是計算碼長時是取自信息量的整數(shù)值，此程序的難點是二元碼的計算，二元碼的長度與碼長相同，且計算時是用二進制數(shù)相乘運算，容易出錯，而且輸出時還要注意每個二元碼之間要有間隔。后面求編碼效率比較容易，是把信源熵和平均碼長相除得到。程序設計框圖如下：

4.2運行結(jié)果■iRI源)數(shù)5一古一分請輸入后源概率似i】＜總概率N和等于力0.10.23.30.20.2儲源符號郭庫后的概率為：TOC\o"1-5"\h\zksti])0.3 0.2 0.2 Q.2 0.1國加概率分別為：F(s[il)0 0.3 0.5 0.7 0.9旨個信源符號的自信息1為;1.736972.321932.321932.321933.32193替?zhèn)€信源符號的碼長分別為：2 3 3 3 4修個信源符號的二元碼為：陋 010 100 101 1110傅源嫡為；2.24644件均碼長為：2g題效率為！0.8023信否要繼續(xù)？(是輸入y否輸入Q、5.實現(xiàn)有噪信道編碼中的循環(huán)碼(題目二)5.1循環(huán)碼編碼算法一般(門水)線性分組碼的k個基底之間不存在規(guī)則的聯(lián)系，因此需要用卜個基底組成生成矩陣來表示一個碼的特征。而循環(huán)碼的卜個基底可以是同一個基底循環(huán)卜次得到，因此用一個基底就可以表示一個碼的特征，我們可以用不大于(門-1)次的碼多項式C(x)來表示：C(x)=cxn-1H Fcx2+CX1+CTOC\o"1-5"\h\zn-1 2 1 0循環(huán)碼的循環(huán)特性可以用碼多項式表示為移1位：C(1)(x)=xC(x)=CXn-1F FCx2FCxFCn-2 1 0 n-1移2位：C(2)(x)=x2C(x)=Cxn-1+…+Cx2+Cx+Cn-3 0 n-1 n-2移n-1位:C(n-1)(x)=xn-1C(x)=Cxn-1F FCx2+Cx+C0 3 21C(x)移，位后又回到C(x),一個碼字的移位最多能得到n個碼字，因此循環(huán)碼碼字的循環(huán)并不意味著循環(huán)碼可以僅從一個碼字循環(huán)而得，一個（門，卜）循環(huán)碼有2k個碼字，它們都是同一基底的線性組合根據(jù)線性碼空間的封閉性，碼字的線性組合仍是碼字。在21個碼字的碼多項式中取一個次數(shù)最低即（n-k）次的多項式作為生成多項式，用0^）表示。可以證明，0區(qū)是嘛多項式中唯一一個（門*）次多項式且常數(shù)項不為0，由生成多項式可以得到循環(huán)碼的生成矩陣，然后用初等行變換將此生成矩陣轉(zhuǎn)化為系統(tǒng)形式的生成矩陣，再寫出信息序列，用信息序列與系統(tǒng)矩陣異或相乘則得到循環(huán)碼。5.2循環(huán)碼編碼特點循環(huán)碼編碼過程較簡單，只要根據(jù)生成多項式寫出生成矩陣然后轉(zhuǎn)換成系統(tǒng)矩陣，再用信息序列與其相乘就得到循環(huán)碼，但得到生成多項式較困難，因為要對多項式進行分解然后尋找最高次數(shù)為門」的那項作為生成多項式，而且循環(huán)碼與漢明碼相比，循環(huán)碼的碼長和信息位之間的關系沒有限制，而漢明碼的碼長和信息位存在一定的關系，所以在設置循環(huán)碼的碼長時選擇空間較大。循環(huán)碼是線性分組碼的一子類，它具有完整的代數(shù)結(jié)構，此外，它還滿足循環(huán)移位特性：碼C中任何一個碼字的循環(huán)移位仍是碼C中的一個碼字。碼字的線性組合仍是碼字。循環(huán)碼時有實用價值的一種糾錯碼。.循環(huán)碼編碼的C程序?qū)崿F(xiàn)程序設計編此循環(huán)碼的實現(xiàn)過程時要設置一些變量，最重要的是該如何表示最后輸出的結(jié)果，最后的輸出結(jié)果為兩列，左邊那列是信息序列，右邊那列是循環(huán)碼序列，因此設計程序的時候用一個16行11列的數(shù)組表示，前四列為信息序列，后七列為循環(huán)碼序列。設計程序的步驟為：先設定線性分組碼的碼長及信息位，以此計算出監(jiān)督位，然后得出它的生成多項式，根據(jù)生成多項式及移位規(guī)則寫出生成多項式，用初等行變換將此矩陣轉(zhuǎn)化為系統(tǒng)形式的生成矩陣，然后用二進制方法寫出信息序列，用信息序列與系統(tǒng)矩陣相乘，則得出循環(huán)碼，容易出錯的地方是矩陣T的設置以及編寫過程中的賦值，因為輸入信息序列時是按照二進制規(guī)則寫的，所以前四列較容易寫出來，求循環(huán)碼時是用信息序列與系統(tǒng)矩陣異或相乘，所以相乘后的數(shù)字要進行轉(zhuǎn)化，這一塊是此代碼的難點，如果稍有不慎就會出現(xiàn)數(shù)據(jù)溢出或傳值時未傳進去等問題，最后輸出丁矩陣時還要注意格式，為了使得輸出結(jié)果與課本上的形式相同，就要注意空格鍵的使用對于16行11列來說，遍歷時從0開始，到15，（從0到10），行數(shù)和列數(shù)的設置容易出錯。在兩個矩陣相乘時要注意第一個矩陣的行乘以第二個矩陣的列，所以第一個矩陣的列數(shù)和第二個矩陣的行數(shù)相同，這些細節(jié)都要注意。算法設計框圖如下：開始運行結(jié)果回1■■'C-\Window5\sy5tem32\Debug\rrv/y.ex*"4n書「書力：?1此生—.明§節(jié)為督,4碼位監(jiān)(7的息的為馬三一口馬馬；10EJeiEli1EJ笫一次消無后的生成矩陣為01回1■■'C-\Window5\sy5tem32\Debug\rrv/y.ex*"4n書「書力：?1此生—.明§節(jié)為督,4碼位監(jiān)(7的息的為馬三一口馬馬；10EJeiEli1EJ笫一次消無后的生成矩陣為0100第二次消元后的生成矩陣為1Q01011QQ1001Q1eQ001Q11e系統(tǒng)形式的生成矩陣為01EJ017,4)eais環(huán)碼00EJ11110001101111111O111Q10111011101[■J"C:\Windows\sy5tem32\Debjg\eirwy.exe"IDC00600000000WQi0001011001000101100011曬11E01000100111QiQi01011000L1Q0110001011101110101060100010110S11001110101010100111011101100011001100010110111010011110111010011111111111PressanykeytDcontinue.總結(jié)此次寫代碼難度較大，因為所要解決的問題也較復雜，之前接觸的這課程的相關編程不多，所以只是學到了理論知識，但是此次的編程需要用到大一大二學到的相關編程知識，所以我首先復習了編程的相關知識點，再根據(jù)選題，對相關的編碼進行系統(tǒng)復習，最后才開始編寫代碼，寫代碼時要從數(shù)學問題出發(fā)，