In this paper, the definition of threshold of elementary absorbing sets is extended to scaled Min-Sum low-density parity-check (LDPC) decoding. Based on the analysis of the behavior of scaled Min-Sum LDPC decoders in the Tanner graph of the absorbing set, it is proven that correct decoding is guaranteed with received channel messages above threshold. A fast algorithm for the threshold computation is derived. Many examples of absorbing sets taken from LDPC codes of various variable node degrees are investigated, and it is shown that all of them can be deactivated with low enough scaling factors.

Emerging memory technologies (like PCM, MRAM and 3D XPoint) can make data storage as fast as the rest of the system. But to cope with the reliability targets of storage applications, error correcting codes (ECCs) able to correct many errors might be needed anyway. Hierarchical codes, ECCs enabling two levels of correction, can be good candidates to satisfy these reliability targets, without impacting (on average) the low-latency characteristics of these technologies. In particular, an Ultra-Fast (UF) ECC can be used as first trial as long as it is able to flag its failures with high probability and low latency. In this paper we design an UF-ECC able to produce a check for incorrect decoding with probability lower than the typical target uncorrectable bit-error rate (UBER) of storage applications (e.g. 1e-15) and with a latency comparable with the UF-ECC correction process.

Absorbing sets (ASs) cause the error floor phenomenon in many Low-Density Parity-Check (LDPC) codes. A recent, simplified system model for Min-Sum (MS) LDPC decoding [1] predicts that ASs exhibit a threshold behavior: if all variable nodes in an AS have channel messages above the threshold, the AS cannot trap the decoder. The threshold is a real-valued parameter that depends on the topology of the AS, and can be evaluated by a nonlinear optimization. In this paper we describe a simple, fast algorithm for evaluating the AS threshold. Additionally, we show that the algorithm is valid also for scaled-MS decoding. We show with an example that the threshold values under scaled-MS decoding are smaller than under MS decoding. Accordingly, scaling decreases the error floor.

The error floor phenomenon in many low-density parity-check (LDPC) codes is caused by combinatorial objects in their Tanner graph, known as absorbing sets. In this paper, we highlight a threshold behavior for the min-sum decoding algorithm in the graph of an absorbing set with fixed-point representation of messages. For an absorbing set of interest in a binary LDPC code we can compute the threshold, a novel real-valued parameter that is closely related to its harmfulness. We show that absorbing sets with negative thresholds cannot trap the decoder if the dynamic range of the extrinsic messages is large enough. We also prove that, in regular LDPC codes, absorbing sets with negative thresholds exist if the variable node degree is odd. The examples presented in this paper show that odd-column-weight LDPC codes can have many absorbing sets with negative thresholds, but that these absorbing sets do not trap a well-designed decoder. Simulations show a good agreement between the results of the analysis presented in this paper and the performance of practical decoders with fixed-point messages.

High-performance storage class memories could benefit from a fast decoding error correcting code (ECC), able to correct a few errors in just a few nanoseconds. The class of BCH codes provides excellent candidates to play this role. The low latency requirement prevents adopting iterative or sequential processes in the encoding and decoding phases-as traditionally done for storage application based on Flash NAND technology. Therefore, we propose an architecture for fast decoding of double and triple ECCs. In our architecture, any time-consuming iterative computation is eliminated, and the most complex evaluations are isolated and carried in parallel with the other terms, to avoid bottlenecks in the decoder. In particular, the error locator polynomial is computed by a combinatorial logic, and its roots are searched by testing all the bits simultaneously. Here, we describe a gate-level design of these architectures. We also give an in-depth analysis of hardware-oriented implementations of finite field operations, and of bases for element representation.

In this paper, we consider Block Differential Modulation (BDM), to tackle the phase slip problem in digital communication systems. When the received signal phase can drift, the synchronizer can suddenly choose a wrong reference phase, e.g. adding multiples of 2π/M in case of M-ary Phase Shift Keying. Phase slips are detrimental for any coherent system since they cause long error bursts, till an opposite phase slip occurs. BDM is a generalization of Differential Modulation (DM). Neither of them relies on the absolute carrier phase. However, BDM differentially encodes information between small blocks of symbols and exploits couples of adjacent blocks to decode. This allows simple and practical demapping, without sacrificing capacity. We show that for low and moderate phase slip probabilities, BDM approaches the constrained capacity of coherent transmission, in particular at high spectral efficiencies. We provide closed-form results for the constrained capacity in absence of phase slips for Phase Shift Keying and Quadrature Amplitude Modulation, and we evaluate numerically the constrained capacity through an efficient Monte Carlo method, when phase slips occur. Besides, we provide simple upper and lower bounds.

In this paper, we consider joint estimation of the channel length and of the impulse response for OFDM systems, exploiting information criteria to find the best trade-off, in terms of Kullback-Leibler divergence, between noise rejection and channel description accuracy. So far, information criteria have not been used for practical channel length estimation methods, due to their prohibitive complexity. We show how to make them affordable, performing channel estimation in a recursive way that allows to establish the optimal channel length with a moderate incremental cost. With reference to IEEE 802.11 OFDM-based standards for WLAN, we investigate several cases, applying the joint channel length and impulse response estimation to many scenarios, ranging from the simplest pilot-aided channel estimation based on training sequences, to the most challenging data-aided channel tracking, driven either by detected or by decoded symbols. In all cases, the achieved performance and robustness are very good, with a very small increase in complexity w.r.t. estimation methods that assume fixed channel length.

In this paper, we consider joint estimation of the channel length and of the impulse response for OFDM systems, exploiting information criteria, to find the best trade-off between noise rejection and channel description accuracy. So far, information criteria have not been considered practical channel estimation methods, due to their prohibitive complexity. We show how to make them affordable, performing channel estimation in a recursive way that allows to establish the optimal channel length with a moderate incremental cost. Focusing on the 802.11 wireless LAN family, we investigate several cases, applying the joint channel length and impulse response estimation to many scenarios, ranging from the simplest pilot-aided channel estimation based on training sequences, to the most challenging data-aided channel tracking, driven either by detected or decoded symbols. In all cases, the performance and robustness are very good, with a very small increase in complexity w.r.t. estimation methods that assume fixed channel length.

We investigate a property that we have found in many efficient bilinear cyclic convolutions in GF (2m). We show that this property can reduce the additive complexity of cyclotomic FFTs. We explain how it arises, and why the most common constructions of cyclic convolutions yield this beneficial feature.

This paper is focused on cyclotomic Fourier transforms in GF(2m), and on their applications to algebraic decoding of Reed-Solomon codes, like the evaluation of syndromes and of error locator (or evaluator) polynomials. Cyclotomic transforms are much more efficient than straightforward evaluation. In particular, the number of multiplications is quite small. In this paper it is shown that also the number of additions can be considerably reduced with respect to previous analyses. A simple interpretation of the cyclotomic Fourier transform best suited for the evaluation of syndromes allows to assemble the required matrix easily and quickly, even in large fields. Fast construction of such matrices is important to obtain the best results, since as many matrices as possible must be generated and compared. It is shown that both the structure of the matrix and of bilinear convolutions need to be exploited, to reduce the complexity of the costly part of cyclotomic Fourier transforms, which is a matrix-vector product. Heuristic algorithms for matrix-vector product are to be run as many times as possible to obtain the best transform. It is shown with several examples that very good results can be obtained even with very simple algorithms.

In this paper we introduce an innovative version of the recently proposed Layered ORthogonal lattice Detector (LORD). LORD is an attractive MIMO detection algorithm, which aims to approach the optimal Maximum-Likelihood (ML) detection performance with a reasonable complexity, quadratic in the number of transmitting antennas rather than exponential. LORD is also well suited to a hardware (e.g. ASIC or FPGA) implementation because of its regularity, deterministic latency and parallelism. Nevertheless, its complexity is still high in case of high cardinality constellations, such as the 64-QAM foreseen by the 802.11n standard. We show that, when only global latency constraints exist, e.g. a fixed time to detect the whole OFDM symbol, the LORD complexity can be remarkably reduced (up to 60%), still approaching the ML performance.

We propose a novel family of Soft-Input Soft-Output detectors for iterative, point-to-point, MIMO receivers. Compared to the optimal Maximum A Posteriori receiver, low complexity is achieved restricting the detector search to small subsets of the entire QAM hyper-symbol constellation, through simple criteria. These criteria are applied to an improved version of the non-iterative Layered ORthogonal lattice Detector. We show that, notwithstanding the suboptimal low-complexity implementation, this detector approaches the EXtrinsic Information Transfer of the MAP detector. Therefore, when included in an iterative receiver it delivers the same performance. Furthermore, the deterministic complexity and highly parallelizable structure of the proposed detector are well suited for HDL and ASIC implementation. To focus on a specific setting, we consider the indoor MIMO wireless LAN 802.11n standard, taking into account errors in Channel Estimation and a frequency selective, spatially correlated channel model.

In this paper we introduce an improved version of the turbo layered orthogonal lattice detector (T-LORD), recently presented. This implementation, namely K-Best T-LORD, misses the performance of the turbo MAP detector by only few tenths of dB in various configurations, like the fully enhanced T-LORD. However, its complexity is quadratic in the number of transmitting antennas instead of exponential. Moreover, we show that the K-Best T-LORD is robust also over realistic channels, with correlation between tones and antennas, and with imperfect channel state Information at the receiver. This behavior is shown not only via Monte Carlo simulations, but also with EXIT chart analysis.

We reconsider the role of user selection in multiuser MIMO broadcast channels (downlink), in the relevant regime where the number of users K is linear in the number of transmitter (base station) antennas M. User selection is known to achieve mutually quasi-orthogonal user channels and, at the same time, a multiuser diversity effect in terms of receiver SNR. These goals are achieved in the regime of fixed number of transmit antennas, and very large number of users. In contrast, we show that when K = O(M) these effects cannot be achieved, and the role of user selection is marginal. In terms of system design, our results suggest that only a small number K ¿ M of users should feedback their channel state information at each point in time. This greatly alleviates the burden of the channel state information feedback, while achieving essentially optimal performance.

In this letter we propose rate variable turbo codes based on the parallel concatenation of tailbiting Recursive Systematic multi-binary (m-ary) convolutional codes. Rate variability is not achieved by puncturing, which can have adverse effects on the minimum distance of the code. Using a variable number of input lines of the encoder, we obtain several different overall rates ranging from 1/2 to 7/8. The most suitable Soft-in- Soft-out decoding algorithm for these turbo codes is based on the Dual Reciprocal Code, which is very efficient for high rate codes. A particular interleaver design, namely the "backbone" interleaver, guarantees a high Hamming weight in codewords with information weight 2 and 3, as well as good minimum distances and fairly low multiplicities for higher information weights. Therefore, these codes have very low error floors.

In this paper we deal with Maximum Likelihood (ML) decoding of Turbo Codes on the Binary Erasure Channel. First we describe a new ML decoder. When the standard iterative decoder fails because the set of erasures includes a stopping set, with the component decoders we obtain a linear system of equations that seeks the codeword constrained by both component codes. We evaluate the complexity in terms of equivalent turbo iterations and we show that this ML decoder is implementable. We also modify the algorithm proposed in [6] for LDPC to decode Turbo Codes and we compare the two methods. We find that, in general, our method is more efficient with low memory or punctured codes. Finally, by simulation we show that m-ary Turbo Codes under ML decoding outperform the error exponent bounds for random codes down to WER=10-6, for all rates ranging from 1/3 to 7/8.

In this paper we propose a coding-decoding scheme to be used for II-type hybrid ARQ on a binary erasure channel model, based on rate compatible punctured binary Turbo Codes, DRP interleaver design and ML decoding at the receiver. We carefully design the interleaver and the puncturing mask, and we describe how to achieve low-complexity Maximum Likelihood decoding. We show for the case of an MPEG2 packet size that this scheme overrides random codes upper bounds, providing throughputs within 0.05 bits from capacity at word error rates greater or equal to 10-6.

In this paper a novel Soft-Input Soft-Output detector, namely Turbo-LORD, is proposed for iterative MIMO receivers. This is an improved version, capable of managing a priori information, of the Layered ORthogonal lattice Detector recently presented. The implementation is straight and efficient when there are only two transmitting antennas. However, problems arising with more than two antennas are also discussed, along with possible solutions. It is shown that notwithstanding the suboptimal low-complexity implementation, this iterative receiver misses the performance of the turbo MAP detector by only few tenths of dB in various configurations, with very high spectral efficiency.

We consider multiple input-multiple output orthogonal frequency division multiplexing indoor wireless communications, adopting training assisted channel estimation. We focus on the transmission of orthogonal training sequences over a generic number of spatial streams, possibly different from the number of antennas. We show how to cope with performance requirements, low latency and complexity, firstly reducing the problem to a series of easier single input-single output problems, and finally exploiting the correlation between adjacent tones to refine the previously obtained estimations. As a practical example, we consider the 802.11n ongoing standard.

In this paper we consider an iterative detection and decoding scheme for Space-Frequency-Bit-Interleaved Coded Modulation (SF-BICM) MIMO-OFDM systems as a candidate receiver architecture for Next Generation Wireless LANs. This work is focused on the implementation complexity reduction of the overall turbo MIMO scheme through the simplification of the three main blocks: the Soft-Interference-Canceller, the MMSE-MIMO detector and the MIMO Soft-Symbol demapper which uses extrinsic soft information, produced by a Soft-Output-Viterbi-Algorithm (SOVA), to perform the LLRs calculation of the coded bits. A new receiver architecture is proposed, its computational complexity is estimated and compared with a more classical turbo MMSE receiver, both for 16-QAM and 64-QAM constellations.

In this letter, a turbo product code (TPC) is combined with multilevel modulations (8-phase-shift keying and 16-quadrature amplitude modulation). The component codes are Bose-Chaudhuri-Hocquengem (BCH) or extended BCH. We derive soft-input/soft-output modules based on the dual code, with exact Euclidean metrics, and we show that the iterative TPC decoder gains no advantage in performance from this. Next, we evaluate asymptotic approximations for maximum-likelihood (ML) decoding from a combinatorial approach that can be applied to any bit-interleaved multilevel modulated code, once the first term (or terms) of the Hamming weight spectrum are known. For the TPCs and modulations studied in this letter, random bit interleaving before modulation leads to improved ML asymptotes. Simulations confirm that this advantage is maintained also under iterative decoding.

We consider turbo decoding of parallel concatenated single parity check (SPC) (K+1,K) codes, with row-column interleaving. The existence and uniqueness of the asymptotic probability density evaluated with the turbo algorithm is proved for every length K and every signal-to-noise ratio (SNR).

We propose a variation of the algorithm for the construction of "spread" or S-random interleavers. This new version guarantees good spread properties that are also maintained under pruning. This makes this kind of interleaver attractive for those applications which require flexible size interleavers, such as flexible block size turbo codes, and flexible rate serially concatenated turbo codes.

The performance of a Reed-Solomon (RS) code has an analytical expression if the errors at the input of the decoder are independent. In concatenated schemes, this condition is often obtained through an interleaving device disrupting the correlation between erroneous symbols. Sometimes the ideal depth of such interleaver is too large to implement, and the RS decoder must operate in suboptimal conditions, for which no analytical formulas are available. In this paper, we present a statistical model that allows analytical evaluation of the performances of a concatenated scheme with an inner turbo code and an outer RS code, in the case of under-dimensioned interleavers. The model requires a statistical analysis of the erroneous symbols at the output of the inner decoder.

An importance sampling technique, tuned for the simulation of ideal or suboptimal MAP bit-per-bit decoding, is applied to some examples of turbo product codes, i.e. to turbo decoding of the product of block codes. The simulation results show the remarkable performances of the suboptimal algorithms. The presence of the so called "knee" in the performance curves, predicted by the maximum likelihood asymptotic bound, is also confirmed.

In this paper we present a comparative analysis of possible simplifications of various nonlinear receivers for the high density optical disc. Specifically, nonlinear adaptive Volterra equalization (NAVE), nonlinear adaptive decision feedback equalization (NDFE), and nonlinear maximum likelihood sequence estimation (NMLSE) are evaluated and compared. Reduced complexity NAVE and NDFE are obtained including fewer linear and nonlinear taps than required by full implementations. The NMLSE structure can be simplified not only reducing the number of (linear and nonlinear) taps of the preliminary equalizer, but also the number of trellis states and the path truncation length (i.e., memory) of the Viterbi detector. The performance comparison presented in this paper is based on a nonlinear channel model represented by a Volterra series. For the sake of simplicity, we assume that noise is additive, white, and Gaussian (AWGN model). Simulation results indicate that considerable simplifications are possible, at the expense of small performance degradations.

This paper presents a study aiming to define a nonlinear model, based on the Volterra series, of the high density optical disc read out process. Under the high density condition, because of the high linear density and reduced track pitch, the signal read out is not a linear process and suffers from crosstalk. To cope with such a problem the identification of a suitable nonlinear model is required. According to the Hopkins (1979) analysis, a physical model based on optical scalar theory was implemented. The results of this analysis have then been used to identify the kernels of a nonlinear model based on the Volterra series. The obtained results show that a second order bidimensional model is sufficient to accurately describe the read out process. The nonlinear Volterra model is a convenient starting point to devise and analyze nonlinear equalization and crosstalk cancellation techniques.

This paper presents a comparative analysis of various linear and nonlinear equalizers for a high density optical channel. Since the read-out process is nonlinear, a suitable model based on the Volterra series has been adopted. We compare the performance and complexity of equalizers designed for linear and nonlinear channels. Specifically, the adaptive minimum mean square error (MSE), adaptive decision feedback equalizer (DFE), nonlinear adaptive Volterra equalizer (NAVE) and nonlinear adaptive decision feedback equalizer (NDFE) are analyzed, along with the maximum likelihood sequence estimator (MLSE), which is considered as a reference. Simulations show that the performance of classical structures (MSE, DFE, MLSE) is significantly reduced by the nonlinear response and that the NAVE and NDFE achieve a performance close to the MLSE, with lower complexity.

In burst digital transmission using PSK (phase shift keying) modulation with coherent detection, the recovery of the carrier reference phase and the symbol clock is a key aspect. If all users have a common clock synchronization, symbol timing needs not to be recovered in each burst. A digital processor for carrier recovery without preambles, in the presence of frequency offset, is considered. As an example, a 2 Mb/s QPSK transmission system is considered in which E/sub b//N/sub o/=10 dB, and the burst and estimation interval length L=15. Using the algorithm described and averaging eight successive estimated frequency offsets, in order to eliminate anomalous errors, the BER (bit error rate) degradation is equal to 0.14 dB when Delta f=20 kHz.>

A solution is proposed for blind deconvolution problems, i.e. the estimation of the impulse response of an unknown discrete-time channel given the output data sequence and statistical information on the input sequence. The solution approaches the optimal one when the input sequence is independent and identically distributed and the channel distortion is small. Numerical results are given in the case of the optimal nonlinear function, which depends on the input probability density function, and in the case of the very simple sign function. The technique can be used iteratively if the distortion is not small.>

In view of a digital implementation of most of the signal processing required in a QAM demodulation-equalization Structure, a performance analysis as a function of equalizer complexity, A/D conversion resolution, and precision of internal arithmetic is presented. The analysis is focused on a 140 Mbit/s 64-QAM modulation scheme (corresponding to CEPT-4 or3 \times DS3systems), but extension to other QAM constellations is straightforward. Considerations of currently available technology, overall computational complexity, and related optimal quantization formats are presented. For high-speed 64 QAM, it is shown that satisfactory performance may be expected from a full digital implementation of reasonable complexity, using current technology.

The aim of this work is to investigate frequency discriminator detection for continuous phase digital modulation (CPM) in order to avoid the RF carrier recovery problem. An efficient demodulation scheme, based on a discriminator followed by a suitable baseband digital processor of acceptable complexity, is presented. The baseband processoris based on decision feedback and correlation. In the binary case we also derive a simplified scheme with good performance.

Continuous-phase, constant-envelope digital modulation schemes are useful in various applications where a high spectrum utilization as well as immunity to nonlinear distortion is required. From this point of view, typical efficient schemes are digital partialresponse frequency modulation methods. The aim of this work is to investigate noncoherent detection in order to avoid the RF carrier recovery problem. In this paper we select for analysis tamed frequency modulation (TFM) as a particularly representative member of this class, but a similar analysis could be carried out for other partialresponse digital FM systems. After an evaluation of the optimal noncoherent detection and of differential phase detection of TFM, we propose a demodulation method based on a simple and efficient baseband processing of the output of a frequency demodulator. It turns out that the power loss with respect to coherent or optimal demodulation of TFM is on the order of 2 dB. The baseband processing here proposed is in some way equivalent to a partial recovery of the carrier phase and could be improved by using a more complex baseband processing such as a decoding scheme based on the Viterbi algorithm.

In this paper we give a new simple expression for the probability of successful transmission on an infinite population ALOHA channel with variable length packets. Expressions for the throughput and the probability density of the packet length on the channel are derived in a straightforward way along with the best and the worst length densities.

A lower bound is found on the mean square error achievable by any nonlinear pulse modulation system without memory. This bound differs by 6 dB from the limit given by Shannon theorems, at high signal-to-noise ratios. The bound is obtained by finding the signal locus which minimizes a simple lower bound on mean square error, for a given average signal energy and without bandwidth constraints. For the locus that we have found, an upper bound on error shows that the degradation with respect to Shannon's limit is within 8 to 9 dB. The locus, however, does not seem of practical interest.

In this correspondence, the problem of lower bounds on mean-square error in parameter estimation is considered. Lower bounds on mean-square error can be used, for instance, to bound the performances, namely the attainable output signal-to-noise ratio, of pulse modulation transmission systems, such as pulse-position modulation (PPM) or pulse-frequency modulation (PFM). The tightest lower bounds to mean-square error previously known are the Ziv-Zakai bounds; the analysis carried out in this paper, which is based on an inequality first obtained by Kotel'nikov, leads to lower bounds tighter than previously known bounds.