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

本章的基本內容

?信道編碼的基本概念；

?線性分組碼；

?循環碼、BCH碼；

?卷積碼與Viterbi譯碼；

?糾突發差錯的Fire碼；

?交織碼；

?級連碼；

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

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

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

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

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

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

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

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

———以糾突發差錯為主的信道編碼；

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

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

重復碼

—不重復時:

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

結論：不重復，方法簡單，但沒有任何抗干擾能力，既不能發現，更不能糾正錯誤。

—重復一次：

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

奇偶檢驗碼其編碼規則為：

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

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

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

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

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

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

——若要發現e個獨立差錯，則要求最小碼距；

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

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

在線性碼中

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

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

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

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

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

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

其中，

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

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

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

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

一個n元碼多項式

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

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

線性分組碼

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

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

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

線性分組碼（續）

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

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

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

線性分組碼（續）

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

寫成矩陣形式

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

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

第二十一頁，共一百二十四頁，2022年，8月28日2023/1/18再改變為矩陣形式:

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

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

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

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

H·GT=OT或G·HT=O

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

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

結合上面n=7的例子,則有

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

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

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

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

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

且

其中表示發送的碼組（字）

表示傳輸中的差錯。

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

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

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

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

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

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

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

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

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

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

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

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

2）由伴隨式決定相對應的陪集首

3）將譯成其具體實現框圖如下：線性分組碼（續）

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

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

伴隨式

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

對于(7,4)碼，若

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

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

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

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

1）理論成熟：可利用成熟的代數結構深入探討其性質；

2）實現簡單；可利用循環移位特性在工程上進行編，譯碼；

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

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

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

碼多項式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移位次數第四十二頁，共一百二十四頁，2022年，8月28日2023/1/18

可見推移7位后出現周期性循環特性.

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

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

在線性分組碼中有:

對應于循環碼中有:

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

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

我們所選的多項式,由系統碼生成規則:

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

輸出開關由1倒向2，并經三次移位，將監督元跟在信息元后依次輸出得到

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

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

伴隨式

1+x+x2

伴隨矢量移位次數

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

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

·突發長度<

n-k+1的突發錯誤；

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

n-k-1)；

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

n-k)；

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

·所有奇數個錯誤；常用的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檢錯碼（續）第五十六頁，共一百二十四頁，2022年，8月28日2023/1/18

BCH

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

BCH

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

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

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

則由此生成多項式生成的循環碼稱為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碼（續）第五十八頁，共一百二十四頁，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

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

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

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

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

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

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

………

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

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

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

=2*3+1

=7個符號

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

=6個符號；

=6*4=24比特；

RS(ReedSolomen)碼(續)第六十二頁，共一百二十四頁，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)碼(續)第六十三頁，共一百二十四頁，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

卷積碼的編碼

卷積碼（續）

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

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

具體例子下列圖形給出一個（2,1,3）卷積碼編碼器結構：

卷積碼（續）

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

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

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

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

進行交織，可構成如下生成矩陣：

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

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

例：若則有：

它與卷積運算結果完全一致。

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

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

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

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

卷積碼（續）

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

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

卷積碼（續）第七十六頁，共一百二十四頁，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)卷積碼編碼器的結構圖

2)輸出碼組c=?

解：由生成多項式可給出卷積碼編碼器結構如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Viterbi譯碼實現的三種結構

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

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

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

軟判決譯碼

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

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

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

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

表2取參數a=16.8，b=1后相應整數度量值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結論：

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

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

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

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

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

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

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

級聯碼標準●

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

1987年NASA制定了級聯碼深空遙測標準CCSDS.●

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

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

內碼

外碼Pb=10-6條件下Eb/N0(dB)較標準（基準）系統功率增益(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