差錯(cuò)控制編碼第二次課

差錯(cuò)控制編碼第二次課第一頁，共五十一頁，2022年，8月28日回顧奇偶監(jiān)督碼在接收端解碼時(shí)，實(shí)際上就是在計(jì)算若S＝0，認(rèn)為無錯(cuò)若S＝1，認(rèn)為有錯(cuò)S只有兩種取值，只能代表有、無錯(cuò)兩種信息，不能指出錯(cuò)碼位置。監(jiān)督關(guān)系式校正子第二頁，共五十一頁，2022年，8月28日在（n,k）碼中，為能糾正一位錯(cuò)誤要求在（n,k）碼中，k=4。為能糾正一位錯(cuò)碼，則r至少應(yīng)為多少？第三頁，共五十一頁，2022年，8月28日舉例說明如何構(gòu)造監(jiān)督關(guān)系式：上例中，若取r=3，則n=k+r=7。(7,4)線性分組碼（a6a5a4a3a2a1a0)校正子與錯(cuò)碼位置的對(duì)應(yīng)關(guān)系如表規(guī)定(也可以另外規(guī)定)。第四頁，共五十一頁，2022年，8月28日S1S2S3錯(cuò)碼位置S1S2S3錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無錯(cuò)第五頁，共五十一頁，2022年，8月28日由表可見，當(dāng)一錯(cuò)碼位置在a2,a4，a5或a6時(shí)校正子S1為1；否則S1為0即構(gòu)成如下關(guān)系第六頁，共五十一頁，2022年，8月28日由此解出給定信息位后，可直接按上式算出監(jiān)督位監(jiān)督方程第七頁，共五十一頁，2022年，8月28日信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111第八頁，共五十一頁，2022年，8月28日2、監(jiān)督矩陣H和生成矩陣G

改寫為第九頁，共五十一頁，2022年，8月28日(模2)簡記為

或第十頁，共五十一頁，2022年，8月28日稱為監(jiān)督矩陣H矩陣的各個(gè)行是線性無關(guān)的行數(shù)=監(jiān)督位數(shù)，列數(shù)=碼字長度典型陣r行n列第十一頁，共五十一頁，2022年，8月28日第十二頁，共五十一頁，2022年，8月28日轉(zhuǎn)置得K行r列第十三頁，共五十一頁，2022年，8月28日Q=PT，在Q矩陣的左邊在加上一個(gè)k×k的單位矩陣，就形成了一個(gè)新矩陣G：

典型形式生成矩陣K行n列稱為生成矩陣生成矩陣G的每一行都是一個(gè)碼組第十四頁，共五十一頁，2022年，8月28日G為典型生成矩陣，則得到的碼為系統(tǒng)碼否則得到的碼為非系統(tǒng)碼第十五頁，共五十一頁，2022年，8月28日例【1】已知線性（6，3）碼的生成矩陣為

求（1）信息碼組為101對(duì)應(yīng)的編碼碼組（2）所有許用碼組、各碼組的碼重、最小碼距和該碼的差錯(cuò)控制能力。

第十六頁，共五十一頁，2022年，8月28日第十七頁，共五十一頁，2022年，8月28日第十八頁，共五十一頁，2022年，8月28日例2已知（7，4）碼的生成矩陣為：列出所有許用碼組并求監(jiān)督矩陣第十九頁，共五十一頁，2022年，8月28日例3課后習(xí)題9-61、寫出監(jiān)督方程2、由監(jiān)督方程求出所有許用碼組3、求生成矩陣4、最小碼距？只用于檢錯(cuò)，能檢出幾位錯(cuò)碼？只用于糾錯(cuò)？同時(shí)用于檢錯(cuò)和糾錯(cuò)？第二十頁，共五十一頁，2022年，8月28日若發(fā)送碼組為表示該位接收碼元無錯(cuò)；表示該位接收碼元有錯(cuò)。3、譯碼接收碼組為二者之差為E稱為錯(cuò)誤圖樣第二十一頁，共五十一頁，2022年，8月28日

接收端譯碼時(shí)計(jì)算錯(cuò)誤圖樣與校正子之間有確定的關(guān)系無錯(cuò)時(shí)，S等于零有錯(cuò)，S不等于零。校正子(伴隨式)第二十二頁，共五十一頁，2022年，8月28日糾錯(cuò)-----------只糾一位錯(cuò)誤時(shí)第二十三頁，共五十一頁，2022年，8月28日例4

設(shè)驗(yàn)證3個(gè)接收碼組是否發(fā)生差錯(cuò)？若在某碼組中有錯(cuò)碼，錯(cuò)碼的校正子是什么？然后再指出發(fā)生錯(cuò)碼的碼字中，哪位有錯(cuò)？且有3個(gè)接收碼組第二十四頁，共五十一頁，2022年，8月28日解：1）若無錯(cuò)，則錯(cuò)誤圖樣為0，S為0

B1無錯(cuò)B2錯(cuò)B3錯(cuò)2）∵S2=H第1列∴E=[100000]第1位錯(cuò)同理S3=H第3列∴E=[001000]第3位錯(cuò)第二十五頁，共五十一頁，2022年，8月28日例5、已知一（7，4），監(jiān)督碼元和信息碼元之間的關(guān)系為：求（1）信息碼字I=[0011]時(shí)的編碼碼組（2）如果接收的碼字B=[1000101]，確定收到的碼組是否有錯(cuò)，并糾正。第二十六頁，共五十一頁，2022年，8月28日4、漢明碼（1）碼長滿足（2）最小碼距d0=3（3）編碼效率第二十七頁，共五十一頁，2022年，8月28日§9.4線性分組碼

我們把建立在代數(shù)學(xué)基礎(chǔ)上的編碼稱為代數(shù)碼。在代數(shù)碼中，常見的是線性碼。線性碼中信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的，或者說，線性碼是按一組線性方程構(gòu)成的。

本節(jié)將以漢明(Hamming)碼為例引入線性分組碼的一般原理。第二十八頁，共五十一頁，2022年，8月28日回顧奇偶監(jiān)督碼在接收端解碼時(shí)，實(shí)際上就是在計(jì)算若S＝0，認(rèn)為無錯(cuò)；若S＝1，認(rèn)為有錯(cuò)。上式稱為監(jiān)督關(guān)系式，S稱為校正子。S只有兩種取值，只能代表有、無錯(cuò)兩種信息，不能指出錯(cuò)碼位置。如果監(jiān)督位增加一位，則增加一個(gè)監(jiān)督關(guān)系式。兩個(gè)校正子的可能值有4種組合：00，01，10，11，故能表示4種不同狀態(tài)。第二十九頁，共五十一頁，2022年，8月28日

若用其一種表示無錯(cuò)，則其余3種就可能用來指示一位錯(cuò)碼的3種不同位置。同理r個(gè)監(jiān)督關(guān)系式能指示一位錯(cuò)碼的(2r-1)個(gè)可能位置。一般地，若碼長為n，信息位數(shù)為k，則監(jiān)督位數(shù)r=n-k。如果希望用r個(gè)監(jiān)督位構(gòu)造出r個(gè)監(jiān)督關(guān)系式來指示一位錯(cuò)碼的n種可能位置，則要求

2r-1≥n，或者2r≥r+k+1第三十頁，共五十一頁，2022年，8月28日舉例說明如何構(gòu)造監(jiān)督關(guān)系式：設(shè)(n，k)分組碼中k=4。為了糾正一位錯(cuò)碼，要求監(jiān)督位數(shù)r≥3。若取r=3，則n=k+r=7。校正子與錯(cuò)碼位置的對(duì)應(yīng)關(guān)系如表9—4規(guī)定(也可以另外規(guī)定)。S1S2S3錯(cuò)碼位置S1S2S3錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無錯(cuò)第三十一頁，共五十一頁，2022年，8月28日由表可見，當(dāng)一錯(cuò)碼在a2,a4，a5或a6時(shí)校正子S1為1；否則S1為0.a2,a4，a5和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系。即構(gòu)成如下關(guān)系:

同理在發(fā)送端編碼時(shí)，信息位a6a5a4a3的值決定于輸入信號(hào)，因此它們是隨機(jī)的。監(jiān)督值a2a1ao應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系來確定．即監(jiān)督位應(yīng)使上三式中的值為零(表示編成的碼組中應(yīng)無錯(cuò)碼)，由此得到方程組第三十二頁，共五十一頁，2022年，8月28日由此解出給定信息位后，可直接按上式算出監(jiān)督位，其結(jié)果如表9—5所列。第三十三頁，共五十一頁，2022年，8月28日信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111第三十四頁，共五十一頁，2022年，8月28日

接收端收到每個(gè)碼組后，先按監(jiān)督方程計(jì)算出S1、S2、S3，再按表9—4判斷錯(cuò)碼情況。例：接收0000011，可得：

S1S2S3=011。由表9—4可知在a3位有錯(cuò)碼。

(7，4)漢明碼：最小碼距d0=3糾一個(gè)錯(cuò)碼或檢測兩個(gè)錯(cuò)碼。編碼效率k/n=(2r-1-r)／(2r-1)=I-r／n。當(dāng)n很大時(shí)，則編碼效率接近1。第三十五頁，共五十一頁，2022年，8月28日線性分組碼的—般原理。線性分組碼是指信息位和監(jiān)督位滿足一組線性方程的編碼。改寫為第三十六頁，共五十一頁，2022年，8月28日(模2)簡記為或第三十七頁，共五十一頁，2022年，8月28日稱為監(jiān)督矩陣H矩陣的各個(gè)行是線性無關(guān)的行數(shù)=監(jiān)督位數(shù)，列數(shù)=碼字長度典型陣第三十八頁，共五十一頁，2022年，8月28日第三十九頁，共五十一頁，2022年，8月28日轉(zhuǎn)置得其中：矩陣P第四十頁，共五十一頁，2022年，8月28日稱為典型生成矩陣第四十一頁，共五十一頁，2022年，8月28日生成矩陣G的每一行都是一個(gè)碼組。例如，（參照前頁矩陣G）。利用生成矩陣，碼字再由得，H和G互為正交關(guān)系第四十二頁，共五十一頁，2022年，8月28日譯碼,若發(fā)送碼組為接收碼組為二者之差為其中E稱為錯(cuò)誤圖樣。表示該位接收碼元無錯(cuò)；表示該位接收碼元有錯(cuò)。第四十三頁，共五十一頁，2022年，8月28日

接收端譯碼時(shí)計(jì)算當(dāng)接收碼組無錯(cuò)時(shí)．S等于零有錯(cuò)但不超過檢錯(cuò)能力時(shí)，S不等于零。在錯(cuò)碼超過檢錯(cuò)能力時(shí)，B變?yōu)榱硪辉S用碼組，仍能成立S等于零。這樣的錯(cuò)碼是不可檢測的。S稱為校正子(伴隨式)。S只與E有關(guān)，而與A無關(guān)，意味著S與E有的線性變換關(guān)系，能與E一一對(duì)應(yīng)，可指示錯(cuò)碼位置。第四十四頁，共五十一頁，2022年，8月28日

線性碼重要性質(zhì)之一，是它具有封閉性。若：A1和A2是線性碼中的兩個(gè)許用碼組，則：(A1+A2)仍為其中的一個(gè)碼組。由封閉性，兩個(gè)碼組之間的距離必是另一碼組的重量。故碼的最小距離即是碼的最小重量(除全“0”碼組外)。線性碼又稱群碼，這是由于線性碼的各許用碼組構(gòu)成代數(shù)學(xué)中的群。第四十五頁，共五十一頁，2022年，8月28日9.3.4線性分組碼的譯碼

碼字Ci

接收字R

Ci的估值干擾

1.差錯(cuò)圖案

線性分組碼C

的任一碼字Ci=(ci1,ci

2,…,cin)經(jīng)信道傳輸后，接收到字

R

=(r

1,r2,…,rn)；令

E=R-Ci=

(r

1-

ci1,r2-ci2,…,rn-cin);

這里稱

E為差錯(cuò)圖案。根據(jù)模2運(yùn)算的性質(zhì)，E=R+Ci

E=0則R是碼C的碼字；否則，R不是碼C

的碼字。對(duì)于二元(n,k)碼，差錯(cuò)圖案E的分量中“1”的個(gè)數(shù)即為接收碼字R差錯(cuò)的個(gè)數(shù)。差錯(cuò)圖案出現(xiàn)t個(gè)差錯(cuò)的圖案數(shù)量為Cnt

。信道譯碼器第四十六頁，共五十一頁，2022年，8月28日2.伴隨式根據(jù)Ci

H

T=01×(n-k)及R=Ci+E，

RH

T

=

(Ci+E)H

T=Ci

H

T+E

H

T=E

H

T

令S=RH

T

或S=E

H

T;這里S=(s1,s2,…,sn-k)

這里稱S

為伴隨式。伴隨式S僅與接收字R或差錯(cuò)圖案E有關(guān)，與碼字Ci

無關(guān)。由于伴隨式S是n-k維矢量，故不同S的個(gè)數(shù)只有2n-k個(gè)；而接收字R或差錯(cuò)圖案E有2n個(gè)，因此，不同的接收字R或差錯(cuò)圖案E

有相同的伴隨式S.

第四十七頁，共五十一頁，2022年，8月28日例(5,2)線性分組碼

1°生成矩陣G2°

校驗(yàn)矩陣H3°編碼碼字:00000011011011111010dmin=34°差錯(cuò)圖案E出現(xiàn)0

個(gè)差錯(cuò)的1個(gè):00000

出現(xiàn)1

個(gè)差錯(cuò)的5個(gè):0000100010001000100010000出現(xiàn)2

個(gè)差錯(cuò)的10個(gè):0001100110011001100000101010101010001001

10010

10001第四十八頁，共五十一頁，2022年，8月28日5°伴隨式S=RHT=

EHT

00000→00000001→00100011→011

00010→010

00110→110

00100→10001100→00101000→10111000→010

10000→11100101→101

01010→11110100→01101001→100

10010→101

10001→110ESESES第四十九頁，共五十一頁，2022年，8月28日3.線性分組碼的譯碼原理生成矩陣G或校驗(yàn)矩陣H確定后，就可以解決編碼問題。碼字經(jīng)過信道傳輸后，接收端獲得的只有R，而Ci未知的，因此E也是未知的.如何根據(jù)H和R進(jìn)行譯碼，

1°如