pipette
ESEspañol

When Majority-Vote Fails: Sequence Reconstruction under Fixed-Weight Substitutions

Vivian Papadopoulou, Yonatan Yehezkeally, V. Arvind Rameshwar, Antonia Wachter-Zeh

Preprint

In the authors' words

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 . We determine , 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 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 , and sufficient for bit-wise majority-vote even below . We evaluate the number of outputs at which this condition is triggered, numerically, and show that it frequently occurs below when the block-length . 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.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.