信息论与纠错编码题库.doc

1、第八章 线性分组码8.1 什么是检错码？什么是纠错码？两者有什么不同？答：能发现错误但不能纠正错误的码称为检错码；不仅能发现错误而且还能纠正错误的码称为纠错码。8.2 试述分组码的概念，并说明分组码的码率 r 的意义。答：分组码是把信息序列以每 k 个码元分组，即每 k 个码元组成一个信息组。n 表示码长,k表示信息位的数目，码率 r=k/n，它说明在一个码字中信息为所占的比重。8.3 什么是码的生成矩阵和校验矩阵？一个（n，k）线性分组码的生产矩阵和校验矩阵各是几行几列的矩阵？答：线 性 分 组 码 的 2 个 码 字 将 组 成 n 维 向 量 空 间 的 一 个 k 维 子 空 间 ，

2、而 线 性空 间 可 由 其 基 底 张 成 ， 因 此 线 性 分 组 码 的 个 码 字 完 全 可 由 k 个 独 立 的向 量 组 成 的 基 底 张 成 。 设 k 个 向 量 为 （ 7.3-2） 将 它 们 写 成 矩 阵 形 式 ： （ 7.3-3） （ n,k） 码 中 的 任 何 码 字 ， 均 可 由 这 组 基 底 的 线 性 组 合 生 成 。 即 C=MG=(mk-1,mk-2,m0)G 式 中 M=(mk-1,mk-2,m0)是 k 个 信 息 元 组 成 的 信 息 组 。 这 就 是 说 ， 每 给 定一 个 信 息 组 ， 通 过 式 （ 7.3-3） 便

3、可 求 得 其 相 应 的 码 字 。 故 称 这 个 由 k个 线 性 无 关 矢 量 组 成 的 基 底 所 构 成 的 kn 阶 矩 阵 G 为 码 的 生 成 矩 阵（ Generator Matrix） 。校 验 矩 阵 H 的 每 一 行 代 表 求 某 一 个 校 验 位 的 线 性 方 程 的 系 数 (n-k)线 性分 组 码 有 r=n-k 个 校 验 元 ， 故 须 有 r 个 独 立 的 线 性 方 程 ， 因 此 H 矩 阵 必由 线 性 无 关 的 r 行 组 成 ， 是 一 个 (n-k)n 阶 矩 阵 ， 一 般 形 式 为一个（n,k）线性分组码生成矩阵有 k

4、 行 n 列校验矩阵有(n-k)行 n 列。8.4 什么样的码成为系统码？系统码的生成矩阵和校验矩阵在形式上有何特点？答：若信息组为不变的形式，称在码字的任意 k 位中出现的码为系统码；一个系统码的生成矩阵 G，其左边 k 行 k 列是一个 k 阶单位方阵，系统码的校验矩阵 H，其右边 r 行 r 列组成一个 r 阶单位方阵。8.5 什么是对偶码？试举例说明之。答：若把（n,k）码的 H 矩阵看成是 (n,r)码的生成矩阵 Gd,而（n,k）码的 G 矩阵就是（n,r ） ，码的校验矩阵 Hd,则称这两种码为互为对偶码。例如课本列举的（7，3）码8.6 试述码的距离和重量的概念。线性分组码的最

5、小距离有何实际意义？答：两个码字之间，对应位取值不同的个数，称为它们之间的汉明距离，简称距离用d(c1,c2)表示。码字中非零码元的个数，称为该码子的汉明重量，简称重量，用 w(c)表示。一个线性分组码的最小距离是衡量码抗干扰能力的重要参数。码的最小距离愈大，其抗干扰能力愈强。8.7 如果要构造一个能纠 2 个错的线性分组码，则其 H 矩阵中至少应保证多少列线性无关？答：4 列 根据定理 8.2 检测 e 个错，则要求码的最小距离 d 大于等于 e+1纠正 t 个错，则要求码的最小距离 d 大于等于 2t+1纠正 t 个错误同时检测 e 个错误，则要求 d 大于等于 t+e+1而根据定理 8.

6、3 （n,k）线性分组码有最小距离为 d 的重要条件是 H 矩阵中任意 d-1 列线性无关所以是 4 列8.8 什么是接收序列 y 的伴随式 s？为什么伴随式 s 只由错误图样 e 决定？ 0,2,1, 0,22,1,2 ,1,1, . .knknn hhhhH= 1001Gd=H= 答：令 其中 y 为接收码字 e 为接收图样，称 s 为接收序列的伴随式。由式可知若 e=0，则 s=0;若 e0,则 s0,因此伴随式 s 只由错误图样 e 决定。8.9 如何构造一个码的标准阵列？标准阵列有哪些性质？答：先把子群中的全部 k2个码字 1c, 2, k置于表的第一行，并把该子群的加法恒等元1e=

7、 c=0(即全零码字放在行的首位) 在余下的 n- 个 n 重中，选择一个 n 重 2e作为第二行得首位元素，意识第二行的元素是 2e和每个码字 ic（i=1,2, k）相加，并把 + ic置于 ic的下面即同一列。第三行再从其余的 n 重 中选择一个 3e作为首位元素，同理将 3e+i置于 i的下面完成第三行。以此类推，一直将 n 重用完为止。如下表：许用码字 1e= c（陪集首）23c k2c禁用码字23en-k22e+3+ cn-k2e+2e+ 3+ cn-k2e+ 32e+ k3+ kcn-k2e+标准阵列的性质有：如果把陪集看成是错误图样，则每一个陪集中具有相同的错误图样。每一个陪集

8、中的 k2个 n 重都有相同的伴随式而不同的陪集具有不同的伴随式。对于同一列的各子集 1, 2 , , k2来说，其中 n-k个 n 重得错误图样虽然不同，但全部对应于同一许用码字。8.10 如何利用标准阵列译码？为什么说用标准阵列译码时，译码错误概率的大小与陪集首的选择有关？答：当输入译码的接收序列为 y 时，经查表总能确定 y 落在标准阵列的第 j 行第 i 列，译码器就能判定发送码字是第 i 列（即子集 i）所对应的许用码字 ic而粗我图样即第 j 行所THys在陪集的陪集首 je用上述方法译码时，译码正确的概率大小与陪集首的选择有关。显然任意选择陪集首不是好的方法。根据最大似然译码准则

9、，重量最轻得错误图样产生的可能性最大，所以应选优先择重量小的 n 重作为陪集首，这样构造的译码表，可使 je+ ic与 i之间的激励最小，从而使译码器以更大的概率正确译码，这就是最小译码距离。8.11 什么是完备码？为什么说汉明码是完备码？答：如果某一（n，k）线性分组码能使n-k2= 0+ 1+nt成立，即错误图样正好等于伴随式数目，则称这种码为完备码。显然，汉明码是 t=1 完备码。8.12 某分组码的校验矩阵为H = 010求：（1） n = ？k= ？该码的码字有多少？（2） 该码的生成矩阵；（3） 矢量 010111 和 100011 是否为码字。解：（1）n=6,k=3,该码有 8

10、 个码字。（2）由校验矩阵可得4c+ 3+ 2=05+ + 1=0c+ 4+ 0=0所以5=4c= 3= 32c= 4+1= 5 + 30c= + 4由此可得生成矩阵为： 0101G（3）经验证，010111 不是码字，100011 是码字。8.13 某二元（n，k）系统线性分组码的全部码字如下00000 01011 10110 11101求：（1） n = ？k= ？（2） 码的生成矩阵 G 和校验矩阵 H。解：（1）n=5，k=2 。根据码字可以得 n=5，又因为总共 4 个码字，说明信息位有 2 位，即 k=2。（2）码的生成矩阵 G= ，校验矩阵 H= 。101 101= G，且 G

11、= : P,根据全部的码字可以得出 P。进而可以得到icimkIG。又 H = : ，从而推出矩阵 H。其中 、 为单位矩阵TPrI kIr8.14 已知一个线性分组码的校验矩阵为H= 1010试求其生成矩阵。当输入信息序列为 1001 1100 1101 时，求编码器输出的码字序列。解：生成矩阵 G= 1001输出的码字序列为：1001100,1100110,1101001。根据 G = : P，H = : 的关系，由 H 矩阵可以写出 G 矩阵。kITrI又由 = G 可以分别得出信息序列为 1001,1100,1101 的码字分别为：icim1001100,1100110,1101001

12、。8.15 设一个（7，4）分组码的生成矩阵为G= 0101求：（1） 该码的全部码字（2） 码的标准序列（3） 码的简化译码表答：(1)信息组 码字0000 00000000001 00011100010 00100110011 00111010100 01001010101 01010110110 01101100111 01110001000 10001111001 10010011010 10101001011 10110101100 11000101101 11011001110 11100011111 1111111（2）标准矩阵列信息组 m 0000 0001 0010 0011

13、 0100 0101 0110 0111许用码字 c 0000000 0001110 0010011 0011101 0100101 0101011 011011001110000000001 0001111 0010010 0011100 0100100 0101010 011011101110010000010 0001100 0010001 0011111 0100111 0101001 011010001110100000100 0001010 0010111 0011001 0100001 0101111 011001001111000001000 0000110 0011011 0

14、010101 0101101 0100011 011111001100000010000 0011110 0000011 0001101 0110101 0111011 01001100101000有单错的n重0100000 0101110 0110011 0111101 0000101 0001011 001011 001100001000000 1001110 1010011 1011101 1100101 1101011 11101101111000信息组 m 1000 1001 1010 1011 1100 1101 1110 1111许用码字 c 1000111 1001001 10

15、10100 1011010 1100010 11011001110001 11111111000110 1001000 1010101 1011011 1100011 11011011110000 11111101000101 1001011 1010110 1011000 1100000 11011101110011 11111011000011 1001101 1010000 1011110 1100110 11010001111001 11110111001111 1000001 1011100 1010010 1101010 11001001110001 11101111010111

16、1011001 1000100 1001010 1110010 11111001100001 11011111100111 1101001 1110100 1111010 1000010 10011001010001 1011111有单错的n重0000111 0001001 0010100 0011010 0100010 01011000110001 0111111（3）译码表伴随式 s 错误图样（陪集首） e000 0000000001 0000001010 0000010100 0000100110 0001000011 0010000101 0100000111 10000008.16

17、构造 8.15 题中（7,4）分组码的对偶码，构造其系统码形式的 G 矩阵和 H 矩阵，并写出全部码字。答：G 矩阵 10101010H码字：信息组 码字000 0000000001 1110001010 1011010011 0101011100 1101100101 0011101110 0110110111 10001118.17 某（5,2）线性分组码的 H 矩阵H = 101求：（1）该码的 G 矩阵（2）该码的标准阵列（3）该码的简化译码表（4）说明该码是否为完备码答：（1）由 H 矩阵的形式可知，该线性分组码为系统码 根据系统码可知 H =P : G = : 、 为单位矩阵rIk

18、ITP10kIr所以可以求出 G = 101（2）根据题意（5,2）的线性分组码可以知道 信息组 m = 然后 根据 c = m G 可10以求出 c = * = 101001所以 根据标准阵列的定义有信息组 m 00 01 10 11许用码字 c 00000 01101 10111 1101000001 01100 10110 1101100010 01111 10101 1100000100 01001 10011 1111001000 00101 11111 10010有单错的n 重 10000 11101 00111 0101000011 01110 10100 11001有两错的 n

19、 重00110 01011 10001 11100有三错的 n 重 00111 01010 10000 11101(3)由标准阵列可以得到错误图样表（陪集首） 与 其伴随式 s = . 根据公式计jejeTH算有 伴随式 s 错误图样（陪集首） e000 00000001 00001010 00010100 00100101 01000111 10000011 00011110 00110（4）不是完备码根据（2） （3）可以知道伴随式数目为 = 8（个） 又由于完备码的概念是使得k-n2的= 成立k-n ti0n.10表示错误个数小于等于 t 的错误图样数 ti0根据（2） （3）可以知道

20、明显 e 的个数大于伴随式的个数 所以不相等 也就是说明改码不是完备码8.18 试构造 GF（2）上的（15,11）汉明码。求出其系统码形式的 H 矩阵和 G 矩阵答：取 r = 4 构造 GF（2）上的（15,11）的汉明码。当 r = 4 时，有 15 个非全 0 的四重，即（0001） （0010） （0100） （1000） （0011）（0101） （0110） （0111） （1001） （1010）（1011） （1100） （1101） （1110） （1111）构成 H 矩阵 10101010H根据 H 矩阵和 G 矩阵的关系以及系统码的概念有H =P : G = : rIkITP101010P、 为单位矩阵kIr所以有 G 矩阵 11000 010100 010010G