Infinity-Norm Permutation Covering Codes from Cyclic Groups

Preprint English OPEN
Karni, Ronen ; Schwartz, Moshe (2017)
  • Subject: Computer Science - Information Theory

We study covering codes of permutations with the $\ell_\infty$-metric. We provide a general code construction, which uses smaller building-block codes. We study cyclic transitive groups as building blocks, determining their exact covering radius, and showing linear-time algorithms for finding a covering codeword. We also bound the covering radius of relabeled cyclic transitive groups under conjugation.
  • References (29)
    29 references, page 1 of 3

    [1] A. Barg and A. Mazumdar, “Codes in permutations and error correction for rank modulation,” IEEE Trans. Inform. Theory, vol. 56, no. 7, pp. 3158-3165, Jul. 2010.

    [2] P. J. Cameron and I. M. Wanless, “Covering radius for sets of permutations,” Discrete Math., vol. 293, pp. 91-109, 2005.

    [3] H. D. Chadwick and L. Kurz, “Rank permutation group codes based on Kendall's correlation statistic,” IEEE Trans. Inform. Theory, vol. IT-15, no. 2, pp. 306-315, Mar. 1969.

    [4] M. Deza and H. Huang, “Metrics on permutations, a survey,” J. Comb. Inf. Sys. Sci., vol. 23, pp. 173-185, 1998.

    [5] F. Farnoud, M. Schwartz, and J. Bruck, “Bounds for permutation rate-distortion,” IEEE Trans. Inform. Theory, vol. 62, no. 2, pp. 703-712, Feb. 2016.

    [6] F. Farnoud, V. Skachek, and O. Milenkovic, “Error-correction in flash memories via codes in the Ulam metric,” IEEE Trans. Inform. Theory, vol. 59, no. 5, pp. 3003-3020, May 2013.

    [7] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 1994.

    [8] A. E. Holroyd, “Perfect snake-in-the-box codes for rank modulation,” arXiv preprint arXiv:1602.08073, 2016.

    [9] M. Horovitz and T. Etzion, “Constructions of snake-in-the-box codes for rank modulation,” IEEE Trans. Inform. Theory, vol. 60, no. 11, pp. 7016-7025, Nov. 2014.

    [10] A. Jiang, R. Mateescu, M. Schwartz, and J. Bruck, “Rank modulation for flash memories,” IEEE Trans. Inform. Theory, vol. 55, no. 6, pp. 2659-2673, Jun. 2009.

  • Metrics
    No metrics available
Share - Bookmark