Permutation code: Difference between revisions

Revision as of 21:45, 23 June 2025

Latest revision as of 05:16, 27 August 2025

Line 2:

{{Orphan|date=December 2024}}

'''Permutation codes''' are a family of [[Error correction model|error correction codes]] that were introduced first by [[David Slepian|Slepian]] in 1965.<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|url-access=subscription }}</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|url-access=subscription }}</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)|}