信息基礎與編碼理論第十章

信息基礎與編碼理論第十章第1頁，共45頁，2023年，2月20日，星期三10.1近世代數(shù)學的基礎知識（1）群的概念定義1

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

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

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

∈G,有

5°a,b∈G,有

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

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

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

第十章

線性分組碼第2頁，共45頁，2023年，2月20日，星期三若運算*滿足：條件1°,2°，3°,4°,5°則稱G為一個交換群或Abel群。若運算*是普通的加法“+”,則群稱為加群

。若運算*是普通的乘法“×”,則群稱為乘群

。定義2

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

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

第3頁，共45頁，2023年，2月20日，星期三例3n維方陣的集合加法構成Abel群,對乘法不是群.例4n維非奇異方陣對乘法構成非Abel群。

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

對乘法不是群。例3當m為素數(shù)時,集合{1,2,…,m-1}對模m乘法運算構成Abel群。例4線性分組碼構成Abel群,所以線性分組碼又稱為群碼。第4頁，共45頁，2023年，2月20日，星期三（2）域的概念

定義1

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

且有如下規(guī)則:

加法運算

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;第5頁，共45頁，2023年，2月20日，星期三乘法運算

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

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

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

域，有限域亦稱為Galois域。第6頁，共45頁，2023年，2月20日，星期三當有限域中元素的個數(shù)為q時，q稱為域的階，記為GF（q）1°無限域的例子例1有理數(shù)、實數(shù)、復數(shù)集對加法,乘法構成域。例2形如的數(shù)對加法,乘法構成域。2°有限域的例子例1集合{0,1,2,…,m-1}對模m加法,乘法運算構成域。第7頁，共45頁，2023年，2月20日，星期三二元域的運算（1）系數(shù)取自GF（2）的多項式對于（n+1）bit的二進制數(shù)字序列，可以用多項式來描述稱為GF（2）上的n次多項式。其中：的值為0或者1，是二元域GF（2）的元素，對應二進制數(shù)字序列。代表著對應系數(shù)所在的位置。（2）可做長除法

第8頁，共45頁，2023年，2月20日，星期三10.2線性分組碼的基本概念（1)模運算(對于整數(shù))①同余

a=b(modm):a

除以m

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

和b

對于模m

同余.

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

r為模m最小非負剩余模

m

運算:a,b∈{0,1,2,…,m-1}；

r為最小非負剩余；將a+b=r

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

記為這種求a+b

和a×b

的模

m。第9頁，共45頁，2023年，2月20日，星期三

最小非負剩余稱為模m的加法運算和模m的乘法運算.

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

1+1+1=1,1+1+1+1=0,…0-1=1,1-0=1,1-1=0+01001110×01000101第10頁，共45頁，2023年，2月20日，星期三

+012001211202201③模q運算(q進制)

例:q=3×012000010122021第11頁，共45頁，2023年，2月20日，星期三

（2）線性分組碼定義1

設Ci=(ci1,ci

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

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

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

且Cs=Ci+Cj

即csr

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

定義2

設(n,k)分組碼C

中的任意兩個碼字

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

2°C中的任意兩個碼字的和仍為碼C的碼字；則分組碼C稱為(n,k)線性分組碼。第12頁，共45頁，2023年，2月20日，星期三

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

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

信息組m

的k

個碼元(信息位)應包含在線性分組碼的碼字中。第13頁，共45頁，2023年，2月20日，星期三例試構造(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第14頁，共45頁，2023年，2月20日，星期三10.3生成矩陣與校驗矩陣（1）一般線性分組碼的生成矩陣與校驗矩陣線性分組碼（n,k）:把k（bit）的消息矢量線性地映射到n（bit）的碼字其中所有可能的消息構成消息空間M，數(shù)量為個,在碼字空間中所對應的合法碼字為個。第15頁，共45頁，2023年，2月20日，星期三線性映射：若是與消息對應的碼字，則，必定為對應的碼字。碼字空間是n維二元線性空間的k維子空間，存在k個線性獨立（不相關）的二元n維矢量使得任何一個碼字都可表示成的線性組合第16頁，共45頁，2023年，2月20日，星期三其中

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

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

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

第17頁，共45頁，2023年，2月20日，星期三（2）系統(tǒng)線性分組碼的生成矩陣與校驗矩陣定義若信息組m的k個碼元以整體不變的形式,放在碼字的任意位置中

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

。否則

,

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

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

維矩陣。

校驗矩陣其中為k×k階單位方程，以獲得信息位；P為k×（n-k)階矩陣，以獲得校驗位。G可由一般線性分組碼的生成矩陣進行初等變化而得，見例2所示。k位信息位n-k位校驗位n-k位校驗位k位信息位第18頁，共45頁，2023年，2月20日，星期三例1：下面是某（n,k）線性二元碼的全部碼字：（1）求n,k為何值；（2）構造這碼的生成矩陣G；（3）構成這碼的一致校驗矩陣H。第19頁，共45頁，2023年，2月20日，星期三解：（1）∵碼字數(shù)M=8=k=3,n=6為（6,3）線性分組碼。（2）生成矩陣G為k=3行,n=6列的矩陣，由k=3個線性獨立的碼字組成。故（3）設信息位為，則碼字∴第20頁，共45頁，2023年，2月20日，星期三∴∴一致校驗矩陣為第21頁，共45頁，2023年，2月20日，星期三例2

構造一個等價于例1中的（6，3）系統(tǒng)線性分組碼。（1）構造（6，3）線性分組碼的生成矩陣；（2）構造這碼的一致校驗矩陣；（3）列出所有的碼字。比較與例1中的碼的糾、檢錯能力。解：（1）將例1中的生成矩陣G進行初等變換，使其成為等價的（6，3）系統(tǒng)線性分組碼的標準生成矩陣。得為等價（6，3）系統(tǒng)線性分組碼的標準生成矩陣。第22頁，共45頁，2023年，2月20日，星期三（2）由得（3）由可生成全部碼字：這線性分組碼的最小漢明距離而由G生成的線性分組碼C的最小漢明距離所以此兩碼的糾、檢測錯誤能力相同。第23頁，共45頁，2023年，2月20日，星期三

例3

試構造(5,2)

線性分組碼,且

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

(00)→(00

000)(01)→(01

011)

(10)→(10

101)(11)→(11

110)

第24頁，共45頁，2023年，2月20日，星期三例4

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

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

,且生成矩陣各行矢量(碼字)的對應元素不相同的個數(shù)≥dmin。第25頁，共45頁，2023年，2月20日，星期三（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+++第26頁，共45頁，2023年，2月20日，星期三小結：線性分組碼生成矩陣的特點①生成矩陣不是唯一的；

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

③生成矩陣的行矢量是模2運算下線性無關；

④線性分組碼任一碼字是行矢量模2運算下的線性組合。第27頁，共45頁，2023年，2月20日，星期三10.3

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

伴隨式:矢量為接收碼矢r的伴隨式，表示為②第28頁，共45頁，2023年，2月20日，星期三③陪集：設群G的子群將它與H中的元依次相加，得，稱a+H為H的一個陪集，a稱為該陪集的陪集首。第29頁，共45頁，2023年，2月20日，星期三（2）標準陣列譯碼法將個可能的接收矢量劃分為個不相交的子集，使每個子集只含有一個碼矢（碼字），該陣列稱為標準陣。表示如下：（n,k）線性分組碼的標準陣第30頁，共45頁，2023年，2月20日，星期三①標準陣構成：第一行：以全0碼字開始，包含所有碼字；第一列：陪集首項，包含了所有可糾正的錯誤圖樣。為全0矢量，既是許用碼組中的一個碼字，也是錯誤圖樣，代表沒有錯誤的情況。其他項為所在行與列對應碼字之和②性質：

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

b）標準陣的陪集首為該（n，k）碼所能糾正的錯誤圖樣，為個。

c）重量越輕的陪集首所對的錯誤出現(xiàn)的概率越大。當且僅當錯誤圖樣不是陪集首時才出現(xiàn)譯碼錯誤。第31頁，共45頁，2023年，2月20日，星期三③

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

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

第34頁，共45頁，2023年，2月20日，星期三伴隨式譯碼方法：存儲個陪集首項（錯誤圖樣）和所對應的伴隨式。①計算接收到碼字r的伴隨式若s=0，表示r為許用碼字，沒錯。若不為0，轉②。②根據(jù)s查出所對應的錯誤圖樣e。③糾正錯誤，譯碼：輸出正確碼字。第35頁，共45頁，2023年，2月20日，星期三第36頁，共45頁，2023年，2月20日，星期三第37頁，共45頁，2023年，2月20日，星期三