Flaws found in a key proof about binary channel decoding limits
Diagnosing the Refuted Mismatched Decoding Converse for Binary-Input Channels
Information Theory
Summary
This paper looks closely at a mathematical proof from 1995 about how well certain communication decoders work for sending data over simple yes-no channels. Later researchers found a numerical example that showed the original proof was wrong, but no one had clearly explained what the mistake was. The authors carefully analyze the original proof and find multiple flawed steps and show that a key supporting claim is generally false. This helps clear up confusion about what limits can be guaranteed in decoding performance.
What this means in practice
- •For communication system designers: Avoid relying on the disproven converse when evaluating decoder performance limits in simple binary channels.
- •For error correction engineers: Use clarified theory to better understand which decoding assumptions are valid for binary channel coding schemes.
A theory result. No direct application yet.
Authors
Jonathan Scarlett
Abstract
We revisit the claimed converse theorem for mismatched decoding over binary-input discrete memoryless channels (Balakirsky, 1995) and the subsequent work refuting this converse via a numerical counter-example (Scarlett, Somekh-Baruch, Martinez, and Guillén i Fàbregas, 2015). A notable gap in the existing understanding is that no concrete flaw was identified in Balakirsky's analysis. In this paper, Balakirsky's proof is "diagnosed", and it is demonstrated that (i) his permutation lemma is flawed regardless of the correctness of his combinatorial approximation lemma; (ii) there are at least two specific incorrect steps regarding restricted codes and selector sequences, and these appear to be unlikely to admit a local repair; and (iii) the proposition in which these incorrect steps are used is false in general.