信息論與編碼-第六章3

1、信息論與編碼-線性分組碼 上次課回顧 線性分組碼信息論與編碼-線性分組碼上次課小結(jié)： 信道編碼定理： )(RNEeeP信息論與編碼-線性分組碼上次課小結(jié)： 信道編碼定理： 差錯控制的途徑： 增加碼長、增加帶寬、提高信噪比、噪聲均化 )(RNEeeP信息論與編碼-線性分組碼上次課小結(jié)： 信道編碼定理： 差錯控制的途徑： 增加碼長、增加帶寬、提高信噪比、噪聲均化 碼距與檢錯糾錯的關(guān)系 )(RNEeeP1mindeecd信息論與編碼-信道編碼 最優(yōu)譯碼與最大似然譯碼 信息論與編碼-信道編碼 最優(yōu)譯碼與最大似然譯碼 最優(yōu)譯碼： )/(max2, 2, 1RCpCiiik信息論與編碼-信道編碼 最優(yōu)譯碼

2、與最大似然譯碼 最優(yōu)譯碼： 最大似然譯碼： )/(max2, 2, 1RCpCiiik)/(max2 , 2 , 1iiiCRpCk信息論與編碼-信道編碼 最優(yōu)譯碼與最大似然譯碼 最優(yōu)譯碼： 最大似然譯碼： 當輸入符號集符號概率相等時，二者等價。)/(max2, 2, 1RCpCiiik)/(max2 , 2 , 1iiiCRpCk信息論與編碼-信道編碼 最優(yōu)譯碼與最大似然譯碼 最優(yōu)譯碼： 最大似然譯碼： 當輸入符號集符號概率相等時，二者等價。 漢明距離、碼字重量、硬判決譯碼)/(max2, 2, 1RCpCiiik)/(max2 , 2 , 1iiiCRpCk信息論與編碼-線性分組碼一、線性

3、分組碼的基本概念信息論與編碼-線性分組碼信息論與編碼-線性分組碼一、線性分組碼的基本概念信息論與編碼-線性分組碼一、線性分組碼的基本概念分組碼是建立在碼的代數(shù)結(jié)構(gòu)基礎(chǔ)上的，所以對分組碼的討論和分析需要一定的代數(shù)基礎(chǔ)。信息論與編碼-線性分組碼一、線性分組碼的基本概念分組碼是建立在碼的代數(shù)結(jié)構(gòu)基礎(chǔ)上的，所以對分組碼的討論和分析需要一定的代數(shù)基礎(chǔ)。在這里我們不準備系統(tǒng)地學習代數(shù)知識，只介紹一些相關(guān)的內(nèi)容。信息論與編碼-線性分組碼（1）域（Field）的概念信息論與編碼-線性分組碼（1）域（Field）的概念域是定義了兩種代數(shù)運算的系統(tǒng)。信息論與編碼-線性分組碼（1）域（Field）的概念域是定義了兩

4、種代數(shù)運算的系統(tǒng)。所謂代數(shù)系統(tǒng)，是指滿足一定規(guī)律或定律的系統(tǒng)，系統(tǒng)中有一群元素構(gòu)成的集合、定義了一些運算等。信息論與編碼-線性分組碼（1）域（Field）的概念域是定義了兩種代數(shù)運算的系統(tǒng)。所謂代數(shù)系統(tǒng)，是指滿足一定規(guī)律或定律的系統(tǒng)，系統(tǒng)中有一群元素構(gòu)成的集合、定義了一些運算等。在域中定義的兩種算術(shù)運算是：（i）加法（ii）乘法信息論與編碼-信道編碼（i）加法：o 集合F在加法運算下是封閉的，即如果 必有 。,FbaFba信息論與編碼-信道編碼（i）加法：o 集合F在加法運算下是封閉的，即如果 必有 。o 滿足加法交換律，即,FbaFbaabba信息論與編碼-信道編碼（i）加法：o 集合F在加

5、法運算下是封閉的，即如果 必有 。o 滿足加法交換律，即o 集合中一定包含一個零元素，滿足,FbaFbaabbaaa0信息論與編碼-信道編碼（i）加法：o 集合F在加法運算下是封閉的，即如果 必有 。o 滿足加法交換律，即o 集合中一定包含一個零元素，滿足o 集合中每個元素都有其逆元素，元素a的逆記為-a，有a+(-a)=a-b,FbaFbaabbaaa0信息論與編碼-信道編碼（ii）乘法：o 集合F在乘法運算下是封閉的，即如果 ，則必有,FbaFab信息論與編碼-信道編碼（ii）乘法：o 集合F在乘法運算下是封閉的，即如果 ，則必有o 滿足乘法結(jié)合律，即,FbaFabcabbca)()(信息

6、論與編碼-信道編碼（ii）乘法：o 集合F在乘法運算下是封閉的，即如果 ，則必有o 滿足乘法結(jié)合律，即o 滿足乘法交換律，即,FbaFabcabbca)()(baab 信息論與編碼-信道編碼（ii）乘法：o 集合F在乘法運算下是封閉的，即如果 ，則必有o 滿足乘法結(jié)合律，即o 滿足乘法交換律，即o 滿足乘法分配律，即,FbaFabcabbca)()(baab bcaccba )(信息論與編碼-信道編碼（ii）乘法：o 集合F在乘法運算下是封閉的，即如果 ，則必有o 滿足乘法結(jié)合律，即o 滿足乘法交換律，即o 滿足乘法分配律，即o 集合中一定有一個單位元I，對任何 有,FbaFabcabbca)

7、()(baab bcaccba )(,FaaaI 信息論與編碼-信道編碼（ii）乘法：o 集合F在乘法運算下是封閉的，即如果 ，則必有o 滿足乘法結(jié)合律，即o 滿足乘法交換律，即o 滿足乘法分配律，即o 集合中一定有一個單位元I，對任何 有o 除零元素外，集合中每一個元素都有逆元素。,FbaFabcabbca)()(baab bcaccba )(,FaaaI 信息論與編碼-信道編碼當域由有限個元素組成時，叫做有限域，也稱為伽羅華（Galois Field）域，記為GF(q)，其中q是域中元素的個數(shù)。信息論與編碼-信道編碼當域由有限個元素組成時，叫做有限域，也稱為伽羅華（Galois Field

8、）域，記為GF(q)，其中q是域中元素的個數(shù)。在一個GF(q)域中，加法和乘法都是模q運算。信息論與編碼-信道編碼當域由有限個元素組成時，叫做有限域，也稱為伽羅華（Galois Field）域，記為GF(q)，其中q是域中元素的個數(shù)。在一個GF(q)域中，加法和乘法都是模q運算。例如在GF(5)中：)5(mod243),5(mod023),5(mod243信息論與編碼-信道編碼（2）矢量空間信息論與編碼-信道編碼（2）矢量空間由初等數(shù)學可知，平面上的二維矢量的全體構(gòu)成一個二維的矢量空間，空間的三維矢量全體構(gòu)成三維矢量空間。推廣可以得到一般的n維矢量空間。nRV信息論與編碼-信道編碼（2）矢量空

9、間由初等數(shù)學可知，平面上的二維矢量的全體構(gòu)成一個二維的矢量空間，空間的三維矢量全體構(gòu)成三維矢量空間。推廣可以得到一般的n維矢量空間。例如：實數(shù)域R上的n重數(shù)組全體 組成一線性空間。 nRV)2();,(21GFaaaain信息論與編碼-信道編碼（2）矢量空間由初等數(shù)學可知，平面上的二維矢量的全體構(gòu)成一個二維的矢量空間，空間的三維矢量全體構(gòu)成三維矢量空間。推廣可以得到一般的n維矢量空間。例如：實數(shù)域R上的n重數(shù)組全體 組成一線性空間。 GF(2)上的n重數(shù)組全體 組成一線性空間 。);,(21RaaaainnRV)2();,(21GFaaaainnV2信息論與編碼-信道編碼在線性空間中，能張成該

10、空間的線性獨立矢量的集合稱為該空間的基底。信息論與編碼-信道編碼在線性空間中，能張成該空間的線性獨立矢量的集合稱為該空間的基底。n個n重（n個GF(q)域元素的有序排列）線性無關(guān)的矢量可以構(gòu)成一個n維矢量空間。信息論與編碼-信道編碼在線性空間中，能張成該空間的線性獨立矢量的集合稱為該空間的基底。n個n重（n個GF(q)域元素的有序排列）線性無關(guān)的矢量可以構(gòu)成一個n維矢量空間。取其中的k個可以張成n維空間的一個子空間。信息論與編碼-信道編碼在線性空間中，能張成該空間的線性獨立矢量的集合稱為該空間的基底。n個n重（n個GF(q)域元素的有序排列）線性無關(guān)的矢量可以構(gòu)成一個n維矢量空間。取其中的k個

11、可以張成n維空間的一個子空間。例如：由（1，0，0）,（0，1，0）,（0，0，1）為基底可以張成一個三維三重空間，信息論與編碼-信道編碼在線性空間中，能張成該空間的線性獨立矢量的集合稱為該空間的基底。n個n重（n個GF(q)域元素的有序排列）線性無關(guān)的矢量可以構(gòu)成一個n維矢量空間。取其中的k個可以張成n維空間的一個子空間。例如：由（1，0，0）,（0，1，0）,（0，0，1）為基底可以張成一個三維三重空間，取其中的兩個為基底可以構(gòu)成一個二維三重空間。信息論與編碼-信道編碼在線性空間中，能張成該空間的線性獨立矢量的集合稱為該空間的基底。n個n重（n個GF(q)域元素的有序排列）線性無關(guān)的矢量可

12、以構(gòu)成一個n維矢量空間。取其中的k個可以張成n維空間的一個子空間。例如：由（1，0，0）,（0，1，0）,（0，0，1）為基底可以張成一個三維三重空間，取其中的兩個為基底可以構(gòu)成一個二維三重空間。以互相正交的基底張成的兩個空間也正交，并互稱為另一個空間的零空間。這兩個空間對偶。信息論與編碼-信道編碼（3）線性分組碼一個n，k分組碼，是把信息劃成k個為一段（稱為信息組），通過編碼器變成長為n個碼元的一組，作為n，k分組碼的一個碼字。則共可能有 個碼字。k2信息論與編碼-信道編碼如果這些碼字集合組成一個k維線性空間，則稱它是一個n，k線性分組碼。信息論與編碼-信道編碼如果這些碼字集合組成一個k維線

13、性空間，則稱它是一個n，k線性分組碼。因此，對于線性分組碼，如果 是碼字，則 必定也是碼字。jiCC 、jiCC21信息論與編碼-信道編碼如果這些碼字集合組成一個k維線性空間，則稱它是一個n，k線性分組碼。因此，對于線性分組碼，如果 是碼字，則 必定也是碼字。其中 是碼元字符集里的任意兩個元素。jiCC 、jiCC2121、信息論與編碼-信道編碼如果這些碼字集合組成一個k維線性空間，則稱它是一個n，k線性分組碼。因此，對于線性分組碼，如果 是碼字，則 必定也是碼字。其中 是碼元字符集里的任意兩個元素。因為一個定義了加法的域一定有零元素，如果取 ，則得到的碼字一定是全零碼。jiCC 、jiCC2

14、121、021信息論與編碼-信道編碼如果這些碼字集合組成一個k維線性空間，則稱它是一個n，k線性分組碼。因此，對于線性分組碼，如果 是碼字，則 必定也是碼字。其中 是碼元字符集里的任意兩個元素。因為一個定義了加法的域一定有零元素，如果取 ，則得到的碼字一定是全零碼。因此，線性分組碼一定包含全零碼。jiCC 、jiCC2121、021信息論與編碼-信道編碼如果這些碼字集合組成一個k維線性空間，則稱它是一個n，k線性分組碼。因此，對于線性分組碼，如果 是碼字，則 必定也是碼字。其中 是碼元字符集里的任意兩個元素。因為一個定義了加法的域一定有零元素，如果取 ，則得到的碼字一定是全零碼。因此，線性分組

15、碼一定包含全零碼。因此：jiCC 、jiCC2121、021),()()(),(0kkjijiCdisCWCCWCCdisd信息論與編碼-信道編碼也就是說：（i）兩個碼字之間的距離必定等于另一個碼字的重量，信息論與編碼-信道編碼也就是說：（i）兩個碼字之間的距離必定等于另一個碼字的重量，所以線性分組碼的最小碼距 等于碼集中非零碼字的最小重量：mindmin0,miniCCCCWdii信息論與編碼-信道編碼也就是說：（i）兩個碼字之間的距離必定等于另一個碼字的重量，所以線性分組碼的最小碼距 等于碼集中非零碼字的最小重量：（ii）研究兩兩碼字之間的距離，可用碼字與全零碼的距離，或各碼字自身的重量來

16、代替。mindmin0,miniCCCCWdii信息論與編碼-信道編碼對于n，k二進制分組碼，共有 個碼字，可以看成是n維n重空間S的一個子空間。k2信息論與編碼-信道編碼對于n，k二進制分組碼，共有 個碼字，可以看成是n維n重空間S的一個子空間。這個子空間是由k個基底張成的，記作碼空間C，它是一個k維n重空間。k2信息論與編碼-信道編碼對于n，k二進制分組碼，共有 個碼字，可以看成是n維n重空間S的一個子空間。這個子空間是由k個基底張成的，記作碼空間C，它是一個k維n重空間。n維n重空間的另外n-k個基底則張成一個n-k維的子空間，稱為校驗空間H。k2信息論與編碼-信道編碼對于n，k二進制分

17、組碼，共有 個碼字，可以看成是n維n重空間S的一個子空間。這個子空間是由k個基底張成的，記作碼空間C，它是一個k維n重空間。n維n重空間的另外n-k個基底則張成一個n-k維的子空間，稱為校驗空間H。分組編碼器的工作，就是要把k維k重的信息組空間的 個矢量一一對應到k維n重碼空間C。k2k2信息論與編碼-信道編碼對于n，k二進制分組碼，共有 個碼字，可以看成是n維n重空間S的一個子空間。這個子空間是由k個基底張成的，記作碼空間C，它是一個k維n重空間。n維n重空間的另外n-k個基底則張成一個n-k維的子空間，稱為校驗空間H。分組編碼器的工作，就是要把k維k重的信息組空間的 個矢量一一對應到k維n

18、重碼空間C。因此，編碼算法就要研究兩個問題：（i）如何確定碼空間C，和（ii）如何映射。k2k2信息論與編碼-信道編碼二、生成矩陣和校驗矩陣信息論與編碼-信道編碼二、生成矩陣和校驗矩陣n，k分組碼的編碼問題就是要在n維線性空間中，找出滿足一定要求的由 個矢量組成的k維n重線性子空間，或者說，要由k個信息碼元得到n-k個冗余碼元。k2信息論與編碼-信道編碼二、生成矩陣和校驗矩陣n，k分組碼的編碼問題就是要在n維線性空間中，找出滿足一定要求的由 個矢量組成的k維n重線性子空間，或者說，要由k個信息碼元得到n-k個冗余碼元。設(shè) 是一組k個信息組，可以寫成矢量形式 。k2kmmm,21),(21kmm

19、mm信息論與編碼-信道編碼二、生成矩陣和校驗矩陣n，k分組碼的編碼問題就是要在n維線性空間中，找出滿足一定要求的由 個矢量組成的k維n重線性子空間，或者說，要由k個信息碼元得到n-k個冗余碼元。設(shè) 是一組k個信息組，可以寫成矢量形式 。編碼器輸出的是k維n重碼空間C的一個矢量，記為 。k2kmmm,21),(21kmmmm),(21iniiiCCCC信息論與編碼-信道編碼二、生成矩陣和校驗矩陣n，k分組碼的編碼問題就是要在n維線性空間中，找出滿足一定要求的由 個矢量組成的k維n重線性子空間，或者說，要由k個信息碼元得到n-k個冗余碼元。設(shè) 是一組k個信息組，可以寫成矢量形式 。編碼器輸出的是k

20、維n重碼空間C的一個矢量，記為 。因此有k2kmmm,21),(21kmmmm),(21iniiiCCCCnjgmgmgmCkjkjjij, 2 , 1,2211信息論與編碼-信道編碼對二進制分組碼來說， 。上式也可以寫成矩陣形式：1 , 0ijgTkiniimmmccc),(),(),(2121k21igggmGC信息論與編碼-信道編碼對二進制分組碼來說， 。上式也可以寫成矩陣形式：其中， 均為一個含有n個元素的行向量。所以有1 , 0ijgTkiniimmmccc),(),(),(2121k21igggmGCk21ggg,knknggggG1111信息論與編碼-信道編碼G是一個k行n列的矩

21、陣，給定任何k碼元的信息比特，都可以由G利用公式 求出對應的碼字，因此，G被稱為碼的生成矩陣。mGCi信息論與編碼-信道編碼G是一個k行n列的矩陣，給定任何k碼元的信息比特，都可以由G利用公式 求出對應的碼字，因此，G被稱為碼的生成矩陣?？梢钥闯觯魏未a字都是G的行矢量的線性組合，即mGCik21igggCkmmm21信息論與編碼-信道編碼G是一個k行n列的矩陣，給定任何k碼元的信息比特，都可以由G利用公式 求出對應的碼字，因此，G被稱為碼的生成矩陣?？梢钥闯觯魏未a子都是G的行矢量的線性組合，即從矢量空間的角度來說，G的k個行矢量相當于k維n重碼字矢量空間的一組基底，mGCik21igggC

22、kmmm21信息論與編碼-信道編碼G是一個k行n列的矩陣，給定任何k碼元的信息比特，都可以由G利用公式 求出對應的碼字，因此，G被稱為碼的生成矩陣?？梢钥闯?，任何碼子都是G的行矢量的線性組合，即從矢量空間的角度來說，G的k個行矢量相當于k維n重碼字矢量空間的一組基底，該空間的任何矢量（碼字）都可以由這組基底的線性組合得到。mGCik21igggCkmmm21信息論與編碼-信道編碼G是一個k行n列的矩陣，給定任何k碼元的信息比特，都可以由G利用公式 求出對應的碼字，因此，G被稱為碼的生成矩陣。可以看出，任何碼子都是G的行矢量的線性組合，即從矢量空間的角度來說，G的k個行矢量相當于k維n重碼字矢量

23、空間的一組基底，該空間的任何矢量（碼字）都可以由這組基底的線性組合得到。并且這組基底本身也是一組碼字。mGCik21igggCkmmm21信息論與編碼-信道編碼一般形式的G，得到的碼字前k位的信息位也發(fā)生了變化，信息論與編碼-信道編碼一般形式的G，得到的碼字前k位的信息位也發(fā)生了變化，而一般來說，我們只是希望在信息位后加上冗余比特，信息論與編碼-信道編碼一般形式的G，得到的碼字前k位的信息位也發(fā)生了變化，而一般來說，我們只是希望在信息位后加上冗余比特，所以，可以對生成矩陣通過行運算（以及列置換）作適當?shù)淖儞Q，變成“系統(tǒng)性式”，信息論與編碼-信道編碼一般形式的G，得到的碼字前k位的信息位也發(fā)生了

24、變化，而一般來說，我們只是希望在信息位后加上冗余比特，所以，可以對生成矩陣通過行運算（以及列置換）作適當?shù)淖儞Q，變成“系統(tǒng)性式”，即)()(2)( 12221212111100010001)(knkknknkkpppppppppGPIk信息論與編碼-信道編碼一般形式的G，得到的碼字前k位的信息位也發(fā)生了變化，而一般來說，我們只是希望在信息位后加上冗余比特，所以，可以對生成矩陣通過行運算（以及列置換）作適當?shù)淖儞Q，變成“系統(tǒng)性式”，即這樣生成的（n，k）碼是系統(tǒng)碼。)()(2)( 12221212111100010001)(knkknknkkpppppppppGPIk信息論與編碼-信道編碼與碼空

25、間C相對應，一定存在一個對偶空間H。信息論與編碼-信道編碼與碼空間C相對應，一定存在一個對偶空間H。對偶空間H的基底，是n維n重矢量空間的基底中，除去張成k維碼字空間C的k個基底，而剩下的n-k個基底。信息論與編碼-信道編碼與碼空間C相對應，一定存在一個對偶空間H。對偶空間H的基底，是n維n重矢量空間的基底中，除去張成k維碼字空間C的k個基底，而剩下的n-k個基底。因此，H空間和C空間一定正交。即0HCTi信息論與編碼-信道編碼與碼空間C相對應，一定存在一個對偶空間H。對偶空間H的基底，是n維n重矢量空間的基底中，除去張成k維碼字空間C的k個基底，而剩下的n-k個基底。因此，H空間和C空間一定

26、正交。即生成矩陣的每一行，都是一個碼字，所以有0HCTi0GHT信息論與編碼-信道編碼因此)(knTIPH信息論與編碼-信道編碼因此H叫做碼字空間C的校驗矩陣，)(knTIPH信息論與編碼-信道編碼因此H叫做碼字空間C的校驗矩陣，可以利用 是否等于零矢量，來判斷一個 是不是碼字。)(knTIPHTiHCiC信息論與編碼-信道編碼例題：對一個（7，4）碼，其生成矩陣為1101000011010011100101010001G（1）對于信息組(1 0 1 1 )，對應碼字是什么？（2）設(shè)計一個（7，4）分組編碼器原理圖。（3）若接收到一個7位碼r=（1 0 0 1 1 0 1），判斷它是否是碼字。

27、信息論與編碼-信道編碼解：（1）由生成矩陣可知，得到的一定是系統(tǒng)碼。由 得mGCi421743263215mmmcmmmcmmmciiik21igggCkmmm21信息論與編碼-信道編碼解：（1）由生成矩陣可知，得到的一定是系統(tǒng)碼。由 得0, 0, 0765iiicccmGCi421743263215mmmcmmmcmmmciii將信息位的值(1 0 1 1 )代入，得： 信息論與編碼-信道編碼解：（1）由生成矩陣可知，得到的一定是系統(tǒng)碼。由 得0, 0, 0765iiicccmGCi421743263215mmmcmmmcmmmciii將信息位的值(1 0 1 1 )代入，得： 因此，編得的

28、碼字為因此，編得的碼字為)1011000(iC信息論與編碼-信道編碼解：（1）由生成矩陣可知，得到的一定是系統(tǒng)碼。由 得0, 0, 0765iiicccmGCi421743263215mmmcmmmcmmmciii將信息位的值(1 0 1 1 )代入，得： 因此，編得的碼字為因此，編得的碼字為)1011000(iC注意:加法是模2加。信息論與編碼-信道編碼（2）由編碼后冗余位與信息位的關(guān)系，可得編碼器的原理圖如圖所示：1m2m3m4m7ic6ic5ic輸入輸出421743263215mmmcmmmcmmmciii信息論與編碼-信道編碼（3）要檢驗一個碼序列R是否是碼字，可以使用校驗矩陣H，如果

29、 ，則一定是碼字，否則一定不是碼字。0TRH信息論與編碼-信道編碼（3）要檢驗一個碼序列R是否是碼字，可以使用校驗矩陣H，如果 ，則一定是碼字，否則一定不是碼字。0TRH100101101011100010111)(knTIPH信息論與編碼-信道編碼（3）要檢驗一個碼序列R是否是碼字，可以使用校驗矩陣H，如果 ，則一定是碼字，否則一定不是碼字。因此， 就產(chǎn)生三個方程，只有第一個為零，另兩個不為零，所以R不是碼字。0TRH100101101011100010111)(knTIPHTRH信息論與編碼-信道編碼（3）要檢驗一個碼序列R是否是碼字，可以使用校驗矩陣H，如果 ，則一定是碼字，否則一定不是

30、碼字。因此， 就產(chǎn)生三個方程，只有第一個為零，另兩個不為零，所以R不是碼字。系統(tǒng)碼的前k位為信息位，后n-k位為校驗位。0TRH100101101011100010111)(knTIPHTRH信息論與編碼-信道編碼校驗矩陣H除了可以用來檢驗碼字外，還與碼的最小距離（也就和碼的檢錯糾錯能力）有關(guān)。信息論與編碼-信道編碼校驗矩陣H除了可以用來檢驗碼字外，還與碼的最小距離（也就和碼的檢錯糾錯能力）有關(guān)。因為其中， 是H矩陣的列向量。),()(2)(1 )(2222111211n21hhhHnknknknnnhhhhhhhhhn21hhh,信息論與編碼-信道編碼因此，也就是說，n個矢量 一定是線性相關(guān)

31、的。TnT2T1TihhhHCiniiccc21Thj信息論與編碼-信道編碼因此，也就是說，n個矢量 一定是線性相關(guān)的。如果分組碼的最小距離為 ，則根據(jù)線性碼的特點，碼集里面一定有一個碼字其重量最小為 ，即有 個非零元素。TnT2T1TihhhHCiniiccc21Thjmindmindmind信息論與編碼-信道編碼因此，也就是說，n個矢量 一定是線性相關(guān)的。如果分組碼的最小距離為 ，則根據(jù)線性碼的特點，碼集里面一定有一個碼字其重量最小為 ，即有 個非零元素。將其代入校驗矩陣的方程，左邊就有 個 項，而右邊為零。TnT2T1TihhhHCiniiccc21Thjmindmindmindmind

32、Thj信息論與編碼-信道編碼因此，也就是說，n個矢量 一定是線性相關(guān)的。如果分組碼的最小距離為 ，則根據(jù)線性碼的特點，碼集里面一定有一個碼字其重量最小為 ，即有 個非零元素。將其代入校驗矩陣的方程，左邊就有 個 項，而右邊為零。也就是說， 個 是線性相關(guān)的。 而TnT2T1TihhhHCiniiccc21ThjmindmindmindmindThjmindThj信息論與編碼-信道編碼 個 一定是線性無關(guān)的1mindThj信息論與編碼-信道編碼 個 一定是線性無關(guān)的（反證法：如果 個 列矢量是線性相關(guān)的，則可以把其對應的系數(shù)當成碼字，而該碼字的重量為 ，這與碼字的最小重量為 相矛盾）。1mind

33、Thj1mindThj1mindmind信息論與編碼-信道編碼 個 一定是線性無關(guān)的（反證法：如果 個 列矢量是線性相關(guān)的，則可以把其對應的系數(shù)當成碼字，而該碼字的重量為 ，這與碼字的最小重量為 相矛盾）。由于H是 的矩陣，其秩最大為n-k，也就是說，最多有n-k個列矢量線性無關(guān)。1mindThj1mindThj1mindmindnkn )(信息論與編碼-信道編碼 個 一定是線性無關(guān)的（反證法：如果 個 列矢量是線性相關(guān)的，則可以把其對應的系數(shù)當成碼字，而該碼字的重量為 ，這與碼字的最小重量為 相矛盾）。由于H是 的矩陣，其秩最大為n-k，也就是說，最多有n-k個列矢量線性無關(guān)。在編碼的時候，

34、我們希望 越大越好，所以1mindThj1mindThj1mindmindnkn )(mind信息論與編碼-信道編碼 個 一定是線性無關(guān)的（反證法：如果 個 列矢量是線性相關(guān)的，則可以把其對應的系數(shù)當成碼字，而該碼字的重量為 ，這與碼字的最小重量為 相矛盾）。由于H是 的矩陣，其秩最大為n-k，也就是說，最多有n-k個列矢量線性無關(guān)。在編碼的時候，我們希望 越大越好，所以1mindThj1mindThj1mindmindnkn )(mind1,1minminkndknd即信息論與編碼-信道編碼也就是說，二進制（n，k）線性碼的最小碼距的上界是n-k+1。稱這樣的碼為極大最小距離碼（MDC:Ma

35、ximized minimum Distance Code）。信息論與編碼-信道編碼三、伴隨式與譯碼信息論與編碼-信道編碼三、伴隨式與譯碼1. 伴隨式本節(jié)討論如何譯碼。信息論與編碼-信道編碼三、伴隨式與譯碼1. 伴隨式本節(jié)討論如何譯碼。設(shè)發(fā)送的碼字為 通過有擾信道傳輸，信道產(chǎn)生的錯誤圖樣為 ，),(110NcccC),(110NeeeE信息論與編碼-信道編碼三、伴隨式與譯碼1. 伴隨式本節(jié)討論如何譯碼。設(shè)發(fā)送的碼字為 通過有擾信道傳輸，信道產(chǎn)生的錯誤圖樣為 ，接收端譯碼器收到的n重矢量為 ，則R=C+E),(110NcccC),(110NeeeE),(110NrrrR信息論與編碼-信道編碼譯碼

36、器的任務就是要從收到的R中得出 ，或者由R中解出錯誤圖樣 ，從而得到 ，并使譯碼錯誤概率最小。EERCC信息論與編碼-信道編碼譯碼器的任務就是要從收到的R中得出 ，或者由R中解出錯誤圖樣 ，從而得到 ，并使譯碼錯誤概率最小。對于二進制碼字，模2減與模2加等同。EERCC信息論與編碼-信道編碼譯碼器的任務就是要從收到的R中得出 ，或者由R中解出錯誤圖樣 ，從而得到 ，并使譯碼錯誤概率最小。對于二進制碼字，模2減與模2加等同。對于n，k分組碼C，滿足 ，因此EERC0CHTTTTEHHECRH)(C信息論與編碼-信道編碼譯碼器的任務就是要從收到的R中得出 ，或者由R中解出錯誤圖樣 ，從而得到 ，并

37、使譯碼錯誤概率最小。對于二進制碼字，模2減與模2加等同。對于n，k分組碼C，滿足 ，因此若E=0，則 ，EERC0CHTTTTEHHECRH)(0RHTC信息論與編碼-信道編碼譯碼器的任務就是要從收到的R中得出 ，或者由R中解出錯誤圖樣 ，從而得到 ，并使譯碼錯誤概率最小。對于二進制碼字，模2減與模2加等同。對于n，k分組碼C，滿足 ，因此若E=0，則 ，若 ，并且僅與錯誤圖樣E有關(guān)，而與發(fā)送什么碼字無關(guān)。EERC0CHTTTTEHHECRH)(0RHT0RH0ET則,C信息論與編碼-信道編碼S稱為接收矢量R的伴隨式（校正子）。伴隨式完全由E決定，它充分反映了信道的干擾情況。TTEHRHS令信

38、息論與編碼-信道編碼S稱為接收矢量R的伴隨式（校正子）。伴隨式完全由E決定，它充分反映了信道的干擾情況。譯碼器的主要任務就是如何從S中得到最象E的錯誤圖樣 ，從而譯出 。EERCTTEHRHS令信息論與編碼-信道編碼S稱為接收矢量R的伴隨式（校正子）。伴隨式完全由E決定，它充分反映了信道的干擾情況。譯碼器的主要任務就是如何從S中得到最象E的錯誤圖樣 ，從而譯出 。如果一個n，k譯碼器要糾正t個錯誤，則要求對于錯誤個數(shù) 的所有可能組合的錯誤圖樣，都應該有不同的伴隨式與之對應。EERCtTTEHRHS令信息論與編碼-信道編碼2. 標準陣列由前面的討論可知，n，k分組碼的譯碼步驟可歸結(jié)為以下三步：信

39、息論與編碼-信道編碼2. 標準陣列由前面的討論可知，n，k分組碼的譯碼步驟可歸結(jié)為以下三步：（1）由接收到的R，計算伴隨式 ；TRHS 信息論與編碼-信道編碼2. 標準陣列由前面的討論可知，n，k分組碼的譯碼步驟可歸結(jié)為以下三步：（1）由接收到的R，計算伴隨式 ；（2）若S=0，則認為接收無誤。若 ，則由 S找出錯誤圖樣 ；TRHS 0S E信息論與編碼-信道編碼2. 標準陣列由前面的討論可知，n，k分組碼的譯碼步驟可歸結(jié)為以下三步：（1）由接收到的R，計算伴隨式 ；（2）若S=0，則認為接收無誤。若 ，則由 S找出錯誤圖樣 ；（3）由 和R找出 。TRHS 0S EEERC信息論與編碼-信道

40、編碼2. 標準陣列由前面的討論可知，n，k分組碼的譯碼步驟可歸結(jié)為以下三步：（1）由接收到的R，計算伴隨式 ；（2）若S=0，則認為接收無誤。若 ，則由 S找出錯誤圖樣 ；（3）由 和R找出 。這里最關(guān)鍵的是由S找出E，只要找出的E是正確的，譯出的碼也是正確的。由S的定義式， ，即TRHS 0S EEERCTEHS 信息論與編碼-信道編碼共有n-k個方程，但有n個未知量，所以解不唯一。Tnknnknnknhhhheeesss)(11 )(112121),(),(信息論與編碼-信道編碼共有n-k個方程，但有n個未知量，所以解不唯一。對于二進制，少一個方程導致兩個解，少兩個方程導致四個解，少k個方

41、程導致有 個解.Tnknnknnknhhhheeesss)(11 )(112121),(),(k2信息論與編碼-信道編碼共有n-k個方程，但有n個未知量，所以解不唯一。對于二進制，少一個方程導致兩個解，少兩個方程導致四個解，少k個方程導致有 個解.也就是說，可以解出 個不同的錯誤圖樣，從而對應了 個碼字（碼字的全部可能）。Tnknnknnknhhhheeesss)(11 )(112121),(),(k2k2k2信息論與編碼-信道編碼共有n-k個方程，但有n個未知量，所以解不唯一。對于二進制，少一個方程導致兩個解，少兩個方程導致四個解，少k個方程導致有 個解.也就是說，可以解出 個不同的錯誤圖樣

42、，從而對應了 個碼字（碼字的全部可能）。根據(jù)最大似然譯碼規(guī)則，應該譯成可能性最大的那個碼字。Tnknnknnknhhhheeesss)(11 )(112121),(),(k2k2k2信息論與編碼-信道編碼對于二進制對稱信道，若差錯概率為p，則錯一個比特的概率（ ）大于錯兩個比特的概率（ ），。1)1 (npp22)1 (npp信息論與編碼-信道編碼對于二進制對稱信道，若差錯概率為p，則錯一個比特的概率（ ）大于錯兩個比特的概率（ ），。所以，應該譯成所有 個差錯圖樣中重量最小的那一個。1)1 (npp22)1 (nppk2信息論與編碼-信道編碼對于二進制對稱信道，若差錯概率為p，則錯一個比特的

43、概率（ ）大于錯兩個比特的概率（ ），。所以，應該譯成所有 個差錯圖樣中重量最小的那一個。但如果每接收一個R就要解一次方程組，顯然太麻煩了。1)1 (npp22)1 (nppk2信息論與編碼-信道編碼對于二進制對稱信道，若差錯概率為p，則錯一個比特的概率（ ）大于錯兩個比特的概率（ ），。所以，應該譯成所有 個差錯圖樣中重量最小的那一個。但如果每接收一個R就要解一次方程組，顯然太麻煩了?？梢灶A先把不同S下的方程組解出來，并得到最大概率的那個錯誤圖樣，和錯誤圖樣對應的R，存成一個表格，譯碼的時候，只要根據(jù)不同的R查表，就可以得到對應的最大可能的碼字。1)1 (npp22)1 (nppk2信息論與

44、編碼-信道編碼表5-4-1就是一個這樣的表，叫做標準陣列譯碼表。信息論與編碼-信道編碼表5-4-1 標準陣列譯碼表11ES 22ES jjES knkn22ES00011 CE212ECEjjECE1knknECE212221CCE22CE 2CEj22CEkniCE 2ijCE iCEkn2iiCCE1kkCCE221kCE22kCEj2kknCE22信息論與編碼-信道編碼表5-4-1就是一個這樣的表，叫做標準陣列譯碼表。表中有 列，每一列的頭一個元素對應的是一個碼字，所以共對應 個不同的碼字；k2k2信息論與編碼-信道編碼表5-4-1就是一個這樣的表，叫做標準陣列譯碼表。表中有 列，每一列

45、的頭一個元素對應的是一個碼字，所以共對應 個不同的碼字；每一列的列首元素下，是 個禁用碼字（即n維空間點中不是碼字的那些點），k2k2kn2信息論與編碼-信道編碼表5-4-1就是一個這樣的表，叫做標準陣列譯碼表。表中有 列，每一列的頭一個元素對應的是一個碼字，所以共對應 個不同的碼字；每一列的列首元素下，是 個禁用碼字（即n維空間點中不是碼字的那些點），代表該列首元素（碼字）在不同差錯圖樣下偏移后所對應的空間點，正好對應了 個不同的伴隨式。k2k2kn2kn2信息論與編碼-信道編碼表5-4-1就是一個這樣的表，叫做標準陣列譯碼表。表中有 列，每一列的頭一個元素對應的是一個碼字，所以共對應 個不

46、同的碼字；每一列的列首元素下，是 個禁用碼字（即n維空間點中不是碼字的那些點），代表該列首元素（碼字）在不同差錯圖樣下偏移后所對應的空間點，正好對應了 個不同的伴隨式。全部的元素個數(shù)是 ，正好是n維矢量空間中總的點數(shù)，也就是說，每一個空間點k2k2kn2kn2nkkn222信息論與編碼-信道編碼都有其所對應的碼字，這樣，在譯碼的時候，當接收到一個R后，只要在標準陣列表中找到該R的位置，這一列的列首元素就是它應該譯成的碼字。信息論與編碼-信道編碼都有其所對應的碼字，這樣，在譯碼的時候，當接收到一個R后，只要在標準陣列表中找到該R的位置，這一列的列首元素就是它應該譯成的碼字。表中第一行對應的是 個

47、碼字，相當于差錯為零；第二行到第n+1行分別對應n個差錯為1的差錯圖樣；。每一行的行首元素叫做陪集首，是該行所對應的錯誤圖樣。k2信息論與編碼-信道編碼都有其所對應的碼字，這樣，在譯碼的時候，當接收到一個R后，只要在標準陣列表中找到該R的位置，這一列的列首元素就是它應該譯成的碼字。表中第一行對應的是 個碼字，相當于差錯為零；第二行到第n+1行分別對應n個差錯為1的差錯圖樣；。每一行的行首元素叫做陪集首，是該行所對應的錯誤圖樣。但是，錯誤圖樣數(shù)有 個，標準陣列譯碼表只有 行，代表 個伴隨式和錯誤圖樣。那么，k2n2kn2kn2信息論與編碼-信道編碼怎么從 個錯誤圖樣中選擇 個，作為陪集首？n2k

48、n2信息論與編碼-信道編碼怎么從 個錯誤圖樣中選擇 個，作為陪集首？原則當然是要使得譯碼的錯誤概率最小。n2kn2信息論與編碼-信道編碼怎么從 個錯誤圖樣中選擇 個，作為陪集首？原則當然是要使得譯碼的錯誤概率最小。前面已經(jīng)說過，對BSC信道，當錯誤概率p0.5時，產(chǎn)生一個錯誤的概率比產(chǎn)生兩個錯誤的概率要大，產(chǎn)生兩個錯誤的概率比產(chǎn)生3個錯誤的概率要大，。n2kn2信息論與編碼-信道編碼怎么從 個錯誤圖樣中選擇 個，作為陪集首？原則當然是要使得譯碼的錯誤概率最小。前面已經(jīng)說過，對BSC信道，當錯誤概率p0.5時，產(chǎn)生一個錯誤的概率比產(chǎn)生兩個錯誤的概率要大，產(chǎn)生兩個錯誤的概率比產(chǎn)生3個錯誤的概率要大

49、，?？傊e誤圖樣重量越小，產(chǎn)生的可能性就越大。n2kn2信息論與編碼-信道編碼怎么從 個錯誤圖樣中選擇 個，作為陪集首？原則當然是要使得譯碼的錯誤概率最小。前面已經(jīng)說過，對BSC信道，當錯誤概率p0.5時，產(chǎn)生一個錯誤的概率比產(chǎn)生兩個錯誤的概率要大，產(chǎn)生兩個錯誤的概率比產(chǎn)生3個錯誤的概率要大，?？傊?，錯誤圖樣重量越小，產(chǎn)生的可能性就越大。因此，譯碼器必須首先保證能正確糾正這些出現(xiàn)可能性比較大的錯誤圖樣，這相當于構(gòu)造標準陣列譯碼表時，要求按照錯誤圖樣重量從輕到重的順序挑選為陪首集。n2kn2信息論與編碼-信道編碼例題：某（5，2）系統(tǒng)線性碼的生成矩陣是設(shè)收到的碼是R=(10101)，請先構(gòu)造該

50、碼的標準陣列譯碼表，然后譯出發(fā)碼的估值C。1101111001G信息論與編碼-信道編碼例題：某（5，2）系統(tǒng)線性碼的生成矩陣是設(shè)收到的碼是R=(10101)，請先構(gòu)造該碼的標準陣列譯碼表，然后譯出發(fā)碼的估值C。解： （1）標準陣列譯碼表 n-k=3， ，即標準陣列譯碼表共有8行，每行代表一種錯誤圖樣。按照錯誤圖樣重量從輕8231101111001G信息論與編碼-信道編碼到重的順序，無差錯（錯誤圖樣重量為0）的有一 種，重量為1的有 種，重量為2的有 種。5151025信息論與編碼-信道編碼到重的順序，無差錯（錯誤圖樣重量為0）的有一 種，重量為1的有 種，重量為2的有 種。我們挑選的陪首集是1

51、種無錯誤（重量為0），5種有一個錯誤（重量為1）和重量為2的10 種里面的2種。5151025信息論與編碼-信道編碼到重的順序，無差錯（錯誤圖樣重量為0）的有一 種，重量為1的有 種，重量為2的有 種。我們挑選的陪首集是1種無錯誤（重量為0），5種有一個錯誤（重量為1）和重量為2的10 種里面的2種。碼字共有 種，將信息組的可能組合(00)、(01)、(10)、(11)代入生成矩陣，得到四個碼字為：(00000)、(10111)、(01101)、(11010)。51510254222k信息論與編碼-信道編碼到重的順序，無差錯（錯誤圖樣重量為0）的有一 種，重量為1的有 種，重量為2的有 種。我

52、們挑選的陪首集是1種無錯誤（重量為0），5種有一個錯誤（重量為1）和重量為2的10 種里面的2種。碼字共有 種，將信息組的可能組合(00)、(01)、(10)、(11)代入生成矩陣，得到四個碼字為：(00000)、(10111)、(01101)、(11010)。得到的標準陣列譯碼表如下圖所示：51510254222k信息論與編碼-信道編碼標準陣列譯碼表 S1=000E1+C1=00000C2=10111 C3=01101 C4=11010 S2=111E2=10000 00111 11101 01010 S3=101E3=01000 11111 00101 10010 S4=100E4=001

53、00 10011 01001 11110 S5=010E5=00010 10101 01111 11000 S6=001E6=00001 10110 01100 11011 S7=011E7=00011 10100 01110 11001 S8=110E8=00110 10001 01011 11100信息論與編碼-信道編碼當然，上述的標準陣列譯碼表不是唯一的，因為從10種重量為2的錯誤圖樣中選擇兩種，可以是任意選的。信息論與編碼-信道編碼當然，上述的標準陣列譯碼表不是唯一的，因為從10種重量為2的錯誤圖樣中選擇兩種，可以是任意選的。標準陣列譯碼表需要把 個n重存儲在譯碼器中。其復雜性隨n的增大指數(shù)增長，當n比較大時很不實用。n2信息論與編碼-信道編碼當然，上述的標準陣列譯碼表不是唯一的，因為從10種重量為2的錯誤圖樣中選擇兩種，可以是任意選的。標準陣列譯碼表需要把 個n重存儲在譯碼器中。其復雜性隨n的增大指數(shù)增長，當n比較大時很不實用?？梢园褬藴赎嚵凶g碼表進行簡化，即只存儲伴隨式和錯誤圖樣的對應關(guān)系，譯碼時先計算得到伴隨式，再查表得到錯誤圖樣，從而得到譯碼碼字。n2信息論與編碼-信道編碼這樣碼表可以簡化，但譯碼時的計算量增加了。信息論與編碼-信道編碼這樣碼表可以簡化，但譯碼時的計算量增加了。并且當n和k都比較大時，即使采用