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

（n,k）線性分組碼§11.5

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

即每個碼字的監(jiān)督碼元是信息碼元的線性組合。基本概念代數(shù)碼：建立在代數(shù)學基礎(chǔ)上的編碼。---監(jiān)督關(guā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”的位置表示相應(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)的。將上面漢明碼例子中的監(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)督位附在其后。∵由它可以產(chǎn)生整個碼組，即有:G

矩陣的性質(zhì)

①

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

的關(guān)系

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

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

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

都應(yīng)滿足式：∴對于接收碼組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

個線性無關(guān)的碼組構(gòu)成。引思：那么，如何尋找這k個線性無關(guān)的碼組呢？因此，用這ｋ個線性無關(guān)的碼組可構(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)碼的編碼設(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)=

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，預(yù)留給督元?！玫接嗍?/p>

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)。設(shè)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)碼。截短目的：在設(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.4BCH碼——解決了生成多項式與糾錯能力的關(guān)系問題，可以在給定糾錯能力要求的條件下尋找到碼的生成多項式。——有了生成多項式，編碼的基本問題就隨之解決了。BCH碼的重要性:何謂BCH碼？BCH碼的分類：漢明碼是能夠糾正單個隨機錯誤的碼?？梢宰C明，具有循環(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碼。BCH碼的設(shè)計：在工程設(shè)計中，一般不需要用計算方法去尋找生成多項式g(x)。因為前人早已將尋找到的g(x)列成表，故可以用查表法找到所需的生成多項式。教材353頁的表11-7給出了碼長n127的二進制本原BCH碼生成多項式。nktg(x)nktg(x)17212333419121222212232472716635343514566471334765657324534046524443073357107613543000671717773537在上表中的(23,12)碼稱為戈萊(Golay)碼。其最小碼距為7，能糾3個隨機錯碼；其生成多項式系數(shù)(5343)8=(101011100011)2，對應(yīng)g(x)=x11+x9+x7+x6+x5+x+1，且解碼容易，實際應(yīng)用較多。BCH碼的長度都為奇數(shù)。在應(yīng)用中，為了得到偶數(shù)長度的碼，并增大檢錯能力，可以在BCH碼生成多項式中乘上一個因式(x+1)，從而得到擴展BCH碼(n+1,k)。擴展BCH碼相當于在原BCH碼上增加了一個校驗位，因此碼距比原BCH碼增加1。擴展BCH碼已經(jīng)不再具有循環(huán)性。例如，廣泛實用的擴展戈萊碼(24,12)，其最小碼距為8，碼率為1/2，能夠糾3個錯碼和檢4個錯