第17講—— 線性分組碼編碼與譯碼

1、0000010100111001011101110000001001100101101100100011011011011111消息消息碼字碼字碼碼 許用碼字許用碼字 禁用碼字禁用碼字 編碼效率編碼效率漢明重量漢明重量 漢明距離漢明距離 最小漢明距離最小漢明距離糾檢錯能力糾檢錯能力群群 子群子群 分元陪集分元陪集0001 101100000010011001011011消息消息碼字碼字5V35V25V基本概念基本概念000000100110010110110010001101101101111100001010001001111010001010110010111111100001001011

2、1000011001001100111110100111010001101010100011100000111011101010111100分元陪集劃分分元陪集劃分0000010100111001011101110000001001100101101100100011011011011111消息消息碼字碼字碼碼 許用碼字許用碼字 禁用碼字禁用碼字 編碼效率編碼效率漢明重量漢明重量 漢明距離漢明距離 最小漢明距離最小漢明距離糾檢錯能力糾檢錯能力群群 子群子群 分元陪集分元陪集域域GF(2)上的矢量空間上的矢量空間 子空間子空間矢量張成的子空間矢量張成的子空間 基底基底 維數(shù)維數(shù)零化空間零化空間矩

3、陣行空間矩陣行空間0001 101100000010011001011011消息消息碼字碼字5V35V25VGF(2)5V35V25V010010010010110基本概念基本概念線性分組碼線性分組碼長度為長度為n，有，有2k個碼字的碼組，當且僅當這個碼字的碼組，當且僅當這2k個碼字是個碼字是GF(2)上上n維矢量空間的一個維矢量空間的一個k維子空間時，稱為維子空間時，稱為(n,k)線性分組碼，簡稱線性分組碼，簡稱(n,k)碼。碼。由于由于k維子空間是在模維子空間是在模2加法下運算的，構(gòu)成了一個加法加法下運算的，構(gòu)成了一個加法交換群，所以線性分組碼也稱為交換群，所以線性分組碼也稱為群碼群碼。碼

4、率碼率R=k/n， 就是傳輸效率。就是傳輸效率。最小漢明距離最小漢明距離dmin等于非零碼字的最小重量。等于非零碼字的最小重量。系統(tǒng)碼系統(tǒng)碼n-k kk n-k碼字信息位與輸入信息序列相同，并且與校驗位分開碼字信息位與輸入信息序列相同，并且與校驗位分開生成矩陣生成矩陣線性分組碼是線性分組碼是GF(2)上上n維空間中的一個維空間中的一個k維子空間，因維子空間，因此它可以由此它可以由k個線性無關個線性無關n維矢量維矢量 完全確定。完全確定。由于這組矢量的所有線性組合給出了碼由于這組矢量的所有線性組合給出了碼C中的任一個碼中的任一個碼字字 ，稱，稱生成碼生成碼C。110,kgggC中任何一組基底所構(gòu)

5、成的矩陣中任何一組基底所構(gòu)成的矩陣G稱作碼稱作碼C的的生成矩陣生成矩陣1, 11, 11, 11, 11 , 10, 11, 01 , 00, 0110nknknknnknkggggggggggggG生成矩陣生成矩陣對于任何一個給定的信息序列對于任何一個給定的信息序列 ，可指定，可指定),(110kmmmmGmc110110),(kkmmmggg作為相應的碼字。作為相應的碼字。G矩陣的每一行都是一個碼字矢量，分別對應信息位為矩陣的每一行都是一個碼字矢量，分別對應信息位為(100),(0100)(0001)時的碼字。時的碼字。生成矩陣生成矩陣(n,k)分組碼實際上就是這分組碼實際上就是這k個線性

6、無關的碼字矢量張成個線性無關的碼字矢量張成的的k維子空間，這維子空間，這k個矢量組成的矩陣就是生成矩陣。個矢量組成的矩陣就是生成矩陣。確定確定(n,k)碼的生成矩陣的問題實際上就是確定碼的生成矩陣的問題實際上就是確定n重矢重矢量空間中量空間中k維子空間的維子空間的k個線性無關的碼字矢量的問題，個線性無關的碼字矢量的問題，也就是尋找基底的問題。也就是尋找基底的問題。(n,k)碼的碼的n重矢量空間中可以有多個重矢量空間中可以有多個k維子空間，產(chǎn)生維子空間，產(chǎn)生不同的碼組，即有不同的基底。不同的碼組，即有不同的基底。(n,k)碼的碼的n-重矢量空間中的一個重矢量空間中的一個k維子空間的基底可以維子空

7、間的基底可以有多個，因此可以有不同的生成矩陣有多個，因此可以有不同的生成矩陣G，但都產(chǎn)生相，但都產(chǎn)生相同的碼組。同的碼組。基底的線性組合等效于基底的線性組合等效于G的行初等變換，可以產(chǎn)生一組的行初等變換，可以產(chǎn)生一組新的基底。利用這一點，可使生成矩陣具有如下新的基底。利用這一點，可使生成矩陣具有如下“系系統(tǒng)形式統(tǒng)形式”，稱之為典型生成矩陣。，稱之為典型生成矩陣。典型生成矩陣典型生成矩陣即：即：G=Ik Q ，Q為為kr矩陣，矩陣，Ik為為kk單位陣。單位陣。非系統(tǒng)碼與系統(tǒng)碼并無本質(zhì)區(qū)別，它的生成矩陣可非系統(tǒng)碼與系統(tǒng)碼并無本質(zhì)區(qū)別，它的生成矩陣可以通過行初等變換轉(zhuǎn)變?yōu)橄到y(tǒng)形式，這個過程叫做以通過

8、行初等變換轉(zhuǎn)變?yōu)橄到y(tǒng)形式，這個過程叫做系統(tǒng)化。系統(tǒng)化并不會改變碼集，其糾錯能力完全系統(tǒng)化。系統(tǒng)化并不會改變碼集，其糾錯能力完全等價。等價。1, 11, 11, 11, 11 , 10, 11, 01 , 00, 010000010001knknknkknkngggggggggG 例例 題題設二元（設二元（5,3）碼，其生成矩陣為）碼，其生成矩陣為將其化為標準形式？將其化為標準形式？111110001111001G一致校驗矩陣一致校驗矩陣與任何一個與任何一個(n,k)碼的碼空間碼的碼空間C相對應，一定存在一個相對應，一定存在一個對偶空間對偶空間D，它的每個矢量都與，它的每個矢量都與C中的每個矢量

9、正交，中的每個矢量正交，其維數(shù)為其維數(shù)為n-k。事實上，若找出生成空間事實上，若找出生成空間D的基底（的基底（n-k個）用這個）用這n-k個矢量同樣可以生成包含個矢量同樣可以生成包含 個碼字的個碼字的(n,n-k)線性分線性分組碼，我們稱其組碼，我們稱其(n,k)碼的對偶碼，生成矩陣為碼的對偶碼，生成矩陣為kn21, 11 , 10, 11, 11 , 10, 11, 01 , 00, 0110nknknknnnknhhhhhhhhhhhhH一致校驗矩陣一致校驗矩陣由對偶空間的定義知，有對任意的由對偶空間的定義知，有對任意的Cc0cHT即即H可以檢驗一個可以檢驗一個n重是否為碼字，稱重是否為碼

10、字，稱H為碼為碼C的的一致校驗矩陣一致校驗矩陣。1, 11 , 10, 11, 11 , 10, 11, 01 , 00, 0110nknknknnnknhhhhhhhhhhhhH典型一致校驗矩陣典型一致校驗矩陣100000100011, 11, 11, 11, 11 , 10, 11, 01 , 00, 0knknnknnknknknhhhhhhhhhH系統(tǒng)碼的一致校驗矩陣為系統(tǒng)碼的一致校驗矩陣為即即H=P Ir, 其中，其中，Ir為為rr單位陣，單位陣，P為為rk矩陣。矩陣。一致校驗矩陣與生成矩一致校驗矩陣與生成矩陣之間的關系陣之間的關系 由于生成矩陣每一行都是一個碼字，因此應當滿由于生成

11、矩陣每一行都是一個碼字，因此應當滿足一致校驗矩陣所規(guī)定的校驗關系，即應當有：足一致校驗矩陣所規(guī)定的校驗關系，即應當有：GHT=0 或者或者HGT=0 因此因此H與與G互為正交矩陣，說明互為正交矩陣，說明G和和H的行空間的行空間互為零化空間。互為零化空間。一致校驗矩陣與生成矩一致校驗矩陣與生成矩陣之間的關系陣之間的關系對于系統(tǒng)碼，上式可以寫成對于系統(tǒng)碼，上式可以寫成Ik Q P Ir T =0 得得PT+Q= 0所以所以PT =Q 或者或者 P=QT即即P矩陣與矩陣與Q矩陣互為轉(zhuǎn)置矩陣。矩陣互為轉(zhuǎn)置矩陣。對于系統(tǒng)碼，已知校驗矩陣對于系統(tǒng)碼，已知校驗矩陣H就可以確定典型生成矩就可以確定典型生成矩陣

12、陣G，反之，已知生成矩陣也就可以確定校驗矩陣。，反之，已知生成矩陣也就可以確定校驗矩陣。例例 題題【例】設二元【例】設二元(7,4)碼的生成矩陣為碼的生成矩陣為1011000111010011000100110001G求其一致校驗矩陣？求其一致校驗矩陣？【例】設二元【例】設二元(5,3)碼，其生成矩陣為碼，其生成矩陣為111110001111001G求其一致校驗矩陣？求其一致校驗矩陣？線性分組碼編碼線性分組碼編碼 線性分組碼的編碼過程分為兩步：線性分組碼的編碼過程分為兩步： 把信息序列按一定長度分成若干信息碼組，每組由把信息序列按一定長度分成若干信息碼組，每組由 k 位組成；位組成； 編碼器按

13、照預定的編碼器按照預定的線性規(guī)則線性規(guī)則，把信息碼組變換成，把信息碼組變換成 n 重重 (nk) 碼字碼字。 信息碼組長信息碼組長 k 位，有位，有 2k 個不同的信息碼組，則有個不同的信息碼組，則有 2k 個個碼字與它們一一對應。碼字與它們一一對應。一致校驗矩陣編碼一致校驗矩陣編碼設設c=c0,c1,c2,c3,c4,c5,c6，其中，其中，c0,c1,c2,c3為信息為信息位，位，c4,c5,c6為校驗位。為校驗位。 由由HCT=0可知校驗方程為：可知校驗方程為：0123456101110001110010001110010ccccccc c4=c0+c2+c3c5=c0+c1+c2c6=

14、c1+c2+c3信息碼元信息碼元m=1101則編得的碼字則編得的碼字c=1101000 100111001001110011101H生成矩陣編碼生成矩陣編碼1011000111010011000100110001G若信息碼元若信息碼元m=1101，則有，則有c= mG=1101000。100111001001110011101H譯碼準則譯碼準則設發(fā)送碼字為設發(fā)送碼字為c=( c0,c1, cn-1)，由于信道干擾產(chǎn)生差，由于信道干擾產(chǎn)生差錯，反映到接收碼字上可以用一個二元矢量錯，反映到接收碼字上可以用一個二元矢量e表示，表示，e=( e0,e1, en-1) ，稱為，稱為錯誤圖樣錯誤圖樣，其中

15、，其中，ei=1表明相表明相應位有錯，應位有錯，ei=0表明相應位無錯。這時接收碼字可以表表明相應位無錯。這時接收碼字可以表示為示為r=c+e=( c0+e0，c1+e1,cn-1+en-1)譯碼器就是從接收碼字譯碼器就是從接收碼字r得到發(fā)送碼字的估計值，或者得到發(fā)送碼字的估計值，或者說從接收碼字中確定錯誤圖樣說從接收碼字中確定錯誤圖樣e，然后由，然后由c=r-e得到發(fā)送得到發(fā)送碼字的估計值。如果估計正確則譯碼正確，否則譯碼錯碼字的估計值。如果估計正確則譯碼正確，否則譯碼錯誤。誤。如何得到發(fā)送碼字的估計值，根據(jù)什么準則？如何得到發(fā)送碼字的估計值，根據(jù)什么準則？譯碼準則譯碼準則最大后驗概率譯碼最

16、大后驗概率譯碼max()Nmpcv最大似然譯碼最大似然譯碼max()Nmpv c最小距離譯碼最小距離譯碼對于給定的接收矢量，計算它與對于給定的接收矢量，計算它與M個可能的發(fā)個可能的發(fā)送碼字之間的距離，從中選擇能使距離達到最送碼字之間的距離，從中選擇能使距離達到最小的碼字作為判決結(jié)果。小的碼字作為判決結(jié)果。若信道是對稱若信道是對稱DMC信道，其轉(zhuǎn)移概率為信道，其轉(zhuǎn)移概率為1-p和和p/(q-1)，則，則 10)()(NnnnmNcvppcvmmdNdpqp11),(vcmmdd Mm, 1則對數(shù)似然函數(shù)為則對數(shù)似然函數(shù)為pqpdpNpmmN/ ) 1)(1 (ln)1ln()(lncv最大似然譯

17、碼準則可簡化為：最大似然譯碼準則可簡化為：若對所有的若對所有的mm ，有，有0/ ) 1)(1 (ln)(pqpddmm則判定則判定mcc 最小距離譯碼最小距離譯碼最小距離譯碼最小距離譯碼伴隨式伴隨式設碼設碼C的一致校驗矩陣為的一致校驗矩陣為H，接收矢量為，接收矢量為r，定義，定義TknsssrHs),(110稱稱s為接收矢量為接收矢量r的伴隨式。的伴隨式。由伴隨式的定義可知由伴隨式的定義可知s=rHT=(c+e)HT =cHT+eHT=eHT可以看出伴隨式完全由可以看出伴隨式完全由e決定，它充分反映了信道的決定，它充分反映了信道的 干擾情況。如果伴隨式干擾情況。如果伴隨式s0，接收碼字一定有

18、錯誤；，接收碼字一定有錯誤；如果伴隨式如果伴隨式s=0，譯碼器，譯碼器認為認為接收碼字無錯誤。接收碼字無錯誤。1, 11 , 10, 11, 11 , 10, 11, 01 , 00, 0110nknknknnnknhhhhhhhhhhhhH譯碼步驟譯碼步驟由接收碼字由接收碼字r計算伴隨式計算伴隨式sT=HrT若若s=0，則譯碼器，則譯碼器認為認為接收碼字沒錯，否則有錯，并接收碼字沒錯，否則有錯，并由由s計算錯誤圖樣計算錯誤圖樣e由錯誤圖樣進行譯碼，估計發(fā)送的碼字由錯誤圖樣進行譯碼，估計發(fā)送的碼字c=r-e=r+e 其中最困難的是確定錯誤圖樣，即其中最困難的是確定錯誤圖樣，即錯誤定位錯誤定位。

19、如何。如何進行錯誤定位？進行錯誤定位？譯碼思路譯碼思路1根據(jù)根據(jù)sT=HrT=HeT列出線性方程組（含有列出線性方程組（含有n-k個相互獨個相互獨立的方程），通過求解線性方程得到立的方程），通過求解線性方程得到e。 1, 111 , 110, 1011, 111 , 110, 1011, 011 , 010, 000nknnknknknnnnnhehehesheheheshehehes上式有上式有n個未知數(shù)個未知數(shù)e0,e1,en-1 ，有有n-k個方程，因此有多個方程，因此有多解。（伴隨式解。（伴隨式s是一個是一個r=n-k維矢量，共有維矢量，共有 個，而錯個，而錯誤圖樣誤圖樣e是是n維矢量

20、，共有維矢量，共有 個，因此，個，因此，s與與e不存在一一不存在一一對應關系。）最終根據(jù)譯碼準則選取其中一個，常常對應關系。）最終根據(jù)譯碼準則選取其中一個，常常選選取重量最輕的為錯誤圖樣取重量最輕的為錯誤圖樣e的估計值的估計值，從而得到發(fā)送碼，從而得到發(fā)送碼字的估計值，體現(xiàn)最小距離譯碼的思想。字的估計值，體現(xiàn)最小距離譯碼的思想。 kn2n21, 11 , 10, 11, 11 , 10, 11, 01 , 00, 0110nknknknnnknhhhhhhhhhhhhH譯碼思路譯碼思路2 (n,k)分組碼的分組碼的2k個碼字，是個碼字，是n維矢量空間維矢量空間Vn中的一個中的一個k維子空間，它

21、在維子空間，它在GF(2)上是一個子群。利用分元陪集的上是一個子群。利用分元陪集的方法，可以利用該子空間的方法，可以利用該子空間的2k元素，生成元素，生成Vn中的所有中的所有2n個元素。個元素。陪集首陪集首c0c1c2c2k-1e1c1+ e1c2+ e1c2k-1+ e1e2c1+ e2c2+ e2c2k-1+ e2e2r-1c1+ e2r-1c2+ e2r-1c2k-1+ e2r-1陪集首陪集首c0c1c2c2k-1e1c1+ e1c2+ e1c2k-1+ e1e2c1+ e2c2+ e2c2k-1+ e2e2r-1c1+ e2r-1c2+ e2r-1c2k-1+ e2r-1標準陣列譯碼表

22、標準陣列譯碼表譯碼按以下規(guī)則進行譯碼按以下規(guī)則進行：收到碼字：收到碼字R必然在這個表中，必然在這個表中，如果落在表中某一列，譯碼器就譯成第一行的相應如果落在表中某一列，譯碼器就譯成第一行的相應碼字。碼字。非常直觀的譯碼方法，選擇重量最輕的禁用碼字作非常直觀的譯碼方法，選擇重量最輕的禁用碼字作為陪集首，體現(xiàn)最小距離譯碼思想。為陪集首，體現(xiàn)最小距離譯碼思想。 同一陪集中元素的伴隨式都相同，并且，陪集首與伴同一陪集中元素的伴隨式都相同，并且，陪集首與伴隨式矢量有一一對應的關系。根據(jù)這種關系，可以將隨式矢量有一一對應的關系。根據(jù)這種關系，可以將譯碼表簡化。譯碼表簡化。標準陣列譯碼標準陣列譯碼陪集首陪集

23、首c0c1c2c2k-1e1c1+ e1c2+ e1c2k-1+ e1e2c1+ e2c2+ e2c2k-1+ e2e2r-1c1+ e2r-1c2+ e2r-1c2k-1+ e2r-1標準陣列譯碼表標準陣列譯碼表伴隨式伴隨式s0s1s2s2r-1非常直觀的譯碼方法，選擇重量最輕的禁用碼字作非常直觀的譯碼方法，選擇重量最輕的禁用碼字作為陪集首，體現(xiàn)最小距離譯碼思想。為陪集首，體現(xiàn)最小距離譯碼思想。 同一陪集中元素的伴隨式都相同，并且，陪集首與伴同一陪集中元素的伴隨式都相同，并且，陪集首與伴隨式矢量有一一對應的關系。根據(jù)這種關系，可以將隨式矢量有一一對應的關系。根據(jù)這種關系，可以將譯碼表簡化。譯碼表簡化。當當n-k=r較小時較小時(小于小于30)上述標準陣列譯碼方法簡單實上述標準陣列譯碼方法簡單實用。但用。但n進一步大時查表方法就不太實用了，需要找進一步大時查表方法就不太實用了，需要找到更簡化的譯碼方法，或者是具有簡單譯碼方法的編到更簡化的譯碼方法，或者是具有簡單譯碼方法的編碼方法。碼方法。標準陣列譯碼標準陣列譯碼例例 題題設一個設一個(5,2)線性分組碼，其一致校驗矩陣如下線性分組碼，其一致校驗矩陣如下H，(1)寫出所有許用碼字；寫出所有許用碼字；(2)求該碼的最小漢明距離；求該碼的最小漢明距離；