中科大编码理论_chapter2

1概念题（30分，每题6分）1.1设C是一个线性分组码，他的生成矩阵G=P I k，I k是一个k X n阶矩阵。

请问：○1码C中含有多少个非零码字？○2码C的校验矩阵是什么？○3校验矩阵的秩与码字最小汉明码之间有什么关系？解：○12k−1个非零码字○2校验矩阵是H=(I n+k|P T)○3d≤R+11.2请分别用生成矩阵和校验矩阵的语言来描述一个向量C=(C1,C2,…,C n)是码字的充要条件。

解：C=M∙GH∙C T=0T或者 C∙H T=01.3伴随式是如何定义的？伴随式为零是否一定无传输错误,为什么？解：设C是一个q元[n, k]线性码，其校验矩阵为H。

对任意y∈V(n,q)，称yH T为y的伴随，记为S(y)。

1.4请描述利用标准阵的伴随式译码方法的主要步骤。

解：1）计算接收矢量y的伴随式S(y)2）在伴随列表中找到S(y)所对应的陪集代表元a。

3）将y译为码字y-a。

1.5伴随式译码、最小距离译码、和最大似然译码三者彼此之间有什么关系？2计算题（30分，每题10分）2.1设C使一个（n, k）线性码。

用A0和A e分别表示码C中汉明重量为奇数和偶数的码字个数。

假设已知A0>0。

请计算A0和A e的值。

解：A0=A e=2k−12.2设某个通信系统中使用的是以H=10001000110111101111为校验矩阵的汉明码。

如果在接收端收到的向量是r=(1001010)，并且假定传输错误个数不超过1个。

请计算出译码后的正确码字。

解：10010112.3设C1是(n1,k1,d1)线性码，C2是(n2,k2,d2)线性码，它们的生成矩阵分别为G1=P1I k和G2=P2I k。

假定C是以H=I n1+n2−k ⋮P1T I k P2T为校验矩阵的线性码。

请问码C的码长=？，信息位=？，码间最小距离=？解：请问码C的码长=n1+n2，信息位=k，码间最小距离=d1+d2…….3 证明题（40分）3.1（20分）请证明循环码中次数最低的非零码字多项式是唯一的。

20XX年复习资料大学复习资料专业：班级：科目老师：日期：第1章绪论1.1信息论的形成与发展⏹信息论的发展过程✓20X X X X24年，H N y q u i s t，信息率与带宽联系✓20X X X X28年，R V H a r t l e y,引入非统计信息量✓20X X X X36年，E H A r m s t r o n g，带宽与抗干扰能力✓20X X X X36年，H D u d l e y,发明声码机✓40年代初，N W i e n e r,“控制论”✓20X X X X48年，S h a n n o n,“信息论”“A m a t h e m a t i c a l t h e o r y o fc o m m u n i c a t i o n s”信息时代的里程碑✓50年代开始，I R E成立信息论组，出版信息论汇刊⏹信息论的形成与发展✓20X X X X59年，S h a n n o n,信源压缩编码理论，“C o d i n g t h e o r e m f o r a d i s c r e t e s o u r c e w i t h a f i d e l i t y c r i t e r i o n”✓20X X X X0X X1年，S h a n n o n,“双路通信信道”，多用户理论✓20X X X X0X X2年，C o v e r,广播信道⏹三大定理⏹无失真信源编码定理（第一极限定理）⏹信道编码定理（第二极限定理）⏹限失真信源编定理（第三极限定理）S h a n n o n信息论：在噪声环境下，可靠地、安全地、有效地传送信息理论----狭义信息论⏹信息✓定义广义定义：信息是物质的普遍属性，所谓物质系统的信息是指它所属的物理系统在同一切其他物质系统全面相互作用（或联系）过程中，以质、能和波动的形式所呈现的结构、状态和历史概率信息：信息表征信源的不定度，但它不等同于不定度，而是为了消除一定的不定度必须获得与此不定度相等的信息量⏹信息✓性质信息是无形的信息是可共享的信息是无限的信息是无所不在的信息是可度量的⏹信息✓信息与消息、信号比较消息是信息的数学载体、信号是信息的物理载体信号：具体的、物理的消息：具体的、非物理的 信息：非具体的、非物理的 信息的定义和性质⏹ 信息、消息、信号u 信号最具体，它是一物理量，可测量、可显示、可描述，同时它又是载荷信息的实体 信息的物理层表达u 消息是具体的、非物理的，可描述为语言文字、符号、数据、图片，能够被感觉到，同时它也是信息的载荷体。

第二章2.9 （1）对于离散无记忆信源DMS=,试证明：H(X)=H2(p)=-p log p-(1-p)log(1-p)当p=1/2时，H(X)达到最大值。

（2）对（1）中的DMS，考虑它的二次扩展信源X（2）=,证明：H(X(2))=2H(X)。

解：（1）函数H(X)plogp(1p)log(1p)中的变量p在0到1中取值，从函数的结构上可以知道该函数在区间[0,1]上是关于p=1/2对称的函数。

H(X)log（p1）pp（1p）p1ln21ln2(1p)1ln2log(1p)pln2(1p)log1pln2(1p)log（1p）p0在区间[0，0.5]上1-p>p,则（1-p）/p>1，所以log，在此区间上H(x)>0，H(x)单调递增。

又该函数是在区间[0,1]上是关于p=1/2对称的函数，那么在区间[0.5,1]上单调递减。

所以，H(X)H2(p)plogp(1p)log(1p)在p=1/2时，H(X)达到最大值。

(2)二次扩展后的矩阵：=H(X(2))p2logp2p(1p)log2p(1p)2p(1p)logp（1-p）2[plogp(1p)(1p)log(1p)p2(1p)log(1p)p(1p )log(1p)]2H(X )2.11 (1)一个无偏骰子，掷骰子的熵为多少？（2）如果骰子的被改造使得某点出现的概率与其点数成正比，那么熵为多少？（3）一对无偏骰子，各掷一次，得到总点数为7，问得到多少信息量？解：（1）H（x）= -log1/6=log6=2.58(bit/符号)（2）由q(x i)=kx i得21k=1 即k=1/21H(x)=-1/21(log1/21)-2/21(log2/21)-3/21(log3/21)-4/21(log4/21)-5/21( log5/21)-6/21(log6/21)=2.36（bit/符号）（3）I（A+B=7）=-log1/6=log6=2.58(bit)2.12 一个盒子中放有100个球，其中60个球是黑色的，40个球是白色的。

信息论与编码第二章答案本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March2-1、一阶马尔可夫链信源有3个符号{}123,,u u u ，转移概率为：1112()u p u =，2112()u p u =，31()0u p u =，1213()u p u = ，22()0u p u =，3223()u p u =，1313()u p u =，2323()u p u =，33()0u p u =。

画出状态图并求出各符号稳态概率。

解：由题可得状态概率矩阵为：1/21/20[(|)]1/302/31/32/30j i p s s ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦状态转换图为：令各状态的稳态分布概率为1W ，2W ，3W ，则：1W =121W +132W +133W ， 2W =121W +233W , 3W =232W 且：1W +2W +3W =1 ∴稳态分布概率为：1W =25，2W =925，3W = 6252-2.由符号集｛０，１｝组成的二阶马尔可夫链，其转移概率为：P(0|00)=,P(0|11)=,P(1|00)=,P(1|11)=,P(0|01)=,p(0|10)=,p(1|01)=,p(1|10)=画出状态图，并计算各符号稳态概率。

解：状态转移概率矩阵为：令各状态的稳态分布概率为1w 、2w 、3w 、4w ，利用（2-1-17）可得方程组。

1111221331441132112222332442133113223333443244114224334444240.80.50.20.50.50.20.50.8w w p w p w p w p w w w w p w p w p w p w w w w p w p w p w p w w w w p w p w p w p w w =+++=+⎧⎪=+++=+⎪⎨=+++=+⎪⎪=+++=+⎩ 且12341w w w w +++=；0.8 0.2 0 00 0 0.5 0.5()0.5 0.5 0 00 0 0.2 0.8j i p s s ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦解方程组得：12345141717514w w w w ⎧=⎪⎪⎪=⎪⎨⎪=⎪⎪⎪=⎩ 即：5(00)141(01)71(10)75(11)14p p p p ⎧=⎪⎪⎪=⎪⎨⎪=⎪⎪⎪=⎩ 2-3、同时掷两个正常的骰子，也就是各面呈现的概率都是16，求：（1）、“3和5同时出现”事件的自信息量； （2）、“两个1同时出现”事件的自信息量； （3）、两个点数的各种组合的熵或平均信息量； （4）、两个点数之和的熵；（5）、两个点数中至少有一个是1的自信息量。

二章-信息量和熵习题解2.1 莫尔斯电报系统中，若采用点长为0.2s ，1划长为0.4s ，且点和划出现的概率分别为2/3和1/3，试求它的信息速率(bits/s)。

解: 平均每个符号长为:1544.0312.032=⨯+⨯秒 每个符号的熵为9183.03log 3123log 32=⨯+⨯比特/符号所以，信息速率为444.34159183.0=⨯比特/秒 2.2 一个8元编码系统，其码长为3，每个码字的第一个符号都相同(用于同步)，若每秒产生1000个码字，试求其信息速率(bits ／s)。

解: 同步信号均相同不含信息,其余认为等概,每个码字的信息量为 3*2=6 比特；所以，信息速率为600010006=⨯比特/秒2.3 掷一对无偏的骰子，若告诉你得到的总的点数为：(a ) 7；(b ) 12。

试问各得到了多少信息量?解: (a)一对骰子总点数为7的概率是366 所以，得到的信息量为 585.2)366(log 2= 比特 (b) 一对骰子总点数为12的概率是361所以，得到的信息量为 17.5361log 2= 比特 2.4 经过充分洗牌后的一付扑克(含52张牌)，试问：(a) 任何一种特定排列所给出的信息量是多少?(b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量?解: (a)任一特定排列的概率为!521, 所以，给出的信息量为 58.225!521log 2=- 比特 (b) 从中任取13张牌,所给出的点数都不相同的概率为 13131313525213!44A C ⨯=所以，得到的信息量为 21.134log 1313522=C 比特.2.5 设有一个非均匀骰子，若其任一面出现的概率与该面上的点数成正比，试求各点出现时所给出的信息量，并求掷一次平均得到的信息量。

解:易证每次出现i 点的概率为21i,所以 比特比特比特比特比特比特比特398.221log 21)(807.1)6(070.2)5(392.2)4(807.2)3(392.3)2(392.4)1(6,5,4,3,2,1,21log )(2612=-==============-==∑=i i X H x I x I x I x I x I x I i ii x I i2.6 园丁植树一行，若有3棵白杨、4棵白桦和5棵梧桐。

信息论与编码理论Theories of Information
and Coding
第一章介绍
Chapter 1 Introduction
第二章信息理论Chapter 2 Information Theory
信息论与编码理论中的英文单词和短语
第三章 离散无记忆信
道和容量成本方程
Chapter 3 Discrete Memory less Channels and their Capacity -Cost Equations
第四章 离散无记忆信
源和扭曲率方程
Chapter 4 Discrete Memoryless Sources and their Rate -Distortion Equations
第五章 高斯信道和信
源
Chapter 5 Gaussian Channel and Source
第六章 信源-信道编码
理论
Chapter 6 Source -Channel Coding Theory
第七章 第一部分访问
先进标题
Chapter 7 Survey of Advanced Topics for Part One
第八章线性码Chapter 8 Linear codes
第九章循环码Chapter 9 Cyclic Codes
第十章 香农码和相关
的码
Chapter 10 Shannon Codes and Related Codes
第十一章 卷积码
Chapter 11 Convolution Codes
第十二章变量长度源编
码
Chapter 12 Variable-length Source Coding。

分布式算法作业周锋SA140110622.1分析在同步和异步模型下，convergecast算法的时间复杂性。

解：（1）同步模型：最坏情况下，算法执行的每一轮中只有一个msg传递，而此时生成树汇聚最大值的算法最多执行n-1轮，也就是说同步情况下的时间复杂度为O(n-1)。

（2）异步模型：在异步模型的汇集算法的每个容许执行中，树中每个距离pr为t的处理器至多在时刻t接收消息M，因此对于每个节点而言，它到它所有子节点中t最大的路径决定了它本身时间花费。

因此在最坏情况下，仍应该是同步模型下的最坏情况，即生成树中除了末端节点每一个节点只有一个子节点，此时时间复杂度仍为O(n-1)。

可达的，当且仅当它的parent 2.2证明在引理2.6中，一个处理器在图G中是从Pr变量曾被赋过值。

证明：必要性：因为图G是由parent和children确定的静态图，任一节点在收到M后才会加入到图中。

即可达节点收到过M，执行了算法2.2的第五行。

由于是容许执行的，所以第7行（parent:=j）也会执行。

充分性：若算法2.2的第7行执行过了，因为是容许执行，则必然有第5行也执行过了。

即节点收到过M。

而M又是从pr发出的，所以该节点是从pr可达的。

2.3证明Alg2.3构造一棵以Pr为根的DFS树。

证明：连通性：假设构造的图G存在邻居节点Pj和Pi。

Pj从Pr可达，但Pi从Pr是不可达的。

则Pi的parent为nil或者Pi不为Pj的child。

由于G里一结点从pr可达当且仅当它曾设置过自己的parent变量。

所以：1）Pj的parent必然设置过了；2）Pi的parent为nil或者Pi属于Pj的unexplored集合。

而算法的第11和14行决定了Pj会向Pi发送M,使得Pi的parent成为Pj,Pi成为Pj的child。

这与假设的结果矛盾。

故Pi必然也是从Pr可达的。

无环：假设G中存在一个环，P1,P2,….,Pi,P1。