| 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)
-
On the optimality of the binary reflected Gray code
- 2004
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 50:12, s. 3170-3182
-
Tidskriftsartikel (refereegranskat)abstract
- This paper concerns the problem of selecting a binary labeling for the signal constellation in M-PSK, M-PAM, and M-QAM communication systems. Gray labelings are discussed and the original work by Frank Gray is analyzed. As is noted, the number of distinct Gray labelings that result in different bit-error probability grows rapidly with increasing constellation size. By introducing a recursive Gray labeling construction method called expansion, the paper answers the natural question of what labeling, among all possible constellation labelings, will give the lowest possible average probability of bit errors for the considered constellations. Under certain assumptions on the channel, the answer is that the labeling proposed by Gray, the binary reflected Gray code, is the optimal labeling for all three constellations, which has, surprisingly, never been proved before.
|
|
| 4. |
- 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.
|
|
| 5. |
- Anderson, John B
(författare)
-
On the complexity of bounded distance decoding for the AWGN channel
- 2002
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448. ; 48:5, s. 1046-1060
-
Tidskriftsartikel (refereegranskat)abstract
- Earlier work has derived the storage complexity of the bounded distance decoder (BDD) for binary-channel convolutional codes. We extend this work to the Gaussian noise channel and to partial-response codes. We show that the storage requirement similar to(2(1-R) - 1)(-t) paths for rate-R convolutional codes over the binary channel becomes similar to2(2Rt) over the Gaussian channel, where the decoder must correct t errors. Thus, convolutional coding over the Gaussian channel is not only 3 dB more energy efficient, but its decoding is simpler as well. Next, we estimate the path storage for partial-response codes, i.e., real-number convolutional codes, over the Gaussian channel. The growth rate depends primarily on the bandwidth of the code. A new optimization procedure is devised to measure the maximum storage requirement in Gaussian noise for these two code types. An analysis based on difference equations predicts the asymptotic storage growth for partial response codes.
|
|
| 6. |
- Asraf, Daniel, et al.
(författare)
-
An analytical series expansion solution to the problem of noncoherent detection
- 2004
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 50:12, s. 3369-3375
-
Tidskriftsartikel (refereegranskat)abstract
- The well-known noncoherent detection problem concerns optimal detection of an amplitude-modulated sinusoid, with an unknown phase angle, corrupted by additive Gaussian noise. The classical solution to this problem is the noncoherent detector which is known to be optimal if the envelope belongs to a specific set of functions or satisfies the narrow-band approximation i.e., that the bandwidth of the envelope is narrow in comparison with the (carrier) frequency of the sinusoid. In this work, an analytical series expansion solution to the likelihood ratio for the noncoherent detection problem is derived. This solution offers a generalization of the noncoherent detector in which the conditions imposed on the envelope stated above have been relaxed. Analytical expressions for the joint probability density functions (pdfs) of the in-phase and quadrature components, jointly expressed in polar coordinates, are also derived under the signal-plus-noise and the noise-only hypotheses, respectively. Numerical simulations of the detector performance are presented in the form of receiver operating characteristics (ROC) and minimum probability of error curves. The results from a comparison of the general analytical solution with the classical noncoherent detector show significant differences between the two detectors when the narrow-band approximation does not hold.
|
|
| 7. |
- Bocharova, Irina, et al.
(författare)
-
A BEAST for prowling in trees
- 2004
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 50:6, s. 1295-1302
-
Tidskriftsartikel (refereegranskat)abstract
- When searching for convolutional codes and tailbiting codes of high complexity it is of vital importance to use fast algorithms for computing their weight spectra, which corresponds to finding low-weight paths in their code trellises. This can be efficiently done by a combined search in both forward and backward code trees. A bidirectional efficient algorithm for searching such code trees (BEAST) is presented. For large encoder memories, it is shown that BEAST is significantly more efficient than comparable algorithms. BEAST made it possible to rind new convolutional and tailbiting codes that have larger free (minimum) distances than the previously best known codes with the same parameters. Tables of such codes are presented.
|
|
| 8. |
- Bocharova, Irina, et al.
(författare)
-
Low state complexity block codes via convolutional codes
- 2004
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 50:9, s. 2022-2030
-
Tidskriftsartikel (refereegranskat)abstract
- A new class of block codes with low state complexity of their conventional trellis representations called double zero-tail terminated convolutional codes (DZT codes) is introduced. It is shown that there exist DZT-codes meeting the Varshamov-Gilbert bound on the minimum distance and having asymptotically optimal state complexity. Two ways of constructing DZT-codes are considered. Examples of DZT-codes meeting a lower bound on the state complexity are given.
|
|
| 9. |
- Bocharova, Irina, et al.
(författare)
-
Tailbiting codes: Bounds and search results
- 2002
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448. ; 48:1, s. 137-148
-
Tidskriftsartikel (refereegranskat)abstract
- Tailbiting trellis representations of linear block codes with an arbitrary sectionalization of the time axis are studied. The notations of regular and irregular tailbiting codes are introduced and their maximal state complexities are lower-bounded. The asymptotic behavior of the derived bound is investigated. Furthermore, for regular tailbiting codes the product state complexity is lower-bounded. Tables of new tailbiting trellis representations of linear block codes of rates 1/2, 1/3, and 1/4 are presented. Almost all found trellises are optimal in the sense of the new bound on the state complexity and for most codes with nonoptimal trellises there exist time-varying trellises which are optimal. Five of our newly found tailbiting codes are better than the previously known linear codes with the same parameters. Four of them are also superior to any previously known nonlinear code with the same parameters. Also, more than 40 other quasi-cyclic codes have been found that improve the parameter set of previously known quasi-cyclic codes.
|
|
| 10. |
- Bocharova, Irina, et al.
(författare)
-
Tailbiting codes obtained via convolutional codes with large active distance-slopes
- 2002
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 48:9, s. 2577-2587
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- The slope of the active distances is an important parameter when investigating the error-correcting capability of convolutional codes and the distance behavior of concatenated convolutional codes. The slope of the active distances is equal to the minimum average weight cycle in the state-transition diagram of the encoder. A general upper bound on the slope depending on the free distance of the convolutional code and new upper bounds on the slope of special classes of binary convolutional codes are derived. Moreover, a search technique, resulting in new tables of rate R = 1/2 and rate R = 1/3 convolutional encoders with high memories and large active distance-slopes is presented. Furthermore, we show that convolutional codes with large slopes can be used to obtain new tailbiting block codes with large minimum distances. Tables of rate R = 1/2 and rate R = 1/3 tailbiting codes with larger minimum distances than the best previously known quasi-cyclic codes are given. Two new tailbiting codes also have larger minimum distances than the best previously known binary linear block codes with same size and length. One of them is also superior in terms of minimum distance to any previously known binary nonlinear block code with the same set of parameters.
|
|
