纠错码题库_2012

1、1, 什么是ARQ？其中英文全称，其同前向纠错区别在哪里？ARQ分为几类？请绘出ARQ传输系统简单框图和等待ARQ工作流程图。 答：ARQ是自动请求重传，是一种双向差错控制系统，采用错误检测和重传。其英文全称为automatic repeat request。前向纠错是单向差错控制系统，即利用纠错码在接收机自动地纠正检测出的错误。ARQ有两类：等待式和连续式。ARQ传输系统简单框图如下：如上图所示，ARQ系统中接收机检测出错误，就向发送端发出要求重传该消息的要求，直到消息被正确接收。ARQ有两种：等待式和连续ARQs。等待ARQ工作流程图如下：如上图所示, 发送端发射一个码字到接收端，同时等待

2、接收端返回一个确认信号(ACK)或否定应答(NACK, NAK) ,如果是ACK，表示成功译码，传送下个码字；如果Fail，重传前码字。2, 什么是信道容量？ 请写出香农信道容量公式，并解释公式中每个参数，请从物理意义角度解释香农容量公式, 请写出香农两大贡献。答：（1） 信道容量也是给定信噪比和带宽条件下，信道能传输的最大信息速率。香农信道容量公式为C=Blog2(1+SNR)，其中B为信道带宽，SNR为接收信号中信号功率与噪声功率之比。（2）由信道容量公式可知，信息传输速率与带宽成正比，与信噪比对数成正比，也就就是说增加带宽和发射信号功率均可增加信息传输速率。每个信道都存在一个信道容量C（

3、最大信息速率），只要需要传输的信息速率R低于C，则存在速率为R的码，用最大似然译码可实现任意小错误概率的信息可靠传输。 3, 纠错码主要性能衡量指标有哪些？香农限如何定义？请阐述香农有噪声信道编码定理。 答：纠错码主要性能指标：误码率和编码增益（相对于具有相同传输速率的非编码系统）。香农限：纠错码设计的目的是获得特定的误码性能所需的新噪比最小化，根据有噪声信道编码定理,可以推出一个码率为R的编码通信系统达到无误码传输状态所必需的最小信噪比的理论极限，这个限称之为香农限。香农有噪声信道编码定理：每个信道都存在一个信道容量C（最大信息速率），只要需要传输的信息速率R低于C，则存在速率为R的码，用M

4、LD可到任意小的错误概率P(E) 对于任意RC, 存在分组码，存在分组长度n足够大的分组码使 同时存在存储级数m足够大的卷积码(n,k保持不变) 4, 请给出群的定义，并枚举出四个群的实例，选择一个实例简单证明其是群。答：群G为一组元素的组合，在这些集合上定义了一个二元运算符*，G中任意两个元素a和b在二元运算符*作用下，即a*b=c, c仍然属于G, 即封闭性, 另外G在运算符*作用下满足如下三个特性：1) 满足结合律 (a*b)*c=a*(b*c)；2) G中存在一个单位元e，对于G中任意个元素，我们有e*a=a*e=a; 3) 对于G中任意元素，存在另外一个元素a, a*a=a*a=e,

5、 我们称a是a的逆元素。群的实例: 实数集合在实数加法运算是群，非零实数在实数乘法下满足群所有特性，因此是乘法群，整数集合在整数加法运算下满足群所有特性，是加法群。5, 请给出域的定义，并枚举出两个域的实例，同时简单证明它们是域。 6 构造集合0,1,2在模3加法和模3乘法表和模3加法表，观察此两表，请回答如下问题：1) 集合0,1,2在模3加法下构成加法群吗？为什么？如果是加法群，其单位元等于0，1还是2？元素2在加法群中逆元素是0还是1？2） 集合0,1,2在模3乘法构成乘法群吗？为什么？如何修改集合0,1,2使其变成乘法群？新乘法群的单位元等于1还是2在新乘法群中逆元素是1还是2？解：集

6、合0,1,2在模3加法表和模3乘法表分别如下：模3加法表+012001211202201模3乘法表*012000010122021（1） 如上述加法表所示，集合0,1,2在模3加法下满足加法群的所有特性比如封闭性，其中任意两个原则在模3加法仍然形成该集合的元素，模三加满足分配律，结合律和交换律，集合存在单位元0，任意元素均存在逆元素，如2的逆元素是1，0的逆元素是0，因此构成加法群。（2） 集合0,1,2在模3乘法下不构成乘法群，因为0元素不存在逆元素，当然，除去该集合中零元素后的新集合1,2在模3乘法下构成乘法群， 其中1是单位元，2的逆元素是2，1的逆元素是1。7 构造集合0,1,2，3，

7、4模5加法表和模5乘法表，观察此两表，请回答如下问题：（1）集合0,1,2，3，4在模5加法下构成加法群吗？为什么？如果是加法群，其单位元等于多少？ 给出元素3和1在加法群中逆元素；（2）集合0,1,2，3，4在模5乘法构成乘法群吗？为什么？如何修改集合0,1,2，3，4使其变成乘法群？新乘法群的单位元等于多少？在新乘法群中1，2，3和4逆元素分别为多少？答：集合0,1,2，3，4模5加法和模5乘法表如下：模5加法表+01234001234112310223401334012440123模5乘法表+01234000000101234202413303142404321（1） 如上述加法表所示，

8、集合0,1,2，3，4在模5加法下满足加法群的所有特性比如封闭性，其中任意两个原则在模5加法仍然形成该集合的元素，模三加满足分配律，结合律和交换律，集合存在单位元0，任意元素均存在逆元素，如2的逆元素是3，1的逆元素是4，因此构成加法群。（2） 集合0,1,2，3，4在模5乘法下不构成乘法群，因为0元素不存在逆元素，除去零元素后集合的群1,2，3，4在模5乘法下构成乘法群， 其中1是单位元，2的逆元素是3，4的逆元素是4本身。8 X3+X+1在GF(2)是不可约多项式吗？请证明你的结论， X7+X+1被其除后的商和余数多项式为多少？请写出整个多项式除法过程。解：次数低于X3+X+1的大于0的所

9、有多项式为：X,X+1,X2,X2+1,X2+X+1对于X， X3+X+1= (X2+1 )X+1, 对于X+1, X3+X+1除以X+1的过程如下：由上述过程，我们有X3+X+1=（X2+X）(X+1)+1对于X2, 我们有 X3+X+1= (X)X2+X+1, 对于X2+1, 我们有X3+X+1=(X2+1) (X)+1,对于X2+X+1, 我们有X3+X+1由上述过程, 我们有X3+X+1=（X2+X+1）(X+1), 因此X3+X+1是不可约多项式。9 X4+x+1在GF(2)是不可约多项式吗？是本原多项式吗啊？请证明你的结论， X6+X+1被其除后的商和余数多项式为多少？请写出此两个

10、多项式除法过程。 10设a为GF(24)的一个本原元，利用表2-8求解下列X, Y, Z的联立方程组 X+a5Y+Z=a7 X+aY+aZ=a9 a2X+Y+a6Z=a解：11 (7,4)线性分组码的有如下生成矩阵: 请回答如下问题：（1） 该码是系统码吗？（2） u=1 0 1 1待编码消息，请计算相应的码字；（3） 该码的奇偶校验矩阵H=?（4） v=1 0 1 1 1 0 0是G生成的码字吗？（5） 如果接收的码字是r=1 0 1 1 1 0 1 是G生成的码字吗？该码发生错误了？解：(1) 该码是系统码，因为G可写为如下分块矩阵形式P I4;(2) v=uG=1 0 0 1 0 1 1

11、;(3) (4) vHT=0 0 0, 因此v=1 0 1 1 1 0 0是G生成的码字12 (6,3)线性分组码的有如下生成矩阵:请回答如下问题：（1） 该码是系统码吗？（2） u=1 0 1待编码消息，请计算相应的码字；（3） 该码的奇偶校验矩阵H=?（4） v=1 0 1 1 1 0是G生成的码字吗？解：(1) 该码是系统码，因为G可写为如下分块矩阵形式P I4;(2) v=uG=1 0 0 1 0 1 1;(3) (4) vHT=0 0 0, 因此v=1 0 1 1 1 0 0是G生成的码字13 考虑由循环码生成多项式g(X)=1+X+X3生成的(7,4)循环系统码，令u(x)=1+X

12、2+X3为待编码的消息。请求解如下问题：（1） 求由消息u(x)生产码字多项式；（2） 根据g(X)形成该码的生成矩阵；（3） 校验多项式。解：(1)用X3u(X)除以 g(X)获得如下长除过程从上式我们获得b(X)=X, 故码字多项式为v(X)=b(X)+X3u(X)=X+X2+X4+X6(2) 考虑一个(7，4,)循环码，4个多项式g(x), xg(X),X2g(X), X3g(X)张成循环码，以此四个多项式对应的7维向量作为4x7矩阵的行向量，则可得到码C的生成矩阵如下：（3）14 考虑一个(15,11)循环汉明码，生成多项式为g(X)=1+X+X1) 确定该码的校验多项式h(X);2)

13、 确定该码对偶码的生成多项式；3) 找出该码系统形式的生成矩阵和奇偶校验矩阵；15 考虑一个(8,4)系统码，其奇偶校验方程为：V0=u1+u2+u3, v1=u0+u1+u2, v2=u0+u1+u3,v3=u0+u2+u3其中u0、u1、u2和u3是消息位，v0、v1、v2和v3是校验位。求此码的生成矩阵和奇偶校验阵。解析证明此码的最小距离为4。16 设C为线性分组码，其码字重量既有偶数又有奇数。证明偶数重量码字个数等于奇数重量的码字。17 长度为n的重复码(n,1)是线性分组码，其只有两个码字，即全零码字(00.0)和全一码字(11.1), 该码的对偶码是单其偶校验码，请回答下列问题：1

14、） 推导该码的生成矩阵G和奇偶校验矩阵H；2） 该码的对偶码是单其偶校验码生成矩阵G和奇偶校验矩阵H。18考虑如下奇偶校验矩阵H确定的(7，4)线性分组码，r=（1 001001）为接收的码字，通过纠正子译码算法计算r对应的发射端传输的码字v。解： 接收端收到后，计算纠正子：S=rHT=(1 1 1)假定接收端由于信道产生的差错图样为e=(e0,e1,e2,e3,e4,e5,e6)。考虑到S=eHT=rHT我们有：1=e0+e3+e5+e6, 1=e1+e3+e4+e5, 1=e2+e4+e5+e6满足上述方程组共有16种错误图样，即（0000010），（1010011），（1101010），

15、（0111011）（0110110），（1100111），（1011110），（0001111）（1111000），（0100001），（0011000），（1001001）（1000100），（0010101），（0101100），（1111101）其中差错图样e=(000010)具有最小码重，对于BSC信道，e=(000010)是满足上述方程组可能性最大的差错图样，则发射的码字为vV=r+e=（1001001）+（0000010）=（1001011）19 重复码和单奇偶校验码互为对偶码，两者均为线性分组码，假定码字长度为6，请回答如下问题：（1） 给出6重重复码的生成矩阵G和校验矩阵H；（2） 给出重复码的码字集合；（3） 重复码是否是循环码? 请证明自己结论。（5） 重复码是否是否为系统码？20 重复码和单奇偶校验码互为对偶码，两者均为线性分组码，假定码字长度为5，请回答如下问题：（1） 给出单奇偶校验码的生成矩阵G和校验矩阵H；（2） 给出单奇偶校验码的码字集合；（3）单奇偶校验码是否是循环码? 请证明自己结论。（5） 单奇偶校验码是否是否为系统码？21 给定一个生成矩阵多项式为 G(D)=1，1+D3 的前馈二进制卷积码的编码器，回答如下问题：（1） 该卷积码编码器的实现框图（逻辑电路图）；（2