【正文】 ?狀態(tài)圖 前一狀態(tài) b3 b2 當(dāng)前輸入 b1 輸出 c1c2c3 下一狀態(tài) b3 b2 a (00) 0 1 000 111 a (00) b (01) b (01) 0 1 001 110 c (10) d (11) c (10) 0 1 011 100 a (00) b (01) d (11) 0 1 010 101 c (10) d (11) 321331211bbbcbbcbc??????1 2 3 b3 b1 輸入 b2 編碼輸出 c2 c1 c3 a b c d 000 111 101 110 010 011 100 001 56 ? (3, 1, 2)卷積碼網(wǎng)格圖 ?網(wǎng)格圖中的編碼路徑舉例 ?輸入信息位為 1101時 ?輸出編碼序列是： 111 110 010 100 011… 110 110 110 110 011 011 011 010 010 010 101 101 101 001 001 001 001 a b c d a b c d 000 000 000 000 000 111 111 111 111 111 100 100 100 a b c d 000 111 101 110 010 011 100 001 a b c d a b c d 110 010 001 111 100 57 ? 維特比算法 ?基本原理：將接收到的序列和所有可能的發(fā)送序列作比較，選擇其中漢明距離最小的序列當(dāng)作是現(xiàn)在的發(fā)送序列 ?例：設(shè)卷積碼為 (n, k, m) = (3, 1, 2)碼 ? 現(xiàn)在的發(fā)送信息位為 1101 ?為了使移存器中的信息位全部移出，在信息位后面加入了 3個“ 0”，即 1101000 ?編碼后的發(fā)送序列： 111 110 010 100 001 011 000 ?接收序列： 111 010 010 110 001 011 000 (紅色為錯碼 ) ?由于這是一個 (3, 1, 2)卷積碼，發(fā)送序列的約束長度為 N = m + 1 ＝ 3，所以首先需考察 3個信息段，即考察 3n ＝ 9比特，即接收序列前 9位“ 111 010 010”。 58 ?解碼第 1步 ?由網(wǎng)格圖可見，沿路徑每一級有 4種狀態(tài) a, b, c和 d。每種狀態(tài)只有兩條路徑可以到達。故 4種狀態(tài)共有 8條到達路徑。 ?比較網(wǎng)格圖中的這 8條路徑和接收序列之間的漢明距離。例如，由出發(fā)點狀態(tài) a經(jīng)過 3級路徑后到達狀態(tài) a的兩條路徑中上面一條為“ 000 000 000”。它和接收序列“ 111 010 010”的漢明距離等于 5；下面一條為“ 111 001 011”,它和接收序列的漢明距離等于 3。 110 110 110 110 011 011 011 010 010 010 101 101 101 001 001 001 001 a b c d a b c d 000 000 000 000 000 111 111 111 111 111 100 100 100 59 ?將這 8個比較結(jié)果列表如下： ?比較到達每個狀態(tài)的兩條路徑的漢明距離，將距離小的一條路徑保留，稱為幸存路徑。這樣，就剩下 4條路徑了，即表中第 2, 4, 6和 8條路徑。 序號 路徑 對應(yīng)序列 漢明距離 幸存否？ 1 aaaa 000 000 000 5 否 2 abca 111 001 011 3 是 3 aaab 000 000 111 6 否 4 abcb 111 001 100 4 是 5 aabc 000 111 001 7 否 6 abdc 111 110 010 1 是 7 aabd 000 111 110 6 否 8 abdd 111 110 101 4 是 60 ?解碼第 2步：繼續(xù)考察接收序列中的后繼 3個比特“ 110” ?計算 4條幸存路徑上增加 1級后的 8條可能路徑的漢明距離。計算結(jié)果列于下表中。 ?表中總距離最小為 2，其路徑是 abdc+b，相應(yīng)序列為111 110 010 100。它和發(fā)送序列相同，故對應(yīng)發(fā)送信息位 1101。 序號 路徑 原幸存路徑的距離 新增 路徑段 新增距離 總距離 幸存否？ 1 abca+a 3 aa 2 5 否 2 abdc+a 1 ca 2 3 是 3 abca+b 3 ab 1 4 否 4 abdc+b 1 cb 1 2 是 5 abcb+c 4 bc 3 7 否 6 abdd+c 4 dc 1 5 是 7 abcb+d 4 bd 0 4 是 8 abdd+d 4 dd 2 6 否 61 ?按照上表中的幸存路徑畫出的網(wǎng)格圖示于下圖中。 ?圖中粗線路徑是距漢明離最小（等于 2）的路徑。 a b c d 011 010 010 101 001 a b c d 111 100 100 110 110 62 ?在編碼時，信息位后面加了 3個“ 0”。若把這 3個“ 0”仍然看作是信息位，則可以按照上述算法繼續(xù)解碼。這樣得到的幸存路徑網(wǎng)格圖示于下圖中。圖中的粗線仍然是漢明距離最小的路徑。 110 011 010 010 101 101 001 001 a b c d a b c d 000 111 100 100 000 011 011 001 101 63 ?若已知這 3個碼元是（為結(jié)尾而補充的）“ 0”，則在解碼時就預(yù)先知道在接收這 3個“ 0”碼元后，路徑必然應(yīng)該回到狀態(tài) a。而由圖可見， 只有兩條路徑可以回到 a狀態(tài)。所以，這時上圖可以簡化成： 110 011 010 010 101 101 001 001 a b c d a b c d 000 111 100 100 000 011 011 001 110 011 010 010 101 101 001 001 a b c d a b c d 000 111 100 100 000 011 011 001 101 64 ?在上例中卷積碼的約束長度為 N = 3，需要存儲和計算 8條路徑的參量。 ?由此可見，維特比算法的復(fù)雜度隨約束長度 N按指數(shù)形式2N增長。故維特比算法適合約束長度較小（ N ? 10）的編碼。對于約束長度大的卷積碼，可以采用其他解碼算法， 65 Turbo碼 ? 基本原理： ?復(fù)合編碼：將兩種或多種簡單的編碼組合成復(fù)合編碼。 ?鏈接碼：鏈接碼是復(fù)合編碼的一種，它包括一個內(nèi)（部）碼和一個外（部）碼，如下圖所示： ?內(nèi)碼是二進制分組碼或卷積碼，而典型的外碼則是多進制的 RS碼。 ? Turbo碼：是一種特殊的鏈接碼。它在兩個并聯(lián)或串聯(lián)的編碼器之間增加一個交織器，使之具有很大的碼組長度和在低信噪比條件下得到接近理想的性能。 內(nèi)編碼器 (n, k) 調(diào) 制 器 信 道 解 制 器 內(nèi)解碼器 (n, k) 外解碼器 (N, K) 外編碼器 (N, K) 輸入 輸出 66 ? Turbo碼的基本結(jié)構(gòu) ?編碼器：由一對遞歸系統(tǒng)卷積碼（ RSCC） 編碼器和一個交織器組成。 ?輸入信息位是 bi， 輸出是 bic1ic2i， ?故碼率等于 1/3。 ? RSCC編碼器：和前面討論的卷積碼編碼器之間的主要區(qū)別是從移存器輸出到信息位輸入端之間有反饋路徑： ?上圖為碼率等于 1/2的 RSCC編碼器 RSCC 交織器 RSCC bi bi c1i c2i D D bi bi ci 67 ?交織器：基本形式是矩陣交織器。 ?交織目的：將集中出現(xiàn)的突發(fā)錯碼分散，變成隨機錯碼 ?交織原理： ?交織器由容量為 (n1)m比特的存儲器構(gòu)成。 ?碼元按行的方向輸入存儲器，再按列的方向輸出。 a11 a12 ? ? ? a1m a21 a22 ? ? ? a2m ? ? ? ? ? ? an1 an2 ? ? ? anm 68 ?卷積交織器舉例 x x x 1 2 3 4 x x x 1 2 3 4 x x x 1 x x x 1 x x x x x x (a) 第 1~4比特輸入時的狀態(tài) x x 2 5 6 7 8 3 4 x 5 6 7 8 x x 2 5 x 2 x 5 1 x x x x x (b) 第 5~8比特輸入時的狀態(tài) x 3 6 9 3 6 2 9 5 1 x x x x 9 10 11 12 10 11 12 7 8 4 x 3 6 9 (c) 第 9~12比特輸入時的狀態(tài) 10 13 7 6 9 5 4 3 2 1 14 15 16 11 12 8 13 14 15 16 4 7 10 13 4 7 10 13 (d) 第 13~16比特輸入時的狀態(tài) 交織器 解交織器 69 ?卷積交織法優(yōu)點： ?延遲時間短和需要的存儲容量小。 ?端到端的總延遲時間和兩端所需的總存儲容量均為k(N+1)N個碼元，是矩陣交織法的一半。 ? Turbo碼的性能： 由此曲線可以看到， 交織器容量大時誤碼率 低，這是因為交織范圍 大可以使交織器輸入碼 元得到更好的隨機化。 信噪比 (dB) 20 解碼后的誤碼率 交織器容量 100 101 102 103 104 105 106 107