Computing the ball size of frequency permutations under Chebyshev distance

DOI10.1016/J.LAA.2012.02.016MaRDI QIDQ417597zbMATH OpenOpenAlexFDO

Authors Min-Zheng Shieh, Shi-Chun Tsai

Publication date 14 May 2012

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

permutationalgorithmGilbert-Varshamov bounderror correcting codespermanentcoding theoryfrequency permutation arraysphere-packing bound

Mathematics Subject Classification ID

Boolean and Hadamard matrices (15B34) Determinants, permanents, traces, other special matrix functions (15A15) Linear codes (general theory) (94B05) Combinatorial aspects of packing and covering (05B40)

Abstract: Let $S_n^{l}ambda$ be the set of all permutations over the multiset $overbrace{1,\mathrm{...},1}^{lambda},\mathrm{...},overbrace{m,\mathrm{...},m}^{l}ambda$ where $n=mlambda$. A frequency permutation array (FPA) of minimum distance $d$ is a subset of $S_n^{l}ambda$ 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({2dlambdachoosedlambda}^{2.376}logn)$ time and $O({2dlambdachoosedlambda}^2)$ space. The second one runs in $O(2dlambdachoosedlambdadlambda+lambdachooselambdafracnlambda)$ time and $O(2dlambdachoosedlambda)$ space. For small constants $lambda$ and $d$, both are efficient in time and use constant storage space.

Recommendations

• Frequency permutation arrays
• Permutation codes with specified packing radius
• Constructions of permutation arrays
• Equidistant frequency permutation arrays and related constant composition codes
• Bounds on permutation codes of distance four

Cites work

• Correcting Limited-Magnitude Errors in the Rank-Modulation Scheme
• Decoding Frequency Permutation Arrays Under Chebyshev Distance
• Distance-preserving mappings from binary vectors to permutations
• Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices
• Frequency permutation arrays
• Lower bounds on the size of spheres of permutations under the Chebychev distance
• Permutation Arrays Under the Chebyshev Distance
• Rank Modulation for Flash Memories

Cited in

(3)

• Permutation Arrays Under the Chebyshev Distance
• On the size distribution of the fixed-length Levenshtein balls with radius one
• Mirroring and nonlinear perturbation of a circuit's system with multiple attractors

This page was built for publication: Computing the ball size of frequency permutations under Chebyshev distance

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