Lattice codes with the optimal decoding coefficient are capacity-achieving when dimension N → ∞. In communications systems, finite dimensional lattice codes are needed, where the optimal decoding coefficient may still fail decoding even when R−5for a 2-user CF relay using 128- and 256-dimensional lattice codes with optimized CRC length and 2 decoding trials in total.

Approximate Message Passing (AMP) type algorithms are widely used for signal recovery in high-dimensional noisy linear systems. Recently, a principle called Memory AMP (MAMP) was proposed. Leveraging this principle, the gradient descent MAMP (GD-MAMP) algorithm was designed, inheriting the strengths of AMP and OAMP/VAMP. In this paper, we first provide an overflow-avoiding GD-MAMP (OA-GD-MAMP) to address the overflow problem that arises from some intermediate variables exceeding the range of floating point numbers. Second, we develop a complexity-reduced GD-MAMP (CR-GD-MAMP) to reduce the number of matrix-vector products per iteration by 1/3 (from 3 to 2) with little to no impact on the convergence speed.

A coding lattice and a shaping lattice forms a nested lattice code$C$if Under some conditions,$C$is a finite cyclic group formed by rectangular encoding. This paper presents the conditions for the existence of such$C$and provides some designs. These designs correspond to solutions to linear Diophantine equations so that a cyclic lattice code$C$of arbitrary codebook size$M$can possess group isomorphism, which is an essential property for a nested lattice code to be applied in physical layer network relaying techniques such as compute and forward.

Approximate message passing (AMP) type algorithms have been widely used in the signal reconstruction of certain large random linear systems. A key feature of the AMP-type algorithms is that their dynamics can be correctly described by state evolution. However, state evolution does not necessarily guarantee the convergence of iterative algorithms. To solve the convergence problem of AMP-type algorithms in principle, this paper proposes a memory AMP (MAMP) under a sufficient statistic condition, named sufficient statistic MAMP (SS-MAMP). We show that the covariance matrices of SS-MAMP are L-banded and convergent. Given an arbitrary MAMP, we can construct the SS-MAMP by damping, which not only ensures the convergence, but also preserves the orthogonality, i.e., its dynamics can be correctly described by state evolution.

A genie-aided decoder for finite dimensional lattice codes is considered. The decoder may exhaustively search through all possible scaling factors $\alpha \in {\mathbb{R}}$. We show that this decoder can achieve lower word error rate (WER) than the one- shot decoder using αMMSEas a scaling factor. A lower bound on the WER for the decoder is found by considering the covering sphere of the lattice Voronoi region. The proposed decoder and the bound are valid for both power-constrained lattice codes and lattices. If the genie is applied at the decoder, E8 lattice code has 0.5 dB gain and BW16 lattice code has 0.4 dB gain at WER of 10-4compared with the one-shot decoder using αMMSE. A method for estimating the WER of the decoder is provided by considering the effective sphere of the lattice Voronoi region, which shows an accurate estimate for E8 and BW16 lattice codes. In the case of per-dimension power P → ∞, an asymptotic expression of the bound is given in a closed form. A practical implementation of a simplified decoder is given by considering CRC-embedded n =128 polar code lattice.

Designs and methods for nested lattice codes using Construction D’ lattices for coding and convolutional code lattices for shaping are described. Two encoding methods and a decoding algorithm for Construction D’ coding lattices that can be used with shaping lattices for power-constrained channels are given. We construct nested lattice codes with good coding properties, high shaping gain, and low-complexity encoding and decoding. Convolutional code generator polynomials for Construction A lattices with the greatest shaping gain are given, as a result of an extensive search. It is shown that rate 1/3 convolutional codes provide a more favorable performance-complexity trade-off than rate 1/2 convolutional codes. Tail-biting convolutional codes have higher shaping gain than that of zero-tailed convolutional codes. A design for quasi-cyclic low-density parity-check (QC-LDPC) codes to form Construction D’ lattices which have efficient encoding and indexing is presented. The resulting QC-LDPC Construction D’ lattices are evaluated using four shaping lattices: the$E_{8}$lattice, the$BW_{16}$lattice, the Leech lattice and our best-found convolutional code lattice, showing a shaping gain of approximately 0.65 dB, 0.86 dB, 1.03 dB and 1.25 dB at dimension 2304.

Approximate message passing (AMP) is a low-cost iterative parameter-estimation technique for certain high-dimensional linear systems with non-Gaussian distributions. AMP only applies to independent identically distributed (IID) transform matrices, but may become unreliable (e.g., perform poorly or even diverge) for other matrix ensembles, especially for ill-conditioned ones. To solve this issue, orthogonal/vector AMP (OAMP/VAMP) was proposed for general right-unitarily-invariant matrices. However, the Bayes-optimal OAMP/VAMP (BO-OAMP/VAMP) requires a high-complexity linear minimum mean square error (MMSE) estimator. This prevents OAMP/VAMP from being used in large-scale systems. To address the drawbacks of AMP and BO-OAMP/VAMP, this paper offers a memory AMP (MAMP) framework based on the orthogonality principle, which ensures that estimation errors in MAMP are asymptotically IID Gaussian. To realize the required orthogonality for MAMP, we provide an orthogonalization procedure for the local memory estimators. In addition, we propose a Bayes-optimal MAMP (BO-MAMP), in which a long-memory matched filter is used for interference suppression. The complexity of BO-MAMP is comparable to AMP. To asymptotically characterize the performance of BO-MAMP, a state evolution is derived. The relaxation parameters and damping vector in BO-MAMP are optimized based on state evolution. Most crucially, the state evolution of the optimized BO-MAMP converges to the same fixed point as that of the high-complexity BO-OAMP/VAMP for all right-unitarily-invariant matrices, and achieves the Bayes optimal MSE predicted by the replica method if its state evolution has a unique fixed point. Finally, simulations are provided to verify the theoretical results’ validity and accuracy.

This paper focuses on the encoding and decoding of Construction D' coding lattices that can be used with shaping lattices for power-constrained channels. Two encoding methods and a decoding algorithm for Construction D' lattices are given. A design of quasi-cyclic low-density parity-check (QC-LDPC) codes to form Construction D' lattices is presented. This allows construction of nested lattice codes which are good for coding, good for shaping, and have low-complexity encoding and decoding. Numerical results using$E_{8},\ BW_{16}$and Leech lattices for shaping a Construction D' lattice indicate that the shaping gains 0.65 dB, 0.86 dB and 1.03 dB are preserved, respectively.

Approximate message passing (AMP) is a low-cost iterative parameter-estimation technique for certain high-dimensional linear systems with non-Gaussian distributions. However, AMP only applies to independent identically distributed (IID) transform matrices, but may become unreliable for other matrix ensembles, especially for ill-conditioned ones. To handle this difficulty, orthogonal/vector AMP (OAMP/VAMP) was proposed for general right-unitarily-invariant matrices. However, the Bayes-optimal OAMP/VAMP requires high-complexity linear minimum mean square error estimator. To solve the disadvantages of AMP and OAMP/VAMP, this paper proposes a memory AMP (MAMP), in which a long-memory matched filter is proposed for interference suppression. The complexity of MAMP is comparable to AMP. The asymptotic Gaussianity of estimation errors in MAMP is guaranteed by the orthogonality principle. A state evolution is derived to asymptotically characterize the performance of MAMP. Based on the state evolution, the relaxation parameters and damping vector in MAMP are optimized. For all right-unitarily-invariant matrices, the optimized MAMP converges to OAMP/VAMP, and thus is Bayes-optimal if it has a unique fixed point. Finally, simulations are provided to verify the validity and accuracy of the theoretical results.

Polar code lattices are formed from binary polar codes using Construction D. In this paper, we propose a design technique for finite-dimension polar code lattices. The dimension$n$and target probability of decoding error are parameters for this design. To select the rates of the Construction D component codes, rather than using the capacity as in past work, we use the explicit finite-length properties of the polar code. Under successive cancellation decoding, density evolution allows choosing code rates that satisfy the equal error probability rule. At an error-rate of 10−4, a dimension$n$= 128 polar code lattice achieves a VNR of 2.5 dB, within 0.2 dB of the best-known BCH code lattice, but with significantly lower decoding complexity.

Recently, it was found that clipping can significantly improve the section error rate (SER) performance of sparse regression (SR) codes if an optimal clipping threshold is chosen. In this paper, we propose irregularly clipped SR codes, where multiple clipping thresholds are applied to symbols according to a distribution, to further improve the SER performance of SR codes. Orthogonal approximate message passing (OAMP) algorithm is used for decoding. Using state evolution, the distribution of irregular clipping thresholds is optimized to minimize the SER of OAMP decoding. As a result, optimized irregularly clipped SR codes achieve a better tradeoff between clipping distortion and noise distortion than regularly clipped SR codes. Numerical results demonstrate that irregularly clipped SR codes achieve 0.4 dB gain in signal-to-noise-ratio (SNR) over regularly clipped SR codes at code length ≈2.5 × 104and SER ≈10−5. We further show that irregularly clipped SR codes are robust over a wide range of code rates.

This paper proposes a low-complexity decoding algorithm for complex low-density lattice codes (CLDLC). The key is a method to approximate an infinite complex Gaussian mixture that occurs at the variable node of the belief propagation (BP) decoder. We define the reliability of check-to-variable messages and a threshold function to determine the number of complex Gaussian functions to use in the approximation. This allows the number of Gaussians in the approximation to be adaptively selected depending upon its reliability. By using the minimum number of Gaussians needed for an accurate approximation, the complexity of the decoder can be significantly reduced. The reliability is based on a likelihood function, and we form an upper bound on the Kullback-Leibler (KL) divergence to find the threshold function via linear regression. The approximation based on reliability of each message can reduce the complexity to $O(n\cdot t\cdot 1.35^{d-1})$ at high volume-to-noise ratio (VNR), where n is the lattice dimension, d is the degree of the inverse generator matrix, and t is the number of iterations. This algorithm provides higher performance and lower complexity compared to previously proposed approximation algorithms.

The WiFi backscatter communications offer ultralow power and ubiquitous connections for IoT systems. Caused by the intermittent-nature of the WiFi traffics, state-of-the-art WiFi backscatter communications are not reliable for backscatter link or simple for the tag to do the adaptive transmission. In order to build reliable WiFi backscatter communications, we present GuardRider, a WiFi backscatter system that enables backscatter communications to improve the quality of service (QoS). The key contribution of GuardRider is an optimization algorithm of designing RS codes to follow the statistical knowledge of WiFi traffics and adjust backscatter transmission. With GuardRider, the reliable baskscatter link is guaranteed and a backscatter tag is able to adaptively transmit information without heavily listening to the excitation channel, by taking QoS into account. We built a hardware prototype of GuardRider using a customized tag with FPGA implementation. Both the simulations and field experiments verify that GuardRider could achieve notably gains in bit error rate and frame error rate, which are a hundredfold reduction in simulations and around 99% in filed experiments. Our system is able to achieve around 700 kbps throughput.

In this paper, we develop an orthogonal precoding scheme for integer-forcing (IF) linear receivers using the steepest gradient algorithm. Although this scheme can be viewed as a special case of the unitary precoded integer-forcing (UPIF), it has two major advantages. First, the orthogonal precoding outperforms its unitary counterpart in terms of achievable rate, outage probability, and error rate. We verify this advantage via theoretical and numerical analyses. Second, it exhibits lower complexity as the dimension of orthogonal matrices is half that of unitary matrices in the real-valued domain. For finding “good” orthogonal precoder matrices, we propose an efficient algorithm based on the steepest gradient algorithm that exploits the geometrical properties of orthogonal matrices as a Lie group. The proposed algorithm has low complexity and can be easily applied to an arbitrary MIMO configuration. We also confirm numerically that the proposed orthogonal precoding outperforms UPIF type II in some scenarios and the X-precoder in high-order QAM schemes, e.g., 64- and 256-QAM.

This paper focuses on orthogonal precoding for integer-forcing linear receiver and shows it has two advantages over unitary precoding. Orthogonal precoding exhibits lower complexity than unitary precoding because the dimension of orthogonal matrices is half that of unitary matrices for a fixed number of antennas. Moreover, orthogonal precoding outperforms unitary precoding in terms of achievable rate and error-rate. Despite its promising advantages, it is not easy to find the optimal precoding matrices because it involves an orthogonality constraint and the shortest lattice vector problem. To solve this, we separate the optimization problem into two sub-problems and propose methods based on the steepest gradient with Lie groups and a random search algorithm. The proposed methods have low complexity and are applicable to any MIMO dimension. For high-order QAM, the proposed orthogonal precoder outperforms X-precoders which are designed specifically for QAM.

The decoding of Construction D lattices is described. While similar to the multistage decoding of Code Formula codes, modification is required so that lattice components are subtracted in a process called reencoding. A generator matrix for Construction D lattices is given. Construction D lattices obtained from BCH codes were described by Barnes and Sloane. In this paper, we consider some practical issues of encoding and decoding these lattices. Using ordered statistics decoding, dimension 128 BCH code lattices outperform turbo lattices and low-density lattice codes of similar dimension. These results show relatively good performance of lattices based on algebraic constructions, compared to lattices typically designed for high dimensions. The performance over power-constrained channel is also evaluated, where the near-optimal performance is demonstrated.

A physical-layer network coding approach, compute-and- forward based on nested lattice code (NLC), is considered for multi-source multi-relay networks. This paper proposes a design of overlapped chunked code (OCC) which is applied before NLC, which we call OCC/CF. Random linear network coding is applied within each chunk. Only the transmissions from the sources to the relays are considered. The design is based on the empirical rank distribution and the empirical probability distributions of the participation factor of all sources. A consecutive OCC is employed with the proposed design to investigate the performance of OCC/CF. From the numerical results, the design overhead of OCC/CF is low when the probability distribution of the participation factor is dense at chunk size for each source.

This paper studies the shaping gain and the performance-complexity trade-off of convolutional code lattices, lattices that are based on convolutional codes and Construction A. Generator polynomials for convolutional codes which provide the best-found shaping gain are presented, for various code rates, memory orders and lattice dimensions. Results are based on exhaustive searches. The obtained shaping gains usually exceed that of convolutional codes good for coding. Convolutional code lattices with memory order 7 can provide a shaping gain of 1.20 dB (up to a possible 1.53 dB theoretical maximum) at dimension 256, which is higher than the 1.03 dB shaping gain of the Leech lattice. While convolutional code lattices based on rate 1/2 convolutional codes have the best shaping gain for a fixed memory order, we show that using rate 1/3 convolutional codes produces a more favorable performance-complexity trade-off.

With the aim of improving network throughput and achieving full diversity gain, this paper focuses on strategies for applying compute-and-forward (CF) scheme to the multiple access relay channel (MARC). The direct application of the original CF to the MARC results in poor error performance due to the probability of a rank deficient coefficient matrix, which is an inherent problem of a CF system. One way to solve this problem is by allowing the relay and the destination to fully cooperate with each other in constructing a full rank coefficient matrix. However, this requires a large amount of communication overhead. This paper proposes an efficient strategy where the destination always attempts to decode transmitted messages by itself, without the help of the relay. The destination cooperates with the relay only when necessary. It is shown that with a small amount of overhead, the proposed strategy outperforms the existing approaches in terms of achievable sum-rate, outage probability, and throughput. Furthermore, the proposed strategy also achieves the full diversity gain of the MARC.

This paper proposes reliability-based parametric decoding of low-density lattice codes (LDLC). We define the reliability of the check-to-variable messages for two purposes. The first one is to choose to approximate the infinite Gaussian mixtures by one or two Gaussians. The reliability of each check-to-variable message is calculated. If there is higher reliability than a fixed threshold value, one Gaussian will be selected; otherwise two Gaussians will be used. The other purpose is for the updating sequence of variable nodes of the parametric shuffled BP (SBP) decoding algorithm. The parametric SBP increases the convergence speed. The updating sequence of SBP follows the order of reliability of the check-to-variable messages from high to low. The numerical results show that the proposed algorithm gives superior performance and lower complexity compared to two or three Gaussian decoding algorithm. At a probability of symbol error equal 10-4and n = 100 and 1000, the proposed algorithm gains 0.25 and 0.2 dB, respectively. Moreover, the proposed algorithm provides lower decoding time, fewer number of iterations for convergence and lower memory requirement.

Encoding and indexing of lattice codes is generalized from self-similar lattice codes to a broader class of lattices. If coding lattice Acand shaping lattice Assatisfy As⊆ Ac, then Ac/Asis a quotient group that can be used to form a (nested) lattice code C. Conway and Sloane's method of encoding and indexing does not apply when the lattices are not self-similar. Results are provided for two classes of lattices. 1) If Acand As both have generator matrices in a triangular form that satisfies As⊆ Ac, then encoding is always possible. 2) When Acand Asare described by full generator matrices, if a solution to a linear diophantine equation exists, then encoding is possible. In addition, special cases where C is a cyclic code are considered. A condition for the existence of a group isomorphism between the information and C is given. The results are applicable to a variety of coding lattices, including Construction A, Construction D, and low-density lattice codes. A variety of shaping lattices may be used as well, including convolutional code lattices and the direct sum of important lattices such as D4, E8, etc. Thus, a lattice code C can be designed by selecting Acand Asseparately, avoiding the competing design requirements of self-similar lattice codes.

We consider a multiple access relay channel (MARC) network consisting of two sources, one relay, and one common destination applying compute-and-forward (CF) strategy. We show that the direct application of CF to the MARC network results in poor error performance bounded by (p + 1)-1, the probability of rank deficiency of the coefficient matrix over Fp. To solve this problem, we propose two practical approaches. First, given an optimal coefficient vector at the relay, the destination is restricted to select a coefficient vector ensuring a full rank coefficient matrix. Second, given an optimal coefficient vector at the destination obtained via a small amount of feedback, the relay is restricted to choose a coefficient vector guaranteeing a full rank coefficient matrix. We simulate these CF implementation strategies using self-similar nested E8lattice codes and confirm that both of the proposed schemes outperform the direct implementation in terms of achievable transmission rate and frame-error-rate performance. Furthermore, we confirm that with a small amount of feedback, the second strategy is better than the first one. In addition, we present in detail a modified Fincke-Pohst algorithm for computing the coefficient candidates and show its efficiency compared to an exhaustive search.

The general problem of quantizing observation signals appears in different aspects of data processing, from special code designs to realization of low-complexity receivers. To this end, a new framework, known as the Information Bottleneck method, has recently attracted a great deal of attention. In this paper, after introducing this framework and providing the Iterative Information Bottleneck algorithm as the primary pertinent solution, we also discuss three other heuristics aiming to solve the similar problem efficiently. Since the resultant solution of considered approaches is locally optimum, it strongly depends on the choice of initialization. The main contribution of this work is to prove the equivalence of these algorithms asymptotically, i.e., assuming an infinite run of algorithms for the extreme case of infinitely large trade-off parameter. We also substantiate this claim by means of computer-based simulations.

A binary-input, memoryless channel with a continuous-valued output quantized to one bit is considered. For arbitrary noise models, conditions on an optimal quantizer, in the sense of maximizing mutual information between the channel input and the quantizer output, are given. This result is obtained by considering the “backward” channel and applying Burshtein et al.'s theorem on optimal classification. In this backward channel, there exists an optimal quantizer for which the quantizer preimage is convex. It is possible no optimal forward quantizer is convex, but by working with the backward channel, the optimal quantizer may be found. However, if the channel satisfies a certain condition, then a convex optimal forward quantizer exists.

This paper proposes a transmission scheme which applies random linear network coding (RLNC) over compute-and-forward (CF), called RLNC/CF, in multi-source multi-relay networks. Instead of solving the full rank failure at relays, this paper compensates for this overhead to increase the possibility of successfully decoding computed messages at the destination. The concept of the overlapped generations is applied with a proposed computing and storing strategy. This paper provides a compensation based on the estimation of the channel state information (CSI) of the previous generation and a compensation based on the learning data of CSI. By comparing to an orthogonal channel transmission scheme, a performance trade-off is considered. An expression for estimated performances of RLNC/CF in function of the probabilities of the parameters related to CSI is provided to help for the decision of selecting transmission scheme. From the numerical result, RLNC/CF scheme works better than a conventional CF transmission scheme in reducing the transmission latency.

For low-density parity-check (LDPC) codes widely used in NAND flash memories, the bit-error rate performance is closely tied to the number of bits per message used by the message-passing decoder. This paper describes a technique to generate message-passing decoding mapping functions for LDPC codes using 3 and 4 bits per message. These maps are not derived from belief-propagation decoding or one of its approximations, instead, the maps are based on a channel quantizer that maximizes mutual information. More precisely, the construction technique is a systematic method, which uses an optimal quantizer at each step of density evolution to generate message-passing decoding mappings. Numerical results show, for high-rate codes suitable for flash memories, that 4 bits per message and a few iterations (10-20 iterations) are sufficient to approach full belief-propagation decoding, less than 5-7 bits per message typically needed. The construction technique is flexible, since it can generate maps for arbitrary number of bits per message, and can be applied to arbitrary memoryless channels.

Low density lattice codes (LDLCs) are high-dimensional lattices with a sparse inverse generator matrix that can be decoded efficiently using iterative decoding. In the iterative LDLC decoder, the messages are Gaussian mixtures, and for any implementation, the Gaussian mixtures must be approximated. This paper describes a parametric LDLC decoding algorithm, where internally at the variable node, infinite Gaussian mixtures are approximated with three or two Gaussians, while the messages between nodes are single Gaussians. Strengths of the algorithm include its simplicity and suitability for analysis. Analysis is performed by evaluating the Kullback-Leibler divergence between the true messages and the three/two Gaussian approximation. The approximation using three or two Gaussians is more accurate than previously proposed approximations. Also, noise thresholds for the proposed LDLC decoder are presented, and the proposed decoder reduces the noise thresholds 0.05 dB compared with previous parametric decoders. The numerical results show that for n = 100 and n = 1000, the two-Gaussian approximation is the same as the full-complexity decoder. But when the dimension is n = 10 000, a three-Gaussian approximation is needed.

We propose two low-complexity lattice code constructions that have competitive coding and shaping gains. The first construction, named systematic Voronoi shaping, maps short blocks of integers to the dithered Voronoi integers, which are dithered integers that are uniformly distributed over the Voronoi region of a low-dimensional shaping lattice. Then, these dithered Voronoi integers are encoded using a high-dimensional lattice retaining the same shaping and coding gains of lowand high-dimensional lattices. A drawback to this construction is that there is no isomorphism between the underlying message and the lattice code, preventing its use in applications such as compute-and-forward. Therefore, we propose a second construction, called mixed nested lattice codes, in which a high-dimensional coding lattice is nested inside a concatenation of low-dimensional shaping lattices. This construction not only retains the same shaping/coding gains as first construction but also provides the desired algebraic structure. We numerically study these methods, for point-to-point channels as well as compute-and-forward using low-density lattice codes as coding lattices and E8 and Barnes-Wall as shaping lattices. Numerical results indicate a shaping gain of up to 0.86 dB, compared with the state-ofthe-art of 0.4 dB; furthermore, the proposed method has lower complexity than the state-of-the-art approaches.

A recent result has shown connections between statistical learning theory and channel quantization. In this paper, we present a practical application of this result to the implementation of LDPC decoders. In particular, we describe a technique for designing the message-passing decoder mappings (or lookup tables) based on the ideas of channel quantization. This technique is not derived from sum-product algorithm or any other LDPC decoding algorithm. Instead, the proposed algorithm is based on an optimal quantizer in the sense of maximization of mutual information, which is inserted in the density evolution algorithm to generate the lookup tables. This algorithm has low complexity since it only employs 3-bit messages and lookup tables, which can be easily implemented in hardware. Two quantized versions of the min-sum decoding algorithm are used for comparison. Simulation results for a binary-input AWGN channel show 0.3 dB and 1.2 dB gains versus the two quantized min-sum algorithms. On the binary symmetric channel also a gain is seen.

A lattice code construction that employs two separate lattices, a high dimension lattice for coding gain and a low-dimension lattice for shaping gain, is described. Systematic lattice encoding is a method to encode an integer sequence to a lattice point that is nearby that integer sequence. We describe the “Voronoi integers” ℤm/Λs, the set of integers inside the fundamental Voronoi region of a shaping lattice Λs, and a concrete scheme to label these integers. By first shaping the information using the Voronoi integers in low dimension, and then performing systematic lattice encoding using a high-dimension lattice, good shaping and coding gains can be simultaneously obtained. We concentrate on the case of using the E8lattice for shaping and low-density lattice codes (LDLC) with dimension ~ 10,000 for coding. While optimal shaping provides a well-known 1.53 dB gain, previously reported shaping gains with LDLC lattices are on the order of 0.4 dB. The proposed method preserves the shaping gain of the E8lattice, that is, as much as 0.65 dB. This shaping operation can be implemented with lower complexity than previous LDLC approaches.

For low-density lattice codes (LDLC), there is a condition for convergence of the messages under belief-propagation decoding, specifically a condition on the inverse generator matrix for the variances in the Gaussian mixture to converge. It offers guidance on the design of Latin square LDLC lattices. This paper revisits this condition, and then describes two other constructions, a modified Latin square construction and a triangular array code construction. We illustrate how the condition can be applied, demonstrating the validity of the condition for more general LDLC lattices.

We consider t-write codes for write-once memories with n cells that can store multiple levels. Assuming an underlying lattice-based construction and using the continuous approximation, we derive upper bounds on the worst-case sum-rate optimal and fixed-rate optimal n-cell t-write write-regions for the asymptotic case of continuous levels. These are achieved using hyperbolic shaping regions that have a gain of 1 bit/cell over cubic shaping regions. Motivated by these hyperbolic write-regions, we discuss construction and encoding of codebooks for cells with discrete support. We present a polynomial-time algorithm to assign messages to the codebooks and show that it achieves the optimal sum-rate for any given codebook when n = 2. Using this approach, we construct codes that achieve high sum-rate. We describe an alternative formulation of the message assignment problem for n≥ 3, a problem which remains open.

This paper describes a coded modulation scheme where low-dimension lattices are used as the constellation, and Reed-Solomon codes are used for error correction. Low-dimension lattices, such as the eight-dimensional E8lattice, have better distance properties than one- and two-dimensional constellations, and they have efficient soft-input decoding algorithms as well. On the other hand, Reed-Solomon codes have optimal distance properties, and their decoding algorithms are well understood. This construction is targeted at high-rate flash memories, where BCH codes using Gray-coded pulse-amplitude modulation are often used. Performance gains of 1.0 dB to 1.8 dB over BCH codes is demonstrated through analysis and simulation, under the assumption of additive white Gaussian noise. For flash memory systems where the ECC chip is separate from the flash chip, this code construction allows using soft information entirely inside a flash memory chip which has a low-complexity lattice decoder implementation.

The quantization of the output of a binary-input discrete memoryless channel to a smaller number of levels is considered. An algorithm, which finds an optimal quantizer, in the sense of maximizing mutual information between the channel input and quantizer output is given. This result holds for arbitrary channels, in contrast to previous results for restricted channels or a restricted number of quantizer outputs. In the worst case, the algorithm complexity is cubic M3in the number of channel outputs M. Optimality is proved using the theorem of Burshtein, Della Pietra, Kanevsky, and Nádas for mappings, which minimize average impurity for classification and regression trees.

This paper considers that write-once memory (WOM) codes can be seen as a type of dirty-paper code. The current state of the memory, which is known to the encoder, plays the role of the known interference of dirty-paper coding. Erez, Shamai and Zamir showed that lattice strategies can achieve the capacity of the known-interference channel. In this paper, lattices are used to design a WOM code. Encoding is performed modulo a shaping lattice with respect to a lattice fundamental region to obtain a codeword, to be added to the current state of the memory. The fundamental region is designed to accommodate the limitations of the flash memory system, particularly, that values can only increase. The criterion for evaluation is average number of writes. In order to improve the average number of writes, “coset select” bits are introduced, to maximize the average number of writes. For an eight-dimensional lattice, numerical results for practical parameter choices show a promising trend.

This paper proposes a NAND flash system that uses Write-Once Memory (WOM) codes to encode the data stored. It is shown through both analysis and simulation that, with proper parameters, flash memories which use WOM codes to encode data can achieve a lower write amplification than in a non-WOM-coded system. For example, in a 16-level per cell flash memory, when a two-write MLC WOM code is used with a total overprovisioning of 0.8, the write amplification is 15% lower than a non-WOM-coded system. A closed-form expression for the write amplification in a WOM-coded system is given for a system with a greedy garbage collection policy and a uniform random workload. The proposed expression is a function of the total overprovisioning factor, number of WOM code writes, and number of values per cell. The expression is applicable for both SLC and MLC flash.

The problem of finding the optimum output quantizer for a given discrete memoryless channel is investigated, where the quantizer output has fewer values than the channel output. While mutual information has received attention as an objective function for optimization, the focus of this paper is use of the random coding exponent, which was originally derived by Gallager, as criteria. Two problems are addressed, where one problem is a partial problem of the other. The main result is a quantizer design algorithm, and a proof that it finds the optimum quantizer in the partial problem. The quantizer design algorithm is based on a dynamic programming approach, and is an extension of a mutual-information maximization method. For the binary-input case, it is shown that the optimum quantizer can be found with complexity that is polynomial in the number of channel outputs.

Consider a binary-input, M-output discrete memoryless channel (DMC) where the outputs are quantized to K levels, with K <; M. The subject of this paper is the maximization of mutual information between the input and quantizer output, over both the input distribution and channel quantizer. This can be regarded as finding the capacity of a quantized DMC. An algorithm is given, which either finds the optimal input distribution and corresponding quantizer, or declares a failure.

While it is known that spatially-coupled low-density lattice codes (SC-LDLC) have better decoding performance than conventional (non-coupled) LDLC lattices, in this paper it is shown that their encoding complexity is also lower. Since nonzero elements are mainly in lower triangular entries of the sparse inverse generator matrix of SC-LDLC, iterative encoding with the Gauss-Seidel method performs well. The convergence speed of iterative encoding is evaluated by both the mean square error (MSE) and the symbol error rate between a given integer vector b and the inversely generated integer vector from the codeword of b. Numerical experiments show that the convergence of encoding for SC-LDLC is 3 times faster than that of the conventional LDLC, at an MSE of 10-10for dimension n = 10000.

A construction using the E8 lattice and Reed-Solomon codes for error-correction in flash memory is given. Since E8 lattice decoding errors are bursty, a Reed-Solomon code over GF($2^8$) is well suited. This is a type of trellis-coded modulation, where the Euclidean distance of the lattice (which is an eight-dimensional constellation) is combined with the Hamming distance of the code. This system is compared with the conventional technique for flash memories, BCH codes using Gray-coded PAM. This construction has a performance advantage of 1.7 to 2.0 dB for an uncoded data density of 3 bits/cell.

We study a new synchronization algorithm based on low-density parity check codes. The algorithm was developed for scenarios with redundant information in 2010, [1]. We describe a revised version of the algorithm and, for the first time, we discuss the fundamentals about the coding and decoding theory. The results of this analysis define the scope and restrictions of the algorithm. We show that the algorithm is capable of recovering synchronization even in scenarios without redundant information. The algorithm has the characteristic of using not only cyclically permutable codes like the related proposals. Nevertheless special attention must be paid to short codes. Finally, an accurate approximation of the bound is introduced by using maximum likelihood decoding.

An explicit code construction for using low-density lattice codes (LDLC) on the constrained power AWGN channel is given. LDLC lattices can be decoded in high dimension, so that the code relies on the Euclidean distance between codepoints. A sublattice of the coding lattice is used for code shaping. Lattice codes are designed using the continuous approximation, which allows separating the contribution of the shaping region and coding lattice to the total transmit power. Shaping and lattice decoding are both performed using a belief-propagation decoding algorithm. At a rate of 3 bits per dimension, a dimension 100 code which is 3.6 dB from the sphere bound is found.

A new method for decoding low-density lattice codes is given, wherein the belief-propagation decoder messages are single Gaussian functions. Since the message can be represented by two numbers, a mean and a variance, the complexity of this decoder is lower than previous decoders, which either quantized the mixture, or used a mixture of Gaussians. The computational complexity at the check node is also lower. The performance of various code designs, under single-Gaussian decoding, is evaluated by noise thresholds. In particular, the proposed decoding algorithm has noise threshold within 0.1 dB of the quantized-message decoder, which is considerably more complex.

For decoding low-density parity-check (LDPC) codes on discrete memoryless channels, a method to quantize messages and to find message-passing decoding functions for the variable and check nodes is developed. These are used to obtain noise thresholds by density evolution. The message-passing decoding alphabet is restricted to be discrete with a fixed maximum alphabet size. Discrete quantization is required to obtain this fixed alphabet size; a greedy algorithm which uses the mutual information between the code bit and message is presented. It is argued that using this message-passing decoding framework is more efficient for approaching channel capacity than simply quantizing the belief-propagation algorithm. This method is evaluated using regular LDPC codes on the binary symmetric channel. Using a maximum alphabet size of 16 (4 bits), noise thresholds close to those of belief propagation are obtained.

A belief-propagation decoder for low-density lattice codes, which represents messages explicitly as a mixture of Gaussians functions, is given. In order to prevent the number of functions from growing as the decoder iterations progress, a method for reducing the number of Gaussians at each step is given. A squared distance metric is used, which is shown to be a lower bound on the divergence. For an unconstrained power system, comparisons are made with a quantized implementation. For a dimension 100 lattice, a loss of about 0.2 dB was found; for dimension 1000 and 10000 lattices, the difference in error rate was indistinguishable. The memory required to store the messages is substantially superior to the quantized implementation.

Vector quantization of the BCJR and Viterbi algorithms' state metrics for detection of finite-state channels is considered. An estimate is given for the gain associated with vector quantization, over conventional implementations. This is expressed using the volume of the recurrent region, and the maximum state metric difference, which are both intrinsic properties of the channel detector. One application of this gain is the complexity evaluation of a previously proposed lookup-table BCJR implementation. The BCJR algorithm is of interest in turbo equalization used for communication over intersymbol-interference and finite-state Markov channels

This paper describes the analysis of convolutional codes on the erasure channel. We compare the maximum likelihood (ML) sequence decision and the maximum a posteriori (MAP) symbol decision for codes, which are transmitted over the erasure channel. When a codeword from a linear error correcting code with elements from the field GF is transmitted over a q-ary erasure channel, the symbol error rate of the maximum likelihood (ML) sequence decision is the same as that of the symbol maximum a posteriori (MAP) probability decision. When decoding convolutional codes transmitted over an AWGN channel, it is widely known that the probability of symbol error for the Viterbi algorithm (which is a sequence ML decoder) is generally higher than that for the more complex BCJR algorithm (which is a symbol MAP decoder).

Analytic expressions for the exact probability of erasure for systematic, rate- 1/2 convolutional codes used to communicate over the binary erasure channel and decoded using the soft-input, soft-output (SISO) and a posteriori probability (APP) algorithms are given. An alternative forward-backward algorithm which produces the same result as the SISO algorithm is also given. This low-complexity implementation, based upon lookup tables, is of interest for systems which use convolutional codes, such as turbo codes.

Ideas of message passing are applied to the problem of removing the effects of intersymbol interference (ISI) from partial-response channels. Both bit-based and state-based parallel message-passing algorithms are proposed. For a fixed number of iterations less than the block length, the bit-error rate of the state-based algorithm approaches a nonzero constant as the signal-to-noise ratio (SNR) approaches infinity. This limitation can be removed by using a precoder. It is well known that low-density parity-check (LDPC) codes can be decoded using a message-passing algorithm. Here, a single message-passing detector/decoder matched to the combination of a partial-response channel and an LDPC code is investigated.

Message-passing has been proposed for decoding parity check codes, especially low density parity check (LDPC) codes. We propose using message-passing detectors for partial response channels. Furthermore, we investigate how a single message-passing detector/decoder can be matched to a combination of a partial response channel and a LDPC code.