Permutation code

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

Definition and Properties

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

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

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

Gilbert-Varshamov Bound

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 \in 0,1,…,n to denote the set of all permutations in S_n which have exactly k distance from the identity.

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.

The Gilbert-Varshamov bound is a very well known upper bound, and so far outperforms other bounds for small values of d.

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)|}

This theorem works for small values of d, and there has been improvements on it for the case where d=4 as the next theorem shows.

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

\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 n and d, researchers have developed various computer searching strategies to directly look for permutation codes with some prescribed automorphisms. These methods usually provide the best known lower bounds on M(n,d).