Content deleted Content added
Submitting using AfC-submit-wizard |
Citation bot (talk | contribs) Alter: url, issue, date. URLs might have been anonymized. Add: s2cid, authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | Category:CS1 errors: dates | #UCB_Category 54/299 |
||
Line 6:
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 |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 |
== Definition and Properties ==
Line 22:
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 |
'''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 33:
<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 |
==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. -->
| |||