信息基础与编码理论第十章讲稿.ppt

《信息基础与编码理论第十章讲稿.ppt》由会员分享，可在线阅读，更多相关《信息基础与编码理论第十章讲稿.ppt（45页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、信息基础与编码理论第十章第一页，讲稿共四十五页哦10.1 近世代数学的基础知识近世代数学的基础知识（1） 群的概念群的概念 定义定义1 G是一个非空集合，是一个非空集合，*是是G中的一个代数运算，若中的一个代数运算，若 1 a , bG , 有有 a * b G (封闭性封闭性) 2 a , b , cG , 有有(a * b) * c = a * ( b * c ) (结合律结合律) 3存在单位元素存在单位元素 eG , aG , 有有e * a = a * e = a 4 aG , 存在逆元素存在逆元素 G , 有有 5 a , bG , 有有 a * b = b * a (交换律交换律

2、) 如果这种运算如果这种运算 * 满足：条件满足：条件1, 2, 3, 4 则则 G 称对称对 代数运算为一个群代数运算为一个群,或称或称 G为一个为一个非交换群非交换群. 11a aaae1a第十章第十章 线性分组码线性分组码第二页，讲稿共四十五页哦若运算若运算 * *满足：条件满足：条件 1 1,2,2，3 3,4,4 ,5 ,5则称则称G G为一个为一个交换交换群群或或AbelAbel群群。若运算若运算 * * 是普通的加法是普通的加法“+”,+”,则群称为则群称为加群加群 。若运算若运算 * * 是普通的乘法是普通的乘法“”,”,则群称为则群称为乘群乘群 。定义定义2 2 若群若群G

3、G 仅有有限个原素则称为仅有有限个原素则称为有限群有限群 ；否则为；否则为无限群无限群。 1 1）无限群举例）无限群举例例例1 1 整数集对加法构成整数集对加法构成AbelAbel群群 , ,对乘法不是群。对乘法不是群。 例例2 2 有理数、实数、复数集对加法构成有理数、实数、复数集对加法构成AbelAbel群群 ，不含数，不含数 0 0 的有的有理数、实数、复数集对乘法构成理数、实数、复数集对乘法构成AbelAbel群。群。 第三页，讲稿共四十五页哦例例3 3 n n 维方阵的集合加法构成维方阵的集合加法构成AbelAbel群群 , ,对乘法不是群对乘法不是群. .例例4 4 n n 维非奇

4、异方阵对乘法构成非维非奇异方阵对乘法构成非AbelAbel群。群。 2 2）有限群举例）有限群举例例例1 1 数数 0 0 对加法构成群对加法构成群 , , 数数 1 1 对乘法构成群。对乘法构成群。例例2 集合集合 0 , 1 , 2 , , m-1对模对模m加法运算构成加法运算构成Abel群群 , 对乘法不是群。对乘法不是群。例例3 当当 m 为素数时为素数时 , 集合集合 1 , 2 , , m-1对模对模 m 乘法运乘法运 算构成算构成Abel群。群。 例例4 线性分组码构成线性分组码构成Abel群群 , 所以线性分组码又称为所以线性分组码又称为群码群码。第四页，讲稿共四十五页哦（2）

5、 域的概念域的概念 定义定义1 F 是一个非空集合是一个非空集合 , 对于对于F 的任意两个元素的任意两个元素a 和和 b ,定定义集合元素的加法运算义集合元素的加法运算 , 记作记作ab ; 乘法运算乘法运算 ,记作记作a b ; 且有如且有如下规则下规则 : 加法运算加法运算 1 a , b F , 有有 ab F ; 2 a , b F , 有有 ab = ba ; 3 a，b，c F , 有有 (ab)c = a( bc) ; 4存在存在0 F , a F , 有有 a0 = a ； 5 a F , 存在存在 - a F , 有有 a(- a) = 0 ; 第五页，讲稿共四十五页哦乘法

6、运算乘法运算 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 存在存在e F , a F , 有有 a e = a ； 5 a F ,且且a0 , 存在存在 a -1 F , 有有 a a -1= e ; 乘法对加法的分配律乘法对加法的分配律 a , b , c F , 有有 a (bc) = a ba c 以上运算规则都成立，则称以上运算规则都成立，则称 F 对于所规定的加法运算对于所规定的加法运算和乘法运算是一个域和乘法运算是一个域 . .定义定义2 设设F 是一

7、个域是一个域 , 如果如果F 中的元素个数无限中的元素个数无限 , 则则F 称为称为 无限域无限域 . 如果如果 F 中的元素个数有限中的元素个数有限 , 则则 F 称为有限称为有限 域，有限域亦称为域，有限域亦称为Galois域域。第六页，讲稿共四十五页哦当有限域中元素的个数为当有限域中元素的个数为q q时，时，q q称为域的阶，记为称为域的阶，记为GFGF（q q）1 1无限域的例子无限域的例子例例1 1 有理数、实数、复数集对加法有理数、实数、复数集对加法 , , 乘法构成域。乘法构成域。例例2 2 形如形如 的数对加法的数对加法 , ,乘法构成域。乘法构成域。2 2有限域的例子有限域的

8、例子例例1 1 集合集合 0 , 1 , 2 , , 0 , 1 , 2 , , m m-1-1对模对模 m m加法加法, ,乘法运算构成域乘法运算构成域。Rbaba ,2第七页，讲稿共四十五页哦二元域的运算二元域的运算（1）系数取自）系数取自GF（2）的多项式）的多项式 对于（对于（n+1）bit的二进制数字序列，可以用多项式来描述的二进制数字序列，可以用多项式来描述称为称为GF（2）上的）上的n次多项式。次多项式。其中：其中： 的值为的值为0或者或者1，是二元域，是二元域GF（2）的元素，对应二进制）的元素，对应二进制数字序列。数字序列。 代表着对应系数所在的位置。代表着对应系数所在的位置

9、。（2）可做长除法）可做长除法 12212210( )nnnnnnf xf xfxfxf xf xfifix( )( ) ( )( )( )0f xq x g xr xg x第八页，讲稿共四十五页哦10.2 10.2 线性分组码的基本概念线性分组码的基本概念（1) 1) 模运算模运算( (对于整数对于整数) ) 同余同余 a =b(mod m): a 除以除以 m 与与 b 除以除以 m(m1)的余数的余数 相同；相同； 或称为或称为 a 和和 b 对于模对于模 m 同余同余 . . 最小非负剩余最小非负剩余: : a = r (mod m) ; 0 r m ； r r 为模为模 m m最小非

10、负剩余最小非负剩余 模模 m 运算运算: : a ,b 0 ,1 ,2 , , m-1 ； r为最小非为最小非 负剩余；将负剩余；将a + b =r (mod m), a b =r (mod m) 记为记为 这种求这种求a + b 和和 a b 的模的模 m。rbarba 第九页，讲稿共四十五页哦 最小非负剩余称为模最小非负剩余称为模m m 的加法运算和模的加法运算和模 m m的乘法运算的乘法运算. . 为了简单起见为了简单起见 , , 以后将运算符号以后将运算符号 简记为简记为+ +和和。 模模 2 2 运算运算 ( (二进制二进制) ) 1+1+1=1 , 1+1+1+1=0 , 0-1=

11、1 , 1-0=1 , 1-1=0 ,+0100111001000101第十页，讲稿共四十五页哦 +012001211202201 模模 q 运算运算(q进制进制) 例例 : q=3012000010122021第十一页，讲稿共四十五页哦 （2 2） 线性分组码线性分组码定义定义1 1 设设Ci =(ci 1 ,ci 2 , ,ci n ), Cj=(cj 1 ,cj2 , ,cj n ) )是二元码是二元码 C 的两个码的两个码字字 , , 则则 Ci 与与 Cj 的和的和 为为 C Ci i 与与 C Cj j对应码元的模对应码元的模 2 2 运算运算 ；若；若 Cs = ( cs 1 ,

12、 cs 2 , ,cs n ) 且且 Cs =Ci + Cj 即即 cs r = ci r + cj r (r =1, 2, ,n ) 定义定义2 2 设设( n , k )分组码分组码 C 中的任意两个码字中的任意两个码字 1 1C 中有全中有全 0 0 码元的码字；码元的码字； 2 2C 中的任意两个码字的和仍为码中的任意两个码字的和仍为码 C 的码字；的码字； 则分组码则分组码 C 称为称为( n , k )线性分组码线性分组码 。第十二页，讲稿共四十五页哦推论推论 线性分组码线性分组码任意两个以上码字的和任意两个以上码字的和仍为码仍为码 C 的码字。的码字。 根据分组码的定义根据分组码

13、的定义 , 信息组信息组 m 的的 k 个码元个码元(信息位信息位)应包应包 含在线性分组码的码字中。含在线性分组码的码字中。第十三页，讲稿共四十五页哦例例 试构造试构造 (5 , 2) 线性分组码线性分组码 , 且且d min = 3 信息组信息组 m 00 01 10 11 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 1101

14、0 11011 11100 11101 11110 11111 1组组 2组组 3组组 4组组 5组组 6组组 7组组 8组组 9组组00000 00000 00000 00000 00000 00000 00000 00000 0000001011 01011 01011 01101 01101 01101 01110 01110 0111010101 10110 10111 10011 10110 10111 10011 10101 1011111110 11101 11100 11110 11011 11010 11101 11001 11001第十四页，讲稿共四十五页哦10.3 生成矩

15、阵与校验矩阵生成矩阵与校验矩阵（1） 一般线性分组码一般线性分组码的的生成矩阵与校验矩阵生成矩阵与校验矩阵 线性分组码（线性分组码（n, k）: 把把 k（ bit）的消息矢量的消息矢量线性地映射到线性地映射到 n（bit）的码字的码字其中其中 所有可能的消息构成消息空间所有可能的消息构成消息空间M，数量为，数量为 个个,在码字空间中所在码字空间中所对应的合法码字为对应的合法码字为 个。个。011(,)kmmmm011(,)ncccc0,10,1,1imik0,10,1,1jcjn2k2k第十五页，讲稿共四十五页哦线性映射：线性映射：若若 是与消息是与消息 对应的码字，则对应的码字，则 ，必定

16、为，必定为 对应的码字。对应的码字。 码字空间是码字空间是n维二元线性空间的维二元线性空间的k维子空间，存在维子空间，存在k个线性独立个线性独立（不相关）的二元（不相关）的二元n 维矢量维矢量使得任何一个码字都可表示成使得任何一个码字都可表示成 的线性组合的线性组合12,c c12,m m12cc12mm000010,1110111,111,01,11,1(,)(,)(,)nnkkkkngggggggggggg011,kggg001111kkGcm gm gmgm第十六页，讲稿共四十五页哦其中其中 校验矩阵：校验矩阵：在接收端进行正确译码，将码字的校验元和信息元的线性组在接收端进行正确译码，将

17、码字的校验元和信息元的线性组合关系用方程表示，其对应矩阵形式为合关系用方程表示，其对应矩阵形式为一致校验矩阵一致校验矩阵 H 满足满足 ，则码字正确。，则码字正确。生成矩阵生成矩阵G的行与一致校验矩阵的行与一致校验矩阵H的行相互正交。的行相互正交。 011(,)kmm mm011kggGg为为生成矩阵生成矩阵，由该矩阵中的行向量的任意，由该矩阵中的行向量的任意线性组合都构成一个码字。线性组合都构成一个码字。 00TTG HH G或 第十七页，讲稿共四十五页哦（2） 系统线性分组码系统线性分组码的的生成矩阵与校验矩阵生成矩阵与校验矩阵 定义定义 若信息组若信息组 m的的 k 个码元以整体不变的形

18、式个码元以整体不变的形式 , 放在码字的任意位放在码字的任意位置中置中 , 该码为该码为系统码系统码 。 否则否则 , 称为称为非系统码非系统码. 系统码通常如下图将信息组放在码字的最左边或最右边。系统码通常如下图将信息组放在码字的最左边或最右边。上上图右图右所表示的系统码：所表示的系统码：生成矩阵生成矩阵 为为k n 维矩阵。维矩阵。 校验矩阵校验矩阵其中其中 为为kk k阶单位方程，阶单位方程，以获得信息位；以获得信息位；P P为为k（n-k)k)阶矩阵，阶矩阵，以获得校验位以获得校验位。G G可由一般线性分组码的生成矩阵进行初等变化而得，可由一般线性分组码的生成矩阵进行初等变化而得，见例

19、见例2 2所示。所示。kGPIk 位信息位位信息位n- k位校验位位校验位n- k 位校验位位校验位k位信息位位信息位Tn kHIPkI第十八页，讲稿共四十五页哦例例1：下面是某下面是某（n,k）线性二元码的全部码字：线性二元码的全部码字：（1）求）求n ,k为何值；为何值；（2）构造这码的生成矩阵）构造这码的生成矩阵G；（3）构成这码的一致校验矩阵）构成这码的一致校验矩阵H。12345678000000000111011001011110101011101100110010110101cccccccc第十九页，讲稿共四十五页哦解解：（：（1）码字数码字数 M = 8 = k = 3 , n

20、= 6为（为（6, 3）线性分组码。）线性分组码。 （2）生成矩阵）生成矩阵G为为 k = 3 行行, n = 6列的矩阵，由列的矩阵，由k = 3 个线性独立的个线性独立的码字组成。码字组成。 故故（3）设信息位为）设信息位为 ，则码字，则码字322k000111011001101011G123()mm m m123000111() 011001101011cm Gm m m第二十页，讲稿共四十五页哦132212332312145411246513416123421000cmcmccccmmccccccmcccccmmcccmmmccc 一致校验矩阵为一致校验矩阵为1 11000100110

21、1 10101H第二十一页，讲稿共四十五页哦例例2 2 构造一个等价于例构造一个等价于例1 1中的（中的（6 6，3 3）系统线性分组码。）系统线性分组码。 （1 1）构造（）构造（6 6，3 3）线性分组码的生成矩阵；）线性分组码的生成矩阵； （2 2）构造这码的一致校验矩阵；）构造这码的一致校验矩阵； （3 3）列出所有的码字。比较与例）列出所有的码字。比较与例1 1中的码的纠、检错能力。中的码的纠、检错能力。解解：（：（1 1）将例）将例1 1中的生成矩阵中的生成矩阵G G进行初等变换，使其成为等价的（进行初等变换，使其成为等价的（6 6，3 3）系统线性分组码的标准生成矩阵。）系统线性

22、分组码的标准生成矩阵。得得 为等价（为等价（6 6，3 3）系统线性分组码的标准生成矩阵。）系统线性分组码的标准生成矩阵。(1)3000111000111011001110001101011101011100011010101001111kGIPG(1) 列与（ ）列互换列与（4）列互换G第二十二页，讲稿共四十五页哦（2）由）由 得得（3）由）由 可生成全部码字：可生成全部码字：这线性分组码这线性分组码 的最小汉明距离的最小汉明距离而由而由G生成的线性分组码生成的线性分组码C的最小汉明距离的最小汉明距离所以此两码的纠、检测错误能力相同。所以此两码的纠、检测错误能力相同。G011 1001010

23、10111001Tn kHPIG12345678000000100011010101001111110110011010101100111001cccccccccminmin()30iiidW ccccminmin( )30iiidW cccc第二十三页，讲稿共四十五页哦 例例3 3 试构造试构造 (5 , 2) 线性分组码线性分组码 , , 且且 m=(m1 m2 ) = (00) , (01) , (10) , (11) (00) (0 0 0 0 0) (01) (0 1 0 1 1) (10) (1 0 1 0 1) (11) (1 1 1 1 0) 1101010101)()(215

24、4321mmmGcccccCiiiiiimin3d121212()icmmmmmm第二十四页，讲稿共四十五页哦例例4 试构造试构造 (7 , 4) 线性分组码线性分组码 , 且且d min = 3（1）构造生成矩阵）构造生成矩阵生成矩阵生成的线性分组码要有尽可能大的生成矩阵生成的线性分组码要有尽可能大的d min , , 即生即生成矩阵的行矢量中的成矩阵的行矢量中的“1”1”的个数的个数 d min , , 且生成矩阵各行矢量且生成矩阵各行矢量( (码字码字) )的对应元素不相同的个数的对应元素不相同的个数 d min 。 1101000011010011100101010001G100010

25、1010001100101100001010G第二十五页，讲稿共四十五页哦（2）编码器的实现编码器的实现 上例上例 m=(m1 m2 m3 m4) m1 , m2 , m3 , m4 0 ,1 Ci = mGCi = (c1 c2 c3 c4 c5 c6 c7) = (m1 m2 m3 m4 m1+m2 + m3 m2+m3+m4 m1+m2+m4)m1 c1 m2 c2 m3 c3 m4 c4 c5 c6 c7 1101000011010011100101010001G+第二十六页，讲稿共四十五页哦小结：小结： 线性分组码生成矩阵的特点线性分组码生成矩阵的特点 生成矩阵不是唯一的；生成矩阵不

26、是唯一的； 生成矩阵的行矢量均为线性分组码的码字；生成矩阵的行矢量均为线性分组码的码字； 生成矩阵的行矢量是模生成矩阵的行矢量是模 2 2 运算下线性无关；运算下线性无关； 线性分组码任一码字是行矢量模线性分组码任一码字是行矢量模 2 2 运算下的线性组合。运算下的线性组合。第二十七页，讲稿共四十五页哦10.3 线性分组码的译码线性分组码的译码（1）相关概念）相关概念 错误图样错误图样：设发端发送的码字为：设发端发送的码字为为为 个许用码组中的一个，经信道传输后，收到的矢量为个许用码组中的一个，经信道传输后，收到的矢量为 ，为，为 个码字中的一个。个码字中的一个。其中其中 为错误矢量，称为错误

27、矢量，称错误图样错误图样。纠错码的任务纠错码的任务：确定错误图样。：确定错误图样。 伴随式伴随式: : 矢量矢量 为接收码矢为接收码矢r r的伴随式，表示为的伴随式，表示为12( ,)ncc cc2k12( ,)nrr rr2nrce12( ,)nee eeTrHTsrH第二十八页，讲稿共四十五页哦 陪集陪集：设群：设群G G 的子群的子群 将它与将它与H H中的元中的元依次相加，得依次相加，得 ， 称称a+H a+H 为为H H的一个陪的一个陪集，集，a a 称为该陪集的陪集首。称为该陪集的陪集首。12,rHhe hhaH,1,2, iaHah ir第二十九页，讲稿共四十五页哦（2）标准阵列

28、译码法）标准阵列译码法将将 个可能的接收矢量划分为个可能的接收矢量划分为 个不相交的子集，使每个子个不相交的子集，使每个子集只含有一个码矢（码字），该阵列称为集只含有一个码矢（码字），该阵列称为标准阵标准阵。表示如下：。表示如下：2n2k112222222232333222222222kkkkn kn kn kkn kiiijjijjic ecccecececeecececeecececeececece（n, k）线性分组码的标准阵线性分组码的标准阵第三十页，讲稿共四十五页哦11ceijce2n k2n k2n k第三十一页，讲稿共四十五页哦 译码：译码：接收的码字接收的码字 ，必定落在标准阵

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

30、，可以纠正一个错误。共有，可以纠正一个错误。共有6 6个一位错误图个一位错误图样，其限制距离为样，其限制距离为1 1的译码表如下：的译码表如下： ijrceijcre(000000),(010101),(101010),(111111)c 第三十二页，讲稿共四十五页哦0000000101011010101111110000010101001010111111100000100101111010001111010001000100011011101110110010000111011000101101110100000001011110101011111000001101010010100111

31、11该（该（6，2）线性码部分译码表）线性码部分译码表2615c 第三十三页，讲稿共四十五页哦其中二位错误形式（其中二位错误形式（101000），（），（010100），（），（001010），（），（000101），（），（010001），（），（100010）已经在标准阵的前）已经在标准阵的前6行中出现，行中出现，所以这所以这6种为不可纠正的错误，余下的种为不可纠正的错误，余下的9种错误图样可作为陪集首项种错误图样可作为陪集首项，得到不相交的陪集，对应了可纠正，得到不相交的陪集，对应了可纠正2位错误形式。位错误形式。（3）伴随式译码法）伴随式译码法与接收码字与接收码字r对应的伴随式对应的伴

32、随式 为为0的充要条件：码字的充要条件：码字r为许用码字为许用码字。由由 ， 而而所以伴随式由错误图样决定，且一一对应。所以伴随式由错误图样决定，且一一对应。 TsrHrce()TTTTsce HcHeHeH第三十四页，讲稿共四十五页哦伴随式译码方法：伴随式译码方法： 存储存储 个陪集首项（错误图样）和所对应的伴随式。个陪集首项（错误图样）和所对应的伴随式。计算接收到码字计算接收到码字r r的伴随式的伴随式 若若s=0s=0，表示，表示r r为许用码字为许用码字，没错。若不为，没错。若不为0 0，转。，转。根据根据s s查出所对应的错误图样查出所对应的错误图样e e。纠正错误，译码：纠正错误，

33、译码： 输出正确码字。输出正确码字。21rTsrHcre第三十五页，讲稿共四十五页哦第三十六页，讲稿共四十五页哦第三十七页，讲稿共四十五页哦 2) 一致校验矩阵一致校验矩阵 (n , k) 线性分组码为一系统码线性分组码为一系统码 , 则码字有则码字有 (c1 c2 ck ck+1 cn) = (m1 m2 mk ck+1 cn) 由生成矩阵由生成矩阵 G 生成的码字生成的码字 (c1 c2 ck ck+1 cn) = (m1 m2 mk ) G = (m1 m2 mk ) I k P k(n-k) 码字的校验位码字的校验位 ( ck+1 cn) = (m1 m2 mk ) P k(n-k)=

34、(c1 c2 ck ) P k(n-k) (c1 c2 ck ) P k(n-k)- ( ck+1 cn) = 0 1(n-k) (c1 c2 ck ) P k(n-k)+ ( ck+1 cn) I (n-k) = 0 1(n-k)第三十八页，讲稿共四十五页哦 一致校验矩阵一致校验矩阵H (简称校验矩阵简称校验矩阵) 当系统码生成矩阵当系统码生成矩阵 G 确定后确定后 , 校验矩阵校验矩阵H由生成矩阵中的由生成矩阵中的分块矩阵分块矩阵P k(n-k)确定确定. 由生成矩阵由生成矩阵G 生成的任一码字生成的任一码字Ci 均满足下式均满足下式 , 不是不是G生成生成码字则不满足下式码字则不满足下式 因此因此 ,校验矩阵校验矩阵H 可以判断是否为码字可以判断是否为码字.)(1)()(1210)(knknknknkkIPccccc )()()(knnknknkTIPH () ()Tn kn knHP I1 ()() 100TTin kn kC Hi或HC第三十九页，讲稿共四十五页哦 第四十页，讲稿共四十五页哦第四十一页，讲稿共四十五页哦第四十二页，讲稿共四十五页哦第四十三页，讲稿共四十五页哦 第四十四页，讲稿共四十五页哦 第四十五页，讲稿共四十五页哦