Sphere Decoding for Multiset Codes in Noisy Permutation Channels

Motivated by DNA-based storage systems, this paper examines the decoding problems for the multiset codes in the noisy permutation channels, which permute the transmitted symbols randomly and impose noise such as symbol insertions, deletions and substitutions on symbols. The connection between multiset codes and the maximum/maximal independent sets is established. Based on this connection, a sphere decoding algorithm specifically designed for multiset codes is proposed to reduce the time complexity of decoding while guaranteeing the equivalent codeword error rate to that of ML decoding.