We revise the proof of low-rate upper bounds on the reliability function of discrete memoryless channels for ordinary and list-decoding schemes, in particular Berlekamp and Blinovsky's zero-rate bound, as well as Blahut's bound for low rates. The available proofs of the zero-rate bound devised by Berlekamp and Blinovsky are somehow complicated in that they contain in one form or another some cumbersome "non-standard" procedures or computations. Here we follow Blinovsky's idea of using a Ramsey-theoretic result by Komlos, and we complement it with some missing steps to present a proof which is rigorous and easier to inspect. Furthermore, we show how these techniques can be used to fix an error that invalidated the proof of Blahut's low-rate bound, which is here presented in an extended form for list decoding and for general channels.
翻译:我们修改关于普通和列表解码计划的离散无记忆频道的可靠性功能的低率上限证据,特别是Berlekamp和Blinovsky的零率约束,以及Blahut的低利率约束。Berlekamp和Blinovsky设计的零率约束的现有证据有些复杂,因为它们包含一种或另一种繁琐的“非标准”程序或计算。我们在这里遵循Blinovsky关于使用Komlos的拉姆西理论结果的想法,我们用一些缺失的步骤补充它,以提供严格和易于检查的证据。此外,我们展示这些技术如何用来纠正错误,使Blahut的低利率约束的证据无效,而此处以扩展的形式展示了清单解码和一般渠道。