LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Karni, Ronen; Schwartz, Moshe (2017)
Languages: English
Types: Preprint
Subjects: 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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [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.
    • [11] A. Jiang, M. Schwartz, and J. Bruck, “Correcting charge-constrained errors in the rank-modulation scheme,” IEEE Trans. Inform. Theory, vol. 56, no. 5, pp. 2112-2120, May 2010.
    • [12] R. Karni, “Permutation covering codes under the infinity metric,” Master's thesis, Ben-Gurion University of the Negev, 2016.
    • [13] P. Keevash and C. Y. Ku, “A random construction for permutation codes and the covering radius,” Designs, Codes and Cryptography, vol. 41, pp. 79-86, 2006.
    • [14] T. Kløve, “Spheres of permutations under the infinity norm - permutations with limited displacement,” University of Bergen, Bergen, Norway, Tech. Rep. 376, Nov. 2008.
    • [15] --, “Generating functions for the number of permutations with limited displacement,” Elec. J. of Comb., vol. 16, pp. 1-11, 2009.
    • [16] --, “Lower bounds on the size of spheres of permutations under the Chebychev distance,” Designs, Codes and Cryptography, vol. 59, no. 1-3, pp. 183-191, 2011.
    • [17] T. Kløve, T.-T. Lin, S.-C. Tsai, and W.-G. Tzeng, “Permutation arrays under the Chebyshev distance,” IEEE Trans. Inform. Theory, vol. 56, no. 6, pp. 2611-2617, Jun. 2010.
    • [18] A. Mazumdar, A. Barg, and G. Ze´mor, “Constructions of rank modulation codes,” IEEE Trans. Inform. Theory, vol. 59, no. 2, pp. 1018-1029, Feb. 2013.
    • [19] J. Quistorff, “A survey on packing and covering problems in the Hamming permutation space,” Elec. J. of Comb., vol. 13, pp. 1-13, 2006.
    • [20] M. Schwartz and I. Tamo, “Optimal permutation anticodes with the infinity norm via permanents of (0, 1)-matrices,” J. Combin. Theory Ser. A, vol. 118, pp. 1761-1774, 2011.
    • [21] D. Slepian, “Permutation modulation,” Proc. of the IEEE, vol. 53, no. 3, pp. 228-236, 1965.
    • [22] I. Tamo and M. Schwartz, “Correcting limited-magnitude errors in the rank-modulation scheme,” IEEE Trans. Inform. Theory, vol. 56, no. 6, pp. 2551-2560, Jun. 2010.
    • [23] --, “On the labeling problem of permutation group codes for the infinity metric,” IEEE Trans. Inform. Theory, vol. 58, no. 10, pp. 6595-6604, Oct. 2012.
    • [24] D. Wang, A. Mazumdar, and G. W. Wornell, “Compression in the space of permutations,” IEEE Trans. Inform. Theory, vol. 61, no. 12, pp. 6417-6431, Dec. 2015.
    • [25] X. Wang and F.-W. Fu, “Constructions of snake-in-the-box codes under the ℓ∞-metric for rank modulation,” arXiv preprint arXiv:1601.05539, 2016.
    • [26] Y. Yehezkeally and M. Schwartz, “Snake-in-the-box codes for rank modulation,” IEEE Trans. Inform. Theory, vol. 58, no. 8, pp. 5471-5483, Aug. 2012.
    • [27] --, “Limited-magnitude error-correcting gray codes for rank modulation,” in Proceedings of the 2016 IEEE International Symposium on Information Theory (ISIT2016), Barcelona, Spain, Jul. 2016, pp. 2829-2833.
    • [28] Y. Zhang and G. Ge, “Snake-in-the-box codes for rank modulation under Kendall's τ-metric,” IEEE Trans. Inform. Theory, vol. 62, no. 1, pp. 151-158, Jan. 2016.
    • [29] H. Zhou, M. Schwartz, A. Jiang, and J. Bruck, “Systematic error-correcting codes for rank modulation,” IEEE Trans. Inform. Theory, vol. 61, no. 1, pp. 17-32, Jan. 2015.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article

Collected from