Which communication rates can be attained over a channel whose output is an unknown (possibly stochastic) function of the input that may vary arbitrarily in time with no a-priori model? Following the spirit of the finite-state compressibility of a sequence defined by Lempel and Ziv, we define a “capacity” for such a channel as the highest rate achievable by a designer knowing the particular relation that indeed exists between the input and output for all times, yet is constrained to use a fixed finite-length block communication scheme (i.e., use the same scheme over each block). In the case of the binary modulo additive channel, where the output sequence is obtained by modulo addition of an unknown individual sequence to the input sequence, this capacity is upper bounded by 1 − ρ where ρ is the finite state compressibility of the noise sequence. We present a communication scheme with feedback that attains this rate universally without prior knowledge of the noise sequence.
展开▼
