![信息基础与编码理论 第十章课件_第1页](http://file4.renrendoc.com/view/3c53a45cb6e8464e44c9db87a27de26d/3c53a45cb6e8464e44c9db87a27de26d1.gif)
![信息基础与编码理论 第十章课件_第2页](http://file4.renrendoc.com/view/3c53a45cb6e8464e44c9db87a27de26d/3c53a45cb6e8464e44c9db87a27de26d2.gif)
![信息基础与编码理论 第十章课件_第3页](http://file4.renrendoc.com/view/3c53a45cb6e8464e44c9db87a27de26d/3c53a45cb6e8464e44c9db87a27de26d3.gif)
![信息基础与编码理论 第十章课件_第4页](http://file4.renrendoc.com/view/3c53a45cb6e8464e44c9db87a27de26d/3c53a45cb6e8464e44c9db87a27de26d4.gif)
![信息基础与编码理论 第十章课件_第5页](http://file4.renrendoc.com/view/3c53a45cb6e8464e44c9db87a27de26d/3c53a45cb6e8464e44c9db87a27de26d5.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 中职教育一年级上学期《茶叶内含生物活性成分》教学课件
- 箱涵监理规划
- 高等级子午线轮胎生产扩能技术改造项目可行性实施报告
- 校门口交通问题研究报告
- 2024年全国职业院校技能大赛高职组(化工生产技术赛项)考试题库-上(单选题)
- 校园安全工作责任制度
- 保安员专项测试卷含答案试题含答案
- 中班教案红绿灯课件设计
- 中班救护车美术教案
- 人文类纪录片中镜头的组接技巧-以《舌尖上的中国》为例
- 慢性化脓性中耳炎的围手术期护理PPT课件(PPT 21页)
- 新人美版小学美术六上全册PPT课件
- 《过敏性休克》PPT课件(PPT 32页)
- 体育馆钢结构工程施工方案(104页)
- 被子植物APG分类法简介课件
- 蝴蝶基本介绍及标本制作.ppt课件
- 小学三年级数学(下册)口算20和列竖式脱式计算10暑假作业下
- 五年级上册地方课程教学计划
- 【新教材】部编版语文五年级上册课堂作业本答案
- 七年级初一数学竞赛试题及答案
- 三年级语文下学期按要求写句子专项提升练习含答案
评论
0/150
提交评论