編碼理論簡介

第1頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng信息論與編碼宋鵬2014年春E-mail：songpeng@（第一講）

─────────────────

緒論第2頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第1講：緒論第2講：信息論概論第3講：無失真信源編碼方法Ⅰ第4講：無失真信源編碼方法Ⅱ第5講：信道編碼原理第6講：線性分組碼第7講：上機Ⅰ（線性分組碼）第8講：循環(huán)碼Ⅰ第9講：循環(huán)碼Ⅱ第10講：BCH碼與RS碼Ⅰ第11講：BCH碼與RS碼Ⅱ第12講：卷積碼Ⅰ第13講：卷積碼Ⅱ第14講：上機Ⅱ（卷積碼）第15講：總復(fù)習(xí)第16講：考試目錄第3頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng課程概況學(xué)時：32目的：了解信息論與編碼的作用與意義，對信息論與編碼的研究方法和成果有廣泛的基本認識，學(xué)會應(yīng)用，為進一步研究打下基礎(chǔ)。特點：以概念和物理意義為主，數(shù)學(xué)推導(dǎo)盡量簡化。第4頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng其它有關(guān)事項1.課外閱讀：參考教材2.作業(yè)：20%3.上機：10%4.論文：兩年內(nèi)的國內(nèi)外期刊，以一兩篇為主，結(jié)合自己的理解，按電子學(xué)報論文形式，有創(chuàng)見更好。占10%5.考試：基本概念和基本計算。60%6.聯(lián)系方式：Email:songpeng@第5頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng教材與參考書1.《編碼理論(第二版)》，田麗華，西安電子科技大學(xué)出版社，2007年2.《信息論—基礎(chǔ)理論與應(yīng)用》，傅祖蕓，電子工業(yè)出版社3.《糾錯碼—原理與方法》，王新梅，西安電子科技大學(xué)出版社4.《ElementofInformationTheory

》，

ThomasM.Cover，清華大學(xué)出版社第6頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng其它參考書[5]《信息論與編碼（第二版）》，陳運，周亮，陳新，電子工業(yè)出版社，2007年[6]《信息論與編碼原理》，宋鵬，電子工業(yè)出版社，2011年[7]《編碼理論》，張鳴瑞，鄒世開，北京航空航天大學(xué)出版社，1990年

信息論不僅在方法論的層面上解決通信的有效性和可靠性問題，而且在認識論的層面上幫助認識事物的本質(zhì)。學(xué)完信息論之后，再重新審視一下周圍的事物，會有許多新的看法和認識。用信息論可以宏觀地認識某些政治問題，也可以定量地解決某些經(jīng)濟問題，還可以分析、解釋外語學(xué)習(xí)中存在的問題……總之，信息論是高層次信息技術(shù)人才必不可少的基礎(chǔ)知識。第7頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第8頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng內(nèi)容1.線性分組碼2.卷積碼講課：28學(xué)時上機：4學(xué)時重溫加深新內(nèi)容第9頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng內(nèi)容第10頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論123

通信系統(tǒng)模型Shannon信息論的中心問題4Shannon信息論的局限性

一些基本概念

信息的廣義性5

信息科學(xué)6第11頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.1一些基本概念Shannon于2001年2月24日在紐約謝世信息是構(gòu)成任何系統(tǒng)的三大要素之一，另外兩個要素是物質(zhì)和能量。信息雖然是無形的和抽象的，但它是系統(tǒng)的靈魂。信息論和晶體管同時誕生在Bell實驗室1948年，ClaudeShnnon（克勞德·香農(nóng)）在他的經(jīng)典論文“AMathematicalTheoryofCommunication”（通信中的數(shù)學(xué)理論）的引言部分中寫到：“通信中的基本問題就是在某一點精確或近似地再生另一點選擇的信息。”第12頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng《QUALCOMMEQUATION》高通的兩個關(guān)鍵創(chuàng)始人——艾文·雅各布和安德魯·維特比都擁有電子工程學(xué)博士學(xué)位，是克勞德·香農(nóng)的信息理論的卓越的學(xué)生。雅各布和維特比將香農(nóng)的觀點擴大到為高通的成功打下基礎(chǔ)的工程學(xué)系統(tǒng)中。高通的本質(zhì)是：它是一家以信息理論為基礎(chǔ)的信息技術(shù)公司。Qualcomm第13頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.1一些基本概念信息、消息、信號的區(qū)別信息：是系統(tǒng)傳輸、交換、存儲和處理的對象，信息載荷在語言、文字、數(shù)據(jù)、圖像等消息之中。消息：描述事物的特征和狀態(tài)。例如：包含有信息的語言、文字和圖像等。信號：把消息變換成適合信道傳輸?shù)奈锢砹浚@種物理量稱為信號（如電信號、光信號、聲音信號等）。第14頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.1一些基本概念信息、消息和信號是緊密相聯(lián)的三個不同的概念。同樣一個消息，對于不同的人從中可獲得的信息是不一樣的。第15頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論

信息化社會對人類社會發(fā)展的影響經(jīng)濟全球化和知識化，互聯(lián)網(wǎng)已成為社會資源重新分配的基本工具。人們的一切活動都將在信息空間中進行競爭和接受檢驗。導(dǎo)致第三次軍事革命，數(shù)字化部隊，數(shù)字化戰(zhàn)場。許多有形的東西開始向數(shù)字的、無形的方向轉(zhuǎn)變。也使人們越來越忙碌、越來越浮躁，在信息的大洋中有弄潮兒，也有溺水者。第16頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論為了表彰信息論的創(chuàng)始人Shannon的偉大功績，2000年10月6日IEEEInformationSociety的25名成員，在Shannon兒童時代的老家Michigan的Gaylord舉行了Shannon塑像的落成典禮。第17頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論著名信息論和編碼學(xué)者Dr.RichardBlahut在Shannon塑像落成典禮上的題詞中說：“在我看來，兩三百年之后，當(dāng)人們回過頭來看我們這個時代的時候，他們可能不會記得誰曾是美國的總統(tǒng)，他們也不會記得誰曾是影星或搖滾歌星，但是仍然會知曉Shannon的名字，學(xué)校里仍然會講授信息論”。第18頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論

塞繆爾·莫爾斯（SamuelFinleyBreeseMorse，1791-1872），作為一名畫家是成功的。莫爾斯曾兩度赴歐洲留學(xué)，在肖像畫和歷史繪畫方面成了當(dāng)時公認的一流畫家。1826年至1842年任美國畫家協(xié)會主席。

在一次遠洋旅途中，莫爾斯結(jié)識了杰克遜。杰克遜是波士頓城的一位醫(yī)生，也是一位電學(xué)博士。閑聊中，杰克遜把話題轉(zhuǎn)到電磁感應(yīng)現(xiàn)象上。

從此，莫爾斯走上了科學(xué)發(fā)明的崎嶇道路。為了維持生活，莫爾斯于1836年不得不重操舊業(yè)，擔(dān)任紐約大學(xué)藝術(shù)及設(shè)計教授。課余時間，他仍然繼續(xù)從事電報發(fā)明工作。終于在1837年9月4日，莫爾斯制造出了一臺電報機。

1844年5月24日，在華盛頓國會大廈聯(lián)邦最高法院會議廳里，進行電報發(fā)收試驗。年過半百的莫爾斯在預(yù)先約定的時間，興奮地向巴爾的摩發(fā)出人類歷史上的第一份電報。他的助手很快收到那份只有一句話的電報：“上帝創(chuàng)造了何等的奇跡!”第19頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1862年31歲，麥克斯韋發(fā)表了第二篇論文《論物理力線》，不但進一步發(fā)展了法拉第的思想，擴充到磁場變化產(chǎn)生電場，而且得到了新的結(jié)果：電場變化產(chǎn)生磁場，由此預(yù)言了電磁波的存在，并證明了這種波的速度等于光速，揭示了光的電磁本質(zhì)。這篇文章包括了麥克斯韋研究電磁理論達到的主要結(jié)果。1864年他的第三篇論文《電磁場的動力學(xué)理論》，從幾個基本實驗事實出發(fā)，運用場論的觀點，以演繹法建立了系統(tǒng)的電磁理論。1873年出版的《電學(xué)和磁學(xué)論》一書是集電磁學(xué)大成的劃時代著作，全面地總結(jié)了19世紀(jì)中葉以前對電磁現(xiàn)象的研究成果，建立了完整的電磁理論體系。這是一部可以同牛頓的《自然哲學(xué)的數(shù)學(xué)原理》、達爾文的《物種起源》和賴爾的《地質(zhì)學(xué)原理》相媲美的里程碑式的著作。

麥克斯韋的主要科學(xué)貢獻在電磁學(xué)方面，同時在天體物理學(xué)、氣體分子運動論、熱力學(xué)、統(tǒng)計物理學(xué)等方面，都作出了卓越的成績。正如量子論的創(chuàng)立者普朗克（MaxPlankl858—1947）指出的：“麥克斯韋的光輝名字將永遠鐫刻在經(jīng)典物理學(xué)家的門扉上，永放光芒。從生地來說，他屬于愛丁堡；從個性來說，他屬于劍橋大學(xué)；從功績來說，他屬于全世界”。第20頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論

赫茲是一個短命的物理學(xué)家。他于1894年逝世時，年僅37歲。

1886年29歲發(fā)現(xiàn)電磁波，其后不到6年，意大利的馬可尼、俄國的波波夫分別實現(xiàn)廠無線電傳播，并很快投入實際使用。其他利用電磁波的技術(shù)：無線電報（1894年）、無線電廣播（1906年）、無線電導(dǎo)航（1911年）、無線電話（1916年）、短波通訊（1921年）、無線電傳真（1923年）、電視（1929年）、微波通訊（1933年）、雷達（1935年），以及遙控、遙感、衛(wèi)星通訊、射電天文學(xué)……它們使整個世界面貌發(fā)生了深刻的變化。

赫茲關(guān)于電磁波的實驗，為無線電技術(shù)的發(fā)展開拓了新的道路，構(gòu)成了現(xiàn)代文明的骨架，后人為了紀(jì)念他，把頻率的單位定為赫茲。第21頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1876-------------貝爾發(fā)明電話貝爾制成的電話機

貝爾于1875年制成左圖電話的原型。這個裝置由一圈電線、一個磁臂和一塊張緊薄膜組成。聲音震動薄膜，再振動磁臂。磁石的移動令線圈產(chǎn)生波動的電流。這個電訊號可利用線路另一端的相同裝置再轉(zhuǎn)換回聲音。第22頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論信息論的創(chuàng)始人香農(nóng)Shannon，1916年生于美國，大學(xué)時代在美國密執(zhí)安大學(xué)和麻省理工學(xué)院學(xué)習(xí)，修過布爾代數(shù)課，并曾在發(fā)明微分分析儀的數(shù)學(xué)家布什的指導(dǎo)下使用微分分析儀，這使他對繼電器電路的分析產(chǎn)生興趣。他認為這些電路的設(shè)計可用符號邏輯來實現(xiàn)，并意識到分析繼電器的有效數(shù)學(xué)工具正是布爾代數(shù)。1938年，香農(nóng)發(fā)表了著名的論文《繼電器和開關(guān)電路的符號分析》，首次用布爾代數(shù)進行開關(guān)電路分析，并證明布爾代數(shù)的邏輯運算，可以通過繼電器電路來實現(xiàn)，明確地給出了實現(xiàn)加、減、乘、除等運算的電子電路的設(shè)計方法。這篇論文成為開關(guān)電路理論的開端。

后來，香農(nóng)到貝爾實驗室工作，他進一步證明了可以采用能實現(xiàn)布爾代數(shù)運算的繼電器或電子元件來制造計算機，香農(nóng)的理論還為計算機具有邏輯功能奠定了基礎(chǔ)，從而使電子計算機既能用于數(shù)值計算，又具有各種非數(shù)值應(yīng)用功能，使得以后的計算機在幾乎任何領(lǐng)域中都得到了廣泛的應(yīng)用。

無失真變長信源編碼定理（香農(nóng)第一定理）；有噪信道編碼定理（香農(nóng)第二定理）；保真準(zhǔn)則下信源編碼定理（香農(nóng)第三定理）。第23頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論香農(nóng)證明：只要信息傳輸速率小于信道容量C，傳輸?shù)腻e誤概率可以任意地小，反過來如果超過信道容量，則傳輸?shù)腻e誤是不可避免的。信息論解決了通信中的兩個基本問題信道編碼：在香農(nóng)以前的錯誤觀點：增加信道的信息傳輸速率總要引起錯誤概率增加，認為要使錯誤概率為零，則傳輸速率只能為零。信源編碼：達到不失真信源壓縮編碼的極限（最低）編碼速率是多少？答案：這個極限速率等于該信源的熵H。第24頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.2通信系統(tǒng)模型信息論—

通信的數(shù)學(xué)理論：是研究信息的傳輸、存儲和處理的科學(xué)。通信的基本問題：是在彼時（存儲情況）或彼地（通信情況）精確地或近似地再現(xiàn)此時、此地發(fā)出的消息。信息論研究的主要問題：在通信系統(tǒng)設(shè)計中如何實現(xiàn)有效性和可靠性。第25頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.2通信系統(tǒng)模型各種通信系統(tǒng)的形式和用途各不相同，但從信息傳輸、存儲和處理的角度來看，本質(zhì)上有許多共同之處。有收發(fā)兩端的單向通信系統(tǒng)模型：第26頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.2通信系統(tǒng)模型

信源：是產(chǎn)生消息的源。信源研究的主要問題：消息的統(tǒng)計特性和信源產(chǎn)生信息的速率。

編碼器：將信源發(fā)出的消息變換成適于信道傳送的信號的設(shè)備。信源編碼器糾錯編碼器調(diào)制器不一定每個系統(tǒng)的編碼器都含有這3個部分信道編碼器：糾錯編碼器＋調(diào)制器第27頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.2通信系統(tǒng)模型第28頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.2通信系統(tǒng)模型

信道：將信號從發(fā)端傳送到收端的媒質(zhì)或通道。信道的種類：干擾源：為了分析方便，將整個通信系統(tǒng)中各部分引入的各種干擾，如衰落、多徑、碼間干擾、非線性失真、可加噪聲等都集中表示為一個方框作用于信道。干擾源的統(tǒng)計特性：劃分信道的重要因素，決定信道傳輸能力的決定因素。兩大類干擾：加性干擾；乘性干擾。信道的中心課題：信道的統(tǒng)計特性和信道容量。實現(xiàn)有效和可靠通信主要困難：系統(tǒng)中的干擾。通信理論研究的中心課題：如何抗干擾。第29頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.2通信系統(tǒng)模型

譯碼器：編碼的逆變換從受干擾的信號中最大限度地提取出有關(guān)信源輸出消息的信息，應(yīng)盡可能精確地恢復(fù)信源的輸出，并將它們送給信宿。

信宿：信息的接收者，可以是人或物，且與信源處于不同地點或存在于不同時刻。第30頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.2通信系統(tǒng)模型它根據(jù)實際情況而定信源編碼和信道編碼統(tǒng)一設(shè)計問題Shannon開創(chuàng)的在20世紀(jì)七八十年代得到廣泛研究的“多用戶信息論”系統(tǒng)的模型不是不變的多用戶信息系統(tǒng)第31頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.3Shannon信息論的中心問題Shannon信息論的基本任務(wù)：為設(shè)計有效、可靠的通信系統(tǒng)提供理論依據(jù)。通信的基本目的：在接收端精確地或以給定的失真度重現(xiàn)信源的輸出。第32頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.3Shannon信息論的中心問題

信源編碼問題

信源編碼器作用：根據(jù)失真度準(zhǔn)則對信源的輸出進行劃分，給每一類以不同的表示，即碼字。

信源譯碼器的作用：根據(jù)收到的信源表示恢復(fù)出信源所屬的類。

失真度與碼長的關(guān)系：精確度要求越高（失真度要求越低）對信源的劃分就要越細，因而表示信源所需的信息量或碼長就越大。

信息論關(guān)心的信源編碼問題：在給定信源和失真度條件下，要多大信息速率才行？或?qū)o定信源保留一定的信息速率下，可以達到的最小失真是多少？如何實現(xiàn)這一理論結(jié)果（即找出實際可行的信源編碼和譯碼方法）？第33頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.3Shannon信息論的中心問題

信道編碼問題研究在保證信息傳輸可靠性（如錯誤概率小于給定值）的條件下最有效地利用信道的傳信能力；尋找實際可行的編、譯碼方法。若R<C，則可以將速率為R的信息以任意高的可靠性傳送至接收端；若R>C，則不可能。第34頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.3Shannon信息論的中心問題

編碼理論的產(chǎn)生信息論在研究信源和信道編碼定理時所用的方法都是隨機編碼的方法，是非構(gòu)造性的，不能提供具體的編、譯碼方法。

糾錯編碼理論：Hamming（1950）編碼理論—在20世紀(jì)50年代末～60年代大發(fā)展。

信源編碼理論：信息率失真理論（Shannon（1959）和Berger（1971））數(shù)據(jù)壓縮技術(shù)（Davisson&Gray（1976）以及Gilbert（1991））第35頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.3Shannon信息論的中心問題Shannon信息論的特點通信系統(tǒng)設(shè)計的中心問題

將概率統(tǒng)計的觀點和方法引入到通信理論研究中；揭示了通信系統(tǒng)中傳送的對象是信息，并對信息給出科學(xué)的定量的描述。

在隨機噪聲干擾下如何有效而可靠地傳送信息；實現(xiàn)這一目標(biāo)的途徑是編碼（信源編碼和信道編碼）。第36頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.3Shannon信息論的中心問題信息論研究的內(nèi)容信息論基礎(chǔ)：也稱狹義信息論/經(jīng)典信息論/香農(nóng)信息論。主要研究信息測度、信道容量、信息率失真函數(shù)，與這三個概念相對應(yīng)的香農(nóng)三定理，信源編碼，信道編碼。第37頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.3Shannon信息論的中心問題信息論研究的內(nèi)容一般信息論：主要研究信息傳輸和處理問題。除香農(nóng)基本理論之外，還包括噪聲理論、信號濾波和預(yù)測、統(tǒng)計檢測和估計理論、調(diào)制理論。后一部分內(nèi)容以維納為代表。第38頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.3Shannon信息論的中心問題信息論研究的內(nèi)容廣義信息論：是一門綜合性的新型學(xué)科——信息科學(xué)。至今沒有嚴(yán)格的定義。凡是能夠用廣義通信系統(tǒng)模型描述的過程或系統(tǒng)，都能用信息基本理論來研究。第39頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.4Shannon信息論的局限性Shannon信息論的局限性：Shannon通信系統(tǒng)的模型

Shannon的模型是很理想的抽象，高度概括了實際中各類通信系統(tǒng)的本質(zhì)。遠遠不能面面俱到地刻畫人類的實際通信問題。Shannon信息論的功績

Shannon信息論指出了實現(xiàn)有效而可靠通信的必由之路是數(shù)字化和編碼。通信的數(shù)學(xué)理論成為幾十年來數(shù)字化革命的理論基礎(chǔ)。

信息論的發(fā)展幾十年來信息論的理論發(fā)展和實際應(yīng)用走過了曲折而艱辛的道路。在學(xué)術(shù)界，信息論的“死”與“活”的爭論一直存在。第40頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.4Shannon信息論的局限性信源框?qū)τ诳梢远棵枋龅男畔?，Shannon信息論就有用武之地；對于那些難于定量描述的信息，Shannon信息論就顯得無能為力了。Shannon的通信系統(tǒng)模型將信源用一個框表示，引入概率統(tǒng)計工具來描述信源產(chǎn)生消息的規(guī)律。如果實際信源確如這種數(shù)學(xué)描述，那么這種方法就應(yīng)該是有效地、確切地表述了實際信源，否則這種表述只能是近似的，甚至是根本無效的。第41頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1.4Shannon信息論的局限性信宿框人接收消息、提取信息的過程與人畢生的生活經(jīng)歷和經(jīng)驗積累是有關(guān)的，有些消息的接收可能對幾十年后的判斷和信息提取有關(guān)。Shannon模型的信宿是信息的接收者，仍然假定它是一個概率空間，而與發(fā)端消息空間相同，此時彼地（通信系統(tǒng)）或彼時（存儲系統(tǒng)）彼地相互作用。但是當(dāng)人作為信宿時，他的接收消息空間與發(fā)送消息空間往往是不相同的，接收判決策略也因人而異，而且它是動態(tài)變化的，可能擴大可能縮小。雖然有些信息我們還給不出可用的數(shù)學(xué)模型來描述它，因而無法進行量度和計算，但它們常常和可以定量描述的信息有著密切的關(guān)系。第42頁2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章緒論1