包裝和包裝設計外文文獻

1、Designs, Codes and Cryptography, 27, 165–176, 2002 ? C 2002 Kluwer Academic Publishers. Manufactured in The Netherlands.Packing Arrays and Packing DesignsBRETT STEVENS brett@math.carleton.ca School of Mathematics and Sta

2、tistics, Carleton University, 1125 Colonel By Drive, Ottawa, ON K1S 5B6ERIC MENDELSOHN mendelso@math.toronto.edu Department of Mathematics, University of Toronto, 100 St. George St., Toronto, ON M6G 3G3Communicated by: C

3、. J. Colbourn, D. R. Stinson, G. H. J. van ReesReceived May 16, 2001; Accepted July 16, 2001Abstract. A packing array is a b × k array, A with entries ai, j from a g-ary alphabet such that given any two columns, i a

4、nd j, and for all ordered pairs of elements from a g-ary alphabet, (g1, g2), there is at most one row, r, such that ar,i = g1 and ar, j = g2. Further, there is a set of at least n rows that pairwise differ in each column

5、: 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

6、 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]. W

7、hen 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 nea

8、r 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 g + 1. For g a non-prime power, orthogonal arrays

9、 are only known to have k two larger than MOLS(g). For their applications, it is natural to ask for structures that have similarly useful properties as orthogonal arrays but have k larger than these bounds. One generaliz

10、ation is to require that all pairwise interactions be covered at least once. These objects are known as covering arrays or transversal covers and have been extensively studied, see [9,11,13–15] and their references. The

11、other natural generalization of orthogonal array is the packing array.Definition 1. A packing array (PA(k, g : n)) is a b × k array, A with entries ai, j from a g-ary alphabet such that given any two columns, i and

12、j, and for all ordered pairs of elements from the g-ary alphabet, (g1, g2), there is at most one row, r, such that ar,i = g1 and ar, j = g2. Further, there is a set of at least n rows that pairwise differ in each column:

13、 they are disjoint. The largest number of rows possible in a PA(k, g : n) is denoted by pa(k, g : n).PACKING ARRAYS AND PACKING DESIGNS 167motivates the generalization of the Plotkin bound to these objects:THEOREM 1 [12]

14、. A b × k packing array, PA(k, g : n), must satisfy the following bound for all β ≤ b = pa(k, g : n), β = ug + v where 0 ≤ v < g:k((g ? v)u2 + v(u + 1)2) ≤ β2 ? β ? n2 + n + kβ. (1)Abdel-Ghaffar and Abbadi [2] us

15、e MDS codes to allocate large database files to multiple hard disk systems so that the retrieval time is optimal. They establish bounds on the size of packing arrays, the smallest form of MDS codes, to yield bounds on th

16、e efficiency of their system. The MDS or Partial MDS codes that correspond to packing arrays would apply to optimal disk allocation over a large number of disks, specifically at least gk?2, where, in their terminology, g

17、 is the number of sets into which each attribute of the database is divided. If packing arrays were used for optimal disk allocation in their model, any search with at least two specified attributes would yield search ti

18、me of one. This is the best possible search time. Abdel-Ghaffar and Abbadi [2] showed thatpa(k, g : 1) ≥ g + 1 ? k ≤ g2 + g2 , (2)Abdel-Ghaffar showed that the bound from Theorem 1 is tight when k ≥ 2g ? 1 and n = 1 [1].

19、 This result was extended by the two authors to all n and a range of parameters with k < 2g ? 1 [12]. In Section 2, we examine the upper bounds on the size of packing arrays when the size of the set of disjoint rows i

20、s either g or g ? 1. In the later case we derive a bound in terms of the packing design numbers. We determine the range where this bound is stronger than that given in Theorem 1. In Section 3, we discuss conditions which

21、 allow us to construct packing arrays that are tight for this bound. This involves suitably edge colouring the point set incidence graph of the complementary incidence structure of the packing design in question. In Sect

22、ion 4 we examine more closely the connection between packing arrays and the existence of special designs: finite geometries. We show that when a projective plane does not exist, the corresponding packing array cannot eve

23、n have 2g rows, a powerful non-existence result.2. Upper Bounds for Large Sets of Disjoint RowsIn a previous paper the authors presented a number of upper bounds and constructions yielding lower bounds [12]. One of the u

24、pper bounds developed is stated in Theorem 1. This bound is an adaptation of the Plotkin bound from coding theory. The other upper bound arisesfromconsiderationoftherestrictionsnecessaryifthearrayistohavemorethan g rows,