【正文】 ????????????????????????????????????????111011001111000110010001100101110001101TTRHS譯碼器判為有錯(cuò)由于 0S ?T 線 性 分 組 碼 的 譯 碼 第 53頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng 伴隨式和錯(cuò)誤檢測(cè) (5) 舉 例： (7,3) 碼接收矢量 R 的伴隨式計(jì)算 ? 當(dāng)碼元錯(cuò)誤多于 1 個(gè)時(shí)： ? 發(fā)送碼字 C=1010011，接收碼字 R=0011011，伴隨式為： ? 由于 S T 是第一列和第四列之和，不等于 0； ? 但 S T 與 H 陣中任何一列都不相同無(wú)法判定錯(cuò)誤出在哪些位上，只是發(fā)現(xiàn)有錯(cuò)。 返回目錄 線 性 分 組 碼 的 譯 碼 第 51頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng (5) 舉 例： (7,3) 碼接收字 R 的伴隨式計(jì)算 ? 若接收字中沒(méi)有錯(cuò)誤： ? 設(shè)發(fā)送碼字 C=1010011，接收碼字 R＝ 1010011， R 與 C 相同： ? 但接收端譯碼器并不知道就是發(fā)送的碼字 ? 根據(jù)接收字 R 計(jì)算伴隨式： S T= HR T =0T ? 因此，譯碼器判接收字無(wú)錯(cuò) ?????????????1000110010001100101110001101H 伴隨式和錯(cuò)誤檢測(cè) 線 性 分 組 碼 的 譯 碼 第 52頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng (5) 舉 例： (7,3) 碼接收矢量 R 的伴隨式計(jì)算 ? 若接收字中有 1 位錯(cuò)誤： ? 發(fā)送碼字 C=1010011，接收碼字 R=1110011，伴隨式為： ? (7,3) 碼是糾單個(gè)錯(cuò)誤的碼，且 S T 等于 H 的第二列，因此判定接收字 R 的第二位是錯(cuò)的。 ? 不同的錯(cuò)誤圖樣具有不同的伴隨式，它們是一一對(duì)應(yīng)的。 i=n－ 1,n－ 2,…,0 ? 接收字： R=(rn－ 1,rn－ 2,…, r0)=C+E=(－ 1+en－ 1,－ 2+en－ 2,…, c0 +e0) ? 求接收字的伴隨式（接收字用監(jiān)督矩陣進(jìn)行檢驗(yàn)） S T=H?R T=H?(C+E )T=H?C T+H?E T () ? H?C T=0T，所以 S T=H?E T ? 設(shè) H=(h1,h2,…, hn)，（ hi 表示 H 的列）。（ S=2， dmin=3） 線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力 第 46頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng 線性分組碼的譯碼 伴隨式和錯(cuò)誤檢測(cè) 糾錯(cuò)譯碼 第 47頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng 伴隨式和錯(cuò)誤檢測(cè) (1) 如何譯碼？ (2) 伴隨式 (3) 伴隨式的計(jì)算 (4) 伴隨式的特性 (5) 舉例 (6) 伴隨式計(jì)算電路 線 性 分 組 碼 的 譯 碼 第 48頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng 伴隨式和錯(cuò)誤檢測(cè) (1) 如何譯碼？ 用監(jiān)督矩陣編碼，也 用監(jiān)督矩陣譯碼： 接收到一個(gè)字 R 后，校驗(yàn) H?R T=0T 是否成立： ?若關(guān)系成立，則認(rèn)為 R 是一個(gè)碼字； ?否則判為碼字在傳輸中發(fā)生了錯(cuò)誤； ? H?R T 的值是否為 0 是校驗(yàn)碼字出錯(cuò)與否的依據(jù)。 ?定理 ： 若碼的最小距離為 (S+1)，則該碼的監(jiān)督矩陣的任意 S 列線性無(wú)關(guān)，而必存在有相關(guān)的 (S+1)列。 ? 例如 ： 對(duì) dmin=8 的碼，可用來(lái)糾 3 檢 4 錯(cuò)，或糾 2檢 5 錯(cuò)，或糾 1 檢 6錯(cuò)，或者只用于檢 7 個(gè)錯(cuò)誤。 ≥t+1t () ∴ 不會(huì)把 R 誤糾為 U。 ≤l。 ? 糾錯(cuò)和檢錯(cuò)不會(huì)發(fā)生混淆 ： 設(shè)發(fā)送碼字為 V，接收字為 R，實(shí)際錯(cuò)誤數(shù)為 l39。 線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力 第 41頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯(cuò)能力 ?最小距離與檢錯(cuò)能力 ： 幾何意義 ： 線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力 lV Udm i n圖 8 . 5 . 2 dm i n= 4 , 碼 距 和 檢 錯(cuò) 能 力 關(guān) 系 示 意 圖第 42頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯(cuò)能力 ? 最小距離與檢、糾錯(cuò)能力 ： (n,k) 線性碼能糾 t 個(gè)錯(cuò)誤，并能發(fā)現(xiàn) l 個(gè)錯(cuò)誤 (lt) 的充要條件是碼的最小距離為： Dmin ≥ t+l+1 () [證明 ]： ? 因?yàn)?dmin2t+1，根據(jù) 最小距離與糾錯(cuò)能力 定理，該碼可糾 t 個(gè)錯(cuò)誤。 0 () 含義 ： 由于接收字 R 與其它任何碼字 U 的距離都大于 0，說(shuō)明接收字 R 不會(huì)因發(fā)生 l39。 ≤l d(R,V)＝ l39。 ? 幾何意義 ： 線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力 參見(jiàn)圖示 第 39頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯(cuò)能力 ? 最小距離與檢錯(cuò)能力 ： (n,k) 線性碼能夠發(fā)現(xiàn) l 個(gè)錯(cuò)誤的充要條件是碼的最小距離為： dmin≥l+1 () [證明 ]： ? 設(shè)發(fā)送的碼字為 V；接收的碼字為 R； U 為任意其它碼字 ? 則矢量 V、 R、 U 間滿足距離的三角不等式： d(R,V)+d(R,U)≥d(U,V) () ? 設(shè)信道干擾使碼字中碼元發(fā)生錯(cuò)誤的實(shí)際個(gè)數(shù)為 l39。 ≤t，接收字 R 和發(fā)送字 V 間距離 ≤t ，而與其它任何碼字間距離都大于 t，按最小距離譯碼把 R 譯為 V。 ≤t () 線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力 第 38頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯(cuò)能力 ? 最小距離與糾錯(cuò)能力： (n,k) 線性碼能糾 t 個(gè)錯(cuò)誤的充要條件是碼的最小距離為： dmin≥2t+1 () [證明 ]： ? 由于 d(U,V)≥dmin=2t+1，代入式 () ? 得： d(R,U)≥ d(U,V)－ d(R,V)= 2t+1－ t39。 ，且 t39。 ?最小距離與檢糾錯(cuò)能力的關(guān)系 ： 線性碼的最小距離越大，意味著任意碼字間的差別越大，則碼的檢、糾錯(cuò)能力越強(qiáng)。 線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力 返回目錄 第 36頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng (2) 最小距離與檢、糾錯(cuò)能力 ?檢錯(cuò)能力 ： 如果一個(gè)線性碼能檢出長(zhǎng)度 ≤l 個(gè)碼元的任何錯(cuò)誤圖樣，稱(chēng)碼的 檢錯(cuò)能力為 l。 ?最小重量 Wmin ： 線性分組碼 CI 中，非 0 碼字重量最小值，叫做碼 CI 的最小重量： Wmin =min{W(V),V∈ CI ,V≠0} 線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力 第 35頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng (1) 漢明距離、漢明重量和漢明球 ? 最小距離 與最小重量 的關(guān)系 ： 線性分組碼的最小距離等于它的最小重量。 線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力 ? ?tdt ?? ),()( RCRS C第 33頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng (1) 漢明距離、漢明重量和漢明球 ?漢明球 ： 線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力 tV Udm i n圖 8 . 5 . 1 dm i n= 5 , 碼 距 和 糾 錯(cuò) 能 力 關(guān) 系 示 意 圖返回 第 34頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng (1) 漢明距離、漢明重量和漢明球 ?漢明重量 （碼字重量） W： 碼字中非 0 碼元符號(hào)的個(gè)數(shù)，稱(chēng)為該碼字的漢明重量。 碼的最小距離越大，碼的抗干擾能力就越強(qiáng) 。因此，碼字間的距離滿足一般距離公理： 線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力 ?????10)(),(niii vud VU?????????三角不等式③對(duì)稱(chēng)性②非負(fù)性①),(),(),(),(),(0),(WUWVVUUVVUVUdddddd第 31頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng (1) 漢明距離、漢明重量和漢明球 ? 最小距離 dmin： 在 (n,k) 線性碼的碼字 集合中 ，任意兩個(gè)碼字間距離最小值，叫做碼的最小距離。 ? 利用監(jiān)督矩陣構(gòu)造 (7,3) 線性分組碼的編碼電路 ? 設(shè)碼字為： C=(c6c5c4c3c2c1c0) ? 碼的監(jiān)督矩陣為： 線性分組碼的編碼 第 28頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng ? 利用監(jiān)督矩陣構(gòu)造 (7,3) 線性分組碼的編碼電路： ? 根據(jù)上面方程組可直接畫(huà)出 (7,3) 碼的并行編碼電路和串行編碼電路 : 線性分組碼的編碼 m0m1m2c6c5c4c3c2c1c0mC( a ) 并 行 編 碼 電 路 （ b ） 串 行 編 碼 電 路 圖 8 . 4 . 1 ( 7 , 3 ) 線 性 系 統(tǒng) 編 碼 電 路 返回目錄 第 29頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng 線性分組碼的最小距離、檢錯(cuò)和糾錯(cuò)能力 (1) 漢明距離、漢明重量和漢明球 (2) 最小距離與檢、糾錯(cuò)能力 (3) 線性碼的最小距離與監(jiān)督矩陣的關(guān)系 第 30頁(yè) 2022/3/13 Department of Electronics and Information, NCUT Song Peng (1) 漢明距離、漢明重量和漢明球 ? 漢明距離 （距離）：在 (n,k) 線性碼中，兩個(gè)碼字 U、 V 之間對(duì)應(yīng)碼元位上符號(hào)取值不同的個(gè)數(shù)，稱(chēng)為碼字 U、 V 之間的漢明距離。 線性分組碼的生成矩陣 ?