编码技术数学基础

1、编码技术数学基础第1页，共19页，2022年，5月20日，20点30分，星期二简单基础最大公约数GCD最小公倍数LCM同余和剩余类同余类的加减乘除第2页，共19页，2022年，5月20日，20点30分，星期二群一个系统、一种数学系统、一种代数结构非空集合G和G上定义的一种运算“”，并满足条件：封闭性，任意两个集合中元素的运算结果仍是集合的元素, 即任意a,bG，有a b G结合律，(ab)c=a(bc)存在单位元e对任意集合中元素a，有逆元a-1，使得a a-1=a-1a=e规定：n个a的运算记为a a a=an，a0=e满足交换律的群叫交换群或Abel群第3页，共19页，2022年，5月20

2、日，20点30分，星期二群的若干定理及性质群中单位元唯一，每个元素的逆元唯一群中元素的个数称为群的阶循环群：群中每个元素都是a的某个整数次幂an，称该群有a生成，a是该群的生成元使得an=1的最小正整数n，称为a的级n阶循环群中，任意元素的级是n的某个因子n阶循环群中，每个n级的元素都称为n次单位原根单位原根的个数是欧拉数第4页，共19页，2022年，5月20日，20点30分，星期二域非空集合F和F上定义的加法和乘法两种运算，满足条件：F中全体元素构成交换加群，有加法单位元0，a的逆元称为负元，记为-aF中全体非零元素构成交换乘群，乘法单位元为1加法和乘法之间满足分配律记n个a相加为na，n个

3、a相乘为an，a0=1域中元素个数q称为阶，若元素个数有限，则称为有限域或伽罗华域GF(q),Fq第5页，共19页，2022年，5月20日，20点30分，星期二子群，陪集若H是群G的非空子集，且依G上的运算构成群，则H是G的子群G有两个平凡子群，自身和单位元构成的群，其他非平凡子群称为真子群对G的子群H，构建g H=g h1, g h2, ，称为左陪集，构建 H g =h1 g, h2 g, ，称为右陪集，陪集中最左边的第一个称为陪集首交换群中左陪集等于右陪集第6页，共19页，2022年，5月20日，20点30分，星期二陪集的性质G关于H的所有陪集构成G的一个划分，即所有陪集的并就是G任意两个

4、陪集的任意元素都不同陪集的大小是H的阶，所有陪集大小相同第7页，共19页，2022年，5月20日，20点30分，星期二有限域上的多项式系数取自Fq上的x的多项式称为有限域上的多项式，全体这类多项式的集合记为GF(q)x或Fqx全体系数都为0的零多项式，记为0，x的最高次项为1的多项式称为首一多项式不可约多项式：除了常数和本身，没有其他非零次多项式为因子第8页，共19页，2022年，5月20日，20点30分，星期二多项式的概念次数、根多项式的欧几里得除法多项式互素多项式的最大公因式GCD多项式的最小公倍式LCM多项式的同余和剩余类第9页，共19页，2022年，5月20日，20点30分，星期二有限

5、域的乘法结构以素数q为模的整数剩余类构成q阶有限域GF(q)；以GF(q)上m次首一不可约多项式为模的多项式剩余类构成qm阶有限域GF(qm)有限域GF(q)中非零元素构成q-1阶乘群(循环群)，其中存在一个生成元，级为q-1，是q-1次单位原根，称为本原元GF(q)中q-1个非零元素都是xq-1-1=0的根，反之xq-1-1=0的每个根都在GF(q)中，即任意元素的q-1次方都为1第10页，共19页，2022年，5月20日，20点30分，星期二有限域的加法结构满足n个1（乘法单位元）相加为0的最小n称为域的特征，有限域必然有n存在特征为p的域中，对域中任意元素a必有pa=0GF(p)中，p为

6、素数时，特征为p每个域的特征或为素数或为无穷第11页，共19页，2022年，5月20日，20点30分，星期二二元域GF(2)，模2运算GF(2)加减法一样的结果GF(2)上有2n个n次多项式，xn的系数为1GF(2)上两个多项式的运算满足交换律、结合律和分配律GF(2)上任意的m次多项式能整除xn+1，其中n=2m-1m次不可约多项式若能整除xn+1，且n是满足的最小正整数，n=2m-1，则这个m次不可约多项式成为“本原多项式”第12页，共19页，2022年，5月20日，20点30分，星期二GF(2m)以GF(p)上m次首一不可约多项式为模的多项式剩余类构成pm阶有限域GF(pm)GF(2)上

7、次数小于等于m-1的多项式有2m个，构成2m阶有限域GF(2m)GF(2)是GF(2m)的基域， GF(2m)是GF(2)的扩域，二者的特征都是2GF(2m)=0,1,a,a2,a3, 第13页，共19页，2022年，5月20日，20点30分，星期二多项式GF(2)上的多项式f(X)，若 是GF(2m)的一个元素，且是f(X)的根，则对任意l0， 是f(X)的根 故有 ，易得 称为x的共轭根，x的所有互异共轭根也是GF(2m)的元素(x是GF(2m)的元素)共轭根（元）具有相同的最小多项式，也就是说最小多项式包含所有互异的共轭元第14页，共19页，2022年，5月20日，20点30分，星期二最

8、小多项式GF(q)中q-1个非零元素都是xq-1-1=0的根，反之xq-1-1=0的每个根都在GF(q)中，即任意元素的q-1次方都为1GF(2m)中2m-1个非零元素都是 的根，反之 的每个根都在GF(2m)中，即任意元素的2m-1次方都为1，也就是说GF(2m)中全体元素构成了 的全部根设 是 的一个根，其也可能是一个次数较低的多项式的根，设其中次数最低的多项式为 ，就是元素 的最小多项式第15页，共19页，2022年，5月20日，20点30分，星期二最小多项式 的最小多项式 能整除任何一个GF(2)上的多项式 ，如果 是 的根最小多项式是不可约的GF(2m)的所有元素都的最小多项式都能整

9、除任何一个GF(2)上的多项式 ， GF(2m)的元素 是它的根，若 不可约，则以本原元为根的最小多项式就是本原多项式第16页，共19页，2022年，5月20日，20点30分，星期二例子本原多项式为1+X+X4本原元a三种表示两两之间一一对应，三种形式等价第17页，共19页，2022年，5月20日，20点30分，星期二线性空间基底或基，一组线性无关的向量，其线性组合能表示线性空间V的所有向量零空间（即：解空间，对偶空间），V1是n维线性空间V的子空间，则与V1中每个向量正交的空间V中的其他向量构成的子空间V2， V1和V2互为零空间假设有矩阵Amxn行空间，由矩阵的m行张成的空间，是n维向量空间V的