信息基礎(chǔ)與編碼理論第十章

信息基礎(chǔ)與編碼理論第十章第一頁，共四十五頁，2022年，8月28日10.1近世代數(shù)學(xué)的基礎(chǔ)知識（1）群的概念定義1

G是一個非空集合，*是G中的一個代數(shù)運(yùn)算，若

1°a,b∈G,有a*b∈G(封閉性)2°a,b,c∈G,有(a*b)*c=a*

(b*c)(結(jié)合律)3°存在單位元素e∈G,a∈G,有e*a=a*e=a4°a∈G,存在逆元素

∈G,有

5°a,b∈G,有

a*b=b*a(交換律)

如果這種運(yùn)算*滿足：條件1°,2°,3°,4°則G

稱對代數(shù)運(yùn)算為一個群,或稱G為一個非交換群.

第十章

線性分組碼第二頁，共四十五頁，2022年，8月28日若運(yùn)算*滿足：條件1°,2°，3°,4°,5°則稱G為一個交換群或Abel群。若運(yùn)算*是普通的加法“+”,則群稱為加群

。若運(yùn)算*是普通的乘法“×”,則群稱為乘群

。定義2

若群G僅有有限個原素則稱為有限群；否則為無限群。

1）無限群舉例例1整數(shù)集對加法構(gòu)成Abel群,對乘法不是群。例2有理數(shù)、實數(shù)、復(fù)數(shù)集對加法構(gòu)成Abel群，不含數(shù)0的有理數(shù)、實數(shù)、復(fù)數(shù)集對乘法構(gòu)成Abel群。

第三頁，共四十五頁，2022年，8月28日例3n維方陣的集合加法構(gòu)成Abel群,對乘法不是群.例4n維非奇異方陣對乘法構(gòu)成非Abel群。

2）有限群舉例例1數(shù)0對加法構(gòu)成群,數(shù)1對乘法構(gòu)成群。例2集合{0,1,2,…,m-1}對模m加法運(yùn)算構(gòu)成Abel群,

對乘法不是群。例3當(dāng)m為素數(shù)時,集合{1,2,…,m-1}對模m乘法運(yùn)算構(gòu)成Abel群。例4線性分組碼構(gòu)成Abel群,所以線性分組碼又稱為群碼。第四頁，共四十五頁，2022年，8月28日（2）域的概念

定義1

F是一個非空集合,對于F的任意兩個元素a和b,定義集合元素的加法運(yùn)算,記作a＋b;乘法運(yùn)算,記作ab;

且有如下規(guī)則:

加法運(yùn)算

1°a,b∈F,有a＋b∈F;2°a,b∈F,有a＋b=b＋a;3°a，b，c∈F,有(a＋b)＋c=a＋(b＋c);4°存在0∈F,a∈F,有a＋0=a

；

5°a∈F,存在-a∈F,有a＋(-a)=0;第五頁，共四十五頁，2022年，8月28日乘法運(yùn)算

1°a,b∈F,有ab∈F;2°a,b∈F,有ab=ba;3°a，b，c∈F,有(ab)c=a(b

c);4°存在e∈F,a∈F,有a

e=a

；

5°a∈F,且a≠0,存在a

-1∈F,有aa

-1=e;

乘法對加法的分配律

a,b,c∈F,有a(b＋c)=ab＋ac

以上運(yùn)算規(guī)則都成立，則稱F對于所規(guī)定的加法運(yùn)算和乘法運(yùn)算是一個域.定義2

設(shè)F是一個域,如果F中的元素個數(shù)無限,則F稱為無限域.如果F中的元素個數(shù)有限,則F稱為有限

域，有限域亦稱為Galois域。第六頁，共四十五頁，2022年，8月28日當(dāng)有限域中元素的個數(shù)為q時，q稱為域的階，記為GF（q）1°無限域的例子例1有理數(shù)、實數(shù)、復(fù)數(shù)集對加法,乘法構(gòu)成域。例2形如的數(shù)對加法,乘法構(gòu)成域。2°有限域的例子例1集合{0,1,2,…,m-1}對模m加法,乘法運(yùn)算構(gòu)成域。第七頁，共四十五頁，2022年，8月28日二元域的運(yùn)算（1）系數(shù)取自GF（2）的多項式對于（n+1）bit的二進(jìn)制數(shù)字序列，可以用多項式來描述稱為GF（2）上的n次多項式。其中：的值為0或者1，是二元域GF（2）的元素，對應(yīng)二進(jìn)制數(shù)字序列。代表著對應(yīng)系數(shù)所在的位置。（2）可做長除法

第八頁，共四十五頁，2022年，8月28日10.2線性分組碼的基本概念（1)模運(yùn)算(對于整數(shù))①同余

a=b(modm):a

除以m

與b除以m(m>1)的余數(shù)相同；或稱為a

和b

對于模m

同余.

最小非負(fù)剩余:a=r(modm);0≤r<m；

r為模m最小非負(fù)剩余模

m

運(yùn)算:a,b∈{0,1,2,…,m-1}；

r為最小非負(fù)剩余；將a+b=r

(modm),a×b=r(modm)

記為這種求a+b

和a×b

的模

m。第九頁，共四十五頁，2022年，8月28日

最小非負(fù)剩余稱為模m的加法運(yùn)算和模m的乘法運(yùn)算.

為了簡單起見,以后將運(yùn)算符號簡記為+和×。②模2運(yùn)算(二進(jìn)制)

1+1+1=1,1+1+1+1=0,…0-1=1,1-0=1,1-1=0+01001110×01000101第十頁，共四十五頁，2022年，8月28日

+012001211202201③模q運(yùn)算(q進(jìn)制)

例:q=3×012000010122021第十一頁，共四十五頁，2022年，8月28日

（2）線性分組碼定義1

設(shè)Ci=(ci1,ci

2,…,cin),Cj=(cj1,cj2,…,cjn

)是二元碼C的兩個碼字,則Ci與Cj

的和為Ci與Cj對應(yīng)碼元的模2運(yùn)算；若Cs=(cs1,cs2,…,csn)

且Cs=Ci+Cj

即csr

=cir+cjr(r=1,2,…,n)

定義2

設(shè)(n,k)分組碼C

中的任意兩個碼字

1°C中有全0碼元的碼字；

2°C中的任意兩個碼字的和仍為碼C的碼字；則分組碼C稱為(n,k)線性分組碼。第十二頁，共四十五頁，2022年，8月28日

推論線性分組碼任意兩個以上碼字的和仍為碼C

的碼字。根據(jù)分組碼的定義,

信息組m

的k

個碼元(信息位)應(yīng)包含在線性分組碼的碼字中。第十三頁，共四十五頁，2022年，8月28日例試構(gòu)造(5,2)線性分組碼,且dmin=3

信息組m00011011

00000

000010001000011001000010100110

00111

010000100101010

01011

01100

011010111001111

100001000110010

10011

10100

101011011010111

11000

11001110101101111100111011111011111

1組2組3組4組5組6組7組8組9組0000000000

00000

0000000000

00000

00000

00000

0000001011

01011

01011

01101

01101

01101

01110

01110

011101010110110

10111

10011

10110

1011110011

101011011111110

11101

11100

11110

11011

11010

1110111001

11001第十四頁，共四十五頁，2022年，8月28日10.3生成矩陣與校驗矩陣（1）一般線性分組碼的生成矩陣與校驗矩陣線性分組碼（n,k）:把k（bit）的消息矢量線性地映射到n（bit）的碼字其中所有可能的消息構(gòu)成消息空間M，數(shù)量為個,在碼字空間中所對應(yīng)的合法碼字為個。第十五頁，共四十五頁，2022年，8月28日線性映射：若是與消息對應(yīng)的碼字，則，必定為對應(yīng)的碼字。碼字空間是n維二元線性空間的k維子空間，存在k個線性獨(dú)立（不相關(guān)）的二元n維矢量使得任何一個碼字都可表示成的線性組合第十六頁，共四十五頁，2022年，8月28日其中

校驗矩陣：在接收端進(jìn)行正確譯碼，將碼字的校驗元和信息元的線性組合關(guān)系用方程表示，其對應(yīng)矩陣形式為一致校驗矩陣H

滿足，則碼字正確。生成矩陣G的行與一致校驗矩陣H的行相互正交。

為生成矩陣，由該矩陣中的行向量的任意線性組合都構(gòu)成一個碼字。

第十七頁，共四十五頁，2022年，8月28日（2）系統(tǒng)線性分組碼的生成矩陣與校驗矩陣定義若信息組m的k個碼元以整體不變的形式,放在碼字的任意位置中

,該碼為系統(tǒng)碼

。否則

,

稱為非系統(tǒng)碼.

系統(tǒng)碼通常如下圖將信息組放在碼字的最左邊或最右邊。上圖右所表示的系統(tǒng)碼：生成矩陣為k×n

維矩陣。

校驗矩陣其中為k×k階單位方程，以獲得信息位；P為k×（n-k)階矩陣，以獲得校驗位。G可由一般線性分組碼的生成矩陣進(jìn)行初等變化而得，見例2所示。k位信息位n-k位校驗位n-k位校驗位k位信息位第十八頁，共四十五頁，2022年，8月28日例1：下面是某（n,k）線性二元碼的全部碼字：（1）求n,k為何值；（2）構(gòu)造這碼的生成矩陣G；（3）構(gòu)成這碼的一致校驗矩陣H。第十九頁，共四十五頁，2022年，8月28日解：（1）∵碼字?jǐn)?shù)M=8=k=3,n=6為（6,3）線性分組碼。（2）生成矩陣G為k=3行,n=6列的矩陣，由k=3個線性獨(dú)立的碼字組成。故（3）設(shè)信息位為，則碼字∴第二十頁，共四十五頁，2022年，8月28日∴∴一致校驗矩陣為第二十一頁，共四十五頁，2022年，8月28日例2

構(gòu)造一個等價于例1中的（6，3）系統(tǒng)線性分組碼。（1）構(gòu)造（6，3）線性分組碼的生成矩陣；（2）構(gòu)造這碼的一致校驗矩陣；（3）列出所有的碼字。比較與例1中的碼的糾、檢錯能力。解：（1）將例1中的生成矩陣G進(jìn)行初等變換，使其成為等價的（6，3）系統(tǒng)線性分組碼的標(biāo)準(zhǔn)生成矩陣。得為等價（6，3）系統(tǒng)線性分組碼的標(biāo)準(zhǔn)生成矩陣。第二十二頁，共四十五頁，2022年，8月28日（2）由得（3）由可生成全部碼字：這線性分組碼的最小漢明距離而由G生成的線性分組碼C的最小漢明距離所以此兩碼的糾、檢測錯誤能力相同。第二十三頁，共四十五頁，2022年，8月28日

例3

試構(gòu)造(5,2)

線性分組碼,且

m=(m1m2)=(00),(01),(10),(11)

(00)→(00

000)(01)→(01

011)

(10)→(10

101)(11)→(11

110)

第二十四頁，共四十五頁，2022年，8月28日例4

試構(gòu)造(7,4)線性分組碼,且dmin=3（1）構(gòu)造生成矩陣生成矩陣生成的線性分組碼要有盡可能大的dmin

,即生成矩陣的行矢量中的“1”的個數(shù)≥dmin

,且生成矩陣各行矢量(碼字)的對應(yīng)元素不相同的個數(shù)≥dmin。第二十五頁，共四十五頁，2022年，8月28日（2）編碼器的實現(xiàn)上例

m=(m1m2m3m4)

m1,

m2,

m3,

m4∈{0,1}

Ci

=mGCi

=(c1c2c3c4c5c6c7)=(m1m2m3m4m1+m2+

m3m2+m3+m4m1+m2+m4)m1c1m2c2m3c3m4c4

c5

c6

c7+++第二十六頁，共四十五頁，2022年，8月28日小結(jié)：線性分組碼生成矩陣的特點(diǎn)①生成矩陣不是唯一的；

②生成矩陣的行矢量均為線性分組碼的碼字；

③生成矩陣的行矢量是模2運(yùn)算下線性無關(guān)；

④線性分組碼任一碼字是行矢量模2運(yùn)算下的線性組合。第二十七頁，共四十五頁，2022年，8月28日10.3

線性分組碼的譯碼（1）相關(guān)概念①錯誤圖樣：設(shè)發(fā)端發(fā)送的碼字為為個許用碼組中的一個，經(jīng)信道傳輸后，收到的矢量為，為個碼字中的一個。其中為錯誤矢量，稱錯誤圖樣。糾錯碼的任務(wù)：確定錯誤圖樣。

伴隨式:矢量為接收碼矢r的伴隨式，表示為②第二十八頁，共四十五頁，2022年，8月28日③陪集：設(shè)群G的子群將它與H中的元依次相加，得，稱a+H為H的一個陪集，a稱為該陪集的陪集首。第二十九頁，共四十五頁，2022年，8月28日（2）標(biāo)準(zhǔn)陣列譯碼法將個可能的接收矢量劃分為個不相交的子集，使每個子集只含有一個碼矢（碼字），該陣列稱為標(biāo)準(zhǔn)陣。表示如下：（n,k）線性分組碼的標(biāo)準(zhǔn)陣第三十頁，共四十五頁，2022年，8月28日①標(biāo)準(zhǔn)陣構(gòu)成：第一行：以全0碼字開始，包含所有碼字；第一列：陪集首項，包含了所有可糾正的錯誤圖樣。為全0矢量，既是許用碼組中的一個碼字，也是錯誤圖樣，代表沒有錯誤的情況。其他項為所在行與列對應(yīng)碼字之和②性質(zhì)：

a）兩個陪集不相交，或重合。即矩陣各行不相交。

b）標(biāo)準(zhǔn)陣的陪集首為該（n，k）碼所能糾正的錯誤圖樣，為個。

c）重量越輕的陪集首所對的錯誤出現(xiàn)的概率越大。當(dāng)且僅當(dāng)錯誤圖樣不是陪集首時才出現(xiàn)譯碼錯誤。第三十一頁，共四十五頁，2022年，8月28日③

譯碼：接收的碼字，必定落在標(biāo)準(zhǔn)陣列中的某一行。由最大釋然準(zhǔn)則，把與接收矢量最近的碼字譯為發(fā)送碼字。即在標(biāo)準(zhǔn)陣中尋找最輕重量的矢量作為錯誤形式。利用恢復(fù)碼字。小結(jié)：標(biāo)準(zhǔn)陣列譯碼法為基礎(chǔ)譯碼法，直觀，但不最優(yōu)。具體應(yīng)用時，只用列出重量為t的陪集陣列。例：下面列出一個具有4個碼字的（6，2）線性碼這個碼的最小漢明距離為3，可以糾正一個錯誤。共有6個一位錯誤圖樣，其限制距離為1的譯碼表如下：

第三十二頁，共四十五頁，2022年，8月28日完整的標(biāo)準(zhǔn)陣列，還有9列。含有2位的錯誤圖樣共有種。000000010101101010111111000001010100101011111110000010010111101000111101000100010001101110111011001000011101100010110111010000000101111010101111100000110101001010011111…………該（6，2）線性碼部分譯碼表第三十三頁，共四十五頁，2022年，8月28日其中二位錯誤形式（101000），（010100），（001010），（000101），（010001），（100010）已經(jīng)在標(biāo)準(zhǔn)陣的前6行中出現(xiàn)，所以這6種為不可糾正的錯誤，余下的9種錯誤圖樣可作為陪集首項，得到不相交的陪集，對應(yīng)了可糾正2位錯誤形式。（3）伴隨式譯碼法與接收碼字r對應(yīng)的伴隨式為0的充要條件：碼字r為許用碼字。由，而所以伴隨式由錯誤圖樣決定，且一一對應(yīng)。

第三十四頁，共四十五頁，2022年，8月28日伴隨式譯碼方法：存儲個陪集首項（錯誤圖樣）和所對應(yīng)的伴隨式。①計算接收到碼字r的伴隨式若s=0，表示r為許用碼字，沒錯。若不為0，轉(zhuǎn)②。②根據(jù)s查出所對應(yīng)的錯誤圖樣e。③糾正錯誤，譯碼：輸出正確碼字。第三十五頁，共四十五頁，2022年，8月28日第三十六頁，共四十五頁，2022年，8月28日第三十七頁，共四十五頁，2022年，8月28日