信息论与编码第五讲

《信息论与编码第五讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五讲主要内容1、循环码代数基础2、BCH码3、RS码1.1几个名词元素：近代代数的运算对象。集合：一组元素或若干个元素的全体。代数系统：包含集合和一种或几种代数运算（用符号“*”表示）的系统。一、循环码代数基本知识1.2群群，是包含集合G和一种代数运算‘*’，且满足下列条件的代数系统：（a）运算封闭；（b）有恒等元；（c）有逆元；（d）满足结合律。加法群：满足加法和逆运算的群。乘法群：满足乘法和逆运算的群。交换群：满足交换律的群。子群：一个非空集合SG，S满足群G的全部条件，则S称为子群。加群一定是交换群，

2、加群一定含零元素；乘群不一定是交换群，乘群一定不含零元素。无限群：包含无数个元素的群。有限群：包含有限个元素的群。有限群元素的个数称为该群的阶。循环群：某一元素a（称作生成元a）的一切乘幂a0,a1,a2,…的全体组成一个群，称为循环群，写作G={a0,a1,a2,…},其中a0=e是单位元。若序列a0=e，a1,a2,…中没有两个元素是相等的，称之为无限循环群。若上述序列中有两个相等的元素ai=aj,(ij)，可推出G的元素必以n为周期重复，即an=a0=e,这样的循环群称为有限循环群。循环群也叫幂群，具

3、有以下性质：（a）循环群是交换群；（b）循环群的子群仍是循环群；（c）n阶循环群子群的阶数一定是n的因子。例例1：令R、I、E分别是有理数、整数、偶数集合，则(E,+)是(I,+)的子群，则(I,+)是(R,+)的子群，单位元均是0。奇数集合O在加法运算下构不成群，因不满足封闭性条件。例3集合G={0,1,2…m-1}在模m加（用符号表示）运算下构成一个群（G，）。该加群是m阶有限群，单位元是0。元素0的逆元是0，1的逆元是m-1,2的逆元是m-2,…。例4：集合G={1,2…q-1}在模q乘（q是素数）

4、运算下构成一个乘群（G，）。1.3环环，包含集合R和两种代数运算，且满足下列条件的代数系统：（a）按第一种运算（不妨称为加法）构成交换群；（b）第二种运算（不妨称为乘法）满足以下条件：封闭性；结合律；恒等元；（c）与加法间满足分配律：对于a,b,cR，a(b+c)=ab+ac,(a+b)c=ac+bc。交换环：对于a,bR，ab=ba(交换律)，则称R为交换环。1.4域域，具有交换环的性质，且在乘法运算时具有逆元的代数系统。域具有加和乘两种运算及它们的逆运算。无限域有理数、实数和复数都是无限域。有限域：包含

5、有限个（q）元素的域，或称伽罗华域。q称为域的阶。在信道编码中用到的是有限域，GF(q)。(0,1)二元域GF(2)，或称基本域。由GF(2)GF(2m)，称扩域。可以证明，伽逻华域GF(q)的(q-1)个非零元素在模q乘运算下构成一个循环群（幂群），即所有非零元素可由一个元素（该元素称作生成元或本原元）的各次幂0、1、2、…q-2生成。元素各次幂元素的阶加法逆元乘法逆元012311111141212434333134242241414214表2-1GF(5)各非零元素的幂、阶及逆元1.5

6、既约多项式对于某数域上的多项式PI（x），若除了常数C以及CPI（x）外不能被该数域上的任何其它多项式整除，则称为是该数域上的既约多项式。如：x4+x+11.6本原多项式对于有限域GF(q)上的m次既约多项式P(x)，若能被它整除的最简单多项式(xn-1)的次数nqm–1,则称该多项式为本原多项式。本原多项式一定既约；既约多项式未必本原。如：m本原多项式31+x+x341+x+x451+x2+x561+x+x6比如：在GF(2)域上，x4+x+1(q=2,m=4,2m-1=15)不能被x5+1整除；不能被x

7、6+1整除；……不能被x14+1整除；能被x15+1整除；所以x4+x+1是本原多项式。而x4+x3+x2+x+1能被x5+1整除；能被x15+1整除；所以，x4+x3+x2+x+1是既约的，但不是本原的。本原元对于m次本原多项式p(x)，如果p(a)=0,那么a是GF(2m)的一个本原元。利用本原多项式可求扩域GF(2m)的全部元素为：举例p(x)=x2+x+1，求GF(22)的全部元素及加法乘法表。分析：令p(a)=0，得a2+a+1=0，a2＝a+1。那么全部元素为：幂表示矢量表示多项式表示0a0a1a

8、2=a+10001101101xx+11.6GF(q)的加法和乘法在GF(q)中，对元0,1,2,…,q-1使用modq的计算方法：进行加法和乘法，如果结果在q以上，就用q除，把余数作为结果。如GF(3)的加法和乘法如下表：+012012012120201.012012000012021减法：a-b=a-b+qmodq如:1-2=1-2+3=2mod3除法：b/a=b.a-1modq如：因为2×2=