The authors' main finding is that any object among doubly exponentially many objects can be identified in blocklength n with arbitrarily small error probability via a discrete memoryless channel (DMC), if randomization can be used for the encoding procedure. A novel doubly exponential coding theorem is presented which determines the optimal R, that is, the identification capacity of the DMC as a function of its transmission probability matrix. This identification capacity is a well-known quantity, namely, Shannon's transmission capacity for the DMC.>

A study is made of the identification problem in the presence of a noiseless feedback channel, and the second-order capacity C/sub f/ (resp. C/sub F/) for deterministic (resp. randomized) encoding strategies is determined. Several important phenomena are encountered. (1) Although feedback does not increase the transmission capacity of a discrete memoryless channel (DMC), it does increase the (second-order) identification capacity; (2) noise increases C/sub f/; (3) the structure of the new capacity formulas is simpler than C.E. Shannon's (1948) familiar formula. This has the effect that proofs of converses become easier than in the authors' previous work.>

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 Iow complexity (such as those produced by

An instructive counterexample is presented showing that the coding strategy of Cover, El Gamal, and Salehi for multiple access channels with arbitrarily correlated sources is not optimal. Some new insight into the very difficult problem of determining the true capacity regions is given by this example.

Asymptotically coincident upper and lower bounds on the exponent of the largest possible probability of the correct decoding of block codes are given for all rates above capacity. The lower bound sharpens Omura's bound. The upper bound is proved by a new and simple combinatorial argument.