【正文】 計(jì)算出相應(yīng)的伴隨式。錯(cuò)誤圖樣識(shí)別器有 r個(gè)輸入端，通過這 r個(gè)輸入端輸入伴隨式多項(xiàng)式，根據(jù)伴隨式多項(xiàng)式找到錯(cuò)誤圖樣。緩存器用于存儲(chǔ) n位接收碼字。模 2運(yùn)算電路用于糾正錯(cuò)誤。當(dāng)伴隨式為 0時(shí)，模 2運(yùn)算電路中來自錯(cuò)誤圖樣識(shí)別電路的輸入端為0，輸出接收碼字。當(dāng)伴隨式不為 0時(shí)，識(shí)別電路在相應(yīng)的錯(cuò)誤碼元時(shí)刻輸出為 1，它使緩存器輸出取反，這樣就糾正了錯(cuò)誤。 第 10章 信道編碼 圖 一種循環(huán)碼譯碼器原理圖 第 10章 信道編碼 圖 同之處在于：在循環(huán)碼譯碼器中，接收碼字的伴隨式計(jì)算可用循環(huán)移位寄存器來實(shí)現(xiàn)，這個(gè)循環(huán)移位寄存器的連線與生成多項(xiàng)式有關(guān)，由循環(huán)移位寄存器構(gòu)成的伴隨式計(jì)算電路不但簡單而且運(yùn)算快速。 第 10章 信道編碼 卷 積 碼 卷積碼編碼 卷積碼與前面介紹的線性分組碼不同。在線性分組碼 (n, k)中，每個(gè)碼字的 n個(gè)碼元只與本碼字中的 k個(gè)信息碼元有關(guān)，或者說，各碼字中的監(jiān)督碼元只對(duì)本碼字中的信息碼元起監(jiān)督作用。卷積碼則不同，每個(gè) (n, k)碼字 (通常稱其為子碼，碼字長度較短 )內(nèi)的 n個(gè)碼元不僅與該碼字內(nèi)的信息碼元有關(guān)，而且還與前面 m個(gè)碼字內(nèi)的信息碼元有關(guān)?；蛘哒f，各子碼內(nèi)的監(jiān)督碼元不僅對(duì)本子碼起監(jiān)督作用，而且對(duì)前面 m個(gè)子碼內(nèi)的信息碼元也起監(jiān)督作用。所以，卷積碼常用 (n, k, m)表示。通常稱 m為編碼存儲(chǔ)，它反映了輸入信息碼元在編碼器中需要存儲(chǔ)的時(shí)間長短；稱 N=m+1為編碼約束度，它是相互約束的碼字個(gè)數(shù)；稱nN為編碼約束長度，它是相互約束的碼元個(gè)數(shù)。卷積碼也有系統(tǒng)碼和非系統(tǒng)碼之分，如果子碼是系統(tǒng)碼，則稱此卷積碼為系統(tǒng)卷積碼，反之，則稱為非系統(tǒng)卷積碼。 第 10章 信道編碼 圖 (2， 1， 2)卷積碼的編碼電路。此電路由二級(jí)移位寄存器、兩個(gè)模 2加法器，及開關(guān)電路組成。編碼前，各寄存器清 0，信息碼元按 a1， a2， a3， … aj2， aj1， aj， … 的順序輸入編碼器。每輸入一個(gè)信息碼元 aj，開關(guān) K依次接到 aj aj2各端點(diǎn)一次，輸出一個(gè)子碼 aj1aj2。 子碼中的兩個(gè)碼元與輸入信息碼元間的關(guān)系為 (1061) 由此可見，第 j個(gè)子碼中的兩個(gè)碼元不僅與本子碼信息碼元 aj有關(guān)，而且還與前面兩個(gè)子碼中的信息碼元 aj aj2 有關(guān)。因此，卷積碼的編碼存儲(chǔ) m=2，約束度 N=m+1=3，約束長度 nN=6。 ???????????22211jjjjjjjaaaaaaa第 10章 信道編碼 圖 (2， 1， 2)卷積碼編碼電路 第 10章 信道編碼 例 在圖 (2， 1， 2)卷積碼編碼電路中，當(dāng)輸入信息 10011時(shí)，求輸出碼字序列。 解 在計(jì)算第 j個(gè)子碼時(shí)的移存寄存器的內(nèi)容 aj1aj2稱為現(xiàn)狀態(tài) (簡稱為現(xiàn)態(tài) )，編碼工作時(shí)初始狀態(tài)為 00(清 0)，第 j個(gè)子碼的信息進(jìn)入移位寄存器后的狀態(tài)稱為次態(tài)。當(dāng)輸入信息及現(xiàn)態(tài)已知時(shí)，利用式 (1061)即可求出此輸入信息所對(duì)應(yīng)的碼字。輸入信息、輸出碼字、每個(gè)時(shí)刻的現(xiàn)態(tài)及次態(tài)均列于表 1061中。 第 10章 信道編碼 第 10章 信道編碼 卷積碼的圖形描述 卷積碼編碼器的工作過程常用三種等效的圖形來描述，這三種圖形分別是：狀態(tài)圖、碼樹圖和格狀圖。下面以圖 所示的 (2， 1， 2) 1. 狀態(tài)圖 圖 (Mealy)時(shí)序邏輯電路。共有四個(gè)不同的狀態(tài)： aj1aj2=00， 10， 01， 11，為方便起見，這四個(gè)狀態(tài)分別用 a、 b、 c和 d來表示。在每一個(gè)狀態(tài)下都有 0、 1兩種輸入。根據(jù)式 (1061)，我們可求出每種狀態(tài)下每種輸入時(shí)的輸出碼字及相應(yīng)的次態(tài)，見表 1062。 第 10章 信道編碼 第 10章 信道編碼 表 1062的圖形表示就是 (2， 1， 2)卷積編碼器的狀態(tài)圖，見圖 。圖中，用帶箭頭的線表示輸入信息后狀態(tài)的轉(zhuǎn)移，實(shí)線表示輸入信息為“ 0”，虛線表示輸入信息為“ 1”，線旁的二位二進(jìn)制數(shù)表示輸出的碼字。 此狀態(tài)圖完全反映了圖 。有了狀態(tài)圖，我們可以很方便地確定任何輸入信息序列時(shí)所對(duì)應(yīng)的輸出碼字序列。如輸入信息序列為 10011，求輸出碼字序列的方法是：從初始狀態(tài) a開始沿著狀態(tài)圖中的有向線走，輸入為“ 1”時(shí)走虛線，輸入為“ 0”時(shí)走實(shí)線，所經(jīng)路徑上的 1 1 1 01序列即為輸入 10011 第 10章 信道編碼 圖 (2， 1， 2)卷積編碼器的狀態(tài)圖 第 10章 信道編碼 2. 碼樹圖 圖 (2， 1， 2)編碼器的工作原理也可用圖 示的圖形來表示，此圖形稱為 (2， 1， 2)卷積碼的碼樹圖。它描述了編碼器在工作過程中可能產(chǎn)生的各種序列。最左邊為起點(diǎn)，初始狀態(tài)為 a。從每個(gè)狀態(tài)出發(fā)有兩條支路 (因?yàn)槊總€(gè)碼字中只有 1位信息 )，上支路表示輸入為“ 0”，下支路表示輸入為“ 1”。每個(gè)支路上的二位二進(jìn)數(shù)是相應(yīng)的輸出碼字。由圖可知，當(dāng)信息序列給定時(shí)，沿著碼樹圖上的支路很容易確定相應(yīng)的輸出碼序列。如輸入信息為 10011時(shí)，從碼樹圖可得輸出碼字序列為 1 1 1 01，與前面從狀態(tài)圖上得到的碼字序列完全相同。 第 10章 信道編碼 3. 格狀圖 圖 ，稱為 (2， 1，2)卷積碼的格狀圖。在碼樹圖中，從第三級(jí)開始出現(xiàn)全部四個(gè)狀態(tài)，第三級(jí)以后四個(gè)狀態(tài)重復(fù)出現(xiàn)，使圖形變得越來越大。在格狀圖中，把碼樹圖中具有相同狀態(tài)的節(jié)點(diǎn)合并在一起，使圖形變得較為緊湊；碼樹中的上支路 (即輸入信息為 “ 0”)用實(shí)線表示，下支路 (即輸入信息為“ 1”)用虛線表示；支路上標(biāo)注的二進(jìn)制數(shù)據(jù)為輸出碼字；自上而下的 4行節(jié)點(diǎn)分別表示 a、 b、 c、 d四種狀態(tài)。從第三級(jí)節(jié)點(diǎn)開始，圖形開始重復(fù)。當(dāng)輸入信息序列給定時(shí)，從 a開始的路徑跟著就確定了，相應(yīng)的輸出碼字序列也就確定了。如輸入信息序?yàn)?10011時(shí)，對(duì)應(yīng)格狀圖的路徑為 a b c a b d，則相應(yīng)的輸出碼字序列為 1 1 101。 第 10章 信道編碼 圖 (2， 1， 2)卷積碼的碼樹圖 第 10章 信道編碼 圖 (2， 1， 2)卷積碼的格狀圖 第 10章 信道編碼 卷積碼的維特比譯碼 卷積碼的譯碼分代數(shù)譯碼和概率譯碼兩類。代數(shù)譯碼由于沒有充分利用卷積碼的特點(diǎn)，目前很少應(yīng)用。維特比譯碼和序列譯碼都屬于概率譯碼。維特比譯碼方法適用于約束長度不太大的卷積碼的譯碼，當(dāng)約束長度較大時(shí)，采用序列譯碼能大大降低運(yùn)算量，但其性能要比維特比譯碼差些。維特比譯碼方法在通信領(lǐng)域有著廣泛的應(yīng)用，市場上已有實(shí)現(xiàn)維特比譯碼的超大規(guī)模集成電路。 第 10章 信道編碼 維特比譯碼是一種最大似然譯碼。其基本思想是：將已經(jīng)接收到的碼字序列與所有可能的發(fā)送序列進(jìn)行比較，選擇其中碼距最小的一個(gè)序列作為發(fā)送序列 (即譯碼后的輸出序列 )。具體的譯碼方法是： (1) 在格狀圖上，計(jì)算從起始狀態(tài) (j=0時(shí)刻 )開始，到達(dá) j=m時(shí)刻的每個(gè)狀態(tài)的所有可能路徑上的碼字序列與接收到的頭 m個(gè)碼字之間的碼距，保存這些路徑及碼距。 (2) 從 j=m到 j=m+1共有 2k2 m條路徑 (狀態(tài)數(shù)為 2m個(gè)，每個(gè)狀態(tài)往下走各有 2k個(gè)分支 )，計(jì)算每個(gè)分支上的碼字與相應(yīng)時(shí)間段內(nèi)接收碼字間的碼距，分別與前面保留路徑的碼距相加，得到2k2 m個(gè)路徑的累計(jì)碼距，對(duì)到達(dá) j=m+1時(shí)刻各狀態(tài)的路徑進(jìn)行比較，每個(gè)狀態(tài)保留一條具有最小碼距的路徑及相應(yīng)的碼距值。 第 10章 信道編碼 (3) 按 (2)的方法繼續(xù)下去，直到比較完所有接收碼字。 (4) 全部接收碼字比較完后，剩下 2m個(gè)路徑 (每個(gè)狀態(tài)剩下一條路徑 )，選擇最小碼距的路徑，此路徑上的發(fā)送碼字序列即是譯碼后的輸出序列。 第 10章 信道編碼 例 以上述 (2， 1， 2)編碼器為例，設(shè)發(fā)送碼字序列為 0000000000，經(jīng)信道傳輸后有錯(cuò)誤，接收碼字序列為0100010000。顯然，接收碼字序列中有兩個(gè)錯(cuò)誤?，F(xiàn)對(duì)此接收序列進(jìn)行維特比譯碼，求譯碼后的輸出序列。 第 10章 信道編碼 解 由于 (2， 1， 2)編碼器的編碼存儲(chǔ) m=2，應(yīng)用譯碼方法中的步驟 (1)， 應(yīng)從 (2， 1， 2)格狀圖的第 j=m=2時(shí)刻開始。從圖 ， j=2時(shí)刻有 4個(gè)狀態(tài)，從初始狀態(tài)出發(fā)，到達(dá)這4個(gè)狀態(tài)的路徑有 4條，到達(dá)狀態(tài) b路徑的碼字序列為 0000； 到達(dá)狀態(tài) b路徑的碼字序列為 0011； 到達(dá)狀態(tài) c路徑的碼字序列為 1110； 到達(dá)狀態(tài) d路徑的碼字序列為 1101。路徑長度為 2，這段時(shí)間內(nèi)接收碼字有 2個(gè)，這 2個(gè)碼字為 01， 00。 4條路徑上可能發(fā)送的 2個(gè)碼字序列分別與接收的 2個(gè)碼字比較，得到 4條路徑的碼距分別為 2，保留這 4條路徑及相應(yīng)的碼距，被保留下來的路徑稱為幸存路徑。見圖 (a)。 第 10章 信道編碼 圖 (2， 1， 2)卷積碼的維持比譯碼過程 第 10章 信道編碼 應(yīng)用步驟 (2)。觀察格狀圖 ，從 j=2時(shí)刻的 4個(gè)狀態(tài)到達(dá) j=3時(shí)刻的 4個(gè)狀態(tài)共有 8條路徑，從狀態(tài) a出發(fā)的 2條路徑上的碼字分別為 00和 11，和這期間接收碼字 01相比，碼距分別為 1和 1，分別加到 a狀態(tài)前面這段路徑的碼距上，得到 2條延長路徑 000000和 000011的碼距，它們都等于 2，一條到達(dá) j=3時(shí)刻的 a狀態(tài)，另一條到達(dá) j=3 b狀態(tài)。用相同的方法求得從 j=2時(shí)刻的 b、 c、 d出發(fā)到達(dá) j=3時(shí)刻各狀態(tài)的 6條路徑的碼距，并把這些碼距分別加到前面保留路徑的碼距上，得到 6條延長路徑的碼距。各有 2條路徑到達(dá) j=3時(shí)刻的每個(gè)狀態(tài)，在到達(dá)每個(gè)狀態(tài)的 2條路徑中選擇碼距小的路徑保留下來，同樣將相應(yīng)的碼距也保留下來。見圖 (b)所示。 第 10章 信道編碼 按上述方法繼續(xù)計(jì)算到達(dá) j= j=5時(shí)刻各狀態(tài)路徑的碼距，并選擇相應(yīng)的保留路徑及碼距，見圖 (c)、 (d)。 最后，在 j=5時(shí)刻的 4條保留路徑中選擇與接收碼字碼距最(d)可見，碼距最小的路徑是aaaaaa，所對(duì)應(yīng)的發(fā)送碼字序列為 0000000000。 由此可見，通過上述維特比譯碼，接收序列中0100010000中的兩位錯(cuò)得到了糾正。 第 10章 信道編碼 交織碼與級(jí)聯(lián)碼 從發(fā)生錯(cuò)誤的類型來分，信道可分為三類： (1) 隨機(jī)信道，產(chǎn)生隨機(jī)錯(cuò)誤的信道。如白噪聲信道。 (2) 突發(fā)信道，產(chǎn)生突發(fā)錯(cuò)誤的信道。如瑞利衰落信道。 (3) 混合信道，既產(chǎn)生隨機(jī)錯(cuò)誤又產(chǎn)生突發(fā)錯(cuò)誤的信道。 第 10章 信道編碼 交織碼 交織碼又稱交錯(cuò)碼，是一種能糾正突發(fā)錯(cuò)誤的碼。它利用糾隨機(jī)錯(cuò)誤的碼，以交錯(cuò)的方法來構(gòu)造碼字。把糾隨機(jī)錯(cuò)誤的 (n, k)線性分組碼的 m個(gè)碼字，排成 m行的一個(gè)碼陣，該碼陣稱為交錯(cuò)碼陣。一個(gè)交錯(cuò)碼陣就是交錯(cuò)碼的一個(gè)碼字。交錯(cuò)碼陣中的每一行稱為交錯(cuò)碼的子碼或行碼。行數(shù) m稱為交錯(cuò)度。圖 (28， 16)交錯(cuò)碼的一個(gè)碼字。其行碼是能糾單個(gè)隨機(jī)錯(cuò)誤的 (7， 4)漢明碼，交錯(cuò)度 m=4。傳輸時(shí)按列的次序進(jìn)行，因此送往信道的交錯(cuò)碼的一個(gè)碼字為a61a62a63a64a51a52… a01a02a03a04。 第 10章 信道編碼 04142434445464031323334353630212223242526201112131415161aaaaaaaaaaaaaaaaaaaaaaaaaaaa圖 m=4的 (28， 16)交錯(cuò)碼 第 10章 信道編碼 在傳輸過程中若發(fā)生長度 b≤4的單個(gè)突發(fā)錯(cuò)誤，那么無論從哪一位開始，至多只影響圖 。接收端把收到的交錯(cuò)碼的碼字再排成如圖 ，然后逐行分別譯碼。由于每一行碼能糾正一個(gè)錯(cuò)誤，故四行譯完后，就可把接收碼字中 b≤4的突發(fā)錯(cuò)誤糾正過來。 顯然，若要糾正較長的突發(fā)錯(cuò)誤，則可把碼陣中的行數(shù)增加，即增大交錯(cuò)度。一般，一個(gè) (n, k)碼能糾正 t個(gè)隨機(jī)錯(cuò)誤，按照上述方法交錯(cuò)，即可得到一個(gè) (nm, km)交錯(cuò)碼。該交錯(cuò)碼能糾正長度 b≤mt的單個(gè)突發(fā)錯(cuò)誤。 第 10章 信道編碼 級(jí)聯(lián)碼 在某些糾錯(cuò)要求比較高的系統(tǒng)中，可采用約束度非常長的卷積碼或級(jí)聯(lián)碼。當(dāng)約束度很長時(shí)，卷積碼的譯碼要采用序列譯碼，設(shè)備相對(duì)較為復(fù)雜。常用的一種編碼方案是采用級(jí)聯(lián)碼。圖 。 第 10章 信道編碼 圖 級(jí)聯(lián)編碼 第 10章 信道編碼 圖 ：外碼、交織碼和內(nèi)碼。外碼通常使用線性分組碼；內(nèi)碼通常采用約束度較小的卷積碼，卷積碼的譯碼采用維特比譯碼方法。由于維特比譯碼易產(chǎn)生突發(fā)錯(cuò)誤 (錯(cuò)誤太多，無法糾正時(shí) )，所以在外碼和內(nèi)碼之間增加交織編碼的目的是將