管理信息學(xué)第4章課件

2023/7/294.4信息傳輸?shù)目垢蓴_性4.4.1

信道及信道容量4.4.2

信道編碼4.4.3

二元線性碼4.4.4

線性碼的編碼與譯碼4.4.5

循環(huán)碼4.4.6

循環(huán)碼的編碼與譯碼4.4.7

抗干擾信道編碼定理2023/7/29信道的一般數(shù)學(xué)模型4.4.1信道及信道容量

其中X表示輸入，Y表示輸出，條件概率P(Y|X)表示它們之間的統(tǒng)計(jì)依賴關(guān)系（稱為轉(zhuǎn)移概率分布）。這個(gè)數(shù)學(xué)模型也可以寫作{

XP(Y|X)Y}。2023/7/29信道矩陣設(shè)輸入X的符號(hào)表是{a1,a2,…,an}，輸出Y的符號(hào)表是{b1,b2,…,bm}。將P(Y|X)用如下矩陣的方式表示：稱為該信道的信道矩陣。其中行表示輸入X，列表示輸出Y，p(bj|ai)（i=1,…,nj=1,…,m）表示輸入是ai，輸出是bj的條件概率。4.4.1信道及信道容量2023/7/29互信息公式：互信息表示當(dāng)收到bj后，可以提取到的關(guān)于ai的信息量。上式稱I(X;Y)

是Y對(duì)X的平均互信息量，簡(jiǎn)稱平均互信息。平均互信息I(X;Y)

克服了互信息的隨機(jī)性，成為一個(gè)確定的量，因此可以作為信道中信息流通的測(cè)度。4.4.1信道及信道容量2023/7/29假設(shè)信源X的熵為H(X)，我們希望在信道輸出端接收到的信息量就是H(X)，但由于干擾的存在，一般情況下只能接收到I(X;Y)。它是平均意義上每傳送一個(gè)符號(hào)流經(jīng)信道的信息量。

可以把I(X;Y)理解為信道的信息傳輸率（或信息率）:

R=I(X;Y)4.4.1信道及信道容量2023/7/29由于I(X;Y)是信源概率分布P(X)和信道轉(zhuǎn)移概率分布P(Y|X)的函數(shù)。給定一個(gè)信道，其P(Y|X)是固定的，因此，I(X;Y)隨信源概率分布P(X)的變化而變化，調(diào)整P(X)，在接收端就能獲得不同的信息量。

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

C=maxR=maxI(X;Y)4.4.1信道及信道容量2023/7/29有時(shí)我們關(guān)心的是信道在單位時(shí)間內(nèi)能夠傳輸?shù)淖畲笮畔⒘?。若信道平均傳輸一個(gè)符號(hào)需要事件t，則單位時(shí)間的信道容量為

Ct的單位是比特/秒，用bit/s表示。Ct實(shí)際上是信道的最大信息傳輸速率。4.4.1信道及信道容量2023/7/29二元對(duì)稱傳送檢錯(cuò)與糾錯(cuò)原理極大似然譯碼法4.4.2信道編碼2023/7/29二元數(shù)字信息：是用二元數(shù)域F2={0,1}中的數(shù)字0與1組成的數(shù)組或向量F2中的加法運(yùn)算：0+0=1+1=0，0+1=1+0=1F2中的乘法運(yùn)算：1·1=1，1·0=0·1=0·0=0通常用同樣長(zhǎng)度的二元數(shù)組代表一個(gè)信息集合中的信息。如前文的英文字母示例。4.4.2信道編碼：二元對(duì)稱傳送2023/7/29如果在傳送過程中，傳送任何一個(gè)信息是否發(fā)生錯(cuò)誤與前面已傳送的信息是否發(fā)生了錯(cuò)誤無關(guān)，則稱這種傳送為無記憶傳送。在無記憶傳送過程中，如果發(fā)送1收到0的概率與發(fā)送0收到1的概率都是p，且發(fā)送1收到1的概率與發(fā)送0收到0的概率都是1-p，即錯(cuò)誤傳送的概率為p，正確傳送概率為1-p，則稱這種傳送為二元對(duì)稱傳送。一般p遠(yuǎn)小于1/2。二元對(duì)稱傳送4.4.2信道編碼：二元對(duì)稱傳送2023/7/29

抗干擾編碼：數(shù)字信息在傳送過程中會(huì)受到各種可能的干擾而出現(xiàn)錯(cuò)誤，這樣收到的信息可能就不是傳送的原信息?？垢蓴_的有效做法是在采用種種技術(shù)措施的同時(shí)，在信息傳送前進(jìn)行一次抗干擾編碼，再傳送抗干擾編碼后的數(shù)字信息?？垢蓴_編碼有檢錯(cuò)編碼與糾錯(cuò)編碼，檢錯(cuò)編碼是檢查有無錯(cuò)誤發(fā)生的編碼，糾錯(cuò)編碼是能糾正已發(fā)生錯(cuò)誤的編碼。4.4.2信道編碼：檢錯(cuò)與糾錯(cuò)原理2023/7/29

例(奇偶校驗(yàn)碼)：設(shè)原信息是長(zhǎng)為5的二元向量，在傳送前編碼如下：顯然有σ(c)的6個(gè)分量之和為0。傳送σ(c)，設(shè)收到的向量是r=(r0,r1,r2,r3,r4,r5)，則:

若，則在傳送過程中一定發(fā)生了錯(cuò)誤，且有奇數(shù)個(gè)分量發(fā)生了錯(cuò)誤；否則傳送過程可能沒有發(fā)生錯(cuò)誤，也可能發(fā)生了偶數(shù)個(gè)錯(cuò)誤。4.4.2信道編碼：檢錯(cuò)與糾錯(cuò)原理2023/7/29定義4.1

設(shè)原信息集合是F2上k維向量組成的向量空間Vk，σ是Vk到Vn的一個(gè)單射(n>k)，則稱Vk的全體象C=σ(Vk)為碼，C中的每一個(gè)n維向量為碼字，碼字的分量稱為碼元。如果任一碼字在傳送過程中有≤t個(gè)錯(cuò)誤發(fā)生，而收信方可以檢查出有無錯(cuò)誤發(fā)生，則稱這個(gè)碼C可以檢查t個(gè)差錯(cuò)的檢錯(cuò)碼，并稱σ為檢錯(cuò)編碼；如果收信方可以從收到的字正確譯出發(fā)送方發(fā)送的碼字，則稱碼C是可以糾正t個(gè)差錯(cuò)的糾錯(cuò)碼，并稱σ為糾錯(cuò)編碼。稱k為信息長(zhǎng)度，n為碼長(zhǎng)，k/n為碼C的信息率。4.4.2信道編碼：檢錯(cuò)與糾錯(cuò)原理2023/7/29示例k=5n=6碼空間Vn碼字碼元原信息空間Vk映射4.4.2信道編碼：檢錯(cuò)與糾錯(cuò)原理2023/7/29如果p=0.01，從統(tǒng)計(jì)意義上講，每發(fā)送100個(gè)符號(hào)就可能有一個(gè)錯(cuò)誤產(chǎn)生，這顯然不能滿足傳輸?shù)囊?。如果我們把信道輸入符?hào)重復(fù)傳輸N次，即對(duì)于信源符號(hào)“0”，信道輸入端不只發(fā)一個(gè)“0”，而是連續(xù)發(fā)N個(gè)“0”；對(duì)于信源符號(hào)“1”，信道輸入端不只發(fā)一個(gè)“1”，而是連續(xù)發(fā)N個(gè)“1”。則輸入{0,1}變?yōu)?00…0,11…1)，輸出則從{0,1}變?yōu)镹維空間中的某個(gè)向量。重復(fù)編碼4.4.2信道編碼：檢錯(cuò)與糾錯(cuò)原理2023/7/29若N=3，則單符號(hào)離散無記憶信道的信道矩陣為轉(zhuǎn)變?yōu)殡x散無記憶信道的三次擴(kuò)展信道的信道矩陣

4.4.2信道編碼：檢錯(cuò)與糾錯(cuò)原理2023/7/29考慮信道的無記憶性，因此，三次擴(kuò)展信道的信道矩陣可表示為：在信道輸入符號(hào)“0”和“1”等概率的條件下，“0”的碼字“000”和“1”的碼字“111”亦等概率，即采用最大后驗(yàn)概率準(zhǔn)則選擇譯碼規(guī)則，則可得譯碼規(guī)則為：F(000)=F(001)=F(010)=F(100)=000,F(011)=F(110)=F(101)=F(111)=1114.4.2信道編碼：檢錯(cuò)與糾錯(cuò)原理2023/7/29其最小平均錯(cuò)誤譯碼概率經(jīng)過簡(jiǎn)單的重復(fù)信道編碼，同樣采用最大后驗(yàn)概率準(zhǔn)則選擇譯碼規(guī)則，平均錯(cuò)誤譯碼概率的最小值差不多要比不進(jìn)行信道編碼時(shí)降低兩個(gè)數(shù)量級(jí)，從而提高了通信的可靠性。4.4.2信道編碼：檢錯(cuò)與糾錯(cuò)原理2023/7/29定義4.2

在二元對(duì)稱傳送中，若收到字A=(a1,a2,…,an)，則稱發(fā)送碼字c=(c1,c2,…,cn)∈C而收到A的概率為前向傳送概率。如果發(fā)送碼字CA收到A的前向傳送概率達(dá)到最大值，即則將A譯為CA，稱這種譯碼方法為極大似然譯碼法(Maximumlikelihooddecoding)。4.4.2信道編碼：極大似然譯碼法2023/7/29

在二元對(duì)稱傳送中，如果收到字A=(a1,a2,…,an)，則對(duì)任何碼字c=(c1,c2,…,cn)∈C，其前向傳送概率為：其中e是傳送碼字c時(shí)發(fā)生錯(cuò)誤的分量個(gè)數(shù)，因?yàn)閜<1/2,故當(dāng)e最小時(shí)，前向傳送概率達(dá)到最大。從而極大似然譯碼法是將A譯為與A對(duì)應(yīng)分量不同的分量個(gè)數(shù)最少的碼字。4.4.2信道編碼：極大似然譯碼法2023/7/29示例4.4.2信道編碼：極大似然譯碼法2023/7/29定義4.3:

設(shè)X=(x1,x2,…,xn)、Y=(y1,y2,…,yn)，則稱X與Y對(duì)應(yīng)分量不相等的分量個(gè)數(shù)為X與Y的漢明(Hamming)距離，記為d(X,Y)。若記則d(X,Y)=d(x1,y1)+d(x2,y2)+…

d(xn,yn)4.4.2信道編碼：極大似然譯碼法2023/7/29漢明距離性質(zhì)：(1)(非負(fù)且有界性)0≤d(X,Y)≤n；(2)(自反性)d(X,Y)=0當(dāng)且僅當(dāng)X=Y；

(3)(對(duì)稱性)d(X,Y)=d(Y,X)；(4)(三角不等式)d(X,Z)≤d(X,Y)+d(Y,Z)4.4.2信道編碼：極大似然譯碼法2023/7/29漢明距離譯碼設(shè)收到字A，在所有碼字中，如果c是與A的漢明距離最小的碼字（即c是發(fā)生傳送錯(cuò)誤分量個(gè)數(shù)最少的碼字而成為A的），從而在所有碼字中，c是前向傳送概率最大而成為A的碼字，因此應(yīng)將A譯為c，從而等價(jià)于將A譯成與A的漢明距離最小的碼字。

例1:設(shè)碼C=｛0000，0011，1000，1100，0001，1001｝，在二元對(duì)稱傳送中，如果收到A=0111，試問根據(jù)極大似然譯碼法，應(yīng)將A譯為哪一個(gè)碼字?

解：先計(jì)算漢明距離，再判斷。4.4.2信道編碼：極大似然譯碼法2023/7/29

定義4.4:

設(shè)C是至少包含2個(gè)碼字的碼，稱d(C)=min{d(X,Y)|X,Y∈C，X≠Y}為碼C的極小距離。若碼長(zhǎng)為n、極小距離為d的碼C含有M個(gè)碼字，則稱C是(n,M,d)碼。例：在碼長(zhǎng)為5的碼C=｛00000，00011，00111，11111｝中，由于d(00011，00111)=1，而其它任何兩個(gè)不同碼字的漢明距離都≥2，故d(C)=1，從而C是(5，4，1)碼。4.4.2信道編碼：極大似然譯碼法2023/7/29定理4.1

：設(shè)C是碼長(zhǎng)為n的二元碼。（1）若d(C)≥t+1，則C是可以檢查t個(gè)差錯(cuò)的檢錯(cuò)碼；若d(C)=t+1，則C是不能檢查t+1個(gè)差錯(cuò)的檢錯(cuò)碼。（2）若d(C)≥2t+1，則C是可以糾正t個(gè)差錯(cuò)的糾錯(cuò)碼；若d(C)=2t+1，則C是不能糾正t+1個(gè)差錯(cuò)的糾錯(cuò)碼。檢錯(cuò)與糾錯(cuò)能力定理例：{0000,0101,1010,1111}；t=1?？蓹z查1個(gè)錯(cuò)誤，但不能檢查2個(gè)錯(cuò)誤4.4.2信道編碼：極大似然譯碼法2023/7/29AtBDFE幾何意義(1)d(C)≥t+14.4.2信道編碼：極大似然譯碼法2023/7/29d(C)≥2t+1幾何意義(2)AtBEFD4.4.2信道編碼：極大似然譯碼法2023/7/29存在的問題

在碼字個(gè)數(shù)較少，碼長(zhǎng)較小的情況下，譯碼是容易實(shí)現(xiàn)的；而當(dāng)碼字?jǐn)?shù)量很大(如軍事通信中碼字一般多達(dá)2100個(gè))，上述譯碼方法幾乎不可能實(shí)現(xiàn)，因此編碼的任務(wù)之一是要找出有很好的數(shù)學(xué)結(jié)構(gòu)的碼，以便譯碼方便。4.4.2信道編碼：極大似然譯碼法2023/7/294.4.3二元線性碼

有限域上的線性空間線性碼的生成矩陣與校驗(yàn)矩陣線性碼的漢明重量2023/7/29

極大似然譯碼法要將接收到的字A與碼C中的每一個(gè)碼字結(jié)合計(jì)算前向傳送概率或漢明距離，當(dāng)n較大或碼字較多時(shí)，譯碼工作量十分巨大。因此研究并構(gòu)造具有很好數(shù)學(xué)結(jié)構(gòu)的碼具有非常重要的意義。線性碼是最基礎(chǔ)的也是最重要的碼。有限域上的線性空間根據(jù)線性代數(shù)的知識(shí)，F(xiàn)2n={(α1,α2,…,αn)|αiF2,i=1,2,…,n}是F2上的n維線性空間。(2n)

定義4.5

設(shè)C是F2上線性空間V的非空子集，如果C也是F2上線性空間，則稱C是V的子空間。4.4.3二元線性碼：有限域上的線性空間2023/7/29

容易證明，F(xiàn)2上線性空間V的非空子集C是V的子空間的充要條件是：對(duì)X,YC，k1,k2F2，恒有:k1X+k2YC

若α1,α2,…,αkV，容易證明S={λ1α1+λ2α2+…+λkαk|λiF2,i=1,2,…,k}是V的子空間(共有2k個(gè)n維向量)，并稱S是由α1,α2,…,αk生成的子空間，記為span{α1,α2,…,αk}。4.4.3二元線性碼：有限域上的線性空間2023/7/29定義4.6:

設(shè)則稱：為X與Y的內(nèi)積；如果X·Y=0，則稱X與Y正交。

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

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

是F2n的子空間，且dimC+dimC⊥=n。證明：

(1)若a1、a2C⊥

，則k1a1+k2a2C⊥(2)若dimC=k，則存在k個(gè)線性無關(guān)的向量構(gòu)成C子空間的基，而C⊥中的任意向量X應(yīng)與C的每個(gè)基向量正交。則X的基礎(chǔ)解系含有n-k個(gè)解向量。4.4.3二元線性碼：有限域上的線性空間2023/7/29線性碼

定義4.7:

稱F2n的任一子空間C是長(zhǎng)為n的線性碼，并稱子空間C的維數(shù)為線性碼C的維數(shù)，仍記為dimC。并記長(zhǎng)為n、維數(shù)為k的線性碼為［n，k］線性碼。設(shè)C⊥是線性空間F2n的子空間C的正交補(bǔ)子空間，則C⊥也是長(zhǎng)為n的線性碼，稱C⊥是線性碼C的對(duì)偶碼；當(dāng)C⊥=C時(shí)，稱C是自對(duì)偶碼。

S={1000,0100,0000,1100}是[4,2]線性碼4.4.3二元線性碼：線性碼的生成矩陣與校驗(yàn)矩陣2023/7/29線性碼的碼字個(gè)數(shù)定理4.3:

設(shè)C是二元[n,k]線性碼，則

(1)C恰好含有M=2k個(gè)碼字；

(2)當(dāng)C是自對(duì)偶碼時(shí)，k=n/2。證明提示：

(1)若dimC=k，則存在k個(gè)線性無關(guān)的向量構(gòu)成C子空間的基，對(duì)于C中的任意向量可用k個(gè)基向量線性表示。4.4.3二元線性碼：線性碼的生成矩陣與校驗(yàn)矩陣2023/7/29生成矩陣設(shè)C是二元［n，k］線性碼，

α1=(α11,α12,…,α1n),

α2=(α21,α22,…,α2n),…αk=(αk1,αk2,…,αkn)

是C在F2上的一組基4.4.3二元線性碼：線性碼的生成矩陣與校驗(yàn)矩陣2023/7/29則對(duì)cC，存在惟一一組常數(shù)λ1,λ2,…,λkF2，使對(duì)λ1,λ2,…,λkF2，由于C是線性空間，α1,α2,…,αkC，故λ1α1+λ2α2+…+λkαk=(λ1,λ2,…,λk)GC因此C={c|c=(λ1,λ2,…,λk)G,λ1,λ2,…,λkF2}4.4.3二元線性碼：線性碼的生成矩陣與校驗(yàn)矩陣2023/7/29定義4.8

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

4.4.3二元線性碼：線性碼的生成矩陣與校驗(yàn)矩陣2023/7/29檢驗(yàn)矩陣定理4.4

設(shè)C是［n，k］線性碼，H是C的對(duì)偶碼C⊥的生成矩陣，對(duì)X=(x1,x2,…,xn)F2n，則XC的充要條件是HXT=0。證明提示：（1）若XC

，對(duì)于C⊥中構(gòu)成生成矩陣H的任一基向量均與X正交，故有HXT=0。（2）因?yàn)镠XT=0，而C⊥中的任一向量Y可由H生成，所以X與C⊥中的任意向量正交，故X屬于C⊥的正交子空間即C空間。4.4.3二元線性碼：線性碼的生成矩陣與校驗(yàn)矩陣2023/7/29定義4.9

稱C⊥的生成矩陣H為C的校驗(yàn)矩陣。若G與H分別是線性碼C的生成矩陣與校驗(yàn)矩陣，則HGT=0從而GHT=(HGT)T=0T=0H與G之間相互惟一確定。4.4.3二元線性碼：線性碼的生成矩陣與校驗(yàn)矩陣2023/7/29例2設(shè)C是二元［6，3］線性碼，其校驗(yàn)矩陣為求該碼C的生成矩陣和碼字解：由HXT=0得線性方程組4.4.3二元線性碼：線性碼的生成矩陣與校驗(yàn)矩陣2023/7/29解得該方程組的基礎(chǔ)解系為則C的生成矩陣為當(dāng)取中每一個(gè)向量時(shí)，由可得C的所有碼字為4.4.3二元線性碼：線性碼的生成矩陣與校驗(yàn)矩陣432023/7/29

定義4.10

設(shè)X∈F2n

，稱X的非零分量個(gè)數(shù)為X的漢明重量，記為wt(X)，并稱wt(C)=min{wt(X)|X∈C,X≠0}為線性碼C的漢明重量。定理4.5

設(shè)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/7/29二元線性碼的檢錯(cuò)和糾錯(cuò)能力定理4.6

設(shè)H是二元［n，k］線性碼C的校驗(yàn)矩陣，如果H的任意t列都線性無關(guān)，且H有t+1列線性相關(guān)，則(1)d(C)=wt(C)=t+1(2)C是可檢t

個(gè)錯(cuò)誤的檢錯(cuò)碼，且C是可糾[t/2]個(gè)錯(cuò)誤的糾錯(cuò)碼4.4.3二元線性碼2023/7/29二元線性碼的檢錯(cuò)和糾錯(cuò)能力證明提示：（1）①任何碼字c∈C的漢明重量均≥t+1。設(shè)wt(c)=r，則存在r個(gè)分量不為0，由于HcT=0，從而H中有r個(gè)向量(與c的對(duì)應(yīng)分量不為0的向量)線性相關(guān)，所以r≥t+1；②存在某個(gè)碼字c，wt(c)=t+1。因?yàn)镠中存在t+1列線性相關(guān)的向量r1,r2,…,rt+1，則存在一組全不為零的系數(shù)1、2、…、t+1，使得r11+r22+…+rt+1t+1=0

令c={1,2,…,t+1，0,0,…,0}，則滿足HcT=0，故c∈C且wt(c)=t+14.4.3二元線性碼2023/7/294.4.4線性碼的編碼與譯碼

線性碼的編碼線性碼的譯碼2023/7/29

設(shè)C是［n,k］線性碼，則C含有2k個(gè)碼字。設(shè)G是C的生成矩陣，對(duì),則存在惟一一組常數(shù)使:另一方面，對(duì)任意一組常數(shù)則即惟一決定一個(gè)碼字。4.4.4線性碼的編碼與譯碼：線性碼的編碼2023/7/29因此，對(duì)若令則σ是對(duì)原始信息集合F2n的一個(gè)編碼4.4.4線性碼的編碼與譯碼：線性碼的編碼2023/7/29例:設(shè)C是二元［6，3］線性碼，其生成矩陣為求原始信息A=110,B=010的編碼。解：A=110的編碼c

為：

c=AG=(110)=(011110)4.4.4線性碼的編碼與譯碼：線性碼的編碼2023/7/29

B=010的編碼d

為：

d=BG=(010)=(101010)4.4.4線性碼的編碼與譯碼：線性碼的編碼2023/7/29在實(shí)際問題中當(dāng)n較大或碼字個(gè)數(shù)巨大時(shí)，譯碼工作非常困難，甚至無法實(shí)現(xiàn)。下面利用線性碼的特點(diǎn)，降低譯碼的計(jì)算量及難度。設(shè)是C的校驗(yàn)矩陣；設(shè)是收到的字。如果，則X是C中一個(gè)碼字，否則X不是C中碼字，傳送中出現(xiàn)了錯(cuò)誤。利用陪集概念引入校驗(yàn)子，簡(jiǎn)化譯碼過程。4.4.4線性碼的編碼與譯碼：

線性碼的譯碼2023/7/29陪集定義4.11

設(shè)C是F2上線性碼，對(duì)XF2n，稱集合為X所在的陪集，有時(shí)也記為X+C。例：設(shè)C={0000,0100,1000,1100}為[4,2]線性碼，對(duì)任一X∈F24,(1)X=0001，則X+C={0001,0101,1001,1101}(2)X=0010，則X+C={0010,0110,1010,1110}(3)X=0011，則X+C={0011,0111,1011,1111}4.4.4線性碼的編碼與譯碼：

線性碼的譯碼2023/7/29陪集定理4.7:

設(shè)C是二元［n，k］線性碼，則

(1)F2n中每個(gè)向量一定在C的某個(gè)陪集中，且兩個(gè)不同的陪集不相交，所有陪集的并為F2n

；

(2)對(duì)X、YF2n

，則X與Y屬于C的同一個(gè)陪集，當(dāng)且僅當(dāng)X+Y

C；

(3)對(duì)XF2n，則恰好含有2k個(gè)向量，且F2n關(guān)于C恰好有2n-k個(gè)不同陪集。

稱一個(gè)陪集中漢明重量最小的向量為該陪集的陪集頭。

4.4.4線性碼的編碼與譯碼：

線性碼的譯碼2023/7/294.4.4線性碼的編碼與譯碼：

線性碼的譯碼校驗(yàn)子定義4.12

設(shè)

是二元［n,k］線性碼的校驗(yàn)矩陣，

對(duì)

，稱

為字

X的校驗(yàn)子。顯然S(X)是

維向量。定理4.8

設(shè)C是［n,k］線性碼，則有(1)S(X+Y)=S(X)+S(Y)(2)X∈C當(dāng)且僅當(dāng)S(X)=0(3)S(X)=S(Y)當(dāng)且僅當(dāng)X與Y在C的同一個(gè)陪集中(4)共有

個(gè)不同的校驗(yàn)子2023/7/29例

設(shè)C是二元［6，3］線性碼，其校驗(yàn)矩陣為求A1=110110,A2=111111的校驗(yàn)子解：S(A1)=A1HT=(101)S(A2)=A2HT=(111)4.4.4線性碼的編碼與譯碼：

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

線性碼的譯碼2023/7/29譯碼過程(2)根據(jù)譯碼表譯碼：當(dāng)收到字為A時(shí)，先計(jì)算A的校驗(yàn)子S(A)=AHT，如果S(A)=0，則將A譯為A；否則檢查校驗(yàn)子S(A)是否在虛線上方，若在虛線上方，則將A譯為第一行中與A同列的碼字c；如果校驗(yàn)子S(A)在虛線下方，則無法譯碼。4.4.4線性碼的編碼與譯碼：

線性碼的譯碼2023/7/29例

設(shè)C是二元［6，3］線性碼，其校驗(yàn)矩陣為(1)該列碼C的譯碼表(2)設(shè)收到的字A1=110110,A2=111111，試譯A1,A2解：(1)求生成矩陣。由HXT=0得線性方程組4.4.4線性碼的編碼與譯碼：

線性碼的譯碼2023/7/29解得該方程組的基礎(chǔ)解系為則C的生成矩陣為當(dāng)取中每一個(gè)向量時(shí)，由