Good codes can be produced by a few permutations

Ahlswede R, Dueck G (1982)
IEEE transactions on information theory 28(3): 430-443.

Download
OA
Journal Article | Published | English
Author
;
Abstract
Our main result is that good codes, even those meeting the random coding bound, can be produced with relatively few (linear in the block length) permutations from a single codeword. This cutdown in complexity may be of practical importance. The motivation for looking at such codes came from Ahlswede's covering lemma, which makes it possible to build correlated source codes from channel codes via permutations. In Appendix I we show that the problem of finding the best error exponents for coding sources with full side information at the decoder, which has received attention in the recent literature, can easily be reduced to the familiar one for the discrete memoryless channel (DMC). Finally, in Appendices II and III we give rather precise double exponentially small bounds on the probabilities that a randomly chosen code will fail to meet the random coding or expurgated bound for the DMC. According to these results, good codes are hard to miss if selected at random. This also explains why good codes of a low complexity (such as those produced by permuations) do exist.
Publishing Year
ISSN
PUB-ID

Cite this

Ahlswede R, Dueck G. Good codes can be produced by a few permutations. IEEE transactions on information theory. 1982;28(3):430-443.
Ahlswede, R., & Dueck, G. (1982). Good codes can be produced by a few permutations. IEEE transactions on information theory, 28(3), 430-443.
Ahlswede, R., and Dueck, G. (1982). Good codes can be produced by a few permutations. IEEE transactions on information theory 28, 430-443.
Ahlswede, R., & Dueck, G., 1982. Good codes can be produced by a few permutations. IEEE transactions on information theory, 28(3), p 430-443.
R. Ahlswede and G. Dueck, “Good codes can be produced by a few permutations”, IEEE transactions on information theory, vol. 28, 1982, pp. 430-443.
Ahlswede, R., Dueck, G.: Good codes can be produced by a few permutations. IEEE transactions on information theory. 28, 430-443 (1982).
Ahlswede, Rudolf, and Dueck, Gunter. “Good codes can be produced by a few permutations”. IEEE transactions on information theory 28.3 (1982): 430-443.
Main File(s)
Access Level
OA Open Access

This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar