有噪信道编码定理

✍ dations ◷ 2024-09-20 10:54:59 #信息论,数学定理

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

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

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

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

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

反过来同样重要。如果

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

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

定理（香农，1948年）：

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

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

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

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

采用AEP相关的参数，一个指定的信道，长度为n的源字符串 $X_{1}^{n}$ ：

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

步骤

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

定义： $E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\epsilon }^{(n)}\},i=1,2,...,2^{nR}$ $E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\epsilon }^{{(n)}}\},i=1,2,...,2^{{nR}}$

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

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

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

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

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

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

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

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

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

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

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

相关

The Lancet《柳叶刀》（The Lancet），是世界上最悠久及最受重视的同行评审医学期刊之一，主要由爱思唯尔出版公司发行，部分与里德·爱思唯尔集团协同出版。1823年由汤姆·魏克莱（英语：Thomas Wak
吉雷松吉雷松（Giresun）是土耳其的城市，也是吉雷松省的首府，位于该国北部，距离特拉布宗175公里，面积317平方公里，海拔高度10米，受副热带湿润气候影响，每年平均降雨量1,269毫米，2010年人口96,9
溶血性尿毒综合症溶血性尿毒综合征（英语：Hemolytic-uremic syndrome, HUS）是一种由于溶血性贫血（Hemolytic anemia）而引发的急性肾损伤（Acute kidney injury）和血小板数量下降综合征。病因不明，发病
攻占巴士底狱攻占巴士底监狱（法语：Prise de la Bastille）发生于1789年7月14日，巴士底狱被巴黎市民攻下和占领。此监狱是巴黎的一座中世纪城堡和监狱，被认为是法国封建专制统治的象征。攻占巴
机械唯物论机械唯物主义（Mechanistic Materialism，亦称形而上学唯物主义、机械唯物论）是一个马克思主义哲学专有名词。马克思主义理论家认为机械唯物主义是以自然科学为基础，使用机械力学
三大都会地带三大都市圈是一种对国家三个重要都会区的合称，通常是该国发展程度最高的经济核心区域，各都会区的中心都市也是该国内的区域核心。可以指：
溶剂壳在物理化学中，溶剂壳（Solvation shell）为一种用来描述溶剂化的结构。溶剂壳为一种任何化学物质像溶剂一样，围绕着溶质物质的现象。当溶剂为水时，所形成似壳的现象，通常会被称为水
尾随尾随是一种常见的社会工程学手法。通常是指尾随者利用另一合法受权者的识别机制，通过某些检查点，进入一个限制区域。该行为可能是合法或非法的、授权的或未经授权的，视情况而定
无毛猫斯芬克斯猫（Sphynx）又称加拿大无毛猫。这种猫是由于基因突变而产生的品种。体重3.5到7公斤，肌肉发达，毛发稀疏，皮肤皱褶似羚羊皮。头部棱角分明。微呈三角型。眼大呈柠檬状，多数呈
一氟化碳一氟化碳（CF、CFx或(CF)x），也被称作聚合碳一氟化物(PMF)，氟化聚合碳，聚(一氟化碳)，以及氟化石墨。在高温下将氟气与石墨、焦炭或热解碳粉反应可以生成一氟化碳。一氟化碳是高