On Coding Over Sliced Information
Jin Sima, Netanel Raviv, Jehoshua Bruck
Abstract
The interest in channel models in which the data is sent as an unordered set of binary strings has increased lately, due to emerging applications in DNA storage, among others. In this paper we analyze the minimal redundancy of binary codes for this channel under substitution errors, and provide several constructions, some of which are shown to be asymptotically optimal up to constants. The surprising result in this paper is that while the information vector is sliced into a set of unordered strings, the amount of redundant bits that are required to correct errors is order-wise equivalent to the amount required in the classical error correcting paradigm.
Topics & Concepts
Binary numberRedundancy (engineering)AlgorithmInformation theoryComputer scienceCoding (social sciences)Binary dataError detection and correctionDecoding methodsTheoretical computer scienceCoding theorySet (abstract data type)MathematicsVariable-length codeArithmeticStatisticsOperating systemProgramming languageDNA and Biological ComputingAlgorithms and Data CompressionCellular Automata and Applications