管理信息學第4章課件

4.4

信息傳輸的抗干擾性2023/9/211信道及信道容量信道編碼二元線性碼線性碼的編碼與譯碼循環(huán)碼循環(huán)碼的編碼與譯碼抗干擾信道編碼定理信道的一般數學模型4.4.1

信道及信道容量其中X表示輸入，Y表示輸出，條件概率P(Y|X)表示它們之間的統(tǒng)計依賴關系（稱為轉移概率分布）。這個數學模型也可以寫作{X

P(Y|X)Y}。2023/9/212信道矩陣設輸入X的符號表是{a1,a2,…,an}，輸出Y的符號表是{b1,b2,…,bm}。將P(Y|X)用如下矩陣的方式表示：稱為該信道的信道矩陣。其中行表示輸入X，列表示輸出Y，p(bj|ai)（i=1,…,n j=1,…,

m）表示輸入是ai，輸出是bj的條件概率。4.4.1

信道及信道容量2023/9/213互信息公式：互信息表示當收到bj后，可以提取到的關于ai的信息量。上式稱

I(X;

Y)是

Y對

X

的平均互信息量，簡稱平均互信息。平均互信息

I(X;

Y)克服了互信息的隨機性，成為一個確定的量，因此可以作為信道中信息流通的測度。4.4.1

信道及信道容量2023/9/214假設信源

X的熵為

H(X)，我們希望在信道輸出端接收到的信息量就是

H(X)，但由于干擾的存在，一般情況下只能接收到

I(X;

Y)。它是平均意義上每傳送一個符號流經信道的信息量。可以把I(X;Y)理解為信道的信息傳輸率（或信息率）:R

=

I

(X;Y)2023/9/2154.4.1

信道及信道容量由于

I(

X;Y)是信源概率分布

P(X)和信道轉移概率分

布

P(Y|X)

的函數。給定一個信道，其

P(Y|X)

是固定的，因此，I(X;Y)

隨信源概率分布

P(X)的變化而變化，調整

P(X)，在接收端就能獲得不同的信息量。而總能找到某一種

P(X)（即某一種信源），使信道所能傳送的信息率達到最大。定義這個最大的信息傳輸率為信道容量，記為

C。C

=

maxR

=

maxI(X;Y)2023/9/2164.4.1

信道及信道容量有時我們關心的是信道在單位時間內能夠傳輸的最大信息量。若信道平均傳輸一個符號需要事件t，則單位時間的信道容量為Ct的單位是比特/秒，用bit/s表示。Ct

實際上是信道的最大信息傳輸速率。4.4.1

信道及信道容量2023/9/217二元對稱傳送檢錯與糾錯原理極大似然譯碼法2023/9/2184.4.2

信道編碼二元數字信息：是用二元數域F2={0,1}中的數字0與1組成的數組或向量F2中的加法運算：0+0=1+1=0，0+1=1+0=1F2中的乘法運算：1·1=1，1·0=0·1=0·0=0通常用同樣長度的二元數組代表一個信息集合中的信息。如前文的英文字母示例。2023/9/2194.4.2

信道編碼：二元對稱傳送如果在傳送過程中，傳送任何一個信息是否發(fā)生錯誤與前面已傳送的信息是否發(fā)生了錯誤無關，則稱這種傳送為無記憶傳送。在無記憶傳送過程中，如果發(fā)送1收到0的概率與發(fā)送0收到1的概率都是p，且發(fā)送1收到1的概率與發(fā)送0收到0的概率都是1-p，即錯誤傳送的概率為p，正確傳送概率為1-p，則稱這種傳送為二元對稱傳送。一般p遠小于1/2。二元對稱傳送2023/9/21104.4.2

信道編碼：二元對稱傳送抗干擾編碼：數字信息在傳送過程中會受到各種可能的干擾而出現錯誤，這樣收到的信息可能就不是傳送的原信息。

抗干擾的有效做法是在采用種種技術措施的同時，在信息傳

送前進行一次抗干擾編碼，再傳送抗干擾編碼后的數字信息?？垢蓴_編碼有檢錯編碼與糾錯編碼，檢錯編碼是檢查有無錯誤發(fā)生的編碼，糾錯編碼是能糾正已發(fā)生錯誤的編碼。2023/9/21114.4.2

信道編碼：檢錯與糾錯原理例(奇偶校驗碼)：設原信息是長為5的二元向量，在傳送前編碼如下：顯然有σ(c)的6個分量之和為0。傳送σ(c)，設收到的向量是r=(r0,r1,r2,r3,r4,r5)，則:若 ，則在傳送過程中一定發(fā)生了錯誤，且有奇數個分量發(fā)生了錯誤；否則傳送過程可能沒有發(fā)生錯誤，也可能發(fā)生了偶數個錯誤。4.4.2

信道編碼：檢錯與糾錯原理2023/9/2112定義4.1

設原信息集合是F2上k維向量組成的向量空間Vk，σ是Vk到Vn

的一個單射(n>k)，則稱Vk

的全體象C

=σ(Vk)為碼，C中的每一個n維向量為碼字，碼字的分量稱為碼元。如果任一碼字在傳送過程中有≤t

個錯誤發(fā)生，而收信方可以檢查出有無錯誤發(fā)生，則稱這個碼

C

可以檢查

t

個差錯的檢錯碼，并稱σ為檢錯編碼；如果收信方可以從收到的字正確譯出發(fā)送方發(fā)送的碼字，則稱碼

C

是可以糾正

t

個差錯的糾錯碼，并稱σ為糾錯編碼。稱k為信息長度，n為碼長，k/n為碼C的信息率。2023/9/21134.4.2

信道編碼：檢錯與糾錯原理示例k=5n=6碼空間Vn2023/9/2114碼字碼元原信息空間Vk映射

4.4.2

信道編碼：檢錯與糾錯原理重復編碼如果p

=0.01，從統(tǒng)計意義上講，每發(fā)送100個符號就可能有一個錯誤產生，這顯然不能滿足傳輸的要求。如果我們把信道輸入符號重復傳輸N次，即對于信源符號

“0”，信道輸入端不只發(fā)一個“0”，而是連續(xù)發(fā)N個“0”；對于信源符號“1”，信道輸入端不只發(fā)一個“1”，而是連續(xù)發(fā)

N個“1”。則輸入{0,1}變?yōu)?00…0,

11…1)，輸出則從{0,1}變?yōu)镹維空間中的某個向量。2023/9/21154.4.2

信道編碼：檢錯與糾錯原理若N=3，則單符號離散無記憶信道的信道矩陣為轉變?yōu)殡x散無記憶信道的三次擴展信道的信道矩陣4.4.2

信道編碼：檢錯與糾錯原理2023/9/2116考慮信道的無記憶性，因此，三次擴展信道的信道矩陣可表示為：在信道輸入符號“0”和“1”等概率的條件下，“0”的碼字“000”和“1”的碼字“111”亦等概率，即采用最大后驗概率準則選擇譯碼規(guī)則，則可得譯碼規(guī)則為：F(000)=F(001)=F(010)=F(100)=000

,F(011)=F(110)=F(101)=F(111)=1114.4.2

信道編碼：檢錯與糾錯原理2023/9/2117其最小平均錯誤譯碼概率經過簡單的重復信道編碼，同樣采用最大后驗概率準則選擇譯碼規(guī)則，平均錯誤譯碼概率的最小值差不多要比不進行信道編碼時降低兩個數量級，從而提高了通信的可靠性。4.4.2

信道編碼：檢錯與糾錯原理2023/9/2118定義4.2

在二元對稱傳送中，若收到字A

=(a

1

,a

2

,…,an

)，則稱發(fā)送碼字c

=(c1

,c2

,…,cn

)∈C

而收到A

的概率為前向傳送概率。如果發(fā)送碼字CA

收到A的前向傳送概率達到最大值，即2023/9/2119則將A

譯為CA，稱這種譯碼方法為極大似然譯碼法(Maximumlikelihood

decoding)。4.4.2

信道編碼：極大似然譯碼法在二元對稱傳送中，如果收到字A

=(a1,a2,…,an)，則對任何碼字c

=(c1,c2,…,cn)∈C，其前向傳送概率為：2023/9/2120其中e是傳送碼字c時發(fā)生錯誤的分量個數，因為p<1/2,故當e

最小時，前向傳送概率達到最大。從而極大似然譯碼法是將A譯為與A對應分量不同的分量個數最少的碼字。4.4.2

信道編碼：極大似然譯碼法4.4.2

信道編碼：極大似然譯碼法示例2023/9/2121定義4.3:

設X

=(x1,

x2,…,

xn)、

Y

=(y1,

y2,…,

yn)，則稱

X

與

Y對應分量不相等的分量個數為X

與Y

的漢明(Hamming)距離，記為d(X,Y)。若記則

d(X,Y)

=

d(x1,y1)

+

d(x2,y2)

+

…

d(xn,yn)4.4.2

信道編碼：極大似然譯碼法2023/9/2122漢明距離性質：(1)(非負且有界性) 0

≤d(X,Y)≤n；(2)(自反性)

d(X,Y)=

0當且僅當X=Y；(3)(對稱性)

d(X,Y)=d(Y,X)；(4)(三角不等式)

d(X,Z)≤d(X,Y)+d(Y,Z)2023/9/21234.4.2

信道編碼：極大似然譯碼法設收到字A，在所有碼字中，如果c是與A的漢明距離最小的碼字（即c是發(fā)生傳送錯誤分量個數最少的碼字而成為A的），從而在所有碼字中，c

是前向傳送概率最大而成為A的碼字，因此應將A譯為c，從而等價于將A譯成與A的漢明距離最小的碼字。例1:設碼C=｛0000，0011，1000，1100，0001，1001｝，在二元對稱傳送中，如果收到A=0111，試問根據極大似然譯碼法，應將

A譯為哪一個碼字?解：先計算漢明距離，再判斷。2023/9/21244.4.2

信道編碼：極大似然譯碼法漢明距離譯碼定義4.4:

設C是至少包含2個碼字的碼，稱d(C)

=

min{

d(X,Y)

|

X,Y∈C，X

≠

Y}為碼C的極小距離。若碼長為n、極小距離為d的碼C含有M個碼字，則稱C是(n,

M,

d)碼。例：在碼長為5的碼C=｛00000，00011，00111，11111｝中，由于d(00011，00111)=1，而其它任何兩個不同碼字的漢明距離都≥2，故d(C)=1，從而C是(5，4，1)碼。2023/9/21254.4.2

信道編碼：極大似然譯碼法錯碼；+1，則C是不能檢查t

+1

個差錯的檢錯碼。若d

(C)≥2t

+1，則C是可以糾正t

個差錯的糾若d(C)=2t

+1，則C是不能糾正t

+1

個差錯的糾錯碼。檢錯與糾錯能力定理定理4.1：設C是碼長為n的二元碼。（1）若d(C)≥t

+1，則C是可以檢查t

個差錯的檢錯碼；若d(C)=t

例：{0000,0101,1010,1111}；t

=1?？蓹z2023/9/2126（2）查1個錯誤，但不能檢查2個錯誤4.4.2

信道編碼：極大似然譯碼法tABDFEd(C)≥t+12023/9/21274.4.2

信道編碼：極大似然譯碼法幾何意義(1)d

(C)≥

2t+1tAB2023/9/2128EFD4.4.2

信道編碼：極大似然譯碼法幾何意義(2)存在的問題在碼字個數較少，碼長較小的情況下，譯碼是容易實現的；而當碼字數量很大(如軍事通信中碼字一般多達2100個)，上述譯碼方法幾乎不可能實現，因此編碼的任務之一是要找出有很好的數學結構的碼，以便譯碼方便。2023/9/21294.4.2

信道編碼：極大似然譯碼法4.4.3

二元線性碼2023/9/2130有限域上的線性空間線性碼的生成矩陣與校驗矩陣線性碼的漢明重量極大似然譯碼法要將接收到的字A與碼C中的每一個碼字結合計算前向傳送概率或漢明距離，當

n

較大或碼字較多時，譯碼工作量十分巨大。因此研究并構造具有很好數學結構的碼具有非常重要的意義。線性碼是最基礎的也是最重要的碼。有限域上的線性空間根據線性代數的知識，F2n

={(α1,α2,…,αn)|

αi∈F2

,i=1,

2,…,n}是F2上的n維線性空間。(2n)定義4.5

設C

是F

2

上線性空間V

的非空子集，如果C

也是F

2

上線性空間，則稱C是V的子空間。2023/9/21314.4.3

二元線性碼：有限域上的線性空間容易證明，F2

上線性空間V

的非空子集C

是V

的子空間的充要條件是：對?X,Y∈C，?k1,k2∈F2，恒有:k1X

+

k2Y

∈

C若α1,α2,…,αk∈V，容易證明S

=

{

λ1α1+λ2α2+…+λkαk

|

λi∈F2

,

i=1,2,…,k

}是V的子空間(共有2k個n維向量)，并稱S

是由α1,α2,…,αk生成的子空間，記為span{α1,α2,…,αk}。2023/9/21324.4.3

二元線性碼：有限域上的線性空間定義4.6:

設則稱：為X與Y的內積；如果X·Y=0，則稱X與Y正交。4.4.3

二元線性碼：有限域上的線性空間2023/9/2133正交子空間定理4.2

設C是F2上線性空間F2n的子空間，令則C⊥

是F2

的子空間，且

dimC

+dimC

=n。n

⊥證明：(1)

若a1、a2∈C⊥，則k1a1

+k2a2

∈C⊥(2)若dimC=k，則存在k個線性無關的向量構成C子空間的基，而C⊥中的任意向量X應與C的每個基向量正交。則X的基礎解系含有n-k個解向量。4.4.3

二元線性碼：有限域上的線性空間2023/9/2134線性碼定義4.7:稱F2

的任一子空間C

是長為n

的線性碼，并n稱子空間C

的維數為線性碼C

的維數，仍記為dimC。并記長為n、維數為k

的線性碼為［n，k］線性碼。2023/9/2135

設C⊥是線性空間F2

的子空間C的正交補子空間，則Cn

⊥也是長為n的線性碼，稱C⊥是線性碼C的對偶碼；當C⊥=C時，稱C是自對偶碼。S={1000,0100,0000,1100}是[4,2]線性碼4.4.3

二元線性碼：線性碼的生成矩陣與校驗矩陣線性碼的碼字個數定理4.3:

設C是二元[

n,

k]線性碼，則(1)

C恰好含有M=2k個碼字；(2)當C是自對偶碼時，k

=n/2。證明提示：(1)若dimC=k，則存在k個線性無關的向量構成C子空間的基，對于C中的任意向量可用k個基向量線性表示。2023/9/21364.4.3

二元線性碼 ：線性碼的生成矩陣與校驗矩陣生成矩陣設C是二元［n，k］線性碼，α1

=

(

α11

,

α12,

…,

α1n

),α2

=

(

α21,

α22,

…,

α2n

),…αk

=

(

αk1,

αk2,

…,

αkn

)是C

在F2

上的一組基2023/9/21374.4.3

二元線性碼 ：線性碼的生成矩陣與校驗矩陣則對?c∈C，存在惟一一組常數λ1, λ2,…,

λk∈F2，使對?

λ1,

λ2,…,

λk∈F2，由于C

是線性空間，α1,

α2,…,

αk∈C，故λ1α1

+

λ2α2

+

…

+

λkαk

=

(λ1,

λ2,…,

λk)G

∈

C因此C

={

c

|

c=(λ1,

λ2,…,

λk)G, λ1,

λ2,

…,

λk∈F2}4.4.3

二元線性碼 ：線性碼的生成矩陣與校驗矩陣2023/9/2138為［n,k］線性碼C的生定義4.8

稱成矩陣。若C是［n,k］線性碼，則C⊥是［n,n-k］線性碼。設h1,h2,…,hn-k是C⊥的基，則是C⊥的生成矩陣。4.4.3

二元線性碼 ：線性碼的生成矩陣與校驗矩陣2023/9/2139檢驗矩陣定理

4.4

設

C

是［

n

，

k

］線性碼，

H

是

C陣，對?X=(x1,x2,…,xn)∈F2n，則X∈C的充要條件是HXT=0。2023/9/2140⊥證明提示：

（

1

）若

X

∈

C

，對于

C

中構成基向量均與X正交，故有HXT=0。（2）因為HXT=0，而C⊥中的任一向量Y可由H生成，所以X與C⊥中的任意向量正交，故X屬于C⊥的正交子空間即C空間。4.4.3

二元線性碼 ：線性碼的生成矩陣與校驗矩陣定義4.9

稱C⊥的生成矩陣H為C的校驗矩陣。若G與H分別是線性碼C的生成矩陣與校驗矩陣，則HGT

=0從而GHT

=(HGT)T

=0T

=0H與G之間相互惟一確定。2023/9/21414.4.3

二元線性碼 ：線性碼的生成矩陣與校驗矩陣例2

設C是二元［6，3］線性碼，其校驗矩陣為求該碼C的生成矩陣和碼字解：由HXT=0得線性方程組4.4.3

二元線性碼 ：線性碼的生成矩陣與校驗矩陣2023/9/2142解得該方程組的基礎解系為則C的生成矩陣為當取 中每一個向量時，由可得C的所有碼字為4.4.3

二元線性碼 ：線性碼的生成矩陣與校驗矩陣2023/9/2143定義4.10

設X

∈F

n

，稱X的非零分量個數為X的漢明重量，2023/9/21442記為wt(X)，并稱wt(C)=min{wt(X)|

X

∈C,X

≠0}為線性碼C的漢明重量。定理

4.5

設C是二元線性碼，則C的漢明重量等于C的極小距離，即d(C)

=

wt(C)。證明提示：(1)

d

(C

)=min{d

(X

,Y

)}，wt

(C

)=min{d

(X

,0)},d(C)≤wt(C)(2)

d(C)

=min{d(X,

Y)}=

min{

wt(X+Y)

}

≥min{

wt(X)

}

=wt(C)4.4.3

二元線性碼 ：線性碼的漢明重量的校驗矩2023/9/2145二元線性碼的檢錯和糾錯能力定理

4.6

設

H

是二元［

n

，

k

］線性碼

C的任意t列都線性無關，且H有t+1列線性相關，則d(C)

=wt(C)=t+

1C是可檢t個錯誤的檢錯碼，且C是可糾[t/2]個錯誤的糾錯碼4.4.3

二元線性碼二元線性碼的檢錯和糾錯能力證明提示：（1）①任何碼字c∈C的漢明重量均≥t+1。設wt(c)=r，則存在r個分量不為0，由于HcT=0，從而H中有r個向量(與c的對應分量不為0的向量)線性相關，所以r≥t+1；②存在某個碼字c，wt(c)=t+1。因為H中存在t+1列線性相關的向量r1,r2,…,rt+1，則存在一組全不為零的系數λ1、λ2、…、λt+1，使得r1

λ1

+r2

λ2

+…+rt+1

λt+1=0令c={λ1,λ2,…,λt+1，0,0,…,0}，則滿足HcT=0，故c∈C且wt(c)=t+12023/9/21464.4.3

二元線性碼4.4.4

線性碼的編碼與譯碼2023/9/2147線性碼的編碼線性碼的譯碼設C是［n,k］線性碼，則C含有2k個碼字。設G是C的生成矩陣，對

,則存在惟一一組常數 使:另一方面，對任意一組常數則即惟一決定一個碼字。4.4.4

線性碼的編碼與譯碼：線性碼的編碼2023/9/2148因此，對若令則σ

是對原始信息集合F2n

的一個編碼4.4.4

線性碼的編碼與譯碼：線性碼的編碼2023/9/2149例:

設C是二元［6，3］線性碼，其生成矩陣為求原始信息A=110,

B=010的編碼。解：A=110的編碼c為：c

=

AG

=

(110)=

(011110)4.4.4

線性碼的編碼與譯碼：線性碼的編碼2023/9/2150B=010的編碼d為：d

=

BG

=

(010)=

(101010)4.4.4

線性碼的編碼與譯碼：線性碼的編碼2023/9/2151在實際問題中當n較大或碼字個數巨大時，譯碼工作非常困難，甚至無法實現。下面利用線性碼的特點，降低譯碼的計算量及難度。?設是C的校驗矩陣；設是收到的字。如果 ，則X是C中一個碼字，否則X不是C中碼字，傳送中出現了錯誤。利用陪集概念引入校驗子，簡化譯碼過程。4.4.4

線性碼的編碼與譯碼：線性碼的譯碼2023/9/2152定義4.11

設C是F2上線性碼，對

?X∈F2n，稱集合為X所在的陪集，有時也記為X+C。0100,

1000,

1100}

為

[4,

2]

線性碼，對2023/9/2153例：

設

C

={0000,X∈F2

,4X

=0001，則X+C={0001,0101,

1001,1101}X

=0010，則X+C={0010,0110,

1010,1110}X

=0011，則X+C={0011,0111,

1011,1111}4.4.4

線性碼的編碼與譯碼：線性碼的譯碼陪集定理4.7:

設C是二元［n，k］線性碼，則F2n中每個向量一定在C的某個陪集中，且兩個不同的陪集不相交，所有陪集的并為F2n

；對?X、Y∈F2n

，則X與Y屬于C的同一個陪集，當且僅當X+Y∈C；對?

X

∈

F

2

n

，則 恰好含有2

k

個向量，且F

2

n

關于C

恰好有2n-k個不同陪集。稱一個陪集中漢明重量最小的向量為該陪集的陪集頭。4.4.4

線性碼的編碼與譯碼：線性碼的譯碼陪集2023/9/21544.4.4

線性碼的編碼與譯碼：線性碼的譯碼校驗子定義4.12

設 是二元［n,

k］線性碼的校驗矩陣，對 ，稱 為字

X的校驗子。顯然S(X)是 維向量。定理4.8

設C是［n,

k］線性碼，則有S(X

+

Y)=

S(X)+

S(Y)X∈C當且僅當S(X)=0(3)(4)S

(

X

)

=

S

(

Y

)當且僅當X與Y在C的同一個陪集中共有 個不同的校驗子2023/9/2155例 設C是二元［6，3］線性碼，其校驗矩陣為求A1=110110

,

A2=111111的校驗子解：S(A1)

= A1HT

=

(

101

)S(A2)

=A2HT

=

(

111

)4.4.4

線性碼的編碼與譯碼：線性碼的譯碼2023/9/2156譯碼過程(1)構造［n，k］線性碼C的譯碼表：將F2n中2n個向量排成2n-k行2k列的一個表，表中有一條虛線將2n-k行分成上下兩部分；將C中的向量排在第1行，將零碼字排在第1行的第1列，并將C中的2k-1個非零碼字任意排在第1行的第2列一直到第2k列；將F2n關于C的2n-k-1個不同陪集排成2n-k-1行，同一陪集中的2k個向量排在同一行，并將每個陪集的校驗子放在此行的最左邊作為標記；若某陪集中，有唯一的陪集頭X，則將此行排在譯碼表中虛線上方，將陪集頭X排在這一行的第1列，并將 排在碼字c同一列；若某陪集中有多個陪集頭，則將該行排在譯碼表中虛線下方，且任取一個陪集頭X排在該行的第一列，也將 排在碼字c的同一列。4.4.4

線性碼的編碼與譯碼：線性碼的譯碼2023/9/2157譯碼過程(2)根據譯碼表譯碼：當收到字為A時，先計算A的校驗子S

(A

)=AH

T

，如果S

(A

)=0

，則將A

譯為A

；否則檢查校驗子S

(A是否在虛線上方，若在虛線上方，則將A譯為第一行中與A同列的碼字c；如果校驗子S(A)在虛線下方，則無法譯碼。2023/9/21584.4.4

線性碼的編碼與譯碼：線性碼的譯碼例 設C是二元［6，3］線性碼，其校驗矩陣為該列碼C的譯碼表設收到的字A1=110110,

A2=111111

，試譯A1,A2解：(1)

求生成矩陣。由HXT=0得線性方程組4.4.4

線性碼的編碼與譯碼：線性碼的譯碼2023/9/2159解得該方程組的基礎解系