Error-Correcting Codes for Multipermutations
Abstract
THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. Multipermutations appear in various applications in information theory. New applications such as rank modulation for flash memories and voting have suggested the need to consider error-correcting codes for multipermutations. The construction of codes is challenging when permutations are considered and it becomes even a harder problem for multipermutations. In this paper we discuss the general problem of error-correcting codes for multipermutations. We present some tight bounds on the size of error-correcting codes for several families of multipermutations. We find the capacity of the channels of multipermutations and characterize families of perfect codes in this metric which we believe are the only such perfect codes.
Additional Information
The work of Sarit Buzaglo and Tuvi Etzion was supported in part by the Israel Science Foundation (ISF), Jerusalem, Israel, under Grant No. 10/12. The authors would like to thank Alexander Vardy and Michael Langberg for bringing reference [9] to their knowledge.Files
| Name | Size | Download all |
|---|---|---|
|
md5:64f8363f718c339e8b9935a0ef60cff3
|
324.9 kB | Preview Download |
Additional details
- Eprint ID
- 36946
- Resolver ID
- CaltechAUTHORS:20130215-094523026
- 10/12
- Israel Science Foundation
- Created
-
2013-02-15Created from EPrint's datestamp field
- Updated
-
2020-03-09Created from EPrint's last_modified field
- Caltech groups
- Parallel and Distributed Systems Group
- Other Numbering System Name
- Paradise
- Other Numbering System Identifier
- ETR122