Michal Horovitz – Reconstruction of Sequences over Non-Identical Channels.

Event Details

  • Date:

Motivated by the error behavior in DNA storage channels, in this work we extend the previously studied sequence reconstruction problem by Levenshtein.
The reconstruction problem studies the model in which the information is read through multiple noisy channels, and the decoder, which receives all channel estimations, is required to decode the information.
For the combinatorial setup, the assumption is that all the channels cause at most t errors.
However, since the channels do not necessarily have the same behavior, we generalize this model and assume that the channels are not identical and thus may cause a different maximum number of errors.
For example, we assume that there are N channels that cause at most t1 or t2 errors, where t1<t2, and the number of channels with at most t1 errors is at least [pN], for some fixed 0<p<1.
If the information codeword belongs to a code with minimum distance d, the problem is then to find the minimum number of channels that guarantees successful decoding in the worst case.