信息論課件chap6[1]

1、第六章第六章 線性分組碼線性分組碼線性分組碼線性分組碼一、引言一、引言 討論的問題是什么？ 如何尋找合適的分組碼（編碼、譯碼） 問題的由來： 由信道編碼定理可知對(duì)隨機(jī)變量序列X1X2進(jìn)行的信道編碼為(N, L)碼：(X0X1XL-1)(U0U1UN-1)=C(X0X1XL-1)。這個(gè)(N, L)碼又稱為(N, L)分組碼。有如下結(jié)論：當(dāng)RC/H(X)時(shí)存在(N, L)分組碼，使得l信息率(L/N)任意接近Rl譯碼錯(cuò)誤的概率任意接近0 糾錯(cuò)碼的目的：尋找一種在實(shí)際中易于實(shí)現(xiàn)且能達(dá)到有效可靠地通信的編碼方法 總的原理：利用冗余實(shí)現(xiàn)糾檢錯(cuò)線性分組碼線性分組碼二、基本概念1、信息段、信息空間2、碼字、

2、碼空間3、q元分組碼的定義（N、L、D）4、許用序列和禁用序列許用序列：禁用序列：線性碼：線性分組碼線性分組碼5、漢明重量、碼重向量x中非零分量的數(shù)目6、漢明距離兩個(gè)長(zhǎng)為N的q元序列之間對(duì)應(yīng)位不相同的位數(shù)。線性分組碼線性分組碼7、最小漢明距離對(duì)碼整體而言的概念，碼字中所有任意兩個(gè)碼字間漢明距離的最小值。8、 GF（2）上的向量l包含0,1l定義了兩個(gè)運(yùn)算l加法：000，01101，110l乘法：000，010，100，111ld(x,y)=w(x+y)9、矩陣的初等變換10、線性無關(guān)與基矢11、生成矩陣12、系統(tǒng)碼線性分組碼線性分組碼定義定義 取GF(D)上的一個(gè)L行N列的矩陣G，它是滿行秩的

3、。(N, L)分組碼定義為(u0, u1, , uN-1)=(x0, x1, , xL-1)G其中(x0, x1, , xL-1)是信息向量信息向量，(u0, u1, , uN-1)是對(duì)應(yīng)的碼字碼字。（1）稱此碼為D元(N, L)線性分組碼。（2）稱矩陣G為此碼的生成矩陣。生成矩陣生成矩陣生成矩陣生成矩陣lL維子空間的基底lC=x0g0+x1g1+xL-1gL-100010,1010111,111,01,11,11NNLLLNLggggggggGgggg(7,4)漢明碼漢明碼消息序列碼字消息序列碼字000000010010001101000101011001110000000101000111

4、10010010001101101001100101100011000101111000100110101011110011011110111111010000111001001101010010110101100000110101011101111111結(jié)論結(jié)論1 不同的信息向量對(duì)應(yīng)不同的碼字域GF(D)上的一個(gè)L行N列的矩陣（LN階的矩陣）G，設(shè)它是滿行秩的。則變換(u0, u1, , uN-1)=(x0, x1, , xL-1)G一定是單射【即(x0, x1, , xL-1)的不同值一定變換為(u0, u1, , uN-1)的不同值)】。證明：證明： 設(shè)u(1)=x(1)G， u(2)=

5、x(2)G ，且x(1)x(2)。要證明u(1)u(2)。根據(jù)線性性質(zhì)，u(1)-u(2)=(x(1)-x(2)G，因?yàn)?x(1)-x(2)全0的L維向量，所以(x(1)-x(2)G是G的各行的非0線性組合。G滿行秩，所以(x(1)-x(2)G全0的N維向量。所以u(píng)(1)u(2)。生成矩陣生成矩陣結(jié)論結(jié)論2 生成矩陣G的第1行是信息向量(1, 0, 0, , 0)的碼字；生成矩陣G的第2行是信息向量(0, 1, 0, , 0)的碼字；生成矩陣G的第L行是信息向量(0, , 0, 0, 1)的碼字。生成矩陣生成矩陣結(jié)論結(jié)論3 信息向量(x0, x1, , xL-1)的碼字是：C=x0g0+x1g

6、1+uL-1gL-1x0數(shù)乘G的第1行，加x1數(shù)乘G的第2行，加，加xL-1數(shù)乘G的第L行。 結(jié)論結(jié)論4 當(dāng)u(1)和u(2)都是碼字， u(1)+u(2)也是碼字。（線性分組碼的碼字關(guān)于線性運(yùn)算封閉）證明證明 ： 設(shè)u(1)是信息向量x(1)的碼字：u(1)=x(1)G；u(2)是信息向量x(2)的碼字：u(2)=x(2)G。則u(1)+u(2)=x(1)G+x(2)G=(x(1)+x(2)G，即u(1)+u(2)是信息向量(x(1)+x(2)的碼字。證完l一個(gè)一個(gè)N維向量是一個(gè)碼字，當(dāng)且僅當(dāng)它是維向量是一個(gè)碼字，當(dāng)且僅當(dāng)它是G的第的第1行行第第L行的線性行的線性組合。組合。l線性分組碼的碼

7、字集合構(gòu)成一個(gè)線性空間。這個(gè)線性空間是線性分組碼的碼字集合構(gòu)成一個(gè)線性空間。這個(gè)線性空間是L維維的，因?yàn)樯删仃嚨?，因?yàn)樯删仃嘒的第的第1行行第第L行恰好是該線性空間的一組基。行恰好是該線性空間的一組基。生成矩陣生成矩陣結(jié)論結(jié)論5 設(shè)一個(gè)D元(N, L)線性分組碼的生成矩陣為G。設(shè)另一個(gè)D元(N, L)線性分組碼的生成矩陣為G=MG，其中M是L階可逆方陣。則兩個(gè)碼的碼字集合完全重合，只是信息向量與碼字的對(duì)應(yīng)關(guān)系不同。結(jié)論的通俗描述為：如果把線性分組碼的生成矩陣G做可逆行變換變成另一個(gè)生成矩陣，則不改變碼字集合，只改變信息向量與碼字的對(duì)應(yīng)關(guān)系。 生成矩陣生成矩陣證明：證明： 證明的核心思想是證

8、明，第一個(gè)碼中任一個(gè)碼字也是第二個(gè)碼中的碼字；第二個(gè)碼中任一個(gè)碼字也是第一個(gè)碼中的碼字。設(shè)在第一個(gè)碼中，u是信息向量x的碼字：則u=xG；那么在第二個(gè)碼中，因?yàn)?u= xM-1G =xM-1MG=xG 。所以其是信息向量xM-1的碼字。設(shè)在第二個(gè)碼中，u是信息向量x的碼字：則u=xG；那么在第一個(gè)碼中，因?yàn)閡= xMG=xMM-1G =xG，所以 u是信息向量xM的碼字。證完 生成矩陣生成矩陣結(jié)論結(jié)論2 生成矩陣G的第1行是信息向量(1, 0, 0, , 0)的碼字；生成矩陣G的第2行是信息向量(0, 1, 0, , 0)的碼字；生成矩陣G的第L行是信息向量(0, , 0, 0, 1)的碼字。

9、系統(tǒng)碼系統(tǒng)碼系統(tǒng)碼系統(tǒng)碼例：例：二元(7, 4)碼生成矩陣如下：是由信息向量(1000)、(0100)、(0010)、(0001)的碼字組成的4行。1000101010011100101100001011G系統(tǒng)碼系統(tǒng)碼例：例：二元(5, 3)線性分組碼的生成矩陣如下 111110110000111G100110101100111100110110000111111110110000111將其進(jìn)行初等行變換，變成如下模式：系統(tǒng)碼系統(tǒng)碼定義：定義：D元(N, L)線性分組碼的生成矩陣為G=PL(N-L), IL，其中IL是L階單位陣， PL(N-L)是(N-L)L階矩陣。則稱此碼為系統(tǒng)碼。此時(shí)信息

10、向量(x0, x1, , xL-1)的碼字是(u0, u1, , uN-1)=(x0, x1, , xL-1)G=(x0, x1, , xL-1) PL(N-L), x0, x1, , xL-1)。碼字的后L位恰好是信息向量(x0, x1, , xL-1)，稱為碼字的信息位。稱碼字的前N-L位為碼字的一致校驗(yàn)位。系統(tǒng)碼系統(tǒng)碼校驗(yàn)位信息位10001010100111001011000010114210ggggG生成矩陣生成矩陣01012301623212310120023(,)(,)gguxx x x xu uugguxxxuxxxuxxxG校驗(yàn)矩陣校驗(yàn)矩陣lC的對(duì)偶空間VlCV=0lV的生成矩

11、陣H是G的校驗(yàn)矩陣lV的維數(shù)是N-K000TTTcHHGGH校驗(yàn)矩陣校驗(yàn)矩陣1, 11 , 10, 11, 111101, 00100110nknknknnnknhhhhhhhhhHhhh校驗(yàn)矩陣校驗(yàn)矩陣結(jié)論：結(jié)論：（1）一個(gè)線性分組碼有很多一致校驗(yàn)矩陣。一個(gè)一致校驗(yàn)矩陣H經(jīng)過可逆行變換變?yōu)镠， H是同一個(gè)線性分組碼的另一個(gè)一致校驗(yàn)矩陣。（2）一個(gè)N維向量u是一個(gè)碼字，當(dāng)且僅當(dāng)：uHT=全0的N-L維行向量。（3）設(shè)一個(gè)D元(N, L)線性分組碼的生成矩陣G，一致校驗(yàn)矩陣H。則H是一個(gè)D元(N, N-L)線性分組碼的生成矩陣，G是此碼的一致校驗(yàn)矩陣。稱這兩個(gè)碼互為對(duì)偶碼。 校驗(yàn)矩陣校驗(yàn)矩陣（4

12、）設(shè)D元(N, L)線性分組碼是系統(tǒng)碼，生成矩陣為G=P, IL，其中IL是L階單位陣，P是L(N-L)階矩陣。則一致校驗(yàn)矩陣可以取為H=IN-L, -PT，其中IN-L是N-L階單位陣，PT是P 的轉(zhuǎn)置矩陣。證明：證明： GHT=P, IL IN-L, -PTT=P-P=OL(N-L) 證完。 （5）設(shè)D元(N, L)線性分組碼的生成矩陣經(jīng)過可逆行變換后變?yōu)镻, IL，則一致校驗(yàn)矩陣也可以取為H=IN-L, -PT。生成矩陣和校驗(yàn)矩陣的關(guān)系生成矩陣和校驗(yàn)矩陣的關(guān)系10001010100111001011000010114210ggggG111010001110101101001H錯(cuò)誤圖樣錯(cuò)誤

13、圖樣信道干擾Xm10101010Ym10101011CV錯(cuò)誤圖樣錯(cuò)誤圖樣011011011(,)(,),(,)NNnnnNu uuv vvevue eeuvevue錯(cuò)誤圖樣最小漢明距離譯碼最小漢明距離譯碼l什么是漢明距離 d(x,y), x,y中分量不同的數(shù)目l最大似然比譯碼l離散無記憶對(duì)稱信道) 1/()|(1)|(Kpijppiip最小漢明距離譯碼最小漢明距離譯碼/ ) 1)(1ln(),()1ln()1ln(),(1ln),()|(ln)|(ln1pKpxydpNpxydNKpxydxypxypmmmNnmiim最小漢明距離譯碼最小漢明距離譯碼l最小漢明距離譯碼準(zhǔn)則給定輸出值y，尋找碼字

14、u使d(y, u)最小。將輸出值y譯為碼字ul譯碼的最佳性與不足需要計(jì)算大量最小距離l舉例(7,4)漢明碼漢明碼消息序列碼字消息序列碼字00000001001000110100010101100111000000010100011110010010001101101001100101100011000101111000100110101011110011011110111111010000111001001101010010110101100000110101011101111111伴隨式伴隨式TTTTknTHHHHssseececvHs)(),(110伴隨式伴隨式結(jié)論：結(jié)論：（1）當(dāng)兩個(gè)錯(cuò)誤

15、圖樣相同時(shí)，它們的伴隨式相同。即：伴隨式s的值僅僅與信道傳輸錯(cuò)誤有關(guān)，與輸入信道的碼字無關(guān)。證明：證明： s=yHT=(u+e)HT=uHT+eHT= eHT。（2）兩個(gè)錯(cuò)誤圖樣的伴隨式相同，當(dāng)且僅當(dāng)它們的差向量是碼字。證明：證明： 設(shè)有兩個(gè)差錯(cuò)向量e(1)和e(2)。e(1)HT=e(2)HT，當(dāng)且僅當(dāng)(e(1)-e(2)HT=全0的N-L維行向量，當(dāng)且僅當(dāng)(e(1)-e(2)是碼字。伴隨式伴隨式（3）給定一個(gè)差錯(cuò)向量e。則與e具有相同伴隨式的所有差錯(cuò)向量恰好是e加上所有碼字。即：設(shè)s是一個(gè)伴隨式。以s為伴隨式的全體差錯(cuò)向量， 就是以s為伴隨式的一個(gè)差錯(cuò)向量加上全體碼字。（4）伴隨式s是N-

16、L維行向量，因此有DN-L個(gè)不同的伴隨式。差錯(cuò)向量e是N維行向量，因此有DN個(gè)不同的差錯(cuò)向量。具有相同伴隨式的差錯(cuò)向量的個(gè)數(shù)為DL。DLDN-L=DN。 伴隨式和錯(cuò)誤的關(guān)系伴隨式和錯(cuò)誤的關(guān)系ls0,有錯(cuò)誤出現(xiàn)lS=0le0，沒有錯(cuò)誤le=ci, 不可檢錯(cuò)誤l不可檢錯(cuò)誤概率CccwcwncwudppCp0)()()()1 ()(7,4)漢明碼漢明碼消息序列碼字消息序列碼字000000010010001101000101011001110000000101000111100100100011011010011001011000110001011110001001101010111100110111

17、10111111010000111001001101010010110101100000110101011101111111重量分布矢量重量分布矢量lAi碼中重量為i的碼字?jǐn)?shù)目NiiniiudppACp1)1 ()(陪集陪集 l將DN個(gè)可能的向量分為DN-L個(gè)集合l集合中每個(gè)向量的伴隨式相同l這樣的集合稱為陪集l選擇陪集中重量最輕的向量作為陪集代表，稱為陪集首。陪集陪集結(jié)論：結(jié)論：對(duì)信道的輸出向量y，計(jì)算伴隨式s=yHT，以s為地址查找陪集首e(s)，計(jì)算u=y- e(s)。則u就是在所有碼字中與y的Hamming距離最小的碼字。證明證明 ： 首先，u=y- e(s)是碼字。這是因?yàn)閡HT=y

18、HT- e(s)HT=s-s=全0的N-L維行向量。其次，對(duì)任意另一個(gè)碼字c，(y- c)HT=yHT- cHT=yHT=s。這就是說，(y- c)是以s為伴隨式的一個(gè)差錯(cuò)向量。另一方面，(y- u)=e(s)是以s為伴隨式的Hamming重量最小的差錯(cuò)向量。所以w(y- u)w(y- c)，即d(y, u)w(y, c)。證完。 譯碼步驟譯碼步驟l計(jì)算接收矢量的伴隨式l由伴隨式確定陪集首l將陪集首作為錯(cuò)誤圖樣elC=v-e標(biāo)準(zhǔn)陣標(biāo)準(zhǔn)陣12121121212121111112100000kknknknknkkceceesceceesccces伴隨式陪集首陪集例例6.1.8 求一致校驗(yàn)矩陣；碼字

19、集合；譯碼預(yù)計(jì)算（簡(jiǎn)化計(jì)算量）。 顯然是系統(tǒng)碼。100011010101001110G011100101010110001H標(biāo)準(zhǔn)陣標(biāo)準(zhǔn)陣標(biāo)準(zhǔn)陣標(biāo)準(zhǔn)陣信息向量碼字000 000000100 011100010 101010001 110001110 110110101 101101011 011011111 000111伴隨式s陪集首e(s)000 000000100 100000010 010000001 001000011 000100101 000010110 000001111 100100(6,3)碼的標(biāo)準(zhǔn)陣碼的標(biāo)準(zhǔn)陣0010011111000001000100000100010000

20、01000100011000010101000110101011011101000001110000111101010011100000000000陪集首伴隨式正確譯碼概率正確譯碼概率niiniillwnlwcpppppkn0120)()()1 ()1 (第l個(gè)陪集首的重量重量為i的陪集首的數(shù)量分析：分析：設(shè)信道的輸入為碼字u，信道的輸出為向量y，差錯(cuò)向量為e=y-u。則（1）檢錯(cuò)問題：檢錯(cuò)是如何實(shí)現(xiàn)的？通過校驗(yàn)矩陣來判斷，即以yHT的結(jié)果來判定，其本質(zhì)還是看y是否屬于碼集lw(e)dmin：因?yàn)閥HT肯定不是全0的N-L維向量，因而必然可以發(fā)現(xiàn)信道傳輸錯(cuò)誤。（原因？）lw(e) dmin ：

21、因?yàn)閥HT有時(shí)候可以是全0的N-L維向量，所以不一定能發(fā)現(xiàn)信道傳輸錯(cuò)誤。（原因？） 結(jié)論1：線性分組碼的最小距離為dmin則其可以檢測(cè)所有dmin-1位錯(cuò)誤。糾檢錯(cuò)能力糾檢錯(cuò)能力分析：分析：設(shè)信道的輸入為碼字u，信道的輸出為向量y，差錯(cuò)向量為e=y-u。則（2）糾錯(cuò)問題：糾錯(cuò)是如何實(shí)現(xiàn)的？通過陪集首來判斷，即以標(biāo)準(zhǔn)陣來判定，其本質(zhì)是通過最小漢明距離來加以判斷。lw(e)(dmin-1)/2（下方取整） ：因?yàn)榘凑諏?shí)際譯碼準(zhǔn)則不會(huì)與其它碼字產(chǎn)生歧義，因而必然可以發(fā)現(xiàn)并糾正信道傳輸錯(cuò)誤。（原因？）糾檢錯(cuò)能力糾檢錯(cuò)能力證明：證明：（1）當(dāng)w(e)(dmin-1)/2 w(e)=d(y,u)。 因此，

22、所有碼字中，u與y的Hamming距離最小。所以按照最小漢明距離譯碼準(zhǔn)則可以譯碼。證完。糾檢錯(cuò)能力糾檢錯(cuò)能力分析：分析：設(shè)信道的輸入為碼字u，信道的輸出為向量y，差錯(cuò)向量為e=y-u。則（3）超出糾錯(cuò)當(dāng)w(e)(dmin-1)/2（下方取整），通過最小漢明距離未必將y譯為u（即此時(shí)不能保證糾錯(cuò)）。糾檢錯(cuò)能力糾檢錯(cuò)能力證明：證明： 設(shè)信道的輸入為碼字u，另一個(gè)碼字c恰好滿足d(c, u)= dmin。輸出向量y如下：d(c, u)= d(c, y)+d(y,u)； （三角不等式變?yōu)榈仁剑﹚(e)=d(y,u)=(dmin-1)/2+1(dmin-1)/2。請(qǐng)注意，這樣的輸出向量y存在！而且此時(shí)d(c, y)= d(c, u)-d(y,u)=dmin-(dmin-1)/2+1=dmin-1-(dmin-1)/2。糾檢錯(cuò)能力糾檢錯(cuò)能力d(y,u)=(dmin-1)/2+1；d(c, y)=dmin-1-(dmin-1)/2。當(dāng)dmin是奇數(shù)時(shí)，d(y,u)=(dmin-1)/2+1，d(c, y)= (dmin-1)/2，故d(c, y)(dmin-1)/2 ，則e未必是s=eHT的陪集首。糾檢錯(cuò)能力糾檢錯(cuò)能力最小距離和糾錯(cuò)能力的關(guān)系最小距離和糾錯(cuò)能力的關(guān)系l碼的最小距離為dmin,可以糾錯(cuò)的最大數(shù)目為21mindt定理定理1： 設(shè)真正的差錯(cuò)向量為e。w(e)t時(shí)肯定正確譯碼，當(dāng)且