差錯控制編碼第二次課

差錯控制編碼第二次課第一頁，共五十一頁，2022年，8月28日回顧奇偶監(jiān)督碼在接收端解碼時，實際上就是在計算若S＝0，認為無錯若S＝1，認為有錯S只有兩種取值，只能代表有、無錯兩種信息，不能指出錯碼位置。監(jiān)督關系式校正子第二頁，共五十一頁，2022年，8月28日在（n,k）碼中，為能糾正一位錯誤要求在（n,k）碼中，k=4。為能糾正一位錯碼，則r至少應為多少？第三頁，共五十一頁，2022年，8月28日舉例說明如何構(gòu)造監(jiān)督關系式：上例中，若取r=3，則n=k+r=7。(7,4)線性分組碼（a6a5a4a3a2a1a0)校正子與錯碼位置的對應關系如表規(guī)定(也可以另外規(guī)定)。第四頁，共五十一頁，2022年，8月28日S1S2S3錯碼位置S1S2S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無錯第五頁，共五十一頁，2022年，8月28日由表可見，當一錯碼位置在a2,a4，a5或a6時校正子S1為1；否則S1為0即構(gòu)成如下關系第六頁，共五十一頁，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矩陣的各個行是線性無關的行數(shù)=監(jiān)督位數(shù)，列數(shù)=碼字長度典型陣r行n列第十一頁，共五十一頁，2022年，8月28日第十二頁，共五十一頁，2022年，8月28日轉(zhuǎn)置得K行r列第十三頁，共五十一頁，2022年，8月28日Q=PT，在Q矩陣的左邊在加上一個k×k的單位矩陣，就形成了一個新矩陣G：

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

求（1）信息碼組為101對應的編碼碼組（2）所有許用碼組、各碼組的碼重、最小碼距和該碼的差錯控制能力。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

碼字Ci

接收字R

Ci的估值干擾

1.差錯圖案

線性分組碼C

的任一碼字Ci=(ci1,ci

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

R

=(r

1,r2,…,rn)；令

E=R-Ci=

(r

1-

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

這里稱

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

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

的碼字。對于二元(n,k)碼，差錯圖案E的分量中“1”的個數(shù)即為接收碼字R差錯的個數(shù)。差錯圖案出現(xiàn)t個差錯的圖案數(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或差錯圖案E有關，與碼字Ci

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

有相同的伴隨式S.

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

1°生成矩陣G2°

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

個差錯的1個:00000

出現(xiàn)1

個差錯的5個:0000100010001000100010000出現(xiàn)2

個差錯的10個: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或校驗矩陣H確定后，就可以解決編碼問題。碼字經(jīng)過信道傳輸后，接收端獲得的只有R，而Ci未知的，因此E也是未知的.如何根據(jù)H和R進行譯碼，

1°如