Permutation code: Difference between revisions

Revision as of 03:24, 24 December 2024

Latest revision as of 05:16, 27 August 2025

(4 intermediate revisions by 3 users not shown)

Line 2:

{{Orphan|date=December 2024}}

'''Permutation codes''' are a family of [[Error correction model|error correction codecodes]]s that were introduced first by [[David Slepian|Slepian]] in 1965.<ref>{{Cite book |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|date=27 April 2001 |isbn=978-0-444-50329-9 |last1=Ericson |first1=Thomas |last2=Zinoviev |first2=Victor |publisher=Elsevier }} 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 |journal=European Journal of Combinatorics |volume=31 |issue=2 |pages=482–490 |doi=10.1016/j.ejc.2009.03.044 |issn=0195-6698|doi-access=free }}</ref><ref>{{Cite journal |last=Tarnanen |first=H. |date=January 1999 |title=Upper Bounds on Permutation Codes via Linear Programming |journal=European Journal of Combinatorics |volume=20 |issue=1 |pages=101–114 |doi=10.1006/eujc.1998.0272 |issn=0195-6698|doi-access=free }} 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 |bibcode=2020IComL..24..720H |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|url-access=subscription }}</ref>

== Definition and properties ==

Line 17:

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]]s of order <math>k</math>.

The [[Gilbert–Varshamov bound|Gilbert-Varshamov bound]] is a very well known upper bound,<ref name=":0">{{Cite journal |last1=Gao |first1=Fei |last2=Yang |first2=Yiting |last3=Ge |first3=Gennian |date=May 2013 |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 |bibcode=2013ITIT...59.3059G |s2cid=13397633 |issn=0018-9448|url-access=subscription }}</ref> and so far outperforms other bounds for small values of <math>d</math>.

'''Theorem 1''': <math>\frac{n!}{\sum _{k=0} ^{d-1} |D(n,k)|} \leq M(n,d) \leq \frac{n!}{\sum _{k=0} ^{[\frac{d-1}{2}]} |D(n,k)|}

Line 28:

<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]]s <ref>{{Cite journal |last1=Smith |first1=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 |s2cid=207115236 |issn=0925-1022|hdl=11380/1176210 |hdl-access=free }}</ref>

== Other Bounds ==