編碼理論第3章

1、v分組碼：分組碼：將消息序列分組進行編碼將消息序列分組進行編碼v在分組碼中，二元信息序列被分成長度固定的一在分組碼中，二元信息序列被分成長度固定的一組組消息；每組組組消息；每組消息消息u有有k個信息位，共有個信息位，共有2k個不個不同的消息同的消息v編碼器按照一定規(guī)則將每個輸入消息編碼器按照一定規(guī)則將每個輸入消息u變換成二變換成二元元n重重v，nk，這個二元，這個二元n重重v稱作消息稱作消息u的的碼字碼字或碼矢。所有或碼矢。所有2k個碼字組成的集合稱作是分組碼個碼字組成的集合稱作是分組碼v線性分組碼：線性分組碼：具有線性性質(zhì)的分組碼具有線性性質(zhì)的分組碼v定義：定義：長為長為n，有，有2k個碼字

2、的分組碼，當且僅當個碼字的分組碼，當且僅當其其2k個碼字構(gòu)成個碼字構(gòu)成GF(2)上所有上所有n重矢量空間的一個重矢量空間的一個k維子空間時，稱作維子空間時，稱作線性線性(n,k)分組碼分組碼message（0 0 0 0）（1 0 0 0）（0 1 0 0）（1 1 0 0）（0 0 1 0）（1 0 1 0）（0 1 1 0）（1 1 1 0）（0 0 0 1）（1 0 0 1）（0 1 0 1）（1 1 0 1）（0 0 1 1）（0 1 1 1）（1 1 1 1）Code words（0 0 0 0 0 0 0）（1 1 0 1 0 0 0）（0 1 1 0 1 0 0）（1 0 1 1

3、 1 0 0）（1 1 1 0 0 1 0）（0 0 1 1 0 1 0）（1 0 0 0 1 1 0）（0 1 0 1 1 1 0）（1 0 1 0 0 0 1）（0 1 1 1 0 0 1）（1 1 0 0 1 0 1）（0 0 0 1 1 0 1）（0 1 0 0 0 1 1）（0 0 1 0 1 1 1）（1 1 1 1 1 1 1）v因為線性因為線性(n,k)分組碼分組碼C是一個是一個k維子空間，所以在碼維子空間，所以在碼C中中能找到能找到k個線性獨立的碼字個線性獨立的碼字g0, g1, gk-1,使得使得C中的每個中的每個碼字碼字v都是這都是這k個碼字的一種線性組合，即個碼字的一種

4、線性組合，即v=u0g0+u1g1+uk-1gk-1v將這將這k個線性獨立的碼字作為行，得到個線性獨立的碼字作為行，得到kn階矩陣階矩陣v此矩陣稱為碼此矩陣稱為碼C的的生成矩陣生成矩陣。線性線性(n,k)分組碼任何分組碼任何k個線個線性獨立的碼字都可以用來構(gòu)成性獨立的碼字都可以用來構(gòu)成碼碼C的生成矩陣的生成矩陣111110111110100100110nkkknnkggggggggggggGv如果本章如果本章PPT第第3頁的表格所表示的線性分頁的表格所表示的線性分組碼，有如下的生成矩陣組碼，有如下的生成矩陣10001010100111001011000010113210ggggG)000110

5、1(10113210ggggvv若若u=(1101)，則，則v線性系統(tǒng)分組碼：線性系統(tǒng)分組碼：若若(n,k)線性分組碼線性分組碼C的生成矩的生成矩陣形如陣形如G=P Ik( (或或G=Ik P) )，此時稱，此時稱C為線性系為線性系統(tǒng)分組碼。此時，每個碼字都可以被分成兩個部統(tǒng)分組碼。此時，每個碼字都可以被分成兩個部分，即消息部分和冗余部分分，即消息部分和冗余部分10000100001000011, 11 , 10 , 11, 221121, 111101, 00100110knkkkknknknkkppppppppppppIPgggGv關(guān)于線性系統(tǒng)分組碼，對應(yīng)于消息關(guān)于線性系統(tǒng)分組碼，對應(yīng)于消

6、息u=(u0, u1, uk-1)的碼的碼字是字是v=(v0, v1, vn-1)=uG=uP Ik，即，即 vn-k+i=ui , 0ik-1, vj=u0P0j+u1P1j+uk-1Pk-1j, 0jn-k-1 上面兩個式子正好反映系統(tǒng)的組成特性，最后這上面兩個式子正好反映系統(tǒng)的組成特性，最后這n-k個方個方程稱為碼程稱為碼C的的一致校驗方程一致校驗方程1000010000100001,1, 11 , 10 , 11, 221121, 111101, 00100110knkkkknknknkppppppppppppuuuGuvv定義：定義：與與(n,k)線性分組碼線性分組碼C的生成矩陣的生

7、成矩陣G相對應(yīng)相對應(yīng)有一個有一個(n-k)n階矩陣階矩陣H，它的，它的n-k個行是碼個行是碼C的的對偶空間的一組基底，該矩陣對偶空間的一組基底，該矩陣H稱為碼稱為碼C的的一致一致校驗矩陣校驗矩陣v因此，一個因此，一個n重重v是由是由G生成的碼中的碼字，當且生成的碼中的碼字，當且僅當僅當vHT=0v對偶碼：對偶碼：以以H為生成矩陣得到的為生成矩陣得到的(n,n-k)碼稱為碼碼稱為碼C的的對偶碼對偶碼，記為，記為Cdv若碼若碼C的生成矩陣具有系統(tǒng)形式的生成矩陣具有系統(tǒng)形式G=P Ik，則其，則其一致校驗矩陣形如一致校驗矩陣形如H=In-k PTv定理：定理：如果線性碼如果線性碼C是是H矩陣的零化空

8、間，矩陣的零化空間，則對每一個重量為則對每一個重量為w的碼矢，的碼矢，H中有相應(yīng)中有相應(yīng)的的w列線性相關(guān)。反之，列線性相關(guān)。反之，H中若有中若有w列線性列線性相關(guān)，那么就有相應(yīng)的重量為相關(guān)，那么就有相應(yīng)的重量為w的一個碼的一個碼矢矢0,12121niiiTnnThvhhhvvvvHv(7,4)線性碼的生成矩陣和一致校驗矩陣線性碼的生成矩陣和一致校驗矩陣100111001001110011101,1011000111010011000100110001HGv設(shè)設(shè)(n,k)線性分組碼線性分組碼C的生成矩陣為的生成矩陣為G，其校驗矩，其校驗矩陣為陣為H，令，令v=(v0, v1, vn-1)是經(jīng)有擾

9、信道傳送的是經(jīng)有擾信道傳送的碼字，碼字，r=(r0, r1, rn-1)是信道輸出端的接收矢量。是信道輸出端的接收矢量。稱矢量和稱矢量和e=v+r=( (e0, e1, en-1) )為為錯誤矢量錯誤矢量v伴隨式：伴隨式：當接收到當接收到r后，譯碼器計算下述后，譯碼器計算下述n-k重重S=rHT =(s0, s1, sn-k-1)，稱，稱S為為r的伴隨式的伴隨式v當且僅當是一個碼字當且僅當是一個碼字(即無傳輸錯誤即無傳輸錯誤)時有時有S=0，否則錯誤矢量本身就是一個碼字，此時出現(xiàn)了不否則錯誤矢量本身就是一個碼字，此時出現(xiàn)了不可檢錯誤。只要碼可檢錯誤。只要碼C設(shè)計適當，就幾乎不會出現(xiàn)設(shè)計適當，就

10、幾乎不會出現(xiàn)不可檢錯誤。不可檢錯誤。v根據(jù)根據(jù)伴隨式定義，伴隨式定義， S=rHT =(v+e)HT=vHT+eHT=eHT，展開后，有，展開后，有v從上式容易看出，從上式容易看出，伴隨式是錯誤圖樣的組合伴隨式是錯誤圖樣的組合，即伴隨式包含了一定程度的錯誤圖樣信息，因即伴隨式包含了一定程度的錯誤圖樣信息，因而可以用來糾錯而可以用來糾錯伴隨式糾錯伴隨式糾錯1, 111, 111,0111 , 1111101110, 111010000knknknknknknknknknknknknknknpepepeespepepeespepepeesv上述方程有上述方程有2k個解，即，對同一個伴隨式，個解，即

11、，對同一個伴隨式，存在存在2k個可能的錯誤圖樣，因此上述方程個可能的錯誤圖樣，因此上述方程雖然包含錯誤圖樣的信息，但是實際應(yīng)用雖然包含錯誤圖樣的信息，但是實際應(yīng)用起來糾錯困難。實際中的糾錯，都是如何起來糾錯困難。實際中的糾錯，都是如何有效地從這些錯誤圖樣中選取真正的錯誤有效地從這些錯誤圖樣中選取真正的錯誤圖樣，從而得到正確的發(fā)送矢量。圖樣，從而得到正確的發(fā)送矢量。對于對于BSC信道，最可能的錯誤圖樣是非零數(shù)字信道，最可能的錯誤圖樣是非零數(shù)字最少的那個最少的那個v考慮某考慮某(7,4)碼，令碼，令v=(1001011)是發(fā)送碼字，是發(fā)送碼字，r=(1001001)是接收矢量，收到是接收矢量，收到

12、r后首先計算后首先計算S=rHT =(111)，由伴隨式和錯誤圖樣的關(guān)，由伴隨式和錯誤圖樣的關(guān)系方程有：系方程有：1=e0+e3+e5+e6, 1=e1+e3+e4+e5, 1=e2+e4+e5+e6, 則得到則得到24=16個錯誤圖樣個錯誤圖樣(0000010), (1010011), (0111011),其中其中(0000010)是非零分量最少的圖樣，考慮是非零分量最少的圖樣，考慮BSC信道，則信道，則(0000010)是最為可能的錯誤是最為可能的錯誤矢量，因而確定矢量，因而確定v=r+e=(1001001)+ (0000010)=(1001011)v漢明重量：漢明重量：令令v=(v0,

13、v1, vn-1)是二元是二元n重，重，v的漢明重量的漢明重量w(v)定義為定義為v中非零分量的個中非零分量的個數(shù)數(shù)v漢明距離漢明距離：令令u=(u0, u1, un-1)和和v=(v0, v1, vn-1)是兩個二元是兩個二元n重，重，u和和v之間的漢之間的漢明距離明距離d(u, v)定義為定義為u+v的漢明重量。的漢明重量。v漢明距離的性質(zhì)：漢明距離的性質(zhì)：1)非負性，非負性，d(u, v)0；2) d(u, v)=0，當且僅當，當且僅當u=v的時候；的時候；3)對稱性：對稱性： d(u, v) =d(v, u) ；4)三角不等式：三角不等式： d(u, v)+d(v, w)d(u, w)

14、v重量分布：重量分布：對于一個分組碼而言，每個碼對于一個分組碼而言，每個碼字都有一個字都有一個漢明重量，不同的碼字可能具漢明重量，不同的碼字可能具有相同的漢明重量，若記有相同的漢明重量，若記Ai為碼中漢明重為碼中漢明重量為量為i的碼字個數(shù)，則稱的碼字個數(shù)，則稱A0, A1, An是該是該碼的重量分布，其中碼的重量分布，其中n是碼長是碼長v兩個碼字兩個碼字0100,1111, ,它們的漢明重量它們的漢明重量w(0100)=1, w(1111)=4, 其漢明距離其漢明距離d(0100, 1111)=3v若將若將(n,k)線性分組碼線性分組碼C與其對偶碼與其對偶碼Cd的重量分布的重量分布分別記為分別

15、記為A0, A1, An和和B0, B1, Bn ，又記，又記多項式多項式v那么多項式那么多項式A(z)和和B(z)之間滿足如下關(guān)系之間滿足如下關(guān)系 niiiniiizBzBzAzA00, zzBzzAnkn1112v定理定理：令令C是一致校驗矩陣為是一致校驗矩陣為H的的(n,k)線性線性碼，對于漢明重量為碼，對于漢明重量為l的每個碼矢，在的每個碼矢，在H中中都有都有l(wèi)列，使得這列，使得這l列的矢量和為列的矢量和為0，反之，反之，若若H中存在中存在l列，其矢量和為列，其矢量和為0，則，則C中必有中必有一個漢明重量為一個漢明重量為l的碼矢。的碼矢。v定義：定義：在在(n,k)碼中，任意兩個碼字之

16、間都有一個碼中，任意兩個碼字之間都有一個漢明距離，兩組不同碼字之間可能有相同的漢明漢明距離，兩組不同碼字之間可能有相同的漢明距離。若記距離。若記Di(0in)為距離為為距離為i的碼字組數(shù)，那的碼字組數(shù)，那么稱么稱D0, D1, Dn為此分組碼的為此分組碼的距離分布距離分布，并，并且稱能夠使且稱能夠使Di0的那個最小整數(shù)的那個最小整數(shù)i為該碼的為該碼的最小最小碼間距離碼間距離。v對線性分組碼而言，重量分布與距離分布是一回對線性分組碼而言，重量分布與距離分布是一回事。特別的，有如下定理事。特別的，有如下定理v定理：定理：(n,k)線性碼的最小碼間距離等于非零碼字線性碼的最小碼間距離等于非零碼字的最

17、小漢明重量的最小漢明重量v線性分組碼線性分組碼C=0000, 1010, 0101, 1111, 其中分組其中分組長度為長度為n=4，計算碼字之間的漢明距離計算碼字之間的漢明距離 d(0000, 1010) = 2, d(0000, 0101) = 2, d(0000, 1111) = 4, d(1010, 0101) = 4, d(1010, 1111) = 2, d(0101, 1111) = 2. 該碼的最小距離是該碼的最小距離是2, , 并且該碼的最小重量也是并且該碼的最小重量也是2 所以最小距離和最小重量是相等的。所以最小距離和最小重量是相等的。v分組碼的最小碼間距離是決定該碼糾錯和

18、分組碼的最小碼間距離是決定該碼糾錯和檢錯能力的重要指標檢錯能力的重要指標v定理：定理：設(shè)設(shè)(n,k)線性碼線性碼C的最小碼間距離為的最小碼間距離為d，則則1)若若dt+1，則碼，則碼C能檢測能檢測t個隨機錯誤；個隨機錯誤；2)若若d2t+1，則碼，則碼C能糾正能糾正t個隨機錯誤；個隨機錯誤；3)若若dt+e+1，則碼，則碼C能糾正能糾正t(te)個隨機錯誤，個隨機錯誤，同時還能檢測同時還能檢測e個隨機錯誤。個隨機錯誤。v因此，若碼因此，若碼C的最小漢明距離的最小漢明距離d越大，則該越大，則該碼的糾錯和檢錯能力就越強碼的糾錯和檢錯能力就越強v例例1：碼碼C1=000,111，碼的最小距離是，碼的

19、最小距離是3，因此重量為因此重量為1和和2個錯誤圖樣可以被檢測出個錯誤圖樣可以被檢測出來，即錯誤圖樣如果為來，即錯誤圖樣如果為011,101,110,001, 010,100，就可以被檢測出來。，就可以被檢測出來。v例例2：對于碼對于碼C2=001,110,101，碼的最小，碼的最小距離是距離是1，由于，由于d-1=0，所以我們什么都不，所以我們什么都不能說。重量為能說。重量為1的錯誤圖樣的錯誤圖樣010可以被檢測可以被檢測出來，但是該碼不能檢測所有重量為出來，但是該碼不能檢測所有重量為1的的錯誤圖樣，比如錯誤圖樣錯誤圖樣，比如錯誤圖樣100就不能被檢測就不能被檢測出來。出來。v定理：定理：

20、(n,k)線性碼線性碼C的最小碼間距離的最小碼間距離d滿足滿足dn-k+1。該定理給出了。該定理給出了d的上界。的上界。v最大距離可分碼：最大距離可分碼：若若(n,k)線性碼的最小碼線性碼的最小碼間距離間距離d滿足滿足d=n-k+1 ，那么稱此種碼為，那么稱此種碼為最大距離可分碼，簡稱最大距離可分碼，簡稱MDS碼。碼。v令令C是一致校驗矩陣為是一致校驗矩陣為H的的(n,k)線性碼：線性碼： 1) 若若H中沒有中沒有d-1列或者更少的列矢量和為列或者更少的列矢量和為0，則則C的最小碼間距離至少為的最小碼間距離至少為d 2) C的最小碼間距離等于的最小碼間距離等于H中和為中和為0的最小的最小列數(shù)列

21、數(shù)v令令(n,k)線性碼線性碼C的所有碼字是的所有碼字是 接收矢量接收矢量r是一個是一個n重，則按如下的方式構(gòu)造碼重，則按如下的方式構(gòu)造碼C的標準陣：的標準陣：kvv21,.,kknknknknkkkveveveeveveveeveveveevvvviiii2222222332332222222210v步驟步驟1：在第一行寫下所有合法的在第一行寫下所有合法的2k個碼字個碼字v=v1, v2k，第一個碼字為全零碼字；，第一個碼字為全零碼字；v步驟步驟2：選擇一個第一行沒有出現(xiàn)的矢量作選擇一個第一行沒有出現(xiàn)的矢量作為為e2，標準陣第，標準陣第2行寫行寫e2+v；v步驟步驟3：繼續(xù)選擇一個第一行和第

22、二行都沒繼續(xù)選擇一個第一行和第二行都沒有出現(xiàn)的矢量有出現(xiàn)的矢量e3 ，標準陣第，標準陣第3行寫行寫e3+v；v步驟步驟4：依次類推，直到依次類推，直到GF(2n)中所有的矢中所有的矢量都被列出來一次。量都被列出來一次。v考慮碼考慮碼C=0000,1011,0101,1110，對應(yīng)的標準，對應(yīng)的標準陣就是陣就是1100011110010010101000011111010001101101001110001110010110110000碼字碼字陪集首陪集首v性質(zhì)性質(zhì)1：同一行中任意兩個同一行中任意兩個n重之和為一個碼字重之和為一個碼字v性質(zhì)性質(zhì)2：在標準陣中，同一行沒有兩個在標準陣中，同一行沒有

23、兩個n重是相同重是相同的，每個的，每個n重在且僅在一行中出現(xiàn)重在且僅在一行中出現(xiàn)v性質(zhì)性質(zhì)2的證明：的證明：1)假設(shè)第假設(shè)第l行有行有2個個n重是相同的，重是相同的，如對如對ij有有el+vi=el+vj，即，即vi=vj，這與標準陣的構(gòu)造，這與標準陣的構(gòu)造相矛盾，故性質(zhì)相矛盾，故性質(zhì)2的第一行得證。的第一行得證。2)首先由定義知首先由定義知每個每個n重至少出現(xiàn)一次，假設(shè)一個重至少出現(xiàn)一次，假設(shè)一個n重在第重在第l行和第行和第m行行(lm)都出現(xiàn)，則必存在都出現(xiàn)，則必存在i，使得該，使得該n重等于重等于el+vi，且存在，且存在j，使得該，使得該n重等于重等于em+vj，即有，即有em=el+

24、(vi+vj)=el+vs，這意味著，這意味著em在第在第l行，這與標行，這與標準陣的構(gòu)造定義相矛盾。準陣的構(gòu)造定義相矛盾。v陪集：陪集：標準陣中共有標準陣中共有2n-k行，它們稱為碼行，它們稱為碼C的陪集的陪集v陪集首：陪集首：每個陪集中的第一個每個陪集中的第一個n重重ei稱為陪集首。稱為陪集首。陪集中的任何一個元素都可以作為陪集首，需要陪集中的任何一個元素都可以作為陪集首，需要做置換操作做置換操作v對于一個碼字對于一個碼字vi，如果信道造成的錯誤圖樣是陪，如果信道造成的錯誤圖樣是陪集首，則接收矢量集首，則接收矢量r在陪集中，此時，可以將接收在陪集中，此時，可以將接收矢量正確的譯碼為矢量正確

25、的譯碼為vi；否則，若信道造成的錯誤；否則，若信道造成的錯誤圖樣不是陪集首，則會造成錯誤譯碼。當且僅當圖樣不是陪集首，則會造成錯誤譯碼。當且僅當錯誤圖樣為陪集首時，譯碼正確。錯誤圖樣為陪集首時，譯碼正確。v定理：定理：陪集首是可糾正的錯誤圖樣，共有陪集首是可糾正的錯誤圖樣，共有2n-k個可個可糾正的錯誤圖樣糾正的錯誤圖樣v基于標準陣的譯碼策略：基于標準陣的譯碼策略：如果接收矢量如果接收矢量r落落在標準陣中的第在標準陣中的第i行第行第j列，那么就將列，那么就將r譯碼譯碼為為vj，同時錯誤圖樣為，同時錯誤圖樣為ei，即，即r=ei+vjv最小距離譯碼策略：最小距離譯碼策略：如果出現(xiàn)了不可糾正如果出

26、現(xiàn)了不可糾正錯誤圖樣，就出現(xiàn)了譯碼錯誤。對錯誤圖樣，就出現(xiàn)了譯碼錯誤。對BSC信信道，為了使譯碼錯誤概率最小，可以選擇道，為了使譯碼錯誤概率最小，可以選擇漢明重量最小的漢明重量最小的n重做為陪集首，由此導出重做為陪集首，由此導出了最小距離譯碼策略，即將接收矢量了最小距離譯碼策略，即將接收矢量r譯碼譯碼為與為與r的漢明距離最小的那個碼字的漢明距離最小的那個碼字v考慮碼考慮碼C=0000,1011,0101,1110，對應(yīng)的標準，對應(yīng)的標準陣就是陣就是1100011110010010101000011111010001101101001110001110010110110000碼字碼字陪集首陪集首

27、v如果接收矢量是如果接收矢量是1101，在標準陣中找到這個矢，在標準陣中找到這個矢量的位置，那一列最上面的碼字是量的位置，那一列最上面的碼字是0101，所以，所以估計的碼字是估計的碼字是0101，那一行最左邊的矢量是，那一行最左邊的矢量是1000，所以錯誤圖樣就是，所以錯誤圖樣就是1000v考慮碼考慮碼C=00000,01010,10101,11111，該碼的最，該碼的最小距離是小距離是2。如果傳輸?shù)拇a字是。如果傳輸?shù)拇a字是11111，接收的矢，接收的矢量是量是11110，那么，那么，d(11110, 00000)=4, d(11110, 01010)=2, d(11110, 10101)=3

28、, d(11110, 11111)=1, 用最小距離譯碼策略，可以得出傳輸?shù)拇a字就是用最小距離譯碼策略，可以得出傳輸?shù)拇a字就是11111這樣的結(jié)論。但因為這樣的結(jié)論。但因為d2t+1, 23,該碼并不該碼并不能糾正所有能糾正所有t=1的錯誤圖樣，比如，若傳輸?shù)拇a的錯誤圖樣，比如，若傳輸?shù)拇a字是字是00000，接收矢量是，接收矢量是01000，那么，那么， d(01000, 00000)=1, d(01000, 01010)=1, d(01000, 10101)=4, d(01000, 11111)=4, 此時根據(jù)最小距離譯碼策略就此時根據(jù)最小距離譯碼策略就無法清楚地進行唯一的判決無法清楚地進行

29、唯一的判決v對轉(zhuǎn)移概率為對轉(zhuǎn)移概率為p的二元對稱信道而言，陪的二元對稱信道而言，陪集首的重量分布集首的重量分布A0, A1, An與譯碼錯誤與譯碼錯誤概率之間滿足概率之間滿足v定理：定理：對碼間最小距離為對碼間最小距離為d的的(n,k)線性碼，線性碼，重量重量w(d-1)/2=t的的n重都可以被用作標準陣重都可以被用作標準陣的陪集首，并且至少有一個重量為的陪集首，并且至少有一個重量為t+1的的n重不能作為陪集首重不能作為陪集首v注：注：此定理再次顯示了碼此定理再次顯示了碼C能糾正能糾正t個錯誤，個錯誤，但是不能糾正所有但是不能糾正所有t+1個錯誤個錯誤 niiniippAEP011v定理：定理

30、：若若C是是GF(q)上的一個上的一個(n,k)線性碼，則線性碼，則1)長長度為度為n的矢量的矢量b一定在碼一定在碼C的某個陪集中；的某個陪集中；2)每個每個陪集都包含陪集都包含qk個矢量；個矢量；3)兩個陪集要么是不相交兩個陪集要么是不相交的要么就是重合的的要么就是重合的(即相互部分重疊是不可能的即相互部分重疊是不可能的)；4)如果如果a+C是碼是碼C的一個陪集，且有的一個陪集，且有ba+C，那，那么一定有么一定有b+C=a+Cv證明：證明：1) b=b+0b+C；2) 對于所有的對于所有的xC, ,由由xa+x定義的映射定義的映射Ca+C是個一一映射，是個一一映射，所以陪集所以陪集a+C中

31、矢量的個數(shù)和碼集中碼矢中矢量的個數(shù)和碼集中碼矢的個數(shù)相等，即的個數(shù)相等，即qkv證明：證明：3) 反證法。假設(shè)陪集反證法。假設(shè)陪集a+C和和b+C是相是相交的，即它們至少有一個向量是相同的，交的，即它們至少有一個向量是相同的，令令v=(a+C)(b+C)，那么對于任意的，那么對于任意的x,yC，有有v=a+x=b+y, b=a+x+y=a+z,其中其中zC，這，這是根據(jù)碼字集合的封閉性，兩個碼字之和是根據(jù)碼字集合的封閉性，兩個碼字之和仍然是一個碼字，因此仍然是一個碼字，因此b+C=a+z+C=a+C+z或者或者 類似的，還可以得到類似的，還可以得到 所以所以( (b+C)=(a+C)CaCbC

32、bCav證明：證明：4) 由于由于ba+C表明對于某個表明對于某個xC, b=a+x。接下來，如果接下來，如果b+yb+C，那么，那么b+y=(a+x)+y =a+(x+y)a+C, ,即即v另一方面，類似的，如果另一方面，類似的，如果a+za+C，那么，那么a+z=(b+x)+z=b+(x+z)b+C , ,即即v因此因此b+C=a+CCaCbCbCav當所考慮的碼當所考慮的碼C的的n和和k的值都很大的時候，標準的值都很大的時候，標準陣列的長度就變得非常的巨大，此時，用標準陣陣列的長度就變得非常的巨大，此時，用標準陣來譯碼就變得不實用了來譯碼就變得不實用了v有辦法來給標準陣降階么？用伴隨式譯

33、碼有辦法來給標準陣降階么？用伴隨式譯碼v定理：定理：一個陪集的所有一個陪集的所有2k個個n重有同樣的伴隨式。重有同樣的伴隨式。不同陪集的伴隨式不同不同陪集的伴隨式不同 證明：證明：如果如果x,y屬于同一個陪集，那么屬于同一個陪集，那么)()(0ysxsyHxHHyxCyxCyCxTTTv考慮碼考慮碼C=0000,1011,0101,1110，對應(yīng)的標準對應(yīng)的標準陣就是陣就是100111001100011110010010101000011111010001101101001110001110010110110000碼字碼字陪集首陪集首伴隨式伴隨式v步驟步驟1：計算接收矢量計算接收矢量r的伴隨式的伴隨式rHTv步驟步驟2：確定伴隨式等于確