1. |
- Agrell, Erik, 1965, et al.
(författare)
-
A table of upper bounds for binary codes
- 2001
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448 .- 1557-9654. ; 47:7, s. 3004-3006
-
Tidskriftsartikel (refereegranskat)abstract
- Let A(n, d) denote the maximum possible number of codewords in an (n, d) binary code. We establish four new bounds on A(n, d), namely, A(21, 4)⩽43689, A(22, 4)⩽87378, A(22, 6)⩽6941, and A(23, 4)⩽173491. Furthermore, using previous upper bounds on the size of constant-weight binary codes, we reapply known methods to generate a table of bounds on A(n, d) for all n⩽28. This table extends the range of parameters compared with previously known tables.
|
|
2. |
- Agrell, Erik, 1965, et al.
(författare)
-
Closest point search in lattices
- 2002
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 48:8, s. 2201-2214
-
Tidskriftsartikel (refereegranskat)abstract
- In this semitutorial paper, a comprehensive survey of closest point search methods for lattices without a regular structure is presented. The existing search strategies are described in a unified framework, and differences between them are elucidated. An efficient closest point search algorithm, based on the Schnorr-Euchner variation of the Pohst method, is implemented. Given an arbitrary point x is an element of R-m and a generator matrix for a lattice A, the algorithm computes the point of A that is closest to x. The algorithm is shown to be substantially faster than other known methods, by means of a theoretical comparison with the Kannan algorithm and an experimental comparison with the Pohst algorithm and its variants, such as the recent Viterbo-Boutros decoder. Modifications of the algorithm are developed to solve a number of related search problems for lattices, such as finding a shortest vector, determining the kissing number, computing the Voronoi-relevant vectors, and finding. a Korkine-Zolotareff reduced basis.
|
|
3. |
- Agrell, Erik, 1965, et al.
(författare)
-
Upper bounds for constant-weight codes
- 2000
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448 .- 1557-9654. ; 46:7, s. 2373-2395
-
Tidskriftsartikel (refereegranskat)abstract
- Let A(n,d,w) denote the maximum possible number of codewords in an (n,d,w) constant-weight binary code. We improve upon the best known upper bounds on A(n,d,w) in numerous instances for n⩽24 and d⩽12, which is the parameter range of existing tables. Most improvements occur for d=8, 10, where we reduce the upper bounds in more than half of the unresolved cases. We also extend the existing tables up to n⩽28 and d⩽14. To obtain these results, we develop new techniques and introduce new classes of codes. We derive a number of general bounds on A(n,d,w) by means of mapping constant-weight codes into Euclidean space. This approach produces, among other results, a bound on A(n,d,w) that is tighter than the Johnson bound. A similar improvement over the best known bounds for doubly-constant-weight codes, studied by Johnson and Levenshtein, is obtained in the same way. Furthermore, we introduce the concept of doubly-bounded-weight codes, which may be thought of as a generalization of the doubly-constant-weight codes. Subsequently, a class of Euclidean-space codes, called zonal codes, is introduced, and a bound on the size of such codes is established. This is used to derive bounds for doubly-bounded-weight codes, which are in turn used to derive bounds on A(n,d,w). We also develop a universal method to establish constraints that augment the Delsarte inequalities for constant-weight codes, used in the linear programming bound. In addition, we present a detailed survey of known upper bounds for constant-weight codes, and sharpen these bounds in several cases. All these bounds, along with all known dependencies among them, are then combined in a coherent framework that is amenable to analysis by computer. This improves the bounds on A(n,d,w) even further for a large number of instances of n, d, and w.
|
|