【正文】 ： 在標準陣列的同一行中沒有相同的矢量，而且 2n 個 n 重中任一個 n 重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。 [證明 ]： 糾錯譯碼 ? 假定某一 n 重 X 出現(xiàn)在第 l 行第 i 列，那么 X=El+Ci； ? 又假設 X 出現(xiàn)在第 m 行第 j 列，那么 X=Em+Cj， lm； ? 因此 El+Ci = Em+Cj ， 移項得 Em = El+Ci+Cj 而 Ci+Cj 也是一個碼字，設為Cs ， 于是 Em = El+Cs； ? 這意味著 Em 是第 l 行中的一個矢量，但 Em是第 m行 (ml) 的第一個元素 。 ? 按陣列構造規(guī)則，后面行的第一個元素是前面行中未曾出現(xiàn)過的元素，這就和陣列構造規(guī)則相矛盾。 每個 n 重只能出現(xiàn)一次的原因 線 性 分 組 碼 的 譯 碼 第 65頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (3) 標準陣列 ④ 標準陣列的特性 ? 定理 （線性碼糾錯極限定理） ： 二元 (n,k) 線性碼能糾 2n－ k 個錯誤圖樣。 這 2n－ k 個可糾的錯誤圖樣，包括 0 矢量在內(nèi)，即把無錯的情況也看成一個可糾的錯誤圖樣。 [證明 ]： ? 陪集 ： 標準陣列的每一行叫做碼的一個陪集。 ? 陪集首 ： 每個陪集的第一個元素叫做陪集首。 ? (n,k) 線性碼的標準陣列有 2k 列（和碼字數(shù)量相等）， 2n/2k= 2n－ k 行，且任何兩列和兩行都沒有相同的元素。 線 性 分 組 碼 的 譯 碼 第 66頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (3) 標準陣列 ④ 標準陣列的特性 ? 定理 （線性碼糾錯極限定理）： [證明 ]： ? 每一列包含 2n－ k 個元素，最上面的是一個碼字，其它元素是陪集首和該碼字之和，例如第 j 列為： ? 若發(fā)送碼字為 Cj， 信道干擾的錯誤圖樣是陪集首 ，則接收矢量 R 必在 Dj 中； 糾錯譯碼 ),( 232 jjjjj kn CECECECD ???? ??見表 線 性 分 組 碼 的 譯 碼 第 67頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (3) 標準陣列 ④ 標準陣列的特性 ? 定理 (線性碼糾錯極限定理 )： [證明 ]： ? 若錯誤圖樣不是陪集首，則接收矢量 R 不在 Dj 中，則譯成其它碼字，造成錯誤譯碼； ? 當且僅當錯誤圖樣為陪集首時，譯碼才是正確的。 ? 可糾正的錯誤圖樣： 這 2n－ k 個陪集首稱為可糾正的錯誤圖樣。 見表 線 性 分 組 碼 的 譯 碼 第 68頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (3) 標準陣列 ④ 標準陣列的特性 ? 線性碼糾錯能力與監(jiān)督元數(shù)目的關系： 一個可糾 t 個錯誤的線性碼必須滿足： ? 上式中等式成立時的線性碼稱為 完備碼 。即： ??? ?????????????????????????????????????? tiknintnnn02112 ???? ????????? tiknin02 線 性 分 組 碼 的 譯 碼 第 69頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (3) 標準陣列 ④ 標準陣列的特性 ? 線性碼糾錯能力與監(jiān)督元數(shù)目的關系： [證明 ]： ? 糾一個錯誤的 (n,k) 線性碼，必須能糾正 個錯誤圖樣，因此： ? 對糾兩個錯誤的 (n,k) 線性碼，必須能糾 個錯誤圖樣，所以： 11 ?????????n nnkn ????????????? 1112??????????????????211nn ????????????????????2112nnkn 線 性 分 組 碼 的 譯 碼 第 70頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (3) 標準陣列 ④ 標準陣列的特性 ? 線性碼糾錯能力與監(jiān)督元數(shù)目的關系： [證明 ]： ? 依此類推，一個糾 t 個錯誤的 (n,k) 線性碼必須滿足： ? 對于完備碼， 由碼的糾錯能力所確定的伴隨式數(shù)恰好等于可糾的錯誤圖樣數(shù)，所以完備碼的 (n－ k) 個監(jiān)督碼元得到了充分的利用。 ??? ?????????????????????????????????????? tiknintnnn02112 ? 線 性 分 組 碼 的 譯 碼 第 71頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (3) 標準陣列 ④ 標準陣列的特性 ? 完備譯碼 ： (n,k) 線性碼的所有 2n－ k 個伴隨式，在譯碼過程中都用來糾正所有小于等于 個隨機錯誤，以及部分大于 t 的錯誤圖樣。 ? 限定距離譯碼 ： 任一個 (n,k) 線性碼，能糾正 個隨機錯誤，如果在譯碼時僅糾正 t39。 t 個錯誤，而當錯誤個數(shù)大于 t39。 時，譯碼器不進行糾錯而僅指出發(fā)生了錯誤。 ?????? ?? 2 1dt?????? ?? 2 1dt 線 性 分 組 碼 的 譯 碼 第 72頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (3) 標準陣列 ④ 標準陣列的特性 ? 從多維矢量空間的角度看完備碼 ? 假定圍繞每一個碼字 Ci 放置一個半徑為 t 的球，每個球內(nèi)包含了與該碼字漢明距離小于等于 t 的所有接收碼字 R 的集合； ? 在半徑為 的球內(nèi)的接收碼字數(shù)是： ? 因為有 2k 個可能發(fā)送的碼字，也就有 2k 個不相重疊的半徑為 t 的球。包含在 2k 個球中的碼字總數(shù)不會超過 2n 個可能的接收碼字。 ?? ????????ti in0?????? ??21dt 線 性 分 組 碼 的 譯 碼 第 73頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (3) 標準陣列 ④ 標準陣列的特性 ? 從多維矢量空間的角度看完備碼 ? 于是一個糾 t 個差錯的碼必然滿足不等式： ? 如果上式中等號成立，表示所有的接收碼字都落在 2k 個球內(nèi)，而球外沒有一個碼， 這就是完備碼。 ??????????????????????? tikntinkinin00222 ：即 線 性 分 組 碼 的 譯 碼 第 74頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (3) 標準陣列 ④ 標準陣列的特性 ? 從多維矢量空間的角度看完備碼 ? 完備碼特性： 圍繞 2k 個碼字，漢明距離為 t=INT[(dmin－ 1)/2] 的所有球都是不相交的，每一個接收碼字都落在這些球中之一，因此接收碼與發(fā)送碼的距離至多為 t，這時所有重量 ≤t 的錯誤圖樣都能用最佳（最小距離）譯碼器得到糾正，而所有重量 ≥t+1 的錯誤圖樣都不能糾正。 tdm i n圖 8 . 6 . 2 以 碼 字 為 中 心 、 半 徑 t = I N T[ ( dm i n－ 1 ) / 2 ] 的 差 錯 控 制 球 體 示 意 圖dm i nttt 線 性 分 組 碼 的 譯 碼 第 75頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (3) 標準陣列 ④ 標準陣列的特性 ? 從多維矢量空間的角度看完備碼 ? 舉例： 對糾一個錯誤的 (7,4) 漢明碼： (7,4) 漢明碼是一個完備碼。 ? 所有漢明碼都是完備碼： （滿足 2n－ k = 2r=n+1）。 ????????????????????? ??112,811,82nn knkn 所以： 線 性 分 組 碼 的 譯 碼 第 76頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (3) 標準陣列 ④ 標準陣列的特性 ? 標準陣列譯碼 = 最小距離譯碼 = 最佳譯碼 ? 陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，應選取出現(xiàn)概率最大的錯誤圖樣作陪集首； ? 重量較輕的錯誤圖樣出現(xiàn)概率較大，所以在構造標準陣列時是選取重量最輕的 n 重作陪集首； ? 當錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收矢量與原發(fā)送碼字間的距離（等于陪集首）最小； ? 因此，選擇重量最輕的元素作陪集首，按標準陣列譯碼就是按最小距離譯碼； ? 所以標準陣列譯碼法也是最佳譯碼法。 線 性 分 組 碼 的 譯 碼 第 77頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (3) 標準陣列 ④ 標準陣列的特性 ? 定理 ： 在標準陣列中，一個陪集的所有 2k 個 n 重有相同的伴隨式，不同的陪集伴隨式互不相同。 [證明 ]： ? 設 H 為給定 (n,k) 線性碼的監(jiān)督矩陣，在陪集首為 El 的陪集中的任意矢量為： R=El+Ci, i=1,2,…,2 k ? 其伴隨式為： S=RH T=(El+Ci)H T=ElH T+CiH T =ElH T ? 上式表明： 陪集中任意矢量的伴隨式等于陪集首的伴隨式。 即 同一陪集中所有伴隨式相同。 ? 不同陪集中，由于陪集首不同所以伴隨式不同。 返回目錄 線 性 分 組 碼 的 譯 碼 第 78頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 糾錯譯碼 (4) 舉例 ： (6,3)碼的標準陣列 表 8 . ( 6,3) 碼的標準陣列 碼字 000000 （ 陪集首 ） 1001 10 01001 1 001 1 1 1 1 10101 101001 01 1 100 1 1 1010 100000 0001 10 1