Capacity Results for the Noisy Shuffling Channel

Motivated by DNA-based storage, we study the noisy shuffling channel, which can be seen as the concatenation of a standard noisy channel (such as the BSC) and a shuffling channel, which breaks the data block into small pieces and shuffles them. This channel models a DNA storage system, by capturing two of its key aspects: (1) the data is written onto many short DNA molecules that are stored in an unordered way and (2) the molecules are corrupted by noise at synthesis, sequencing, and during storage. For the BSC-shuffling channel we characterize the capacity exactly (for a large set of parameters), and show that a simple index-based coding scheme is optimal.

受基于DNA的存储的启发，我们研究有噪混洗信道，它可被视为一个标准有噪信道（例如二元对称信道BSC）和一个混洗信道的串联，混洗信道将数据块分成小块并对它们进行混洗。该信道通过捕捉DNA存储系统的两个关键方面来为其建模：（1）数据被写入许多以无序方式存储的短DNA分子上；（2）分子在合成、测序以及存储过程中受到噪声的破坏。对于二元对称信道 - 混洗信道，我们精确地描述了（针对大量参数集的）容量，并表明一种简单的基于索引的编码方案是最优的。