×

zbMATH — the first resource for mathematics

Constructing permutation arrays using partition and extension. (English) Zbl 07161120
Summary: We give new lower bounds for \(M(n, d)\), for various positive integers \(n\) and \(d\) with \(n>d\), where \(M(n, d)\) is the largest number of permutations on \(n\) symbols with pairwise Hamming distance at least \(d\). Large sets of permutations on \(n\) symbols with pairwise Hamming distance \(d\) are needed for constructing error correcting permutation codes, which have been proposed for power-line communications. Our technique, partition and extension, is universally applicable to constructing such sets for all \(n\) and all \(d, d<n\). We describe three new techniques, sequential partition and extension, parallel partition and extension, and a modified Kronecker product operation, which extend the applicability of partition and extension in different ways. We describe how partition and extension gives improved lower bounds for \(M(n,n-1)\) using mutually orthogonal Latin squares (MOLS). We present efficient algorithms for computing new partitions: an iterative greedy algorithm and an algorithm based on integer linear programming. These algorithms yield partitions of positions (or symbols) used as input to our partition and extension techniques. We report many new lower bounds for \(M(n, d)\) found using these techniques for \(n\) up to 600.
MSC:
05A05 Permutations, words, matrices
94B25 Combinatorial codes
05A18 Partitions of sets
90C10 Integer programming
90C05 Linear programming
94B65 Bounds on codes
Software:
CPLEX; Gurobi
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bereg S., Hancock Z., Mojica L.G., Morales L., Sudborough H., Wong A.: Permutation arrays for \(p^k+1\), where \(p\) is prime. Manuscript (2017).
[2] Bereg S., Mojica L.G., Morales L., Sudborough H.: Kronecker product and tiling of permutation arrays for hamming distances. In: the 2017 IEEE International Symposium on Information Theory (ISIT), pp. 2198-2202 (2017).
[3] Bereg S., Mojica L.G., Morales L., Sudborough I.H.: Parallel partition and extension. In: 51st Annual Conference on Information Sciences and Systems (CISS 2017), pp. 1-6 (2017).
[4] Bereg, S.; Morales, L.; Sudborough, Ih, Extending permutation arrays: improving MOLS bounds, Des. Codes Cryptogr., 83, 3, 661-683 (2017) · Zbl 1359.05002
[5] Bereg, S.; Levy, A.; Sudborough, Ih, Constructing permutation arrays from groups, Des. Codes Cryptogr., 86, 5, 1095-1111 (2018) · Zbl 1396.05003
[6] Cameron, Pj, Permutation Groups (1999), New York:: Cambridge University Press, New York:
[7] Chu, W.; Colbourn, Cj; Dukes, P., Constructions for permutation codes in powerline communications, Des. Codes Cryptogr., 32, 51-64 (2004) · Zbl 1065.94003
[8] Colbourn, Cj; Dinitz, Jh, Handbook of Combinatorial Designs (2006), Boca Raton: CRC Press, Boca Raton
[9] Colbourn, C.; Kløve, T.; Ling, Ac, Permutation arrays for powerline communication and mutually orthogonal latin squares, IEEE Trans. Inf. Theory, 50, 6, 1289-1291 (2004) · Zbl 1296.94011
[10] Conway, Jh; Curtis, Rt; Norton, Sp; Parker, Ra, Atlas of Finite Groups (1985), Oxford: Oxford University Press, Oxford
[11] Deza, M.; Vanstone, Sa, Bounds for permutation arrays, J. Stat. Plan. Inference, 2, 197-209 (1978) · Zbl 0384.05026
[12] Dixon, Jd; Mortimer, B., Permutation Groups (1996), New York: Springer, New York
[13] Gao, F.; Yang, Y.; Ge, G., An improvement on the Gilbert-Varshamov bound for permutation codes, IEEE Trans. Inf. Theory, 59, 5, 3059-3063 (2013) · Zbl 1364.94781
[14] Gurobi I.: Optimization. Gurobi Optimizer Reference Manual (2016).
[15] Henderson, Hv; Pukelsheim, F.; Searle, Sr, On the history of the Kronecker product, Linear Multilinear Algebra, 14, 2, 113-120 (1983) · Zbl 0517.15017
[16] Holmquist, B., The direct product permuting matrices, Linear Multilinear Algebra, 17, 2, 117-141 (1985) · Zbl 0566.15012
[17] Huczynska, S., Powerline communication and the 36 officers problem, Philos. Trans. R. Soc. Lond. A Math. Phys. Eng. Sci., 364, 1849, 3199-3214 (2006) · Zbl 1152.05301
[18] IBM ILOG: CPLEX. V12. 1: User’s manual for CPLEX. Int. Bus. Mach. Corp. 46(53), 157 (2009).
[19] Janiszczak, I.; Lempken, W.; Östergård, Prj; Staszewski, R., Permutation codes invariant under isometries, Des. Codes Cryptogr., 75, 3, 497-507 (2015) · Zbl 1312.05010
[20] Mojica L.G.: Permutation arrays with large Hamming distance. PhD Thesis, University of Texas at Dallas, Richardson (2017).
[21] Nguyen Q.T.: Transitivity and hamming distance of permutation arrays. PhD thesis, University of Texas at Dallas, Richardson (2013)
[22] Pavlidou, N.; Vinck, Ah; Yazdani, J.; Honary, B., Power line communications: state of the art and future trends, IEEE Commun. Mag., 41, 4, 34-40 (2003)
[23] Smith, Dh; Montemanni, R., A new table of permutation codes, Des. Codes Cryptogr., 63, 2, 241-253 (2012) · Zbl 1237.05008
[24] Von Beth, T., Eine bemerkung zur abschätzung der anzahl orthogonaler lateinischer quadrate mittels siebverfahren, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 53, 1, 284-288 (1983) · Zbl 0507.05010
[25] Wang, X.; Zhang, Y.; Yang, Y.; Ge, G., New bounds of permutation codes under hamming metric and Kendall’s \(\tau \)-metric, Des. Codes Cryptogr., 85, 3, 533-545 (2017) · Zbl 1417.94117
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.