第5章線性分組碼-抗干擾信道編碼

第5章線性分組碼-抗干擾信道編碼第一頁，共243頁。眾所周知，信道總是要受到噪聲干擾，所以我們收到的符號不一定與發(fā)送符號一致。也就是說，當(dāng)我們收到一個符號時，并不能確定發(fā)送的是哪個符號。對于某一個具體的物理信道，其可靠性是確定的。但是在不同的具體通信系統(tǒng)中，有不同的可靠性要求。在具體應(yīng)用時，我們可以通過信道編碼提高通信系統(tǒng)的可靠性，使其滿足具體應(yīng)用要求。下面我們通過兩個具體的例子來說明。第1節(jié)預(yù)備知識1概述第二頁，共243頁。1)奇偶校驗碼（以偶校驗碼為例）首先，我們將發(fā)送的比特流劃分成k比特的分組。然后在每個分組后面添加一位，確保每個分組中符號“1”的個數(shù)為偶數(shù)。最后將處理后的比特流送入信道中。編碼：第1節(jié)預(yù)備知識第三頁，共243頁。解碼：首先，我們將接收到比特流劃分成k＋1個比特的分組。然后檢查每個分組中符號“1”的個數(shù)，若為奇數(shù)個，則說明信道出錯，請求對方重發(fā)；若為偶數(shù)個，則認(rèn)為信道沒有出錯，將最后一個比特丟掉，剩余的k個比特交給信源解碼設(shè)備。信源：1111010010001取k＝8101001100100111010010001偶校驗編碼:101001100010011100100100011例：第1節(jié)預(yù)備知識第四頁，共243頁。如果沒有錯誤發(fā)生，分組中的符號“1”的個數(shù)仍為偶數(shù)個。接收機(jī)將接收到的分組中最后一個比特丟掉，然后將剩余比特送到信源解碼設(shè)備。如果分組中有奇數(shù)個錯誤發(fā)生，則接收分組中一定符號“1”的個數(shù)一定是奇數(shù)個，故接收方一定能夠發(fā)現(xiàn)錯誤，并請求對方重發(fā)(ARQ)。如果分組中有偶數(shù)個錯誤發(fā)生，則接收分組中仍有偶數(shù)個符號“1”，接收者不能發(fā)現(xiàn)錯誤。同樣將最后一個比特丟掉后送到信源解碼器。此類錯誤不能發(fā)現(xiàn)。第一節(jié)預(yù)備知識第五頁，共243頁。假設(shè)每個比特出錯的概率為p，則一個分組出錯但不能被檢測出的概率為編碼效率第1節(jié)預(yù)備知識第六頁，共243頁。如果p=0.02,則而不編碼的分組錯誤概率為：奇偶校驗碼是一種檢錯碼，是所有差錯控制編碼中效率最高的編碼。第1節(jié)預(yù)備知識第七頁，共243頁。2)重復(fù)編碼000000111111如果少于3個錯誤發(fā)生，我們可以糾正錯誤如果少于5個錯誤發(fā)生，我們可以發(fā)現(xiàn)錯誤101011111000001111100000編碼效率重復(fù)編碼是一種糾錯碼，是所有差錯控制編碼中效率最低的一種第1節(jié)預(yù)備知識第八頁，共243頁。第1節(jié)預(yù)備知識差錯控制編碼的基本原理是在信號送入信道之前，在原始信息的基礎(chǔ)上增加一些可控的冗余(額外的符號)。在接收端，如果錯誤的符號數(shù)在差錯控制編碼的設(shè)計范圍內(nèi)，則錯誤可以被糾正或發(fā)現(xiàn)。常見的差錯控制編碼包括奇偶校驗碼、循環(huán)碼、海明碼、卷積碼等等！第九頁，共243頁。第1節(jié)預(yù)備知識2、幾個概念1）分組：由信源碼符號流按劃分成的（k個信源碼符號組成的）符號組2）信道碼符號：構(gòu)成信道有效碼字的符號集信源信源編碼信道編碼信道信道譯碼信源譯碼信宿信源符號信源碼符號信道碼符號信源符號信源碼符號信道碼符號第十頁，共243頁。第1節(jié)預(yù)備知識例：若信源碼符號集為{0,1},則信源編碼后輸出為由0、1組成的符號序列。若信道編碼如下分組信道有效碼字分組信道有效碼字000000010022000010011101121201000221102121011110011111221）將3(k=3)個信源碼符號組成的分組編碼成4(n=4)個信道碼符號組成的信道有效碼字。

2）信道碼符號集為{0,1,2}第十一頁，共243頁。第1節(jié)預(yù)備知識有效(信道)碼字：與分組一一對應(yīng)的、由n個信道碼符號組成的的序列禁用(信道)碼字：除了有效碼字之外的、由n個信道碼符號的序列字:有效碼字＋禁用碼字有效碼字集：{0000,0011,0022,1100,2200,1212,2121,1122}禁用碼字集：I－有效碼字字集：I第十二頁，共243頁。第3節(jié)信道編碼中的基本概念如在重復(fù)編碼中，將“1”編碼成“11111”，將“0”編碼成“00000”，則“11111”和“00000”稱為有效碼字。除了這兩個碼字外，還有30個碼字沒有被使用，這30個碼字都稱為禁用碼字。如果信道不出錯，則輸出的只有可能是兩種有效碼字中的一個；如果輸出的不是這兩個有效碼字，則一定信道一定出錯。第十三頁，共243頁。第1節(jié)預(yù)備知識思考:1、信道編碼是否要考慮前綴編碼條件問題？2、如果信道丟失了一個信道符號，會對譯碼造成什么樣的影響？第十四頁，共243頁。第1節(jié)預(yù)備知識1)、糾錯檢錯的能力，主要用最小海明距離衡量。2)、編碼的效率，或者叫信道的信息率：3)、編碼的軟件硬件實現(xiàn)效率和困難程度。對于一種抗干擾信道編碼，衡量其性能的標(biāo)準(zhǔn)主要有以下幾個方面：2信道編碼的評價標(biāo)準(zhǔn)：第十五頁，共243頁。1、后驗概率譯碼a1a2a3a4b1b2b3b41)后驗概率譯碼第2節(jié)譯碼規(guī)則第十六頁，共243頁。例：譯碼規(guī)則：接收為b1時正確譯碼的概率，等于在接收為b1的條件下發(fā)送符號為a1的概率。第2節(jié)譯碼規(guī)則正確譯碼概率第十七頁，共243頁。錯誤譯碼的概率等于在接收為b1的條件下，發(fā)送符號不是a1的概率平均錯誤概率第2節(jié)譯碼規(guī)則第十八頁，共243頁。譯碼規(guī)則或討論：若在接收為某符號的條件下，發(fā)送為某幾個符號的概率相同，則可任選一個作為譯碼。第2節(jié)譯碼規(guī)則第十九頁，共243頁。2)推廣：第2節(jié)譯碼規(guī)則第二十頁，共243頁。例:已知信源空間為信道轉(zhuǎn)移概率矩陣為：第2節(jié)譯碼規(guī)則第二十一頁，共243頁。求Pe第2節(jié)譯碼規(guī)則第二十二頁，共243頁。第2節(jié)譯碼規(guī)則第二十三頁，共243頁。第2節(jié)譯碼規(guī)則第二十四頁，共243頁。第2節(jié)譯碼規(guī)則第二十五頁，共243頁。第2節(jié)譯碼規(guī)則第二十六頁，共243頁。第2節(jié)譯碼規(guī)則第二十七頁，共243頁。2、最大似然譯碼如果所有信源都是等概率的，則有1)最大似然譯碼第2節(jié)譯碼規(guī)則第二十八頁，共243頁。我們可以得到這樣的結(jié)論：如果信源符號等概率出現(xiàn)，可以利用信道轉(zhuǎn)移概率構(gòu)成譯碼規(guī)則。第2節(jié)譯碼規(guī)則第二十九頁，共243頁。2)平均錯誤譯碼概率第2節(jié)譯碼規(guī)則第三十頁，共243頁。第2節(jié)譯碼規(guī)則第三十一頁，共243頁。例:已知信源概率空間為信道轉(zhuǎn)移概率為：b1b2b3b4a1a2a3a4第2節(jié)譯碼規(guī)則第三十二頁，共243頁。平均錯誤概率第2節(jié)譯碼規(guī)則第三十三頁，共243頁。第2節(jié)譯碼規(guī)則第三十四頁，共243頁。1、分組碼：信源碼符號流被劃分成k個符號的分組，然后編碼成唯一對應(yīng)的n個比特的信道碼字。例子：k=2,n=3第3節(jié)信道編碼中的基本概念和原理第三十五頁，共243頁。2、漢明重量：碼字中非零符號的個數(shù)，用w表示3、漢明距離：兩個碼字中相同位置的不同符號的個數(shù)，用d表示第3節(jié)信道編碼中的基本概念第三十六頁，共243頁。4、最小漢明重量w*：在一種編碼種所有碼字的海明重量的最小值第3節(jié)信道編碼中的基本概念第三十七頁，共243頁。5、最小漢明距離d*：一種編碼中任意兩個碼字的的海明距離的最小值。第3節(jié)信道編碼中的基本概念第三十八頁，共243頁。例：第3節(jié)信道編碼中的基本概念第三十九頁，共243頁。6、解碼球000010,100,001110,101,011111010110,011,000100,111,001101第3節(jié)信道編碼中的基本概念1)字的球模型如左圖所示，與字000海明距離為1的字在以字000為球心、半徑為1的球面上。同理，與字000海明距離為2(或3)的字在以字000為球心、半徑為的2(或3)球面上。同樣，我們也可以以其它字為球心。如左下圖中，就是以字010為球心、建立的分別以1、2或3為半徑的球面。第四十頁，共243頁。第3節(jié)信道編碼中的基本概念2)解碼球在分組碼中，分別以各有效碼字為球心，建立半徑為e的球，且各球互不相交。如果接收的字落到某各球內(nèi)，則譯碼成球心處對應(yīng)的碼字。這樣的球叫解碼球。

例：已知分組碼分別建立以有效碼字000和111為球心、半徑為1的球。如下圖所示：第四十一頁，共243頁。1)信道編碼糾檢錯能力取決于這種編碼的最小海明距離，最小海明距離越大，糾檢錯能力越強(qiáng)。2)如果分組碼能糾正所有的e個符號的錯誤，則最小漢距明離應(yīng)滿足：有效碼字1有效碼字2ee1第3節(jié)信道編碼中的基本概念7、線性分組碼的糾檢錯能力第四十二頁，共243頁。例:重復(fù)編碼000000111111C={00000,11111}第3節(jié)信道編碼中的基本概念第四十三頁，共243頁。3)、如果分組碼能檢測所有的f個符號的錯誤，則最小海明距離應(yīng)滿足：有效碼字1有效碼字2例：C={000,010,101,111}f1例:C={00000,11111}第3節(jié)信道編碼中的基本概念第四十四頁，共243頁。4)、如果分組碼能檢測所有的f個符號的錯誤，并能糾正所有的e為錯誤，則最小海明距離應(yīng)滿足有效碼字1e1e有效碼字2f第3節(jié)信道編碼中的基本概念第四十五頁，共243頁。8、抗干擾信道編碼定理抗干擾信道編碼定理也就是香農(nóng)第二定理，其表述形式如下：設(shè)信道有r個碼符號，當(dāng)信道的信息傳輸率R<C時，只要碼長N足夠長，總可以從輸入集合中(rN個長度為N的字)找到M個碼字，代表分別M個消息，組成一種信道編碼。選擇相應(yīng)的譯碼規(guī)則，使最小譯碼錯誤概率任意小。香農(nóng)第二定理說明：平均錯誤譯碼概率趨近于0，信道信息傳輸率R趨近于信道容量C的抗干擾信道編碼是存在的。第3節(jié)信道編碼中的基本概念第四十六頁，共243頁。第3節(jié)信道編碼中的基本概念我的理解信源編碼的碼率為：Rbit/信源碼符號每k個信源碼符號分為一組，編碼為n個信道碼符號。如果要使信息完全傳遞，則每個信道碼符號攜帶的信息量應(yīng)為：如果信道的容量C滿足bit/信道碼符號則這樣的編碼總是可以找到的第四十七頁，共243頁。P532T7.4T7.6T7.9作業(yè)第四十八頁，共243頁。1線性分組編碼的定義:一個線性編碼具有以下的性質(zhì)信息序列被劃分成等長的k個符號的分組，每個分組被編碼成n個比特的碼字。其中r=n-k為冗余。任意個有效碼字的線性組合仍然是一個有效碼字。全0字也一定是一個有效碼字。例1C={010,011,100,110}例3C={010,000,100,110,111}例2C={000,010,101,111}第4節(jié)線性分組碼定義及性質(zhì)第四十九頁，共243頁。2、線性分組碼的性質(zhì)線性分組碼的最小漢海明距離等于它的非零碼字的最小海明重量。因為如果字C1和C2都是有效碼字,則C3=C1-C2必然也是一個有效碼字。假設(shè)C1和C2

之間的海明距離為線性分組碼的最小海明距離，則該線性分組碼的最小海明距離等于碼字C3的海明重量。第4節(jié)線性分組碼定義及性質(zhì)第五十頁，共243頁。3、說明：我們通常用“群”、“域”和“線性空間”的理論來描述和研究現(xiàn)行分組碼。第4節(jié)線性分組碼定義及性質(zhì)例2C={000,010,101,111}第五十一頁，共243頁。1群i)封閉性1)群的定義G是一個非空集合，在這個集合上定義了一種運算””(可以是乘法或加法)。如果滿足以下四點性質(zhì)，則稱之為群。記作(G，)第5節(jié)線性分組碼的群表示第五十二頁，共243頁。ii)結(jié)合律iii)集合中存在唯一單位元第5節(jié)線性分組碼的群表示第五十三頁，共243頁。vi)集合中每個元素都存在唯一逆元例1定義了“+”整數(shù)集合是一個加法群唯一單位元:唯一逆元：封閉性:結(jié)合律第5節(jié)線性分組碼的群表示第五十四頁，共243頁。例2定義了乘法運算的正數(shù)集合是一個乘法群。唯一的單位元：唯一逆元：封閉性:結(jié)合律討論：是不是加法群?第5節(jié)線性分組碼的群表示第五十五頁，共243頁。例3:所有的m×n階矩陣的集合是一個加法群。唯一的單位元：唯一逆元：封閉性:結(jié)合律討論：是不是乘法群?第5節(jié)線性分組碼的群表示第五十六頁，共243頁。例5:集合={0,1,2,3,4}運算為模5和01234001234112340223401334012440123唯一的單位元：唯一逆元：封閉性:結(jié)合律討論：是不是乘法群?第5節(jié)線性分組碼的群表示第五十七頁，共243頁。例6:集合={1,2,3,4}模5乘法運算123411234224133314244321×唯一的單位元：唯一逆元：封閉性:結(jié)合律討論：是不是加法群?第5節(jié)線性分組碼的群表示第五十八頁，共243頁。例7:G={000,010,101,111}，按位模2加法000010101111000000010101111010010000111101101101111000010111111101010000唯一的單位元：唯一逆元：封閉性:結(jié)合律第5節(jié)線性分組碼的群表示第五十九頁，共243頁。提示：集合S={1,2,3,…,q-1}在模q乘法運算下是一個群的充分必要條件是：q是素數(shù)(質(zhì)數(shù))123112322023321×集合S={1,2,3}在模4乘法運算下不是群第5節(jié)線性分組碼的群表示第六十頁，共243頁。2)群的分類i)按照不同的運算可分為加法群和乘法群。ii)按照集合中元素的個數(shù)可分為有限群和無限群i)交換群則稱之為交換群，也叫做阿貝爾群。3)兩種特殊的群如果一個群中的元素滿足交換率，即第5節(jié)線性分組碼的群表示說明：加法群一定不是乘法群，乘法群一定不是加法群第六十一頁，共243頁。ii)循環(huán)群如果群中的元素可用如下的形式表示，則稱之為循環(huán)群。如果循環(huán)中的元素是有限的，則稱之為有限循環(huán)群，可表示為：例:G={i,-i,1,-1}是一個乘法群，也是一個有限循環(huán)群G={i0,i1,i2,i3}G={(-i)0,(-i)1,(-i)2,(-i)3}第5節(jié)線性分組碼的群表示第六十二頁，共243頁。(1)元素a稱為生成元例:G={-1,i,-i,1}乘法運算說明：(2)循環(huán)群一定是阿貝爾群(3)循環(huán)群中元素的個數(shù)稱為循環(huán)群的階(4)循環(huán)群中生成元的個數(shù)不一定唯一第5節(jié)線性分組碼的群表示第六十三頁，共243頁。例:G={1,2,3,4}模5乘法運算G={20,21,22,23}G={30,31,32,33}第5節(jié)線性分組碼的群表示第六十四頁，共243頁。4)子群例6:G={-1,i,-i,1}S={-1,1}如果G是一個群，集合SG且在同樣的運算規(guī)則下滿足群的四點性質(zhì)，我們將S稱為G的子群。例7:G={000,010,101,111}S={000,111}第5節(jié)線性分組碼的群表示第六十五頁，共243頁。5)陪集和陪集首陪集的定義若G是一個群，S是G的子群，a為群G中的任意一個元素，我們把集合：a+S={a+x|xC}叫做一個陪集。第5節(jié)線性分組碼的群表示第六十六頁，共243頁。例:G={000,001,010,011,100,101,110,111}S={000,010,101,111}Coset1:000+S={000,010,101,111}Coset2:001+S={001,011,100,110}Coset1:010+S={010,000,111,101}Coset2:011+S={011,001,110,100}Coset2:100+S={100,110,001,011}Coset1:101+S={101,111,000,010}Coset2:110+S={110,100,011,001}Cose1:111+S={111,101,010,000}第5節(jié)線性分組碼的群表示第六十七頁，共243頁。陪集1:000+S=010+S=101+S=111+S={000,010,101,111}陪集2:001+S=011+S=100+S=110+S={001,011,100,110}G=陪集1陪集2由上面的例子我們可以看出，所有的陪集中，只有兩個不同的陪集，這兩個陪集中的元素構(gòu)成了群G中的所有元素。第5節(jié)線性分組碼的群表示第六十八頁，共243頁。群G的任何一個元素必在它的某個陪集中。兩個陪集要么完全相同，要么完全不同，不存在兩個陪集中的元素部分相同的情況。如果a+S是S的一個陪集且ba+S,則有b+S=a+Siv.陪集中的元素的個數(shù)一定與子群中元素的個數(shù)相同v.互不相同的陪集的個數(shù)為：第5節(jié)線性分組碼的群表示陪集的性質(zhì)：第六十九頁，共243頁。子群陪集首000010101111000000010101111001001011100110陪集1陪集2在構(gòu)成每個陪集的元素中，我們選取海明重量最小的一個來構(gòu)成陪集，這個元素叫做陪集首。第5節(jié)線性分組碼的群表示陪集首：第七十頁，共243頁。第5節(jié)線性分組碼的群表示說明例G={000,011,101,110}按位模2加a、線性分組碼中的所有有效碼字構(gòu)成在按位模2加運算下的加法子群，因此可以用群去描述線性分組碼，可以用群的理論去分析線性分組碼。分組碼字分組碼字00000101010101111110信道編碼信道…0第七十一頁，共243頁。例：G={0000,1111,0011}按位模2加第5節(jié)線性分組碼的群表示000001111120011信道編碼信道…10第七十二頁，共243頁。例：G={000,111,222}按位模3加第5節(jié)線性分組碼的群表示000011112222信道編碼信道…10第七十三頁，共243頁。第5節(jié)線性分組碼的群表示b、不同的陪集代表不同的出錯情況下的信道輸出00000010111010111110信道編碼信道譯碼信道第七十四頁，共243頁。第5節(jié)線性分組碼的群表示子群陪集000011101110000000011101110001001010100111010010001111100011011000110101100100111001010101101110000011110110101011000111111100010001第七十五頁，共243頁。第5節(jié)線性分組碼的群表示子群陪集首000011101110000000011101110001001010100111c、陪集首代表最有可能出錯的情況，糾錯譯碼的基本原理第七十六頁，共243頁。討論：如果k=17，n=23,則表一共有2k＝217

行,每一行有n+k＝40個比特，所以在發(fā)送端我們需要40×217

個比特的存儲空間，而在接收端需要40×223

個存儲單元。表越大，需要的存儲空間越大，檢索越困難。第5節(jié)線性分組碼的群表示第七十七頁，共243頁。在集合F上定義了兩種“+”和“·”運算，并且在這兩種運算下滿足以下八點性質(zhì)，則稱F是一個域。記做(F,+,·)加法和乘法的封閉性滿足交換律1）域的定義第5節(jié)線性分組碼的群表示2域第七十八頁，共243頁。第5節(jié)線性分組碼的群表示滿足結(jié)合律存在唯一加法單位元存在唯一乘法單位元iv)滿足結(jié)合律第七十九頁，共243頁。集合F中的任何一個元素，都存在唯一的加法逆元。集合F中的任何一個非零元素，都存在唯一的加法逆元。第5節(jié)線性分組碼的群表示第八十頁，共243頁。第5節(jié)線性分組碼的群表示域中的元素可以是有限或無限個，如果域中的元素是有限的q個，則稱為伽羅瓦域，記做GF(q)。2）伽羅瓦域第八十一頁，共243頁。例:集合F＝{0,1,2,3,4}。它的模5加法與模5乘法下是一個5階伽羅瓦域。0123400123411234022340133401244012301234000000101234202413303142404321×由乘法和加法表，可以很直觀地看出，它是一個伽羅瓦域。第5節(jié)線性分組碼的群表示第八十二頁，共243頁。1、寫出一個加法群和一個乘法群(要求群中元素不少于5個)，一定要指明其運算法則，并對其定義中的四點性質(zhì)進(jìn)行說明。2、寫出一個循環(huán)群，先說明它是一個群，然后寫出生成元。3、寫出一個群以及它的一個子群，并寫出該子群的陪集，指明陪集首。4、寫出一個域的例子，并對其八點性質(zhì)進(jìn)行說明。作業(yè)第八十三頁，共243頁。5、令G取一切有理數(shù)對(a,b)所構(gòu)成的集合，且a0。若定義有理數(shù)對的乘法規(guī)則為(a1,b1)(a2,b2)=(a1a2,a2b1+b2)問G對于該乘法是否構(gòu)成群？為什么？作業(yè)第八十四頁，共243頁。3基于子群的線性分組碼的一種可行的編碼方法由前面線性分組碼所定義可知，它必須滿足以下條件：i)全零碼字必須包含在其中。ii)幾個碼字的線性組合必為另外一個有效碼字。所以二進(jìn)制線性分組碼能夠被看作一個在按位模2和運算下的加法子群，其加法單位元就是全零碼字。例:{000,010,101,111}第5節(jié)線性分組碼的群表示第八十五頁，共243頁。例：寫出包含下列元素的線性分組碼1)<S>={1100,0100,0011}二進(jìn)制伽羅瓦域。1100+0100=10001100+0011=11110100+0011=01111100+0100+0011=1011C={0000,1100,0100,0011,1000,1111,0111,1011}線性分組碼C的最小海明距離為1第5節(jié)線性分組碼的群表示第八十六頁，共243頁。00000001100001010001000110111000100111110101111101011111第5節(jié)線性分組碼的群表示第八十七頁，共243頁。2)<S>={12,21}GF(3)12+21=0012+2×(21)=212×(12)+21=12C={00,12,21}最小海明距離為2第5節(jié)線性分組碼的群表示2×(12)+2×21=00第八十八頁，共243頁。1一個簡單的例子之所以要介紹線性空間，是因為任何一個字都可以看作線性空間的一個矢量，所有線性分組碼的編碼過程就可以看作矢量的空間變換過程。第6節(jié)線性分組碼的線性空間表示第八十九頁，共243頁。(1,1)(0,1)(1,0)(0,0)假設(shè)編碼為二進(jìn)制，k=2,n=3。也就是將需要編碼的比特流劃分成2比特的分組，然后編碼成3比特。其編碼過程如下圖所示兩比特的分組的可能組合有以下四種：00，01，10，11在二維空間表示如右圖所示第6節(jié)線性分組碼線性空間表示第九十頁，共243頁。第6節(jié)線性分組碼線性空間表示0zyx0111010101如果將該二維空間的矢量搬移到如圖所示的三位空間的二維子空間，則可得到如中圖所示的黃色平面。右圖為編碼可以清楚看出，進(jìn)行該變換后，碼字之間的距離明顯拉大了，也就是海明距離發(fā)生了變化。00011011000010101111第九十一頁，共243頁。第6節(jié)線性分組碼線性空間表示在上述的編碼中，部分碼字的海明距離增加了，但最小海明距離仍為1，總體來說不是一種很好的編碼。但如果我們將原始碼的二維空間映射左下圖的黃色平面上，則可得到最小海明距離為2的編碼。第九十二頁，共243頁。第6節(jié)線性分組碼線性空間表示zyx011001110100011011000011101110zyx0110011101112注意：在二進(jìn)制中，點(1,1,2)和點(1,1,0)是同一個點，因此左圖黃色平面與中圖黃色平面為同一平面。第九十三頁，共243頁。2線性空間(1)線性空間的定義定義域(F,·,+)上的所有的n重矢量集合V={Vi}，其中Vi=(vi1,vi2,vi3…vin).矢量的集合叫做F域上的n維空間。第6節(jié)線性分組碼線性空間表示說明：1）矢量是可以平移的。2）線性空間的每一個點與一個以原點為起點的矢量一一對應(yīng)。3）線性空間與域有關(guān)第九十四頁，共243頁。例：在域GF()2:{-,}上，二維空間有無窮多個一維子空間。而在GF(2)上，二維空間只有三個一維子空間。(1,1)(0,1)(1,0)(0,0)第6節(jié)線性分組碼線性空間表示第九十五頁，共243頁。在域GF()3:{-,}上，三維空間有無窮多個二維子空間。而在域GF(2)3上，三維空間只有七個二維子空間。0zyx0ABCDEFG第6節(jié)線性分組碼線性空間表示第九十六頁，共243頁。(2)線性空間的性質(zhì)i)任意矢量與實數(shù)域中任意元素的乘積仍為原空間的一個矢量。第6節(jié)線性分組碼線性空間表示第九十七頁，共243頁。ii)滿足分配律和結(jié)合律iii)k維空間所有矢量的集合是一個加法群。第6節(jié)線性分組碼線性空間表示第九十八頁，共243頁。(3)線性相關(guān)(1,1)(0,1)(1,0)(0,0)設(shè)vi是n維空間的矢量，ai是GF(q)上的不全為零的元素。若能夠找到一組ai使等式則稱這些矢量線性相關(guān)。第6節(jié)線性分組碼線性空間表示第九十九頁，共243頁。(4)線性空間的基礎(chǔ)矢量如果我們有k個線性無關(guān)的矢量V1,V2…Vk，它們可以構(gòu)成一個k為線性空間Vk。我們將這k個矢量稱作空間Vk的一組基礎(chǔ)矢量。第6節(jié)線性分組碼線性空間表示第一百頁，共243頁。(1,1)(0,1)(1,0)(0,0)例：在一維空間，任意選擇一個矢量，其它所有矢量都可以用這個矢量的線性形式表示。例：在二維空間，任意選擇兩個線性無關(guān)的矢量，其它所有矢量都可以用兩個矢量的線性組合形式表示。第6節(jié)線性分組碼線性空間表示第一百零一頁，共243頁。(5)線性子空間如果矢量Vs是矢量群V的一個子群,我們稱空間Vs為空間V的子空間zyx0zyx0V1=(1,0,0)一維三重空間第6節(jié)線性分組碼線性空間表示第一百零二頁，共243頁。S={000,001,010,011,100,101,110,111}S1={000,011,,101,110}zyx0011110101

V2=(0,1,0)V1=(1,0,0)二維三重空間第6節(jié)線性分組碼線性空間表示第一百零三頁，共243頁。如果我們從n維空間中選取k個線性無關(guān)的是矢量，則這些矢量可以確定一個n重k維子空間，子空間中的任意一個矢量均可以用這k個線性無關(guān)矢量的線性組合表示出來。第6節(jié)線性分組碼線性空間表示第一百零四頁，共243頁。(6)正交矢量與正交空間i)正交矢量：如果兩個矢量的內(nèi)積為0，則這兩個矢量正交。第6節(jié)線性分組碼線性空間表示第一百零五頁，共243頁。如果兩個矢量其內(nèi)積為：如果兩個矢量正交，則有：第6節(jié)線性分組碼線性空間表示第一百零六頁，共243頁。ii)如果一個空間中的任何一個非0矢量與另外一個空間中的任何一個非0矢量正交，則這兩個空間正交。zyx0011110101zyx0第6節(jié)線性分組碼線性空間表示第一百零七頁，共243頁。6)對偶空間i)S1

S且S2

Sii)dimension(S1)+dimension(S2)=

dimension(S)兩個子空間S1

和S2

同屬線性空間S，兩個子空間的維數(shù)之和等于線性空間S的維數(shù)，兩個子空間只相交于坐標(biāo)原點，且兩個子空間正交，則這兩個子空間互為對偶空間。iii)S1S2=

0注意：互為對偶空間的兩個空間的并集并不等于原空間。第6節(jié)線性分組碼線性空間表示iv)S1和S2正交第一百零八頁，共243頁。zyx0zyx0011110101010001100011101110000111V1V2V第6節(jié)線性分組碼線性空間表示第一百零九頁，共243頁。線性分組碼加法子群線性子空間GF(q)1)任何碼字都可以看作一個n重矢量。2)K個線性無關(guān)的矢量可以決定一個n重k維子空間。3)所有的許用碼字構(gòu)成n重k維子空間。結(jié)論：4)在所有的碼字中選出k個線性無關(guān)的碼字，其它碼字都可以由這些碼字的線性組合得到。第6節(jié)線性分組碼線性空間表示第一百一十頁，共243頁。線性分組碼的一種可行的編碼和解碼方法如下圖所示在發(fā)送端有一個編碼表，表中的原碼與信道編碼碼字一一對應(yīng)，如果要發(fā)送一個原碼，則在表中查找該原碼對應(yīng)的碼字并將發(fā)送出去。在接收端也有一個解碼表，表示接收到某個字后應(yīng)如何譯碼。第7節(jié)線性分組碼的生成矩陣及編碼00000010111010111110信道編碼信道譯碼信道

000？100？001？10？010？110？011？111？第一百一十一頁，共243頁。在二進(jìn)制編碼中，k比特的分組可以有2k個不同的分組，編碼后成為2k個n比特的碼字。1、幾個簡單例子我們知道，線性分組碼(n,k)是將k個信源碼符號的信息序列編碼成n個信道碼符號組成的碼字。即：第7節(jié)線性分組碼的生成矩陣及編碼第一百一十二頁，共243頁。碼字是由信息序列決定的，即有以下關(guān)系，其中fi是線性映射。第7節(jié)線性分組碼的生成矩陣及編碼第一百一十三頁，共243頁。第7節(jié)線性分組碼的生成矩陣及編碼例1：我們知道信息序列的長度k＝3，碼字長度n＝6.碼字和信息序列的關(guān)系如左圖所示。則其編碼如右圖所示。信息序列碼字第一百一十四頁，共243頁。第7節(jié)線性分組碼的生成矩陣及編碼例2：我們知道信息序列與碼字的關(guān)系為：k＝1，n＝5信息序列碼字第一百一十五頁，共243頁。第7節(jié)線性分組碼的生成矩陣及編碼例3：已知碼字和信息序列的關(guān)系：偶校驗碼k＝3,n＝4信息序列碼字第一百一十六頁，共243頁。一般表達(dá)形式第7節(jié)線性分組碼的生成矩陣及編碼第一百一十七頁，共243頁。第7節(jié)線性分組碼的生成矩陣及編碼第一百一十八頁，共243頁。此處，“C”是線性分組碼，“I”是信息序列，“G”叫做生成矩陣。說明：如果利用生成矩陣，編碼是只需要保存生成矩陣，即需要n×k比特的存儲空間。思考：是不是可以對生成矩陣的元素任意賦值？該如何得到生成矩陣？第7節(jié)線性分組碼的生成矩陣及編碼第一百一十九頁，共243頁。1、寫出GF(3)上的四維空間的一個三維子空間，列出這個空間的一組基礎(chǔ)矢量。2、寫出五維空間的一個二維子空間，列出該子空間的一組基礎(chǔ)矢量，并指出該子空間的對偶空間。第7節(jié)線性分組碼的生成矩陣及編碼第一百二十頁，共243頁。第7節(jié)線性分組碼的生成矩陣及編碼由第6節(jié)的內(nèi)容我們知道，任何的(n,k)線性分組碼都可以看作域GF(q)n的一個線性子空間，我們可以利用一組基礎(chǔ)矢量來生成這個n重k維線性子空間的全部矢量，換句話說就是可以利用k個線性無關(guān)的碼字的線性組合來得到整個碼空間。2、生成矩陣的構(gòu)成第一百二十一頁，共243頁。假設(shè)我們知道n重k維子空間的k個線性無關(guān)的矢量，則這個空間的所有矢量均可用這k個線性無關(guān)矢量的線性組合表示。即：各矢量線性無關(guān)說明第7節(jié)線性分組碼的生成矩陣及編碼第一百二十二頁，共243頁。同理，如果知道n重k維碼空間的k個線性無關(guān)的碼字Ci(i=1，2，…，k)，則任何一個碼字C都可以用這k個線性無關(guān)碼字的線性組合表示。即：第7節(jié)線性分組碼的生成矩陣及編碼第一百二十三頁，共243頁。這k個線性無關(guān)的碼字可以看作k個線性無關(guān)的n重矢量，可表示以下形式：第7節(jié)線性分組碼的生成矩陣及編碼第一百二十四頁，共243頁。第7節(jié)線性分組碼的生成矩陣及編碼第一百二十五頁，共243頁。由此可以看出，生成矩陣具有以下性質(zhì)：1、生成矩陣的每一行是一個有效碼字，這些碼字線性無關(guān)。2、生成矩陣是一個k行n列的矩陣，它的秩一定等于k。3、信息序列I，碼字C以及生成矩陣G的關(guān)系式為：4、對應(yīng)一種線性分組碼，其生成矩陣不唯一。一個空間可以有不同的基礎(chǔ)矢量組，許用碼字碼空間也是這樣。因此可以選擇k個不同的線性無關(guān)碼字組構(gòu)成不同的生成矩陣。第7節(jié)線性分組碼的生成矩陣及編碼第一百二十六頁，共243頁。第7節(jié)線性分組碼的生成矩陣及編碼例：設(shè)GF(2)上的線性分組碼為C={000,010,101,111}，下面分別用不同的基礎(chǔ)矢量組構(gòu)造生成矩陣。第一百二十七頁，共243頁。由上面的例子可以看出，從qk=22=4個碼字中選取k=2個線性無關(guān)的碼字可以構(gòu)造生成矩陣，兩種不同的生成矩陣得到的許用碼字空間相同。這是一個(3,2)線性分組碼。3、利用生成矩陣編碼第7節(jié)線性分組碼的生成矩陣及編碼第一百二十八頁，共243頁。因此我們可以得到利用生成矩陣進(jìn)行線性分組碼編碼的一般原理方框圖信道譯碼信道信息序列K個符號碼字n個符號K個符號的信息序列分組，送入編碼器中，與生成矩陣相乘，得到n符號的碼字，并將碼字放到信道上。第7節(jié)線性分組碼的生成矩陣及編碼第一百二十九頁，共243頁。第7節(jié)線性分組碼的生成矩陣及編碼例：設(shè)有一個GF(2)上的線性分組碼(7,3,4)，其信息序列及碼字如圖所示信息序列碼字i3i2i1c7c6c5c4c3c2c100000000000010011101010010011101110011101001101001101101001111001110101111110100第一百三十頁，共243頁。第7節(jié)線性分組碼的生成矩陣及編碼如果我們選擇紅色的三個碼字作為基底，即001110101001111001110可以得到如下所示的37生成矩陣通過將簡單地將信息序列與生成矩陣相乘，就可以得到該信息序列對應(yīng)的碼字。第一百三十一頁，共243頁。第7節(jié)線性分組碼的生成矩陣及編碼第一百三十二頁，共243頁。110100110100111110100可得到如下的生成矩陣如果選擇三個綠色的碼字作為基底，即編碼過程如下所示：第7節(jié)線性分組碼的生成矩陣及編碼第一百三十三頁，共243頁。第7節(jié)線性分組碼的生成矩陣及編碼第一百三十四頁，共243頁。由上面的例子可以看出，生成矩陣的不同只會使得信息序列與碼字的對應(yīng)關(guān)系不同，不影響碼空間，也不會使得編碼的最小海明距離不同。4、系統(tǒng)矩陣及系統(tǒng)碼但是在前一個生成矩陣1)系統(tǒng)矩陣和系統(tǒng)碼第7節(jié)線性分組碼的生成矩陣及編碼第一百三十五頁，共243頁。編碼時，我們發(fā)現(xiàn)一個有趣的現(xiàn)象。就是碼字的前3個符號與信息序列相同。同時我們注意到，生成矩陣的前面的3×3的分塊矩陣是一個單位矩陣。假設(shè)生成矩陣可以表示成以下的形式：這樣的生成矩陣叫做系統(tǒng)矩陣，由系統(tǒng)矩陣得到的編碼叫做系統(tǒng)碼。第7節(jié)線性分組碼的生成矩陣及編碼第一百三十六頁，共243頁。若信息序列為M，則有：我們可以直觀看出，碼字中的前k個符號等于信息序列，這就是系統(tǒng)碼的特點。第7節(jié)線性分組碼的生成矩陣及編碼第一百三十七頁，共243頁。2)系統(tǒng)碼的編碼rk信道信息序列K個符號冗余r個符號合并系統(tǒng)碼的編碼方框圖如上所示，利用系統(tǒng)矩陣，可以減小編碼器需要存儲的數(shù)據(jù)，同時大大減小了計算量，因此系統(tǒng)碼是線性分組碼編碼的首選。第7節(jié)線性分組碼的生成矩陣及編碼第一百三十八頁，共243頁。3）、生成矩陣的初等變換如果我們知道一個非系統(tǒng)矩陣的生成矩陣，為了得到一個系統(tǒng)矩陣，是否需要將所有碼字寫出來并選擇適當(dāng)?shù)拇a字構(gòu)成系統(tǒng)矩陣？答案是否定的，我們可以通過矩陣的初等變換來構(gòu)造一個等效的系統(tǒng)矩陣。生成矩陣的初等變換主要包括以下幾個方面：2)矩陣的行乘以一個非0的量。1)矩陣的行與行交換4)矩陣的列與列之間交換。3)矩陣的行與行之間線性相加。第7節(jié)線性分組碼的生成矩陣及編碼第一百三十九頁，共243頁。矩陣行與行之間的變換，不改變碼空間，只會影響信息序列與碼字的對應(yīng)關(guān)系。列與列之間的變換可能會改變碼空間，但兩個碼空間的各自海明距離一定相同，從而這兩種編碼也是等效碼。第7節(jié)線性分組碼的生成矩陣及編碼第一百四十頁，共243頁。例：P534T16設(shè)線性分組碼的生成矩陣為1)運用矩陣的列變換將G變換為系統(tǒng)形式。第7節(jié)線性分組碼的生成矩陣及編碼第一百四十一頁，共243頁。1、6列互換2、4列互換3、6列互換2)寫出生成矩陣G對應(yīng)的所有有效碼字第7節(jié)線性分組碼的生成矩陣及編碼第一百四十二頁，共243頁。第7節(jié)線性分組碼的生成矩陣及編碼第一百四十三頁，共243頁。4)比較兩種編碼的特點和它們的糾檢錯能力，并說明其原因。由G0得到的是系統(tǒng)碼，每個碼字的的前3個比特正好等于對應(yīng)的信息序列。兩種編碼的最小海明距離都是3，能夠糾正所有的一位錯誤或發(fā)現(xiàn)所有的兩位錯誤，糾檢錯能力相同。這是因為G0是由G經(jīng)過初等變換得到，故兩種編碼互為等效碼。第7節(jié)線性分組碼的生成矩陣及編碼第一百四十四頁，共243頁。P534T14，T15作業(yè)：第一百四十五頁，共243頁。信道是有噪聲的，接收到的字通常情況下不是發(fā)送的碼字，此時接收方首先要根據(jù)接收的字判斷信道是否出錯，如果出錯的話，要么請求對方重發(fā)，要么根據(jù)冗余信息將錯誤糾正。這就是譯碼過程了，此前我們并未涉及。這一節(jié)主要給大家介紹線性分組碼的一種譯碼方法－標(biāo)準(zhǔn)陣列譯碼。1、錯誤矢量在介紹譯碼之前，先介紹一下錯誤矢量這個概念。設(shè)發(fā)送碼字矢量為W，接收字矢量為R，接收字矢量與發(fā)送碼字之間的差值即為錯誤矢量E。第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百四十六頁，共243頁。在二進(jìn)制下，加法運算和減法運算相同，即有：發(fā)送碼字(W)101110011000接收字(R)100111010001錯誤矢量(E)001001001001發(fā)送碼字(W))101110011000接收字(R)111001010100錯誤矢量(E)010111001100第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百四十七頁，共243頁。錯誤矢量的海明距離代表接收矢量中出錯的位數(shù)。對于一個(n，k)線性分組碼，海明重量為0的錯誤矢量只有一個，即全0矢量；海明重量為1的錯誤矢量有n個；海明重量為2的錯誤矢量有n(n-1)/2個。依此類推，海明重量為i(n≥i≥0)的錯誤是矢量個數(shù)為：第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百四十八頁，共243頁。2、陪集與陪集首我們知道，碼空間是一個n重k維子空間，也是一個子群，包含有qk個元素，對應(yīng)的群是一個包含qn個元素。任意從群中取一個字，就可以構(gòu)成碼空間的陪集?；ゲ幌嗤呐慵还灿衠(n-k)個。第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百四十九頁，共243頁。例：q=2,n=3,k=2也就是將兩個比特的信息序列編碼成3個比特。其碼空間和完整空間表示為：G={000,001,010,011,100,101,110,111}C={000,011,101,110}陪集1:000+C={000,011,101,110}陪集2:001+C={001,010,100,111}第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百五十頁，共243頁。碼字101110011000陪集1(000)101110011000陪集2(001)100111010001從上面的表中可以看出，如果發(fā)生錯誤為000，則接收矢量為表中第二行所示。如果錯誤矢量為001，則接收矢量為第三行。所有碼空間的陪集實際上代表在某種出錯情況下接收矢量的集合。第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百五十一頁，共243頁。第8節(jié)標(biāo)準(zhǔn)陣列譯碼0010111111有效碼字信息字符c7c6c5c4c3c2c1i3i2i10000000000101110010011100100100111001110100101100111001011010101110011因為k=3，n=7，所有每個陪集中的元素個數(shù)為8，一共有16個陪集，由于篇幅關(guān)系，我只列出了其中的8個陪集。第一百五十二頁，共243頁。第8節(jié)標(biāo)準(zhǔn)陣列譯碼eC…………第一百五十三頁，共243頁。定義：每個陪集中的海明重量最小的一個叫做陪集首。如果有超過一個的元素具有最小海明重量，則任選取一個作為陪集首。第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百五十四頁，共243頁。例：已知群G子群={000,001,010,011,100,101,110,111}及它一個子群S={000,010,101,111}，因此有k=2,n=3。這個子群有兩個不同的陪集。陪集1:000+S=010+S=101+S=111+S={000,010,101,111}陪集2:001+S=011+S=100+S=110+S={001,011,100,110}G=陪集1陪集2第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百五十五頁，共243頁。子群陪集首000010101111000000010101111001001011100110在第一個陪集中，海明在量最小的是000，因此它就是陪集首。在第二個陪集中海明中量最小的元素有兩個，我們?nèi)我膺x取一個作為陪集首，如001。陪集1陪集2由上面的例子我們可以看出，所有的陪集中，只有兩個不同的陪集，這兩個陪集中的元素構(gòu)成了群G中的所有元素。第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百五十六頁，共243頁。c將第一個和第二個陪集中都沒有出現(xiàn)的碼字中海明重量最小的一個作為陪集首，構(gòu)造第三個陪集；如果有多個海明重量最小的一個，則任選一個。d重復(fù)以上過程，直到群中所有的qn個元素出現(xiàn)并且只出現(xiàn)一次。這樣的陪集共有qn-k個。第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百五十七頁，共243頁。從以上分析可以看出，為了找出所有的陪集首并構(gòu)造所有的陪集而不出差錯，一般需要按如下的步驟進(jìn)行：a將全0碼字作為陪集首，構(gòu)造第一個陪集b將第一個陪集中沒有出現(xiàn)的碼字中海明重量最小的一個作為陪集首，構(gòu)造第二個陪集；如果有多個海明重量最小的一個，則任選一個。第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百五十八頁，共243頁。3、標(biāo)準(zhǔn)陣列1)定義：一種(n,k)線性分組碼C的標(biāo)準(zhǔn)陣列是一個qn-kqk的矩陣，每一行對應(yīng)編碼C的一個陪集。2)構(gòu)造標(biāo)準(zhǔn)陣列的步驟：與尋找陪集首的步驟相同。例：寫出GF(2)上的線性分組碼C={0000,1011,0101,1110}的標(biāo)準(zhǔn)陣列。第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百五十九頁，共243頁。例：寫出GF(2)上的線性分組碼C={0000,1011,0101,1110}的標(biāo)準(zhǔn)陣列。首先確定n=4,k=2,q=20000101101011110寫出標(biāo)準(zhǔn)陣列00001011010111100000000100011010010011110010001010010111110010001000001111010110第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百六十頁，共243頁。4、標(biāo)準(zhǔn)陣列譯碼設(shè)信道中每個碼符號出錯的概率為p，則對于GF(2)上的(n,k)線性分組碼，不出錯的概率為一位出錯的概率為二位出錯的概率為下面我們介紹利用標(biāo)準(zhǔn)陣列譯碼的方法。1)標(biāo)準(zhǔn)陣列譯碼條件第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百六十一頁，共243頁。i(n≥i≥1)位出錯的概率為i+1(n-1≥i≥0)位出錯的概率為如果要求：即：第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百六十二頁，共243頁。第8節(jié)標(biāo)準(zhǔn)陣列譯碼其中，互不相同的陪集有滿足個，也就是有個陪集首，其中海明重量為0的有個，海明重量為1的有個，海明重量為2的有個…，海明重量為i的應(yīng)該有小于或等于個。即i為海明重量最大的陪集首的海明重量。第一百六十三頁，共243頁。第8節(jié)標(biāo)準(zhǔn)陣列譯碼若則我可以得到這樣的結(jié)論：不出錯的可能性大于1位出錯的可能性，1位出錯的可能性大于兩位出錯的可能性…，依此類推，n-1位出錯的可能性小于n位出錯的可能性。第一百六十四頁，共243頁。如果單個符號出錯概率大于(i+1)/(n+1)，則上述譯碼不一定成立。因此接收字最可能是離它最近的碼字出錯后而來。也就是說接收到一個字后，將之譯碼成與其海明距離最小的有效碼字時出錯的可能性最小。這就是滿足條件時的譯碼規(guī)則。第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百六十五頁，共243頁。2)標(biāo)準(zhǔn)陣列譯碼在滿足條件時，將接收的字譯碼成與它海明距離最小的有效碼字。一種可行的方法就是將接收字與每個有效碼字相減，比較差值的海明重量，選擇海明重量最小的一個差值作為錯誤矢量。但是這種方法不直觀，而且比較繁瑣。第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百六十六頁，共243頁。回過頭來看看標(biāo)準(zhǔn)陣列，我們可以發(fā)現(xiàn)，如果將每個接收字譯碼成這個字在表中所在列的最上面的一個碼字，恰好能滿足將海明距離最小的有效碼字的條件。因此標(biāo)準(zhǔn)陣列譯碼的譯碼方法就是：將接收的字譯碼它在標(biāo)準(zhǔn)陣列中所在列的最上面一個碼字。第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百六十七頁，共243頁。第8節(jié)標(biāo)準(zhǔn)陣列譯碼例：已知GF(2)上的線性分組碼C={0000,1011,0101,1110}，試?yán)脴?biāo)準(zhǔn)陣列譯碼方法對接收矢量R=1101進(jìn)行譯碼。0000101101011110000000001011010111100001000110100100111100100010100101111100100010000011110101101)寫出標(biāo)準(zhǔn)陣列第一百六十八頁，共243頁。

d(1101,0000)=3,d(1101,1011)=2d(1101,0101)=1,d(1101,1110)=2討論：2)標(biāo)準(zhǔn)陣列譯碼我們發(fā)現(xiàn)1101在第三列，對應(yīng)的碼字為W=0101，對應(yīng)的錯誤矢量為E=1000第8節(jié)標(biāo)準(zhǔn)陣列譯碼第一百六十九頁，共243頁。從上一節(jié)我們知道，通過生成矩陣，大大地提高了線性分組碼地編碼效率。那么能否找到一種類似的方法，用以提高解碼效率呢？答案是肯定的，這就是一致校驗矩陣。一種有效的線性分組碼是一個n重k維子空間，子空間中的每一個矢量對應(yīng)一個碼字。碼空間的對偶空間是一個n重(n-k)維子空間，對偶空間與碼空間正交，因此對偶空間中的任意非0矢量與碼空間中的任意非0矢量正交。1、一致校驗矩陣的定義第9節(jié)一致校驗矩陣第一百七十頁，共243頁。假設(shè)已經(jīng)找到了對偶空間的r個線性無關(guān)矢量，并用這r個矢量構(gòu)成了一個矩陣，那么這個矩陣就叫做一致校驗矩陣，記作：H。碼空間的k個線性無關(guān)矢量的線性組合何以用來表示碼空間的任意矢量，也就是任何碼字。同樣對偶空間的r=n-k個線性無關(guān)的矢量可以表示對偶空間的任意矢量。第9節(jié)一致校驗矩陣第一百七十一頁，共243頁。2、一致校驗矩陣的特征1)一致校驗矩陣是一個r×n階矩陣。2)一致校驗矩陣各行組成的矢量線性無關(guān)。3)若c是任意碼字，H是一致校驗矩陣，則必有：3、一致校驗矩陣與生成矩陣的關(guān)系第9節(jié)一致校驗矩陣第一百七十二頁，共243頁。4、一致校驗矩陣的構(gòu)造假設(shè)已知生成矩陣設(shè)一致校驗矩陣為：第9節(jié)一致校驗矩陣第一百七十三頁，共243頁。由得第9節(jié)一致校驗矩陣第一百七十四頁，共243頁。說明：一致校驗矩陣不唯一，不方便直接求出。如果我們找到一個r×n的矩陣，各行互不相關(guān)，且與生成矩陣的乘積為0矩陣，則這個矩陣就是與該生成矩陣對應(yīng)的一個一致校驗矩陣。第9節(jié)一致校驗矩陣第一百七十五頁，共243頁。定理：若生成矩陣為系統(tǒng)矩陣，即：則矩陣是G0的一致校驗矩陣。證明：因為H0右邊是一個r×r的單位矩陣，所以r個行向量一定線性無關(guān)。生成矩陣確定，則碼空間確定，對偶空間也將確定，但是一致校驗矩陣不唯一。第9節(jié)一致校驗矩陣第一百七十六頁，共243頁。5、一致校驗矩陣與線性分組碼檢糾錯能力的關(guān)系定理：線性分組碼的最小海明距離等于一致校驗矩陣最小線性相關(guān)列向量數(shù)。證明：如果一致校驗矩陣H已知，則對偶空間確定，任何與對偶空間正交的矢量一定落在碼空間。令第9節(jié)一致校驗矩陣第一百七十七頁，共243頁。將一致校驗矩陣按列劃分成n個分塊矩陣，根據(jù)分塊矩陣的乘法可以得到上式。第9節(jié)一致校驗矩陣第一百七十八頁，共243頁。第9節(jié)一致校驗矩陣假設(shè)一致校驗矩陣中有s列線性相關(guān)，即現(xiàn)有一個字滿足則必有：和即：a必然是一個有效碼字，且a的海明重量為s。第一百七十九頁，共243頁。若一致校驗矩陣中有s列線性相關(guān)，則必然至少有一個海明重量為s的碼字。如果一致校驗矩陣中最少有d列線性相關(guān)，則對應(yīng)的碼字的最小海明重量為d，因為線性分組碼的最小海明距離等于其非0碼字的最小海明重量，所有這種編碼的最小海明距離也應(yīng)為d。第9節(jié)一致校驗矩陣第一百八十頁，共243頁。第9節(jié)一致校驗矩陣第一百八十一頁，共243頁。第9節(jié)一致校驗矩陣?yán)河幸粋€(7,4)線性分組碼，其生成矩陣如下：分析試求出其最小海明距離。第一百八十二頁，共243頁。因為第1,2,6列相加為0，且沒有任何兩列相加為0，所以該線性分組碼的最小海明距離為3。第9節(jié)一致校驗矩陣第一百八十三頁，共243頁。例：構(gòu)造一個(4,3,2)線性分組碼。分析：n=4,k=3r=1d*=2第9節(jié)一致校驗矩陣第一百八十四頁，共243頁。第9節(jié)一致校驗矩陣生成矩陣為：第一百八十五頁，共243頁。標(biāo)準(zhǔn)陣列譯碼雖然直觀，但如果n,k太大，存在存儲空間大檢索困難的問題。因此我們要尋求更為方便和快捷的方法，這就是伴隨式譯碼。1、伴隨式（Syndrome癥狀）

我們知道，任何一個有效碼字與一致校驗矩陣的轉(zhuǎn)置的乘積為0矩陣。那么可以得到以下等式:我們把S叫作R的伴隨式。第10節(jié)伴隨式譯碼第一百八十六頁，共243頁。2、譯碼表線性分組碼有多少陪集，就有多上陪集首，就有多少伴隨式。也就是說陪集首與伴隨式一一對應(yīng)。對于GF(q)上的(n,k)線性分組碼,有m=qn-k個陪集，每個陪集首稱為一個錯誤模式，或者叫錯誤圖樣。因此可以得到如下形式的表第10節(jié)伴隨式譯碼第一百八十七頁，共243頁。錯誤圖樣伴隨式E1S1E2S2……EmSm這樣的表稱為譯碼表。第10節(jié)伴隨式譯碼第一百八十八頁，共243頁。3、伴隨式譯碼方法從上面的等式我們可以看出，任何錯誤矢量相同的接收字都具有相同的伴隨式，而標(biāo)準(zhǔn)陣列中的每一行(一個陪集)的所有字都具有相同錯誤矢量，因此具有相同的錯誤矢量，伴隨式相同，也就是具有相同的“癥狀”。因此我們可以用伴隨式確定錯誤矢量，再利用公式：求出接收矢量譯碼后的碼字。第10節(jié)伴隨式譯碼第一百八十九頁，共243頁。第10節(jié)伴隨式譯碼例已知線性分組碼C＝{0000,1011,0101,1110},標(biāo)準(zhǔn)陣列如下圖所示。寫出譯碼表并對接收矢量1111進(jìn)行譯碼。0000101101011110000000001011010111100001000110100100111100100010100101111100100010000011110101101)由C很容易知道：k=2,n=4,n-k=2。其生成矩陣不唯一，為了計算方便選擇系統(tǒng)生成矩陣:第一百九十頁，共243頁。第10節(jié)伴隨式譯碼一致校驗矩陣為：根據(jù)下面的公式第一百九十一頁，共243頁。第10節(jié)伴隨式譯碼很容易計算出每一行的伴隨式相同且為下表中最后一列：0000101101011110伴隨式0000000010110101111000000100011010010011110100100010100101111100101000100000111101011011相應(yīng)的譯碼表為Errorpatternsyndrome000000000101001010100011第一百九十二頁，共243頁。第10節(jié)伴隨式譯碼2)如果接收矢量為R=1111，則其伴隨式為查譯碼表，伴隨式S＝01對應(yīng)的錯誤圖樣為E=0001，所有接收矢量R譯碼后的碼字為：W=R+E=1111+0001=1110與標(biāo)準(zhǔn)陣列譯碼比較，二者譯碼后的結(jié)果完全相同。第一百九十三頁，共243頁。第10節(jié)伴隨式譯碼4、伴隨式譯碼的步驟根據(jù)S=EHT寫出譯碼表計算接收矢量R的伴隨式從譯碼表中找到R的伴隨式所對應(yīng)的錯誤矢量，也就是錯誤圖樣E。從接收矢量R中減去錯誤樣圖E，得到的結(jié)果就是R所對應(yīng)的碼字。第一百九十四頁，共243頁。第10節(jié)伴隨式譯碼5、存在的問題有時需要列出標(biāo)準(zhǔn)陣列之后才能寫出譯碼表，在下一節(jié)我們將了解到，完備碼不需要知道標(biāo)準(zhǔn)陣列就可以直接寫出譯碼表。第一百九十五頁，共243頁。第10節(jié)伴隨式譯碼P535T21設(shè)(6,3)線性分組碼的生成矩陣為1)寫出所有的有效碼字2)排除標(biāo)準(zhǔn)陣列，并進(jìn)行譯碼。3)寫出相應(yīng)的一致校驗矩陣4)寫出譯碼表5)若接收序列為R1＝111100,R2＝100001,R3＝001011,利用譯碼表進(jìn)行譯碼。第一百九十六頁，共243頁。第10節(jié)伴隨式譯碼1)寫出所有的有效碼字第一百九十七頁，共243頁。第10節(jié)伴隨式譯碼0000000011100101010110111000111011011101101110001000001011101101011110110000110011010101100110000100000111100001010010111100111111011001101010000010000001100111010100111010111001011111101100000001000010100100010111111001111010011100101111000000100011000101110110011000011011111101001110100000010011110101000110101000101011001101111110011001001010101100011111110001110010010100100111002)排除標(biāo)準(zhǔn)陣列，并進(jìn)行譯碼。第一百九十八頁，共243頁。第10節(jié)伴隨式譯碼接收的字譯碼成該字在標(biāo)準(zhǔn)陣列中的所在列的最上面一個元素。3)寫出相應(yīng)的一致校驗矩陣第一百九十九頁，共243頁。第10節(jié)伴隨式譯碼4)寫出譯碼表錯誤矢量伴隨式000000000100000011010000101001000110000100100000010010000001001100100111第二百頁，共243頁。第10節(jié)伴隨式譯碼5)若接收序列為R1＝111100,R2＝100001,R3＝001011,利用譯碼表進(jìn)行譯碼。①若R1＝111100，則其伴隨式為：從譯碼表中可以看出，對應(yīng)的錯誤樣圖為：所以譯碼后的碼字為②若R2＝100001，則其伴隨式為：從譯碼表中可以看出，對應(yīng)的錯誤樣圖為：所以譯碼后的碼字為第二百零一頁，共243頁。第10節(jié)伴隨式譯碼③若R3＝001011,則其伴隨式為：從譯碼表中可以看出，對應(yīng)的錯誤樣圖為：所以譯碼后的碼字為第二百零二頁，共243頁。第10節(jié)伴隨式譯碼生成矩陣分組信道分組一致校驗矩陣譯碼表至此，我們寫出線性分組碼編解碼過程的方框圖。在發(fā)送端，利用生成矩陣信源符號進(jìn)行編碼，然后將碼字送入信道。在接收端，利用譯碼表和一致校驗矩陣進(jìn)行解碼。第二百零三頁，共243頁。第11節(jié)線性分組碼的殘留誤碼率在上一節(jié)我們提到，只有當(dāng)單個符號出錯的概率p小于(i+1)/(n+1)時，也就是說i個符號出錯的概率小于i+1個符號出錯的概率時，并且錯誤矢量正好時錯誤圖樣中的一種時，利用標(biāo)準(zhǔn)陣列或伴隨式的譯碼方法才不會出錯。實際上碼字在信道中傳輸時，不同的自然信道單個符號出錯的可能性不同，而且錯誤矢量也不一定是錯誤樣圖。因此，即使經(jīng)過信道編碼、譯碼之后的編碼信道，也可能會出錯，也就是