信息论与编码基础知识 有限域

《信息论与编码基础知识 有限域》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、有限域部分信道编码理论与代数学有着密切的联系。多项式、向量、矩阵运算以及近世代数的有关理论是研究信息编码必不可少的数学工具。鉴于这些数学知识在有关教科书中都有详细论述，这里仅对本书用到的一些主要数学概念简要介绍。1.1整数的可除性我们把1，2，3，…，n，…称为自然数，并用N表示自然数的集合：N={1，2，3，…，n，…}。任意两个自然数的和与积仍是自然数，但两个自然数相减就不一定是自然数，因为减法运算产生了零和负数。通常把正整数、负整数和零的集合称为整数集合，用Z表示，即：Z={…，-n，…，-2，-1，0，1，2，…，n，…}。在整数集合Z中可以做加、减、乘等运算，但除

2、法不总是可以进行的，因为相除后其结果可能不再是整数。定义1.1定义1.1对于整数集合Z中任意两个数a，b，如果存在一个q∈Z，使得b=aq，则称a整除b，记为a∣b；否则称a不能整除b。若a∣b，也称a是b的因数，或b是a的倍数。整除的一些性质：10如果a∣b，则a∣（-b），-a∣b，-a∣（-b）。有了性质10，我们今后只需考虑正整数和零的正因子和正倍数即可。20如果a∣b及a∣c，则a∣mb+nc，m，n∈Z。该性质还可推广到有限个的情况，即如果a∣bi，i=1，2，…，n，则ki∈Z，i=1，2，…，n。30如果a∣b，b∣c，则a∣c。40如果a∣b，且b∣a，则

3、a=b。50如果a∣b，c≠0则ac∣bc。60如果ac∣bc，则a∣b。定理1.1既然除法运算在整数集合中不总是可以进行的，那么用整数集合Z中一个非零整数去除Z中任意个整数，就有除的尽与除不尽两种可能。下面定理给出了用b除Z中任一个数a所得的结果，这就是带余除法定理。定理1.1设a，b是整数集合Z中任意两个数，且a≠0，则一定存在唯一的两个整数q和r，使得：b=aq+r，0≤r<∣a∣。最大公因数和最小公倍数若a∣b则a∣（-b）及-a∣b，因此只讨论正整数和零的正因数和正倍数。定义1.2若d是a的因数，又是b的因数，则d称为a与b的公因数；若m既是a的倍数，又是b的倍数

4、，则m称为a与b的公倍数；一般情况下，a与b的公因数不是唯一的，它有有限多个，当然这些公因数中一定有一个最大的。然而两个数的公倍数有无限多个，但这些公倍数中一定有一个最小的。定义1.3定义1.3设a与b不全为零，如果有一个d，满足:10d∣a，d∣b；20若e是a与b的公因数，则有e∣d。我们就称d是a与b的最大公因数，记为d=（a，b），或者d=GCD（a，b）。最大公因数的一些性质：10d∣a与d∣b同时成立的充分必要条件是d∣（a，b）。20设（a，b）=d，则（ka，kb）=kd；若k∣a，k∣b，则。30（a，b）=d，的充分必要条件是：最大公因数的一些性质：40

5、如果（a，b）=d，则一定存在一对整数u，v，使得ua+vb=d，而且可以进一步要求u，v适合条件，，其中a·b≠0，a≠b，且适合上述条件的u，v是唯一的。定义1.4定义1.4设a，b不全为零，如果a，b的一个公倍数m具有如下性质：a与b的任何一个公倍数都是m的倍数，则m叫做a与b的最小公倍数，记为m=[a，b]或m=LVM（a，b）。定义1.5如果两个数a与b的最大公因数是1，即（a，b）=1，则称a与b是互素的。性质50如果（a，b）=1，则存在一对整数u和v使得ua+vb=1，其中0≤u

6、。60如果a∣b·c，且（a，b）=1，则a∣c。70如果a∣b，b∣c，且（a，b）=1，则a·b∣c。80如果（a，c）=1，（b，c）=1，则（a·b，c）=1。定义1.6定义1.6如果一个大于1的整数a，除了1和它本身以外，没有其它因数，则a称为素数，大于1不是素数的数叫做合数。素数的一些性质：10对于一个素数p和任一个整数a，p∣a或者（p，a）=1，两者必有且仅有其一成立。20如果一个素数p∣a·b，则p∣a或者p∣b。定义1.7定义1.7如果一个素数p∣a，则p叫做a的素因子。根据互素和素数的性质，应用数学归纳法，可以证明整数的基本原理，即因子分解唯一性定理。

7、定理1.2任何一大于1的整数a可以分解成有限个素因子p1，p2，…，pr的乘积a=q1q2…qr，且上述分解是唯一的，这就是说，如果还有一种分解a=q1q2…qs，其中pi和qi都是素数，则r=s且将qi的脚标作适当调换之后可使：q1=p1，q2=p2，…，qr=pr。定理1.3定理1.3设两个整数a与b的最大公因数和最小公倍数分别为（a，b）和[a，b]，则有a·b=（a，b）·[a，b]。欧几里德算法求两个数的最大公因数的常用方法是辗转相除法，即欧几里德（Euclid）算法。欧几里德算法基于以下定理：定理1.4