c7-第11章 差錯(cuò)控制編碼

制作：曹麗娜ccllna@163.com

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

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

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

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

碼距

碼率

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

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

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

§11.1

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

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

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

差錯(cuò)控制編碼

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

差錯(cuò)控制方式：

差錯(cuò)控制方式（ARQ）（FEC）——

——自動(dòng)請(qǐng)求重發(fā)

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

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

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

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

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

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

1位

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

=

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

（n，k）

碼長(zhǎng)

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

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

011011”

的距離為

3例

碼重和碼距

碼重為

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

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

和檢糾錯(cuò)能力的關(guān)系檢ｅ個(gè)錯(cuò)碼，要求：糾ｔ個(gè)錯(cuò)碼，要求：糾

t

個(gè)錯(cuò)碼,同時(shí)檢

e個(gè)錯(cuò)碼，要求：證明：§11.3

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

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

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

因此，糾錯(cuò)碼主要應(yīng)用于功率受限而帶寬不太受限的信道中?！冻龅拇鷥r(jià)是帶寬增大。設(shè)編碼前系統(tǒng)工作在圖中C點(diǎn)，提高速率后Pe由C點(diǎn)升到E點(diǎn)。傳輸速率RB

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

(dB)但采用糾錯(cuò)編碼后，Pe仍可降到D點(diǎn)?！?1.4

簡(jiǎn)單的實(shí)用編碼11.4.1

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

適用：檢測(cè)隨機(jī)出現(xiàn)的零星差錯(cuò)。編碼規(guī)則：只有一位監(jiān)督元（∵不知錯(cuò)碼位置）很高（因?yàn)橹挥幸晃槐O(jiān)督位）。

碼率：編出的碼字應(yīng)為

：

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

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

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

=

00000校驗(yàn)碼組和錯(cuò)碼的關(guān)系：

按上表判決:無錯(cuò)碼

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

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

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

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

、a4、a5或a6

時(shí)，

校正子S1為1；否則S1為

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

編碼效率：漢明碼特點(diǎn):式中的等號(hào)成立，即:d0=3（糾1或檢2）r

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

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

簡(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”的位置表示相應(yīng)碼元之間存在的監(jiān)督關(guān)系。(7，4)碼r=3

②

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

---生成矩陣

或者寫成：P陣式中，Q為一個(gè)k

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

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

矩陣的性質(zhì)

①

G矩陣的各行是線性無關(guān)的?！哂墒娇梢钥闯?任一碼組A都是G的各行的線性組合。G共有k行，若它們線性無關(guān)，則可以組合出2k種不同的碼組A。它恰是有k位信息位的全部碼組。G和H

的關(guān)系

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

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

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

都應(yīng)滿足式：∴對(duì)于接收碼組B，可通過計(jì)算:來進(jìn)行檢測(cè)。將B=A+E代入上式，可得 0若,

則S為0，否則S不為0。因此，可根據(jù)S

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

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

①封閉性A1和A2(A1+A2)證明：若A1和A2是兩個(gè)碼組，則有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ì)②只需找最小碼重?zé)o需兩兩碼組比較循環(huán)碼西安電子科技大學(xué)通信工程學(xué)院

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

表中的第2

碼組向右移一位即得到第

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

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

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

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

僅是碼元位置標(biāo)記。n=7時(shí)

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

（Q

為整數(shù)）

m

p

(模n)則在模n

運(yùn)算下，有

碼多項(xiàng)式的按模運(yùn)算：

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

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

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

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

生成矩陣

G可由k

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

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

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

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

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

=h(x)g(x)∵碼組A(x)是一個(gè)(n–k)次多項(xiàng)式，故xkA(x)是一個(gè)n次多項(xiàng)式?？芍?，

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

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

信息碼(an-1

an-2…an-k)的多項(xiàng)式為：

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

xk-2+?+an-k——其最高次數(shù)為k-1則循環(huán)碼的多項(xiàng)式為：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）個(gè)0，預(yù)留給督元?！玫接嗍?/p>

r(x)，作為監(jiān)督碼元

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

=

xn-k

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

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

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

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

i

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

–i

,k

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

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

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

3)和正整數(shù)t

<m/2，必定存在一個(gè)碼長(zhǎng)為

n=2m–1，監(jiān)督位為n–k

mt，能糾正所有不多于t個(gè)隨機(jī)錯(cuò)誤的BCH碼。若碼長(zhǎng)n=(2m-1)/i（i>1，且除得盡(2m-1)），則為非本原BCH碼。BCH碼的設(shè)計(jì)：在工程設(shè)計(jì)中，一般不需要用計(jì)算方法去尋找生成多項(xiàng)式g(x)。因?yàn)榍叭嗽缫褜ふ业降膅(x)列成表，故可以用查表法找到所需的生成多項(xiàng)式。教材353頁(yè)的表11-7給出了碼長(zhǎng)n127的二進(jìn)制本原BCH碼生成多項(xiàng)式。nktg(x)nktg(x)17212333419121222212232472716635343514566471334765657324534046524443073357107613543000671717773537在上表中的(23,12)碼稱為戈萊(Golay)碼。其最小碼距為7，能糾3個(gè)隨機(jī)錯(cuò)碼；其生成多項(xiàng)式系數(shù)(5343)8=(101011100011)2，對(duì)應(yīng)g(x)=x11+x9+x7+x6+x5+x+1，且解碼容易，實(shí)際應(yīng)用較多。BCH碼的長(zhǎng)度都為奇數(shù)。在應(yīng)用中，為了得到偶數(shù)長(zhǎng)度的碼，并增大檢錯(cuò)能力，可以在BCH碼生成多項(xiàng)式中乘上一個(gè)因式(x+1)，從而得到擴(kuò)展BCH碼(n+1,k)。擴(kuò)展BCH碼相當(dāng)于在原BCH碼上增加了一個(gè)校驗(yàn)位，因此碼距比原BCH碼增加1。擴(kuò)展BCH碼已經(jīng)不再具有循環(huán)性。例如，廣泛實(shí)用的擴(kuò)展戈萊碼(24,12)，其最小碼距為8，碼率為1/2，能夠糾3個(gè)錯(cuò)碼和檢4個(gè)錯(cuò)碼。它比漢明碼的糾錯(cuò)能力強(qiáng)很多，付出的代價(jià)是解碼更復(fù)雜，碼率也比漢明碼低。此外，它不再是循環(huán)碼了。擴(kuò)展BCH碼：11.6.5RS碼——它是一類具有很強(qiáng)糾錯(cuò)能力的多進(jìn)制BCH碼?！衫锏潞退髀迕?Reed–Solomon)提出。

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

r=n-k=2t

個(gè)符號(hào)，或

2tq

比特信元長(zhǎng)度：

k

個(gè)符號(hào)，或kq個(gè)比特參數(shù)或q(2q–1)個(gè)比特

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

是伽羅華域GF(2q

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

非分組碼概念：分組碼:——每個(gè)碼組中的督元僅與本碼組中的k個(gè)信元有約束關(guān)系。

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

(n,k,N

)N

---

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

---

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

R=k/n(n,1,N

)

簡(jiǎn)單,常用N

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

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

K個(gè)共有N

段移存器，每段k

級(jí)

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

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

段移存器，每段1

級(jí)（存儲(chǔ)1個(gè)信元）

每次輸入1b，輸出3b

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

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

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

或G

所確定。

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

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

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

(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是卷積碼的一個(gè)最重要矩陣。只要給定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)中的輸出碼元序列可寫成：對(duì)比：可見，循環(huán)碼的G也是一個(gè)半無窮矩陣，其特點(diǎn)：每一行的結(jié)構(gòu)相同，只是比上一行向右退后n=3列?？芍舜a的生成矩陣G即為上式最右矩陣：式中，I1

為一階單位方陣；Qi

為12階矩陣；

0

為一階全零方陣。

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

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

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

基本生成矩陣g式中:

Ik

－k階單位方陣；Qi

－(n–k)k階矩陣；

0k

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

g

＝

[Ik

Q1

0k

Q2

0k

Q30k

QN]

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

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

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

b6b5b4b3b2b1bici輸入輸出bici

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

b2

b3

b4

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

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

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

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

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

碼樹圖：觀察1

每條樹枝上標(biāo)注的碼元為輸出比特，每個(gè)節(jié)點(diǎn)為移存器的狀態(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í)用，因?yàn)殡S著信息序列的增長(zhǎng)，碼樹分支數(shù)目按指數(shù)規(guī)律增長(zhǎng)；在上面的碼樹圖中，只有4個(gè)信息位，分支已有24=16個(gè)。但是它為以后實(shí)用解碼算法建立了初步基礎(chǔ)。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時(shí)隙以后的網(wǎng)格圖形完全是重復(fù)第3時(shí)隙的圖形。這是因?yàn)榇?3,1,3)卷積碼的約束長(zhǎng)度為3。3）網(wǎng)格圖將狀態(tài)圖在時(shí)間上展開網(wǎng)格圖圖中畫出了5個(gè)時(shí)隙。當(dāng)輸入信息位為11010時(shí)，在網(wǎng)格圖中的編碼路徑：這時(shí)的輸出編碼序列：111110010100011…。基于上面的狀態(tài)圖和網(wǎng)格圖，下面將討論維特比解碼算法。3

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

111110010100001011

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

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

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

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

§11.8

——屬于復(fù)合碼類

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

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

(Low-DensityParity-Check，LDPC)

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

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

基本的解碼算法稱為置信傳播算法，通常簡(jiǎn)稱BP算法。

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

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

§11.10

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

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

1

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