信息論基礎(chǔ)第七章信道編碼

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

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

?信道編碼的基本概念；

?線性分組碼；

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

?卷積碼與Viterbi譯碼；

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

?交織碼；

?級(jí)連碼；

?實(shí)際信道編碼的應(yīng)用。信道編碼

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

從編碼的角度看信道的分類(lèi)按照差錯(cuò)類(lèi)型大致可分為三類(lèi)：

1）獨(dú)立差錯(cuò)信道：噪聲獨(dú)立隨機(jī)的影響每個(gè)碼元，白噪聲信道屬于這類(lèi)信道。差錯(cuò)獨(dú)立隨機(jī)出現(xiàn)；

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

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

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

———以糾獨(dú)立隨機(jī)差錯(cuò)為主的信道編碼；

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

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

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

重復(fù)碼

—不重復(fù)時(shí):

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

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

—重復(fù)一次：

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

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

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

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

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

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

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

（2，1）重復(fù)碼：，（3，1）重復(fù)碼：，糾正隨機(jī)獨(dú)立差錯(cuò)能力與碼距之間的關(guān)系：

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

——若要糾正t個(gè)獨(dú)立差錯(cuò)，則要求最小碼距；

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

在線性碼中

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

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

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

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

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

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

其中，

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

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

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

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

一個(gè)n元碼多項(xiàng)式

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

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

線性分組碼

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

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

由上述定義，可見(jiàn)線性分組碼f可看成：

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

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

線性分組碼是分組碼中最重要最有實(shí)用價(jià)值的一個(gè)子類(lèi)，下面將從具體例子入手，闡明它的一些基本概念。

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

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

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

寫(xiě)成矩陣形式

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

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

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

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

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

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

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

H·GT=OT或G·HT=O

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

互為對(duì)偶碼可構(gòu)成(7,3)線性分組碼可構(gòu)成(7,4)線性分組碼第二十三頁(yè)，共一百二十四頁(yè)，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)（組織）碼來(lái)描述生成矩陣G與監(jiān)督矩陣H，僅是其中的一種。在很多情況下是采用非系統(tǒng)碼的描述方式，那么兩者之間有沒(méi)有什么實(shí)質(zhì)上的差別？線性分組碼（續(xù)）

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

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

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

且

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

表示傳輸中的差錯(cuò)。

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

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

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

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

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

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

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

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

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

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

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

1）計(jì)算接收矢量的伴隨式：

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

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

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

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

伴隨式

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

對(duì)于(7,4)碼，若

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

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

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

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

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

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

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

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

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

碼多項(xiàng)式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ù)第四十二頁(yè)，共一百二十四頁(yè)，2022年，8月28日2023/1/18

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

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

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

在線性分組碼中有:

對(duì)應(yīng)于循環(huán)碼中有:

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

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

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

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

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

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

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

伴隨式

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

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

·突發(fā)長(zhǎng)度<

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

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

n-k-1)；

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

n-k)；

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

·所有奇數(shù)個(gè)錯(cuò)誤；常用的CRC碼，已成為國(guó)際標(biāo)準(zhǔn)的有：

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

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

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

BCH

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

BCH

碼具有糾錯(cuò)能力強(qiáng)，構(gòu)造方便，編、譯碼易于實(shí)現(xiàn)的一系列優(yōu)點(diǎn)。我們這里不討論BCH碼的理論與性質(zhì)，因?yàn)樗婕案畹慕来鷶?shù)的群、環(huán)、域的知識(shí)；重點(diǎn)側(cè)重于對(duì)BCH碼的工程上的使用，即利用已知的BCH碼表格，構(gòu)造對(duì)應(yīng)的生成多項(xiàng)式。若循環(huán)碼生成多項(xiàng)式為：

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

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

則由此生成多項(xiàng)式生成的循環(huán)碼稱為BCH碼，其最小距：dmin≥d0=2t+1(d0為設(shè)計(jì)碼距)，它能糾正t個(gè)隨機(jī)獨(dú)立差錯(cuò)。

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

它是一個(gè)可糾正3個(gè)隨機(jī)獨(dú)立差錯(cuò)的BCH碼，即t=3;

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

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

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

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

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

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

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

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

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

………

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

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

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

=2*3+1

=7個(gè)符號(hào)

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

=6個(gè)符號(hào)；

=6*4=24比特；

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

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

=15－6=9個(gè)符號(hào)；

=9*4＝36比特；碼長(zhǎng)：n=15個(gè)符號(hào)=15*4=60比特；該碼應(yīng)為：(15,9)RS碼或(15*4，9*4)

=(60,36)二進(jìn)制碼

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

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

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

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

?1963年，Massey提出比較實(shí)用的門(mén)限譯碼法；

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

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

卷積碼的編碼

卷積碼（續(xù)）

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

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

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

卷積碼（續(xù)）

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

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

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

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

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

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

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

例：若則有：

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

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

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

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

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

卷積碼（續(xù)）

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

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

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

g2(x)=1+x2

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

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

2)輸出碼組c=?

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

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

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

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

卷積碼（續(xù)）第七十九頁(yè)，共一百二十四頁(yè)，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)；按以上步驟可畫(huà)出如下?tīng)顟B(tài)圖:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.全并行,即采用2m個(gè)ACS單元同時(shí)運(yùn)算并作PM、MM操作；

2.全串行，即采用一個(gè)ACS單元進(jìn)行2m次ACS與PM、MM操作；

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

輸入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第九十八頁(yè)，共一百二十四頁(yè)，2022年，8月28日2023/1/18卷積碼的譯碼（續(xù)）第九十九頁(yè)，共一百二十四頁(yè)，2022年，8月28日2023/1/18卷積碼的譯碼（續(xù)）第一百頁(yè)，共一百二十四頁(yè)，2022年，8月28日2023/1/18

軟判決譯碼

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

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

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

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

表2取參數(shù)a=16.8，b=1后相應(yīng)整數(shù)度量值O1O2I2I1010850105810第一百零三頁(yè)，共一百二十四頁(yè)，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é)論：

--軟與硬判決譯碼過(guò)程完全類(lèi)似；不同之處有：

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

--度量值及準(zhǔn)則不一樣，一個(gè)為最小漢明，一個(gè)為最大似然；

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

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

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

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

級(jí)聯(lián)碼標(biāo)準(zhǔn)●

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

1987年NASA制定了級(jí)聯(lián)碼深空遙測(cè)標(biāo)準(zhǔn)CCSDS.●

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

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

內(nèi)碼

外碼Pb=10-6條件下Eb/N0(dB)較標(biāo)準(zhǔn)（基準(zhǔn)）系統(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