TheZeroErrorCapacityofCompoundChannels.pptVIP

The Zero-Error Capacity of Compound Channels Jayanth Nayak Kenneth Rose University of California, Santa Barbara Outline Preliminaries Problem definition Capacity Neither side has side-information Encoder has side-information Decoder has side-information Comparison with vanishing-error case Zero-Error vs. Vanishing-Error Vanishing-error Case tends to zero as block length tends to infinity. Zero-error case zero at all block lengths Tools: graph theory and combinatorics Discrete Memoryless Channel Channel Code Code ? symbols pair-wise connected = clique Example (cont.) Scalar code: 1-use capacity = is the clique number Channel Code uses of the channel Fan-out set is Cartesian product of fan-out sets at each coordinate = size of largest pairwise connected set Channel Code Zero error capacity (Shannon ’56) Other Graph Capacities Shannon capacity of a set of graphs: Asymptotic size of set of sequences connected with respect to every graph from Defined by Cohen et al. ‘88 Directed graphs Other Graph Capacities Sperner capacity of a graph largest pairwise connected set : connected with respect to every graph Sperner capacities defined by Gargano et al. ’94 Motivated by extremal set theory The Compound Channel Capacity Conventional Case: Dobrushin ‘59, Wolfowitz ‘60, Breiman ‘59 Zero-Error Case: Cohen et al. ‘88, Gargano et al. ‘94 Capacity expression accurate only when decoder is informed. Characteristic Set of Graphs Fan-out set Vertex set Directed graph Capacity of Compound Channel Every code is a pairwise connected set with respect to and vice versa Encoder Informed of S If 0, encoder sends side-information to decoder. Needs constant number of channel uses. = 0 case: contains an edge-free graph Decoder Informed of S Decoder can change with channel Therefore Conventional vs. Zero-Error Conventional Capacities Zero-Error Capacities Reason: Decoder can