第九章-隨機(jī).

1、第九章 差錯控制編碼 9.1 引言 9.2 糾錯編碼的基本原理 9.3 常用的簡單編碼 9.4 線性分組碼 9.5 循環(huán)碼 9.6 卷積碼9.1引 言 一、信源編碼與信道編碼 數(shù)字通信中，根據(jù)不同的目的，編碼分為信源編碼與信道編碼二大類。 信源編碼：提高數(shù)字信號的有效性，如，PCM編碼，編碼，圖象數(shù)據(jù)壓縮編碼等。 信道編碼：提高傳輸?shù)目煽啃?，又稱抗干擾編碼，糾錯編碼 。 從差錯控制角度看：信道分三類：（信道編碼技術(shù)） 隨機(jī)信道：由加性白噪聲引起的誤碼，錯 碼是隨機(jī)的，錯碼間統(tǒng)計(jì)獨(dú)立。 突發(fā)信道：錯碼成串，由脈沖噪聲干擾引 起。 混合信道：既存在隨機(jī)錯誤，又存在突發(fā)錯碼，那一種都不能忽略不計(jì)的信

2、道。二：差錯控制的工作方式 檢錯重發(fā) 前向糾錯，不要反向信道 反饋校驗(yàn)法，雙向信道 檢錯重發(fā)前向糾錯反饋校驗(yàn)法檢錯誤判決信號糾錯碼信息信號發(fā)發(fā)發(fā)收收收信息信號9.2 糾錯編碼的基本原理 一：分組碼，碼重，碼距 （樊書P282 表9-1） 將碼組分段：分成信息位段和監(jiān)督位段，稱為分組碼，記為（n, k） n編碼組的總位數(shù)，簡稱碼長（碼組的長度） k 每組二進(jìn)制信息碼元數(shù)目（信息位段） n-k=r 監(jiān)督碼元數(shù)目，（監(jiān)督位段）（見樊書P282，圖9-2） 在分組碼中，有“1”的數(shù)目稱為碼組的重量，簡稱碼重。例如，碼組（1 1 0 1 0），碼長n=5，碼重為3。 把兩個碼組對應(yīng)位不同的數(shù)目稱為這兩個

3、碼組的距離，簡稱碼距，又稱Hamming（漢明）的距離。例如，碼組（1 1 0 0 0）與（1 0 0 1 1）的距離為3。 而碼組集合中，全體碼組之間的距離的最小值稱為最小碼距（d0 ）。 檢測e個錯， 糾正t個錯, 糾正t個錯同時檢測e個錯 碼長n發(fā)生r個錯的概率 糾1，2個錯誤碼率也下降幾個數(shù)量級01de021dt01,detet !( )(1)(1)!()!rrn rrn rnneeeenp rC ppppr nr3357710 ,(1)7.*10 ,(2)2.*10eppp9.3常用的簡單編碼 糾錯碼的分類 ： (1) 奇偶校驗(yàn)碼“1”的數(shù)目應(yīng)為偶或奇數(shù)） (2) 二維奇偶校驗(yàn)碼 (

4、3) 恒比碼 (4) 正反碼(1) 奇偶校驗(yàn)碼 0021aaann0110011偶 校 驗(yàn)位信息位1 1 0 0 1 1(2) 二維奇偶校驗(yàn)碼01000100110011列監(jiān)督位， 行監(jiān)督位， /0/1/0/1對稱出現(xiàn)4個錯碼也檢不出來001111100001110011111001010111110011 (3) 恒比碼 例如，我國電傳機(jī)傳輸阿拉伯?dāng)?shù)字時，用5位代碼表示，其中恒有3個“1”，稱為 “5中取3” 恒比碼。 阿拉伯?dāng)?shù)字保護(hù)電碼阿拉伯?dāng)?shù)字保護(hù)電碼123450101111001101101101000111678901010111100011101001101101(4) 正反碼 正

5、反碼的信息位段長與監(jiān)督位段長相同，如正反碼組： 信息位段有奇數(shù)個1：1100111001 （監(jiān)督位與信息位重復(fù)） 信息位段有偶數(shù)個1：1000101110 （監(jiān)督位是信息位反碼）信息位 監(jiān)督位信息位 監(jiān)督位9.4 線性分組碼 一：基本概念一：基本概念 可用線性方程組（代數(shù)關(guān)系）表述碼的規(guī)律性的分組碼稱為線性分組碼 。 在代數(shù)碼中，常見的是線性碼，即編碼中的信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著，或者說可用線性代數(shù)方程表述編碼的規(guī)律性。 二：線性分組碼的一種二：線性分組碼的一種 漢明碼漢明碼 構(gòu)造原理 先回顧偶校驗(yàn)碼 在接收端實(shí)際上計(jì)算監(jiān)督關(guān)系式： 021aaasnn 無錯 0s1s 有錯 稱

6、校正子 s兩個監(jiān)督式就有兩個校正子，其可能值有4種組合：0 0，0 1，1 0，1 1，這4種組合代表不同信息。 若用1種組合表示無錯,其余3種組合就可以用來表示一位錯碼的3種不同位置。 同理，r個監(jiān)督式能指示一位錯碼的 個可能位置。12 r 一般來說，若碼長n，信息位數(shù)k，則監(jiān)督位 ,漢明碼n與r滿足：knr12 rn 現(xiàn)以（n，k）=（7，4），r=3為例的漢明碼來說明如何具體構(gòu)造這些監(jiān)督關(guān)系式。設(shè)碼字（n，k）= 0456aaaa信息位監(jiān)督位456012aaaaaa321sss,校正子321sss, 的值與錯碼位置的對應(yīng)關(guān)系 如下表24561aaaas13562aaaas03463aaa

7、as 只要（s1或s2，或s3）為“1”，就表示有錯321,sss321sss,0a4a1a5a2a6a3a錯碼位置錯碼位置001101010110100111011000無 錯321sss,全為零，表示無錯。 在發(fā)端編碼時，信息位 的值是隨機(jī)的，監(jiān)督位 應(yīng)根據(jù)信息位按監(jiān)督關(guān)系來確定，即監(jiān)督位應(yīng)使上面的 監(jiān)督式為零。 6543aaaa,012aaa,321sss, 即要求： 02456aaaa01356aaaa00346aaaa或?qū)懗杀O(jiān)督碼元在左邊的形式： 4562aaaa3561aaaa3460aaaa 信息位 一旦確定后，可直接按上式計(jì)算出監(jiān)督位。（見樊書P289 圖9-5）3456aaa

8、a, 接收端收到每個碼字（碼組）后，先計(jì)算出偶監(jiān)督關(guān)系式， 再按表9-4（樊書P288）判斷錯碼情況。 321sss, 如果 不全零，可判出在哪一位出錯。321sss,查樊書表9-4，判錯哪一位并糾正之265416530643aaaaaaaaaaaa654265316430000aaaaaaaaaaaa發(fā)送端，將信發(fā)送端，將信息位按此式加息位按此式加上監(jiān)督位后發(fā)上監(jiān)督位后發(fā)送送接收端，先計(jì)算校正為零否，接收端，先計(jì)算校正為零否，不為零則出錯碼，查表后，糾不為零則出錯碼，查表后，糾正改之正改之 漢明碼最小距 =3（見樊書表9-5），能夠糾正單個錯誤。 0d三：線性分組碼的一般原理 (1) 監(jiān)督陣

9、和生成矩陣 將上述漢明碼（7，4）的監(jiān)督關(guān)系式改寫成：（見樊書P289，9.4-8） 1654321011101000saaaaaaa 2654321011010100saaaaaaa 3654321010110010saaaaaaa 上式中 簡寫為+，表示模2相加。 寫成矩陣形式： 1001101010101100101110123456aaaaaaa000=（模2） 簡記 （H 監(jiān)督矩陣） 監(jiān)督矩陣H為 （ 行， 列）階矩陣，H陣的每行之間彼此線性無關(guān)。 也可將H矩陣分為兩部分：0H anrrn H = 36aa 012aaa 其中P為rk階矩陣， 為rr階單位矩陣。rIrPI100010

10、101010110010111若把監(jiān)督關(guān)系式改寫補(bǔ)充： 34603561456233445566aaaaaaaaaaaaaaaaaaaa 可改寫為矩陣形式： 656453423101000010000100001111011011011aaaaaaaaaaa65432106543aaaaaa aa a a aG1101000101010001100101110001GkIQ=PT G稱為生成矩陣，如果找到G，則糾錯編碼方法就確定了，可由信息組和G可產(chǎn)生全部碼字。 也稱典型生成矩陣，其中 QIGk 為kk方陣 ， kI1000010000100001 由典型生成矩陣得出的碼組A中，信息位不變，監(jiān)

11、督位附加其后，這種碼稱為系統(tǒng)碼。 110101011111Q(2) 校正子S（伴隨式） 設(shè)發(fā)送碼組設(shè)接收碼組 0121aaaaAnn,0121bbbbBnn, 則發(fā)送碼組與接收碼組之差定義為E（也稱錯誤圖樣）：（模2）ABE0121eeeeEnn,其中 iiiiiababe當(dāng)當(dāng) 1 0, 因此，若 ,表示該位接收碼元無錯；若 ，則表示有錯。 0ie1ieABE,也可改寫為 EAB 例如：發(fā)送A = 1 0 0 0 1 1 1 錯誤E = 0 0 0 0 1 0 0 接收B = 1 0 0 0 0 1 1THBS 令 稱S為校正子，也稱伴隨式。 TTTTTEHEHAHHEAHBS )(零矩陣 由

12、此可見，校正子S與錯誤圖樣E之間有確定的線性變換關(guān)系，若S和E之間一一對應(yīng)，則S將能代表錯碼的位置。 接收端譯碼器的任務(wù)就是從校正子S確定錯誤圖樣，然后，從接收到的碼字中減去錯誤圖樣E。 上述（7，4）漢明碼的校正子S與錯誤圖樣E的對應(yīng)關(guān)系見下表： 表中，校正子S的 種形式分別代表A碼無錯和 -1種有錯的圖樣。r2r21b2b3b序號錯誤碼位錯誤圖樣 E校正子 S 0 0 0 0 0 0 0 00 0 01 0 0 0 0 0 0 10 0 12 0 0 0 0 0 1 00 1 03 0 0 0 0 1 0 01 0 04 0 0 0 1 0 0 00 1 15 0 0 1 0 0 0 01

13、 0 16 0 1 0 0 0 0 01 1 07 1 0 0 0 0 0 01 1 10b4b5b6b e6 e5 e4 e3 e2 e1 e02s1s0s9.5 循環(huán)碼 一、特點(diǎn)： 編碼和解碼設(shè)備都不太復(fù)雜，且檢（糾）錯能力較強(qiáng)。具有線性和循環(huán)性，即循環(huán)碼中任一碼組循環(huán)一位（將最右端的碼元移至左端，或反之）以后，仍為該碼中的一個碼組。 將各碼元當(dāng)作是一個多項(xiàng)式的系數(shù)，樊書P293頁，表96中的任一碼組可表示為 這種多項(xiàng)式中，x僅是碼元位置的標(biāo)記。這種多項(xiàng)式有時稱為碼多項(xiàng)式。二、編碼原理121210( )nnnnT xaxaxa xa(1)、碼多項(xiàng)式的按模運(yùn)算 若一整數(shù)m可以表示為式中Q整數(shù)

14、。則在模n運(yùn)算下，有mpn模mpQpnnn在循環(huán)碼中，若T(x)是一個長為n的許用碼組，則 ixT x在按模1nx 運(yùn)算下，也是一個許用碼組，即若 1inxT xTxx模則 Tx也是一個許用碼組。 例如65235327( )1,11001013( )mod(1)0101110codeiiT xxxxxxleftshiftxT xxxxxx (2)、循環(huán)碼的生成矩陣G 在一個 循環(huán)碼中有 個不同碼組。若用 表示其中前（k1）位皆為0的碼組，則 都是碼組，而且這k個碼組是線性無關(guān)的。 因此他們可以用來構(gòu)成此循環(huán)碼的生成 矩陣G 。 Tab. 9-6 Page 293, k=3, g(x)-0010

15、111 x 43210 2k 421g xxxx 21,.,kg xxg xx g xxg x, n k g x 循環(huán)碼的生成矩陣G可以寫成 12( )( )( )( )kkxg xxg xG xxg xg x上式可作線性變換成 的形式。kGI Q 循環(huán)碼的生成多項(xiàng)式應(yīng)該是 的一個 次因式。例如， 可以分解為1nx nk71x 為了求（7，3）循環(huán)碼的生成多項(xiàng)式g(x)，要從上式中找一個（n-k)=4次的因子。這樣的因子有兩個，即32432111xxxxxx3242111xxxxxx 以上兩式都可作為生成多項(xiàng)式用。不過，選用的生成多項(xiàng)式不同，產(chǎn)生出的循環(huán)碼碼組也就不同。73231111xxxx

16、xx(3)、尋找生成多項(xiàng)式三、循環(huán)碼編、解碼方法（1）編碼步驟 (代數(shù)方法） 1、用 乘 。這一運(yùn)算實(shí)際上是把信息碼附加上（ ）個0。 2、用 除 ，得到商Q（x）和余式 。 3、編出的碼組 為 (2) T=m G (matrix-operation) n kx( )m xnk( )g x( )n kxm x( )r x( )T x ( )n kT xxm xr x（2）解碼步驟 1、用生成多項(xiàng)式 除接收碼組 得出余式 ； 2、按余式 用查表的方法或通過某種運(yùn)算得 到錯誤圖樣 就可以確定錯碼的位置； 3、從 中減去 ，變得到已糾正錯誤的原發(fā)送碼組 。 ( )g x( )( )( )R xT xE x( )r x( )r x( )E x( )R x( )E x( )T x9.6 卷積碼一.卷積碼的結(jié)構(gòu)圖D1D2km 1kc 2kckc由圖可知，（2，1，2）卷積碼的編碼規(guī)則為 12212kkkkkkkcmmcmmm輸出碼字為 12,kkkccc二. 卷積碼的生成多項(xiàng)式則相應(yīng)的系統(tǒng)沖擊響應(yīng)為 1828101(5)111(7)gg1122120kkkkkkhh用生成多項(xiàng)式表示212211gxgxx 三.編碼率與約束長度k輸入，n輸出,每時刻輸出與過去(L-1)k個輸入亦關(guān)編碼率=k/n=1/2,約束長度=L=7L=