Packing Arrays and Packing Designs

Authors: Stevens B.¹; Mendelsohn E.^{2, 3}

Source: Designs, Codes and Cryptography, Volume 27, Numbers 1-2, October 2002 , pp. 165-176(12)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

A packing array is a b × k array, A with entries a_i,j from a g-ary alphabet such that given any two columns, i and j, and for all ordered pairs of elements from a g-ary alphabet, (g₁, g₂), there is at most one row, r, such that a_r,i = g₁ and a_r,j = g₂. Further, there is a set of at least n rows that pairwise differ in each column: they are disjoint. A central question is to determine, for given g, k and n, the maximum possible b. We examine the implications when n is close to g. We give a brief analysis of the case n = g and show that 2g rows is always achievable whenever more than g exist. We give an upper bound derived from design packing numbers when n = g - 1. When g + 1 k then this bound is always at least as good as the modified Plotkin bound of [12]. When the associated packing has as many points as blocks and has reasonably uniform replication numbers, we show that this bound is tight. In particular, finite geometries imply the existence of a family of optimal or near optimal packing arrays. When no projective plane exists we present similarly strong results. This article completely determines the packing numbers, D(v, k, 1), when v < \frac{k(k-1)}{2}.

Keywords: packing array; orthogonal array; packing design; Plotkin bound

Language: English

Document Type: Research article

Affiliations: 1: School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, ON K1S 5B6 brett@math.carleton.ca 2: Department of Mathematics, University of Toronto, 100 St. George St., Toronto, ON M6G 3G3 m 3:

Publication date: 2002-10-01