141035013季秋峰离散无噪声系统

离散无噪声系统电子与通信工程141035013季秋峰一、离散无噪声信道离散信道传送选择序列，可以出现特定序列，电传打字机的持续时间相同，若每个符号表示5比特信息，系统每秒传送n个符号，那信道的容量为5n比特/秒。但这只是最大可能速率，实际速率能否达到这一最大值，取决于向信道馈送信息的信源。定义：离散信道的容量CTTNCT)(loglim式中，N（T）是指在允许出现的信号中，持续时间为T的信号数目。假定允许出现信号S1，…，Sn的所有序列，而且这些符号的持续时间为t1，…，tn。信道容量是多少呢？如果N(t)表示持续时间为t的序列数，则有：N（t）=N（t-t1）+N（t-t2）+...+N（t-tn）该总数等于以S1,S2,...,Sn结尾的序列数目之和，这些数目分别为N（t-t1），N（t-t2），...，N（t-tn）。由有限差分中一个众所周知的结果可知，对于大的t值，N（t）趋近于tX0，其中X0是以下特征方程的最大实数解：1...21ntttXXX因此，C=logX0在对允许出现的序列设定了限制时，仍然能够获得这一类型的差分方程，并由该特征方程得C。定理1：设)(sijb是指在状态i下允许出现并导致状态j的第s个符号的持续时间，则信道容量C等于logW，其中W为以下行列式方程的最大实根：0)(ijsbsijW其中，当i=j时，ij=0，否则，等于0。二、离散信源我们可以认为离散信源是逐个字符地生成消息。它将会根据特定概率值选择相继符号，这些概率值通常取决于之前的选择和所考虑的特定符号。如果一个物理系统或者一个系统的数学模型，在一组概率的控制下生成符号序列，则这种系统或模型称为随机过程3。因此，我们可以考虑用随机过程表示离散信源。相反，任何一个随机过程，只要它生成的离散符号序列是从有限集合中选出的，则可以将其看作离散信源。三、英文的近似序列为了直观地感受这一系列过程是如何近似模拟一种语言的，构造了英文的一些典型近似序列，在所有情况下，我们假定“字母表”中有27个符号——26个字母和一个空格。1.零阶近似（符号的选择相互独立，概率相等）。XFOMLRXKHRJFFJUJZLPWCFWKCYJFFJEYVKCQSGHYDQPAAMKBZAACIBZLHJQD。2.一阶近似（符号的选择相互独立，但其概率与英文文本中相同）。OCROHLIRGWRNMIELWISEULLNBNESEBYATHEEIALHENHTTPAOOBTTVANAHBRL。3.二阶近似（英文中的二连字结构）。ONIEANTSOUTINYSARETINCTORESTBESDEAMYACHINDILONASIVETUCOOWEATTEASONAREFUSOTIZINANDYTOBESEACECTISBE。4.三阶近似（英文中的三连字结构）。INNOISTLATWHEYCRATICTFROUREBIRSGROCIDPONDENOMEOFDEMONSTURESOFTHEREPTAGINISREGOACTIONAOFCRE。5.一阶单词近似。我们接下来不再继续给出四连字结构，……，n连字结构，而是直接由三连字跳到以单词为单位，这样更容易一些，也更好一些。这里的单词选择是相互独立的，但具有适当的各自频率。REPRESENTINGANDSPEEDILYISANGOODAPTORCOMECANDIFFERENTNATURALHEREHETHEAINCAMETHETOOFTOEXPERTGRAYCOMETOFURNISHESTHELINEMESSAGEHADBETHESE。6.二阶单词近似。单词转换概率与英文中一致，但没有包含其他结构。THEHEADANDINFRONTALATTACKONANENGLISHWRITERTHATTHECHARACTEROFTHISPOINTISTHEREFOREANOTHERMETHODFORTHELETTERSTHATTHETIMEOFWHOEVERTOLDTHEPROBLEMFORANUNEXPECTED。四、马尔可夫过程的图形表示上文所述类型的随机过程在数学上称为离散马尔可夫过程，一般情况可以描述如下：一个系统存在有限种可能“状态”S1，S2，...,Sn。此外，还有一组转换概率pi（j），也就是当系统为状态Si，接下来进入状态Sj的概率。为使此马尔可夫过程表示信源，只需要假定每次从一状态转换到另一状态时，生成一个字符即可。这种状态对应于先前字符产生的“影响残余”。五、各态历经与混合信源如果马尔可夫过程的图形具有以下两个性质，则相应的过程是各态历经的：1.图中不存在这样两个相互分离的A、B部分：根据箭头的方向，无法沿着图中的连线，由A部分的交点到达B部分中的交点，也无法由B部分的交点到达A部分的交点。2.如果图中有一系列连线闭合起来，而且连线上的所有箭头都指向相同方向，将这些闭合线称为“回路”。一个回路的“长度”就是其中连线的数目。因此，在图5中，BEBES是一个长度为5的回路。需要满足的第二个性质是，图中所有回路长度的最大公约数为1。六、选择，不确定性和熵如果存在这样一种度量，比如说H（p1,p2,...,pn），那要求它具有以下性质是合理的：1.H应当关于pi连续。2.如果所有pi都相等，即pi=1/n，则H应当是n的单调增函数。如果事件的可能性相等，那可能事件越多，选择或者说不确定性也更多。3.如果一项选择被分解为两个连续选择，则原来的H应当是各个H值的加权和，最终结果将拥有和前面一样的概率值。定理2：唯一能够满足上述三条假定的H具有如下形式：niiippkH1log其中K是一个正常数。七、信源的熵定理3：给定任意0和0，我们可以求得一个N0，使得任意长度0NN的序列都属于以下两个类别之一：1.一个总概率小于的集合。2.不属于上述集合的所有序列，这些序列的概率都满足不等式：NNP1log换言之，当N很大时，我们几乎可以肯定NP1log会非常接近于H。定理4：HNqnN)(loglim其中，q不等于0和1。定理5：设)(iBp是信源中发出的一个符号序列iB的概率。令iiiNBpBpNG)(log)(1其中，该求和运算是针对所有包含N个符号的序列Bi执行。因此，GN是N的单调减函数，且：NNHGlim定理6：设),(jiSBp是序列iB之后跟有符号jS的概率，)(/),()(ijijBBpSBpSpi是出现iB之后出现jS的条件概率。令：jijBjiNSpSBpFi,)(log),(其中，该求和运算是针对所有包括N-1个符号的块Bi及针对所有符号jS执行的。则FN是N的单调减函数，1)1(NNNGNNGFNnnNFNG11NNGF及HFnNlim八、编解码处理的表示定理7：一个有限状态转换器在由有限状态的统计信源驱动时，其输出是一个有限状态统计信源，其熵（每单位时间）小于或等于输入的熵。如果转换器是非奇异的，则两者相等。定理8：将一套约束条件看作一个信道，设其容量为WClog。如果我们指定：)()(sijlijsijWBBp其中，)(sijl是由状态i导致状态j的第s个符号的持续时间，Bi满足：jsljisijWBB,)(则，H为最大值，并等于C。九、无噪声信道的基本定理定理9：设一个信源的熵为H（比特/符号），一个信道的容量为C（比特/秒）。有可能采用某种方式对该信源的输出进行编码，从而可以在该信道上以HC符号/秒的平均速率上进行传送，其中为任意小。不可能以大于HC的平均速率进行传送。