Permutation code

This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (December 2024)

Permutation codes are a family of error correction codes that were introduced first by Slepian in 1965.^[1] and have been widely studied both in Combinatorics^[2][3] and Information theory due to their applications related to Flash memory^[4] and Power-line communication.^[5]

A permutation code ${\displaystyle C}$ is defined as a subset of the Symmetric Group in ${\displaystyle S_{n}}$ endowed with the usual Hamming distance between strings of length ${\displaystyle n}$. More precisely, if ${\displaystyle \sigma ,\tau }$ are permutations in ${\displaystyle S_{n}}$, then ${\displaystyle d(\tau ,\sigma )=|\left\{i\in \{1,2,...,n\}:\sigma (i)\neq \tau (i)\right\}|}$

The minimum distance of a permutation code ${\displaystyle C}$ is defined to be the minimum positive integer ${\displaystyle d_{min}}$ such that there exist ${\displaystyle \sigma ,\tau }$ ${\displaystyle \in }$ ${\displaystyle C}$, distinct, such that ${\displaystyle d(\sigma ,\tau )=d_{min}}$.

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 powerline communication less impactful on codewords

A main problem in permutation codes is to determine the value of ${\displaystyle M(n,d)}$, where ${\displaystyle M(n,d)}$ is defined to be the maximum number of codewords in a permutation code of length ${\displaystyle n}$ and minimum distance ${\displaystyle d}$. There has been little progress made for ${\displaystyle 4\leq d\leq n-1}$, except for small lengths. We can define ${\displaystyle D(n,k)}$ with ${\displaystyle k\in \{0,1,...,n\}}$ to denote the set of all permutations in ${\displaystyle S_{n}}$ which have distance exactly ${\displaystyle k}$ from the identity.

Let ${\displaystyle D(n,k)=\{\sigma \in S_{n}:d_{H}(\sigma ,id)=k\}}$ with ${\displaystyle |D(n,k)|={\tbinom {n}{k}}D_{k}}$, where ${\displaystyle D_{k}}$ is the number of derangements of order ${\displaystyle k}$.

The Gilbert-Varshamov bound is a very well known upper bound,^[6] and so far outperforms other bounds for small values of ${\displaystyle d}$.

Theorem 1: ${\displaystyle {\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)|}}}$

There has been improvements on it for the case where ${\displaystyle d=4}$ ^[6] as the next theorem shows.

Theorem 2: If ${\displaystyle k^{2}\leq n\leq k^{2}+k-2}$ for some integer ${\displaystyle k\geq 2}$, then

${\displaystyle {\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)}}}$.

For small values of ${\displaystyle n}$ and ${\displaystyle d}$, researchers have developed various computer searching strategies to directly look for permutation codes with some prescribed automorphisms ^[7]

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 asymptotically by a factor ${\displaystyle \log(n)}$, when the code length goes to infinity.^[8]

Let ${\displaystyle G(n,d)}$ denote the subgraph induced by the neighbourhood of identity in ${\displaystyle \Gamma (n,d)}$, the Cayley graph ${\displaystyle \Gamma (n,d):=\Gamma (S_{n},S(n,d-1))}$ and ${\displaystyle S(n,k):=\bigcup _{i=1}^{k}D(n,i)}$.

Let ${\displaystyle m(n,d)}$ denotes the maximum degree in ${\displaystyle G(n,d)}$

Theorem 3: Let ${\displaystyle m'(n,d)=m(n,d)+1}$ and

${\displaystyle 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}$

Then, ${\displaystyle M(n,d)\geq M_{IS}(n,d)}$

where ${\displaystyle \Delta (n,d)=\sum _{k=0}^{d-1}{\binom {n}{k}}D_{k}}$.

The Gilbert-Varshamov bound is, ${\displaystyle M(n,d)\geq M_{GV}(n,d):={\frac {n!}{1+\Delta (n,d)}}}$

Theorem 4: when ${\displaystyle d}$ is fixed and ${\displaystyle n}$ does to infinity, we have

${\displaystyle {\frac {M_{IS}(n,d)}{M_{GV}(n,d)}}=\Omega (\log(n))}$

Using a ${\displaystyle [n,k,d]_{q}}$ linear block code, one can prove that there exists a permutation code in the symmetric group of degree ${\displaystyle n}$, having minimum distance at least ${\displaystyle d}$ and large cardinality.^[9] A lower bound for permutation codes that provides asymptotic improvements in certain regimes of length and distance of the permutation code^[9] is discussed below. For a given subset ${\displaystyle \mathrm {K} }$ of the symmetric group ${\displaystyle S_{n}}$, we denote by ${\displaystyle M(\mathrm {K} ,d)}$ the maximum cardinality of a permutation code of minimum distance at least ${\displaystyle d}$ entirely contained in ${\displaystyle \mathrm {K} }$, i.e.

${\displaystyle M(\mathrm {K} ,d)=max\{|\Gamma |:\Gamma \subset \mathrm {K} ,d(\Gamma )\geq d\}}$.

Theorem 5: Let ${\displaystyle d,k,n}$ be integers such that ${\displaystyle 0<k<n}$ and ${\displaystyle 1<d\leq n}$. Moreover let ${\displaystyle q}$ be a prime power and ${\displaystyle s,r}$ be positive integers such that ${\displaystyle n=qs+r}$ and ${\displaystyle 0\leq r<q}$. If there exists an ${\displaystyle [n,k,d]_{q}}$ code ${\displaystyle C}$ such that ${\displaystyle C^{\perp }}$ has a codeword of Hamming weight ${\displaystyle n}$, then

${\displaystyle M(n,d)\geq {\frac {n!M(\mathrm {K} ,d)}{(s+1)!^{r}s!^{q-r}q^{n-k-1}}},}$

where ${\displaystyle \mathrm {K} =(S_{s+1})^{r}\times (S_{s})^{q-r}}$

Corollary 1: for every prime power ${\displaystyle q\geq n}$, for every ${\displaystyle 2<d\leq n}$,

${\displaystyle M(n,d)\geq {\frac {n!}{q^{d-2}}}}$.

Corollary 2: for every prime power ${\displaystyle q}$, for every ${\displaystyle 3<d<q}$,

${\displaystyle M(q+1,d)\geq {\frac {(q+1)!}{2q^{d-2}}}}$.