《编码原理 习题(含答案或提示)》由会员分享，可在线阅读，更多相关《编码原理 习题(含答案或提示)（5页珍藏版）》请在金锄头文库上搜索。
1、 纠错编码课程习题及解答提示 纠错编码课程习题及解答提示 1. 奇校验码码字是奇校验码码字是 011 (, ) k m mmp =c? ，其中奇校验位，其中奇校验位p满足方程，满足方程， 2 mod 1 110 =+ pmmm k ? 证明奇校验码的检错能力与偶奇校验码的检错能力相同，但奇校验码不是线性分组码。证明奇校验码的检错能力与偶奇校验码的检错能力相同，但奇校验码不是线性分组码。 证明提示证明提示： 奇数个差错的发生总导致校验方程不满足。全 0 向量不是奇校验码码字。 2. 一个一个)2 , 6(线性分组码的一致校验矩阵为线性分组码的一致校验矩阵为 1 2 3 4 1 0 0 0 1 0
2、 0 0 1 1 0 0 1 0 1 0 1 1 1 0 h h h h = H （1）求）求4 , 3 , 2 , 1, =ihi使该码的最小码距使该码的最小码距3 min d 。 （2）求该码的系统码生成矩阵）求该码的系统码生成矩阵 s G 及其所有及其所有 4 个码字。个码字。 解题提示： 解题提示： （1）对 H 作行初等变换得 1 21 31 423 10001 10010 10100 01000 h hh H hh hhh + = + + 要使最小码距等于 3，有 11213423 , , , hhhhhhhh+中任意两项为 1，其余为零。当要使最 小码距大于 3，有 112134
3、23 , , , hhhhhhhh+中三项或四项均为 1，其余为零。有上述关系可以 求得一组或多组关于4 , 3 , 2 , 1, =ihi的解。 （2）对 H 作行初等变换得 () 423 31 21 1 01000 10100 10010 10001 T k rr hhh hh HQI hh h + + = = + 3. 一个纠错码的全部消息与码字的对应关系如下：一个纠错码的全部消息与码字的对应关系如下： (00)(00000)，(01)(00111)，(10)(11110)，(11)(11001) （1）证明该码是线性分组码；）证明该码是线性分组码； （2）求该码的码长，编码效率和最小码
4、距；）求该码的码长，编码效率和最小码距； （3）求该码的生成矩阵和一致校验矩阵；）求该码的生成矩阵和一致校验矩阵； （4）构造该码在）构造该码在 BSC 上的标准阵列；上的标准阵列； （5）若在转移概率）若在转移概率 3 10=p 的的 BSC 上消息等概发送，求用标准阵列译码后的码字差错概率和 消息比特差错概率。 上消息等概发送，求用标准阵列译码后的码字差错概率和 消息比特差错概率。 解题提示：解题提示： （1）任意两个码字的和是另一个码字且全零向量为码字。 （2）码长为向量长，即5n =。码字数为 4，故 2 log log 42 55 q M R n =。最小非零码字的 重量为min3w
5、d=。 （3）因为码字数为 4，任意两非零码字构成生成矩阵的行向量 11110 00111 G = 。按 G 与 H 正交的 条件，解得 H 的一种可能情况等于 11110 11000 01101 。 （4）标准阵列见题表（3.1） 。 题表（3.1） 标准阵列 0 c00000 1 c00111 2 c11110 3 c11001 0 e00000 00000 00111 11110 11001 1 e00001 00001 00110 11111 11000 2 e00010 00010 00101 11100 11011 3 e00100 00100 00011 11010 11101
6、4 e01000 01000 01111 10110 10001 5 e10000 10000 10111 01110 01001 6 e10010 10010 10101 01100 01011 7 e10100 10100 10011 01010 01101 （5）按题解（4）的标准阵列译码，记 c A是标准阵列中码字 c 对应的列，E是包括无错图案和全 部可纠正差错图案的集合，那么码字差错概率为 ()()() 543 2 ( )1( ) ()1( )( ) 1( )( ) ( ( ) 1 1415121 4 Wc c Cc Ce E c Ce E PeP c P rceAP cP e P
7、 cP eP c ppppp = =+ = = = + 均匀分布，信道差错均匀分布 记消息比特差错概率为( ) b P e，消息向量差错概率为( ) B P e，注意到该码是非系统码以及消息向量 长为 2，则应有 () 2 ( )( )1( )11( ) WBBb PeP eP cP e= = () 23 ( )11( )111252 bW P ePepppp= = + （6）码字差错概率计算中 0 ()0.8 0.8P c=， 12 ( )()0.8 0.2P cP c=， 3 ()0.2 0.2P c= ()()() 543 2 ( )15121 e E P eppppp =+ 消息比特差
8、错概率： ()() ()() () ()() () 222222 10.8810.2810.810.21pppppp （7）码字差错概率计算中 0123 ()( )()()1 4P cP cP cP c= ()() 22 42 0102111210 11 11 101 10 44 PPPPP 消息比特差错概率： ()()()() 22 424422 11 11 101 108 101 108 101 10 44 此题，恰有码字差错概率和消息比特差错概率相等。 4. 证明线性分组码的码字重量或者为偶数（包括证明线性分组码的码字重量或者为偶数（包括 0）或者恰好一半为偶数（包括）或者恰好一半为偶数
9、（包括 0）另一半为奇数。）另一半为奇数。 证明提示：证明提示： 若码字重量全为奇数，则码不含全零码字，故不是线性码。 若码字重量全为偶数，则任意两偶数重量的码字 c 与 c相加仍为偶数重码字，故所有码字均可以 是偶数重码字。 若 0 M个偶数重量的码字集合 cc和 1 M个奇数重量码字为集合 c ， 则根据二元线性分组码的 任意码字重量满足()( )( )()2 HHHH wccwcwcwc c+=+可得：对固定的奇数重码字 1 c有 1 ccc+ ，所以 101 ccMM + = 。又对任意奇数重码字 j c ， 1 2,3,jM=，由 1j cc+而有， 11 2,3, j ccjMc+
10、=， 所以 10 11MM ， 由此证明 01 MM=。 5. 一个通信系统消息比特速率为一个通信系统消息比特速率为Kbps 10，信道为衰落信道，在衰落时间（最大为，信道为衰落信道，在衰落时间（最大为ms 2）内可以 认为完全发生数据比特传输差错。 ）内可以 认为完全发生数据比特传输差错。 （1）求衰落导致的突发差错的突发比特长度。）求衰落导致的突发差错的突发比特长度。 （2）若采用汉明码和交织编码方法纠正突发差错，求汉明码的码长和交织深度。）若采用汉明码和交织编码方法纠正突发差错，求汉明码的码长和交织深度。 （3）若用分组码交织纠正突发差错并限定交织深度不大于）若用分组码交织纠正突发差错并
11、限定交织深度不大于 256，求合适的码长和最小码距。，求合适的码长和最小码距。 （4）若用某个）若用某个 BCH 码交织来纠正突发差错并限定交织深度不大于码交织来纠正突发差错并限定交织深度不大于 256，求合适的码长和，求合适的码长和 BCH 码 生成多项式。 码 生成多项式。 解题提示：解题提示： （1）突发长度为 33 10 102 1020b = =bits。 （2）汉明码可纠正 t1 个差错，所以交织深度D为/20b t =。由于没有延迟限制，所以任何码 长汉明码均可。 （3）由()2562561 2bD ttd= ，以及1dnk+设计。 6. 若循环码以若循环码以 ( )1xx= +
12、g 为生成多项式，则为生成多项式，则 （1）证明）证明 ( )xg 可以构成任意长度的循环码；可以构成任意长度的循环码； （2）求该码的一致校验多项式）求该码的一致校验多项式 ( )xh ； （3）证明该码等价为一个偶校验码。）证明该码等价为一个偶校验码。 解题提示：解题提示： （1）由 123 1(1)(1) nnnn xxxxx =+?， 1x+总是1 n x 的因子。 （2）一致效验多项式为 21 ( )1/ ( )1 nn h xxg xxxx = +?。 （3）对生成矩阵作行初等变换总能获得偶校验码的生成矩阵形式。 (1)(1) 11000010001 01100001001 000
13、11000101 00001100011 nnnn ? ? ? ? ? ? ? ? ? ? 行初等变换 7. 已知已知)5 , 8(线性分组码的生成矩阵为线性分组码的生成矩阵为 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 = G ， （1）证明该码为循环码；）证明该码为循环码； （2）求该码的生成式）求该码的生成式 ( )xg ，一致校验式，一致校验式 ( )xh 和最小码距和最小码距d。 解题提示：解题提示： （1）行等价生成矩阵为 5 8 11110000 01111000
14、00111100 00011110 00001111 （2）生成多项式为 23 ( )1g xxxx= +，校验多项式为 45 ( )1h xxxx= +，最小码距为 2。 8. ATM 协议对帧头协议对帧头 4 字节（字节（32 比特）地址和路由信息校验所用的比特）地址和路由信息校验所用的 8 比特比特 CRC 码生成多项式为码生成多项式为 1)( 28 +=xxxxg ，在实际应用中是以此码构造一个最小码距为，在实际应用中是以此码构造一个最小码距为4=d的的 )32,40( 码，讨论其构造方法。码，讨论其构造方法。 解题提示：解题提示：利用循环码缩短方法。 9. 对如下图（对如下图（E-9A）和图（）和图（E-9B）两卷积码分别做：）两卷积码分别做： 图图 E-9A 图图 E-9B （1） 求卷积码的多项式生成矩阵） 求卷积码的多项式生成矩阵( ) xG， 生成矩阵， 生成矩阵 G ， 渐进编码效率， 渐进编码效率R， 约束长度， 约束长度K， 状态数， 状态数M。 （2）求自由距离）求自由距离 f d 。 （3）画出开放型的状态转移图，栅格图。）画出开放型的状态转移图，栅格图。 消息 ( )xu 码字 ( )xv 码字 1( ) xv 码字 2( ) xv 消息( )xu （4）求消息）求消息(100110)=u的卷积码码字序列的卷积码码字序列 012
