1、本科生畢業(yè)論文設計題目:MATLAB；現(xiàn)卷積碼編譯碼專業(yè)代碼：學號：單位：指導教師：1. 年月日目錄前言3糾錯碼根本理論41.1糾錯碼根本理論41.1.1糾錯碼概念41.1.2根本原理和性能參數(shù)52. 1.2幾種常用的糾錯碼9卷積碼的根本理論112.1卷積碼介紹112.1.1卷積碼的過失控制原理112.2卷積碼編碼原理132.2.1卷積碼解析表示法132.2.2卷積碼圖形表小法143. 2.3卷積碼譯碼原理172.3.1卷積碼三種譯碼方式17VITERBI譯碼原理19卷積碼編譯碼與MATLAB真213.1.1 3.1MxtlabM述21MAtlab的特點21MAtlab和具箱和容223.2卷積

2、碼編碼與仿真223.2.1編碼程序233.3信道傳輸過程仿真244. 3.4維特比譯碼程序與仿真253.4.1維特比譯碼算法解析26VTERBI譯碼程序28VITERBI譯碼matlaiM313.4.4信噪比對卷積碼譯碼性能的影響313.4.5碼率對卷積碼譯碼性能的影響333.4.6約束長度對卷積碼誤碼性能的影響343.4.7回溯長度對卷積碼誤碼性能的影響353.4.8判決方式對卷積碼誤碼性能的影響35結(jié)論與展望374.1結(jié)論374.2展望38完畢語38參考文獻39致40附錄41摘要在數(shù)字通信系統(tǒng)中，通常采用過失控制編碼來提高系統(tǒng)的可靠性。自P.Elias首次提出卷積碼編碼以來，這一編碼技術(shù)至

3、今仍顯示出強大的生命力。目前，卷積碼已廣泛應用在無線通信標準中，如GSMCDMA2000日IS-95等無線通信標準中。本文簡單介紹了糾錯碼的根本原理，論述了卷積碼編譯碼原理和算法，并通過matlab仿真對卷積碼性能進展研究，重點比擬分析了不同碼率、不同約束長度、不同回溯長度以與不同譯碼判決方式對Viterbi譯碼性能的影響，并得出相關(guān)結(jié)論。關(guān)鍵詞：卷積碼,Viterbi,Matlab,誤碼率，數(shù)字通信系統(tǒng)AbstractIndigitalcommunicationsystems,errorcontrolcodingisusuallyusedtoimprovesystemreliability.

4、SinceP.Eliasputforwardtheconvolutionalcodingthefirsttime,thecodingisstillshowingstrongvitality.,hasbecomewidelyusedinsatellitecommunications,wirelesscommunicationsandmanyothercommunicationsystemsasakindofchannelcodingmethod.suchasGSM,CDMA2000andhasbeenawirelesscommunicationstandardsofIS-95.Thisartic

5、leintroducesthebasicprinciplesoferror-correctingcodes,mainlyreasearchtheprincipleoftheconvolutionalcodeencodinganddecodingandthealgorithms.Throughthematlabsimulation,westudytheperformanceofconvolutionalcode,especillytheperformanceoftheviterbidecodingwithdifferentbitrates,differentConstraintlength,di

6、fferenttracebackdeptheanddifferentdecisiontypes,compareandmakeconclusions.Keywords:convolutionalcodes,Viterbi,Matlab,biterrorrate,thedigitalcommunicationsystemMATLAB現(xiàn)卷積碼編譯碼刖曰信道編碼是數(shù)字通信系統(tǒng)的重要組成局部，隨著通信技術(shù)的不斷開展，信道編碼技術(shù)也在不斷地開展。在通信系統(tǒng)中，信道傳輸特性不理想以與噪聲的存在，會導致接收端出現(xiàn)接收信號的錯誤，因此用丁信道糾錯的信道編碼是數(shù)字通信系統(tǒng)中極為重要的一個環(huán)節(jié)。二十世紀40年代香農(nóng)

7、定理的出現(xiàn)為人們指出了糾錯碼的研究方向。根據(jù)香農(nóng)的有噪信道編碼定理，可以推導出一個碼率為R的編碼通信系統(tǒng)達到無誤碼傳輸狀態(tài)所必須的最小信噪比的理論極限。這個理論極限通常稱為香農(nóng)限，它說明對一個碼率為R的編碼通信系統(tǒng)，只有當SNR®過這個極限值時才能獲得無誤碼傳輸。只要SNR高丁這個極限值，香農(nóng)的編碼定理保證了能夠獲得無誤碼傳輸?shù)目赡芟喈攺碗s編碼通信系統(tǒng)的存在性。另外，香農(nóng)證明了在采用無限長的隨機編碼時，數(shù)據(jù)可以以接近信道容量的速率幾乎無誤碼的傳輸，從而為信道編碼的研究奠定了根底。本文主要介紹了信道編碼的根本理論，著重研究了卷積碼的編碼方法和viterbi譯碼，介紹了MATLAB勺使用

8、方法，并編寫卷積碼的編碼和解碼程序，通過MATLA朋真軟件對卷積碼編解碼進展仿真。重點對viterbi譯碼進展了研究，該算法就是利用卷積碼編碼器的格圖來計算路徑度量，選擇從起始時刻到終止時刻的惟一幸存路徑作為最大似然路徑，沿著最大似然路徑回溯到開始時刻，所走過的路徑對應的編碼輸出就是最大似然譯碼輸出序列。它是一種最大似然譯碼方法，當編碼約束長度不大、或者誤碼率要求不是很高的情況下，Viterbi譯碼器設備比擬簡單，計算速度快，因而Viterbi譯碼器被廣泛應用丁各種領域。1.糾錯碼根本理論1.1糾錯碼根本理論1.1.1糾錯碼概念糾錯碼(errorcorrectingcode),在傳輸過程中發(fā)生

9、錯誤后能在收端自行發(fā)現(xiàn)或糾正的碼。僅用來發(fā)現(xiàn)錯誤的碼一般常稱為檢錯碼。為使一種碼具有檢錯或糾錯能力，須對原碼字增加多余的碼元，以擴大碼字之間的差異，即把原碼字按某種規(guī)那么變成有一定剩余度見信源編碼的碼字，并使每個碼字的碼之間有一定的關(guān)系。關(guān)系的建立稱為編碼。碼字到達收端后，可以根據(jù)編碼規(guī)那么是否滿足以判定有無錯誤。當不能滿足時，按一定規(guī)那么確定錯誤所在位置并予以糾正。糾錯并恢復原碼字的過程稱為譯碼。檢錯碼與其他手段結(jié)合使用，可以糾錯。1.1.2根本原理和性能參數(shù)糾錯碼編碼的根本思想是在被傳輸?shù)男畔⒋a元中附加一些監(jiān)視碼元，并且使它們之間確定某一種關(guān)系，根據(jù)傳輸過程中這種關(guān)系是否被破壞來發(fā)現(xiàn)或糾正

10、錯誤。可見這種過失控制能力是用增加信息量的冗余度來換取的。設編碼后的碼組長度、碼組中所含信息碼元以與監(jiān)視碼元的個數(shù)分別為n、k和r,三者問滿足n=k+r，定義編碼效率為R=k/n=1-r/n?？梢姶a組長度一定時，所參加的監(jiān)視碼元個數(shù)越多，編碼效率越低。香農(nóng)的信道編碼定理指出：對丁一個給定的有擾信道，假設信道容量為C,只要發(fā)送端以低丁甜勺速率R發(fā)送信息，其中R為編碼器的輸入二進制碼元速率，那么一定存在一種編碼方法，使編碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值。可以表示為PenE(r)(1-1)其中E(R)稱為誤差指數(shù)，它與街日C的關(guān)系如圖1-1所示。由定理有如下結(jié)論：.在碼長與發(fā)送信

11、息速率一定的情況下，為減小P可以增大信道容量。由圖2-1可知，E(R)隨信道容量的增加而增大。由式(1-1)可知，錯誤概率隨E(R)的增大而指數(shù)下降。(1) .在信道容量與發(fā)送信息速率一定的條件下，增加碼長，可以使錯誤概率指數(shù)下降。對丁實際應用來說，此時的設備復雜性和譯碼延時也隨之增加。香農(nóng)的信道編碼定理為信道編碼奠定了理論根底，雖然定理本身并沒有給出具體的過失控制編碼方法和糾錯碼的結(jié)構(gòu)，但它從理論上為信道編碼的開展指出了努力方向。我們用3位二進制碼組來說明檢錯糾錯的根本原理。3位二進制碼元共有8種可能的組合：000、001、010、011、100、101、110、111。如果這8種碼組都可傳

12、遞消息，假設在傳輸過程中發(fā)生一個誤碼，那么一種碼組會錯誤地變成另一種碼組。由丁每一種碼組都可能出現(xiàn)，沒有多余的信息量，因此接收端不可能發(fā)現(xiàn)錯誤，認為發(fā)送的就是另一種碼組。如果選其中000、011、101、110來傳送消息，這相當丁只傳遞00、01、10、11四種信息，而第3位是附加的。這位附加的監(jiān)視碼元與前面兩位碼元一起，保證碼組中“1"碼的個數(shù)為偶數(shù)。這4種碼組稱為許用碼組。另外4種碼組不滿足這種校驗關(guān)系，稱為禁用碼組，它們在編碼后的發(fā)送碼元中不會出現(xiàn)。接收時一旦發(fā)現(xiàn)有禁用碼組，就說明傳輸過程中發(fā)生了錯誤。用這種簡單的校驗關(guān)系可以發(fā)現(xiàn)1個或3個錯誤，但不能糾正錯誤。因為當接收到的碼

13、組為禁用碼組時，比如為010,無法判斷發(fā)送的是哪個碼組。雖然原發(fā)送碼組為101的可能性很小(因為3個誤碼的概率一般很小)，但不能絕對排除，即使傳輸過程中只發(fā)生一個誤碼，也有三種可能的發(fā)送碼組即000、011和110。假設我們進一步將許用碼組限制為二種即000和111,顯然這樣可以發(fā)現(xiàn)所有2位以下的誤碼，假設用來糾錯，可以用最大似然準那么糾正1位錯誤?？梢杂靡粋€三維立方體來表示上述3位二進制碼組的例子，如圖1-2所示。圖中立方體各頂點分別表示8位碼組，3位碼元依次表示x、v、z軸的坐標。(0,0,1)圖1-2碼距的幾何解釋這里定義碼組中非零碼元的數(shù)目為碼組的重量，簡稱碼重。比如100碼組的碼重為

14、1,101碼組的碼重為2。定義兩個碼組中對應碼位上具有不同二進制碼元的位數(shù)為兩碼組的距離，稱為漢明(Hamming)距，簡稱碼距。在前面3位二進制碼組的例子中，當8種碼組均為許用碼組時，兩碼組問的最小距離為1,稱這種編碼的最小碼距為1,一般記為dmin=l；當選4種碼組為許用碼組時，最小碼距dmin=2；當用2種碼組作為許用碼組時，dmin=3。從圖1-2所示的立方體可以看出，碼距就是從一個頂點沿立方體各邊移到另一個頂點所經(jīng)過的最少邊數(shù)。圖中粗線表示000與111之間的一條最短路徑。很容易得出前例中各種情況下的碼距。根據(jù)以上分析可知，編碼的最小碼距直接關(guān)系到這種碼的檢錯和糾錯能力，所以最小碼距

15、是過失控制編碼的一個重要參數(shù)。對丁分組碼一般有以下結(jié)論：在一個碼組檢測e個誤碼，要求最小碼距dmine1(1-2)在一個碼組糾正t個誤碼，要求最小碼距dmin2t1(1-3)在一個碼組糾正t個誤碼，同時檢測e(et)個誤碼，要求最小碼距dminte1(1-4)這些結(jié)論可以用圖1-3所示的幾何圖形簡單的給予證明。圖1-3碼距與檢錯和糾錯能力的關(guān)系圖1-3(a)中C表示某碼組，當誤碼不超過e個時，該碼組的位置移動將不超出以它為圓心以e為半徑的圓。只要其它任何許用碼組都不落入此圓，那么以生e個誤碼時就不可能與其它許用碼組混淆。這意味著其它許用碼組必須位丁以C為圓心，以e+1為半徑的圓上或圓外。因此該

16、碼的最小碼距cU為e+1o圖1-3(b)中G、G分別表示任意兩個許用碼組，當各自誤碼不超過t個時，發(fā)生誤碼后兩碼組的位置移動將各自不超出以C、G為圓心，t為半徑的圓。只要這兩個圓不相交，當誤碼小丁t個時，根據(jù)它們落在哪個圓可以正確地判斷為G或G,就是說可以糾正錯誤。以C1、G為圓心的兩圓不相交的最近圓心距離為2t+l,即為糾正t個誤碼的最小碼距。式(1-1)所述情形中糾正t個誤碼同時檢測e個誤碼，是指當誤碼不超過t個時，能自動糾正誤碼，而當誤碼超過t個時，那么不可能糾正錯誤但仍可檢測e個誤碼。圖1-3(c)中G、G分別為兩個許用碼組，在最壞情況下G發(fā)生e個誤碼而C2發(fā)生t個誤碼，為了保證此時兩

17、碼組仍不發(fā)生混淆，那么要求以G為圓心e為半徑的圓必須與以G為圓心t為半徑的圓不發(fā)生交疊，即要求最小碼距dM=t+e+1?？梢奷min表達了碼組的糾、檢錯能力。碼組問最小距離越大，說明碼字問最小差異越大，抗干擾能力就越強。由丁編碼系統(tǒng)具有糾錯能力，因此在達到同樣誤碼率要求時，編碼系統(tǒng)會使所要求的輸入信噪比低丁非編碼系統(tǒng)，為此引入了編碼增益的概念。其定義為，在給定誤碼率下，非編碼系統(tǒng)與編碼系統(tǒng)之間所需信噪比Eb/N0之差(用dB表小)o米用不同的編碼會得到不同的編碼增益，但編碼增益的提高要以增加系統(tǒng)帶寬或復雜度來換取。(2.1.3)糾錯碼實現(xiàn)糾錯碼實現(xiàn)中最復雜的局部是譯碼。它是糾錯碼能否應用的關(guān)鍵

18、。根據(jù)式(1),采用的碼長n越大,那么誤碼率越小。但n越大，編譯碼設備也越復雜，且延遲也越大。人們希望找到的譯碼方法是：誤碼率隨碼長n的增加按指數(shù)規(guī)律下降；譯碼的復雜程度隨碼長n的增加接近線性地增加；譯碼的計算量那么與碼長n根本無關(guān)?？上?，已經(jīng)找到的碼能滿足這樣要求的很少。不過由丁大規(guī)模集成電路的開展，既使應用比擬復雜的但性能良好的碼，本錢也并不太高。因此，糾錯碼的應用越來越廣泛。糾錯碼傳輸?shù)亩际菙?shù)字信號。這既可用硬件實現(xiàn)，也可用軟件實現(xiàn)。前者主要用各種數(shù)字電路，主要是采用大規(guī)模集成電路。軟件實現(xiàn)特別適合計算機通信網(wǎng)等場合。因為這時可以直接利用網(wǎng)中的計算機進展編碼和譯碼，不需要另加專用設備。硬

19、件實現(xiàn)的速度較高，比軟件可快幾個數(shù)量級。在傳信率一定的情況下，如果采用糾錯碼提高可靠性，要求信道的傳輸率增加，帶寬加大。因此，糾錯碼主要用丁功率受限制而帶寬較大的信道，如衛(wèi)星、散射等系統(tǒng)中。糾錯碼還用在一些可靠性要求較高，但設備或器件的可靠性較差，而余量較大的場合，如磁帶、磁盤和半導體存儲器等。在分組碼的研究中，譜分析的方法受到人們的重視。糾同步錯誤碼、算術(shù)碼、不對稱碼、不等錯誤糾正碼等，也得到較多的研究.1.2幾種常用的糾錯碼(1) RS編碼RS碼即里德-所羅門碼，它是能夠糾正多個錯誤的糾錯碼，RS碼為204,188,t=8，其中t是可抗長度字節(jié)數(shù)，對應的188符號，監(jiān)視段為16字節(jié)(開銷字

20、節(jié)段。實際中實施255,239,t=8的RS編碼，即在204字節(jié)包括同步字節(jié)前添加51個全“0”字節(jié)，產(chǎn)生RS碼后丟棄前面51個空字節(jié)，形成截短的204,188RS碼。RS的編碼效率是：188/204。(2) 卷積碼卷積碼非常適用丁糾正隨機錯誤，但是，解碼算法本身的特性卻是：如果在解碼過程中發(fā)生錯誤，解碼器可能會導致突發(fā)性錯誤。為此在卷積碼的上部采用RS碼塊，RS碼適用丁檢測和校正那些由解碼器產(chǎn)生的突發(fā)性錯誤。所以卷積碼和RS碼結(jié)合在一起可以起到相互補償?shù)淖饔?。卷積碼分為兩種： 根本卷積碼:根本卷積碼編碼效率為，T=1/2,編碼效率較低，優(yōu)點是糾錯能力強。 收縮卷積碼:如果傳輸信道質(zhì)量較好，為

21、提高編碼效率，可以采樣收縮截短卷積碼。有編碼效率為：T=1/2、2/3、3/4、5/6、7/8這幾種編碼效率的收縮卷積碼。編碼效率高，一定帶寬可傳輸?shù)挠行П忍芈试龃螅m錯能力越減弱。(3) Turbo碼1993年誕生的Turbo碼，單片Turbo碼的編碼/解碼器，運行速率達40Mb/s。該芯片集成了一個32X32交織器，其性能和傳統(tǒng)的RS外碼和卷積碼的級聯(lián)一樣好。所以Turbo碼是一種先進的信道編碼技術(shù)，由丁其不需要進展兩次編碼，所以其編碼效率比傳統(tǒng)的RS-e積碼要好。交織在實際應用中，比特過失經(jīng)常成申發(fā)生，這是由丁持續(xù)時間較長的衰落谷點會影響到幾個連續(xù)的比特，而信道編碼僅在檢測和校正單個過

22、失和不太長的過失申時才最有效如RS只能糾正8個字節(jié)的錯誤。為了糾正這些成申發(fā)生的比特過失與一些突發(fā)錯誤，可以運用交織技術(shù)來分散這些誤差，使長申的比特過失變成短申過失，從而可以用前向碼對其糾錯，例如：在DVB-C系統(tǒng)中,RS(204,188)的糾錯能力是8個字節(jié)，交織深度為12,那么糾可抗長度為8X12=96個字節(jié)的突發(fā)錯誤。實現(xiàn)交織和解交織一般使用卷積方式。交織技術(shù)對已編碼的信號按一定規(guī)那么重新排列，解交織后突發(fā)性錯誤在時間上被分散，使其類似丁獨立發(fā)生的隨機錯誤，從而前向糾錯編碼可以有效的進展糾錯，前向糾錯碼加交積的作用可以理解為擴展了前向糾錯的可抗長度字節(jié)。糾錯能力強的編碼一般要求的交織深度

23、相對較低。糾錯能力弱的那么要求更深的交織深度。一般來說，對數(shù)據(jù)進展傳輸時，在發(fā)端先對數(shù)據(jù)進展FEC編碼，然后再進展交積處理。在收端次序和發(fā)端相反，先做去交積處理完成誤差分散，再FEC解碼實現(xiàn)數(shù)據(jù)糾錯。交積不會增加信道的數(shù)據(jù)碼元。(5)偽隨機序列擾碼進展基帶信號傳輸?shù)娜秉c是其頻譜會因數(shù)據(jù)出現(xiàn)連“1”和連“0”而包含大的低頻成分，不適應信道的傳輸特性，也不利丁從中提取出時鐘信息。解決方法之一是采用擾碼技術(shù)，使信號受到隨機化處理，變?yōu)閭坞S機序列，乂稱為“數(shù)據(jù)隨機化'和“能量擴散"處理。擾碼不但能改善位定時的恢復質(zhì)量，還可以使信號頻譜平滑，使幀同步和自適應同步和自適應時域均衡等系統(tǒng)的

24、性能得到改善。擾碼雖然“擾亂”了原有數(shù)據(jù)的本來規(guī)律，但因為是人為的“擾亂"，在接收端很容易去加擾，恢復成原數(shù)據(jù)流。實現(xiàn)加擾和解碼，需要產(chǎn)生偽隨機二進制序列PRBS再與輸入數(shù)據(jù)逐個比特作運算。PRBS&稱為m序列，這種m序列與TS的數(shù)據(jù)碼流進展模2加運算后,數(shù)據(jù)流中的“1”和“0”的連續(xù)游程都很短，且出現(xiàn)的概率根本一樣。利用偽隨機序列進展擾碼也是實現(xiàn)數(shù)字信號高性傳輸?shù)闹匾侄沃?。一般將信源產(chǎn)生的二進制數(shù)字信息和一個周期很長的偽隨即序列模2相加，就可將原信息變成不可理解的另一序列。這種信號在信道中傳輸自然具有高度性。在接收端將接收信號再加上模2和同樣的偽隨機序列，就恢復為原來發(fā)

25、送的信息。2.卷積碼的根本理論2.1卷積碼介紹卷積碼最早丁1955年由Elias提出，稍后，1957年Wozencraft提出了一種有效地譯碼方法即序列譯碼。1963年Massey提出了一種性能稍差但是比擬實用的門限譯碼方法，使得卷積碼開始走向?qū)嵱没?。而?967年Viterbi提出了最大似然譯碼算法，它對存儲級數(shù)較小的卷積碼很容易實現(xiàn)，被稱作Viterbi譯碼算法，廣泛的應用丁現(xiàn)代通信中。2.1.1卷積碼的過失控制原理卷積碼是一種性能優(yōu)越的信道編碼，它的編碼器和解碼器都比擬易丁實現(xiàn)，同時還具有較強的糾錯能力，這使得它的使用越來越廣泛。我們在一些資料上可以找到關(guān)丁分組碼的一些介紹，分組碼的實現(xiàn)

26、是將編碼信息分組單獨進展編碼，因此無論是在編碼還是譯碼的過程中不同碼組之間的碼元無關(guān)。卷積碼和分組碼的根本區(qū)別在丁，它不是把信息序列分組后再進展單獨編碼，而是由連續(xù)輸入的信息序列得到連續(xù)輸出的已編碼序列。即進展分組編碼時，其本組中的n-k個校驗元僅與本組的k個信息元有關(guān)，而與其它各組信息無關(guān)；但在卷積碼中，其編碼器將k個信息碼元編為n個碼元時，這n個碼元不僅與當前段的k個信息有關(guān)，而且與前面的N1段信息有關(guān)N為編碼的約束長度。同樣，在卷積碼譯碼過程中，不僅從此時刻收到的碼組中提取譯碼信息，而且還要利用以前或以后各時刻收到的碼組中提取有關(guān)信息。而且卷積碼的糾錯能力隨約束長度的增加而增強，過失率那

27、么隨著約束長度增加而呈指數(shù)下降。卷積碼(n,k,N)主要用來糾隨機錯誤，它的碼元與前后碼元有一定的約束關(guān)系，編碼復雜度可用編碼約束長度N*n來表示。一般地，最小距離d說明了卷積碼在連續(xù)N段以的距離特性，該碼可以在N個連續(xù)碼流糾正(d-1)/2個錯誤。卷積碼的糾錯能力不僅與約束長度有關(guān)，還與采用的譯碼方式有關(guān)?？傊啥,k較小，且利用了各組之間的相關(guān)性，在同樣的碼率和設備的復雜性條件下，無論理論上還是實踐上都證明：卷積碼的性能至少不比分組碼差。以二元碼為例，輸入信息序列為u=(u0,u1,)，其多項式表示為u(x)=u0+u1x+ulxl+。編碼器的連接可用多項式表示為g(1,1)(x)=1

28、+x+x2和g(1,2)(x)=1+x2,稱為碼的子生成多項式。它們的系數(shù)欠量g(1,1)=(111)和g(1,2)=(101)稱作碼的子生成元。以子生成多項式為陣元構(gòu)成的多項式矩陣G(x)=g(1,1)(x),g(1,2)(x),稱為碼的生成多項式矩陣。由生成元構(gòu)成的半無限矩陣稱為碼的生成矩陣。其中(11,10,11)是由g(1,1)和g(1,2)交義連接構(gòu)成。編碼器輸出序歹0為c=u-G稱為碼序歹0,其多項式表示為c(x),它可看作是兩個子碼序列c(1)(x)和c(2)(x)經(jīng)過合路開關(guān)S合成的，其中c(1)(x)=u(x)g(1,1)(x)和c(x)=u(x)g(1,2)(x),它們分別

29、是信息序列和相應子生成元的卷積，卷積碼由此得名。在一般情況下，輸入信息序列經(jīng)過一個時分開關(guān)被分成k0個子序列，分別以u(x)表示，其中i=1,2,-k0,即u(x)=u(x),-,u(x)。編碼器的結(jié)構(gòu)由k0xn0階生成多項式矩陣給定。輸出碼序列由n0個子序列組成，即c(x)=c(x),c(x)，c(x)，且c(x)=u(x)-G(x)。假設m是所有子生成多項式g(x)中最高次式的次數(shù)，稱這種碼為(n0,k0,N)卷積碼。卷積碼中編碼后的n個碼元不僅與當前段的k個信息有關(guān)，而且也與前面N-1段的信息有關(guān)，編碼過程中相互關(guān)聯(lián)的碼元為nN個。因此，這N時間的碼元數(shù)目nN通常被稱為這種碼的約束長度。

30、卷積碼的糾錯能力隨著N的增加而增大，在編碼器復雜程度一樣的情況下，卷段積碼的性能優(yōu)丁分組碼。卷積碼也是分組的，但它的監(jiān)視元不僅與本組的信息元有關(guān)，而且還與前假設干組的信息元有關(guān)。卷積碼根據(jù)需要，有不同的結(jié)構(gòu)與相應的糾錯能力，但都有類似的編碼規(guī)律。值得指出的是一種(2,1,N)卷積碼,其碼率為1/2,它的監(jiān)視位只有1位，編碼效率較高，也比擬簡單。如使用較長的約束長度，那么既可以糾正突發(fā)過失，也可以糾正隨機過失。2.2卷積碼編碼原理卷積碼一般表示為(n,k,N)的形式，即將k個信息比特編碼為n個比特的碼組，N為編碼約束長度，說明編碼過程中相互約束的碼段個數(shù)。卷積碼編碼后的n個碼元不僅與當前組的k個

31、信息比特有關(guān)，還與前N-1個輸入組的信息比特有關(guān)。編碼過程中相互關(guān)聯(lián)的碼兀有N*n個。R=k/n是編碼效率。編碼效率和約束長度是衡量卷積碼的兩個重要參數(shù)。典型的卷積碼一般選n,k較小，但N值可取較大(>10),以獲得簡單而高性能的卷積碼。卷積碼的編碼描述方式有很多種：沖激響應描述法、生成矩陣描述法、多項式乘積描述法、狀態(tài)圖描述，樹圖描述，網(wǎng)格圖描述等。2.2.1卷積碼解析表示法卷積碼的解析表示發(fā)大致可以分為離散卷積法，生成矩陣法，碼多項式法。下面以離散卷積為例進展說明。卷積碼的編碼器一般比擬簡單，為一個具有k個輸入端，n個輸出端，m級移位存放器的有限狀態(tài)有記憶系統(tǒng)。下列圖所示為(2,1,

32、7)卷積碼的編碼器。Secondoulipm圖2-12,1,7卷積碼編碼器假設輸入序列為u=(u0u1u2u3),那么對應兩個碼字序列C1=(ca0ca1ca2ca3)和C2=(cb0cb1cb2cb3)相應的編碼方程可寫為P1=u?C1,P2=u?C2,P=(P1,P2)。"？"符號表示卷積運算，P1,P2表示編碼器的兩個沖激響應，即編碼器的輸出可以由輸入序列和編碼器的兩個沖擊響應卷積而得到，故稱為卷積碼。這里的沖激響應指：當輸入為10000序列時，所觀察到的兩個輸出序列值。由丁上圖N值為乙故沖激響應至多可持續(xù)到第7位，可寫為P1=1111001,P2=1011011然后

33、將兩個輸出端的碼字序列合并為一個碼字序列為C=(ca0cb0ca1cb1ca2cb2)。假設輸入信息序列為1101;那么P1=1001010101,P2=1111101111,C=11010111011001110111。如圖3-2所示為(2,1,3)卷積碼的編碼器，也是本次課程設計所研究的卷積碼編碼器，由丁其生成沖激響應分別為111和101，故被稱為(7,5)碼。圖2-22,1,3卷積碼編碼器2.2.2卷積碼圖形表示法除了用解析法描述卷積碼的編碼外，還可以使用比擬形象的圖形法來表示卷積碼。比擬常用的有狀態(tài)圖法，樹圖法和網(wǎng)格圖法。狀態(tài)圖法：由丁卷積碼編碼器在下一時刻的輸出取決丁編碼器的當前狀態(tài)

34、和下一時刻的輸入，而編碼器當前狀態(tài)取決丁編碼器當前各移位存放器的存儲容。稱編碼器當前各移位存放器存儲容(0或1)為編碼器在該時刻的狀態(tài)(此狀態(tài)代表記憶以前的輸入信息)。隨著信息序列的不斷輸入，編碼器不斷從一個狀態(tài)轉(zhuǎn)移到另外一個狀態(tài)，并且輸出相應的編碼序列。編碼器的總可能狀態(tài)數(shù)為2mk個。對(7,5)碼的編碼器來說，n=2,k=1,N=3,m=2共有四個可能狀態(tài)，其狀態(tài)圖如圖2-3所示：0/00圖2-3卷積碼狀態(tài)圖圖中四個方塊表示狀態(tài)，狀態(tài)間的連線與箭頭表示轉(zhuǎn)移方向，連線上的數(shù)字表示是狀態(tài)發(fā)生轉(zhuǎn)移的到來比特，斜杠后的數(shù)字由一個狀態(tài)到另一個狀態(tài)轉(zhuǎn)移時的輸出碼字。如當前狀態(tài)為11,輸入信息為0,那么

35、轉(zhuǎn)移到01狀態(tài)并輸出01碼字，假設輸入信息為1,那么依然為11狀態(tài)，并輸出10碼字。樹圖法描述卷積碼的編碼過程除了用它的生成矩陣外，還可以用半無限碼樹圖。卷積碼的樹圖表示是一種形象的表示卷積碼編碼過程的方法。卷積碼的各種距離度量與樹圖有密切關(guān)系。以(2,1,3)卷積碼為例，它的生成多項式矩陣和生成矩陣分別為：GD1DD2,1D2(2-1)111011111011G111011g0g1g2g0gg2g0gg2(2-2)假設輸入編碼器的信息序列M(D)=(m0,m1,m2.)=(11011.),那么由編碼器輸出碼序列C為C=M=(11,01,01,00,01,01,)=(C0,Cl,C2,C3,)

36、(2-3)可以把這個編碼過程用如圖3-4所示的半無限碼樹圖來說明。設編碼器的初始狀態(tài)為0,碼樹中每個節(jié)點的下一級的上面的分支表示輸入為0,下面的分支表示輸入為l。每個分支上面的數(shù)字表示對應次分支的輸出。因此輸入不同的信息序列，編碼器就走不同的路徑，輸出不同的碼序列。按照上面的例子，那么編碼過程對應碼樹中粗線表示的一條路徑。對該碼序列來說，樹圖上的這條路徑就是它的正確路徑。對丁一般的二進制(n,k,N)編碼器來說，每次輸入的是k個信息元，有2k個可能的信息組，這對應丁從碼樹每一個節(jié)點上分出的分支樹有2*條，相應丁2k個不同信息組的輸入，并且每條都有n個碼元，作為與此相應的輸出子碼。由以上討論可知

37、，卷積碼編碼過程的實質(zhì)，是在輸入信息序列的控制下，編碼器沿碼樹通過某一特定路徑的過程。顯然，譯碼過程就是根據(jù)接收序列和信道干擾的統(tǒng)計特性，譯碼器在原碼樹上力圖恢復原來編碼器所走的路徑，即尋找正確路徑的過程。其過程如圖2-4所示。00_00-+S000S011S20US0_1410S2_01-11S2001001010011110001010S3ST1S0101S2S2S101S3S3圖2-4(2,1,3)卷積碼的樹圖網(wǎng)格圖法：網(wǎng)格圖可以描述卷積碼的狀態(tài)隨時間推移而轉(zhuǎn)移的情況。該圖縱坐標表示所有狀態(tài)，橫坐標表示時間。網(wǎng)格圖在卷積碼的概率譯碼，特別是Viterbi譯碼中非常重要，它綜合了狀態(tài)圖法直

38、觀簡單和樹圖法時序關(guān)系活晰的特點。如圖2-5所示t12狀態(tài)00.0氣«01202圖2-5譯碼器網(wǎng)格圖圖中實線表示輸入0時所走分支，虛線表示輸入1時所走分支，編碼時只需從起始狀態(tài)開始依次選擇路線并讀出輸出即可。假設從a狀態(tài)開始，輸入為1011,那么可由圖中讀出輸出為11101001。2.3卷積碼譯碼原理2.3.1卷積碼三種譯碼方式(1)代數(shù)譯碼代數(shù)譯碼是將卷積碼的一個編碼約束長度的碼段看作是n0(m+1),k0(m+1)線性分組碼，每次根據(jù)(m+1)分支長接收數(shù)字，對相應的最早的那個分支上的信息數(shù)字進展估計，然后向前推進一個分支。如果假設輸入的信息序列為=(10111),相應的編碼輸出

39、序列為c=(111)。在未超出編碼約束長度的情況下，可以通過譯碼時將承受序列與所有可能的輸出編碼序列進展比擬，通過比擬可以得到最小距離，進而可以得到可能的最大概率。按同樣方法判決，將每一位進展比擬，進展糾錯。假設此時接收序列R=(111),先根據(jù)R的前三個分支101000和碼樹中前三個分支長的所有可能的8條路徑(000000)、(000011)、(001110)、(001101)、(111011)、(111000)、(110101)和(110110)進展比擬，可知(111001)與接收序列(101000)的距離最小，丁是判定第0分支的信息數(shù)字為0。然后以R的第13分支數(shù)字(100001)按同樣

40、方法判決，依此類推下去，最后得到信息序列的估值為=(10111),遂實現(xiàn)了糾錯。這種譯碼法，譯碼時采用的接收數(shù)字長度或譯碼約束長度為(m+1)n0,所以只能糾正不多丁(dmin-1)/2個錯誤(n長上的)。實用中多采用反應擇多邏輯譯碼法實現(xiàn)。(2)維特比譯碼維特比譯碼是根據(jù)接收序列在碼的格圖上找出一條與接收序列距離或其他量度為最小的一種算法。它和運籌學中求最短路徑的算法相類似。假設接收序列為R=(111)，譯碼器從某個狀態(tài)，例如從狀態(tài)q出發(fā)，每次向右延伸一個分支對丁l<L,從每個節(jié)點出發(fā)都有2種可能的延伸，其中L是信息序列段數(shù)，對l>L,只有一種可能，并與接收數(shù)字相應分支進展比擬，

41、計算它們之間的距離，然后將計算所得距離加到被延伸路徑的累積距離值中。對到達每個狀態(tài)的各條路徑有2條的距離累積值進展比擬，保存距離值最小的一條路徑，稱為幸存路徑當有兩條以上取最小值時，可任取其中之一，譯碼過程如圖。圖中標出到達各級節(jié)點的幸存路徑的距離累積值。對給定R的估值序列為=(10111)。這種算法所保存的路徑與接收序列之間的似然概率為最大，所以乂稱為最大似然譯碼。這種譯碼的譯碼約束長度常為編碼約束長度的數(shù)倍，因而可以糾正不多丁(df/2)個錯誤。維特比譯碼器的復雜性隨m呈指數(shù)增大。實用中m不大丁10。它在衛(wèi)星和深空通信中有廣泛的應用。在解決碼問申擾和數(shù)據(jù)壓縮中也可應用。3序貫譯碼序貫譯碼是

42、根據(jù)接收序列和編碼規(guī)那么，在整個碼樹中搜索既可以前進，也可以后退出一條與接收序歹0距離或其他量度最小的一種算法。由丁它的譯碼器的復雜性隨m值增大而線性增長，在實用中可以選用較大的m值如2040以保證更高的可靠性。許多深空和海事通信系統(tǒng)都采用序貫譯碼。2.3.2 Viterbi譯碼原理卷積碼概率譯碼的根本思路是：以接收碼流為根底，逐個計算它與其他所有可能出現(xiàn)的、連續(xù)的網(wǎng)格圖路徑的距離，選出其中可能性最大的一條作為譯碼估值輸出。概率最大在大多數(shù)場合可解釋為距離最小，這種最小距離譯碼表達的正是最大似然的準那么。卷積碼的最大似然譯碼與分組碼的最大似然譯碼在原理上是一樣的，但實現(xiàn)方法上略有不同。主要區(qū)別

43、在?。悍纸M碼是孤立地求解單個碼組的相似度，而卷積碼是求碼字序列之間的相似度。基丁網(wǎng)格圖搜索的譯碼是實現(xiàn)最大似然判決的重要方法和途徑。用格圖描述時，由丁路徑的會聚消除了樹狀圖中的多余度，譯碼過程中只需考慮整個路徑集合中那些使似然函數(shù)最大的路徑。如果在某一點上發(fā)現(xiàn)某條路徑已不可能獲得最大對數(shù)似然函數(shù)，就放棄這條路徑，然后在剩下的“幸存'路徑中重新選擇路徑。這樣一直進展到最后第L級(L為發(fā)送序列的長度)。由丁這種方法較早地丟棄了那些不可能的路徑，從而減輕了譯碼的工作量，Viterbi譯碼正是基丁這種想法。對丁(n,k,N)卷積碼，其網(wǎng)格圖中共2kL種狀態(tài)。由網(wǎng)格圖的前N-1條連續(xù)支路構(gòu)成的路

44、徑互不相交，即最初2k_1條路徑各不一樣，當接收到第N條支路時，每條路徑都有2條支路延伸到第N級上，而第N級上的每兩條支路乂都會聚在一個節(jié)點上。在Viterbi譯碼算法中，把會聚在每個節(jié)點上的兩條路徑的對數(shù)似然函數(shù)累加值進展比擬，然后把具有較大對數(shù)似然函數(shù)累加值的路徑保存下來，而丟棄另一條路徑，經(jīng)挑選后第N級只留下2N條幸存路徑。選出的路徑同它們的對數(shù)似然函數(shù)的累加值將一起被存儲起來。由丁每個節(jié)點引出兩條支路，因此以后各級中路徑的延伸都增大一倍，但比擬它們的似然函數(shù)累加值后，丟棄一半，結(jié)果留存下來的路徑總數(shù)保持常數(shù)。由此可見，上述譯碼過程中的根本操作是，“加-比-選"，即每級求出對數(shù)

45、似然函數(shù)的累加值，然后兩兩比擬后作出選擇。有時會出現(xiàn)兩條路徑的對數(shù)似然函數(shù)累加值相等的情形，在這種情況下可以任意選擇其中一條作為“幸存'路徑。卷積碼的編碼器從全零狀態(tài)出發(fā)，最后乂回到全零狀態(tài)時所輸出的碼序列，稱為結(jié)尾卷積碼。因此，當序列發(fā)送完畢后，要在網(wǎng)格圖的終結(jié)處加上N-1個己知的信息作為完畢信息。在完畢信息到來時，由丁每一狀態(tài)中只有與發(fā)送信息相符的那條支路被延伸，因而在每級比擬后，幸存路徑減少一半。因此，在接收到N-1個己知信息后，在整個網(wǎng)格圖中就只有唯一的一條幸存路徑保存下來，這就是譯碼所得的路徑。也就是說，在己知接收到的序列的情況下，這條譯碼路徑和發(fā)送序列是最相似的。2.3.3

46、維特比譯碼算法性能對丁（n,k,N）卷積碼，其編碼存儲度（移位存放器單元的數(shù)量）為N,幸存路徑有2N條。每條幸存路徑（或信息序列）存儲器單元數(shù)是n*D,其中，n是卷積碼碼組寬度，D是需要存儲的碼組的個數(shù)。D的取值一般考慮取m的整倍數(shù)，稱D為幸存路徑長度。編碼存儲度和幸存路徑長度的取值問題關(guān)系到芯片規(guī)格、傳輸時延等問題。假設D很大，那么譯碼器的存儲量太大而難以實用。一般情況下，當譯碼進展到第5級（每級包括m個時刻）以后，每個狀態(tài)幸存路徑的前幾個分支已根本重合在一起，這就是說每個路徑存儲器不必存儲D個很大的碼序列。譯碼時，當譯碼器接收并處理完第D個碼組后，譯碼器中的幸存路徑存儲器已全部存滿，當譯碼

47、器開始處理第D+1個碼組時，他就對幸存路徑存儲器中的最頂端的碼組做出判決并輸出。1適當增加幸存路徑的長度可以提高譯碼器的糾錯能力。2幸存路徑的長度在增加到一定值時，譯碼器糾錯能力趨丁穩(wěn)定。當N值增加到6以上，誤比特率降低幅度大為減小，曲線有合二為一的趨勢。因此，可以認為幸存路徑長度D取編碼存儲度的6倍以上就可以取得比擬好的譯碼性能。3選擇適宜的延時。路徑量度（似然度）的累加選取和碼字延時判決輸出提高了譯碼的準確性，D越大越有利丁判決的正確性，但是這乂和通信的實時性背道而馳，一般D為卷積碼約束長度N的510倍即可，本文算法D取50。4留存路徑的更新的描述。每個狀態(tài)的留存路徑選擇實際上是從當前時刻

48、往前推的，例如，在時刻t,乂假設到達狀態(tài)s2的路徑有兩個，分別為s4和s5,對應的輸出碼字分別是00和11,我們分別計算出兩條路經(jīng)的分支量度BM并累加它們對應的前狀態(tài)路徑量度PM_I,發(fā)現(xiàn)累加后s5-s2的PM值比s4-s2的大，所以保存s5所對應的留存路徑，并更新狀態(tài)s2所對應的留存路徑存儲器。對每一狀態(tài)都做如此比擬，保存大的分支量度BM然后再累加前一狀態(tài)路徑量度PM_I,最后完成所有狀態(tài)的選擇，比擬當前所有狀態(tài)的路經(jīng)量度PM選擇最大路徑，如果延時超過D就判決輸出碼字。顯然此處判決的碼字要延時D時刻才能移位輸出。3.卷積碼編譯碼與MATLAB真圖3-1卷積碼編譯碼流程圖3.1Matlab概述

49、計算機對科學技術(shù)的幾乎一切領域產(chǎn)成了極其深遠的影響。熟練掌握并利用計算機進展科學計算研究與工程應用已是廣闊科研設計人員所必備的根本技能之一。從事科學研究和工程應用時候所遇到的最大的困擾大抵是我們在計算涉與矩陣運算或畫圖時，采用Fortran、C與C+瑋計算機語言進展程序設計是一項十分麻煩的工作，不僅需要對所利用的有關(guān)算法有深刻的了解，還需要掌握所用語言的語法與編程技巧。Matlab軟件由美國MathWorks公司丁1984年推出，歷經(jīng)十幾年的開展和黨爭，現(xiàn)已成為通用科技計算和圖視交互系統(tǒng)的程序語言，是(IEEE)國際公認的最優(yōu)秀的科技應用軟件之一。它的指令表達與數(shù)學、工程中常用的習慣形式十分相

50、似，從而使許多用C或Fortran實現(xiàn)起來十分復雜和費時的問題用Matlab就可以輕松地解決。Matlab的典型應用包括：數(shù)學計算、算法研究、數(shù)據(jù)分析和計算結(jié)果可視化、建模與仿真等。3.1.1Matlab的特點Matlab作為一種數(shù)值計算和與圖形處理工具軟件，其特點是語法結(jié)構(gòu)簡明、數(shù)值計算高效、圖形處理完備、易學易用，它在矩陣代數(shù)數(shù)值計算、數(shù)字信號處理、震動理論、神經(jīng)網(wǎng)絡控制、動態(tài)仿真等領域都有廣泛的應用。與CC+Fortran等高級語言相比，Matlab不但在數(shù)學語言的表達與解釋方面表現(xiàn)出人機交互的高度一致，而且具有優(yōu)秀高技術(shù)計算環(huán)境所不可缺少的如下特征：1高質(zhì)量、高可靠的數(shù)值計算能力；2基

51、丁向量、數(shù)組和矩陣的高維設計語言；3高級圖形和可視化數(shù)據(jù)處理的能力；4廣泛解決各學科各專業(yè)領域復雜問題的能力；5擁有一個強大的非線性系統(tǒng)仿真工具箱Simulink；6支持科學和工程計算標準的開放式、可交互結(jié)構(gòu)；7跨平臺兼容。3.1.2Matlab工具箱和容目前Matlab已經(jīng)成為國際上最流行的軟件之一，它除了傳統(tǒng)的交互式編程外，還提供了豐富可靠的矩陣運算。圖形繪制、數(shù)據(jù)處理、圖象處理、方便的Windows編程等便利工具。出現(xiàn)了各種以Matlab為根底的使用工具箱，廣泛的應用丁自動控制、圖像信號處理、生物醫(yī)學工程、語言處理、雷達工程、信號分析、震動理論、時序分析與建模、化學統(tǒng)計學、優(yōu)化設計等領域

52、，并表現(xiàn)出一般高級語言難以比擬的優(yōu)勢。較為常見的工具箱主要包括：控制系統(tǒng)工具箱(Controlsystemstoolbox)、系統(tǒng)識別工具箱(Systemsidentificationtoolbox)、多變量頻率設計工具箱(Multivariablefrequencydesigntoolbox)、魯棒控制工具箱(Robustcontroltoolbox)、分析與珠合工具箱(analysisandsynthesistoolbox)、神經(jīng)網(wǎng)絡工具箱(Neuralnetworktoolbox)、最優(yōu)化工具箱(Optimizationtoolbox)、信號處理工具箱(Signalprocessingt

53、oolbox)、模糊推理數(shù)據(jù)工具箱(Fuzzyinferencesystemtoolbox)、小波分析工具箱(Wavelettoolbox)、通信工具箱(Communicationstoolbox)。3.2卷積碼編碼與仿真在程序設計中，我們沒有采用MATLAffi帶的編碼函數(shù)而是采用了自己的編碼函數(shù)codec對2,1,3卷積碼編碼，其參數(shù)m為輸入信息序歹0,g1,g2為兩個輸出端口的沖激響應序列。3.2.1編碼程序為兩輸出端口的沖激響應序列。functioncod=codec(m,g1,g2)%g1,g2m1=conv(m,g1);%端口一輸出m2=conv(m,g2);%端口二輸出l=len

54、gth(m1);fori=1:l;cod(2*i-1)=rem(m1(i),2);將端口一編碼輸出賦給cod奇數(shù)位置cod(2*i)=rem(m2(i),2);將端口二編碼輸出賦給cod偶數(shù)位置end試運行編碼:clearallg1=111;g2=101;msg=1101;cod=codec(msg,g1,g2)輸出為:cod=1仿真結(jié)果如下列圖3-2圖3-22,1,3卷積碼編碼3.3信道傳輸過程仿真為了方便起見，我們采用了二相相移鍵控BPSK,也就是用二進制基帶信號0、1對載波進展二相調(diào)制。BPS處最簡單的PSK式，相移大小為180°,乂可稱為2-PSK。當基帶信號為1時對應相位為

55、兀，而當基帶信號為0時，對應的相位為-兀。根據(jù)這個理論，我們對BPSK勺調(diào)制過程作了模擬仿真，用一個簡短的程序?qū)PSK勺全過程進展了觀察。程序代碼如下：functionbpsk_output=bpsk_1(g);g=110101001011;%卷積碼編碼輸出信號cp=;bit=;forn=1:length(g);ifg(n)=0;die=-ones(1,100);%使得信號在坐標為0到100皆為-1,生成圖線se=zeros(1,100);elseg(n)=1;die=ones(1,100);se=ones(1,100);endcp=cpdie;bit=bitse;endsnr_db=35;

56、%可以調(diào)整變化的信噪比同時考慮信道中可能存在的噪聲noise=randn(1,length(bpsk);%隨機噪聲sigma=sqrt(5)*10A(-(snr_db)/20);recv=bpsk+3*sigma*noise;%產(chǎn)生的噪聲疊加在bpsk上仿真結(jié)果如圖3-3所示。在matlab運行時，我們對信道高斯白噪聲進展模擬,通過調(diào)節(jié)信噪比，我們可以活晰地觀察到噪聲對BPS涮制的影響，信噪比越大,傳輸?shù)男盘査芨蓴_越小，傳輸越準確。卷積碼煽媽之后拘調(diào)帛川盲導.rIillg-j|-一T1VftIIIiIIorZLTTZ：ii1iB1IaftIIIif十tIC200400GOOaon100012

57、CD是帶信號姓過BPSK調(diào)制?LL11JL_|f>ii|li|g0-t-I-iiii,P)lIIItlt，rt0200400E03300111012ET圖3-3模擬信道傳輸3.4維特比譯碼程序與仿真信號通過bpsk調(diào)制后在信道中傳輸，到達接收端時，先要進展解調(diào)，判決代碼為forj=1:length(recv);ifrecv(j)>0;recv(j)=1;elserecv(j)=0;endend3.4.1維特比譯碼算法解析Viterbi算法是通過加-比擬-選擇來實現(xiàn)的，狀態(tài)量度的計算方法如下：將前兩個狀態(tài)點上的狀態(tài)量度和相應分支量度相加，得到的兩個可能路徑量度作為新的狀態(tài)量度的候選項，送入邏輯單元中進展比擬，將其中似然性最大(距離最小)的一個作為狀態(tài)的新狀態(tài)量度存儲，同時存儲的還有狀態(tài)新的路徑記錄，主要算法步驟為：(1) 將接收到的序列分成每段長為n。的m組子序列。(2) 對所研究的碼畫出深度為m級的網(wǎng)格圖。對該網(wǎng)格圖的最后(L-1)級僅畫出對應丁全0輸入序歹0的路徑。(3) 置s=1，并置初始全0狀態(tài)的度量等丁0。(4) 對網(wǎng)格圖中全部連接第s級狀態(tài)到(s+1)級狀態(tài)的支路求出該接收序列中的第s個子序列的距離。(5) 將這些距離加到第s級各狀態(tài)的度量上去，得到對第(s+1)級狀態(tài)的度量候選者。對丁第(s+1)級的每一狀態(tài)，有2k0個候選