1、2020/9/21,1,To choose time is to save time,2020/9/21,2,6.2.1 一般概念 6.2.2 一致監(jiān)督方程和一致監(jiān)督矩陣 6.2.3 線性分組碼的生成矩陣 6.2.4 線性分組碼的編碼 6.2.5 線性分組碼的最小距離、檢錯和糾錯能力 6.2.6 線性分組碼的譯碼 6.2.7 線性分組碼的性能 6.2.8 漢明碼 6.2.9 由已知碼構造新碼的方法 6.2.10 線性分組碼的碼限,6.2 線性分組碼,2020/9/21,3,(2) 糾錯譯碼 最佳譯碼準則（最大似然譯碼） 通信是一個統(tǒng)計過程，糾、檢錯能力最終要反映到差錯概率上。 對于FEC方式，

2、采用糾錯碼后的碼字差錯概率為pwe， p(C)：發(fā)送碼字C 的先驗概率 p(C/R)：后驗概率 若碼字數(shù)為 2k，對充分隨機的消息源有p(C)=1/ 2k，所以最小化的pwe等價為最小化p(CCR )，又等價為最大化p(C=CR)；,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,4,對于 BSC 信道：最大化的 p(C=CR) 等價于最大化的 p(RC) ，最大化的p(RC) 又等價于最小化 d(R,C)，所以使差錯概率最小的譯碼是使接收向量 R 與輸出碼字 C 距離最小的譯碼。,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,5, 標準陣列 碼矢參數(shù)

3、 發(fā)送碼矢：取自于 2k 個碼字集合C； 接收矢量：可以是 2n 個 n 重中任一個矢量。 譯碼方法 把 2n 個 n 重劃分為 2k 個互不相交的子集 ，使得在每個子集中僅含一個碼矢； 根據(jù)碼矢和子集間一一對應關系，若接收矢量 Rl 落在子集 Dl中，就把 Rl 譯為子集 Dl 含有的碼字 Cl； 當接收矢量 R 與實際發(fā)送碼矢在同一子集中時，譯碼就是正確的。 標準陣列：是對給定的 (n,k) 線性碼，將 2n 個 n 重劃分為 2k 個子集的一種方法。,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,6,標準陣列構造方法 先將 2k 個碼矢排成一行，作為標準陣列的第一行

4、，并將全0碼矢C1=(000)放在最左面的位置上； 然后在剩下的 (2n2k) 個 n 重中選取一個重量最輕的 n 重 E2 放在全0碼矢 C1 下面，再將 E2 分別和碼矢 相加，放在對應碼矢下面構成陣列第二行； 在第二次剩下的 n 重中，選取重量最輕的 n 重 E3，放在 E2 下面，并將 E3 分別加到第一行各碼矢上，得到第三行； ，繼續(xù)這樣做下去，直到全部 n 重用完為止。得到表6.2.2所示的給定 (n,k) 線性碼的標準陣列。,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,7,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,8,標準陣列的特

5、性 定理6.2.5：在標準陣列的同一行中沒有相同的矢量，而且 2n 個 n 重中任一個 n 重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。 證明： 因為陣列中任一行都是由所選出某一 n 重分別與 2k 個碼矢相加構成的，而 2k 個碼矢互不相同，它們與所選矢量的和也不可能相同，所以在同一行中沒有相同的矢量； 在構造標準陣列時，是用完全部 n 重為止，因而每個 n 重必出現(xiàn)一次； 每個n重只能出現(xiàn)一次。 假定某一 n 重 X 出現(xiàn)在第 l 行第 i 列，那么 XEl+Ci， 又假設 X 出現(xiàn)在第 m 行第 j 列，那么 XEm+Cj，lm，,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,

6、9,因此El+Ci = Em+Cj ，移項得Em = El+Ci+Cj 而Ci+Cj也是一個碼矢，設為Cs ，于是Em = El+Cs， 這意味著 Em 是第 l行中的一個矢量，但Em是第m行(ml)的第 一個元素，而按陣列構造規(guī)則，后面行的第一個元素是前面 行中未曾出現(xiàn)過的元素，這就和陣列構造規(guī)則相矛盾。,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,10,定理6.2.6 (線性碼糾錯極限定理)：二元 (n,k) 線性碼能糾 2nk 個錯誤圖樣。這 2nk 個可糾的錯誤圖樣，包括0矢量在內，即把無錯的情況也看成一個可糾的錯誤圖樣。 證明： (n,k) 線性碼的標準陣列有

7、 2k 列（和碼矢矢量相等），2n/2k= 2nk行，且任何兩列和兩行都沒有相同的元素。 陪集：標準陣列的每一行叫做碼的一個陪集。 陪集首：每個陪集的第一個元素叫做陪集首。 每一列包含 2nk 個元素，最上面的是一個碼矢，其它元素是陪集首和該碼矢之和，例如第 j 列為,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,11,若發(fā)送碼矢為 Cj，信道干擾的錯誤圖樣是陪集首，則接收矢量 R 必在 Dj 中； 若錯誤圖樣不是陪集首，則接收矢量 R不在 Dj 中，則譯成其它碼字，造成錯誤譯碼； 當且僅當錯誤圖樣為陪集首時，譯碼才是正確的。 可糾正的錯誤圖樣：這 2nk 個陪集首稱為可

8、糾正的錯誤圖樣。,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,12,線性碼糾錯能力與監(jiān)督元數(shù)目的關系：一個可糾 t 個錯誤的線性碼必須滿足 上式中等式成立時的線性碼稱為完備碼。即 證明： 糾一個錯誤的 (n,k) 線性碼，必須能糾正 個錯誤圖樣，因此,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,13,對糾兩個錯誤的 (n,k) 線性碼，必須能糾 個錯誤圖樣，所以 依此類推，一個糾 t 個錯誤的 (n,k) 線性碼必須滿足 對于完備碼，由碼的糾錯能力所確定的伴隨式數(shù)恰好等于可糾的錯誤圖樣數(shù)，所以完備碼的 (nk) 個監(jiān)督碼元得到了充分的利用。,6.

9、2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,14,定義：(n,k) 線性碼的所有 2nk 個伴隨式，在譯碼過程中若都用來糾正所有小于等于 個隨機錯誤，以及部分大于 t 的錯誤圖樣，則這種譯碼方法稱為完備譯碼。 限定距離譯碼：任一個 (n,k) 線性碼，能糾正 個隨機錯誤，如果在譯碼時僅糾正 t t 個錯誤，而當錯誤個數(shù)大于t時，譯碼器不進行糾錯而僅指出發(fā)生了錯誤，稱這種方法為限定距離譯碼。,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,15,從多維矢量空間的角度看完備碼： 假定圍繞每一個碼字 Ci 放置一個半徑為 t 的球，每個球內包含了與該碼字漢明距

10、離小于等于 t 的所有接收碼字 R 的集合； 這樣，在半徑為 t=(dmin1)/2 的球內的接收碼字數(shù)是 因為有 2k 個可能發(fā)送的碼字，也就有2k 個不相重疊的半徑為t的球。包含在2k個球中的碼字總數(shù)不會超過2n個可能的接收碼字。 于是一個糾 t 個差錯的碼必然滿足不等式 如果上式中等號成立，表示所有的接收碼字都落在 2k 個球內，而球外沒有一個碼，這就是完備碼。,6.2.6 線性分組碼的譯碼,6.2線性分組碼,Here,2020/9/21,16,完備碼特性：圍繞 2k 個碼字，漢明距離為t=(dmin1)/2的所有球都是不相交的，每一個接收碼字都落在這些球中之一，因此接收碼與發(fā)送碼的距離

11、至多為 t，這時所有重量t的錯誤圖樣都能用最佳（最小距離）譯碼器得到糾正，而所有重量t+1的錯誤圖樣都不能糾正。,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,17,舉例：對糾一個錯誤的 (7,4) 漢明碼， 可見，(7,4)漢明碼是一個完備碼。 所有漢明碼都是完備碼（滿足2nk = 2m=n+1）。 標準陣列譯碼=最小距離譯碼法=最佳譯碼法 陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，應選取出現(xiàn)概率最大的錯誤圖樣作陪集首； 重量較輕的錯誤圖樣出現(xiàn)概率較大，所以在構造標準陣列時是選取重量最輕的 n 重作陪集首； 這樣，當錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收矢量

12、與原發(fā)送碼矢間的距離（等于陪集首）最?。?6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,18,因此，選擇重量最輕的元素作陪集首，按標準陣列譯碼就是按最小距離譯碼； 所以標準陣列譯碼法也是最佳譯碼法。 定理6.2.7：在標準陣列中，一個陪集的所有 2k 個 n 重有相同的伴隨式，不同的陪集伴隨式互不相同。 證明： 設 H 為給定 (n,k) 線性碼的監(jiān)督矩陣，在陪集首為 El 的陪集中的任意矢量 R 為 R=El+Ci, i=1,2,2k 其伴隨式為 S=RHT=(El+Ci)HT=ElHT+CiHT =ElHT 上式表明：陪集中任意矢量的伴隨式等于陪集首的伴隨式。即同一陪

13、集中所有伴隨式相同。 不同陪集中，由于陪集首不同所以伴隨式不同。,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,19, 結論 任意 n 重的伴隨式決定于它在標準陣列中所在陪集的陪集首。 標準陣列的陪集首和伴隨式是一一對應的，因而碼的可糾錯誤圖樣和伴隨式是一一對應的，應用此對應關系可以構成比標準陣列簡單得多的譯碼表，從而得到 (n,k) 線性碼的一般譯碼步驟。 (n,k) 線性碼的一般譯碼步驟 計算接收矢量 R 的伴隨式 ST=HRT ； 根據(jù)伴隨式和錯誤圖樣一一對應的關系，利用伴隨式譯碼表，由伴隨式譯出 R 的錯誤圖樣 E； 將接收字減錯誤圖樣，得發(fā)送碼矢的估值 C=RE

14、 。,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,20,上述譯碼法稱為伴隨式譯碼法或查表譯碼法。 線性分組碼一般譯碼器 譯碼器如圖6.2.9。這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯誤概率，原則上可用于任何 (n,k) 線性碼。,6.2.6 線性分組碼的譯碼,6.2線性分組碼,2020/9/21,21,在通信中檢糾錯碼的實際性能是在統(tǒng)計上體現(xiàn)出來的。以下分析均以BSC信道為模型。 (1)不可檢錯誤概率 (2)譯碼錯誤概率 (3)譯碼失敗概率 (4)比特誤碼率,6.2.7 線性分組碼的性能,6.2線性分組碼,2020/9/21,22,(1)不可檢錯誤概率 pud 由

15、 (n,k) 線性碼的重量分布求 pud 令Ai為碼的重量分布，表示重量為i的碼字個數(shù)，i=0,1,2,n； 由于僅當錯誤圖樣與碼矢集合中的非0碼矢相同時，才不能檢出錯誤，所以（p是BSC的誤碼率，且碼字等概發(fā)送） 舉例： (7,3) 碼的重量分布是 A0=1,A1=A2=A3=0,A4=7，其不可檢錯誤概率為 pud7p4(1p)3，若p=0.01，則 pud6.8108。 利用 (n,k) 碼重量分布與其對偶碼的重量分布關系求 pud 設A0,A1,A2, ,An 是 (n,k) 碼的重量分布； B0,B1,B2, ,Bn 是它的對偶碼的重量分布；,6.2.7 線性分組碼的性能,6.2線性

16、分組碼,2020/9/21,23,對偶碼的重量枚舉式：下面的多項式稱為 (n,k) 碼和它的對偶碼的重量枚舉式。 MacWilliams恒等式：若已知線性碼的對偶碼的重量分布，就可確定該碼本身的重量分布。 由式(6.2.23)得,6.2.7 線性分組碼的性能,6.2線性分組碼,2020/9/21,24,令 將這個恒等式代入式 (6.2.26) 得 將恒等式和 (6.2.25) 代入上式得.,6.2.7 線性分組碼的性能,6.2線性分組碼,2020/9/21,25,當k (nk) 時，用式(6.2.29)計算 pud 則更容易。 舉例：已知 (7,4) 碼的監(jiān)督矩陣 H(7,4)，它等于其對偶碼

17、的生成矩陣 G(7,3)，即 由此生成矩陣的行的線性組合，可得到(7,3)碼的8個碼字 由此得到 (7,3) 對偶碼的重量枚舉式為 B(x)=1+7x4 利用式 (6.2.29) 得出 (7,4) 碼的未檢出錯誤概率為 pud =231+7(12p)4(1p)7 設 p=0.01，則 pud =6106 。,6.2.7 線性分組碼的性能,6.2線性分組碼,2020/9/21,26,(2) 譯碼錯誤概率pwe 正確譯碼概率pwc：糾正小于等于t個差錯的概率 譯碼錯誤概率 pwe 譯碼錯誤發(fā)生在差錯數(shù)目大于 t，接收向量 R 與另一碼字 C 的距離小于等于 t 的情況； Di 是重量 i 并譯為錯

18、誤碼字的可能的接收向量 R 的數(shù)目，即 譯碼錯誤概率pwe為,6.2.7 線性分組碼的性能,6.2線性分組碼,2020/9/21,27,(3)譯碼失敗概率pwf 由于仍存在不滿足式 (6.2.30) 的接收碼矢 R，對于限定距離譯碼器來說就處于譯碼失敗狀態(tài)，即 pwf=1 pwc pwe 圖6.2.30中 RA正確譯碼概率 RB譯碼錯誤概率 RC譯碼失敗概率,6.2.7 線性分組碼的性能,6.2線性分組碼,2020/9/21,28,(4) 比特誤碼率 pbc：信道的比特差錯概率，對于BSC信道，pbc等于信道轉移概率p。 pbd：譯碼錯誤導致的碼字之間的比特差錯率。 pbm：消息源與消息接收終

19、端之間的比特差錯概率。 一般認為消息和碼字之間的映射不改變碼字差錯導致在整個碼長內比特差錯的均勻分布特性，在統(tǒng)計意義上有 pbm pbd,6.2.7 線性分組碼的性能,6.2線性分組碼,2020/9/21,29,pbe 譯碼錯誤的誤碼率：設碼字是等概率發(fā)送，則 是發(fā)送全0碼字并錯接收為 重量為j的碼字的概率； Pbc 與 pwe的關系 碼字錯必然有至少 2t+1位碼字比特錯； 每個碼字平均有 位消息比特錯，所以pbc與pwe有如下漸進關系,6.2.7 線性分組碼的性能,6.2線性分組碼,2020/9/21,30,pbf 譯碼失敗造成的誤碼率 pbd譯碼后總的誤碼率： pbd = pbe+pbf

20、,6.2.7 線性分組碼的性能,6.2線性分組碼,2020/9/21,31,漢明碼是漢明于1950年提出的糾一個錯誤的線性碼，也是第一個糾錯碼。由于它編碼簡單，因而是在通信系統(tǒng)和數(shù)據(jù)存儲系統(tǒng)中得到廣泛應用的一類線性碼。 漢明碼的結構參數(shù)： 糾一個錯誤的線性碼，其最小距離 dmin=3 ；監(jiān)督矩陣任意兩列線性無關/ H 的任兩列互不相同；沒有全0的列。 監(jiān)督元個數(shù) nk=r；H 陣中每列有 r 個元素，至多可構成 2r1種互不相同的非0列。 對于任意正整數(shù) m3，漢明碼的結構參數(shù)為 碼長： n=2m1 信息位數(shù)： k=2mm1 監(jiān)督位數(shù)： nk=m 碼的最小距離：dmin=3(t=1),6.2.

21、8 漢明碼,6.2線性分組碼,2020/9/21,32,漢明碼監(jiān)督矩陣構成的兩種方式 構成 H 陣的標準形式，H=Q Im，其中 Im 為 m 階單位子陣，子陣 Q 是構造 Im 后剩下的列任意排列。用這種形式的 H 陣編出的漢明碼是系統(tǒng)碼。 按m重（重量為m ）表示的二進制順序排列。按這種形式 H 陣編出的碼是非系統(tǒng)碼。當發(fā)生可糾的單個錯誤時，伴隨式為 H 陣中對應的列，所以伴隨式的二進制數(shù)值就是錯誤位置號，有時這種碼譯碼比較方便。 由于漢明碼可糾的錯誤圖樣數(shù)為,6.2.8 漢明碼,6.2線性分組碼,2020/9/21,33,(1) 擴展/Extending和打孔/Puncturing (2

22、) 增廣/Augmenting和刪信/Expunging/Expurgating (3) 延長/Lengthening和縮短/Shortening (4) 乘積/Product (5) 級聯(lián)/Concatenating (6) 交織/Interleaving,6.2.9 由已知碼構造新碼的方法,6.2線性分組碼,2020/9/21,34,(1) 擴展/Extending和打孔/Puncturing 擴展：保持碼字數(shù) k 不變，增加冗余位數(shù)以增加碼長。 打孔：保持 k 不變，減小冗余位。可以認為是擴展的逆過程。 (2) 增廣/Augmenting和刪信/Expunging/Expurgating

23、 增廣：保持 n 不變，增加碼字數(shù)目 k。 刪信：保持 n 不變減小 k。 (3) 延長/Lengthening和縮短/Shortening 延長：同時增加 k 和 n。 縮短：同時減小 k 和 n。,6.2.9 由已知碼構造新碼的方法,6.2線性分組碼,2020/9/21,35,舉例： (7,4,3) 漢明碼的各種修正關系如圖6.2.31所示。,6.2.9 由已知碼構造新碼的方法,6.2線性分組碼,2020/9/21,36,(4) 乘積/Product 消息作為陣列，分別進行行列編碼。 (5) 級聯(lián)/Concatenating 對消息編碼后的碼字再進行一次編碼。 級聯(lián)編碼的第一次所用碼稱外碼；第二次所用碼稱內碼。 級聯(lián)編碼常用于既有隨機差錯又有突發(fā)差錯的信道編碼。 (6) 交織/Interleaving 交織編碼分為分組交織和卷積交織兩種。 如果交織編碼所用的 (n,k) 碼可以糾正 t 個隨機差錯，那么交