Binary sequence decoding improved beyond majority voting error limits
When Majority-Vote Fails: Sequence Reconstruction under Fixed-Weight Substitutions
Information Theory
Summary
Sometimes when a message is sent multiple times with mistakes, guessing the original by looking at the majority of received bits doesn’t always work well. This paper studies when that usual majority method fails and finds the minimum number of repeated messages needed to perfectly figure out the original sequence. The authors also introduce a practical early stopping rule to know when decoding can finish reliably, even before hearing all repeats. They propose a new decoding method that can correctly recover the original message with fewer repeats than the majority-vote method in some cases.
What this means in practice
- •For communications engineers: Design error-correcting decoders that recover original signals more efficiently when fixed numbers of bit flips occur.
- •For data storage developers: Improve data retrieval reliability by using better decoding strategies for fixed-weight substitution errors in memory systems.
Authors
Vivian Papadopoulou, Yonatan Yehezkeally, V. Arvind Rameshwar, Antonia Wachter-Zeh
Abstract
We consider the problem of binary sequence reconstruction where a sequence is transmitted multiple times over a channel, and each undergoes substitution errors by an arbitrary error vector of Hamming weight exactly $t$. We determine $N_{\mathrm{wc}}$, the minimum number of distinct channel output observations guaranteeing unique reconstruction by an optimal decoder, and show that the bit-wise majority-vote decoder, which was proved by Levenshtein (2001) to be optimal for channels corrupting up to $t$ bits, is in fact suboptimal here. Despite this suboptimality, we prove a condition that admits a practical early-termination rule, necessary for every decoder at any number of outputs $N$, and sufficient for bit-wise majority-vote even below $N_{\mathrm{wc}}$. We evaluate the number of outputs at which this condition is triggered, numerically, and show that it frequently occurs below $N_{\mathrm{wc}}$ when the block-length $k>2t+1$. Finally, we propose an alternative algorithm aimed at guaranteeing unique reconstruction with fewer observations than bit-wise majority-vote, and demonstrate through exhaustive enumeration that it successfully decodes channel output-sets where bit-wise majority-vote fails.