讯息在低4位元.PPT

* 線性區塊碼種類 線性區塊碼包含有下列常見的碼： 漢明碼(Hamming codes) 循環碼(Cyclic codes) 平方剩餘碼(Quadratic Residue codes) BCH碼(BCH codes) 里德所羅門碼(Reed-Solomon codes) 低密度同位檢查碼 (LDPC codes) * 線性區塊碼家族關係 Linear block codes Cyclic codes LDPC codes BCH codes Hamming codes Reed Solomon codes QR codes * 漢明碼 Richard Hamming在1950年提出漢明碼，它是設計來更正1位元錯誤，及偵測2位元錯誤，它也是線性區塊碼家族的一員。 若 m ? 3，漢明碼有下列的特性 : 長度：n = 2m – 1 訊息位元長度：k = 2m– m – 1 查核位元或冗餘長度：n – k = m 錯誤更正能力：t = 1, (dmin = 3) * 漢明碼的參數 例如若 m = 3，則稱為(7, 4, 3)漢明碼: 長度：n = 2m – 1 = 7 訊息位元長度：k = 2m– m – 1 = 4 查核位元或冗餘長度：n – k = m = 3 錯誤更正能力：t = 1, (dmin = 3) * 線性區塊的編碼 編碼： 生成多項式 (Generator polynomial)與生成矩陣(Generator matrix)： (1) (2) = * Systematic and Non-systematic 利用矩陣的行列運算，(1)式可改寫成如下： (3) Non-systematic：由(2)式編碼所得到的碼稱為Non-systematic碼 Systematic：由(3)式編碼所得到的碼稱為Systematic ，若無特別說明，我們都以 Systematic碼代表。 * 漢明碼的生成矩陣 生成多項式： 由(2)式得到Non-systematic 生成矩陣： 經行列運算後得到(2)式Systematic 生成矩陣： * 漢明碼的編碼 c=mG = (c6,c5,c4,c3,c2,c1,c0)，where (c3,c2,c1,c0) = (m3,m2,m1,m0)，訊息在低4位元，(c6,c5,c4) is parity check bits。 漢明碼的碼字共有16個，如下表所示： * 漢明碼的16個碼字 m c=mG m c=mG 0000 0000000 1000 1101000 0001 1010001 1001 0111001 0010 1110010 1010 0011010 0011 0100011 1011 1001011 0100 0110100 1100 1011100 0101 1100101 1101 0001101 0110 1000110 1110 0101110 0111 0010111 1111 1111111 * 線性區塊的解碼 解碼： Parity check polynomial同位檢查多項式與同位檢查矩陣(Parity check matrix) ： (4) Let r = n – k + 1, (5) * 同位檢查矩陣 Parity check polynomial同位檢查多項式與同位檢查矩陣(Parity check matrix) ： (4) Let r = n – k + 1, (5) * H的轉置矩陣HT 利用行列運算，(5)式可改寫成Systematic form：