编码技术 数学基础.

Slides:



Advertisements
Similar presentations
数值分析 第二章 矩阵分析基础 第一节 线性空间 第二节 赋范线性空间 第三节 内积空间 第四节 矩阵代数基础 第五节 矩阵的三角分解 第六节 矩阵的正交分解 第七节 矩阵的奇异值分解.
Advertisements

线 性 空 间 线性空间的定义 线性空间 的子空间 小结. 线性空间是线性代数最基本的概念之一,也是 一个抽象的概念,它是向量空间概念 线性空间是线性代数最基本的概念之一,也是 一个抽象的概念,它是向量空间概念的推广. 线性空间是为了解决实际问题而引入的,它是 某一类事物从量的方面的一个抽象,即把实际问题看作向量空间,进而通过研究向量空间来解决实际问题.
复习: :对任意的x∈A,都有x∈B。 集合A与集合B间的关系 A(B) A B :存在x0∈A,但x0∈B。 A B A B.
向量空间与线性变换 在数学大厦中的重要地位
第6章 向量空间 6.1 向量空间的定义和例子 6.2 子空间 6.3 向量的线性相关 6.4 基和维数 6.5 坐 标
3.4 空间直线的方程.
第二节 线性空间的定义与简单性质 主要内容 引入 定义 线性空间的简单性质.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
一、二阶行列式的引入 用消元法解二元线性方程组. 一、二阶行列式的引入 用消元法解二元线性方程组.
第三章 函数逼近 — 最佳平方逼近.
10.2 立方根.
[S;*]是一个代数系统,*为定义在S上的二元运算,若满足:
近世代数(Abstract Algebra)
第7章 纠错编码代数基础.
§1 线性空间的定义与性质 ★线性空间的定义 ★线性空间的性质 ★线性空间的子空间 线性空间是线性代数的高等部分,是代数学
四种命题 2 垂直.
常用逻辑用语复习课 李娟.
§ 7.1 线性空间的概念 我们考察数域P上全体m×n矩阵的集合Mn,n(P)和数域P上全体n维向量集合(即n维向量空间)Pn, 可以看出,这两个集合中元素的加法与数域P中数与集合元素之间的数量乘 法都有十分相似的运算性质.如果它们抽象出来,就得出一般线性空间的概念.
第四章 多项式环与有限域.
总结 高等代数 多项式 线性代数 矩阵 向量 方程组 计算.
第二章 矩阵(matrix) 第8次课.
第十章 群与环 主要内容 群的定义与性质 子群与群的陪集分解 循环群与置换群 环与域.
有限域.
组合数学 第五章 二项式系数 主要内容: 1. 二项式系数及相关性质 2. 链与反链.
第四章 向量组的线性相关性.
密码学中常用的数学知识 公钥密码体制的基本概念 RSA算法
线性代数 第二章 矩阵 §1 矩阵的定义 定义:m×n个数排成的数表 3) 零矩阵: 4) n阶方阵:An=[aij]n×n
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
定理14.17:F[x]为域F上的多项式环, 商环F[x]/(p(x))是域, 当且仅当p(x)为F[x]上的不可约多项式。
循环群与群同构.
Z3[x]/(x2+1) x2+1在Z3上不可约, Z3[x]/(x2+1)为域 Z3[x]/(x2+1) ={ax+b|a,bZ3}
复习.
第十章 双线性型 Bilinear Form 厦门大学数学科学学院 网址: gdjpkc.xmu.edu.cn
第13讲 环和域, 格与布尔代数 主要内容: 1.环和域的有关内容. 2格与布尔代数的有关内容..
测验: 2.设是群G上的等价关系,并且对于G的任意三个元素a,x,x‘,若axax’则必有x x‘。证明:与G中单位元等价的元素全体构成G的一个子群。 H={x|xG,并且xe} 对任意的xH, xe, xee=xx-1 对任意的x,yH, xe, ye, eye, x-1xyx-1x.
Zp上的n次不可约多项式f(x)的根域是什么? 定理:Zp上的n次不可约多项式f(x)的根域是GF(pn)=Zp()
第16讲 相似矩阵与方阵的对角化 主要内容: 1.相似矩阵 2. 方阵的对角化.
§3 向量组的秩.
§8.3 不变因子 一、行列式因子 二、不变因子.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
第13讲 非齐次线性方程组的结构解, 线性空间与线性变换
1.2 子集、补集、全集习题课.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
例:循环群的每个子群一定是循环群。 证明:设H是循环群G的子群,a是G的生成元。 1.aH
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
2.2矩阵的代数运算.
上杭二中 曾庆华 上杭二中 曾庆华 上杭二中 曾庆华.
第五章 循环码.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
线 性 代 数 厦门大学线性代数教学组 2019年5月12日4时19分 / 45.
A经有限次初等变换化为B,称A与B等价,记作A→B.
《离散结构》 二元运算性质的判断 西安工程大学计算机科学学院 王爱丽.
§2 方阵的特征值与特征向量.
6.2 线性变换的运算 授课题目:6.2 线性变换的运算 授课时数:2学时 教学目标:掌握线性变换的三种运算及
主讲教师 欧阳丹彤 吉林大学计算机科学与技术学院
§4 理想与商环 一、理想 定义14.13:[R;+,*]为环, 若I ,IR,关于+,*运算满足条件:
定理16.8:F()与F()是域F上的两个单代数扩域, 与在F上具有相同的极小多项式p(x)F[x],则:F()≌F()。
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
§5 向量空间.
陪集 例:三次对称群S3={e,1, 2, 3, 4, 5}的所有非平凡子群是:
定理15.8:对f(x)F[x],g(x)F[x], g(x)0,存在唯一的q(x),r(x)F[x], degr(x)
第三节 数量积 向量积 混合积 一、向量的数量积 二、向量的向量积 三、向量的混合积 四、小结 思考题.
编码技术 数学基础.
§4.5 最大公因式的矩阵求法( Ⅱ ).
离散数学─归纳与递归 南京大学计算机科学与技术系
第三章 线性方程组 §4 n维向量及其线性相关性(续7)
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
第七章 线性空间与线性变换 §1 线性空间定义与性质
Cfc Zeilberger 算法 陈焕林 陈永川 付梅 臧经涛 2009年7月29日.
第十章 群与环 主要内容 群的定义与性质 子群.
Presentation transcript:

编码技术 数学基础

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

群 一个系统、一种数学系统、一种代数结构 规定: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群

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

域 非空集合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

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

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

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

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

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

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

二元域 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次不可约多项式成为“本原多项式”

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,…, }

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

最小多项式 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)中全体元素构成了 的全部根 设 是 的一个根,其也可能是一个次数较低的多项式的根,设其中次数最低的多项式为 ,就是元素 的最小多项式

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

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

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

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