Jump to content

Permutation codes

From Wikipedia, the free encyclopedia

Permutation codes are a family of error correction codes 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

[edit]

A permutation code is defined as a subset of the Symmetric Group in endowed with the usual Hamming distance between strings of length . More precisely, if are permutations in , then

The minimum distance of a permutation code is defined to be the minimum positive integer such that there exist , distinct, such that .

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

Gilbert-Varshamov bound

[edit]

A main problem in permutation codes is to determine the value of , where is defined to be the maximum number of codewords in a permutation code of length and minimum distance . There has been little progress made for , except for small lengths. We can define with to denote the set of all permutations in which have distance exactly from the identity.

Let with , where is the number of derangements of order .

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

Theorem 1:

There has been improvements on it for the case where [7] as the next theorem shows.

Theorem 2: If for some integer , then

.

For small values of and , researchers have developed various computer searching strategies to directly look for permutation codes with some prescribed automorphisms [8]

Other Bounds

[edit]

There are numerous bounds on permutation codes, we list two here

Gilbert-Varshamov Bound Improvement

[edit]

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 , when the code length goes to infinity. [9]

Let denote the subgraph induced by the neighbourhood of identity in , the Cayley graph and .

Let denotes the maximum degree in

Theorem 3: Let and

Then,

where .

The Gilbert-Varshamov bound is,

Theorem 4: when is fixed and does to infinity, we have

Lower bounds using linear codes

[edit]

Using a linear block code, one can prove that there exists a permutation code in the symmetric group of degree , having minimum distance at least and large cardinality.[10] A lower bound for permutation codes that provides asymptotic improvements in certain regimes of length and distance of the permutation code[10] is discussed below. For a given subset of the symmetric group , we denote by the maximum cardinality of a permutation code of minimum distance at least entirely contained in , i.e.

.

Theorem 5: Let be integers such that and . Moreover let be a prime power and be positive integers such that and . If there exists an code such that has a codeword of Hamming weight , then

where

Corollary 1: for every prime power , for every ,

.

Corollary 2: for every prime power , for every ,

.

References

[edit]
  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. S2CID 124937273.
  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. S2CID 214381288.
  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. S2CID 18529905.
  7. ^ a b Gao, Fei; Yang, Yiting; Ge, Gennian (May 2013). "An Improvement on the Gilbert–Varshamov Bound for Permutation Codes". IEEE Transactions on Information Theory. 59 (5): 3059–3063. doi:10.1109/tit.2013.2237945. ISSN 0018-9448. S2CID 13397633.
  8. ^ Smith, Derek H.; Montemanni, Roberto (2011-08-19). "A new table of permutation codes". Designs, Codes and Cryptography. 63 (2): 241–253. doi:10.1007/s10623-011-9551-8. ISSN 0925-1022. S2CID 207115236.
  9. ^ F. Gao, Y. Yang and G. Ge, "An Improvement on the Gilbert–Varshamov Bound for Permutation Codes," in IEEE Transactions on Information Theory, vol. 59, no. 5, pp. 3059-3063, May 2013, doi: 10.1109/TIT.2013.2237945.
  10. ^ a b G. Micheli and A. Neri, "New Lower Bounds for Permutation Codes Using Linear Block Codes," in IEEE Transactions on Information Theory, vol. 66, no. 7, pp. 4019-4025, July 2020, doi: 10.1109/TIT.2019.2957354.