外文翻譯--維特比算法和軟硬判決譯碼的差錯(cuò)控制 (2)

1、<p><b>　　中文4650字</b></p><p>　　畢業(yè)設(shè)計(jì)（英文翻譯）</p><p>　　原文題目：The Viterbi Algorithm and Probability of Error for Soft and Hard-Decision Decoding </p><p>　　譯文題目：維特比算法和軟硬判決譯

2、碼的差錯(cuò)控制</p><p><b>　　二零一四年三月</b></p><p><b>　　摘 要</b></p><p>　　卷積碼可以用維特比算法作為譯碼算法，由于維特比譯碼器復(fù)雜度隨著反饋深度的增長(zhǎng)成指數(shù)倍增長(zhǎng)，因而譯碼反饋深度對(duì)譯碼器的復(fù)雜度影響很大甚至可能無法使用，目前有些文獻(xiàn)中僅給出了反饋深度的大致范圍，但在

3、硬件實(shí)現(xiàn)和性能仿真時(shí)無法確定一個(gè)具體的數(shù)值。它是一個(gè)最大似然序列估計(jì)器(MLSE)，所以，卷積碼的譯碼就是搜遍網(wǎng)格圖找出最可能的序列，搜索網(wǎng)格圖時(shí)所用的量度可以是漢明距離，也可以是歐氏距離。由于卷積碼沒有固定長(zhǎng)度，可以利用網(wǎng)格圖某給定節(jié)點(diǎn)上第一次與全零序列匯合的序列的差錯(cuò)概率推導(dǎo)其性能。把節(jié)點(diǎn)B上與全零路徑匯合的路徑的量度首次超過全零路徑量度的概率定義為首次差錯(cuò)事件概率。</p><p>　　關(guān)鍵字：卷積碼；維特

4、比譯碼；網(wǎng)格圖；差錯(cuò)概率</p><p>　　1. 卷積碼的最佳譯碼—維特比算法</p><p>　　在無記憶信道分組碼的譯碼中，我們需計(jì)算接受碼字與個(gè)可能發(fā)送碼字之間的距離(硬判決譯碼時(shí)時(shí)漢明譯碼距離，軟判決譯碼時(shí)是歐氏(Euclidean)距離)，選擇一個(gè)離接受碼字最近的碼字作為譯碼輸出。這種判決法則需要計(jì)算個(gè)距離量度(metrics)。在加性高斯白噪聲、p<1/2的二進(jìn)制對(duì)稱信

5、道中，該算法的差錯(cuò)率最小，從這個(gè)意義丄說它是最優(yōu)的。</p><p>　　不像分組碼那樣有固定的長(zhǎng)度n，卷積碼基本上是一個(gè)有限狀態(tài)機(jī)，因此它的最佳譯碼器與5.1.4節(jié)所屬的有記憶信號(hào)（如NIZI和CPM）屬同一類型，是一個(gè)最大似然序列估計(jì)器（MLSE，Maximum Likelihood Sequence Estimator）。所以，卷積碼的譯碼就是搜索網(wǎng)絡(luò)圖找出最可能的序列。根據(jù)解調(diào)器后的譯碼器執(zhí)行軟判決和硬判

6、決，搜索網(wǎng)絡(luò)圖時(shí)所用的量度可以是漢明距離，也可以是歐氏距離。下面，我們針對(duì)圖8-2-2所示卷積碼的網(wǎng)格圖{圖8-2-5}來詳細(xì)說明。</p><p>　　觀察網(wǎng)格圖中的兩條路徑，它們從初始狀態(tài)a經(jīng)過3次狀態(tài)轉(zhuǎn)移(3個(gè)分支)又回到狀態(tài)a，這兩條路徑對(duì)應(yīng)的信息序列分別是 000和 100，對(duì)應(yīng)的發(fā)送序列分別是000 000 000和111 001 011。用{, j=1, 2, 3; m=1, 2, 3}，表示發(fā)送比

7、特，其中下標(biāo)j表示第j個(gè)分支，下標(biāo)m表示該分支的第m個(gè)比特。同樣的，用{, j=1, 2, 3; m=1, 2, 3}表示解調(diào)器的輸出。如果采用硬判決譯碼，則調(diào)制器輸出的發(fā)送比特不是0就是 1.另一方面，如果用軟判決譯碼，且編碼序列二進(jìn)制相干PSK傳輸，則譯碼器的輸出為</p><p><b>　　(8.2-9)</b></p><p>　　式中表示加性噪聲，是發(fā)送每

8、個(gè)編碼比特所用的信號(hào)能量。</p><p>　　穿過網(wǎng)格圖的第i條路徑之第j分支的量度定義為在第i條路徑上發(fā)送序列為{, m=1, 2, 3}而接受序列是{, m=1, 2, 3}的聯(lián)合條件概率的對(duì)數(shù)，即</p><p>　　, j=1, 2, 3, … (8.2-10)</p><p>　　把穿過網(wǎng)格由B個(gè)分支組成的第i條

9、路徑的量度定義為</p><p><b>　　(8.2-11)</b></p><p>　　在穿過網(wǎng)格圖的兩條路徑之間進(jìn)行判決的準(zhǔn)則是選取量度較大的一條路徑。這個(gè)準(zhǔn)則使正確判決的概率最大，或等效于使信息比特序列的差錯(cuò)概率最小。比如，準(zhǔn)備執(zhí)行硬判決譯碼的解調(diào)器輸出一個(gè)接受序列{101 000 100}。令i=0代表分支組成的全零路徑；令i=1代表第二個(gè)三分支組成的路徑，

10、他從初始狀態(tài)a開始，經(jīng)過3次轉(zhuǎn)移之后和全零路徑在狀態(tài)a合并。這兩條路徑的量度分別為</p><p><b>　　(8.2-12)</b></p><p>　　式中，p是比特差錯(cuò)概率。假定p<1/2，可求的量度。這個(gè)結(jié)果和一下事實(shí)一致，即全零路徑到接受序列的漢明距離d=3，而i=1的路徑與接受路徑的漢明距離d=5。因此對(duì)硬判決譯碼來說漢明距離是一種等效的量度。&l

11、t;/p><p>　　與此類似，假設(shè)采用軟判決譯碼，切信道給信號(hào)疊加了高斯白噪聲，那么解調(diào)器的輸出從統(tǒng)計(jì)角度可以用概率密度函數(shù)表示為</p><p><b>　　(8.2-13)</b></p><p>　　式中，是加性高斯噪聲的方差。如果忽略各分支量度同等擁有的項(xiàng)，第i條路徑的第j條分支量度可以表示為</p><p>　　

12、(8.2-14) </p><p>　　此例中n=3。這兩個(gè)路徑的相對(duì)量度為</p><p><b>　　(8.2-15)</b></p><p>　　定義了由譯碼器計(jì)算的分支量度和路徑量度后，下一步研究維特比算法在卷積碼最佳譯碼上的應(yīng)用。

13、考慮上述兩條路徑，它們是經(jīng)過3次轉(zhuǎn)移后又匯合到狀態(tài)a的。注意，從這個(gè)節(jié)點(diǎn)起源的任何一條穿過網(wǎng)格圖的特定路徑，都要在其路徑量度和上加上相同的項(xiàng)。因此，如果經(jīng)過3次轉(zhuǎn)移后在匯合接點(diǎn)a處滿足>，那么對(duì)于任何起源于a節(jié)點(diǎn)的路徑，將仍然大于。這意味著從此以后可以不再考慮與對(duì)應(yīng)的路徑。與量度對(duì)應(yīng)的路徑叫做留存路徑(Survivor)。同理，根據(jù)兩個(gè)量度的大小，在b狀態(tài)匯合的兩條路徑也可以去除其中之一。對(duì)c狀態(tài)和d狀態(tài)也可以同樣重復(fù)這種步驟。結(jié)

14、果，經(jīng)過開頭3次狀態(tài)轉(zhuǎn)移之后，只剩下4條路徑，每個(gè)狀態(tài)作為其中一條的終點(diǎn)，并且每條留存路徑有相應(yīng)的量度。隨著以后每一時(shí)間間隔中新信號(hào)的接受，在網(wǎng)格圖中的每一級(jí)都重復(fù)這樣的步驟。</p><p>　　一般來說，如果用維特比算法對(duì)一個(gè)k=1且約束長(zhǎng)度為K的二進(jìn)制卷積碼譯碼，應(yīng)有個(gè)狀態(tài)。因此每級(jí)有條留存路徑，每條留存路徑有一個(gè)路徑量度，共個(gè)。更一般地，一個(gè)二進(jìn)制卷積碼若一次能讓k個(gè)信息比特輸入到由K個(gè)k比特移存器構(gòu)成的

15、編碼器，這樣卷積碼將產(chǎn)生個(gè)狀態(tài)的網(wǎng)絡(luò)圖。若想用維特比算法對(duì)這種碼進(jìn)行譯碼，要保存條留存路徑和個(gè)路徑量度。在網(wǎng)格圖每一級(jí)的每一個(gè)節(jié)點(diǎn)，有條路徑匯合于該點(diǎn)。由于匯合于同一節(jié)點(diǎn)的每一條路徑都要計(jì)算其量度，因此每個(gè)節(jié)點(diǎn)要計(jì)算個(gè)量度。在匯合于每個(gè)節(jié)點(diǎn)的條路徑中，留存路徑只有一條，它就是最可能(最小距離)的路徑。這樣，在執(zhí)行每一級(jí)的譯碼時(shí)，計(jì)算量將隨k和K呈指數(shù)增加，這就將維特比算法的應(yīng)用局限于k和K值較小的場(chǎng)合。</p><p

16、>　　在對(duì)一個(gè)卷積碼的長(zhǎng)序列進(jìn)行譯碼時(shí)，譯碼延時(shí)對(duì)大多數(shù)實(shí)際應(yīng)用場(chǎng)合來說太長(zhǎng)，用來存儲(chǔ)留存序列全部長(zhǎng)度的存儲(chǔ)器太大太貴。解決這個(gè)問題的辦法如5.1.4節(jié)所述，設(shè)法修改維特比算法，是修改后既能保持一個(gè)固定的譯碼延時(shí)，有對(duì)算法的最佳性能沒有顯著影響。修改辦法是在任意給定時(shí)間t內(nèi)保留每個(gè)留存序列中最新的個(gè)譯碼信息比特(符號(hào))。當(dāng)收到每一個(gè)新的信息比特(符號(hào))時(shí)，譯碼器對(duì)留存序列量度的大小作比較，找出具有最大量度的留存序列，再在網(wǎng)格圖(時(shí)

17、間)上回退個(gè)分支，將該留存序列上該時(shí)刻的比特判決為接受比特(符號(hào))的譯碼輸出。如果選的足夠大，在時(shí)間上回退個(gè)分支后，所有留存序列將包含相同的譯碼輸出比特(符號(hào))。這就是說，時(shí)刻t的所有留存序列極有可能是起源于時(shí)刻t-的同一節(jié)點(diǎn)。實(shí)驗(yàn)(計(jì)算機(jī)模擬法)證明，當(dāng)延時(shí)時(shí)，與最佳維特比算法性能相比其性能的下降忽略不計(jì)。</p><p>　　2. 軟判決譯碼的差錯(cuò)控制</p><p>　　本節(jié)的主題是

18、討論加性高斯白噪聲信道中使用軟判決譯碼時(shí)維特比算法的差錯(cuò)概率性能。</p><p>　　再推導(dǎo)卷積碼的差錯(cuò)概率時(shí)，利用這類編碼的線性特性可使推導(dǎo)簡(jiǎn)化，也就是假定發(fā)送的是全零序列，求誤判成另一序列的差錯(cuò)概率。假定傳輸采用的是二廂PSK(或四相PSK)，解調(diào)器使用相干檢測(cè)，所得的卷積碼第j個(gè)分支上的二進(jìn)制編碼數(shù)字如8.2.2節(jié)定義，用{, m=1, 2…,n}表示。解調(diào)器的輸出，即維特比譯碼器的輸入是序列{, m=1

19、, 2… n; j=1, 2…}，其中如式(8-2-9)定義。</p><p>　　維特比軟判決譯碼器計(jì)算的分支量度由式(8-2-14)定義，以此可計(jì)算路徑量度為</p><p><b>　　(8.2-16)</b></p><p>　　這里，i表示各節(jié)點(diǎn)的任意一條待選路徑，B是一條路徑上的分支(信息符號(hào))數(shù)。例如，全零路徑用i=0表示，具有路

20、徑量度</p><p><b>　　(8.2-17)</b></p><p>　　由于卷積碼沒有固定長(zhǎng)度，可以利用網(wǎng)格圖某給定節(jié)點(diǎn)上第一次與全零序列匯合的序列的差錯(cuò)概率推導(dǎo)其性能。把在節(jié)點(diǎn)B上與全零路徑匯合的量度首次超過全零路徑量度路徑的概率定為首次差錯(cuò)事件概率。假設(shè)和全零路徑匯合的編號(hào)為i=1的不正確路徑與全零路徑有d比特的差別，即編號(hào)i=1的路徑上有d個(gè)“1”而其

21、余為“0”。兩條路徑為一對(duì)，成對(duì)比較量度和 ，得差錯(cuò)概率</p><p><b>　　(8.2-18)</b></p><p>　　由于兩條路徑的編碼比特除了在d個(gè)位置上不同外，其他都相同，所以式(8-2-18)可以簡(jiǎn)化為</p><p><b>　　(8.2-19)</b></p><p>　　式

22、中，下表1代表兩條路徑中不同的d個(gè)比特，集合{}表示和該d比特對(duì)應(yīng)的譯碼器輸入。{}是獨(dú)立等概的高斯隨機(jī)變量，均值為，方差為。因此，兩條相差d比特的路徑成對(duì)比較時(shí)的差錯(cuò)概率為</p><p><b>　　(8.2-20)</b></p><p>　　式中，是接收端的每比特信噪比，是碼率。</p><p>　　盡管我們推出了與全零路徑為d的錯(cuò)誤路

23、徑的首次差錯(cuò)事件概率，但在給定節(jié)點(diǎn)B上可能有很多路徑以不同的距離和全零路徑匯合。實(shí)際上，轉(zhuǎn)移函數(shù)T(D)為所有以不同距離與全零路徑匯合于B節(jié)點(diǎn)的路徑提供了最完整的描述。于是可以用式(8-2-20)將所有可能距離的路徑的差錯(cuò)概率統(tǒng)統(tǒng)加起來，通過求和運(yùn)算，得到首次差錯(cuò)事件概率的上邊界為</p><p><b>　　(8.2-21)</b></p><p>　　式中，表示與

24、全零路徑首次匯合且距離為d的路徑的數(shù)目。</p><p>　　有兩個(gè)理由說明為什么式(8-2-21)是首次差錯(cuò)事件概率的上邊界。一是引起差錯(cuò)概率{}的事件不是獨(dú)立的，這可以從網(wǎng)格圖看出來。二是對(duì)所有可能的求和時(shí)，默認(rèn)卷積碼是無限長(zhǎng)的。如果卷積碼在B節(jié)點(diǎn)之后周期的截短，式(8-2-21)的上邊界可以通過求間的差錯(cuò)事件總和而得到改善。這個(gè)改善對(duì)于確定短卷積碼的性能有利，但當(dāng)B很大時(shí)，它對(duì)性能的影響可以忽略。</

25、p><p>　　如果Q函數(shù)被一個(gè)指數(shù)框出上限，即</p><p><b>　　(8.2.22)</b></p><p>　　那么式(8-2-21)的上邊界可以用略有不同的另一種形式表示。將式(8-2-22)代入式(8-2-21)，首次差錯(cuò)事件概率的上邊界可以表示為</p><p><b>　　(8.2-23)<

26、;/b></p><p>　　雖然首次差錯(cuò)事件概率提供了一種用來衡量卷積碼性能的方法，但衡量性能跟有用的辦法是比特差錯(cuò)概率。用確定首次差錯(cuò)事件概率邊界的方法同樣可確定比特差錯(cuò)概率的上邊界。一旦選擇一條差錯(cuò)路徑，其信息比特和正確路徑信息比特的差異將造成譯碼的不正確。轉(zhuǎn)移函數(shù)T(D,N)中因子N的指數(shù)代表與全零路徑匯合于某節(jié)點(diǎn)B的所選錯(cuò)誤路徑中的差錯(cuò)信息比特?cái)?shù)(即“1”的個(gè)數(shù))，如果把成對(duì)差錯(cuò)概率乘以路徑匯合處

27、由錯(cuò)誤路徑造成的譯碼信息比特的差錯(cuò)個(gè)數(shù)，可得到該差錯(cuò)路徑的比特差錯(cuò)率。若令每一對(duì)差錯(cuò)概率都乘以相應(yīng)錯(cuò)誤路徑(這些錯(cuò)誤路徑與正確路徑在節(jié)點(diǎn)B處匯合)中的譯碼信息比特的差錯(cuò)個(gè)數(shù)，并對(duì)所有d求和，可獲得平均比特差錯(cuò)概率的上邊界。</p><p>　　讓T(D，N)對(duì)N求微分，得到與每一條差錯(cuò)路徑中的信息比特差錯(cuò)個(gè)數(shù)相對(duì)應(yīng)的非常合適的乘法因子。一般的，T(D，N)可表示為</p><p><

28、b>　　(8.2-24)</b></p><p>　　式中，f(d) 表示N的指數(shù)，它是d的函數(shù)。求T(D，N)對(duì)N的導(dǎo)數(shù)并令N=1，得</p><p><b>　　(8.2-25)</b></p><p>　　式中，。于是，k=1時(shí)的比特差錯(cuò)概率上邊界為</p><p><b>　　(8.2

29、-26)</b></p><p>　　如果Q函數(shù)像式(8-2-22)那樣由一個(gè)指數(shù)框出上邊界，式(8-2-26)簡(jiǎn)化為</p><p><b>　　(8.2-27)</b></p><p>　　如果k>1，相應(yīng)的比特差錯(cuò)概率可以由式(8-2-26)和式(8-2-27)除以k求得。</p><p>　　以

30、上差錯(cuò)概率表達(dá)式是在假設(shè)編碼比特用二相相干PSK傳輸?shù)那疤嵯碌玫降?。這個(gè)結(jié)果對(duì)四相相干PSK也同樣成立，因?yàn)樗南嗾{(diào)制/解調(diào)技術(shù)等效于兩個(gè)獨(dú)立(相位正交)的二相PSK系統(tǒng)。在其他調(diào)制/解調(diào)技術(shù)，如相干和非相干二進(jìn)制FSK時(shí)也能使用，但需重新計(jì)算成對(duì)差錯(cuò)概率。也就是說，發(fā)送編碼信息序列的調(diào)制/解調(diào)技術(shù)的變化只影響的計(jì)算，的推導(dǎo)不變。</p><p>　　雖然上述卷積碼維特比譯碼時(shí)差錯(cuò)概率的推導(dǎo)是應(yīng)用與二進(jìn)制卷積碼的，

31、但很容易推廣到非二進(jìn)制卷積碼，此時(shí)，每個(gè)二進(jìn)制符號(hào)映射到不同的波形上。關(guān)鍵地，式(8-2-25)中T(D，N)導(dǎo)數(shù)展開式的系數(shù){}表示兩條距離(用符號(hào)數(shù)衡量)相隔d符號(hào)的路徑中的符號(hào)差錯(cuò)個(gè)數(shù)。用表示兩條成對(duì)比較的間隔為d符號(hào)的路徑的差錯(cuò)概率，k比特符號(hào)的符號(hào)差錯(cuò)概率的上邊界應(yīng)為</p><p>　　此符號(hào)差錯(cuò)概率可以轉(zhuǎn)換成等效的比特差錯(cuò)概率。例如，用個(gè)正交波形發(fā)送k比特符號(hào)時(shí)，等效比特差錯(cuò)概率是乘以 ，如第五章所

32、述。</p><p>　　3. 硬判決譯碼的差錯(cuò)概率</p><p>　　正如處理軟判決譯碼的那樣，從確定首次差錯(cuò)事件概率開始。假設(shè)發(fā)送的是全零路徑，并假定某節(jié)點(diǎn)B上準(zhǔn)備與全零路徑比較的路徑和全零路徑相距d。若d是奇數(shù)，那么當(dāng)接收序列的差錯(cuò)數(shù)小于時(shí)，會(huì)正確的選擇全零路徑；反之，選擇錯(cuò)誤路徑。所以，選擇錯(cuò)誤路徑的概率為</p><p><b>　　(8-2-

33、28)</b></p><p>　　式中，p是二進(jìn)制對(duì)稱信道的比特差錯(cuò)概率。若d為偶數(shù)，差錯(cuò)數(shù)超過時(shí)將選擇錯(cuò)誤路徑。如果差錯(cuò)數(shù)等于，兩條路徑的量度一樣，隨便選擇兩條路徑之一，這時(shí)有一半差錯(cuò)機(jī)會(huì)。于是，選擇差錯(cuò)路徑的總概率是</p><p><b>　　(8-2-29)</b></p><p>　　正如8.2.3節(jié)所述，在給定的節(jié)點(diǎn)上

34、有許多具有不同距離的路徑與全零路徑匯合，所以寫不出既簡(jiǎn)單又精確的表達(dá)式。但是，把該節(jié)點(diǎn)上與全零路徑匯合的所有可能路徑的成對(duì)差錯(cuò)概率加起來，可以求出首次差錯(cuò)事件概率的上邊界。于是得到聯(lián)合邊界如下</p><p><b>　　(8-2-30)</b></p><p>　　式中，表示與不同距離ius1yvc相對(duì)應(yīng)的路徑數(shù)目。這些系數(shù)正是轉(zhuǎn)移函數(shù)或 展開式中的系數(shù)。</p>

35、;<p>　　如果不用式(8-2-28)和式(8-2-29)中的表達(dá)式，可用其上邊界</p><p><b>　　(8-2-31)</b></p><p>　　該式在8.1.5節(jié)定義。利用式(8-2-30)的邊界，可以得到首次差錯(cuò)事件概率的較松的上邊界如下</p><p><b>　　(8-2-32)</b>

36、</p><p><b>　　Abstract</b></p><p>　　The decoder is largely affected by the decoder traceback, because the decoder complexity increases exponentially with the decoder traceback depth.

37、There are lots of references which are analyzed theoretically the performance caused by traceback depth, but the range is so wide that it is difficult to choose precise value. It is a maximum-likelihood sequence estimato

38、r (MLSE). Therefore, optimum decoding of a convolutional code involves a search through the trellis for the most probable sequence. D</p><p>　　Keywords: Optimum Decoding; The Viterbi Algorithm; the trellis;

39、Probability of Error</p><p>　　1. Optimum Decoding of Convolutional Codes-The Viterbi Algorithm</p><p>　　In the decoding of a block code for a memoryless channel, we computed the distances (Hammi

40、ng distance for hard-decision decoding and Euclidean distance for soft-decision decoding) between the received code word and the possible transmitted code words. Then we selected the code word that was closest in distanc

41、e to the received code word .This decision rule, which requires the computation of metrics, is optimum in the sense that it results in a minimum probability of error for the binary symmetric</p><p>　　Unlike

42、a block code which has a fixed length n , a convolutional encoder is basically a finite-state machine. Hence the optimum decoder is a maximum-likelihood sequence estimator (MLSE) of the type described in Section 5.1.4 fo

43、r signals with memory, such as NRZI and CPM. Therefore, optimum decoding of a convolutional code involves a search through the trellis for the most probable sequence. Depending on whether the detector following the demod

44、ulator performs hard or soft decisions, the correspon</p><p>　　Consider the two paths in the trellis that begin at the initial state a and remerge at state a after three state transitions (three branches), c

45、orresponding to the two information sequences 000 and 100 and the transmitted sequences 000 000 000 and 111 001 011, respectively. We denote the transmitted bits by {, j=1, 2, 3; m=1, 2, 3}, where the index j indicates t

46、he jth branch and index m the mth bit in that branch. Correspondingly, we define {, j=1, 2, 3; m=1, 2, 3} as the output of the demodulat</p><p><b>　　(8.2-9)</b></p><p>　　where repre

47、sents the additive noise and is the transmitted signal energy for each code bit.</p><p>　　A metric is defined for the jth branch of the ith path through the trellis as the logarithm of the joint probability

48、 of the sequence {, m=1, 2, 3} conditioned on the transmitted sequence {, m=1, 2, 3} for the ith path. That is, </p><p>　　, j=1, 2, 3, … (8.2-10)</p><p>　　Furthermore, a metric for

49、 the ith path consisting of B branches through the trellis is defined as </p><p><b>　　(8.2-11)</b></p><p>　　The criterion for deciding between two paths through the trellis is to sel

50、ect the one having the larger metric. This rule maximizes the probability of a correct decision or, equivalently, it minimizes the probability of error for the sequence of information bits. For example, suppose that hard

51、-decision decoding is performed by the demodulator, yielding the received sequence {101 000 100}. Let i=0 denote the three-branch all-zero path and i=1 the second three-branch path that begins in the initia</p>&l

52、t;p><b>　　(8.2-12)</b></p><p>　　where p is the probability of a bit error. Assuming that p<1/2, we find that the metric. This result is consistent with the observation that the all-zero path

53、 is at Hamming distance d=3 from the received sequence, while the i=1 path is at Hamming distance d=5 from the received path .Thus the Hamming distance is an equivalent metric for hard-decision decoding.</p><p

54、>　　Similarly, suppose that soft-decision decoding is employed and the channel adds white Gaussian noise to the signal. Then the demodulator output is described statistically by the probability density function</p&g

55、t;<p><b>　　(8.2-13)</b></p><p>　　where is the variance of the additive Gaussian noise. If we neglect the terms that are common to all branch metrics, the branch metric for the jth branch

56、of the ith path may be expressed as </p><p><b>　　(8.2-14)</b></p><p>　　where, in our example, n=3. Thus the correlation metrics for the two paths under consideration are</p>&

57、lt;p><b>　　(8.2-15)</b></p><p>　　Having defined the branch metrics and path metrics computed by the decoder, we now consider the use of the Viterbi algorithm for optimum decoding of the convolu

58、tionally encoded information sequence. We consider the two paths described above, which merge at state a after three transitions. Note that any particular path through path through the trellis that stems from this node w

59、ill add identical terms to the path metrics and. Consequently, if > at the merged node a after three transition, will </p><p>　　In general, when a binary convolutional code with k=1 and constraint lengt

60、h K is decoded by means of the Viterbi algorithm, there are states. Hence, there are surviving paths at each state and metrics, one for each surviving path. Furthermore, a binary convolutional code in which k bits at

61、a time are shifted into an encoder that consists of K (k-bit) shift-register stages generates a trellis that has states. Consequently, the decoding of such a code by means of the Viterbi algorithm requires</p>&l

62、t;p>　　The decoding delay in decoding a long information sequence that has been convolutionally encoded is usually too long for most practical applications. Moreover, the memory required to store the entire length of s

63、urviving sequences is large and expensive. As indicated in Section 5.1.4 a solution to this problem is to modify the Viterbi algorithm in a way which results in a fixed decoding delay without significantly affecting the

64、optimal performance of the algorithm. Recall that the modification is</p><p>　　2. Probability of Error. For Soft-Decision Decoding</p><p>　　The topic of this subsection is the error rate perform

65、ance of the Viterbi algorithm on an additive white Gaussian noise channel with soft-decision decoding.</p><p>　　In deriving the probability of error for convolutional codes, the linearity property for this c

66、lass of codes is employed to simplify the derivation. That is, we assume that the all-zero sequence is transmitted and we determine the probability of error in deciding in favor of anther sequence. The coded binary digi

67、ts foe the jth branch of the convolutional code, denoted as {, m=1, 2…,n} and defined in Section 8.2.2 are assume to be transmitted by binary PSK (or four-phase PSK) and demodulated coh</p><p>　　The Viterbi

68、soft-decision decoder forms the branch metrics defined by Equation 8.2-14 and form these computes the path metrics</p><p><b>　　(8.2-16)</b></p><p>　　where i denotes any one of the co

69、mpeting paths at each node and B is the number of branches (information symbol) in a path. For example, the all-zero path denoted as i=0, has a path metric</p><p><b>　　(8.2-17)</b></p><

70、;p>　　Since the convolutional code does not necessarily have a fixed length, we derive its performance from the probability of error for sequences that merge with all-zero sequence foe the first time at a given node in

71、 the trellis. In particular, we define the first-event error probability as the probability that another path that merges with the all-zero path at node B has s metric that exceeds the metric of the all-zero path for the

72、 first time. Suppose the incorrect path, call it i=1, that merges wi</p><p><b>　　(8.2-18)</b></p><p>　　Since the coded bits in the two paths are identical expect in the d position. E

73、quation 8.2-18 can be written in the simpler form</p><p><b>　　(8.2-19)</b></p><p>　　where the index l runs over the set of d bits in which the two paths differ and the set {} represe

74、nts the input to the decoder for these d bits.</p><p>　　The {} are independent and identically distributed Gaussian random variables with mean and variance. Consequently the probability of error in the pairw

75、ise comparison of these two paths that differ in d bits is where the received SNR per bit is and is the code rate.</p><p><b>　　(8.2-20)</b></p><p>　　Although we have derived the fir

76、st-event error probability for a path of distance d from the all-zero path, there are many possible paths with different distances that merge with the all-zero path, at a given node B. In fact, the transfer function T(D)

77、 provides a complete description of all the possible paths that merge with the all-zero path at node B and their distances. Thus we can sum the error probability in Equation 8.2-20 over all possible path distances. Upon

78、performing this summation, w</p><p><b>　　(8.2-21)</b></p><p>　　where denotes the number of paths of distance d from the all-zero path that merge with the all-zero path for the first

79、 time.</p><p>　　There are two reasons why Equation 8.2-21 is an upper bound on the first-event error probability. One is that the events that result in the error probabilities {} are not disjoint. This can b

80、e seen from observation of the trellis. Second, by summing over all possible, we have implicitly assumed that the convolutional code has infinite length. If the code is truncated periodically after B nodes, the upper bou

81、nd in Equation 8.2-21 can be improved by summing the error events for. This refinement ha</p><p>　　The upper bound in Equation 8.2-21 can be expressed in a slightly different form if the Q function is upper-

82、bounded by an exponential. That is，</p><p><b>　　(8.2.22)</b></p><p>　　If we use Equation 8.2.22 in Equation 8.2.21, the upper bound on the first-event error probability can be expres

83、sed as </p><p><b>　　(8.2-23)</b></p><p>　　Although the first-event error probability provides a measure of the performance of a convolutional code, a more useful measure of performan

84、ce is the bit in bounding the first-event error probability. Specifically, we know that when an incorrect path is selected, the information bits in which the selected path differs from the correct path will be decoded in

85、correctly. We also know that the exponents in the factor N contained in the transfer T (D, N) indicate the number of information bit errors </p><p>　　The appropriate multiplication factors corresponding to t

86、he number of information bit errors for each incorrectly selected path may be obtained by differentiating T (D, N) with respect to N. In general, T (D, N) can be expressed as</p><p><b>　　(8.2-24)</b

87、></p><p>　　where f(d) denotes the exponent of N as a function of d. Taking the derivative of T (D, N) with respect to N and setting N=1, we obtain</p><p><b>　　(8.2-25) </b></p&

88、gt;<p>　　where . Thus the bit error probability for k=1 is upper-bounded by</p><p><b>　　(8.2-26)</b></p><p>　　If the Q function is upper-bounded by an exponential as indicated

89、 in Equation 8.2-22, then Equation 8.2-26 can be expressed in the simple form </p><p><b>　　(8.2-27)</b></p><p>　　If k>1, the equivalent bit error probability is obtained by diving

90、 Equations 8.2-26 and 8.2-27 by k.</p><p>　　The expressions for the probability of error given above are based on the assumption that the code bits are transmitted by binary coherent PSK. The results also ho

91、ld for four-phase coherent PSK, since this modulation/demodulation technique is equivalent to two independent (phase-quadrature) binary PSK systems. Other modulation and demodulation techniques, such as coherent and no c

92、oherent binary FSK, can be accommodated by recomputing the pairwise error probability. That is, a change in the modul</p><p>　　Although the above derivation of the error probability for Viterbi decoding of a

93、 convolutional code applies to binary convolutional codes, it is relatively easy to generalize it to nonbinary convolutional codes in which each nonbinary symbol is mapped into a distinct waveform. In particular, the coe

94、fficients {} in the expansion of the derivative of T (D, N), given in Equation 8.2-25, represent the number of symbol errors in two paths separated in distance (measured in terms of symbols) by d symb</p><p>

95、;　　The symbol error probability can be converted into an equivalent bit error probability. For example, if orthogonal waveforms are used to transmit the k-bit symbol, the equivalent bit error probability is multiplied b

96、y a factor, as shown in Chapter 5.</p><p>　　3. Probability of Error for Hard-Decision Decoding</p><p>　　As in our treatment of soft-decision decoding, we begin by determining the first-event err

97、or probability. The all-zero path is assumed to be transmitted. Suppose that the path being compared with the all-zero path at some node B has distance d from the all-zero path. If d is odd, the all-zero path will be cor

98、rectly selected if the number of errors in the received sequence is less than; otherwise, the incorrect path will be selected. Consequently, the probability of selecting the incorrect path i</p><p><b>

99、　　(8.2-28)</b></p><p>　　where p is the probability of a bit error for the binary symmetric channel. If d is even, the incorrect path is selected when the number of errors exceeds. If the number of erro

100、rs equals , there is a tie between the metrics in the two paths, which may be resolved by randomly selecting one of the paths; thus, an error occurs half the time. Consequently, the probability of selecting the incorrect

101、 path is </p><p><b>　　(8.2-29)</b></p><p>　　As indicated in Section 8.2.3, there are many possible paths with different distances that merge with the all-zero path at a given node. T

102、herefore, there is no simple exact expression foe the first-event error probability. However, we can over bound this error probability by the sum of the pairwise error probabilities over all possible paths that merge wit

103、h the all-zero path at the given node. Thus, we obtain the union bound</p><p><b>　　(8.2-30)</b></p><p>　　where the coefficients represent the number of paths corresponding to the se

104、t of distances . These coefficients are the coefficients in the expansion of the transfer function or .</p><p>　　Instead of using the expressions for given in Equations 8.2-28 and 8.2-29, we use the Chernof