[理學]信息論與編碼原理_第8章_線性分組碼(編輯修改稿)

　

【文章內容簡介】 jidd ?CC第 32頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (1) 漢明距離、漢明重量和漢明球 ?漢明球 ： 以碼字 C 為中心，半徑為 t 的漢明球是與 C 的漢明距離 ≤t 的向量全體 SC(t) ： ?任意兩個漢明球不相交最大程度取決于任意兩個碼字之間的最小漢明距離 dmin。 線性分組碼的最小距離、檢錯和糾錯能力 ? ?tdt ?? ),()( RCRS C第 33頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (1) 漢明距離、漢明重量和漢明球 ?漢明球 ： 線性分組碼的最小距離、檢錯和糾錯能力 tV Udm i n圖 8 . 5 . 1 dm i n= 5 , 碼 距 和 糾 錯 能 力 關 系 示 意 圖返回 第 34頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (1) 漢明距離、漢明重量和漢明球 ?漢明重量 （碼字重量） W： 碼字中非 0 碼元符號的個數，稱為該碼字的漢明重量。 ?在二元線性碼中，碼字重量就是碼字中含“ 1”的個數。 ?最小重量 Wmin ： 線性分組碼 CI 中，非 0 碼字重量最小值，叫做碼 CI 的最小重量： Wmin =min{W(V),V∈ CI ,V≠0} 線性分組碼的最小距離、檢錯和糾錯能力 第 35頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (1) 漢明距離、漢明重量和漢明球 ? 最小距離 與最小重量 的關系 ： 線性分組碼的最小距離等于它的最小重量。 [證明 ]： ? 設線性碼 CI，且 U∈ CI, V∈ CI ? 又設 U－ V=Z ? 由線性碼的封閉性知， Z∈ CI ? 因此， d(U,V)=W(Z) ? 由此可推知，線性分組碼的最小距離必等于非 0 碼字的最小重量。 線性分組碼的最小距離、檢錯和糾錯能力 返回目錄 第 36頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯能力 ?檢錯能力 ： 如果一個線性碼能檢出長度 ≤l 個碼元的任何錯誤圖樣，稱碼的 檢錯能力為 l。 ?糾錯能力 ： 如果線性碼能糾正長度 ≤t 個碼元的任意錯誤圖樣，稱碼的 糾錯能力為 t。 ?最小距離與檢糾錯能力的關系 ： 線性碼的最小距離越大，意味著任意碼字間的差別越大，則碼的檢、糾錯能力越強。 線性分組碼的最小距離、檢錯和糾錯能力 第 37頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯能力 ? 最小距離與糾錯能力 ： (n,k) 線性碼能糾 t 個錯誤的充要條件是碼的最小距離為： dmin≥2t+1 () [證明 ]： ? 設發送的碼字為 V；接收的碼字為 R； U 為任意其它碼字 ? 則矢量 V、 R、 U 間滿足距離的三角不等式： d(R,V)+d(R,U)≥d(U,V) () ? 設信道干擾使碼字中碼元發生錯誤的實際個數為 t39。 ，且 t39。 ≤t d(R,V)＝ t39。 ≤t () 線性分組碼的最小距離、檢錯和糾錯能力 第 38頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯能力 ? 最小距離與糾錯能力： (n,k) 線性碼能糾 t 個錯誤的充要條件是碼的最小距離為： dmin≥2t+1 () [證明 ]： ? 由于 d(U,V)≥dmin=2t+1，代入式 () ? 得： d(R,U)≥ d(U,V)－ d(R,V)= 2t+1－ t39。 t () 含義 ： 如果接收字 R 中錯誤個數 t39。 ≤t，接收字 R 和發送字 V 間距離 ≤t ，而與其它任何碼字間距離都大于 t，按最小距離譯碼把 R 譯為 V。此時譯碼正確，碼字中的錯誤被糾正。 ? 幾何意義 ： 線性分組碼的最小距離、檢錯和糾錯能力 參見圖示 第 39頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯能力 ? 最小距離與檢錯能力 ： (n,k) 線性碼能夠發現 l 個錯誤的充要條件是碼的最小距離為： dmin≥l+1 () [證明 ]： ? 設發送的碼字為 V；接收的碼字為 R； U 為任意其它碼字 ? 則矢量 V、 R、 U 間滿足距離的三角不等式： d(R,V)+d(R,U)≥d(U,V) () ? 設信道干擾使碼字中碼元發生錯誤的實際個數為 l39。 ，且 l39。 ≤l d(R,V)＝ l39。 ≤l () 線性分組碼的最小距離、檢錯和糾錯能力 第 40頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯能力 ? 最小距離與檢錯能力 ： (n,k) 線性碼能夠發現 l 個錯誤的充要條件是碼的最小距離為： dmin≥l+1 () [證明 ]： ? 由于 d(U,V)≥dmin=l+1，代入式 () ? 得： d(R,U)≥ d(U,V)－ d(R,V)=l+1－ l39。 0 () 含義 ： 由于接收字 R 與其它任何碼字 U 的距離都大于 0，說明接收字 R 不會因發生 l39。 個錯誤變為其它碼字，因而必能發現錯誤。 線性分組碼的最小距離、檢錯和糾錯能力 第 41頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯能力 ?最小距離與檢錯能力 ： 幾何意義 ： 線性分組碼的最小距離、檢錯和糾錯能力 lV Udm i n圖 8 . 5 . 2 dm i n= 4 , 碼 距 和 檢 錯 能 力 關 系 示 意 圖第 42頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯能力 ? 最小距離與檢、糾錯能力 ： (n,k) 線性碼能糾 t 個錯誤，并能發現 l 個錯誤 (lt) 的充要條件是碼的最小距離為： Dmin ≥ t+l+1 () [證明 ]： ? 因為 dmin2t+1，根據 最小距離與糾錯能力 定理，該碼可糾 t 個錯誤。 ? 因為 dminl+1，根據 最小距離與檢錯能力 定理 , 該碼有檢 l 個錯誤的能力。 ? 糾錯和檢錯不會發生混淆 ： 設發送碼字為 V，接收字為 R，實際錯誤數為 l39。 ，且 t l39。 ≤l。 這時 R 與 其它任何碼字 U 的距離： d(R,U)≥d(U,V)－ d(R,V)=t+l+1－ l39。 ≥t+1t () ∴ 不會把 R 誤糾為 U。 線性分組碼的最小距離、檢錯和糾錯能力 第 43頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯能力 ?最小距離與檢、糾錯能力： 幾何意義： 線性分組碼的最小距離、檢錯和糾錯能力 ldm i n圖 8 . 5 . 3 dm i n= 5 , t = 1 , l = 3 時 碼 距 和 檢 錯 能 力 關 系 示 意 圖tVU第 44頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯能力 線性分組碼的最小距離、檢錯和糾錯能力 dm i nldm i ntdm i nt l圖 8 . 5 . 4 最 小 碼 距 與 檢 糾 錯 能 力? 當 (n,k) 線性碼的最小距離 dmin 給定后，可按實際需要靈活安排糾錯的數目。 ? 例如 ： 對 dmin=8 的碼，可用來糾 3 檢 4 錯，或糾 2檢 5 錯，或糾 1 檢 6錯，或者只用于檢 7 個錯誤。 返回目錄 第 45頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng (3) 線性碼的最小距離與監督矩陣的關系 ?定理 ： 設 H 為 (n,k) 線性碼的一致監督矩陣，若 H 中任意 S 列線性無關，而 H 中存在 (S+1) 列線性相關，則碼的最小距離為 (S+1)。 ?定理 ： 若碼的最小距離為 (S+1)，則該碼的監督矩陣的任意 S 列線性無關，而必存在有相關的 (S+1)列。 ?定理 ： 在二元線性碼的監督矩陣 H 中，如果任一列都不是全“ 0”，且任兩列都不相等，則該碼能糾一個錯誤。（ S=2， dmin=3） 線性分組碼的最小距離、檢錯和糾錯能力 第 46頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 線性分組碼的譯碼 伴隨式和錯誤檢測 糾錯譯碼 第 47頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 伴隨式和錯誤檢測 (1) 如何譯碼？ (2) 伴隨式 (3) 伴隨式的計算 (4) 伴隨式的特性 (5) 舉例 (6) 伴隨式計算電路 線 性 分 組 碼 的 譯 碼 第 48頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 伴隨式和錯誤檢測 (1) 如何譯碼？ 用監督矩陣編碼，也 用監督矩陣譯碼： 接收到一個字 R 后，校驗 H?R T=0T 是否成立： ?若關系成立，則認為 R 是一個碼字； ?否則判為碼字在傳輸中發生了錯誤； ? H?R T 的值是否為 0 是校驗碼字出錯與否的依據。 (2) 伴隨式 /監督子 /校驗子： S=R?H T 或 S T=H?R T 返回目錄 線 性 分 組 碼 的 譯 碼 第 49頁 2022/3/13 Department of Electronics and Information, NCUT Song Peng 伴隨式和錯誤檢測 (3) 伴隨式的計算 ? 發送碼字： C=(－ 1,－ 2,…, c0) ? 信道錯誤圖樣： E=(en－ 1,en－ 2,…, e0) ? ei=0，表示第 i 位無錯； ? ei=1，表示第 i 位有錯。 i=n－ 1,n－ 2,…,0 ? 接收字： R=(rn－ 1,rn－ 2,…, r0)=C+E=(－ 1+en－ 1,－ 2+en－ 2,…, c0 +e0) ? 求接收字的伴隨式（接收字用監督矩陣進行檢驗） S T=H?R T=H?(C+E )T=H?C T+H?E T () ? H?C T=0T，所以 S T=H?E T ? 設 H=(h1,h2,…, hn)，（ hi 表示 H 的列）。代入式 ()得： S T=h1 en－ 1