編碼理論簡介

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

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

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

》，

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

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

通信系統模型Shannon信息論的中心問題4Shannon信息論的局限性

一些基本概念

信息的廣義性5

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

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

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

在一次遠洋旅途中，莫爾斯結識了杰克遜。杰克遜是波士頓城的一位醫生，也是一位電學博士。閑聊中，杰克遜把話題轉到電磁感應現象上。

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

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

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

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

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

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

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

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

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

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

信源：是產生消息的源。信源研究的主要問題：消息的統計特性和信源產生信息的速率。

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

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

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

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

信源編碼問題

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

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

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

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

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

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

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

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

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

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

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

Shannon信息論指出了實現有效而可靠通信的必由之路是數字化和編碼。通信的數學理論成為幾十年來數字化革命的理論基礎。

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