码纠错能力的判断 ·任一(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,bG ，恒有 a bG 2) 结合律。对任意 a,b,cG ，恒有 (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)——是一类加群，集合中的元素是 欧氏空间中的离散点