编码技术 数学基础.

Presentation on theme: "编码技术 数学基础."— Presentation transcript:

1 编码技术 数学基础

2 简单基础 最大公约数GCD 最小公倍数LCM 同余和剩余类 同余类的加减乘除

3 群 一个系统、一种数学系统、一种代数结构 规定：n个a的运算记为a · a · … · a=an，a0=e
非空集合G和G上定义的一种运算“·”，并满足条件： 封闭性，任意两个集合中元素的运算结果仍是集合的元素, 即任意a,b∈G，有a ·b ∈G 结合律，(a·b)·c=a·(b·c) 存在单位元e 对任意集合中元素a，有逆元a-1，使得a ·a-1=a-1·a=e 规定：n个a的运算记为a · a · … · a=an，a0=e 满足交换律的群叫交换群或Abel群

4 群的若干定理及性质 群中单位元唯一，每个元素的逆元唯一 群中元素的个数称为群的阶
循环群：群中每个元素都是a的某个整数次幂an，称该群有a生成，a是该群的生成元 使得an=1的最小正整数n，称为a的级 n阶循环群中，任意元素的级是n的某个因子 n阶循环群中，每个n级的元素都称为n次单位原根 单位原根的个数是欧拉数

5 域 非空集合F和F上定义的加法和乘法两种运算，满足条件： 记n个a相加为na，n个a相乘为an，a0=1
F中全体元素构成交换加群，有加法单位元0，a的逆元称为负元，记为-a F中全体非零元素构成交换乘群，乘法单位元为1 加法和乘法之间满足分配律 记n个a相加为na，n个a相乘为an，a0=1 域中元素个数q称为阶，若元素个数有限，则称为有限域或伽罗华域GF(q),Fq

6 子群，陪集 若H是群G的非空子集，且依G上的运算构成群，则H是G的子群 G有两个平凡子群，自身和单位元构成的群，其他非平凡子群称为真子群
对G的子群H，构建g ·H={g ·h1, g ·h2, …}，称为左陪集，构建 H · g ={h1 ·g, h2 · g, …}，称为右陪集，陪集中最左边的第一个称为陪集首 交换群中左陪集等于右陪集

7 陪集的性质 G关于H的所有陪集构成G的一个划分，即 所有陪集的并就是G 任意两个陪集的任意元素都不同 陪集的大小是H的阶，所有陪集大小相同

8 有限域上的多项式 系数取自Fq上的x的多项式称为有限域上的多项式，全体这类多项式的集合记为GF(q)[x]或Fq[x]
不可约多项式：除了常数和本身，没有其他非零次多项式为因子

9 多项式的概念 次数、根 多项式的欧几里得除法 多项式互素 多项式的最大公因式GCD 多项式的最小公倍式LCM 多项式的同余和剩余类

10 有限域的乘法结构 以素数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

11 有限域的加法结构 满足n个1（乘法单位元）相加为0的最小n称为域的特征，有限域必然有n存在 特征为p的域中，对域中任意元素a必有pa=0
GF(p)中，p为素数时，特征为p 每个域的特征或为素数或为无穷

12 二元域 GF(2)，模2运算 GF(2)加减法一样的结果 GF(2)上有2n个n次多项式，xn的系数为1
GF(2)上任意的m次多项式能整除xn+1，其中n=2m-1 m次不可约多项式若能整除xn+1，且n是满足的最小正整数，n=2m-1，则这个m次不可约多项式成为“本原多项式”

13 GF(2m) 以GF(p)上m次首一不可约多项式为模的多项式剩余类构成pm阶有限域GF(pm)
GF(2)上次数小于等于m-1的多项式有2m个，构成2m阶有限域GF(2m) GF(2)是GF(2m)的基域， GF(2m)是GF(2)的扩域，二者的特征都是2 GF(2m)={0,1,a,a2,a3,…, }

14 共轭根（元）具有相同的最小多项式，也就是说最小多项式包含所有互异的共轭元
GF(2)上的多项式f(X)，若 是GF(2m)的一个元素，且是f(X)的根，则对任意l>0， 是f(X)的根 故有 ，易得 称为x的共轭根，x的所有互异共轭根也是GF(2m)的元素(x是GF(2m)的元素) 共轭根（元）具有相同的最小多项式，也就是说最小多项式包含所有互异的共轭元

15 最小多项式 GF(q)中q-1个非零元素都是xq-1-1=0的根，反之xq-1-1=0的每个根都在GF(q)中，即任意元素的q-1次方都为1
GF(2m)中2m-1个非零元素都是 的根，反之 的每个根都在GF(2m)中，即任意元素的2m-1次方都为1，也就是说GF(2m)中全体元素构成了 的全部根 设 是 的一个根，其也可能是一个次数较低的多项式的根，设其中次数最低的多项式为 ，就是元素 的最小多项式

16 最小多项式 的最小多项式 能整除任何一个GF(2)上的多项式 ，如果 是 的根 最小多项式是不可约的
GF(2m)的所有元素都的最小多项式都能整除 任何一个GF(2)上的多项式 ， GF(2m)的元素 是它的根，若 不可约，则 以本原元为根的最小多项式就是本原多项式

17 例子 本原多项式为1+X+X4 本原元a 三种表示两两之间一一对应，三种形式等价

18 线性空间 基底或基，一组线性无关的向量，其线性组合能表示线性空间V的所有向量
零空间（即：解空间，对偶空间），V1是n维线性空间V的子空间，则与V1中每个向量正交的空间V中的其他向量构成的子空间V2， V1和V2互为零空间 假设有矩阵Amxn 行空间，由矩阵的m行张成的空间，是n维向量空间V的子空间 列空间类似定义

19 矩阵的初等变换 初等变换保持矩阵等价 初等变换后的矩阵具有相同的行空间 交换行（列） 行（列）乘以非零因子
行（列）乘以因子k后加到其他行（列）上 初等变换后的矩阵具有相同的行空间