《信息論與編碼》課件1第1章

第1章緒論

1.1信息的定義與性質(zhì)1.2信息論的主要研究?jī)?nèi)容1.3信道編碼的研究?jī)?nèi)容與發(fā)展簡(jiǎn)史1.4信源編碼的研究?jī)?nèi)容與發(fā)展簡(jiǎn)史

1.1信息的定義與性質(zhì)人類(lèi)在日常生活和社會(huì)活動(dòng)中，一時(shí)一刻也離不開(kāi)信息的交流。特別是在今天的信息社會(huì)中，人們要有效地工作、明智地行動(dòng)必須擁有充分的信息。但是，究竟什么是“信息”呢？“信息”有什么屬性？怎樣度量？這些概念通常卻是含糊不清的。自從信息論這一學(xué)科誕生以來(lái)，“信息”這一名詞便在工程上有了比較明確的概念，成為一個(gè)基本的技術(shù)術(shù)語(yǔ)。1.1.1信息的定義“信息”是一個(gè)常用詞，在日常生活中泛指“消息”、“信號(hào)”、“情況”、“情報(bào)”、“知識(shí)”等。例如，人們從報(bào)紙或電視新聞中得到某些消息，便說(shuō)得到了信息;司機(jī)根據(jù)紅綠燈信號(hào)得到車(chē)輛行駛信息，等等。隨著信息的開(kāi)發(fā)和利用，“信息”也逐漸顯示出其巨大的威力，為人類(lèi)和人類(lèi)社會(huì)的進(jìn)步帶來(lái)明顯的經(jīng)濟(jì)效益和社會(huì)效益。因此，在日常生活和社會(huì)活動(dòng)中“信息”又被賦予各種動(dòng)人的比喻?？梢?jiàn)，通常的“信息”概念僅僅是從實(shí)用角度出發(fā)在某個(gè)側(cè)面為“信息”建立的非常粗淺、非常模糊且具有很強(qiáng)主觀性的概念，這些概念對(duì)于不同的人在不同的時(shí)間、地點(diǎn)和條件下，其意義、程度有很大的差異。因此，關(guān)于信息的這些含糊不清的概念必須進(jìn)行加工、概括、提升和開(kāi)拓。在我們的專(zhuān)業(yè)學(xué)習(xí)中，信息通常是指代表著某一個(gè)抽象的有待傳送、交換、存儲(chǔ)以及提取和識(shí)別的內(nèi)容，它有嚴(yán)格、確切的含義，有一定的數(shù)學(xué)模式并能定量地度量。信息論的主要奠基人香農(nóng)（C.E.Shannon）以通信系統(tǒng)為物理模型，用概率測(cè)度和數(shù)理統(tǒng)計(jì)的方法研究通信系統(tǒng)中的基本問(wèn)題，并于1948年在《貝爾系統(tǒng)技術(shù)》雜志上發(fā)表了著名論文《通信的數(shù)學(xué)理論》，奠定了信息論的理論基礎(chǔ)。在這篇論文中他將信息定義為“用來(lái)消除不確定性的東西”。圖1-1給出了一個(gè)一般的通信系統(tǒng)。在這樣的通信系統(tǒng)中，發(fā)信者（信源）發(fā)出的信息在某種物理媒介（信道）中傳輸并被收信者（信宿）接收。例如在由人與人的信息交流活動(dòng)所構(gòu)成的信息系統(tǒng)中，傳輸?shù)氖侨梭w各種感覺(jué)器官（如眼、耳、鼻、舌等）所能感知的光、聲和字符等信號(hào);在電信系統(tǒng)中，消息（符號(hào)）便為不同頻率、不同相位、不同強(qiáng)弱的電信號(hào)。因此，我們可以將這種一般的通信系統(tǒng)表述為傳輸消息（符號(hào)）的系統(tǒng)。圖1-1一般的通信系統(tǒng)在圖1-1所示的通信系統(tǒng)中，顯然存在著一個(gè)能夠使發(fā)信、收信雙方都能理解的符號(hào)表（如某種文字、語(yǔ)音、圖像、圖形或電信號(hào)）。然而，通信過(guò)程是一個(gè)隨機(jī)的、不確定的過(guò)程，即誰(shuí)使用此通信系統(tǒng)、在什么時(shí)間發(fā)出何種具體符號(hào)是不能夠事先預(yù)料的，而且通信過(guò)程中不可避免的干擾也是隨機(jī)出現(xiàn)的。這些隨機(jī)性因素使得這種消息或符號(hào)的傳遞過(guò)程有一個(gè)最基本、最普遍卻又十分不引人注意的特點(diǎn)，就是收信者在收到符號(hào)之前不知道發(fā)信者發(fā)出的是哪一個(gè)符號(hào)，即對(duì)于收信者而言具有一定的隨機(jī)性或不確定性。只有通過(guò)通信過(guò)程，收信者才能知道是誰(shuí)向他發(fā)出符號(hào)，發(fā)出的是何種符號(hào)，消除關(guān)于發(fā)信者及其發(fā)出何種符號(hào)的不確定性。由此可知，信息的傳遞過(guò)程對(duì)于接收者而言是一個(gè)由不確定到確定的過(guò)程，而實(shí)現(xiàn)由不確定到確定的轉(zhuǎn)變，所依賴(lài)的只能是接收者由通信過(guò)程所獲得的信息。所以，信息確實(shí)是用來(lái)消除不確定性的東西，這也就是香農(nóng)信息定義的含義。對(duì)于一次實(shí)際的通信過(guò)程，由于信道中存在著隨機(jī)性的干擾，因此接收者在通信完成之后可能完全消除了關(guān)于信源的不確定性，也可能只消除了部分不確定性，甚至仍然具有同樣的不確定性。根據(jù)香農(nóng)信息定義，接收者由這一通信過(guò)程所獲得的信息量是不同的，即可能獲得了信源輸出的全部信息，也可能只獲得部分信息甚至是沒(méi)有得到信息。度有關(guān)。只要原有的不確定性程度有所減少，接收者便由此次通信得到了一定的信息。所以，香農(nóng)信息定義一方面指明了信息與消息、信號(hào)、情況、情報(bào)的差異，即消息、信號(hào)、情況、情報(bào)只是攜帶著信息，是信息的載體，并不是信息本身，信息則是這個(gè)載體所攜帶的內(nèi)容。另一方面，香農(nóng)信息定義指明了信息是可以度量的，即消息、信號(hào)、情況、情報(bào)所攜帶的信息量的大小與接收者通過(guò)通信過(guò)程消除或減少對(duì)于該事物的不確定程礎(chǔ)。但是，該定義只是從信息的功能上對(duì)信息加以描述，只是說(shuō)出了信息能夠做什么，有什么用，并沒(méi)有正面回答信息是什么。關(guān)于信息的定義，學(xué)術(shù)界有多種描述，但是尚無(wú)一種適用范圍廣、得到普遍公認(rèn)的定義形式。這說(shuō)明人們對(duì)于信息的研究還沒(méi)有達(dá)到完全揭示本質(zhì)的程礎(chǔ)。但是，該定義只是從信息的功能上對(duì)信息加以描述，只是說(shuō)出了信息能夠做什么，有什么用，并沒(méi)有正面回答信息是什么。關(guān)于信息的定義，學(xué)術(shù)界有多種描述，但是尚無(wú)一種適用范圍廣、得到普遍公認(rèn)的定義形式。這說(shuō)明人們對(duì)于信息的研究還沒(méi)有達(dá)到完全揭示本質(zhì)的程度。但是人們?cè)谶@一領(lǐng)域所從事的研究、所提出的各種定義仍然在一定程度或從一定的側(cè)面觸及到了信息的某些實(shí)質(zhì)問(wèn)題。例如，控制論的創(chuàng)始人維納（N.Wiener）1948年在《控制論——?jiǎng)游锖蜋C(jī)器中的通信與控制問(wèn)題》一書(shū)中指出：“信息就是信息，不是物質(zhì)，也不是能量”。1950年，他又在《人有人的用處》中提出：“信息就是人和外界互相作用的過(guò)程中相互交換的內(nèi)容和名稱(chēng)”。維納的定義表明，人與客觀世界除了物質(zhì)、能量的交換之外，還有信息的交換。人類(lèi)通過(guò)語(yǔ)言、文字、圖像等各種手段交換信息，學(xué)習(xí)有關(guān)彼此的知識(shí)，使人類(lèi)社會(huì)成為一個(gè)有機(jī)的整體。由此可知，信息及其信息的交換確實(shí)也是一種客觀存在。同時(shí)也應(yīng)當(dāng)注意到，信息的交換不僅發(fā)生在人與外界相互作用的過(guò)程中，在沒(méi)有人參與的許多相互作用的過(guò)程中同樣包含信息的交換。從更一般的意義上可以認(rèn)為，信息反映了一切事物的存在和運(yùn)動(dòng)方式的描述。此時(shí)信息的定義表述為：事物運(yùn)動(dòng)（包括客觀世界和主觀世界以及人腦的思維活動(dòng)）所表現(xiàn)出來(lái)的各種狀態(tài)和方式。在這種定義下，維納所說(shuō)的“人與外界……相互交換的內(nèi)容”不是別的，正是“事物運(yùn)動(dòng)的狀態(tài)和方式”，即人從外界得到的信息是外界事物的運(yùn)動(dòng)狀態(tài)和方式，而人給外界的信息則是人的思維運(yùn)動(dòng)的狀態(tài)和方式，是人的意志和命令。對(duì)于香農(nóng)定義中的所謂不確定性，則正是對(duì)于事物運(yùn)動(dòng)的狀態(tài)和方式所具有的不確定性，即不知道事物處于什么運(yùn)動(dòng)狀態(tài)中，不知道事物正在以什么方式運(yùn)動(dòng)。要消除這種不確定性，就需要知道事物運(yùn)動(dòng)的狀態(tài)和方式，需要得到信息。因此，信息——事物運(yùn)動(dòng)的狀態(tài)和方式，就是用來(lái)消除不確定性的東西。可見(jiàn)，這一定義不僅統(tǒng)一了多種定義的概念，而且從更一般的意義上較好地揭示了信息的本質(zhì)。近十幾年來(lái)，以計(jì)算機(jī)、信息處理、網(wǎng)絡(luò)、通信和微電子技術(shù)的發(fā)展、應(yīng)用和普及為標(biāo)志的信息技術(shù)得到了迅猛發(fā)展。人類(lèi)已經(jīng)進(jìn)入信息時(shí)代，我們對(duì)于信息及其在人類(lèi)的生活和社會(huì)活動(dòng)中的作用有了更加明確、深刻的認(rèn)識(shí)，“信息”已經(jīng)成為人類(lèi)在“數(shù)字化生存”中的一項(xiàng)基本要素，決定了人在現(xiàn)代社會(huì)中的生存方式和生存質(zhì)量。由上面的分析我們可以歸納出以下三點(diǎn)：（1）信息不是物質(zhì)或能量，它是自然世界和人類(lèi)社會(huì)中的另一種基本要素;（2）信息具有客觀存在的屬性，是客觀事物運(yùn)動(dòng)狀態(tài)和方式的表征，不完全取決于人的主觀認(rèn)識(shí);（3）信息又與主觀認(rèn)識(shí)有關(guān)，是客觀事物在人腦中的反映。在信息處理學(xué)科中，信息常表示為對(duì)數(shù)據(jù)含義的一種解釋?zhuān)鴶?shù)據(jù)則是那些可以記錄下來(lái)、反映事物運(yùn)動(dòng)狀態(tài)和方式的符號(hào)，包括數(shù)值、曲線(xiàn)、圖像、語(yǔ)音等。在信息的處理過(guò)程中，輸入的是數(shù)據(jù)，處理后的輸出結(jié)果仍然是數(shù)據(jù)，而信息則隱含于這些數(shù)據(jù)中，針對(duì)某種特定的目的，可由數(shù)據(jù)解釋其含義。例如衛(wèi)星獲得的地物遙感影像數(shù)據(jù)，經(jīng)數(shù)字圖像處理、識(shí)別與分析后，輸出仍是數(shù)據(jù)。對(duì)于同一幅遙感影像數(shù)據(jù)，通過(guò)不同方法處理可以得到不同的地物目標(biāo)分類(lèi)，農(nóng)業(yè)、礦業(yè)、軍事等不同的應(yīng)用部門(mén)由輸出數(shù)據(jù)或影像可解譯出不同的結(jié)果，獲取不同的信息，如農(nóng)作物面積、礦藏分布或軍事設(shè)施。在我們的專(zhuān)業(yè)學(xué)習(xí)中，通常遇到的是這種狹義的信息概念。1.1.2信息的性質(zhì)信息作為客觀世界的第三要素，與物質(zhì)、能量相比具有一些特殊的性質(zhì)。（1）信息是無(wú)形的。信息不同于物質(zhì)和能量，它是客觀世界中的一種看不見(jiàn)、摸不著、沒(méi)有重量的基本要素。新聞、報(bào)紙、信號(hào)、密碼等只不過(guò)是信息的載體。（2）信息是可以共享的。在客觀世界中，物質(zhì)和能量所遵循的基本規(guī)律之一是守恒定律，即物質(zhì)和能量不能創(chuàng)造也不能消滅，只能轉(zhuǎn)換。然而，信息不受守恒定律的制約，沒(méi)有重量，易于復(fù)制，能以極快的速度傳播，是一種可以共享的重要的社會(huì)資源。信息的交流不但不會(huì)使信息的持有者失去原有信息，而且可以獲得新的信息。在現(xiàn)代社會(huì)中，飛速發(fā)展的通信手段和信息處理技術(shù)為信息資源的充分共享提供了優(yōu)越的條件，同時(shí)國(guó)家之間的軍事對(duì)抗、商業(yè)活動(dòng)中的市場(chǎng)爭(zhēng)奪、多媒體數(shù)字產(chǎn)品的版權(quán)歸屬等，也對(duì)信息的安全和保密提出了更高的要求。（3）信息是無(wú)限的。客觀世界的運(yùn)動(dòng)是永恒的。作為描述客觀事物的運(yùn)動(dòng)狀態(tài)和運(yùn)動(dòng)方式的信息，與客觀事物及它們的運(yùn)動(dòng)一樣，也是永恒的。在組成客觀世界的三大要素中，人類(lèi)可以使用的物質(zhì)和能量資源只能供有限的人使用，總有一天會(huì)出現(xiàn)短缺危機(jī)，而信息則永遠(yuǎn)在產(chǎn)生、更新和演變，可以多人共享使用，并且使用的人越多，其價(jià)值越高。信息已經(jīng)成為人類(lèi)社會(huì)中的一個(gè)取之不盡、用之不竭的知識(shí)源泉。信息的這一無(wú)限性在時(shí)空上表現(xiàn)為可擴(kuò)展性。例如，失去了現(xiàn)實(shí)應(yīng)用時(shí)效的歷史資料可以反映社會(huì)發(fā)展變化的統(tǒng)計(jì)規(guī)律，先進(jìn)地區(qū)的科學(xué)技術(shù)可以帶動(dòng)落后地區(qū)的經(jīng)濟(jì)發(fā)展。（4）信息是可開(kāi)發(fā)的。信息的開(kāi)發(fā)是指信息的表示、存儲(chǔ)、傳輸、處理和利用。顯然，信息的開(kāi)發(fā)和利用歷來(lái)是客觀世界發(fā)展、人類(lèi)文明史進(jìn)化的一個(gè)基本條件。在信息社會(huì)的今天，信息技術(shù)產(chǎn)業(yè)已成為推動(dòng)社會(huì)進(jìn)步，拉動(dòng)經(jīng)濟(jì)、科技、教育等各個(gè)領(lǐng)域發(fā)展的重要部分。（5）信息是可度量的。信息反映事物的運(yùn)動(dòng)狀態(tài)和方式。通過(guò)研究客觀世界所遵循的自然規(guī)律，人類(lèi)將不斷地認(rèn)識(shí)和掌握事物變化、發(fā)展的客觀規(guī)律，并且找出適當(dāng)?shù)姆椒枋鍪挛锏倪\(yùn)動(dòng)狀態(tài)和方式，于是反映客觀事物的運(yùn)動(dòng)狀態(tài)和方式的信息也可以按某種方式加以度量。例如，在香農(nóng)的信息定義中，信息量與事件發(fā)生的不確定程度及信源發(fā)出符號(hào)的隨機(jī)性有關(guān)，信息是關(guān)于事件隨機(jī)性的一種描述。因此，我們可以用概率統(tǒng)計(jì)的方法來(lái)度量信息。設(shè)發(fā)信者發(fā)出的符號(hào)ai出現(xiàn)的概率為P(ai)。P(ai)愈小，則ai的隨機(jī)性即不確定性愈大，ai含有的信息量也就愈大。由此可知，ai具有的信息量應(yīng)當(dāng)與ai發(fā)生的概率成反比，即（1.1）在通信的過(guò)程中，信道中不可避免地存在著隨機(jī)性的干擾。于是，在接收端收到符號(hào)bj時(shí)，發(fā)信者發(fā)出符號(hào)為ai的可能性可以用條件概率P(ai|bj)來(lái)表示,那么在接收到符號(hào)bj后對(duì)發(fā)信者發(fā)出的符號(hào)是否是ai仍然存在的不確定性便成為于是，通過(guò)信息的傳遞，接收者對(duì)于事件ai的不確定性改變了，表明通過(guò)這樣的信息傳輸系統(tǒng)我們由bj得到了關(guān)于ai的信息。顯然,由這一通信過(guò)程所獲得的信息量的大小應(yīng)當(dāng)與關(guān)于事件ai的不確定性的改變量有關(guān)。于是，通過(guò)信息傳輸，接收者由bj得到的關(guān)于ai的信息量可以表示為可見(jiàn)，香農(nóng)給出的信息度量確實(shí)是一種對(duì)通信過(guò)程中所消除的不確定性的度量。1.2信息論的主要研究?jī)?nèi)容由上面的討論我們知道，信息論的研究對(duì)象是傳輸消息（符號(hào)）的系統(tǒng)。由于這些消息載荷著信息，因此這種消息傳輸系統(tǒng)即為信息傳輸系統(tǒng)，通常簡(jiǎn)稱(chēng)為通信系統(tǒng)。信息論的創(chuàng)始人香農(nóng)以狹義的通信系統(tǒng)為物理模型，研究信息的定量描述方法和編碼理論，分析通信系統(tǒng)中的有效性和可靠性問(wèn)題，奠定了信息論的理論體系。隨著科學(xué)技術(shù)的發(fā)展，信息論的研究范圍、應(yīng)用領(lǐng)域和指導(dǎo)意義已遠(yuǎn)遠(yuǎn)超出了原來(lái)的范圍，成為研究廣義信息系統(tǒng)中一般規(guī)律的工程學(xué)科，它的主要目的是提高信息系統(tǒng)的可靠性和有效性，實(shí)現(xiàn)系統(tǒng)的最優(yōu)化。客觀世界中存在著各種各樣的信息傳輸、存儲(chǔ)和處理系統(tǒng)，如電報(bào)、電話(huà)、雷達(dá)、遙感、計(jì)算機(jī)系統(tǒng)等工程意義上的各類(lèi)狹義的通信系統(tǒng)，以及人類(lèi)社會(huì)的管理系統(tǒng)、生物有機(jī)體的神經(jīng)系統(tǒng)、生物遺傳系統(tǒng)等。這些系統(tǒng)的形式、用途各不相同，但從信息傳輸?shù)慕嵌确治?，在本質(zhì)上它們有許多共同之處，即在這些系統(tǒng)中都有信息的發(fā)送者和接收者，都存在著信息的傳遞、交換和處理。對(duì)于這些互不相同的信息系統(tǒng)，我們可抽象為一個(gè)廣義的通信系統(tǒng)來(lái)描述，并概括為圖1-2所示的模型。圖1-2通信系統(tǒng)模型廣義的通信系統(tǒng)模型主要由信源、編碼器、信道、譯碼器和信宿五個(gè)部分組成。利用這樣的模型我們可以分析、探討通信系統(tǒng)在傳輸消息的過(guò)程中的一般規(guī)律。

(1)信源：發(fā)出信息的客觀事物，可以是人，也可以是某種設(shè)備或物體。由于消息是信息的載體，因此信源的輸出是消息或消息序列，如電信號(hào)、文字、圖像、語(yǔ)音等。消息或消息序列可以是連續(xù)的，也可以是離散的。由前面的討論我們已經(jīng)知道，信息的基本屬性之一是隨機(jī)性，因此信源輸出的消息、消息序列需要用隨機(jī)過(guò)程加以描述。信源研究的主要問(wèn)題是其統(tǒng)計(jì)模型（統(tǒng)計(jì)特性描述）及信源所具有的信息量的定量表示。（2）信道：傳輸信號(hào)的物理媒介或通道。在狹義的通信系統(tǒng)中，實(shí)際信道有明線(xiàn)、電纜、波導(dǎo)、光纖、無(wú)線(xiàn)電傳播空間等。廣義的通信系統(tǒng)的信道多種多樣。除了傳輸信號(hào)，信道還具有存儲(chǔ)信號(hào)的作用，如書(shū)信在郵遞過(guò)程中不僅執(zhí)行信息的傳遞任務(wù)，同時(shí)也起到了信號(hào)的存儲(chǔ)作用。再如，計(jì)算機(jī)中的硬盤(pán)、移動(dòng)存儲(chǔ)設(shè)備不僅可以保存數(shù)據(jù)或文件，存儲(chǔ)的數(shù)據(jù)、文件也可以與其他計(jì)算機(jī)進(jìn)行交流，實(shí)現(xiàn)信息的傳遞和共享。信道研究的主要問(wèn)題是它能傳輸、存儲(chǔ)多少信息，即它的信道容量有多大。（3）編碼器：將信源輸出的消息或消息序列轉(zhuǎn)換成適合通信系統(tǒng)要求的信號(hào)的設(shè)備。不同的通信系統(tǒng)中允許的消息或消息序列的表示形式可能不同。例如，面對(duì)面的交談需將要表達(dá)的內(nèi)容通過(guò)發(fā)聲器官轉(zhuǎn)換成聽(tīng)覺(jué)器官能夠接收的聲波，并在允許聲波傳播的空間中傳輸;使用郵政通信需將要傳遞的消息轉(zhuǎn)換成文字并構(gòu)成規(guī)范化的書(shū)信;電報(bào)通信則需將文字轉(zhuǎn)換成由點(diǎn)、畫(huà)構(gòu)成的莫爾斯碼;語(yǔ)音、圖像、視頻等數(shù)字媒體文件需使用二進(jìn)制符號(hào)表示并按照一定的格式進(jìn)行處理與存儲(chǔ)。因此，對(duì)于任何通信系統(tǒng)而言，信源輸出的信息都必須通過(guò)編碼實(shí)現(xiàn)從消息到信號(hào)、數(shù)據(jù)的轉(zhuǎn)換，才能夠通過(guò)某種信道進(jìn)行傳輸、存儲(chǔ)和處理。由消息到信號(hào)、數(shù)據(jù)的轉(zhuǎn)換一般要經(jīng)過(guò)信源編碼器和信道編碼器。對(duì)于狹義通信系統(tǒng)，編碼器還包括調(diào)制等各種處理。編碼器研究的主要問(wèn)題是如何進(jìn)行信源編碼，使信源的消息被充分利用并可靠地通信。（4）譯碼器：編碼器的逆過(guò)程，它將信號(hào)轉(zhuǎn)變?yōu)橄?。與編碼器相對(duì)應(yīng)，譯碼器分為信道譯碼器和信源譯碼器。對(duì)于狹義的通信系統(tǒng)，還包括信號(hào)的接收與解調(diào)。（5）信宿：消息的接收者，即接收消息的人或設(shè)備。（6）噪聲源：信號(hào)在信道傳播的過(guò)程中常常會(huì)受到噪聲的干擾。噪聲可分為系統(tǒng)內(nèi)噪聲和系統(tǒng)外噪聲，如雷電、宇宙輻射、設(shè)備自身的電子噪聲和人為電子干擾等。在廣義通信系統(tǒng)模型中，這些干擾和噪聲都等效地折合為信道干擾，可看做是由一個(gè)噪聲源產(chǎn)生并作用于在信道中傳輸?shù)男盘?hào)。在通信系統(tǒng)中，噪聲是影響可靠通信的主要原因之一，可通過(guò)各種信道編碼技術(shù)提高系統(tǒng)的抗干擾能力。通過(guò)對(duì)廣義通信系統(tǒng)模型的分析可以看出，通信的基本目的是在接收端（信宿）準(zhǔn)確地或近似地再現(xiàn)從另一端（信源）選擇出來(lái)的消息，因而通信系統(tǒng)的基本問(wèn)題是信源、信道及編碼問(wèn)題，信息論的基本任務(wù)則是為設(shè)計(jì)有效而且可靠的信息系統(tǒng)提供理論依據(jù)。本教材主要涉及狹義的通信系統(tǒng)，即討論香農(nóng)的信息理論，在深入分析香農(nóng)信息論的基本概念和編碼定理的基礎(chǔ)上，研究提高信息系統(tǒng)有效性的理論與工程手段，即討論信源編碼原理和數(shù)據(jù)壓縮的一般方法。1.3信道編碼的研究?jī)?nèi)容與發(fā)展簡(jiǎn)史信道編碼是20世紀(jì)40年代末提出、60年代發(fā)展起來(lái)的一門(mén)提高數(shù)據(jù)傳輸可靠性的理論與技術(shù)，至今已有60余年的歷史。隨著數(shù)字通信的發(fā)展，特別是20世紀(jì)70年代以來(lái)，衛(wèi)星通信和高速數(shù)據(jù)網(wǎng)的飛速發(fā)展，對(duì)數(shù)據(jù)傳輸?shù)目煽啃蕴岢隽嗽絹?lái)越高的要求，因此，如何提高數(shù)據(jù)傳輸?shù)目煽啃砸恢笔峭ㄐ虐l(fā)展過(guò)程中研究的重點(diǎn)之一。自從1948年Shannon發(fā)表了《AMathematicalTheoryofCommunication》這篇論文后，就開(kāi)創(chuàng)了兩個(gè)現(xiàn)代研究領(lǐng)域——信息論和編碼理論。他最杰出的貢獻(xiàn)就是引入了概率論來(lái)分析和研究通信系統(tǒng)。在信道編碼領(lǐng)域，他給出了“信息”的一個(gè)非常有用的定義，以及幾個(gè)“信道編碼定理”，描述了給定通信系統(tǒng)可靠傳輸?shù)木_上界（稱(chēng)為信道容量）。在這篇論文中，最令人感興趣的結(jié)果是“noisychannelcodingtheoremforcontinuouschannelswithaveragepowerlimitations”，這個(gè)定理采用帶限加性高斯白噪聲信道模型，這個(gè)信道模型可以近似描述許多實(shí)際的數(shù)字通信和存儲(chǔ)系統(tǒng)。定理的證明表明，對(duì)于任何小于等于信道容量的傳輸速率，存在一個(gè)編碼方案，可以達(dá)到任意小的錯(cuò)誤概率;相反地，如果傳輸速率大于信道容量，則不存在任何編碼方案可以達(dá)到可靠的性能。然而，這是一個(gè)存在性定理，對(duì)于如何尋找合適的編碼方案，實(shí)現(xiàn)起來(lái)多么復(fù)雜，該定理并沒(méi)有給出任何指導(dǎo)。從1950年Hamming的工作開(kāi)始，許多通信工程師和編碼理論家已經(jīng)開(kāi)發(fā)了很多種不同的復(fù)雜度合理的方法，試圖接近Shannon所預(yù)期的性能。在這里，我們將沿著過(guò)去60余年編碼在通信和存儲(chǔ)系統(tǒng)中的應(yīng)用歷程來(lái)看一下在縮小實(shí)際系統(tǒng)和信道容量之間的距離上已經(jīng)取得的巨大進(jìn)步。在Shannon定義了可靠通信的理論極限的同時(shí)，Hamming和Golay正在著手開(kāi)發(fā)第一個(gè)可實(shí)現(xiàn)的差錯(cuò)控制方案，他們的工作開(kāi)辟了一個(gè)欣欣向榮的應(yīng)用數(shù)學(xué)的分支——編碼理論。通常認(rèn)為RichardHamming是發(fā)現(xiàn)第一個(gè)差錯(cuò)控制碼的人。在1946年，Hamming在Bell實(shí)驗(yàn)室工作，從事彈性理論的研究，然而，他最終在計(jì)算機(jī)上花費(fèi)了大量的精力。那時(shí)候，計(jì)算機(jī)的運(yùn)行非常不穩(wěn)定，雖然具備了檢錯(cuò)能力，但是當(dāng)發(fā)現(xiàn)錯(cuò)誤的時(shí)候，程序只能中斷執(zhí)行。那時(shí)Hamming的程序很少不中斷地從頭到尾執(zhí)行，他嘗試了很多方法對(duì)輸入進(jìn)行編碼，最終使得計(jì)算機(jī)能夠糾正單個(gè)錯(cuò)誤進(jìn)而能連續(xù)運(yùn)行。他的編碼方法是在每4比特信息位后面插入3比特校驗(yàn)位，校驗(yàn)位是由信息比特線(xiàn)性組合得到的，被后人稱(chēng)做Hamming碼（漢明碼）。雖然Hamming碼取得了很大的進(jìn)步，但也存在很多缺點(diǎn)：一是傳輸效率不高，二是在每個(gè)數(shù)據(jù)塊中只能糾正一個(gè)錯(cuò)誤。MarcelGolay指出了這些問(wèn)題并將Hamming的工作進(jìn)行了推廣，這就是著名的Golay碼。Golay碼將數(shù)據(jù)中每12個(gè)比特組成一個(gè)數(shù)據(jù)塊，然后插入11個(gè)比特的校驗(yàn)位，組成長(zhǎng)度為23比特的碼字，可以糾正3個(gè)比特錯(cuò)誤。這類(lèi)碼字的一個(gè)共同特點(diǎn)是在每k個(gè)信息比特之后插入r個(gè)校驗(yàn)比特組成n個(gè)比特的碼字，這就是眾所周知的分組碼。在引入信道編碼的這60余年當(dāng)中，已經(jīng)找到了很多性能優(yōu)良的分組碼，并得到了大量的應(yīng)用，比如Golay碼就曾被應(yīng)用到木星探測(cè)中。當(dāng)然，現(xiàn)在它早已經(jīng)被很多性能更好的編碼方式代替了。

1957年P(guān)range提出了循環(huán)碼的概念。這種碼字可以用多項(xiàng)式來(lái)描述，有很?chē)?yán)謹(jǐn)?shù)臄?shù)學(xué)結(jié)構(gòu)。它有一個(gè)很大的優(yōu)點(diǎn)是每個(gè)碼字循環(huán)移位后仍然是一個(gè)碼字，可以利用這種循環(huán)移位特性來(lái)降低編碼器和譯碼器的復(fù)雜度，尤其是譯碼，采用一種Meggitt譯碼器的結(jié)構(gòu)可以非常有效地對(duì)糾錯(cuò)能力較小的循環(huán)碼進(jìn)行譯碼，但是譯碼復(fù)雜度隨著糾錯(cuò)能力的提高指數(shù)增加。循環(huán)碼的一個(gè)很重要的子類(lèi)是1959年Hocquenghem以及1960年Bose和RayChaudhuri組成的研究小組發(fā)現(xiàn)的，這就是著名的BCH碼。Reed和Solomon還在多進(jìn)制上構(gòu)造出BCH碼，后人稱(chēng)之為RS碼。RS碼的出現(xiàn)是編碼歷史上一個(gè)很重要的進(jìn)步，因?yàn)樗梢约m正突發(fā)錯(cuò)誤。但是直到1967年Berlekamp才提出了一個(gè)有效的譯碼算法，RS碼才逐步得到廣泛應(yīng)用，如CD、DVD。雖然分組碼得到了成功的應(yīng)用，但是在使用過(guò)程中它也有幾個(gè)缺點(diǎn)：第一，由于分組碼是分幀的，因此在譯碼之前必須要接收到整個(gè)碼字才可以進(jìn)行，這會(huì)對(duì)系統(tǒng)引入一個(gè)不可接收的延遲，尤其是對(duì)于碼長(zhǎng)較長(zhǎng)的分組碼;第二，分組碼需要精確的幀同步;第三，大部分基于代數(shù)的譯碼器輸入的是硬判決比特，而不是解調(diào)器輸出的沒(méi)有量化的“軟”值。如果分組碼使用硬判決比特，則信道被假定為二進(jìn)制信道;如果是軟判決比特，則信道的輸出是連續(xù)取值的。然而，為了達(dá)到Shannon預(yù)測(cè)的性能限，需要采用連續(xù)取值的信道輸出。因此，雖然在相對(duì)較好的信道上分組碼可以取得卓越的性能，但是當(dāng)信噪比較低時(shí)，它具有相當(dāng)差的性能。注意，在低信噪比的情況下，分組碼較差的性能并不是碼本身的特性，而是由于硬判決譯碼具有次最優(yōu)特性，因此分組碼也可以用軟判決來(lái)譯碼。但在不久以前，人們還認(rèn)為軟判決譯碼太復(fù)雜，目前這種想法正在發(fā)生改變，主要是因?yàn)樽罱鼛啄甑囊恍┭芯抗ぷ鳎鏡S碼的糾錯(cuò)糾刪譯碼算法和1998年S.Lin等人提出的基于網(wǎng)格軟判決譯碼算法。

1955年，Elias提出了卷積碼的概念。卷積碼可以克服分組碼的缺點(diǎn)，卷積編碼器采用移位寄存器對(duì)連續(xù)的比特流增加冗余。第一個(gè)有價(jià)值的譯碼算法是1961年Wozencraft和Reiffen提出的序列譯碼算法。之后，1963年Fano和1969年Jelinek分別對(duì)其做了改進(jìn)。雖然Fano和Jelinek的工作對(duì)譯碼算法進(jìn)行了改進(jìn)，但是直到1967年引入了Viterbi算法以后，最佳的譯碼方案（在最大似然的意義上）才可實(shí)際操作。卷積碼最致命的弱點(diǎn)是對(duì)突發(fā)錯(cuò)誤非常敏感。卷積碼抗突發(fā)錯(cuò)誤能力較差的問(wèn)題可以通過(guò)交織器來(lái)減輕。通過(guò)打亂發(fā)送端的比特的順序，并在接收端恢復(fù)比特的順序，突發(fā)錯(cuò)誤可以被展開(kāi)，對(duì)譯碼器來(lái)說(shuō)，就可以看成隨機(jī)錯(cuò)誤。這種串行級(jí)聯(lián)的形式是DavidForney于1966年首先提出來(lái)的，并用于NASA和ESA在1987年制定的深空網(wǎng)絡(luò)標(biāo)準(zhǔn)中。在這個(gè)標(biāo)準(zhǔn)中(q=8，n=255，k=223，t=16)RS碼同Odenwalder卷積碼級(jí)聯(lián)使用。

1993年7月在GenevaSwitzerland召開(kāi)的InternationalConferenceonCommunications(ICC)會(huì)議上，實(shí)際編碼系統(tǒng)與Shannon理論極限之間的距離更加接近了。在這次會(huì)議上，有兩篇論文討論了一種新的編碼方式和相關(guān)的譯碼技術(shù)，作者Berrou、Glavieux和Thitimajshima造了個(gè)新詞“TurboCodes”來(lái)描述這類(lèi)新的碼字，他們的這個(gè)發(fā)現(xiàn)產(chǎn)生了很大的影響，并獲得了很高贊譽(yù)。低密度奇偶校驗(yàn)碼(LowDensityParityCheckCodes，LDPC碼)是一種可以用非常稀疏的校驗(yàn)矩陣來(lái)定義的線(xiàn)性分組糾錯(cuò)碼。Gallager于1960年在其博士論文中首次提出LDPC碼，并證明了它的距離特性。LDPC碼具有性能接近香農(nóng)極限，誤碼率極小，抗干擾能力強(qiáng)等特點(diǎn)。但是LDPC碼的運(yùn)算復(fù)雜度較大，在接下來(lái)的時(shí)間里就逐漸被人們淡忘了。

D.J.C.MacKay、M.Neal和N.Wiberg等人對(duì)Gallager早在20世紀(jì)60年代初就提出的LDPC碼重新進(jìn)行了研究，發(fā)現(xiàn)LDPC碼同樣具有逼近香農(nóng)極限的性能，而且復(fù)雜度更低。于是越來(lái)越多的學(xué)者開(kāi)始關(guān)注并研究LDPC碼。

LDPC碼的優(yōu)異性能及其在信息可靠傳輸中的良好應(yīng)用前景（如第4代移動(dòng)通信系統(tǒng)、高速與甚高速數(shù)字用戶(hù)線(xiàn)、磁記錄系統(tǒng)等），已引起各國(guó)學(xué)術(shù)界和IT界的廣泛關(guān)注。LDPC碼將取代Turbo碼的趨勢(shì)已很明顯，研究LDPC碼將具有很大的學(xué)術(shù)價(jià)值及工程應(yīng)用與商業(yè)價(jià)值。1.4信源編碼的研究?jī)?nèi)容與發(fā)展簡(jiǎn)史將信源輸出的消息或消息序列轉(zhuǎn)換成電子信息系統(tǒng)和通信系統(tǒng)要求的碼字的過(guò)程稱(chēng)為信源編碼。為了提高系統(tǒng)的有效性，信源編碼的主要目的是選出一組適當(dāng)?shù)拇a字，使表示信源輸出消息和消息序列的碼率最低。這種以壓縮數(shù)碼率、提高系統(tǒng)有效性為目的的技術(shù)手段亦稱(chēng)做數(shù)據(jù)壓縮。1.4.1數(shù)據(jù)壓縮的必要性隨著大規(guī)模集成電路（微電子技術(shù)）與計(jì)算機(jī)技術(shù)的飛速發(fā)展和廣泛應(yīng)用，將各類(lèi)模擬的連續(xù)信號(hào)轉(zhuǎn)換為數(shù)字信號(hào)并實(shí)現(xiàn)數(shù)字信號(hào)的存儲(chǔ)、傳輸和處理日益顯示出其巨大的優(yōu)越性。將模擬信號(hào)轉(zhuǎn)換成為數(shù)字信號(hào)并構(gòu)成數(shù)字信息系統(tǒng)，其突出優(yōu)點(diǎn)是抗干擾能力強(qiáng)，宜于再生與存儲(chǔ)，宜于誤碼保護(hù)與加密，宜于多路復(fù)用、分組與組合，并可應(yīng)用現(xiàn)代計(jì)算技術(shù)與手段進(jìn)行信息的提取、濾波、分類(lèi)、識(shí)別等信息處理。在當(dāng)今的信息時(shí)代，各種信源信息的存儲(chǔ)與傳輸業(yè)務(wù)與日俱增。文件和圖形的傳真、電視電話(huà)、會(huì)議電視、數(shù)字電視、高清電視、視聽(tīng)圖文數(shù)據(jù)庫(kù)系統(tǒng)等靜止圖像、語(yǔ)音數(shù)據(jù)存儲(chǔ)與傳輸?shù)难芯亢蛻?yīng)用已有突飛猛進(jìn)的發(fā)展。以圖像、圖形、語(yǔ)音信息的存儲(chǔ)、傳輸為代表的數(shù)字信息系統(tǒng)的發(fā)展和應(yīng)用必將給人們的日常生活乃至人類(lèi)社會(huì)的進(jìn)步帶來(lái)巨大的變革，在政治、軍事、經(jīng)濟(jì)、教育等各個(gè)領(lǐng)域中發(fā)揮重要作用。然而，數(shù)字的信息系統(tǒng)也有其明顯的缺點(diǎn)，即模擬信號(hào)轉(zhuǎn)換成數(shù)字信號(hào)后，數(shù)據(jù)量大，占用頻帶寬。例如，數(shù)字電話(huà)系統(tǒng)的通頻帶寬通常為模擬電話(huà)帶寬的8倍，常規(guī)電視圖像數(shù)據(jù)的傳輸速率達(dá)165Mb/s。各類(lèi)數(shù)字信息系統(tǒng)的應(yīng)用（特別是圖像信息的通信與存儲(chǔ)）將使其數(shù)據(jù)量大的缺點(diǎn)更為突出。雖然衛(wèi)星通信、光纖通信等現(xiàn)代通信手段使得通信頻帶成倍拓寬，激光存儲(chǔ)設(shè)備為海量數(shù)據(jù)存儲(chǔ)提供了更加充分的硬件環(huán)境，但是，人類(lèi)社會(huì)對(duì)于各種媒體信息的存儲(chǔ)、傳輸和利用的需求仍然超過(guò)、甚至遠(yuǎn)遠(yuǎn)超過(guò)存儲(chǔ)設(shè)備的容量和通信系統(tǒng)的傳輸能力。因此，通過(guò)信源編碼在無(wú)失真或滿(mǎn)足某種失真要求的條件下，降低數(shù)碼率的數(shù)據(jù)壓縮處理已成為現(xiàn)代通信系統(tǒng)和數(shù)字信息系統(tǒng)的關(guān)鍵技術(shù)課題之一。1.4.2數(shù)據(jù)壓縮的可能性和基本方法作為信息傳輸系統(tǒng)中一般規(guī)律的基礎(chǔ)理論學(xué)科，香農(nóng)信息論在提高系統(tǒng)有效性方面進(jìn)行了深入的理論分析，除了應(yīng)用數(shù)理統(tǒng)計(jì)方法對(duì)各類(lèi)信源進(jìn)行描述、分類(lèi)及定量地計(jì)算輸出信息量之外，針對(duì)信源輸出中含有不包含信息的多余成分的現(xiàn)象，從信源符號(hào)的概率分布和信源符號(hào)序列中各分量的相關(guān)性出發(fā)，研究信源輸出信息的能力并定義了信源的信息冗余度，深入分析了信息系統(tǒng)中信息傳輸率和失真的關(guān)系并構(gòu)成了信息率失真理論。在這些理論的基礎(chǔ)上，香農(nóng)第一編碼定理和香農(nóng)第三編碼定理分別指出了無(wú)失真信源編碼和限失真信源編碼的最優(yōu)碼的存在性以及最小信息傳輸率的理論極限。香農(nóng)信息論中的這些討論為信源編碼原理和應(yīng)用技術(shù)的研究奠定了重要的理論基礎(chǔ)。依據(jù)香農(nóng)信息論中的這些理論，去除信源輸出中的冗余數(shù)據(jù)即可實(shí)現(xiàn)無(wú)失真的數(shù)據(jù)壓縮。若進(jìn)一步根據(jù)人的生理特性和心理特性，在信息系統(tǒng)中引入一定限度內(nèi)的失真，即丟棄包含信息量少的次要成分，保留信息量豐富的主要成分，則可實(shí)現(xiàn)限失真條件下的高效信源數(shù)據(jù)壓縮，大大提高信息系統(tǒng)的有效性。由此可知，信源編碼原理包括無(wú)失真信源編碼和限失真信源編碼兩種類(lèi)型，相應(yīng)地?cái)?shù)據(jù)壓縮應(yīng)用技術(shù)也可以分為無(wú)失真數(shù)據(jù)壓縮（如傳真通信系統(tǒng)）和限失真數(shù)據(jù)壓縮（如圖像、語(yǔ)音系統(tǒng)）。對(duì)于多數(shù)信息系統(tǒng)，由于人的心理特性和生理特性的影響，一定限度內(nèi)的失真對(duì)于接收者而言或者并無(wú)覺(jué)察，或者認(rèn)為是可以接受的，而這種少量的失真卻可以換取明顯的數(shù)據(jù)壓縮效果。因此數(shù)據(jù)壓縮研究的重點(diǎn)是在信息率失真理論指導(dǎo)下的限失真編碼方法。