“一般有噪网络的切面不再只是独立边容量相加。网络切集信息上界用 $I(X S;Y {S^c} X {S^c})$ 约束跨界信息流,将同侧节点完全合作作为放宽条件。它在独立无噪链路上恢复割容量,…”
形式陈述
考虑有限字母表的离散无记忆网络,节点
任何可达率都满足切集上界
每个
直觉
即便让切面同侧的所有节点完全合作,源消息仍必须穿过切面才能到终点。将一侧合并成超级发送者、另一侧合并成超级接收者,只会让任务更容易,所以容易任务的容量也限制原网络。
同一份输入分布要接受所有切面的检查。先对每个切面单独最大化再取最小,仍可能是上界,却通常更松;它允许不同切面各自使用不相容的最优分布。
从一段码到单字母上界
任取长度
无记忆性消去更早信号的额外影响,因果编码保证当前输入只依赖允许的历史。令
例子与边界
三节点中继有两条关键切面
源输入
切
无噪串联链的匹配例子
源到中继每次最多传
换成一般有噪无线中继后,切集值未必可达。特别是同一个接收输出同时混合多个发送输入时,不能把每条画出的箭头独立当作一条给定容量的管道。
参考资料
- El Gamal 与 Kim,《Lecture Notes on Network Information Theory》完整 v4,Chapters 17、19,中继及一般网络切集界。
- El Gamal 与 Kim,ISIT 2011 教程,Cutset Bound 部分。