信息論基礎第七章信道編碼第一頁，共一百二十四頁，2022年，8月28日2023/1/18

本章的基本內(nèi)容

?信道編碼的基本概念；

?線性分組碼；

?循環(huán)碼、BCH碼；

?卷積碼與Viterbi譯碼；

?糾突發(fā)差錯的Fire碼；

?交織碼；

?級連碼；

?實際信道編碼的應用。信道編碼

第二頁，共一百二十四頁，2022年，8月28日2023/1/18

從編碼的角度看信道的分類按照差錯類型大致可分為三類：

1）獨立差錯信道：噪聲獨立隨機的影響每個碼元，白噪聲信道屬于這類信道。差錯獨立隨機出現(xiàn)；

2）突發(fā)差錯信道：差錯成片，成串出現(xiàn)，衰落信道、碼間干擾、脈沖干擾信道屬于這類；

3）混合差錯信道：差錯既有隨機獨立的，也有成片，成串出現(xiàn)的，實際的移動信道屬于此類；信道編碼的基本概念第三頁，共一百二十四頁，2022年，8月28日2023/1/18

信道編碼的分類從功能上看可分為檢錯（發(fā)現(xiàn)錯誤）碼與糾錯（不僅發(fā)現(xiàn)而且能自動糾正）碼兩類，本章中僅討論糾錯編碼。糾錯碼可根據(jù)不同信道類型相應劃分為

———以糾獨立隨機差錯為主的信道編碼；

———以糾突發(fā)差錯為主的信道編碼；

———糾混合差錯的信道編碼。信道編碼的基本概念（續(xù)）第四頁，共一百二十四頁，2022年，8月28日2023/1/18

信道編碼的任務：構(gòu)造出以最小多余度的代價換取最大抗干擾性的“好“碼；下面，首先從直觀概念出發(fā)，尋求“好“碼性能的兩個極端情況：高可靠性，低有效性的重復碼；高有效性，低可靠性的奇偶校驗碼。

重復碼

—不重復時:

信道編碼的基本概念（續(xù)）收端第五頁，共一百二十四頁，2022年，8月28日2023/1/18

結(jié)論：不重復，方法簡單，但沒有任何抗干擾能力，既不能發(fā)現(xiàn)，更不能糾正錯誤。

—重復一次：

結(jié)論：重發(fā)一次，效率降低一倍.可以換取在傳輸過程中允許產(chǎn)生一個錯誤（收端能發(fā)現(xiàn)它），但不能糾正。信道編碼的基本概念（續(xù)）發(fā)端收端能發(fā)現(xiàn)一個錯第六頁，共一百二十四頁，2022年，8月28日2023/1/18—重復二次：結(jié)論：重發(fā)二次，效率降低二倍，但換取了可糾正一個差錯或發(fā)現(xiàn)兩個差錯的性能改善。信道編碼的基本概念（續(xù)）發(fā)端收端能糾正一個錯或發(fā)現(xiàn)兩個錯第七頁，共一百二十四頁，2022年，8月28日2023/1/18

奇偶檢驗碼其編碼規(guī)則為：

其中結(jié)論：這類碼效率高，但可靠性較差，僅具有部分（奇或偶）檢錯功能。能否找到可靠性既高效率又不低的信道編碼，這就是本章中要討論的核心問題。信道編碼的基本概念（續(xù)）例：第八頁，共一百二十四頁，2022年，8月28日2023/1/18

線性分組碼從信道編碼的構(gòu)造看，往往可以劃分為：線性分組碼是其中最為常用的一類它可記為(n，k)碼，即每k位信息為一組進行編碼，可編成n位碼長的信道編碼，其中監(jiān)督（校驗）位為n-k位，編碼效率為。線性分組碼中，通常采用碼重與碼距的概念。信道編碼的基本概念（續(xù)）第九頁，共一百二十四頁，2022年，8月28日2023/1/18

線性分組碼中的碼重是指碼組C中所含“1”的數(shù)目，比如在上述(3，1)重復碼中：

線性分組碼中的碼距是指兩個碼組Ci與Cj中相應碼元不相同的數(shù)目。比如在上述重復碼中：（1，1）重復碼：，

信道編碼的基本概念（續(xù)）第十頁，共一百二十四頁，2022年，8月28日2023/1/18

（2，1）重復碼：，（3，1）重復碼：，糾正隨機獨立差錯能力與碼距之間的關系：

——若要發(fā)現(xiàn)e個獨立差錯，則要求最小碼距；

——若要糾正t個獨立差錯，則要求最小碼距；

——若要求發(fā)現(xiàn)e個又糾正t個獨立差錯，則；信道編碼的基本概念（續(xù)）第十一頁，共一百二十四頁，2022年，8月28日2023/1/18

在線性碼中

——(n，1)重復碼，隨著n的增大，可靠性不斷提高，但有效性卻在下降：；

——(n，n-1)奇偶監(jiān)督碼，隨著n的增大，其效率，很高，但是可靠性差，僅能發(fā)現(xiàn)奇（偶）數(shù)個獨立差錯；

——我們要尋找的是高可靠性即差錯率，且編碼效率的理想信道編碼，這類信道編碼理論上編碼定理已指出是存在的，但是實際上構(gòu)造起來很困難，目前已找到的絕大部分碼是當時，亦趨于0，僅有少數(shù)比如turbo碼，兩者性能都比較好。信道編碼的基本概念（續(xù)）第十二頁，共一百二十四頁，2022年，8月28日2023/1/18

目前大多數(shù)信道編碼性能卻不很理想，因此目前信道編碼的主要目標是以可靠性為主，即在尋求抗干擾強的碼的基礎上，尋求適當?shù)挠行?，尋求和?gòu)造最小距離比較大的碼。有關線性分組碼的n種等效研究方法

所謂有限域，是指有限個元素的集合，可以進行按規(guī)定的代數(shù)四則運算，其結(jié)果仍屬于集合中的有限元素。信道編碼的基本概念（續(xù)）第十三頁，共一百二十四頁，2022年，8月28日2023/1/18

在信道編碼中，可以將碼組（字）中的每個碼元0與1的產(chǎn)生、運算規(guī)律，引用最簡單的二元有限域{0，1}來描述，稱它為二元Galois域，記為，并規(guī)定其加法與乘法運算⊙如下：顯然中，對0、1的、⊙運算是自封閉的，并可以進一步驗證這兩種運算滿足域運算的全部運算規(guī)則，故稱它為二元有限域。在一個碼組中若含有n位碼元，記為，其中每個碼元取值為0、1，遵從GF(2)運算規(guī)律。則可將碼元的GF(2)拓廣至碼組的上，即有：信道編碼的基本概念（續(xù)）第十四頁，共一百二十四頁，2022年，8月28日2023/1/18

其中，

顯然對于碼組它應該遵從有限擴域的運算規(guī)則，也可看作是由擴展成的n維的矢量空間。這類引用有限域有限擴域（矢量空間）的方法，在信道編碼的理論研究中非常有用，即可引用有限域理論分析研究信道編碼的性質(zhì)，尋找性能好的信道編碼等等。

信道編碼的基本概念（續(xù)）第十五頁，共一百二十四頁，2022年，8月28日2023/1/18

在信道編碼的工程構(gòu)造上往往引用另一種等效的概念，即模多項式分析方法更為方便。

信道編碼的基本概念（續(xù)）一個n元碼組（字）

一個n元碼多項式

一一對應同構(gòu)映射第十六頁，共一百二十四頁，2022年，8月28日2023/1/18

線性分組碼中的線性是指編碼規(guī)律即碼元之間的約束關系是線性的，而分組則是對編碼方法而言，即編碼是將每k個信息為分為一組進行獨立處理——編碼，編成長度為n位（n>k）的二進制碼組。

線性分組碼

第十七頁，共一百二十四頁，2022年，8月28日2023/1/18

按數(shù)學上更為一般的定義可表示為：，其中n>k，若f進一步滿足下列線性關系：其中：

由上述定義，可見線性分組碼f可看成：

線性分組碼（續(xù)）

——線性空間的變換——有限域空間的變換第十八頁，共一百二十四頁，2022年，8月28日2023/1/18

線性分組碼是分組碼中最重要最有實用價值的一個子類，下面將從具體例子入手，闡明它的一些基本概念。

例：以（7，3）二元線性分組碼為例，其中：，，，這時輸入編碼器的信息分成三個一組，即，它可按下列線性方程組編碼：

線性分組碼（續(xù)）

第十九頁，共一百二十四頁，2022年，8月28日2023/1/18

寫成矩陣形式

稱G為生成矩陣，若即能分解出單位方陣為子陣，且I的位置可任意，則稱為系統(tǒng)碼（或組織碼）若將上述監(jiān)督線性方程組改寫為:線性分組碼（續(xù)）

第二十頁，共一百二十四頁，2022年，8月28日2023/1/18即線性分組碼（續(xù)）

第二十一頁，共一百二十四頁，2022年，8月28日2023/1/18再改變?yōu)榫仃囆问?

即H·CT=OT(P┆I)·CT=OT

稱H為監(jiān)督(校驗)矩陣，若H=(P┆I)，即能分解出單位方陣為子陣，且I的位置可任意，則稱C為系統(tǒng)（組織）碼。線性分組碼（續(xù)）

第二十二頁，共一百二十四頁，2022年，8月28日2023/1/18

生成矩陣G一般用于發(fā)端編碼，而監(jiān)督矩陣H則一般用于接收端的譯碼。由于生成矩陣G中的每一行及其線性組合都是線性（n,k）碼的碼組（字），因此有：

H·GT=OT或G·HT=O

它說明矩陣G與H互為零化空間。由線性空間理論，一個n維的線性空間Vn可以分解為一對互為對偶的正交子空間Vk與Vn-k。即：線性分組碼（續(xù)）

互為對偶碼可構(gòu)成(7,3)線性分組碼可構(gòu)成(7,4)線性分組碼第二十三頁，共一百二十四頁，2022年，8月28日2023/1/18

結(jié)合上面n=7的例子,則有

顯然有：(7,3)碼的生成矩陣G3就是(7,4)碼監(jiān)督矩陣H’3

，(7,3)碼的監(jiān)督矩陣H4就是(7,4)碼的生成矩陣G’4采用系統(tǒng)（組織）碼來描述生成矩陣G與監(jiān)督矩陣H，僅是其中的一種。在很多情況下是采用非系統(tǒng)碼的描述方式，那么兩者之間有沒有什么實質(zhì)上的差別？線性分組碼（續(xù)）

可構(gòu)成(n,k)線性分組碼可構(gòu)成(n,n-k)線性分組碼互為對偶碼第二十四頁，共一百二十四頁，2022年，8月28日2023/1/18由線性代數(shù)理論，任何一個非系統(tǒng)的生成矩陣G均可以通過矩陣的初等變換得到相應的系統(tǒng)碼的生成矩陣G。因此，我們可以得到如下結(jié)論：任何一個線性分組（n,k）碼，均可找到一個等價的系統(tǒng)碼，而且還可以進一步證明只要在碼率R和碼長n相同的條件下，最優(yōu)的系統(tǒng)碼與最優(yōu)的線性分組碼具有相同的錯誤概率。線性分組碼特別是系統(tǒng)碼的編碼器極其簡單，其具體結(jié)構(gòu)可參見書上有關章節(jié)，這里就不再贅述。線性分組碼（續(xù)）

第二十五頁，共一百二十四頁，2022年，8月28日2023/1/18線性分組碼（續(xù)）

線性分組碼的譯碼，特別是系統(tǒng)碼也比較簡單，在數(shù)據(jù)通信中，最優(yōu)譯碼即為最小誤碼準則下的譯碼，它在信源等概率即p0=p1時，可等效為最大似然準則，當信道為BSC時，它又可等效為最小漢明距離準則，關于準則問題將在后面討論卷積碼的譯碼時進一步詳細討論。譯碼時，在接收端收到的信號為：

且

其中表示發(fā)送的碼組（字）

表示傳輸中的差錯。

第二十六頁，共一百二十四頁，2022年，8月28日2023/1/18

由監(jiān)督方程：即只要在傳輸中不產(chǎn)生差錯，即則必滿足上式。實際上傳輸中一定產(chǎn)生差錯，這時，則有且有我們稱s為伴隨子（校正子），這是由于s僅與e有關，而與碼組(字)c無關。對于一個(n,k)線性分組碼，H矩陣是一個(n-k)行n列的矩陣，所以s為一個（n-k）維的矢量。

它僅可以給出（n-k）個獨立方程組，監(jiān)督(n-k)位的差錯。然而在信線性分組碼（續(xù)）

第二十七頁，共一百二十四頁，2022年，8月28日2023/1/18線性分組碼（續(xù)）

道中傳輸?shù)牟铄ee是一個n維矢量，有可能產(chǎn)生n位差錯。因此僅上述伴隨子方程不能求解n位差錯，由于2n=2n-k×2k，半隨子方程僅能解出2n-k個差錯圖樣，也可以說有2k個差錯圖樣共用一個伴隨子方程，真正的差錯是2n-k中的某一個。在二進制對稱信道BSC條件下，最可能出現(xiàn)的錯誤圖樣是接收碼組中漢明重量最小的碼組，即非0個數(shù)最小的碼組。下面以(7,4)線性分組碼為例，不過這里的(7,4)碼不是直接與(7,3)碼互為對偶碼，而是將其對偶碼再經(jīng)過矩陣初等變換后的(7,4)碼，監(jiān)督矩陣和生成矩陣分別如下：第二十八頁，共一百二十四頁，2022年，8月28日2023/1/18線性分組碼（續(xù)）

第二十九頁，共一百二十四頁，2022年，8月28日2023/1/18線性分組碼（續(xù)）

第三十頁，共一百二十四頁，2022年，8月28日2023/1/18線性分組碼（續(xù)）

第三十一頁，共一百二十四頁，2022年，8月28日2023/1/18

按照上述規(guī)則，可以將一個（n，k）線性分組碼的譯碼，按照伴隨式的規(guī)則劃分為個行矢量乘以個列矢量所構(gòu)成的下列標準陣列：線性分組碼（續(xù)）

第三十二頁，共一百二十四頁，2022年，8月28日2023/1/18

稱這種譯碼為伴隨式譯碼，或稱為查表譯碼。它原則上適合于任何（n，k）線性分組碼。伴隨式譯碼步驟可歸納如下：

1）計算接收矢量的伴隨式：

2）由伴隨式?jīng)Q定相對應的陪集首

3）將譯成其具體實現(xiàn)框圖如下：線性分組碼（續(xù)）

第三十三頁，共一百二十四頁，2022年，8月28日2023/1/18線性分組碼（續(xù)）

第三十四頁，共一百二十四頁，2022年，8月28日2023/1/18線性分組碼（續(xù)）

伴隨式

陪集首00000000001001000000010010000000100100001100001000011000010011100000101010000001<表>(7,4)碼的陪集首集合第三十五頁，共一百二十四頁，2022年，8月28日2023/1/18

對于(7,4)碼，若

其具體運算和糾正差錯過程可參考書上的(7,4)線性分組碼譯碼電路圖。線性分組碼（續(xù)）

第三十六頁，共一百二十四頁，2022年，8月28日2023/1/18

循環(huán)碼是線性分組碼中最主要，最有適用價值的一類，它是1957年由Prange首先提出循環(huán)碼第三十七頁，共一百二十四頁，2022年，8月28日2023/1/18

基本定義：一個（n,k）線性分組碼，經(jīng)任意循環(huán)移位之后，仍然是線性分組碼，則稱它為循環(huán)碼主要特點

1）理論成熟：可利用成熟的代數(shù)結(jié)構(gòu)深入探討其性質(zhì)；

2）實現(xiàn)簡單；可利用循環(huán)移位特性在工程上進行編，譯碼；

3）循環(huán)碼的描述方式有很多，但在工程上可采用最有用的多項式的描述方法。一一對應：

n元碼組(字)n階(含0階)碼多項式

有限域多項式域模運算碼組模2運算多項式乘積運算循環(huán)碼（續(xù)）第三十八頁，共一百二十四頁，2022年，8月28日2023/1/18在多項式描述中，我們可以將“同余”（模）運算推廣到多項式中。即循環(huán)碼（續(xù)）例：第三十九頁，共一百二十四頁，2022年，8月28日2023/1/18則有下列多項式除法:循環(huán)碼（續(xù)）第四十頁，共一百二十四頁，2022年，8月28日2023/1/18下面給出(7,3)碼循環(huán)移位特性：（見下頁）循環(huán)碼（續(xù)）第四十一頁，共一百二十四頁，2022年，8月28日2023/1/18循環(huán)碼（續(xù)）碼組

碼多項式0

1011100

1+x2+x3+x41

0101110

x(1+x2+x3+x4)2

0010111

x2(1+x2+x3+x4)3

1001011

x3(1+x2+x3+x4)=1+x3+x5+x6,mod(1+x7)4

1100101

x4(1+x2+x3+x4)=1+x

+x4+x6,mod(1+x7)5

1110010

x5(1+x2+x3+x4)=1+x

+x2+x5,mod(1+x7)6

0111001

x6(1+x2+x3+x4)=x+x2+x3+x6,mod(1+x7)7

1011100

x7(1+x2+x3+x4)=1+x2+x3+x4,mod(1+x7)x0x1x2x3x4x5x6移位次數(shù)第四十二頁，共一百二十四頁，2022年，8月28日2023/1/18

可見推移7位后出現(xiàn)周期性循環(huán)特性.

下面進一步研究(7,3)循環(huán)碼生成矩陣表達式:循環(huán)碼（續(xù)）第四十三頁，共一百二十四頁，2022年，8月28日2023/1/18

可見,在循環(huán)碼中,其生成矩陣結(jié)構(gòu)更加簡化,它是由生成多項式g(x)循環(huán)推移構(gòu)成.書中給出k位信息位的一般化表達式,以及在一般情況下,當為系統(tǒng)碼時循環(huán)碼的生成矩陣表達式.有興趣者可進一步仔細閱讀.

在線性分組碼中有:

對應于循環(huán)碼中有:

例:仍以(7,3)循環(huán)碼為例:循環(huán)碼（續(xù)）第四十四頁，共一百二十四頁，2022年，8月28日2023/1/18(7,3)碼生成多項式的階次為:n-k=7-3=4,故有或者由線性分組碼的對偶性,可求得對應(7,4)碼的生成多項式與監(jiān)督多項式如下:

或循環(huán)碼（續(xù)）第四十五頁，共一百二十四頁，2022年，8月28日2023/1/18循環(huán)碼的編碼例:若輸入信息碼元為:u=(1001)即,下面將簡介最簡單的系統(tǒng)循環(huán)碼的編譯碼.仍以(7,4)系統(tǒng)循環(huán)碼為例:

我們所選的多項式,由系統(tǒng)碼生成規(guī)則:

即：循環(huán)碼（續(xù)）第四十六頁，共一百二十四頁，2022年，8月28日2023/1/18循環(huán)碼（續(xù)）第四十七頁，共一百二十四頁，2022年，8月28日2023/1/18其中最右邊的4位是信息元，這樣編碼器結(jié)構(gòu)圖如下：循環(huán)碼（續(xù)）輸入信息碼字輸出門D0D1D2第四十八頁，共一百二十四頁，2022年，8月28日2023/1/18循環(huán)碼（續(xù)）輸出碼字為:D0D1D2D2D1D01第四十九頁，共一百二十四頁，2022年，8月28日2023/1/18上述編碼過程如下：三級寄碼器的初態(tài)為000，信息元組以(即1001）分兩路,一路直接輸出，另一路送入g(x)除法電路；經(jīng)四次移位后，信息元組1001全部輸出，另一路也全部送入g(x)除法電路并完成除法電路運算。這時寄存器中的狀態(tài)為余式r(x)即監(jiān)督元

輸出開關由1倒向2，并經(jīng)三次移位，將監(jiān)督元跟在信息元后依次輸出得到

c==(0111001)。循環(huán)碼（續(xù)）第五十頁，共一百二十四頁，2022年，8月28日2023/1/18（7,4）循環(huán)碼譯碼過程如下：若即y=(1111001)

將其輸入譯碼器，其譯碼過程如下列表格所示：循環(huán)碼（續(xù)）第五十一頁，共一百二十四頁，2022年，8月28日2023/1/18循環(huán)碼（續(xù)）i次移位后伴隨矢量錯誤圖樣

伴隨式

1+x+x2

伴隨矢量移位次數(shù)

e61+x2

101

0

101

e5

111

1

101

e4x+x2011

2

101

e31+x

110

3101

e2x2

0014101e1

x010

5

101

e01

1006101e(x)s(x)s0s1

s2is0s1

s2第五十二頁，共一百二十四頁，2022年，8月28日2023/1/18生成的（7,4）循環(huán)碼譯碼器原理圖循環(huán)碼（續(xù)）第五十三頁，共一百二十四頁，2022年，8月28日2023/1/18上述譯碼器工作步驟如下：首先將移位寄存器復0，清洗到初始狀態(tài)；輸入y分兩路進入譯碼器，一路進入緩存器，另一路經(jīng)門1進入伴隨式計算電路，分別計算s0s1s2；在輸出y的同時，s0s1s2依次循環(huán)移位，無差錯時，錯誤檢測電路無輸出，最后輸出碼元與接收的y中碼元一致；有錯誤時，錯誤檢測電路輸出為1，它正好與y中的錯誤位在模2加中相遇，并自動予以糾正。這一循環(huán)譯碼器與前面線性分組（7，4）碼的譯碼器比較是實現(xiàn)結(jié)構(gòu)簡化了，在線性分組碼中，對每一種伴隨式要設計一個相對應的伴隨式計算電路，而在循環(huán)（7，4）碼中，可利用碼的循環(huán)特性共用一套設備。循環(huán)碼（續(xù)）第五十四頁，共一百二十四頁，2022年，8月28日2023/1/18

循環(huán)碼特別適合于檢測錯誤，這是由于它具有很強的檢測錯誤的能力，同時實現(xiàn)起來也較簡單；CRC一般能檢測如下錯誤：

·突發(fā)長度<

n-k+1的突發(fā)錯誤；

·大部分長度=n-k+1的突發(fā)錯誤，其中不可檢測錯誤僅占2-(

n-k-1)；

·大部分長度>n-k+1的突發(fā)錯誤，其中不可檢測錯誤僅占2-(

n-k)；

·所有與許用碼組碼距≤dmin-1的錯誤；

·所有奇數(shù)個錯誤；常用的CRC碼，已成為國際標準的有：

·CRC-12，其生成多項式：g(x)=1+x+x2+x3+x11+x12CRC檢錯碼（cyclicredundancycheck）第五十五頁，共一百二十四頁，2022年，8月28日2023/1/18·CRC-16，其生成多項式：g(x)=1+x2+x15+x16·CRC-CCITT，其生成多項式：g(x)=1+x5+x12+x16·CRC-32，其生成多項式：

g(x)=1+x+x2+x4+x5+x7+x8+x10+x11+x12+x16+x22+x23+x26+x32

其中CRC-12用于6bit字符，其余則用于8bit字符。CRC檢錯碼（續(xù)）第五十六頁，共一百二十四頁，2022年，8月28日2023/1/18

BCH

碼是一類最重要的循環(huán)碼，它能糾正多個隨機錯誤，它是1959-1960年由Hocquenghem，Bose與Chandari三位學者獨立發(fā)現(xiàn)的二元線性循環(huán)碼。人們將三人名字的字頭BCH命名為BCH碼。

BCH

碼具有糾錯能力強，構(gòu)造方便，編、譯碼易于實現(xiàn)的一系列優(yōu)點。我們這里不討論BCH碼的理論與性質(zhì)，因為它要涉及更深的近世代數(shù)的群、環(huán)、域的知識；重點側(cè)重于對BCH碼的工程上的使用，即利用已知的BCH碼表格，構(gòu)造對應的生成多項式。若循環(huán)碼生成多項式為：

g(x)=LCM[m1(x),m3(x),……m2t-1(x)]

這里t為糾錯的位數(shù)，mi(x)為素多項式，LCM為求最小公倍數(shù)。BCH碼第五十七頁，共一百二十四頁，2022年，8月28日2023/1/18

則由此生成多項式生成的循環(huán)碼稱為BCH碼，其最小距：dmin≥d0=2t+1(d0為設計碼距)，它能糾正t個隨機獨立差錯。

BCH碼的碼長為n=2m―1或是n=2m―1的因子，通常稱前者為本原BCH碼，稱后者為非本原BCH碼。書中列出n≤127的本原BCH碼，和部分非本原BCH碼的生成多項式表與部分不可約的多項式表。例1：BCH(15，5)碼。

它是一個可糾正3個隨機獨立差錯的BCH碼，即t=3;

d≥d0=2t+1=2*3+1=7;BCH碼（續(xù)）第五十八頁，共一百二十四頁，2022年，8月28日2023/1/18

n=15=2m-1=24-1,m=4;查不可約多項式，可求得

m1(x)=(23)*8=010011=x4+x+1**

m3(x)=(37)8=011111=x4+x3+x2+x+1

m5(x)=(07)8=000111=x2+x+1

g(x)=LCM[m1(x),m3(x),m5(x)]=LCM[(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)]=x10+x8+x5+x4+x2+x+1

注：*.(x

x)8

是八進制表達式**.本節(jié)中編碼序列與以前相反，它是從高位向低位排列，其原因，這里引用的三個表格是從高向低排。BCH碼（續(xù)）第五十九頁，共一百二十四頁，2022年，8月28日2023/1/18

它是一類糾錯能力很強的特殊的非二進制BCH碼.對于任選正整數(shù)S可構(gòu)造一個相應的碼長為n=qS-1的q進制BCH碼,其中碼元符號取自有限域GF(q),而q作為某個素數(shù)的冪.當S=1，q>2時所建立的碼長n=q-1的q進制BCH碼,稱它為RS碼.當q=2m(m>1),其碼元符號取自于F(2m)的二進制RS碼可用來糾正突發(fā)差錯，它是最常用的RS碼．

RS碼的構(gòu)造一個可糾正t個符號錯誤的RS碼有如下參數(shù)：碼長：n=2m-1符號，或m(2m-1)比特；信息位：k符號，或km比特；監(jiān)督位：n-k=2t符號，或m(n-k)=2mt比特；

RS(ReedSolomen)碼第六十頁，共一百二十四頁，2022年，8月28日2023/1/18

最小碼距：dmin=d0=2t+1,或mdmin=m(2t+1)比特．RS碼的糾錯能力具有同時糾正隨機與突發(fā)差錯的能力．它可糾正的錯誤圖樣有：總長度為：b1=(t-1)m+1比特的單個突發(fā)；

總長度為：b2=(t-3)m+3比特的兩個突發(fā)；

………

總長度為：bi=(t-2i+1)m＋2i-1比特的i個突發(fā)．

RS(ReedSolomen)碼(續(xù))第六十一頁，共一百二十四頁，2022年，8月28日2023/1/18

例：試構(gòu)造一個能糾正三個符號錯誤，碼長n=15，m=４的RS碼．已知t=3，n=4，m=4；求得碼距為：d=2t+1

=2*3+1

=7個符號

=7*4=28比特；監(jiān)督位：n-k＝2t=2*3

=6個符號；

=6*4=24比特；

RS(ReedSolomen)碼(續(xù))第六十二頁，共一百二十四頁，2022年，8月28日2023/1/18

信息位：k=n-(n-k)

=15－6=9個符號；

=9*4＝36比特；碼長：n=15個符號=15*4=60比特；該碼應為：(15,9)RS碼或(15*4，9*4)

=(60,36)二進制碼

RS(ReedSolomen)碼(續(xù))第六十三頁，共一百二十四頁，2022年，8月28日2023/1/18

卷積碼是非分組碼，它與分組碼的主要差別是有記憶編碼，即在任意時段，編碼器的n個輸出不僅與此時段的k個輸入有關，而且還與存貯其中的前m個輸入有關，故卷積碼一般可表示為(n，k，m)，典型的卷積碼一般選n和k(n＜k)較小，但m值較大(m＜10左右)，以獲取高性能．

?卷積碼是1955年Elias最早提出；

?1957年Wozencraft提出了序列的譯碼法;

?1963年，Massey提出比較實用的門限譯碼法；

?1967年，Viterbi提出最大似然的Viterbi譯碼法

卷積碼第六十四頁，共一百二十四頁，2022年，8月28日2023/1/18

卷積碼的編碼

卷積碼（續(xù)）

卷積碼編碼器是由一個有k個輸入端口,n個輸出端且具有m節(jié)移位寄存器所構(gòu)成的有限狀態(tài)有記憶系統(tǒng),通常也稱它為時序網(wǎng)絡。第六十五頁，共一百二十四頁，2022年，8月28日2023/1/18描述卷積碼的方法很多，它大致可劃分為兩大類

卷積碼（續(xù)）第六十六頁，共一百二十四頁，2022年，8月28日2023/1/18

具體例子下列圖形給出一個（2,1,3）卷積碼編碼器結(jié)構(gòu)：

卷積碼（續(xù)）

若輸入信息序列為：第六十七頁，共一百二十四頁，2022年，8月28日2023/1/18

對應輸出兩碼組為：對應的編碼方程為：其中“*”表示卷積運算，故卷積碼因此而得名。而表示編碼的兩個脈沖沖擊響應。一般情況下，最后可求得

卷積碼（續(xù)）第六十八頁，共一百二十四頁，2022年，8月28日2023/1/18

卷積碼（續(xù)）若：則有至于離散卷積應在信號與系統(tǒng)中學過，不了解者可參見書中有關介紹。第六十九頁，共一百二十四頁，2022年，8月28日2023/1/18下面介紹解析法中的生成矩陣法：若將沖擊響應看成生成序列，則將該生成序列

進行交織，可構(gòu)成如下生成矩陣：

則前面的編碼方程可改寫為下列矩陣形式：若輸出信息序列為一半無限序列：則上述生成矩陣就是一個半無限的矩陣。

卷積碼（續(xù)）第七十頁，共一百二十四頁，2022年，8月28日2023/1/18

例：若則有：

它與卷積運算結(jié)果完全一致。

卷積碼（續(xù)）第七十一頁，共一百二十四頁，2022年，8月28日2023/1/18下面介紹解析法中的碼多項式法:

卷積碼（續(xù)）第七十二頁，共一百二十四頁，2022年，8月28日2023/1/18則有:

卷積碼（續(xù)）第七十三頁，共一百二十四頁，2022年，8月28日2023/1/18

它亦與前面兩種方法所求得的結(jié)果完全一致.再舉兩個例子若給出一個二元(3,2,1)卷積碼編碼器如下:

卷積碼（續(xù)）

它是由k=2兩個輸入端，n=3三個輸出端，m=1一節(jié)移位寄存器構(gòu)成的編碼器。第七十四頁，共一百二十四頁，2022年，8月28日2023/1/18若輸入，則它可分兩路并行由上述編碼器結(jié)構(gòu)圖可求出生成序列如下：

卷積碼（續(xù)）第七十五頁，共一百二十四頁，2022年，8月28日2023/1/18則

卷積碼（續(xù)）第七十六頁，共一百二十四頁，2022年，8月28日2023/1/18再給出一個(2,1,2)卷積碼的例子。若已知碼的生成多項式為：g1(x)=1+x+x2

g2(x)=1+x2

輸入信息為:u(x)=1+x2+x3+x4

試求1)卷積碼編碼器的結(jié)構(gòu)圖

2)輸出碼組c=?

解：由生成多項式可給出卷積碼編碼器結(jié)構(gòu)如下：

卷積碼（續(xù)）第七十七頁，共一百二十四頁，2022年，8月28日2023/1/18

卷積碼（續(xù)）且第七十八頁，共一百二十四頁，2022年，8月28日2023/1/18下面討論圖形表示法，首先從狀態(tài)圖入手：對于(2,1,2)卷積碼：k=1，n=2，m=2，其總狀態(tài)數(shù)為2km=21×2=22=4個，即a=00，b=10，c=01，d=11。每狀態(tài)可能輸入和輸出有2k=21=2個，用0和1表示。若輸入序列為u=(1011100…)，其狀態(tài)圖可以按以下步驟畫出：[對照（2,1,2）編碼器結(jié)構(gòu)圖]1)首先，移位寄存器復0，其狀態(tài)為002)輸入u0=1，狀態(tài)改為10，輸出

3)輸入u1=0,狀態(tài)改為01,輸出c11=1,c12=0,求得c1=（10）；

卷積碼（續(xù)）第七十九頁，共一百二十四頁，2022年，8月28日2023/1/184)輸入u2=1,狀態(tài)改為10，輸出c21=0，c22=0，求得c2=(00)；

5)輸入u3=1,狀態(tài)改為11，輸出c31=0，c32=1，求得c3=(01)；

6)輸入u4=1,狀態(tài)仍為11，輸出c41=1，c42=0，求得c4=(10)；

7)輸入u5=0,狀態(tài)改為01，輸出c51=0，c52=1，求得c5=(01)；

8)輸入u6=0,狀態(tài)改為00,輸出c61=1，c62=1，求得c6=(11)；

9)輸入u7=0,狀態(tài)仍為00，輸出c71=0，c72=0，求得c7=(00)；按以上步驟可畫出如下狀態(tài)圖:

卷積碼（續(xù)）第八十頁，共一百二十四頁，2022年，8月28日2023/1/18

再討論樹圖結(jié)構(gòu):它是由狀態(tài)圖展開成的.即按輸入信息序列u的輸入順序按時間l=0,1,2,…展開,并展示所有可能的輸入,輸出情況如下:

卷積碼（續(xù)）第八十一頁，共一百二十四頁，2022年，8月28日2023/1/18第八十二頁，共一百二十四頁，2022年，8月28日2023/1/18

由圖可見，以初始狀態(tài)s0=a=00為樹根（l=0）,若節(jié)點級數(shù)用l表示，每個節(jié)點分為兩個分支：0分支向上，1分支向下，即可求得l=0,1,2…7不斷延伸的樹狀結(jié)構(gòu)。它是按上述狀態(tài)圖按照l值展開的。對特殊的輸入信息序列u=(1011100…)相對應的輸出碼組c=(11100001100111…)圖中我們用紅線表示，且它與前面狀態(tài)中用紅線表示的結(jié)果完全一致。樹圖最大特點是按時間順序展開的（即l=0,1,2…）且能將所有時序狀態(tài)表示為不相重合的路徑，但是它也存在很大的缺點：結(jié)構(gòu)太復雜，結(jié)構(gòu)重復性太多。

卷積碼（續(xù)）第八十三頁，共一百二十四頁，2022年，8月28日2023/1/18

最后討論格圖（又稱籬笆圖）格圖的最大特點是保持了樹圖的時序展開性，同時又克服了樹圖中太復雜的缺點，它將樹圖中產(chǎn)生的重復狀態(tài)合并起來，形成格狀結(jié)構(gòu)如下：

卷積碼（續(xù)）第八十四頁，共一百二十四頁，2022年，8月28日2023/1/18

卷積碼（續(xù)）第八十五頁，共一百二十四頁，2022年，8月28日2023/1/18格圖在Viterbi譯碼中特別有用。將樹圖轉(zhuǎn)化為格圖是很方便的。在樹圖中，當l=m+1=3時，狀態(tài)a,b,c,d呈現(xiàn)重復，如果將重復狀態(tài)，折合起來加以合并，就可以得到縱深寬度（有稱高度）為2km=21*2=22=4的格狀圖。圖中實線表示輸入為“0”時所走的分支，虛線則表示輸入為“1”時所走的分支。由于格圖既能體現(xiàn)時序關系，又能較簡潔的表示狀態(tài)結(jié)構(gòu)，所以它是卷積碼的一種簡潔的表達形式。

卷積碼（續(xù)）第八十六頁，共一百二十四頁，2022年，8月28日2023/1/18

圖中粗紅線是表示輸入u=(1011100)時其對應編碼為c這一結(jié)果與前面狀態(tài)圖方式，樹圖方式所得結(jié)果完全一致。不同的信息序列在樹圖上所對應路徑完全不重合，但是在格圖上則有可能有部分重合，這樣兩個不同輸入序列，只需計算格圖中不相重合部分即可，所以在譯碼時利用格圖更加方便。

卷積碼（續(xù)）第八十七頁，共一百二十四頁，2022年，8月28日2023/1/18

卷積碼的譯碼可分為兩大類型:代數(shù)譯碼與概率譯碼.屬于代數(shù)譯碼的有Massey1963年提出的門限(或稱為大數(shù)邏輯)譯碼;屬于概率譯碼的有1957年Wozencraft提出的序列譯碼和1967年Viterbi提出的最大似然譯碼(后來人們就稱它為Viterbi譯碼).在分組碼中,我們重點介紹了代數(shù)譯碼,這里只重點介紹Viterbi譯碼.

卷積碼的譯碼第八十八頁，共一百二十四頁，2022年，8月28日2023/1/18首先介紹譯碼準則:

在數(shù)字、數(shù)據(jù)通信中常用的準則是最小平均誤碼率準則.卷積碼的譯碼（續(xù)）第八十九頁，共一百二十四頁，2022年，8月28日2023/1/18由Bayes公式：若發(fā)送碼組（字）是等概率的，這時為常數(shù)，當已知接受碼組（字）時，亦為常數(shù)，則結(jié)論：當發(fā)送碼組等概率時，最小平均誤碼率準則與最大后驗概率準則以及最大似然準則等效。對于離散無記憶信道（DMC）有：由于對數(shù)函數(shù)為單調(diào)函數(shù)，故可將其改寫為對數(shù)函數(shù)形式：卷積碼的譯碼（續(xù)）第九十頁，共一百二十四頁，2022年，8月28日2023/1/18我們稱按上述公式進行譯碼的算法為最大似然譯碼算法，同時稱為對數(shù)似然函數(shù)，有時簡稱為似然函數(shù)。進一步，對于二進制對稱信道BSC，似然函數(shù)可以進一步改寫為：

其中為與之間的漢明距離，由于且為常數(shù)，而，則有卷積碼的譯碼（續(xù)）第九十一頁，共一百二十四頁，2022年，8月28日2023/1/18

結(jié)論：對于BSC最大似然譯碼等效于最小漢明距離譯碼。ΔViterbi算法的舉例：在二進制對稱信道BSC下卷積碼譯碼的Viterbi算法就是建立在前面介紹的格圖基礎上的最小漢明距離算法，下面仍以具體例子入手來分析?！だ阂宰詈唵蔚?2,1,2)卷積碼為例若發(fā)送的信息序列為，即L=5,

經(jīng)過編碼后輸出的碼組(字)為接收到的信號序列為：卷積碼的譯碼（續(xù)）第九十二頁，共一百二十四頁，2022年，8月28日2023/1/18

在BSC下，其譯碼在格圖上的每一步的計算結(jié)果（距離圖）和累計計算結(jié)果幸存路徑圖如下述兩個圖形所示：卷積碼的譯碼（續(xù)）a=00b=10c=01d=11l=0l=1l=2l=3l=4l=5l=6l=7狀態(tài)數(shù)第九十三頁，共一百二十四頁，2022年，8月28日2023/1/18

結(jié)論:最后求得的最小漢明距離路徑如圖中粗黑線表示為:

a0b1c2b3d4d5c6a7,最小漢明距離值為2.卷積碼的譯碼（續(xù)）l=0l=1l=2l=3l=4l=5l=6l=7a=00b=10c=01d=11第九十四頁，共一百二十四頁，2022年，8月28日2023/1/18Viterbi算法由上面的例子可以總結(jié)出如下規(guī)律:

維特比算法,對于DMC信道(或BSC信道),主要體現(xiàn)在上述格形圖中尋找具有最大似然值的路徑,具體是采用迭代法進行處理.即在每一步中,它將進入每一狀態(tài)的所有路徑的度量值進行比較,保存并度量最大度量值(或最小漢明距離值),稱為幸存路徑,并丟棄其他路徑;

DMC(或BSC)中viterbi算法可歸結(jié)為如下三步:1.從時刻l=m開始,(l<m為起始狀態(tài))計算進入每一狀態(tài)的單個路徑的部分度量值,并存入每一狀態(tài)下的幸存路徑及其度量值.2.l增加1,即l=m+1,將進入某一狀態(tài)的分支度量值,與前一時段的幸存度量值相加,然后計算進入該狀態(tài)的所有最大度量的路徑(或最小漢明距離路徑)即幸存路徑及其度量,并刪去所有其它路徑.卷積碼的譯碼（續(xù)）第九十五頁，共一百二十四頁，2022年，8月28日2023/1/183.若l<L+m=5+2=7,重復步驟2,否則停止.

上述三個步驟中,1是2的初始化,3是2的延續(xù),關鍵在于第2步,它主要包括兩部分,一是對每個狀態(tài)進行度量和比較,并決定幸存路徑,另一個是記錄幸存路徑與度量值.上述三步的進一步細化:1.

從l=m=2時刻開始,使網(wǎng)格圖充滿狀態(tài),將路徑存儲器(PM)和路徑度量存儲器(MM)從l=0到l=m=2進行初始化;2.

l=l+1=2+1=33.接收到新的一組數(shù)據(jù),它代表l=l+1的分支上接收符號組;4.對每一狀態(tài):

a.進行分支度量計算;卷積碼的譯碼（續(xù)）第九十六頁，共一百二十四頁，2022年，8月28日2023/1/18

b.從MM中取出第l時刻幸存路徑度量值;

c.進行累加---比較---選擇(ACS)基本運算,產(chǎn)生新的幸存路徑;

d.將新的幸存路徑及其度量值分別存入PM及MM中;5.如果l<L+m=5+2=7,回到步驟2,否則繼續(xù)往下做;6.求MM中最大似然值對應路徑,從PM中輸出判決結(jié)果.

Viterbi譯碼實現(xiàn)的三種結(jié)構(gòu)

1.全并行,即采用2m個ACS單元同時運算并作PM、MM操作；

2.全串行，即采用一個ACS單元進行2m次ACS與PM、MM操作；

3.時分復用方案，即部分并行，采用少于2m個ACS單元分數(shù)次完成全部2m次的ACS與相應PM、MM操作。卷積碼的譯碼（續(xù)）第九十七頁，共一百二十四頁，2022年，8月28日2023/1/18卷積碼的譯碼（續(xù)）Viterbi譯碼過程

輸入u=(1011100)后兩位為尾比特.

以(2,1,2)碼為例,BSC下

c=(11,10,00,01,10,01,11)

y=(10,10,00,01,11,01,10)具體步驟如下:00漢明距離d(d’)估值1)l=01,y0=10,S0010

S11111第九十八頁，共一百二十四頁，2022年，8月28日2023/1/18卷積碼的譯碼（續(xù)）第九十九頁，共一百二十四頁，2022年，8月28日2023/1/18卷積碼的譯碼（續(xù)）第一百頁，共一百二十四頁，2022年，8月28日2023/1/18

軟判決譯碼

為了提高譯碼性能可將硬判決改為軟判決，即多電平判決，這是由于兩電平的硬判決在強噪聲時容易丟失有用信息，而采用多電平軟判決后大約可改進1.5-2dB，在具體實現(xiàn)時，考慮到實現(xiàn)的復雜度，一般可取4-8電平。

軟判決的依據(jù)：對最大似然比作下列線性變換：卷積碼的譯碼（續(xù)）第一百零一頁，共一百二十四頁，2022年，8月28日2023/1/18其中：a為任意正整數(shù)，b為任意實數(shù)；

實例：以(2,1,2)卷積碼為例，通過DMC信道采用簡單的四電平軟判決。

1）DMC信道轉(zhuǎn)移圖如下：卷積碼的譯碼（續(xù)）第一百零二頁，共一百二十四頁，2022年，8月28日2023/1/18表1經(jīng)DMC轉(zhuǎn)移后的對數(shù)比特值卷積碼的譯碼（續(xù)）2）DMC轉(zhuǎn)移后的對數(shù)比特度量值以及經(jīng)過上面公式線性變換后的值用下列表格表示：O1O2I2I10-0.4-0.52-0.70-11-1-0.7-0.52-0.40

表2取參數(shù)a=16.8，b=1后相應整數(shù)度量值O1O2I2I1010850105810第一百零三頁，共一百二十四頁，2022年，8月28日2023/1/183）若輸入：u=（1011100），后兩位為尾比特，

DMC輸入：c=（11，10，00，01，10，01，11）

DMC輸出：y=（I2O1，I1O1，O1O2，O1I1，I1I2

，O2I1，I2O2）軟判決譯碼輸出：u=（1011100）=

u結(jié)論：

--軟與硬判決譯碼過程完全類似；不同之處有：

--信道模型不一樣，硬為BSC，軟為DMC；

--度量值及準則不一樣，一個為最小漢明，一個為最大似然；

--軟比硬復雜度增加不多，但性能卻有1.5～2dB改善；卷積碼的譯碼（續(xù)）第一百零四頁，共一百二十四頁，2022年，8月28日2023/1/18引言●級聯(lián)碼是由短碼構(gòu)造長碼的一種有效的方法,它是由Forney首先提出.●級聯(lián)碼可用于糾正混合差錯.即既有獨立隨機差錯又有突發(fā)差錯,且糾錯能力很強.●級聯(lián)碼是由內(nèi)外兩個短碼構(gòu)成一個長碼,內(nèi)碼可設計成一般復雜度以糾正隨機獨立差錯為主的糾錯碼,外碼可設計為較復雜,且糾錯能力較強,即可糾正內(nèi)碼不能糾正的隨機獨立差錯和部分突發(fā)差錯的碼.●原則上,無論是內(nèi)碼還是外碼,均可采用分組碼和卷積碼,但目前采用最多的是內(nèi)碼為卷積碼,外碼是RS分組碼.級聯(lián)編碼第一百零五頁，共一百二十四頁，2022年，8月28日2023/1/18基本原理●它由兩個短碼即內(nèi)碼與外碼串接而成:即(n,k)=[n1×

n2,k1×k2]=[(n1k1)(n2

k2)]●稱(n1,k1)為內(nèi)碼,(n2,k2)為外碼。一組k位信息可分解為k2個字節(jié)，而每個字節(jié)中有k1個信息位,(n1,k1)可糾字節(jié)內(nèi)獨立隨機差錯,一般由卷積碼構(gòu)成,稱為內(nèi)碼;(n2,k2)可糾正余下的差錯以及字節(jié)間的突發(fā)差錯.一般由糾錯能力強的RS碼構(gòu)成,稱為外碼。級聯(lián)編碼（續(xù)）第一百零六頁，共一百二十四頁，2022年，8月28日2023/1/18基本方框圖級聯(lián)編碼（續(xù)）●若(n1,k1)最小距離為d1

(n2,k2)最小距離為d2,串接后級聯(lián)碼最小距離d≥d1×d2,●級聯(lián)碼是由內(nèi)外碼串接而成,又稱為串行級聯(lián)碼,其設備僅是兩者的制機組合,它要比采用一個長碼時所需的設備簡單得多.第一百零七頁，共一百二十四頁，2022年，8月28日2023/1/18

級聯(lián)碼標準●

最早采用級聯(lián)碼的是八十年代美國宇航局NASA,將它用于深空遙測數(shù)據(jù)的糾錯.●

1987年NASA制定了級聯(lián)碼深空遙測標準CCSDS.●

典型標準級聯(lián)碼系統(tǒng)框圖如下:級聯(lián)編碼（續(xù)）第一百零八頁，共一百二十四頁，2022年，8月28日2023/1/181984年,NASA采用上述的典型標準，其中：內(nèi)碼為(2,1,7)卷積碼,外碼為(255,223)RS碼.而交織器深度大約為2～8個外碼塊,其性能很優(yōu)異,當Eb／N0=2.53dB時，誤碼率Pb≤10-6。

級聯(lián)碼的性能下面給出在Pb≤10-6條件下(Pb為誤比特率)，一些級聯(lián)碼的性能:級聯(lián)編碼（續(xù)）第一百零九頁，共一百二十四頁，2022年，8月28日2023/1/18

內(nèi)碼

外碼Pb=10-6條件下Eb/N0(dB)較標準（基準）系統(tǒng)功率增益(dB)(4,1,5)(255,223)0.911.62(5,1,14)(1023,927)0.571.96(5,1,15)(1023,959)0.502.03(6,1,14)(1023