第9章差错控制编码习题解答.pdf

第第 9 章章 差错控制编码习题解答差错控制编码习题解答 9-1 （1） 写出循环码的码多项式的一般表达式； ),(kn （2） 已知循环码的生成多项式为，若分别为和 1， 求循环码的码字。 ) 3 , 7(1)( 24 +=xxxxg)(xm 2 x 解： :, 1)()( )( :,)( 1)(: , 4, 3,) 3 , 7()2( )( ),() 1 ( 3 624 2 24 01 2 2 1 1 过程如下的余式为 得根据编码规则若信息码 生成多项式 循环码 式为系统码码字的一般表达 + = = += = += xxxgxmx xxxxmx xxm xxxxg rk axaxaxaxA kn r r n n n n L 1001011 1 1011 1 1 1 1 0123456 2 3 3 24 234 2346 624 = + + + + + + + aaaaaaa x xx xx xxx xxx xxxx xxxx 最后得系统码码字为 对应码为 得余多项式为 1001011 1 1011 1 1 1 1 0123456 2 3 3 24 234 2346 624 = + + + + + + + aaaaaaa x xx xx xxx xxx xxxx xxxx 最后得系统码码字为 对应码为 得余多项式为 0010111 1 0111 1 1 1 1 0123456 2 2 24 424 = + + + + aaaaaaa xx xx xxx xxxx 最后得系统码码字为 对应码为 得余多项式 :, 1)()( )(:, 1)( 2 4 过程如下的余式为 则有若信息码 + = xxxgxmx xxmxxm r r 0010111 1 0111 1 1 1 1 0123456 2 2 24 424 = + + + + aaaaaaa xx xx xxx xxxx 最后得系统码码字为 对应码为 得余多项式 :, 1)()( )(:, 1)( 2 4 过程如下的余式为 则有若信息码 + = xxxgxmx xxmxxm r r 9-2 （5,1）重复码若用于检错，能检测几位错？若用于纠错，能纠正几位错？，若同时用 于检错与纠错，情况又如何？ 1 解： .31 ,2,4, 5) 1 , 5( : 1,)(,)2( 12,)2( 1,) 1 ( 0 0 0 0 位错位错和检并同时能纠 位错纠位错故能检重复码由上述公式得 则要求随机错误个同时检测个纠 则要求个随机错误纠 则要求个随机错误检测 = + + + d etdteet tdt ede 9-3 已知八个码字分别为 000000、001110、010101、011011、100011、101101、110110、 111000，试求其最小码距。 0 d 解： . 3,1, 1,0:. , , .: . ,: 111000 110110, 101101, 100011, 011011, ,010101 ,001110 ,000000 8 0 =d故得的个数为最小汉明距离该码中少的码 的个数为最找出码外除全具体方法是是类似的 性这和实数运算具有封闭属于该码组中的一个码 仍然算的结果码组中任意两组异或运闭性是指 所谓封性来判断利用码组是否具有封闭方法二 码组大时较麻烦 这种方法在可得最小汉明距离两两比较方法一 个码组为已知 9-4 上题所给的码组若用于检错，能检测几位错？用于纠错，能纠正几位错？，若同时用 于检错与纠错，情况又如何？ 解： ).3?( ,2,1: 1 ,)(,)3( 12,)2( 1,) 1 ( :. 3 0 0 0 0 条不满足第为什么同时用于纠错和检错 但不能位错检位错能纠由上述公式得 要求 则随机错误个同时检测个纠 则要求个随机错误纠 则要求个随机错误检测 利用公式得 + + + = etd teet tdt ede d 9-5 汉明码（7,4）循环码的，若输入信息组 0111，试设计该码的编码电路， 并求出对应的输出码字。 1)( 3 +=xxxg 2 解： :.0111010 )()( ) 1()( :, 1)( 1)(:, 3, 4,)4 , 7() 1 ( 0123456 34523 2 3 编码器如下最后得系统码字为 的余式为 则有若信息码 生成多项式循环码 = +=+= += += aaaaaaa xxgxmx xxxxxxxmx xxxm xxxgrk r r 0 D 1 D 2 D门1门1 门2门2 或 门 或 门 输出输出 m 9-6 已知线性码的监督矩阵为 = 1 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 H 试求其标准监督矩阵。 解： = 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 14 初等变换 行行移至第将第 初等变换 H P I = 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 14 初等变换 行行移至第将第 初等变换 H P I 3 9-7 有如下所示两个生成矩阵，试说明它们能否生成相同的码字？ 21 GG 和 = 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 1 G = 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 2 G 解： 经初等变换后，它们的标准阵相同，故能生成相同码字。 = 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 21 GG 9-8 已知（7,4）循环码的生成多项式为。 1)( 3 +=xxxg （1）求生成矩阵和监督矩阵； （2）写出循环码的全部码字。 解： = = + + + + = = = += 1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 1 )( )( )( )( )( )( )( )( )( 1)(, 3, 4,)4 , 7( 3 24 235 346 2 3 2 1 3 H G xx xxx xxx xxx xg xxg xgx xgx xg xxg xgx xgx xG xxxgrk k k 初等变换 循环码 LLL = = + + + + = = = += 1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 1 )( )( )( )( )( )( )( )( )( 1)(, 3, 4,)4 , 7( 3 24 235 346 2 3 2 1 3 H G xx xxx xxx xxx xg xxg xgx xgx xg xxg xgx xgx xG xxxgrk k k 初等变换 循环码 LLL 9-9 已 知 （ 15,7 ） 循 环 码 由生 成 ， 问 接 收 码 字 为 ，是否需要重发？ 1)( 4678 +=xxxxxg 1)( 514 +=xxxxT 解： 4 ., 0 1 1 1 1 11 1)( 1)(,)7 ,15( 356 367 367 3791011 691011 59111213 56101213 610121314 5144678 514 4678 故需要重发错故码字在传输过程中有由于余多项式不为 得余多项式为 接收码字为 循环码已知 xxx xxxx xxxx xxxxx xxxxx xxxxx xxxxxx xxxxx xxxxxxx xxxxT xxxxxg + + + + + + + + + += += ., 0 1 1 1 1 11 1)( 1)(,)7 ,15( 356 367 367 3791011 691011 59111213 56101213 610121314 5144678 514 4678 故需要重发错故码字在传输过程中有由于余多项式不为 得余多项式为 接收码字为 循环码已知 xxx xxxx xxxx xxxxx xxxxx xxxxx xxxxxx xxxxx xxxxxxx xxxxT xxxxxg + + + + + + + + + += += 9-10 设（7,3）线性分组码的监督矩阵为 = 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 H 试解答以下问题： （1）监督码元与信息码元之间的关系表达式； （2）列出所有的许用码字； （3）汉明距离 ? 0 =d （4）画出编码器电路； （5）校正子的数学表达式； （6）列出错误码位、错误图样和校正子输出之间关系的表格； （7）画出译码器电路。 解： （1）由：，得： = 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 H = = = = 540 651 6542 643 aaa aaa aaaa aaa （2）所有的许用码字如下： 456 aaa 0123 aaaa 000 0000 001 1101 010 0111 011 1010 100 1110 101 0011 110 1001 111 0100 5 （3）由上表知汉明距离为4 0 =d。 （4）画出编码器电路如下： 6 a 5 a 4 a 3 a 2 a 1 a 0 a （5） = = = = = 0451 1562 24563 3464 eees eees eeees eees EHS T （6）列出错误码位、错误图样和校正子输出之间关系的表格如下： S4S3S2S1e6e5e4e3e2e1e0哪位出错 对应 4-16 译码 器输出 0000 0000000 无错 Z0 0001 0000001 b0Z1 0010 0000010 b1Z2 0100 0000100 b2Z4 1000 0001000 b3Z8 1101 0010000 b4Z13 0111 0100000 b5Z7 1110 1000000 b6Z14 （7）画出译码器电路如下： 6 b 5 b 4 b 3 b 2 b 1 b 0 b 3 S 1 S 2 S 6 b 5 b 4 b 纠错电路 异或运算 4 S 14 Z 4-16 译 码 器 13 Z 15 Z 7 Z 2 Z 1 Z 或 门 出错 指示 6 9-11 已知（7,4）循环码的生成多项式为，试解答以下问题： 1)( 3 +=xxxg （1）设计出该循环码的编码电路； （2）设计出该循环码的译码电路，分以下步骤进行： 已知发送端发送的正确码字为0100111 0123456 =aaaaaaaT， 若有错， 利用它设 计译码器中的校正电路（即反馈移位寄存器的哪些输出应接非门） ； 6 a 写出译码电路中反馈移位寄存器的状态方程； 画出状态转换表； 画出状态转换图； 分析当码字中的、分别出错时，译码器能否正确纠错？ 从而论证译码器的设计是否正确。 5 a 4 a 3 a 2 a 1 a 0 a 解 根据图 9-7 所示的规则，得除法电路为例 9-5 图所示。 1、编码电路的设计结果如下图所示。 1 D 2 D 0 D 输入信息码 输出码字 1 K 2 K 1 2 2、译码电路的设计结果下如图所示。 （1） 其中反馈移位寄存器的哪些输出端要加非门可由码元发生错误来确定。 出错， 码字变成 1100111， 对应的码多项式为， 余多项式为， 在 和的输出端口串入一个非门。 6 a 6 a 1)( 256 +=xxxxxT100 2 x 2 R 1 R 4 T 3 T 2 T 1 T 1 R K & S 校正 信号输出 译码 输出)(xT 7级缓存器(延时器) 除法运算器 余数最高位 异或器 6 T 5 T 反馈移位寄存器及输出和S校正信号产生器 余数最低位 6 a 5 a 4 a 3 a 2 a 1 a 0 a 0 T 2 R 3 R 余数 1 R 2 R 3 R n Q1 n Q2 n Q3 7 （2）根据上图，得反馈移