Permutation code: Difference between revisions

Revision as of 17:29, 17 December 2024

Revision as of 03:24, 24 December 2024

Line 1:

{{Short description|Class of error correction codes}}

{{Orphan|date=December 2024}}

'''Permutation codes''' are a family of [[error correction code]]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 |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 properties ==

Line 33 ⟶ 34:

=== Gilbert-Varshamov Bound Improvement ===

An Improvement is done to the Gilbert-Varshamov bound already discussed above. Using the connection between permutation codes and independent sets in certain graphs one can improve the Gilbert–Varshamov bound [[Asymptote|asymptotically]] by a factor <math>\log(n)</math>, when the code length goes to infinity. <ref>F. Gao, Y. Yang and G. Ge, "An Improvement on the Gilbert–Varshamov Bound for Permutation Codes," in IEEE Transactions on Information Theory, vol. 59, no. 5, pp. 3059-3063, May 2013, doi: 10.1109/TIT.2013.2237945.</ref>

Let <math>G(n, d)</math> denote the subgraph induced by the neighbourhood of identity in <math>\Gamma (n, d)</math>, the [[Cayley graph]] <math>\Gamma (n, d) := \Gamma (S_n, S(n, d - 1))</math> and <math>S(n, k):= \bigcup_{i = 1}^k D(n, i)</math>.

Line 39 ⟶ 40:

Let <math>m(n, d)</math> denotes the maximum degree in <math>G(n, d)</math>

'''Theorem 3''': Let <math>m'(n, d) = m(n, d) + 1</math> and

<math>M_{IS}(n, d) := n!.\int_0^1 \frac{(1 - t)^{\frac{1}{m'(n, d)}}}{m'(n, d) + [\Delta(n, d) - m'(n, d)]t}dt</math>

Line 49 ⟶ 50:

The Gilbert-Varshamov bound is, <math>M(n, d) \ge M_{GV}(n, d) := \frac{n!}{1 + \Delta(n, d)}</math>

'''Theorem 4''': when <math>d</math> is fixed and <math>n</math> does to infinity, we have

<math>\frac{M_{IS}(n, d)}{M_{GV}(n, d)} = \Omega(\log(n))</math>

=== Lower bounds using linear codes ===

Line 74 ⟶ 75:

==References==

{{reflist}}

[[Category:Error detection and correction]]