编码理论习题.doc

第1章 概述1.1：通信的主要目的是什么？通信: 采用某种方法，借助某种媒介将信息从甲地传送到乙地的过程通信的目的：要把对方不知道的消息及时可靠地(有时秘密的)传送给对方1.2：信道编码的主要目的是什么？信源编码的主要作用是：在保证通信质量的前提下，尽可能的通过对信源的压缩，提高通信时的有效性。就是让通信变得更加的有效率。以更少的符号来表示原始信息，所以减少了信源的剩余度。信道编码的主要作用是：通过对做完信源编码后的信息加入冗余信息，使得接收方在收到信号后，可通过信道编码中的冗余信息，做前向纠错。保证通信的可靠性。1.3：仙农编码定理的主要内容是什么？仙农编码定理：如果系统的传输率小于信道容量，那么适当选择编码技术就能实现可靠通信，即可以将差错率减小到任意小的程度。更确切地，每个信道都具有固定的信道容量C，对任何小于C的信息传输率R，存在一个码长为n码率为R的分组码，若用最大似然译码，则其译码错误概率为 。对于码率为R约束长度为ne的卷积码，其译码错误概率也有类似的关系，即 其中A和B都为大于0的数，Eb(R)和Ee(R)为正实函数，叫做误差指数。1.4：请画出数字通信系统模型的通用框图。1.5：信源编码扩张了数据么，为什么？信源编码没有扩张数据。信源编码减少了数据的冗余。信源编码器：将信源输出变成二元数字(bit)序列，称为信息序列，在信源连续的情况下，还需要进行模/数(A/D)转换。理想信源编码器模型要满足(1)为表示信源输出所要求的单位时间的比特数要尽量小；(2)信源的输出S可从信息序列U中确切的重新构造1.6：信道编码扩张了数据么，为什么？信道编码扩张了数据。信道编码器：将信息序列U变换成离散的有结构的编码序列X，这称为码字。即为了使传输有效，人为的增加一些冗余度，使其具有自动检错和纠错的能力。码字的结构主要用以对付传输或存储码字的有扰信道，码字的设计和实现是本课程的主题。1.7：为什么要用信源编码器？理想的信源编码器应该满足什么要求？为了减少数据的冗余。信源编码器：将信源输出变成二元数字(bit)序列，称为信息序列，在信源连续的情况下，还需要进行模/数(A/D)转换。理想信源编码器模型要满足(1)为表示信源输出所要求的单位时间的比特数要尽量小；(2)信源的输出S可从信息序列U中确切的重新构造1.8：为什么要用信道编码器？为了使传输有效信道编码器：将信息序列U变换成离散的有结构的编码序列X，这称为码字。即为了使传输有效，人为的增加一些冗余度，使其具有自动检错和纠错的能力。码字的结构主要用以对付传输或存储码字的有扰信道，码字的设计和实现是本课程的主题。1.9：为什么要用调制器？离散符号不适合于在实际信道上传输或记录在数字存储媒质上。调制器将信道编码器的每个输出的离散符号，通过调制变成适合传输(或存储)的持续时间为T的波形，此波型进入信道(或存储媒质)，并受噪声干扰1.10：有哪些典型的传输信道、存储媒质和信道干扰？典型的传输信道：有线信道、无线信道、电话线路、高频无线线路、遥测线路、微波线路、卫星线路、光纤信道、磁记录信道、大气光信道、水声信道等典型的存储煤质：磁芯和半导体存储器、磁带、磁鼓、磁盘、光存储器、光盘等典型的干扰：开关脉冲噪声、热噪声、串音、闪电、磁涂层缺损、光盘划痕等1.11：为什么要用解调器？解调器(或读出单元) ：处理接收到的每个持续时间为T的波形，并产生一个可能是离散的（量化的）或连续的（未量化的）输出。对应于编码序列X的解调器的输出序列Y称为接收序列1.12：信道译码器的功能是什么？信道译码器：将接收序列Y变换成二元序列V，称为估值序列。在理想的情况下，V与信息序列U完全一致，但是噪声会造成译码错误。译码方法根据信道编码规则和信道（或存储煤质）的噪声特性而定。但设计和实现译码错误概率最小的信道译码器也是本课程的主要论题之一1.13：为什么要用信源译码器？信源译码器：把估值序列V变成信源输出的估值(原来消息的估值)，并将此估值传送给用户。如果信源是连续的，需要进行数/模转换。在一个精心设计的系统中，除非信道(或存储煤质)的干扰太强，否则这个估值将是信源输出的准确重现1.14：请画出数字通信系统模型的简化框图。1.15：简述信道编码的主要应用领域。？通信系统：如卫星、有线和无线的电话通信、军事通信等，利用纠错码来实现可靠通信和敌人的恶意干扰计算机系统：如计算机存储器、数字磁带、磁盘、光盘、数字逻辑电路中商业领域：如条形码，由黑白相间的不同宽度的条纹来代表不同的信息，包含了一定的纠错信息，可以纠正由于条码的模糊不清等原因造成的读写错误，因此条形码在运输、仓储、超级市场管理等物流行业获得了广泛的应用1.16：简述分组码和卷积码的相同点和不同点。分组码编码器：将信息序列分为长度为K比特的消息段U=u1,u2, ,uK,称为消息,分组进行编码,总共有2K个消息,将每个消息U独立的变换成长度为N比特的码字的序列V=v1,v2, ,vN(N, K)分组码：所有个2K码字的集合码速率：比值R=K/N，可以理解为码字含有信息比特数量，为使编码不冲突，R1纠错机理：当R1时,码字比消息多了n-k个比特, 称为校验位,可以抗干扰无记忆：每个N长的码字V由相应的K长消息U唯一确定分组码可用组合逻辑电路来实现卷积码编码器：也是接收长度K比特的信息序列U=u1,u2, ,uK,并产生一个长度为N比特的码字的序列V=v1,v2, ,vN有记忆：每一编码组不仅与同一时间单元上K比特消息有关，还与前m个输入有关。因而编码器的存储器为m级(N, K, m)卷积码：有K个输入，N个输出，存储级为m的编码器产生的序列集码速率：比值R=K/N在KH(X)，对于信源X，两个输出消息不是等概率的，事先大致可以猜测消息x1会出现，故信源X的不确定性要小H(X)表示变量X的随机性当信源符号是等概率出现的时候，信息熵可以达到最大值1.26：简述等长信源编码定理的主要内容。定理: 一个熵为H(X)的离散无记忆信源，若对信源长为N的符号序列进行等长编码，设码字是从r个字母的码符号集合中，选取l个码元组成。对于任意的0，只要满足则当N足够大时，可实现几乎无失真编码，即译码错误概率可为任意小。1.27：简述前缀码和惟一可译码之间的关系。前缀码/前缀条件码定义: 若码C中，没有任何完整的码字是其他码字的前缀，称此码为前缀码，也称即时码或非延长码前缀码和即时码的定义是一致的：如果没有一个码字是其他码字的前缀，则在译码过程中，当收到一个完整码字的码符号序列时，就能直接把它译成对应的信源符号，无需等待下一个信号到达后才作判断，这就是即时码关系：前缀码是惟一可译码的一类子码：即前缀码一定是惟一可译码，但是惟一可译码不一定是前缀码1.28：霍夫曼编码唯一么？简述霍夫曼编码的主要步骤。不唯一霍夫曼编码的步骤：将信源符号按照概率递减的顺序进行排序将0和1符号分别分配给概率最小的两个信源符号，并将这两个概率最小的符号合并成一个新符号，用这两个信源符号的概率之和作为这个新符号的概率以此类推继续这个过程，直到只剩下2个符号为止，从而完成霍夫曼树的构造从树的最后一个节点，依编码路径从后往前返回，读出每个分支上对应的符号标示，即可得到对应的码字1.29：考虑比特流111111111111111000000000000000000111111，如果对之用游程编码方案进行压缩编码，那么压缩率为多少？游程编码定义：游程指的是信源输出的字符序列中，各种字符连续的重复出现的字符串的个数游程编码：就是将这种字符序列映射成字符串的长度和字符串的位置的标志序列考虑比特序列111111111111111000000000000000000111111，可以被表示成(15,1),(18,0),(6,1)，字符最长的重复的数目为18，因此把该比特序列编码为(01111,1), (10010,0), (00110,1)，此时压缩率为15:39=1:1.30：简述LZ编码的分段方法和编码方法。LZ编码分段的方法为：(1)游程先取第一个符号作为第一段，然后再继续分段(2)若有出现与前面符号一样时，就再添加紧跟后面的一个符号一起组成一段(3)尽可能取最少个连着的符号并保证各段都不相同(4)以此类推，直至信源符号序列结束编码方法为：首先去掉最后一个符号，然后看剩下的字符串在字典中的排序，这个排序值转换成二进制数作为指针K的值，最后一个信源符号作为码字第2项d的值，即得到码字(X, d)1.31：考虑比特序列01010110011010101011，如果用LZ编码，那么其分段是什么，编码后的码字又是什么？0,1,01,011,00,11,010,10,101,1(000,0),( 000,1), (001,1), (011,1), (001,0), (010,1), (011,0), (010,0),( 1000,1),( 000,1)1.32：考虑一个如图1.2所示的BSC信道，其信道转移概率为P(0|1)=P(1|0)=p，求该信道的容量。如果=0.5，用信道容量的公式，可以获得BSC的信道容量为C=1+plog2p+(1-p)log2(1-p)，熵函数为H(p)=-plog2p-(1-p)log2(1-p)，因此得到C=1-H(p)1.33：求具有如下信道传递矩阵的信道的容量。1.34：简述信道编码定理的内容。定理：假设DMS有信源字符集X，熵为每信源符号H(X)比特，而且信源每Ts秒产生一个符号，那么信源的平均信息率为每秒H(X)/ Ts比特，假设信道可以每Tc秒使用一次，而信道容量为每次信道使用C比特，那么每单位时间的信道容量为每秒钟C/Tc比特。如果H(X)/ Ts C/Tc ，那么就存在编码方案使得在有噪声的信道上传输的信源消息，能够以任意小的错误概率进行恢复。1.35：什么是无记忆信道和二元对称信道？无记忆信道：如果在给定时间间隔上，检测器的输出只与在该时间间隔上传送的信号有关，而与任何前面时间的传送的信号无关，称此信道为无记忆信道离散无记忆信道：是一种M元输入、Q元输出的信道模型二元对称信道: M=2,Q=2二元对称信道: 是一种2元输入、2元输出的信道模型1.36：仙农的信息定义是什么？信息量的多少跟事件发生的不确定性之间有什么关系？仙农对于信息的定义：信息是事物运动状态或存在方式不确定性的描述一个句子中所含信息的多少，同句子中所表达的事件出现的概率有关：呈现相反的关系信息量的多少，同事件发生的不确定性有关：呈现相反的关系第二章2.1：某些域中元素有大小之分，另一些域中的元素无大小之分，各举一个例子。2.2：交换律、分配律、结合律在群上成立么？在环上成立么？在域上成立么？结合律在群上成立，交换律在交换群上成立，分配律群上不成立结合律在环上成立，交换律（乘法）在交换环上成立，加法和乘法在环上满足分配律结合律、交换律、分配律在域上成立2.3：简述群、环、域三者之间的关系？定义：一个集合G，在其上定义了一个二元运算*，若它满足以下条件称为群满足封闭性，即对G中任意两个元素a,b,有a*bG二元运算*满足结合律G中存在一个元素e，称为恒元或单位元，使得G中任何元素，有a*e=e*a=a对于G中任何一个元素a，G中存在另一个元素 ，称作a的逆元，使得定义：非空元素集合R中，定义了两种二元运算，称作加法和乘法，这样的代数系统(R,+,)称为一个环，若它满足以下条件R中全体元素在加法下构成交换群，单位元为0，逆元记为-a乘法运算满足封闭性满足乘法结合率，即 (ab)c=a(bc) ，加法和乘法之间满足分配律 a(b+c)=ab+ac, (b+c)a=ba+ca, 定义：非空元素集合F中，定义了两种二元运算，称作加法和乘法，这样的代数系统(F,+,)称为一个域，若它满足以下条件F中全体元素在加法下构成交换群，恒元为0F中非零元素在乘法下为交换群，恒元为1加法和乘法之间满足分配律 (a+b)c=ac+bc环中全体元素在加法下构成交换群，单位元为0，逆元记为-a域中全体元素在加法下构成交换群，恒元为0域中非零元素在乘法下为交换群，恒元为12.4：存在含有256个元素的有限域么？为什么？不是由有限域的性质可知：定理1：有限域的特征q是素数256不是素数2.5：构造一个含13个元素的有限域。在该域中，3的逆元和负元是什么？1/3 -32.6：全体整数的集合对普通减法是否构成一个群？为什么？不不满足结合律 3-(2-1)与(3-2)-1不等2.7：全体非负整数的集合在加法和乘法下是否构成群？为什么？全体非负整数集合在实数加法运算下构成可交换群，整数0为恒元，整数-a是整数a的逆元。全体非负整数集合对乘法不构成群，因为不存在乘法逆元2.8：证明群的性质定理1-4。定理1：群G的恒元是唯一的 证明：假定G中有两个恒元e和，则有 证毕定理2：任何一个群元素的逆元是唯一的 证明：假定元素a有两个逆元 ，则 证毕定理3：若a,bG，则 证明： 所以a*b和 互为逆元定理4：给定G中任意两个元素a和b，则方程a*x=b和y*a=b在G中有唯一解 证明：方程a*x=b的解是x=a-1*b，这是因为 a*a-1*b=e*b=b，同理，y*a=b的解是y=b*a-1。 下面证明解的唯一性。如果在方程a*x=b中， 除了x=a-1*b，还有另外一个解x1，使a*x1=b,则把该式两边左乘以a的逆元a-1，则有a-1*a*x1=a-1*b，由此可得e*x1=x1=a-1*b。同理，可证方程y*a=b的解的唯一性2.9：简述循环群的定义，什么是生成元？定义：一个集合G，在其上定义了一个二元运算*，若它满足以下条件称为群满足封闭性，即对G中任意两个元素a,b,有a*bG二元运算*满足结合律G中存在一个元素e，称为恒元或单位元，使得G中任何元素，有a*e=e*a=a对于G中任何一个元素a，G中存在另一个元素 ，称作a的逆元，使得循环群定义：若存在aG是一个集合，使得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，都有ne0，则称域F的特征是0；若有正整数n，使ne=0，则称使ne=0成立的最小正整数n为域F的特征。域的特征或是0，或是有限的素数。2.11：证明有限域的性质定理1-3。定理1：在特征为q的域中，若a是域中的任意元素，则均有qa=0证明：若a0，则qa=a+a+a=1a+1a+1a=(1+1+1)a =q 1a=0a=0，定理成立；若a=0，定理显然成立。证毕定理1：有限域的特征q是素数证明：设q0，假设q不是素数，即q=q1q2,1q1q,1q2q,于是0=qe=(q1q2)e=(q1e)(q2e), 因此q1e=0或者q2e=0，但这与q的最小性相矛盾，所以q只能是素数。对于任意有限域，由于其只有有限个元素，所以其特征不可能为0，从而其特征一定为素数。定理2：设a是有限域GF(q)的非零元素，则aq-1=1。证明：令b1,b2,bq-1为GF(q)的q-1个非零元素，显然q-1个非零元素ab1,ab2,abq-1非零且互不相同，因此 (ab1)(ab2) (abq-1)=b1b2bq-1 所以aq-1(b1b2bq-1)= b1b2bq-1 即有aq-1=1。定理3：设a是有限域GF(q)的非零元素，令n是a的阶，则q-1能被n整除，即n|(q-1) 证明：假设q-1不能被n整除，则q-1=kn+r,其中0rn，于是aq-1=akn+r=aknar=(an)kar=ar, 根据aq-1=1，an=1，推出ar=1，这与n的定义里的最小性矛盾，所以q-1必能被n整除。证毕。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。若fn0，则称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)的根，则对任意的l0，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，av是V中的元素条件3：分配率。对任意u,vV和a,bF，有a(u+v)=au+av, (a+b)v=av+bv条件4：结合率。对任意vV和a,bF，有(ab)v=a(bv)条件5：令1是F的单位元，则对任意vV ，有1 v= v2.23：矢量空间有哪些性质？性质1：令0是域F中的零元，对任意的vV，有0v=0性质2：对任意cF，有c0=0性质3：对任意cF和vV ，有 (-c)v=c(-v)=-(cv)性质4：如果cv=0,则c=0或者v=0 2.24：简述n重的定义。n重：GF(2)上的n个分量的有序序列(a1,a2,an)称作n重,共有2n个不同的n重，令Vn表示所有n重的集合2.25： 什么是线性组合？什么是线性相关？令v1,v2,vkV是k个矢量，a1,a2,akF是k个标量，称ai vi为线性组合定义：域F上矢量空间V的一组矢量v1,v2,vk称作是线性相关的，当且仅当存在不全为0的标量a1,a2,ak，使得 。否则称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个线性独立的码字作为行，得到kn阶矩阵此矩阵称为码C的生成矩阵。线性(n,k)分组码任何k个线性独立的码字都可以用来构成码C的生成矩阵举例: (7,4)线性分组码如果表格所表示的线性分组码，有如下的生成矩阵若u=(1101)，则3.3：什么是线性系统(n,k)分组码？线性系统分组码：若(n,k)线性分组码C的生成矩阵形如G=P Ik(或G=Ik P)，此时称C为线性系统分组码。此时，每个码字都可以被分成两个部分，即消息部分和冗余部分3.4：什么是一致校验方程？什么是一致校验矩阵？什么是对偶码？关于线性系统分组码，对应于消息u=(u0, u1, uk-1)的码字是v=(v0, v1, vn-1)=uG=uP Ik，即 vn-k+i=ui , 0ik-1, vj=u0P0j+u1P1j+uk-1Pk-1j, 0jn-k-1 上面两个式子正好反映系统的组成特性，最后这n-k个方程称为码C的一致校验方程定义：与(n,k)线性分组码C的生成矩阵G相对应有一个(n-k)n阶矩阵H，它的n-k个行是码C的对偶空间的一组基底，该矩阵H称为码C的一致校验矩阵对偶码：以H为生成矩阵得到的(n,n-k)码称为码C的对偶码，记为Cd3.5：什么是伴随式？伴随式纠错的原理是什么？伴随式：当接收到r后，译码器计算下述n-k重S=rHT =(s0, s1, sn-k-1)，称S为r的伴随式根据伴随式定义， S=rHT =(v+e)HT=vHT+eHT=eHT，展开后，有从上式容易看出，伴随式是错误图样的组合，即伴随式包含了一定程度的错误图样信息，因而可以用来纠错伴随式纠错3.6：什么是汉明重量？什么是汉明距离？汉明距离的性质是什么？汉明重量：令v=(v0, v1, vn-1)是二元n重，v的汉明重量w(v)定义为v中非零分量的个数汉明距离：令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(0in)为距离为i的码字组数，那么称D0, D1, Dn为此分组码的距离分布，并且称能够使Di0的那个最小整数i为该码的最小码间距离。对线性分组码而言，重量分布与距离分布是一回事。特别的，有如下定理定理：(n,k)线性码的最小码间距离等于非零码字的最小汉明重量3.14：如何计算线性分组码的检错纠错能力？定理：设(n,k)线性码C的最小码间距离为d，则1)若dt+1，则码C能检测t个随机错误；2)若d2t+1，则码C能纠正t个随机错误；3)若dt+e+1，则码C能纠正t(te)个随机错误，同时还能检测e个随机错误。因此，若码C的最小汉明距离d越大，则该码的纠错和检错能力就越强3.15：什么是最大距离可分码？定理： (n,k)线性码C的最小码间距离d满足dn-k+1。该定理给出了d的上界。最大距离可分码：若(n,k)线性码的最小码间距离d满足d=n-k+1 ，那么称此种码为最大距离可分码，简称MDS码。3.16：简述标准阵的构造步骤？步骤1：在第一行写下所有合法的2k个码字v=v1, v2k，第一个码字为全零码字；步骤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重是相同的，如对ij有el+vi=el+vj，即vi=vj，这与标准阵的构造相矛盾，故性质2的第一行得证。2)首先由定义知每个n重至少出现一次，假设一个n重在第l行和第m行(lm)都出现，则必存在i，使得该n重等于el+vi，且存在j，使得该n重等于em+vj，即有em=el+(vi+vj)=el+vs，这意味着em在第l行，这与标准阵的构造定义相矛盾。3.18：什么是陪集和陪集首？陪集：标准阵中共有2n-k行，它们称为码C的陪集陪集首：每个陪集中的第一个n重ei称为陪集首。陪集中的任何一个元素都可以作为陪集首，需要做置换操作3.19：简述基于标准阵的译码策略和最小距离译码策略的内容。基于标准阵的译码策略：如果接收矢量r落在标准阵中的第i行第j列，那么就将r译码为vj，同时错误图样为ei，即r=ei+vj最小距离译码策略：如果出现了不可纠正错误图样，就出现了译码错误。对BSC信道，为了使译码错误概率最小，可以选择汉明重量最小的n重做为陪集首，由此导出了最小距离译码策略，即将接收矢量r译码为与r的汉明距离最小的那个码字3.20：证明陪集的性质定理1-4。定理：若C是GF(q)上的一个(n,k)线性码，则1)长度为n的矢量b一定在码C的某个陪集中；2)每个陪集都包含qk个矢量；3)两个陪集要么是不相交的要么就是重合的(即相互部分重叠是不可能的)；4)如果a+C是码C的一个陪集，且有ba+C，那么一定有b+C=a+C证明：1) b=b+0b+C；2) 对于所有的xC,由xa+x定义的映射Ca+C是个一一映射，所以陪集a+C中矢量的个数和码集中码矢的个数相等，即qk3.21：简述伴随式译码方法的步骤。步骤1：计算接收矢量r的伴随式rHT步骤2：确定伴随式等于rHT对应的陪集首ei，然后假定ei是信道引起的错误图样步骤3：将接收矢量r译码为码字v=r+ei3.22：请构造一种线性分组码，给出具体的生成矩阵，一致校验矩阵，以及译码方法等。(7,4)线性分组码如果表格所表示的线性分组码，有如下的生成矩阵，一致校验矩阵第四章4.1：什么是循环右移？什么是循环码？循环移位: 将n重v=(v0,v1,vn-1)的分量循环右移一位，得到另一个n重v(1)=(vn-1,v0,v1,vn-2)，称为v的循环移位。若v的分量循环右移i位，得到v(i)=(vn-i,vn-1, v0,v1,vn-i-1)循环码的定义：一个(n,k)线性码C，若它的每个码字的任何循环移位都仍然是一个码字，则称此码为循环码4.2：什么是码字多项式？证明码字多项式v(i)(x)就是xiv(0)(x)/(xn+1)的余式。码字多项式：为研究循环码的代数特性，将码字v=(v0,v1,vn-1)的各个分量看成是多项式 的系数，此多项式称为v的码字多项式码字v(0)=(v0,v1,vn-1)右移一位，得到v(1)=(vn-1, v0,vn-2)，类似的v(2)=(vn-2,vn-1,vn-3) v(0)(x)=vn-1xn-1+vn-2xn-2 +v1 x+v0 v(1)(x)=vn-2xn-1+vn-3xn-2+v0 x+vn-1 v(2)(x)=vn-3xn-1+vn-4xn-2+vn-1 x+vn-2 v(i)(x)= vn-i-1xn-1 + vn-i-2xn-2+vn-i+1x+vn-i因而有v(1)(x)= xv(0)(x) mod (xn+1) v(2)(x)= xv(1)(x)=x2v(0)(x) mod (xn+1) xiv(0)(x)=vn-1xn+i-1+vn-2xn+i-2 +vn-i-1xn-1+v1xi+1+v0xi= vn-i+vn-i+1x+vn-1xi-1+v0xi+v1xi+1 +vn-i-1xn-1+ vn-i (xn+1)+vn-i+1x(xn+1)+vn-1xi-1(xn+1)=q(x)(xn+1)+v(i)(x) 其中q(x)= vn-i +vn-i+1x+vn-1xi-14.3：证明循环码的代数性质定理1-3？定理1：循环码C中次数最低的非零码字多项式是唯一的证明：令 是C中次数最低的码字多项式，若g(x)不唯一，则存在另一个码字多项式 ，由线性性质可知，g(x)+g*(x)也是一个码字多项式，但它的次数小于r，和前提矛盾，所以循环码C中次数最低的非零码字多项式是唯一的。证毕。定理2：若g(x)=g0+g1x+gr-1xr-1+xr是(n.k)循环码C中次数最低的非零码字多项式，则必有g0=1证明：若g0=0，则g(x)=x(g1+g2x+gr-1xr-2+xr-1)，将g(x)循环右移n-1位之后，可以得到一个次数更低的码字多项式，其次数为r-1，和前提矛盾，则必有g0=1。证毕。结合定理1和定理2，知在(n,k)循环码中，次数最低的非零码字多项式形如g(x)=1+g1x+g2x2+gr-1xr-1+xr定理3：若g(x)是(n.k)循环码C中次数最低的非零码字多项式，一个次数小于或等于n-1的二元多项式f(x)是码字多项式当且仅当f(x)是g(x)的倍式证明：反证法。设f(x)是码字多项式并且其次数小于或等于n-1，假设f(x)=a(x)g(x)+b(x), deg(b(x)r，由线性性质可知b(x)=f(x)+a(x)g(x)也是一个码字多项式，而deg(b(x)deg(g(x)，这和前提矛盾，则只能当f(x)是g(x)的倍式的时候，f(x)是码字多项式。证毕。4.4：简述系统循环码的编码原理和编码步骤？编码原理给定循环码的生成多项式g(x)，可以使该码成为系统形式。假定待编码的消息是u=(u0, u1, uk-1)，则对应的消息多项式为u(x)=u0+u1x+u2x2+ uk-1xk-1从而有，xn-ku(x)=u0xn-k+u1xn-k+1+ uk-1xn-1用生成多项式g(x)除xn-ku(x)，得到xn-ku(x)= a(x)g(x)+b(x)，deg(b(x)n-k调整上式得到xn-ku(x)+b(x)=a(x)g(x)，即xn-ku(x)+ b(x)是g(x)的倍式，因而是C的码字多项式， xn-ku(x)+b(x)=b0+b1x+b2x2+ bn-k-1xn-k-1+ u0xn-k+u1xn-k+1+ uk-1xn-1 ，这对应码矢(b0,b1,bn-k-1, u0, u1,uk-1)，此即为系统形式编码步骤第一步：先用xn-k乘以消息多项式u(x)=u0+u1x+u2x2+ uk-1xk-1第二步：用生成多项式g(x)