信息與編碼課件...ppt

第二部分編碼理論 第七章線性碼 第七章線性碼 7 1生成和一致校驗(yàn)矩陣7 2q進(jìn)制對稱信道上的伴隨式譯碼7 3漢明幾何和碼的性能7 4漢明碼7 5一般q進(jìn)制對稱信道上的伴隨式譯碼7 6重量牧舉多項(xiàng)式和MacWilliams恒等式 7 1生成和一致校驗(yàn)矩陣 定義 Fq上的一個(gè) n k 線性碼 是n維矢量空間Vn Fq x1 x2 xn xi Fq 的一個(gè)k維子空間 n稱為碼的長度 k稱為為數(shù) 碼的速率為k n 7 1生成和一致校驗(yàn)矩陣 n k 線性分組碼是把信息流分割成一串前后獨(dú)立的kbit信息組 再將每組信息元映射成由n個(gè)碼元組成的碼字 codeword k信息元組可以寫成矢量u u1 u2 uk 或矩陣 u1 u2 uk 的形式 碼字C可寫成c c1 cn 1 線性分組碼碼空間C是由k個(gè)線性無關(guān)的基底g1 gk張成的k維n重子空間 碼空間的所有碼字都可以寫成k個(gè)基底的線性組合 即C u1g1 ukgk 這里gk是n重矢量 寫成1 n的矩陣形式 gk gk1 gk2 gkn 7 1生成和一致校驗(yàn)矩陣 將這k個(gè)基底碼字排列成一個(gè)k n的矩陣G 則G稱為C的生成矩陣 7 1生成和一致校驗(yàn)矩陣 定義 令C是Fq上的一個(gè) n k 線性碼 一個(gè)行空間等于C的k n階矩陣G稱為C的生成矩陣 相反 如果G是元素取自Fq的一個(gè)矩陣 則它的行空間稱為由G生成的碼 由于k個(gè)基底即G的k個(gè)行矢量線性無關(guān) 矩陣G的秩一定等于k 當(dāng)信息元確定后 碼字僅由G矩陣決定 因此稱這k n矩陣G為該 n k 線性分組碼的生成矩陣 將信息u映射為碼字x的規(guī)則是 x uG 7 1生成和一致校驗(yàn)矩陣 例7 1一個(gè) 5 1 線性碼C1 具有生成矩陣G1 1 1 1 1 1 顯然C1僅含有兩個(gè)碼字00000和11111 速率R 1 5 重復(fù)編碼 例7 2一個(gè) 5 3 線性碼C2 具有生成矩陣 例7 3一個(gè) 7 4 線性碼C3 具有生成矩陣 7 4 含明碼 7 1生成和一致校驗(yàn)矩陣 基底不是惟一的 生成矩陣也就不是惟一的 事實(shí)上 將k個(gè)基底線性組合后產(chǎn)生另一組k個(gè)矢量 只要滿足線性無關(guān)的條件 依然可以作為基底張成一個(gè)碼空間 不同的基底有可能生成同一碼集 但因編碼涉及碼集和映射兩個(gè)因素 碼集一樣而映射方法不同也不能說是同樣的碼 基底的線性組合等效于生成矩陣G的行運(yùn)算 可以產(chǎn)生一組新的基底 7 1生成和一致校驗(yàn)矩陣 性質(zhì) 如果G是C的生成矩陣 則任意與G行等價(jià)的矩陣也是C的生成矩陣 任意生成矩陣等價(jià)于一個(gè)行遞減階梯 RRE 矩陣 任意線性碼都具有唯一的一個(gè)RRE生成矩陣 域F上RRE的矩陣的三個(gè)性質(zhì) a 每行最左邊的非零元素是1 b 每個(gè)包含這樣一個(gè)最左1元素的列中的其他元素都為0 c 如果第i行的最左非零元素出現(xiàn)在第ti列上 則t1 t2 tr 7 1生成和一致校驗(yàn)矩陣 可見G1和G3是RRE形式了 當(dāng)G2不是 G2的唯一RRE生成矩陣為 7 1生成和一致校驗(yàn)矩陣 定義 存在一個(gè)編碼規(guī)則 使信息符號獨(dú)立地出現(xiàn)在碼字中 就稱為它是系統(tǒng)的 反之 不具備 系統(tǒng) 特性的碼叫非系統(tǒng)碼 非系統(tǒng)碼與系統(tǒng)碼并無本質(zhì)的區(qū)別 它的生成矩陣可以通過行運(yùn)算轉(zhuǎn)變?yōu)橄到y(tǒng)形式 這個(gè)過程叫系統(tǒng)化 系統(tǒng)化不改變碼集 只改變映射規(guī)則 所有的線性碼都是系統(tǒng)的 對于無記憶信道 對G進(jìn)行列置換并不會改變碼的性能 因此在這種情況下總可以假設(shè)G IkA 7 1生成和一致校驗(yàn)矩陣 與任何一個(gè) n k 分組線性碼的碼空間C相對應(yīng) 一定存在一個(gè)對偶空間D 事實(shí)上 碼空間基底數(shù)k只是n維n重空間全部n個(gè)基底的一部分 若能找出另外n k個(gè)基底 也就找到了對偶空間D 既然用k個(gè)基底能產(chǎn)生一個(gè) n k 分組線性碼 那么也就能用n k個(gè)基底產(chǎn)生包含2n k個(gè)碼字的 n n k 分組線性碼 稱 n n k 碼是 n k 碼的對偶碼 將D空間的n k個(gè)基底排列起來可構(gòu)成一個(gè) n k n矩陣 將這個(gè)矩陣稱為碼空間C的校驗(yàn)矩陣H 而它正是 n n k 對偶碼的生成矩陣 它的每一行是對偶碼的一個(gè)碼字 C和D的對偶是相互的 G是C的生成矩陣又是D的校驗(yàn)矩陣 而H是D的生成矩陣 又是C的校驗(yàn)矩陣 7 1生成和一致校驗(yàn)矩陣 由于C的基底和D的基底正交 空間C和空間D也正交 它們互為零空間 因此 n k 線性碼的任意碼字x一定正交于其對偶碼的任意一個(gè)碼字 也必定正交于校驗(yàn)矩陣H的任意一個(gè)行矢量 即xHT 0或HxT 0該式可以用來檢驗(yàn)一個(gè)n重矢量是否為碼字 若等式成立 得零矢量 該n重必為碼字 否則不是碼字 由于生成矩陣的每個(gè)行矢量都是一個(gè)碼字 因此必有GHT 0對于G IkA 必然有H ATIn k 7 1生成和一致校驗(yàn)矩陣 如果G不具有這種形式 則可以通過列置換為 IkA 形式 然后再對 ATIn k 進(jìn)行逆置換而得到H 例如有G1 G2和G3生成的一致校驗(yàn)矩陣是 7 1生成和一致校驗(yàn)矩陣 定理7 1 令C是Fq上的一個(gè) n k 線性碼 則存在唯一的一個(gè)k n階RRE矩陣G 滿足x C 當(dāng)且僅當(dāng)x在G的行空間內(nèi) 另外 存在一個(gè) n k n階矩陣H 滿足x C當(dāng)且僅當(dāng)HxT 0 如果碼C被用于一個(gè)無記憶信道 則不失一般性 可以假設(shè)存在一個(gè)k n k 階矩陣A 使得 G IkA H ATIn k 在這種情況下 矢量u Vk Fq 的編碼由u u uA 給出 7 2q進(jìn)制對稱信道上的伴隨式譯碼 假定信道輸出符號集AY Fq 即輸入與輸出符號集相同 因此如果傳輸?shù)氖莤 x1 x2 xn Vn Fq 則接收矢量y y1 y2 yn 也屬于Vn Fq 兩者的差值z y x稱為錯(cuò)誤圖案 如果zi 0 我們就稱在第i個(gè)位置上出現(xiàn)了一個(gè)錯(cuò)誤 錯(cuò)誤圖案 7 2q進(jìn)制對稱信道上的伴隨式譯碼 伴隨式 如果傳輸?shù)氖莤 輸出的是y 引進(jìn)矢量s HyT 稱為y的伴隨式 伴隨式最重要的特性是 它只依賴于錯(cuò)誤圖案z而不依賴于所傳輸?shù)拇a字 即s HyT H x z T HzT由于y是已知的 則只要知道了z 就能求得x 伴隨式提供了z的一些信息 但不夠充分 因?yàn)閷τ谝粋€(gè)固定的s 方程HzT s的解的集合形成了碼C的一個(gè)陪集 即一個(gè)具有如下形式的Vn Fq 的子集 C z0 x z0 x C 7 2q進(jìn)制對稱信道上的伴隨式譯碼 對應(yīng)于qn k個(gè)伴隨式s 碼C一共有qn k個(gè)陪集 每個(gè)陪集包含qk個(gè)元素 因此一旦接收方計(jì)算出s 就可以將z的搜尋范圍從qn種可能降低到qk種可能 即搜尋范圍是與s相對應(yīng)的陪集元素 7 2q進(jìn)制對稱信道上的伴隨式譯碼 假設(shè)信道是q進(jìn)制對稱信道 qSC 即如果X是表示信道輸入的隨機(jī)矢量 Y是表示信道輸出的隨機(jī)矢量 則Y X Z Z是一個(gè)隨機(jī)矢量 它的分量是獨(dú)立 同分布的隨機(jī)變量 具有相同的分布 P Z 0 1 q 1 P Z z且z 0 對于這個(gè)信道 z Vn Fq 則P Z z 1 q 1 n WH Z WH Z wH Z 為z的漢明重量 被定義為z中非零分量的個(gè)數(shù) 即出現(xiàn)錯(cuò)誤的個(gè)數(shù) 7 2q進(jìn)制對稱信道上的伴隨式譯碼 如果 1 q 則上式就是wH Z 的遞減函數(shù) 因此最有可能的z是具有最小重量的z 所以q進(jìn)制對稱信道上的伴隨式譯碼算法如下 1 計(jì)算伴隨式s HyT2 在對應(yīng)于s的陪集中找出最小重量矢量 稱為z0 3 輸出碼字x y z0 7 2q進(jìn)制對稱信道上的伴隨式譯碼 例考慮碼C2 它的一致校驗(yàn)矩陣是 只有四個(gè)可能的伴隨式 00 01 10 11 7 3漢明幾何和碼的性能 漢明距離 定義兩個(gè)矢量x和y之間的漢明距離為 dH x y 分量xi yi的個(gè)數(shù) wH y x 它滿足真正的測度所具有的下列性質(zhì) a d x x 0 b 如果x y 則d x y 0 c d x y d y x d d x y d x z d z y 7 3漢明幾何和碼的性能 漢明幾何 假設(shè)希望碼C能夠糾正漢明重量 e的錯(cuò)誤圖案 即如果發(fā)送xi 接收到y(tǒng) xi z 如果wH z e 則譯碼器的輸出x xi 對于qSC 譯碼的最佳策略是使dH xi y 最小的那個(gè)碼字 如果采用這種幾何譯碼策略 則碼能夠糾正所有重量 e的錯(cuò)誤圖案的充分必要條件是 每一對碼字之間的距離都 2e 1 7 3漢明幾何和碼的性能 定義 碼C的最小距離為 dmin C min dH x x x x C x x 定理7 2碼C x1 x2 xM 能夠糾正所有重量 e的錯(cuò)誤圖案 當(dāng)且僅當(dāng)dmin C 2e 1 定義 碼C的最小重量wmin C min wH x x C x 0 7 3漢明幾何和碼的性能 如果C是線性碼 則x x 也是C的一個(gè)碼字 因?yàn)閐H x x wH x x 則dmin C wmin C 這樣計(jì)算量從qk qk 1 2減少到qk 定理7 3如果C是Fq上的一個(gè) n k 線性碼 具有一致校驗(yàn)矩陣H 則dmin C H中線性相關(guān)列的最小數(shù)目 因此如果H中任意2t及更少的列所組成的子集都是線性無關(guān)的 則這個(gè)碼能夠糾正所有重量 t的錯(cuò)誤圖案 推論 如果q 2 且H中 e列的所有可能線性組合都不同 則dmin C 2e 1 由此可知C能糾正重量 e的錯(cuò)誤圖案 7 3漢明幾何和碼的性能 例題 H1的任意4列或更少列的子集是不相關(guān)的 但5列相關(guān) 故dmin C1 5 而H2中的第3 4列相關(guān) 故dmin C2 2 因H3中的列不為零也不相同 故dmin C3 3 但H3中的第1 2 3相關(guān) 故dmin C3 3 7 4漢明碼 定義令H是一個(gè)m 2m 1 階二進(jìn)制矩陣 H的列是Vm F2 中以某種順序排列的2m 1個(gè)非零矢量 則在F2上 一致校驗(yàn)矩陣為H的線性碼被稱碼長為2m 1的漢明碼 7 4漢明碼 完備碼 n k 線性分組碼的n個(gè)碼元中 無一差錯(cuò)的圖案有Cn0個(gè) t個(gè)差錯(cuò)的圖案有Cnt個(gè) 另一方面 n k 分組碼有2n k個(gè)伴隨式 假如該碼的糾錯(cuò)能力是t 則對于任何一個(gè)重量小于等于t的差錯(cuò)圖案 都應(yīng)有一個(gè)伴隨式與之對應(yīng) 即伴隨式的數(shù)目應(yīng)滿足條件 2n k Cn0 Cnt如果能使等式成立的 n k 線性分組碼 稱為完備碼 7 4漢明碼 完備碼特性 圍繞2k個(gè)碼字 漢明距d dmin 1 2 的所有球都是不相交的 每一個(gè)接收碼字都落在這些球中之一 因此接收碼離發(fā)送碼的距離至多為t 這時(shí)所有重量 t的差錯(cuò)圖案都能用最佳 最小距離 譯碼器得到糾正 迄今發(fā)現(xiàn)的完備碼有t 1的漢明碼 t 3的高萊碼 以及長度n為奇數(shù) 由兩個(gè)碼字組成 滿足dmin n的任何二進(jìn)制碼 還有三進(jìn)制t 3的 11 6 碼 7 4漢明碼 漢明碼特性 1 H中的列是2m 1個(gè)二進(jìn)制數(shù)字的一個(gè)排列 定義 2 漢明碼是糾錯(cuò)能力t 1的線性碼 3 漢明碼是完備碼 4 漢明碼非常容易實(shí)現(xiàn)伴隨式譯碼 7 4漢明碼 漢明碼譯碼 1 計(jì)算伴隨式s HyT 2 如果s 0 輸出x y 3 否則s等于H的i列 則錯(cuò)誤圖案z在第i位上為1 其它位為0 輸出x y z 7 5一般q進(jìn)制信道上的伴隨式譯碼 對于qSC 噪聲樣本概率分布為 P Z 0 1 q 1 P Z z且z 0 對于一般q進(jìn)制信道上噪聲樣本概率分布為 P Z z p z 這樣伴隨式譯碼方式如下 1 計(jì)算伴隨式s HyT 2 在對應(yīng)于s的陪集中 尋找最大的P z 的矢量 稱之為z0 3 輸出碼字x y z0 7 5一般q進(jìn)制信道上的伴隨式譯碼 這種譯碼方式存在兩個(gè)難點(diǎn) 1 步驟2很難實(shí)現(xiàn) 2 實(shí)際很難獲取p z 只能通過經(jīng)驗(yàn)獲取 即估計(jì) 令F為Vn Fq 的一個(gè)子集 將F看作信道上具有 中等 以上發(fā)生的概率的錯(cuò)誤圖案的集合 E為F的一個(gè)子集 將E看作是具有 高 發(fā)生概率的錯(cuò)誤圖案的集合 給定一個(gè)線性碼C 希望設(shè)計(jì)一個(gè)譯碼器 它能夠檢測到F中的錯(cuò)誤圖案 并能糾正E中的錯(cuò)誤圖案 7 5一般q進(jìn)制信道上的伴隨式譯碼 這意味著 允許譯碼器輸出一個(gè)碼字x 或一個(gè)特殊的刪除符號 假設(shè)發(fā)送的是x 接收的是y x z 則有三種可能 a 譯碼器輸出x x 錯(cuò)誤圖案被糾正了 b 譯碼器輸出x x 產(chǎn)生一個(gè)錯(cuò)誤 c 譯碼器輸出 檢測到一個(gè)錯(cuò)誤 7 5一般q進(jìn)制信道上的伴隨式譯碼 定義如果可以設(shè)計(jì)碼C的譯碼器 它能夠糾正E中的錯(cuò)誤圖案z 并能夠糾正或檢測F中的錯(cuò)誤圖案z 則稱碼C為E糾錯(cuò) F檢錯(cuò)碼 定理7 4令C是Fq上的一個(gè) n k 線性碼 具有一致校驗(yàn)矩陣H 并令E F為Vn Fq 的子集 則C為E糾錯(cuò) F檢錯(cuò)碼的充分必要條件是它具有下列性質(zhì) a z1 z2 E z1 z2 則Hz1T Hz1T b z1 E z2 F E 則Hz1T Hz1T 7 5一般q進(jìn)制信道上的伴隨式譯碼 例7 4令C是 7 3 碼 具有 令E z wH z 1 F z wH z 2 則C為E糾錯(cuò) F檢錯(cuò)碼 7 6重量牧舉多項(xiàng)式和MacWilliams恒等式 如果C是一個(gè) n k 線性碼 則它的重量牧舉多項(xiàng)式為A z A0 A1z AnZn其中Ai表示碼C中漢明重量為i的碼字?jǐn)?shù)目 顯然A0 1 A 1 qk 7 6重量牧舉多項(xiàng)式和MacWilliams恒等式 定理7 5令C是一個(gè)二進(jìn)制線性碼 用于輸入符號集Ax 0 1 及輸出符號集為AY的DMC上 并且采用最大似然準(zhǔn)則譯碼 則最終的錯(cuò)誤概率界限為 特別地 對于原始誤比特為 的BSC 例7 6碼C1僅含00000和11111兩個(gè)碼 則A z 1 z5 所以PE 32 1 5 2 7 6重量牧舉多項(xiàng)式和MacWilliams恒等式 定理7 6 MacWilliams恒等式 令A(yù) z 是一個(gè) n k 線性碼C的重量牧舉多項(xiàng)式 并令B z 是其對偶碼C 的重量牧舉多項(xiàng)式 則A z 與B z 的關(guān)系為 7 6重量牧