《信息论与编码基础》课程教学资源（教案讲义）第七章（7-1）同余性质

定义7一1:如果两个整数a,b被模 m除后有相同的余数r,即: a=gimtr, b=g2m+r 则称a,b对模m同余,记作a=b m0dm。 否则称a,b对模m不同余,记作a主b mOdm。 同余性质: 性质1:两个整数a,b对模m同余的充 要条件是m(ab)。 性质2:(反身性)a≡ a mod m 性质3:(对称性)若a≡ b mod m, 则b≡ a mod n 性质4:(传递性)若a≡ b mod m, 且c≡ b mod m,则a≡ c mod n 例3:m=5 C0={…-15,-10,-5,0,5,10,15,…} C1={…-14,-9,-4,1,6, C2={…-13,-8,-3,2,7,12,17,… C3={…-12,-7,-2,3,8,13,18,…} C4={…-11,-6 4,9,14,19,…}

定义 7－1：如果两个整数 a，b 被模 m 除后有相同的余数 r，即： a=q1m+r，b=q2m+r 则称 a,b 对模 m 同余，记作 a≡b mod m。 否则称 a,b 对模 m 不同余，记作 a≡b mod m。 同余性质： 性质 1：两个整数 a，b 对模 m 同余的充 要条件是 m∣(a-b)。 性质 2：（反身性）a≡a mod m 性质 3：（对称性）若 a≡b mod m， 则 b≡a mod m 性质 4：（传递性）若 a≡b mod m， 且 c≡b mod m，则 a≡c mod m 例 3：m=5 C0={…－15，－10，－5，0，5，10，15，…} C1={…－14，－9，－4，1，6，11，16，…} C2={…－13，－8，－3，2，7，12，17，…} C3={…－12，－7，－2，3，8，13，18，…} C4={…－11，－6，－1，4，9，14，19，…}

定义7—2:设a,b∈Zm={0,1,2, (m-1)},按下式规定a与b的加法称为模 m加法:a⊕b=(a+b)m 按下式规定a与b的乘法称为模m 乘法:a⊙b=(a×b)m 例4:m2 4812=(60)2=0 513=(54)2=0 51G2=(53)2=1 例5:m5 15⊕16=(31)5=1 17c13=(221)。=1 模m运算性质: 设a,b∈Z,m为非0正整数,且 a=r1modm,b≡n2modm,则 a⊕b=(n1n2)modm a⊙b=(n1⊙r2)modm

定义 7－2：设 a，b∈Zm＝｛0，1，2，… (m-1)｝，按下式规定 a 与 b 的加法称为模 m 加法：a⊕b=(a+b)m 按下式规定 a 与 b 的乘法称为模 m 乘法：a⊙b=(a×b)m 例 4：m=2 48⊕12＝(60)2＝0 0⊕0=0 mod 2 51⊕3＝(54)2＝0 1⊕1=0 mod 2 51⊕2＝(53)2＝1 1⊕0=1 mod 2 例 5：m=5 15⊕16=(31)5=1 0⊕1=1 mod 5 17⊙13=(221)5=1 2⊙3=6=1 mod 5 模 m 运算性质： 设 a，b∈Z，m 为非 0 正整数，且 a≡r1 mod m，b≡r2 mod m，则： a⊕b=( r1⊕r2) mod m a⊙b=( r1⊙r2) mod m

模5加法表 0 234 模5乘法表 01234⊙1234 234011234 22340122413 33401 440123443 定义7-3:一个非空集合G,对于所规 定的代数运算(记为*),若满足以下条 件,则称G为一个群( Group) 1、封闭性:对于任意a,b∈G,恒有a*b ∈G 2、结合律成立:对于任意a,b,c∈G 恒有(a*b)*C=a*(b*C); 3、存在一个恒等元e,对于任意a∈G, 满足a*e=a(或e*a=a); 4、对于任意a∈G,都存在逆元al∈G, 满足a*a1=e(或a*a=e)

模 5 加法表 模 5 乘法表 定义 7－3：一个非空集合 G，对于所规 定的代数运算（记为*），若满足以下条 件，则称 G 为一个群（Group）： 1、封闭性：对于任意 a，b∈G，恒有 a*b ∈G； 2、结合律成立：对于任意 a，b，c∈G 恒有(a*b)*c=a*(b*c)； 3、存在一个恒等元 e，对于任意 a∈G， 满足 a*e=a（或 e * a =a）； 4、对于任意 a∈G，都存在逆元 a －1∈G， 满足 a* a －1 =e（或 a －1 * a =e）。 ⊕ 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 ⊙ 1 2 3 4 1 1 2 3 4 2 2 4 1 3 3 3 1 4 2 4 4 3 2 1

“群的练习:(对错判断) 1.(R,+)构成加法Abel群。() 2.(R,×)构成乘法Abel群。( 3.(R*,ⅹ)构成乘法Abel群。() 4.({0,1},⊕)构成加法Abel群。() 5.(Zm,⊕)构成加法Abel群 定义7-4:设R是一个非空集合,R上 存在两种运算“+”与“·,若R满足 下述条件,就成为一个环(Ring)。 1、R对于加法“+”构成一个交换群; 2、R对乘法是封闭的,且适合结合律: 即对于任意a,b,c∈R,恒有 (a·b)·c=a·(b·c); 3、加法、乘法间适合两个分配律:即对 于对于任意a,b,c∈R,恒有 a·(bc)=a·b+a·c和 (b+c)·a=b·a+c·a

“群”的练习：（对错判断） 1．（R，＋）构成加法 Abel 群。 （ ） 2. （R，×）构成乘法 Abel 群。 （ ） 3．（R ＊ ，×）构成乘法 Abel 群。 （ ） 4．（｛0，1｝，⊕）构成加法 Abel 群。（ ） 5．（Zm，⊕）构成加法 Abel 群。 （ ） 定义 7－4：设 R 是一个非空集合，R 上 存在两种运算“＋”与“·”，若 R 满足 下述条件，就成为一个环（Ring）。 1、R 对于加法“＋”构成一个交换群； 2、R 对乘法是封闭的，且适合结合律： 即对于任意 a，b，c∈R，恒有 (a·b) ·c=a·(b·c)； 3、加法、乘法间适合两个分配律：即对 于对于任意 a，b，c∈R，恒有 a·(b+c)= a·b+ a·c 和 (b+c)·a = b·a + c·a

定义7-5:非空元素集合F,若在F中 定义了加和乘两种运算,且满足下述条 件: 1、F对于加法构成阿贝尔群,其加法恒 等元记为0; 2、F中非零元素全体对乘法构成阿贝尔 群,其乘法恒等元(单位元)记为1 3、加法和乘法间分配律成立: a(b+c=abac (b+ca=barca 则称F是一个域( Field) “域”的练习:下列代数系统是否构成域? 1.(Q,十,X);2.(R,十,×) 3.(C,十,×);4.(Z,十,x); 5.(Z5,⊕,⊙);6.(Z6,⊕,⊙); 定理7-1:设p是一个素数,Zp=(0,1, (p-1)},则Z对模p加和模p乘构成一 个p阶有限域。一素域GF(p)

定义 7－5：非空元素集合 F，若在 F 中 定义了加和乘两种运算，且满足下述条 件： 1、F 对于加法构成阿贝尔群，其加法恒 等元记为 0； 2、F 中非零元素全体对乘法构成阿贝尔 群，其乘法恒等元（单位元）记为 1； 3、加法和乘法间分配律成立： a(b+c)=ab+ac (b+c)a=ba+ca 则称 F 是一个域（Field）。 “域”的练习：下列代数系统是否构成域？ 1．（Q，＋，×）； 2．（R，＋，×）； 3．（C，＋，×）； 4．（Z，＋，×）； 5．（Z5，⊕，⊙）； 6．（Z6，⊕，⊙）； 定理 7－1：设 p 是一个素数，Zp =｛0，1，…, （p-1）｝，则 Zp 对模 p 加和模 p 乘构成一 个 p 阶有限域。—素域 GF(p)

定义7-6:对于F域上的一组矢量 152 ,如果存在一组不全为0的标量 q1,a2 ak∈F,使a+a22+…+aF=0, 则称这组矢量线性相关;否则,若只有 当a1,a2,…,ak全为0时等式才成立, 则称其线性无关或线性独立。 定义7—7:如果分量取自域F上的n维矢 量集合V:=(vn2“m),∈F满足以下条 件 、Ⅴ中元素(=0,2,)对于加法构成阿贝 尔加群,其加法规定为: H+吃=("+vnl,vi2+v/12,…vin+vm) 2、v∈v,ve∈F,恒有c·n=(cvn,c"2,cvn)∈V, 称c为纯量(或标量); 3、分配律成立:v,2∈,ve,d∈F,恒有: c1+v2)=cVi+cl (c+d)1=c1+ 4、结合律成立:Wev,ved∈F,恒有: 则称V是F上的一个n维矢量空间(或线 性空间),记为Vn(F)

定义 7－6：对于 F 域上的一组矢量 V V Vk     , , 1 2 ，如果存在一组不全为 0 的标量 a1，a2，…，ak∈F，使 a1V1 + a2V2 + + akVk = 0     ， 则称这组矢量线性相关；否则，若只有 当 a1，a2，…，ak全为 0 时等式才成立， 则称其线性无关或线性独立。 定义 7－7：如果分量取自域 F 上的 n 维矢 量集合 V： { ( ), } Vi = vi1 vi2vin vi F  满足以下条 件： 1、V 中元素 ( 0,1,2, )  Vi i = 对于加法构成阿贝 尔加群，其加法规定为： ( , , ) i j i1 j1 i2 j2 in jn V +V = v + v v + v v + v   ； 2、 Vi V,cF  ，恒有 c Vi = (cvi1 ,cvi2 , cvin )V  ， 称 c 为纯量（或标量）； 3、分配律成立： V1 ,V2 V,c,d  F   ，恒有： 1 1 1 1 2 1 2 ( ) ( ) c d V cV dV c V V cV cV        + = + + = + 4、结合律成立： Vi V,c,d F  ，恒有： ( ) ( ) i dVi cd V c   = 则称 V 是 F 上的一个 n 维矢量空间（或线 性空间），记为 Vn（F）

定义7-8:若线性空间V中的子集T 也满足线性空间的条件,则称V是线性 空间V中的一个子空间 定义7—9:能张成(或生成)整个线性 空间Vn(F)(或子空间)的一组线性无 关的矢量集合称为该线性空间的一个基 底,基底中的矢量数目称为该线性空间 (或子空间)的维数

定义 7－8：若线性空间 V 中的子集 Vs 也满足线性空间的条件，则称 Vs是线性 空间 V 中的一个子空间。 定义 7－9：能张成（或生成）整个线性 空间 Vn（F）（或子空间）的一组线性无 关的矢量集合称为该线性空间的一个基 底，基底中的矢量数目称为该线性空间 （或子空间）的维数

定义7-10:两个矢量(或数组) l1512,…υ n)2=(m2,22n),若其内积: v1·V2=(n21+22+…+v1n"2n)=∑v12;=0 i=1 则称这两个矢量(或数组)互为正交。 定义7-11:如果V1,V2是V中两个子 空间,且V中每个矢量都与V2中每个矢 量正交,则称V和V2互为零空间(解空 间)或两空间正交。V1·V2=0 定理7-3:n维线性空间Vn中两个正交 子空间V,V2,若V是k维子空间,则 2必为(nk)维子空间

定义 7－10 ：两个 矢量（或 数组） ( , , ), ( , , ) 1 11 12 1n 2 21 22 2n V v v v V v v v    = = ，若其内积： ( ) 0 1 1  2 = 1 1 2 1 + 1 2 2 2 + + 1 2 =  1 2 = = n i n n i i V V v v v v  v v v v   则称这两个矢量（或数组）互为正交。 定义 7－11：如果 V1，V2 是 V 中两个子 空间，且 V1 中每个矢量都与 V2 中每个矢 量正交，则称 V1 和 V2 互为零空间（解空 间）或两空间正交。V1• V2＝0 定理 7－3：n 维线性空间 Vn 中两个正交 子空间 V1，V2，若 V1 是 k 维子空间，则 V2 必为（n-k）维子空间