We survey a number of topics and constructions of combinatorial arrays based on finite fields. These combinatorial objects include orthogonal arrays, covering arrays, ordered orthogonal arrays, permutationarrays, fre...
详细信息
We survey a number of topics and constructions of combinatorial arrays based on finite fields. These combinatorial objects include orthogonal arrays, covering arrays, ordered orthogonal arrays, permutationarrays, frequency permutation arrays, hypercubes and Costas arrays.
We address the problem of multipermutation code design in the Ulam metric for novel storage applications. Multipermutation codes are suitable for flash memory where cell charges may share the same rank. Changes in the...
详细信息
We address the problem of multipermutation code design in the Ulam metric for novel storage applications. Multipermutation codes are suitable for flash memory where cell charges may share the same rank. Changes in the charges of cells manifest themselves as errors whose effects on the retrieved signal may be measured via the Ulam distance. As part of our analysis, we study multipermutation codes in the Hamming metric, known as constant composition codes. We then present bounds on the size of multipermutation codes and their capacity, for both the Ulam and the Hamming metrics. Finally, we present constructions and accompanying decoders for multipermutation codes in the Ulam metric.
Let S-n(lambda) be the set of all permutations over the multiset [GRAPHICS] 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 dis...
详细信息
ISBN:
(纸本)9781457705953
Let S-n(lambda) be the set of all permutations over the multiset [GRAPHICS] 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. FPAs have many applications related to error correcting codes. In coding theory, the Gilbert- Varshamov bound and the spherepacking bound are derived from the size of balls of certain radii. We propose two efficient algorithms that compute the ball size of frequencypermutations under Chebyshev distance. Both methods extend previous known results. The first one runs in O((()(2d lambda)2.376)(d lambda) log n) time and O((()(2d lambda)2)(d lambda)) space. The second one runs in O ((()(2d lambda)()(d lambda) (d lambda+lambda))(lambda)n/lambda) time and O((2d lambda)(d lambda)) space. For small constants lambda and d, both are efficient in time and use constant storage space.
暂无评论