信息論與編碼理論-全

信息論與編碼理論

山東大學(xué)

信息科學(xué)與工程學(xué)院

第一章緒論通信系統(tǒng)模型信源編碼器信道譯碼器信宿干擾源通信系統(tǒng)模型進(jìn)一步細(xì)分信源信源編碼器信道編碼器調(diào)制器信道干擾源解調(diào)器信道譯碼器信源譯碼器信宿等效離散信道等效離散信源等效信宿信道編碼器信道譯碼器各部件功能信源產(chǎn)生消息的源，消息可以是文字，語言，圖像?？梢噪x散，可以連續(xù)。隨機(jī)發(fā)生。研究的主要問題是消息的統(tǒng)計(jì)特性和產(chǎn)生信息的速率編碼器信源編碼器：對(duì)信源輸出進(jìn)行變換，求得有效性信道編碼器：對(duì)信源編碼輸出變換，提高抗干擾性調(diào)制器：將信道編碼輸出變成適合信道傳輸?shù)姆绞礁鞑考δ苄诺佬盘?hào)從發(fā)端傳到手段的介質(zhì)干擾源系統(tǒng)各部分引入的干擾，包括衰落，多徑，碼間干擾，非線性失真，加性噪聲，主要是統(tǒng)計(jì)特性信道的中心問題是研究信道的統(tǒng)計(jì)特性和傳信能力，即信道容量各部件功能譯碼器編碼器的逆變換中心問題是研究各種可實(shí)現(xiàn)的解調(diào)和譯碼方法信宿信息的接收者信息、消息和信號(hào)信息一個(gè)抽象的概念，可以定量的描述。信息、物質(zhì)和能量是構(gòu)成一切系統(tǒng)的三大要素消息是信息的載體，相對(duì)具體的概念，如語言，文字，數(shù)字，圖像信號(hào)表示消息的物理量，電信號(hào)的幅度，頻率，相位等等1.2信息論研究的中心問題和發(fā)展Shannon信息論的基本任務(wù)1948年shannon發(fā)表了“通信的數(shù)學(xué)理論”奠定了信息論理論基礎(chǔ)基本任務(wù)是設(shè)計(jì)有效而可靠的通信系統(tǒng)可靠是要使信源發(fā)出的消息經(jīng)過傳輸后，盡可能準(zhǔn)確地、不失真地再現(xiàn)在接收端有效是用盡可能短的時(shí)間和盡可能少的設(shè)備來傳輸一定量的消息信息論的研究內(nèi)容狹義信息論（經(jīng)典信息論）研究信息測度，信道容量以及信源和信道編碼理論一般信息論研究信息傳輸和處理問題，除經(jīng)典信息論外還包括噪聲理論，信號(hào)濾波和預(yù)測，統(tǒng)計(jì)檢測和估值理論，調(diào)制理論，信息處理理論和保密理論廣義信息論除上述內(nèi)容外，還包括自然和社會(huì)領(lǐng)域有關(guān)信息的內(nèi)容，如模式識(shí)別，計(jì)算機(jī)翻譯，心理學(xué)，遺傳學(xué)，神經(jīng)生理學(xué)狹義信息論體系結(jié)構(gòu)Shannon信息論壓縮理論有失真編碼無失真編碼等長編碼定理Shannon1948McMillan1953變長編碼定理Shannon1948McMillan1956Huffman碼(1952)、Fano碼算術(shù)碼(1976,1982)LZ碼(1977,1978)率失真理論ShannonGallagerBerger壓縮編碼JPEGMPEG傳輸理論信道編碼定理網(wǎng)絡(luò)信息理論糾錯(cuò)碼編碼調(diào)制理論網(wǎng)絡(luò)最佳碼信息論發(fā)展簡史電磁理論和電子學(xué)理論對(duì)通信理論技術(shù)發(fā)展起重要的促進(jìn)作用1820－1830年，法拉第發(fā)現(xiàn)電磁感應(yīng)莫爾斯1832－1835建立電報(bào)系統(tǒng)。1876年Bell發(fā)明電話1864麥克斯韋預(yù)言電磁波存在，1888年赫茲驗(yàn)證該理論1895年馬可尼發(fā)明了無線電通信微波電子管導(dǎo)致微波通信系統(tǒng)，微波雷達(dá)系統(tǒng)激光技術(shù)使通信進(jìn)入光通信時(shí)代量子力學(xué)使通信進(jìn)入量子通信領(lǐng)域信息論發(fā)展簡史1832年莫爾斯電碼對(duì)shannon編碼理論的啟發(fā)1885年凱爾文研究了一條電纜的極限傳信速率1922年卡遜對(duì)調(diào)幅信號(hào)的頻譜結(jié)構(gòu)進(jìn)行研究1924年奈奎斯特證明了信號(hào)傳輸速率和帶寬成正比1928年Hartley提出信息量定義為可能消息量的對(duì)數(shù)1939年Dudley發(fā)明聲碼器1940維納將隨機(jī)過程和數(shù)理統(tǒng)計(jì)引入通信與控制系統(tǒng)信息論發(fā)展簡史1948年shannon信息論奠基1952年Fano證明了Fano不等式，給出了shannon信道編碼逆定理的證明1957，Wolfowitz，1961Fano，1968Gallager給出信道編碼定理的簡介證明并描述了碼率，碼長和錯(cuò)誤概率的關(guān)系，1972年Arimoto和Blahut發(fā)明了信道容量的迭代算法1956McMillan證明了Kraft不等式。1952年Fano碼，Huffman碼。1976Rissanen算術(shù)編碼，1977，78Ziv和Lempel的LZ算法信息論發(fā)展簡史1950年漢明碼，1960年卷積碼的概率譯碼，Viterbi譯碼，1982年Ungerboeck編碼調(diào)制技術(shù)，1993年Turbo編譯碼技術(shù)，1999年LDPC編碼技術(shù)。1959年，Shannon提出率失真函數(shù)和率失真信源編碼定理1961年，Shannon的“雙路通信信道”開拓了網(wǎng)絡(luò)信息論的研究，目前是非常活躍的研究領(lǐng)域。信息的概念第一個(gè)重要概念：信道上傳送的是隨機(jī)變量的值。注意：（1）這就是說，我們?cè)谑盏较⒅?，并不知道消息的?nèi)容。否則消息是沒有必要發(fā)送的。（2）消息隨機(jī)變量有一個(gè)概率分布。（3）消息隨機(jī)變量的一個(gè)可能取值就稱為一個(gè)事件。信息的概念第二個(gè)重要概念：事件發(fā)生的概率越小，此事件含有的信息量就越大。（不太可能發(fā)生的事件竟然發(fā)生了，令人震驚）例事件“中國足球隊(duì)3：0力克韓國足球隊(duì)”含有的信息量大。（小概率事件發(fā)生了，事件信息量大）例事件“中國足球隊(duì)0：1負(fù)于韓國足球隊(duì)”含有的信息量小。（大概率事件發(fā)生了，事件信息量?。┬畔⒌母拍?/p>

第三個(gè)重要概念：消息隨機(jī)變量的隨機(jī)性越大，此消息隨機(jī)變量含有的信息量就越大。例消息隨機(jī)變量X=“中國足球隊(duì)與韓國足球隊(duì)比賽的結(jié)果”，則消息隨機(jī)變量X含有的信息量小。（隨機(jī)性小，可預(yù)見性大，因此該消息隨機(jī)變量含有的信息量小。）例消息隨機(jī)變量X=“意大利足球隊(duì)與德國足球隊(duì)比賽的結(jié)果”，則消息隨機(jī)變量X含有的信息量大。（隨機(jī)性大，可預(yù)見性小，因此該消息隨機(jī)變量含有的信息量大。）信息的概念第四個(gè)重要概念：兩個(gè)消息隨機(jī)變量的相互依賴性越大，它們的互信息量就越大（這里指的是絕對(duì)值大）。例X=西安明日平均氣溫,Y=咸陽明日平均氣溫，Z=北京明日平均氣溫，W=紐約明日平均氣溫。則X與Y互信息量大，X與Z互信息量小得多，X與W互信息量幾乎為0。第二章信息量和熵信息量和熵2.1離散變量的非平均信息量2.2離散集的平均自信息量－熵2.3離散集的平均互信息量2.4連續(xù)隨機(jī)變量的互信息和熵2.5凸函數(shù)和互信息的凸性2.1離散變量的非平均信息量輸入，輸出空間定義輸入空間X={xk,k=1,2,…,K},概率記為q(xk)輸出空間Y={yj,j=1,2,…,J},概率記為ω(yj)聯(lián)合空間XY={xkyj;k=1,2,…,K;j=1,2,…,J},概率為p(xkyj)

p(xkyj)=p(xk|yj)ω(yj)=p(yj|xk)q(xk)非平均互信息量例2.1.1輸入消息碼字p(xk)收到0收到01收到011X1X2X3X4X5X6X7x80000010100111001011101111/81/81/81/81/81/81/81/81/41/41/41/40000001/21/2000000010000非平均互信息量輸入消息碼字p(xk)收到0收到01收到011X1X2X3X4X5X6X7x80000010100111001011101111/81/41/81/41/161/161/161/161/61/31/61/30000001/32/3000000010000非平均互信息量例2.1.2輸入消息碼字p(xk)收到0收到01收到011X1X20001111/21/21-pp1/21/21-pp1-p1-p0011pp非平均互信息量條件互信息和聯(lián)合事件互信息三個(gè)事件集的條件互信息定義為可以推廣到任意有限多個(gè)空間情況互信息的可加性系統(tǒng)u1u2u3系統(tǒng)u1u2u3離散變量的非平均自信息量非平均自信息的性質(zhì)非負(fù)體現(xiàn)先驗(yàn)不確定性大小條件自信息和聯(lián)合自信息自信息、條件自信息和互信息I(xk)I(yj)I(xk;yj)2.2離散集的平均自信息量－熵熵集X中事件出現(xiàn)的平均不確定性例2.2.1H(p)例2.2.2條件熵和聯(lián)合熵XY獨(dú)立時(shí)有H(X|Y)=H(X)熵的性質(zhì)對(duì)稱性非負(fù)性確定性擴(kuò)展性可加性極值性是H(P)上凸函數(shù)熵的性質(zhì)－可加性H(p1q11,p1q12,…,p4q44)=H(p1…,p4)+p1H(q11,…,q14)+…+p4H(q41,…,q44)p1p2p3p4q11q12q13q14熵的極值性引理1:lnx≤x-1熵的極值性引理2：H(X|Y)≤H(X)H(U1…UN)≤H(U1)+…+H(UN)熵的凸性H(P)是P的上凸函數(shù)2.3離散集的平均互信息量平均互信息量非負(fù)性對(duì)稱性

平均互信息量4.I(X;Y)≤H(X),I(X;Y)≤H(Y)H(X)H(Y)I(X;Y)H(Y|X)H(X|Y)條件互信息信息處理定理Z出現(xiàn)情況下，X和Y獨(dú)立,構(gòu)成一個(gè)馬氏鏈系統(tǒng)1系統(tǒng)2XYZ信息處理定理2.4連續(xù)隨機(jī)變量的互信息和相對(duì)熵連續(xù)隨機(jī)變量的互信息例:求互信息例:求互信息

隨機(jī)變量的相對(duì)熵(微分熵)均勻分布的相對(duì)熵高斯分布的相對(duì)熵熵功率相對(duì)熵的極大化1.峰值功率受限均勻分布相對(duì)熵最大2.平均功率受限高斯分布相對(duì)熵最大3.平均功率大于等于熵功率2.5凸函數(shù)與互信息的凸性凸函數(shù)凸集R：a，b屬于R，qa+(1-q)b也屬于R，其中0≤q≤1概率矢量矢量a的所有分量和為1上凸函數(shù)凸函數(shù)的性質(zhì)f(a)是上凸的，－f(a)是下凸的f1(a),…,fL(a)是R上的上凸函數(shù)，c1,…,cL是正數(shù)，c1f1(a)+…+cLfL(a)也是上凸函數(shù)f(a)是上凸函數(shù)，E[f(a)]≤f[E(a)],E為求數(shù)學(xué)期望K-T條件f(a)是定義域R上的上凸函數(shù)，a是概率矢量。偏導(dǎo)數(shù)存在且連續(xù)，f(a)在R上為極大的充分必要條件互信息的凸性p(y|x)給定，I(X;Y)是q(x)的上凸函數(shù)Q(x)給定，I(X;Y)是p(y|x)的下凸函數(shù)互信息的凸性q1和q2是X上的任意兩個(gè)概率矢量，相應(yīng)的互信息為I1和I2，令θ滿足0<θ<1。q=θq1＋(1－θ)q2是合成概率矢量，此時(shí)輸入X和輸出Y之間的互信息為I。需要證明第三章信源編碼（一）離散信源無失真編碼3.1信源及其分類3.2離散無記憶信源的等長編碼3.3離散無記憶信源的不等長編碼3.4最佳不等長編碼無失真編碼限失真編碼3.1信源及其分類信源及其分類離散信源連續(xù)信源無記憶信源有記憶信源簡單信源－獨(dú)立同分布平穩(wěn)信源，各態(tài)歷經(jīng)源M階記憶源時(shí)間離散連續(xù)源隨機(jī)波形源3.2離散無記憶源的等長編碼離散無記憶源字母表A={a1,…,aK},概率p1,…,pK,長為L的源輸出序列uL={u1,…,uL}，共有KL種序列碼符號(hào)字母表B={b1,…,bD},以碼符號(hào)表示源輸出序列，D元碼等長D元碼，不等長D元碼單義可譯碼，每個(gè)消息都至少有一個(gè)碼字與之對(duì)應(yīng)。單義可譯碼存在充要條件DN≥KLN≥LlogK/logDDMS的等長編碼NlogD≥LH(U)H(U)是統(tǒng)計(jì)平均值，L達(dá)到無限時(shí)，一個(gè)具體的源輸出序列的平均每符號(hào)的信息量才等于H(U)選L足夠長，使NlogD≥L[H(U)+eL]弱、強(qiáng)e典型序列集信源劃分定理編碼速率和等長編碼定理R=(1/L)logM=(N/L)logD,M為碼字總數(shù)對(duì)于給定信源和編碼速率R以及任意e>0，若有L0,以及編譯碼方法，使得L>L0,錯(cuò)誤概率小于e，R是可達(dá)的等長編碼定理R>H(U),R是可達(dá)的，R<H(U)是不可達(dá)的編碼效率h=H(U)/R

3.3DMS的不等長編碼平均碼長幾個(gè)定義唯一可譯碼逗點(diǎn)碼，無逗點(diǎn)碼字頭或前綴異字頭碼或異前綴碼樹碼，滿樹，非滿樹，全樹樹碼構(gòu)造異字頭碼例子信源字母集概率碼A碼B碼C碼Da1a2a3a40.50.250.1250.125001100100110101101110010110111Shannon－Fano編碼D元碼每次信源符號(hào)化為概率近似相等的D個(gè)子集這樣可以保證D個(gè)碼元近似等概，每個(gè)碼字承載的信息量近似最大，碼就近似最短。理想情況I(ak)=nklogD,p(ak)=D-nkKraft不等式不等長編碼定理3.4最佳不等長編碼兩個(gè)定理1.對(duì)于給定信源，存在最佳唯一二元可譯碼，最小概率的兩個(gè)碼字碼長相等且最長，他們之間僅最后一位不同2.對(duì)輔助集為最佳的碼，對(duì)原始集也是最佳的Huffman編碼例(0.20,0.19,0.18,0.17,0.15,0.10,0.01)D元Huffman編碼共有K個(gè)符號(hào)，概率最小的R個(gè)符號(hào)碼長最長K+B=D+m(D-1)注意B<D-1K-2=m(D-1)+D-2-BB個(gè)R個(gè)B=D-2-((K-2)mod(D-1))R=2+((K-2)mod(D-1))Shannon-Fano-Elias編碼累計(jì)分布函數(shù)修正累計(jì)分布函數(shù)Shannon-Fano-Elias編碼采用的數(shù)值作為ak的碼字碼長Shannon-Fano-Elias編碼Shannon-Fano-Elias編碼信源符號(hào)P(ak)F(ak)修正值二進(jìn)制碼長碼字a10.250.250.1250.0013001a20.50.750.50.10210a30.1250.8750.81250.110141101a40.1251.00.93750.111141111算術(shù)碼算術(shù)碼信源序列(u1u2…un)的累計(jì)分布算術(shù)編碼是計(jì)算序列的累計(jì)分布，用累計(jì)分布值表示序列，所以稱為算術(shù)編碼以二元信源輸出序列的編碼為例01110P(0)P(1)F(0)F(1)01算術(shù)碼P(00)P(01)F(0)F(01)F(1)P(010)P(011)F(011)P(0110)P(0111)F(0111)P(01110)P(01111)F(01111)算術(shù)碼信源符號(hào)序列u對(duì)應(yīng)區(qū)間的寬度等于符號(hào)序列的概率算術(shù)編碼F(u)將[0,1)分割成許多小區(qū)間，取小區(qū)間內(nèi)的一個(gè)點(diǎn)代表該序列，以該點(diǎn)數(shù)值的二進(jìn)制小數(shù)表示該序列，碼字長度為算術(shù)編碼例：P(0)=0.25,P(1)=0.75,u=11111100P(u=11111100)=0.7560.252L=7F(s)=0.110100100111C=1101010編碼效率92.7%LZ編碼利用字典編碼方法信源符號(hào)A=(a1…aK)將序列分為不同的段取最短長度的連續(xù)符號(hào)構(gòu)成段，保證互不相同。先取一個(gè)符號(hào)分段，若與前面段相同，就再取一個(gè)符號(hào)，直至序列結(jié)束得到字典表，碼字由段號(hào)加后一個(gè)符號(hào)組成。單符號(hào)的碼字，段號(hào)為0LZ編碼符號(hào)碼字a0a1a2a300011011LZ編碼000000011000011000011000000100011101234567LZ編碼設(shè)長為L的信源序列u分為M(u)個(gè)碼段，每段短語的二元碼符號(hào)長度為總碼長平均+LZ編碼設(shè)長度為l段有Kl種。若把長為L的信源序列u分為M(u)個(gè)碼段后，設(shè)最長的段長為lmax，而且所有小于等于lmax

的段型全部都有，則LZ編碼典型段，ak出現(xiàn)的次數(shù)為lmaxp(ak)LZ編碼設(shè)較短的段型忽略不計(jì)第四章信道及其容量信道及其容量4.1信道分類4.2離散無記憶信道4.3信道的組合4.4時(shí)間離散的無記憶信道4.5波形信道4.1信道分類4.1信道分類離散信道：輸入輸出均為離散事件集連續(xù)信道：輸入輸出空間均為連續(xù)事件集半連續(xù)信道：輸入和輸出一個(gè)是離散的，一個(gè)是連續(xù)的時(shí)間離散的連續(xù)信道：信道輸入和輸出是連續(xù)的時(shí)間序列波形信道：輸入和輸出都是時(shí)間的實(shí)函數(shù)x(t),y(t)4.1信道分類兩端信道多端信道恒參信道：參數(shù)不隨時(shí)間變化隨參信道：參數(shù)隨時(shí)間變化無記憶信道和有記憶信道對(duì)稱信道和非對(duì)稱信道4.2離散無記憶信道離散無記憶信道平穩(wěn)信道例：二元對(duì)稱信道p=0.11-p1-ppp1100信道容量定理4.2.1定理4.2.2Q={Q0,Q1,…,QK-1}達(dá)到信道容量的充要條件

對(duì)稱DMC容量的計(jì)算若信道轉(zhuǎn)移概率矩陣所有行矢量都是第一行的置換，稱為關(guān)于輸入對(duì)稱。對(duì)稱DMC容量的計(jì)算P的所有列都是第一列的一種置換，關(guān)于輸出是對(duì)稱的當(dāng)輸入事件等概，Qk=1/K對(duì)稱DMC的容量計(jì)算輸出集Y可劃為若干和子集,每個(gè)子集對(duì)應(yīng)的信道轉(zhuǎn)移概率矩陣P中列所組成的子陣具有下列性質(zhì)每一行都是第一行的置換每一列都是第一列的置換該信道稱為準(zhǔn)對(duì)稱信道關(guān)于輸入對(duì)稱Y的劃分只有一個(gè)時(shí)，關(guān)于輸入和輸出均對(duì)稱，稱為對(duì)稱信道（例）對(duì)稱DMC容量的計(jì)算定理4.2.3實(shí)現(xiàn)準(zhǔn)對(duì)稱DMC信道容量的輸入分布為等概分布YS：子陣中每一列都是第一列置換對(duì)每個(gè)j相同對(duì)每個(gè)k相同對(duì)稱DMC容量計(jì)算K元對(duì)稱信道二元對(duì)稱信道C=1-H(p)準(zhǔn)對(duì)稱信道離散無記憶模K加性噪聲信道Z=X=Y={0,1,…,K-1}y=x+zmodK一般DMC的容量計(jì)算信道轉(zhuǎn)移矩陣時(shí)非奇異方陣，假定所有Qk>0一般DMC的容量計(jì)算4.3信道的組合積信道C1＝maxI(X1,Y1)C2＝maxI(X2,Y2)信道1和信道2同時(shí)傳遞消息，輸入集X=X1×X2,輸出集Y=Y1×Y2,轉(zhuǎn)移概率p(jj’|kk’)=p(j|k)p(j’|k’)C=C1+C2信道1P(j|k)X1Y1信道2P(j‘|k’)X2Y2證明和信道單位時(shí)間內(nèi)可隨機(jī)選用信道1和信道2中的一個(gè)，選用信道1的概率為p1，選用信道2的概率為p2，p1＋p2＝1輸入空間X=X1+X2，Y=Y1+Y2，級(jí)聯(lián)信道信道1的輸出作為信道2的輸入4.4時(shí)間離散的無記憶連續(xù)信道可加噪聲信道P(y|x)=p(y-x)=p(z)可加噪聲信道高斯噪聲信道平均功率受限的可加噪聲信道平均功率受限的時(shí)間離散、恒參、可加高斯噪聲信道容量最佳分布是均值為0，方差為S的高斯型分布平均功率受限時(shí)間離散恒參可加噪聲信道容量給定信號(hào)功率，高斯信道是最差的信道平行可加高斯噪聲信道X=(x1,…,xN),y=(y1,…,yN)4.5波形信道可加波形信道Y(t)=x(t)+z(t)可加波形信道可加波形信道可加波形信道Shannon公式N=2WTW趨于無窮大，單位時(shí)間的信道容量Shannon極限-1.59dB第五章信道編碼定理1.離散信道編碼問題2.信道譯碼3.Fano不等式和信道編碼逆定理1.離散信道編碼問題糾錯(cuò)編碼器送給糾錯(cuò)編碼器的消息是經(jīng)過最佳信源編碼后，信息速率為比特/秒的離散二元或q元數(shù)字序列。分組碼

每K個(gè)信息數(shù)字為一組，計(jì)算出N個(gè)編碼數(shù)字，稱這些數(shù)字為一個(gè)碼字。通常N為整數(shù)。卷積碼輸出的n0長碼段不僅依賴于當(dāng)前的k0位信息數(shù)字，還依賴于前m個(gè)信息段的信息數(shù)字，即總共與（m＋1）k0個(gè)信息數(shù)字有關(guān)。糾錯(cuò)編碼器R＝K/N，碼率誤組率誤比特率2.信道譯碼問題譯碼錯(cuò)誤概率譯碼準(zhǔn)則最小錯(cuò)誤概率譯碼：使pe(y)最小最大后驗(yàn)概率譯碼：最大似然譯碼所有Q(m)相同最大對(duì)數(shù)似然譯碼最小漢明距離譯碼漢明距離

d(x,y),x,y中分量不同的數(shù)目碼字先驗(yàn)等概K元對(duì)稱信道最小漢明距離譯碼判決區(qū)域Ym:lnp(y|xm)>lnp(y|xm’)給定m,錯(cuò)誤概率高斯信道Fano不等式和信道編碼逆定理Fano不等式信道編碼逆定理離散平穩(wěn)源有M個(gè)字母熵為HL(U),信道容量為C,當(dāng)HL(U)>(N/L)C時(shí),誤碼率為非零值信道編碼定理R<C時(shí)，R是可達(dá)的，即對(duì)信息速率R,任意給定的e>0，存在編譯碼方法，當(dāng)N足夠大，p<e第七章信道編碼線性分組碼信息位，信息空間碼字，碼空間分組碼：n維線性空間中的k維子空間參數(shù)（n,k,d），n是碼長，k是信息位長度，d是最小漢明距離漢明重量：向量x中非零分量的數(shù)目最小距離：所有碼字中最小非零重量GF（2）上的向量GF(2)包含0,1定義了兩個(gè)運(yùn)算加法：0＋0＝0，0＋1＝1＋0＝1，1＋1＝0乘法：0×0＝0，0×1＝0，1×0＝0，1×1＝1d(x,y)=w(x+y)生成矩陣K維子空間的基底C=u0g0+u1g1+…+uk-1gk-1(7,4)漢明碼消息序列碼字消息序列碼字00000001001000110100010101100111000000010100011110010010001101101001100101100011000101111000100110101011110011011110111111010000111001001101010010110101100000110101011101111111系統(tǒng)碼校驗(yàn)位信息位生成矩陣校驗(yàn)矩陣C的對(duì)偶空間Vcv=0V的生成矩陣H是G的校驗(yàn)矩陣V的維數(shù)是N-K校驗(yàn)矩陣生成矩陣和校驗(yàn)矩陣的關(guān)系錯(cuò)誤圖樣錯(cuò)誤圖樣伴隨式伴隨式和錯(cuò)誤的關(guān)系s≠0,有錯(cuò)誤出現(xiàn)S=0e＝0，沒有錯(cuò)誤e=ci,不可檢錯(cuò)誤不可檢錯(cuò)誤概率重量分布矢量Ai碼中重量為i的碼字?jǐn)?shù)目陪集將2N個(gè)可能的向量分為2N-k個(gè)集合集合中每個(gè)向量的伴隨式相同這樣的集合稱為陪集選擇陪集中重量最輕的向量作為陪集代表，稱為陪集首。標(biāo)準(zhǔn)陣伴隨式陪集首陪集正確譯碼概率第l個(gè)陪集首的重量重量為i的陪集首的數(shù)量(6,3)碼的標(biāo)準(zhǔn)陣陪集首伴隨式譯碼步驟