信息論基礎

第4章抗干擾二元編碼韓宇輝6/23/20241第4章抗干擾二元編碼4.1抗干擾二元編碼的基本概念4.2檢錯碼4.3用于單向信道的簡單糾錯碼4.4糾一位錯誤的漢明碼4.5循環碼4.6糾正獨立錯誤的卷積碼4.7糾正突發錯誤的編碼4.8有限域的基本知識6/23/202424.1抗干擾二元編碼的基本概念6/23/202434.1.1抗干擾編碼的基本思想000110110011奇校驗抗干擾編碼的基本思想：利用剩余的增加來換取可靠性的提高信息元監督元許用碼字：系統實際使用的碼字。001,010,100,111禁用碼字：系統中不使用的碼字。000,011,101,1106/23/202444.1.2幾個定義①碼距（漢明距離）W=x1x2…xn

xi∈{0,1}W’=x1’x2’…xn’xi’

∈{0,1}②最小碼距（最小漢明距離）一個碼組（碼字）集合中，兩碼字間的最小距離dmin稱為該碼字集合的最小距離，簡稱最小碼距。③碼重（漢明重量）碼組中所含碼元“1”的數量，稱為該碼組的重量，簡稱碼重。6/23/202454.1.3最小碼距與糾檢錯能力的關系1.譯碼準則X:{x1,x2,…,xn}Y:{y1,y2,…,ym}P(Y/X):{p(yj/xi);i=1,2,…n;j=1,2,…m這時定義一個收到yj后判定為xi的單值函數，即：F(yj)=xi(i=1,2,…n;j=1,2,…m)；這個函數稱為譯碼函數。它構成一個譯碼函數組，這些函數的值組成了譯碼準則。對于有n個輸入，m個輸出的信道來說，可以有nm個不同的譯碼準則。6/23/202462.最小碼距譯碼準則若d(x*j,yj)≤d(xi,yj)

(對一切的i)，則F(yj)=x*j(j=1,2,…m，x*j

∈X)3.最小碼距與糾檢錯能力的關系【例】X：{0000000,1111111}，

dmin=7檢錯能力：發送碼字：接收碼字：判斷結果：糾錯能力：發送碼字：接收碼字：譯碼結果：00000000000000√00000000000000√10000000000000√11000000000000√11100001111111

×11110001111111

×11111001111111

×11111101111111

×11111110000000最多可以發現6位錯誤0000000傳輸正確√

最多可以糾正3位錯誤1000000傳輸錯誤

√

1100000傳輸錯誤

√

1110000傳輸錯誤

√

1111000傳輸錯誤√

1111100傳輸錯誤

√

1111110傳輸錯誤√

1111111傳輸正確

×

6/23/20247糾錯同時檢錯的能力糾正1位錯誤：發送碼字：接收碼字：判斷結果：譯碼結果：糾正2位錯誤：發送碼字：接收碼字：判斷結果：譯碼結果：0000000000000010000001100000111000011110001111100111111011111110000000最多可以同時發現5位錯誤0000000傳輸正確√

1000000傳輸錯誤√

1100000傳輸錯誤√

1110000傳輸錯誤√

1111000傳輸錯誤√

1111100傳輸錯誤√

1111110傳輸錯誤√1111111傳輸正確

×

最多可以同時發現4位錯誤0000000

√0000000

√不進行譯碼不進行譯碼不進行譯碼不進行譯碼1111111

×1111111

×傳輸正確√

傳輸錯誤√

傳輸錯誤√

傳輸錯誤√

傳輸錯誤√

傳輸錯誤√

傳輸錯誤√傳輸正確

×

0000000

√0000000

√0000000√不進行譯碼√不進行譯碼1111111

×1111111

×1111111

×6/23/20248若發現e個錯誤，則要求dmin≥e+1;若糾正t個錯誤，則要求dmin≥2t+1;若糾正t個錯誤，同時發現e個錯誤，則要求dmin≥t+e+1（t<e

）6/23/202494.1.4抗干擾編碼的基本原理1.原理：

dmin與糾檢錯能力的關系2.實現方法：信息元+監督元3.代數編碼：信息元與監督元是按一定的代數關系互相制約的。(1)分組碼（塊碼）

k—信息位長度

n—碼長

r=n-k—監督位長度特點：無記憶性(n,k)分組碼的碼率（編碼效率）：η=R/C=H(A)/Hmax(A)=k/n邏輯網絡12k12n......6/23/202410分組碼按其結構可以分為系統碼和非系統碼。如果在一個分組碼碼字中，信息元安排在前k位，而監督元安排在后n-k=r位，則稱其為系統碼，否則就稱為非系統碼。(2)卷積碼（連環碼）

m=m’+1—編碼器的約束長度或編碼約束長度

n=n0×m—卷積碼的約束長度

特點：有記憶性，輸出不僅與當時的輸入有關，還與前m’個單位時間的輸入有關。(n0,k0,m)卷積碼的碼率（編碼效率）：η=k0/n0時序網絡12k012n0......6/23/2024114.抗干擾編碼的分類(1)用途：檢錯碼和糾錯碼(2)干擾的性質：糾正獨立錯誤的編碼和糾正突發錯誤的編碼

獨立錯誤也稱為隨機錯誤，是由隨機噪聲引起的，其特點是各碼元發生錯誤與否是互相獨立的，因而一般不會成片地出現錯誤。

突發錯誤是由突發噪聲（脈沖噪聲、深衰落、接觸不良引起噪聲等）引起的，其特點是各碼元是否發生錯誤存在某種相關性。通常稱突發錯誤持續時間內的碼元數目為突發長度。(3)對信息的處理方式：分組碼和卷積碼(4)約束關系：線性碼和非線性碼(5)信息元的位置：系統碼和非系統碼6/23/2024125.差錯控制系統的分類(1)ARQ(AutomaticRepeatreQuest)自動反饋重傳采用檢錯碼，接收端收到碼字后判斷在傳輸中有無錯誤產生，并通過反饋信道把檢測結果告訴發送端。發端把收端認為有錯的消息再次傳送，直到收端認為正確為止。優點：譯碼設備簡單，由于同一種碼的檢錯能力比糾錯能力要高得多，因而整個系統能獲得極低的誤碼率。缺點：應用ARQ方式必須有一條從收端至發端的反饋信道，只適用于點對點的方式，并要求收、發兩端必須互相配合，其控制電路比較復雜，實時性也較差。6/23/202413(2)FEC(ForwardErrorCorrection)前向糾錯采用糾錯碼，接收端收到碼字后，自動地糾正傳輸中的錯誤。優點：不需要反饋信道，既適用于點對點的方式，也適用于點對多點的方式，實時性較好，控制電路也比較簡單。缺點：譯碼設備較復雜，編碼效率較低。(3)HFC(HybridErrorCorrection)混合糾錯是前兩種方式的結合。發端發送的碼既能檢錯、又有一定的糾錯能力。收端譯碼時若發現錯誤個數在碼的糾錯能力以內，則自動進行糾錯；若錯誤個數超過了碼的糾錯能力，但能檢測出來，則通過反饋信道告知發方重發。6/23/2024144.2檢錯碼6/23/202415一致監督檢錯碼也叫一致監督校驗碼或奇偶校驗碼。1.原理：信息元（k位）：x1，x2，…，xk監督元（1位）：xn=xk+1偶校驗：奇校驗：4.2.1一致監督檢錯碼6/23/2024162.漏檢概率奇偶校驗碼只能發現碼字中的奇數個錯誤，不能發現偶數個錯誤。n為偶數：n為奇數：若，則6/23/202417定比碼也稱恒比碼、等重碼或范·德倫碼，每個碼字中“1”與“0”的比例是固定的，“1”的個數也是固定的。

1.五三定比碼五三定比碼每個碼字的碼長為5，含有3個“1”和2個“0”的碼字作為許用碼字。

(1)許用碼字數目：

禁用碼字數目：4.2.2定比碼6/23/202418

(2)漏檢概率若“1”錯成“0”的數目正好等于“0”錯成“1”的數目，則五三定比碼不能發現這類錯誤。一個碼字中有2位錯誤，且其中1位“1”錯成“0”，1位“0”錯成“1”的概率為一個碼字中有4位錯誤，且其中2位“1”錯成“0”，2位“0”錯成“1”的概率為因此，漏檢概率為當時，6/23/202419(3)編碼效率

η=R/C=H/Hmax=log10/log32≈66%2.七三定比碼七三定比碼每個碼字的碼長為7，含有3個“1”和4個“0”的碼字作為許用碼字。

(1)許用碼字數目：

禁用碼字數目：

(2)編碼效率

η=R/C=H/Hmax=log35/log128≈72%6/23/202420

(3)漏檢概率一個碼字中有2位錯誤，且其中1位“1”錯成“0”，1位“0”錯成“1”的概率為一個碼字中有4位錯誤，且其中2位“1”錯成“0”，2位“0”錯成“1”的概率為一個碼字中有6位錯誤，且其中3位“1”錯成“0”，3位“0”錯成“1”的概率為因此，漏檢概率為當時，6/23/2024214.3用于單向信道的簡單糾錯碼6/23/202422編碼效率：η=1/n(1)逐位重復：用于糾正隨機錯誤。(2)逐段重復：還可用于糾正突發錯誤。例如，10110100逐位重復，三重碼：111000111111000111000000逐段重復，四位一段，三重碼：10111011

101101000100

01004.3.1簡單重復碼將信息重復多次，只要正確傳輸的次數多于傳錯的次數，則可以將錯誤糾正過來。重復次數n通常為奇數。6/23/2024234.4糾一位錯誤的漢明碼6/23/2024241.線性分組碼的定義若分組碼的監督元與信息元之間是一種線性約束關系，則稱其為線性分組碼。(n,k)線性分組碼的碼率：η=k/n許用碼字數目：2k禁用碼字數目：2n-2k系統碼：[x1x2…xk

xk+1xk+2…xn]信息元監督元6/23/2024252.線性分組碼的監督矩陣線性分組碼監督元與信息元之間的線性關系可以用二元域上的線性方程組描述。整理得：6/23/202426將方程組用矩陣方程來表示，可得監督矩陣[H][H][C]T=[0]碼字向量[C]=[x1

x2…xn

]6/23/202427r×k子陣Pr×r單位陣Irr=n-k行：r個監督元，r個監督方程n列：n個碼元之間的監督關系(n,k)系統線性分組碼監督矩陣形式:(典型監督矩陣或標準監督矩陣)[H]=[P

Ir]6/23/2024283.線性分組碼的生成矩陣6/23/202429碼字[C]信息碼組[m]生成矩陣[G]由于對于矩陣A，B，C有因此[C]=[m][G]6/23/202430[G]=[Ik

PT](n,k)系統線性分組碼生成矩陣形式:(典型生成矩陣或標準生成矩陣)子陣PTk×k單位陣Ikk行×n列6/23/202431【例】已知線性分組碼的生成矩陣[G]，寫出信息碼組[m1]=[1000]，[m2]=[0100]，[m3]=[0010]，[m4]=[0001]，[m5]=[1100]，[m6]=[1110]，[m7]=[1111]對應的各個碼字。

[C1]=[m1][G]=[1000][G]=[1000011][C2]=[m2][G]=[0100][G]=[0100101][C3]=[m3][G]=[0010][G]=[0010110][C4]=[m4][G]=[0001][G]=[0001111]解：6/23/202432

[C5]=[m5][G]=[1100][G]=[1100110][C6]=[m6][G]=[1110][G]=[1110000][C7]=[m7][G]=[1111][G]=[1111111](n,k)線性分組碼的2k個碼字構成二元n重矢量空間中的一個k維子空間。(n,k)線性分組碼的生成矩陣由k個線性無關的碼字矢量組成，構成k維子空間的一個基底，其線性組合可以生成所有的碼字。6/23/202433【例】已知線性分組碼的監督矩陣為判斷其碼長和信息位長度，并寫出其生成矩陣[G]。解：r=3，n=7，

k=4[H]=[P

I3][G]=[I4

PT]6/23/2024344.線性分組碼的譯碼(1)錯誤圖樣發送碼字：接收碼字：錯誤圖樣：ei=1表明相應位有錯，ei=0表明相應位無錯。6/23/202435(2)校驗矩陣定義[S]=[H][R]T為校驗矩陣，也稱為校驗子或伴隨式。若[S]=0，表明收到的碼字為許用碼字，譯碼器認為接收碼字無錯誤。若[S]≠0，表明收到的碼字為禁用碼字，可以判定接收碼字一定有錯誤。由于因此校驗子與發送碼字無關，而僅與錯誤圖樣有關。6/23/202436(3)校驗子與譯碼【例】(7,4)線性分組碼的監督矩陣為(1)無錯

[E]=[0000000](2)錯一位

[E]=[1000000][E]=[0100000][E]=[0010000]

[S]=[H][E]T=[000]T…[S]=[H][E]T=[011]T[S]=[H][E]T=[101]T[S]=[H][E]T=[110]T6/23/202437若校驗子為[0]，認為收到的碼字沒有錯誤；若校驗子恰好等于[H]的第i列，認為接收碼字的第i位發生了錯誤。線性分組碼可以糾正1位錯誤需滿足的條件：

[H]的各個列不同且不含有全0列；

2r-1≥n。6/23/2024385.漢明碼(1)漢明碼的定義對于任意正整數r≥3，存在有下列參數的線性分組碼：碼長：n

≤2r-1信息位：k=n-r監督位：r=n-k最小碼距：dmin=3

這種碼稱為漢明碼。若n

=2r-1稱為狹義漢明碼或完備漢明碼；若n

<2r-1稱為廣義漢明碼。(2)漢明碼[H]矩陣的構造將2r-1非全0的r維列向量作為[H]的各列。6/23/202439【例】構造(7,4)漢明碼的監督矩陣。解：n=7，k=4，r=n-k=3。由于n

=2r-1，故為狹義漢明碼。將7個非全0的3維列向量作為[H]的各列即可。或系統碼非系統碼6/23/202440(3)漢明碼的錯誤譯碼概率①狹義漢明碼狹義漢明碼可以糾正一位錯誤，因此其錯誤譯碼概率為：由于當時，有因此當時，有所以6/23/202441②廣義漢明碼

廣義漢明碼可以糾正一位錯誤，還可以糾正部分2位及2位以上的錯誤，因此其錯誤譯碼概率：比如，(6,3)廣義漢明碼的監督矩陣為錯2位時：若第1位和第6位錯，或者第2位和第5位錯，或者第3位和第4位錯，校驗子均為[111]T。因此，不妨規定當校驗子為[111]T時，譯作第1位和第6位錯。此時，該廣義漢明對于第1位和第6位錯這種錯兩位的情況也可以糾正。6/23/202442(4)增余漢明碼在漢明碼的基礎上，再增加一位監督元，使漢明碼的最小碼距dmin=4，可以在糾一位錯的同時檢兩位錯，這種線性分組碼稱為增余漢明碼。增加的監督元通常取為原漢明碼所有碼元的模2和，也就是說增余漢明碼的[H]矩陣是在原漢明碼[H]矩陣的最右側加上一個全0列，再在下面加上一個全為1的行。6/23/202443(7,4)漢明碼(8,4)增余漢明碼[H]矩陣的各個列不同，且任何兩列之和不同于另一列，因此可以糾1位錯的同時檢出2位錯。增余漢明碼的構成方法不唯一。

1

1

1

1

1

1

1

1

1

1

1

0

0

0

0

16/23/2024444.5循環碼6/23/2024451.循環碼的定義具有循環移位自閉性的線性分組碼稱為循環碼。所謂循環移位自閉性是指碼字集合中的任何一個碼字的循環移位也是該碼字集合中的一個碼字。若C(0)=[cn-1,cn-2,……c1,c0]∈C(C為許用碼字集合)

，

則C(1)=[cn-2,cn-3,……c0,cn-1]∈C。0000000001110101001110111010循環碼1001110101001111010011110100循環碼000001010011信息碼100101110111信息碼(7,3)系統循環碼6/23/2024462.循環碼的多項式描述一個(n,k)循環碼的碼字c=[cn-1,cn-2,……,c1,c0]可以用一個二元域上的n-1次多項式表示：

c(x)=cn-1xn-1+cn-2xn-2+……+c1x+c0

ci

∈{0,1}

這個多項式稱為碼字多項式或碼多項式。碼字矢量的向左循環移位一次可以用x乘上C(x)后取模xn-1(或xn+1)來表示。模xn-1相當于xn-1=0，即xn=1

xc(x)=x(cn-1xn-1+cn-2xn-2+……+c1x+c0)=cn-1xn+cn-2xn-1+……+c1x2+c0

x=cn-2xn-1+……+c1x2+c0

x+cn-1(模xn-1)6/23/2024473.循環碼的生成多項式定義：(n,k)循環碼中，次數最低的非0碼多項式是唯一的，其次數為r=n-k次。該多項式稱為循環碼的生成多項式。

g(x)=grxr+gr-1xr-1+……+g1x+g0（gr=g0=1）g(x),xg(x),x2g(x),…,xk-1g(x)為k個線性無關的碼字，可以作為該循環碼生成矩陣的k行。6/23/202448信息碼組[m]=[mk-1,mk-2,…,m0]對應的碼多項式為：

c(x)=[mk-1,mk-2,…,m0][G(x)]=mk-1xk-1g(x)+mk-2xk-2g(x)+…+m0g(x)=m(x)g(x)結論：所有循環碼的碼多項式都是其生成多項式g(x)的倍式；反之，任何次數不大于n-1次的多項式也一定是碼多項式。6/23/2024494.循環碼的編碼(1)非系統循環碼c(x)=m(x)g(x)【例】已知(7,4)循環碼的生成多項式為g(x)=x3+x+1，求信息碼組[0101]對應的循環碼碼字。解：

m(x)=x2+1

c(x)=m(x)g(x)=(x2+1)(x3+x+1)=x5+x3+x2+x3+x+1=x5+x2+x+1[C]=[0100111]6/23/202450(2)系統循環碼信息多項式m(x)=mk-1xk-1+mk-2xk-2+…+m0所對應的系統循環碼的碼多項式c(x)應滿足如下條件：①

c(x)的次數不大于n-1次，即可以表示c(x)=cn-1xn-1+cn-2xn-2+……+c1x+c0；②

c(x)為g(x)的倍式；③

cn-1=mk-1，cn-2=mk-2，…，cn-k=m0。系統循環碼編碼步驟：

①

②

(r(x)次數≤n-k-1)

③6/23/202451由于因此可見，c(x)為g(x)的倍式，條件②滿足。6/23/202452【例】(7,4)循環碼g(x)=x3+x+1，求m=[1010]的系統循環碼碼字。解：m(x)=x3+x

xn-km(x)=x3(x3+x)=x6+x4

C(x)=xn-km(x)+r(x)=x6+x4+x+1；[C]=[1010011]x3x6+x4+x3

x3

除式x6+x4x3+x+1+1x3+x+1x+1被除式商式余式6/23/202453(3)如何確定g(x)?定理1：(n,k)循環碼的生成多項式g(x)是xn-1的因式。定理2：若g(x)是一個n-k次多項式，且為xn-1的因式，則g(x)一定可以生成一個(n,k)循環碼。例如，x7-1=(x+1)(x3+x2+1)(x3+x+1)(7,6)循環碼：g(x)=(x+1)(7,4)循環碼：g(x)=x3+x2+1或g(x)=x3+x+1(7,3)循環碼：g(x)=(x+1)(x3+x2+1)

或g(x)=(x+1)(x3+x+1)(7,1)循環碼：g(x)=(x3+x2+1)(x3+x+1)結論：xn-1的諸因式決定了所有碼長為n的循環碼。6/23/2024545.循環碼的譯碼發送碼字多項式：c(x)=cn-1xn-1+cn-2xn-2+……c1x+c0錯誤圖樣多項式：e(x)=en-1xn-1+en-2xn-2+……e1x+e0接收碼字多項式：c’(x)=cn-1’xn-1+cn-2’xn-2+……+c1’x+c0’

c’(x)=c(x)+e(x)校驗子多項式：s(x)≡c’(x)≡

e(x)[模g(x)]

s(x)=sr-1xr-1+sr-2xr-2+…+s0

——r-1次多項式若s(x)

=0，表明收到的碼字為許用碼字，譯碼器認為接收碼字無錯誤。若s(x)≠0，表明收到的碼字為禁用碼字，可以判定接收碼字一定有錯誤。6/23/202455【例】(7,4)循環碼g(x)=x3+x+1，求接收碼字不錯或只錯一位時的校驗子多項式。e(x)s(x)[s2,s1,s0]0000011001xx010x2x2100x3x+1011x4x2+x110x5x2+x+1111x6x2+11016/23/202456這個表給出了接收碼字不出錯或只錯一位時校驗子多項式和校驗子矢量的結果。根據這個表可以進行譯碼。例如，發送碼字多項式為c(x)=x4+x2+x

接收碼字多項式為c’(x)=x4+x3+x2+x

g(x)=x3+x+1

校驗子多項式為：s(x)≡c’(x)[模g(x)]=x+1

查表可知e(x)=x3

因此

c(x)=c’(x)+e(x)=x4+x2+x

發送碼字為00101106/23/2024576.截短循環碼通常xn-1只能分解出不多的幾個因式，因此使得給定長度為n的循環碼的數量往往很少。為了克服這個缺點，出現了截短循環碼。對于一個(n,k)循環碼，若取所有前i個信息元均為0的碼字構成一個子集(0<i<k)，其監督位長度不變，信息位長度減少至k-i位，則得到一個(n-i,k-i)碼，稱為截短循環碼或縮短循環碼。截短循環碼是原循環碼的子集，因此它的最小碼距保證了它的糾錯能力不會低于原來的(n,k)循環碼。6/23/202458截短循環碼的[H]矩陣可以從原碼的[H]矩陣中除去前i列而得到，[G]矩陣可以從原碼的[G]矩陣中除去前i列和前i行而得到。例如，可以由(7,4)循環碼構成(5,2)截短循環碼。(7,4)循環碼(5,2)截短循環碼6/23/202459截短循環碼的[H]矩陣可以從原碼的[H]矩陣中除去前i列而得到，[G]矩陣可以從原碼的[G]矩陣中除去前i列和前i行而得到。例如，可以由(7,4)循環碼構成(5,2)截短循環碼。(7,4)循環碼(5,2)截短循環碼6/23/2024604.6糾正獨立錯誤的卷積碼6/23/202461卷積碼的最大特點是有記憶性，(n0,k0,m)卷積碼編碼器在j時刻輸出與j，j-1，j-2，…，j-m+1共m個單位時間的輸入有關。m