信息论基础(9)

《信息论基础(9)》由会员分享，可在线阅读，更多相关《信息论基础(9)（78页珍藏版）》请在金锄头文库上搜索。

1、第十章 有约束信道及其编码,http:/:4213/xxl/main.htm,本章主要内容,摘要：,本章研究有约束信道编码的基本理论与技术，主要内容按顺序安排如下：介绍研究有约束信道的重要工具标号图；引入有约束信道容量的概念并提出有约束信道容量的计算方法；研究游程长度受限序列、部分响应最大似然序列和直流平衡序列的性质；介绍仙农有约束信道的基本定理和有限状态编码定理；最后介绍重要的有约束编码序列的实例及主要应用。,10.1 标号图的性质,主要内容,10.1.1 标号图的基本概念,一个标号图（或有限标号图）G由一个有限状态集合(V=VG)）和一个有限边集合(E=EG)以及边标号(L=LG: E ，

2、其中为有限字母表）组成，其中每条边 都有一个初始状态和一个终止状态，这些状态都属于。标号图记为G =（V，E，L）,相关概念及性质,标号图为有向图，每条边只有一个方向，由起始状态指向终止状态，而且每条边都和一个标号相对应。每条边也是其初始状态的输出边，同时又是其终止状态的输入边。对于每个状态，都允许存在从自身起始并终止到自身的边。这种边称做自环。 从给定状态到某一状态允许存在多条边，但每条边要有不同的标号；而从一状态到不同状态的边可以有相同的标号。为了用标号图产生有限符号序列，可沿图中的选定的路径依次读出所经过边所对应的标号，这就产生一串符号序列。,该图有3个状态1，2，3；有限字母表为 ；图

3、中有6条边，其中在状态1存在自环，从状态3到状态1有两条边，但标号不同；而从状态3到状态1和从状态3到状态2有两条相同标号（c）的边；沿路径， 可产生序列为bbda。,有约束系统,沿标号图的所有路径读出的标号所产生的序列（或字）集合，称为一个有约束系统，记为S。可见一个给定的有约束系统可以用标号图来表示。由于有约束系统只与标号有关而与标号图的状态无关，所以同一个有约束系统可用多种不同的标号图来表示。,连接矩阵,由于标号图是有向图，所以可以用连接矩阵来描述。设一个N状态的标号图G ，定义连接矩阵DG（或简记为D）为NN 阶矩阵： D=d i j （ 1011）,其中，dij为从状态i到状态j 的

4、边的数目， i，j =1，N。连接矩阵也称邻接矩阵。 例如，例10.1 中的标号图的连接矩阵是：,N阶连接矩阵,设G是一个标号图，G的N次幂用GN表示，也是一个状态集合与G相同的标号图，而它的每条边都与在G中产生的长度为N的路径相对应。因此GN的每条边对应的标号就是一条长度为N且满足G的约束的序列。GN的连接矩阵DG就是DG的N次幂DGN（或简记为DN），即（ 1012） 其中，每个元素表示在图G中从状态i经N步到状态j的路径数。实际上，它表示此有约束系统从状态i到状态j所能构成的长度为N的序列的数目。,求例10.1.1图中的有约束系统,由状态3到状态2所能构成的长度为3的序列的数目，并列出这

5、些序列。,解：计算所求序列数为，这3个序列是：cbc，dab，cab。,10.1.2 标号图的变换,等价状态合并 :在标号图中，状态s1,s2,sJ是等价的，当且仅当对每一个可能的输入序列，不管s1,s2,sJ中哪一个是初始状态，所产生的序列完全相同。可以验证，对于两状态si,sj，如果它们具有相同数目和对应相同标号的输出边，并且具有相同标号的边的终止状态也相同，那么si和sj是等价的。等价状态满足自反性、对称性和传递性。,等价状态可以合并成一个状态。例如，状态si具有输出边集合ei1,ei2，状态sj具有输出边集合ej1,ej2，并且ei1与ej1有相同的标号和终止状态，ei2与ej2有相同

6、的标号和终止状态，那么状态si和sj可以合并成一个状态。等价状态合并后，原来两状态合并前的输入边都保留作为合并后新状态的输入边，而只保留合并前其中一个状态的输出边。等价状态合并后的图与合并前的图是等价的。即两图所产生的序列完全相同。等价状态合并的示意图如下图所示。,状态节点的吸收,如图所示,节点s2可被吸收，从而变成新的标号图。此时应注意：1、状态节点被吸收后，图的标号集合要扩展。例如，图中的标号集合就增加ba,ca 等元素。2、状态节点被吸收后，标号图与原来的图不等价。因此，仅当所研究的问题与有约束序列的起点无关时才能使用该方法。,在摩尔斯电码中，容许的符号有3个，分别为“点”、“划”、“空

7、”，规定不能出现3个连续的“空”。试画出摩尔斯电码所对应的状态图。,解：将“点”、“划”、“空”、“空空”作为图的4个状态，由题意，“空空”后面不能接“空”。所求状态图如图所示。图中, 状态集合V=点，划，空，空空，边标号集合=点，划，空。,利用等价状态关系对上状态图化简解：合并等价节点 状态节点吸收, 10.2 有约束信道容量,主要内容,一个有约束信道的容量C定义为：其中，M（T）为时间长度T内所允许的序列的个数。这些不同排列构成的序列可以代表信源的不同输出。根据渐近均分特性，当T足够大时，信源输出序列接近等概率出现；再根据离散最大熵定理，当这M（T）种序列等概率时，达到最大熵。所以，上式表

8、示在单位时间内所能传输的最大信息量。,10.2.1 有约束信道容量的定义,为使传送的消息适应信道的特性或与检测所采用的信号处理方式相匹配，传输系统将某些约束加到传输序列上，这个过程就是对有约束序列进行编码的过程。我们将产生有约束序列的系统称为有约束系统。因此信道传送有约束的消息和系统按照某种约束产生消息实际的效果是一样的，所以有约束系统和有约束信道具有相同的含义。实际上，这种有约束信道与信源问题没有多大差别。如果我们把受信道规则约束的符号看成受同样规则约束的信源符号，那么信道符号间的约束相当于信源符号之间的相关性，所以计算信源的最大熵与计算这种信道的容量是等价的。,定理 ：等时长有约束信道的容

9、量等于系统连接矩阵最大特征值的对数，即 C=log2 max (比特/符号） 其中， max为系统连接矩阵最大特征值。证明：（见教材）,10.2.2 等时长符号有约束信道的容量,设一个有约束系统的标号图。如图所示，其中0,1符号等时长,写出系统的连接矩阵和特征方程，并求d=1时有约束信道的容量。 解：令d=1则 （*）得：信道容量 令 得（比特/符号）,特征方程： 设信源符号 的时间长度分别为 ，其中每个是某单位时长的整数倍，方程 称为系统的特征方程。 定理1021：等时长有约束信道的容量等于系统连接矩阵最大特征值的对数。C=log2 max (比特/符号）,10.2.3 不等时长符号无约束信

10、道的容量,在摩尔斯电码中，“点”、“划”、“空”，的时间长度分别为（其中为单位时长），求无约束信道的容量。解 列出特征方程为求解可得 ， 比特信道容量 比特/单位时长,将前例中的标号图化简成一个状态，然后求无约束信道的容量。 解 将例10. 2. 2中的标号图中的1，2，d状态节点吸收可得到如图所示所对应的特征方程为 与（*）式完全相同。故所求结果与例10. 2. 1相同。,定理10. 2. 3 设 为所允许的从状态i到状态j的第s符号的时长,则信道容量 为下面方程的最大实根：其中,证明：（参见教材）,10.2.4 不等时长符号有约束信道的容量,定理10.2.3可以把定理10.2.1与定理10

11、.2.2两种情况作为特例来处理。例如，当等时长符号时，设 ，方程 变为 ，这与 等价。对于无约束情况， 中相当于只含一项，而 包含了所有符号的时长，这归结于,在例10.2.2中引入两个“空”后不能再接“空”的约束，求信道容量。 解：记 =“空空”， =“空”， =“点划”，则有 代入方程 ，得 展开得 求解可得： 信道容量,10.3 有约束序列的性质,主要内容,10.3.1 信道对传输序列的约束,信道的约束通常可以分为时域约束和频域约束。时域约束：对于采用峰值检测技术的系统，要求在传输二电平符号序列中两个“1”（高电平）符号之间的“0”游程的长度不能太小，以减小码间干扰；也不能太大，以利于同步

12、信息的提取。与这类要求对应的编码是游程长度受限（RLL）码。 对于采用部分响应最大似然检测技术的系统，不但要求数据序列中两个“1”符号之间的“0”游程不能太长（以利于同步信息的提取和增益控制），而且还要求序列的奇偶交织子序列中的“0”游程也不能太长（以减小记忆长度防止恶性差错传播）。与这类要求对应的编码是部分响应最大似然（PRML）序列编码。 以上两种约束都是时域约束。,频域约束：频域约束指的是，要求传输的序列满足一定的频谱特性，以便与信道的频谱特性相匹配或减小对系统某些频率范围的干扰。例如，要求序列不含某一个特殊频率，这就是频谱零点限制。在大多数情况下要求传输的序列不含直流。这种序列称为无直

13、流序列或直流平衡序列。本节所介绍的游程受限序列和部分响应最大似然序列都是时域受限序列，它们的信道容量计算和编译码器的设计方法都是类似的。,10.3.2 游程长度受限序列（RLL）,在RLL序列中规定了符号游程的最小和最大长度。因为RLL序列与称做（d，k）序列有密切关系。我们先介绍（d，k）序列。（d，k）序列：一个（d，k）受限序列，简称（d，k）序列，同时满足下列两个条件： d约束 两个逻辑“1”被长度至少为d的“0”游程所分隔； k约束 “0”游程的最大长度为k。 如果仅满足（1），则称d受限（k= ），并称为d序列。,（d，k）序列的容量,一个（d，k）序列的标号图如图所示： 设 为（

14、d，k）序列连接矩阵 ，则D为 矩阵，且将上图化简，只剩下状态1，则图中所包含的符号长度分别为d+1，k，k+1，可以证明，此（d，k）序列的特征方程为： （d，k）序列的容量也由C=log2 max确定,NRZI 码,在实际应用中，RLL序列通常按如下步骤产生： 首先按RLL序列的要求产生（d，k）序列， 再将（d，k）序列变成NRZI码，从而构成RLL序列。NRZI（Non-Return to Zero-Inverted）码，实际上是一种差分编码。设 分别为编码器的输入、输出与状态序列，NRZI编码器的运算关系如下：其中， 为初态，可预先给定。,已知一（d，k）序列为 0 1 0 0 0

15、1 0 0 1 0 0 0 1 1 0 1 ， 求对应的NRZI码，设编码器初态为1。 k = 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 k = 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 1 k = 1 1 -1 -1 -1 -1 1 1 1 -1 -1- 1 -1 1 -1 -1 1 # 很容易证明，由d，k序列转换成的RLL 序列的游程最小长度和最大长度分别为d+1和k+1。在本例中，（d，k）=（0，3），所以在输出的NRZI码序列中，最短的同符号游程长度为2，最大的同符号游程长度为4。,NRZI编码器,NRZI编码器可用状态转移图或网格图来描述， 状态转移图 网格图 图中，编码器有两个状态、4条边，每条边标号的左右两部分分别表示在该边的起始状态下编码器的输入与输出。例如，在状态0，当输入为1时输出为+1，然后转到状态1。,