第17講--線性分組碼編碼與譯碼課件

線性分組碼的

編碼與譯碼(1)第十九講線性分組碼的

編碼與譯碼(1)第十九講10000010100111001011101110000001001100101101100100011011011011111消息碼字碼許用碼字禁用碼字編碼效率漢明重量漢明距離最小漢明距離糾檢錯(cuò)能力群子群分元陪集0001101100000010011001011011消息碼字基本概念00000000消息碼字碼許用碼字禁用碼字編碼效率漢明20000001001100101101100100011011011011111000010100010011110100010101100101111111000010010111000011001001100111110100111010001101010100011100000111011101010111100分元陪集劃分00000010011001011011001000110130000010100111001011101110000001001100101101100100011011011011111消息碼字碼許用碼字禁用碼字編碼效率漢明重量漢明距離最小漢明距離糾檢錯(cuò)能力群子群分元陪集域GF(2)上的矢量空間子空間矢量張成的子空間基底維數(shù)零化空間矩陣行空間0001101100000010011001011011消息碼字GF(2)基本概念00000000消息碼字碼許用碼字禁用碼字編碼效率漢明4線性分組碼長(zhǎng)度為n，有2k個(gè)碼字的碼組，當(dāng)且僅當(dāng)這2k個(gè)碼字是GF(2)上n維矢量空間的一個(gè)k維子空間時(shí)，稱為(n,k)線性分組碼，簡(jiǎn)稱(n,k)碼。由于k維子空間是在模2加法下運(yùn)算的，構(gòu)成了一個(gè)加法交換群，所以線性分組碼也稱為群碼。碼率R=k/n，就是傳輸效率。最小漢明距離dmin等于非零碼字的最小重量。系統(tǒng)碼n-k

kk

n-k碼字信息位與輸入信息序列相同，并且與校驗(yàn)位分開線性分組碼長(zhǎng)度為n，有2k個(gè)碼字的碼組，當(dāng)且僅當(dāng)這2k個(gè)碼字5生成矩陣線性分組碼是GF(2)上n維空間中的一個(gè)k維子空間，因此它可以由k個(gè)線性無(wú)關(guān)n維矢量完全確定。由于這組矢量的所有線性組合給出了碼C中的任一個(gè)碼字，稱生成碼C。C中任何一組基底所構(gòu)成的矩陣G稱作碼C的生成矩陣生成矩陣線性分組碼是GF(2)上n維空間中的一個(gè)k維子空間，6生成矩陣對(duì)于任何一個(gè)給定的信息序列，可指定作為相應(yīng)的碼字。G矩陣的每一行都是一個(gè)碼字矢量，分別對(duì)應(yīng)信息位為(10…0),(010…0)…(00…01)時(shí)的碼字。生成矩陣對(duì)于任何一個(gè)給定的信息序列7生成矩陣(n,k)分組碼實(shí)際上就是這k個(gè)線性無(wú)關(guān)的碼字矢量張成的k維子空間，這k個(gè)矢量組成的矩陣就是生成矩陣。確定(n,k)碼的生成矩陣的問題實(shí)際上就是確定n重矢量空間中k維子空間的k個(gè)線性無(wú)關(guān)的碼字矢量的問題，也就是尋找基底的問題。(n,k)碼的n重矢量空間中可以有多個(gè)k維子空間，產(chǎn)生不同的碼組，即有不同的基底。(n,k)碼的n-重矢量空間中的一個(gè)k維子空間的基底可以有多個(gè)，因此可以有不同的生成矩陣G，但都產(chǎn)生相同的碼組。生成矩陣(n,k)分組碼實(shí)際上就是這k個(gè)線性無(wú)關(guān)的碼字矢量張8基底的線性組合等效于G的行初等變換，可以產(chǎn)生一組新的基底。利用這一點(diǎn)，可使生成矩陣具有如下“系統(tǒng)形式”，稱之為典型生成矩陣。典型生成矩陣即：G=[IkQ]，Q為k×r矩陣，Ik為k×k單位陣。非系統(tǒng)碼與系統(tǒng)碼并無(wú)本質(zhì)區(qū)別，它的生成矩陣可以通過行初等變換轉(zhuǎn)變?yōu)橄到y(tǒng)形式，這個(gè)過程叫做系統(tǒng)化。系統(tǒng)化并不會(huì)改變碼集，其糾錯(cuò)能力完全等價(jià)。基底的線性組合等效于G的行初等變換，可以產(chǎn)生一組新的基底。利9例題設(shè)二元（5,3）碼，其生成矩陣為將其化為標(biāo)準(zhǔn)形式？例題設(shè)二元（5,3）碼，其生成矩陣為將其化為標(biāo)準(zhǔn)形式？10一致校驗(yàn)矩陣與任何一個(gè)(n,k)碼的碼空間C相對(duì)應(yīng)，一定存在一個(gè)對(duì)偶空間D，它的每個(gè)矢量都與C中的每個(gè)矢量正交，其維數(shù)為n-k。事實(shí)上，若找出生成空間D的基底（n-k個(gè)）用這n-k個(gè)矢量同樣可以生成包含個(gè)碼字的(n,n-k)線性分組碼，我們稱其(n,k)碼的對(duì)偶碼，生成矩陣為一致校驗(yàn)矩陣與任何一個(gè)(n,k)碼的碼空間C相對(duì)應(yīng)，一定存在11一致校驗(yàn)矩陣由對(duì)偶空間的定義知，有對(duì)任意的即H可以檢驗(yàn)一個(gè)n重是否為碼字，稱H為碼C的一致校驗(yàn)矩陣。一致校驗(yàn)矩陣由對(duì)偶空間的定義知，有對(duì)任意的即H可以檢驗(yàn)一個(gè)n12典型一致校驗(yàn)矩陣系統(tǒng)碼的一致校驗(yàn)矩陣為即H=[PIr],

其中，Ir為r×r單位陣，P為r×k矩陣。典型一致校驗(yàn)矩陣系統(tǒng)碼的一致校驗(yàn)矩陣為即H=[PIr],13一致校驗(yàn)矩陣與生成矩陣之間的關(guān)系由于生成矩陣每一行都是一個(gè)碼字，因此應(yīng)當(dāng)滿足一致校驗(yàn)矩陣所規(guī)定的校驗(yàn)關(guān)系，即應(yīng)當(dāng)有：GHT=0或者HGT=0因此H與G互為正交矩陣，說明G和H的行空間互為零化空間。一致校驗(yàn)矩陣與生成矩陣之間的關(guān)系由于生成矩陣每一行都14一致校驗(yàn)矩陣與生成矩陣之間的關(guān)系對(duì)于系統(tǒng)碼，上式可以寫成[IkQ][PIr]T=0得[PT+Q]=0所以PT=Q或者P=QT即P矩陣與Q矩陣互為轉(zhuǎn)置矩陣。對(duì)于系統(tǒng)碼，已知校驗(yàn)矩陣H就可以確定典型生成矩陣G，反之，已知生成矩陣也就可以確定校驗(yàn)矩陣。一致校驗(yàn)矩陣與生成矩陣之間的關(guān)系對(duì)于系統(tǒng)碼，上式可以寫成對(duì)于15例題【例】設(shè)二元(7,4)碼的生成矩陣為求其一致校驗(yàn)矩陣？【例】設(shè)二元(5,3)碼，其生成矩陣為求其一致校驗(yàn)矩陣？例題【例】設(shè)二元(7,4)碼的生成矩陣為求其一致校驗(yàn)矩陣？16線性分組碼編碼線性分組碼的編碼過程分為兩步：把信息序列按一定長(zhǎng)度分成若干信息碼組，每組由k位組成；編碼器按照預(yù)定的線性規(guī)則，把信息碼組變換成n重(n>k)碼字。信息碼組長(zhǎng)k位，有2k個(gè)不同的信息碼組，則有2k個(gè)碼字與它們一一對(duì)應(yīng)。線性分組碼編碼17一致校驗(yàn)矩陣編碼設(shè)c=[c0,c1,c2,c3,c4,c5,c6]，其中，[c0,c1,c2,c3]為信息位，[c4,c5,c6]為校驗(yàn)位。由HCT=0可知校驗(yàn)方程為：c4=c0+c2+c3c5=c0+c1+c2c6=c1+c2+c3信息碼元m=[1101]則編得的碼字c=[1101000]一致校驗(yàn)矩陣編碼設(shè)c=[c0,c1,c2,c3,c4,c5,18生成矩陣編碼若信息碼元m=[1101]，則有c=mG=[1101000]。生成矩陣編碼若信息碼元m=[1101]，則有c=mG=[119譯碼準(zhǔn)則設(shè)發(fā)送碼字為c=(c0,c1,……,cn-1)，由于信道干擾產(chǎn)生差錯(cuò)，反映到接收碼字上可以用一個(gè)二元矢量e表示，e=(e0,e1,……,en-1)，稱為錯(cuò)誤圖樣，其中，ei=1表明相應(yīng)位有錯(cuò)，ei=0表明相應(yīng)位無(wú)錯(cuò)。這時(shí)接收碼字可以表示為r=c+e=(c0+e0，c1+e1,……cn-1+en-1)譯碼器就是從接收碼字r得到發(fā)送碼字的估計(jì)值，或者說從接收碼字中確定錯(cuò)誤圖樣e，然后由c=r-e得到發(fā)送碼字的估計(jì)值。如果估計(jì)正確則譯碼正確，否則譯碼錯(cuò)誤。如何得到發(fā)送碼字的估計(jì)值，根據(jù)什么準(zhǔn)則？譯碼準(zhǔn)則設(shè)發(fā)送碼字為c=(c0,c1,……,cn-1)，20譯碼準(zhǔn)則最大后驗(yàn)概率譯碼最大似然譯碼最小距離譯碼對(duì)于給定的接收矢量，計(jì)算它與M個(gè)可能的發(fā)送碼字之間的距離，從中選擇能使距離達(dá)到最小的碼字作為判決結(jié)果。譯碼準(zhǔn)則最大后驗(yàn)概率譯碼最大似然譯碼最小距離譯碼對(duì)于給定的接21若信道是對(duì)稱DMC信道，其轉(zhuǎn)移概率為1-p和p/(q-1)，則

則對(duì)數(shù)似然函數(shù)為最大似然譯碼準(zhǔn)則可簡(jiǎn)化為：若對(duì)所有的，有則判定最小距離譯碼最小距離譯碼若信道是對(duì)稱DMC信道，其轉(zhuǎn)移概率為1-p和p/(q-1)，22伴隨式設(shè)碼C的一致校驗(yàn)矩陣為H，接收矢量為r，定義稱s為接收矢量r的伴隨式。由伴隨式的定義可知s=rHT=(c+e)HT=cHT+eHT=eHT可以看出伴隨式完全由e決定，它充分反映了信道的干擾情況。如果伴隨式s≠0，接收碼字一定有錯(cuò)誤；如果伴隨式s=0，譯碼器認(rèn)為接收碼字無(wú)錯(cuò)誤。伴隨式設(shè)碼C的一致校驗(yàn)矩陣為H，接收矢量為r，定義稱s為接收23譯碼步驟由接收碼字r計(jì)算伴隨式sT=HrT若s=0，則譯碼器認(rèn)為接收碼字沒錯(cuò)，否則有錯(cuò)，并由s計(jì)算錯(cuò)誤圖樣e由錯(cuò)誤圖樣進(jìn)行譯碼，估計(jì)發(fā)送的碼字c=r-e=r+e

其中最困難的是確定錯(cuò)誤圖樣，即錯(cuò)誤定位。如何進(jìn)行錯(cuò)誤定位？譯碼步驟由接收碼字r計(jì)算伴隨式sT=HrT其中最困難的是確定24譯碼思路1根據(jù)sT=HrT=HeT列出線性方程組（含有n-k個(gè)相互獨(dú)立的方程），通過求解線性方程得到e。上式有n個(gè)未知數(shù)e0,e1,…,en-1，有n-k個(gè)方程，因此有多解。（伴隨式s是一個(gè)r=n-k維矢量，共有個(gè)，而錯(cuò)誤圖樣e是n維矢量，共有個(gè)，因此，s與e不存在一一對(duì)應(yīng)關(guān)系。）最終根據(jù)譯碼準(zhǔn)則選取其中一個(gè)，常常選取重量最輕的為錯(cuò)誤圖樣e的估計(jì)值，從而得到發(fā)送碼字的估計(jì)值，體現(xiàn)最小距離譯碼的思想。譯碼思路1根據(jù)sT=HrT=HeT列出線性方程組（含有n-k25譯碼思路2(n,k)分組碼的2k個(gè)碼字，是n維矢量空間Vn中的一個(gè)k維子空間，它在GF(2)上是一個(gè)子群。利用分元陪集的方法，可以利用該子空間的2k元素，生成Vn中的所有2n個(gè)元素。陪集首c0c1c2…c2k-1e1c1+e1c2+e1c2k-1+e1e2c1+e2c2+e2c2k-1+e2……………e2r-1c1+e2r-1c2+e2r-1c2k-1+e2r-1譯碼思路2(n,k)分組碼的2k個(gè)碼字，是n維矢量空間Vn26陪集首c0c1c2…c2k-1e1c1+e1c2+e1c2k-1+e1e2c1+e2c2+e2c2k-1+e2……………e2r-1c1+e2r-1c2+e2r-1c2k-1+e2r-1標(biāo)準(zhǔn)陣列譯碼表譯碼按以下規(guī)則進(jìn)行：收到碼字R必然在這個(gè)表中，如果落在表中某一列，譯碼器就譯成第一行的相應(yīng)碼字。陪集首c0c1c2…c2k-1e1c1+e1c2+e1c27非常直觀的譯碼方法，選擇重量最輕的禁用碼字作為陪集首，體現(xiàn)最小距離譯碼思想。同一陪集中元素的伴隨式都相同，并且，陪集首與伴隨式矢量有一一對(duì)應(yīng)的關(guān)系。根據(jù)這種關(guān)系，可以將譯碼表簡(jiǎn)化。標(biāo)準(zhǔn)陣列譯碼非常直觀的譯碼方法，選擇重量最輕的禁用碼字作為陪集首，體現(xiàn)最28陪集首c0c1c2…c2k-1e1c1+e1c2+e1c2k-1+e1e2c1+e2c2+e2c2k-1+e2……………e2r-1c1+e2r-1c2+e2r-1c2k-1+e2r-1標(biāo)準(zhǔn)陣列譯碼表伴隨式s0s1s2…s2r-1陪集首c0c1c2…c2k-1e1c1+e1c2+e1c29非常直觀的譯碼方法，選擇重量最輕的禁用碼字作為陪集首，體現(xiàn)最小距離譯碼思想。同一陪集中元素的伴隨式都相同，并且，陪集首與伴隨式矢量有一一對(duì)應(yīng)的關(guān)系。根據(jù)這種關(guān)系，可以將譯碼表簡(jiǎn)化。當(dāng)n-k=r較小時(shí)(小于30)上述標(biāo)準(zhǔn)陣列譯碼方法簡(jiǎn)單實(shí)用。但n進(jìn)一步大時(shí)查表方法就不太實(shí)用了，需要找到更簡(jiǎn)化的譯碼方法，或者是具有簡(jiǎn)單譯碼方法的編碼方法。標(biāo)準(zhǔn)陣列譯碼非常直觀的譯碼方法，選擇重量最輕的禁用碼字作為陪集首，體現(xiàn)最30例題設(shè)一個(gè)(5,2)線性分組碼，其一致校驗(yàn)矩陣如下H，(1)寫出所有許用碼字；(2)求該碼的最小漢明距離；(3)試構(gòu)造