检索结果-内蒙古大学图书馆

permutation arrays Under the Chebyshev Distance

IEEE TRANSACTIONS ON INFORMATION THEORY 2010年第6期56卷 2611-2617页

作者： Klove, Torleiv Lin, Te-Tsung Tsai, Shi-Chun Tzeng, Wen-Guey Univ Bergen Dept Informat N-5020 Bergen Norway Natl Chiao Tung Univ Dept Comp Sci Hsinchu 30050 Taiwan

An (n, d) permutation array (PA) is a subset of S-n with the property that the distance (under some metric) between any two permutations in the array is at least d. They became popular recently for communication over power lines. Motivated by an application to flash memories, in this paper, the metric used is the Chebyshev metric. A number of different constructions are given, as well as bounds on the size of such PA.

关键词： Bounds Chebyshev distance code constructions flash memory permutation arrays

来源：评论

学校读者我要写书评

暂无评论

Constructions for retransmission permutation arrays

引用

DESIGNS CODES AND CRYPTOGRAPHY 2012年第3期65卷 325-351页

作者： Dinitz, Jeffrey H. Paterson, Maura B. Stinson, Douglas R. Wei, Ruizhong Univ Vermont Dept Math & Stat Burlington VT 05405 USA Birkbeck Univ London Dept Econ Math & Stat London WC1E 7HX England Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada Lakehead Univ Dept Comp Sci Thunder Bay ON P7B 5E1 Canada

Li et al. (Retransmission not equal repeat: simple retransmission permutation can resolve overlapping channel collisions, 2009) introduced a technique for resolving overlapping channel transmissions that used an interesting new type of combinatorial structure. In connection with this problem, they provided an example of a 4 x 4 array having certain desirable properties. We define a class of combinatorial structures, which we term retransmission permutation arrays, that generalise the example that Li et al. provided. We show that these arrays exist for all possible orders. We also define some extensions having additional properties, for which we provide some partial results.

关键词： permutation arrays Latin squares Sudoku Latin Squares

来源：评论

学校读者我要写书评

暂无评论

Constructing permutation arrays using partition and extension

引用

DESIGNS CODES AND CRYPTOGRAPHY 2020年第2期88卷 311-339页

作者： Bereg, Sergey Mojica, Luis Gerardo Morales, Linda Sudborough, Hal Univ Texas Dallas Dept Comp Sci Box 830688 Richardson TX 75083 USA

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 pairwiseHamming distance d are needed for constructing error correcting permutation codes, which have been proposed for power-line communications. Our technique, partition and extension, is universally applicable to constructing such sets for all n and all d, d < n. We describe three new techniques, sequential partition and extension, parallel partition and extension, anda modifiedKronecker 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 M(n, d) found using these techniques for n up to 600.

关键词： permutation arrays Partition and extension Kronecker product Coset method

来源：评论

学校读者我要写书评

暂无评论

New lower bounds for permutation arrays using contraction

引用

DESIGNS CODES AND CRYPTOGRAPHY 2019年第9期87卷 2105-2128页

作者： Bereg, Sergey Miller, Zevi Mojica, Luis Gerardo Morales, Linda Sudborough, I. H. Univ Texas Dallas Comp Sci Dept Richardson TX 75083 USA Miami Univ Dept Math Oxford OH 45056 USA

A permutation array A is a set of permutations on a finite set Omega, say of size n. Given distinct permutations pi, sigma is an element of Omega, we let hd(pi, sigma) = vertical bar{x is an element of Omega : pi(x) not equal sigma(x)}vertical bar, called the Hamming distance between pi and sigma. Nowlet hd(A) = min{hd(pi, sigma) : pi, sigma is an element of A}. For positive integers n and d with d <= n we let M(n, d) be the maximum number of permutations in any array A satisfying hd(A) >= d. There is an extensive literature on the function M(n, d), motivated in part by suggested applications to error correcting codes for message transmission over power lines. A basic fact is that if a permutation group G is sharply k-transitive on a set of size n >= k, then M(n, n - k + 1) = vertical bar G vertical bar. Motivated by this we consider the permutation groups AGL(1, q) and PGL(2, q) acting sharply 2-transitively on GF(q) and sharply 3-transitively on GF(q) boolean OR {infinity} respectively. Applying a contraction operation to these groups, we obtain the following new lower bounds for prime powers q satisfying q equivalent to 1 (mod 3). 1. M(q - 1, q - 3) >= (q(2) - 1)/ 2 for q odd, q >= 7, 2. M(q - 1, q - 3) >= (q - 1)(q + 2)/3 for q even, q >= 8, 3. M(q, q - 3) >= Kq(2)log(q) for some constant K > 0 if q is odd. These results resolve a case left open in a previous paper (Bereg et al. in Des Codes Cryptogr 86(5):1095-1111, 2018), where itwas shownthat M(q-1, q-3) >= q(2)-q and M(q, q-3) >= q(3) - q for all prime powers q such that q not equivalent to 1 (mod 3). We also obtain lower bounds for M(n, d) for a finite number of exceptional pairs n, d, by applying this contraction operation to the sharply 4 and 5-transitive Mathieu groups.

关键词： permutation arrays Contraction AGL(1, q) PGL(2, q)

来源：评论

学校读者我要写书评

暂无评论

Extending permutation arrays: improving MOLS bounds

引用

DESIGNS CODES AND CRYPTOGRAPHY 2017年第3期83卷 661-683页

作者： Bereg, Sergey Morales, Linda Sudborough, I. Hal Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

A permutation array (PA) A is a set of permutations on Z(n) = (0, 1, ... , n - 1}, for some n. A PA A has pairwise Hamming distance at least d, if for every pair of permutations sigma and tau in A, there are at least d integers i in Z(n) such that sigma(i) not equal tau(i). Let M(n, d) denote the maximum number of permutations in any PA with pairwise Hamming distance at least d. Recently considerable effort has been devoted to improving known lower bounds for M(n, d) for all n > d > 3. We give a partition and extension operation that enables the production of a new PA A' for M (n + 1, d) from an existing PA A for M (n, d - 1). In particular, this operation allows for improvements for PA's for M(q + 1, q) for powers of prime numbers q, as well as for many other choices of n and d, where n is not a power of a prime. Finally, for prime numbers p, the partition and extension technique provides an asymptotically better lower bound for M(p + 1, p) than that given by current knowledge about mutually orthogonal Latin squares. We prove a new asymptotic lower bound for the set of primes p, namely, M(p + 1, p) >= p(1.5) / 2 - O(p).

关键词： permutation arrays Hamming distance Error correcting codes

来源：评论

学校读者我要写书评

暂无评论

Improved bounds for permutation arrays under Chebyshev distance

引用

DESIGNS CODES AND CRYPTOGRAPHY 2024年第4期92卷 1023-1039页

作者： Bereg, Sergey Haghpanah, Mohammadreza Malouf, Brian Sudborough, I. Hal Univ Texas Dallas Dept Comp Sci Box 830688 Richardson TX 75083 USA

permutation arrays under the Chebyshev metric have been considered for error correction in noisy channels. Let P(n, d) denote the maximum size of any array of permutations on n symbols with pairwise Chebyshev distance... 详细信息

关键词： Chebyshev metric permutation arrays Code constructions

来源：评论

学校读者我要写书评

暂无评论

Equidistant frequency permutation arrays and related constant composition codes

引用

DESIGNS CODES AND CRYPTOGRAPHY 2010年第2期54卷 109-120页

作者： Huczynska, Sophie Univ St Andrews Sch Math & Stat St Andrews KY16 9SS Fife Scotland

In this paper we study the special class of equidistant constant composition codes of type CCC( n, d, mu(m)) ( where n = m mu), which correspond to equidistant frequency permutation arrays;we also consider related codes with composition "close to" mu(m). We establish various properties of these objects and give constructions for optimal families of codes.

关键词： permutation arrays Constant composition codes Combinatorial designs

来源：评论

学校读者我要写书评

暂无评论

Using permutation rational functions to obtain permutation arrays with large hamming distance

引用

DESIGNS CODES AND CRYPTOGRAPHY 2022年第7期90卷 1659-1677页

作者： Bereg, Sergey Malouf, Brian Morales, Linda Stanley, Thomas Sudborough, I. Hal Univ Texas Dallas Dept Comp Sci Box 830688 Richardson TX 75083 USA

We consider permutation rational functions (PRFs), V(x)/U(x), where both V(x) and U(x) are polynomials over a finite field F-q. permutation rational functions have been the subject of several recent papers. Let M (n, D) denote the maximum number of permutations on n symbols with pairwise Hamming distance D. Computing lower bounds for M(n, D) is the subject of current research with applications in error correcting codes. Using PRFs of specified degrees d we obtain improved lower bounds for M (q, q - k) for prime powers q and k is an element of {5, 6, 7, 8, 9}, and for M (q + 1, q - k) for prime powers q and k is an element of {4, 5, 6, 7, 8, 9}.

关键词： permutation codes permutation arrays Hamming distance permutation rational functions permutation polynomials

来源：评论

学校读者我要写书评

暂无评论

Constructing permutation arrays from groups

引用

DESIGNS CODES AND CRYPTOGRAPHY 2018年第5期86卷 1095-1111页

作者： Bereg, Sergey Levy, Avi Sudborough, I. Hal Univ Texas Dallas Erik Jonsson Sch Engn & Comp Sci Dept Comp Sci Richardson TX 75083 USA Univ Washington Dept Math Seattle WA 98195 USA

Let M(n, d) be the maximum size of a permutation array on n symbols with pairwise Hamming distance at least d. We use various combinatorial, algebraic, and computational methods to improve lower bounds for M(n, d). We compute the Hamming distances of affine semilinear groups and projective semilinear groups, and unions of cosets of AGL(1, q) and PGL(2, q) with Frobenius maps to obtain new, improved lower bounds for M(n, d). We give new randomized algorithms. We give better lower bounds for M(n, d) also using new theorems concerning the contraction operation. For example, we prove a quadratic lower bound for for all such that is a prime power.

关键词： permutation codes permutation arrays Finite fields Groups

来源：评论

学校读者我要写书评

暂无评论

Isometries and Construction of permutation arrays

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2010年第7期56卷 3177-3179页

作者： Bogaerts, Mathieu Univ Libre Bruxelles Serv Math Fac Sci Appl B-1050 Brussels Belgium

An (n,d)-permutation code is a subset C of Sym(n) such that the Hamming distance d(H) between any two distinct elements of C is at least equal to d. In this paper, we use the characterization of the isometry group of the metric space (Sym(n), d(H)) in order to develop generating algorithms with rejection of isomorphic objects. To classify the (n,d)-permutation codes up to isometry, we construct invariants and study their efficiency. We give the numbers of nonisometric (4,3)- and (5,4)- permutation codes. Maximal and balanced (n,d)-permutation codes are enumerated in a constructive way.

关键词： Constant composition codes Hamming distance isometry permutation arrays permutation codes

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：