informationandcoding2010lecture14

1、第六章 信道編碼2022/7/41第六章 信道編碼2022/7/426.2.1 一般概念一般概念6.2.2 一致監(jiān)督方程和一致監(jiān)督矩陣一致監(jiān)督方程和一致監(jiān)督矩陣6.2.3 線性分組碼的生成矩陣線性分組碼的生成矩陣6.2.4 線性分組碼的編碼線性分組碼的編碼6.2.5 線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2.7 線性分組碼的性能線性分組碼的性能6.2.8 漢明碼漢明碼6.2.9 由已知碼構(gòu)造新碼的方法由已知碼構(gòu)造新碼的方法6.2.10 線性分組碼的碼限線性分組碼的碼限6.2 線性分組碼線性分組碼第六章 信道編碼2

2、022/7/43(2) 糾錯(cuò)譯碼糾錯(cuò)譯碼 最佳譯碼準(zhǔn)則（最大似然譯碼）最佳譯碼準(zhǔn)則（最大似然譯碼）通信是一個(gè)統(tǒng)計(jì)過程，糾、檢錯(cuò)能力最終要反映到差錯(cuò)概率上。通信是一個(gè)統(tǒng)計(jì)過程，糾、檢錯(cuò)能力最終要反映到差錯(cuò)概率上。對(duì)于對(duì)于FEC方式，采用糾錯(cuò)碼后的碼字差錯(cuò)概率為方式，采用糾錯(cuò)碼后的碼字差錯(cuò)概率為pwe，p(C C)：發(fā)送碼字：發(fā)送碼字C C 的先驗(yàn)概率的先驗(yàn)概率p(C C/R R)：后驗(yàn)概率：后驗(yàn)概率若碼字?jǐn)?shù)為若碼字?jǐn)?shù)為 2k，對(duì)充分隨機(jī)的消息源有，對(duì)充分隨機(jī)的消息源有p(C C)=1/ 2k，所以最小化的，所以最小化的pwe等價(jià)為最小化等價(jià)為最小化p(C CC CR R )，又等價(jià)為最大化，又等

3、價(jià)為最大化p(C C=C CR R)；)()(RCCCpppwe6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼第六章 信道編碼2022/7/44對(duì)于對(duì)于 BSC 信道：最大化的信道：最大化的 p(C C=C CR R) 等價(jià)于最大化的等價(jià)于最大化的 p(R RC C) ，最大化的最大化的p(R RC C) 又等價(jià)于最小化又等價(jià)于最小化 d(R R,C C)，所以使差錯(cuò)概率最小，所以使差錯(cuò)概率最小的譯碼是使接收向量的譯碼是使接收向量 R R 與輸出碼字與輸出碼字 C C 距離最小的譯碼。距離最小的譯碼。) ,(),(min: CRCRCCddii6.2.6 線性分組碼的譯

4、碼線性分組碼的譯碼6.2線線性性分分組組碼碼第六章 信道編碼2022/7/45 標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列碼矢參數(shù)碼矢參數(shù)發(fā)送碼矢：取自于發(fā)送碼矢：取自于 2k 個(gè)碼字集合個(gè)碼字集合C C；接收矢量：可以是接收矢量：可以是 2n 個(gè)個(gè) n 重中任一個(gè)矢量。重中任一個(gè)矢量。譯碼方法譯碼方法把把 2n 個(gè)個(gè) n 重重劃分為劃分為 2k 個(gè)互不相交的子集個(gè)互不相交的子集 ，使，使得在每個(gè)子集中僅含一個(gè)碼矢；得在每個(gè)子集中僅含一個(gè)碼矢；根據(jù)碼矢和子集間一一對(duì)應(yīng)關(guān)系，若接收矢量根據(jù)碼矢和子集間一一對(duì)應(yīng)關(guān)系，若接收矢量 R Rl 落在子集落在子集 D Dl中，就把中，就把 R Rl 譯為子集譯為子集 D Dl 含有

5、的碼字含有的碼字 C Cl；當(dāng)接收矢量當(dāng)接收矢量 R R 與實(shí)際發(fā)送碼矢在同一子集中時(shí)，譯碼就是正確與實(shí)際發(fā)送碼矢在同一子集中時(shí)，譯碼就是正確的。的。標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列：是對(duì)給定的是對(duì)給定的 (n,k) 線性碼，將線性碼，將 2n 個(gè)個(gè) n 重劃分為重劃分為 2k 個(gè)子個(gè)子集的一種方法。集的一種方法。6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼k221,DDD第六章 信道編碼2022/7/46標(biāo)準(zhǔn)陣列構(gòu)造方法標(biāo)準(zhǔn)陣列構(gòu)造方法先將先將 2k 個(gè)碼矢排成一行，作為個(gè)碼矢排成一行，作為標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列的第一行，并將全的第一行，并將全0碼矢碼矢C C1=(000)放在最左面的位

6、置上；放在最左面的位置上；然后在剩下的然后在剩下的 (2n2k) 個(gè)個(gè) n 重中選取一個(gè)重量最輕的重中選取一個(gè)重量最輕的 n 重重 E E2 放在放在全全0碼矢碼矢 C C1 下面，再將下面，再將 E E2 分別和碼矢分別和碼矢 相加，放在相加，放在對(duì)應(yīng)碼矢下面構(gòu)成陣列第二行；對(duì)應(yīng)碼矢下面構(gòu)成陣列第二行；在第二次剩下的在第二次剩下的 n 重中，選取重量最輕的重中，選取重量最輕的 n 重重 E E3，放在，放在 E E2 下面，下面，并將并將 E E3 分別加到第一行各碼矢上，得到第三行；分別加到第一行各碼矢上，得到第三行；，繼續(xù)這樣做下去，直到全部，繼續(xù)這樣做下去，直到全部 n 重用完為止。得

7、到表重用完為止。得到表6.2.2所示所示的給定的給定 (n,k) 線性碼的標(biāo)準(zhǔn)陣列。線性碼的標(biāo)準(zhǔn)陣列。6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼k232,CCC第六章 信道編碼2022/7/476.2.6 線性分組碼的譯碼6.2線性分組碼k2C22ECk32ECkknk22ECkni2ECkn22ECkn2E第六章 信道編碼2022/7/48標(biāo)準(zhǔn)陣列的特性標(biāo)準(zhǔn)陣列的特性定理定理6.2.5：在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且 2n 個(gè)個(gè) n 重中任一個(gè)重中任一個(gè) n 重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。重在陣列中出現(xiàn)一次且僅出

8、現(xiàn)一次。 證明證明：L因?yàn)殛嚵兄腥我恍卸际怯伤x出某一因?yàn)殛嚵兄腥我恍卸际怯伤x出某一 n 重重分別與分別與 2k 個(gè)碼矢相個(gè)碼矢相加構(gòu)成的，而加構(gòu)成的，而 2k 個(gè)碼矢互不相同，它們與所選矢量的和也不個(gè)碼矢互不相同，它們與所選矢量的和也不可能相同，所以在同一行中沒有相同的矢量；可能相同，所以在同一行中沒有相同的矢量；L在構(gòu)造標(biāo)準(zhǔn)陣列時(shí)，是用完全部在構(gòu)造標(biāo)準(zhǔn)陣列時(shí)，是用完全部 n 重為止，因而每個(gè)重為止，因而每個(gè) n 重必重必出現(xiàn)一次；出現(xiàn)一次；L每個(gè)每個(gè)n重只能出現(xiàn)一次。重只能出現(xiàn)一次。 假定某一假定某一 n 重重 X X 出現(xiàn)在第出現(xiàn)在第 l 行第行第 i 列，那么列，那么 X XE El

9、+C Ci， 又假設(shè)又假設(shè) X X 出現(xiàn)在第出現(xiàn)在第 m 行第行第 j 列，那么列，那么 X XE Em+C Cj，ll)的第的第 一個(gè)元素，而按陣列構(gòu)造規(guī)則，后面行的第一個(gè)元素是前面一個(gè)元素，而按陣列構(gòu)造規(guī)則，后面行的第一個(gè)元素是前面 行中未曾出現(xiàn)過的元素，這就和陣列構(gòu)造規(guī)則相矛盾。行中未曾出現(xiàn)過的元素，這就和陣列構(gòu)造規(guī)則相矛盾。6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼第六章 信道編碼2022/7/410定理定理6.2.6 (線性碼糾錯(cuò)極限定理線性碼糾錯(cuò)極限定理)：二元二元 (n,k) 線性碼能糾線性碼能糾 2nk 個(gè)錯(cuò)誤圖樣。個(gè)錯(cuò)誤圖樣。這這 2nk 個(gè)可糾的

10、錯(cuò)誤圖樣，包括個(gè)可糾的錯(cuò)誤圖樣，包括0 0矢量在內(nèi)，矢量在內(nèi)，即把無錯(cuò)的情況也看成一個(gè)可糾的錯(cuò)誤圖樣。即把無錯(cuò)的情況也看成一個(gè)可糾的錯(cuò)誤圖樣。 證明證明：L(n,k) 線性碼的標(biāo)準(zhǔn)陣列有線性碼的標(biāo)準(zhǔn)陣列有 2k 列（和碼矢矢量相等），列（和碼矢矢量相等），2n/2k= 2nk行，且任何兩列和兩行都沒有相同的元素。行，且任何兩列和兩行都沒有相同的元素。L陪集陪集：標(biāo)準(zhǔn)陣列的每一行叫做碼的一個(gè)陪集。：標(biāo)準(zhǔn)陣列的每一行叫做碼的一個(gè)陪集。L陪集首陪集首：每個(gè)陪集的第一個(gè)元素叫做陪集首。：每個(gè)陪集的第一個(gè)元素叫做陪集首。L每一列包含每一列包含 2nk 個(gè)元素，最上面的是一個(gè)碼矢，其它元素是個(gè)元素，最上面

11、的是一個(gè)碼矢，其它元素是陪集首和該碼矢之和，例如第陪集首和該碼矢之和，例如第 j 列為列為6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼),(232jjjjjknCECECECD第六章 信道編碼2022/7/411L若發(fā)送碼矢為若發(fā)送碼矢為 C Cj，信道干擾的錯(cuò)誤圖樣是陪集首，則接收，信道干擾的錯(cuò)誤圖樣是陪集首，則接收矢量矢量 R R 必在必在 D Dj 中；中；L若錯(cuò)誤圖樣不是陪集首，則接收矢量若錯(cuò)誤圖樣不是陪集首，則接收矢量 R R不在不在 D Dj 中，則譯成中，則譯成其它碼字，造成錯(cuò)誤譯碼；其它碼字，造成錯(cuò)誤譯碼；L當(dāng)且僅當(dāng)錯(cuò)誤圖樣為陪集首時(shí)，譯碼才是正確的。

12、當(dāng)且僅當(dāng)錯(cuò)誤圖樣為陪集首時(shí)，譯碼才是正確的。L可糾正的錯(cuò)誤圖樣可糾正的錯(cuò)誤圖樣：這：這 2nk 個(gè)陪集首稱為可糾正的錯(cuò)誤圖個(gè)陪集首稱為可糾正的錯(cuò)誤圖樣。樣。6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼第六章 信道編碼2022/7/412線性碼糾錯(cuò)能力與監(jiān)督元數(shù)目的關(guān)系線性碼糾錯(cuò)能力與監(jiān)督元數(shù)目的關(guān)系：一個(gè)可糾一個(gè)可糾 t 個(gè)錯(cuò)個(gè)錯(cuò)誤的線性碼必須滿足誤的線性碼必須滿足 上式中等式成立時(shí)的線性碼稱為上式中等式成立時(shí)的線性碼稱為完備碼完備碼。即。即 證明證明：L糾一個(gè)錯(cuò)誤的糾一個(gè)錯(cuò)誤的 (n,k) 線性碼，必須能糾正線性碼，必須能糾正 個(gè)錯(cuò)誤個(gè)錯(cuò)誤圖樣，因此圖樣，因此6.2

13、.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼11nnnkn1112tiknintnnn02112tiknin02第六章 信道編碼2022/7/413L對(duì)糾兩個(gè)錯(cuò)誤的對(duì)糾兩個(gè)錯(cuò)誤的 (n,k) 線性碼，必須能糾線性碼，必須能糾 個(gè)錯(cuò)個(gè)錯(cuò)誤圖樣，所以誤圖樣，所以L依此類推，一個(gè)糾依此類推，一個(gè)糾 t 個(gè)錯(cuò)誤的個(gè)錯(cuò)誤的 (n,k) 線性碼必須滿足線性碼必須滿足L對(duì)于完備碼，對(duì)于完備碼，由碼的糾錯(cuò)能力所確定的伴隨式數(shù)恰好等于可糾由碼的糾錯(cuò)能力所確定的伴隨式數(shù)恰好等于可糾的錯(cuò)誤圖樣數(shù)，所以完備碼的的錯(cuò)誤圖樣數(shù)，所以完備碼的 (nk) 個(gè)監(jiān)督碼元得到了充分的個(gè)監(jiān)督碼元得到了充分的利用利

14、用。6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼211nn2112nnkntiknintnnn02112第六章 信道編碼2022/7/414定義定義：(n,k) 線性碼的所有線性碼的所有 2nk 個(gè)伴隨式，在譯碼過程中若都個(gè)伴隨式，在譯碼過程中若都用來糾正所有小于等于用來糾正所有小于等于 個(gè)隨機(jī)錯(cuò)誤，以及部分個(gè)隨機(jī)錯(cuò)誤，以及部分大于大于 t 的錯(cuò)誤圖樣，則這種譯碼方法稱為的錯(cuò)誤圖樣，則這種譯碼方法稱為完備譯碼完備譯碼。限定距離譯碼限定距離譯碼：任一個(gè)任一個(gè) (n,k) 線性碼，能糾正線性碼，能糾正 個(gè)隨機(jī)錯(cuò)誤，如果在譯碼時(shí)僅糾正個(gè)隨機(jī)錯(cuò)誤，如果在譯碼時(shí)僅糾正 t t

15、個(gè)錯(cuò)誤，而當(dāng)錯(cuò)誤個(gè)數(shù)個(gè)錯(cuò)誤，而當(dāng)錯(cuò)誤個(gè)數(shù)大于大于t時(shí)，譯碼器不進(jìn)行糾錯(cuò)而僅指出發(fā)生了錯(cuò)誤，稱這種方時(shí)，譯碼器不進(jìn)行糾錯(cuò)而僅指出發(fā)生了錯(cuò)誤，稱這種方法為法為限定距離譯碼限定距離譯碼。2/ ) 1( dt6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼2/ ) 1( dt第六章 信道編碼2022/7/415從多維矢量空間的角度看完備碼從多維矢量空間的角度看完備碼：假定圍繞每一個(gè)碼字假定圍繞每一個(gè)碼字 C Ci 放置一個(gè)半徑為放置一個(gè)半徑為 t 的球，每個(gè)球內(nèi)包含的球，每個(gè)球內(nèi)包含了與該碼字漢明距離小于等于了與該碼字漢明距離小于等于 t 的所有接收碼字的所有接收碼字 R R 的

16、集合；的集合；這樣，在半徑為這樣，在半徑為 t=(dmin1)/2 的球內(nèi)的接收碼字?jǐn)?shù)是的球內(nèi)的接收碼字?jǐn)?shù)是因?yàn)橛幸驗(yàn)橛?2k 個(gè)可能發(fā)送的碼字，也就有個(gè)可能發(fā)送的碼字，也就有2k 個(gè)不相重疊的半徑為個(gè)不相重疊的半徑為t的的球。包含在球。包含在2k個(gè)球中的碼字總數(shù)不會(huì)超過個(gè)球中的碼字總數(shù)不會(huì)超過2n個(gè)可能的接收碼字。個(gè)可能的接收碼字。于是一個(gè)糾于是一個(gè)糾 t 個(gè)差錯(cuò)的碼必然滿足不等式個(gè)差錯(cuò)的碼必然滿足不等式如果上式中等號(hào)成立，表示所有的接收碼字都落在如果上式中等號(hào)成立，表示所有的接收碼字都落在 2k 個(gè)球內(nèi)，個(gè)球內(nèi)，而球外沒有一個(gè)碼，而球外沒有一個(gè)碼，這就是完備碼這就是完備碼。tikntink

17、inin00222即6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼tiin0 第六章 信道編碼2022/7/416完備碼特性完備碼特性：圍繞：圍繞 2k 個(gè)個(gè)碼字，漢明距離為碼字，漢明距離為t=(dmin1)/2的所有球的所有球都是不相交的，每一個(gè)都是不相交的，每一個(gè)接收碼字都落在這些球接收碼字都落在這些球中之一，因此接收碼與中之一，因此接收碼與發(fā)送碼的距離至多為發(fā)送碼的距離至多為 t，這時(shí)所有重量這時(shí)所有重量t的錯(cuò)誤的錯(cuò)誤圖樣都能用最佳（最小圖樣都能用最佳（最小距離）譯碼器得到糾正，距離）譯碼器得到糾正，而所有重量而所有重量t+1的錯(cuò)誤的錯(cuò)誤圖樣都不能糾正。圖樣都不能

18、糾正。6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼第六章 信道編碼2022/7/417舉例：對(duì)糾一個(gè)錯(cuò)誤的舉例：對(duì)糾一個(gè)錯(cuò)誤的 (7,4) 漢明碼，漢明碼， 可見，可見，(7,4)漢明碼是一個(gè)完備碼。漢明碼是一個(gè)完備碼。所有漢明碼都是完備碼所有漢明碼都是完備碼（滿足（滿足2nk = 2m=n+1）。）。標(biāo)準(zhǔn)陣列譯碼標(biāo)準(zhǔn)陣列譯碼=最小距離譯碼法最小距離譯碼法=最佳譯碼法最佳譯碼法陪集首是可糾正的錯(cuò)誤圖樣，為了使譯碼錯(cuò)誤概率最小，陪集首是可糾正的錯(cuò)誤圖樣，為了使譯碼錯(cuò)誤概率最小，應(yīng)選取出現(xiàn)概率最大的錯(cuò)誤圖樣作陪集首；應(yīng)選取出現(xiàn)概率最大的錯(cuò)誤圖樣作陪集首；重量較輕的錯(cuò)誤圖樣

19、出現(xiàn)概率較大，所以在構(gòu)造標(biāo)準(zhǔn)陣列重量較輕的錯(cuò)誤圖樣出現(xiàn)概率較大，所以在構(gòu)造標(biāo)準(zhǔn)陣列時(shí)是選取重量最輕的時(shí)是選取重量最輕的 n 重作陪集首；重作陪集首；這樣，當(dāng)錯(cuò)誤圖樣為陪集首時(shí)（可糾的錯(cuò)誤圖樣），接收這樣，當(dāng)錯(cuò)誤圖樣為陪集首時(shí)（可糾的錯(cuò)誤圖樣），接收矢量與原發(fā)送碼矢間的距離（等于陪集首）最??；矢量與原發(fā)送碼矢間的距離（等于陪集首）最??；6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼112,811, 82nnknkn所以第六章 信道編碼2022/7/418因此，選擇重量最輕的元素作陪集首，按標(biāo)準(zhǔn)陣列譯碼就是因此，選擇重量最輕的元素作陪集首，按標(biāo)準(zhǔn)陣列譯碼就是按最小距離譯碼；

20、按最小距離譯碼；所以標(biāo)準(zhǔn)陣列譯碼法也是最佳譯碼法。所以標(biāo)準(zhǔn)陣列譯碼法也是最佳譯碼法。定理定理6.2.7：在標(biāo)準(zhǔn)陣列中，一個(gè)陪集的所有：在標(biāo)準(zhǔn)陣列中，一個(gè)陪集的所有 2k 個(gè)個(gè) n 重有相同的重有相同的伴隨式，不同的陪集伴隨式互不相同。伴隨式，不同的陪集伴隨式互不相同。 證明證明：設(shè)設(shè) H H 為給定為給定 (n,k) 線性碼的監(jiān)督矩陣，在陪集首為線性碼的監(jiān)督矩陣，在陪集首為 E El 的陪集的陪集中的任意矢量中的任意矢量 R R 為為 R R=E El+C Ci, i=1,2,2k其伴隨式為其伴隨式為 S S=RHRHT=(E El+C Ci)HHT=E ElHHT+C CiHHT =E El

21、HHT上式表明：上式表明：陪集中任意矢量的伴隨式等于陪集首的伴隨式陪集中任意矢量的伴隨式等于陪集首的伴隨式。即同一陪集中所有伴隨式相同。即同一陪集中所有伴隨式相同。不同陪集中，由于陪集首不同所以伴隨式不同。不同陪集中，由于陪集首不同所以伴隨式不同。6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼第六章 信道編碼2022/7/419 結(jié)論結(jié)論任意任意 n 重的伴隨式?jīng)Q定于它在標(biāo)準(zhǔn)陣列中所在陪集的陪集首。重的伴隨式?jīng)Q定于它在標(biāo)準(zhǔn)陣列中所在陪集的陪集首。標(biāo)準(zhǔn)陣列的陪集首和伴隨式是一一對(duì)應(yīng)的，因而碼的可糾錯(cuò)誤圖樣標(biāo)準(zhǔn)陣列的陪集首和伴隨式是一一對(duì)應(yīng)的，因而碼的可糾錯(cuò)誤圖樣和伴隨式是

22、一一對(duì)應(yīng)的，應(yīng)用此對(duì)應(yīng)關(guān)系可以構(gòu)成比標(biāo)準(zhǔn)陣列簡單和伴隨式是一一對(duì)應(yīng)的，應(yīng)用此對(duì)應(yīng)關(guān)系可以構(gòu)成比標(biāo)準(zhǔn)陣列簡單得多的譯碼表，從而得到得多的譯碼表，從而得到 (n,k) 線性碼的一般譯碼步驟。線性碼的一般譯碼步驟。(n,k) 線性碼的一般譯碼步驟線性碼的一般譯碼步驟計(jì)算接收矢量計(jì)算接收矢量 R R 的伴隨式的伴隨式 S ST=HRHRT ；根據(jù)伴隨式和錯(cuò)誤圖樣一一對(duì)應(yīng)的關(guān)系，利用伴隨式譯碼表，根據(jù)伴隨式和錯(cuò)誤圖樣一一對(duì)應(yīng)的關(guān)系，利用伴隨式譯碼表，由伴隨式譯出由伴隨式譯出 R R 的錯(cuò)誤圖樣的錯(cuò)誤圖樣 E E；將接收字減錯(cuò)誤圖樣，得發(fā)送碼矢的估值將接收字減錯(cuò)誤圖樣，得發(fā)送碼矢的估值 C C=R RE

23、E 。6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼第六章 信道編碼2022/7/420 上述譯碼法稱為伴隨式譯碼法或查表譯碼法。上述譯碼法稱為伴隨式譯碼法或查表譯碼法。線性分組碼一般譯碼器線性分組碼一般譯碼器 譯碼器如圖譯碼器如圖6.2.9。這種查表譯碼法具有最小的譯碼延遲和最小的。這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯(cuò)誤概率，原則上可用于任何譯碼錯(cuò)誤概率，原則上可用于任何 (n,k) 線性碼。線性碼。6.2.6 線性分組碼的譯碼線性分組碼的譯碼6.2線線性性分分組組碼碼第六章 信道編碼2022/7/421 在通信中檢糾錯(cuò)碼的實(shí)際性能是在統(tǒng)計(jì)上體現(xiàn)出來在通信中

24、檢糾錯(cuò)碼的實(shí)際性能是在統(tǒng)計(jì)上體現(xiàn)出來的。以下分析均以的。以下分析均以BSC信道為模型。信道為模型。(1)不可檢錯(cuò)誤概率不可檢錯(cuò)誤概率(2)譯碼錯(cuò)誤概率譯碼錯(cuò)誤概率(3)譯碼失敗概率譯碼失敗概率(4)比特誤碼率比特誤碼率6.2.7 線性分組碼的性能線性分組碼的性能6.2線線性性分分組組碼碼第六章 信道編碼2022/7/422(1)不可檢錯(cuò)誤概率不可檢錯(cuò)誤概率 pud由由 (n,k) 線性碼的重量分布求線性碼的重量分布求 pud令令A(yù)i為碼的重量分布，表示重量為為碼的重量分布，表示重量為i的碼字個(gè)數(shù)，的碼字個(gè)數(shù)，i=0,1,2,n；由于由于僅當(dāng)錯(cuò)誤圖樣與碼矢集合中的非僅當(dāng)錯(cuò)誤圖樣與碼矢集合中的非0

25、碼矢相同時(shí)，才不能檢碼矢相同時(shí)，才不能檢出錯(cuò)誤出錯(cuò)誤，所以（，所以（p是是BSC的誤碼率，且碼字等概發(fā)送的誤碼率，且碼字等概發(fā)送）舉例舉例： (7,3) 碼的重量分布是碼的重量分布是 A0=1,A1=A2=A3=0,A4=7，其不可，其不可檢錯(cuò)誤概率為檢錯(cuò)誤概率為 pud7p4(1p)3，若，若p=0.01，則，則 pud6.8108。利用利用 (n,k) 碼重量分布與其對(duì)偶碼的重量分布關(guān)系求碼重量分布與其對(duì)偶碼的重量分布關(guān)系求 pud設(shè)設(shè)A0,A1,A2, ,An 是是 (n,k) 碼碼的重量分布；的重量分布；B0,B1,B2, ,Bn 是是它的對(duì)偶碼它的對(duì)偶碼的重量分布；的重量分布；6.2

26、.7 線性分組碼的性能線性分組碼的性能6.2線線性性分分組組碼碼)23. 2 . 6(11niiniiudppAp第六章 信道編碼2022/7/423對(duì)偶碼的重量枚舉式對(duì)偶碼的重量枚舉式：下面的多項(xiàng)式稱為：下面的多項(xiàng)式稱為 (n,k) 碼和它的對(duì)偶碼和它的對(duì)偶碼的重量枚舉式。碼的重量枚舉式。MacWilliams恒等式恒等式：若已知線性碼的對(duì)偶碼的重量分布，就：若已知線性碼的對(duì)偶碼的重量分布，就可確定該碼本身的重量分布?？纱_定該碼本身的重量分布。由式由式(6.2.23)得得)24. 2 . 6()()(22102210nnnnxBxBxBBxBxAxAxAAxA6.2.7 線性分組碼的性能線性

27、分組碼的性能6.2線線性性分分組組碼碼)25. 2 . 6(11)1 (2)()(xxBxxAnkn)26. 2 . 6(111niiinudppApp)23. 2 . 6(11niiniiudppAp第六章 信道編碼2022/7/424令令將這個(gè)恒等式代入式將這個(gè)恒等式代入式 (6.2.26) 得得將恒等式和將恒等式和 (6.2.25) 代入上式得代入上式得.)28. 2 . 6(111ppAppnud6.2.7 線性分組碼的性能線性分組碼的性能6.2線線性性分分組組碼碼)27. 2 . 6(1111)24. 2 . 6(110niiippAppAAppx，得到恒等式，并考慮到，代入式nii

28、inknudpBpBppBp0)()21 ()21 ()29. 2 . 6()1 ()21 (2其中)24. 2 . 6()()(22102210nnnnxBxBxBBxBxAxAxAAxA第六章 信道編碼2022/7/425當(dāng)當(dāng)k (nk) 時(shí)，用式時(shí)，用式(6.2.29)計(jì)算計(jì)算 pud 則更容易。則更容易。舉例：已知舉例：已知 (7,4) 碼的監(jiān)督矩陣碼的監(jiān)督矩陣 HH(7,4)，它等于其對(duì)偶碼的生成，它等于其對(duì)偶碼的生成矩陣矩陣 GG(7,3)，即，即 由此生成矩陣的行的線性組合，可得到由此生成矩陣的行的線性組合，可得到(7,3)碼的碼的8個(gè)碼字個(gè)碼字 由此得到由此得到 (7,3) 對(duì)

29、偶碼的重量枚舉式為對(duì)偶碼的重量枚舉式為 B(x)=1+7x4 利用式利用式 (6.2.29) 得出得出 (7,4) 碼的未檢出錯(cuò)誤概率為碼的未檢出錯(cuò)誤概率為 pud =231+7(12p)4(1p)7 設(shè)設(shè) p=0.01，則，則 pud =6106 。100101101011100010111)4,7()3 ,7(HG6.2.7 線性分組碼的性能線性分組碼的性能6.2線線性性分分組組碼碼01001110011101110100111101001010011100111001110100000000第六章 信道編碼2022/7/426(2) 譯碼錯(cuò)誤概率譯碼錯(cuò)誤概率pwe正確譯碼概率正確譯碼概率

30、pwc：糾正小于等于：糾正小于等于t個(gè)差錯(cuò)的概率個(gè)差錯(cuò)的概率譯碼錯(cuò)誤概率譯碼錯(cuò)誤概率 pwe譯碼錯(cuò)誤發(fā)生在差錯(cuò)數(shù)目大于譯碼錯(cuò)誤發(fā)生在差錯(cuò)數(shù)目大于 t，接收向量，接收向量 R R 與另一碼字與另一碼字 C C 的距離小于等于的距離小于等于 t 的情況；的情況；D Di 是重量是重量 i 并譯為錯(cuò)誤碼字的可能的接收向量并譯為錯(cuò)誤碼字的可能的接收向量 R R 的數(shù)目，即的數(shù)目，即譯碼錯(cuò)誤概率譯碼錯(cuò)誤概率pwe為為6.2.7 線性分組碼的性能線性分組碼的性能6.2線線性性分分組組碼碼tiiniwcppinp01)30. 2 . 6(,)(CCCRRRDtdiWintiinintiiniiweppinp

31、pp1111D第六章 信道編碼2022/7/427(3)譯碼失敗概率譯碼失敗概率pwf由于仍存在不滿足式由于仍存在不滿足式 (6.2.30) 的接收碼矢的接收碼矢 R R，對(duì)于限定距離譯碼，對(duì)于限定距離譯碼器來說就處于譯碼失敗狀態(tài)，即器來說就處于譯碼失敗狀態(tài)，即 pwf=1 pwc pwe 圖圖6.2.30中中RA正確譯碼概率正確譯碼概率RB譯碼錯(cuò)誤概率譯碼錯(cuò)誤概率RC譯碼失敗概率譯碼失敗概率6.2.7 線性分組碼的性能線性分組碼的性能6.2線線性性分分組組碼碼第六章 信道編碼2022/7/428(4) 比特誤碼率比特誤碼率pbc：信道的比特差錯(cuò)概率信道的比特差錯(cuò)概率，對(duì)于，對(duì)于BSC信道，信

32、道，pbc等于信道轉(zhuǎn)移概率等于信道轉(zhuǎn)移概率p。pbd：譯碼錯(cuò)誤導(dǎo)致的碼字之間的比特差錯(cuò)率譯碼錯(cuò)誤導(dǎo)致的碼字之間的比特差錯(cuò)率。pbm：消息源與消息接收終端之間的比特差錯(cuò)概率消息源與消息接收終端之間的比特差錯(cuò)概率。一般認(rèn)為消息和碼字之間的映射不改變碼字差錯(cuò)導(dǎo)致在整個(gè)碼一般認(rèn)為消息和碼字之間的映射不改變碼字差錯(cuò)導(dǎo)致在整個(gè)碼長內(nèi)比特差錯(cuò)的均勻分布特性，在統(tǒng)計(jì)意義上有長內(nèi)比特差錯(cuò)的均勻分布特性，在統(tǒng)計(jì)意義上有 pbm pbd6.2.7 線性分組碼的性能線性分組碼的性能6.2線線性性分分組組碼碼第六章 信道編碼2022/7/429pbe 譯碼錯(cuò)誤的誤碼率譯碼錯(cuò)誤的誤碼率：設(shè)碼字是等概率發(fā)送，則設(shè)碼字是等概

33、率發(fā)送，則 是發(fā)送全是發(fā)送全0碼字并錯(cuò)接收為碼字并錯(cuò)接收為 重量為重量為j的碼字的概率；的碼字的概率；Pbc 與與 pwe的關(guān)系的關(guān)系碼字錯(cuò)必然有至少碼字錯(cuò)必然有至少 2t+1位碼字比特錯(cuò)；位碼字比特錯(cuò)；每個(gè)碼字平均有每個(gè)碼字平均有 位消息比特錯(cuò)，所以位消息比特錯(cuò)，所以pbc與與pwe有如下有如下漸進(jìn)關(guān)系漸進(jìn)關(guān)系njjwebejpnp1)(16.2.7 線性分組碼的性能線性分組碼的性能6.2線線性性分分組組碼碼)( jwep) 12(tnkwebepnktkp) 12(第六章 信道編碼2022/7/430pbf 譯碼失敗造成的誤碼率譯碼失敗造成的誤碼率pbd譯碼后總的誤碼率：譯碼后總的誤碼率：

34、pbd = pbe+pbf6.2.7 線性分組碼的性能線性分組碼的性能6.2線線性性分分組組碼碼ntiiniibfpipDinnp111第六章 信道編碼2022/7/431漢明碼是漢明于漢明碼是漢明于1950年提出的糾一個(gè)錯(cuò)誤的線性碼，也年提出的糾一個(gè)錯(cuò)誤的線性碼，也是第一個(gè)糾錯(cuò)碼。由于它編碼簡單，因而是在通信系統(tǒng)是第一個(gè)糾錯(cuò)碼。由于它編碼簡單，因而是在通信系統(tǒng)和數(shù)據(jù)存儲(chǔ)系統(tǒng)中得到廣泛應(yīng)用的一類線性碼。和數(shù)據(jù)存儲(chǔ)系統(tǒng)中得到廣泛應(yīng)用的一類線性碼。漢明碼的結(jié)構(gòu)參數(shù)：漢明碼的結(jié)構(gòu)參數(shù)：糾一個(gè)錯(cuò)誤的線性碼，其最小距離糾一個(gè)錯(cuò)誤的線性碼，其最小距離 dmin=3 ；監(jiān)督矩陣任意兩列；監(jiān)督矩陣任意兩列線性

35、無關(guān)線性無關(guān)/ H H 的任兩列互不相同的任兩列互不相同；沒有全；沒有全0 0的列。的列。監(jiān)督元個(gè)數(shù)監(jiān)督元個(gè)數(shù) nk=r；H H 陣中每列有陣中每列有 r 個(gè)元素，至多可構(gòu)成個(gè)元素，至多可構(gòu)成 2r1種互不相同的非種互不相同的非0 0列。列。對(duì)于任意正整數(shù)對(duì)于任意正整數(shù) m3，漢明碼的結(jié)構(gòu)參數(shù)為，漢明碼的結(jié)構(gòu)參數(shù)為碼長：碼長： n=2m1信息位數(shù)：信息位數(shù)： k=2mm1監(jiān)督位數(shù)：監(jiān)督位數(shù)： nk=m碼的最小距離：碼的最小距離：dmin=3(t=1)6.2.8 漢明碼漢明碼6.2線線性性分分組組碼碼第六章 信道編碼2022/7/432漢明碼監(jiān)督矩陣構(gòu)成的兩種方式漢明碼監(jiān)督矩陣構(gòu)成的兩種方式構(gòu)成

36、構(gòu)成 H H 陣的標(biāo)準(zhǔn)形式，陣的標(biāo)準(zhǔn)形式，HH=Q IQ Im，其中，其中 I Im 為為 m 階單位子陣，階單位子陣，子陣子陣 Q Q 是構(gòu)造是構(gòu)造 I Im 后剩下的列任意排列。用這種形式的后剩下的列任意排列。用這種形式的 H H 陣編陣編出的漢明碼是系統(tǒng)碼。出的漢明碼是系統(tǒng)碼。按按m重（重量為重（重量為m ）表示的二進(jìn)制順序排列。按這種形式）表示的二進(jìn)制順序排列。按這種形式 H H 陣陣編出的碼是非系統(tǒng)碼。當(dāng)發(fā)生可糾的單個(gè)錯(cuò)誤時(shí)，伴隨式為編出的碼是非系統(tǒng)碼。當(dāng)發(fā)生可糾的單個(gè)錯(cuò)誤時(shí)，伴隨式為 H H 陣中對(duì)應(yīng)的列，所以伴隨式的二進(jìn)制數(shù)值就是錯(cuò)誤位置號(hào)，有陣中對(duì)應(yīng)的列，所以伴隨式的二進(jìn)制數(shù)值

37、就是錯(cuò)誤位置號(hào)，有時(shí)這種碼譯碼比較方便。時(shí)這種碼譯碼比較方便。由于漢明碼可糾的錯(cuò)誤圖樣數(shù)為由于漢明碼可糾的錯(cuò)誤圖樣數(shù)為6.2.8 漢明碼漢明碼6.2線線性性分分組組碼碼因此漢明碼是完備碼。即滿足式，tiknminnn02121第六章 信道編碼2022/7/433(1) 擴(kuò)展擴(kuò)展/Extending和打孔和打孔/Puncturing(2) 增廣增廣/Augmenting和刪信和刪信/Expunging/Expurgating(3) 延長延長/Lengthening和縮短和縮短/Shortening(4) 乘積乘積/Product(5) 級(jí)聯(lián)級(jí)聯(lián)/Concatenating(6) 交織交織/Int

38、erleaving6.2.9 由已知碼構(gòu)造新碼的方法由已知碼構(gòu)造新碼的方法6.2線線性性分分組組碼碼第六章 信道編碼2022/7/434(1) 擴(kuò)展擴(kuò)展/Extending和打孔和打孔/Puncturing擴(kuò)展擴(kuò)展：保持碼字?jǐn)?shù)保持碼字?jǐn)?shù) k 不變，增加冗余位數(shù)以增加碼長。不變，增加冗余位數(shù)以增加碼長。打孔打孔：保持保持 k 不變，減小冗余位?？梢哉J(rèn)為是擴(kuò)展的逆過程。不變，減小冗余位?？梢哉J(rèn)為是擴(kuò)展的逆過程。(2) 增廣增廣/Augmenting和刪信和刪信/Expunging/Expurgating增廣增廣：保持保持 n 不變，增加碼字?jǐn)?shù)目不變，增加碼字?jǐn)?shù)目 k。刪信刪信：保持保持 n 不變減

39、小不變減小 k。(3) 延長延長/Lengthening和縮短和縮短/Shortening延長延長：同時(shí)增加同時(shí)增加 k 和和 n?？s短縮短：同時(shí)減小同時(shí)減小 k 和和 n。6.2.9 由已知碼構(gòu)造新碼的方法由已知碼構(gòu)造新碼的方法6.2線線性性分分組組碼碼第六章 信道編碼2022/7/435舉例舉例： (7,4,3) 漢明碼的各種修正關(guān)系如圖漢明碼的各種修正關(guān)系如圖6.2.31所示。所示。6.2.9 由已知碼構(gòu)造新碼的方法由已知碼構(gòu)造新碼的方法6.2線線性性分分組組碼碼第六章 信道編碼2022/7/436(4) 乘積乘積/Product 消息作為陣列，分別進(jìn)行行列編碼。消息作為陣列，分別進(jìn)行行列編碼。(5) 級(jí)聯(lián)級(jí)聯(lián)/Concatenating對(duì)消息編碼后的碼字再進(jìn)行一次編碼。對(duì)消息編碼后的碼字再進(jìn)行一次編碼。級(jí)聯(lián)編碼的第一次所用碼稱外碼；第二次所用碼稱內(nèi)碼。級(jí)聯(lián)編碼的第一次所用碼稱外碼；第二次所用碼稱內(nèi)碼。級(jí)聯(lián)編碼常用于既有隨機(jī)差錯(cuò)又有突發(fā)差錯(cuò)的信道編碼。級(jí)聯(lián)編碼常用于既有隨機(jī)差錯(cuò)又有突發(fā)差錯(cuò)的信道編碼。(6) 交織交織/Interleaving交織編碼分為分組交織和卷積交織兩種。交織編碼分為分組交織和卷積交織兩種。如果交織編碼所用的如果交織編碼所用的 (n,k) 碼可以糾正碼可以糾正 t 個(gè)隨機(jī)差錯(cuò)，那么交織深個(gè)隨機(jī)差錯(cuò)，那么