Asymptotically dense spherical codes .II. laminated spherical codes

For pt. I see ibid., vol.43, no.6, p.1774-85, 1997. New spherical codes called laminated spherical codes are constructed in dimensions 2-49 using a technique similar to the construction of laminated lattices. Each spherical code is recursively constructed from existing spherical codes in one lower dimension. Laminated spherical codes outperform the best known spherical codes in the minimum distance sense for many code sizes. The density of a laminated spherical code approaches the density of the laminated lattice in one lower dimension, as the minimum distance approaches zero. In particular, the three-dimensional laminated spherical code is asymptotically optimal, in the sense that its density approaches the Fejes Toth (1959) upper bound as the minimum distance approaches zero. Laminated spherical codes perform asymptotically as well as wrapped spherical codes in those dimensions where laminated lattices are optimal sphere packings     

Gaussian source coding with spherical codes

A fixed-rate shape-gain quantizer for the memoryless Gaussian source is proposed. The shape quantizer is constructed from wrapped spherical codes that map a sphere packing in ℝ^k-1 onto a sphere in ℝ^k, and the gain codebook is a globally optimal scalar quantizer. A wrapped Leech lattice shape quantizer is used to demonstrate a signal-to-quantization-noise ratio within 1 dB of the distortion-rate function for rates above 1 bit per sample, and an improvement over existing techniques of similar complexity. An asymptotic analysis of the tradeoff between gain quantization and shape quantization is also given     

Efficient maximum-likelihood decoding of spherical lattice codes

A new framework for efficient exact Maximum- Likelihood (ML) decoding of spherical lattice codes is developed. It employs a double-tree structure: The first is that which underlies established tree-search decoders; the second plays the crucial role of guiding the primary search by specifying admissible candidates and is our present focus. Lattice codes have long been of interest due to their rich structure, leading to decoding algorithms for unbounded lattices, as well as those with axis-aligned rectangular shaping regions. Recently, spherical Lattice Space-Time (LAST) codes were proposed to realize the optimal diversity-multiplexing tradeoff of MIMO channels. We address the so-called boundary control problem arising from the spherical shaping region defining these codes. This problem is complicated because of the varying number of candidates to consider at each search stage; it is not obvious how to address it effectively within the frameworks of existing decoders. Our proposed strategy is compatible with all sequential tree-search detectors, as well as auxiliary processing such as the MMSEGDFE and lattice reduction. We demonstrate the superior performance and complexity profiles achieved when applying the proposed boundary control in conjunction with two current efficient ML detectors and show an improvement of 1dB over the state-of-the-art at a comparable complexity.     

Sphere-packing upper bounds on the free distance of trellis codes

Sphere-packing arguments are used to develop upper bounds on the free distance of trellis codes. A general bounding procedure is presented. Sphere packing bounds, including bounds on the density of infinite regions, packings for hypercubes, and packings on the surface of a unit sphere, are then used to produce bounds for a wide variety of trellis codes. Among the applications are convolutional codes, Ungerboeck codes for phase-shift keying and quadrature amplitude modulation, coset codes, and continuous phase modulation codes. The new bounds are significantly tighter than existing bounds in many cases of practical interest     

Performance of lattice codes over the Gaussian channel

We derive an upper bound on the error probability of lattice codes combined with Quadrature Amplitude Modulation (qam) over the additive white Gaussian noise channel. This bound depends on a lattice figure of merit and is readily put in exponential form by using Chernoff bound. An interesting lower bound is derived by a similar reasoning. We also examine the estimation of the average information rate based upon the continuous approximation of the average power normalized to two dimensions, and suggest to improve it by using the sphere packing idea. Examples of performance evaluation are given for a few lattices. Finally, we present upper and lower bounds on the best fundamental coding gains per dimension (due to both density and thickness) for an arbitrarily large number of dimensions. It is shown in the Appendix that, as the Ungerboeck codes, the lattice codes do not shape the signal power spectrum.     

Spherical space-time codes (SSTC)

We present the extension of the trellis space-time code (STC) concept to include signal mapping drawn from an N-dimensional sphere. The signal points were designed as such to increase the minimum squared distance between points in the constellation without increasing the average transmit energy. The mapping of the N-dimensional spherical constellations was performed in accordance to set partitioning rules for STC developed by AT&T but optimized for these codes. Performance evaluation for these spherical space-time codes (SSTC) are illustrated in an OFDM framework, which is a natural choice for multidimensional signaling     

Iteratively maximum likelihood decodable spherical codes and amethod for their construction

The authors propose a class of spherical codes which can be easily decoded by an efficient iterative maximum likelihood decoding algorithm. A necessary and sufficient condition for a spherical code to be iteratively maximum likelihood decodable is formulated. A systematic construction method for such codes based on shrinking of Voronoi corners is analyzed. The base code used for construction is the binary maximal length sequence code. The second-level construction is described. Computer simulation results for selected codes constructed by the proposed method are given     

LDPC codes and convolutional codes with equal structural delay: a comparison

We compare convolutional codes and LDPC codes with respect to their decoding performance and their structural delay, which is the inevitable delay solely depending on the structural properties of the coding scheme. Besides the decoding performance, the data delay caused by the channel code is of great importance as this is a crucial factor for many applications. Convolutional codes are known to show a good performance while imposing only a very low latency on the data. LDPC codes yield superior decoding performance but impose a larger delay due to the block structure. The results obtained by comparison will also be related to theoretical limits obtained from random coding and the sphere packing bound. It will be shown that convolutional codes are still the first choice for applications for which a very low data delay is required and the bit error rate is the considered performance criterion. However, if one focuses on a low signal-to-noise ratio or if the obtained frame error rate is the base for comparison, LDPC codes compare favorably.     

Lattice code decoder for space-time codes

We explore the lattice sphere packing representation of a multi-antenna system and the algebraic space-time (ST) codes. We apply the sphere decoding (SD) algorithm to the resulted lattice code. For the uncoded system, SD yields, with small increase in complexity, a huge improvement over the well-known V-BLAST detection algorithm. SD of algebraic ST codes exploits the full diversity of the coded multi-antenna system, and makes the proposed scheme very appealing to take advantage of the richness of the multi-antenna environment. The fact that the SD does not depend on the constellation size, gives rise to systems with very high spectral efficiency, maximum-likelihood performance, and low decoding complexity     

Location-correcting codes

We study codes over GF(q) that can correct t channel errors assuming the error values are known. This is a counterpart to the well-known problem of erasure correction, where error values are found assuming the locations are known. The correction capabilities of these so-called t-location correcting codes (t-LCCs) are characterized by a new metric, the decomposability distance, which plays a role analogous to that of the Hamming metric in conventional error-correcting codes (ECCs). Based on the new metric, we present bounds on the parameters of t-LCCs that are counterparts to the classical Singleton, sphere packing and Gilbert-Varshamov bounds for ECCs. In particular, we show examples of perfect LCCs, and we study optimal (MDS-Like) LCCs that attain the Singleton-type bound on the redundancy. We show that these optimal codes are generally much shorter than their erasure (or conventional ECC) analogs. The length n of any t-LCC that attains the Singleton-type bound for t>1 is bounded from above by t+O(√(q)), compared to length q+1 which is attainable in the conventional ECC case. We show constructions of optimal t-LCCs for t∈{1, 2, n-2, n-1, n} that attain the asymptotic length upper bounds, and constructions for other values of t that are optimal, yet their lengths fall short of the upper bounds. The resulting asymptotic gap remains an open research problem. All the constructions presented can be efficiently decoded     

Tables of sphere packings and spherical codes

The theta function of a sphere packing gives the number of centers at each distance from the origin. The theta functions of a number of important packings (A_{n},D_{n},E_{n}, the Leech lattice, and others) and tables of the first fifty or so of their coefficients are given in this paper.     

Multidimensional constellations. II. Voronoi constellations

For pt.I see ibid., vol.7, no.6, p.877-92 (1989). Voronoi constellations, also called Voronoi codes are implementable N-dimensional constellations based on partitions of N-dimensional lattices (Λ) that can achieve good shape gains and that are inherently suited for use with coded modulation. Two methods are given for specifying Voronoi constellations on the basis of arbitrary lattice partitions Λ/Λ_s, where Λ_s, the shaping lattice, is an N-dimensional sublattice of Λ. One of the methods is conjectured to be optimum, and the other has desirable symmetries and naturally supports opportunistic secondary channels. When Λ and Λ_s are 2-D-symmetric, the constituent 2-D constellation is itself a Voronoi constellation. The shaping constellation expansion ratio and peak-to-average-power ratio are determined in general and for various Λ_s. Methods for labeling Voronoi constellations are given. Their complexity is shown to be dominated by that of decoding Λ_s. It is also shown that coding and shaping are separable and dual. Bounds on the shape gain of Voronoi constellations are given that depend on the depth and normalized informativity of Λ_s. These bounds suggest the use of lattices Λ with depth 2 and normalized informativity less than 1, which can achieve near-optimal shape gains with reduced constellation expansion and implementation complexity     

Sphere-bound-achieving coset codes and multilevel coset codes

A simple sphere bound gives the best possible tradeoff between the volume per point of an infinite array L and its error probability on an additive white Gaussian noise (AWGN) channel. It is shown that the sphere bound can be approached by a large class of coset codes or multilevel coset codes with multistage decoding, including certain binary lattices. These codes have structure of the kind that has been found to be useful in practice. Capacity curves and design guidance for practical codes are given. Exponential error bounds for coset codes are developed, generalizing Poltyrev's (1994) bounds for lattices. These results are based on the channel coding theorems of information theory, rather than the Minkowski-Hlawka theorem of lattice theory     

Unitary signal constellations for differential space-time modulation with two transmit antennas: parametric codes, optimal designs, and bounds

We focus on the design of unitary signal constellations for differential space-time modulation with double transmit antennas. By using the parametric form of a two-by-two unitary matrix, we present a class of unitary space-time codes called parametric codes and show that this class of unitary space-time codes leads to a five-signal constellation with the largest possible diversity product and a 16-signal constellation with the largest known diversity product. Although the parametric code of size 16 is not a group by itself, we show that it is a subset of a group of order 32. Furthermore, the unitary signal constellations of sizes 32, 64, 128, and 256 obtained by taking the subsets of the parametric codes of sizes 37, 75, 135, and 273, respectively, have the largest known diversity products. We also use large diversity sum of unitary space-time signal constellations as another significant property for the signal constellations to have good performance in low-SNR scenarios. The newly introduced unitary space-time codes can lead to signal constellations with sizes of 5 and 9 through 16 that have the largest possible diversity sums. Subsequently, we construct a few sporadic unitary signal constellations with the largest possible diversity product or diversity sum. A four-signal constellation which has both the largest possible diversity product and the largest possible diversity sum and three unitary signal constellations with the largest possible diversity sums for sizes of 6, 7, and 8 are constructed, respectively. Furthermore, by making use of the existing results in sphere packing and spherical codes, we provide several upper and lower bounds on the largest possible diversity product and the largest possible diversity sum that unitary signal constellations of any size can achieve.     

On the frame-error rate of concatenated turbo codes

Turbo codes with long frame lengths are usually constructed using a randomly chosen interleaver. Statistically, this guarantees excellent bit-error rate (BER) performance but also generates a certain number of low weight codewords, resulting in the appearance of an error floor in the BER curve. Several methods, including using an outer code, have been proposed to improve the error floor region of the BER curve. We study the effect of an outer BCH code on the frame-error rate (FER) of turbo codes. We show that additional coding gain is possible not only in the error floor region but also in the waterfall region. Also, the outer code improves the iterative APP decoder by providing a stopping criterion and alleviating convergence problems. With this method, we obtain codes whose performance is within 0.6 dB of the sphere packing bound at an FER of 10^-6     

Density/length profiles and trellis complexity of lattices

The density/length profile (DCP) of a lattice Λ is analogous to the dimension/length profile of a linear code. The DLP is a geometrical invariant of Λ that includes the coding gain of Λ. Duality results analogous to those of linear block codes are derived for lattices. Bounds on the DLP may be derived from bounds on Hermite's constants; these hold with equality for many dense lattices. In turn, the DLP lowerbounds the state complexity profile of a minimal trellis diagram for Λ in any coordinate system. It is shown that this bound can be met for the E₈ lattice by a laminated lattice construction with a novel trellis diagram. Bounds and constructions for other important low-dimensional lattices are given. Two laminated lattice constructions of the Leech lattice yield trellis diagrams with maximum state space sizes 1024 and 972     

Performance of sphere decoding of block codes

A sphere decoder searches for the closest lattice point within a certain search radius. The search radius provides a tradeoff between performance and complexity. We focus on analyzing the performance of sphere decoding of linear block codes. We analyze the performance of soft-decision sphere decoding on AWGN channels and a variety of modulation schemes. A hard-decision sphere decoder is a bounded distance decoder with the corresponding decoding radius. We analyze the performance of hard-decision sphere decoding on binary and q-ary symmetric channels. An upper bound on the performance of maximum-likelihood decoding of linear codes defined over F_q (e.g. Reed- Solomon codes) and transmitted over q-ary symmetric channels is derived and used in the analysis.We then discuss sphere decoding of general block codes or lattices with arbitrary modulation schemes. The tradeoff between the performance and complexity of a sphere decoder is then discussed.     

A counterexample to a Voronoi constellation conjecture

Voronoi constellations are of interest because it is possible to save on signal power by choosing a lattice for which the second moment of the Voronoi region is close to that of a sphere with the same dimensionality. A Voronoi constellation based on the lattice partition Λ/Λ_s is the set of points in some translate Λ+a that fall within the Voronoi region R(Λ_s). G.D. Forney, Jr. (1989) proposed an algorithm for constructing Voronoi constellations and conjectured that this algorithm minimized the average signal power. A two-dimensional counterexample, to Forney's conjecture is presented     

Balanced codes and nonequiprobable signaling

The problem of shaping signal constellations that are designed for the Gaussian channel is considered. The signal constellation consists of all points from some translate of a lattice Λ that lie within a region R. The signal constellation is partitioned into T annular subconstellations Ω_o,…,Ω_T-1, by scaling the region R. Signal points in the same subconstellation are used equiprobably, and a shaping code selects region Ω_i with frequency f_i. If the signal constellation is partitioned into annular subconstellations of unequal size. then the transmission rate should vary with the choice of codeword in the shaping code. and it will be necessary to queue the data in buffers. It is described how the balanced binary codes constructed by D. E. Knuth (1986) can be used to avoid a data rate that is probabilistic. The basic idea is that if symbols 0 and 1 represent constellations of unequal size. and if all shaping codewords have equally many 0's and 1's, then the data rate will be deterministic     

Decoding spherical codes for the Gaussian channel

A decoding algorithm for permutation codes that is equivalent to maximum-likelihood decoding, but less complex than the correlation decoder, is presented. A general construction for iteratively maximum-likelihood decodable (IMLD) codes is proved and used to construct IMLD codes for every dimension n. D. Slepian (1965) defined permutation modulation codes and presented an efficient algorithm for their decoding. Slepian's decoding scheme is one of the principal components of the permutation code decoding algorithm presented