1,721,058 research outputs found
High-Throughput Random Access via Codes on Graphs
No full textRecently, contention resolution diversity slotted ALOHA (CRDSA) has
been introduced as a simple but effective improvement to slotted ALOHA. It relies on MAC burst repetitions and on interference cancellation to increase the normalized throughput of a classic slotted ALOHA access scheme. CRDSA allows achieving a larger throughput than slotted ALOHA, at the price of an increased average transmitted power. A way to trade-off the increment of the average transmitted power and the improvement of the throughput is presented in this paper. Specifically, it is proposed to divide each MAC burst in k sub-bursts, and to encode them via a (n, k) erasure correcting code. The n encoded sub-bursts are transmitted over the MAC channel, according to specific time/frequency-hopping patterns. Whenever n − e ≥ k sub-bursts (of the same burst) are received without collisions, erasure decoding allows recovering the remaining e sub-bursts (which were lost due to collisions). An interference cancellation process can then take place, removing in e slots the interference caused by the e recovered sub-bursts, possibly allowing the correct decoding of sub-bursts related to other bursts. The process is thus iterated as for the CRDSA case
Quasi-cyclic Generalized LDPC codes with low error floors
No full textIn this paper, a novel methodology for designing structured generalized LDPC (G-LDPC) codes is presented. The proposed design results in quasi-cyclic G-LDPC codes for which efficient encoding is feasible through shift-register-based circuits. The structure imposed on the bipartite graphs, together with the choice of simple component codes, leads to a class of codes suitable for fast iterative decoding. A pragmatic approach to the construction of G-LDPC codes is proposed. The approach is based on the substitution of check nodes in the protograph of a low-density parity-check code with stronger nodes based, for instance, on Hamming codes. Such a design approach, which we call LDPC code doping, leads to low-rate quasi-cyclic G-LDPC codes with excellent performance in both the error floor and waterfall regions on the additive white Gaussian noise channel
A Decoding Algorithm for LDPC Codes Over Erasure Channels with Sporadic Errors
No full textAn efficient decoding algorithm for low-density parity-check (LDPC) codes on erasure channels with sporadic errors (i.e., binary error-and-erasure channels with error probability much smaller than the erasure probability) is proposed and its performance analyzed. A general single-error multiple-erasure (SEME) decoding algorithm is first described, which may be in principle used with any binary linear block code. The algorithm is optimum whenever the non-erased part of the received word is affected by at most one error, and is capable of performing error detection of multiple errors. An upper bound on the average block error probability under SEME decoding is derived for the linear random code ensemble. The bound is tight and easy to implement. The algorithm is then adapted to LDPC codes, resulting in a simple modification to a previously proposed efficient maximum likelihood LDPC erasure decoder which exploits the parity-check matrix sparseness. Numerical results reveal that LDPC codes under efficient SEME decoding can closely approach the average performance of random codes
Short Low-Rate Non-Binary Turbo Codes
No full textA serial concatenation of an outer non-binary turbo
code with different inner binary codes is introduced and analyzed.
The turbo code is based on memory-1 time-variant
recursive convolutional codes over high order fields. The resulting
codes possess low rates and capacity-approaching performance,
thus representing an appealing solution for spread spectrum
communications. The performance of the scheme is investigated
on the additive white Gaussian noise channel with coherent and
noncoherent detection via density evolution analysis. The proposed
codes compare favorably w.r.t. other low rate constructions
in terms of complexity/performance trade-off. Low error floors
and performances close to the sphere packing bound are achieved
down to small block sizes (k = 192 information bits)
Viaggio di quasi tutta l'Europa : colle viste del commercio, dell'istruzione e della salute
No full textTurbo Codes Based on Time-Variant Memory-1 Convolutional Codes over Fq
No full textTwo classes of turbo codes over high-order finite fields are introduced. The codes are derived from a particular protograph sub-ensemble of the (dv=2,dc=3) low-density parity-check code ensemble. A first construction is derived as a parallel concatenation of two non-binary, time-variant accumulators. The second construction is based on the serial concatenation of a non-binary, time-variant differentiator and of a non-binary, time-variant accumulator, and provides a highly-structured flexible encoding scheme for (dv=2,dc=4) ensemble codes. A cycle graph representation is provided. The proposed codes can be decoded efficiently either as low-density parity-check codes (via belief propagation decoding over the codes bipartite graph) or as turbo codes (via the forward-backward algorithm applied to the component codes trellis). The forward-backward algorithm for symbol maximum a posteriori decoding of the component codes is developed and simplified by means of the fast Fourier transform. The proposed codes provide remarkable gains (~1 dB) over binary low-density parity-check and turbo codes in the moderate-short block regimes
From Product Codes to Structured Generalized LDPC Codes
No full textProduct codes, due to their relatively large minimum distance, are often seen as a natural solution for applications requiring low error floors. In this paper, we show by means of an ensemble weight enumerator analysis that the minimum distance multiplicities of product codes are much higher than those obtainable by other generalized LDPC (GLDPC) constructions employing the same component codes. We then propose a simple construction of quasi-cyclic GLDPC codes which leads to significantly lower error floors while leaving the decoder architecture of product codes almost untouched
Protograph LDPC Codes Design Based on EXIT Analysis
No full textIn this paper, a novel extrinsic information transfer
(EXIT) analysis is presented for protograph-based and multiedge
type low-density parity-check (LDPC) codes. A protograph
defines a subset of an LDPCC ensemble (identified by the
degree distributions of the bipartite graph), introducing further
constraints about the edge connections. For many codes belonging
to this class, the conventional approach based on EXIT charts
cannot be applied. The proposed EXIT analysis takes into
account edge connections, permitting the decoding convergence
evaluation for protograph-based LDPC codes, allowing the design
of highly-structured capacity approaching LDPC codes
On Optimum Decoding of Certain Product Codes
No full textOptimum decoding of a class of product codes is investigated. The class is the one given by the serial concatenation of a binary single-parity-check code with a low-dimension binary linear block code. It was proved by Wolf that maximum likelihood decoding for this class of product codes can be efficiently performed through the Viterbi algorithm over a compact trellis representation of the code. In this letter, it is showed that the decoding complexity can be further reduced by formulating the decoding problem as a symbol-wise maximum-a-posteriori decision problem. Results illustrated for suitably designed codes show that the proposed algorithm significantly outperforms conventional iterative decoders. Finally, a generalization of the code construction, enjoying the same low-complexity decoding principle is presented and analyzed, achieving tangible coding gains at moderate error rates
Bounds on the Error Probability of Block Codes over the q-Ary Erasure Channel
No full textIn this paper, tight bounds on the block error probability of linear block codes over order-q finite fields for the q-ary erasure channel, under maximum-likelihood (ML) decoding, are developed. Upper bounds are obtained for uniform parity-check ensembles, sparse parity-check ensembles, general parity-check ensembles (e.g., Gallager regular nonbinary low-density parity-check ensembles), and for any given linear code with known distance spectrum. The tightness of the upper bounds is confirmed both by the comparison with simple lower bounds and, for Gallager low-density parity-check ensembles, by extensive Monte Carlo simulations. Exploiting the derived bounds, it is shown how already for short blocks and small q>2 sparse ensembles attain block error probabilities close to those of idealized maximum distance separable (MDS) codes, down to low error probabilities, whereas in the same regime binary codes show visible losses with respect to the Singleton bound. Thanks to the accurate performance estimates, the developed bounds can support the design of near-optimum erasure correcting codes with short and moderate lengths
- …
