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

1、信息论与编码Information Theory & Coding 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 (交换律 ) 如果这种运算 * 满足：条件1, 2, 3, 4 则 G 称对 代数运算为一个群,或称 G为一个

2、非交换群. 第十章 线性分组码若运算 *满足：条件 1,2，3,4 ,5则称G为一个交换群或Abel群。若运算 * 是普通的加法“+”,则群称为加群 。若运算 * 是普通的乘法“”,则群称为乘群 。定义2 若群G 仅有有限个原素则称为有限群 ；否则为无限群。 1）无限群举例例1 整数集对加法构成Abel群 ,对乘法不是群。 例2 有理数、实数、复数集对加法构成Abel群 ，不含数 0 的有理数、实数、复数集对乘法构成Abel群。 例3 n 维方阵的集合加法构成Abel群 ,对乘法不是群.例4 n 维非奇异方阵对乘法构成非Abel群。 2）有限群举例例1 数 0 对加法构成群 , 数 1 对乘法

3、构成群。例2 集合 0 , 1 , 2 , , m-1对模m加法运算构成Abel群 , 对乘法不是群。例3 当 m 为素数时 , 集合 1 , 2 , , m-1对模 m 乘法运 算构成Abel群。 例4 线性分组码构成Abel群 , 所以线性分组码又称为群码。（2） 域的概念 定义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

4、存在0 F , a F , 有 a0 = a ； 5 a F , 存在 - a F , 有 a(- a) = 0 ;当有限域中元素的个数为q时，q称为域的阶，记为GF（q）1无限域的例子例1 有理数、实数、复数集对加法 , 乘法构成域。例2 形如 的数对加法 ,乘法构成域。2有限域的例子例1 集合 0 , 1 , 2 , , m-1对模 m加法,乘法运算构成域。二元域的运算（1）系数取自GF（2）的多项式 对于（n+1）bit的二进制数字序列，可以用多项式来描述称为GF（2）上的n次多项式。其中： 的值为0或者1，是二元域GF（2）的元素，对应二进制数字序列。 代表着对应系数所在的位置。（2）

5、可做长除法 最小非负剩余称为模m 的加法运算和模 m的乘法运算. 为了简单起见 , 以后将运算符号 简记为+和。 模 2 运算 (二进制) 1+1+1=1 , 1+1+1+1=0 , 0-1=1 , 1-0=1 , 1-1=0+0100111001000101 +012001211202201 模 q 运算(q进制) 例 : q=3012000010122021 （2） 线性分组码定义1 设Ci =(ci 1 ,ci 2 , ,ci n ), Cj=(cj 1 ,cj2 , ,cj n )是二元码 C 的两个码字 , 则 Ci 与 Cj 的和 为 Ci 与 Cj对应码元的模 2 运算 ；若 C

6、s = ( cs 1 , cs 2 , ,cs n ) 且 Cs =Ci + Cj 即 cs r = ci r + cj r (r =1, 2, ,n ) 定义2 设( n , k )分组码 C 中的任意两个码字 1C 中有全 0 码元的码字； 2C 中的任意两个码字的和仍为码 C 的码字； 则分组码 C 称为( n , k )线性分组码 。例 试构造 (5 , 2) 线性分组码 , 且d min = 3 信息组 m 00 01 10 11 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100

7、 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 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 10111

8、11110 11101 11100 11110 11011 11010 11101 11001 1100110.3 生成矩阵与校验矩阵（1） 一般线性分组码的生成矩阵与校验矩阵 线性分组码（n, k）: 把 k（ bit）的消息矢量线性地映射到 n（bit）的码字其中 所有可能的消息构成消息空间M，数量为 个,在码字空间中所对应的合法码字为 个。其中 校验矩阵：在接收端进行正确译码，将码字的校验元和信息元的线性组合关系用方程表示，其对应矩阵形式为一致校验矩阵 H 满足 ，则码字正确。生成矩阵G的行与一致校验矩阵H的行相互正交。 为生成矩阵，由该矩阵中的行向量的任意线性组合都构成一个码字。 （2

9、） 系统线性分组码的生成矩阵与校验矩阵 定义 若信息组 m的 k 个码元以整体不变的形式 , 放在码字的任意位置中 , 该码为系统码 。 否则 , 称为非系统码. 系统码通常如下图将信息组放在码字的最左边或最右边。上图右所表示的系统码：生成矩阵 为k n 维矩阵。 校验矩阵其中 为kk阶单位方程，以获得信息位；P为k（n-k)阶矩阵，以获得校验位。G可由一般线性分组码的生成矩阵进行初等变化而得，见例2所示。k 位信息位n- k位校验位n- k 位校验位k位信息位例1：下面是某（n,k）线性二元码的全部码字：（1）求n ,k为何值；（2）构造这码的生成矩阵G；（3）构成这码的一致校验矩阵H。解：

10、（1）码字数 M = 8 = k = 3 , n = 6为（6, 3）线性分组码。 （2）生成矩阵G为 k = 3 行, n = 6列的矩阵，由k = 3 个线性独立的码字组成。 故（3）设信息位为 ，则码字 一致校验矩阵为例2 构造一个等价于例1中的（6，3）系统线性分组码。 （1）构造（6，3）线性分组码的生成矩阵； （2）构造这码的一致校验矩阵； （3）列出所有的码字。比较与例1中的码的纠、检错能力。解：（1）将例1中的生成矩阵G进行初等变换，使其成为等价的（6，3）系统线性分组码的标准生成矩阵。得 为等价（6，3）系统线性分组码的标准生成矩阵。 例3 试构造 (5 , 2) 线性分组码

11、 , 且 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) 例4 试构造 (7 , 4) 线性分组码 , 且d min = 3（1）构造生成矩阵生成矩阵生成的线性分组码要有尽可能大的d min , 即生成矩阵的行矢量中的“1”的个数 d min , 且生成矩阵各行矢量(码字)的对应元素不相同的个数 d min 。小结： 线性分组码生成矩阵的特点 生成矩阵不是唯一的； 生成矩阵的行矢量均为线性分组码的码字； 生成矩阵的行矢量是模 2

12、运算下线性无关； 线性分组码任一码字是行矢量模 2 运算下的线性组合。10.3 线性分组码的译码（1）相关概念 错误图样：设发端发送的码字为为 个许用码组中的一个，经信道传输后，收到的矢量为 ，为 个码字中的一个。其中 为错误矢量，称错误图样。纠错码的任务：确定错误图样。 伴随式: 矢量 为接收码矢r的伴随式，表示为 陪集：设群G 的子群 将它与H中的元依次相加，得 ， 称a+H 为H的一个陪集，a 称为该陪集的陪集首。（2）标准阵列译码法将 个可能的接收矢量划分为 个不相交的子集，使每个子集只含有一个码矢（码字），该阵列称为标准阵。表示如下：（n, k）线性分组码的标准阵 标准阵构成：第一行

13、：以全0码字开始，包含所有码字；第一列：陪集首项，包含了所有可纠正的错误图样。 为全0矢量，既是许用码组中的一个码字，也是错误图样，代表没有错误的情况。其他项为所在行与列对应码字之和 性质： a）两个陪集不相交，或重合。即矩阵各行不相交。 b）标准阵的陪集首为该（n，k）码所能纠正的错误图样，为 个。 c）重量越轻的陪集首所对的错误出现的概率越大。当且仅当错误图样不是陪集首时才出现译码错误。 译码：接收的码字 ，必定落在标准阵列中的某一行。 由最大释然准则，把与接收矢量最近的码字译为发送码字。即在 标准阵中寻找最轻重量的矢量作为错误形式。 利用 恢复码字。小结：标准阵列译码法为基础译码法，直观

14、，但不最优。具体应用时，只用列出重量为t的陪集阵列。例：下面列出一个具有4个码字的（6，2）线性码这个码的最小汉明距离为3，可以纠正一个错误。共有6个一位错误图样，其限制距离为1的译码表如下： 完整的标准阵列，还有9列。含有2位的错误图样共有种。000000010101101010111111000001010100101011111110000010010111101000111101000100010001101110111011001000011101100010110111010000000101111010101111100000110101001010011111该（6，2）线性码

15、部分译码表其中二位错误形式（101000），（010100），（001010），（000101），（010001），（100010）已经在标准阵的前6行中出现，所以这6种为不可纠正的错误，余下的9种错误图样可作为陪集首项，得到不相交的陪集，对应了可纠正2位错误形式。（3）伴随式译码法与接收码字r对应的伴随式 为0的充要条件：码字r为许用码字。由 ， 而所以伴随式由错误图样决定，且一一对应。 伴随式译码方法： 存储 个陪集首项（错误图样）和所对应的伴随式。计算接收到码字r的伴随式 若s=0，表示r为许用码字，没错。若不为0，转。根据s查出所对应的错误图样e。纠正错误，译码： 输出正确码字。 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