SIMPLE PROOFS OF SOME THEOREMS ON NOISELESS CHANNELS

Shannon's capacity formula for memoryless and finite-state noiseless channels is proved in a simple elementary way, for arbitrary symbol costs; actually, a somewhat stronger result is proved. Further, a simple proof of a version of the noiseless coding theorem is given, based on the properties of entropy and avoiding combinatorial arguments; also, in the familiar proof of the mentioned theorem, a possible simplification is pointed out. Finally, a nearly optimal encoding for finite-state noiseless channels is suggested. © 1969 Academic Press, Inc.