Computing the Ball Size of Frequency Permutations under Chebyshev Distance

2011/02/14 by Min-Zheng Shieh, Shieh, Min-Zheng, Shi‐Chun Tsai +2
Computer Science · Engineering · Mathematics · #Algorithms and Data Compression #Coding theory and cryptography #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.DM #cs.IT #graph theory and CDMA systems #math.IT

paper · pdf · doi:10.48550/arxiv.1102.2799

Submitted to ISIT 2011

openalex publication_date 2011/02/14 · arxiv created 2011/02/15 · arxiv updated 2011/02/16 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28

Abstract

Let S_n^λ be the set of all permutations over the multiset \\overbrace1,...,1^λ,...,\overbracem,...,m^λ\ where n=mλ. A frequency permutation array (FPA) of minimum distance d is a subset of S_n^λ in which every two elements have distance at least d. FPAs have many applications related to error correcting codes. In coding theory, the Gilbert-Varshamov bound and the sphere-packing bound are derived from the size of balls of certain radii. We propose two efficient algorithms that compute the ball size of frequency permutations under Chebyshev distance. Both methods extend previous known results. The first one runs in O(2dλ\choose dλ^2.376log n) time and O(2dλ\choose dλ²) space. The second one runs in O(2dλ\choose dλdλ+λ\choose λ\fracnλ) time and O(2dλ\choose dλ) space. For small constants λ and d, both are efficient in time and use constant storage space.

Related

• Improved Bounds for Permutation Arrays Under Chebyshev Distance
• Permutation Arrays Under the Chebyshev Distance
• New Lower Bounds on Sizes of Permutation Arrays
• New Upper Bounds on Sizes of Permutation Arrays
• Improved Lower Bounds on the Size of Balls over Permutations with the Infinity Metric