Content deleted Content added
m Pichpich moved page Permutation Codes to Permutation codes: Change to sentence case (MOS:AT) |
sentence case |
||
Line 3:
Permutation codes are a family of [[error correction code]]s that were introduced first by [[David Slepian|Slepian]] in 1965.<ref>{{Cite web |title=Codes on Euclidean Spheres, Volume 63 - 1st Edition |url=https://www.elsevier.com/books/codes-on-euclidean-spheres/ericson/978-0-444-50329-9 |access-date=2022-09-20 |website=www.elsevier.com}} Holland Mathematical Library. North-Holland Publishing Co., Amsterdam, 2001.</ref><ref>{{Cite journal |last=Slepian |first=D. |date=March 1965 |title=Permutation modulation |url=https://ieeexplore.ieee.org/document/1445610 |journal=Proceedings of the IEEE |volume=53 |issue=3 |pages=228–236 |doi=10.1109/PROC.1965.3680 |s2cid=124937273 |issn=1558-2256}}</ref> and have been widely studied both in [[Combinatorics]]<ref>{{Cite journal |last=Cameron |first=Peter J. |date=2010-02-01 |title=Permutation codes |url=https://doi.org/10.1016/j.ejc.2009.03.044 |journal=European Journal of Combinatorics |volume=31 |issue=2 |pages=482–490 |doi=10.1016/j.ejc.2009.03.044 |issn=0195-6698}}</ref><ref>{{Cite journal |last=Tarnanen |first=H. |date=January 1999 |title=Upper Bounds on Permutation Codes via Linear Programming |url=http://dx.doi.org/10.1006/eujc.1998.0272 |journal=European Journal of Combinatorics |volume=20 |issue=1 |pages=101–114 |doi=10.1006/eujc.1998.0272 |issn=0195-6698}} J. Combin., 20(1):101–114, 1999</ref> and [[Information theory]] due to their applications related to [[Flash memory]]<ref>{{Cite journal |last1=Han |first1=Hui |last2=Mu |first2=Jianjun |last3=He |first3=Yu-Cheng |last4=Jiao |first4=Xiaopeng |last5=Ma |first5=Wenping |date=April 2020 |title=Multi-Permutation Codes Correcting a Single Burst Unstable Deletions in Flash Memory |url=https://ieeexplore.ieee.org/document/8959303 |journal=IEEE Communications Letters |volume=24 |issue=4 |pages=720–724 |doi=10.1109/LCOMM.2020.2966619 |s2cid=214381288 |issn=1089-7798}}</ref> and [[Power-line communication]].<ref>{{Cite journal |last1=Chu |first1=Wensong |last2=Colbourn |first2=Charles J. |last3=Dukes |first3=Peter |date=May 2004 |title=Constructions for Permutation Codes in Powerline Communications |url=http://dx.doi.org/10.1023/b:desi.0000029212.52214.71 |journal=Designs, Codes and Cryptography |volume=32 |issue=1–3 |pages=51–64 |doi=10.1023/b:desi.0000029212.52214.71 |s2cid=18529905 |issn=0925-1022}}</ref>
== Definition and
A permutation code <math>C</math> is defined as a subset of the [[Symmetric group|Symmetric Group]] in <math>S_n</math> endowed with the usual [[Hamming distance]] between strings of length <math>n</math>. More precisely, if <math>\sigma, \tau</math> are permutations in <math>S_n</math>, then<math>
d(\tau, \sigma) = |\left \{ i \in \{1, 2, ..., n\} : \sigma(i) \neq \tau(i) \right \}|</math>
Line 11:
One of the reasons why permutation codes are suitable for certain channels is that the alphabet symbols only appear once in each codeword, which for example makes the errors occurring in the context of [[Power-line communication|powerline]] communication less impactful on codewords
== Gilbert-Varshamov
A main problem in permutation codes is to determine the value of <math>M(n,d)</math>, where <math>M(n,d)</math> is defined to be the maximum number of codewords in a permutation code of length <math>n</math> and minimum distance <math>d</math>. There has been little progress made for <math>4 \leq d \leq n-1</math>, except for small lengths. We can define <math>D(n,k)</math> with <math>k \in \{0, 1, ..., n\}</math> to denote the set of all permutations in <math>S_n</math> which have distance exactly <math>k</math> from the identity.
| |||