一種優(yōu)雅高效的卷積碼譯碼方法—維特比譯碼

本文翻譯自 MIT 6.02 DRAFT Lecture Notes, 2012

CHAPTER 8:Viterbi Decoding of Convolutional Codes

面臨的問題

在接收端，我們有一組對應(yīng)于發(fā)射監(jiān)督比特的電壓采樣序列。為簡單并不失一般性，我們將假設(shè)接收端獲得了最佳采樣點(diǎn)（或者一組采樣集的均值對應(yīng)一個(gè)監(jiān)督位），通過與閾值比較判為“0”或“1”（解映射），并將判決結(jié)果傳遞給譯碼器。

現(xiàn)在我們有了一組接收比特序列，對應(yīng)于卷積編碼輸出的監(jiān)督比特。在沒有關(guān)于采樣點(diǎn)和譯碼器其它信息的情況下，譯碼過程被稱為硬判決譯碼（“硬譯碼”）。 如果提供給譯碼器以采樣點(diǎn)的“模擬”信息（以數(shù)字化形式，通過模數(shù)轉(zhuǎn)換量化），我們稱該過程為軟判決譯碼（“軟譯碼”）。

維特比譯碼器適用于任何一種情況。直觀講，由于硬判決譯碼會(huì)對比特是0還是1做出早期判決，因此在數(shù)字化過程中丟失了部分信息。硬判決將在接收的比特序列中引入更多的誤碼，因?yàn)樗赡茏龀鲥e(cuò)誤的判決，特別是對于接近閾值的電壓而言。盡管硬判決譯碼仍然可以產(chǎn)生最可能的發(fā)送序列，然而由于早期數(shù)字化中引入額外的錯(cuò)誤，其糾錯(cuò)能力將小于軟判決譯碼。但硬判決譯碼在概念上更容易理解，因此我們將從此開始，然后再介紹軟判決譯碼。

圖1

如前一章所述，網(wǎng)格為了解卷積碼的譯碼過程提供了一個(gè)很好的框架（如圖1）。假設(shè)我們有表述一組碼的整個(gè)網(wǎng)格，并且接收到一串?dāng)?shù)字比特（或電壓樣點(diǎn)）。如果接收沒有錯(cuò)誤，那么定會(huì)有一些網(wǎng)格路徑與接收到的序列完全匹配，該路徑對應(yīng)于發(fā)射監(jiān)督比特（具體地說是在狀態(tài)轉(zhuǎn)移的過程中產(chǎn)生的發(fā)射監(jiān)督比特）。從網(wǎng)格的每個(gè)節(jié)點(diǎn)發(fā)出，往上的路徑對應(yīng)于“0”bit，往下的路徑對應(yīng)于“1”bit，據(jù)此很容易譯得原始編碼信息。

當(dāng)有誤碼發(fā)生時(shí)，我們可以做什么？如前所述，找到最可能發(fā)送的消息序列是有吸引力的，因?yàn)樗畲笙薅鹊販p少了譯碼的誤碼率。如果我們能夠想出一種方法來度量從一個(gè)狀態(tài)到下一個(gè)狀態(tài)所引入的錯(cuò)誤量，那么我們可以沿著一條路徑累積這些錯(cuò)誤量，并得出沿著該路徑的總錯(cuò)誤量。然后，以此得到的總錯(cuò)誤量最小的路徑就是我們想要的路徑，并且發(fā)送的消息序列可以通過上面解釋的狀態(tài)轉(zhuǎn)移關(guān)系方便地確定。

我們需要一種方法來收集通過網(wǎng)格狀態(tài)時(shí)發(fā)生的任何錯(cuò)誤，以及無需遍歷整個(gè)網(wǎng)格的路徑導(dǎo)航方式（即無需窮舉所有可能路徑也能找到累積錯(cuò)誤最小的那條路徑），維特比譯碼器解決了這些問題。動(dòng)態(tài)規(guī)劃是一個(gè)解決優(yōu)化問題的普遍方法，維特比譯碼就是其中一例。在本課程的后面，我們將在網(wǎng)絡(luò)路由中應(yīng)用相似的概念，可以在多跳網(wǎng)絡(luò)中找到好的路徑。

維特比譯碼器

譯碼算法使用兩個(gè)度量：分支度量（branch metric,BM）和路徑度量（path metric,PM）。分支度量計(jì)算的是發(fā)射和接收內(nèi)容之間的“距離”，它是為網(wǎng)格中的每條分支路徑定義的。在硬判決譯碼中，給出一組已經(jīng)數(shù)字化的接收監(jiān)督比特，分支度量就是監(jiān)督比特預(yù)測值和接收監(jiān)督比特之間的漢明距離。圖2展示了一個(gè)示例，其中接收的位為00，對于每個(gè)狀態(tài)轉(zhuǎn)移，分支路徑上的數(shù)字顯示該轉(zhuǎn)移的分支度量。其中有兩條路徑的分支量度為0，對應(yīng)于漢明距離為0的唯一狀態(tài)和轉(zhuǎn)移關(guān)系，其他非0分支量度對應(yīng)于存在位錯(cuò)誤的情況。

圖 2

路徑度量值與網(wǎng)格中的狀態(tài)相關(guān)聯(lián)（即與整個(gè)路徑的每個(gè)節(jié)點(diǎn)有關(guān)）。對于硬判決解碼，它對應(yīng)于網(wǎng)格中從初始狀態(tài)到當(dāng)前狀態(tài)的最可能路徑與接收監(jiān)督比特序列間的漢明距離?！白钣锌赡堋笔侵冈谟?jì)算從初始狀態(tài)到當(dāng)前狀態(tài)之間的所有可能路徑度量后，取漢明距離最小的那條。具有最小漢明距離的路徑使誤碼最小化，并且當(dāng)誤碼率較低時(shí)具有最大似然度。

維特比算法的關(guān)鍵點(diǎn)在于，接收機(jī)可以使用分支度量和先前計(jì)算的狀態(tài)路徑度量遞推地計(jì)算當(dāng)前狀態(tài)的路徑度量。

計(jì)算路徑度量

假設(shè)接收機(jī)已經(jīng)在時(shí)刻i計(jì)算好每個(gè)狀態(tài)s的路徑量度PM[s,i]（設(shè)卷積碼的編碼約束度為K，則狀態(tài)數(shù)為2^(K-1)）。在硬判決譯碼中，PM[s,i]的值是在接收監(jiān)督比特與最可能發(fā)送的消息進(jìn)行比較時(shí)得到的差錯(cuò)比特總數(shù)（通常我們將狀態(tài)“00”作為起始狀態(tài)）。

在時(shí)刻i的所有可能狀態(tài)中，最可能的狀態(tài)是具有最小路徑度量的狀態(tài)。如果具備最小路徑度量的狀態(tài)不止一個(gè)，那它們擁有相等的可能性。

現(xiàn)在，我們?nèi)绾未_定時(shí)刻i+1下每個(gè)狀態(tài)s的路徑度量PM[s,i+1]呢？要回答這個(gè)問題，首先要注意的是，對于i+1時(shí)刻的狀態(tài)s，它必須由i時(shí)刻的兩種可能狀態(tài)中的一個(gè)中轉(zhuǎn)移而來。這兩個(gè)之前狀態(tài)記為α和β，并且對于給定的狀態(tài)s，它們是固定的。實(shí)際上α和β僅由卷積碼的編碼約束度決定，與生成多項(xiàng)式無關(guān)。圖2顯示了每個(gè)狀態(tài)的之前狀態(tài)（箭頭的另一端），該例中，對于狀態(tài)00，α= 00 ，β= 01；對于狀態(tài)01，α= 10 ，β= 11。

任何使得發(fā)射機(jī)在i+1時(shí)刻處于狀態(tài)s的信息序列必定使得發(fā)射機(jī)在i時(shí)刻位于狀態(tài)α或β。例如，在圖2中，在時(shí)刻i+1時(shí)到達(dá)狀態(tài)01，必定符合以下兩點(diǎn)之一：

1. 發(fā)射機(jī)在時(shí)刻i位于狀態(tài)10，且第i個(gè)信息比特為0。在這種情況下，發(fā)射機(jī)輸出監(jiān)督位11。由于接收比特為00，因此將產(chǎn)生2位誤碼，新的狀態(tài)路徑度量PM[01,i+1] = PM[10,i] + 2。
2. 發(fā)射機(jī)在時(shí)刻i位于狀態(tài)11，且第i個(gè)信息比特為0。在這種情況下，發(fā)射機(jī)輸出監(jiān)督位01。由于接收比特為00，因此將產(chǎn)生1位誤碼，新的狀態(tài)路徑度量PM[01,i+1] = PM[11,i] + 1。

通過上面直觀的分析，我們看到：

（式1）

其中α和β為上一時(shí)刻的可能狀態(tài)。

在譯碼算法中，重要的是記錄最小漢明距離對應(yīng)的那條路徑，因?yàn)槲覀冃枰ㄟ^跟蹤所記錄的路徑，遍歷從最終狀態(tài)到最初狀態(tài)的整條路徑，然后將估計(jì)比特倒序，最終得到最可能的消息。

尋找最大似然路徑

現(xiàn)在我們可以來描述譯碼器是如何找到最大似然路徑了。初始時(shí)，狀態(tài)00代價(jià)為0，其它2^(k-1)-1個(gè)狀態(tài)代價(jià)為正無窮（∞）。

算法的主循環(huán)由兩個(gè)主要步驟組成：首先計(jì)算下一時(shí)刻監(jiān)督比特序列的分支度量，然后計(jì)算該時(shí)刻各狀態(tài)的路徑度量。路徑度量的計(jì)算可以被認(rèn)為是一個(gè)“加比選”過程：

1.將分支度量與上一時(shí)刻狀態(tài)的路徑度量相加。

2.每一狀態(tài)比較達(dá)到該狀態(tài)的所有路徑（每時(shí)刻每個(gè)狀態(tài)只有兩條這樣的路徑進(jìn)行比較，因?yàn)橹挥袃蓷l來自前一時(shí)刻狀態(tài)的分支）。

3.每一狀態(tài)刪除其余到達(dá)路徑，保留最小度量的路徑（稱為幸存路徑），該路徑對應(yīng)于錯(cuò)誤最少的路徑。

圖3顯示了維特比譯碼器從一個(gè)時(shí)刻到下一個(gè)時(shí)刻的譯碼過程。這個(gè)例子顯示接收到的位序列為11 10 11 00 01 10，以及接收器如何處理它。第四部分顯示了具有相同路徑度量四個(gè)不同狀態(tài)，在這個(gè)階段，通向這四個(gè)狀態(tài)的任一路徑都是最可能發(fā)送的比特序列（它們都具有度量為2的漢明距離）。最下面的部分只顯示幸存路徑的情況，幸存路徑是有可能成為最大似然路徑的路徑。還有很多其他路徑可以被刪除，因?yàn)樗鼈儾豢赡苡袪顟B(tài)回溯回來。維特比譯碼器之所以能被實(shí)際應(yīng)用，是因?yàn)樾掖媛窂降臄?shù)量遠(yuǎn)遠(yuǎn)小于網(wǎng)格中所有可能路徑的總數(shù)。

圖 3

關(guān)于維特比譯碼器的另一個(gè)重點(diǎn)是，未來的知識(shí)將幫助它打破任何關(guān)系，甚至可能導(dǎo)致在特定時(shí)刻步驟被認(rèn)為“最可能”的路徑發(fā)生改變。圖4繼續(xù)圖3中的例子，直到所有接收到監(jiān)督比特序列都被譯碼，得到最有可能的發(fā)送消息路徑，其具有兩位錯(cuò)誤。

圖 4

軟判決譯碼

硬判決譯碼通過將接收到的電壓信號(hào)與閾值進(jìn)行比較，數(shù)字化后將其傳遞給譯碼器進(jìn)行譯碼。結(jié)果，我們失去了部分信息：電壓為0.500001時(shí)數(shù)字化結(jié)果的可信度肯定比電壓為0.999999時(shí)低得多，但兩者都被視為“1”，且譯碼器現(xiàn)在以相同的方式對待它們，盡管0.999999比其他值更可能是“1”。

軟判決譯碼（有時(shí)也稱為“軟輸入維特比譯碼”）建立在這一觀察上，它在譯碼之前不會(huì)數(shù)字化輸入樣本。相反，它使用具備連續(xù)性的模擬樣本（經(jīng)采樣量化）作為譯碼器的輸入。例如，如果期望的發(fā)射監(jiān)督位為0并且接收到的電壓為0.3V，那么我們可以使用0.3（或0.32或某些此類函數(shù)）作為該位的值，而不是數(shù)字化它。

一個(gè)恰當(dāng)?shù)亩攘坑?jì)算方式是求接收電壓和預(yù)期電壓之差的平方，其中的技術(shù)原理將在后面講到。如果卷積碼產(chǎn)生p個(gè)監(jiān)督比特，它們對應(yīng)的模擬樣本是v = v1，v2，...，vp，可以按如下方式構(gòu)建軟判決分支度量：

（式2）

u = u1，u2，...，up是預(yù)期的p個(gè)監(jiān)督位（為0或1）。圖5顯示了p=2時(shí)，當(dāng)u為00時(shí)的軟判決分支度量。

圖5

軟判決譯碼算法與前述硬判決譯碼的譯碼過程相同，除了分支度量不再是整數(shù)漢明距離而是一個(gè)正實(shí)數(shù)。

事實(shí)證明，當(dāng)信道經(jīng)受加性高斯噪聲時(shí)，該軟判決度量與正確譯碼的概率密切相關(guān)。首先，我們來看1個(gè)監(jiān)督比特位時(shí)的簡單情況（可直接擴(kuò)展為其它一般情況），假設(shè)接收機(jī)獲得的第i個(gè)監(jiān)督位對應(yīng)的數(shù)據(jù)為電壓vi（在硬判決譯碼中，根據(jù)vi是小于還是大于0.5，它將判為為0或1），當(dāng)發(fā)送信息位為ui時(shí)（0或1），vi將被接收的概率是多少？當(dāng)信道噪聲為零均值加性高斯噪聲時(shí)，此事件的PDF由下式給出：

（式3）

其中，ui=0時(shí)，di=vi^2；ui=1時(shí)，di=(vi-1)^2。

該P(yáng)DF的對數(shù)似然函數(shù)與-di^2成比例。一組發(fā)送碼序列U = ui,u2,...,up得到接收序列V = v1,v2,...,vp，其聯(lián)合概率密度函數(shù)為各獨(dú)立樣點(diǎn)PDF的乘積。該路徑的對數(shù)PDF為各獨(dú)立樣點(diǎn)對數(shù)似然函數(shù)的和，且與-∑i(di^2)成比例。

但這恰恰是我們在公式2中定義的分支度量的負(fù)值，維特比譯碼器最小化不同的可能路徑度量，而最小化路徑度量等同于最大化對數(shù)似然度！

這意味著軟判決譯碼器產(chǎn)生與接收的電壓序列相對應(yīng)的最大似然路徑。

我們之所以選擇平方和作為公式2的分支度量，是由于其與對數(shù)PDF的直接關(guān)系。不同的噪聲分布（除了高斯）可能需要不同的軟解碼分支度量，以獲得與正確譯碼PDF類似的聯(lián)系。

實(shí)現(xiàn)更高和更精細(xì)的匹配速率：打孔

按目前為止所描述的，卷積碼的最大碼率為1／r，其中r是由卷積碼1比特輸入生成的監(jiān)督比特?cái)?shù)。但是如果我們想要一個(gè)大于1/2的碼率，或者一些在1／r和1/(r+1)之間的碼率呢？

一種叫做打孔的通用技術(shù)給我們提供了一種方法。其思想很簡單：編碼器不發(fā)送每一個(gè)監(jiān)督位，而是在輸出流上進(jìn)行打孔，僅發(fā)射由收發(fā)雙方約定好的部分碼流。例如，對于1/2卷積編碼，一個(gè)人通過在編碼輸出上每3bit刪除一個(gè)特定位，原本每3bit需要發(fā)送6bit監(jiān)督數(shù)據(jù)，而現(xiàn)在只需要發(fā)送4bit，由此得到3/4碼率的編碼輸出。

在這個(gè)例子中，設(shè)卷積編碼器為1/2編碼，在打孔前，需要發(fā)送p0[0]p1[0]p0[1]p1[1]p0[2]p1[2]，在打孔之后則只發(fā)送p0[0]p1[0]-p1[1]p0[2]-，其中-表示被刪除的比特。

在譯碼器中，當(dāng)使用打孔編碼時(shí)，被刪除的監(jiān)督位不參與分支度量的計(jì)算，除此之外的譯碼過程與以前相同。我們可以把每一個(gè)缺失的監(jiān)督位看作一個(gè)空白（“-”），運(yùn)行譯碼器時(shí)只需跳過空白。

編碼和譯碼的實(shí)現(xiàn)復(fù)雜度

關(guān)于卷積編碼器和維特比譯碼器的時(shí)間和空間復(fù)雜度，我們必須回答兩個(gè)重要的問題：

1. 編碼器需要多少狀態(tài)和存儲(chǔ)空間？
2. 譯碼器需要多少時(shí)間完成譯碼？

第一個(gè)問題容易回答：在編碼器端，需要的存儲(chǔ)空間與編碼約束度K成線性關(guān)系；需要的時(shí)間與消息長度n成線性關(guān)系。編碼器比維特比譯碼器的實(shí)現(xiàn)要容易的多。譯碼器需要的時(shí)間取決于編碼約束度K和接收序列長度（與n成線性關(guān)系）。在每個(gè)時(shí)刻，譯碼器需要計(jì)算轉(zhuǎn)移至每一狀態(tài)的兩條分支路徑，共2^(K-1)個(gè)狀態(tài)，需要進(jìn)行2^K次比較，因此譯碼n比特信息的時(shí)間復(fù)雜度為O(n*2^K)。

此外，按目前所描述的來看，我們只能在最末端解碼消息的第一位。有一點(diǎn)需要表明，雖然未來的知識(shí)是有用的，但假設(shè)編碼約束度為6，第1000時(shí)刻的比特不太可能會(huì)改變我們對第1時(shí)刻比特的譯碼結(jié)果。事實(shí)上，在實(shí)踐中，譯碼器計(jì)算長度一旦滿足編碼約束度的幾倍就可以開始譯碼。實(shí)驗(yàn)數(shù)據(jù)表明，無論監(jiān)督比特流對應(yīng)于消息比特有多長，5·K的消息比特時(shí)間（左右）是一個(gè)合理的譯碼窗口。

設(shè)計(jì)優(yōu)秀的卷積碼

到此，人們可能自然地會(huì)想到一個(gè)問題，“什么樣的生成多項(xiàng)式能促成一個(gè)優(yōu)秀的卷積碼？換句話說，是否有系統(tǒng)的方法來產(chǎn)生優(yōu)秀的卷積碼？或者，給定兩個(gè)卷積碼，是否有一種方法來分析它們的生成矩陣，并確定它們在接下來的過程中如何相互關(guān)聯(lián)并執(zhí)行？了解了這些，使得我們能在一個(gè)有噪聲的信道上以盡可能高的速率進(jìn)行通信。

原則上，許多因素決定了卷積碼的有效性。人們期望卷積碼糾正錯(cuò)誤的能力取決于編碼約束度K，因?yàn)榫幋a約束度越大，任何給定的消息比特對監(jiān)督位的貢獻(xiàn)程度越大，對比特錯(cuò)誤的復(fù)原能力也就越大。人們也希望隨著監(jiān)督比特?cái)?shù)量的增加，錯(cuò)誤的恢復(fù)能力會(huì)更高，因?yàn)檫@對應(yīng)于一個(gè)較低的碼率（更多的冗余）。最后同樣重要的一點(diǎn)是，生成多項(xiàng)式的系數(shù)在決定卷積碼的性能方面確實(shí)有一定的作用。

幸運(yùn)的是，有一個(gè)度量，稱為卷積碼的自由距離，它囊括了這些衡量維度，并對卷積碼的糾錯(cuò)能力起主要決定作用。

自由距離

由于卷積碼是線性的，因此所有我們所學(xué)的線性碼都適用于這里。特別是，任何線性碼的漢明距離，即任意兩個(gè)有效碼字之間的最小漢明距離，等于具有最小碼重的非零碼字中1的個(gè)數(shù)。一個(gè)碼字的碼重為其所含1的個(gè)數(shù)。

對卷積碼而言，任意兩個(gè)有效碼字之間的最小漢明距離稱為自由距離。具體而言，一個(gè)卷積碼的自由距離等于全零路徑與從狀態(tài)00重新回到狀態(tài)00的最小非零路徑之間的路徑度量之差。圖6舉例說明這一概念。

圖 6

在這個(gè)例子中，自由距離是4，它需要8個(gè)輸出位才能回到正確的狀態(tài)，所以如果數(shù)據(jù)塊從第一個(gè)監(jiān)督位開始，人們期望這個(gè)卷積碼每8bit數(shù)據(jù)塊能夠糾正(4-1)/2 = 1位錯(cuò)誤。事實(shí)上，這種糾錯(cuò)能力基本上與(8,4,3)二維奇偶監(jiān)督碼相同。

注意，這個(gè)例子中的自由距離是4，而不是5：從初始00狀態(tài)回到狀00態(tài)之間最小的非零路徑如下：00→10→11→01→00，相應(yīng)的路徑度量值變化如下：0→2→2→3→4。在下一節(jié)中，我們將發(fā)現(xiàn)生成器的一個(gè)小的改變（如以101替換110），也將大大影響卷積碼的性能。

如果是以相同方式定義的，為什么我們要重新定義一個(gè)“自由距離”，而不是也把它叫做漢明距離？原因是，漢明距離為D的任何編碼（無論是否為線性碼），都可以糾正任何(D-1)/2位形式的錯(cuò)誤。如果我們把同樣的概念應(yīng)用于卷積碼，我們將會(huì)以為我們可以糾正固定位數(shù)的錯(cuò)誤，如在上例中我們可以糾正任何單比特錯(cuò)誤。

現(xiàn)在，卷積碼產(chǎn)生無邊界的比特流，這明顯不同于分組碼。(D-1)/2不太適合于描述卷積碼真正的糾錯(cuò)性能。當(dāng)這些錯(cuò)誤離得足夠遠(yuǎn)時(shí)，卷積碼（使用Viterbi譯碼）可以糾正t = (D-1)/2位形式的錯(cuò)誤，所以我們使用的是自由距離。從某種意義上說，在一個(gè)間隔很近的突發(fā)塊中，錯(cuò)誤可以連續(xù)發(fā)生，只要沒有超過t個(gè)錯(cuò)誤出現(xiàn)，譯碼器就可以糾正它們。

選擇好的卷積碼

自由距離概念還提供了一種構(gòu)造良好卷積碼的方法。給定譯碼資源預(yù)算（如硬件資源），首先為編碼約束度K確定一個(gè)邊界，然后，根據(jù)最大速率選擇r的上限。給定一個(gè)具體的K和r，就已經(jīng)把生成多項(xiàng)式的選取方案限定在一定范圍內(nèi)了。人們可以編寫一個(gè)程序，遍歷所有可能的生成多項(xiàng)式組合，計(jì)算自由距離，并選擇最大自由距離的卷積碼。卷積碼完全通過指定生成多項(xiàng)式來產(chǎn)生（如果列出生成多項(xiàng)式，則K和r都是隱含在其中的了）。

比較編碼的糾錯(cuò)性能

這一部分討論如何比較不同編碼的糾錯(cuò)性能，并評(píng)估在不同控制條件下實(shí)現(xiàn)不同編碼的仿真結(jié)果。本節(jié)有兩個(gè)目標(biāo)：第一，從“最佳實(shí)踐意義”角度比較不同編碼器，并討論常見的陷阱；第二，比較某些特定的卷積碼和二維奇偶監(jiān)督碼，并討論某些編碼器比其它編碼器執(zhí)行得更好的原因。

有兩個(gè)衡量標(biāo)準(zhǔn)：第一是譯碼后的誤碼率（BER），有時(shí)也稱為譯碼錯(cuò)誤概率；第二個(gè)是碼率。對于這兩種度量，我們關(guān)心它們?nèi)绾坞S信道參數(shù)的變化而變化，例如BSC中的ε值（即信道的底層比特差錯(cuò)概率）或信道上的噪聲程度（對于加性高斯噪聲信道，我們將在下一章中詳細(xì)描述）。

這里，我們只關(guān)注編碼的譯碼后誤碼率。

基于BSC的譯碼誤碼率

對于BSC，變量是ε（譯者注：BSC全稱為二元對稱信道，這里BSC的ε表示譯碼前的錯(cuò)誤比特率），當(dāng)ε變化時(shí)，我們關(guān)心不同的編碼器將會(huì)如何表現(xiàn)（以BER衡量）。圖7顯示了幾個(gè)不同的線性二維奇偶監(jiān)督碼和卷積碼的譯碼誤碼率隨BSC錯(cuò)誤率ε變化的情況。

圖 7

圖中顯示，碼率為1/3的二維奇偶監(jiān)督碼在高ε時(shí)表現(xiàn)得最為穩(wěn)健，而兩個(gè)1/2碼率的卷積碼在其它誤碼率下表現(xiàn)很好。圖中同樣可以看出，(7,4)和(15,11)漢明碼要劣于其它編碼。

這些結(jié)論的問題是，他們沒有考慮到編碼的編碼效率，其中一些編碼的開銷要比其他編碼高很多。這樣，如圖7曲線所示譯碼誤碼率隨ε的變化，將具有相同碼率的編碼在一起比較才有意義。因此，可以將(8,4)二維奇偶監(jiān)督碼與其他三個(gè)卷積碼進(jìn)行比較，并得出以下結(jié)論：

1. 兩個(gè)卷積碼(3,(7,5))（生成多項(xiàng)式為(111, 101)）和(4,(14,13))（生成多項(xiàng)式為(1110, 1101)）表現(xiàn)最好，它們明顯優(yōu)于(3,(7,6))卷積碼（我們從Bussgang關(guān)于如何選取好的卷積碼的文章獲得這些碼）。(3,(7,5))和(4,(14,13))這兩個(gè)碼（自由距離分別為5和6）表現(xiàn)優(yōu)異的原因是它們具有比(3,(7,6))（自由距離為4）更大的自由距離。
2. 有趣的是，結(jié)果顯示自由距離為5的(3,(7,5))表現(xiàn)要強(qiáng)于自由距離為6的(4,(14,13))。其原因是，在(3,(7,5))下，從狀態(tài)00返回到狀態(tài)00的網(wǎng)格邊數(shù)僅為3，對應(yīng)于一組6個(gè)連續(xù)編碼比特。相關(guān)的狀態(tài)轉(zhuǎn)換是00→10→01→00，相應(yīng)的路徑度量為0→2→3→5。相比之下(4,(14,13))雖然擁有大小為6的自由距離，但它需要經(jīng)過4條網(wǎng)格邊來實(shí)現(xiàn)000→100→010→001→000的狀態(tài)轉(zhuǎn)移，意味著在長度為8的滑動(dòng)窗內(nèi)它能糾正2bit內(nèi)的錯(cuò)誤。

此外，從5到6（偶數(shù)）的自由距離的增加并不能提高編碼的糾錯(cuò)能力。

3. 對于(8,4)二維奇偶監(jiān)督碼和(3,(7,6))卷積碼，譯碼后的BER大致相同。其原因是該K＝3的卷積碼的自由距離為4，這意味著它可以在與(8,4)二維奇偶監(jiān)督碼長度相似的塊上糾正1個(gè)比特錯(cuò)誤。直觀地說，這兩個(gè)方案的監(jiān)督位利用了相同長度的歷史信息。在二維奇偶監(jiān)督碼情況下，行監(jiān)督位來自兩個(gè)連續(xù)的消息位，而列監(jiān)督位則來自間隔一位的兩個(gè)消息位，同時(shí)我們也發(fā)送消息位。所以我們用編碼約束度K＝3的卷積碼來與之比較，證明(3,(111,110))不是一個(gè)好的卷積碼。
4. (7,4)漢明碼類似于(8,4)二維奇偶監(jiān)督碼，但它具有更高的碼率（4/7對1/2），這意味著它用更低的開銷實(shí)現(xiàn)了相同的糾錯(cuò)功能。因此，可以得出結(jié)論，它是比(8,4)二維奇偶監(jiān)督碼更好的編碼。

但是，如何比較不同碼率下的譯碼誤碼率呢？我們需要一種方法來衡量不同碼率編碼的冗余量。要做到這一點(diǎn)，我們需要改變模型來解釋物理（模擬）層上發(fā)生的情況。處理這個(gè)問題的一般方法是使用信噪比（SNR）作為控制變量（X軸），發(fā)送信號(hào)通過高斯噪聲干擾的信道。下一章詳細(xì)地研究了這個(gè)噪聲模型，這里我們只描述在這個(gè)模型下比較編碼性能時(shí)所獲得的基本直覺和結(jié)果。該模型對于理解軟判決譯碼的好處也是必不可少的，因?yàn)檐涀g碼直接使用接收的電壓樣本作為譯碼器的輸入，而無需先對每個(gè)樣本進(jìn)行數(shù)字化。通過比較軟判決譯碼和硬判決譯碼，能觀察到增加了多少的增益。

高斯噪聲模型和Eb/N0的概念

考慮一組n bit長的信息。我們有兩個(gè)編碼：C1碼率為k/n1，C2碼率為k/n2，設(shè)n2＞n1。因此，對于k bit信息，當(dāng)使用C1編碼時(shí)，我們發(fā)射n1位，當(dāng)使用C2編碼時(shí)，發(fā)射n2位。顯然，使用C2消耗更多的資源，因?yàn)樗枰谛诺郎习l(fā)送更長的時(shí)間。

衡量C1資源消耗的一個(gè)簡單方式是運(yùn)行一個(gè)實(shí)驗(yàn)，將位1映射為特定電壓V1，將位0映射為特定電壓V0。由于在下章中將會(huì)講到的一個(gè)原因，與譯碼有關(guān)的是V1和V0之間的電壓差，因此我們假設(shè)這兩個(gè)電壓中值為0。為方便起見，設(shè)V1=sqrt(Es)，V0=-sqrt(Es),Es為每個(gè)樣點(diǎn)的能量。該能量（或者說功率）與所使用的電壓的平方成比例。

現(xiàn)在我們使用C1編碼，k bit消息被編碼成n1 bit。先假定每一編碼比特以一個(gè)電壓樣點(diǎn)發(fā)送（為簡化描述），則每一位的能量Eb=(n1/k)*Es。同樣對于C2編碼，每一位的能量Eb=(n2/k)*Es。在高斯噪聲信道中，每一個(gè)電壓樣點(diǎn)被干擾成具備一定方差的高斯分布，該方差即代表噪聲的大?。ǚ讲钤酱?，噪聲越大，BSC的誤碼率ε也就會(huì)越大）。因此，適合用于比較不同編碼碼率下的譯碼誤碼率的x軸變量應(yīng)為Eb/N0，它表示每個(gè)信息比特的能量與信道高斯噪聲能量之比。

圖 8

圖8展示了模擬不同具有代表性的Eb/N0值的高斯信道的性能實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)中的每一個(gè)數(shù)據(jù)點(diǎn)都是統(tǒng)計(jì)200萬個(gè)信息比特在一個(gè)噪聲信道上編碼和傳輸?shù)慕Y(jié)果。最上面的曲線顯示未編碼時(shí)的誤碼率。X軸為Eb/N0，以dB為單位。y軸顯示對數(shù)刻度上的誤碼率。從結(jié)果看，這些點(diǎn)值得注意：

1. 好的卷積碼明顯優(yōu)于漢明碼和二維奇偶監(jiān)督碼。
2. 軟判決譯碼明顯優(yōu)于硬判決譯碼。對于相同的譯碼誤碼率，軟解碼相對于硬譯碼有2至2.3 dB的增益，即硬譯碼將不得不通過增加信噪比（1.6倍左右）來實(shí)現(xiàn)與軟譯碼相同的譯碼誤碼率。

總結(jié)

從一開始作為影響力巨大的卷積碼的譯碼方法，到現(xiàn)在維特比譯碼器已經(jīng)成為工程系統(tǒng)和各領(lǐng)域中應(yīng)用最廣泛的算法之一。現(xiàn)代磁盤驅(qū)動(dòng)器通過PRML技術(shù)來加速訪問；語音識(shí)別系統(tǒng)，自然語言系統(tǒng)，以及各種通信網(wǎng)絡(luò)使用此方法或其變種。

事實(shí)上，用更現(xiàn)代的觀點(diǎn)描述，可將本課中描述的軟判決譯碼技術(shù)看作在隱馬爾科夫模型（HMM）中尋找最大似然的狀態(tài)集路徑。一些基本現(xiàn)象被建模為一個(gè)馬爾可夫狀態(tài)機(jī)，它的狀態(tài)之間有一定概率的轉(zhuǎn)換。我們觀測到被噪聲污染的各狀態(tài)，并將觀測結(jié)果拼接起來，以確定最可能的狀態(tài)轉(zhuǎn)移序列。事實(shí)證明，維特比解碼器是解決這類問題的極好起點(diǎn)（有時(shí)也是完備解）。

另一方面，盡管有著不可否認(rèn)的成功，維特比譯碼并不是解卷積碼的唯一方法。一方面，它確實(shí)需要窮舉每個(gè)狀態(tài)，因此它的計(jì)算復(fù)雜度與編碼約束度K呈指數(shù)關(guān)系。當(dāng)K很大時(shí)，可以使用其他解碼方法，例如BCJR或Fano的序貫譯碼方案。

卷積碼本身在有線和無線鏈路上非常流行。它有時(shí)被用作外部塊糾錯(cuò)碼的“內(nèi)部碼”，但也可自己作為外部糾錯(cuò)碼使用。Turbo碼是目前實(shí)踐中使用性能最高的譯碼器之一，卷積碼即可作為其內(nèi)部組件。