Constructing permutation arrays using partition and extension

DOI10.1007/S10623-019-00684-ZMaRDI QIDQ2291664zbMATH OpenOpenAlexWikidataFDO

Authors Sergey Bereg, Luis Gerardo Mojica, Linda Morales, Hal Sudborough

Publication date 31 January 2020

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.08252

zbMATH Keywords

coset methodKronecker productpartition and extensionpermutation arrays

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Partitions of sets (05A18) Linear programming (90C05) Integer programming (90C10) Combinatorial codes (94B25) Bounds on codes (94B65)

Abstract: 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$ is a necessary component of constructing error correcting permutation codes, which have been proposed for power-line communications. Our technique, {em partition and extension}, is universally applicable to constructing such sets for all $n$ and all $d$, $d<n$. We describe three new techniques, {em sequential partition and extension}, {em parallel partition and extension}, and a {em 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 for $M(n,d)$ found using these techniques for $n$ up to $600$.

Review text

Let \(n > d\) be positive integers and \(M(n, d)\) be the largest number of permutations on \(n\) symbols with pairwise Hamming distance at least \(d\). Finding better bounds on \(M(n, d)\) is an interesting combinatorial problem. A universally applicable technique, partition and extension, was introduced recently by the authors to construct sets of permutations on \(n\) symbols with pairwise Hamming distance \(d\). These sets of large sizes were proposed for power-line communication. In this paper, several new computational methods for the partition and extension technique were presented, which produced several competitive new lower bounds on \(M(n, d)\) for various integers \(n\) and \(d\). Among them, the sequential partition and extension is an improvement which uses iteration to extend permutation arrays (PAs) by two or more symbols. The parallel partition and extension introduces several new symbols simultaneously, which can give new lower bounds for \(M (n + r , d )\) by extending PAs on \(n\) symbols with Hamming distance \(d- r\). A modification of the Kronecker product operation on PAs can be used to create larger PAs suitable for simple partition and extension. Moreover, two efficient algorithms for computing new partitions (an iterative greedy algorithm and an algorithm based on integer linear programming) were also presented. Experimental results provide new lower bounds for \(M(n, n -1)\), for many integers \( n< 600\).

Recommendations

• Constructions for permutation codes in powerline communications
• Extending permutation arrays: improving MOLS bounds
• A new table of permutation codes
• Permutation codes with specified packing radius
• Constructing permutation arrays from groups

Cites work

• A new table of permutation codes
• An Improvement on the Gilbert–Varshamov Bound for Permutation Codes
• Bounds for permutation arrays
• Constructing permutation arrays from groups
• Constructing permutation arrays using partition and extension
• Constructions for permutation codes in powerline communications
• Eine Bemerkung zur Abschätzung der Anzahl orthogonaler lateinischer Quadrate mittels Siebverfahren
• Extending permutation arrays: improving MOLS bounds
• scientific article; zbMATH DE number 3906699 (Why is no real title available?)
• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
• On the history of the kronecker product
• Permutation Arrays for Powerline Communication and Mutually Orthogonal Latin Squares
• Permutation codes invariant under isometries
• Powerline communication and the 36 officers problem
• The direct product permuting matrices

Cited in

(15)

• Constructing permutation arrays from groups
• Using permutation rational functions to obtain permutation arrays with large Hamming distance
• Improved lower bounds for permutation arrays using permutation rational functions
• Constructing permutation arrays using partition and extension
• New lower bounds for permutation arrays using contraction
• Two Constructions of Permutation Arrays
• Permutation codes with specified packing radius
• Constructions of permutation arrays
• A construction of product blocks with a fixed block size
• Powerline communication and the 36 officers problem
• Good permutation codes based on the shuffle-exchange network
• Multiple contractions of permutation arrays
• Classes of permutation arrays in finite projective spaces
• Upper bounds on the size of permutation codes with a Hamming distance of five
• A new table of permutation codes

Describes a project that uses

Uses Software

• Gurobi
• CPLEX

This page was built for publication: Constructing permutation arrays using partition and extension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2291664)