Coding theorem defines decoding error capacity for general scenarios

The rate at which information can be coded so that it can be decoded within a particular error probability constraint is one of the "major research topics in information theory" as Hideki Yagi at the University of Electro-Communications, Te Sun Han at the National Institute of Information and Communications Technology, and Ryo Nomura at Senshu University in Japan explain in their recent report. In this latest work they formulate a theorem for a general class of coding theorems that gives a formula for the decoding error capacity. They also show how the theorem reduces to known theorems for more restricted scenarios.

The researchers describe their system as an input stream that is coded into the output by a channel sequence. The channel capacity is then the rate at which information can be reliably transmitted by that channel.

Previous work has demonstrated formulae for the error capacity for coding channels but they were limited by the length of the coding stream - which becomes uncomputable for general scenarios. Other work has characterised the channel capacity in such a way that the complexity does not increase with the channel length, but they are limited in terms of what mixture of channel types can be coded in this way.

While progress has been made towards more general theorems, Yagi, Han and Nomura now establish the first-order coding theorem, which gives a formula for the error-capacity for mixed memoryless channels with general mixture. They also provide a direct part of the second-order coding theorem, and show that other previously established formulas can be obtained by reducing the theorem to restricted scenarios.

They add in their concluding remarks, "Extensions of the established formulas for mixed channels with general input and/or output alphabets are interesting and practically important research subjects."