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

algorithmcoding theoryerror correcting codesfrequency permutation arrayGilbert-Varshamov boundpermanentpermutationsphere-packing bound

Mathematics Subject Classification ID

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

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.

Review text

Let \(S_n^\lambda\) be the set of all permutations over the multiset \(\{1,\dots ,1,\dots ,m,\dots , m\}\) (\(\lambda\;1\)'s and \(m\)'s) where \(n=m\lambda\). A frequency permutation array (FPA) of minimum distance \(d\) is a subset of \(S_n^\lambda\) in which every two elements have distance at least \(d\). FPA's 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. The authors propose two efficient algorithms that compute the ball size of frequency permutations under Chebyshev distance. Both methods extend previous know results by \textit{M. Schwartz} [Linear Algebra Appl. 430, No. 4, 1364--1374 (2009; Zbl 1163.65022)].

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

(4)

• 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
• Metrics on permutations with the same descent set

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)