制作：曹麗娜ccllna@163.com

美工設計：陳英技術支持：張嘉等人課件差錯控制編碼

通信原理（第7版）第11章樊昌信曹麗娜編著

本章內容第11章差錯控制編碼

基本概念—差控方式編碼原理

碼距

碼率

性能簡單實用碼—奇偶監督恒比碼

正反碼線性分組碼—漢明碼監督矩陣H、生成矩陣G

循環碼—生成多項式編譯方法BCH碼RS碼卷積碼—編譯原理代數表述幾何表述Turbo碼低密度奇偶校驗碼網格編碼調制—TCM信號的產生與解調

§11.1

概述開銷。這就好像我們運送一批玻璃杯一樣，為了保證運送途中不出現打爛玻璃杯的情況，我們通常都用一些泡沫或海棉等物將玻璃杯包裝起來，這種包裝使玻璃杯所占的容積變大，原來一部車能裝5000個玻璃杯的，包裝后就只能裝4000個了，顯然包裝的代價使運送玻璃杯的有效個數減少了。

為保證運送途中不出現打碎燈泡的情況——有效性——可靠性

通信中的情況：開銷。這就好像我們運送一批玻璃杯一樣，為了保證運送途中不出現打爛玻璃杯的情況，我們通常都用一些泡沫或海棉等物將玻璃杯包裝起來，這種包裝使玻璃杯所占的容積變大，原來一部車能裝5000個玻璃杯的，包裝后就只能裝4000個了，顯然包裝的代價使運送玻璃杯的有效個數減少了。針對乘性干擾針對加性干擾合理選擇調制/解調方法，增大發射功率—采用均衡等措施

差錯控制編碼

信道類型——根據錯碼的不同分布規律分為：

差錯控制方式：

差錯控制方式（ARQ）（FEC）——

——自動請求重發

缺點：工作在半雙工狀態，傳輸效率較低。

3種自動要求重發(ARQ)系統（1）停止等待ARQ系統系統需要雙工信道。（2）拉后ARQ系統第5組傳輸速率比第（1）種高。（3）選擇重發ARQ系統ARQ的主要缺點：碼率較高。∵用較少的監督碼元就能使誤碼率降到很低；檢錯的計算復雜度較低；檢錯用的編碼方法和加性干擾的統計特性基本無關，能適應不同特性的信道。需雙向信道來重發，不適用單向信道和一點到多點的通信系統。重發使得ARQ系統的傳輸效率降低。信道干擾嚴重時，將發生因反復重發而造成事實上的通信中斷。不適用于要求實時通信的場合，例如電話通信。ARQ的主要優點：與前向糾錯（FEC）方法相比ARQ系統的原理方框圖§11.2

糾錯編碼的基本原理規則：使碼組中“1”的個數為偶數情形1：沒有冗余——不能發現錯誤情形2：加入冗余

——可以發現錯誤

冗余?另外4個碼組許用碼組禁用碼組例許用碼組禁用碼組也不能糾正

錯誤。（奇數個錯碼）這時，能夠發現2個以下錯碼，或者糾正

1位

錯碼。例綜上所述：---信息碼元位數---編碼后碼字位數不同的編碼方法，檢錯或糾錯能力也不同。分組碼和系統碼編碼后的每組長度為n

=

k+r就是分組碼前面的例子：信息位與監督位關系：分組碼的符號：分組碼的結構：

（n，k）

碼長

(n)：碼組（碼字）中的碼元個數。

碼重(W)：碼組中“1”的數目。“

011011”

的距離為

3例

碼重和碼距

碼重為

3對于3位的編碼組，可用3維空間來說明（4個許用碼組之間）各頂點之間沿立方體各邊行走的幾何距離——碼距=2

碼距的幾何意義：對于（n，k）分組碼，有以下結論：最小碼距d0

和檢糾錯能力的關系檢ｅ個錯碼，要求：糾ｔ個錯碼，要求：糾

t

個錯碼,同時檢

e個錯碼，要求：證明：§11.3

糾錯編碼的性能系統帶寬和信噪比的矛盾右圖所示的某種編碼性能可見：不增大發送功率,就能降低誤碼率約一個半數量級。A點B點例10-610-510-410-310-210-1編碼后PeCDAB編碼前信噪比

(dB)2PSK調制可見：能節省功率2dB

——稱為編碼增益D點10-610-510-410-310-210-1編碼后PeCDAB編碼前信噪比(dB)2PSK調制C點

因此，糾錯碼主要應用于功率受限而帶寬不太受限的信道中。——付出的代價是帶寬增大。設編碼前系統工作在圖中C點，提高速率后Pe由C點升到E點。傳輸速率RB

和信噪比Eb/n0的關系若希望提高RB，則必使Eb/n0下降，誤碼率Pe增大。這時付出的代價仍是帶寬增大。10-610-510-410-310-210-1編碼后CDEAB編碼前信噪比

(dB)但采用糾錯編碼后，Pe仍可降到D點。§11.4

簡單的實用編碼11.4.1

奇偶監督碼偶數監督奇數監督

適用：檢測隨機出現的零星差錯。編碼規則：只有一位監督元（∵不知錯碼位置）很高（因為只有一位監督位）。

碼率：編出的碼字應為

：

若收到10011，檢測結果為：根據偶數監督規則：---存在錯碼若收到00011，檢測結果為：

可見，奇偶監督碼不能檢出偶數個錯碼。

例解---認為無錯1101111.4.2二維奇偶監督碼編碼規則：（方陣碼）檢測方法：計算接收碼組中“1”的數目，就可知是否有錯。11.4.3恒比碼適用：用于電報傳輸系統或其他鍵盤設備產生的字母和符號。編碼規則：(等重碼)例個許用碼組，可分別用來代表26個英文字母及其他符號。11.4.4正反碼編碼規則：設碼長n=10，其中信息位k=5，監督位r=5。其編碼規則為：——一種能夠糾錯的編碼。例譯碼方法：

=

00000校驗碼組和錯碼的關系：

按上表判決:無錯碼

∵信息位中有奇數個“1”，∴校驗碼組=00000發送碼組為1100111001糾檢能力：（n,k）線性分組碼§11.5

線性碼：按照一組線性方程構成的代數碼。

即每個碼字的監督碼元是信息碼元的線性組合。基本概念代數碼：建立在代數學基礎上的編碼。---監督關系式若S=0，認為無錯（偶監督時）；若S=1，認為有錯。若要構造具有糾錯能力的（n，k）碼，則需增加督元的數目。當“=”成立時，構造的線性分組碼稱為漢明碼校正子?構造原理只有一位監督元---檢錯漢明碼的——能糾1位錯碼的高效

線性分組碼例(7,4)漢明碼由表可見:僅當一位錯碼的位置在a2

、a4、a5或a6

時，

校正子S1為1；否則S1為

0。同理：(A)移項運算解出監督位(A)例接收端譯碼——檢錯糾錯過程以上構造的線性分組碼，稱為漢明碼。最小碼距：當n很大和r很小時，碼率Rc接近1。

編碼效率：漢明碼特點:式中的等號成立，即:d0=3（糾1或檢2）r

是不小于3的任意正整數答：最小碼距:故能糾1或檢2d0=3線性分組碼的一般原理將前面(7,4)漢明碼的監督方程：改寫為：表示成如下矩陣形式：H

---監督矩陣

簡記為H

A=[a6

a5

a4

a3

a2

a1

a0]0=[000]監督矩陣

或轉置轉置“T”r

行n

列=[PIr]r

k階矩陣r

r階方陣——典型監督矩陣H

矩陣的性質

①H

的行數等于監督位的數目r

。H的每行中“1”的位置表示相應碼元之間存在的監督關系。(7，4)碼r=3

②

H的各行應該是線性無關的，否則得不到r個線性無關的監督關系式。若一矩陣能寫成典型陣形式[PIr]，則其各行一定是線性無關的。將上面漢明碼例子中的監督位公式：改寫成矩陣形式：G

---生成矩陣

或者寫成：P陣式中，Q為一個k

r階矩陣，它為P的轉置，即:

Q=PTP陣Q陣將Q的左邊加上1個kk階單位方陣，就構成矩陣:生成矩陣，或者因此，若找到了碼的G，則編碼的方法就完全確定了。具有[IkQ]形式的稱為典型生成矩陣。由典型G得到的碼稱為系統碼。稱為典型生成矩陣碼組A中，信息位的位置不變，監督位附在其后。∵由它可以產生整個碼組，即有:G

矩陣的性質

①

G矩陣的各行是線性無關的。∵由式可以看出:任一碼組A都是G的各行的線性組合。G共有k行，若它們線性無關，則可以組合出2k種不同的碼組A。它恰是有k位信息位的全部碼組。G和H

的關系

校正子與錯誤圖樣設發送碼組為一個n列的行矩陣A，

接收碼組的行矩陣B則發送碼組和接收碼組之差就是錯碼矩陣（錯誤圖樣）：式中(模2)A=B+E例在接收端，若能求出錯誤圖樣E就能恢復出發送碼組A

，即∵任一發送碼組A

都應滿足式：∴對于接收碼組B，可通過計算:來進行檢測。將B=A+E代入上式，可得 0若,

則S為0，否則S不為0。因此，可根據S

是否為0判斷接收碼組是否出錯!由以上分析可知，（n,k)線性分組碼譯碼的三個步驟：2)由S找到錯誤圖樣E；3)由公式A=B+E

得到譯碼器譯出的碼組。（n,k)線性分組碼譯碼的三個步驟：

①封閉性A1和A2(A1+A2)證明：若A1和A2是兩個碼組，則有A1

HT=0和A2

HT=0，將兩式相加，有A1

HT+A2

HT=(A1+A2)HT=0②

最小距離（證畢）線性分組碼的性質信息位a6~

a3監督位a2a1a0信息位a6~

a3監督位a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111表中所列的(7,4)漢明碼的最小碼距d0=？d0=3糾1或檢2根據性質②只需找最小碼重無需兩兩碼組比較循環碼西安電子科技大學通信工程學院

課件制作：曹麗娜它除了具有線性分組碼的一般性質外，還具有循環性。§11.6

表中的第2

碼組向右移一位即得到第

5碼組；(7,3)循環碼11.6.1

循環碼原理表中的第6

碼組向右移一位即得到第3碼組。注意：碼字（1100101）的多項式可表示為：

碼多項式多項式的系數就是碼組中的各碼元，x

僅是碼元位置標記。n=7時

例——碼字（碼組）的多項式表示1.碼多項式的按模運算一般說來，若一個整數m可以表示為

（Q

為整數）

m

p

(模n)則在模n

運算下，有

碼多項式的按模運算：

或則式中，碼多項式系數之間的加法和乘法仍按模2運算。例解運算過程：即有則有這是因為，A(x)正是A(x)代表的碼組向左循環移位i次的結果。循環碼的碼多項式

則A(x)也是該編碼中的一個許用碼組。

例循環碼組，其碼長n=7。現給定i=3，則01011101100101左移i位3由上述分析可見:2.

循環碼的生成矩陣G

生成矩陣

G可由k

個線性無關的碼組構成。引思：那么，如何尋找這k個線性無關的碼組呢？因此，用這ｋ個線性無關的碼組可構成該循環碼的生成矩陣G

，即r=n-k=7-3=4，解例碼組中唯一一個4次碼多項式代表的或據此，可以寫出此循環碼多項式A(x):∵任一循環碼多項式A(x)

都是g(x)的倍式，∴可以寫成

而生成多項式g(x)本身也是一個碼組，即有A

(x)=g(x)A(x)

=h(x)g(x)∵碼組A(x)是一個(n–k)次多項式，故xkA(x)是一個n次多項式。可知，

xkA(x)在模(xn+1)運算下也是一個碼組，故可寫成由式上式左端分子和分母都是n次多項式，故商式Q(x)=1。上式可化成將和代入上式，化簡后得到A(x)=g(x)A(x)

=h(x)g(x)求(7,3)循環碼的生成多項式g(x)。例將(x7+1)進行因式分解：解：n–k即有或11.6.2循環碼的編解碼方法1.循環碼的編碼設

信息碼(an-1

an-2…an-k)的多項式為：

m(x)=an-1xk-1+an-2

xk-2+?+an-k——其最高次數為k-1則循環碼的多項式為：A(x)=

A(x)=m(x)g(x)即（1）用xn-k乘m(x)，得到

xn-k

m(x)

（2）作g(x)除xn-k

m(x)，即

——將信元左移（n–k）位，附上（n–k）個0，預留給督元。——得到余式

r(x)，作為監督碼元

——即得循環碼的碼多項式。系統循環碼的編碼步驟：（3）作A(x)

=

xn-k

m(x)+r(x)——通常是非系統碼例可見編碼電路：可采用(n–k)級移位寄存器組成的除法電路實現。設1xx2x4A(x)m(x)例如，上例(7,3)循環碼的生成多項式g(x)=x4+x2+x+1，

其編碼電路：2.循環碼的解碼目的：檢錯和糾錯。若能除盡，則無錯；若除不盡而有余項，則表示在傳輸中發生錯誤。檢錯：糾錯：11.6.3截短循環碼例：構造一個能夠糾正1位錯碼的(13,9)碼。可由(15,11)循環碼的碼組中選出前兩信息位均為“0”的碼組，構成一個新的碼組集合。在發送時不發送這兩位“0”。于是發送碼組成為(13,9)截短循環碼。截短目的：在設計糾錯編碼方案時，若找不到合適的碼長n及信息位k

時，可以把循環碼的碼長截短以得到符合要求的編碼。截短方法：設給定一個(n,k)循環碼，它共有2k種碼組，現使其前i

(0<i<k)個信息位全為“0”，于是它變成僅有2k-

i

種碼組。然后從中刪去這i位全“0”的信息位，最終得到一個(n

–i

,k

–i)的線性碼——截短循環碼。截短循環碼性能：循環碼截短前后至少具有相同的糾錯能力，并且編解碼方法仍和截短前的方法一樣。11.6.4BCH碼——解決了生成多項式與糾錯能力的關系問題，可以在給定糾錯能力要求的條件下尋找到碼的生成多項式。——有了生成多項式，編碼的基本問題就隨之解決了。BCH碼的重要性:何謂BCH碼？BCH碼的分類：漢明碼是能夠糾正單個隨機錯誤的碼。可以證明，具有循環性質的漢明碼就是能糾正單個隨機錯誤的本原BCH碼。BCH碼的性能：碼長n

與監督位、糾錯個數t之間的關系：

對于正整數m(m

3)和正整數t

<m/2，必定存在一個碼長為

n=2m–1，監督位為n–k

mt，能糾正所有不多于t個隨機錯誤的BCH碼。若碼長n=(2m-1)/i（i>1，且除得盡(2m-1)），則為非本原BCH碼。BCH碼的設計：在工程設計中，一般不需要用計算方法去尋找生成多項式g(x)。因為前人早已將尋找到的g(x)列成表，故可以用查表法找到所需的生成多項式。教材353頁的表11-7給出了碼長n127的二進制本原BCH碼生成多項式。nktg(x)nktg(x)17212333419121222212232472716635343514566471334765657324534046524443073357107613543000671717773537在上表中的(23,12)碼稱為戈萊(Golay)碼。其最小碼距為7，能糾3個隨機錯碼；其生成多項式系數(5343)8=(101011100011)2，對應g(x)=x11+x9+x7+x6+x5+x+1，且解碼容易，實際應用較多。BCH碼的長度都為奇數。在應用中，為了得到偶數長度的碼，并增大檢錯能力，可以在BCH碼生成多項式中乘上一個因式(x+1)，從而得到擴展BCH碼(n+1,k)。擴展BCH碼相當于在原BCH碼上增加了一個校驗位，因此碼距比原BCH碼增加1。擴展BCH碼已經不再具有循環性。例如，廣泛實用的擴展戈萊碼(24,12)，其最小碼距為8，碼率為1/2，能夠糾3個錯碼和檢4個錯碼。它比漢明碼的糾錯能力強很多，付出的代價是解碼更復雜，碼率也比漢明碼低。此外，它不再是循環碼了。擴展BCH碼：11.6.5RS碼——它是一類具有很強糾錯能力的多進制BCH碼。——由里德和索洛蒙(Reed–Solomon)提出。

一個能夠糾t個錯誤符號的m進制的RS碼有如下參數：最小碼距：d0=2t+1個符號，或q（2t+1）比特碼組長度：n=m–1=2q–1個符號，督元長度：

r=n-k=2t

個符號，或

2tq

比特信元長度：

k

個符號，或kq個比特參數或q(2q–1)個比特

∵RS碼能夠糾正t個m進制錯碼，即能糾正碼組中t個不超過q位連續的二進制錯碼，∴RS碼特別適用于存在突發錯誤的信道，例如，移動通信網等衰落信道中。此外，∵它是多進制糾錯編碼，∴特別適合用于多進制調制的場合。RS碼的生成多項式：g(x)=(x+)(x+2)…(x+2t)式中，

是伽羅華域GF(2q

)中的本原元素。應用卷積碼——一種非分組碼§11.7

非分組碼概念：分組碼:——每個碼組中的督元僅與本碼組中的k個信元有約束關系。

非分組碼:即一個碼組中的督元監督著N個信息段。卷積碼的符號:

(n,k,N

)N

---

編碼約束度，表示編碼過程中互相約束的碼段個數；nN

---

編碼約束長度，表示編碼過程中互相約束的碼元個數。卷積碼的碼率:

R=k/n(n,1,N

)

簡單,常用N

或nN也反映了卷積碼編碼器的復雜度。

11.7.1卷積碼的基本原理編碼器原理方框圖存儲以前的k(N-1)個信息碼當前

K個共有N

段移存器，每段k

級

如圖所示的(n,k,N)=

(3,1,3)卷積碼編碼器。例共有3

段移存器，每段1

級（存儲1個信元）

每次輸入1b，輸出3b

分析：信息位---設移存器初始是全零狀態，當輸入信息序列

：則編碼器輸出序列：結果為系統碼形式。ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi－1bitt輸入輸出信息位bi的監督位和各信息位之間的約束關系如下圖中虛線所示：（編碼約束度N=3，約束長度nN=3×3=9）卷積碼的表述方法：11.7.2卷積碼的代數表述仍以前面

(3,1,3)卷積碼為例分析。設各級移存器初始是“0”狀態，則監督位di、ei和信息位bi之間的關系可以寫為:上式：表示的卷積碼也是一種線性碼。——可完全由H

或G

所確定。

監督矩陣H監督矩陣生成矩陣左式可以改寫為注：上面兩式及后面的式子中“＋”表示“”。將上式用矩陣表示成：H可見，卷積碼的監督矩陣H是一個有頭無尾的半無窮矩陣。且自第7行起，每兩行的左端比上兩行多了3個“0”。此外，該矩陣的每3列的結構相同，只是后3列比前3列向下移了兩行。

這種截短監督矩陣的結構形式如下圖所示：

H1=nn–k(n–k)N因此，通常只需研究產生前nN個碼元（此例nN=9）的監督矩陣。(3,1,3)由圖可見約束長度此例

(3,1,3)碼中的截短監督矩陣有如下形式：式中：——2階單位方陣；Pi——21階矩陣，i=1,2,3；02——2階全零方陣。H1=式中In-k—(n–k)階單位方陣；Pi—(n–k)k階矩陣；

0n-k—(n–k)階全零方陣。

h是卷積碼的一個最重要矩陣。只要給定h，則可構造出H1。——H1的末行：h

=[PN

0n-kPN-1

0n-kPN-2

0n-k

P1In-k]H1

截短監督矩陣H1一般形式：

基本監督矩陣h[b1d1e1b2d2e2b3d3e3b4d4e4

]=

[b1b1b1b2b2(b2+b1)b3(b3+b1)(b3+b2+b1)b4(b4+b2)(b4+b3+b2)

]

生成矩陣G上例(n,k,N)=(3,1,3)中的輸出碼元序列可寫成：對比：可見，循環碼的G也是一個半無窮矩陣，其特點：每一行的結構相同，只是比上一行向右退后n=3列。可知，此碼的生成矩陣G即為上式最右矩陣：式中，I1

為一階單位方陣；Qi

為12階矩陣；

0

為一階全零方陣。

截短生成矩陣G1與H1矩陣比較可見，Qi是矩陣Pi

的轉置：Qi=PiT

一般說來，截短生成矩陣具有如下形式：(i=1,2,)只要給定g，則可從已知的信息位得到整個編碼序列。

基本生成矩陣g式中:

Ik

－k階單位方陣；Qi

－(n–k)k階矩陣；

0k

－k階全零方陣。——G1矩陣第一行

g

＝

[Ik

Q1

0k

Q2

0k

Q30k

QN]

截短生成矩陣一般形式分類：代數解碼：——利用編碼本身的代數結構進行解碼，不考慮信道的統計特性。概率解碼（最大似然解碼）：——基于信道的統計特性和卷積碼的特點進行計算。11.7.3卷積碼的解碼如：大數邏輯解碼（門限解碼），適用nN較短的卷積碼。

序貫解碼:適用無記憶信道維特比算法：當碼的nN較短時，效率更高、速度更快約束長度首先將接收信息位暫存于移存器中，并從接收碼元的信息位和監督位計算校正子。然后，將計算得出的校正子暫存，并用它來檢測錯碼的位置。在信息位移存器輸出端，接有一個模2加電路；當檢測到輸出的信息位有錯時，在輸出的信息位上加“1”，從而糾正之。校正子計算信息位移存器校正子移存器錯碼檢測

輸入輸出修正校正子信息位監督位1大數邏輯解碼工作原理這里的錯碼檢測是采用二進制碼的大數邏輯解碼算法。它利用一組“正交”校驗方程進行計算。這里的“正交”定義：若被校驗的那個信息位出現在校驗方程組的每一個方程中，而其他的信息位至多在一個方程中出現，則稱這組方程為正交校驗方程。這樣就可以根據被錯碼影響了的方程數目在方程組中是否占多數來判斷該信息位是否錯了。下面將用一個實例來具體講述這一過程。c1=b1c2=b2c3=b3c4=b1+b4c5=b1+b2+b5c6=b1+b2+b3+b6

b6b5b4b3b2b1bici輸入輸出bici

(2,1,6)卷積碼編碼器方框圖：監督位和信息位的關系：（當輸入序列為b1

b2

b3

b4

時）S1=c1+b1S2=c2+b2S3=c3+b3S4=c4+b1+b4S5=c5+b1+b2+b5S6=c6+b1+b2+b3+b6監督位監督關系式例在上式中，只有信息位b1出現在每個方程中，監督位和其他信息位均最多只出現一次。因此，在接收端解碼時，考察b1、c1至b6、c6等12個碼元，僅當b1出錯時，式中才可能有3個或3個以上方程等于“1”。從而能夠糾正b1的錯誤。正交校驗方程組

上式經過簡單線性變換后，得出如下正交校驗方程組：輸入輸出Yb6b5b4b3b2b1S6S5S4S3S2S1門限電路：“1”的個數

3？校正子Si校正子移存器信息位移存器重算監督位ci接收監督位計算校正子Si654321解碼器方框圖：2

卷積碼的幾何表述1）碼樹圖以前面(3,1,3)

卷積碼為例：并設M1，M2和M3的初始狀態000(n,k,N)(3,1,3)

碼樹圖：觀察1

每條樹枝上標注的碼元為輸出比特，每個節點為移存器的狀態abcd若信息位

1 1 0 1編碼輸出111110

010100

(3,1,3)

碼樹圖：觀察2(3,1,3)

碼樹圖：觀察3若信息位

1 1 0 1編碼輸出111110

010100

碼樹圖原則上還可以用于解碼。發送序列?若信息位

1 1 0 1編碼輸出111110

010100

發送序列?一般說來，碼樹搜索解碼法并不實用，因為隨著信息序列的增長，碼樹分支數目按指數規律增長；在上面的碼樹圖中，只有4個信息位，分支已有24=16個。但是它為以后實用解碼算法建立了初步基礎。2）狀態圖碼樹圖狀態圖由(3,1,3)編碼器結構可知：

前一狀態a只能轉到下一狀態a或b；前一狀態b只能轉到下一狀態c或d，等等。

按照表中的規律畫出的狀態圖：由表看出：abcd000111101110010011100001abcd000111101110010011100001利用狀態圖可方便地從輸入序列得到輸出序列。例如：輸入信息位

1 1 0

1編碼輸出111110

010100

111110010100可見：在第4時隙以后的網格圖形完全是重復第3時隙的圖形。這是因為此(3,1,3)卷積碼的約束長度為3。3）網格圖將狀態圖在時間上展開網格圖圖中畫出了5個時隙。當輸入信息位為11010時，在網格圖中的編碼路徑：這時的輸出編碼序列：111110010100011…。基于上面的狀態圖和網格圖，下面將討論維特比解碼算法。3

維特比解碼算法基本原理仍用上面(3,1,3)卷積碼的例子來說明維特比算法的原理。例設發送信息位為1101，為了使圖中移存器的信息位全部移出，在信息位后面加入3個“0”，故編碼后的發送序列為

111110010100001011

000設接收序列為111010010110001011000現在，比較網格圖中的這8條路徑和接收序列之間的漢明距離。(n,k,N)第1步例如，由出發點狀態a經過3級路徑后到達狀態a的兩條路徑中：上面一條為“000000000”，它和接收序列“111010010”的漢明距離=5下面一條為“111001011”，它和接收序列的漢明距離=3同樣，由出發點a經過3級路徑后到達狀態b、c和d的路徑分別都有兩條，故總共有8條路徑。

下表中列出了這8條路徑和其漢明距離。接收序列111010010110001011000將到達每個狀態的兩條路徑的漢明距離作比較，將距離小的一條路徑保留，稱為幸存路徑。若兩條路徑的漢明距離相同，則可任意保存一條。這樣就剩下4條路徑：2,4,6，8第2步接收序列111010010110001011000abcd011010010101001abcd111100100110110按照表中的幸存路徑畫出的網格圖示于下圖中：上例卷積碼的約束度N=3，需要存儲和計算

8條路徑的參量。故維特比解碼算法適合約束度較小（N

10）的編碼。對于約束度大的卷積碼，可以采用其他解碼算法。由此可見，維特比解碼算法的復雜度隨約束長度N按指數形式2N增長。Turbo碼——一種特殊的鏈接碼(1993)

§11.8

——屬于復合碼類

由于分組碼和卷積碼的復雜度隨碼組長度或約束度的增大按指數規律增長，所以為了提高糾錯能力，不要單純增大碼的長度，而是將兩種或多種簡單的編碼組合成復合編碼。Turbo碼基本原理Turbo碼的編碼器在兩個并聯或串聯的分量碼編碼器之間增加一個交織器，使之具有很大的碼組長度，能在低信噪比條件下得到接近理想的性能。Turbo碼的譯碼器有兩個分量碼譯碼器，譯碼在兩個分量譯碼器之間進行迭代譯碼，故整個譯碼過程類似渦輪（turbo）工作，所以又形象的稱為Turbo碼。RSCC編碼器和卷積碼編碼器之間的主要區別：從移存器輸出端到信息位輸入端之間有反饋路徑。原來的卷積碼編碼器像是一個FIR數字濾波器。增加了反饋路徑后，它就變成了一個IIR濾波器，或稱遞歸濾波器。Turbo碼編碼器它由一對遞歸系統卷積碼(RSCC)編碼器和一個交織器組成：RSCC編碼器交織器RSCC編碼器bibic1ic2i因為輸出中第1位是信息位，所以它是系統碼。DDbibiciRSCC編碼器舉例：它是一個碼率等于1/2的卷積碼編碼器，輸入為bi，輸出為bici

。矩陣交織器：它由容量為(n-1)m比特的存儲器構成：矩陣交織器原理圖：再按列的方向輸出將信號碼元按行的方向輸入存儲器xxx1234xxx1234xxx1xxx1xxxxxx(a)第1~4比特輸入時的狀態xx2567834x5678xx25x2x51xxxxx(b)第5~8比特輸入時的狀態x369362951xxxx9101112101112784x369(c)第9~12比特輸入時的狀態1013769543211415161112813141516471013471013(d)第13~16比特輸入時的狀態交織器解交織器卷積交織器：低密度奇偶校驗碼§11.9

(Low-DensityParity-Check，LDPC)

當碼組很長時才具有優良性能，廣泛地應用于移動通信、無線局域網和光纖通信等多種領域LDPC碼簡介：LDPC碼分類：LDPC碼和普通的奇偶監督碼一樣，可以由有n列、m行的監督矩陣H確定；n是碼長，m是校正子個數。但是其H矩陣和普通奇偶監督碼的有所不同：它是稀疏矩陣，即矩陣中“1”的個數很少，密度很低；設H矩陣每列有j個“1”，每行有k個“1”，則應有j<<m，k<<n，且j3。其H矩陣的任意兩行的元素不能在相同位置上為“1”，即H矩陣中沒有四角由“1”構成的矩形。LDPC碼通常用上述3個參量(n,j,k)表示。在編碼時，設計好H矩陣后，由H矩陣可以導出生成矩陣G。這樣，對于給定的信息位，不難算出碼組。LDPC碼的構造：

LDPC碼的解碼方法也和一般的奇偶監督碼的解碼方法不同。

基本的解碼算法稱為置信傳播算法，通常簡稱BP算法。

這種算法實質上是求最大后驗概率，類似于一般的最大似然準則解碼算法，但是它需要進行多次迭代運算，逐步逼近最優的解碼值。

LDPC碼的具體編解碼算法十分復雜，這里不再深入討論。LDPC碼的解碼：網格編碼調制——將糾錯編碼和調制相結合

§11.10

——同時節省功率和帶寬

TrellisCodedModulation,TCM11.10.1TCM的基本概念回顧QPSK系統：QPSK是一個4相相移鍵控系統，它的每個碼元傳輸2比特信息。若在接收端判決時因干擾而將信號相位錯判至相鄰相位，則將出現錯碼。現將系統改成8PSK，它的每個碼元本可以傳輸3比特信息。但是，仍令每個碼元傳輸2比特信息，第3比特用于糾錯碼，例如，采用碼率為2/3的卷積碼。這時，接收端的解調和解碼是作為一個步驟完成的，不像傳統作法，先解調得到基帶信號后再為糾錯去解碼。右圖示出了8PSK信號星座圖中的8個信號點：假設信號振幅等于1， 則相鄰兩信號點的歐氏距離d0=0.765

1

d0=2sin(/8)=0.765d1=√2兩個信號序列的歐氏距離越大，即它們的差別越大，則因干擾造成互相混淆的可能性越小。為了利用卷積碼維特比解碼的優點，這時仍然需要用到網格圖。但是，和卷積碼維特比解碼時的網格圖相比，在TCM中是將這些波形映射為網格圖，故TCM網格圖中的各狀態是波形的狀態。圖中的信號點代表某個確定相位的已調信號波形。A0B0B1