Designs, Codes and Cryptography - Large sets of combinatorial designs has always been a fascinating topic in design theory. These designs form a partition of the whole space into combinatorial... 相似文献
For z1,z2,z3∈Zn, the tristance d3(z1,z2,z3) is a generalization of the L1-distance on Zn to a quantity that reflects the relative dispersion of three points rather than two. A tristance anticodeAd of diameter d is a subset of Zn with the property that d3(z1,z2,z3)?d for all z1,z2,z3∈Ad. An anticode is optimal if it has the largest possible cardinality for its diameter d. We determine the cardinality and completely classify the optimal tristance anticodes in Z2 for all diameters d?1. We then generalize this result to two related distance models: a different distance structure on Z2 where d(z1,z2)=1 if z1,z2 are adjacent either horizontally, vertically, or diagonally, and the distance structure obtained when Z2 is replaced by the hexagonal lattice A2. We also investigate optimal tristance anticodes in Z3 and optimal quadristance anticodes in Z2, and provide bounds on their cardinality. We conclude with a brief discussion of the applications of our results to multi-dimensional interleaving schemes and to connectivity loci in the game of Go. 相似文献
Given an (n, k) linear code
over GF(q), the intersection of
with a codeπ(
), whereπSn, is an (n, k1) code, where max{0, 2k−n}k1k. The intersection problem is to determine which integers in this range are attainable for a given code
. We show that, depending on the structure of the generator matrix of the code, some of the values in this range are attainable. As a consequence we give a complete solution to the intersection problem for most of the interesting linear codes, e.g. cyclic codes, Reed–Muller codes, and most MDS codes. 相似文献
Motivated by applications in universal data compression algorithms we study the problem of bounds on the sizes of constant weight covering codes. We are concerned with the minimal sizes of codes of lengthn and constant weightu such that every word of lengthn and weightv is within Hamming distanced from a codeword. In addition to a brief summary of part of the relevant literature, we also give new results on upper and lower bounds to these sizes. We pay particular attention to the asymptotic covering density of these codes. We include tables of the bounds on the sizes of these codes both for small values ofn and for the asymptotic behavior. A comparison with techniques for attaining bounds for packing codes is also given. Some new combinatorial questions are also arising from the techniques.Part of this work was done while the first and third authors were visiting Bellcore. The third author was supported in part by National Science Foundation under grant NCR-8905052. Part of this work was presented in the Coding and Quantization Workshop at Rutgers University, NJ, October 1992. 相似文献
Lower and upper bounds on the size of a covering of subspaces in the Grassmann graph \(\mathcal{G }_q(n,r)\) by subspaces from the Grassmann graph \(\mathcal{G }_q(n,k)\), \(k \ge r\), are discussed. The problem is of interest from four points of view: coding theory, combinatorial designs, \(q\)-analogs, and projective geometry. In particular we examine coverings based on lifted maximum rank distance codes, combined with spreads and a recursive construction. New constructions are given for \(q=2\) with \(r=2\) or \(r=3\). We discuss the density for some of these coverings. Tables for the best known coverings, for \(q=2\) and \(5 \le n \le 10\), are presented. We present some questions concerning possible constructions of new coverings of smaller size. 相似文献
We tackle the problem of computing the Voronoi diagram of a 3-D polyhedron whose faces are planar. The main difficulty with the computation is that the diagram's edges and vertices are of relatively high algebraic degrees. As a result, previous approaches to the problem have been non-robust, difficult to implement, or not provenly correct.
We introduce three new proximity skeletons related to the Voronoi diagram: (1) the Voronoi graph (VG), which contains the complete symbolic information of the Voronoi diagram without containing any geometry; (2) the approximate Voronoi graph (AVG), which deals with degenerate diagrams by collapsing sub-graphs of the VG into single nodes; and (3) the proximity structure diagram (PSD), which enhances the VG with a geometric approximation of Voronoi elements to any desired accuracy. The new skeletons are important for both theoretical and practical reasons. Many applications that extract the proximity information of the object from its Voronoi diagram can use the Voronoi graphs or the proximity structure diagram instead. In addition, the skeletons can be used as initial structures for a robust and efficient global or local computation of the Voronoi diagram.
We present a space subdivision algorithm to construct the new skeletons, having three main advantages. First, it solves at most uni-variate quartic polynomials. This stands in sharp contrast to previous approaches, which require the solution of a non-linear tri-variate system of equations. Second, the algorithm enables purely local computation of the skeletons in any limited region of interest. Third, the algorithm is simple to implement. 相似文献