Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-02T23:09:53.302Z Has data issue: false hasContentIssue false

Channel capacities for list codes

Published online by Cambridge University Press:  14 July 2016

Rudolf Ahlswede*
Affiliation:
Ohio State University, Columbus

Abstract

In the present paper we demonstrate that the concept of a list code is from a mathematical point of view a more canonical notion than the classical code concept (list size one) in that it allows a unified treatment of various coding problems. In particular we determine for small list sizes the capacities of arbitrarily varying channels.

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 1973 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Shannon, C. E. (1956) The zero error capacity of a noisy channel. IRE Trans. Inf. Th. IT-2, 819.Google Scholar
[2] Berge, C. (1962) The Theory of Graphs and its Applications. English translation. Methuen, London.Google Scholar
[3] Elias, P. (1955) List decoding for noisy channels. Technical Report 335, Research Laboratory of Electronics, M. I. T., Cambridge, Mass. Google Scholar
[4] Ahlswede, R. (1972) A constructive proof of the coding theorem for discrete memoryless channels with noiseless feedback. To appear in the Transactions of the Sixth Prague Conference on Inf. Th., Random Processes and Statistical Decision Functions. Google Scholar
[5] Ahlswede, R. (1973) The capacity of channels with arbitrarily varying channel probability functions in the presence of feedback. Zeit. Wahrscheinlichkeitsth. 25, 239252.CrossRefGoogle Scholar
[6] Ahlswede, R. (1970) A note on the existence of the weak capacity for channels with arbitrarily varying channel probability functions and its relation to Shannon's zero error capacity. Ann Math. Statist. 41, 10271033.CrossRefGoogle Scholar
[7] Ahlswede, R. and Wolfowitz, J. (1970) The capacity of a channel with arbitrarily varying channel probability functions and binary output alphabet. Zeit. Wahrscheinlichkeitsth. 15, 186194.CrossRefGoogle Scholar
[8] Shannon, C. E., Gallager, R. G. and Berlekamp, E. (1967) Lower bounds to error probability for coding on discrete memoryless channels. Inf. and Control 10, 65103.Google Scholar
[9] Forney, G. D. (1968) Exponential error bounds for erasure, list and decision feedback schemes. IEEE Trans. Inf. Th. IT-14, 206220.Google Scholar
[10] Ahlswede, R. (1968) The weak capacity of averaged channels. Zeit. Wahrscheinlichkeitsth. 11, 6173.CrossRefGoogle Scholar
[11] Wolfowitz, J. (1960) Simultaneous channels. Arch. Rational Mech. Anal. 4, 371386.Google Scholar
[12] Nishimura, S. (1969) The strong converse theorem in the decoding scheme of list size L. Kodai Math. Sem. Rep. 21, 418425.Google Scholar
[13] Elias, P. (1958) Zero error capacity for list detection. Quarterly Progress Report No. 48, Research Laboratory of Electronics, M. I. T., Cambridge, Mass. Google Scholar