The channel reliability function is an important tool that characterizes the reliable transmission of messages over communication channels. For many channels, only the upper and lower bounds of the function are known. In this paper 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 consider the $R_\infty$ function and the zero-error feedback capacity, since they play an important role in the context of the reliability function. Both the $R_\infty$ function and the zero-error feedback capacity are not Banach Mazur computable. We show that the $R_\infty$ function is additive. The zero-error feedback capacity is super-additive and we characterize its behavior.
翻译：频道可靠性功能是一个重要的工具,它通过通信渠道可靠传输信息。对于许多频道来说,只有该功能的上下界是已知的。在本文中,我们分析了可靠性功能及其相关功能的可计算性。我们表明,可靠性功能不是图灵可计算性功能。同样也适用于域包装和排污约束的功能。此外,我们认为,$R ⁇ infty$函数和零error反馈能力,因为它们在可靠性功能方面起着重要作用。$R ⁇ infty$函数和零error反馈能力都不是Banachur Mazubable。我们表明,$R ⁇ infty$函数是添加性的。零error反馈能力是超级增加的,我们描述其行为。
相关内容
微信扫码咨询专知VIP会员