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

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

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

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

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

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

6、況下，自由距是碼設(shè)計的首選目標它代表了漸近性能大部分分組譯碼算法的譯碼能力也限于自由距普洛特金限（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作為一個子群，它的每一個陪集在碼C的正交空間H中的投影是一個點，而不同的陪集投影不同。每一個陪集有一個最小碼重，作為陪集首，代表最可能的錯誤圖案。這就引出了伴隨式譯碼：s=rHT，將s與最可能的e建一張表，即可通過查表法實現(xiàn)譯碼。18小結(jié)：引入線性碼的好處簡化了分析：距離譜變成