Permutation codes are a family of error correction codes 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 {\displaystyle C} is defined as a subset of the Symmetric Group in S n {\displaystyle S_{n}} endowed with the usual Hamming distance between strings of length n {\displaystyle n} . More precisely, if σ , τ {\displaystyle \sigma ,\tau } are permutations in S n {\displaystyle S_{n}} , then d ( τ , σ ) = | { i ∈ { 1 , 2 , . . . , n } : σ ( i ) ≠ τ ( i ) } | {\displaystyle d(\tau ,\sigma )=|\left\{i\in \{1,2,...,n\}:\sigma (i)\neq \tau (i)\right\}|}
The minimum distance of a permutation code C {\displaystyle C} is defined to be the minimum positive integer d m i n {\displaystyle d_{min}} such that there exist σ , τ {\displaystyle \sigma ,\tau } ∈ {\displaystyle \in } C {\displaystyle C} , distinct, such that d ( σ , τ ) = d m i n {\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
… excerpt ends here. Continue reading the full article.
