Permutation code: Difference between revisions

Revision as of 22:20, 26 October 2022

Revision as of 18:12, 27 October 2022

Line 12:

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

== UpperGilbert-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 arehave exactly k distance away 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 outperformoutperforms 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 shown in the next theorem shows.

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