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

《信息論與編碼-第6章-第17、18講-信道編碼-線性分組碼.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《信息論與編碼-第6章-第17、18講-信道編碼-線性分組碼.ppt（49頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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