We study the problem of retrieving data from a channel that breaks the input sequence into a set of unordered fragments of random lengths, which we refer to as the chop-and-shuffle channel. The length of each fragment follows a geometric distribution. We propose nested Varshamov-Tenengolts (VT) codes to recover the data. We evaluate the error rate and the complexity of our scheme numerically. Our results show that the decoding error decreases as the input length increases, and our method has a significantly lower complexity than the baseline brute-force approach. We also propose a new construction for VT codes, quantify the maximum number of the required parity bits, and show that our approach requires fewer parity bits compared to known results.
翻译:我们研究从一个将输入序列分解成一组无顺序随机长度碎片的频道检索数据的问题,我们称之为排和排泄通道。每个碎片的长度遵循几何分布法。我们建议嵌入 Varshamov-Tenngolts (VT) 代码来恢复数据。我们用数字来评估错误率和我们计划的复杂性。我们的结果表明,随着输入长度的增加,解码错误会减少,我们的方法比基线粗力方法要复杂得多。我们还提议了一个新的VT代码结构,量化所要求的对等点的最大数量,并表明我们的方法比已知结果要求的对等位数要少。