编码理论习题.docx
- 文档编号:15010058
- 上传时间:2023-06-29
- 格式:DOCX
- 页数:38
- 大小:418.93KB
编码理论习题.docx
《编码理论习题.docx》由会员分享,可在线阅读,更多相关《编码理论习题.docx(38页珍藏版)》请在冰点文库上搜索。
编码理论习题
编码理论习题
第一章概述
1.1:
通信的主要目的是什么?
通信:
采用某种方法,借助某种媒介将信息从甲地传送到乙地的过程
通信的目的:
要把对方不知道的消息及时可靠地(有时秘密的)传送给对方
1.2:
信道编码的主要目的是什么
信源编码的主要作用是:
在保证通信质量的前提下,尽可能的通过对信源的压缩,提高通信时的有效性。
就是让通信变得更加的有效率。
以更少的符号来表示原始信息,所以减少了信源的剩余度。
信道编码的主要作用是:
通过对做完信源编码后的信息加入冗余信息,使得接收方在收到信号后,可通过信道编码中的冗余信息,做前向纠错。
保证通信的可靠性。
1.3:
仙农编码定理的主要内容是什么?
仙农编码定理:
如果系统的传输率小于信道容量,那么适当选择编码技术就能实现可靠通信,即可以将差错率减小到任意小的程度。
更确切地,每个信道都具有固定的信道容量C,对任何小于C的信息传输率R,存在一个码长为n码率为R的分组码,若用最大似然译码,则其译码错误概率为
。
对于码率为R约束长度为ne的卷积码,其译码错误概率也有类似的关系,即
其中A和B都为大于0的数,Eb(R)和Ee(R)为正实函数,叫做误差指数。
1.4:
请画出数字通信系统模型的通用框图。
1.5:
信源编码扩张了数据么,为什么?
信源编码没有扩张数据。
信源编码减少了数据的冗余。
信源编码器:
将信源输出变成二元数字(bit)序列,称为信息序列,在信源连续的情况下,还需要进行模/数(A/D)转换。
理想信源编码器模型要满足
(1)为表示信源输出所要求的单位时间的比特数要尽量小;
(2)信源的输出S可从信息序列U中确切的重新构造
1.6:
信道编码扩张了数据么,为什么?
信道编码扩张了数据。
信道编码器:
将信息序列U变换成离散的有结构的编码序列X,这称为码字。
即为了使传输有效,人为的增加一些冗余度,使其具有自动检错和纠错的能力。
码字的结构主要用以对付传输或存储码字的有扰信道,码字的设计和实现是本课程的主题。
1.7:
为什么要用信源编码器理想的信源编码器应该满足什么要求
为了减少数据的冗余。
信源编码器:
将信源输出变成二元数字(bit)序列,称为信息序列,在信源连续的情况下,还需要进行模/数(A/D)转换。
理想信源编码器模型要满足
(1)为表示信源输出所要求的单位时间的比特数要尽量小;
(2)信源的输出S可从信息序列U中确切的重新构造
1.8:
为什么要用信道编码器?
为了使传输有效
信道编码器:
将信息序列U变换成离散的有结构的编码序列X,这称为码字。
即为了使传输有效,人为的增加一些冗余度,使其具有自动检错和纠错的能力。
码字的结构主要用以对付传输或存储码字的有扰信道,码字的设计和实现是本课程的主题。
1.9:
为什么要用调制器?
离散符号不适合于在实际信道上传输或记录在数字存储媒质上。
调制器将信道编码器的每个输出的离散符号,通过调制变成适合传输(或存储)的持续时间为T的波形,此波型进入信道(或存储媒质),并受噪声干扰
1.10:
有哪些典型的传输信道、存储媒质和信道干扰?
典型的传输信道:
有线信道、无线信道、电话线路、高频无线线路、遥测线路、微波线路、卫星线路、光纤信道、磁记录信道、大气光信道、水声信道等
典型的存储煤质:
磁芯和半导体存储器、磁带、磁鼓、磁盘、光存储器、光盘等
典型的干扰:
开关脉冲噪声、热噪声、串音、闪电、磁涂层缺损、光盘划痕等
1.11:
为什么要用解调器?
解调器(或读出单元):
处理接收到的每个持续时间为T的波形,并产生一个可能是离散的(量化的)或连续的(未量化的)输出。
对应于编码序列X的解调器的输出序列Y称为接收序列
1.12:
信道译码器的功能是什么?
信道译码器:
将接收序列Y变换成二元序列V,称为估值序列。
在理想的情况下,V与信息序列U完全一致,但是噪声会造成译码错误。
译码方法根据信道编码规则和信道(或存储煤质)的噪声特性而定。
但设计和实现译码错误概率最小的信道译码器也是本课程的主要论题之一
1.13:
为什么要用信源译码器?
信源译码器:
把估值序列V变成信源输出的估值(原来消息的估值),并将此估值传送给用户。
如果信源是连续的,需要进行数/模转换。
在一个精心设计的系统中,除非信道(或存储煤质)的干扰太强,否则这个估值将是信源输出的准确重现
1.14:
请画出数字通信系统模型的简化框图。
1.15:
简述信道编码的主要应用领域。
通信系统:
如卫星、有线和无线的电话通信、军事通信等,利用纠错码来实现可靠通信和敌人的恶意干扰
计算机系统:
如计算机存储器、数字磁带、磁盘、光盘、数字逻辑电路中
商业领域:
如条形码,由黑白相间的不同宽度的条纹来代表不同的信息,包含了一定的纠错信息,可以纠正由于条码的模糊不清等原因造成的读写错误,因此条形码在运输、仓储、超级市场管理等物流行业获得了广泛的应用
1.16:
简述分组码和卷积码的相同点和不同点。
分组码
编码器:
将信息序列分为长度为K比特的消息段U=[u1,u2,…,uK],称为消息,分组进行编码,总共有2K个消息,将每个消息U独立的变换成长度为N比特的码字的序列V=[v1,v2,…,vN]
(N,K)分组码:
所有个2K码字的集合
码速率:
比值R=K/N,可以理解为码字含有信息比特数量,为使编码不冲突,R≤1
纠错机理:
当R<1时,码字比消息多了n-k个比特,称为校验位,可以抗干扰
无记忆:
每个N长的码字V由相应的K长消息U唯一确定
分组码可用组合逻辑电路来实现
卷积码
编码器:
也是接收长度K比特的信息序列U=[u1,u2,…,uK],并产生一个长度为N比特的码字的序列V=[v1,v2,…,vN]
有记忆:
每一编码组不仅与同一时间单元上K比特消息有关,还与前m个输入有关。
因而编码器的存储器为m级
(N,K,m)卷积码:
有K个输入,N个输出,存储级为m的编码器产生的序列集
码速率:
比值R=K/N
在K 通常K,N都是较小的整数,当保持K,N不变时,可通过增大存储级来添加更多的冗余度 卷积码有记忆,必须用序列逻辑电路来实现 1.17: 硬判决和软判决有什么不同? 因为存在噪声或干扰,信号在信道中传输,经常会发生错误,所以接收端必须进行判决以确定发送端发送的是什么码元: 硬判决: 当用二元码时,调制器仅有二元输入。 类似的,解调器输出采用二元量化时,译码器只有二元输入,这种情况下,解调器采用硬判决 软判决: 如解调器输出未量化或者量化门限大于2,则解调器采用软判决 删除信号: 对没有把握做出正确判决的信号,就暂时搁置起来不做判决,并用“×”表示,称为删除符号 1.18: 仙农信息论的基本思想是什么? 1948年,仙农在一篇具有历史意义的论文指出证明了: 对信息进行适当的编码,在不牺牲信息传输和存储速率的情况下,可以将有扰信道或存储介质引入的差错减到任意低的程度 仙农编码定理解决了纠错码的存在性问题,从此纠错编码的研究与应用开始了前所未有的发展,人们一直在不停的努力解决构造性问题 过程比结果更重要: 为了接近信息传输率的上限,已经提出了很多的纠错编码技术 1.19: 什么是正交振幅调制? QAM: QuadratureAmplitudeModulation 数据信号: 由相互正交的两个载波的幅度变化表示 幅度、相位联合调制: 在最小距离相同的条件下可实现更高的频带利用率 QAM最高已达到1024-QAM(1024个样点),样点数目越多,传输效率越高 举例: 具有16个样点的16-QAM信号,每个样点表示一种矢量状态,16-QAM有16态,每4位二进制数规定了16态中的一态,16-QAM中规定了16种载波和相位的组合,16-QAM的每个符号和周期传送4比特 调制的原理: 发送数据在编码器内被分成两路,各为原来两路信号的1/2,然后分别与一对正交调制分量相乘,求和后输出。 接收端完成相反过程,正交解调出两个相反码流,均衡器补偿由信道引起的失真,判决器识别复数信号并映射回原来的二进制信号 1.20: 最大后验概率译码和最大似然译码之间的关系是什么? 最大后验概率译码: 对于每个输入Y,如果译码器能在码字集合中选择一个码字,作为发送码字的估值,并且使P(X/Y)最大,则这种译码规则一定能使译码器输出的错误概率最小 最大似然译码定义: 对于给定的Y,可选择能使上式右边最大的向量作为X的估计值 如果所有码字都是等可能的,即P(X)是常数,那么上式左边最大,就推导出P(Y/X)最大 P(Y/X): 似然函数,信道转移概率 若能在码字集合选择合适的码字X,使得P(Y/X)最大,则这种译码规则被称为最大似然译码 1.21: 最小距离译码准则和最大似然译码准则的关系。 最大似然译码定义: 对于给定的Y,可选择能使上式右边最大的向量作为X的估计值 如果所有码字都是等可能的,即P(X)是常数,那么上式左边最大,就推导出P(Y/X)最大 P(Y/X): 似然函数,信道转移概率 若能在码字集合选择合适的码字X,使得P(Y/X)最大,则这种译码规则被称为最大似然译码 定义: 若能在码字集合选择合适的码字X,使得P(Y/X)最大,则这种译码规则被称为最大似然译码 MLD: 对应的译码器称为最大似然译码器 对数似然函数: 由于lnx与x是单调关系,故有lnP(Y/X) 对于离散无记忆信道, 所以 最小距离译码器: 在BSC中,MLD规则变成了选择能使Y和X之间的汉明距离为最小的向量,作为码字X的估计值 1.22: 列出2种典型传输错误并说明其不同点。 随机错误 定义: 接收序列中的传输错误是随机出现的 这样的信道称为随机错误信道 常见于无记忆信道中,因为噪声随机独立的影响每个传输信号 深空通信和卫星通信信道都是典型的随机错误信道 为纠正随机错误而设计的码称为纠随机错误码 突发错误 定义: 不同状态特性下,错误出现的概率不一样,这种错误为突发错误 信道状态特性变化较大,进而有突发错误信道的概念。 常出现在有记忆信道中,此时噪声对各次传输的影响是彼此相关的 突发错误的例子: 无线通信(由多径传输引起的信号衰落造成的错误),有线和电缆传输(开关脉冲和串话的影响),磁带记录(涂层缺损和灰尘引起的带脱落) 纠突发错误码: 为纠正突发错误而设计的码 不同点: 随机错误的特点是码元间的错误相互独立,及每个码元的错误概率与它前后的错误无关。 突发错误则不然,一个码元的错误往往影响前后码元的错误概率。 即一个码元产生错误则后面几个码元都可能发生错误。 1.23: 列出3种差错控制方式,比较传输效率。 前向纠错(FEC): 利用纠错码自动的纠正接收端检查出的错误 单向传输系统一般只能这样差错控制 优点: 不需要反馈信道,译码实时性好,控制电路简单,能进行一个用户对多个用户的同播通信 缺点: 译码设备较复杂,对信道适应性差,所选用的纠错码必须与信道的干扰情况相匹配,编码效率低 例子: 磁带存储系统(记录在磁带上的信息很久以后再重读),深空通信系统(飞行体上的编码设备很简单,地面的译码设备可以很强大),军事通信 自动要求重传(ARQ): 当接收端检查到错误时,就自动要求发送端重新传送该消息 优点: 易于实现,成本和复杂性低 缺点: 必须有反馈信道,实现控制较复杂,难以用于同播系统,通信效率低,很难适合实时传输系统 双向传输系统可使用这种方法进行差错控制 混合差错控制(HEC): 是FEC和ARQ方式的结合,具有FEC和ARQ方式的优点 发送端: 发送有纠错和检错能力的码 接收端: 检查错误情况,如果错误在该码的纠错能力范围内,则自动进行纠正;如果信道干扰很严重,错误超过纠错能力,但是能检测出来,则经反馈信道请求发送端重发 适用于环路时延大的高速传输系统中,如卫星通信 信息反馈方式(IRQ) 接收端: 把接收到数据,原封不动的通过反馈信道送回发送端 发送端: 比较发送数据和反馈数据,如发现错误,则重新发送出错的消息,直到没有发信错误为止 优点: 不需要检、纠错、编、译码器,控制设备和检错设备较简单 缺点: 需要反馈信道,环路时延较大,发送端需要存储器存储已经发送的码组 仅适用于传输效率较低,数据信道错误率较低,有双向传输信道和控制简单的系统中 传输速率: 自动要求重传(ARQ)通信效率低,混合差错控制(HEC)传输速率较高,信息反馈方式(IRQ)传输速率较低。 1.24: 对于如图1.1所示的BSC信道,信源符号发生的概率为P(x1)=0.6,P(x2)=0.4,求 (1)信源X中事件x1和x2分别的自信息(以比特为单位); (2)接收符号yi(i=1,2)发生的概率;(3)求条件概率P(xi|yi);(4)收到消息yi(i=1,2)后,获得的关于xi(i=1,2)的信息量;(5)x和yi之间的互信息;(5)信源X和信源Y的信息熵;(6)条件熵H(X|Y)和H(Y|X) (1)X1的自信息I(x1)=-log0.6=I(x2)=-log0.4= (2)P(y1)=0.6*(5/6)+0.4*(3/4)=0.8P(y2)=0.6*(1/6)+0.4*(1/4)=0.2 (3)P(x1|y1)=P(x1y1)/P(y1)=P(y1|x1)P(x1)/P(y1)=5/8 P(x1|y2)=P(x1y2)/P(y2)=P(y2|x1)P(x1)/P(y2)=1/2 P(x2|y1)=P(x2y1)/P(y1)=P(y1|x2)P(x2)/P(y1)=3/8 P(x2|y2)=P(x2y2)/P(y2)=P(y2|x2)P(x2)/P(y2)=1/2 (4)但是 (5)I(x1;y1)=log(P(x1|y1)/P(x1))=log(5/8/0.6)=log(25/24) I(x1;y2)=log(P(x1|y2)/P(x1))=log(1/2/0.6)=log(5/6) I(x2;y1)=log(P(x2|y1)/P(x2))=log(3/8/0.4)=log(15/16) I(x2;y2)=log(P(x2|y2)/P(x2))=log(1/2/0.4)=log(5/4) (6)H(X)= (7)=-(P(x1)logP(x1)+P(x2)logP(x2))=-(0.6log0.6+0.4log0.4)= H(Y)=-(P(y1)logP(y1)+P(y2)logP(y2))=-(0.8log0.8+0.2log0.2)= (8)H(X|Y)= =-(P(x1y1)log(P(x1|y1))+P(x2y1)log(P(x2|y1))+P(x1y2)log(P(x1|y2))+P(x2y2)log(P(x2|y2)))=-(0.5log0.5+0.3log0.3+0.1log0.1+0.1log0.1) 1.25: 信息熵和消息的平均信息量、信源的平均不确定性之间有什么关系? 平均自信息量(信息熵) 定义: 离散随机变量X的平均自信息定义为,其样本空间为{xi,i=1,2,…,n},则事件X=xi的平均自信息量的定义为 H(X)表示每个信源符号的平均信息量 举例: 变量X,P(X=x1)=0.99,P(X=x2)=0.01,变量Y,P(Y=y1)=0.5,P(Y=y2)=0.5,则信息熵为 H(X)=-0.99log0.99-0.01log0.01=0.08(比特/符号) H(Y)=-0.5log0.5-0.5log0.5=1(比特/符号) 信息熵的物理含义 H(X)表示信源输出后,每个消息(或符号)提供的平均信息量 H(X)表示信源输出前,信源的平均不确定性 例如: 上页例子中,H(Y)>H(X),对于信源X,两个输出消息不是等概率的,事先大致可以猜测消息x1会出现,故信源X的不确定性要小 H(X)表示变量X的随机性 当信源符号是等概率出现的时候,信息熵可以达到最大值 1.26: 简述等长信源编码定理的主要内容。 定理: 一个熵为H(X)的离散无记忆信源,若对信源长为N的符号序列进行等长编码,设码字是从r个字母的码符号集合中,选取l个码元组成。 对于任意的ε>0,只要满足 则当N足够大时,可实现几乎无失真编码,即译码错误概率可为任意小。 1.27: 简述前缀码和惟一可译码之间的关系。 前缀码/前缀条件码 定义: 若码C中,没有任何完整的码字是其他码字的前缀,称此码为前缀码,也称即时码或非延长码 前缀码和即时码的定义是一致的: 如果没有一个码字是其他码字的前缀,则在译码过程中,当收到一个完整码字的码符号序列时,就能直接把它译成对应的信源符号,无需等待下一个信号到达后才作判断,这就是即时码 关系: 前缀码是惟一可译码的一类子码: 即前缀码一定是惟一可译码,但是惟一可译码不一定是前缀码 1.28: 霍夫曼编码唯一么? 简述霍夫曼编码的主要步骤。 不唯一 霍夫曼编码的步骤: 将信源符号按照概率递减的顺序进行排序 将0和1符号分别分配给概率最小的两个信源符号,并将这两个概率最小的符号合并成一个新符号,用这两个信源符号的概率之和作为这个新符号的概率 以此类推继续这个过程,直到只剩下2个符号为止,从而完成霍夫曼树的构造 从树的最后一个节点,依编码路径从后往前返回,读出每个分支上对应的符号标示,即可得到对应的码字 1.29: 考虑比特流111111*********000000000000000000111111,如果对之用游程编码方案进行压缩编码,那么压缩率为多少? 游程编码定义: 游程指的是信源输出的字符序列中,各种字符连续的重复出现的字符串的个数 游程编码: 就是将这种字符序列映射成字符串的长度和字符串的位置的标志序列 考虑比特序列111111*********000000000000000000111111,可以被表示成(15,1),(18,0),(6,1),字符最长的重复的数目为18,因此把该比特序列编码为(01111,1),(10010,0),(00110,1),此时压缩率为15: 39=1: 1.30: 简述LZ编码的分段方法和编码方法。 LZ编码分段的方法为: (1)游程先取第一个符号作为第一段,然后再继续分段 (2)若有出现与前面符号一样时,就再添加紧跟后面的一个符号一起组成一段(3)尽可能取最少个连着的符号并保证各段都不相同(4)以此类推,直至信源符号序列结束 编码方法为: 首先去掉最后一个符号,然后看剩下的字符串在字典中的排序,这个排序值转换成二进制数作为指针K的值,最后一个信源符号作为码字第2项d的值,即得到码字(X,d) 1.31: 考虑比特序列010*********,如果用LZ编码,那么其分段是什么,编码后的码字又是什么? 0,1,01,011,00,11,010,10,101,1 (000,0),(000,1),(001,1),(011,1),(001,0),(010,1),(011,0),(010,0),(1000,1),(000,1) 1.32: 考虑一个如图1.2所示的BSC信道,其信道转移概率为P(0|1)=P(1|0)=p,求该信道的容量。 如果ω=0.5,用信道容量的公式,可以获得BSC的信道容量为C=1+plog2p+(1-p)log2(1-p),熵函数为H(p)=-plog2p-(1-p)log2(1-p),因此得到C=1-H(p) 1.33: 求具有如下信道传递矩阵的信道的容量。 1.34: 简述信道编码定理的内容。 定理: 假设DMS有信源字符集X,熵为每信源符号H(X)比特,而且信源每Ts秒产生一个符号,那么信源的平均信息率为每秒H(X)/Ts比特,假设信道可以每Tc秒使用一次,而信道容量为每次信道使用C比特,那么每单位时间的信道容量为每秒钟C/Tc比特。 如果H(X)/Ts≤C/Tc,那么就存在编码方案使得在有噪声的信道上传输的信源消息,能够以任意小的错误概率进行恢复。 1.35: 什么是无记忆信道和二元对称信道? 无记忆信道: 如果在给定时间间隔上,检测器的输出只与在该时间间隔上传送的信号有关,而与任何前面时间的传送的信号无关,称此信道为无记忆信道 离散无记忆信道: 是一种M元输入、Q元输出的信道模型 二元对称信道: M=2,Q=2 二元对称信道: 是一种2元输入、2元输出的信道模型 1.36: 仙农的信息定义是什么信息量的多少跟事件发生的不确定性之间有什么关系 仙农对于信息的定义: 信息是事物运动状态或存在方式不确定性的描述 一个句子中所含信息的多少,同句子中所表达的事件出现的概率有关: 呈现相反的关系 信息量的多少,同事件发生的不确定性有关: 呈现相反的关系 第二章 2.1: 某些域中元素有大小之分,另一些域中的元素无大小之分,各举一个例子。 2.2: 交换律、分配律、结合律在群上成立么在环上成立么在域上成立么 结合律在群上成立,交换律在交换群上成立,分配律群上不成立 结合律在环上成立,交换律(乘法)在交换环上成立,加法和乘法在环上满足分配律 结合律、交换律、分配律在域上成立 2.3: 简述群、环、域三者之间的关系? 定义: 一个集合G,在其上定义了一个二元运算*,若它满足以下条件称为群 满足封闭性,即对G中任意两个元素a,b,有a*b∈G 二元运算*满足结合律 G中存在一个元素e,称为恒元或单位元,使得G中任何元素,有a*e=e*a=a 对于G中任何一个元素a,G中存在另一个元素,称作a的逆元,使得 定义: 非空元素集合R中,定义了两种二元运算,称作加法和乘法,这样的代数系统(R,+,·)称为一个环,若它满足以下条件 R中全体元素在加法下构成交换群,单位元为0,逆元记为-a 乘法运算满足封闭性 满足乘法结合率,即(a·b)·c=a·(b·c), 加法和乘法之间满足分配律 a·(b+c)=a·b+a·c,(b+c)·a=b·a+c·a, 定义: 非空元素集合F中,定义了两种二元运算,称作加法和乘法,这样的代数系统(F,+,·)称为一个域,若它满足以下条件 F中全体元素在加法下构成交换群,恒元为0 F中非零元素在乘法下为交换群,恒元为1 加法和乘法之间满足分配律 (a+b)·c=a·c+b·c 环中全体元素在加法下构成交换群,单位元为0,逆元记为-a 域中全体元素在加法下构成交换群,恒元为0 域中非零元素在乘法下为交换群,恒元为1 2.4: 存在含有256个元素的有限域么为什么 不是 由有限域的性质可知: 定理1: 有限域的特征q是素数 256不是素数 2.5: 构造一个含13个元素的有限域。 在该域中,3的逆元和负元是什么? 1/3-3 2.6: 全体整数的集合对普通减法是否构成一个群为什么 不 不满足结合律3-(2-1)与(3-2)-1不等 2.7: 全体非负整数的集合在加法和乘法下是否构成群为什么 全体非负整数集合在实数加法运算下构成可交换群,整数0为恒元,整数-a是整数a的逆元。 全体非负整数集合对乘法不构成群,因为不存在乘法逆元 2.8: 证明群的性质定理1-4。 定理1: 群G的恒元是唯一的 证明: 假定G中有两个恒元e和 ,则有 证毕 定理2: 任何一个群元素的逆元是唯一的 证明: 假定元素a有两个逆元,则 证毕 定理3: 若a,b∈G,则 证明: 所以a*b和互为逆元 定理4: 给定G中任意两个元素a和b,则方程a*x=b和y*a=b在G中有唯一解 证明: 方程a*x=b的解是x=a-1*b,这是因为 a*a-1*b=e*b=b,同理,y*a=b的解是y=b*a-1。 下面证明解的唯一性。 如果在方程a*x=b中, 除了x=a-1*b,还有另外一个解x1,使a*x1=b,则把该式两边左乘以a的逆元a-1,则有a-1*
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编码 理论 习题