Permutation code

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

Definition and Properties

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

Upper Bound

Gilbert-Varshamov (page 2 of the document)

Lower Bound

We can look at a few different lower bounds on the permutation codes. Using the results from the theory of MDS, or Maximum Distance Separable, codes to provide two new lower bounds. The first of the two is when you are dealing with the next prime power larger than or equal to n is smaller than the next prime larger than or equal to n. The second has to do with large distances. We use the results of a theorem to be able to understand further theorems that get us to these MDS lower bounds.

Theorem 1: Let d,k,n be integers such that 0 < k < n and 1 < d ≤ n. Moreover, let q be a prime power and s,r be positive integers such that n = qs+r and 0 ≤ r < q. If there exists an [n,k,d]q code C such that C^⊥ has a codeword of Hamming weight n, then M(n,d) ≥ {n!M(K,d)}/{(s + 1)!^rs!^{q-r} q^{n-k-1}}, whereK=(S_{s+1})^r ×(S_s)^{q-r} .

The proof is extensive and can be found here ^[7]. Now we can take a look at another theorem that follows directly from the previous.

Theorem 2:For every prime power q ≥ n, and every integer d with 2<d<n, M(n,d) ≥ n!/q^{d-2}.

The proof of this follows directly from the previous theorem. This second theorem provides a lower bound on M(nod) using the existence of MDS codes of length n over a finite field with cardinality at least n.

Now we can take a look into the lower bounds that deal with large distances. Another theorem can be obtained from the first, and it states

Theorem 3:For every prime power q, and every 3 < d < q, M(q+1,d) ≥ (q+1)^!/2q^{d-2}.

Again, the proof follows directly from the first theorem. With the second theorem above this allows our q to be the next prime power greater than or equal to n, we beat - or at least equal - previously found bounds. If n-1 is the next prime power, the third theorem shown above beats previously found bounds asymptotically in large distance.

References

1. "Codes on Euclidean Spheres, Volume 63 - 1st Edition". www.elsevier.com. Retrieved 2022-09-20. Holland Mathematical Library. North-Holland Publishing Co., Amsterdam, 2001.
2. Slepian, D. (March 1965). "Permutation modulation". Proceedings of the IEEE. 53 (3): 228–236. doi:10.1109/PROC.1965.3680. ISSN 1558-2256.
3. Cameron, Peter J. (2010-02-01). "Permutation codes". European Journal of Combinatorics. 31 (2): 482–490. doi:10.1016/j.ejc.2009.03.044. ISSN 0195-6698.
4. Tarnanen, H. (January 1999). "Upper Bounds on Permutation Codes via Linear Programming". European Journal of Combinatorics. 20 (1): 101–114. doi:10.1006/eujc.1998.0272. ISSN 0195-6698. J. Combin., 20(1):101–114, 1999
5. Han, Hui; Mu, Jianjun; He, Yu-Cheng; Jiao, Xiaopeng; Ma, Wenping (April 2020). "Multi-Permutation Codes Correcting a Single Burst Unstable Deletions in Flash Memory". IEEE Communications Letters. 24 (4): 720–724. doi:10.1109/LCOMM.2020.2966619. ISSN 1089-7798.
6. Chu, Wensong; Colbourn, Charles J.; Dukes, Peter (May 2004). "Constructions for Permutation Codes in Powerline Communications". Designs, Codes and Cryptography. 32 (1–3): 51–64. doi:10.1023/b:desi.0000029212.52214.71. ISSN 0925-1022.
7. https://www.adarshsrinivasan.com/publication/permutation-error-correcting-codes-and-their-applications-to-public-key-cryptography/permutation-error-correcting-codes-and-their-applications-to-public-key-cryptography.pdf.