Capacity of Channels With Action-Dependent States

Abstract

We consider channels with action-dependent states: Given the message to be communicated, the transmitter chooses an action sequence that affects the formation of the channel states, and then creates the channel input sequence based on the state sequence. We characterize the capacity of such a channel both for the case where the channel inputs are allowed to depend noncausally on the state sequence and the case where they are restricted to causal dependence. Our setting covers previously considered scenarios involving transmission over channels with states known at the encoder, as well as various new coding scenarios for channels with a “rewrite” option that may arise naturally in storage for computer memories with defects or in magnetic recoding. A few examples are worked out in detail.