信息論與編碼-第6章-第17、18講-信道編碼-線性分組碼.ppt

2020 1 22 1 6 1一般概念6 2一致監(jiān)督方程和一致監(jiān)督矩陣6 3線性分組碼的生成矩陣6 4線性分組碼的編碼6 5線性分組碼的最小距離 檢錯和糾錯能力6 6線性分組碼的譯碼6 7線性分組碼的性能6 8漢明碼 6線性分組碼 2020 1 22 2 線性分組碼的編碼 線性分組碼的編碼過程分為兩步 把信息序列按一定長度分成若干信息碼組 每組由k位組成 編碼器按照預(yù)定的線性規(guī)則 可由線性方程組規(guī)定 把信息碼組變換成n重 n k 碼字 其中 n k 個附加碼元是由信息碼元的線性運算產(chǎn)生的 信息碼組長k位 有2k個不同的信息碼組 則有2k個碼字與它們一一對應(yīng) 6 1一般概念 2020 1 22 3 名詞解釋線性分組碼 通過預(yù)定的線性運算將長為k位的信息碼組變換成n重的碼字 n k 由2k個信息碼組所編成的2k個碼字集合 稱為線性分組碼 碼矢 一個n重的碼字可以用矢量來表示C Cn 1 Cn 2 C1 C0 所以碼字又稱為碼矢 n k 線性碼 信息位長為k 碼長為n的線性碼 編碼效率 編碼速率 碼率 傳信率 R k n 它說明了信道的利用效率 R是衡量碼性能的一個重要參數(shù) 6 1一般概念 2020 1 22 4 1 一致監(jiān)督方程編碼就是給已知信息碼組按預(yù)定規(guī)則添加監(jiān)督碼元 以構(gòu)成碼字 在k個信息碼元之后附加r r n k 個監(jiān)督碼元 使每個監(jiān)督元是其中某些信息元的模2和 舉例 k 3 r 4 構(gòu)成 7 3 線性分組碼 設(shè)碼字為 C6 C5 C4 C3 C2 C1 C0 C6 C5 C4為信息元 C3 C2 C1 C0為監(jiān)督元 每個碼元取 0 或 1 監(jiān)督元可按下面方程組計算 6 2一致監(jiān)督方程和一致監(jiān)督矩陣 2020 1 22 5 一致監(jiān)督方程 一致校驗方程 確定由信息元得到監(jiān)督元規(guī)則的一組方程稱為監(jiān)督方程 校驗方程 由于所有碼字都按同一規(guī)則確定 又稱為一致監(jiān)督方程 一致校驗方程 由于一致監(jiān)督方程是線性的 即監(jiān)督元和新信源之間是線性運算關(guān)系 所以由線性監(jiān)督方程所確定的分組碼是線性分組碼 6 2一致監(jiān)督方程和一致監(jiān)督矩陣 2020 1 22 6 2 舉例信息碼組 101 即C6 1 C5 0 C4 1代入 6 2 1 得 C3 0 C2 0 C1 1 C0 1由信息碼組 101 編出的碼字為 1010011 其它7個碼字如表6 2 1 6 2一致監(jiān)督方程和一致監(jiān)督矩陣 2020 1 22 7 3 一致監(jiān)督矩陣為了運算方便 將式 6 2 1 監(jiān)督方程寫成矩陣形式 得式 6 2 2 可寫成H CT 0T或C HT 0CT HT 0T分別表示C H 0的轉(zhuǎn)置矩陣 6 2一致監(jiān)督方程和一致監(jiān)督矩陣 2020 1 22 8 系數(shù)矩陣H的后四列組成一個 4 4 階單位子陣 用I4表示 H的其余部分用P表示 6 2一致監(jiān)督方程和一致監(jiān)督矩陣 2020 1 22 9 推廣到一般情況 對 n k 線性分組碼 每個碼字中的r r n k 個監(jiān)督元與信息元之間的關(guān)系可由下面的線性方程組確定 6 2一致監(jiān)督方m程和一致監(jiān)督矩陣 2020 1 22 10 令上式的系數(shù)矩陣為H 碼字行陣列為C 6 2一致監(jiān)督方程和一致監(jiān)督矩陣 2020 1 22 11 4 一致監(jiān)督矩陣特性對H各行實行初等變換 將后面r列化為單位子陣 于是得到下面矩陣 行變換所得方程組與原方程組同解 監(jiān)督矩陣H的標(biāo)準(zhǔn)形式 后面r列是一單位子陣的監(jiān)督矩陣H H陣的每一行都代表一個監(jiān)督方程 它表示與該行中 1 相對應(yīng)的碼元的模2和為0 6 2一致監(jiān)督方程和一致監(jiān)督矩陣 2020 1 22 12 H的標(biāo)準(zhǔn)形式還說明了相應(yīng)的監(jiān)督元是由哪些信息元決定的 例如 7 3 碼的H陣的第一行為 1011000 說明此碼的第一個監(jiān)督元等于第一個和第三個信息元的模2和 依此類推 H陣的r行代表了r個監(jiān)督方程 也表示由H所確定的碼字有r個監(jiān)督元 為了得到確定的碼 r個監(jiān)督方程 或H陣的r行 必須是線性獨立的 這要求H陣的秩為r 若把H陣化成標(biāo)準(zhǔn)形式 只要檢查單位子陣的秩 就能方便地確定H陣本身的秩 6 2一致監(jiān)督方程和一致監(jiān)督矩陣 2020 1 22 13 1 線性碼的封閉性線性碼的封閉性 線性碼任意兩個碼字之和仍是一個碼字 定理6 2 1 設(shè)二元線性分組碼CI CI表示碼字集合 是由監(jiān)督矩陣H所定義的 若U和V為其中的任意兩個碼字 則U V也是CI中的一個碼字 證明 由于U和V是碼CI中的兩個碼字 故有HUT 0T HVT 0T那么H U V T H UT VT HUT HVT 0T即U V滿足監(jiān)督方程 所以U V一定是一個碼字 6 3線性分組碼的生成矩陣 2020 1 22 14 2 線性分組碼的生成矩陣 n k 線性碼是n維線性空間Vn中的一個k維子空間Vk 在這個k維子空間中 一定存在k個線性獨立的碼字 g1 g2 gk 那么 任何碼字C都可以表示為這k個碼字的一種線性組合 即 6 3線性分組碼的生成矩陣 2020 1 22 15 G中每一行g(shù)i gi1 gi2 gin 都是一個碼字 對每一個信息組m 由矩陣G都可以求得 n k 線性碼對應(yīng)的碼字生成矩陣 由于矩陣G生成了 n k 線性碼 稱矩陣G為 n k 線性碼的生成矩陣 n k 線性碼的每一個碼字都是生成矩陣G的行矢量的線性組合 6 3線性分組碼的生成矩陣 2020 1 22 16 線性系統(tǒng)分組碼通過行初等變換 將G化為前k列是單位子陣的標(biāo)準(zhǔn)形式 6 3線性分組碼的生成矩陣 2020 1 22 17 線性系統(tǒng)分組碼 用標(biāo)準(zhǔn)生成矩陣Gk n編成的碼字 前面k位為信息數(shù)字 后面r n k位為校驗字 這種信息數(shù)字在前校驗數(shù)字在后的線性分組碼稱為線性系統(tǒng)分組碼 當(dāng)生成矩陣G確定之后 n k 線性碼也就完全被確定了 只要找到碼的生成矩陣 編碼問題也同樣被解決了 6 3線性分組碼的生成矩陣 2020 1 22 18 3 舉例 7 4 線性碼的生成矩陣為 6 3線性分組碼的生成矩陣 2020 1 22 19 4 生成矩陣與一致監(jiān)督矩陣的關(guān)系由于生成矩陣G的每一行都是一個碼字 所以G的每行都滿足Hr nCTn 1 0Tr 1 則有Hr nGTn k 0Tr k或Gk nHTn r 0k r線性系統(tǒng)碼的監(jiān)督矩陣H和生成矩陣G之間可以直接互換 6 3線性分組碼的生成矩陣 2020 1 22 20 舉例已知 7 4 線性系統(tǒng)碼的監(jiān)督矩陣為 6 3線性分組碼的生成矩陣 2020 1 22 21 5 對偶碼對偶碼 對一個 n k 線性碼CI 由于Hr nGTn k 0Tr k 如果以G作監(jiān)督矩陣 而以H作生成矩陣 可構(gòu)造另一個碼CId 碼CId是一個 n n k 線性碼 稱碼CId為原碼的對偶碼 例如 7 4 線性碼的對偶碼是 7 3 碼 7 3 碼的監(jiān)督矩陣H 7 3 是 7 4 碼生成矩陣G 7 4 6 3線性分組碼的生成矩陣 2020 1 22 22 7 3 碼的生成矩陣G 7 3 是 7 4 碼監(jiān)督矩陣H 7 4 6 3線性分組碼的生成矩陣 2020 1 22 23 n k 線性碼的編碼就是根據(jù)線性碼的監(jiān)督矩陣或生成矩陣將長為k的信息組變換成長為n n k 的碼字 利用監(jiān)督矩陣構(gòu)造 7 3 線性分組碼的編碼電路 設(shè)碼字矢量為C C6C5C4C3C2C1C0 碼的監(jiān)督矩陣為 6 4線性分組碼的編碼 2020 1 22 24 根據(jù)方程組可直接畫出 7 3 碼的并行編碼電路和串行編碼電路 如圖6 2 2 6 4線性分組碼的編碼 2020 1 22 25 1 漢明距離 漢明重量和漢明球漢明距離 距離 在 n k 線性碼中 兩個碼字U V之間對應(yīng)碼元位上符號取值不同的個數(shù) 稱為碼字U V之間的漢明距離 例如 7 3 碼的兩個碼字U 0011101 V 0100111 它們之間第2 3 4和6位不同 因此 碼字U和V的距離為4 線性分組碼的一個碼字對應(yīng)于n維線性空間中的一點 碼字間的距離即為空間中兩對應(yīng)點的距離 因此 碼字間的距離滿足一般距離公理 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 26 最小距離 dmin 在 n k 線性碼的碼字集合中 任意兩個碼字間距離最小值 叫做碼的最小距離 若C i 和C j 是任意兩個碼字 則碼的最小距離表示為碼的最小距離是衡量碼的抗干擾能力 檢 糾錯能力 的重要參數(shù) 碼的最小距離越大 碼的抗干擾能力就越強 漢明球 以碼字C為中心 半徑為t的漢明球是與C的漢明距離 t的向量全體SC t 任意兩個漢明球不相交最大程度取決于任意兩個碼字之間的最小漢明距離dmin 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 27 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 28 漢明重量 碼字重量 W 碼字中非0碼元符號的個數(shù) 稱為該碼字的漢明重量 在二元線性碼中 碼字重量就是碼字中含 1 的個數(shù) 最小重量 Wmin 線性分組碼CI中 非0碼字重量最小值 叫做碼CI的最小重量 Wmin min W V V CI V 0 最小距離與最小重量的關(guān)系 線性分組碼的最小距離等于它的最小重量 證明 設(shè)線性碼CI 且U CI V CI 又設(shè)U V Z 由線性碼的封閉性知 Z CI 因此 d U V W Z 由此可推知 線性分組碼的最小距離必等于非0碼字的最小重量 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 29 2 最小距離與檢 糾錯能力一般地說 線性碼的最小距離越大 意味著任意碼字間的差別越大 則碼的檢 糾錯能力越強 檢錯能力 如果一個線性碼能檢出長度 l個碼元的任何錯誤圖樣 稱碼的檢錯能力為l 糾錯能力 如果線性碼能糾正長度 t個碼元的任意錯誤圖樣 稱碼的糾錯能力為t 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 30 最小距離與糾錯能力 n k 線性碼能糾t個錯誤的充要條件是碼的最小距離為 證明 設(shè) 發(fā)送的碼字為V 接收的碼字為R U為任意其它碼字 則 矢量V R U間滿足距離的三角不等式 d R V d R U d U V 6 2 16 設(shè) 信道干擾使碼字中碼元發(fā)生錯誤的實際個數(shù)為t 且t td R V t t 6 2 17 由于d U V dmin 2t 1 代入式 6 2 16 得d R U d U V d R V 2t 1 t t 6 2 18 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 31 上式表明 如果接收字R中錯誤個數(shù)t t 那么接收字R和發(fā)送字V間距離 t 而與其它任何碼字間距離都大于t 按最小距離譯碼把R譯為V 此時譯碼正確 碼字中的錯誤被糾正 幾何意義 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 32 最小距離與檢錯能力 n k 線性碼能夠發(fā)現(xiàn)l個錯誤的充要條件是碼的最小距離為dmin l 1或l dmin 1 6 2 19 證明 設(shè) 發(fā)送的碼字為V 接收的碼字為R U為任意其它碼字 則 矢量V R U間滿足距離的三角不等式 d R V d R U d U V 6 2 20 設(shè) 信道干擾使碼字中碼元發(fā)生錯誤的實際個數(shù)為l 且l ld R V l l 6 2 21 由于d U V dmin l 1 代入式 6 2 20 得d R U d U V d R V l 1 l 0 6 2 22 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 33 上式表明 由于接收字R與其它任何碼字U的距離都大于0 則說明接收字R不會因發(fā)生l 個錯誤變?yōu)槠渌a字 因而必能發(fā)現(xiàn)錯誤 幾何意義 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 34 最小距離與檢 糾錯能力 n k 線性碼能糾t個錯誤 并能發(fā)現(xiàn)l個錯誤 l t 的充要條件是碼的最小距離為dmin t l 1或t l dmin 1 6 2 23 證明 因為dmin 2t 1 根據(jù)最小距離與糾錯能力定理 該碼可糾t個錯誤 因為dmin l 1 根據(jù)最小距離與檢錯能力定理 該碼有檢l個錯誤的能力 糾錯和檢錯不會發(fā)生混淆 設(shè)發(fā)送碼字為V 接收字為R 實際錯誤數(shù)為l 且tt 1 t 6 2 24 因而不會把R誤糾為U 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 35 幾何意義 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 36 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 37 當(dāng) n k 線性碼的最小距離dmin給定后 可按實際需要靈活安排糾錯的數(shù)目 例如 對dmin 8的碼 可用來糾3檢4錯 或糾2檢5錯 或糾1檢6錯 或者只用于檢7個錯誤 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 38 3 線性碼的最小距離與監(jiān)督矩陣的關(guān)系定理6 2 2 設(shè)H為 n k 線性碼的一致監(jiān)督矩陣 若H中任意S列線性無關(guān) 而H中存在 S 1 列線性相關(guān) 則碼的最小距離為 S 1 矩陣H的秩為S 定理6 2 3 若碼的最小距離為 S 1 則該碼的監(jiān)督矩陣的任意S列線性無關(guān) 而必存在有相關(guān)的 S 1 列 定理6 2 4 在二元線性碼的監(jiān)督矩陣H中 如果任一列都不是全 0 且任兩列都不相等 則該碼能糾一個錯誤 6 5線性分組碼的最小距離 檢錯和糾錯能力 2020 1 22 39 1 伴隨式和錯誤檢測 用監(jiān)督矩陣編碼 也用監(jiān)督矩陣譯碼 接收到一個接收字R后 校驗H RT 0T是否成立 若關(guān)系成立 則認(rèn)為R是一個碼字 否則判為碼字在傳輸中發(fā)生了錯誤 H RT的值是否為0是校驗碼字出錯與否的依據(jù) 伴隨式 監(jiān)督子 校驗子 S R HT或ST H RT 如何糾錯 設(shè)發(fā)送碼矢C Cn 1 Cn 2 C0 信道錯誤圖樣為E En 1 En 2 E0 其中Ei 0 表示第i位無錯 Ei 1 表示第i位有錯 i n 1 n 2 0 6 6線性分組碼的譯碼 2020 1 22 40 接收字R為R Rn 1 Rn 2 R0 C E Cn 1 En 1 Cn 2 En 2 C0 E0 求接收字的伴隨式 接收字用監(jiān)督矩陣進(jìn)行檢驗 ST H RT H C E T H CT H ET 6 2 25 由于H CT 0T 所以ST H ET設(shè)H h1 h2 hn 其中hi表示H的列 代入式 6 2 25 得到 6 6線性分組碼的譯碼 2020 1 22 41 總結(jié)伴隨式僅與錯誤圖樣有關(guān) 而與發(fā)送的具體碼字無關(guān) 即伴隨式僅由錯誤圖樣決定 伴隨式是錯誤的判別式 若S 0 則判為沒有出錯 接收字是一個碼字 若S 0 則判為有錯 不同的錯誤圖樣具有不同的伴隨式 它們是一一對應(yīng)的 對二元碼 伴隨式是H陣中與錯誤碼元對應(yīng)列之和 6 6線性分組碼的譯碼 2020 1 22 42 舉例 7 3 碼接收矢量R的伴隨式計算設(shè)發(fā)送碼矢C 1010011 接收碼字R 1010011 R與C相同 6 6線性分組碼的譯碼 2020 1 22 43 若接收字中有一位錯誤 6 6線性分組碼的譯碼 2020 1 22 44 當(dāng)碼元錯誤多于1個時 6 6線性分組碼的譯碼 2020 1 22 45 伴隨式計算電路伴隨式的計算可用電路來實現(xiàn) 以 7 3 碼為例 設(shè)接收字為R R6R5R4R3R2R1R0 伴隨式為根據(jù)上式可畫出伴隨式計算電路 如圖6 2 7所示 6 6線性分組碼的譯碼 2020 1 22 46 根據(jù)上式可畫出伴隨式計算電路 如圖6 2 7所示 6 6線性分組碼的譯碼 作業(yè) 補充1 已知 7 4 漢明碼的生成矩陣為 1 求該碼的全部碼字 2 求該碼的監(jiān)督矩陣 3 若接收碼字為1101101 計算伴隨式 2020 1 22 48 補充2 已知 8 4 系統(tǒng)線性碼的監(jiān)督方程為式中m m3 m2 m1 m0 為信息矢量 C3 C2 C1 C0為編碼監(jiān)督數(shù)字 求這個碼的監(jiān)督矩陣和生成矩陣 證明該碼的最小距離為4 作業(yè) 作業(yè) 補充3 設(shè)5元線性碼L的生成矩陣為 1 確定碼L的標(biāo)準(zhǔn)型生成矩陣 2 確定碼L的標(biāo)準(zhǔn)型校驗矩陣 3 求碼L的最小距離