试题及答案

西安科技大学研究生考试试卷

题号 1 2 3 分 数 阅卷人 学 号 ______ ________ 研究生姓名 ______ ________ 班 级 ______ ________ 考 试 科 目 信息论与编码 考 试 日 期 ________ ______ 课 程 学 时 _______ 54__ 开（闭）卷 ________开卷__

4 5 6 7 8 9

10 总分 注 意 事 项 1、考生必须遵守考场纪律 2、答题必须写清楚题号 3、字迹要清楚，保持卷面整洁 4、试题随试卷一起交回（试题写在黑板上时，答题时应抄写题目） 信息论与编码考试蓝图

填空 名词解释 画图 简答 计算 小计 7 2分，信息的概念 Ch1 5分，通信系统模型 4分，平均Ch2 互信息的特性 Ch3 4分，离散平稳信源的概念 10分，计算平均信息率 10分，计算一阶马尔可夫信源的熵 10分，计算信道容量 11 14 5分，波形Ch4 信道的分类 Ch5 14 4分，线性分组码的概念 4分，平均失真度的概念 12 1分，码的Ch6 剩余度 Ch7 Ch8 小计 16 6分，信源序8分，霍夫列与典型序曼编码步列的关系 骤 8分，有噪 信道编码定理 7分，率失 真信源编码定理 6分，相关信7分，网络源的多址接信道的划入信道模型 分 12 30 14 16 11 30 13 100 信息论与编码试题及答案

一、 填空（161分）

（1） 信息是事物 运动状态 或 存在方式 的不确定性的描述。

（2） 通信系统模型主要分成 信息源（简称信源）、编码器、信道、译码器 和 信

宿 五个部分。

（3） 平均互信息的特性有 非负性、极值性、交互性 和 凸状性。

（4） 按噪声的统计特性，波形信道可分为 高斯信道、白噪声信道、高斯白噪

声信道 和有色噪声信道。

（5） 为了衡量各种编码与最佳码的差距，定义码的剩余度为：11Hr(S)L

二、 名词解释（34分）

（1） 离散平稳信源：各维联合概率分布均与时间起点无关的完全平稳主源。 （2） 线性分组码：若C是V（n,q）的n重k维子空间V（k,q），则称C为q

元(n,k)线性分组码，简称线性码。

（3） 平均失真度：规定了单个符号失真度d(ui,vj)后，传输一个符号引起的平

均失真，即信源平均失真度DE[d(ui,vj)]E[d(u,v)]。其中E[]是对U和V的联合空间求平均。

三、 画图题（26分）

（1） 画出信源序列和典型序列之间的关系

S信源中信源序列SN N非典型序列集GN 典型序列集GN约有个2NH(S)

（2） 画出相关信源的多

n址接入信道模型

s1S 相关信源 P(s1s2) n1x1(s1)X1 编辑器1 多址接入yYn 信道MAC p(yx1x2) ˆ1(y)S1ns译码器 ˆ2(y)S2n ss2S2 编辑器2 nx2(s2)X2 n 相关信源的多址接入信道模型

四、 简答题（30分，1、4为7分，2、3为8分）

（1） 简述网络信道划分的几种典型情况；（7分）

① 多址接入信道：多个不同信源的信息经过几个编码器编码后，送入同一信道传送。收端仅仅由一个译码器译出不同信源的信息，送给不同的信宿。 ② 广播信道：多个信源的信息经过一个公用的编码器后，送入信道，而信道输出通过不同的译码器译码后送给不同信宿。

③ 中继信道：一对用户之间经过多种途径中转所进行的单向信道。

④ 串扰信道：它有两个发送端和两个接收端，它们通过一个公共信道传送信息。 ⑤ 双向信道：它有两个发送端和两个接收端，且是双向信道。 ⑥ 多用户通信网：由多个相关信源和信宿组成的多信道的通信。 ⑦ 具有反馈的信道：系统的译码器输出有部分信息反馈传送到编码器。 （2） 简述霍夫曼码的编码步骤：（8分） 霍夫曼码（Huffman）的编码步骤： ①

将q个信源符号按概率分布p(si)的大小，以递减次序排列起来，设

p1p2p3pq

② 用0和1码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个符号，从而得到只包含q-1个符号的新信源，称为S信源的缩减信源S1。

③

把缩减信源S1的符号仍按概率大小以递减次序排列，再将其最后二个概率最小的符号合并成一个符号，并分别用0和1码符号表示，这样又形成了q-2个符号的缩减信源S2。

④ 依次继续下 ，直至信源最后只剩两个符号为止。将这最后两个信源符号分别用0和1码符号表示。然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得对应的码字。

（3） 简述有噪信道编码定理：（8分）

设离散无记忆信道[X,P(yx),Y]，P(yx)为信道传递概率，其信道容量为C。当信息传输率RC时，只要码长n足够长，总可以在输入Xn符号集中找到

M(2nR)个码字组成的一组码(2nR,n)和相应的译码规则，使译码的错误概率任

意小(PE0)。

（4） 率失真信源编码定理（7分）

信源的信息率失真函数为R（D），并有有限的失真测度，若RR(D)则码长n足够长，一定存在一种信源编码，码字个数M2nR，而码的平均失真度D。若RR(D)，这种码不存在。

五、 计算题（310分）

（1） 为了传输一个由字母ABCDEFGH组成的符号集，把每个字母编码成三个二

元码脉冲序列，即A：000，B：001，C：010，D：011，E：100，F：101，G：110，H：111。每个二元码脉冲宽度为5ms.

1) 不同字母等概出现时，计算传输的平均信息率。 2) 若

PA14每个字

6母出现的

16概

1率分别为

,PBPCPD1,PEPFPGPH，试计算传输的平均信息速率。

B18H18AX解：1）不同字母等概率出现时，符号集的概率空间为1P(a)i8

每个字母信息量

Hlog283bit/符号

现在用三个二元脉冲代表一个字母，每个二元码脉冲宽度为5ms，则每个字

5，s母占用t31m一秒内可以传输的字母个数为：n1t2003bit/s66.7字母/s

得传输的平均信息速率：RnH(X)200bit/s

2）字母出现概率不同时，根据题意其概率空间为

ABCDEFGH8X (ai)1 111111P11P(a)i1i466616161616得此时每个字母含有的平均信息量是：

8H(X)P(ai)logP(ai)i114log4316log64116log16

2.79bit/符号同理1），计算得传输的平均信息速率为：

RnH(X)186bit/s

（2）设有一信源，，它产生0、1序列的消息，即信源X0,1，设其出现的概率分别为P(0)0.P3,(1)。假设消息前后有关联，其依赖关系为

P(11)0.9,P(01)0.1,P(10)0.2,P(00)0.8，求此一阶马尔可夫信源的熵H2。

解：由给出的依赖关系可知，消息满足一阶马尔可夫信源的定义，此一阶马尔可夫信源为

a10,a21XP(ak2ak1)2

k21P(ak2ak1)1,k1,k21,2其状态集E=A=a10,a21。从给出的依赖关系可以画出其状态转移图，如下

101图示，并从图中可得状态的一步转移矩阵P0.90.1

00.20.80.2 0.9 0 0.8 1 0.1

此马尔可夫链是时齐的、状态数有限，且是不可约闭集。所以状态的极限概率存在，其满足

Q(1)Q(1)TPQ(0)Q(0)

Q(0)Q(1)1Q(1)0.9即，Q(0)0.10.2Q(1) 0.8Q(0)Q(1)0.9Q(1)0.2Q(0)Q(0)0.1Q(1)0.8Q(0) Q(0)Q(1)1由此可得，Q(0)13,Q(1)23

此一阶马尔可夫信源的熵为：

2HH2Q(E)H(Xii1Ei)Q(0)0.2log0.20.8log0.8Q(1)0.9log0.90.1log0.11313H(0.2,0.8)0.7222323

H(0.9,0.1)0.4690.553bit/符号（3）在有扰离散信道上传输符号0和1，在传输过程中每100个符号发生一个错误，已知P(0)P(1)12，信源每秒内发出1000个符号，求此信道的信道容量。

解：由题意可知该二元信道的转移概率矩阵为：

0.99P0.010.01 为一个0.99BSC信道

所以由BSC信道的信道容量计算公式得到：

2ClogsH(P)log2pilogi11pi0.92bit/符号

Ct1tC1000C920bit/s

实验一 信道容量

一、实验目的：

（1） （2） （3）

进一步熟悉信道容量的迭代算法； 学习如何将复杂的公式转化为程序；

掌握Matlab语言数值计算程序的设计和调试技术。

二、实验原理与步骤：

为了说明迭代计算的基本方法,先让我们重写一下 X ,Y 的平均互信息公式,为计算方便公式中的对数取自然对数。

I(X;Y)p(yjxi)ijp(xi)p(yjxi)lnip(xi)p(yj) （1）

求信道容量 C就是在p(xi) 的约束下 ,求I(X;Y) 的极大值。首先引入反条件概率,即q(xiyj)p(xi)p(yjxi)ip(xi)p(yjxi) （2）

这样，（2）式可写成I(X;Y)ijp(xi)p(yjxi)lnq(xiyj)p(xi) （3）

迭代算法的要点是,当信道固定(即p(yjxi)固定) 时 ,把 I(X ; Y) 看成p(xi) 和

q(xiyj)

的函数 ,用(3) 进行信道容量计算的迭代。每一次迭代由两步组成(变量

的上标为迭代次序) :

(1) 将p(n)(xi) 固定 , 在约束q(xiyj)1的条件下变动q(xiyj) ,得到 I( X; Y)

i(n)(n)的极大值,记为I(X;Y)C(p(n)(xi);qx(iyj)Cn(n, );此时q(xiyj) 满足(2)

式;重写为q(n)(xiyj)p(n)(xi)p(yjxi)(xi)p(yjxi)p(n) （4）

(2) 将q(n)(xiyj) 固定 ,在约束p(xi)1的条件下变动p(xi) ,得到 I(X ; Y)

i(n的极大值 ,记为I(XY;)Cp(1)xi(q)x;iyj(Cn))nn();(此1时,满)足

p(yjxi)lnqp(n1)(n)(xiyj)(xi)ieje p(yjxi)lnqj(n)(xiyj) （5）

信道容量迭代算法法流程图如下：

P(ai)=P(ai)(0) aiexp[P(bj|ai)lnjP(bj|ai)](i1,2,...,r)|ai)P(a)P(biijC(n1,n)lnP(ai)aiiC'(n1,n)ln(maxai)iY C(n1,n)C'(n1,n)N CC(n1,n) P(ai)(i1,2,...,r)P(ai)aiP(a)aiii 结束 (4) 与 (5) 是迭代的基本公式。先选取一组均匀分布,由 (4) 计算

q(n)p(n)(xi)(n1)p的初始值,通常选取

(xi)(xiyj); 再将此值代入 (5) 计算

(n1),依此反复计

算下去。每次迭代都要利用(3) 计算 I(X; Y) 的值。可以设置门限值,当相邻的两次计算 I(X ; Y) 的误差小于门限值时,就结束迭代过程,此时 I( X; Y) 的值就是信道容量 C。

三、程序代码：

%信道容量C计算的Matlab程序

clc;clear all;

N = input('输入信源符号X的个数N=');

M = input('输出信源符号Y的个数M=');

p_yx=zeros(N,M); %程序设计需要信道矩阵初始化为零 fprintf('输入信道矩阵概率\\n') for i=1:N

for j=1:M

p_yx(i,j)=input('p_yx=');%输入信道矩阵概率 if p_yx(i)<0

error('不符合概率分布') end end end

for i=1:N %各行概率累加求和 s(i)=0; for j=1:M

s(i)=s(i)+p_yx(i,j); end end

for i=1:N %判断是否符合概率分布 if (s(i)<=0.999999||s(i)>=1.000001) error('不符合概率分布') end end

b=input('输入迭代精度：');%输入迭代精度 for i=1:N

p(i)=1.0/N; %取初始概率为均匀分布 end

for j=1:M %计算q(j) q(j)=0; for i=1:N

q(j)=q(j)+p(i)*p_yx(i,j); end

end

for i=1:N %计算a(i) d(i)=0; for j=1:M

if(p_yx(i,j)==0) d(i)=d(i)+0; else

d(i)=d(i)+p_yx(i,j)*log(p_yx(i,j)/q(j)); end end

a(i)=exp(d(i)); end u=0;

for i=1:N %计算u u=u+p(i)*a(i); end

IL=log2(u); %计算IL

IU=log2(max(a));%计算IU n=1;

while((IU-IL)>=b) %迭代计算 for i=1:N

p(i)=p(i)*a(i)/u; %重新赋值p(i) end

for j=1:M %计算q(j) q(j)=0; for i=1:N

q(j)=q(j)+p(i)*p_yx(i,j); end end

for i=1:N %计算a(i) d(i)=0; for j=1:M

if(p_yx(i,j)==0) d(i)=d(i)+0; else

d(i)=d(i)+p_yx(i,j)*log(p_yx(i,j)/q(j)); end end

a(i)=exp(d(i)); end u=0;

for i=1:N %计算u u=u+p(i)*a(i); end

IL=log2(u); %计算IL

IU=log2(max(a));%计算IU n=n+1; end

fprintf('信道矩阵为：\\n'); disp(p_yx);

fprintf('迭代次数n=%d\\n',n);

fprintf('信道容量C=%f比特/符号',IL);

运行结果：

输入信源符号X的个数N=2 输出信源符号Y的个数M=4 输入信道矩阵概率

p_yx=0.5 p_yx=0.25 p_yx=0.125 p_yx=0.125 p_yx=0.25 p_yx=0.5 p_yx=0.125 p_yx=0.125

输入迭代精度：0.0001 信道矩阵为：

0.5000 0.2500 0.1250 0.1250 0.2500 0.5000 0.1250 0.1250 迭代次数n=1

信道容量C=0.061278比特/符号>> 输入信源符号X的个数N=3 输出信源符号Y的个数M=4 输入信道矩阵概率 p_yx=0.5 p_yx=0.25 p_yx=0.1 p_yx=0.15 p_yx=0.23 p_yx=0.4 p_yx=0.27 p_yx=0.1 p_yx=0.19 p_yx=0.21 p_yx=0.6 p_yx=0

输入迭代精度：0.00001 信道矩阵为：

0.5000 0.2500 0.1000 0.1500 0.2300 0.4000 0.2700 0.1000 0.1900 0.2100 0.6000 0 迭代次数n=85

信道容量C=0.271258比特/符号>>

四、结果分析：

从以上程序的运行结果可以看出，信道容量的大小与迭代的次数是直接相关的，迭代算法求信道容量时，迭代的次数越多，信道容量越大。

实验二 信源编码

一、实验目的：

（1） （2） （3）

进一步了解信源编码及其原理； 学习霍夫曼码的原理及编码步骤；

学习运用matlab编写霍夫曼码编码的程序。

二、实验原理与步骤：

1）霍夫曼码具有以下三个特点：

（1）

霍夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，即

（2） （3） （4）

pjpk，有

ljlk，而且短码得到充分利用。

每次缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同，（二元编码情况）。

每次缩减信源的最长两个码字有相同的码长。 这三个特点保证了所得的霍夫曼码一定是最佳码。

2）霍夫曼码（Huffman）的编码步骤：

（1）

将q个信源符号按概率分布

p1p2p3pqp(si)的大小，以递减次序排列起来，设

（2） 用0和1码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个符号，从而得到只包含q-1个符号的新信源，称为S信源的缩减信源

S1。

（3） 把缩减信源

S1的符号仍按概率大小以递减次序排列，再将其最后二个

概率最小的符号合并成一个符号，并分别用0和1码符号表示，这样又形成了q-2个符号的缩减信源

（4）

S2。

依次继续下 ，直至信源最后只剩两个符号为止。将这最后两个信源符

号分别用0和1码符号表示。然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得对应的码字。

三、程序代码：

function [code, L] = huffman(P) P = [8 7 6 5 4 3 2 1] P = P / (sum(P) + ~sum(P)); Psave = P;

n = length(P);

P = [P zeros(1,n - 1) + 2]; code = zeros((n * 2) - 2, 1) - 1; tree = zeros(n-1, 3);

% Build Binary Tree for Huffman Code for i = 1:n-1,

[index1, index2] = findmin2(P); tree(i, 1) = P(index1) + P(index2); P(n + i) = tree(i, 1); tree(i, 2) = index1; tree(i, 3) = index2; P(index1) = 2; P(index2) = 2; end tree

% Walk back through the Binary Tree to determine code code(tree(n-1,2),1) = 0; code(tree(n-1,3),1) = 1; codelen = 1; for i = n-2:-1:1,

tempcode = code(i + n,find(code(i + n,:) > -1)); tlen = length(tempcode); [row, col] = size(code);

while col < tlen + 1, % add to the code length as necessary code = [code (zeros((n * 2) - 2, 1) - 1)]; codelen = codelen + 1; col = col + 1; end

code(tree(i,2), 1:tlen) = tempcode; code(tree(i,2), tlen + 1) = 0; code(tree(i,3), 1:tlen) = tempcode;

code(tree(i,3), tlen + 1) = 1; end

code = code(1:n, :)

% Calculate L L = 0; for i=1:n,

L = L + (Psave(i) * length(find(code(i,:) > -1))); end

% FINDMIN2.M - Find the smallest two probabilities. %

% ee740 w98 - J. Schamus

function [index1, index2] = findmin2(P) min1 = 3; min2 = 3; n = length(P); for i = 1:n, if P(i) < min1, index1 = i; min1 = P(i); end end

P(index1) = 2; for i = 1:n, if P(i) < min2, index2 = i; min2 = P(i); end end

运行结果：

P =

8 7 6 5 4 3 2 1

tree =

0.0833 8.0000 7.0000

0.1667 0.2500 0.3333 0.4167

6.0000 9.0000 5.0000 4.0000 3.0000 10.0000 2.0000 1.0000

0.5833 11.0000 12.0000 1.0000 13.0000 14.0000 code =

0 1 -1 -1 -1 0 0 -1 -1 -1 1 1 0 -1 -1 1 0 1 -1 -1 1 0 0 -1 -1 1 1 1 0 -1 1 1 1 1 1 1 1 1 1 0

ans =

0 1 -1 -1 -1 0 0 -1 -1 -1 1 1 0 -1 -1 1 0 1 -1 -1 1 0 0 -1 -1 1 1 1 0 -1 1 1 1 1 1 1 1 1 1 0

四、结果分析：

从以上结果分析及我们所学其它编码方法的学习知道，霍夫曼码是一种最

佳的逐个符号的编码方法。

实验三 信道编码

一、实验目的：

（1） （2） （3）

进一步了解信道编码的原理；

掌握卷积码的编码的特性、产生原理及方法； 掌握用matlab语言进行卷积码的编码。

二、实验原理与步骤：

1）理论基础

在分组码中，每k个信息比特的序列均以某种固定的方式映射为一个n信道输入的序列，但是与前面的信息比特无关。在卷积码中，每k0个信息比特序列映射为一个长为n0的信道输入序列，但是这个信道输入序列不仅取决于最当前的

k0个信息比特，而且还与该编码器的前(L1)k0个输入序列有关。因此，这种编

码器有一种有限状态机的结构，在其中的每一时刻，输出序列不但与输入序列有关，而且与编码器的状态有关，这个状态是编码器的前(L1)k0个输入序列决定的。下图给出了k02,n03和L4的一种卷积码的方框图。

k02 n03 通常，用卷积码的生成序列来定义卷积码，记为g1,g2gn。一旦给定了生

成序列，卷积码就被惟一确定了。

2）实验步骤：

当信息序列为1 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 1时，由上图的卷积码编码器可求出其输出序列。该信息的长度是17，它不是k02的倍数。因此，现在补一个额外的0就足够了，这样长度即为18。于是就有了下面的信息序列：

1 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 1 0。

0010100100000001 现在，因为有G10000001可得n03和L4，因此输出序列的长度为1841336 2为了确保编码器从全0状态开始，并且回到全0状态，要求在输入序列的起始和末尾都添加(L1)k0个0。因此，上述序列就变为

0 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 1 ，利用函数cnv_encd，求得输出序列。

三、程序代码：

主程序：

k0=2;

g=[0 0 1 0 1 0 0 1;0 0 0 0 0 0 0 1;1 0 0 0 0 0 0 1]; input=[1 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 1]; output=cnv_encd(g, k0,input)

子程序：

function output=cnv_encd(g,k0,input) if rem(length(input),k0) > 0

input=[input,zeros(size(1:k0-rem(length(input),k0)))]; end

n=length(input)/k0;

if rem(size(g,2),k0) > 0 %判断g的大小 error('Error, g is not of the right size.') end

l=size(g,2)/k0;

n0=size(g,1); %确定l和n0

u=[zeros(size(1:(l-1)*k0)),input,zeros(size(1:(l-1)*k0))]; u1=u(l*k0:-1:1); for i=1:n+l-2

u1=[u1,u((i+l)*k0:-1:i*k0+1)]; end

uu=reshape(u1,l*k0,n+l-1);

output=reshape(rem(g*uu,2),1,n0*(l+n-1)); %确定

运行结果：

output =

Columns 1 through 9

0 0 0 0 0 0 0 0 1

Columns 10 through 18

0 1 1 0 1 0 1 0 1

Columns 19 through 27

0 0 0 0 1 0 1 0 0

Columns 28 through 36

0 1 1 1 1 1 1 1 1

四、结果分析：

卷积码是一种纠错编码，它将输入的k 个信息比特编成 n 个比特输出，特别适合以串行形式进行传输，时延小。