線(xiàn)性碼與線(xiàn)性分組碼

線(xiàn)性碼與線(xiàn)性分組碼第一頁(yè)，共十九頁(yè)，編輯于2023年，星期三編碼與譯碼對(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。幾乎是不可能譯碼的。第二頁(yè)，共十九頁(yè)，編輯于2023年，星期三為什么要引入線(xiàn)性碼發(fā)現(xiàn)或構(gòu)造好碼是信道編碼研究的主要問(wèn)題編碼方案太多，以至全局搜索是不可能的現(xiàn)實(shí)的做法是對(duì)編碼方案加以一定的約束，在一個(gè)子集中尋找局部最優(yōu)這種約束即要能包含盡可能好的碼，又要便于分析，便于譯碼目前對(duì)線(xiàn)性系統(tǒng)的研究遠(yuǎn)比非線(xiàn)性系統(tǒng)充分第三頁(yè)，共十九頁(yè)，編輯于2023年，星期三線(xiàn)性碼的定義碼字集中的元之間的任意線(xiàn)性組合仍是合法碼字，即對(duì)線(xiàn)性組合運(yùn)算封閉的碼字集，稱(chēng)為線(xiàn)性碼因此，為了構(gòu)成線(xiàn)性空間，必須首先定義運(yùn)算第四頁(yè)，共十九頁(yè)，編輯于2023年，星期三群——定義了一種運(yùn)算的集合群運(yùn)算封閉有恒等元有逆元滿(mǎn)足結(jié)合律交換群滿(mǎn)足交換律的群第五頁(yè)，共十九頁(yè)，編輯于2023年，星期三環(huán)——定義了兩種運(yùn)算的集合按第一種運(yùn)算（不妨稱(chēng)為加法）構(gòu)成交換群第二種運(yùn)算（不妨稱(chēng)為乘法）滿(mǎn)足以下條件封閉性結(jié)合律與加法間滿(mǎn)足分配律第六頁(yè)，共十九頁(yè)，編輯于2023年，星期三域——一種特殊的環(huán)乘法有恒等元（稱(chēng)為1元），且除了加法的恒等元（稱(chēng)為0元）以外有逆的環(huán)除0元外，對(duì)乘法構(gòu)成交換群無(wú)限域和有限域有理數(shù)、實(shí)數(shù)和復(fù)數(shù)都是無(wú)限域信道編碼中用到的是有限域，GF(q)兩者在空間意義上有很強(qiáng)的可類(lèi)比性第七頁(yè)，共十九頁(yè)，編輯于2023年，星期三子群與陪集就給定群G所定義的（加法）運(yùn)算封閉的非空子集H，稱(chēng)H為G的子群G中任一元g與H相加得到的子集稱(chēng)為H的陪集舉例陪集不相交陪集首商集整數(shù)群的子群m的所有倍數(shù)剩余類(lèi)第八頁(yè)，共十九頁(yè)，編輯于2023年，星期三線(xiàn)性空間、線(xiàn)性碼與線(xiàn)性分組碼利用線(xiàn)性空間中的子空間作為許用碼字的編碼稱(chēng)線(xiàn)性碼當(dāng)線(xiàn)性空間為有限維空間時(shí)即為線(xiàn)性分組碼GF(q)上的n維線(xiàn)性空間Vn中的一個(gè)k維子空間Vn,k稱(chēng)為(n,k)線(xiàn)性分組碼第九頁(yè)，共十九頁(yè)，編輯于2023年，星期三線(xiàn)性分組碼的特點(diǎn)全零序列是許用碼字與任一碼字的距離譜都相同只須考慮重量譜自由距就是最小碼重量平均差錯(cuò)概率就是當(dāng)發(fā)全零序列時(shí)的條件差錯(cuò)概率：Pe=x1P(x1)P(e|x1)=P(e|全零)第十頁(yè)，共十九頁(yè)，編輯于2023年，星期三碼的球半徑和覆蓋半徑碼空間中以許用碼字為中心半徑相等的互不相交的球，其最大半徑稱(chēng)為碼的球半徑s(C)，對(duì)自由距為d的碼，球半徑為

s(C)=(d-1)/2可以覆蓋整個(gè)碼空間的以許用碼字為中心半徑相等的球，其最小半徑稱(chēng)為碼的覆蓋半徑t(C)，顯然球半徑不大于覆蓋半徑當(dāng)相等時(shí)稱(chēng)為完備碼，在k和d相不變的碼中n最小當(dāng)給定編碼參數(shù)n和k時(shí)，覆蓋半徑越小碼距就可以越大第十一頁(yè)，共十九頁(yè)，編輯于2023年，星期三線(xiàn)性碼的矢量與矩陣表示(n,k)線(xiàn)性分組碼是GF(q)上的n維線(xiàn)性空間中k個(gè)線(xiàn)性無(wú)關(guān)的向量c1,c2,……,ck張成的對(duì)碼空間中任一個(gè)碼字C0可表示為將所有矢量寫(xiě)成行向量的形式：c0=d*G生成矩陣第十二頁(yè)，共十九頁(yè)，編輯于2023年，星期三校驗(yàn)矩陣若C是n維線(xiàn)性空間的一個(gè)k維子空間，則必存在一個(gè)的n-k維子空間H，它與C互為零空間。即CH，或CH=。中任一矢量r是許用碼字的充要條件是校驗(yàn)矩陣第十三頁(yè)，共十九頁(yè)，編輯于2023年，星期三對(duì)偶碼用校驗(yàn)矩陣H中行矢量張成的子空間是一個(gè)(n,n-k)線(xiàn)性分組碼，它與碼C互為對(duì)偶碼第十四頁(yè)，共十九頁(yè)，編輯于2023年，星期三自由距與校驗(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)碼，稱(chēng)為漢明碼，是完備碼漢明碼的對(duì)偶碼為2 (2m-1，m，2m-1)碼，等價(jià)于m序列，又稱(chēng)極長(zhǎng)碼，如果用BPSK，并看成2m進(jìn)制調(diào)制時(shí)，是一種自相關(guān)性最好的調(diào)制方式第十五頁(yè)，共十九頁(yè)，編輯于2023年，星期三我們能得到多大的自由距？在大部分情況下，自由距是碼設(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)第十六頁(yè)，共十九頁(yè)，編輯于2023年，星期三最大的自由距存在區(qū)間第十七頁(yè)，共十九頁(yè)，編輯于2023年，星期三線(xiàn)性分組碼譯碼的基本方法碼C作為一個(gè)子群，它的每一個(gè)陪集在碼C的正交空間H中的投影是一個(gè)點(diǎn)，而不同的陪集投影不同。每一個(gè)陪集有一個(gè)最小碼重，作為陪集首，代表最可能的錯(cuò)誤圖案。這就引出了伴隨式譯碼：s=rHT，將s與最可能的e建一張表，即可通過(guò)查表法實(shí)現(xiàn)譯碼。第十八頁(yè)，共十九頁(yè)，編輯于2023年，星期三小結(jié)：引入線(xiàn)性碼的好處簡(jiǎn)化了分析：距