论文标题：二进制信道的代数信息论及其应用

||理论计算机科学电子笔记158（2006）289-306www.elsevier.com/locate/entcs二进制信道的代数信息论Keye Martin1 Ira S.莫斯科维茨2 Gerard Allwein3高保证计算机系统中心，代码5540美国海军研究实验室华盛顿特区20375摘要本文研究了二元信道幺半群的代数结构，并利用文[3]中的运算证明了它在单位区间上对偶同构于区间域我们证明了一个二元信道的容量是Scott连续的，作为区间域上的一个映射，并且它对二元信道的任何最大交换子幺半群的限制是单位区间上的一个序这些结果使我们能够解决一个重要的公开问题，在隐通道的分析：一个可证明的正确的方法注入噪声到隐通道，这将减少其容量到任何水平所需的方式，从业者是自由插入噪声在系统中的任何一点。保留字：信息论，域理论，隐通道，幺半群1介绍本文中的信道是指离散的、无记忆的非定时信道[5]。 在二进制通道中，发送方尝试传输比特（"0“或”0“），a“1”）到接收器。然而，由于噪声，有时“0”会作为“1”到达，反之亦然。这种噪声在信息论中通过噪声矩阵来建模，该噪声矩阵完全由两个概率确定：a=P（0 0），当发送“0”时接收到“0”的概率因此，信道的噪声矩阵可以写成1电子邮件地址：kmartin@itd.nrl.navy.mil2电子邮件地址：moskowitz@itd.nrl.navy.mil3电子邮件地址：allwein@itd.nrl.navy.mil1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.04.015290K. Martin等人/理论计算机科学电子笔记158（2006）289∈作为一对（a，b）[0， 1]2.在信息论文献中似乎没有注意到，噪声矩阵的集合在与单位矩阵（1， 0）作为幺半群的单位的矩阵乘法下形成幺半群。但是这个幺半群结构仍然很有趣。本文主要我们将对此进行研究，并利用我们的研究结果来开发减少隐蔽信道威胁的方法。正如我们将要说明的那样，把注意力限制在我们所说的非负信道（即噪声矩阵满足a≥b的信道）上并没有失去一般性。由此得到的非负通道幺半群N具有一个美丽的性质，即它与区间域I[0，1]对偶同构，其中二元运算在[2]和[3]中独立发现通过解释-将二进制信道的容量作为I[0，1]上的函数，我们发现了仅这个结果就为信息论中经常使用的几个直觉提供了形式上的证明，但由于不等式和公式，即使在二元情况下也过于复杂，无法有效地操作，因此这些直觉的实际证明往往要么困难，要么被省略但这一结果也使我们能够解决一个重要的公开问题，在隐蔽通道的分析。隐蔽信道是一种信道，其中两方通过使用系统的某些元素以不同于它们最初设计的方式进行通信。当在高安全性设备或系统中发现隐蔽通道时，该通道的容量是衡量其构成的威胁的指标。能力越大，威胁就越大。理想情况下，人们希望简单地完全消除隐蔽通道。然而，这通常是不可能的，因为它通常需要将系统性能降低到不可接受的水平。因此，如果我们遇到一个隐藏的通道，其容量太高，我们可以希望的最多的一般是一种方法，减少其容量的某种程度上，系统的性能是保留，但由该通道构成的威胁是succiently减少。具体地说，给定一个隐通道，其容量需要降低到某个较低的水平r，我们如何规范地计算一个噪声矩阵（a，b），其注入到给定的隐通道中将原始通道的容量降低到r？注意，先验问题没有正则解，因为我们有一个方程C（a，b）=r，但有两个未知数（a，b）。然而，噪声矩阵的代数和域理论结构恰恰提供了这样一种方法，如果你喜欢的话，这是一个“额外的方程”。第一，每个不同于单位元的非负通道存在于唯一的极大交换子幺半群中。虽然有无限个容量为r的噪声矩阵，但在由通道确定的最大交换子幺半群中只有一个原因是我们可以证明K. Martin等人/理论计算机科学电子笔记158（2006）289291·b'b⎝-∈·容量对由通道确定的最大交换子幺半群的限制是[0，1]的序同构我们还给出了一个可证明正确的算法来计算这个独特的通道。因为这个独特的通道与原始通道交换，所以从业者可以选择在隐蔽通道的开始或结束时将噪声注入隐蔽通道，从而在将噪声注入隐蔽通道时给予高保证设备的审查者2噪声矩阵幺二进制信道的噪声矩阵M模拟噪声对通过信道发送的数据的影响。如果数据根据分布x通过通道发送，则输出分布为y=x M。该噪声矩阵由下式给出：M=aa其中，a是当发送第一个符号时接收第一个符号的概率，b是当发送第二个符号时接收第一个符号的概率，并且dx：=1x为x[0，1]。 我们用y（a，b）来表示它的噪声矩阵。噪声矩阵的集合由单位平方[0， 1]2描述。两个噪声矩阵的乘积为：（a，b）·（α，β）=（a（α−β） +β，b（α−β） +β）=α（a，b） +β（a<$，<$b）其中右边的表达式使用标量乘法和向量加法。[0， 1]2上的恒等式是1：=（1， 0）。行列式是typedet的函数：（[0，1]2，·）→（[-1，1]，·）定义了一个由n个幺半群构成的同态m令人高兴的是，我们发现det（a，b）=a-b对于任何噪声矩阵（a，b）∈[0， 1]2。定义2.1当det（a，b）>0时，通道（a，b）被称为正通道，当det（a，b）0时，通道（a，b）被称为负通道，当det（a，b）= 0时，通道（a，b）被称为零通道<如果通道为正或零，则通道是非负的注意，det（a，b）∈（0， 1]表示正通道，det（a，b）∈[−1，0）表示负通道。正通道的集合是一个子幺半群，非负通道的集合也是一个子幺半群;行列式函数是一个同态从非负通道到（[0， 1]，）。为了我们的目的，所有通道都可以假设为非负的，如下所示。 的信息量292K. Martin等人/理论计算机科学电子笔记158（2006）289- -∈a−b2可以通过信道（a，b）发送的信息由其容量给出C（a，b）=supx∈[0，1]H（（a−b）x+b）−xH（a）−（1 −x）H（b）可以证明[4]，这定义了单位平方[0， 1]2上的连续函数，由下式给出：C（a，b）=a<$H（b）− <$bH（a）+log.H（a）−H（b）a−b.a<$H（b）−<$bH（a） bH（a）−aH（b）<$=log22a−b+2a−b其中C（a，a）：= 0和H（x）=x log2（x）（1x）log2（1x）是基2熵。但是任何负通道都可以使用映射扭曲（a，b）：=（b，a）：引理2.2扭曲映射将负通道转换为正通道并保持容量。证据 为了证明扭曲映射保持容量，只需要非定时容量C（a，b）= C（b，a）的对称性质。Q存在大量将负通道映射到正通道并保持容量的映射。然而，扭曲映射的区别在于，它对应于将0重命名为1和将1重命名为0的平凡行为。因此，我们可以不失一般性地假设通道是非负的。因此，我们研究了非负通道幺半群。定义2.3将n个可压缩信道的m表示为（N，·，1）。3交换性与恒等式不同的每个通道x=（a，b）N位于将恒等式1连接到对角线的唯一线上。在参数形式中，这条线πx：[0，1]→N由下式给出：πx（t）=（1−t）·（0x， 0x）+t·（1， 0）对于t∈[0，1]，其中（0x， 0x）是由下式给出的对角线上的点：B0x：=1 −det（x）注意，对于用于定义0x的特定x，我们有（πxπdet）（x）=x一加二K. Martin等人/理论计算机科学电子笔记158（2006）289293−、、→→所以这条线从π（0）=（0x， 0x）到π（a b）=x，然后到恒等式π（1）= 1。以下是迄今为止的情况：负（0，1）（一、一）、、、积极渠道，，渠道，πx（t）=（1−t）·（0x， 0x）+t·（1， 0）（0， 0），、、X x（0， 0）............（1， 0）身份定义3.1通过恒等式将x∈N\{1}连接到对角线的直线表示为π x：[0，1]N。我们定义π1：[0，1] N为将恒等式连接到（1/2，1/2）的直线。引理3.2对任意x∈N和s，t∈ [0，1]，有π x（s）·π x（t）= π x（st）.证据设（a，b）=πx（s）=（（1−s）0x+s，（1−s）0x）且（α，β）=πx（t）=（（1−t）0x+t，（1−t）0x）.然后πx（s）·πx（t）=（a，b）·（α，β）=（a（α−β）+β，b（α−β）+β）=（1−s）0x+s）·t+（1−t）0x，（1−s）0x·t+（1−t）0x）=（（1−st）0x+st，（1−st）0x）=πx（st）对于任何s，t∈[0， 1]。QLemma3. 3两个元素s（a，b），（α，β）∈N共同i ∈βa<$=bα<$.证据 如果我们写出每一个产品（a，b）·（α，β）=（a（α−β）+β，b（α−β）+β）（α，β）·（a，b）=（α（a-b）+b，β（a-b）+b）那么我们可以看到（a，b）和（α，β）可换当且仅当β−βa=b−bα和bα+β=βa+b惠βa<$=bα<$且βa<$=bα<$294K. Martin等人/理论计算机科学电子笔记158（2006）289这就完成了证据。Q幺半群M中的交换子幺半群S是极大的，如果对所有S∈T的交换子幺半群T，我们有S=T.K. Martin等人/理论计算机科学电子笔记158（2006）289295∈定理3.4(i) 两个通道x，yN通勤i有一条线穿过x和y，并将恒等式连接到对角线上。(ii) N的最大交换子幺半群是连接对角形和恒等式4的线.(iii) 行列式是极大交换子幺半群与（[0，1]，·）之间的同构.证据（i）设x=（a，b），y=（α，β）.在不失一般性的情况下，我们可以假设两者都不是恒等式。然后我们有πx=πy惠0x=0y惠βa<$=bα<$惠x·y=y·x这意味着x和y是交换的，并且它们由将单位元连接到对角线的线连接。注意，第一个等价成立是因为一条直线由两个点唯一确定，第二个等价成立是因为简单的算术，最后一个等价成立是因为引理3.3。(ii) 根据引理3.2，πx[0，1]在乘法下是闭的。通过（i），它是交换子幺半群。设S是交换子幺半群，πx[0，1]≠S. 如果y∈S，则它与x交换，因此通过（i），我们必须使y∈πx[0， 1]。因此，πx[0，1]是一个极大交换子幺半群。 相反，任何交换子幺半群必须包含在某个πx[0，1]中，因此最大的一个必须等于πx[0，1]。(iii) 行列式将πx[0，1]满射映射到[0，1]上，因为对于所有t∈[0，1]，det（πx（t））=t。然而，这也意味着当限制为πx[0， 1]时它是单射的：det（π x（s））= det（π x（t））π s = t π x（s）= π x（t）。这就完成了证明。Q由（ii）则极大交换子幺半群为{πx[0， 1]：x=（p，p），p∈[0，1]}。由（iii），任意两个极大交换子幺半群同构.例3.5Z通道{（p，0）：p∈ [0，1]}和{（1，p）：p∈ [0，1]}是极大l-连通子幺半群。 二进制信道s{（p′，p）：p∈[0，1/2]}也构成一个极大交换子幺半群.我们给出N的极大交换子幺半群的一个纯代数刻画。4更多是真的。最大交换子幺半群也是“最大的”，因为它们包含任何交换子幺半群，它们相交于一点而296K. Martin等人/理论计算机科学电子笔记158（2006）289{\displaystyle {}是有向的，如果（<$x，y∈S）（<$z∈S）x，y±z.上确界SofSP是定义3.6m ∈ M中的右zero是一个元素，它满足x·0=0，对所有x∈M。M中右零元素的集合记为0（M）。提案3.7(i) N中的右零元素的集合是0（N）={（a，b）：det（a，b）= 0}。(ii) 对于任何xN1，存在唯一的0x0（N），它与x，由下式明确给出：其中x =（a，b）。B0x=1−det（x）(iii) N的极大交换子幺半群与{Z（x）：x∈0（N）}其中Z（x）={y∈N：x·y=y·x}是与x可交换的元素的集合。证据（i）如果det（α，β）= 0，则α=β，因此对于元素x=（a，b），我们有x·（α，β）=（a，b）·（α，α）=（a·0+α，b· 0+α）=（α，α）这意味着（α，α）∈0（N）。反之，设x=（α，β）∈0（N），则（1，1）·x=x。但是（1，1）·x=（α，α），这意味着det（x）= 0。(ii)由定理3.4（i），我们已经知道0x与x交换，因为它位于通过x并将恒等式连接到对角线的直线πx如果存在另一个0y∈ 0（N）与x交换，则根据定理3.4，0y也位于线πx上，这意味着0y与0x交换。但后来0x= 0y· 0x= 0x· 0y= 0y这证明了它的独特性㈢立即。Q几何上，集合0（N）是单位正方形中的对角线，而集合Z（x）是通过x将恒等式连接到对角线的直线。请注意代数和信息论之间的以下美丽联系：二进制通道x具有正容量ix不是所有噪声矩阵的幺半群中的右零元素。4域Let（P，±）是一个偏序集或poset[1]. 一个都没有。ptysubsetSPK. Martin等人/理论计算机科学电子笔记158（2006）289297.S与y±对于某些s∈S，我们有x±s。当它存在时，它的上界最小。dcpo是一个偏序集，其中每个有向集都有一个上确界。为了我。dcpoD的元素x，y，我们将xy表示为每个有向子集定义4.1设（D，±）是dcpo。我们设定• ↓x：={y∈D：yx}和↑x：={y∈D：xy}• ↓x：={y∈D：y±x}和↑x：={y∈D：x±y}称D是连续的，如果对每个x ∈ D，↓x是有向的，有上确界x。定义4.2定义域D的基是一个子集B<$D，使得B<$↓x有向于上确界x，对所有x∈D。一个整环是ω-连续的，如果它有一个可数基。例4.3单位区间I[0， 1]={[a，b]：a，b∈[0， 1]a≤b}逆包含[a，b]±[c，d]是ω-连续dcpo：• 对于有向S∈I[0，1]，S=S，• 我J惠J惠int（I），以及• {[p，q]：p，q∈Q<$[0， 1]p≤q}是IR的可数基.定义域I [0，1]称为区间定义域。注意int（I）指的是区间I在其相对欧几里得拓扑中的内部，因此对于a >0和b1，int[a，b] =（a，b），而对于b1，int[0，b] = [0，b），对于a >0，int[a，1] =（a，区间域I[0，1]有一个自然的幺半群结构，它至少在两个不同的场合被独立地发现：Escardo在[2]中研究实PCF中的积分时，以及第一作者在[3]中研究量子力学中的熵时。例4.4对I[0， 1]的二进制运算[a，b]<$[c，d]= [a+c·（b-a），a+d·（b-a）]是结合的，有单位区间[0， 1]作为单位元和许多其他互属性。度量μ [a，b] = b−a是从（I[0，1]，）到o（[0，1]，·）的同态。298K. Martin等人/理论计算机科学电子笔记158（2006）289⊥I[0， 1]和二进制通道之间的联系很容易证明，但仍然令人大开眼界：定理m4.5自然映射<$：（N，·，1）→（I[0，1]，<$，<$）由下式给出：n（a，b）= [b，a]是幺半群的对偶同构，其中μ_（1）= μ_（1），μ_（1）= det。证据 映射将非负通道发送到[0，1]的紧凑间隔中。对于（a，b），（c，d）∈N，<$（（a，b）·（c，d））=<$（a（c-d）+d，b（c-d）+d）=[b（c-d）+d，a（c-d）+d]=[d，c][b，a]=（c，d）（a，b）因为取1到[0，1]，且有一个由−1[a，b] =（b，a）给出的逆，证明就完成了。Q也就是说，每个非负通道确定扭曲映射下的唯一区间，通道矩阵的乘法恰好是I[0， 1]上的对偶运算，通道矩阵的行列式是其相关区间的长度我们能从中学到什么吗？我们认为域是信息对象的空间，粗略地说，有两种形式：部分和全部。定义域D中的最大元素的集合是max（D）：={x∈D：↑x={x}}是全部元素的例子，而域D中部分元素的典型例子是它的最小元素，当它存在时。最小元素在域D中，是唯一的元素，其中对所有x∈D都有<$x ±x。在I[0， 1]的情况下，最大元素为max（I[0， 1]）={[a，a]：a∈[0， 1]}而最小的元素是= [0， 1]。在信息论术语中，最大元素是零信道，而最小元素是无噪声信道。从系统安全的角度来看，这是非常有意义的。在域理论中，部分元素具有不同程度的不确定性，最大元素是完全确定的，最小元素是最大不确定的。想象一个只有一个隐蔽通道的系统，也许是一个严格受限的子系统然后，信道的容量是系统有多安全的度量，即，它衡量了我们的不确定性，K. Martin等人/理论计算机科学电子笔记158（2006）289299→≤信息只以已知的方式传播。从安全的角度来看，当隐通道是零通道时，我们最确定系统是安全的;当隐通道是零通道时，我们最不确定系统是安全的。考虑到N和I[0， 1]之间的这种联系，我们然后将在I[0， 1]上的阶也定义在N上的阶：定义4.6对于（a，b），（c，d）∈N，（a，b）±（c，d）（a，b）±（c，d）通过承认二元通道的这个新方面，它们的领域-理论方面，学科之间更深层次的联系出现了，正如我们很快就会看到的，允许人们解决目前未知的信息论问题。一个这样的联系是：二进制信道的容量是噪声矩阵的Scott连续定义4.7连续dcpo D上的Scott拓扑以所有形式为↑x（x∈ D）的集合为基。例4.8I[0， 1]中的基本Scott开集是^[a，b]={x ∈ I [0，1]：x ∈ int（[a，b]）}。在N中，这样一个集合形成一个直角三角形，其对角线位于对角线上，但其其他两边被移除。定义域之间的函数f：D E是Scott连续的，如果E中的Scott开集的逆像在D中是Scott开的。这就相当于说[1]f是单调的，（x，y∈D）x±y<$f（x）±f（y），并且它保持有向上确界：f（.S）=.f（S），对于所有有向SD。在证明能力的斯科特连续性之前，让我们从信息理论家的角度来思考这个问题。假设我们有两个二进制通道（a，b）±（c，d）。那么这就意味着（a，b）=[b，a]±从c a，我们可以看到，当发送时，接收到'0'的概率降低将“0”插入“1”的概率300K. Martin等人/理论计算机科学电子笔记158（2006）289≤b d，我们可以看到，当发送“1”时，接收到“0”的概率增加，即“1”被删除的概率也增加。因此，无论发送什么符号，如果通过信道（c，d）发送它，则它将比通过信道（a，b）发送它更有可能被解密换句话说，通道（c，d）中的噪声比通道（a，b）中的噪声多因此，我们预计它的容量较小。在符号中，C（a，b）≥C（c，d）也就是说，我们期望函数C作为从I[0， 1]到单位区间的函数是单调的，其对偶阶为（[0， 1]<$，±），即阶为（<$x，y∈[0， 1]）x±y<$y≤x。但是，由于C已经知道是欧几里德连续的，我们确切地断言容量是从域I[0， 1]到域[0， 1]的Scott连续函数。定理4.9容量C：I[0，1]→[0，1]是Scott连续且严格单调的：x±yC（x）= C（y）x=y对于所有的x，y ∈ I[0，1]。证据因为容量是欧几里德连续的，我们只需要证明它在[0， 1]中的单调性。首先考虑正信道（a，b）I（x，a，b）=h（（a-b）x+b）-xh（a）-（1-x）h（b），其中x是发送第一个输入符号的概率。设a，b，x∈（0， 1）。则（a-b）x+b∈（0， 1），因为00a（a−b）x+b aI=（1−x）·。ln.1−1−ln。1−1ΣΣ0b（a−b）x+b b最后，让我们指出，当a= 1和b= 0时，这些结果也成立为a= 1，I=（1−x）·。ln.1−1−ln。1−1ΣΣ0b（1−b）x+b bK. Martin等人/理论计算机科学电子笔记158（2006）289301∈ ∈/∈∈≤拉瓜∈≥ax一并且对于b=0，I=x ·。ln.1-1 − ln. 1−1> 0现在假设[b，a]±[d，c]。如果b= 1，a= 0或a=b，则无需证明，因为两者相等。则a∈（0，1]，b∈[0，1]，ai=b.但由于[b，a]现在必须是具有正容量的通道，我们还可以假设d[0，1），c（0，1]和c = d。设x（0， 1）.如果a= 1，b= 0，则没有什么需要证明的，因此其中一个必须失败。假设1。则a∈（0， 1）。对于固定的b∈[0，1），我们知道I（x，a，b）随着a. 因为0 I（x，c，d）。由于c d，[d，c]是正容量通道，因此存在一个唯一的x∈（0，1），其中C[d，c] =I（x∈，c，d）。这给出了C[b，a]I（x∈，a，b）> C[d，c]。假设b >0且a∈（0，1]。然后考虑渠道x = [1−a，1−b]和y =[1−c，1−d]，满足x±y。 由于b > 0，1−b<1，所以刚刚证明的结果适用于给出C[b，a]= C（x）>C（y）=C[d，c]这就完成了证据。Q包含在交换子幺半群中的两个通道必须位于从对角线到单位元的直线上。但是我们可以从最接近对角线的点到最接近恒等式的点，首先向右移动（这意味着a增加），然后向下移动（这意味着b减少）。根据最后一个定理，容量只能在这样的运动中增加。这里是形式证明，它揭示了一些非常令人惊讶的事情：在由通道确定的交换子幺半群内，行列式是定性反映容量的同构。命题4.10设π是N的极大交换子幺半群。然后x±y 惠det（x）≥det（y）惠C（x）≥C（y）对任意x，y∈ π.302K. Martin等人/理论计算机科学电子笔记158（2006）289∈≤± ⇔ ≤⇒± ⇔ ≤⇐⎛⎞A=B=±证据 设π（t）是从恒等式到零通道（α，α）0（N）的直线，由下式给出：π（t）=（tα+t<$，tα）首先注意，（s，t∈[0， 1]）s≤t惠π（s）±π（t）如下：π（s）±π（t）惠[sα，sα+s<$]±[tα，tα+t<$]优惠（sα≤tα）（tα+t<$≤sα+s<$）惠（s≤t<$α= 0）（s−t）（1 −α）≤0惠（s≤tα=0）（s≤tα=1）惠s≤t特别地，π是内射的。现在让我们证明x yC（y）C（x）。 方向（从定理4.9可以清楚地看出。假设C（y）C（x）。由于x和y属于极大交换子幺半群，x=π（s）和y=π（t）。 若t s，则x=π（t）<$π（s）=y，由π的内射性.根据定理4.9，C（x）>C（y），这是个矛盾因此，s≤t，得到y±x。为了证明x ydet（y）det（x），我们考虑（）方向，因为另一个方向是明确的。 由于x和y属于极大交换子幺半群，x=π（s）和y=π（t），并且由于det（π（t））=t= det（y）≤det（x）=s= det（π（s）），所以通过π的单调性，我们有y=π（t）±π（s）=x。Q利用序理论的技巧，建立了N的可换子幺半群的长度与容量之间的定性等价关系。我们不知道有一个基于不等式的直接证明推论4.11 C <$π x：[0，1] → [0，1]是一个序同构。证据直线πx从对角线到恒等式，而不是从恒等式到对角线，这就颠倒了Prop.4.10中的不等式。因此，s≤t惠C（πx（s））≤C（πx（t））。Q在这一节中，有一些令人惊讶的结果的应用例4.12考虑两个具有各自噪声矩阵的16年7月16日9月16日2016年3月 16日13月 16日11/ 3221/322017年12月25日哪个容量更大？我们可以回答这个问题，而不需要计算两者的容量。一种方法是注意到A=（14/ 32， 6/ 32）而B=（11/ 32， 7/ 32）。由于A B，我们有C（A）>C（B），这意味着A具有更大的容量。在这种情况下，另一种方法是使用行列式。K. Martin等人/理论计算机科学电子笔记158（2006）289303±||一加二一≥log22a−b+2a−b根据引理3.3，这两个噪声矩阵可交换，因此根据Prop.4.10，我们可以通过简单地比较行列式来确定容量更大的通道det（A）= 4/ 16 = 1/ 4> 1/ 8 = 4/ 32 = det（B）所以我们再次看到A是具有较大容量的信道我们可以很容易地看到这个例子，并直观地推理出A具有容量大于B，因为P（0 |0）= 14/32和P（1 |1）= 26/32 for A whileB的P（0 0）= 11/32和P（1 1）= 2 5/32。但这种直觉的真实-soning完全等同于陈述A B。 问题是：为什么它遵循C（A）>C（B）？答案是容量是Scott连续的且严格单调的。例4.13每个通道（a，b）是Z个通道（a，b）=（1，b/a）·（a，0）当a/= 0且（0， 0）=（1， 0）·（0， 0）当a= 0≥b≥ 0时。 假设a >0。 因为x±x≠y，I[0， 1]上的容量C是Scott连续的，我们有C（n（a，0））≥C（n（a，0）nn（1，b/a））=C（n（a，b））这个结果与直觉是一致的。然而，如果我们从不等式的角度来看，我们会发现我们刚刚证明了.−H（a）。a<$H（b）−<$bH（a）bH（a）−aH（b）<$我们不知道这个结果的分析证明。然而，域理论的技术，本文允许一个简单的证明结果，其证明应该是简单的。简而言之，容量的斯科特连续性形式上证明了人们在推理二进制信道时经常依赖的一些有效直觉。我们在本节中强调了域理论如何使信息论受益。然而，值得指出的是幺半群（I[0，1]，λ，λ）是比特流域（λ∞，·，ε）上的一个连续向量，它以空字符串为单位元并置.让我们把这一点说清楚：地图φ（ε）=ε，φ（0）=[0， 1/ 2]，φ（1）=[1/ 2， 1]C（a，0）= log2= C（a，b）304K. Martin等人/理论计算机科学电子笔记158（2006）289⊥⊥PM扩展到Scott连续同态。它对极大元集的限制是从Cantor集（Stone空间）到单位区间的连续满射事实上，这种映射是一种非常重要的数值方法：二分法是由两个元素ntleft（）=[0，1/2]和rig ht（）=[1/2，1]的重复相乘而产生的。但值得注意的是：如果串的串联是区间的乘法，而区间的乘法是矩阵乘法，则二进制串的串联可以理解为矩阵乘法。更妙的是：每个有限字符串都由一个可逆矩阵表示！5将噪音注入隐蔽信道增加隐蔽信道中的噪声量会降低其容量。香农[5]已经证明，不能以大于容量的速率进行传输.因此，降低隐蔽通道容量的能力提供了一种减少其构成的威胁的方法。二进制信道的代数和域理论结构提供了如下容量减少问题的优雅解决方案。假设我们有一个具有噪声矩阵M的隐蔽信道，我们希望将其容量减少到r：为此，我们引入了一个新的P. 有两个地方我们可以引入噪音，或MP第一个系统的容量是C（PM），第二个系统的容量是C（MP）。然而，在某些情况下，在系统中的某些点引入P在物理上可能是不可能的例如，如果信道M末端的接收者是窃听者，那么因为我们不一定知道他们的确切位置，甚至根本不知道他们的存在，所以不可能可靠地构建系统MP;唯一的可能性是PM。 另一方面，如果在系统中的任何一点都有可能引入噪声，我们希望从业者能够自由选择最便宜的方法。MK. Martin等人/理论计算机科学电子笔记158（2006）289305→−◦→≤ ≤≤◦可能 这两个问题都可以解决，如果有可能找到一个矩阵，P与M交换使得C（MP）= C（PM）=r。M和P交换的价值在于，我们可以自由地在通道M之前或之后插入这个新分量，因为上面的两个修改在统计上是相同的。因此，从业者也可以自由地以尽可能最便宜的方式放置组件，从而避免必须在系统的开始处插入噪声矩阵的不可能的情况，尽管事实上仅通过将P放置在系统的末端来实现容量r现在我们使用前面几节中发展的代数和域理论技巧来证明这样一个矩阵唯一存在，以及如何计算它：定理5.1设x∈N\{1}是正通道5，且0 ≤r≤ C（x）.(i) 有一个唯一的y与x交换使得C（xy）= C（yx）= r。(ii) 如果π x[0，1]是连接0x到1的极大交换子幺半群，则f：[0，1] R由f（t）= C（π x（t））给出 r是连续的，并且在[0，det（x）]上改变符号。证据（i）设π x：[0，1] →N是通过x的将恒等式连接到对角线的直线。根据推论4.11，函数Cπx：[0，1] [0，1]是严格递增的，即（s，t ∈ [0，1]）s 0，我们可以定义y=πx（s/t）。 然后xy=yx，我们有C（yx）= C（πx（s/t）·πx（t））= C（πx（（s/t）·t））= C（πx（s））=r对于y的唯一性，设u=πx（v）是另一个这样的元素，则C（ux）=C（πx（v）·πx（t））= C（πx（vt））=r根据Cπx的内射性，vt=s，这意味着v=s/t，因此u=y。5由定理4.9可知，正信道就是具有正容量的非负信道306K. Martin等人/理论计算机科学电子笔记158（2006）289(ii)这是直接的，因为f（0）= C（0x）−r= 0−r≤ 0，f（det（x））= C（x）−r≥0。Q我们现在有一个算法，用于将隐蔽通道M=x的容量减少到任何所需的水平r。首先，我们求解方程f（t）=0。噪声矩阵πx（t）则具有容量r。如果可以在系统中用πx（t）替换M，那么我们可以这样做，剩余的隐蔽通道将具有容量r。另一方面，如果我们只能向现有的系统为了减少容量，然后将分量P=M−1πx（t）添加到M的任一侧将使隐蔽通道的容量减少到r，其中M −1存在，请注意，该算法也适用于单位通道，只要我们也选择一个特定的交换子幺半群（“路径”），一个典型的路径选择似乎是连接1到（1/ 2，1/ 2）的线函数f总是在[0， 1]上改变符号。6今后工作我们想把我们的结果扩展到二进制定时信道。直到最近才解决了二进制定时信道的容量问题[4];我们对这里介绍的代数和域理论技术对定时设置的适应性持乐观态度。在这种情况下，测量属性特别有趣回想一下，测量通常用于帮助我们确定定义域中给定元素接近最大元素的程度这正是我们在试图减少隐通道x的容量时所做的：我们将x视为零通道（α，α）的近似，并且我们说我们希望计算最大元素（α，α）的还有其他方法可以用来减少隐蔽信道的容量。例如，遵循曲面上的梯度（a，b，C（a，b））。虽然这肯定会“更快地”降低容量，但它具有限制从业者将噪声引入系统的能力的不实用的效果，因为通常获得的矩阵不会与信道的矩阵交换。然而，这种方法可能有其他用途。这是我们感兴趣的事情。最后，虽然我们在这里的重点在本质上很大程度上是务实的，想知道如何以实践者可以使用的算法方式减少容量，但作者并没有忽视I[0， 1]是一个紧致幺半群，具有许多与序有关的有趣性质K. Martin等人/理论计算机科学电子笔记158（2006）289307和一门代数学。如果能发现像I[0，1]和I_∞这样的幺半群所具有的性质，那么本文中的许多结果就能被抽象地证明例如，它应该遵循从域理论幺半群的公理，交换元素总是比较，或劳森拓扑域理论幺半群总是紧的。7确认第一作者感谢美国国家科学院，三位作者都感谢海军研究实验室。我们感谢前两位审稿人提出的宝贵建议，这些建议提高了本文的质量，特别是他们令人鼓舞的评论。最后，我们被第三个裁判逗乐了，他写道：我们很高兴您对我们的意向评价如此之高引用[1] S. Abramsky和A.俊作。域理论In S. Abramsky，D. M. Gabbay，T. S. E. Maibaum，编辑，计算机科学逻辑手册，卷。三. 牛津大学出版社，1994年。[2] A. Edalat和M.埃斯卡多 集成到实际PCF中。 信息与计算，第160卷，第1-2期，第128-166页，2000年。[3] K.马丁熵是一个固定点。ICALP 2004年。Theoretical Computer Science，Volume 350，Issues2-3，p. 292[4] K. 马丁和我S. 莫斯科维茨二 进制输入和输出的噪声定时通道。信息隐藏，计算机科学讲义，Springer-Verlag，2006年，即将出版。[5] C. E.香农沟通的数学理论。Bell Systems Technical Journal，27：379