Content deleted Content added
Citation bot (talk | contribs) Altered template type. Add: publisher, isbn, date, authors 1-2. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Error detection and correction | #UCB_Category 68/128 |
Citation bot (talk | contribs) Added bibcode. Removed URL that duplicated identifier. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 60/967 |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 1:
{{Short description|Class of error correction codes}}
{{Orphan|date=December 2024}}
'''Permutation codes''' are a family of [[Error correction model|error correction
== Definition and properties ==
Line 16 ⟶ 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 27 ⟶ 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 ==
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.
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]]
| |||