首，需要做置换操作
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的一个陪集，且有b∈a+C，那么一定有b+C=a+C
证明：1) b=b+0∈b+C；2) 对于所有的x∈C,由x→a+x定义的映射C→a+C是个一一映射，所以陪集a+C中矢量的个数和码集中码矢的个数相等，即qk 3.21：简述伴随式译码方法的步骤。 步骤1：计算接收矢量r的伴随式r·HT
步骤2：确定伴随式等于r·HT对应的陪集首ei，然后假定ei是信道引起的错误图样 步骤3：将接收矢量r译码为码字v=r+ei
3.22：请构造一种线性分组码，给出具体的生成矩阵，一致校验矩阵，以及译码方法等。 (7,4)线性分组码
如果表格所表示的线性分组码，有如下的生成矩阵，一致校验矩阵
??1000110?1110G??0100011???10?1001?0010111??,H??11?0001101????011100
第四章
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)
0?0?1???循环码的定义：一个(n,k)线性码C，若它的每个码字的任何循环移位都仍然是一个码字，则称此码为循环码
4.2：什么是码字多项式？证明码字多项式v(i)(x)就是xiv(0)(x)/(xn+1)的余式。
码字多项式：为研究循环码的代数特性，将码字v=(v0,v1,?,vn-1)的各个分量看成是多项式
v?x???vix?v0?v1x?...?vn?1xii?0的系数，此多项式称为v的码字多项式
n?1n?1
码字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-1
4.3：证明循环码的代数性质定理1-3？
定理1：循环码C中次数最低的非零码字多项式是唯一的 证明：令
g?x???gixi,gr?1i?0rr 是C中次数最低的码字多项式，若g(x)不唯一，则存在另
，由线性性质可知，g(x)+g*(x)也是一个码字多项式，
一个码字多项式
*g??x???gi*xi,gr?1i?0但它的次数小于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)) 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)) 编码步骤 第一步：先用xn-k乘以消息多项式u(x)=u0+u1x+u2x2+?+ uk-1xk-1 第二步：用生成多项式g(x)除xn-ku(x)，得到余式b(x) 第三步：联合b(x)和xn-ku(x)，得到码字多项式v(x)=b(x)+xn-ku(x) 4.5：请构造一个具体的循环码并且采用适当的算法进行译码？ 考虑(7,3)汉明码，n=7,k=3,k-1=2，码字为 (1001110),(0100111),(1010011),(1101001),(1110100),(0111010),(0011101)，因为码字(0011101)前面有k-1=2个零，将它作为g(x)，即g(x)= 1+x+x2+x4，得到 2346?x2g(x)??x?x?x?x??1110100????235?G(x)??xg(x)???x?x?x?x?G??0111010???24???g(x)?1?x?x?x?????0011101?? ?因为生成多项式 kg(x)是1+xn的因式，所以存在另一个多项式 h?x???i?0hixi,h0?hk?1 ，使得g(x)h(x)=1+xn，此多项式h(x)称为码C的校验多项 式，码C的一致校验矩阵可以由h(x)得到。 设v=(v0, v1,?, vn-1)是C的一个码矢，则v(x)=a(x) g(x)，有v(x)h(x)=a(x)g(x)h(x)=a(x)(1+xn)=a(x)+ a(x)xn，由于deg(a(x))≤k-1，故在a(x)+a(x)xn中不会出现xk, xk+1,?, xn-1等各次幂，于是v(x)h(x)的展开式中xk, xk+1,?, xn-1的系数等于零 译码算法描述如下： 1) 接收矢量全部移入伴随式寄存器，便得到了伴随式，与此同时，接收矢量也存入缓冲寄存器 2) 把伴随式读入检测器，以探测相应的错误图样，检测器的输出是一个与缓存器输出符号相应的错误估计值 3)由缓存器输出第一个接收符号，与此同时，伴随式寄存器移位一次。若检测到第一个接收符号是错误的，则检测器的输出给予纠正。检测器的输出也反馈到伴随式寄存器以修正伴随式。这样便得到了一个新的伴随式，它相应于向右移位1次后所得的修正接收矢量的伴随式 4) 由第3步所得的新伴随式，用来检测第2个接收符号是否有错。译码器重复第2-3步。第2个符号的纠正方法和第一个接收符号一样 5)如上所述，译码器逐个符号地译接收矢量，直到从缓存器中读出全部接收矢量为止 举例 多项式1+x7可以分解为1+x7=(1+x)(1+x+x3) (1+x2+x3)，其中有两个次数为3的因式，都可以生成(7,4)循环码，本章PPT第13页给出的表格的循环码，是由1+x+x3生成的，该码最小距离为3，能纠正1个错误。 该码非系统码，若待编码消息u=(1010)，相应消息多项式为1+x2，用g(x)和u(x)相乘得到如下码字多项式v(x)=u(x)g(x)=(1+x2) (1+x+x3)=1+x+x3+x2+x3+x5=1+x+x2+x5，即码矢为(1110010) 4.6：如何根据码字多项式g(x)得到循环码的生成多项式？ 第四章7 8 9页ppt 六、从所学专业角度，谈谈你自己对编码理论这门课程的理解。（共10分） 编码理论是数学和计算机科学的一个分支，处理在噪声信道传送资料时的错误倾向。按照编码理论，资料传送时会采用更好的方法以修正传送途中所产生的大量错误。 编码共分两类： 1，信源编码（数据压缩） 2，信道编码（前向纠错） 研究信息传输过程中信号编码规律的数学理论。编码理论与信息论、数理统计、概率论、随机过程、线性代数、近世代数、数论、有限几何和组合分析等学科有密切关系，已成为应用数学的一个分支。编码是指为了达到某种目的而对信号进行的一种变换。其逆变换称为译码或解码。 分支 根据编码的目的不同，编码理论有三个分支： ①信源编码。对信源输出的信号进行变换，包括连续信号的离散化，即将模拟信号通过采样和量化变成数字信号，以及对数据进行压缩，提高数字信号传输的有效性而进行的编码。[1] ②信道编码。对信源编码器输出的信号进行再变换，包括区分通路、适应信道条件和提高通信可靠性而进行的编码。 ③保密编码。对信道编码器输出的信号进行再变换，即为了使信息在传输过程中不易被人窃取而进行的编码。编码理论在数字化遥测遥控系统、电气通信、数字通信、图像通信、卫星通信、深空通信、计算技术、数据处理、图像处理、自动控制、人工智能和模式识别等方面都有广泛的应用。 信源编码（数据压缩） 在计算机科学和信息论中，数据压缩或者源编码是按照特定的编码机制用比未经编码少的数 据比特（或者其它信息相关的单位）表示信息的过程。例如，如果我们将“compression”编码为“comp”那么这篇文章可以用较少的数据位表示。一种流行的压缩实例是许多计算机都在使用的ZIP文件格式，它不仅仅提供了压缩的功能，而且还作为归档工具（Archiver）使用，能够将许多文件存储到同一个文件中。 信道编码（前向纠错） 前向纠错（英语：Forward error correction,缩写FEC）是一种在单向通信系统中控制传输错误的技术，通过连同数据发送额外的信息进行错误恢复，以降低误码率（bit error rate,BER）。FEC又分为带内FEC和带外FEC。FEC的处理往往发生在早期阶段处理后的数字信号是第一次收到。也就是说，纠错电路往往是不可分区的一部分的模拟到数字的转换过程中，还涉及数字调制解调，或线路编码和解码。 FEC是通过添加冗余信息的传输采用预先确定的算法。1949年汉明（Hamming）提出了可纠正单个随机差错的汉明码。1960年Hoopueghem,Bose和Chaudhum发明了BCH码，Reed与Solomon又提出 ReedSolomon（RS）编码，纠错能力很强，后来称之为里德-所罗门误码校正编码（The reed-solomon error correction code,即后来的附加的前向纠错）。ITU-T G.975/G.709规定了“带外FEC”是在SDH层下面增加一FEC层，专门处理FEC的问题。带外FEC编码冗余度大，纠错能力较强。FEC有别于ARQ，发现错误无须通知发送方重发。一旦系统丢失了原始的数据包，FEC机制可以以冗余数据包加以补入。例如有一数据包为“10”，分成二个数据包，分别为“1”和“0”，有一冗余数据包“0”，收到任意两个数据包就能组装出原始的包。但这些冗余数据包也会产生额外负担。 历史背景 1843年美国著名画家S.F.B.莫尔斯精心设计出莫尔斯码，广泛应用在电报通信中。莫尔斯码使用三种不同的符号：点、划和间隔，可看作是顺序三进制码。根据编码理论可以证明，莫尔斯码与理论上可达到的极限只差15%。但是直到20世纪30～40年代才开始形成编码理论。1928年美国电信工程师H.奈奎斯特提出著名的采样定理，为连续信号离散化奠定了基础。1948年美国应用数学家C.E.香农在《通信中的数学理论》一文中提出信息熵的概念，为信源编码奠定了理论基础。1949年香农在《有噪声时的通信》一文中提出了信道容量的概念和信道编码定理，为信道编码奠定了理论基础。无噪信道编码定理（又称香农第一定理）指出，码字的平均长度只能大于或等于信源的熵。有噪信道编码定理（又称香农第二定理）则是编码存在定理。（见香农三大定理）它指出只要信息传输速率小于信道容量，就存在一类编码，使信息传输的错误概率可以任意小。随着计算技术和数字通信的发展，纠错编码和密码学得到迅速的发展。[1] 在信源编码方面 1951年香农证明，当信源输出有冗余的消息时可通过编码改变信源的输出，使信息传输速