通常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*