c7-第11章 差錯控制編碼

制作：曹麗娜ccllna@163.com

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

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

本章內(nèi)容第11章差錯控制編碼

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

碼距

碼率

性能簡單實用碼—奇偶監(jiān)督恒比碼

正反碼線性分組碼—漢明碼監(jiān)督矩陣H、生成矩陣G

循環(huán)碼—生成多項式編譯方法BCH碼RS碼卷積碼—編譯原理代數(shù)表述幾何表述Turbo碼低密度奇偶校驗碼網(wǎng)格編碼調(diào)制—TCM信號的產(chǎn)生與解調(diào)

§11.1

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

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

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

差錯控制編碼

信道類型——根據(jù)錯碼的不同分布規(guī)律分為：

差錯控制方式：

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

——自動請求重發(fā)

缺點：工作在半雙工狀態(tài)，傳輸效率較低。

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

糾錯編碼的基本原理規(guī)則：使碼組中“1”的個數(shù)為偶數(shù)情形1：沒有冗余——不能發(fā)現(xiàn)錯誤情形2：加入冗余

——可以發(fā)現(xiàn)錯誤

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

錯誤。（奇數(shù)個錯碼）這時，能夠發(fā)現(xiàn)2個以下錯碼，或者糾正

1位

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

=

k+r就是分組碼前面的例子：信息位與監(jiān)督位關系：分組碼的符號：分組碼的結(jié)構(gòu)：

（n，k）

碼長

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

碼重(W)：碼組中“1”的數(shù)目?！?/p>

011011”

的距離為

3例

碼重和碼距

碼重為

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

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

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

t

個錯碼,同時檢

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

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

(dB)2PSK調(diào)制可見：能節(jié)省功率2dB

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

因此，糾錯碼主要應用于功率受限而帶寬不太受限的信道中?！冻龅拇鷥r是帶寬增大。設編碼前系統(tǒng)工作在圖中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

奇偶監(jiān)督碼偶數(shù)監(jiān)督奇數(shù)監(jiān)督

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

碼率：編出的碼字應為

：

若收到10011，檢測結(jié)果為：根據(jù)偶數(shù)監(jiān)督規(guī)則：---存在錯碼若收到00011，檢測結(jié)果為：

可見，奇偶監(jiān)督碼不能檢出偶數(shù)個錯碼。

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

=

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

按上表判決:無錯碼

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

線性碼：按照一組線性方程構(gòu)成的代數(shù)碼。

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

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

、a4、a5或a6

時，

校正子S1為1；否則S1為

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

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

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

---監(jiān)督矩陣

簡記為H

A=[a6

a5

a4

a3

a2

a1

a0]0=[000]監(jiān)督矩陣

或轉(zhuǎn)置轉(zhuǎn)置“T”r

行n

列=[PIr]r

k階矩陣r

r階方陣——典型監(jiān)督矩陣H

矩陣的性質(zhì)

①H

的行數(shù)等于監(jiān)督位的數(shù)目r

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

②

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

---生成矩陣

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

r階矩陣，它為P的轉(zhuǎn)置，即:

Q=PTP陣Q陣將Q的左邊加上1個kk階單位方陣，就構(gòu)成矩陣:生成矩陣，或者因此，若找到了碼的G，則編碼的方法就完全確定了。具有[IkQ]形式的稱為典型生成矩陣。由典型G得到的碼稱為系統(tǒng)碼。稱為典型生成矩陣碼組A中，信息位的位置不變，監(jiān)督位附在其后?！哂伤梢援a(chǎn)生整個碼組，即有:G

矩陣的性質(zhì)

①

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

的關系

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

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

，即∵任一發(fā)送碼組A

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

則S為0，否則S不為0。因此，可根據(jù)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②

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

a3監(jiān)督位a2a1a0信息位a6~

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

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

表中的第2

碼組向右移一位即得到第

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

循環(huán)碼原理表中的第6

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

碼多項式多項式的系數(shù)就是碼組中的各碼元，x

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

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

（Q

為整數(shù)）

m

p

(模n)則在模n

運算下，有

碼多項式的按模運算：

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

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

例循環(huán)碼組，其碼長n=7?，F(xiàn)給定i=3，則01011101100101左移i位3由上述分析可見:2.

循環(huán)碼的生成矩陣G

生成矩陣

G可由k

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

，即r=n-k=7-3=4，解例碼組中唯一一個4次碼多項式代表的或據(jù)此，可以寫出此循環(huán)碼多項式A(x):∵任一循環(huán)碼多項式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)循環(huán)碼的生成多項式g(x)。例將(x7+1)進行因式分解：解：n–k即有或11.6.2循環(huán)碼的編解碼方法1.循環(huán)碼的編碼設

信息碼(an-1

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

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

xk-2+?+an-k——其最高次數(shù)為k-1則循環(huán)碼的多項式為：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)，作為監(jiān)督碼元

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

=

xn-k

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

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

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

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

i

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

–i

,k

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

與監(jiān)督位、糾錯個數(shù)t之間的關系：

對于正整數(shù)m(m

3)和正整數(shù)t

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

n=2m–1，監(jiān)督位為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個隨機錯碼；其生成多項式系數(shù)(5343)8=(101011100011)2，對應g(x)=x11+x9+x7+x6+x5+x+1，且解碼容易，實際應用較多。BCH碼的長度都為奇數(shù)。在應用中，為了得到偶數(shù)長度的碼，并增大檢錯能力，可以在BCH碼生成多項式中乘上一個因式(x+1)，從而得到擴展BCH碼(n+1,k)。擴展BCH碼相當于在原BCH碼上增加了一個校驗位，因此碼距比原BCH碼增加1。擴展BCH碼已經(jīng)不再具有循環(huán)性。例如，廣泛實用的擴展戈萊碼(24,12)，其最小碼距為8，碼率為1/2，能夠糾3個錯碼和檢4個錯碼。它比漢明碼的糾錯能力強很多，付出的代價是解碼更復雜，碼率也比漢明碼低。此外，它不再是循環(huán)碼了。擴展BCH碼：11.6.5RS碼——它是一類具有很強糾錯能力的多進制BCH碼。——由里德和索洛蒙(Reed–Solomon)提出。

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

r=n-k=2t

個符號，或

2tq

比特信元長度：

k

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

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

是伽羅華域GF(2q

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

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

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

(n,k,N

)N

---

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

---

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

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

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

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

(3,1,3)卷積碼為例分析。設各級移存器初始是“0”狀態(tài)，則監(jiān)督位di、ei和信息位bi之間的關系可以寫為:上式：表示的卷積碼也是一種線性碼?！赏耆蒆

或G

所確定。

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

這種截短監(jiān)督矩陣的結(jié)構(gòu)形式如下圖所示：

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

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

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

h是卷積碼的一個最重要矩陣。只要給定h，則可構(gòu)造出H1?！狧1的末行：h

=[PN

0n-kPN-1

0n-kPN-2

0n-k

P1In-k]H1

截短監(jiān)督矩陣H1一般形式：

基本監(jiān)督矩陣h[b1d1e1b2d2e2b3d3e3b4d4e4

]=

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

]

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

為一階單位方陣；Qi

為12階矩陣；

0

為一階全零方陣。

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

的轉(zhuǎn)置：Qi=PiT

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

基本生成矩陣g式中:

Ik

－k階單位方陣；Qi

－(n–k)k階矩陣；

0k

－k階全零方陣?！狦1矩陣第一行

g

＝

[Ik

Q1

0k

Q2

0k

Q30k

QN]

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

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

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

b6b5b4b3b2b1bici輸入輸出bici

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

b2

b3

b4

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

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

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

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

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

碼樹圖：觀察1

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

1 1 0 1編碼輸出111110

010100

(3,1,3)

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

碼樹圖：觀察3若信息位

1 1 0 1編碼輸出111110

010100

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

1 1 0 1編碼輸出111110

010100

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

前一狀態(tài)a只能轉(zhuǎn)到下一狀態(tài)a或b；前一狀態(tài)b只能轉(zhuǎn)到下一狀態(tài)c或d，等等。

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

1 1 0

1編碼輸出111110

010100

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

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

111110010100001011

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

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

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

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

§11.8

——屬于復合碼類

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

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

(Low-DensityParity-Check，LDPC)

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

LDPC碼的解碼方法也和一般的奇偶監(jiān)督碼的解碼方法不同。

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

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

LDPC碼的具體編解碼算法十分復雜，這里不再深入討論。LDPC碼的解碼：網(wǎng)格編碼調(diào)制——將糾錯編碼和調(diào)制相結(jié)合

§11.10

——同時節(jié)省功率和帶寬

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

1

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