通信原理差錯控制編碼-課件

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

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

碼距

碼率

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

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

循環(huán)碼—生成多項式編譯方法BCH碼RS碼卷積碼—編譯原理代數(shù)表述幾何表述本章內(nèi)容第11章差錯控制編碼基本概念—差§11.1

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

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

差錯控制編碼差錯控制編碼

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

差錯控制方式：

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

——自動請求重發(fā)信道類型——根據(jù)錯碼的不同分布規(guī)律分為：差錯控制方式

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

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

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

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

冗余?另外4個碼組許用碼組禁用碼組規(guī)則：使碼組中情形1：沒有冗余——不能發(fā)現(xiàn)錯誤情形2例許用碼組禁用碼組也不能糾正

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

1位

錯碼。例這時，能夠發(fā)現(xiàn)2個以下錯碼，或者糾正1位錯碼。例綜上所述：---信息碼元位數(shù)---編碼后碼字位數(shù)綜上所述：---信息碼元位數(shù)---編碼后碼字位數(shù)不同的編碼方法，檢錯或糾錯能力也不同。不同的編碼方法，檢錯或糾錯能力也不同。分組碼和系統(tǒng)碼編碼后的每組長度為n

=

k+r就是分組碼前面的例子：信息位與監(jiān)督位關(guān)系：分組碼和系統(tǒng)碼編碼后的每組長度為n

=

k+r就是分組碼分組碼的符號：分組碼的結(jié)構(gòu)：

（n，k）

分組碼的符號：分組碼的結(jié)構(gòu)：（n，k）

碼長

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

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

011011”

的距離為

3例

碼重和碼距

碼重為

3碼長(n)：碼組（碼字）中的碼元個數(shù)。碼重(W)：碼組對于3位的編碼組，可用3維空間來說明（4個許用碼組之間）各頂點之間沿立方體各邊行走的幾何距離——碼距=2

碼距的幾何意義：對于3位的編碼組，可用3維空間來說明（4個許用碼組之間）各頂對于（n，k）分組碼，有以下結(jié)論：最小碼距d0

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

t

個錯碼,同時檢

e個錯碼，要求：對于（n，k）分組碼，有以下結(jié)論：最小碼距d0和檢糾錯證明：證明：§11.3

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

CD

A

B編碼前信噪比

(dB)2PSK調(diào)制右圖所示的某種編碼性能可見：不增大發(fā)送功率,就能A可見：能節(jié)省功率2dB

——稱為編碼增益D點10-610-510-410-310-210-1編碼后Pe

CD

A

B編碼前信噪比(dB)2PSK調(diào)制C點可見：能節(jié)省功率2dBD點10-610-510-410-

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

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

CDEAB編碼前信噪比

(dB)但采用糾錯編碼后，Pe仍可降到D點。設(shè)編碼前系統(tǒng)工作在圖中C點，傳輸速率RB和信噪比Eb/§11.4

簡單的實用編碼§11.4簡單的實用編碼11.4.1

奇偶監(jiān)督碼偶監(jiān)督碼奇監(jiān)督碼

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

碼率：11.4.1奇偶監(jiān)督碼偶監(jiān)督碼奇監(jiān)督碼適用：檢編出的碼字應(yīng)為

：

若收到10011，檢測結(jié)果為：根據(jù)偶數(shù)監(jiān)督規(guī)則：---有錯若收到00011，檢測結(jié)果為：奇偶監(jiān)督碼不能檢出偶數(shù)個錯例解---認為無錯11011編出的碼字應(yīng)為：若收到10011，檢測結(jié)果為：11.4.2二維奇偶監(jiān)督碼編碼規(guī)則：（方陣碼）11.4.2二維奇偶監(jiān)督碼編碼規(guī)則：（方陣碼）檢測方法：計算接收碼組中“1”的數(shù)目，可知是否有錯。11.4.3恒比碼適用：用于電報傳輸系統(tǒng)或其他鍵盤設(shè)備產(chǎn)生的字母和符號。編碼規(guī)則：(等重碼)例個許用碼組，可分別用來代表26個英文字母及其他符號。檢測方法：計算接收碼組中“1”的數(shù)目，可知是否有錯。11.411.4.4正反碼編碼規(guī)則：

設(shè)碼長n=10，即信息位k=5，監(jiān)督位r=5。例監(jiān)督位數(shù)與信息位數(shù)相同；能糾錯。編碼效率低：50%。11.4.4正反碼編碼規(guī)則：設(shè)碼長n=10，即譯碼方法：

=

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

（n,k）線性分組碼§11.5線性碼：按照一組線性方程構(gòu)成的代數(shù)碼。

即每個碼字的監(jiān)督碼元是信息碼元的線性組合?；靖拍畲鷶?shù)碼：建立在代數(shù)學(xué)基礎(chǔ)上的編碼。線性碼：按照一組線性方程構(gòu)成的代數(shù)碼?；靖拍畲鷶?shù)碼：建立在正反碼，效率50%，太低。糾正1位錯，最少增加多少監(jiān)督位？構(gòu)造出以最小多余度代價換取最大抗干擾能力的好碼糾錯編碼任務(wù)：漢明碼：能糾正1位錯，編碼效率較高正反碼，效率50%，太低。構(gòu)造出以最小多余度代價換取最大抗干---監(jiān)督關(guān)系式若S=0，認為無錯（偶監(jiān)督時）；若S=1，認為有錯。若要構(gòu)造具有糾錯能力的（n，k）碼，則需增加督碼元的數(shù)目。當“=”成立時，構(gòu)造的線性分組碼稱為漢明碼校正子構(gòu)造原理只有一位監(jiān)督元---檢錯漢明碼的——能糾1位錯碼的高效

線性分組碼---監(jiān)督關(guān)系式若S=0，認為無錯（偶監(jiān)督時）；若S=1例(7,4)漢明碼可以其他假設(shè)例(7,4)漢明碼可以其他假設(shè)由表可見:僅當一位錯碼的位置在a2

、a4、a5或a6

時，

校正子S1為1；否則S1為

0。同理：由表可見:僅當一位錯碼的位置在a2、a4、a5同理：(A)移項運算解出監(jiān)督位(A)移項運算(A)(A)例接收端譯碼——檢錯糾錯過程以上構(gòu)造的線性分組碼，稱為漢明碼。例接收端譯碼——檢錯糾錯過程以上構(gòu)造的線性分組碼，稱為漢明最小碼距：當n很大

r很小時，Rc≈

1。

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

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

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

線性分組碼的一般原理將前面(7,4)漢明碼的監(jiān)督方程：改寫簡記為H

A=[a6

a5

a4

a3

a2

a1

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

或轉(zhuǎn)置轉(zhuǎn)置“T”簡記為HA=[a6a5a4a3a2a1ar

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個線性無關(guān)的監(jiān)督關(guān)系式。若一矩陣能寫成典型陣形式[PIr]，則其各行一定是線性無關(guān)的。rn=[PIr]rk階rr階——將上面漢明碼例子中的監(jiān)督位公式：改寫成矩陣形式：G

---生成矩陣

或者寫成：P陣將上面漢明碼例子中的監(jiān)督位公式：改寫成矩陣形式：G---式中，Q為一個k

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

Q=PTP陣Q陣式中，Q為一個kr階矩陣，它為P的轉(zhuǎn)置，即:Q將Q的左邊加上1個k

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

n將Q的左邊加上1個kk階單位方陣，就構(gòu)成矩陣:生成G

矩陣的性質(zhì)

①

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

的關(guān)系

G和H的關(guān)系

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

接收碼組的行矩陣B錯碼矩陣（錯誤圖樣）(模2)校正子與錯誤圖樣設(shè)發(fā)送碼組為一個n列的行矩陣A，A=B+E例在接收端，若能求出錯誤圖樣E就能恢復(fù)出發(fā)送碼組A

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

都應(yīng)滿足式：∴對于接收碼組B，可通過計算:來進行檢測。A=B+E例在接收端，若能求出錯誤圖樣E就能恢將B=A+E代入上式，可得 0若,

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

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

得到譯碼器譯出的碼組。（n,k)線性分組碼譯碼的三個步驟：2)由S找到錯誤圖樣E；3)由公式A=B+

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

HT=0和A2

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

HT+A2

HT=(A1+A2)HT=0②

最小距離（證畢）線性分組碼的性質(zhì)①封閉性A1和A2(A1+A2)證明：若A1和A2是兩個根據(jù)性質(zhì)②線性分組碼計算最小碼距，只需找最小碼重，無需兩兩碼組比較③完備性：漢明碼中，伴隨式的非零形式與錯誤圖樣一一對應(yīng)，且伴隨式的圖樣除全0外為個，正好等于碼長，最充分利用了監(jiān)督位所提供的信息。根據(jù)性質(zhì)②③完備性：漢明碼中，伴隨式的非零形式與錯誤圖樣一循環(huán)碼西安電子科技大學(xué)通信工程學(xué)院

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

循環(huán)碼西安電子科技大學(xué)通信工程學(xué)院表中的第2

碼組向右移一位即得到第

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

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

碼組向右移一位即得到第3碼組。表中的第2碼組向右移一位即得到第5碼組；(7,3注意：注意：碼字（）的多項式可表示為：

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

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

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

（Q

為整數(shù)）

m

p

(模n)則在模n

運算下，有1.碼多項式的按模運算一般說來，若一個整數(shù)m可以表示為

碼多項式的按模運算：

或則碼多項式系數(shù)之間的加法和乘法：按模2運算。例碼多項式的按模運算： 或則碼多項式解運算過程：即有則有余式解運算過程：即有則有余式因為，A

(x)是A(x)代表的碼組向左循環(huán)移位i次的結(jié)果。循環(huán)碼的碼多項式

則余式A

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

例循環(huán)碼組，碼長n=7。i=3時，有因為，A(x)是A(x)代表的碼組向左循環(huán)移位i左移i位3

由上述分析可見:左移i位3由上述分析可見:2.

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

生成矩陣

G可由k

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

，即2.循環(huán)碼的生成矩陣G生成矩陣

G可由k個線性無關(guān)的碼生成多項式生成多項式⑶g(x)是xn+1的因式g(x)的性質(zhì)：⑴g(x)必有一常數(shù)項a0＝1⑵g(x)的次數(shù)為n-k次，且唯一否則，循環(huán)右移1位出現(xiàn)k連0,線性分組碼不可能信息位全0，監(jiān)督位不全為0若2個，由封閉性得兩者和為碼組，連0個數(shù)至少多出2位：a0、an-k線性分組碼不可能后面說明⑶g(x)是xn+1的因式g(x)的性質(zhì)：⑴g(x)必有r=n-k=7-3=4，解例碼組中唯一一個4次碼多項式代表的或此循環(huán)碼多項式A(x):r=n-k=7-3=4，解例碼組中唯一一個4次碼多(n-k)+(k-1)=n-1(n-k)+(k-1)=n-1∵任一循環(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)運算下也是一個碼組，故可寫成∵任一循環(huán)碼多項式A(x)都是g(x)的倍式，∴可以左端分子和分母都是n次多項式，故Q(x)=1：將和代入上式，化簡后得到A

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

=h(x)

g(x)左端分子和分母都是n次多項式，故Q(x)=1：將求(7,3)循環(huán)碼的生成多項式g(x)。例將(x7+1)進行因式分解：解：n–k即有或求(7,3)循環(huán)碼的生成多項式g(x)。11.6.2循環(huán)碼的編解碼方法1.循環(huán)碼的編碼設(shè)

信息碼(an-1

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

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

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

11.6.2循環(huán)碼的編解碼方法1.循環(huán)碼的編碼設(shè)信息A(x)=m(x)g(x)即（1）xn-k乘m(x)，得

xn-k

m(x)

（2）xn-k

m(x)除以g(x)： ——將信元左移（n–k）位，附上（n–k）個0，預(yù)留給監(jiān)督碼元。——得到余式

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

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

=

xn-k

m(x)+r(x)——通常是非系統(tǒng)碼（n–k）+（k-1）（n–1）-（k-1）=r（n–1）最高次數(shù)A(x)=m(x)g(x)即（1）xn-k乘m(例可見例可見2.循環(huán)碼的解碼目的：檢錯和糾錯。若能除盡，則無錯；若除不盡而有余項，則表示在傳輸中發(fā)生錯誤。檢錯：2.循環(huán)碼的解碼目的：檢錯和糾錯。若能除盡，則無錯；若糾錯：糾錯：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)碼。截短目的：在設(shè)計糾錯編碼方案時，若找不到合適的碼長n及信息位k

時，可以把循環(huán)碼的碼長截短以得到符合要求的編碼。截短方法：設(shè)給定一個(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.3截短循環(huán)碼例：構(gòu)造一個能夠糾正1位錯碼的(111.6.4BCH碼——解決了生成多項式與糾錯能力的關(guān)系問題，可以在給定糾錯能力要求的條件下尋找到碼的生成多項式。BCH碼的重要性:BCH碼的分類：多個11.6.4BCH碼——解決了生成多項式與糾錯能力的關(guān)系漢明碼是能夠糾正單個隨機錯誤的碼。可以證明，具有循環(huán)性質(zhì)的漢明碼就是能糾正單個隨機錯誤的本原BCH碼。BCH碼的性能：碼長n

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

對于正整數(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碼。漢明碼是能夠糾正單個隨機錯誤的碼。可以證明，具有循環(huán)性質(zhì)的漢BCH碼的設(shè)計：在工程設(shè)計中，一般不需要用計算方法去尋找生成多項式g(x)。因為前人早已將尋找到的g(x)列成表，故可以用查表法找到所需的生成多項式。教材348/353頁的表11-7給出了碼長n

127的二進制本原BCH碼生成多項式。n=(2m-1)n=(2m-1)BCH碼的設(shè)計：在工程設(shè)計中，一般不需要用計算方法去尋找生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個錯碼。它比漢明碼的糾錯能力強很多。代價：解碼更復(fù)雜，碼率也比漢明碼低。不再是循環(huán)碼。擴展BCH碼：BCH碼的長度都為奇數(shù)。擴展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)個比特11.6.5RS碼——一類具有很強糾錯能力的多進制BCH∵RS碼能夠糾正t個m進制錯碼，即能糾正碼組中t個不超過q位連續(xù)的二進制錯碼，∴RS碼特別適用于存在突發(fā)錯誤的信道，例如，移動通信網(wǎng)等衰落信道中。∵它是多進制糾錯編碼，∴特別適合用于多進制調(diào)制的場合。RS碼的生成多項式：g(x)=(x+

)(x+

2)…(x+

2t)式中，

是伽羅華域GF(2q

)中的本原元素。應(yīng)用∵RS碼能夠糾正t個m進制錯碼，即能糾正碼組中t個不超過q位卷積碼——一種非分組碼§11.7

卷積碼——一種非分組碼§11.7非分組碼概念：分組碼:——每個碼組中的監(jiān)督碼元僅與本碼組中的k個信元有約束關(guān)系。

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

(n,k,N

)N

---

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

---

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

R=k/n(n,1,N

)

簡單,常用N

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

將k比特信息段編成n比特碼組非分組碼概念：分組碼:——每個碼組中的監(jiān)督碼元僅與本碼組一般，k，n較小，N較大；隨著N增大，誤碼率呈指數(shù)下降；更適用于前向糾錯，性能優(yōu)于分組碼，運算簡單。GSM（2,1,5）IS-95（2,1,9）CDMA2000（2,1,9)……一般，k，n較小，N較大；GSM（2,1,5）11.7.1卷積碼的基本原理編碼器原理方框圖存儲以前的k(N-1)個信息碼當前

K個共有N

段移存器，每段k

級

11.7.1卷積碼的基本原理編碼器原理方框圖存儲以前的k如圖所示的(n,k,N)=

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

段移存器，每段1

級（存儲1個信元）

每次輸入1b，輸出3b

分析：信息位---如圖所示的(n,k,N)=(3,1,3)設(shè)移存器初始是全零狀態(tài)，當輸入信息序列

：則編碼器輸出序列：結(jié)果為系統(tǒng)碼形式。設(shè)移存器初始是全零狀態(tài)，當輸入信息序列：則編碼器輸出序列：ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi－1bitt輸入輸出信息位bi的監(jiān)督位和各信息位之間的約束關(guān)系如下圖中虛線所示：（編碼約束度N=3，約束長度nN=3×3=9）ci-2di-2ei-2ci-1di-1ei-1cidiei卷積碼的表述方法：卷積碼的表述方法：11.7.2卷積碼的代數(shù)表述上式：表示的卷積碼也是一種線性碼。——可完全由H

或G

所確定。監(jiān)督矩陣生成矩陣11.7.2卷積碼的代數(shù)表述上式：表示的卷積碼也是一種線分類：代數(shù)解碼：——利用編碼本身的代數(shù)結(jié)構(gòu)進行解碼，不考慮信道的統(tǒng)計特性。概率解碼（最大似然解碼）：——基于信道的統(tǒng)計特性和卷積碼的特點進行計算。11.7.3卷積碼的解碼如：大數(shù)邏輯解碼（門限解碼），適用nN較短的卷積碼。

序貫解碼:適用無記憶信道維特比算法：當碼的nN較短時，效率更高、速度更快約束長度分類：代數(shù)解碼：概率解碼（最大似然解碼）：11.7.3卷2

卷積碼的幾何表述 —維特比解碼算法的基礎(chǔ)1）碼樹圖以前面(3,1,3)

卷積碼為例：并設(shè)M1，M2和M3的初始狀態(tài)000(n,k,N)2卷積碼的幾何表述1）碼樹圖以前面(3,1,3)卷(3,1,3)

碼樹圖：觀察1規(guī)定(3,1,3)碼樹圖：觀察1規(guī)定

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

1 1 0 1編碼輸出111110

010100

(3,1,3)

碼樹圖：觀察2若信息位1 M1M2M3110011101100M3M20111100100狀態(tài)11011101M1M2M3110011101100M3M201111001(3,1,3)

碼樹圖：觀察3(3,1,3)碼樹圖：觀察3若信息位

1 1 0 1編碼輸出111110

010100

碼樹圖原則上還可用于解碼。發(fā)送序列?010110不實用基礎(chǔ)若信息位1 1 0 2）狀態(tài)圖碼樹圖

狀態(tài)圖由(3,1,3)編碼器結(jié)構(gòu)可知：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)圖：由表看出：abcd000111101110010011100001前一狀態(tài)a只能轉(zhuǎn)按照表中的規(guī)律由表看出：abcd000abcd000111101110010011100001利用狀態(tài)圖可方便地從輸入序列得到輸出序列。例如：輸入信息位

1 1 0

1編碼輸出111110

010100

111110010100abcd000111101110010011100001利用第4時隙后完全是第3時隙的重復(fù)，因（3,1,3）碼約束長度為3。3）網(wǎng)格圖將狀態(tài)圖在時間上展開

網(wǎng)格圖5個時隙abcd000111101110010011100001第4時隙后完全是第3時隙的重復(fù)，因（3,1,3）碼約束長度為當輸入信息位為11010時，在網(wǎng)格圖中的編碼路徑：這時的輸出編碼序列：111110010100011…。基于上面的狀態(tài)圖和網(wǎng)格圖，討論維特比解碼算法。當