|Uncertainty of Reconstructing Multiple Messages from Uniform-Tandem-Duplication Noise
|Yonatan Yehezkeally, Moshe Schwartz, Ben-Gurion University of the Negev, Israel
|A.4: Combinatorial Coding Theory I
|Algebraic and Combinatorial Coding Theory
|Click here to download the manuscript
|Click here to watch in the Virtual Symposium
|We propose a list-decoding scheme for reconstruction codes in the context of uniform-tandem-duplication noise, which can be viewed as an application of the associative memory model to this setting. We find the uncertainty associated with $m>2$ strings (where a previous paper considered $m=2$) in asymptotic terms, where code-words are taken from a typical set of strings, consisting a growing fraction of the space size, converging to $1$. Thus, we find the trade-off between the number of errors, the acceptable list size and the resulting uncertainty, which corresponds to the required number of distinct retrieved outputs for successful reconstruction. It is therefore seen that by accepting list-decoding one may decrease the required number of reads.