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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、在維子空間，它在GF(2)上是一個(gè)子群。利用分元陪集的上是一個(gè)子群。利用分元陪集的方法，可以利用該子空間的方法，可以利用該子空間的2k元素，生成元素，生成Vn中的所有中的所有2n個(gè)元素。個(gè)元素。陪集首陪集首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標(biāo)準(zhǔn)陣列譯碼表

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

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