Content deleted Content added
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 |
|||
| (27 intermediate revisions by 14 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
▲Permutation codes are a family of [[error correction code]] 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 |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 |last=Han |first=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 |issn=1089-7798}}</ref> and [[Power-line communication]] <ref>{{Cite journal |last=Chu |first=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 |issn=0925-1022}}</ref>.
A permutation code <math>C</math> is defined as a subset of the [[Symmetric group|Symmetric Group]] in <math>S_n</math> endowed with the usual [[Hamming distance]] between strings of length <math>n</math>. More precisely, if <math>\sigma, \tau</math> are permutations in <math>S_n</math>, then <math>d(\tau, \sigma) = |\left \{ i \in \{1, 2, ..., n\} : \sigma(i) \neq \tau(i) \right \}|</math>▼
The minimum distance of a permutation code <math>C</math> is defined to be the minimum positive integer <math>d_{min}</math> such that there exist <math>\sigma, \tau</math> <math>\in</math> <math>C</math>, distinct, such that <math>d(\sigma, \tau) = d_{min} </math>.▼
▲== Definition and Properties ==
▲A permutation code <math>C</math> is defined as a subset of the [[Symmetric group|Symmetric Group]] in <math>S_n</math> endowed with the usual [[Hamming distance]] between strings of length <math>n</math>. More precisely, if <math>\sigma, \tau</math> are permutations in <math>S_n</math>, then<math>
One of the reasons why permutation codes are suitable for certain channels is that the alphabet symbols only appear once in each codeword, which for example makes the errors occurring in the context of [[Power-line communication|powerline]] communication less impactful on codewords▼
▲The minimum distance of a permutation code is defined to be the minimum positive integer <math>d_{min}</math> such that there exist <math>\sigma, \tau</math> <math>\in</math> <math>C</math>, distinct, such that <math>d(\sigma, \tau) = d_{min} </math>.
== Gilbert-Varshamov bound ==
▲One of the reasons why permutation codes are suitable for certain channels is that alphabet symbols only appear once in each codeword, which for example makes the errors occurring in the context of [[Power-line communication|powerline]] communication less impactful on codewords
A main problem in permutation codes is to determine the value of <math>M(n,d)</math>, where <math>M(n,d)</math> is defined to be the maximum number of codewords in a permutation code of length <math>n</math> and minimum distance <math>d</math>. There has been little progress made for <math>4 \leq d \leq n-1</math>, except for small lengths. We can define <math>D(n,k)</math> with <math>k
Let <math>D(n,k)= \{ \sigma \in S_n
▲A main problem in permutation codes is to determine the value of M(n,d). There has been little progress made for 4 \leq d \leq n-1, except for small lengths. We can define D(n,k) with k=0,1,…,n to denote the set of all permutations in S_n which are exactly k distance away from the identity.
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>.
▲D(n,k)= { \sigma \in S_n : d_H (\sigma, id)=k} with |D(n,k)|={n choose k)D_k. where D_k is the number of derangements of order k.
'''Theorem 1''': <math>\frac{n!}{
</math>
▲Theorem 1: 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)|}
'''Theorem 2''': If <math>k^2 \leq n \leq k^2+k-2</math> for some integer <math>k \geq 2</math>, then
▲This theorem works for small values of d, and there has been improvements on it for the case where d=4, as shown in the next theorem.
<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>.▼
▲Theorem 2: If k^2 \leq n \leq k^2+k-2 for some integer k \geq 2, then
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>
▲\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)}.
== Other Bounds ==
There are numerous bounds on permutation codes, we list two here
==
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>.
== References ==▼
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>
Then, <math>M(n, d) \ge M_{IS}(n, d)</math>
where <math>\Delta(n, d) = \sum_{k = 0}^{d - 1}\binom{n}{k}D_k</math>.
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 ===
Using a <math>[n, k, d]_q</math> linear block code, one can prove that there exists a permutation code in the symmetric group of degree <math>n</math>, having minimum distance at least <math>d</math> and large cardinality.<ref name=":1">G. Micheli and A. Neri, "New Lower Bounds for Permutation Codes Using Linear Block Codes," in IEEE Transactions on Information Theory, vol. 66, no. 7, pp. 4019-4025, July 2020, doi: 10.1109/TIT.2019.2957354.</ref> A lower bound for permutation codes that provides asymptotic improvements in certain regimes of length and distance of the permutation code<ref name=":1" /> is discussed below. For a given subset <math>\Kappa</math> of the symmetric group <math>S_n</math>, we denote by <math>M(\Kappa, d)</math> the maximum cardinality of a permutation code of minimum distance at least <math>d</math> entirely contained in <math>\Kappa</math>, i.e.
<math>M(\Kappa, d) = max\{|\Gamma| : \Gamma \subset \Kappa , d(\Gamma) \ge d\}</math>.
'''Theorem 5:''' Let <math>d, k, n</math> be integers such that <math>0 < k < n</math> and <math>1 < d \le n</math>. Moreover let <math>q</math> be a prime power and <math>s, r</math> be positive integers such that <math>n = qs + r</math> and <math>0 \le r < q</math>. If there exists an <math>[n, k, d]_q</math> code <math>C</math> such that <math>C^\perp</math> has a codeword of Hamming weight <math>n</math>, then
<math>M(n, d) \ge \frac{n!M(\Kappa, d)}{(s + 1)!^r s!^{q-r}q^{n - k -1}},</math>
where <math>\Kappa = (S_{s + 1})^r \times (S_s)^{q-r}</math>
'''Corollary 1''': for every prime power <math>q \ge n</math>, for every <math>2 < d \le n</math>,
<math>M(n, d) \ge \frac{n!}{q^{d - 2}}</math>.
'''Corollary 2''': for every prime power <math>q </math>, for every <math>3 < d < q</math>,
<math>M(q + 1, d) \ge \frac{(q + 1)!}{2q^{d - 2}}</math>.
{{reflist}}
[[Category:Error detection and correction]]
| |||