第三講——線性碼與線性分組碼again

1、第三講線性碼與線性分組碼1編碼與譯碼對(duì) 二進(jìn)制(n, k)碼，信息數(shù)量（或合法碼字?jǐn)?shù)）為2k，可用編碼空間的點(diǎn)數(shù)為2n個(gè)。任一種2k信息集合到二進(jìn)制序列集合(2n)的映射都是一種(n, k)碼。因此總共可能的編碼方案有 種。如，共有1029種(100,50)碼。譯碼運(yùn)算量：如果直接用最大似然序列譯碼，對(duì)一般性的編碼而言，正比于n* 2k ，對(duì)(100,50)碼，則為1017。幾乎是不可能譯碼的。2為什么要引入線性碼發(fā)現(xiàn)或構(gòu)造好碼是信道編碼研究的主要問(wèn)題編碼方案太多，以至全局搜索是不可能的現(xiàn)實(shí)的做法是對(duì)編碼方案加以一定的約束，在一個(gè)子集中尋找局部最優(yōu)這種約束即要能包含盡可能好的碼，又要便于分析，

2、便于譯碼目前對(duì)線性系統(tǒng)的研究遠(yuǎn)比非線性系統(tǒng)充分3線性碼的定義碼字集中的元之間的任意線性組合仍是合法碼字，即對(duì)線性組合運(yùn)算封閉的碼字集，稱為線性碼因此，為了構(gòu)成線性空間，必須首先定義運(yùn)算4群定義了一種運(yùn)算的集合群運(yùn)算封閉有恒等元有逆元滿足結(jié)合律交換群滿足交換律的群5環(huán)定義了兩種運(yùn)算的集合按第一種運(yùn)算（不妨稱為加法）構(gòu)成交換群第二種運(yùn)算（不妨稱為乘法）滿足以下條件封閉性結(jié)合律與加法間滿足分配律6域一種特殊的環(huán)乘法有恒等元（稱為1元），且除了加法的恒等元（稱為0元）以外有逆的環(huán)除0元外，對(duì)乘法構(gòu)成交換群無(wú)限域和有限域有理數(shù)、實(shí)數(shù)和復(fù)數(shù)都是無(wú)限域信道編碼中用到的是有限域，GF(q)兩者在空間意義上有很

3、強(qiáng)的可類比性7子群與陪集就給定群G所定義的（加法）運(yùn)算封閉的非空子集H，稱H為G的子群G中任一元g與H相加得到的子集稱為H的陪集舉例陪集不相交陪集首商集整數(shù)群的子群m的所有倍數(shù)剩余類8線性空間、線性碼與線性分組碼利用線性空間中的子空間作為許用碼字的編碼稱線性碼當(dāng)線性空間為有限維空間時(shí)即為線性分組碼GF(q)上的n維線性空間Vn中的一個(gè)k維子空間Vn,k稱為(n,k)線性分組碼9線性分組碼的特點(diǎn)全零序列是許用碼字與任一碼字的距離譜都相同只須考慮重量譜自由距就是最小碼重量平均差錯(cuò)概率就是當(dāng)發(fā)全零序列時(shí)的條件差錯(cuò)概率：Pe=x1P(x1)P(e|x1)= P(e|全零)10碼的球半徑和覆蓋半徑碼空間

4、中以許用碼字為中心半徑相等的互不相交的球，其最大半徑稱為碼的球半徑 s(C)，對(duì)自由距為d的碼，球半徑為s(C) = (d-1)/2可以覆蓋整個(gè)碼空間的以許用碼字為中心半徑相等的球，其最小半徑稱為碼的覆蓋半徑 t(C)，顯然球半徑不大于覆蓋半徑當(dāng)相等時(shí)稱為完備碼，在k和d相不變的碼中n最小當(dāng)給定編碼參數(shù)n和k時(shí)，覆蓋半徑越小碼距就可以越大11線性碼的矢量與矩陣表示(n,k)線性分組碼是GF(q)上的n維線性空間中k個(gè)線性無(wú)關(guān)的向量c1,c2,ck張成的對(duì)碼空間中任一個(gè)碼字C0可表示為將所有矢量寫成行向量的形式：c0=d*G生成矩陣12校驗(yàn)矩陣若C是n維線性空間的一個(gè)k維子空間，則必存在一個(gè)的n

5、-k維子空間H，它與C互為零空間。即CH，或CH=。中任一矢量r是許用碼字的充要條件是校驗(yàn)矩陣13對(duì)偶碼用校驗(yàn)矩陣H中行矢量張成的子空間是一個(gè)(n ,n-k)線性分組碼，它與碼C互為對(duì)偶碼14自由距與校驗(yàn)矩陣校驗(yàn)矩陣的秩為df -1例：糾一個(gè)錯(cuò)的碼設(shè)計(jì)自由距至少為3校驗(yàn)矩陣的秩至少為2，即任兩個(gè)列矢量不同當(dāng)冗余位數(shù)m固定時(shí)，最多的非零列矢量個(gè)數(shù)為2m -1最高效率為(2m-1，2m-1-m，3)碼，稱為漢明碼，是完備碼漢明碼的對(duì)偶碼為2(2m-1，m，2m-1)碼，等價(jià)于m序列，又稱極長(zhǎng)碼，如果用BPSK，并看成2m進(jìn)制調(diào)制時(shí)，是一種自相關(guān)性最好的調(diào)制方式15我們能得到多大的自由距？在大部分情

6、況下，自由距是碼設(shè)計(jì)的首選目標(biāo)它代表了漸近性能大部分分組譯碼算法的譯碼能力也限于自由距普洛特金限（Plotkin）,自由距小于平均距： d nqk-1(q-1)/(qk-1) 或 k/n1-2d/n漢明限，球包限：k/n1-H2(d/2n)沃爾沙莫夫-吉爾伯特（V-G）限，H陣的秩與距離的關(guān)系：k/n1-H2(d/n)其中 H2(x) = -xlog2x (1-x)log2(1-x)16最大的自由距存在區(qū)間17線性分組碼譯碼的基本方法碼C作為一個(gè)子群，它的每一個(gè)陪集在碼C的正交空間H中的投影是一個(gè)點(diǎn)，而不同的陪集投影不同。每一個(gè)陪集有一個(gè)最小碼重，作為陪集首，代表最可能的錯(cuò)誤圖案。這就引出了伴隨式譯碼：s=rHT，將s與最可能的e建一張表，即可通過(guò)查表法實(shí)現(xiàn)譯碼。18小結(jié)：引入線性碼的好處簡(jiǎn)化了分析：距離譜變成