当前位置：文档之家 › 信息论与纠错编码题库

信息论与纠错编码题库

  • 格式：doc
  • 大小：285.50 KB
  • 文档页数：10

第八章线性分组码8.1 什么是检错码？什么是纠错码？两者有什么不同？答：能发现错误但不能纠正错误的码称为检错码；不仅能发现错误而且还能纠正错误的码称为纠错码。

8.2 试述分组码的概念，并说明分组码的码率r的意义。

答：分组码是把信息序列以每k个码元分组，即每k个码元组成一个信息组。

n表示码长,k 表示信息位的数目，码率r=k/n，它说明在一个码字中信息为所占的比重。

8.3 什么是码的生成矩阵和校验矩阵？一个（n，k）线性分组码的生产矩阵和校验矩阵各是几行几列的矩阵？答：线性分组码的2个码字将组成n维向量空间的一个k维子空间，而线性空间可由其基底张成，因此线性分组码的个码字完全可由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）便可求得其相应的码字。

故称这个由k 个线性无关矢量组成的基底所构成的k×n阶矩阵G为码的生成矩阵（Generator Matrix）。

校验矩阵H 的每一行代表求某一个校验位的线性方程的系数(n-k)线性分组码有r=n-k 个校验元，故须有r 个独立的线性方程，因此H 矩阵必由线性无关的r 行组成，是一个(n-k)×n 阶矩阵，一般形式为一个（n,k ）线性分组码生成矩阵有k 行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 试述码的距离和重量的概念。

线性分组码的最小距离有何实际意义？ 答：两个码字之间，对应位取值不同的个数，称为它们之间的汉明距离，简称距离用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.3 （n,k ）线性分组码有最小距离为d 的重要条件是H 矩阵中任意d-1列线性无关所以是4列8.8 什么是接收序列y 的伴随式s ？为什么伴随式s 只由错误图样e 决定？ 答：令⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡---------0,2,1,0,22,21,20,12,11,1..................,...k n n k n n k n n n n n h h h h h h h hh ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1101000011010011100101010001Gd=H=TT eH yH s ==其中y 为接收码字e 为接收图样，称s 为接收序列的伴随式。

由式可知若e=0，则s=0;若 e ≠0,则s ≠0,因此伴随式s 只由错误图样e 决定。

8.9 如何构造一个码的标准阵列？标准阵列有哪些性质？ 答：先把子群中的全部k2个码字1c ,2c ,```,k 2c 置于表的第一行，并把该子群的加法恒等元1e =1c =0(即全零码字放在行的首位)在余下的n 2-k 2个n 重中，选择一个n 重2e 作为第二行得首位元素，意识第二行的元素是2e 和每个码字i c （i=1,2,```, k 2）相加，并把2e +i c 置于i c 的下面即同一列。

第三行再从其余的n 重 中选择一个3e 作为首位元素，同理将3e +i c 置于i c 的下面完成第三行。

以此类推，一直将n 重用完为止。

如果把陪集看成是错误图样，则每一个陪集中具有相同的错误图样。

每一个陪集中的k2个n 重都有相同的伴随式而不同的陪集具有不同的伴随式。

对于同一列的各子集1φ,2φ ,… , k 2φ来说，其中n-k 2个n 重得错误图样虽然不同，但全部对应于同一许用码字。

8.10 如何利用标准阵列译码？为什么说用标准阵列译码时，译码错误概率的大小与陪集首的选择有关？答：当输入译码的接收序列为y 时，经查表总能确定y 落在标准阵列的第j 行第i 列，译码器就能判定发送码字是第i 列（即子集i φ）所对应的许用码字i c 而粗我图样即第j 行所在陪集的陪集首je用上述方法译码时，译码正确的概率大小与陪集首的选择有关。

显然任意选择陪集首不是好的方法。

根据最大似然译码准则，重量最轻得错误图样产生的可能性最大，所以应选优先择重量小的n 重作为陪集首，这样构造的译码表，可使j e +i c 与ic 之间的激励最小，从而使译码器以更大的概率正确译码，这就是最小译码距离。

8.11 什么是完备码？为什么说汉明码是完备码？ 答：如果某一（n ，k ）线性分组码能使n-k 2=n 0⎛⎫ ⎪⎝⎭+n 1⎛⎫ ⎪⎝⎭+…+n t ⎛⎫ ⎪⎝⎭成立，即错误图样正好等于伴随式数目，则称这种码为完备码。

显然，汉明码是t=1完备码。

8.12 某分组码的校验矩阵为H =⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡000011010101001110 求：（1） n = ？k= ？该码的码字有多少？（2） 该码的生成矩阵；（3） 矢量010111和100011是否为码字。

解：（1）n=6,k=3,该码有8个码字。

（2）由校验矩阵可得 4c +3c +2c =05c +3c +1c =0 5c +4c +0c =0 所以5c =5c 4c = 4c 3c = 3c 2c = 4c +3c 1c =5c +3c0c =5c +4c由此可得生成矩阵为：⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=011100101010110001G（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=⎥⎦⎤⎢⎣⎡1101001101，校验矩阵H=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡100100101100101。

i c =i m ·G ，且G = [k I : P ],根据全部的码字可以得出P 。

进而可以得到G 。

又H =[TP : r I ] ，从而推出矩阵H 。

其中k I 、r I 为单位矩阵8.14 已知一个线性分组码的校验矩阵为H=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡100101101011010011110 试求其生成矩阵。

当输入信息序列为 1001 1100 1101时，求编码器输出的码字序列。

解：生成矩阵G=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1111000011010010100101100001输出的码字序列为：1001100,1100110,1101001。

根据G = [k I : P ]，H =[TP : r I ]的关系，由H 矩阵可以写出G 矩阵。

又由i c =i m ·G 可以分别得出信息序列为1001,1100,1101的码字分别为： 1001100,1100110,1101001。

8.15 设一个（7，4）分组码的生成矩阵为G=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0111000110010010100101110001 求：（1） 该码的全部码字 （2） 码的标准序列 （3） 码的简化译码表 答： (1)（3）译码表8.16 构造8.15题中（7,4）分组码的对偶码，构造其系统码形式的G 矩阵和H 矩阵，并写出全部码字。

答： G 矩阵⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=100011101011010011011G ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=1000110010001100101110001101H码字：8.17 某（5,2）线性分组码的H 矩阵H = ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡100110100100111 求：（1）该码的G 矩阵（2）该码的标准阵列 （3）该码的简化译码表 （4）说明该码是否为完备码 答：（1）由H 矩阵的形式可知，该线性分组码为系统码 根据系统码可知H =[P : r I ] G = [k I : TP ] ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=110111P k I 、r I 为单位矩阵所以可以求出 G = ⎥⎦⎤⎢⎣⎡1011011101 （2）根据题意（5,2）的线性分组码可以知道 信息组 m = ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡11011000 然后 根据c = m G 可以求出c = ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡11011000 * ⎥⎦⎤⎢⎣⎡1011011101 = ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0111111011011000000 所以(3)由标准阵列可以得到错误图样表（陪集首）j e 与 其伴随式 s = j e . TH 根据公式计算有（4根据（2）（3）可以知道伴随式数目为 k-n 2= 8（个） 又由于完备码的概念是使得k-n 2∑=⎪⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛++⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛≥t i i t 0n n ...1n 0n 的= 成立∑=⎪⎪⎭⎫ ⎝⎛ti i 0n 表示错误个数小于等于t 的错误图样数 根据（2）（3）可以知道 明显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 矩阵⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=100010101011011010011001101101001011110001110000111111110000H 根据H 矩阵和G 矩阵的关系以及系统码的概念有 H =[P : r I ] G = [k I : TP ]⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=10101011011110011011011111000111011111110000P k I 、r I 为单位矩阵所以有G 矩阵⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=111110000000000011101000000000101100100000000001100010000000110100001000000011100000100000100100000010000111000000001000011000000000100101000000000010110000000000001G。

合集下载

信息论与编码题库及答案

信息论与编码题库及答案

信息论与编码题库及答案信息论是一门关于信息传输和处理的学科，主要研究信息的传输、存储与处理，以及在信息传输过程中可能产生的各种噪声和干扰。

信息论在近年来得到了广泛的应用，尤其在计算机科学、通信工程、数据处理以及加密技术等领域中得到了广泛应用。

作为信息处理学科的一个分支，编码学是信息论中重要的研究领域之一，主要研究在信息传输的过程中如何将信息进行编码，并在保证高可靠性的同时减少信息传输的开销。

现代编码学研究所涉及到的内容非常广泛，包括错误检测、纠正编码、信息压缩以及密码学等领域。

为了帮助广大信息与通信工程学习者更好地掌握编码理论及其应用，以下总结了一些编码学的题库及答案，供大家参考。

一、错误检测编码1. 什么是奇偶校验码？答：奇偶校验码是一种简单的错误检测编码方式，它采用了消息的一位奇偶性作为编码方式。

具体而言，对于一组位数固定的二进制数，在其中加入一个附加位，使得这组数的位数为偶数。

然后将这些二进制数按照某种规则排列，例如相邻的两位组成一组，计算每组中1的个数。

如果某组中1的个数是偶数，则附加位赋值为0，否则为1。

这样，如果在传输的过程中数据出现了单一位的错误，则会被检测出来。

2. 什么是海明编码？答：海明编码是一种通过添加校验位来实现错误检测和纠正的编码方式。

在海明编码中，校验位的数目为2的k次幂个，其中k 表示数据位中最大1的位置数。

具体而言，将原始信息看作一组二进制数，再将这些数按照某种规则排列，然后按照一定的算法计算出每个校验位的值，并将这些值添加到原始信息中。

在传输的过程中，如果发现了错误的位，则可以通过一系列错误检测和纠正的操作来确定和修复出错的信息位。

二、信息压缩编码1. 什么是霍夫曼编码？答：霍夫曼编码是一种基于无损数据压缩的编码方式，它的特点是可以将原始信息中出现最频繁的字符用最短的二进制码来表示，同时将出现次数较少的字符用较长的二进制码来表示。

具体来说，霍夫曼编码首先对原始信息中的字符进行统计，确定每个字符出现的频率。

信息论编码与纠错课后作业答案

信息论编码与纠错课后作业答案

信息论第一章作业参考答案1.3 同时掷一对均匀的骰子，要得知面朝上点数之和，描述这一信源的数学模型。

解：设该信源符号集合为X23456789101112123456543213636363636363636363636X P ⎡⎤⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦⎣⎦1.4 解：根据符号转移概率状态空间为S={00（S 0），01（S 1），02 （S 2），10（S 3），11（S 4），12（S 5），20（S 6），21（S 7），22（S 8）}可写出转移概率矩阵12000001200000121200000120000012121212p p p p pp ppp p p p P p p p ppp p ppp ppppp -⎡⎤⎢⎥-⎢⎥⎢⎥-⎢⎥-⎢⎥⎢⎥=-⎢⎥-⎢⎥⎢⎥-⎢⎥-⎢⎥⎢⎥-⎣⎦状态转移图（略）由状态转移图列方程组，设各状态的转移概率分别为,0~8i p i =00361036231475414762587825881(12)()()()(12)()()(12)()1i i p p p p p p p p p p pp p p p p p p p p p p p p p p p p p p p p p p =⎧=-++⎪⎪=++=⎪=++=⎪⎪=-++⎨⎪=++=⎪⎪=-++⎪⎪=∑⎩ 解得0481235671233p p p p p p p p p p p -⎧===⎪⎪⎨⎪======⎪⎩1.5 解：（1）求平稳后各状态出现的概率 转移概率矩阵为01434121414100P ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦由P 列方程组12321231212312114431441p p p p p p p p p p p p ⎧=+⎪⎪⎪=+⎪⎨⎪=+⎪⎪⎪++=⎩ 解得平稳分布为111613213513p p p ⎧=⎪⎪⎪=⎨⎪⎪=⎪⎩ （2）若在初始时刻0l =时处于状态S 1，求2l =时刻，21x a =的概率S3S 1S 1l l =1l =221011137{}14248p x a S s ⇒===⨯+⨯=或由二步转移概率矩阵(2)111616 337 81616713 844P P P ⎡⎤⎢⎥⎢⎥⎢⎥=⋅=⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦可得（4）求稳态下字母序列31212a a a a a出现的概率511151416p=⨯⨯⨯⨯=平稳分布P3转移概率1.6 解：信源符号等概率分布，故信源熵为1()12H=bit，9500个符号的信息量为9500bit。

信息论与纠错编码 (孙丽华 著) 电子工业出版社_khdaw

信息论与纠错编码 (孙丽华 著) 电子工业出版社_khdaw


w .c
1−δ − ε (1 − ε ) / 2
− H 2 (ε )
om
]
− H 2 (ε )
（2） I(1;1) = log
I(1;0) = log
δ (1 − ε ) / 2
da
[
4.14 （1） C = ln 1 + 2e
kh
（2） C (ε = 0) = ln 1 + 2e
[
] = ln[1 + 2e ]
x5
11
21
20
hd
12 10
（4）Huffman 编码，D＝4
消息 码字
.k
33 32
x1
2
x2
0
x3
x4
x5
31
3.21 （1）D=2
消息 码字
w
x1
x2
x3
x4
011
x5
001
aw .c
x6 x7 x8
110 1110 1111
答
x6
x7
x8
221
220
x6
x7
11
x8
10
30
x6
000
x7
1101
1
若侵犯了您的版权利益，敬请来信通知我们！ ℡
kh
da
（2）H(X) =2.36 (Bit/符号)
w
2.11（1）H(X) = log6 = 2.58 (Bit/符号)
.c
1 = 225.6( Bit ) 52! 52! （2） I ( xi ) = − log q ( xi ) = log 13 4 13!39! 1 （3） H (U ) = － log = log 52 = log 4 × 3 = 2 log 13 = 7.4( Bit / 符号) 52 1 （4） H ( X ) − log = log 13 = 3.7( Bit / 符号) 13
信息论与纠错编码课后练习题含答案

信息论与纠错编码课后练习题含答案

信息论与纠错编码课后练习题含答案前言信息论与纠错编码是计算机科学与通信工程中非常重要的领域。

本文档将介绍该领域中一些常见的练习题，并且配有答案供参考。

第一部分：信息论题目一假设在信道中有两个符号a和b，其发生概率分别为P(a)和P(b)。

则符号a和b在信道中的平均传输信息量为多少？答案一符号a和b分别传输的信息量为 $I(a)=-\\log_2P(a)$ 和 $I(b)=-\\log_2P(b)$。

因此，符号a和b在信道中的平均传输信息量为：$$I_{avg}=\\frac{1}{2}(I(a)+I(b))=\\frac{1}{2}(-\\log_2P(a)-\\log_2P(b))=-\\frac{1}{2}\\log_2(P(a)P(b))$$题目二以上一题中的符号为例，若P(a)=0.2，P(b)=0.8，则符号b传输的信息量是符号a的多少倍？答案二符号a和b的信息量为：$$I(a)=-\\log_2P(a)=-\\log_2(0.2)=2.322$$$$I(b)=-\\log_2P(b)=-\\log_2(0.8)=0.321$$因此，符号b传输的信息量为符号a的 $\\frac{0.321}{2.322}=0.138$ 倍。

第二部分：纠错编码题目三对于一个二元码，其生成矩阵为$G=\\begin{bmatrix}1&0&1\\\\0&1&1\\end{bmatrix}$。

请问该码的最小汉明距离是多少？答案三对于二元码，最小汉明距离等于最小权值。

该码的所有码字是：$$\\begin{bmatrix}1&0&0\\end{bmatrix}，\\begin{bmatrix}0&1&0\\end{bmatrix}，\\begin{bmatrix}1&1&0\\end{bmatrix}，\\begin{bmatrix}0&0&1\\end{bmatrix}，\\begin{bmatrix}1&0&1\\end{bmatrix}，\\begin{bmatrix}0&1&1\\end{bmatrix}，\\begin{bmatrix}1&1&1\\end{bmatrix}，\\begin{bmatrix}0&0&0\\end{bmatrix}$$因此，该码的最小汉明距离是d min=1。