Computability of the Channel Reliability Function and Related Bounds


Conference / Medium


Christian Deppe Holger Boche

Research Hub

Research Hub A: Kryptographie der Zukunft
Research Hub B: Eingebettete Sicherheit

Research Challenges

RC 5: Physical-Layer Security


The channel reliability function is an important tool that characterizes the reliable transmission of messages over communication channels. For many channels, only upper and lower bounds of the function are known. We analyze the computability of the reliability function and its related functions. We show that the reliability function is not a Turing computable performance function. The same also applies to the functions of the sphere packing bound and the expurgation bound. Furthermore, we show that the R ∞ function is not Banach Mazur computable and additive.


Coding Theory
Complexity Theory
Information Theory
Implementation Attacks
Post-Quantum Cryptography