跳頻通信系統(tǒng)培訓(xùn)_PPT_ 編碼

1、 跳頻通信系統(tǒng)中的信道編碼技術(shù) 跳頻通信系統(tǒng)中的關(guān)鍵技術(shù) 西安電子科技大學(xué)西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室孫錦華孫錦華跳頻通信系統(tǒng)中的信道編碼技術(shù)與一般的定頻通信系統(tǒng)相比，跳頻通信系統(tǒng)雖然通過跳頻能跳出受干擾的信道，但是畢竟在部分信道上還是受到了干擾。另外即使沒有受到干擾也希望能夠提供更好的功率利用率（誤碼性能），因此在跳頻系統(tǒng)中也使用糾錯編碼技術(shù)糾正錯誤。在跳頻通信系統(tǒng)中，糾錯編碼除了向在定頻通信系統(tǒng)中能夠糾正由于噪聲、衰落、脈沖干擾等引起的錯誤之外，還起到了抗干擾的作用。 如果一個碼字的每一個比特在不同的信道中發(fā)送，并且這些如果

2、一個碼字的每一個比特在不同的信道中發(fā)送，并且這些信道的頻譜沒有重疊，那么一個能糾正信道的頻譜沒有重疊，那么一個能糾正n個錯誤的糾錯碼，個錯誤的糾錯碼，就能使接收機抗拒就能使接收機抗拒n個單頻連續(xù)波人為干擾信號。個單頻連續(xù)波人為干擾信號。跳頻通信系統(tǒng)中的信道編碼技術(shù) 1.引言一、差錯控制編碼的目的二、傳輸中產(chǎn)生誤碼的原因三、差錯控制方法 一、差錯控制編碼的目的將信源信息通過信道傳到信宿，怎樣才能做到盡可能不失真不失真而又快速快速呢？Q1：在不失真或允許一定失真的條件下，如何用盡可能少的符號來傳送信源信息？Q2：在信道受干擾的情況下，如何增加信號的抗干擾能力，同時又使得信息傳輸率最大？一、差錯控制

3、編碼的目的數(shù)字編碼的兩種類型： 信源編碼（source coding） 減少冗余、提高符號的平均信息量、提高有效性 有時接收端并不要求完全精確地恢復(fù)輸出的信息，比如允許產(chǎn)生一定程度的失真，這是符合大多數(shù)實際情況的。因為在很多實際問題中，精確復(fù)值既無可能，也無必要。連續(xù)信源就屬于這一類，而且由于實際信道總是存在干擾，同時信宿無論是人還是機器都存在一定的靈敏度和分辨率。Q1：在不失真或允許一定失真的條件下，如何用盡可能少的符號來傳送信源信息？一、差錯控制編碼的目的信源編碼（source coding） e.g. ASCII碼 Huffman編碼 數(shù)字電視：MPEG-2 、H.264 語音編碼（GS

4、M：FR、EFR、HR； WCDMA&TD：AMR CDMA2000：QCELP）一、差錯控制編碼的目的 信道編碼（channel coding） 增加冗余、降低誤碼、提高可靠性增加冗余、降低誤碼、提高可靠性 Q2：在信道受干擾的情況下，如何增加信號的抗干擾能力，同時又使得信息傳輸率最大？二、傳輸中產(chǎn)生誤碼的原因不管是模擬通信系統(tǒng)還是數(shù)字通信系統(tǒng)，都存在因干擾和信道傳輸特性不好對信號造成的不良影響。tt信道干擾 d(t)f (t)f (t) d(t)模擬信號(a) 模擬系統(tǒng)干擾示意圖tt信道干擾 d(t)f (t)f (t) d(t)數(shù)字信號(b) 數(shù)字系統(tǒng)干擾示意圖OOOO二、傳輸中

5、產(chǎn)生誤碼的原因?qū)τ谀M信號： 干擾信號波形畸變很難糾正 在模擬系統(tǒng)中只能采取各種抗干擾、防干擾措施，盡量將干擾降到最低程度以保證通信質(zhì)量。n對于數(shù)字信號： 干擾信號波形畸變一定程度的信號畸變不會影響對數(shù)字信息的接收 關(guān)心數(shù)字信號的電平狀態(tài)（是高電平還是低電平，或者是正電平還是負(fù)電平），而不太在乎其波形的失真。但是當(dāng)干擾超過系統(tǒng)的限度就會使數(shù)字信號產(chǎn)生誤碼，從而引起信息傳輸錯誤。二、傳輸中產(chǎn)生誤碼的原因按加性干擾引起的錯碼分布規(guī)律的不同，將信道分為三類： 隨機信道 （錯碼隨機出現(xiàn)，錯碼之間統(tǒng)計獨立） 正態(tài)分布的白噪聲 突發(fā)信道 （錯碼成串集中出現(xiàn)，前后錯碼的相關(guān)性） 脈沖干擾、某一段時間發(fā)生衰落

6、、光盤上一條劃痕 混合信道 （既存在隨機錯碼又存在突發(fā)錯碼） 實際傳輸信道二者兼而有之或以某個信道屬性為主 二、傳輸中產(chǎn)生誤碼的原因二元碼產(chǎn)生誤碼的情況二、傳輸中產(chǎn)生誤碼的原因設(shè)二元碼數(shù)字信號為s(t)，信道產(chǎn)生的噪聲為n(t)，則數(shù)字信號經(jīng)過信道傳輸后，在接收端的輸出信號y(t)為，y(t)=s(t)+n(t)。 設(shè)二元碼中對應(yīng)數(shù)據(jù)“1”的電平為A，對應(yīng)數(shù)據(jù)“0”的電平為0，則在噪聲干擾的情況下，數(shù)據(jù)“1”和“0”的輸出為 數(shù)據(jù)“1”：y(kT)=A+n(kT) 數(shù)據(jù)“0”：y(kT)=n(kT) k為0,1,2,.,N的正整數(shù)，T為碼元的時間長度。 在接收端，設(shè)置判決門限電平d(=A/2)

7、，判決準(zhǔn)則如下： y(kT)d 判定數(shù)字信號為數(shù)據(jù)“1”； y(kT)d 判定數(shù)字信號為數(shù)據(jù)“0”。 三、差錯控制方法檢錯重發(fā)法（檢錯重發(fā)法（ARQ） 接收端在收到的信碼中檢測出錯碼時，即設(shè)法通知發(fā)送端重發(fā)，直到正確收到為止。需要雙向信道n前向糾錯法（前向糾錯法（FEC） 接收端不僅能在收到的信碼中發(fā)現(xiàn)有錯碼，還能夠糾正錯碼。不需要反向信道、實時性好n混合糾錯法（混合糾錯法（HEC） 接收端首先檢錯，如果在糾錯碼的糾錯能力以內(nèi)，則自動糾正錯誤。如果錯誤較多，超過碼的糾錯能力，但能檢測出來，則通過反饋信道要求發(fā)端重發(fā)有錯的消息。n反饋校驗法反饋校驗法 接收端將收到的信碼原封不動地轉(zhuǎn)發(fā)回發(fā)送端，并

8、與原發(fā)送信碼相比較。如果發(fā)現(xiàn)錯誤，則發(fā)送端再進(jìn)行重發(fā)。 需要雙向信道、效率低接收端識別有無錯碼，根據(jù)什么來識別？三、差錯控制方法信息碼元是一種隨機序列，接收端無法預(yù)知，也無法識別其中有無錯碼?？梢杂砂l(fā)送端的信道編碼器在信息碼元序列中增加一些監(jiān)督碼元。這些監(jiān)督碼和信碼之間有一定的關(guān)系，使接收端可以利用這種關(guān)系由信道譯碼器來發(fā)現(xiàn)或糾正可能存在的錯碼。 差錯控制編碼（糾錯編碼）三、差錯控制方法不同的編碼方法，有不同的檢錯或糾錯能力，有的編碼只能檢錯，不能糾錯。一般，付出的代價越大，檢（糾）錯的能力就越強。碼率（編碼速率、編碼效率）： 將每個碼組內(nèi)信息碼元數(shù)k與總碼元數(shù)n之比稱為碼率，=k/n。 若編

9、碼序列中，平均每兩個信息碼元就有一個監(jiān)督碼元，則這種編碼的多余度為1/3，即編碼效率為2/3。增加的監(jiān)督碼元的多少，增加的監(jiān)督碼元的多少，用多余度來衡量用多余度來衡量差錯控制編碼原則上是以降低信息傳輸速率為代價來換取傳輸可靠性的提高2. 糾錯編碼的基本原理跳頻通信系統(tǒng)中的信道編碼技術(shù)糾錯編碼的基本原理例子： 設(shè)有一種由3位二進(jìn)制數(shù)字構(gòu)成的碼組，它共有8種不同的可能組合。若將其全部用來表示天氣，則可以表示8種不同天氣，例如： “000”（晴），“001”（云）， “010”（陰），“011”（雨）， “100”（雪），“101”（霜）， “110”（霧），“111”（雹）。其中任一碼組在傳輸中若

10、發(fā)生一個或多個錯碼，則將變成另一個信息碼組。這時，接收端將無法發(fā)現(xiàn)錯誤。糾錯編碼的基本原理l若在上述8種碼組中只準(zhǔn)許使用4種來傳送天氣，例如：“000”晴 “011”云 “101”陰 “110”雨 這時，雖然只能傳送4種不同的天氣，但是接收端卻有可能發(fā)現(xiàn)碼組中的一個錯碼。 例如，若“000”（晴）中錯了一位，則接收碼組將變成“100”或“010”或“001”。這3種碼組都是不準(zhǔn)使用的，稱為禁用碼組禁用碼組。糾錯編碼的基本原理 接收端在收到禁用碼組時，就認(rèn)為發(fā)現(xiàn)了錯碼。當(dāng)發(fā)生3個錯碼時，“000”變成了“111”，它也是禁用碼組，故這種編碼也能檢測3個錯碼。 但是這種碼不能發(fā)現(xiàn)一個碼組中的兩個錯

11、碼，因為發(fā)生兩個錯碼后產(chǎn)生的是許用碼組許用碼組。 “000” “011”、 “101”、 “110”云陰雨晴糾錯編碼的基本原理l檢錯和糾錯 上面這種編碼只能檢測錯碼，不能糾正錯碼。例如，當(dāng)接收碼組為禁用碼組“100”時，接收端將無法判斷是哪一位碼發(fā)生了錯誤，因為晴、陰、雨三者錯了一位都可以變成“100”。 要能夠糾正錯誤，還要增加多余度。例如，若規(guī)定許用碼組只有兩個：“000”（晴），“111”（雨），其他都是禁用碼組，則能夠檢測兩個以下錯碼，或能夠糾正一個錯碼。例如，當(dāng)收到禁用碼組“100”時，若當(dāng)作僅有一個錯碼，則可以判斷此錯碼發(fā)生在“1”位，從而糾正為“000”（晴）。因為“111”（雨

12、）發(fā)生任何一位錯碼時都不會變成“100”這種形式。 但是，這時若假定錯碼數(shù)不超過兩個，則存在兩種可能性：“000”錯一位和“111”錯兩位都可能變成“100”，因而只能檢測出存在錯碼而無法糾正錯碼。21糾錯編碼的基本原理分組碼l將信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼稱為分組碼分組碼 。l在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。 l信息位和監(jiān)督位的關(guān)系：舉例如下信息位監(jiān)督位晴000云011陰101雨110糾錯編碼的基本原理分組碼的一般結(jié)構(gòu)分組碼的符號：(n, k)ln 碼組的總位數(shù)，又稱為碼組的長度（碼長）。lk 碼組中信息碼元的數(shù)目。ln k r 碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位

13、數(shù)目。 糾錯編碼的基本原理分組碼的碼重和碼距l(xiāng)碼重：把碼組中“1”的數(shù)目稱為碼組的重量，簡稱碼重碼重。 1 0 1 1 0 碼重：碼重：3 0 1 1 0 0 2l碼距：把兩個碼組中對應(yīng)位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距碼距。碼距又稱漢明（漢明（Hamming）距離）距離。 例如，“000”晴，“011”云，“101”陰，“110”雨，4個碼組之間，任意兩個的距離均為2。l最小碼距：把某種編碼中各個碼組之間距離的最小值稱為最最小碼距小碼距(d0)。例如，上面的編碼的最小碼距d0 = 2。糾錯編碼的基本原理碼距的幾何意義l對于3位的編碼組，可以在3維空間中說明碼距的幾何意義。 l每個碼組

14、的3個碼元的值 (a2, a1, a0)就是此立方體各頂點的坐標(biāo)。而上述碼距概念在此圖中就對應(yīng)于各頂點之間沿立方體各邊行走的幾何距離。l由此圖可以直觀看出，上例中4個準(zhǔn)用碼組之間的距離均為2。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1糾錯編碼的基本原理碼距和檢糾錯能力的關(guān)系l一種編碼的最小碼距d0的大小直接關(guān)系著這種編碼的檢錯和糾錯能力l為檢測e個錯碼，要求最小碼距 d0 e + 1若碼組A中發(fā)生兩位錯碼，則其位置不會超出以0點為圓心，以2為半徑的圓。因此，只要最小碼距不小于3，碼組A發(fā)生兩位以下錯碼時，不可能變

15、成另一個準(zhǔn)用碼組，因而能檢測錯碼的位數(shù)等于2。 0123BA漢明距離ed0糾錯編碼的基本原理l為了糾正t個錯碼，要求最小碼距d0 2t + 1【證】圖中畫出碼組A和B的距離為5。碼組A或B若發(fā)生不多于兩位錯碼，則其位置均不會超出半徑為2以原位置為圓心的圓。這兩個圓是不重疊的。判決規(guī)則為：若接收碼組落于以A為圓心的圓上就判決收到的是碼組A，若落于以B為圓心的圓上就判決為碼組B。這樣，就能夠糾正兩位錯碼。 BtA漢明距離012345td0糾錯編碼的基本原理l為了糾正t個錯碼，同時檢測e個錯碼，要求最小碼距d0 e + t + 1（ e t ） “糾檢結(jié)合”： 對于出現(xiàn)較頻繁但錯碼數(shù)很少的碼組，按前

16、向糾錯方式工作，以節(jié)省反饋重發(fā)時間； 對一些錯碼數(shù)較多的碼組，在超過該碼的糾錯能力后，能自動按檢錯重發(fā)方式工作，以降低系統(tǒng)的總誤碼率。糾錯編碼的基本原理 編碼性能未采用糾錯編碼時，若接收信噪比等于7dB，編碼前誤碼率約為810-4，圖中A點，在采用糾錯編碼后，誤碼率降至約410-5，圖中B點。這樣，不增大發(fā)送功率就能降低誤碼率約一個半數(shù)量級。跳頻通信系統(tǒng)中的信道編碼技術(shù)3.簡單的實用編碼奇偶監(jiān)督碼漢明碼卷積碼30幾種實用編碼n奇偶監(jiān)督碼l奇偶監(jiān)督碼分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼兩種，兩者的原理相同。在偶數(shù)監(jiān)督碼中，無論信息位多少，監(jiān)督位只有1位，它使碼組中“1”的數(shù)目為偶數(shù)，即滿足下式條件： 式中

17、a0為監(jiān)督位，其他位為信息位。0021aaann信息位信息位監(jiān)督位監(jiān)督位晴晴000云云011陰陰101雨雨110監(jiān)督位與信監(jiān)督位與信息位滿足的息位滿足的關(guān)系式關(guān)系式幾種實用編碼l這種編碼能夠檢測奇數(shù)個錯碼。在接收端，按照上式求“模2和”，若計算結(jié)果為“1”就說明存在錯碼，結(jié)果為“0”就認(rèn)為無錯碼。l奇數(shù)監(jiān)督碼與偶數(shù)監(jiān)督碼相似，只不過其碼組中“1”的數(shù)目為奇數(shù)：1021aaann幾種實用編碼漢明碼線性分組碼l基本概念代數(shù)碼代數(shù)碼：建立在代數(shù)學(xué)基礎(chǔ)上的編碼。線性碼線性碼：按照一組線性方程構(gòu)成的代數(shù)碼。在線性碼中信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的。線性分組碼線性分組碼：按照一組線性方程構(gòu)成的

18、分組碼 。本節(jié)將以漢明碼為例引入線性分組碼的一般原理。幾種實用編碼漢明碼n漢明碼漢明碼能夠糾正1位錯碼且編碼效率較高的一種線性分組碼l漢明碼的構(gòu)造原理。以偶數(shù)監(jiān)督碼為例，偶數(shù)監(jiān)督碼是這樣的，它使用了一位監(jiān)督位a0，它和信息位an-1 a1一起構(gòu)成一個代數(shù)式：在接收端解碼時，實際上就是在計算若S = 0，就認(rèn)為無錯碼；若S = 1，就認(rèn)為有錯碼?，F(xiàn)將上式稱為監(jiān)督關(guān)系式監(jiān)督關(guān)系式，S稱為校正子校正子。由于校正子S只有兩種取值，故它只能代表有錯和無錯這兩種信息，而不能指出錯碼的位置。 0021aaann021aaaSnn幾種實用編碼漢明碼若監(jiān)督位增加一位，即變成兩位，則能增加一個類似的監(jiān)督關(guān)系式。兩

19、個校正子有4種組合： 00，01，10，11。 若用其中1種組合表示“無錯”，則其余3種組合就可用來指示一個錯碼的3種不同位置。同理，r個監(jiān)督關(guān)系式能指示1位錯碼的(2r 1)個可能位置。一般來說，若碼長為n，信息位數(shù)為k，則監(jiān)督位數(shù)rnk。如果希望用r個監(jiān)督位構(gòu)造出r個監(jiān)督關(guān)系式來指示1位錯碼的n種可能位置，則要求下面通過一個例子來說明如何具體構(gòu)造這些監(jiān)督關(guān)系式。1212rknrr或無錯幾種實用編碼漢明碼n例：設(shè)分組碼分組碼(n, k)中k = 4，為了糾正1位錯碼，由上式可知，要求監(jiān)督位數(shù) r 3。若取 r = 3，則n = k + r = 7。我們用a6 a5 a0表示這7個碼元，用S1

20、、S2和S3表示3個監(jiān)督關(guān)系式中的校正子，則S1、S2和S3的值與錯碼位置的對應(yīng)關(guān)系可以規(guī)定如下表所列：S1 S2 S3錯碼位置S1 S2 S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無錯碼21rn 幾種實用編碼漢明碼n由表中規(guī)定可見，僅當(dāng)一位錯碼的位置在a2 、a4、a5或a6時，校正子S1為1；否則S1為零。這就意味著a2 、a4、a5和a6四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：n同理， a1、a3、a5和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系：n以及a0、a3、a4 和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系24561aaaaS13562aaaaS03463aaaaS幾種實用編碼漢明碼n在發(fā)送

21、端編碼時，信息位a6、a5、a4和a3的值決定于輸入信號，因此它們是隨機的。監(jiān)督位a2、a1和a0應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系來確定，即監(jiān)督位應(yīng)使上3式中S1、S2和S3的值為0（表示編成的碼組中應(yīng)無錯碼）： 上式經(jīng)過移項運算，解出監(jiān)督位 給定信息位后，可以直接按上式算出監(jiān)督位， 結(jié)果見下表：000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa幾種實用編碼漢明碼信息位a6 a5 a4 a3監(jiān)督位a2 a1 a0信息位a6 a5 a4 a3監(jiān)督位a2 a1 a00000000100011100010111001100001010110100100

22、011110101100101001101100001010110111010100110011111010001110001111111346035614562aaaaaaaaaaaa幾種實用編碼漢明碼接收端收到每個碼組后，先計算出S1、S2和S3，再查表判斷錯碼情況。例如，若接收碼組為0000011，按上述公式計算可得：S1 = 0，S2 = 1，S3 = 1。由于S1 S2 S3 等于011，故查表 可知在a3位有1錯碼。 1654200000Saaaa2653100011Saaaa 3643000011Saaaa S1 S2 S3錯碼位置錯碼位置S1 S2 S3錯碼位置錯碼位置001a

23、0101a4010a1110a5100a2111a6011a3000無錯碼無錯碼a6a0幾種實用編碼漢明碼按照上述方法構(gòu)造的碼稱為漢明碼。 表中所列的(7, 4)漢明碼的最小碼距d0 = 3。因此，這種碼能夠糾正1個錯碼或檢測2個錯碼。由于碼率k/n = (n - r) /n =1 r/n，故當(dāng)n很大和r很小時，碼率接近1?？梢?，漢明碼是一種高效碼。幾種實用編碼卷積碼卷積碼l非分組碼概念：卷積碼是一種非分組碼。通常它更適用于前向糾錯，因為對于許多實際情況它的性能優(yōu)于分組碼，且運算較簡單。卷積碼在編碼時雖然也是把k個比特的信息段編成n個比特的碼組，但是監(jiān)督碼元不僅和當(dāng)前的k比特信息段有關(guān)，而且還

24、同前面m = (N 1)個信息段有關(guān)。所以一個碼組中的監(jiān)督碼元監(jiān)督著N個信息段。通常將N稱為編碼約束度約束度，并將nN稱為編碼約束長度約束長度。一般說來，對于卷積碼，k 和 n 的值是比較小的整數(shù)。我們將卷積碼記作(n, k, N)。碼率則仍定義為k / n。 42幾種實用編碼卷積碼l卷積碼的基本原理編碼器原理方框圖編碼輸出每次輸入k比特1k1k1k1k 1 k2k3kNk 12nNk級移存器n個模2加法器每輸入k比特旋轉(zhuǎn)1周43幾種實用編碼卷積碼l例： (n, k, N) = (3, 1, 3)卷積碼編碼器設(shè)輸入信息比特序列是bi-2 bi-1 bi bi+1，則當(dāng)輸入bi時，此編碼器輸出3

25、比特ci di ei，輸入和輸出的關(guān)系如下：bi-2bi輸入bibi-1編碼輸出dicieiM2M3M121 2iiiiiiiiibbbebbdbc44ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi1bitt輸入輸出幾種實用編碼卷積碼在下圖中用虛線示出了信息位bi的監(jiān)督位和各信息位之間的約束關(guān)系。這里的編碼約束長度nN等于9。45幾種實用編碼卷積碼n卷積碼的譯碼l卷積碼的幾何表述碼樹圖：現(xiàn)仍以上面(3, 1, 3)碼為例，介紹卷積碼的碼樹 。起點信息位狀態(tài) M3M2 a 0 0 b 0 1 c 1 0 d 1 1信息位信息位 11 0 1000111c1d1e1000

26、111001110011100010101000111001110011100010101c4d4e4111000001110c2d2e22000100111011001101110010c3d3e3abcdabcdabcdabcd上半部下半部ba10aabcdabcdcdab01100146幾種實用編碼卷積碼u將圖中移存器M1，M2和M3的初始狀態(tài)000作為碼樹的起點。現(xiàn)在規(guī)定：輸入信息位為“0”，則狀態(tài)向上支路移動；輸入信息位為“1”，則狀態(tài)向下支路移動。于是，就可以得出圖中所示的碼樹。u設(shè)現(xiàn)在的輸入碼元序列為1101，則當(dāng)?shù)?個信息位b1 = 1輸入后，各移存器存儲的信息分別為M1 =

27、1，M2 = M3 = 0。此時的輸出為c1 d1 e1= 111，碼樹的狀態(tài)將從起點a向下到達(dá)狀態(tài)b；此后，第2個輸入信息位b2 = 1，故碼樹狀態(tài)將從狀態(tài)b向下到達(dá)狀態(tài)d。這時M2 = 1，M3 = 0，此時，c2d2e2 = 110。第3位和后繼各位輸入時，編碼器將按照圖中粗線所示的路徑前進(jìn)，得到輸出序列：111 110 010 100 。u由此碼樹圖還可以看到，從第4級支路開始，碼樹的上半部和下半部相同。這意味著，從第4個輸入信息位開始，輸出碼元已經(jīng)與第1位輸入信息位無關(guān)，此編碼器的約束度N = 3。47幾種實用編碼卷積碼u碼樹圖原則上還可以用于解碼。在解碼時，按照漢明距離最小的準(zhǔn)則沿

28、上面的碼樹進(jìn)行搜索。 例如，若接收碼元序列為111 010 010 110 ，和發(fā)送序列相比可知第4和第11碼元為錯碼。當(dāng)接收到第46個碼元“010”時，將這3個碼元和對應(yīng)的第2級的上下兩個支路比較，它和上支路“001”的漢明距離等于2，和下支路“110”的漢明距離等于1，所以選擇走下支路。 發(fā)送序列：111 110 010 10048幾種實用編碼卷積碼u類似地，當(dāng)接收到第1012個碼元“110”時，和第4級的上下支路比較，它和上支路的“011”的漢明距離等于2，和下支路“100”的漢明距離等于1，所以走下支路。這樣，就能夠糾正這兩個錯碼。 u一般說來，碼樹搜索解碼法并不實用，因為隨著信息序列

29、的增長，碼樹分支數(shù)目按指數(shù)規(guī)律增長；在上面的碼樹圖中，只有4個信息位，分支已有24 = 16個。但是它為以后實用解碼算法建立了初步基礎(chǔ)。49幾種實用編碼卷積碼n狀態(tài)圖上面的碼樹可以改進(jìn)為下述的狀態(tài)圖。由上例的編碼器結(jié)構(gòu)可知，輸出碼元ci di ei由當(dāng)前輸入信息位bi和前兩位信息位bi-1和bi-2（即移存器M2和M3的狀態(tài)）決定。在上圖中已經(jīng)為M2和M3的4種狀態(tài)規(guī)定了代表符號a, b, c 和d。所以，可以將當(dāng)前輸入信息位、移存器前一狀態(tài)、移存器下一狀態(tài)和輸出碼元之間的關(guān)系歸納于下表中。50幾種實用編碼卷積碼由上表看出，前一狀態(tài)a只能轉(zhuǎn)到下一狀態(tài)a或b，前一狀態(tài)b只能轉(zhuǎn)到下一狀態(tài)c或d，等

30、等。按照此表中的規(guī)律，可以畫出狀態(tài)圖如下圖所示。 移存器前一狀態(tài)M3 M2當(dāng)前輸入信息位 bi輸出碼元cidiei移存器下一狀態(tài)M3 M2a (00)01000111a (00)b (01)b (01)01001110c (10)d (11)c (10)01011100a (00)b (01)d (11)01010101c (10)d (11)212iiiiiiiiicbdbbebbb51幾種實用編碼卷積碼 虛線輸入信息位為“1”時狀態(tài)轉(zhuǎn)變的路線； 實線輸入信息位為“0”時狀態(tài)轉(zhuǎn)變的路線； 線條旁的3位數(shù)字是編碼輸出比特。利用這種狀態(tài)圖可以方便地從輸入序列得到輸出序列利用這種狀態(tài)圖可以方便地從

31、輸入序列得到輸出序列abcd00011110111001001110000152幾種實用編碼卷積碼n網(wǎng)格圖（格狀圖、籬笆圖）將狀態(tài)圖在時間上展開，可以得到網(wǎng)格圖如下： 圖中畫出了5個時隙。在此圖中，仍用虛線虛線表示輸入信息位為“1”時狀態(tài)轉(zhuǎn)變的路線；實線實線表示輸入信息位為“0”時狀態(tài)轉(zhuǎn)變的路線?？梢钥闯?，在第4時隙以后的網(wǎng)格圖形完全是重復(fù)第3時隙的圖形。這也反映了此(3, 1, 3)卷積碼的約束度為3。 110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100

32、10053幾種實用編碼卷積碼在上圖中給出了輸入信息位為11010時，在網(wǎng)格圖中的編碼路徑。圖中示出這時的輸出編碼序列是：111 110 010 100 011。由上述可見，用網(wǎng)格圖表示編碼過程和輸入輸出關(guān)系比碼樹圖更為簡練。有了上面的狀態(tài)圖和網(wǎng)格圖，下面就可以討論維特比解碼算法了。abcdabcd11001000111110054幾種實用編碼卷積碼維特比解碼算法l最大似然算法的基本原理將接收到的信號序列和所有可能的發(fā)送信號序列比較，選擇其中漢明距離最小的序列認(rèn)為是當(dāng)前發(fā)送信號序列。若發(fā)送一個k位序列，則有2k種可能的發(fā)送序列。計算機應(yīng)存儲這些序列，以便用作比較。當(dāng)k較大時，存儲量太大，使實用受

33、到限制。維特比算法對此作了簡化，使之能夠?qū)嵱谩，F(xiàn)在仍用上面(3, 1, 3)卷積碼的例子來說明維特比算法的原理。55幾種實用編碼卷積碼例： (3, 1, 3)卷積碼設(shè)現(xiàn)在的發(fā)送信息位為1101，為了使圖中移存器的信息位全部移出，在信息位后面加入3個“0”，故編碼后的發(fā)送序列為111 110 010 100 001 011 000。并且假設(shè)接收序列為 111 010 010 110 001 011 000，其中第4和第11個碼元為錯碼。由于這是一個(n, k, N) = (3, 1, 3)卷積碼，發(fā)送序列的約束度N = 3，所以首先需考察nN 9比特。第1步考察接收序列前9位“111 010 0

34、10”。由此碼的網(wǎng)格圖可見，沿路徑每一級有4種狀態(tài)a, b, c和d。每種狀態(tài)只有兩條路徑可以到達(dá)。故4種狀態(tài)共有8條到達(dá)路徑?，F(xiàn)在比較網(wǎng)格圖中的這8條路徑和接收序列之間的漢明距離。 56110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100幾種實用編碼卷積碼例如，由出發(fā)點狀態(tài)a經(jīng)過3級路徑后到達(dá)狀態(tài)a的兩條路徑中上面一條為“000 000 000”。它和接收序列“111 010 010”的漢明距離等于5；下面一條為“111 001 011”,它和接收序

35、列的漢明距離等于3。同樣，由出發(fā)點狀態(tài)a經(jīng)過3級路徑后到達(dá)狀態(tài)b、c和d的路徑分別都有兩條，故總共有8條路徑。在下表中列出了這8條路徑和其漢明距離。57幾種實用編碼卷積碼現(xiàn)在將到達(dá)每個狀態(tài)的兩條路徑的漢明距離作比較，將距離小的一條路徑保留，稱為幸存路徑。若兩條路徑的漢明距離相同，則可以任意保存一條。這樣就剩下4條路徑了，即表中第2, 4, 6和8條路徑。序號路徑對應(yīng)序列漢明距離幸存否1aaaa000 000 0005否2abca111 001 0113是3aaab000 000 1116否4abcb111 001 1004是5aabc000 111 0017否6abdc111 110 0101

36、是7aabd000 111 1106否8abdd111 110 1014是58幾種實用編碼卷積碼第2步繼續(xù)考察接收序列的后繼3個比特“110”。計算4條幸存路徑上增加1級后的8條可能路徑的漢明距離。結(jié)果如下表。表中最小的總距離等于2，其路徑是abdc+b，相應(yīng)序列為111 110 010 100。它和發(fā)送序列相同，故對應(yīng)發(fā)送信息位1101。按照表中的幸存路徑畫出的網(wǎng)格圖示于下圖中。 序號路徑原幸存路徑的距離新增路徑段新增距離總距離幸存否1abca+a3aa25否2abdc+a1ca23是3abca+b3ab14否4abdc+b1cb12是5abcb+c4bc37否6abdd+c4dc15是7a

37、bcb+d4bd04是8abdd+d4dd26否59幾種實用編碼卷積碼圖中藍(lán)色的路徑是漢明距離最?。ǖ扔?）的路徑。 abcd011010010101001abcd11110010011011060幾種實用編碼卷積碼上面提到過，為了使輸入的信息位全部通過編碼器的移存器，使移存器回到初始狀態(tài)，在信息位1101后面加了3個“0”。若把這3個“0”仍然看作是信息位，則可以按照上述算法繼續(xù)解碼。這樣得到的幸存路徑網(wǎng)格圖示于下圖中。圖中的藍(lán)色虛線仍然是漢明距離最小的路徑。但是，若已知這3個碼元是（為結(jié)尾而補充的）“0”，則在解碼計算時就預(yù)先知道在接收這3個“0”碼元后，路徑必然應(yīng)該回到狀態(tài)a。而由圖可見

38、，只有兩條路徑可以回到a狀態(tài)。所以，這時上圖可以簡化成下圖。110011010010101101001001abcdabcd000 111100100000 01101100110161幾種實用編碼卷積碼在上例中卷積碼的約束度N = 3，需要存儲和計算8條路徑的參量。由此可見，維特比解碼算法的復(fù)雜度隨約束長度N按指數(shù)形式2N增長。故維特比解碼算法適合約束度較小（N 10）的編碼。對于約束度大的卷積碼，可以采用其他解碼算法。 110011010010101101001001abcdabcd000 111100100000 011011001跳頻通信系統(tǒng)中的信道編碼技術(shù)4.其他編碼RS碼Turbo碼TPC碼LDPC碼其他編碼RS碼：碼：它是一類具有很強糾錯能力的多進(jìn)制BCH碼。l若用n表示RS碼的碼長，則對于m進(jìn)制的RS碼，其碼長需要滿足下式：n = m 1 = 2q 1 式中 q 2，為整數(shù)。由于RS碼能夠糾正t個m進(jìn)制錯碼，或者說，能夠糾正碼組中t個不超過q位連續(xù)的二進(jìn)制錯碼，所以RS碼特別適用于存在突發(fā)錯誤的信道，例如移動通信網(wǎng)等衰落信道中。此外，因為它是多進(jìn)制糾錯編碼，所以特別適合用于多進(jìn)制調(diào)制的場合。其他編碼Turbo碼l什么是Turbo碼？它是