信息論與編碼第六章

信息論與編碼第六章第一頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼最優(yōu)譯碼與最大似然譯碼最優(yōu)譯碼：最大似然譯碼：漢明距離、碼字重量第二頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼一、線性分組碼的基本概念分組碼是建立在碼的代數(shù)結(jié)構(gòu)基礎(chǔ)上的，所以對(duì)分組碼的討論和分析需要一定的代數(shù)基礎(chǔ)。在這里我們不準(zhǔn)備系統(tǒng)地學(xué)習(xí)代數(shù)知識(shí)，只介紹一些相關(guān)的內(nèi)容。第三頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼域（Field）的概念域是定義了兩種代數(shù)運(yùn)算的系統(tǒng)。所謂代數(shù)系統(tǒng)，是指滿足一定規(guī)律或定律的系統(tǒng)，系統(tǒng)中有一群元素構(gòu)成的集合、定義了一些運(yùn)算等。在域中定義的兩種算術(shù)運(yùn)算是：第四頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼（i）加法：集合F在加法運(yùn)算下是封閉的，即如果必有。滿足加法結(jié)合率，即集合中一定包含一個(gè)零元素，滿足集合中每個(gè)元素都有其逆元素，元素a的逆記為-a，有a+(-a)=a-a=0第五頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼（ii）乘法：集合F在乘法運(yùn)算下是封閉的，即如果，則必有滿足乘法結(jié)合率，即滿足乘法交換率，即滿足乘法分配率，即集合中一定有一個(gè)單位元I，對(duì)任何有除零元素外，集合中每一個(gè)元素都有逆元素。第六頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼當(dāng)域由有限個(gè)元素組成時(shí)，叫做有限域，也稱為伽羅華（GaloisField）域，記為GF(q)，其中q是域中元素的個(gè)數(shù)。例如，集合｛0，1｝對(duì)加法和乘法（不包含零元）都是模2的運(yùn)算構(gòu)成一個(gè)域GF（2）。集合｛0，1，2，3，4｝對(duì)加法和乘法（不包含零元）都是模5的運(yùn)算構(gòu)成一個(gè)域GF（5）。第七頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼（2）矢量空間由初等數(shù)學(xué)可知，平面上的二維矢量的全體構(gòu)成一個(gè)二維的矢量空間，空間的三維矢量全體構(gòu)成三維矢量空間。推廣可以得到一般的n維矢量空間。第八頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼在線性空間中，能張成該空間的線性獨(dú)立矢量的集合稱為該空間的基底。n個(gè)n重線性無(wú)關(guān)的矢量可以構(gòu)成一個(gè)n維矢量空間。取其中的k個(gè)可以張成n維空間的一個(gè)子空間。例如：由（1，0，0），（0，1，0），（0，0，1）為基底可以張成一個(gè)三維三重空間，取其中的兩個(gè)為基底可以構(gòu)成一個(gè)二維三重空間。以互相正交的基底張成的兩個(gè)空間也正交，并互稱為另一個(gè)空間的零空間。這兩個(gè)空間對(duì)偶。第九頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼線性分組碼一個(gè)[n，k]分組碼，是把信息劃成k個(gè)為一段（稱為信息組），通過(guò)編碼器變成長(zhǎng)為n個(gè)碼元的一組，作為[n，k]分組碼的一個(gè)碼字。則共可能有個(gè)碼字。如果這些碼字集合組成一個(gè)k維線性空間，則稱它是一個(gè)[n，k]線性分組碼。第十頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼

對(duì)于線性分組碼，如果是碼字，則必定也是碼字。其中是碼元字符集里的任意兩個(gè)元素。因?yàn)橐粋€(gè)定義了加法的域一定有零元素，如果取，則得到的碼字一定是全零碼。因此，線性分組碼一定包含全零碼。因此：第十一頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼也就是說(shuō)：（i）兩個(gè)碼字之間的距離必定等于另一個(gè)碼字的重量，所以線性分組碼的最小碼距等于碼集中非零碼字的最小重量：（ii）研究?jī)蓛纱a字之間的距離，可用碼字與全零碼的距離，或各碼字自身的重量來(lái)代替。第十二頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼對(duì)于[n，k]二進(jìn)制分組碼，共有個(gè)碼字，可以看成是n維n重空間S的一個(gè)子空間。這個(gè)子空間是由k個(gè)基底張成的，記作碼空間C，它是一個(gè)k維n重空間。n維n重空間的另外n-k個(gè)基底則張成一個(gè)n-k維的子空間，稱為校驗(yàn)空間H。分組編碼器的工作，就是要把k維k重的信息組空間的個(gè)矢量一一對(duì)應(yīng)到k維n重碼空間C。因此，編碼算法就要研究?jī)蓚€(gè)問(wèn)題：（i）如何確定碼空間C，和（ii）如何映射。第十三頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼二、生成矩陣和校驗(yàn)矩陣[n，k]分組碼的編碼問(wèn)題就是要在n維線性空間中，找出滿足一定要求的由個(gè)矢量組成的k維n重線性子空間，或者說(shuō)，要由k個(gè)信息碼元得到n-k個(gè)冗余碼元。設(shè)是一組k個(gè)信息組，可以寫(xiě)成矢量形式。編碼器輸出的是k維n重碼空間C的一個(gè)矢量，記為。因此有第十四頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼對(duì)二進(jìn)制分組碼來(lái)說(shuō)，。上式也可以寫(xiě)成矩陣形式：其中，均為一個(gè)含有n個(gè)元素的行向量。所以有第十五頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼G是一個(gè)k行n列的矩陣，給定任何k碼元的信息比特，都可以由G利用公式求出對(duì)應(yīng)的碼字，因此，G被稱為碼的生成矩陣?？梢钥闯?，任何碼子都是G的行矢量的線性組合，即從矢量空間的角度來(lái)說(shuō)，G的k個(gè)行矢量相當(dāng)于k維n重碼字矢量空間的一組基底，該空間的任何矢量（碼字）都可以由這組基底的線性組合得到。并且這組基底本身也是一組碼字。第十六頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼一般形式的G，得到的碼字前k位的信息位也發(fā)生了變化，而一般來(lái)說(shuō)，我們只是希望在信息位后加上冗余比特，所以，可以對(duì)生成矩陣通過(guò)行運(yùn)算（以及列置換）作適當(dāng)?shù)淖儞Q，變成“系統(tǒng)形式”，即這樣生成的（n，k）碼是系統(tǒng)碼。第十七頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼與碼空間C相對(duì)應(yīng)，一定存在一個(gè)對(duì)偶空間H。對(duì)偶空間H的基底，是n維n重矢量空間的基底中，除去張成k維碼字空間C的k個(gè)基底，而剩下的n-k個(gè)基底。因此，H空間和C空間一定正交。即生成矩陣的每一行，都是一個(gè)碼字，所以有第十八頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼因此H叫做碼字空間C的校驗(yàn)矩陣，可以利用是否等于零矢量，來(lái)判斷一個(gè)是不是碼字。例題：對(duì)一個(gè)（7，4）碼，其生成矩陣為第十九頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼（1）對(duì)于信息組(1011)，對(duì)應(yīng)碼字是什么？（2）設(shè)計(jì)一個(gè)（7，4）分組編碼器原理圖。（3）若接收到一個(gè)7位碼r=（1001101），判斷它是否是碼字。解：（1）由生成矩陣可知，得到的一定是系統(tǒng)碼。由得第二十頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼將信息位的值代入，得：，因此，編得的碼字為。注意加法是模2加。（2）由編碼后冗余位與信息位的關(guān)系，可得編碼器的原理圖如圖所示：輸入輸出第二十一頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼（3）要檢驗(yàn)一個(gè)碼序列R是否是碼字，可以使用校驗(yàn)矩陣H，如果，則一定是碼字，否則一定不是碼字。因此，就產(chǎn)生三個(gè)方程，只有第一個(gè)為零，另兩個(gè)不為零，所以R不是碼字。系統(tǒng)碼的前k位為信息位，后n-k位為校驗(yàn)位。第二十二頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼校驗(yàn)矩陣H除了可以用來(lái)檢驗(yàn)碼字外，還與碼的最小距離（也就和碼的檢錯(cuò)糾錯(cuò)能力）有關(guān)。因?yàn)槠渲?，是H矩陣的列向量。第二十三頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼因此，也就是說(shuō)，n個(gè)矢量一定是線性相關(guān)的。如果分組碼的最小距離為，則根據(jù)線性碼的特點(diǎn)，碼集里面一定有一個(gè)碼字其重量最小為，即有個(gè)非零元素。將其代入校驗(yàn)矩陣的方程，左邊就有個(gè)項(xiàng)，而右邊為零。也就是說(shuō)，個(gè)是線性相關(guān)的。而第二十四頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼

個(gè)一定是線性無(wú)關(guān)的（反證法：如果個(gè)列矢量是線性相關(guān)的，則可以把其對(duì)應(yīng)的系數(shù)當(dāng)成碼字，而該碼字的重量為，這與碼字的最小重量為相矛盾）。由于H是的矩陣，其秩最大為n-k，也就是說(shuō)，最多有n-k個(gè)列矢量線性無(wú)關(guān)。所以第二十五頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼在編碼的時(shí)候，我們希望越大越好。二進(jìn)制（n，k）線性碼的最小碼距的上界是n-k+1。稱這樣的碼為極大最小距離碼（MDC:MaximizedminimumDistanceCode）。第二十六頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼本節(jié)討論如何用伴隨式譯碼伴隨式設(shè)發(fā)送的碼字為

通過(guò)有擾信道傳輸，信道產(chǎn)生的錯(cuò)誤圖樣為收端譯碼器收到的n重矢量為第二十七頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼R=C+E，譯碼器的任務(wù)就是要從收到的R中得出，或者由R中解出錯(cuò)誤圖樣，從而得到，并使譯碼錯(cuò)誤概率最小。對(duì)于二進(jìn)制碼字，模2減與模2加等同。對(duì)于[n，k]分組碼C，滿足，因此若E=0，則，若，并且僅與錯(cuò)誤圖樣E有關(guān)，而與發(fā)送什么碼字無(wú)關(guān)。第二十八頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼令S稱為接收矢量R的伴隨式（校正子）。伴隨式完全由E決定，它充分反映了信道的干擾情況。譯碼器的主要任務(wù)就是如何從S中得到最象E的錯(cuò)誤圖樣，從而譯出。S與E是否有一一對(duì)應(yīng)的關(guān)系？如果一個(gè)[n，k]譯碼器要糾正t個(gè)錯(cuò)誤，則要求對(duì)于錯(cuò)誤個(gè)數(shù)的所有可能組合的錯(cuò)誤圖樣，都應(yīng)該有不同的伴隨式與之對(duì)應(yīng)。第二十九頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼2.標(biāo)準(zhǔn)陣列由前面的討論可知，[n，k]分組碼的譯碼步驟可歸結(jié)為以下三步：（1）由接收到的R，計(jì)算伴隨式；（2）若S=0，則認(rèn)為接收無(wú)誤。若，則由

S找出錯(cuò)誤圖樣；（3）由和R找出。這里最關(guān)鍵的是由S找出E，只要找出的E是正確的，譯出的碼也是正確的。第三十頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼由S的定義式，，即共有n-k個(gè)方程，但有n個(gè)未知量，所以解不唯一。對(duì)于二進(jìn)制，少一個(gè)方程導(dǎo)致兩個(gè)解，少兩個(gè)方程導(dǎo)致四個(gè)解，少k個(gè)方程導(dǎo)致有個(gè)解，也就是說(shuō)，可以解出個(gè)不同的錯(cuò)誤圖樣，從而對(duì)應(yīng)了個(gè)碼字（碼字的全部可能）。根據(jù)最大似然譯碼規(guī)則，應(yīng)該譯成可能性最大的那個(gè)碼字。第三十一頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼對(duì)于二進(jìn)制對(duì)稱信道，若差錯(cuò)概率為p，則錯(cuò)一個(gè)比特的概率（）大于錯(cuò)兩個(gè)比特的概率（），…。所以，應(yīng)該譯成所有個(gè)差錯(cuò)圖樣中重量最小的那一個(gè)。但如果每接收一個(gè)R就要解一次方程組，顯然太麻煩了?？梢灶A(yù)先把不同S下的方程組解出來(lái)，并得到最大概率的那個(gè)錯(cuò)誤圖樣，和錯(cuò)誤圖樣對(duì)應(yīng)的R，存成一個(gè)表格，譯碼的時(shí)候，只要根據(jù)不同的R查表，就可以得到對(duì)應(yīng)的最大可能的碼字。第三十二頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼下表就是一個(gè)這樣的表，叫做標(biāo)準(zhǔn)陣列譯碼表。表中有列，每一列的頭一個(gè)元素對(duì)應(yīng)的是一個(gè)碼字，所以共對(duì)應(yīng)個(gè)不同的碼字；每一列的列首元素下，是個(gè)禁用碼字（即n維空間點(diǎn)中不是碼字的那些點(diǎn)），代表該列首元素（碼字）在不同差錯(cuò)圖樣下偏移后所對(duì)應(yīng)的空間點(diǎn)，正好對(duì)應(yīng)了個(gè)不同的伴隨式。全部的元素個(gè)數(shù)是，正好是n維矢量空間中總的點(diǎn)數(shù)，也就是說(shuō)，每一個(gè)空間點(diǎn)第三十三頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼都有其所對(duì)應(yīng)的碼字，這樣，在譯碼的時(shí)候，當(dāng)接收到一個(gè)R后，只要在標(biāo)準(zhǔn)陣列表中找到該R的位置，這一列的列首元素就是它應(yīng)該譯成的碼字。第三十四頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼

標(biāo)準(zhǔn)陣列譯碼表第三十五頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼表中第一行對(duì)應(yīng)的是個(gè)碼字，相當(dāng)于差錯(cuò)為零；第二行到第n+1行分別對(duì)應(yīng)n個(gè)差錯(cuò)為1的差錯(cuò)圖樣；…。每一行的行首元素叫做陪集首，是該行所對(duì)應(yīng)的錯(cuò)誤圖樣。但是，錯(cuò)誤圖樣數(shù)有個(gè)，標(biāo)準(zhǔn)陣列譯碼表只有行，代表個(gè)伴隨式和錯(cuò)誤圖樣。那么，怎么從個(gè)錯(cuò)誤圖樣中選擇個(gè)，作為陪集首？第三十六頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼原則當(dāng)然是要使得譯碼的錯(cuò)誤概率最小。前面已經(jīng)說(shuō)過(guò)，對(duì)BSC信道，當(dāng)錯(cuò)誤概率p<0.5時(shí)，產(chǎn)生一個(gè)錯(cuò)誤的概率比產(chǎn)生兩個(gè)錯(cuò)誤的概率要大，產(chǎn)生兩個(gè)錯(cuò)誤的概率比產(chǎn)生3個(gè)錯(cuò)誤的概率要大，…?？傊?，錯(cuò)誤圖樣重量越小，產(chǎn)生的可能性就越大。因此，譯碼器必須首先保證能正確糾正這些出現(xiàn)可能性比較大的錯(cuò)誤圖樣，這相當(dāng)于構(gòu)造標(biāo)準(zhǔn)陣列譯碼表時(shí)，要求按照錯(cuò)誤圖樣重量從輕到重的順序挑選為陪首集。第三十七頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼例題：某（5，2）系統(tǒng)線性碼的生成矩陣是設(shè)收到的碼是R=(10101)，請(qǐng)先構(gòu)造該碼的標(biāo)準(zhǔn)陣列譯碼表，然后譯出發(fā)碼的估值C。第三十八頁(yè)，共五十五頁(yè)，2022年，8月28日H=[PT┆I3]==s1＝e1h11+e2h12+e3h13+e4h14+e5h15=e1+e2+e3

s2=e1h21+e2h22+e3h23+e4h24+e5h25=e1+e4s3=e1h31+e3h32+e3h33+e4h34+e5h35=e1+e2+e5解：對(duì)應(yīng)（s1,s2,s3）=(111),e=(10000),(01010),(00111)和(11101)四種錯(cuò)誤圖樣信息論與編碼-線性分組碼第三十九頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼標(biāo)準(zhǔn)陣列譯碼表

n-k=3，，即標(biāo)準(zhǔn)陣列譯碼表共有8行，每行代表一種錯(cuò)誤圖樣。按照錯(cuò)誤圖樣重量從輕到重的順序，無(wú)差錯(cuò)（錯(cuò)誤圖樣重量為0）的有一種，重量為1的有種，重量為2的有種。我們挑選的陪首集是1種無(wú)錯(cuò)誤（重量為0），5種有一個(gè)錯(cuò)誤（重量為1）和重量為2的10種里面的2種。第四十頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼碼字共有種，將信息組的可能組合(00)、(01)、(10)、(11)代入生成矩陣，得到四個(gè)碼字為：(00000)、(10111)、(01101)、(11010)。得到的標(biāo)準(zhǔn)陣列譯碼表如下圖所示：第四十一頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼標(biāo)準(zhǔn)陣列譯碼表S1=000E1=00000C2=10111C3=01101C4=11010S2=111E2=10000001111110101010S3=101E3=01000111110010110010S4=100E4=00100100110100111110S5=010E5=00010101010111111000S6=001E6=00001101100110011011S7=011E7=00011101000111011001S8=110E8=00110100010101111100第四十二頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼當(dāng)然，上述的標(biāo)準(zhǔn)陣列譯碼表不是唯一的，因?yàn)閺?0種重量為2的錯(cuò)誤圖樣中選擇兩種，可以是任意選的。標(biāo)準(zhǔn)陣列譯碼表需要把個(gè)n重存儲(chǔ)在譯碼器中。其復(fù)雜性隨n的增大指數(shù)增長(zhǎng)，當(dāng)n比較大時(shí)很不實(shí)用。第四十三頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼可以把標(biāo)準(zhǔn)陣列譯碼表進(jìn)行簡(jiǎn)化，即只存儲(chǔ)伴隨式和錯(cuò)誤圖樣的對(duì)應(yīng)關(guān)系，譯碼時(shí)先計(jì)算得到伴隨式，再查表得到錯(cuò)誤圖樣，從而得到譯碼碼字。這樣碼表可以簡(jiǎn)化，但譯碼時(shí)的計(jì)算量增加了。并且當(dāng)n和k都比較大時(shí)，即使采用這種簡(jiǎn)化的碼表，譯碼器的復(fù)雜性還是很高。因此在線性分組碼理論中，如何簡(jiǎn)化譯碼器是最中心的研究課題之一。第四十四頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼

完備碼對(duì)于糾錯(cuò)能力為t的（n，k）分組碼，重量小于等于t的錯(cuò)誤圖樣共有因此，要想糾正t個(gè)錯(cuò)誤，必須有第四十五頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼如果伴隨式的數(shù)目剛好等于重量小于等于t的錯(cuò)誤圖樣的數(shù)目，即則稱這樣的（n，k）分組碼為完備碼。這樣每一個(gè)錯(cuò)誤圖樣，都有一個(gè)不同的伴隨式與之對(duì)應(yīng)，每一個(gè)伴隨式都對(duì)應(yīng)一個(gè)不同的錯(cuò)誤圖樣。第四十六頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼從多維矢量空間的角度來(lái)看完備碼假定我們圍繞每一個(gè)碼字ci放置一個(gè)半徑為t的球，每個(gè)球內(nèi)包含了與該碼字漢明距離小于、等于t的所有收碼R的集合，這樣在半徑為t＝[(dmin-1)/2]的球內(nèi)的收碼數(shù)是。

第四十七頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼因?yàn)橛?k個(gè)可能發(fā)送的碼字，也就有2k個(gè)不相重疊的半徑為t的球。包含在2k個(gè)球中的碼字總數(shù)不會(huì)超過(guò)2n個(gè)可能的接收碼字。于是一個(gè)糾t差錯(cuò)的碼必然滿足不等式

2k?≤2n即2n-k≥第四十八頁(yè)，共五十五頁(yè)，2022年，8月28日信息論與編碼-線性分組碼如果等號(hào)成立，表示所有的收碼都落在2k個(gè)球內(nèi)，而球外沒(méi)有一個(gè)碼，這就是完備碼。完備碼具有下述特性：圍繞個(gè)碼字、漢明距離為t=└（dmin-1）/2┘的所有球都是不相交的，每一個(gè)接收碼字都落在這些球中之一，因此接收碼離發(fā)碼的距離至多為t，這時(shí)所有的重量≤t的差錯(cuò)圖案都能用最佳（最小距離）譯碼器得到糾正，而所有重量≥t+1的差錯(cuò)圖案都不能糾正。第四十九頁(yè)，共五