a-1*a*x1=a-1*b，由此可得e*x1=x1=a-1*b。同理，可证方程y*a=b的解的唯一性 2.9：简述循环群的定义，什么是生成元？
定义：一个集合G，在其上定义了一个二元运算*，若它满足以下条件称为群 满足封闭性，即对G中任意两个元素a,b,有a*b∈G 二元运算*满足结合律
G中存在一个元素e，称为恒元或单位元，使得G中任何元素，有a*e=e*a=a 对于G中任何一个元素a，G中存在另一个元素 ，称作a的逆元，使得
a?a??a??a?e
循环群定义：若存在a∈G是一个集合，使得G中的每个元素都是a的某次幂，即an(n是整数)，则称G是循环群
生成元：该循环群由a生成，a是该群的生成元
2.10：什么是有限域？什么是扩域？什么是域的特征？ 有限域：阶为有限的域，也称为Galois(伽罗华)域
从域的例子2可看出，对任何素数q都存在一个q阶有限域
扩域的定义：对任何正整数m，可以将素域GF(q)扩展为有qm个元素的域，称为GF(q)的扩域，记为GF(qm)。称GF(q)为GF(qm)的基域。此外已经证明，任何有限域的阶都是素数的幂次
有限域的特征：设F是域，0和e是加法和乘法的单位元，若对任意正整数n，都有ne≠0，则称域F的特征是0；若有正整数n，使ne=0，则称使ne=0成立的最小正整数n为域F的特征。域的特征或是0，或是有限的素数。 2.11：证明有限域的性质定理1-3。
定理1：在特征为q的域中，若a是域中的任意元素，则均有qa=0 证明：若a≠0，则qa=a+a+?+a=1·a+1·a+?+1·a=(1+1+?+1)·a =q· 1·a=0·a=0，定理成立；若a=0，定理显然成立。证毕 定理1：有限域的特征q是素数 证明：设q≠0，假设q不是素数，即q=q1q2,1 证明：令b1,b2,?,bq-1为GF(q)的q-1个非零元素，显然q-1个非零元素ab1,ab2,?,abq-1非零且互不相同，因此 (ab1)·(ab2) ·?·(abq-1)=b1·b2·?·bq-1 所以aq-1(b1·b2·?·bq-1)= b1·b2·?·bq-1 即有aq-1=1。 定理3：设a是有限域GF(q)的非零元素，令n是a的阶，则q-1能被n整除，即n|(q-1) 证明：假设q-1不能被n整除，则q-1=kn+r,其中0 2.12：证明有限域的特征定理1-3。 2.13：简述本原元的定义，并且会用该定义判断当给定q时有限域GF(q)上的本原元。 本原元：在有限域GF(q)中，若非零元素a的阶为q-1，则称之为本原元。 2.14：什么是多项式？什么是首一多项式？ 多项式定义：二元域GF(2)中表达式f(x)=f0+f1x+?+fnxn，其中fi=0或1。若fn≠0，则称f(x)是n次多项式，记为deg(f(x))=n， fn称为多项式的首项系数。GF(2)中共有2n个多项式 首一多项式：首项系数为1的多项式 2.15：掌握根据本原多项式和本原元生成GF(2)的扩域GF(2m)的方法。 p(x)=1+x+x4是GF(2)上的本原多项式，假设a是本原元，则a4=a+1,由此可以构造GF(24) 2.16：什么是最高公因式？什么是公倍式？什么是最低公倍式？ 最高公因式：若f(x)为a(x)与b(x)的所有公因式中次数最高的，并且首项系数为1，记为gcd(a(x), b(x)) f(x)为a(x)与b(x)的公倍式：当a(x)≠0, b(x)≠0，并且a(x)| f(x)，b(x)|f(x) 最低公倍式：若f(x)为a(x)与b(x)的所有公倍式中次数最低的，并且首项系数为1，记为LCM(a(x), b(x)) 2.17：什么是本原多项式？ 本原多项式的定义：若m次既约多项式p(x)可以除尽xn+1的最小整数n满足n=2m-1，则称p(x)是本原多项式 2.18： 证明GF(2)上的多项式f(x)满足[f(x)]2= f(x2) 。 2.19： GF(2)上的多项式的根的特点是什么。 定理：若f(x)为GF(2)上的一个m次既约多项式，则其扩域GF(2m)含有f(x)的m个根；进一步的，若m|d，则任何GF(2d)含有f(x)的根 定理：若f(x)是系数取自GF(2)的多项式，令b是GF(2)扩域中的元素，若b是f(x)的根，则对任意的l≥0，b2l也是f(x)的根 2.20：什么是域元素的共轭元。 注：元素b2l称为b的共轭元，以上定理说明若是b是多项式f(x)的根，则b的所有共轭元b2l也是f(x)的根 2.21：什么是最小多项式？ 定义：令m(x)是使得m(b)=0成立的次数最低的多项式，则称m(x)是b的最小多项式 2.22：什么是矢量空间？ 定义：令V是元素的集合，在其上定义了一个称作是加法(+)的二元运算。令F是域。在域F中的元素和V中的元素之间还定义了一个数乘运算(·)。若集合V满足下述条件，就称它为域F上的矢量空间或线性空间： 条件1：V是加法下的可交换群 条件2：对F中的任意元素a和V中的任意元素v，a·v是V中的元素 条件3：分配率。对任意u,v∈V和a,b∈F，有a·(u+v)=a·u+a·v, (a+b)·v=a·v+b·v 条件4：结合率。对任意v∈V和a,b∈F，有(a·b)·v=a·(b·v) 条件5：令1是F的单位元，则对任意v∈V ，有1· v= v 2.23：矢量空间有哪些性质？ 性质1：令0是域F中的零元，对任意的v∈V，有0·v=0 性质2：对任意c∈F，有c·0=0 性质3：对任意c∈F和v∈V ，有 (-c)·v=c·(-v)=-(c·v) 性质4：如果c·v=0,则c=0或者v=0 2.24：简述n重的定义。 n重：GF(2)上的n个分量的有序序列(a1,a2,?,an)称作n重,共有2n个不同的n重，令Vn表示所有n重的集合 2.25： 什么是线性组合？什么是线性相关？ 令v1,v2,?,vk∈V是k个矢量，a1,a2,?,ak∈F是k个标量，称∑ai vi为线性组合 定义：域F上矢量空间V的一组矢量v1,v2,?,vk称作是线性相关的，当且仅当存在不全为0 的标量a1,a2,?,ak，使得 ?avi?1kii?0 。否则称v1,v2,?,vk是线性独立的 第三章 3.1：简述线性(n,k)分组码的定义。 定义：长为n，有2k个码字的分组码，当且仅当其2k个码字构成GF(2)上所有n重矢量空间的一个k维子空间时，称作线性(n,k)分组码 3.2：什么是生成矩阵？请具体构造几个线性(n,k)分组码的生成矩阵。 因为线性(n,k)分组码C是一个k维子空间，所以在码C中能找到k个线性独立的码字g0, g1,?, gk-1,使得C中的每个码字v都是这k个码字的一种线性组合，即v=u0g0+u1g1+?+uk-1gk-1 将这k个线性独立的码字作为行，得到k×n阶矩阵 ?g0??g00????g1??g10G???????????g?g?k?1??k?10g01g11gk?11g0n?1??g1n?1?????gk?1n?1? ?此矩阵称为码C的生成矩阵。线性(n,k)分组码任何k个线性独立的码字都可以用来构成码C的生成矩阵 举例: (7,4)线性分组码 如果表格所表示的线性分组码，有如下的生成矩阵 ??g0???1101000?G??g110100????1?0??g110010??2???1?g?3?????1010001??? 若u=(1101)，则 v?1?g0?1?g1?0?g2?1?g3?(0001101) 3.3：什么是线性系统(n,k)分组码？ 线性系统分组码：若(n,k)线性分组码C的生成矩阵形如G=[P Ik](或G=[Ik P])，此时称C为线性系统分组码。此时，每个码字都可以被分成两个部分，即消息部分和冗余部分 ???g0??p00p01?p0,n?k?1?100??p10p11?p1,n?k?1?010?G??g??1??Ik???p21?p2,n?k?1?001?????P?p12???????g??k?1?????pk?1,0pk?1,1?pk?1,n?k?1?000?3.4：什么是一致校验方程？什么是一致校验矩阵？什么是对偶码？ 关于线性系统分组码，对应于消息u=(u0, u1,?, uk-1)的码字是v=(v0, v1,?, vn-1)=u·G=u·[P Ik]，即 vn-k+i=ui , 0≤i≤k-1, vj=u0P0j+u1P1j+?+uk-1Pk-1j, 0≤j≤n-k-1 上面两个式子正好反映系统的组成特性，最后这n-k个方程称为码C的一致校验方程 定义：与(n,k)线性分组码C的生成矩阵G相对应有一个(n-k)×n阶矩阵H，它的n-k个行是码C的对偶空间的一组基底，该矩阵H称为码C的一致校验矩阵 对偶码：以H为生成矩阵得到的(n,n-k)码称为码C的对偶码，记为Cd 3.5：什么是伴随式？伴随式纠错的原理是什么？ 伴随式：当接收到r后，译码器计算下述n-k重S=r·HT =(s0, s1,?, sn-k-1)，称S为r的伴随式 根据伴随式定义， S=r·HT =(v+e)·HT=v·HT+e·HT =e·HT，展开后，有 s0?e0?en?kp00?en?k?1p10???en?1pk?1,0s1?e1?en?kp01?en?k?1p11???en?1pk?1,1?sn?k?1?en?k?1?en?kp0,n?k?1?en?k?1p1,n?k?1???en?1pk?1,n?k?1从上式容易看出，伴随式是错误图样的组合，即伴随式包含了一定程度的错误图样信息，因而可以用来纠错——伴随式纠错 3.6：什么是汉明重量？什么是汉明距离？汉明距离的性质是什么？ 汉明重量：令v=(v0, v1,?, vn-1)是二元n重，v的汉明重量w(v)定义为v中非零分量的个数 0?0??0????1??汉明距离：令u=(u0, u1,?, un-1)和v=(v0, v1,?, vn-1)是两个二元n重，u和v之间的汉明距离d(u, v)定义为u+v的汉明重量。 汉明距离的性质：1)非负性，d(u, v)≥0；2) d(u, v)=0，当且仅当u=v的时候；3)对称性： d(u, v) =d(v, u) ；4)三角不等式： d(u, v)+d(v, w)≥d(u, w) 3.7：简述线性(n,k)分组码的定义。 3.8：什么是生成矩阵？请具体构造几个线性(n,k)分组码的生成矩阵。 3.9：什么是线性系统(n,k)分组码？ 3.10：什么是一致校验方程？什么是一致校验矩阵？什么是对偶码？ 3.11：什么是伴随式？伴随式纠错的原理是什么？ 3.12：什么是汉明重量？什么是汉明距离？汉明距离的性质是什么？ 3.13：重量分布和距离分布的定义是什么？简述二者之间的联系。 重量分布：对于一个分组码而言，每个码字都有一个汉明重量，不同的码字可能具有相同的汉明重量，若记Ai为码中汉明重量为i的码字个数，则称{A0, A1,?, An}是该码的重量分布，其中n是码长 定义：在(n,k)码中，任意两个码字之间都有一个汉明距离，两组不同码字之间可能有相同的汉明距离。若记Di(0≤i≤n)为距离为i的码字组数，那么称{D0, D1,?, Dn}为此分组码的距离分布，并且称能够使Di≠0的那个最小整数i为该码的最小码间距离。 对线性分组码而言，重量分布与距离分布是一回事。特别的，有如下定理 定理：(n,k)线性码的最小码间距离等于非零码字的最小汉明重量 3.14：如何计算线性分组码的检错纠错能力？ 定理：设(n,k)线性码C的最小码间距离为d，则1)若d≥t+1，则码C能检测t个随机错误；2)若d≥2t+1，则码C能纠正t个随机错误；3)若d≥t+e+1，则码C能纠正t(t≤e)个随机错误，同时还能检测e个随机错误。 因此，若码C的最小汉明距离d越大，则该码的纠错和检错能力就越强 3.15：什么是最大距离可分码？ 定理： (n,k)线性码C的最小码间距离d满足d≤n-k+1。该定理给出了d的上界。 最大距离可分码：若(n,k)线性码的最小码间距离d满足d=n-k+1 ，那么称此种码为最大距离可分码，简称MDS码。 3.16：简述标准阵的构造步骤？ 步骤1：在第一行写下所有合法的2k个码字v={v1,?, v2^k}，第一个码字为全零码字； 步骤2：选择一个第一行没有出现的矢量作为e2，标准阵第2行写e2+v； 步骤3：继续选择一个第一行和第二行都没有出现的矢量e3 ，标准阵第3行写e3+v； 步骤4：依次类推，直到GF(2n)中所有的矢量都被列出来一次。 3.17：标准阵的性质是什么？证明标准阵的性质2。 性质1：同一行中任意两个n重之和为一个码字 性质2：在标准阵中，同一行没有两个n重是相同的，每个n重在且仅在一行中出现 性质2的证明：1)假设第l行有2个n重是相同的，如对i≠j有el+vi=el+vj，即vi=vj，这与标准阵的构造相矛盾，故性质2的第一行得证。2)首先由定义知每个n重至少出现一次，假设一个n重在第l行和第m行(l 3.18：什么是陪集和陪集首？ 陪集：标准阵中共有2n-k行，它们称为码C的陪集 陪集首：每个陪集中的第一个n重ei称为陪集首。陪集中的任何一个元素都可以作为陪集