《信息論與編碼》 課件 楊守義 第5-7章 信源編碼-網(wǎng)絡(luò)信息論初步

信息論與編碼2第5章信源編碼目的：提高通信系統(tǒng)的有效性，即通過編碼，用盡可能短的編碼序列符號(hào)來表示原信源序列。基本思想是：1.盡可能去除原消息序列中符號(hào)之間的相關(guān)性；2.盡可能使編碼后各符號(hào)出現(xiàn)的概率相等。3第5章信源編碼主要解決兩個(gè)方面的問題：1.“信源編碼是用盡可能短的編碼序列符號(hào)來表示原信源序列”，這個(gè)“短”，有沒有極限？如果有，該極限是多少？2.用什么方法達(dá)到或者接近該極限？4非分組碼和分組碼將長(zhǎng)消息序列按順序分成若干個(gè)符號(hào)一組，對(duì)每一組獨(dú)立進(jìn)行編碼，稱為分組碼；否則稱為非分組碼。定長(zhǎng)碼和變長(zhǎng)碼若編碼后的碼字長(zhǎng)度都相同，則稱為定長(zhǎng)碼；否則稱為變長(zhǎng)碼。5.1信源編碼的有關(guān)概念5.1.1幾個(gè)概念5奇異碼和非奇異碼若編碼前的信源組和編碼后的碼字是一一對(duì)應(yīng)的，則稱為非奇異碼；否則稱為奇異碼。非唯一可譯碼和唯一可譯碼如果任意有限長(zhǎng)的碼元序列都只能被唯一地分割成一個(gè)個(gè)的碼字，則稱為唯一可譯碼；否則稱為非唯一可譯碼。5.1信源編碼的有關(guān)概念6非即時(shí)碼和即時(shí)碼在接收端接收碼元序列的過程中，如果接收到的碼元序列已經(jīng)組成了一個(gè)碼字，但接收端并不能立即判斷出，還要等下一個(gè)碼字開始接收的時(shí)候才能判斷出前者已經(jīng)是一個(gè)完整碼字，從而開始譯碼，則稱為非即時(shí)碼；反之則稱為即時(shí)碼。5.1信源編碼的有關(guān)概念75.1信源編碼的有關(guān)概念5-1編碼的分類85.1信源編碼的有關(guān)概念信源符號(hào)ai符號(hào)出現(xiàn)的概率p(ai)碼1碼2碼3碼4碼5a11/2000011a21/40111101001a31/8100000100001a41/811110110000001例5-1表5-1中的分組碼1、碼2、碼3、碼4和碼5，從上述的4個(gè)方面分別判斷屬于什么類型的碼。表5-1碼的不同屬性95.1.2克勞福特不等式唯一可譯碼存在的充分和必要條件各碼字的長(zhǎng)度Ki應(yīng)符合克勞夫特不等式：

其中m是進(jìn)制，n是信源可能取值的符號(hào)數(shù)。10例：設(shè)對(duì)符號(hào)集{ai,i=1,2,3,4}進(jìn)行二進(jìn)制編碼；(1)對(duì)應(yīng)的碼長(zhǎng)分別為K1＝1,K2＝2,K3＝2,K4＝3，試判斷是否存在這樣的唯一可譯碼；(2)

若K1=1,

K2=2,

K3=3,

K4=3又如何？答：(1)由克勞福特定理可得：因此不存在滿足這種碼長(zhǎng)的唯一可譯碼。

11(2)由克勞福特定理可得：因此滿足這種碼長(zhǎng)的唯一可譯碼是存在的,例如{0，10，110，111}。

克勞夫特不等式只是用來說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)。例如，{0,10,010,111}12無失真信源編碼定理定長(zhǎng)信源編碼定理變長(zhǎng)信源編碼定理限失真信源編碼定理

5.2信源編碼定理135.2.1無失真信源編碼（香農(nóng)第一定理）X＝(X1X2…Xi…XL)Xi

{a1,a2,…,ai,…,an}

nL種信源編碼器Yk

{b1,b2,…,bj,…,bm}

M=mKL種

KL

logm用Y表示L長(zhǎng)的信源序列X，則送出一個(gè)信源符號(hào)所需要的信息率平均為

編碼目的：使最小。

14無失真信源編碼定理研究的內(nèi)容:最小信息率為多少時(shí)，才能得到無失真的譯碼？若小于這個(gè)信息率是否還能無失真地譯碼?

無記憶平穩(wěn)信源平均符號(hào)熵為HL(X)，對(duì)任意

，只要

則當(dāng)L足夠大時(shí)，必可使譯碼差錯(cuò)概率小于δ；即可實(shí)現(xiàn)幾乎無失真編碼；

反之，當(dāng)時(shí)，譯碼差錯(cuò)一定是有限值，而L足夠大時(shí)，譯碼幾乎必定出錯(cuò)。151.無失真定長(zhǎng)信源編碼定理：碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無失真，當(dāng)然條件是L足夠大。反之，當(dāng)時(shí)，不可能構(gòu)成無失真的編碼，也就是不可能做一種編碼器，能使收端譯碼時(shí)差錯(cuò)概率趨于零。當(dāng)時(shí)，則為臨界狀態(tài)，可能無失真，也可能有失真。16說明：L,,

,δ三者之間有什么關(guān)系？對(duì)于給定的

和δ，多大的L算足夠大？17問題：式中

為信源序列的自信息方差，

為一正數(shù)。當(dāng)

和

2均為定值時(shí)，只要L足夠大，Pe可以小于任一正數(shù)

。即，如果給定差錯(cuò)概率上界δ，則

越小，要求的編碼長(zhǎng)度L就越大。L越大，編碼器越復(fù)雜，且時(shí)延越大，在有時(shí)延要求的場(chǎng)合，往往難以滿足實(shí)時(shí)性要求。增加

，可以減小對(duì)編碼長(zhǎng)度L的要求，但以犧牲編碼效率為代價(jià)：18討論：19例題5-3：設(shè)離散無記憶信源概率空間為若要求編碼效率為90%，譯碼差錯(cuò)概率δ≤10-6試求所需要的編碼序列長(zhǎng)度L。20例題5-3：自信息方差為：若要求編碼效率η=90%：若要求編碼效率δ≤10-6：當(dāng)L有限時(shí)，要做到高編碼效率、低錯(cuò)誤率，對(duì)于定長(zhǎng)編碼來說是不可能做到的。對(duì)例5-3中的信源，有8種不同的信源符號(hào)取值（a1~a8），如果用二進(jìn)制序列來表示的話，每個(gè)符號(hào)需要3

bit（3位二進(jìn)制數(shù)可以表示8中不同的符號(hào)）。但由于不是等概率的，所以其熵H(X)=2.55

bit，按照無失真定長(zhǎng)信源編碼定理，其極限編碼長(zhǎng)度是2.55bit，而，也就是說，只能表示5.856種不同的符號(hào)，其余的符號(hào)怎么辦？實(shí)際上，由于a1~a8中部分符號(hào)的概率較小，如果序列長(zhǎng)度L足夠大，則總有某種序列出現(xiàn)的概率足夠小，對(duì)這些概率足夠小的序列，如果不設(shè)計(jì)對(duì)應(yīng)的編碼碼字，造成的錯(cuò)誤概率也非常小。21思考：222.無失真變長(zhǎng)信源編碼定理：平均碼長(zhǎng)：定長(zhǎng)編碼中，由于所有的碼字都使用相同的長(zhǎng)度，限制了其靈活性，導(dǎo)致或者效率不高，或者復(fù)雜度太高（L太大）。變長(zhǎng)編碼可以對(duì)出現(xiàn)概率大的信源盡量用短碼，從而提高編碼效率.（統(tǒng)計(jì)匹配）232.無失真變長(zhǎng)信源編碼定理：(1).單符號(hào)變長(zhǎng)編碼定理若離散單符號(hào)信源X：xi∈{a1,a2,…,an}的熵為H(X)，對(duì)每個(gè)單符號(hào)進(jìn)行無失真變長(zhǎng)編碼，設(shè)yj∈{b1,b2,…,bm}。則24(2).離散平穩(wěn)無記憶序列變長(zhǎng)編碼定理

對(duì)于平均符號(hào)熵為HL(X)的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率滿足不等式其中

為任意小正數(shù)。25例題5-4：設(shè)離散無記憶信源概率空間為試討論其編碼效率。若L=1,用二元定長(zhǎng)編碼(0，1)來構(gòu)造一個(gè)即時(shí)碼：x1→0，x2→1。平均碼長(zhǎng)＝1二元碼符號(hào)/信源符號(hào)

編碼效率為輸出的信息率為26（續(xù)）例題5-4：若對(duì)長(zhǎng)度為L(zhǎng)=2的信源序列進(jìn)行變長(zhǎng)編碼，其即時(shí)碼如表5-2所示。27（續(xù)）例題5-4：xip(xi)即時(shí)碼x1x19/160x1x23/1610x2x13/16110x2x21/16111表5-2長(zhǎng)度為2的信源序列對(duì)應(yīng)的即時(shí)碼該碼平均長(zhǎng)度：?jiǎn)畏?hào)平均碼長(zhǎng)：編碼效率為：28（續(xù)）例題5-4：29（續(xù)）例題5-4：L＝3

η3=0.985

R3＝0.985比特/二元碼符號(hào)

L＝4

η4=0.991

R4＝0.991比特/二元碼符號(hào)

30（續(xù)）例題5-4：定長(zhǎng)二元碼編碼，要求編碼效率達(dá)到96％時(shí)，允許譯碼錯(cuò)誤概率δ≤10-5

。315.2.2限失真信源編碼（香農(nóng)第三定理）

信息率失真函數(shù)給出了失真小于D時(shí)所必須具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一種編碼，使譯碼后的失真小于D。

限失真信源編碼定理：對(duì)于任意的D≥0和

＞0，當(dāng)信息率R>R(D)時(shí)，一定存在一種編碼方法，其譯碼失真小于或等于D+

，條件是編碼的信源序列長(zhǎng)度L足夠長(zhǎng)。反之，如果R<R(D)，則無論采用什么編碼方法，其譯碼失真必大于D。325.2.2限失真信源編碼（香農(nóng)第三定理）香農(nóng)第三定理是一個(gè)存在性定理，它只說明一定存在一種滿足要求的編碼方法。至于如何尋找這種最佳壓縮編碼方法，定理中沒有給出。在實(shí)際應(yīng)用中，該理論主要存在以下兩類問題：（1）符合實(shí)際信源的R(D)函數(shù)的計(jì)算相當(dāng)困難；（2）即使求得了符合實(shí)際的信息率失真函數(shù)，還需要研究采用何種編碼方法，才能達(dá)到或接近極限值R(D)。335.2.2限失真信源編碼（香農(nóng)第三定理）34香農(nóng)編碼哈弗曼編碼算術(shù)編碼（非分組碼）

5.3常用信源編碼方法355.3.1

香農(nóng)編碼將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列確定滿足下列不等式的整數(shù)碼長(zhǎng)Ki

5.3常用信源編碼方法36香農(nóng)編碼為了編成唯一可譯碼，計(jì)算第i個(gè)消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)。取Pi二進(jìn)數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符號(hào)的二進(jìn)制碼字。

5.3常用信源編碼方法37香農(nóng)編碼為了編成唯一可譯碼，計(jì)算第i個(gè)消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)。取Pi二進(jìn)數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符號(hào)的二進(jìn)制碼字。

38香農(nóng)編碼

香農(nóng)編碼的基本做法：是把長(zhǎng)度為1的整個(gè)累積概率區(qū)間，按照信源符號(hào)集中q個(gè)信源符號(hào)的概率大小，分成q份不同長(zhǎng)度的子區(qū)間（每份子區(qū)間的長(zhǎng)度正比于對(duì)應(yīng)符號(hào)的概率大?。瑢⒚糠N信源符號(hào)xi，映射到其對(duì)應(yīng)子區(qū)間上的一個(gè)點(diǎn)。這樣，每個(gè)信源符號(hào)xi映射區(qū)間都是不重疊的，從而可以保證唯一可譯碼，而且可以證明，也是即時(shí)碼；另一方面，碼字長(zhǎng)度由其概率決定，概率大的用短碼。

39香農(nóng)編碼

例5.4設(shè)信源共7個(gè)符號(hào)消息

信源消息符號(hào)ai符號(hào)概率p(ai)累加概率Pi-logp(ai)碼字長(zhǎng)度Ki碼字a10.2002.343000a20.190.22.413001a30.180.392.483011a40.170.572.563100a50.150.742.743101a60.100.893.3441110a70.010.996.667111111040香農(nóng)編碼

香農(nóng)編碼效率不高，不具有實(shí)際應(yīng)用價(jià)值，但其概率匹配的思想很有指導(dǎo)意義。415.3.2

哈夫曼編碼哈夫曼編碼是按照概率匹配思想構(gòu)建的一種具有實(shí)際使用價(jià)值的編碼方法。哈夫曼編碼是唯一可譯碼、即時(shí)碼。421.哈夫曼樹圖5-1碼樹結(jié)構(gòu)圖43碼樹樹根樹枝數(shù)節(jié)點(diǎn)終端節(jié)點(diǎn)節(jié)數(shù)非滿樹滿樹碼字的起點(diǎn)碼的進(jìn)制數(shù)碼字或碼字的一部分碼字碼長(zhǎng)變長(zhǎng)碼等長(zhǎng)碼442哈夫曼編碼(碼樹法)設(shè)信源符號(hào)集X={x1,x2,…,xq}，對(duì)應(yīng)的概率為p(X)={p(x1),p(x2),…,p(xq)}，且所有的p(x)>0，其編碼步驟如下：以q個(gè)信源符號(hào)的概率為權(quán)值，構(gòu)造q個(gè)帶權(quán)值的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)作為一棵樹，構(gòu)造一個(gè)具有q棵樹的森林；在森林中選出兩棵根節(jié)點(diǎn)權(quán)值最小的樹作為一棵新樹的左、右子樹，且置新樹的附加根節(jié)點(diǎn)權(quán)值為其左、右子樹上根節(jié)點(diǎn)權(quán)值之和；452哈夫曼編碼(碼樹法)從森林中刪除這兩棵樹，同時(shí)把新樹加入到森林中；重復(fù)步驟②、③，直到森林中只有一棵樹為止，此樹便是哈夫曼樹，需要編碼的q個(gè)符號(hào)為該哈夫曼樹的q個(gè)終端節(jié)點(diǎn)；(將哈夫曼樹中指向左子樹的分支標(biāo)記為“0”，指向右子樹的分支標(biāo)記為“1”，從根節(jié)點(diǎn)到每個(gè)終端節(jié)點(diǎn)路徑上的“0”、“1”組成的序列作為各個(gè)終端節(jié)點(diǎn)對(duì)應(yīng)的編碼，即得哈夫曼編碼。462哈夫曼編碼(碼樹法)例5-6：設(shè)給定信源X={x1,x2,x3,x4,x5,x6,x7}，對(duì)應(yīng)的概率為p(X)={0.2,0.19,0.18,0.17,0.15,0.10,0.01}。給出哈夫曼編碼過程。0.010.100.110.150.260.170.180.350.610.190.200.3910010

1010101圖5-2

碼樹法哈夫曼編碼過程472哈夫曼編碼(圖表法)將q個(gè)信源符號(hào)按概率分布的大小，以遞減次序排列起來，設(shè)用“0”和“1”碼符號(hào)分別代表概率最小的兩個(gè)信源符號(hào)，并將兩個(gè)概率最小的符號(hào)合并成一個(gè)符號(hào)，合并的符號(hào)概率為兩個(gè)符號(hào)概率之和，從而得到只包含q-1個(gè)符號(hào)的新信源，稱為縮減信源。482哈夫曼編碼(圖表法)把縮減信源的符號(hào)仍舊按概率大小以遞減次序排列，再將其概率最小的兩個(gè)信源符號(hào)分別用“0”和“1”表示，并將其合并成一個(gè)符號(hào)，概率為兩符號(hào)概率之和，這樣又形成了q-2個(gè)符號(hào)的縮減信源。依此繼續(xù)下去，直至信源只剩下兩個(gè)符號(hào)為止。將這最后兩個(gè)信源符號(hào)分別用“0”和“1”表示。然后從最后一級(jí)縮減信源開始，向前返回，就得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即對(duì)應(yīng)的碼字。492哈夫曼編碼(圖表法)表5-2圖表法哈夫曼編碼過程例5-6：設(shè)給定信源X={x1,x2,x3,x4,x5,x6,x7}，對(duì)應(yīng)的概率為p(X)={0.2,0.19,0.18,0.17,0.15,0.10,0.01}。給出哈夫曼編碼過程。502哈夫曼編碼信源符號(hào)xi概率p(xi)碼字Wi碼長(zhǎng)Kix10.20102x20.19112x30.180003x40.170013x50.150103x60.1001104x70.0101114512哈夫曼編碼

碼元/符號(hào)

bit/符號(hào)

52哈夫曼編碼結(jié)果并不是唯一的哈夫曼樹的左右分支表示“0”或者“1”，是可以互換的；當(dāng)有多個(gè)節(jié)點(diǎn)具有相同的概率時(shí)，選擇哪些節(jié)點(diǎn)進(jìn)行合并是任意的。如果縮減信源中有兩個(gè)以上的節(jié)點(diǎn)概率相同，則應(yīng)優(yōu)先選擇未被合并過（或合并次數(shù)少）的節(jié)點(diǎn)進(jìn)行合并，以便盡量減小編碼方差，從而減小編碼設(shè)備復(fù)雜度。53哈夫曼編碼結(jié)果并不是唯一的例

設(shè)有離散無記憶信源給出哈夫曼編碼過程。542哈夫曼編碼哈夫曼碼是用概率匹配方法進(jìn)行信源編碼。哈夫曼碼的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼，充分利用了短碼；縮減信源的最后二個(gè)碼字總是最后一位不同，從而保證了哈夫曼碼是即時(shí)碼。555.3.3

算術(shù)編碼香農(nóng)編碼和哈夫曼編碼，都是基于分組的塊編碼。分組編碼方法沒有考慮到組間符號(hào)的相關(guān)性，因此編碼效率會(huì)有所損失。增加碼長(zhǎng)可以考慮更多符號(hào)間的相關(guān)性，但會(huì)增加編碼復(fù)雜度及編碼時(shí)延。算術(shù)編碼是一種非分組編碼方法，其基本思路是借鑒香農(nóng)編碼的區(qū)間映射思想。565.3.3

算術(shù)編碼算術(shù)編碼從全序列出發(fā)，將不同的信源序列的累計(jì)概率映射到[0,1]區(qū)間上，使每個(gè)序列對(duì)應(yīng)區(qū)間上的一點(diǎn)，也就是說，把區(qū)間[0,1]分成許多互不重疊的小區(qū)間，不同的信源序列對(duì)應(yīng)不同的小區(qū)間，可以證明，只要這些小區(qū)間互不重疊，就可以編得即時(shí)碼。0(P1)P2

P3

P4P5……1

……p1

p2p3p4575.3.3

算術(shù)編碼問題：是否需要等到要編碼的序列全部都已知以后才開始進(jìn)行區(qū)間映射（編碼）嗎？設(shè)P(S)表示序列S的累積概率（即其對(duì)應(yīng)的子區(qū)間的起始點(diǎn)），A(S)為序列S對(duì)應(yīng)的子區(qū)間長(zhǎng)度，C(S)表示對(duì)序列S編碼得到的的碼字，pr表示m進(jìn)制單符號(hào)xr的概率，Pr(r=0,1,2,…,m-1)表示m進(jìn)制單符號(hào)xr的累計(jì)概率。可建立遞推更新過程：585.3.3

算術(shù)編碼符號(hào)符號(hào)概率pi符號(hào)累積概率Pja0.100(1/2)0.000b0.010(1/4)0.100c0.001(1/8)0.110d0.001(1/8)0.111例5-7

有4個(gè)符號(hào)a，b，c，d構(gòu)成簡(jiǎn)單序列S＝abda，各符號(hào)及其對(duì)應(yīng)概率如下表（二進(jìn)制），試給出算術(shù)編解碼過程。595.3.3

算術(shù)編碼設(shè)起始狀態(tài)為空序列?，則A(?)＝1，P(?)＝0。605.3.3

算術(shù)編碼設(shè)起始狀態(tài)為空序列?，則A(?)＝1，P(?)＝0。615.3.3

算術(shù)編碼故編碼后的碼字C(abda)即為序列abda的累積概率P(abda)（二進(jìn)制數(shù)）小數(shù)點(diǎn)后的7位：0101110.625.3.3

算術(shù)編碼編碼過程（為簡(jiǎn)化圖，只給出了序列abd的編碼過程）：圖5-9算術(shù)編碼過程63算術(shù)編碼的譯碼過程C(abda)=0.010111<0.1

[0,0.1]

第一個(gè)符號(hào)為a

放大至[0,1](×pa-1)：

C(abda)×21＝0.10111

[0.1,0.110]

第二個(gè)符號(hào)為b64算術(shù)編碼的譯碼過程去掉累積概率Pb：0.10111-0.1=0.00111

放大至[0,1](×pb-1)：

0.00111×22=0.111

[0.111,1]

第三個(gè)符號(hào)為d

去掉累積概率Pd：0.111-0.111=0

放大至[0,1](×pd-1)：0×24＝0

[0,0.1]第四個(gè)符號(hào)為a本章小結(jié)65第五章主要內(nèi)容結(jié)構(gòu)66本章小結(jié)本章學(xué)習(xí)思路碼的分類→即時(shí)碼存在的充分必要條件：克勞福特不等式→信源編碼定理→常用信源編碼方法：編碼效率分析。67本章小結(jié)本章學(xué)習(xí)要點(diǎn)

1.信源編碼的目的

信源編碼的目的主要是提高通信系統(tǒng)的有效性，即通過編碼，用盡可能短的編碼序列符號(hào)來表示原序列。

68本章小結(jié)本章學(xué)習(xí)要點(diǎn)

2.無失真信源編碼定理

（1）單符號(hào)無失真變長(zhǎng)信源編碼定理

（2）離散平穩(wěn)無記憶序列無失真變長(zhǎng)信源編碼定理

第5章介紹了信源編碼，是關(guān)于有效性的，第5章與第2章（第4章）是一條有效性主線；本章將介紹信道編碼，是關(guān)于可靠性的，第6章與第3章是一條可靠性主線。69第6章信道編碼70本章內(nèi)容一些基本概念信道編碼定理常用信道編碼方法—線性分組碼、卷積碼71基本概念一些基本概念72

一些概念73差錯(cuò)控制編碼及分類：差錯(cuò)控制編碼：

通過增加冗余碼元，提高通信的可靠性。如：k個(gè)碼元的信息碼組m=（mk-1，mnk2，…，m1，m0），組合得到n個(gè)碼元的碼字C

=（cn-1，cn-2，…，c1，c0）（n>k），該n個(gè)碼元只有個(gè)是獨(dú)立的，其余k個(gè)是冗余。分類：從功能角度：檢錯(cuò)碼（可以檢測(cè)出發(fā)生了差錯(cuò)）、糾錯(cuò)碼（可以糾正一定數(shù)量的差錯(cuò)）對(duì)信息序列的處理方法：分組碼（相關(guān)性只分布于組內(nèi)）、卷積碼（組間也有相關(guān)性）碼元與原始信息位的關(guān)系：線性碼（所有碼元由信息碼元線性組合得到）、非線性碼（所有碼元由信息碼元非線性組合得到）差錯(cuò)類型：糾隨機(jī)差錯(cuò)碼、糾突發(fā)差錯(cuò)碼等一些概念74差錯(cuò)控制系統(tǒng)的分類：前向糾錯(cuò)（FEC）：發(fā)端信息經(jīng)糾錯(cuò)編碼后傳送，收端通過糾錯(cuò)譯碼自動(dòng)糾正傳遞過程中的差錯(cuò)（信息傳遞只有前向的：從發(fā)送端到接收端）反饋重發(fā)（ARQ）：收端通過檢測(cè)接收碼是否符合編碼規(guī)律來判斷，如判定碼組有錯(cuò)，則通過反向信道通知發(fā)端重發(fā)該碼（須有反饋信道：從接收端到發(fā)送端的信息傳遞）混合糾錯(cuò)（HEC）：前向糾錯(cuò)和反饋重發(fā)的結(jié)合，發(fā)端發(fā)送的碼兼有檢錯(cuò)和糾錯(cuò)兩種能力一些概念75譯碼規(guī)則：譯碼：就是接收端收到接收符號(hào)集中的某一符號(hào)，據(jù)此來判斷（或者說猜測(cè)。因?yàn)樾诺朗怯袛_信道，輸入符號(hào)和輸出符號(hào)不是一一對(duì)應(yīng)的）發(fā)送端發(fā)送的是發(fā)送符號(hào)集中的哪個(gè)符號(hào)，即設(shè)計(jì)一個(gè)規(guī)則。最大后驗(yàn)概率譯碼（MAP）：設(shè)接收端收到符號(hào)的條件下，發(fā)送端發(fā)送符號(hào)的概率為，如果設(shè)計(jì)的譯碼規(guī)則為，那么，譯碼正確的概率就是，而譯碼錯(cuò)誤的概率則為。如果想使錯(cuò)誤概率最小，則需要最大，即：

稱為后驗(yàn)概率，因此，上述的譯碼規(guī)則，稱為最大后驗(yàn)概率

譯碼。最大后驗(yàn)概率譯碼使最佳譯碼。最大似然譯碼（ML）：稱為最大似然譯碼，稱為似然概率。一些概念76最小漢明距離譯碼：對(duì)于二進(jìn)制對(duì)稱信道（BSC）來說，似然概率

若發(fā)送碼字矢量為C，接受碼字矢量為R，其漢明距離（接受碼字和發(fā)送碼字按比特比較，不同的比特個(gè)數(shù)）為d，此時(shí)似然函數(shù)是

由于一般，，所以d越小，似然函數(shù)就越大，因此，對(duì)于BSC信道，最大似然譯碼就等價(jià)于最小漢明距離譯碼。一些概念77矢量空間：正交完備基：n維空間由n個(gè)相互正交的基底張成，n維空間的任何一個(gè)矢量，可以由這n個(gè)基底線性組合而得到。這組基底稱為正交完備基。例如：三維空間可由三個(gè)相互正交的單位矢量張成。矢量的表示：

n維空間的一個(gè)矢量，可以由n個(gè)元素組成的數(shù)組表示，是這個(gè)矢量的端點(diǎn)坐標(biāo)。這個(gè)數(shù)組也叫做n重。如C

=（cn-1，cn-2，…，c1，c0）是一個(gè)n重。子空間：n維空間的一個(gè)k維子空間，可以用一個(gè)k維n重來表示：C

=（cn-1，cn-2，…，c1，c0），

n個(gè)元素中的k個(gè)是獨(dú)立的，而另外n

-k個(gè)元素可由k個(gè)元素線性組合得到。例如：三維空間中令z=x+y（即：3重?cái)?shù)組中的2個(gè)：x、y是獨(dú)立的，而由x、y組合而成），則可以得到一個(gè)2維子空間。矢量空間中點(diǎn)的個(gè)數(shù)：實(shí)數(shù)空間：有無窮多個(gè)點(diǎn)；整數(shù)空間：對(duì)q進(jìn)制，n維空間的每個(gè)坐標(biāo)軸上有q個(gè)不同取值（0，1，…，q-1），故共有qn個(gè)點(diǎn)。一些概念78碼空間：

以(n,k)分組碼為例。所謂(n,k)分組碼，是將信息碼流分成k個(gè)一組（稱為信息碼組，也叫k維k重），通過增加個(gè)n-k碼元的冗余，變成n個(gè)碼元的一個(gè)碼字（k維n重）。

從矢量空間的角度來看：一個(gè)碼字可以看成矢量空間（整數(shù)空間）的一個(gè)點(diǎn)；碼空間可以看成n維空間的一個(gè)k維子空間（碼字的n個(gè)碼元，只有k個(gè)是獨(dú)立的）；碼空間（k維空間）共有qk個(gè)點(diǎn)，特別地，對(duì)二進(jìn)制，共有2k個(gè)點(diǎn)；一些概念79n維空間共有qn個(gè)點(diǎn)；將一個(gè)信息碼組（k個(gè)碼元）編碼成一個(gè)碼字（n個(gè)碼元，其中k個(gè)是獨(dú)立的），可以看成是將一個(gè)k維碼空間映射到一個(gè)n維空間的k維子空間上；n維空間共有qn個(gè)點(diǎn)，選擇了其中的qk個(gè)點(diǎn)作為碼空間qk個(gè)點(diǎn)的映射，稱為許用點(diǎn)；其余的qn-

qk個(gè)點(diǎn)稱為禁用點(diǎn)；碼字通過信道傳輸，如果發(fā)生了某些碼元錯(cuò)誤，則可能從一個(gè)許用點(diǎn)錯(cuò)到一個(gè)禁用點(diǎn)，就可以檢測(cè)到錯(cuò)誤（檢錯(cuò)，通過某些機(jī)制，甚至可以糾錯(cuò)）；禁用點(diǎn)越多（n-k越大），檢錯(cuò)糾錯(cuò)能力越強(qiáng)，但付出的代價(jià)（n-k是冗余）越大。一些概念80信道編碼定理信道編碼定理81信道編碼定理如果不考慮速率，當(dāng)然可以達(dá)到任意高的可靠性。這沒有意義。那么，就應(yīng)該考慮可靠性和速率之間的關(guān)系。香農(nóng)把問題定義為：在可以使解碼錯(cuò)誤概率漸近于零的條件下，信道的最高傳輸速率是多少？這是香農(nóng)信道編碼定理要解決的問題。82信道編碼定理定理：

若一個(gè)離散無記憶信道的信道容量為C，只要平均信息率R小于信道容量C，總存在一種信道編碼方法和相應(yīng)的譯碼規(guī)則，使譯碼錯(cuò)誤概率PE任意小。證明思路：采用隨機(jī)編碼，如果隨機(jī)編碼的平均譯碼錯(cuò)誤概率可以趨近于零，則一定有一部分“好碼”，其錯(cuò)誤概率趨近于零。

Gallager在1965年證明，平均譯碼錯(cuò)誤概率的上界為：83信道編碼定理

其中，N為碼長(zhǎng)，R為信息速率，E(R)稱為可靠性函數(shù)，E(R)~R關(guān)系曲線如下圖所示：曲線表明：只要信息速率R<信道容量C，可靠性函數(shù)E(R)>0，因此，只要碼長(zhǎng)N足夠大，總可以使平均譯碼錯(cuò)誤概率趨近于零。84信道編碼定理

下圖為不同信道容量時(shí)的E(R)~R關(guān)系曲線?？梢钥闯觯簩?duì)同樣的信息碼率R，信道容量C越大，可靠性函數(shù)E（R）的值越大，可靠性越高。對(duì)同樣的信道容量C，信息速率R越小，可靠性函數(shù)E（R）的值越大，可靠性越高。85信道編碼定理

因此，為提高可靠性，降低譯碼錯(cuò)誤概率，可以：增大信道容量C。根據(jù)香農(nóng)公式，要增大信道容量，可以：增加帶寬；增加信號(hào)功率。減小速率R。增大碼長(zhǎng)N。86信道編碼定理

信源信道聯(lián)合編碼定理：信源編碼定理說，只要信息率R>信源熵H(X)，就可以實(shí)現(xiàn)無失真編碼；信道編碼定理說，只要信息率R<信道容量C，就可以實(shí)現(xiàn)無差錯(cuò)譯碼。將兩者結(jié)合，就可以得到信源信道聯(lián)合編碼定理：

若離散無記憶信源熵為H(X)，離散無記憶信道容量為C，只要：H(X)<C，則總存在一種信源信道聯(lián)合編碼方法，使得信源輸出信息能夠以任意小的差錯(cuò)概率通過該信道可靠傳輸。87常用信道編碼方法

常用信道編碼方法88常用信道編碼方法

香農(nóng)的信道編碼定理說明，一定存在“好碼”。但怎么樣構(gòu)造“好碼”，香農(nóng)沒有給出方法。下面介紹兩種常用的信道編碼方法：線性分組碼卷積碼89常用信道編碼方法—線性分組碼

線性分組碼如前所述，線性分組碼的編碼，就是從k維k重信息空間映射到一個(gè)n維空間的k維子空間（碼空間）。線性分組碼的編碼：n維空間由n個(gè)正交基底矢量張成，n維空間的k維子空間可以由這n個(gè)基底矢量中的k個(gè)張成。

不失一般性，可以選張成k維子空間。

于是，k維k重信息空間的一個(gè)信息碼組到n維空間的k維子空間的映射，就是這k個(gè)基底矢量的線性組合：90常用信道編碼方法—線性分組碼

寫成矢量形式，就是：上式可以理解成：由信息碼組的k個(gè)碼元，組合得到碼字的n個(gè)碼元，其中k個(gè)是獨(dú)立的，

n-k個(gè)是冗余。

可以看出，給定了矩陣G，一個(gè)信息碼組m，就可以映射為一個(gè)碼字C。91常用信道編碼方法—線性分組碼

1.生成矩陣：所以矩陣G叫做生成矩陣：92常用信道編碼方法—線性分組碼

2.校驗(yàn)矩陣：把n個(gè)基底矢量剩余的k個(gè)基底張成的空間叫做校驗(yàn)空間。組成的矩陣叫做校驗(yàn)矩陣：93常用信道編碼方法—線性分組碼

2.校驗(yàn)矩陣：由于碼空間的基底和校驗(yàn)空間的基底矢量是相互正交的，故碼空間和校驗(yàn)空間相互正交：上式可用于檢驗(yàn)一個(gè)接收矢量R是不是碼字。如果，則R一定不是碼字。這也是H被叫做校驗(yàn)矩陣的原因。94常用信道編碼方法—線性分組碼

3.系統(tǒng)形式的生成矩陣：如果碼字C

=（mk-1，mk-2，…，

m0，cn-k-1，c1，c0）即：碼字的前k個(gè)碼元就是信息碼元，后n-k個(gè)碼元是由信息碼元組合得到的冗余碼元?jiǎng)t：這樣的碼字叫做系統(tǒng)碼。一般形式的生成矩陣G，用C=mG得不到系統(tǒng)碼。

為此，需要對(duì)生成矩陣G系統(tǒng)化。

95常用信道編碼方法—線性分組碼4.生成矩陣的系統(tǒng)化：如果生成矩陣是如下形式：則可以得到系統(tǒng)碼。

可以通過對(duì)普通形式的生成矩陣G做行運(yùn)算得到系統(tǒng)形式的生成矩陣

Gs

96常用信道編碼方法—線性分組碼注意：系統(tǒng)化時(shí)對(duì)生成矩陣G只能做行運(yùn)算！而不能做列運(yùn)算。原因：生成矩陣的每一行，是n維矢量空間的一個(gè)基底矢量。行運(yùn)算相當(dāng)于對(duì)基底矢量的線性組合。這種運(yùn)算并不會(huì)改變其張成的矢量空間（碼空間）。如果做列運(yùn)算，則改變了基底矢量本身。97常用信道編碼方法—線性分組碼對(duì)系統(tǒng)形式的生成矩陣：容易證明，其對(duì)應(yīng)的校驗(yàn)矩陣為：若為二進(jìn)制，則：98常用信道編碼方法—線性分組碼線性分組碼的編碼電路：

用移位寄存器、加法器和撥檔開關(guān)等電路元件可實(shí)現(xiàn)由信息碼元得到碼字碼元的編碼過程，組成編碼電原理圖，可參見下例。99常用信道編碼方法—線性分組碼例題：若一個(gè)（6，3）線性分組碼的生成矩陣為：

試：①計(jì)算碼集，列出信息碼組與碼字的映射關(guān)系；②將該碼系統(tǒng)化，計(jì)算系統(tǒng)碼碼集，并列出映射關(guān)系；③計(jì)算系統(tǒng)碼的校驗(yàn)矩陣H。若收碼為，檢驗(yàn)它是否為碼字。④

根據(jù)系統(tǒng)碼生成矩陣，畫出編碼器電原理圖。100常用信道編碼方法—線性分組碼1.信

息碼

字系統(tǒng)碼字000000000000000001011101001011010110001010110011101100011101100111010100111101100111101100110001011110001111010110111010101常用信道編碼方法—線性分組碼2.對(duì)生成矩陣G做行運(yùn)算，原第1、3行相加作為第1行，原第1、2、3行相加作為第2行，原第1、2行相加作為第三行，可得系統(tǒng)化后的生成矩陣為：102常用信道編碼方法—線性分組碼3.系統(tǒng)形式的生成矩陣為：故校驗(yàn)矩陣為：

，所以r不是碼字。103常用信道編碼方法—線性分組碼4.由系統(tǒng)形式的生成矩陣可得，碼字的各個(gè)碼元與信息碼元的關(guān)系為：104常用信道編碼方法—線性分組碼故電原理圖為：105常用信道編碼方法—線性分組碼

106常用信道編碼方法—線性分組碼

107常用信道編碼方法—線性分組碼

線性分組碼的譯碼：

1.求解差錯(cuò)圖案E

S=RHT=EHT也就是說：伴隨式S只和差錯(cuò)圖案有關(guān)。如果得到接收矢量R后，由S=RHT計(jì)算出伴隨式S，再由S=EHT計(jì)算得到差錯(cuò)圖案E，則可以得到譯碼結(jié)果。但是，差錯(cuò)圖案E=（en-1，en-2，…，e1，e0），共有n個(gè)變量；而RHT=EHT是矢量方程，共有n-k個(gè)方程（R是1×n的矢量，是n×（n-k）的矩陣）。108常用信道編碼方法—線性分組碼

線性分組碼的譯碼：

1.求解差錯(cuò)圖案En個(gè)未知數(shù)，n-k個(gè)方程，未知數(shù)個(gè)數(shù)>方程個(gè)數(shù)。

差錯(cuò)圖案E是二元域上，每一個(gè)元素為0（對(duì)應(yīng)碼元沒有差錯(cuò)）或1（對(duì)應(yīng)碼元發(fā)生了差錯(cuò)）。少1個(gè)方程，則有2組解（多出的未知數(shù)可以為0或1）；少2個(gè)方程，則有4組解；……少k個(gè)方程，則有2k組解。109常用信道編碼方法—線性分組碼

線性分組碼的譯碼：

1.求解差錯(cuò)圖案E

應(yīng)該選擇這2k組解中的哪組解？

前面說過：對(duì)二進(jìn)制通信，最大似然譯碼等價(jià)于最小漢明距離譯碼。發(fā)碼和收碼的漢明距離最小，就意味著對(duì)應(yīng)的差錯(cuò)圖案的重量最輕。

因此，應(yīng)該選2k組解中重量最輕的那個(gè)。110常用信道編碼方法—線性分組碼

111常用信道編碼方法—線性分組碼

112常用信道編碼方法—線性分組碼

線性分組碼的譯碼：

2.標(biāo)準(zhǔn)陣列譯碼表

下圖是一個(gè)標(biāo)準(zhǔn)陣列譯碼表：113常用信道編碼方法—線性分組碼

線性分組碼的譯碼：

2.標(biāo)準(zhǔn)陣列譯碼表

該表共有2n-k行，

2k列。

每一行代表一種伴隨式Si（伴隨式S是1×（n-k）的向量，對(duì)二進(jìn)制來說，共有2n-k種不同的伴隨式），也就是一種差錯(cuò)圖案Ei

（每一個(gè)伴隨式對(duì)應(yīng)的2k個(gè)解中重量最輕的那個(gè)）；每一列對(duì)應(yīng)一個(gè)發(fā)碼Cj，共有2k個(gè)不同的發(fā)碼（信息碼組是1×k的向量）；表中共有2n-k×2k=2n個(gè)元素，代表2n個(gè)不同的收碼。114常用信道編碼方法—線性分組碼

線性分組碼的譯碼：

2.標(biāo)準(zhǔn)陣列譯碼表

實(shí)際構(gòu)造標(biāo)準(zhǔn)陣列譯碼表時(shí)，并不需要對(duì)每一種伴隨式解方程組得到對(duì)應(yīng)的差錯(cuò)圖案！2n-k種不同的伴隨式，每種伴隨式有2k個(gè)差錯(cuò)圖案解，共有2n-k

×2k=2n個(gè)差錯(cuò)圖案，剛好遍歷了所有可能的差錯(cuò)圖案。

每2k個(gè)差錯(cuò)圖案解中，選一個(gè)重量最輕的，共選2n-k了種不同的差錯(cuò)圖案；由于重量輕的優(yōu)先被選擇，并且差錯(cuò)圖案是被遍歷的，所以選擇的一定是差錯(cuò)圖案中重量最輕的2n-k個(gè)。

115常用信道編碼方法—線性分組碼

線性分組碼的譯碼：

2.標(biāo)準(zhǔn)陣列譯碼表

可以先選擇重量為0的差錯(cuò)圖案（1種，全零差錯(cuò)圖案E=（0，0，…，0））；

接下來選擇重量為1的差錯(cuò)圖案（n種，“1”分別位于n個(gè)不同的位置）；

……直到選夠個(gè)不同的差錯(cuò)圖案為止。116常用信道編碼方法—線性分組碼

線性分組碼的譯碼：

2.標(biāo)準(zhǔn)陣列譯碼表每一行叫做一個(gè)“陪集”，每一個(gè)陪集的第一個(gè)元素叫做“陪集首”。陪集首就是各差錯(cuò)圖案Ej。

每一列叫做一個(gè)“子集”，每一個(gè)子集的第一個(gè)元素叫做“子集頭”。子集頭就是各發(fā)送碼字。117常用信道編碼方法—線性分組碼

線性分組碼的譯碼：

例題：設(shè)(6,3)碼的生成矩陣為其標(biāo)準(zhǔn)陣列譯碼表為：000000001101010011011110100110101011110101111000000001001100010010011111100111101010110100111001000010001111010001011100100100101001110111111010000100001001010111011010100010101111110001111100001000000101011011010110101110100011111101110000010000011101000011001110110110111011100101101000100000101101110011111110000110001011010101011000100001101100110010111111000111001010010100011001

其標(biāo)準(zhǔn)陣列如表6-3所示：表6-3(6,3)碼的標(biāo)準(zhǔn)陣列譯碼表118常用信道編碼方法—線性分組碼

線性分組碼的譯碼：若發(fā)送碼字為C=[101011]，E=[010000]，則接收碼字R=C+E=[111011]，查標(biāo)準(zhǔn)陣列表可知，它所在子集頭為C=[101011]，因此譯碼正確。又如同一碼字C=[101011]，若其差錯(cuò)圖案為E=[001100]，接收碼字R=C+E=[100111]，查表可得此收碼R對(duì)應(yīng)的C=[100110]，譯碼出現(xiàn)錯(cuò)誤。為什么？119常用信道編碼方法—線性分組碼

線性分組碼的譯碼：回顧一下上述構(gòu)造標(biāo)準(zhǔn)陣列譯碼表的過程：第1行選的是全0差錯(cuò)圖案；第2行到第7行選的是6個(gè)（n=6）重量為1的差錯(cuò)圖案；由于，故需要8行，目前已有7行，還差一行，要選用1個(gè)重量為2的差錯(cuò)圖案。重量為2的伴隨式有種。

應(yīng)該選哪一個(gè)？這15種差錯(cuò)圖案，重量均為2，所以概率相同，只能隨便選一個(gè)。這就造成了不同的選法，得到不同的標(biāo)準(zhǔn)陣列譯碼表，因此有時(shí)會(huì)得到不同的譯碼結(jié)果。上述譯碼錯(cuò)誤，就是這個(gè)原因造成的。120常用信道編碼方法—線性分組碼

線性分組碼的性質(zhì)：定理6.1：線性分組碼的最小碼距等于碼集中非零碼字的最小重量：定理6.2：任何最小碼距為的線性分組碼，其檢錯(cuò)能力為:

糾錯(cuò)能力為121常用信道編碼方法—線性分組碼

線性分組碼的性質(zhì)：

定理6.3：（n，k)線性分組碼最小碼距等于

的必要條件是：校驗(yàn)矩陣中有

列線性無關(guān)。

定理6.4：（n，k）線性分組碼的最小碼距必定小于等于（n-k+1），即：122常用信道編碼方法—線性分組碼

線性分組碼之循環(huán)碼：

線性分組碼用生成矩陣來表示，只要給定生成矩陣，線性分組碼的編碼方式就被確定下來。但用矩陣形式來表示，書寫和運(yùn)算都多有不便。有沒有一種辦法解決？123常用信道編碼方法—線性分組碼

循環(huán)碼空間：1.矢量的多項(xiàng)式表示：

碼矢量C＝[cn-1cn-2

…c1c0]可用多項(xiàng)式C(x)=cn-1xn-1+cn-2xn-2

+…+c1x+c0來表示，

C(x)稱為碼多項(xiàng)式。2.循環(huán)碼空間：一個(gè)(n,k)線性分組碼集C，若它的任意一個(gè)碼字每一循環(huán)移位仍是碼集C的一個(gè)碼字，則C是一個(gè)循環(huán)碼。如果C＝[cn-1cn-2

…c1c0]是循環(huán)碼的一個(gè)碼字，那么對(duì)C的元素循環(huán)移一位得到的C’＝[cn-2

…c1c0cn-1]，也是循環(huán)碼的一個(gè)碼字。124常用信道編碼方法—線性分組碼

循環(huán)碼空間：3.循環(huán)移位的多項(xiàng)式運(yùn)算表示：

對(duì)碼矢量C＝[cn-1cn-2

…c1c0]循環(huán)左移一位得到新的碼矢量C’＝[cn-2

…c1c0cn-1]，可用多項(xiàng)式運(yùn)算C’(x)=xC(x)mod(xn+1)來表示，

其中mod為除余運(yùn)算。125常用信道編碼方法—線性分組碼

循環(huán)碼空間：例：三維空間n=3，一組正交基分別為i、j、k，用數(shù)組表示分別為：i=（1，0，0）、j=（0，1，0）、k=（0，0，1；用多項(xiàng)式表示分別為：，和

i循環(huán)左移一位，則

ximod(x3+1)=

xx2

mod(x3+1)=

x3

mod(x3+1)=1=k即：

i循環(huán)左移一位得到k;同樣地，

k循環(huán)左移一位得到j(luò)，

j循環(huán)左移一位得到i。126常用信道編碼方法—線性分組碼

循環(huán)碼的生成多項(xiàng)式：

生成矩陣的每一行，是一個(gè)基底矢量，基底矢量也是碼矢量，也滿足循環(huán)移位性質(zhì)。只要給定一個(gè)基底矢量的碼多項(xiàng)式，經(jīng)循環(huán)移位，就可以得到所有k個(gè)基底矢量的碼多項(xiàng)式，從而確定生成矩陣。這樣的基底多項(xiàng)式，叫做生成多項(xiàng)式。定理：(n,k)循環(huán)碼中，一定存在一個(gè)g(x)＝x

n-k

+gn-k-1x

n-k-1+…+g2x2+g1x+1的(n-k)次首一碼多項(xiàng)式（即(n-k)次項(xiàng)的系數(shù)為1），使得所有的碼多項(xiàng)式都是g(x)的倍式，即c(x)=m(x)g(x)

，且g(x)一定是(xn+1)的因子。127常用信道編碼方法—線性分組碼

循環(huán)碼的生成多項(xiàng)式：如果生成多項(xiàng)式為

，再經(jīng)k-1次循環(huán)移位，就可得到k個(gè)碼多項(xiàng)式：，，…，

。寫成矩陣形式，就可得到多項(xiàng)式形式的生成矩陣：128常用信道編碼方法—線性分組碼

循環(huán)碼的生成多項(xiàng)式：將給定的一個(gè)信息碼組寫成信息多項(xiàng)式：則可得碼多項(xiàng)式：129常用信道編碼方法—線性分組碼

循環(huán)碼的生成多項(xiàng)式：

例：設(shè)二進(jìn)制(7,4)循環(huán)碼的生成多項(xiàng)式為，求其生成矩陣G及生成的碼字。解：即：130常用信道編碼方法—線性分組碼

循環(huán)碼的生成多項(xiàng)式：由此生成矩陣G生成的(7,4)循環(huán)碼的碼字如表所示：消息碼字消息碼字000000000001000101100000010001011100011010011001000101101010100111000110011101101110001010100010110011001110100010101001111101111111101100111010111011000100111011000111111101001131常用信道編碼方法—線性分組碼

循環(huán)碼的生成多項(xiàng)式：也可用信息多項(xiàng)式方法得到碼字，例如，對(duì)于信息碼組“1101”，其對(duì)應(yīng)的信息多項(xiàng)式為：故碼多項(xiàng)式為：可得碼字為（1111111）。132常用信道編碼方法—線性分組碼

循環(huán)碼的校驗(yàn)多項(xiàng)式：由于生成多項(xiàng)式g(x)是多項(xiàng)式xn+1的因子，故：xn+1＝g(x)h(x)其中，h(x)叫做該循環(huán)碼的一致校驗(yàn)多項(xiàng)式，其階次為k。h(x)的校驗(yàn)作用表現(xiàn)在：任何碼多項(xiàng)式C(x)與h(x)的模xn+1乘積一定等于0，而非碼字與h(x)的乘積必不為0：C(x)h(x)=m(x)g(x)h(x)=m(x)(xn+1)=0mod(xn+1)循環(huán)碼是一種特殊的線性分組碼，故線性分組碼的譯碼方法也完全適用于循環(huán)碼。133常用信道編碼方法—卷積碼卷積碼的產(chǎn)生分組碼以孤立碼塊為單位編譯碼信息流割裂為孤立塊后喪失了分組間的相關(guān)信息分組碼長(zhǎng)n越大越好，但譯碼運(yùn)算量隨n指數(shù)上升問題

如何在不增加碼長(zhǎng)n，充分利用各個(gè)碼字之間的相關(guān)性，等價(jià)于增加了碼長(zhǎng)，從而提高系統(tǒng)性能，但譯碼復(fù)雜度并無太多增加？卷積碼的編碼將信息序列分隔成長(zhǎng)度k的一個(gè)個(gè)分組某一時(shí)刻的編碼輸出不僅取決于本時(shí)刻的分組，而且取決于本時(shí)刻以前的L個(gè)分組。稱L＋1為約束長(zhǎng)度最重要的三個(gè)參數(shù)(n,k,L)(n,k,L)卷積編碼示意卷積碼的編碼也可以將卷積編碼器畫成下圖所示的一般結(jié)構(gòu)。圖中每一列是一個(gè)信息碼組，最左列是當(dāng)前信息碼組；所有信息碼組（L+1個(gè)）一起進(jìn)入線性組合器，組合得到當(dāng)前碼字的各個(gè)碼元。卷積編碼器的一般結(jié)構(gòu)卷積編碼器的一般結(jié)構(gòu)輸出碼元與信息碼元的關(guān)系可寫為：其中，表示第l個(gè)信息碼組的第p個(gè)信息碼元對(duì)輸出碼字的第j個(gè)碼元的貢獻(xiàn)。對(duì)二進(jìn)制，，表示第l個(gè)信息碼組的第p個(gè)信息碼元對(duì)輸出碼字的第j個(gè)碼元有貢獻(xiàn)；則表示第l個(gè)信息碼組的第p個(gè)信息碼元對(duì)輸出碼字的第j個(gè)碼元沒有貢獻(xiàn)。卷積編碼器的轉(zhuǎn)移函數(shù)矩陣一個(gè)信息碼組的各個(gè)碼元，對(duì)碼字各個(gè)碼元的貢獻(xiàn)，可以用一個(gè)k×n的矩陣來表示其中，這實(shí)際上就是線性分組碼的生成矩陣。由于（

n,k,L

）卷積碼有L+1個(gè)信息碼組參與線性組合，因此會(huì)有L+1個(gè)k×n的矩陣?；蛘哒f，（

n,k,L

）卷積碼的生成矩陣是一個(gè)k×n×(L+1)的三維矩陣?？梢园讶S生成矩陣的第三維壓縮在一起，變成一個(gè)二維矩陣，以便書寫。該二維矩陣的每一個(gè)元素，實(shí)際上是第三維的L+1個(gè)元素的疊加。為了能區(qū)分出來，用多項(xiàng)式表示：卷積編碼器的轉(zhuǎn)移函數(shù)矩陣

其中，Dl對(duì)應(yīng)項(xiàng)的系數(shù)，即為第三維的第l個(gè)元素。于是可以寫成：該矩陣叫做卷積碼的轉(zhuǎn)移函數(shù)矩陣。例6-3某二元（3,1,2）卷積碼的轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)矩陣為G(D)=(1,1+D,1+D+D2)，試畫出其編碼器電原理圖。該卷積碼信息緩存矩陣為1×3，三維矩陣中的平面數(shù)目（L+1）為3，根據(jù)轉(zhuǎn)移函數(shù)矩陣=（1,1+D,1+D+D2）可分解出三個(gè)平面（分別對(duì)應(yīng)緩存矩陣的三列）對(duì)應(yīng)的二維矩陣為：G0=(1,1,1),G1=(0,1,1)，G2=(0,0,1)卷積編碼器的狀態(tài)流圖

卷積編碼器除了可用轉(zhuǎn)移函數(shù)矩陣表示，還可用狀態(tài)流圖來表示。

卷積編碼器輸出的某一碼字，除了和當(dāng)前時(shí)間單元的信息碼組有關(guān)，還和當(dāng)前時(shí)間單元以前的信息有關(guān)。可以把當(dāng)前時(shí)刻之前L個(gè)信息碼組，作為當(dāng)前時(shí)刻所處的狀態(tài)。

卷積編碼器當(dāng)前的輸出碼字，由當(dāng)前時(shí)間單元的信息碼組和當(dāng)前時(shí)間單元以前的L組信息碼組決定，即：卷積編碼器的狀態(tài)流圖

如果把當(dāng)前單元之前的L組信息碼元作為當(dāng)前的狀態(tài)，即：則：

并且，隨著當(dāng)前時(shí)間單元信息碼組的出現(xiàn)，下一時(shí)間單元的狀態(tài)會(huì)隨之發(fā)生變化：卷積編碼器的狀態(tài)流圖

于是，隨著信息碼組的不斷出現(xiàn)，狀態(tài)之間相互轉(zhuǎn)移，并且隨著狀態(tài)轉(zhuǎn)移而產(chǎn)生碼字序列。我們可以用狀態(tài)流圖來表示。卷積編碼器的狀態(tài)流圖例6-4：例6-3中的（3，1，2）卷積編碼器，試畫出其狀態(tài)流圖。如果輸入信息碼組序列為10110…，給出輸出碼字序列。解：由于（3，1，2）卷積編碼器的L=2，故當(dāng)前時(shí)間單元的狀態(tài)由前面兩個(gè)信息碼組決定。每個(gè)信息碼組只有1比特，所以共有四種不同的狀態(tài)，如表所示：狀態(tài)S000S101S210S311卷積編碼器的狀態(tài)流圖

在每一種狀態(tài)下，隨著當(dāng)前時(shí)間單元信息碼組mi（mi=0或1）的到來，線性組合器會(huì)輸出相應(yīng)的碼字序列，如表所示：輸入

狀態(tài)S0000111S1001110S2011100S3010101卷積編碼器的狀態(tài)流圖

而且，由于新的信息碼組到來，使得狀態(tài)發(fā)生了變化，如表所示：輸入

狀態(tài)S0S0S2S1S0S2S2S1S3S3S1S3卷積編碼器的狀態(tài)流圖0/000

S01/1110/0011/110

S2

S10/0111/1000/010

S31/101

圖6-7(3,1,2)卷積碼狀態(tài)流圖將其畫成狀態(tài)流圖，如圖所示：假如輸入信息序列 是10110…，則

卷積編碼器的網(wǎng)格圖隨著信息碼組序列的輸入，狀態(tài)流圖是在狀態(tài)轉(zhuǎn)移圖上循環(huán)往復(fù)，不能清楚地表明編碼過程。網(wǎng)格圖可以清楚地表明整個(gè)編碼過程?？梢钥闯墒菭顟B(tài)流圖隨著信息碼組序列輸入過程的時(shí)間展開。例6-4的網(wǎng)格圖如下圖所示：卷積編碼器的網(wǎng)格圖輸入信息序列是10110…，輸出碼字是111，011，110，100，010…第一部分：網(wǎng)格圖 第二部分：編碼軌跡（路徑）圖卷積碼的譯碼對(duì)于線性分組碼，由于碼字之間沒有關(guān)系，所以每個(gè)碼字可以單獨(dú)譯碼，如果采用最大似然譯碼準(zhǔn)則，對(duì)于二進(jìn)制編碼來說，就是最小漢明距離譯碼：對(duì)一個(gè)收碼R，在所有許用碼字中，選擇一個(gè)和收碼漢明距離最小的，作為譯碼輸出。卷積碼的譯碼對(duì)于卷積碼來說，由于碼字之間是有相關(guān)性的，前一個(gè)碼字的輸出，還同時(shí)決定了下一個(gè)狀態(tài)，而下一個(gè)碼字的輸出，是和狀態(tài)有關(guān)的。因此，對(duì)一個(gè)時(shí)刻的收碼R，譯成和其漢明距離最小的許用碼字，從碼字序列的整體來看，就不一定是最好的。卷積碼的譯碼例6-5：例6-3中的（3，1，2）卷積碼，假定目前處于S0狀態(tài)，連續(xù)三個(gè)收碼分別為010、011，101。如果按照線性分組碼的最大似然譯碼，每個(gè)碼字獨(dú)立譯碼，則譯碼過程為：

輸出碼字為000（與收碼漢明距離為1）、111（與收碼漢明距離為1）和011（與收碼漢明距離為2）。如果把序列作為整體，則譯碼序列與收碼序列漢明距離為4。卷積碼的譯碼實(shí)際上，由于每次從某個(gè)狀態(tài)出發(fā)，可以有兩條路徑，當(dāng)收到3個(gè)收碼以后，可以有23=8條路徑，如下圖所示：卷積碼的譯碼相應(yīng)地，有8種譯碼輸出序列：①000、000、000，譯碼序列與收碼序列漢明距離為5；②000、000、111，譯碼序列與收碼序列漢明距離為4；③000、111、011，譯碼序列與收碼序列漢明距離為4；④000、111、100，譯碼序列與收碼序列漢明距離為3；⑤111、011、001，譯碼序列與收碼序列漢明距離為3；⑥111、011、110，譯碼序列與收碼序列漢明距離為4；⑦111、100、010，譯碼序列與收碼序列漢明距離為8；⑧111、100、101，譯碼序列與收碼序列漢明距離為5。卷積碼的譯碼可以看出：序列④和序列⑤具有最小的序列漢明距離（漢明距離為3），按照最大似然規(guī)則，應(yīng)該譯為序列④（或序列⑤，兩者具有相同的差錯(cuò)概率）；按照線性分組碼的單獨(dú)譯碼算法得到的結(jié)果，實(shí)際上是這里的序列③，序列漢明距離為4，顯然不是最佳的。卷積碼的譯碼例6-5說明，對(duì)于卷積碼，由于碼字之間是有關(guān)系的，因此，即使譯碼時(shí)某條譯碼路徑當(dāng)時(shí)看來是最好的，但也有可能該路徑是一個(gè)錯(cuò)誤路徑，導(dǎo)致沿著該路徑輸出錯(cuò)誤的譯碼碼字序列，后續(xù)碼字的譯碼將會(huì)出現(xiàn)較多比特的錯(cuò)誤。卷積碼的譯碼由此看來，卷積碼的譯碼過程中，似乎每一條可能路徑都不能隨便舍棄掉，因?yàn)椴坏阶g碼結(jié)束，每一條允許路徑都是可能的譯碼路徑。但是，如果在譯碼結(jié)束前保留每一條允許譯碼路徑的話，將導(dǎo)致譯碼路徑數(shù)指數(shù)級(jí)增加，因?yàn)樵试S路徑數(shù)為2M，M為收碼序列中收碼的個(gè)數(shù)。并且由于只有譯碼結(jié)束的時(shí)候，才可以輸出最佳的譯碼結(jié)果，使得譯碼時(shí)延很大。卷積碼的譯碼1967年，維特比(Viterbi)提出了一種用于卷積碼的最大似然譯碼方法。它對(duì)（n，k，L）卷積碼中約束長(zhǎng)度L較小的卷積碼的譯碼很容易實(shí)現(xiàn)，因此被廣泛地應(yīng)用于現(xiàn)代通信中，稱為維特比算法或維特比譯碼。卷積碼的譯碼-維特比譯碼維特比譯碼方法①

路徑舍棄

實(shí)際上，譯碼過程并不需要記憶所有的允許路徑。在譯碼過程中，有些路徑會(huì)隨著譯碼過程的進(jìn)行不斷被舍棄。

設(shè)有兩條（或多條）不同路徑在當(dāng)前時(shí)刻均到達(dá)狀態(tài)Si。

此后的譯碼，只和當(dāng)前時(shí)刻的狀態(tài)有關(guān)，而與如何到達(dá)本狀態(tài)的路徑無關(guān)；因此，根據(jù)最大似然原則，到達(dá)本狀態(tài)的多條路徑中，與收碼序列漢明距離最小的那條路徑，是最佳的，應(yīng)該保留，稱為幸存路徑；而剩余其他的路徑，就可以舍棄掉。卷積碼的譯碼-維特比譯碼維特比譯碼方法①

路徑舍棄

若有T種不同的狀態(tài)，由于到達(dá)每一種狀態(tài)的幸存路徑只有一個(gè)，所以每個(gè)時(shí)刻只會(huì)保留T條幸存路徑。卷積碼的譯碼-維特比譯碼例6-6：例6-3中的（3，1，2）卷積碼，假定起始時(shí)刻處于S0狀態(tài)，連續(xù)三個(gè)收碼分別為110、111，011，用PMl（i）表示第i個(gè)狀態(tài)在第l個(gè)時(shí)刻的路徑度量（所謂路徑度量，即該路徑上譯碼輸出序列與收碼序列的漢明距離）。分析各時(shí)刻可能的譯碼路徑、該路徑的路徑度量及幸存路徑（若到達(dá)某一狀態(tài)多條路徑的路徑度量相同，則可取其中的任一條做為幸存路徑，因?yàn)樗鼈兙哂邢嗤牟铄e(cuò)概率）。卷積碼的譯碼-維特比譯碼解：i）起始時(shí)刻（l=0）起始時(shí)刻處于S0狀態(tài)，ii）第1個(gè)時(shí)刻（l=1）此時(shí)各狀態(tài)對(duì)應(yīng)的PMl（i）如下圖所示：卷積碼的譯碼-維特比譯碼iii）第2個(gè)時(shí)刻（l=2）此時(shí)各狀態(tài)對(duì)應(yīng)的PMl（i）如下圖所示：卷積碼的譯碼-維特比譯碼iv）第3個(gè)時(shí)刻（l=3）此時(shí)各狀態(tài)對(duì)應(yīng)的PMl（i）如下圖所示：卷積碼的譯碼-維特比譯碼

在l=3時(shí)刻，到達(dá)每一狀態(tài)均有兩條路徑，其中用實(shí)線表示的，是兩條路徑中路徑度量較小者，為幸存路徑，另一條路徑用虛線表示，被舍棄。例如：在l=3時(shí)刻，有兩條路徑到達(dá)S0狀態(tài)，一條是從上個(gè)S0狀態(tài)到達(dá)，其路徑度量為7；另一條是從狀態(tài)S1到達(dá)，其路徑度量為3，該條路徑為幸存路徑。

由于路徑舍棄（只保留幸運(yùn)路徑），使得每個(gè)狀態(tài)只保留一條路徑（幸存路徑），稱為留存路徑。因此，對(duì)維特比譯碼來說，在每個(gè)時(shí)刻（初始幾個(gè)時(shí)刻除外），都有2k條留存路徑（因?yàn)楣灿?k個(gè)不同的狀態(tài)）。卷積碼的譯碼-維特比譯碼②

提前輸出

當(dāng)收碼序列全部接收完以后，比較每條留存路徑的路徑度量，路徑度量最小的那條路徑，就是最大似然路徑，沿著該路徑，就可以得到譯碼序列。如例6-6中，如果收碼序列只有3個(gè)：110、111、011，則當(dāng)接收完收碼序列后，比較最后一個(gè)時(shí)刻（l=3）時(shí)各留存路徑的路徑度量可知,這條路徑的路徑度量最?。ǎ?，所以該路徑為最大似然路徑，譯碼序列為：000、111、011.卷積碼的譯碼-維特比譯碼但是，如果等收碼序列全部接收完以后，再根據(jù)各留存路徑的路徑度量，找出最大似然路徑，從而輸出譯碼序列，將會(huì)導(dǎo)致很大的譯碼時(shí)延，而且每條留存路徑都很長(zhǎng)，需要較大的存儲(chǔ)量。卷積碼的譯碼-維特比譯碼實(shí)際上，隨著收碼不斷到達(dá)譯碼器，各留存路徑的路徑度量是單調(diào)增加的，但增加的速度不一樣。正確的譯碼路徑，其路徑度量值增大的程度，取決于接收碼字的差錯(cuò)，一般來說，正常通信時(shí)，該差錯(cuò)概率比較??；而其他路徑的路徑度量值增大，是由于路徑差異導(dǎo)致的，上升速度會(huì)很快。所以，經(jīng)過一段時(shí)延后，正確路徑的路徑度量就會(huì)變成所有留存路徑中最小的。卷積碼的譯碼-維特比譯碼因此，隨著收碼不斷到來，各狀態(tài)留存路徑較靠前的部分，有合并為一條的趨勢(shì)。如例6-6中，在l=3時(shí)，狀態(tài)S1的留存路徑和狀態(tài)S3的留存路徑，靠前的部分，已經(jīng)是一樣的了（都是

）。也就是說，經(jīng)過一段時(shí)間后，各條留存路徑的靠前部分，已經(jīng)有很大概率是一樣的了，此時(shí)，我們可以把最靠前的一個(gè)譯碼碼字輸出，而不必等到全部收碼序列都完成接收。卷積碼的譯碼-維特比譯碼維特比譯碼方法，就是設(shè)定一個(gè)時(shí)延D（一般取卷積碼狀態(tài)數(shù)的5倍），當(dāng)譯碼時(shí)間達(dá)到時(shí)延D時(shí)，就把當(dāng)時(shí)的最佳留存路徑（路徑度量最小的路徑）最前面的一個(gè)碼字輸出，而不必等到所有收碼全部接收完。稱之為提前輸出。卷積碼的譯碼-維特比譯碼例6-7：例6-3中的