Codes in the Space of Multisets—Coding for Permutation Channels With Impairments

DOI10.1109/TIT.2017.2789292MaRDI QIDQ4682825zbMATH OpenOpenAlexFDO

Authors Vincent Y. F. Tan, Mladen Kovačević

Publication date 19 September 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.08837

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Source coding (94A29)

Abstract: Motivated by communication channels in which the transmitted sequences are subject to random permutations, as well as by certain DNA storage systems, we study the error control problem in settings where the information is stored/transmitted in the form of multisets of symbols from a given finite alphabet. A general channel model is assumed in which the transmitted multisets are potentially impaired by insertions, deletions, substitutions, and erasures of symbols. Several constructions of error-correcting codes for this channel are described, and bounds on the size of optimal codes correcting any given number of errors derived. The construction based on the notion of Sidon sets in finite Abelian groups is shown to be optimal, in the sense of the asymptotic scaling of code redundancy, for any "error radius" and any alphabet size. It is also shown to be optimal in the stronger sense of maximal code cardinality in various cases.

Recommendations

• Random coding bound and codes produced by permutations for the multiple-access channel
• On the performance of permutation codes for multi-user communication
• Coding for the $\boldsymbol \ell _\infty $ -Limited Permutation Channel
• Coding Theorems for Noisy Permutation Channels
• Permutation codes for the Gaussian channel
• Codes in Permutations and Error Correction for Rank Modulation
• Information sets and partial permutation decoding for codes from finite geometries
• Bounds of multipermutation codes in the generalized Cayley distance
• Optimal coding strategies for certain permuting channels
• Codes from multipartite graphs and minimal permutation decoding sets

Cited in

(6)

• Abelian difference sets as lattice coverings and lattice tilings
• Lattice packings of cross‐polytopes from Reed–Solomon codes and Sidon sets
• Codes for adversaries: between worst-case and average-case jamming
• An iterative code construction and codes generated by permutations for the asymmetric multiple-access channel (Corresp.)
• Information-Theoretic Foundations of DNA Data Storage
• Community Detection in General Hypergraph Via Graph Embedding

This page was built for publication: Codes in the Space of Multisets—Coding for Permutation Channels With Impairments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4682825)