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

2、的分組碼，當(dāng)且僅當(dāng)個(gè)碼字的分組碼，當(dāng)且僅當(dāng)其其2k個(gè)碼字構(gòu)成個(gè)碼字構(gòu)成GF(2)上所有上所有n重矢量空間的一個(gè)重矢量空間的一個(gè)k維子空間時(shí)，稱作維子空間時(shí)，稱作線性線性(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因?yàn)榫€性因?yàn)榫€性(n,k)分組碼分組碼C是一個(gè)是一個(gè)k維子空間，所以在碼維子空間，所以在碼C中中能找到能找到k個(gè)線性獨(dú)立的碼字個(gè)線性獨(dú)立的碼字g0, g1, gk-1,使得使得C中的每個(gè)中的每個(gè)碼字碼字v都是這都是這k個(gè)碼字的一種線性組合，即個(gè)碼字的一種

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

5、1(10113210ggggvv若若u=(1101)，則，則v線性系統(tǒng)分組碼：線性系統(tǒng)分組碼：若若(n,k)線性分組碼線性分組碼C的生成矩的生成矩陣形如陣形如G=P Ik( (或或G=Ik P) )，此時(shí)稱，此時(shí)稱C為線性系為線性系統(tǒng)分組碼。此時(shí)，每個(gè)碼字都可以被分成兩個(gè)部統(tǒng)分組碼。此時(shí)，每個(gè)碼字都可以被分成兩個(gè)部分，即消息部分和冗余部分分，即消息部分和冗余部分10000100001000011, 11 , 10 , 11, 221121, 111101, 00100110knkkkknknknkkppppppppppppIPgggGv關(guān)于線性系統(tǒng)分組碼，對(duì)應(yīng)于消息關(guān)于線性系統(tǒng)分組碼，對(duì)應(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 上面兩個(gè)式子正好反映系統(tǒng)的組成特性，最后這上面兩個(gè)式子正好反映系統(tǒng)的組成特性，最后這n-k個(gè)方個(gè)方程稱為碼程稱為碼C的的一致校驗(yàn)方程一致校驗(yàn)方程1000010000100001,1, 11 , 10 , 11, 221121, 111101, 00100110knkkkknknknkppppppppppppuuuGuvv定義：定義：與與(n,k)線性分組碼線性分組碼C的生成矩陣的生

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

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

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

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

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

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

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

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

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

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

17、小漢明重量的最小漢明重量v線性分組碼線性分組碼C=0000, 1010, 0101, 1111, 其中分組其中分組長(zhǎng)度為長(zhǎng)度為n=4，計(jì)算碼字之間的漢明距離計(jì)算碼字之間的漢明距離 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分組碼的最小碼間距離是決定該碼糾錯(cuò)和

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

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

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

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

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

23、兩個(gè)n重是相同重是相同的，每個(gè)的，每個(gè)n重在且僅在一行中出現(xiàn)重在且僅在一行中出現(xiàn)v性質(zhì)性質(zhì)2的證明：的證明：1)假設(shè)第假設(shè)第l行有行有2個(gè)個(gè)n重是相同的，重是相同的，如對(duì)如對(duì)ij有有el+vi=el+vj，即，即vi=vj，這與標(biāo)準(zhǔn)陣的構(gòu)造，這與標(biāo)準(zhǔn)陣的構(gòu)造相矛盾，故性質(zhì)相矛盾，故性質(zhì)2的第一行得證。的第一行得證。2)首先由定義知首先由定義知每個(gè)每個(gè)n重至少出現(xiàn)一次，假設(shè)一個(gè)重至少出現(xiàn)一次，假設(shè)一個(gè)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行，這與標(biāo)行，這與標(biāo)準(zhǔn)陣的構(gòu)造定義相矛盾。準(zhǔn)陣的構(gòu)造定義相矛盾。v陪集：陪集：標(biāo)準(zhǔn)陣中共有標(biāo)準(zhǔn)陣中共有2n-k行，它們稱為碼行，它們稱為碼C的陪集的陪集v陪集首：陪集首：每個(gè)陪集中的第一個(gè)每個(gè)陪集中的第一個(gè)n重重ei稱為陪集首。稱為陪集首。陪集中的任何一個(gè)元素都可以作為陪集首，需要陪集中的任何一個(gè)元素都可以作為陪集首，需要做置換操作做置換操作v對(duì)于一個(gè)碼字對(duì)于一個(gè)碼字vi，如果信道造成的錯(cuò)誤圖樣是陪，如果信道造成的錯(cuò)誤圖樣是陪集首，則接收矢量集首，則接收矢量r在陪集中，此時(shí)，可以將接收在陪集中，此時(shí)，可以將接收矢量正確的譯碼為矢量正確

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

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

27、v如果接收矢量是如果接收矢量是1101，在標(biāo)準(zhǔn)陣中找到這個(gè)矢，在標(biāo)準(zhǔn)陣中找到這個(gè)矢量的位置，那一列最上面的碼字是量的位置，那一列最上面的碼字是0101，所以，所以估計(jì)的碼字是估計(jì)的碼字是0101，那一行最左邊的矢量是，那一行最左邊的矢量是1000，所以錯(cuò)誤圖樣就是，所以錯(cuò)誤圖樣就是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é)論。但因?yàn)檫@樣的結(jié)論。但因?yàn)閐2t+1, 23,該碼并不該碼并不能糾正所有能糾正所有t=1的錯(cuò)誤圖樣，比如，若傳輸?shù)拇a的錯(cuò)誤圖樣，比如，若傳輸?shù)拇a字是字是00000，接收矢量是，接收矢量是01000，那么，那么， d(01000, 00000)=1, d(01000, 01010)=1, d(01000, 10101)=4, d(01000, 11111)=4, 此時(shí)根據(jù)最小距離譯碼策略就此時(shí)根據(jù)最小距離譯碼策略就無(wú)法清楚地進(jìn)行唯一的判決無(wú)法清楚地進(jìn)行

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

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

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

32、bCav證明：證明：4) 由于由于ba+C表明對(duì)于某個(gè)表明對(duì)于某個(gè)xC, b=a+x。接下來(lái)，如果接下來(lái)，如果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當(dāng)所考慮的碼當(dāng)所考慮的碼C的的n和和k的值都很大的時(shí)候，標(biāo)準(zhǔn)的值都很大的時(shí)候，標(biāo)準(zhǔn)陣列的長(zhǎng)度就變得非常的巨大，此時(shí)，用標(biāo)準(zhǔn)陣陣列的長(zhǎng)度就變得非常的巨大，此時(shí)，用標(biāo)準(zhǔn)陣來(lái)譯碼就變得不實(shí)用了來(lái)譯碼就變得不實(shí)用了v有辦法來(lái)給標(biāo)準(zhǔn)陣降階么？用伴隨式譯

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