Capacity Results for the Discrete Memoryless Network
01 January 2003
A discrete memoryless network (DMN) is a memoryless multi-terminal channel with discrete inputs and outputs. A sequence of inner bounds to the DMN capacity region is derived by using code trees. Capacity expressions are given for four classes of DMNs: 1) a single-letter expression for a class with strong symmetries, 2) a single-letter expression for a class with a common output, 3) a two-letter expression for a binary symmetric broadcast channel with partial feedback, and 4) a finite-letter expression for push-to-talk DMNs. The second result is a consequence of a new capacity outer bound for common output DMNs. The fourth result demonstrates that the common practice of using a time-sharing random variable does not include all time-sharing possibilities, namely time-sharing of channels. Several techniques for improving the bounds are developed: 1) casually conditioned entropy and directed information simplify the inner bounds, 2) code trellises serve as simple code trees, 3) superposition coding with code trees improves rates. Numerical computations show that the last technique enlarges the best known rate regions for a multiple-access channel and a broadcast channel, both with feedback. In addition to the rate bounds, a sequence of inner bounds to the DMN reliability function is derived. A numerical example for a two-way channel illustrates the behavior of the error exponents.