Content deleted Content added
Line 2:
Permutation codes are a family of [[error correction code|error correction codes]] 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 |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 |last=Han |first=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 |issn=1089-7798}}</ref> and [[Power-line communication]] <ref>{{Cite journal |last=Chu |first=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 |issn=0925-1022}}</ref>.
== Definition and Properties ==
Line 8:
d(\tau, \sigma) = |\left \{ i \in \{1, 2, ..., n\} : \sigma(i) \neq \tau(i) \right \}|</math>
The minimum distance of a permutation code <math>C</math> is defined to be the minimum positive integer <math>d_{min}</math> such that there exist <math>\sigma, \tau</math> <math>\in</math> <math>C</math>, distinct, such that <math>d(\sigma, \tau) = d_{min} </math>.
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 Bound ==
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
Let <math>D(n,k)= \{ \sigma \in S_n: d_H (\sigma, id)=k\}</math> with <math>|D(n,k)|=\tbinom{n}{k}D_k</math>, where <math>D_k</math> is the number of [[Derangement|derangements]] of order <math>k</math>.
The [[Gilbert–Varshamov bound|Gilbert-Varshamov bound]] is a very well known upper bound <ref name=":0">{{Cite journal |last=Gao |first=Fei |last2=Yang |first2=Yiting |last3=Ge |first3=Gennian |date=2013-05 |title=An Improvement on the Gilbert–Varshamov Bound for Permutation Codes |url=http://dx.doi.org/10.1109/tit.2013.2237945 |journal=IEEE Transactions on Information Theory |volume=59 |issue=5 |pages=3059–3063 |doi=10.1109/tit.2013.2237945 |issn=0018-9448}}</ref>, and so far outperforms other bounds for small values of <math>d</math>.
Line 29:
<math>\frac{n!}{M(n,4)} \geq 1 + \frac{(n+1)n(n-1)}{n(n-1)-(n-k^2)((k+1)^2-n)((k+2)(k-1)-n)}</math>.
For small values of <math>n</math> and <math>d</math>, researchers have developed various computer searching strategies to directly look for permutation codes with some prescribed [[Automorphism|automorphisms]] <ref>{{Cite journal |last=Smith |first=Derek H. |last2=Montemanni |first2=Roberto |date=2011-08-19 |title=A new table of permutation codes |url=http://dx.doi.org/10.1007/s10623-011-9551-8 |journal=Designs, Codes and Cryptography |volume=63 |issue=2 |pages=241–253 |doi=10.1007/s10623-011-9551-8 |issn=0925-1022}}</ref>.
==References==<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->
| |||