有噪信道编码定理

✍ dations ◷ 2025-07-11 16:00:24 #信息论,数学定理

在信息论里,有噪信道编码定理指出,尽管噪声会干扰通信信道,但还是有可能在信息传输速率小于信道容量的前提下,以任意低的错误概率传送数据信息。这个令人惊讶的结果,有时候被称为信息原理基本定理,也叫做香农-哈特利定理或香农定理,是由克劳德·艾尔伍德·香农于1948年首次提出。

通信信道的信道容量或香农限制是指在指定的噪音标准下,信道理论上的最大传输率。

根据香农1948年的陈述,本定理描述了在不同级别的噪音干扰和数据损坏情况下,错误监测和纠正可能达到的最高效率。定理没有指出构造错误监测的模型,只是告诉大家达到的最佳效果。香农定理可以广泛应用在通信和数据存储领域。本定理是现代信息论的基础理论。香农只是提出了证明的大概提纲。1954年,艾米尔·范斯坦第一个提出了严密的论证。

香农定理假设一个有噪音的信道,信道容量为,信息以速度传送,如果

那么就存在一种编码技术使接收端收到的错误达到任意小的数值。这意味着理论上,有可能无错误地传送信息直到达到速度限制。

反过来同样重要。如果

那么想达到任意小的错误率是不可能实现的。因此,在传送速度超过信道容量的时候,可靠传输信息是不能被保证的。定理并没有指出在什么特殊情况下速度和容量相等。

简单的流程如"重复发送数据3遍,用一个投票系统在数据不一样的时候选择3个里面相同的那两个的值"是低效的错误纠正的方式,不能保证数据块能完全没有错误地传送。先进一些的技术如里德-所罗门码编码技术和更现代一些的Turbo码、LDPC码等编码技术更逼近香农限制,但是计算复杂度很高。

定理(香农,1948年):

和信息论的其它主要结果一样,噪音信道编码定理包括一个可以实现的结果和相应的相反的结果。这两个组成部分中间有一个界线。在本案例中,可以通过有噪音的信道的可能速度的集合和相应边界显示出这是一个紧密边界。

下面的证明框架只是已有的许多种不同证明方法中的一种而已。

下面这个可实现性的证明是使用渐近等同分割特性(Asymptotic equipartition property(英语:Asymptotic equipartition property) - AEP)方法。另一种信息论常用证明方法是错误列举法(Error Exponent(英语:Error Exponent))。

两种证明方法都使用随机编码参数来构造信道。这样的目的是减少计算的复杂度,同时仍旧可以证明在速度低于信道容量的时候,存在误码率在可接受范围甚至是接近于理想的无失真的编码方式。

采用AEP相关的参数,一个指定的信道,长度为n的源字符串 X 1 n {\displaystyle X_{1}^{n}}

我们可以说两个序列 X 1 n {\displaystyle {X_{1}^{n}}} ,如果它们是基于上述定义的匹配序列集合。

步骤

这个流程产生的错误可以分成两个部分:

定义: E i = { ( X 1 n ( i ) , Y 1 n ) A ϵ ( n ) } , i = 1 , 2 , . . . , 2 n R {\displaystyle E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\epsilon }^{(n)}\},i=1,2,...,2^{nR}}

作为消息1发送出去,消息i作为匹配的消息接收到的结果。

我们可以发现如果信道 R < I ( X ; Y ) {\displaystyle R<I(X;Y)} ,n变为无穷大,错误的可能性将降为0。

最后,假设平均的编码方式是“好”的话,我们知道存在一个编码方式的效率比平均的值要好,因此可以满足我们在有噪音的信道低误码率的要求。

假设一种编码有 2 n R {\displaystyle 2^{nR}} 个编码词语。W假设为在这个集合上的一个索引。设 X n {\displaystyle X^{n}} Y n {\displaystyle Y^{n}} 分别为编码词和接收到的词。

这些步骤的结果是 P e ( n ) 1 1 n R C R {\displaystyle P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}} 。当块的长度变为无穷大,如果R比C大,我们得到 P e ( n ) {\displaystyle P_{e}^{(n)}} 不可能降到0。只有在R比C小的情况下,我们可以得到任意低的误码率。

强逆定理证明由Wolfowitz于1957年提出。,证明归结于证明如下不等式,

其中 A {\displaystyle A} 为有限的正常数。当 n {\displaystyle n} 变为无穷大的时候,弱逆定理证明错误的可能性不可能变成0,而强逆定理证明了错误以指数方式趋向于1。因此, C {\displaystyle C} 是可靠连接和不可靠连接的临界点。

我们假设信道是无记忆的,但是随着时间的变化,传输的可靠性是变化的。发送端和接收端一样工作正常。这样信道容量如下

针对每个不同的信道,计算出取得该信道容量似的分布,以求得上式中的最大值,这样 C = lim inf 1 n i = 1 n C i {\displaystyle C=\liminf {\frac {1}{n}}\sum _{i=1}^{n}C_{i}} ,信道i的容量为 C i {\displaystyle C_{i}}

证明方法和上面信道编码定理几乎一样。在指定的信道里面,每一个符号的选择是随机的,编码方式也是随机的,采用渐近等同分割特性(AEP)方法来定义变化的无记忆信道的参数集。

1 n i = 1 n C i {\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}C_{i}} 不收敛时,下极限开始起作用。

相关

  • 荷兰语荷兰语(英语:Dutch),又称尼德兰语(荷兰语:Nederlands),属于印欧语系日耳曼语族的西日耳曼语支,主要通行于荷兰,在比利时与苏里南有六成人口使用(这三个国家共同组成荷兰语联盟);也是荷兰
  • 鸟虫书陶文 ‧ 甲骨文 ‧ 金文 ‧ 古文 ‧ 石鼓文籀文 ‧ 鸟虫书 ‧ 篆书(大篆 ‧  小篆)隶书 ‧ 楷书 ‧ 行书 ‧ 草书漆书 ‧  书法 ‧ 飞白书笔画 ‧ 
  • 魔法魔法,是一种在现实中尚未经过证实的,催动并控制能量的方法,大多牵涉具神秘色彩的力量或是行为。广义而言的魔法(包括下文所提及的仙术、妖术等)多为依附在特定信仰体系之下,为信仰
  • 打酱油打酱油是源自中国大陆的汉语网络用语,原意是去商店购买酱油,后来衍生出两种用法:一个传统意思,“某某人的孩子都可以打酱油了”是指孩子很大了,可以帮着做家务,其父母不再年轻。另
  • 多变量分析多变量统计分析(Multivariate Statistical Analysis),又称多元统计分析,简称多变量分析,为统计学的一支,常用于管理科学、社会科学和生命科学等领域中。多变量分析主要用于分析
  • 王清任王清任(1768年-1831年),又名全任,字勋臣,清代直隶玉田(今河北省玉田县)人,清朝名医。王清任自幼习武,是武庠生。青年时曾考取武秀才,后捐资得千总衔。后改习岐黄,以医为业。于北京开设药
  • 奥克兰大学奥克兰大学(简称:奥大,毛利语:Te Whare Wānanga o Tāmaki Makaurau,英文:The University of Auckland)始建于1883年,位于新西兰最大城市奥克兰市,有7个校区。它不仅是该国最重要的
  • 里察马拉尊最高元首后东姑阿兹纱阿蜜娜(英语:Tunku Azizah Aminah Maimunah)副最高元首苏丹纳兹林沙(马来语:Sultan Nazrin Muizuddin Shah ibni Sultan Azlan Muhibbuddin Shah)副首相(不设
  • 括苍山括苍山,中国浙江省中部的一条山脉,为灵江和瓯江的分水岭。括苍山山区面积约7000平方公里,和雁荡山同为福建洞宫山脉向东北伸展而成。括苍山脉形成于中生代晚期,总体上表现为一个
  • Masson三色染色法马森三色染色法(Masson's trichrome stain),是一种用于组织学的染色方法。从皮埃尔·马森(英语:Pierre Masson)(1880–1959年)的原始配方开发而来的新配方具有不同的特定应用,但都适