信息论与编码学考试试题.docVIP

信息的概念 信息：是指各个事物运动的状态及状态变化的方式。（具有不确定性，任何已经确定的事物都不含有信息） 相对熵的概念及计算 连续信源可以假设是一个不可数的无限多个幅度值的信源，需要无限多个二进制数来表示，因此它的熵为无穷大。连续信源的熵具有相对性，有时也叫相对熵。 连续信源熵（相对熵）：Hc(X)= 信源熵的概念及计算 信源中各个符号不确定度的数学期望叫做信源熵 H(X)=E[I(X)]= 单位：比特/符号 其中：0≤ ≤1，当信源中只含一个符号x时，必定有=1. 分组码 将信源消息分成若干组，即符号序列Xi，Xi=（X1，X2...Xl...XL),序列中的每个符号取自于符号集A,Xl∈{a1,a2,...,ai,...,an}.而每个符号序列Xi 依照固定的码表映射成一个码字Yi，这样的码称为分组码，也叫快码。只有分组码才有对应的码表，而非分组码中不存在。 唯一可译码 任意有限长的码元序列，只能被唯一的分割成一个个的码字，便称为唯一可译码。 唯一可译码分为：非即时码和即时码 唯一可译码存在的充分必要条件的概念及应用 用树的概念可导出唯一可译码存在的充分必要条件，即各码字的长度Ki应符合克劳夫特不等式：≤1 （m是进制数，n是信源符号数） 疑义度的概念及计算 条件熵H(X/Y)可以看做是信道上的干扰和噪声所造成的对信源符号x的不确定度，故又称为疑义度或损失熵。 H(X/Y)=E[I(xi/yi)]= = 散布度或噪声熵 H(Y/X)=E[I(yi/xi)]= = 恒重码的概念 如果码集的所有码字都具有相同的重量，这种码就叫做恒重码 平均自信息量的概念及计算 平均自信息量是消除信源不确定度时所需要的信息的量度，即收到一个信源符号，全部解除了这个符号的不确定度。和信源熵在数值上相等，含义不同。 平均互信息的概念及计算 互信息量I(xi;yi)在联合概率空间P（XY）上的统计平均值被称为平均互信息量，用I（X;Y）表示。 I（X;Y）==单位：比特/消息 平均互信息量克服了互信息量的随机性，成为一个确定的量，因此可作为信道中流通信息量的整体测度。 密码体制中的保密性 保密性要求密码分析员无法从截获的密文中求出明文。包括两个要求： 即使截获了一段密文C，甚至知道了与它对应的明文M,密码分析员要从中系统地求出解密变换任然是计算上不可能的。 密码分析员要由截获的密文C系统地求出明文M是计算上不可能的。 无论被截获的密文消息的数量和长度是多少，为了实现保密性，这两个要求都必须成立。保密性只要求对变换Dk(解密密钥)加以保密，只要不影响Dk的保密性，变换EK可以公布于众。 DES的概念 DES的明文长度是64bit，密钥长度是56bit，加密后的密文长度也是64bit，脱密过程则相反，它首先按照分组进行脱密，然后去除填充信息并进行连接。 定长编码定理和应用 定长编码定理：由L个符号组成的、每个符号的熵为HL（X）的无记忆平稳信源符号序列X1X2...Xl...XL，可用KL个符号 Y1，Y2，...,Yk...(每个符号有m种可能值）进行定长编码。 对于任意ε0,δ0,只要+ε,则当L足够大时，必使译码差错小于δ；反之，当-2ε，译码差错一定是有限值，而当L足够大时，译码几乎必定出错。 计算无记忆信源信息量 自信息量的概念及计算 自信息量为一个随机事件出现概率对数的负数。即 I(xi)=-logp(xi) 单位和所用的对数底有关，底数通常为2 以2为底时，单位是比特（bit） 以e为底时，单位是奈特（nat） 以10为底时，单位是笛特（det） 转换关系为：1 nat=log2e ≈ 1.433bit ; 1det=log210 ≈3.322bit 构造霍夫曼码 霍夫曼编码的步骤如下： ⑴ 将n个信源消息符号按其出现的概率大小依次排列p(x1)≥p(x2)≥…≥ p(xn) ⑵取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。 ⑶ 对重排后的两个概率最小符号重复步骤⑵的过程。 ⑷不断继续上述过程，直到最后两个符号配以0和1为止。 ⑸ 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。 码组的平均长度,信息传输速率的计算 平均码长表示编码后的每个信源符号平均所需的码元个数： = 单位：码元/信源符号， Ki为码字长度（i=1,2,...,q) 信息传输率R是指编码后每个码元载荷的信息量： R= 单位：比特/码元 或 比特/码符号 游程编码的概念及应用 游程编码，指数字