西安电子科技大学：《信息论与编码理论基础》课程PPT教学课件（编码部分）码纠错能力的判断

码纠错能力的判断 ·任一(n)分组码，若要在码字内： 1)检测e个随机错误，则要求码的最小汉明距离 d>=e+1 2)纠正t个随机错误，则要求d>=2+1 3)纠正t个随机错误，同时检测e(e>=t)个错误， 则要求d>=e+t+1 若一(n,k)分组码的最小汉明距离为d0,则该 码全多可纠正-“2 个错误

码纠错能力的判断 • 任一(n, k)分组码，若要在码字内： 1) 检测e个随机错误，则要求码的最小汉明距离 d0>=e+1 2) 纠正t个随机错误，则要求d0>=2t+1 3) 纠正t个随机错误，同时检测e (e>=t)个错误， 则要求d0>=e+t+1 若一(n,k)分组码的最小汉明距离为d0 ，则该 码至多可纠正       − = 2 d 1 t 个错误

几种基本的译码方法 问题： M→C→R 如何根据接收信号R估计发送序列C,进而估 计信息序列M'? 设计译码算法的原测：使译码错误概率最小 PE=∑ER)P(R P(ER=PC≠C'|R)

几种基本的译码方法 问题： M→C →R 如何根据接收信号R估计发送序列C’ ,进而估 计信息序列M’？ 设计译码算法的原则：使译码错误概率最小 = ( ) ( ) R PE P E R P R P(E R) = P(C  C' R)

最大后验概率译码 (Maximum Posterior Probability) MinPg MinP(ER)=MinP(C+CR) MinPC+CR)=Min(1-P(C=CR) →MaxP(C=C'lR)

MinP MinP(E R) MinP(C C R) E = =  ' MinP(C  C' R) = Min(1− P(C = C' R))  MaxP(C = C' R) 最大后验概率译码 （Maximum Posterior Probability）

最大似然译码 (Maximum Likelihood Decode) RC,c)-rRC） P(R) P(R) MaxP(C,;R)→MaxP(RC,）

最大似然译码 (Maximum Likelihood Decode) ( ) ( ) ( ) ( ) ( ) ( , ) P R P C P RC P R P C R PC R i i i i  = = ( ) ( ) MaxP Ci R  MaxP R Ci

代数初步

代数初步

要求掌握的内容 ·群、子群和陪集的概念 ·环的概念 ·域的概念 ·会判断

要求掌握的内容 • 群、子群和陪集的概念 • 环的概念 • 域的概念 • 会判断

一、同余和剩余类 同余：若整数a和b被同一正整数m除时，有相同 的余数，则称a、b关于模m同余，记为 a =b(modm) 剩余类(Residue):给定正整数m,可将全体整数按 余数相同进行分类，可获得个剩余类，分别用 0,1,.,m-1 a+b-a+b,a.b-a.b

一、同余和剩余类 同余：若整数a和b被同一正整数m除时，有相同 的余数，则称a、b关于模m同余，记为 a  b(modm) 剩余类(Residue)：给定正整数m，可将全体整数按 余数相同进行分类，可获得m个剩余类，分别用 0,1,,m −1 a + b = a + b, a  b = a  b

二、群(Group)的定义 设G是一个非空集合，并在G内定义了一种代 数运算“。”，若满足： 1)封闭性。对任意a,b∈G,恒有aob∈G 2)结合律。对任意，b,c∈G,恒有(aob)oc=ao(boc) 3)G中存在一恒等元e,对任意a∈G,使aoe=eoa=a 4)对任意a∈G,存在a的逆元a1∈G,使 aoa1=a1。a=e 则称G构成一个群。 若加法，恒等元用0表示， 若为乘法，恒等元称为单位元

二、群(Group)的定义 设G是一个非空集合，并在G内定义了一种代 数运算 “ 。”，若满足： 1) 封闭性。对任意 a,bG ，恒有 a  bG 2) 结合律。对任意 a,b,cG ，恒有 (a  b) c = a  (b  c) 3) G中存在一恒等元e,对任意 a G ，使 a  e = e  a = a 4) 对任意 a G a a = a a = e − −   1 1 ，存在a的逆元 a G −1 ，使 则称G构成一个群。 若加法，恒等元用0表示， 若为乘法，恒等元称为单位元

Examples: 1、全体整数 对加法构成群 对乘法不构成群 2、全体偶数 对加法构成群 对乘法不构成群 3、全体实数 对加法构成群 除0元素外，对乘法构成群 4、全体复数 对加法构成群 除0元素外，对乘法构成群 5、全体有理数对加法构成群 除0元素外，对乘法构成群 6、模m的全体剩余类，0,1，，m-1对模m加法构成群 对模m乘法，有待讨论

Examples: 1、全体整数 2、全体偶数 3、全体实数 6、模m的全体剩余类, 0,1,,m −1 4、全体复数 5、全体有理数 对加法构成群 对乘法不构成群 对加法构成群 对乘法不构成群 对加法构成群 除0元素外，对乘法构成群 对加法构成群 除0元素外，对乘法构成群 对加法构成群 除0元素外，对乘法构成群 对模m加法构成群 对模m乘法，有待讨论

三、有关群的几个概念 。 群的阶(Order of a Group) ·有限群(Finite Group)、无限群(Infinite Group) ·加群、乘群 。 阿贝尔群(Abelian Group) 。 半群(Semigroup)、弱群(Monoid) 置换群(Permutation Group)、对称群(Symmetric Group) 。 格(Lattice 是一类加群，集合中的元素是 欧氏空间中的离散点

三、有关群的几个概念 • 群的阶(Order of a Group) • 有限群(Finite Group)、无限群(Infinite Group) • 加群、乘群 • 阿贝尔群(Abelian Group) • 半群(Semigroup)、弱群(Monoid) • 置换群(Permutation Group)、对称群(Symmetric Group) • 格(Lattice)——是一类加群，集合中的元素是 欧氏空间中的离散点