信息基础与编码理论第十章

信息基础与编码理论第十章第一页，共四十五页，2022年，8月28日10.1近世代数学的基础知识（1）群的概念定义1

G是一个非空集合，*是G中的一个代数运算，若

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

称对代数运算为一个群,或称G为一个非交换群.

第十章

线性分组码第二页，共四十五页，2022年，8月28日若运算*满足：条件1°,2°，3°,4°,5°则称G为一个交换群或Abel群。若运算*是普通的加法“+”,则群称为加群

。若运算*是普通的乘法“×”,则群称为乘群

。定义2

若群G仅有有限个原素则称为有限群；否则为无限群。

1）无限群举例例1整数集对加法构成Abel群,对乘法不是群。例2有理数、实数、复数集对加法构成Abel群，不含数0的有理数、实数、复数集对乘法构成Abel群。

第三页，共四十五页，2022年，8月28日例3n维方阵的集合加法构成Abel群,对乘法不是群.例4n维非奇异方阵对乘法构成非Abel群。

2）有限群举例例1数0对加法构成群,数1对乘法构成群。例2集合{0,1,2,…,m-1}对模m加法运算构成Abel群,

对乘法不是群。例3当m为素数时,集合{1,2,…,m-1}对模m乘法运算构成Abel群。例4线性分组码构成Abel群,所以线性分组码又称为群码。第四页，共四十五页，2022年，8月28日（2）域的概念

定义1

F是一个非空集合,对于F的任意两个元素a和b,定义集合元素的加法运算,记作a＋b;乘法运算,记作ab;

且有如下规则:

加法运算

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日乘法运算

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

以上运算规则都成立，则称F对于所规定的加法运算和乘法运算是一个域.定义2

设F是一个域,如果F中的元素个数无限,则F称为无限域.如果F中的元素个数有限,则F称为有限

域，有限域亦称为Galois域。第六页，共四十五页，2022年，8月28日当有限域中元素的个数为q时，q称为域的阶，记为GF（q）1°无限域的例子例1有理数、实数、复数集对加法,乘法构成域。例2形如的数对加法,乘法构成域。2°有限域的例子例1集合{0,1,2,…,m-1}对模m加法,乘法运算构成域。第七页，共四十五页，2022年，8月28日二元域的运算（1）系数取自GF（2）的多项式对于（n+1）bit的二进制数字序列，可以用多项式来描述称为GF（2）上的n次多项式。其中：的值为0或者1，是二元域GF（2）的元素，对应二进制数字序列。代表着对应系数所在的位置。（2）可做长除法

第八页，共四十五页，2022年，8月28日10.2线性分组码的基本概念（1)模运算(对于整数)①同余

a=b(modm):a

除以m

与b除以m(m>1)的余数相同；或称为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。第九页，共四十五页，2022年，8月28日

最小非负剩余称为模m的加法运算和模m的乘法运算.

为了简单起见,以后将运算符号简记为+和×。②模2运算(二进制)

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运算(q进制)

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

（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)线性分组码。第十二页，共四十五页，2022年，8月28日

推论线性分组码任意两个以上码字的和仍为码C

的码字。根据分组码的定义,

信息组m

的k

个码元(信息位)应包含在线性分组码的码字中。第十三页，共四十五页，2022年，8月28日例试构造(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）的码字其中所有可能的消息构成消息空间M，数量为个,在码字空间中所对应的合法码字为个。第十五页，共四十五页，2022年，8月28日线性映射：若是与消息对应的码字，则，必定为对应的码字。码字空间是n维二元线性空间的k维子空间，存在k个线性独立（不相关）的二元n维矢量使得任何一个码字都可表示成的线性组合第十六页，共四十五页，2022年，8月28日其中

校验矩阵：在接收端进行正确译码，将码字的校验元和信息元的线性组合关系用方程表示，其对应矩阵形式为一致校验矩阵H

满足，则码字正确。生成矩阵G的行与一致校验矩阵H的行相互正交。

为生成矩阵，由该矩阵中的行向量的任意线性组合都构成一个码字。

第十七页，共四十五页，2022年，8月28日（2）系统线性分组码的生成矩阵与校验矩阵定义若信息组m的k个码元以整体不变的形式,放在码字的任意位置中

,该码为系统码

。否则

,

称为非系统码.

系统码通常如下图将信息组放在码字的最左边或最右边。上图右所表示的系统码：生成矩阵为k×n

维矩阵。

校验矩阵其中为k×k阶单位方程，以获得信息位；P为k×（n-k)阶矩阵，以获得校验位。G可由一般线性分组码的生成矩阵进行初等变化而得，见例2所示。k位信息位n-k位校验位n-k位校验位k位信息位第十八页，共四十五页，2022年，8月28日例1：下面是某（n,k）线性二元码的全部码字：（1）求n,k为何值；（2）构造这码的生成矩阵G；（3）构成这码的一致校验矩阵H。第十九页，共四十五页，2022年，8月28日解：（1）∵码字数M=8=k=3,n=6为（6,3）线性分组码。（2）生成矩阵G为k=3行,n=6列的矩阵，由k=3个线性独立的码字组成。故（3）设信息位为，则码字∴第二十页，共四十五页，2022年，8月28日∴∴一致校验矩阵为第二十一页，共四十五页，2022年，8月28日例2

构造一个等价于例1中的（6，3）系统线性分组码。（1）构造（6，3）线性分组码的生成矩阵；（2）构造这码的一致校验矩阵；（3）列出所有的码字。比较与例1中的码的纠、检错能力。解：（1）将例1中的生成矩阵G进行初等变换，使其成为等价的（6，3）系统线性分组码的标准生成矩阵。得为等价（6，3）系统线性分组码的标准生成矩阵。第二十二页，共四十五页，2022年，8月28日（2）由得（3）由可生成全部码字：这线性分组码的最小汉明距离而由G生成的线性分组码C的最小汉明距离所以此两码的纠、检测错误能力相同。第二十三页，共四十五页，2022年，8月28日

例3

试构造(5,2)

线性分组码,且

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

(00)→(00

000)(01)→(01

011)

(10)→(10

101)(11)→(11

110)

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

试构造(7,4)线性分组码,且dmin=3（1）构造生成矩阵生成矩阵生成的线性分组码要有尽可能大的dmin

,即生成矩阵的行矢量中的“1”的个数≥dmin

,且生成矩阵各行矢量(码字)的对应元素不相同的个数≥dmin。第二十五页，共四十五页，2022年，8月28日（2）编码器的实现上例

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日小结：线性分组码生成矩阵的特点①生成矩阵不是唯一的；

②生成矩阵的行矢量均为线性分组码的码字；

③生成矩阵的行矢量是模2运算下线性无关；

④线性分组码任一码字是行矢量模2运算下的线性组合。第二十七页，共四十五页，2022年，8月28日10.3

线性分组码的译码（1）相关概念①错误图样：设发端发送的码字为为个许用码组中的一个，经信道传输后，收到的矢量为，为个码字中的一个。其中为错误矢量，称错误图样。纠错码的任务：确定错误图样。

伴随式:矢量为接收码矢r的伴随式，表示为②第二十八页，共四十五页，2022年，8月28日③陪集：设群G的子群将它与H中的元依次相加，得，称a+H为H的一个陪集，a称为该陪集的陪集首。第二十九页，共四十五页，2022年，8月28日（2）标准阵列译码法将个可能的接收矢量划分为个不相交的子集，使每个子集只含有一个码矢（码字），该阵列称为标准阵。表示如下：（n,k）线性分组码的标准阵第三十页，共四十五页，2022年，8月28日①标准阵构成：第一行：以全0码字开始，包含所有码字；第一列：陪集首项，包含了所有可纠正的错误图样。为全0矢量，既是许用码组中的一个码字，也是错误图样，代表没有错误的情况。其他项为所在行与列对应码字之和②性质：

a）两个陪集不相交，或重合。即矩阵各行不相交。

b）标准阵的陪集首为该（n，k）码所能纠正的错误图样，为个。

c）重量越轻的陪集首所对的错误出现的概率越大。当且仅当错误图样不是陪集首时才出现译码错误。第三十一页，共四十五页，2022年，8月28日③

译码：接收的码字，必定落在标准阵列中的某一行。由最大释然准则，把与接收矢量最近的码字译为发送码字。即在标准阵中寻找最轻重量的矢量作为错误形式。利用恢复码字。小结：标准阵列译码法为基础译码法，直观，但不最优。具体应用时，只用列出重量为t的陪集阵列。例：下面列出一个具有4个码字的（6，2）线性码这个码的最小汉明距离为3，可以纠正一个错误。共有6个一位错误图样，其限制距离为1的译码表如下：

第三十二页，共四十五页，2022年，8月28日完整的标准阵列，还有9列。含有2位的错误图样共有种。000000010101101010111111000001010100101011111110000010010111101000111101000100010001101110111011001000011101100010110111010000000101111010101111100000110101001010011111…………该（6，2）线性码部分译码表第三十三页，共四十五页，2022年，8月28日其中二位错误形式（101000），（010100），（001010），（000101），（010001），（100010）已经在标准阵的前6行中出现，所以这6种为不可纠正的错误，余下的9种错误图样可作为陪集首项，得到不相交的陪集，对应了可纠正2位错误形式。（3）伴随式译码法与接收码字r对应的伴随式为0的充要条件：码字r为许用码字。由，而所以伴随式由错误图样决定，且一一对应。

第三十四页，共四十五页，2022年，8月28日伴随式译码方法：存储个陪集首项（错误图样）和所对应的伴随式。①计算接收到码字r的伴随式若s=0，表示r为许用码字，没错。若不为0，转②。②根据s查出所对应的错误图样e。③纠正错误，译码：输出正确码字。第三十五页，共四十五页，2022年，8月28日第三十六页，共四十五页，2022年，8月28日第三十七页，共四十五页，2022年，8月28日