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

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

G是一個(gè)非空集合，*是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

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

第十章

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

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

。定義2

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

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

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

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

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

定義1

F是一個(gè)非空集合,對(duì)于F的任意兩個(gè)元素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;第五頁(yè)，共四十五頁(yè)，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;

乘法對(duì)加法的分配律

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

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

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

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

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

a=b(modm):a

除以m

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

和b

對(duì)于模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。第九頁(yè)，共四十五頁(yè)，2022年，8月28日

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

為了簡(jiǎn)單起見,以后將運(yùn)算符號(hào)簡(jiǎ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第十頁(yè)，共四十五頁(yè)，2022年，8月28日

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

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

（2）線性分組碼定義1

設(shè)Ci=(ci1,ci

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

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

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

且Cs=Ci+Cj

即csr

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

定義2

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

中的任意兩個(gè)碼字

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

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

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

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

信息組m

的k

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

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

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

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

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

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

。否則

,

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

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

維矩陣。

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

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

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

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

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

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

m=(m1m2m3m4)

m1,

m2,

m3,

m4∈{0,1}

Ci

=mGCi

=(c1c2c3c4c5c6c7)=(m1m2m3m4m1+m2+

m3m2+m3+m4m1+m2+m4)m1c1m2c2m3c3m4c4

c5

c6

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

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

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

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

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

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

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

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

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

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

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

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