信息論第六章 信道編碼(3)

1、第六章信道編碼有信心不一定會成功；沒有信心一定不會成功。英雄本色2第六章信道編碼6.2.16.2.26.2.36.2.46.2.56.2.66.2.76.2.86.2.96.2.10一般概念一致監(jiān)督方程和一致監(jiān)督矩陣線性分組碼的生成矩陣線性分組碼的編碼線性分組碼的最小距離、檢錯和糾錯能力線性分組碼的譯碼線性分組碼的性能漢明碼線性分組碼的碼限由已知碼構(gòu)造新碼的方法6.2 線性分組碼 最佳譯碼準(zhǔn)則（最大后驗概率譯碼最佳譯碼準(zhǔn)則（最大后驗概率譯碼MAP）l通信是一個統(tǒng)計過程，糾、檢錯能力最終要反映到差通信是一個統(tǒng)計過程，糾、檢錯能力最終要反映到差錯概率上。錯概率上。l對于對于FEC方式，采用糾錯碼后

2、的碼字差錯概率為方式，采用糾錯碼后的碼字差錯概率為pwe，lp(C C)：發(fā)送碼字：發(fā)送碼字C C 的先驗概率的先驗概率lp(C C/R R)：后驗概率：后驗概率l若碼字?jǐn)?shù)為若碼字?jǐn)?shù)為 2k，對充分隨機(jī)的消息源有，對充分隨機(jī)的消息源有p(C C)=1/ 2k，所，所以最小化以最小化pwe等價為最小化等價為最小化p(C CC CR R )，又等價為最大，又等價為最大化化p(C C=C CR R)；)()(RCCCpppwe6.2.6 線性分組碼的譯碼(2) 糾錯譯碼糾錯譯碼l由貝葉斯公式：由貝葉斯公式：l對于對于 BSC 信道：最大化后驗概率信道：最大化后驗概率p(C C=C CR R) 等價于

3、最大等價于最大化似然函數(shù)化似然函數(shù)p(R RC C) l最大化最大化p(R RC C) 又等價于最小化又等價于最小化 d(R R,C C)，所以使差錯概率，所以使差錯概率最小的譯碼是使接收向量最小的譯碼是使接收向量 R R 與輸出碼字與輸出碼字 C C 距離最小的譯距離最小的譯碼。碼。) ,(),(min: CRCRCCddiip p( (R R) )p p( (R R/ /C C) )p p( (C C) )p p( (C C/ /R R) )6.2.6 線性分組碼的譯碼 標(biāo)準(zhǔn)陣列譯碼標(biāo)準(zhǔn)陣列譯碼l碼矢參數(shù)碼矢參數(shù)l發(fā)送碼矢：取自于發(fā)送碼矢：取自于 2k 個碼字集合個碼字集合C C；l接收矢

4、量：可以是接收矢量：可以是 2n 個個 n 重中任一個矢量。重中任一個矢量。l譯碼方法譯碼方法l把把 2n 個個 n 重矢量劃分為重矢量劃分為 2k 個互不相交的子集個互不相交的子集 ，使得在每個子集中僅含一個碼矢；使得在每個子集中僅含一個碼矢；l根據(jù)碼矢和子集間一一對應(yīng)關(guān)系，若接收矢量根據(jù)碼矢和子集間一一對應(yīng)關(guān)系，若接收矢量 R Rl 落在子集落在子集 D Dl中，就把中，就把 R Rl 譯為子集譯為子集 D Dl 含有的碼字含有的碼字 C Cl；l當(dāng)接收矢量當(dāng)接收矢量 R R 與實(shí)際發(fā)送碼矢在同一子集中時，譯碼就是與實(shí)際發(fā)送碼矢在同一子集中時，譯碼就是正確的。正確的。l標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列：是

5、對給定的：是對給定的 (n,k) 線性碼，將線性碼，將 2n 個個 n 重劃分為重劃分為 2k 個個子集的一種方法。子集的一種方法。k221,DDD6.2.6 線性分組碼的譯碼l標(biāo)準(zhǔn)陣列構(gòu)造方法標(biāo)準(zhǔn)陣列構(gòu)造方法l先將先將 2k 個碼矢排成一行，作為個碼矢排成一行，作為標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列的第一行，并將的第一行，并將全全0碼矢碼矢C C1=(000)放在最左面的位置上；放在最左面的位置上；l然后在剩下的然后在剩下的 (2n2k) 個個 n 重中選取一個重量最輕的重中選取一個重量最輕的 n 重重 E E2 放在全放在全0碼矢碼矢 C C1 下面，再將下面，再將 E E2 分別和碼矢分別和碼矢 相加，放

6、在對應(yīng)碼矢下面，構(gòu)成陣列第二行；相加，放在對應(yīng)碼矢下面，構(gòu)成陣列第二行；l在第二次剩下的在第二次剩下的 n 重中，選取重量最輕的重中，選取重量最輕的 n 重重 E E3，放在，放在 E E2 下面，并將下面，并將 E E3 分別加到第一行各碼矢上，得到第三行；分別加到第一行各碼矢上，得到第三行；l，繼續(xù)這樣做下去，直到全部，繼續(xù)這樣做下去，直到全部 n 重用完為止。得到下重用完為止。得到下頁表格所示的頁表格所示的 (n,k) 線性碼的標(biāo)準(zhǔn)陣列。線性碼的標(biāo)準(zhǔn)陣列。k232,CCC6.2.6 線性分組碼的譯碼k2C22ECk32ECkknk22ECkni2ECkn22ECkn2E6.2.6 線性分

7、組碼的譯碼標(biāo)準(zhǔn)陣列的特性：標(biāo)準(zhǔn)陣列的特性：l定理定理：在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且：在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且 2n 個個 n 重中任一個重中任一個 n 重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。 證明證明：L因為陣列中任一行都是由所選出某一因為陣列中任一行都是由所選出某一 n 重矢量分別與重矢量分別與 2k 個碼矢相加構(gòu)成的，而個碼矢相加構(gòu)成的，而 2k 個碼矢互不相同，它們與個碼矢互不相同，它們與所選矢量的和也不可能相同，所以在同一行中沒有相所選矢量的和也不可能相同，所以在同一行中沒有相同的矢量；同的矢量；L在構(gòu)造標(biāo)準(zhǔn)陣列時，是用完全部在構(gòu)造

8、標(biāo)準(zhǔn)陣列時，是用完全部 n 重為止，因而每個重為止，因而每個 n 重必出現(xiàn)一次；重必出現(xiàn)一次；L接下頁接下頁6.2.6 線性分組碼的譯碼L每個每個n重只能出現(xiàn)一次。重只能出現(xiàn)一次。 假定某一假定某一 n 重重 X X 出現(xiàn)在第出現(xiàn)在第 l 行第行第 i 列，那么列，那么 X XE El+C Ci， 又假設(shè)又假設(shè) X X 出現(xiàn)在第出現(xiàn)在第 m 行第行第 j 列，那么列，那么 X XE Em+C Cj，ll)的第的第 一個元素，一個元素， 而按陣列構(gòu)造規(guī)則，后面行的第一而按陣列構(gòu)造規(guī)則，后面行的第一個元素是前面行中未曾出現(xiàn)過的元素，這就和陣列構(gòu)造規(guī)個元素是前面行中未曾出現(xiàn)過的元素，這就和陣列構(gòu)造規(guī)

9、則相矛盾。則相矛盾。6.2.6 線性分組碼的譯碼l線性碼糾錯極限定理線性碼糾錯極限定理：二元：二元 (n,k) 線性碼能糾線性碼能糾 2nk 個錯誤個錯誤圖樣。這圖樣。這 2nk 個可糾的錯誤圖樣，包括個可糾的錯誤圖樣，包括0 0矢量在內(nèi)，即把矢量在內(nèi)，即把無錯的情況也看成一個可糾的錯誤圖樣。無錯的情況也看成一個可糾的錯誤圖樣。 證明證明：L(n,k) 線性碼的標(biāo)準(zhǔn)陣列有線性碼的標(biāo)準(zhǔn)陣列有 2k 列（和碼矢量相等），列（和碼矢量相等），2n/2k= 2nk行，且任何兩列和兩行都沒有相同的元素。行，且任何兩列和兩行都沒有相同的元素。L陪集陪集：標(biāo)準(zhǔn)陣列的每一行叫做碼的一個陪集。：標(biāo)準(zhǔn)陣列的每一行

10、叫做碼的一個陪集。L陪集首陪集首：每個陪集的第一個元素叫做陪集首。：每個陪集的第一個元素叫做陪集首。L每一列包含每一列包含 2nk 個元素，最上面的是一個碼矢，其它元素個元素，最上面的是一個碼矢，其它元素是陪集首和該碼矢之和，例如第是陪集首和該碼矢之和，例如第 j 列為列為L接下頁接下頁),(232jjjjjknCECECECD6.2.6 線性分組碼的譯碼L若發(fā)送碼矢為若發(fā)送碼矢為 C Cj，信道干擾的錯誤圖樣是陪集首，則接收，信道干擾的錯誤圖樣是陪集首，則接收矢量矢量 R R 必在必在 D Dj 中；中；L若錯誤圖樣不是陪集首，則接收矢量若錯誤圖樣不是陪集首，則接收矢量 R R不在不在 D

11、Dj 中，則譯中，則譯成其它碼字，造成錯誤譯碼；成其它碼字，造成錯誤譯碼；L當(dāng)且僅當(dāng)錯誤圖樣為陪集首時，譯碼才是正確的。當(dāng)且僅當(dāng)錯誤圖樣為陪集首時，譯碼才是正確的。L可糾正的錯誤圖樣可糾正的錯誤圖樣：這：這 2nk 個陪集首稱為可糾正的錯誤圖個陪集首稱為可糾正的錯誤圖樣。樣。6.2.6 線性分組碼的譯碼l線性碼糾錯能力與監(jiān)督元數(shù)目的關(guān)系線性碼糾錯能力與監(jiān)督元數(shù)目的關(guān)系：一個可糾：一個可糾 t 個錯誤個錯誤的線性碼必須滿足的線性碼必須滿足 上式中等式成立時的線性碼稱為上式中等式成立時的線性碼稱為完備碼完備碼。即。即證明證明 (接下頁接下頁)L對于糾一個錯誤的對于糾一個錯誤的 (n,k) 線性碼，

12、必須能糾正線性碼，必須能糾正 個個錯誤圖樣，因此錯誤圖樣，因此11nnnkn1112tiknintnnn02112tiknin026.2.6 線性分組碼的譯碼L對糾兩個錯誤的對糾兩個錯誤的 (n,k) 線性碼，必須能糾線性碼，必須能糾 個個錯誤圖樣，所以錯誤圖樣，所以L依此類推，一個糾依此類推，一個糾 t 個錯誤的個錯誤的 (n,k) 線性碼必須滿足線性碼必須滿足L對于完備碼，對于完備碼，由碼的糾錯能力所確定的伴隨式數(shù)恰好等于由碼的糾錯能力所確定的伴隨式數(shù)恰好等于可糾的錯誤圖樣數(shù)，所以完備碼的可糾的錯誤圖樣數(shù)，所以完備碼的 (nk) 個監(jiān)督碼元得到個監(jiān)督碼元得到了充分的利用了充分的利用。211

13、nn2112nnkntiknintnnn021126.2.6 線性分組碼的譯碼l完備譯碼完備譯碼：(n,k) 線性碼的所有線性碼的所有 2nk 個伴隨式，在譯碼過個伴隨式，在譯碼過程中若都用來糾正所有小于等于程中若都用來糾正所有小于等于 個隨機(jī)錯個隨機(jī)錯誤，以及部分大于誤，以及部分大于 t 的錯誤圖樣，則這種譯碼方法稱為的錯誤圖樣，則這種譯碼方法稱為完完備譯碼備譯碼。l限定距離譯碼限定距離譯碼：任一：任一 (n,k) 線性碼，能糾正線性碼，能糾正 個隨機(jī)錯誤，如果在譯碼時僅糾正個隨機(jī)錯誤，如果在譯碼時僅糾正 t t 個錯誤，而當(dāng)錯誤個錯誤，而當(dāng)錯誤個數(shù)大于個數(shù)大于t時，譯碼器不進(jìn)行糾錯而僅指出

14、發(fā)生了錯誤，時，譯碼器不進(jìn)行糾錯而僅指出發(fā)生了錯誤，稱這種方法為稱這種方法為限定距離譯碼限定距離譯碼。2/ ) 1(dt2/ ) 1( dt6.2.6 線性分組碼的譯碼從多維矢量空間的角度看完備碼從多維矢量空間的角度看完備碼：l假定圍繞每一個碼字假定圍繞每一個碼字 C Ci 放置一個半徑為放置一個半徑為 t 的球，每個球內(nèi)包含的球，每個球內(nèi)包含了與該碼字漢明距離小于等于了與該碼字漢明距離小于等于 t 的所有接收碼字的所有接收碼字 R R 的集合；這樣，的集合；這樣，在半徑為在半徑為 t=(dmin1)/2 的球內(nèi)的接收碼字?jǐn)?shù)是：的球內(nèi)的接收碼字?jǐn)?shù)是：l因為有因為有 2k 個可能發(fā)送的碼字，也就

15、有個可能發(fā)送的碼字，也就有2k 個不相重疊的半徑為個不相重疊的半徑為t的的球。包含在球。包含在2k個球中的碼字總數(shù)不會超過個球中的碼字總數(shù)不會超過2n個可能的接收碼字。個可能的接收碼字。于是一個糾于是一個糾 t 個差錯的碼必然滿足不等式個差錯的碼必然滿足不等式l如果上式中等號成立，表示所有的接收碼字都落在如果上式中等號成立，表示所有的接收碼字都落在 2k 個球內(nèi)，而個球內(nèi)，而球外沒有一個碼，球外沒有一個碼，這就是完備碼這就是完備碼。tikntinkinin00222即tiin06.2.6 線性分組碼的譯碼l完備碼特性完備碼特性：圍繞：圍繞 2k 個個碼字，漢明距離為碼字，漢明距離為t=(dmi

16、n1)/2的所有球的所有球都是不相交的，每一個都是不相交的，每一個接收碼字都落在這些球接收碼字都落在這些球中之一，因此接收碼與中之一，因此接收碼與發(fā)送碼的距離至多為發(fā)送碼的距離至多為 t，這時所有重量這時所有重量t的錯誤圖的錯誤圖樣都能用最佳（最小距樣都能用最佳（最小距離）譯碼器得到糾正，離）譯碼器得到糾正，而所有重量而所有重量t+1的錯誤圖的錯誤圖樣都不能糾正。樣都不能糾正。tdmin以碼字為中心、半徑t=INT(dmin1)/2的差錯控制球體示意圖dminttt6.2.6 線性分組碼的譯碼l例：對糾一個錯誤的例：對糾一個錯誤的 (7,4) 漢明碼，漢明碼，l可見，可見，(7,4)漢明碼是一

17、個完備碼。漢明碼是一個完備碼。所有漢明碼都是完所有漢明碼都是完備碼備碼（滿足（滿足2nk = 2m=n+1）。）。112,811, 82nnknkn所以6.2.6 線性分組碼的譯碼標(biāo)準(zhǔn)陣列譯碼標(biāo)準(zhǔn)陣列譯碼=最小距離譯碼法最小距離譯碼法=最佳譯碼法最佳譯碼法l陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，應(yīng)選取出現(xiàn)概率最大的錯誤圖樣作陪集首；應(yīng)選取出現(xiàn)概率最大的錯誤圖樣作陪集首；l重量較輕的錯誤圖樣出現(xiàn)概率較大，所以在構(gòu)造標(biāo)準(zhǔn)陣列重量較輕的錯誤圖樣出現(xiàn)概率較大，所以在構(gòu)造標(biāo)準(zhǔn)陣列時是選取重量最輕的時是選取重量最輕的 n 重作陪集首；重作陪集首

18、；l這樣，當(dāng)錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收這樣，當(dāng)錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收矢量與原發(fā)送碼矢間的距離（等于陪集首）最??；矢量與原發(fā)送碼矢間的距離（等于陪集首）最??；l因此，選擇重量最輕的元素作陪集首，按標(biāo)準(zhǔn)陣列譯碼就因此，選擇重量最輕的元素作陪集首，按標(biāo)準(zhǔn)陣列譯碼就是按最小距離譯碼；是按最小距離譯碼；l所以標(biāo)準(zhǔn)陣列譯碼法也是最佳譯碼法。所以標(biāo)準(zhǔn)陣列譯碼法也是最佳譯碼法。6.2.6 線性分組碼的譯碼l在標(biāo)準(zhǔn)陣列中，一個陪集的所有在標(biāo)準(zhǔn)陣列中，一個陪集的所有 2k 個個 n 重有相同的伴隨重有相同的伴隨式，不同的陪集伴隨式互不相同。式，不同的陪集伴隨式互不相同。 證明證

19、明：l設(shè)設(shè) H H 為給定為給定 (n,k) 線性碼的監(jiān)督矩陣，在陪集首為線性碼的監(jiān)督矩陣，在陪集首為 E El 的陪集中的任意矢量的陪集中的任意矢量 R R 為為 R R=E El+C Ci, i=1,2,2kl其伴隨式為其伴隨式為 S S=RHRHT=(E El+C Ci)HHT=E ElHHT+C CiHHT =E ElHHTl上式表明：上式表明：陪集中任意矢量的伴隨式等于陪集首的伴陪集中任意矢量的伴隨式等于陪集首的伴隨式隨式。即同一陪集中所有伴隨式相同。即同一陪集中所有伴隨式相同。l不同陪集中，由于陪集首不同，所以伴隨式不同。不同陪集中，由于陪集首不同，所以伴隨式不同。6.2.6 線性

20、分組碼的譯碼結(jié)論：結(jié)論：l任意任意 n 重的伴隨式?jīng)Q定于它在標(biāo)準(zhǔn)陣列中所在陪集的陪重的伴隨式?jīng)Q定于它在標(biāo)準(zhǔn)陣列中所在陪集的陪集首。集首。l標(biāo)準(zhǔn)陣列的陪集首和伴隨式是一一對應(yīng)的，因而碼的可標(biāo)準(zhǔn)陣列的陪集首和伴隨式是一一對應(yīng)的，因而碼的可糾錯誤圖樣和伴隨式是一一對應(yīng)的，應(yīng)用此對應(yīng)關(guān)系可糾錯誤圖樣和伴隨式是一一對應(yīng)的，應(yīng)用此對應(yīng)關(guān)系可以構(gòu)成比標(biāo)準(zhǔn)陣列簡單得多的譯碼表，從而得到以構(gòu)成比標(biāo)準(zhǔn)陣列簡單得多的譯碼表，從而得到 (n,k) 線性碼的一般譯碼線性碼的一般譯碼步驟：步驟：l計算接收矢量計算接收矢量 R R 的伴隨式的伴隨式 S ST=HRHRT ；l根據(jù)伴隨式和錯誤圖樣一一對應(yīng)的關(guān)系，利用伴隨式譯

21、根據(jù)伴隨式和錯誤圖樣一一對應(yīng)的關(guān)系，利用伴隨式譯碼表，由伴隨式譯出碼表，由伴隨式譯出 R R 的錯誤圖樣的錯誤圖樣 E E；l將接收碼字減錯誤圖樣，得發(fā)送碼矢的估值將接收碼字減錯誤圖樣，得發(fā)送碼矢的估值 C C=R RE E 。 上述譯碼法稱為伴隨式譯碼法或查表譯碼法。上述譯碼法稱為伴隨式譯碼法或查表譯碼法。6.2.6 線性分組碼的譯碼l線性分組碼一般譯碼器結(jié)構(gòu)：線性分組碼一般譯碼器結(jié)構(gòu)： 這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯誤概率，原則上可用于任何誤概率，原則上可用于任何 (n,k) 線性碼。線性碼。伴隨式計算電路SE組合邏輯電路糾錯(

22、RE)電路輸入輸出 線性分組碼一般譯碼器6.2.6 線性分組碼的譯碼第六章信道編碼在通信中檢糾錯碼的實(shí)際性能是在統(tǒng)計上體現(xiàn)出來的。以下分析均以BSC信道為模型。(1)不可檢錯誤概率(2)譯碼錯誤概率(3)譯碼失敗概率(4)比特誤碼率6.2.7 線性分組碼的性能6.2線性分組碼pud Ai pi (1 p )n i第六章信道編碼舉例： (7,3) 碼的重量分布是 A0=1,A1=A2=A3=0,A4=7，其不可檢錯誤概率為pud7p4(1p)3，若p=0.01，則 pud6.810-8。利用 (n,k) 碼重量分布與其對偶碼的重量分布關(guān)系求 pud設(shè)A0,A1,A2, ,An 是 (n,k) 碼

23、的重量分布；B0,B1,B2, ,Bn 是它的對偶碼的重量分布；6.2線性分組碼(1)不可檢錯誤概率 pud由 (n,k) 線性碼的重量分布求 pud令A(yù)i為碼的重量分布，表示重量為i的碼字個數(shù)，i=0,1,2,n；由于僅 當(dāng) 錯 誤 圖 樣 與 碼 矢 集 合 中 的 非0碼 矢 相 同 時 ， 才 不 能 檢出錯誤，所以（p是BSC的誤碼率，且碼字等概發(fā)送）n(6.2.23)i 16.2.7 線性分組碼的性能n ipud Ai p i (1 p )第六章信道編碼對偶碼的重量枚舉式：下面的多項式稱為 (n,k) 碼和它的對偶MacWilliams恒等式：若已知線性碼的對偶碼的重量分布，就可確

24、定該碼本身的重量分布。由式(6.2.23)得(6.2.24)碼的重量枚舉式。6.2.7 線性分組碼的性能6.2線性分組碼(6.2.25)(6.2.26)(6.2.23)ni 10112201122( )( )nnnnA xAA xA xA xB xBB xB xB x()1( )2(1)()1nknxA xxBx1(1)()1nniudiipPpAp令 x ，代入式(6.2.24)，并考慮到A0 1，得到恒等式B(1 2 p) Bi (1 2p)i第六章信道編碼將這個恒等式代入式 (6.2.26) 得將恒等式和 (6.2.25) 代入上式得.(6.2.28)6.2.7 線性分組碼的性能6.2線

25、性分組碼(6.2.27)p1 pni 0(6.2.29)其中(6.2.24)()2(12 )(1)n knudPBpp(1) ()11nudpPpAp1()1()11niiippAApp01 12201 122( )( )nnnnA xAAxA xA xB xBB xB xB x第六章信道編碼當(dāng)k (nk) 時，用式(6.2.29)計算 pud 則更容易。舉例：已知 (7,4) 碼的監(jiān)督矩陣 H(7,4)，它等于其對偶碼的生成矩陣 G(7,3)，即G( 7 ,3) H( 7 , 4 ) 由此生成矩陣的行的線性組合，可得到(7,3)碼的8個碼字0000000 0111010 1001110 10

26、100116.2.7 線性分組碼的性能6.2線性分組碼1 1 1 0 1 0 00 1 1 1 0 1 01 1 0 1 0 0 1第六章信道編碼(2) 譯碼錯誤概率pwe正確譯碼概率pwc：糾正小于等于t個差錯的概率譯碼錯誤概率 pwe譯碼錯誤發(fā)生在差錯數(shù)目大于 t，接收向量 R 與另一碼字 C的距離小于等于 t 的情況；Di 是重量 i 并譯為錯誤碼字的可能的接收向量 R 的數(shù)目，即6.2線性分組碼6.2.7 線性分組碼的性能(6.2.30)譯碼錯誤概率pwe為0(1)tiniwcinPppi|( ), ( , ),|iwi d r ct ccDrr10(1)(1)ntiniiniweii

27、tinPppppi D第六章信道編碼(3)譯碼失敗概率pwf由于仍存在不滿足式 (6.2.30) 的接收碼矢 R，對于限定距離譯碼器來說就處于譯碼失敗狀態(tài)，即pwf=1 pwc pwe圖6.2.30中RA正確譯碼概率RB譯碼錯誤概率RC譯碼失敗概率6.2線性分組碼6.2.7 線性分組碼的性能tA圖6.2.30 正確譯碼、錯誤譯碼與譯碼失敗tBC信道發(fā)送碼字pbm pbd第六章信道編碼(4) 比特誤碼率pbc：信道的比特差錯概率，對于BSC信道，pbc等于信道轉(zhuǎn)移概率p。pbd：譯碼錯誤導(dǎo)致的碼字之間的比特差錯率。pbm：消息源與消息接收終端之間的比特差錯概率。一般認(rèn)為消息和碼字之間的映射不改變

28、碼字差錯導(dǎo)致在整個碼長內(nèi)比特差錯的均勻分布特性，在統(tǒng)計意義上有6.2線性分組碼6.2.7 線性分組碼的性能.2.31pbcpbdpbm第六章信道編碼Pbc 與 pwe的關(guān)系碼字錯必然有至少 2t+1位碼字比特錯；6.2線性分組碼pbe 譯碼錯誤的誤碼率：設(shè)碼字是等概率發(fā)送，則 是發(fā)送全0碼字并錯接收為 重量為j的碼字的概率；6.2.7 線性分組碼的性能每個碼字平均有 (2t 1) k/n 位消息比特錯，所以pbc與pwe有如下pweknkpbe (2t 1)()1njbewejdPjpn()jw ep第六章信道編碼pbd譯碼后總的誤碼率：pbd = pbe+pbf6.2線性分組碼6.2.7 線

29、性分組碼的性能pbf 譯碼失敗造成的誤碼率11(1)tinibfiitnPippin D第六章信道編碼漢明碼是漢明于1950年提出的糾一個錯誤的線性碼，也是第一個糾錯碼。由于它編碼簡單，因而是在通信系統(tǒng)和數(shù)據(jù)存儲系統(tǒng)中得到廣泛應(yīng)用的一類線性碼。漢明碼的結(jié)構(gòu)參數(shù)：糾一個錯誤的線性碼，其最小距離 dmin=3 ；監(jiān)督矩陣任意兩列線性無關(guān)/ H 的任兩列互不相同；沒有全0的列。監(jiān)督元個數(shù) nk=r；H 陣中每列有 r 個元素，至多可構(gòu)成 2r1種互不相同的非0列。對于任意正整數(shù) m3，漢明碼的結(jié)構(gòu)參數(shù)為碼長：信息位數(shù)：監(jiān)督位數(shù)：n=2m1k=2mm1nk=m碼的最小距離：dmin=3(t=1)6.2

30、線性分組碼6.2.8 漢明碼第六章信道編碼漢明碼監(jiān)督矩陣構(gòu)成的兩種方式構(gòu)成 H 陣的標(biāo)準(zhǔn)形式，H=Q Im，其中 Im 為 m 階單位子陣，子陣 Q 是構(gòu)造 Im 后剩下的列任意排列。用這種形式的 H陣編出的漢明碼是系統(tǒng)碼。按m重（重量為m ）表示的二進(jìn)制順序排列。按這種形式 H 陣編出的碼是非系統(tǒng)碼。當(dāng)發(fā)生可糾的單個錯誤時，伴隨式為 H陣中對應(yīng)的列，所以伴隨式的二進(jìn)制數(shù)值就是錯誤位置號，有時這種碼譯碼比較方便。由于漢明碼可糾的錯誤圖樣數(shù)為6.2線性分組碼因此漢明碼是完備碼。即滿足式6.2.8 漢明碼121mnn02tnkini第六章信道編碼(1) 研究碼限的意義研究碼的糾錯能力，也就是分析碼

31、的 n,k,d 之間的關(guān)系，不僅能從理論上指出哪些碼可以構(gòu)造出，哪些碼不能構(gòu)造出，而且也為工程實(shí)驗提供了對各種碼性能估計的理論依據(jù)。研究碼的糾錯能力始終是編碼理論中一個重要的課題。在糾錯編碼實(shí)現(xiàn)上總希望在盡可能小的 n 和 r 條件下獲得盡可能大的 k,d 或 t。滿足碼限的碼稱為最佳碼。6.2線性分組碼6.2.9 線性分組碼的碼限第六章信道編碼(2) 三個碼限普羅特金(Plotkin)限(P限)對任意二元 (n,k,d) 碼滿足6.2線性分組碼6.2.9 線性分組碼的碼限當(dāng)n充分大時滿足1.221kknd142dkRnn 第六章信道編碼漢明限(H限)對任意二元 (n,k,2t+1) 碼滿足6

32、.2線性分組碼6.2.9 線性分組碼的碼限H 2 ( x) x log 2 x (1 x) log 2 (1 x)其中滿足上式中等式成立的碼稱為完備碼。當(dāng)n充分大時漢明限可表示為02tn kini 12dRHn 第六章信道編碼瓦爾沙莫夫吉爾伯特(Varshamov-Gilbert)(V-G限)存在某個二元(n,k,d)碼滿足6.2線性分組碼6.2.9 線性分組碼的碼限當(dāng)n充分大時2012dn kini12.2dRHn 第六章信道編碼在 n 充分大時各個碼限的關(guān)系曲線如圖6.2.33所示。圖中以 V-G 限為下限，H 限和 P 限為上限所圍的區(qū)域(藍(lán)色區(qū)域)是好碼（滿足所有上述碼限的 (n,k,

33、d)碼）。6.2線性分組碼6.2.9 線性分組碼的碼限第六章信道編碼(1) 擴(kuò)展/Extending和打孔/Puncturing(2) 增廣/Augmenting和刪信/Expunging/Expurgating(3) 延長/Lengthening和縮短/Shortening(4) 乘積/Product(5) 級聯(lián)/Concatenating(6) 交織/Interleaving6.2.10 由已知碼構(gòu)造新碼的方法6.2線性分組碼第六章信道編碼(1) 擴(kuò)展/Extending和打孔/Puncturing擴(kuò)展：保持碼字?jǐn)?shù) k 不變，增加冗余位數(shù)以增加碼長。打孔：保持 k 不變，減小冗余位。可以認(rèn)

34、為是擴(kuò)展的逆過程。(2) 增廣/Augmenting和刪信/Expunging/Expurgating增廣：保持 n 不變，增加碼字?jǐn)?shù)目 k。刪信：保持 n 不變減小 k。(3) 延長/Lengthening和縮短/Shortening延長：同時增加 k 和 n?？s短：同時減小 k 和 n。6.2線性分組碼6.2.10 由已知碼構(gòu)造新碼的方法第六章信道編碼舉例： (7,4,3) 漢明碼的各種修正關(guān)系如圖6.2.31所示。6.2.10 由已知碼構(gòu)造新碼的方法6.2線性分組碼延長縮短第六章信道編碼(4) 乘積/Product消息作為陣列，分別進(jìn)行行列編碼。(5) 級聯(lián)/Concatenating對

35、消息編碼后的碼字再進(jìn)行一次編碼。級聯(lián)編碼的第一次所用碼稱外碼；第二次所用碼稱內(nèi)碼。級聯(lián)編碼常用于既有隨機(jī)差錯又有突發(fā)差錯的信道編碼。(6) 交織/Interleaving交織編碼分為分組交織和卷積交織兩種。如果交織編碼所用的 (n,k) 碼可以糾正 t 個隨機(jī)差錯，那么交織深度為 D 的交織編碼可以糾正 D t 長的突發(fā)錯誤。6.2線性分組碼6.2.10 由已知碼構(gòu)造新碼的方法第六章信道編碼舉例：視盤存儲的糾錯編碼采用對(31,21)糾雙錯的BCH碼進(jìn)行256深度的交織，可以有效糾正因為介質(zhì)損壞、磁（光）頭污染或者定時抖動等引起的連續(xù)差錯。6.2.10 由已知碼構(gòu)造新碼的方法6.2線性分組碼2

36、：已知(7,4)漢明碼的生成矩陣為(1) 求該碼的全部碼字；(3) 若接收碼字為1101101，計算伴隨式。第六章信道編碼1：一個 (6,2) 線性分組碼的一致校驗矩陣如下，求(1) 求hi,i=1,2,3,4使該碼的最小碼距dmin3；(2) 求該碼的系統(tǒng)碼生成矩陣Gs及其所有4個碼字。(2) 求該碼的監(jiān)督矩陣；作 業(yè)1234100010001 100101011 10hhHhh1000111010010100100110001110H第六章信道編碼作 業(yè)3：已知 (8,4) 系統(tǒng)線性碼的監(jiān)督方程為C0 m1 m2 m3C1 m0 m1 m2C2 m0 m1 m3C3 m0 m2 m3式中m=(