An important problem in secret sharing schemes is minimizing the share size. For (k, n)-threshold schemes and (k, L, n)-ramp schemes, constructions that minimize the share size are known. This paper presents optimal constructions for a more general class of access structures in which subsets with the same cardinality have the same amount of information about the secret. We refer to schemes with such uniform access structures as uniform secret sharing. We first derive a tight lower bound for share entropy and then present an optimal construction. Our lower bound exceeds that previously reported. The optimal construction encodes the secret value using one or more ramp schemes.

Non-binary multi-edge type ensembles of low-density parity-check codes are analyzed in terms of non-binary codeword weight distribution and its growth rate. In particular, an exact expression of the growth rate for small weights is developed. As a side result, the stopping set distributions of these ensembles are developed. Examples of weight distributions are provided, showing that the derived closed-form expressions can be easily evaluated. The obtained results can thus be exploited to analyze and design non-binary low-density parity-check codes that fall within the multi-edge type framework such as, but not limited to, protograph-based codes.

The non-binary codeword weight distribution and its growth rate are developed for non-binary multi-edge type ensembles of low-density parity-check codes. Moreover, an analysis of the growth rate for small weights is provided. The derived expressions can serve as powerful and flexible tools to analyze and design the non-binary low-density parity-check codes that fall within the multi-edge type framework.

This paper analyzes the asymptotic exponent of the weight spectrum for irregular doubly-generalized LDPC (D-GLDPC) codes. In the process, an efficient numerical technique for its evaluation is presented, involving the solution of a 4 × 4 system of polynomial equations. The expression is consistent with previous results, including the case where the normalized weight or stopping set size tends to zero. The spectral shape is shown to admit a particularly simple form in the special case where all variable nodes are repetition codes of the same degree, a case which includes Tanner codes; for this case it is also shown how certain symmetry properties of the local weight distribution at the CNs induce a symmetry in the overall weight spectral shape function. Finally, using these new results, weight and stopping set size spectral shapes are evaluated for some example generalized and doubly-generalized LDPC code ensembles.

In this paper, a low-density parity-check (LDPC) coded recording system is investigated, for which the run-length-limited (RLL) constraint is satisfied by deliberate flipping at the write side and by estimating the flipped bits at the read side. Two approaches are proposed for enhancing the error performance of such a system. The first approach is to alleviate the negative effect of incorrect estimation of the flipped bits by adjusting the soft information. The second approach is to increase the likelihood of the correct detection of flipped bits by designing a flipped-bit detection algorithm that utilizes both the RLL constraint and the parity-check constraint of the LDPC code. These two approaches can be combined to obtain significant improvement in performance over previously proposed methods.

We introduce in this paper the concept of a correctable error set and a fixed initialization decoding, by noticing that the sum-product decoder with a given iteration number only depends on the initialized probability of error, for a BSC. Although this value has been conventionally selected as the BSC crossover probability, we show that other selections can provide better performance or faster convergence. We also prove that for any fixed initialization (i.e., any given correctable error set), the word-error-rate can be represented as a polynomial of the BSC crossover probability. This suggests that the word-error-rate can be analytically derived from the knowledge of the correctable error set.

Using the EXIT chart approach, a necessary and sufficient condition is developed for the local stability of iterative decoding of multi-edge type (MET) doubly-generalized low-density parity-check (D-GLDPC) code ensembles. In such code ensembles, the use of arbitrary linear block codes as component codes is combined with the further design of local Tanner graph connectivity through the use of multiple edge types. The stability condition for these code ensembles is shown to be succinctly described in terms of the value of the spectral radius of an appropriately defined polynomial matrix.

A deterministic method to design degree distributions for low-density parity-check codes over the binary erasure channel is proposed. This method consists of matching the first and high-order derivatives of the extrinsic information transfer (EXIT) function of the variable node set to the corresponding derivatives of the inverse EXIT function of the check node set, in order to reduce the gap between the two curves in the EXIT chart. A sufficient condition for a check-concentrated distribution to achieve derivative matching up to some order is first obtained, and then a deterministic design algorithm, enabled by the Fourier-Budan theorem, is developed exploiting this sufficient condition. A comparison with other deterministic design techniques is also provided, revealing the potential of the proposed algorithm.

In this paper, the asymptotic growth rate of the weight distribution of irregular doubly generalized LDPC (D-GLDPC) codes is derived. The analysis yields a compact expression which accurately approximates the growth rate function for the case of small linear-weight codewords. This paper generalizes existing results for LDPC and generalized LDPC (GLDPC) codes. Ensembles with smallest check or variable node minimum distance greater than 2 are shown to have good growth-rate behavior, while for other ensembles a fundamental parameter is identified which discriminates between an asymptotically small and an asymptotically large expected number of small linear-weight codewords. Also, in the latter case it is shown that the growth rate depends only on the check and variable nodes with minimum distance 2. An important connection between this new result and the stability condition of D-GLDPC codes over the BEC is highlighted. Such a connection, previously observed for LDPC and GLDPC codes, is now extended to the case of D-GLDPC codes. Finally, it is shown that the analysis may be extended to include the growth rate of the stopping set size distribution of irregular D-GLDPC codes.

Ensemble design of low-density parity-check (LDPC) codes and their generalizations is usually performed via numerical optimization techniques, such as differential evolution, in which a threshold analysis tool is always necessary. Threshold analysis of unstructured doubly-generalized LDPC (D-GLDPC) code ensembles over the binary erasure channel (BEC) can be performed via extrinsic information transfer (EXIT) chart, exploiting the information functions and split information functions of the check and variable component codes, respectively. In this paper, multi-type information functions of linear block codes are introduced as an extension of the concept of information functions, when the bit positions are assumed to be associated with different types. It is shown how multi-type information functions (together with their split counterparts) can be exploited within an EXIT analysis approach to perform threshold analysis over the BEC of multi-edge type D-GLDPC code ensembles. The proposed technique for threshold analysis captures D-GLDPC codes based on protographs as a special case.

This paper analyzes the asymptotic exponent of both the weight spectrum and the stopping set size spectrum for a class of generalized low-density parity-check (GLDPC) codes. Specifically, all variable nodes (VNs) are assumed to have the same degree (regular VN set), while the check node (CN) set is assumed to be composed of a mixture of different linear block codes (hybrid CN set). A simple expression for the exponent (which is also referred to as the growth rate or the spectral shape) is developed. This expression is consistent with previous results, including the case where the normalized weight or stopping set size tends to zero. Furthermore, it is shown how certain symmetry properties of the local weight distribution at the CNs induce a symmetry in the overall weight spectral shape function.

In this paper, we introduce the concept of correctable error set for the BSC, which allows to generalize sum-product decoding for this channel. As a result, better error performance or faster convergence can be achieved. Furthermore, the correctable error set allows to evaluate the error performance of generalized sum-product decoding with a given iteration number for the BSC.

We introduce two permutation decoder designs for the binary images of double-parity [n, n - 2, 3] Reed-Solomon (RS) codes over binary extension fields F2m. The codes considered are limited to have zeros {1, α}, where α is any primitive element in F2m. We show that there exists a large set of m binary symbol errors that may be corrected via permutation decoding. The permutation decoders are shown to achieve near maximum-likelihood decoder performance, while only utilizing simple ideas borrowed from well-known reliability-based decoding algorithms.

For the memoryless AWGN channel, there exists low complexity methods to test the optimality of any chosen candidate codeword (i.e., whether the codeword in question equals the most-likely codeword or not). Such optimality tests find application in practical decoders that perform heuristic searches for the most-likely codeword. If some located codeword passes the optimality test, then the search may be terminated and computations saved. In this paper, we generalize techniques for determining if a codeword is optimal, for intersymbol interference (ISI) channels.

In this paper, we present a generalization of the ordered statistics decoding (OSD) techniques for the class of intersymbol interference (ISI) channels, and show decoding results for the extended Bose-Chaudhuri-Hocquenghem (eBCH) [128, 64, 22] code and the [255, 239, 17] Reed-Solomon (RS) binary image, over the PR2 partial response channel. Using the generalized OSD technique, we go on to generalize the Box-and- Match Algorithm (BMA) to the class of ISI channels. The BMA is an enhancement of OSD, and prior work has shown it to provide significant performance gain over OSD for memoryless additive white Gaussian noise (AWGN) channels. We present decoding results of the BMA for ISI channels, for the same eBCH and RS (binary image) codes, and PR2 channel. Our results show that the BMA (generalized for ISI channels) is superior to the OSD in terms of its performance/complexity trade-off. More specifically, the BMA may be tuned such that both algorithms have similar complexity, whereby the BMA still outperforms the OSD by a significant margin.

For binary linear block codes, this letter deals with a class of decoding algorithms which utilize bounded-distance and encoding-based decodings with input sequences that are calculated from a received sequence and given test patterns. We propose a new method for selecting the test patterns by simulation. The effectiveness of the decoding algorithm whose test patterns are selected by the proposed method is also shown by simulation.

In this paper, we propose a new implementation of the Extended Min-Sum (EMS) decoder for non-binary LDPC codes. A particularity of the new algorithm is that it takes into accounts the memory problem of the non-binary LDPC decoders, together with a significant complexity reduction per decoding iteration. The key feature of our decoder is to truncate the vector messages of the decoder to a limited number nmof values in order to reduce the memory requirements. Using the truncated messages, we propose an efficient implementation of the EMS decoder which reduces the order of complexity to ¿(nmlog2nm). This complexity starts to be reasonable enough to compete with binary decoders. The performance of the low complexity algorithm with proper compensation is quite good with respect to the important complexity reduction, which is shown both with a simulated density evolution approach and actual simulations.

We consider primitive Reed-Solomon (RS) codes over the field F2mof length n=2m-1. Building on Lacan 's results for the case of binary extension fields, we show that the binary images of certain two-parity symbol RS [n, n-2, 3] code, have a code automorphism subgroup related to the general linear group GL(m, 2). For these codes, we obtain a code automorphism subgroup of order m! GL(m,2). An explicit algorithm is given to compute a code automorphism (if it exists), that sends a particular choice of m binary positions, into binary positions that correspond to a single symbol of the RS code. If one such automorphism exists for a particular choice of m binary symbol positions, we show that there are at least m! of them. Computationally efficient permutation decoders are designed for the two-parity symbol RS [n, n-2, 3] codes. Simulation results are shown for the additive white Gaussian noise (AWGN) channel. For the finite fields F23and F24, we go on to derive subgroups of code automorphisms, belonging to binary images of certain RS codes that have three-parity symbols. A table of code automorphism subgroup orders, computed using the Groups, Algorithms, and Programming (GAP) software, is tabulated for the fields F23, F24, and F25.

In this paper, a method for the asymptotic analysis of generalized low-density parity-check (GLDPC) codes and doubly generalized low-density parity-check (D-GLDPC) codes over the binary erasure channel (BEC), based on extrinsic information transfer (EXIT) chart, is described. This method overcomes the problem consisting of the impossibility to evaluate the EXIT function for the check or variable component codes, in situations where the information functions or split information functions for component codes are unknown. According to the proposed technique, GLDPC codes and D-GLDPC codes where the generalized check and variable component codes arerandomcodes with minimum distance at least 2, are considered. A technique is then developed which finds the EXIT chart for the overall GLDPC or D-GLDPC code, by evaluating the expected EXIT function for each check and variable component code. This technique is finally combined with the differential evolution algorithm in order to generate some good GLDPC and D-GLDPC edge distributions. Numerical results of long, random codes, are presented which confirm the effectiveness of the proposed approach. They also reveal that D-GLDPC codes can outperform standard LDPC codes and GLDPC codes in terms of both waterfall performance and error floor.

This paper builds on Mittelholzer and Lahtonen's study of group codes for the Gaussian channel based on reflection groups. A careful analysis of the action of a reflection group on its roots leads to the development of improved methods for encoding and decoding. The new algorithm is proved to achieve maximum likelihood decoding. The complexity of decoding is analyzed, and it is shown that a proper choice of the sequence of subgroups used in the algorithm can yield significant gains in the efficiency of decoding.

An error-burst correcting algorithm is developed based on a circulant parity-check matrix of a cyclic code. The proposed algorithm is more efficient than error trapping if the code rate is less than about 2/3. It is shown that for any (n, k) cyclic code, there is an n × n circulant parity-check matrix such that the algorithm, applied to this matrix, corrects error bursts of lengths up to the error-burst correction limit of the cyclic code. This same matrix can be used to efficiently correct erasure bursts of lengths up to n - k. The error-burst correction capabilities of a class of cyclic low-density parity-check (LDPC) codes constructed from finite geometries are also considered.

The growth rate of the weight distribution of irregular doubly-generalized LDPC (D-GLDPC) codes is developed and in the process, a new efficient numerical technique for its evaluation is presented. The solution involves simultaneous solution of a 4 × 4 system of polynomial equations. This represents the first efficient numerical technique for exact evaluation of the growth rate, even for LDPC codes. The technique is applied to two example D-GLDPC code ensembles.

In this paper, we investigate the asymptotic ensemble weight enumerators of multi-edge type codes whose component codes are arbitrary block codes. Two forms of asymptotic growth rate of codewords, corresponding to the primal and dual problems, are obtained. Furthermore, for the codewords of small linear-sized weights, we develop a simplification method to restrict the search space of the primal problem and study the optimality conditions of the dual problem, giving a first-order approximation of the growth rate and a condition of exponentially few small weight codewords.

A class of doubly-generalized low-density parity-check (D-GLDPC) codes, where single parity-check (SPC) codes are used as variable nodes (VNs), is investigated. An expression for the growth rate of the weight distribution of any D-GLDPC ensemble with a uniform check node (CN) set is presented at first, together with an analytical technique for its efficient evaluation. These tools are then used for detailed analysis of a case study, namely, a rate-1/2 D-GLDPC ensemble where all the CNs are (7, 4) Hamming codes and all the VNs are length-7 SPC codes. It is illustrated how the VN representations can heavily affect the code properties and how different VN representations can be combined within the same graph to enhance some of the code parameters. The analysis is conducted over the binary erasure channel. Interesting features of the new codes include the capability of achieving a good compromise between waterfall and error floor performance while preserving graphical regularity, and values of threshold outperforming LDPC counterparts.

In this paper, a method to perform parallel decoding of the errors within a burst is presented for cyclic codes. It is shown that O(L) operations per position are sufficient to estimate each error of a burst of length L in parallel.

For LDPC-like codes such as LDPC, GLDPC, and DGLDPC codes, it is well known that the error floor can be caused by the codewords of small weights or stopping sets of small sizes. In this paper, we investigate the computation of asymptotic weight enumerators such that it becomes a convenient tool to determine a good distribution of code ensembles. In addition, by analyzing the first order approximation, we derive a condition to obtain a negative asymptotic growth rate of the codewords of small linear-sized weights, which is an important constraint for distribution optimization. Also the weight enumerators of turbo and repeat-accumulate codes are investigated. Furthermore, we extend our results to nonbinary DGLDPC codes. Generalization to N-layer and convolutional code based LDPC-like codes are also developed.

In this paper, the design of doubly generalized low-density parity-check (DGLDPC) codes is proposed. This approach generalizes the structure of LDPC codes at both check and variable nodes. The performance of DGLDPC codes over the AWGN channel is analyzed using EXIT charts. Combined with differential evolution optimization, this analysis provides thresholds for DGLDPC codes that are better than that of LDPC and GLDPC codes with the same maximum variable degree. These theoretical thresholds are verified via simulations. Furthermore DGLDPC codes exhibit a lower error floor compared with their LDPC and GLDPC counterparts.

While preparing [H. Hagiwara et al., 2006], we realized that the proof of [M. Fossorier, 2004, Theorem 2.3] was leading to confusion as written. More precisely, only e1= o2directly follows from o1+ e1and o2+ e2= e. The other equality o1= e2follows from e1= e2and the fact that the sum of the (distinct) Delta's between the two rows considered has to be zero. Actually, a much concise proof can be obtained by directly observing that for J = p = 2m, {Delta1,2(I) mod p, 0I=0L-1Delta1,2(I) = m mod p ne 0. Since Ruwei Chen recently pointed out this issue, we decided to clarify this point.

The iterative decoding threshold of low-density parity-check (LDPC) codes over the binary erasure channel (BEC) fulfills an upper bound depending only on the variable and check nodes with minimum distance 2. This bound is a consequence of the stability condition, and is here referred to as stability bound. In this paper, a stability bound over the BEC is developed for doubly-generalized LDPC codes, where variable and check nodes can be generic linear block codes, assuming maximumaposteriorierasure correction at each node. It is proved that also in this generalized context the bound depends only on the variable and check component codes with minimum distance 2. A condition is also developed, namely, the derivative matching condition, under which the bound is achieved with equality. The stability bound leads to consider single parity-check codes used as variable nodes as an appealing option to overcome common problems created by generalized check nodes.

In this paper, the impulse method to determine the low weight profile of sparse codes is improved based on efficient probabilistic approaches for reliability based decoding that are adapted to this problem. As a result, compared with previous approaches, the same low weight profile can be obtained with a significant time reduction (for example from 30 hours to a few minutes) or more complete low weight profiles can be determined in the same amount of time.

In this paper, a new proof of the work by Lacan et. al is obtained. This approach led to newly discovered connections between the automorphism group of the Reed Solomon (RS) binary image, and elementary group theory. This new development facilitated proving the existence and constructing permutations that have not been previously reported in the literature. Simple special cases are then considered in this work.

In this paper, we propose and study a new family of error-correcting codes. These achieve excellent error performance under an iterative decoding over the binary-input noisy channel and solves the memory space requirements problem of the non-binary LDPC decoders. We named this class of codes, Split non-binary LDPC codes. The main particularity of this new family of codes is that the variable and the check nodes are not defined over the same finite field GF(2p), like in the case of classical non-binary LDPC codes. The class of Split non-binary LDPC codes is obviously larger than that of existing types of codes, which gives more degrees of freedom to find good codes when the existing codes show their limits. We provide two examples of interesting split NB-LDPC codes.

Protograph-based doubly generalized LDPC (DGLDPC) codes are explored in this paper. We extend (and in the process simplify) the technique for computing the ensemble weight enumerators of protograph-based LDPC and GLDPC codes to DGLDPC codes. We find that with careful design, protograph-based DGLDPC codes can have a better asymptotic growth rate of minimum distance than that of the protograph-based LDPC and GLDPC codes. Simulation results confirm that protograph-based DGLDPC codes have a low error floor.

In this paper, the idea of diversification is applied to box-and-match technique and a multi-basis-multi-box decoding algorithm is developed for soft-decision decoding of binary linear block codes. New preprocessing techniques are also employed to improve computational efficiency. These new techniques allow to achieve near maximum likelihood decoding of the (256,131) extended BCH code, which has not been reported so far.

A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC.

In this paper, a method to design regular (2, dc)- LDPC codes over GF(q) with both good waterfall and error floor properties is presented, based on the algebraic properties of their binary image. First, the algebraic properties of rows of the parity check matrix H associated with a code are characterized and optimized to improve the waterfall. Then the algebraic properties of cycles and stopping sets associated with the underlying Tanner graph are studied and linked to the global binary minimum distance of the code. Finally, simulations are presented to illustrate the excellent performance of the designed codes.

A new identity for the weight enumerator of a code is derived. The new identity is shown to be related to the average value of the probability of an undetected error when is a continuous random variable.

In this paper, we propose a new implementation of the EMS decoder for non binary LDPC codes presented in (D. Declencq and M. Fossorier, 2007). A particularity of the new algorithm is that it takes into accounts the memory problem of the non binary LDPC decoders, together with a significant complexity reduction per decoding iteration. The key feature of our decoder is to truncate the vector messages of the decoder to a limited number nm of values in order to reduce the memory requirements. Using the truncated messages, we propose an efficient implementation of the EMS decoder which reduces the order of complexity to O(nmlog2nm), which starts to be reasonable enough to compete with binary decoders. The performance of the low complexity algorithm with proper compensation are quite good with respect to the important complexity reduction, which is shown both with a simulated density evolution approach and actual FER simulations.

In this paper, the gains achievable by proper decimation (or puncturing) of the received sample for fast correlation attack are investigated. In particular, the instances in which such an approach is interesting are clearly identified.

In this paper, we investigate the use of most reliable basis (MRB) based decoding algorithms for the Markov modulated Gaussian noise (MMGN) channel, with an interleaver used at the transmitter. The decoder first finds a most reliable column basis (MRCB), which is a common reliable basis for each row of the interleaver (each row of the interleaver is a codeword). Based on this common reliable basis, each row is decoded with a MRB based decoding algorithm. This new decoding method is denoted as joint column decoding (JCD). Simulation results show that this new method can achieve better performance than the straightforward MRB based decoding, where each codeword is decoded independently with a smaller complexity. An upper bound of the decoding error performance of JCD is derived based on the theory of order statistics and Markov chain.

In this paper, the stability condition for low-density parity-check (LDPC) codes on the binary erasure channel (BEC) is extended to generalized LDPC (GLDPC) codes and doubly-generalized LDPC (D-GLDPC) codes. It is proved that, in both cases, the stability condition only involves the component codes with minimum distance 2. The stability condition for GLDPC codes is always expressed as an upper bound to the decoding threshold. This is not possible for D-GLDPC codes, unless all the generalized variable nodes have minimum distance at least 3. Furthermore, a condition called derivative matching is defined in the paper. This condition is sufficient for a GLDPC or D- GLDPC code to achieve the stability condition with equality. If this condition is satisfied, the threshold of D-GLDPC codes (whose generalized variable nodes have all minimum distance at least 3) and GLDPC codes can be expressed in closed form.

In this letter, we address the problem of decoding nonbinary low-density parity-check (LDPC) codes over finite fields GF(q), with reasonable complexity and good performance. In the first part of the letter, we recall the original belief propagation (BP) decoding algorithm and its Fourier domain implementation. We show that the use of tensor notations for the messages is very convenient for the algorithm description and understanding. In the second part of the letter, we introduce a simplified decoder which is inspired by the min-sum decoder for binary LDPC codes. We called this decoder extended min-sum (EMS). We show that it is possible to greatly reduce the computational complexity of the check-node processing by computing approximate reliability measures with a limited number of values in a message. By choosing appropriate correction factors or offsets, we show that the EMS decoder performance is quite good, and in some cases better than the regular BP decoder. The optimal values of the factor and offset correction are obtained asymptotically with simulated density evolution. Our simulations on ultra-sparse codes over very-high-order fields show that nonbinary LDPC codes are promising for applications which require low frame-error rates for small or moderate codeword lengths. The EMS decoder is a good candidate for practical hardware implementations of such codes

We investigate the performance of iterative decoding algorithms for multistep majority logic decodable (MSMLD) codes of intermediate length. We introduce a new bit-flipping algorithm that is able to decode these codes nearly as well as a maximum-likelihood decoder on the binary-symmetric channel. We show that MSMLD codes decoded using bit-flipping algorithms can outperform comparable Bose-Chaudhuri-Hocquenghem (BCH) codes decoded using standard algebraic decoding algorithms, at least for high bit-flip rates (or low and moderate signal-to-noise ratios (SNRs)).

We propose an augmented belief propagation (BP) decoder for low-density parity check (LDPC) codes which can be utilized on memoryless or intersymbol interference channels. The proposed method is a heuristic algorithm that eliminates a large number of pseudocodewords that can cause nonconvergence in the BP decoder. The augmented decoder is a multistage iterative decoder, where, at each stage, the original channel messages on select symbol nodes are replaced by saturated messages. The key element of the proposed method is the symbol selection process, which is based on the appropriately defined subgraphs of the code graph and/or the reliability of the information received from the channel. We demonstrate by examples that this decoder can be implemented to achieve substantial gains (compared to the standard locally-operating BP decoder) for short LDPC codes decoded on both memoryless and intersymbol interference Gaussian channels. Using the Margulis code example, we also show that the augmented decoder reduces the error floors. Finally, we discuss types of BP decoding errors and relate them to the augmented BP decoder.

In this correspondence, we propose an approach to construct irregular low-density parity-check (LDPC) codes based on quasi-cyclic extension. When decoded iteratively, the constructed irregular LDPC codes exhibit a relatively low error floor in the high signal-to-noise ratio (SNR) region and are subject to relatively few undetected errors. The LDPC codes constructed based on the proposed scheme remain efficiently encodable

In this correspondence, iteration-1 of bit flipping decoding based on a set of nonorthogonal check sums is analyzed for both regular and irregular models. In particular, the tradeoff between the Hamming weight (and overlapping) of the check sums and the number of redundant check sums required to start converging under iterative decoding is investigated. The model is then applied to an iterative attack of McEliece public-key cryptosystem since a successful attack of this system can be achieved by algebraic bounded distance decoding of a random code. Based on this model, the attack can be decomposed into two phases: a preprocessing phase which, for one particular key kappa, consists of finding a sufficiently large set S of check sums up to a certain Hamming weight, and a bit flipping decoding phase which uses the set S for each message encrypted with the key kappa

In this paper, a general framework which enables to compare previously proposed block decoding approaches for the fast correlation attack is developed. All attacks are based on decoding using a set of parity check sums of an underlying linear code. The purpose of this paper is twofold:to provide a simple close form estimate about the number of check sums of a particular structure necessary for the corresponding attack to succeed;

In this correspondence, the optimality of variant-I permutation codes initially proposed by Slepian [see proc. IEEE, vol. 53, no. 3, p. 228-236, Mar. 1965] is shown in a simple way.

In this paper, a new reliability-based soft-decision decoding algorithm is presented. This algorithm repeatedly uses biased reliability values to construct the most-reliable-basis (MRB). As a result, this new method makes use of multiple information sets in a stochastic way. Compared to previously proposed competitive approaches, this new method produces a more efficient MRB reprocessing type algorithm to achieve near maximum-likelihood decoding (MLD) performance with a proper choice of the bias value. It can be combined with any MRB reprocessing type algorithm and in each case, a tight performance analysis can be derived

Replica shuffled versions of iterative decoders for low-density parity-check (LDPC) codes and turbo codes are presented. The proposed schemes can converge faster than standard and plain shuffled approaches. Two methods, density evolution and extrinsic information transfer (EXIT) charts, are used to analyze the performance of the proposed algorithms. Both theoretical analysis and simulations show that the new schedules offer good tradeoffs with respect to performance, complexity, latency, and connectivity

In this paper, an efficient method to improve the performance of the box and matching algorithm (BMA) is presented. By constructing a control band which is error free with high probability, we enhance the matching capability of the BMA. More precisely, the performance of BMA of order (i + 1) is nearly achieved with a linear increase in complexity and no increase in memory with respect to BMA of order i. Simulation results show that the performance of the enhanced BMA with a finite number of random biasing iterations for the decoding of the RS(255,239) code is about 0.1 dB away from that of maximum likelihood decoding (MLD) at the word error rate (WER) 10 3. A tight performance analysis is derived based on the theory of ordered statistics for this new approach.

This paper investigates cyclic codes for correcting bursts of errors from a new point of view. A simple iterative algorithm for correcting bursts of errors is developed. This algorithm is optimal in the sense that it corrects burst of errors of lengths up to the burst-error-correction limit of a cyclic code. Also included in the paper is an iterative process for correcting bursts of erasures.

The design of generalized low-density parity-check (GLDPC) codes at both check and bit nodes over AWGN channel is considered in this paper. The new codes are referred to as doubly generalized LDPC codes. EXIT charts are used to optimize the parameters of these codes. Closed forms of EXIT functions for some subcodes are presented. Both analysis and simulations show that this method can provide more flexibility in constructing codes with good threshold.

In this paper, it is shown that under very mild assumptions, practically any binary linear block code of length N and dimension K is able to correct any burst of length up to N - K with probability of success Pc= 1 for erasures, and any burst of length up to N - K - m with probability of success Pcges 1 - N2-mfor errors. In both cases, the decoding is based on identifying a string of zeroes in an extended syndrome corresponding to a particular representation of the parity check matrix of the code and its complexity is O(N2) binary operations

In this work, an efficient approach is introduced for reliability-based list decoding of a linear block code. This method terminates the decoding if a local optimal candidate satisfies a probabilistic sufficient condition. The average computation complexity is greatly reduced with this method. The false alarm probability associated with the use of the probabilistic sufficient condition is also derived. Simulation results confirm the analysis with no performance degradation and important computation savings on average for soft decision decoding of the (255,239) RS code (reduction by a factor between 2 and 20)

In this paper, we develop algebraic properties of regular (2, tr, N) non binary LDPC codes designed using their binary image. First, we characterize the algebraic properties of optimized rows of the parity check matrix H associated with a code, and then we study the algebraic properties of cycles and stopping sets associated with the underlaying Tanner graph

The design of generalized low-density parity-check (GLDPC) codes at both check and bit nodes over AWGN channel is considered in this paper. The new codes are referred to as doubly generalized LDPC codes. EXIT charts are used to optimize the parameters of these codes. Both analysis and simulations show that this method can provide more flexibility in constructing codes with good threshold

In this letter, a general orthogonal-modulation model to develop new modulations and to identify some widely used modulation schemes is proposed. Based on this general framework, an optimum scheme for non-Gaussian channels under a given set of constraints can be derived. In software radios, the modulation should be changed by tracking this optimum scheme. The proposed model is based on orthonormal vectors, which are obtained by multidimensional rotations. Several widely used modulation schemes are renamed by their consecutive multidimensional rotation angles within the proposed framework. New modulation examples in continuous-wave interference and impulse interference channels are given to illustrate the corresponding local optima.

We propose an augmented belief-propagation (BP) decoder for low-density parity-check (LDPC) codes which can be used on memoryless or intersymbol-interference (ISI) channels. The proposed method is a heuristic algorithm that eliminates a large number of pseudocodewords that can cause nonconvergence in the BP decoder. The augmented decoder is a multistage iterative decoder, where at each stage, the original channel messages on select symbol nodes are replaced by saturated messages. The key element of the proposed method is the symbol-selection process, which is based on the appropriately defined subgraphs of the code graph and/or the reliability of the information received from the channel. We demonstrate by examples that this decoder can be implemented to achieve substantial gains (compared with the standard locally operating BP decoder) for short LDPC codes decoded on both memoryless and ISI Gaussian channels. Using the Margulis code example, we also show that the augmented decoder reduces the error floors. Finally, we discuss types of BP decoding errors and relate them to the augmented BP decoder.

In this paper, the mean field (MF) and mixed mean field (MMF) algorithms for decoding low-density parity-check (LDPC) codes are considered. The MF principle is well established in statistical physics and artificial intelligence. Instead of using a single completely factorized approximated distribution as in the MF approach, the mixed MF algorithm forms a weighted average of several MF distributions as an approximation of the true posterior probability distribution. The MF decoding algorithm for linear block codes is derived and shown to be an approximation of the a posteriori probability (APP) decoding algorithm. The MF approach is then developed in the context of iterative decoding and presented as an approximation of the popular belief propagation decoding method. These results are extended to iterative decoding with the MMF algorithm. Simulation results show that the MF and MMF decoding algorithms yield a good performance-complexity tradeoff, especially when employed for decoding LDPC codes based on finite geometries.

A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes. The performance of the proposed scheme is investigated on a BEC and BSC for infinite and finite code lengths. The analysis shows that the performance of the scheme on a BEC is poor compared to that of LDPC codes. However, the performance on a BSC is competitive to that of LDPC codes. Furthermore, results of the finite length analysis on a BEC can be used under certain conditions as a tight lower bound on the performance of the scheme on a BSC.

Reduced latency versions of iterative decoders of low-density parity-check codes are analyzed in this paper. The proposed schemes converge faster than standard approaches. Two methods, density evolution and EXIT charts, are used to analyze the performance of the proposed algorithms. Both theoretical analysis and simulations show that the new schedules offer good performance versus complexity and latency trade-offs.

A two-dimensional post normalization scheme is proposed to improve the performance of conventional min-sum (MS) and normalized MS decoding of irregular low density parity check codes. An iterative procedure based on parallel differential optimization algorithm is presented to obtain the optimal two-dimensional normalization factors. Both density evolution analysis and specific code simulation show that the proposed method provides a comparable performance as belief propagation decoding while requiring less complexity. Interestingly, the new method exhibits a lower error floor than that of belief propagation decoding in the high SNR region. With respect to standard MS and one-dimensional normalized MS decodings, the two-dimensional normalized MS offers a considerably better performance.

In this paper, we develop a generalization of the minsum (MS) algorithm which not only performs additions without the need of channel estimation, but also with the two following objectives: (i) a complexity much lower than O(q2) so that finite fields of large order can be considered; and (ii) a small performance degradation compared with BP decoding. The first objective is achieved by introducing configuration sets, which allow to keep only a small number of meaningful values at the check node processing. The second objective is achieved by applying at the variable node processing the correction techniques of J. Chen and M. Fossorier, (2002) to the proposed algorithm

In this paper, a general framework which enables to compare previously proposed approaches for the fast correlation attacks is developed. All attacks are based on decoding using a set of parity check sums of an underlying linear code. The purpose of this paper is two-fold: (a) to provide a simple close form estimate about the number of check sums of a particular structure necessary for the corresponding attack to succeed; (b) to illustrate how such estimates are useful in minimizing the computational complexity of each attack considered, and consequently, in establishing a unified framework for comparison

Replica shuffled versions of iterative decoders of turbo codes, low-density parity-check codes and turbo product codes are presented. The proposed schemes converge faster than standard and previously proposed "shuffled" approaches. Simulations show that the new schedules offer good performance versus complexity/latency trade-offs.

Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.

Shuffled versions of iterative decoding of low-density parity-check codes and turbo codes are presented. The proposed schemes have about the same computational complexity as the standard versions, and converge faster. Simulations show that the new schedules offer better performance/complexity tradeoffs, especially when the maximum number of iterations has to remain small.

In this correspondence, a new method for improving hard-decision bit-flipping decoding of low-density parity-check (LDPC) codes is presented. Bits with a number of unsatisfied check sums larger than a predetermined threshold are flipped with a probability p /spl les/ 1 which is independent of the code considered. The probability p is incremented during decoding according to some rule. With a proper choice of the initial p, the proposed improved bit-flipping (BF) algorithm achieves gain not only in performance, but also in average decoding time for signal-to-noise ratio (SNR) values of interest with respect to p = 1.

Low-density parity-check (LDPC) codes in their broader-sense definition are linear codes whose parity-check matrices have fewer 1s than 0s. Finding their minimum distance is therefore in general an NP-hard problem. We propose a randomized algorithm called nearest nonzero codeword search (NNCS) approach to tackle this problem for iteratively decodable LDPC codes. The principle of the NNCS approach is to search codewords locally around the all-zero codeword perturbed by minimal noise, anticipating that the resultant nearest nonzero codewords will most likely contain the minimum-Hamming- weight codeword whose Hamming weight is equal to the minimum distance of the linear code. This approach has its roots in Berrou et al.'s error-impulse method and a form of Fossorier's list decoding for LDPC codes.

We propose a family of randomized approximate algorithms, called nearest nonzero codewords search (NNCS), for computing the minimum distance of low-density parity-check (LDPC) codes, including Gallager-type and finite-geometry-type codes.

This paper presents the study of transmit power adaption and capacity-approaching coding/decoding in multiple-input-multiple-output (MIMO) Rayleigh fading channels under the assumption that perfect channel state information (CSI) is known at both the transmitter and the receiver. We propose three different simple, but powerful, methods for transforming the MIMO fading channel into a set of additive white noise Gaussian (AWGN) channels. We show that the channel capacity can be closely approached by using only a small number of different codes designed for the Gaussian channel.

We propose an improved belief-propagation (BP) decoder for low-density parity-check (LDPC) codes based on channel information correction. We show that our algorithm achieves sizeable performance gains (in waterfall and error floor regions) compared to the standard BP decoder. We verify by examples that the proposed decoder almost achieves the maximum-likelihood decoding performance for short LDPC codes

The chase decoding algorithms are reliability-based algorithms achieving bounded-distance (BD) decoding for any binary linear code of Hamming distance d. The least complex version of the original chase algorithms ("Chase-3") uses O(d) trials of a conventional binary decoder. In this paper, we propose a class of Chase-like BD decoding algorithms of lower complexity than the original Chase-3 algorithm. In particular, the least complex member of this class requires only O(d/sup 2/3/) trials.

In this paper, we focus on the suboptimality of iterative decoding on graphs with cycles, through examining the use of a reliability-based decoding algorithm for some concatenated codes with an interleaver, known as turbo-like codes. The a posteriori probabilities delivered by the iterative decoding are regarded as reliability information, and an efficient algorithm for the overall linear block code is applied at certain iterations. Simulation results show that the suboptimality of iterative decoding due to cycles can be at least partially compensated by this approach. Some insights about the potential additional coding gains achievable are investigated based on the characteristics of the constituent decoders. These characteristics are related to the nature of suboptimality in the overall iterative decoding. The effects of some code parameters and channel conditions on the behavior of iterative decoding are also studied for a better understanding of its suboptimality.

This paper describes a new approach to list-based soft-input soft-output (SISO) decoding based on order-i reprocessing. Approximations to both the log-maximum a posteriori (MAP) and max-log-MAP algorithms are developed. Additional decoding steps are proposed to correct common types of errors remaining after iterative decoding. These steps can significantly improve performance at low bit-error rates in later iterations. The proposed algorithms offer a wide range of complexity versus performance tradeoffs, which are explored through Monte Carlo simulations of product code decodings. The algorithms improve performance over previous approaches.

The box and match decoding algorithm (BMA) significantly reduces the computational complexity of the ordered statistic decoding algorithm at the expense of increased memory requirements. A soft-input/soft-output version of the BMA is developed. Additional complexity-reduction techniques are also described.

In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than 12, and a relatively mild necessary and sufficient condition for the code to have a girth of 6, 8,10, or 12 is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered. To this end, a necessary condition for the codes investigated to reach their maximum possible minimum Hamming distance is proposed.

In this paper, we improve the ordered statistics decoding algorithm by using matching techniques. This allows us: to reduce the worst case complexity of decoding (the error performance being fixed) or to improve the error performance (for a same complexity); to reduce the ratio between average complexity and worst case complexity; to achieve practically optimal decoding of rate-1/2 codes of lengths up to 128 (rate-1/2 codes are a traditional benchmark, for coding rates different from 1/2, the decoding is easier); to achieve near-optimal decoding of a rate-1/2 code of length 192, which could never be performed before.

The main reference of this paper is the sphere-packing bound of 1967 (SP67) derived by Shannon, Gallager, and Berlekamp. It offers a lower bound on the decoding error probability over a very large variety of channels. If it has failed so far to provide any usable material in practical implementation of telecommunication systems, it is due to an original focus on asymptotic results (making it inapplicable for moderate code lengths) and to the difficulty of the involved methods (which makes the derivation of SP67 quite hermetic and uninspiring for further research). The purpose of this paper is two-fold: 1) to stir up some renewed interest in the topic on which Shannon concluded his career in information theory thanks to a qualitative (rather than technical) review of the derivation of SP67, introduced by a review of the simpler sphere-packing bound derived by Shannon in 1959; 2) to prove the practical interest of SP67 by extending its field of application to continuous output channels and particularly the additive white Gaussian noise (AWGN) channel used with any particular modulation scheme, and by improving its lower bound for the moderate code length case so that it becomes the best lower bound for most iteratively decodable codes (turbo codes, low-density parity-check (LDPC) codes, repeat-accumulate (RA) codes, etc.) of usual lengths.

A soft-decision decoder for an error-correcting block code of Hamming distance d is said to achieve bounded-distance (BD) decoding if its error-correction radius is equal to that of a complete Euclidean distance decoder. The Chase decoding algorithms are reliability-based algorithms achieving BD decoding. The least complex version of the original Chase algorithms ("Chase-3") uses O(d) trials of a conventional binary decoder. In this correspondence, we propose classes of Chase-like BD decoding algorithms of lower complexity than the original Chase-3 algorithm. In particular, the least complex members of these classes require only O(d/sup 2/3/) trials.

Soft output detection for signals transmitted on linear channels is investigated. A particular emphasis is made for signal detection on multiple antenna channels. The a posteriori information at the detector output is evaluated from a shifted spherical list of point candidates. The spherical list is centered on the maximum likelihood point, which has the great advantage of stabilizing the list size. Thus, the sphere radius is selected in order to control the list size and to cope with the boundaries of the finite multiple antenna constellation. Our new soft output sphere decoder is then applied to the computation of constrained channel capacity and to the iterative detection of a coded transmission. For example, we achieved a signal-to-noise ratio at 1.25 dB from capacity limit on a 4/spl times/4 MIMO channel with 16-QAM modulation and a 4-state rate 1/2 parallel turbo code.

Synchronization is an important feature in the design of high-speed Viterbi decoders for punctured convolutional codes. Since some punctured codes might show invariance (total or partial) to phase rotations or other transformations, it is difficult to determine their synchronization status using a simple method. Necessary and sufficient conditions for a code to be totally invariant to an affine class of symbol transformations have been derived by A. Mogre et al. (see ibid., vol.48, p.1066-9, 2000) in conjunction with invariance compensation techniques at the receiver. Detection of these invariances is usually achieved based on a synchronization pattern. We propose a method to replace this pattern by a cyclic redundancy check code, since such codes are already present in many communications systems. We also investigate the effects of partial invariances, which can occur in several ways. After deriving some sufficient conditions for a code to exhibit partial invariance, we show that for rate k/n convolutional codes with 2k>n, the types of partial invariances considered have negligible effect on the error performance and, therefore, can be ignored at the receiver.

The paper presents two efficient Viterbi decoding-based suboptimal algorithms for tailbiting codes. The first algorithm, the wrap-around Viterbi algorithm (WAVA), falls into the circular decoding category. It processes the tailbiting trellis iteratively, explores the initial state of the transmitted sequence through continuous Viterbi decoding, and improves the decoding decision with iterations. A sufficient condition for the decision to be optimal is derived. For long tailbiting codes, the WAVA gives essentially optimal performance with about one round of Viterbi trial. For short- and medium-length tailbiting codes, simulations show that the WAVA achieves closer-to-optimum performance with fewer decoding stages compared with the other suboptimal circular decoding algorithms. The second algorithm, the bidirectional Viterbi algorithm (BVA), employs two wrap-around Viterbi decoders to process the tailbiting trellis from both ends in opposite directions. The surviving paths from the two decoders are combined to form composite paths once the decoders meet in the middle of the trellis. The composite paths at each stage thereafter serve as candidates for decision update. The bidirectional process improves the error performance and shortens the decoding latency of unidirectional decoding with additional storage and computation requirements. Simulation results show that both proposed algorithms effectively achieve practically optimum performance for tailbiting codes of any length.

In this paper, we analyze the performance of two improved BP-based decoding algorithms for LDPC codes, namely the normalized BP-based and the offset BP-based algorithms, by means of density evolution. The numerical calculations show that with one properly chosen parameter for each of these two improved BP-based algorithms, performances very close to that of the BP algorithm can be achieved. Simulation results for LDPC codes with code length moderately long validate the proposed optimization. Finite quantization effects on the BP-based and the offset BP-based decoding algorithms are evaluated.

In this paper, the use of a reliability-based decoding algorithm for some concatenated codes with an interleaver, known as turbo-like codes, is examined to address and overcome the suboptimality of iterative decoding. Simulation results show that the suboptimality of iterative decoding for moderate length codes can be at least partially compensated by this combined approach. Some insights about the potential additional coding gains achievable by the combined approach are investigated based on the characteristics of the constituent decoders, which highlights the nature of suboptimality in iterative decoding.

The order statistic decoding (OSD) algorithm is a probabilistic list decoding algorithm which allows to achieve practically optimum soft decision decoding of binary linear block codes of length up to 128. Recently, matching techniques were applied to the OSD algorithm to reduce both the worst case and average complexities of decoding at the expense of memory. The corresponding box-and-match algorithm (BMA) allows to achieve near optimum decoding of codes of length up to 192. In this work, we investigate the application of iterative information set reduction to the BMA, which provides further refinements in the trade-offs between error performance and decoding complexity.

In this paper, we propose a belief-propagation (BP)-based decoding algorithm which utilizes normalization to improve the accuracy of the soft values delivered by a previously proposed simplified BP-based algorithm. The normalization factors can be obtained not only by simulation, but also, importantly, theoretically. This new BP-based algorithm is much simpler to implement than BP decoding as it requires only additions of the normalized received values and is universal, i.e., the decoding is independent of the channel characteristics. Some simulation results are given, which show this new decoding approach can achieve an error performance very close to that of BP on the additive white Gaussian noise channel, especially for low-density parity check (LDPC) codes whose check sums have large weights. The principle of normalization can also be used to improve the performance of the max-log-MAP algorithm in turbo decoding, and some coding gain can be achieved if the code length is long enough.

The reliability-based decoding approach using the reprocessing of the most reliable information set only is extended into the iterative reprocessing of several information sets. At the end of each information set reprocessing, some information bits are delivered by the decoder. Consequently, information sets with decreasing cardinality values are considered at each iteration. A tight upper bound on the error performance achieved by this new method is derived. Compared to previously proposed competitive approaches, this new method reduces the number of candidate codewords needed to achieve practically optimum decoding. Importantly, it also preserves the very simple structured implementation of the order statistic decoding.

The statistical approach proposed by Agrawal and Vardy (see ibid., vol.46, no.1, p.60-83, 2000) to evaluate the error performance of the generalized minimum distance (GMD) decoding is extended to other reliability-based decoding algorithms for binary linear block codes, namely Chase (1972) type, combined GMD and Chase type, and order statistic decoding (OSD). In all cases, tighter and simpler bounds than those previously proposed have been obtained with this approach.

We propose a normalized a posteriori probability (APP) based algorithm for the decoding of low-density parity check (LDPC) codes. The normalized APP-based algorithm utilizes normalization to improve the accuracy of the soft values delivered by the simplified APP-based algorithm from one iteration to another during the iterative decoding, and can achieve very good tradeoff between decoding complexity and performance.

Many decoding algorithms need to compute some lists of binary vectors that minimize a given weight function. Furthermore, it is often desirable that these vectors are generated by increasing weight. The considered weight function is usually decreasing in the a priori likelihood that the vector yields correct decoding. We present a new technique to generate candidates for error patterns from the most a priori likely to the least, that proves significantly more efficient than any other known method.

In this paper, reliability based decoding is combined with belief propagation (BP) decoding for low-density parity check (LDPC) codes. At each iteration, the soft output values delivered by the BP algorithm are used as reliability values to perform reduced complexity soft decision decoding of the code considered. This approach allows to bridge the error performance gap between belief propagation decoding which remains suboptimum, and maximum likelihood decoding which is too complex to be implemented for the codes considered. Trade-offs between decoding complexity and error performance are also investigated. In particular, a stopping criterion which reduces the average number of iterations at the expense of very little performance degradation is proposed for this combined decoding approach. Simulation results for several Gallager (1963, 1968) LDPC codes and different set cyclic codes of hundreds of information bits are given and elaborated.

We consider the progressive transmission of a lossy source across a power constrained Gaussian channel using binary phase-shift keying modulation. Under the theoretical assumptions of infinite bandwidth, arbitrarily complex channel coding, and lossless transmission, we derive the optimal channel code rate and the optimal energy allocation per transmitted bit. Under the practical assumptions of a low complexity class of algebraic channel codes and progressive image coding, we numerically optimize the choice of channel code rate and the energy per bit allocation. This model provides an additional degree of freedom with respect to previously proposed schemes, and can achieve a higher performance for sources such as images. It also allows one to control bandwidth expansion or reduction.

This paper presents a geometric approach to the construction of low-density parity-check (LDPC) codes. Four classes of LDPC codes are constructed based on the lines and points of Euclidean and projective geometries over finite fields. Codes of these four classes have good minimum distances and their Tanner (1981) graphs have girth 6. Finite-geometry LDPC codes can be decoded in various ways, ranging from low to high decoding complexity and from reasonably good to very good performance. They perform very well with iterative decoding. Furthermore, they can be put in either cyclic or quasi-cyclic form. Consequently, their encoding can be achieved in linear time and implemented with simple feedback shift registers. This advantage is not shared by other LDPC codes in general and is important in practice. Finite-geometry LDPC codes can be extended and shortened in various ways to obtain other good LDPC codes. Several techniques of extension and shortening are presented. Long extended finite-geometry LDPC codes have been constructed and they achieve a performance only a few tenths of a decibel away from the Shannon theoretical limit with iterative decoding.

Low density parity check (LDPC) codes with iterative decoding based on belief propagation (IDBP) achieve astonishing error performance close to the Shannon limit. Until now there has been no known method for constructing these Shannon limit approaching codes systematically. Good LDPC codes are largely generated by computer search. As a result, the encoding of long LDPC codes is in general very complex. This paper presents the first algebraic method for constructing LDPC codes systematically based on finite analytic geometries. Four classes of finite geometry LDPC codes with relatively good minimum distances are constructed. These codes are either cyclic or quasi-cyclic and therefore their encoding can be implemented with simple linear feedback shift registers. Long finite geometry LDPC codes have been constructed and they achieve an error performance only a few tenths of a dB away from the Shannon limit. Finite geometry LDPC codes are strong competitors to turbo codes for error control in communication and digital data storage systems.

In this letter, Chase decoding algorithms are generalized into a family of bounded distance decoding algorithms, so that the conventional Chase algorithm-2 and Chase algorithm-3 become the two extremes of this family. Consequently, more flexibility in the tradeoffs between error performance and decoding complexity is provided by this generalization, especially for codes with large minimum distance. Finally this approach is extended to decoding with erasures.

In this paper, multilevel coded asymmetric modulation with multistage decoding and unequal error protection (UEP) is discussed. These results further emphasize the fact that unconventional signal set partitionings are more promising than traditional (Ungerboeck-type) partitionings, to achieve UEP capabilities with multilevel coding and multistage decoding. Three types of unconventional partitionings are analyzed for asymmetric 8-PSK and 16-QAM constellations over the additive white Gaussian noise channel to introduce design guidelines. Generalizations to other PSK and QAM type constellations follow the same lines. Upper bounds on the bit-error probability based on union bound arguments are first derived. In some cases, these bounds become loose due to the large overlappings of decision regions associated with asymmetric constellations and unconventional partitionings. To overcome this problem, simpler and tighter approximated bounds are derived. Based on these bounds, it is shown that additional refinements can be achieved in the construction of multilevel UEP codes, by introducing asymmetries in PSK and QAM signal constellations.

The maximum a posterioriprobability (MAP) algorithm is a trellis-based MAP decoding algorithm. It is the heart of turbo (or iterative) decoding that achieves an error performance near the Shannon limit. Unfortunately, the implementation of this algorithm requires large computation and storage. Furthermore, its forward and backward recursions result in a long decoding delay. For practical applications, this decoding algorithm must be simplifled and its decoding complexity and delay must be reduced. In this paper, the MAP algorithm and its variation's, such as log-MAP and max-log-MAP algorithms, are first applied to sectionalized trellises for linear block codes and carried out as two-stage decodings. Using the structural properties of properly sectionalized trellises, the decoding complexity and delay of the MAP algorithms can be reduced. Computation-wise optimum sectionalizations of a trellis for MAP algorithms are investigated. Also presented in this paper are bidirectional and parallel MAP decodings.

Previously, the belief propagation (BP) algorithm has received a lot of attention in the coding community, mostly due to its near-optimum decoding for low-density parity check (LDPC) codes and its connection to turbo decoding. In this paper, we investigate the performance achieved by the BP algorithm for decoding one-step majority logic decodable (OSMLD) codes. The BP algorithm is expressed in terms of likelihood ratios rather than probabilities, as conventionally presented. The proposed algorithm fits better the decoding of OSMLD codes with respect to its numerical stability due to the fact that the weights of their check sums are often much higher than that of the corresponding LDPC codes. Although it has been believed that OSMLD codes are far inferior to LDPC codes, we show that for medium code lengths (say between 200-1000 bits), the BP decoding of OSMLD codes can significantly outperform BP decoding of their equivalent LDPC codes. The reasons for this behavior are elaborated.

In this paper, theoretical upper bounds and computer simulation results on the error performance of multilevel block coded modulations for unequal error protection (UEP) and multistage decoding are presented. It is shown that nonstandard signal set partitionings and multistage decoding provide excellent UEP capabilities beyond those achievable with conventional coded modulation. The coding scheme is designed in such a way that the most important information bits have a lower error rate than other information bits. The large effective error coefficients, normally associated with standard mapping by set partitioning, are reduced by considering nonstandard partitionings of the underlying signal set. The bits-to-signal mappings induced by these partitionings allow the use of soft-decision decoding of binary block codes. Moreover, parallel operation of some of the staged decoders is possible, to achieve high data rate transmission, so that there is no error propagation between these decoders. Hybrid partitionings are also considered that trade off increased intraset distances in the last partition levels with larger effective error coefficients in the middle partition levels. The error performance of specific examples of multilevel codes over 8-PSK and 64-QAM signal sets are simulated and compared with theoretical upper bounds on the error performance.

This paper investigates the principle of metric differences for trellis decoding of convolutional codes. Based on this differential method, a new algorithm, referred to as differential trellis decoding (DTD), is proposed. DTD offers an alternative to the conventional "add-compare-select" (ACS) method for implementing the Viterbi algorithm.

In this study, error performance analysis and simulation results are provided for the weighted erasure decoding (WED) of binary linear block codes on Q-ary output channel. In particular, the optimum channel quantizer for WED is derived and compared with WED designed based on the cutoff rate criterion, as traditionally proposed. Simulations are conducted for the (64, 42, 8) Reed-Muller (RM) code on 4-ary and 8-ary output channels. For Q=8 and the bit error rate (BER) 10/sup -4/, the WED with optimum quantizer has a 0.65 dB coding gain over the WED with cutoff rate quantizer and a 1.0 dB coding gain over algebraic decoding.

In general, a channel quantizer for a communication system subject to additive white Gaussian noise (AWGN) is designed based on the cutoff rate. This criterion is good if the scheme considered performs close to the theoretical performance corresponding to the cutoff rate, as for error control systems employing convolutional codes. However, it is no longer true for systems using low complexity suboptimum decoding algorithms for block codes. We illustrate this point and present three examples for which we compare the optimum quantizer and the quantizer based on the cutoff rate for Q=4 quantization levels.

Two simplified versions of the belief propagation algorithm for fast iterative decoding of low-density parity check codes on the additive white Gaussian noise channel are proposed. Both versions are implemented with real additions only, which greatly simplifies the decoding complexity of belief propagation in which products of probabilities have to be computed. Also, these two algorithms do not require any knowledge about the channel characteristics. Both algorithms yield a good performance-complexity trade-off and can be efficiently implemented in software as well as in hardware, with possibly quantized received values.

This paper presents two simple and effective criteria for stopping the iteration process in turbo decoding with a negligible degradation of the error performance. Both criteria are devised based on the cross-entropy (CE) concept. They are as efficient as the CE criterion, but require much less and simpler computations.

In this correspondence, the low-weight terms of the weight distribution of the block code obtained by terminating a convolutional code after x information blocks are expressed as a function of x. It is shown that this function is linear in x for codes with noncatastrophic encoders, but quadratic in x for codes with catastrophic encoders. These results are useful to explain the poor performance of convolutional codes with a catastrophic encoder at low-to-medium signal-to-noise ratios.

We study joint source-channel coding for a power constrained Gaussian channel and its application to progressive image compression. For a given power constrained, we consider the optimum allocation of energy per bit for a BPSK transmitter and the best choice of channel code rate, when the performance is measured by end-to-end average quantizer distortion. Choosing the average energy per transmitted bit in conjunction with both the source rate and the channel code rate provides an additional degree of freedom with respect to previously proposed schemes, and therefore can achieve higher overall PSNRs for images.

This paper presents a unified method for evaluating the error-correction radii of many reliability-based soft-decision decoding algorithms for binary linear block codes. Based on this unified method, these decoding algorithms as well as their potential improvements can be compared directly. The error-correction radius for each of these decoding algorithms is determined by finding the closest point on the boundary of the decision region of the soft-decision decoder to the transmitted signal sequence. It is shown that this problem can be formulated as a constrained optimization problem. Although no general closed-form expression is possible, a simple algorithm that always converges to the optimum solution of this optimization problem is presented. Based on these results, the error-correction radii of some well-known reliability-based soft-decision decoding algorithms are revisited and compared.

In this correspondence, the bit-error probability P/sub b/ for maximum-likelihood decoding of binary linear block codes is investigated. The contribution P/sub b/(j) of each information bit j to P/sub b/ is considered and an upper bound on P/sub b/(j) is derived. For randomly generated codes, it is shown that the conventional approximation at high SNR P/sub b//spl ap/(d/sub H//N).P/sub s/, where P/sub s/ represents the block error probability, holds for systematic encoding only. Also systematic encoding provides the minimum P/sub b/ when the inverse mapping corresponding to the generator matrix of the code is used to retrieve the information sequence. The bit-error performances corresponding to other generator matrix forms are also evaluated. Although derived for codes with a generator matrix randomly generated, these results are shown to provide good approximations for codes used in practice. Finally, for soft-decision decoding methods which require a generator matrix with a particular structure such as trellis decoding, multistage decoding, or algebraic-based soft-decision decoding, equivalent schemes that reduce the bit-error probability are discussed. Although the gains achieved at practical bit-error rates are only a fraction of a decibel, they remain meaningful as they are of the same orders as the error performance differences between optimum and suboptimum decodings. Most importantly, these gains are free as they are achieved with no or little additional circuitry which is transparent to the conventional implementation.

In this correspondence, various aspects of reliability-based syndrome decoding of binary codes are investigated. First, it is shown that the least reliable basis (LRB) and the most reliable basis (MRB) are dual of each other. By exploiting this duality, an algorithm performing maximum-likelihood (ML) soft-decision syndrome decoding based on the LRB is presented. Contrarily to previous LRB-based ML syndrome decoding algorithms, this algorithm is more conveniently implementable for codes whose codimension is not small. New sufficient conditions for optimality are derived. These conditions exploit both the ordering associated with the LRB and the structure of the code considered. With respect to MRR-based sufficient conditions, they present the advantage of requiring no soft information and thus can be preprocessed and stored. Based on these conditions, low-complexity soft-decision syndrome decoding algorithms for particular classes of codes are proposed. Finally, a simple algorithm is analyzed. After the construction of the LRB, this algorithm computes the syndrome of smallest Hamming weight among o(K/sup i/) candidates, where K is the dimension of the code, for an order i of reprocessing. At practical bit-error rates, for codes of length N/spl les/128, this algorithm always outperforms any algebraic decoding algorithm capable of correcting up to t+1 errors with an order of reprocessing of at most 2, where t is the error-correcting capability of the code considered.

The soft decision decoding algorithm based on the ordered statistics proposed by Fossorier and Lin (see IEEE Trans. Inform. Theory, vol.41, no.9, p.1379-96, 1995) is applied to the Rayleigh fading channel with coherent detection. For an (N, K) block code, it is shown that order-1 reprocessing, or equivalently considering K+1 codeword candidates, provides most of the coding gain over uncoded binary phase shift keying (BPSK). In addition to its contribution to coding for the Rayleigh fading channel, the article also provides a general framework for evaluating the error performance of an algorithm based on a total or partial ordering of a random variable (RV) depending on one or many other RVs and illustrates how the reprocessing method of Fossorier et al. relates to the reliability measures defining the ordering.

This letter generalizes the coset decoding of decomposable codes, offering further refinements in the tradeoffs among error performance, decoding complexity, and decoding speed.

In this correspondence, the exact weight distribution for closest coset decoding of |u|u+v| constructed codes is derived. The results allow more accurate evaluations of the decoding error probabilities.

This correspondence presents a hybrid reliability-based decoding algorithm which combines the reprocessing method based on the most reliable basis and a generalized Chase-type algebraic decoder based on the least reliable positions. It is shown that reprocessing with a simple additional algebraic decoding effort achieves significant coding gain. For long codes, the order of reprocessing required to achieve asymptotic optimum error performance is reduced by approximately 1/3. This significantly reduces the computational complexity, especially for long codes. Also, a more efficient criterion for stopping the decoding process is derived based on the knowledge of the algebraic decoding solution.

Codes with decomposable structure allow the use of multistage decoding procedures to achieve suboptimum bounded-distance error performance with reduced decoding complexity. This correspondence presents some new decomposable codes, including a class of distance-8 codes, that are constructed based on the |a+x|b+x|a+b+x| construction method. Some existing best codes are shown to be decomposable and hence can be decoded with multistage decoding.

Maximum likelihood sequence detection (MLSD) provides optimum detection for intersymbol interference (ISI) channels subject to additive white Gaussian noise (AWGN). This decoding process dynamically searches the most likely path through the intersymbol interference (ISI) channel trellis, using the Viterbi algorithm (VA). In this paper, we exploit the structure of this trellis and, for an M-point pulse amplitude modulation (PAM) constellation, present a new scheme based on dynamic quantization. This scheme becomes extremely efficient for the single memory unit channel 1+f/sub 1/D, as it achieves optimum MLSD with O(M) computations per decoding step, instead of O(M/sup 2/) for the VA. Generalization to any finite length channel is also possible and conserves good computational efficiency.

Coset codes are considered as terminated convolutional codes. Based on this approach, three new general results are presented. First, it is shown that the iterative squaring construction can equivalently be defined from a convolutional code whose trellis terminates. This convolutional code determines a simple encoder for the coset code considered, and the state and branch labelings of the associated trellis diagram become straightforward. Also, from the generator matrix of the code in its convolutional code form, much information about the trade-off between the state connectivity and complexity at each section, and the parallel structure of the trellis, is directly available. Based on this generator matrix, it is shown that the parallel branches in the trellis diagram of the convolutional code represent the same coset code C/sub 1/ of smaller dimension and shorter length. Utilizing this fact, a two-stage optimum trellis decoding method is devised. The first stage decodes C/sub 1/ while the second stage decodes the associated convolutional code, using the branch metrics delivered by stage 1. Finally, a bidirectional decoding of each received block starting at both ends is presented. If about the same number of computations is required, this approach remains very attractive from a practical point of view as it roughly doubles the decoding speed. This fact is particularly interesting whenever the second half of the trellis is the mirror image of the first half, since the same decoder can be implemented for both parts.

Soft-decision decoding of a linear block code using the most reliable basis corresponding to each received word is investigated. Based either on probabilistic properties or on the structure of the code considered, three improvements to the algorithm devised by Fossorier and Lin (see ibid., vol.41, no.9, p.1379-1396, 1995) are presented. These modifications allow large computation savings or significant decoding speedup with little error performance degradation. First, a reduced probabilistic list of codeword candidates is associated with order-i reprocessing of a given code. It results in a large reduction of the maximum number of computations with a very small degradation in performance. Then, a probabilistic stopping criterion is introduced for order-0 reprocessing. This new test significantly decreases the average number of computations when appropriately implemented. Finally, the application of the algorithm to coset decoding is considered for |u|u+v| constructed codes. In addition to the conventional coset decoding, a new adaptive practically optimum coset decoding method is presented where at each reprocessing stage, the number of surviving cosets decreases. Suboptimum closest coset decoding is also investigated. It is shown that two-stage decoding with the algorithm of Fossorier and Lin offers a large variety of choices, since the reprocessing order of each stage can be determined independently.

Soft-decision decoding algorithms of binary linear block codes require reordering of the received symbols within each block in decreasing reliability. Efficient decoding algorithms based on reordering have been devised. This paper presents different results related to the ordering of a sequence of N received symbols with respect to their reliability measure, for BPSK transmission over the AWGN channel model. First, a tight approximation of Pe(i; N), the probability that the hard decision associated with the ith symbol of the ordered sequence is in error, is derived. Then, it is shown that despite the fact that the random variables representing the noise at positions n/sub 1/, n/sub 2/,...,n/sub j/ of the ordering are no longer independent, the events of having a hard decision decoding error at these positions remain almost independent. Pe(n/sub 1/,n/sub 2/,...,n/sub j/; N), the probability that the hard decisions associated with the symbols at positions n/sub 1/, n/sub 2/,...n/sub j/ in the ordered sequence are in error, is thus well approximated from each of the Pe (n/sub i/; N), for i/spl isin/[1,j]. Finally, based on the independence of these events, the fully connected 2/sup N/-state BSC representing the channel after ordering is simplified by N independent time-shared 2-state BSCss. This new model allows one to easily and tightly approximate the capacity of the channel after ordering.

The paper shows that the catastrophic behavior of TCM codes based on partially overlapped signal constellations significantly increases both the effective error coefficient and the decoding delay of such codes, resulting in a non negligible performance degradation with respect to the asymptotic coding gain.>

Presents a novel approach to soft decision decoding for binary linear block codes. The basic idea is to achieve a desired error performance progressively in a number of stages. For each decoding stage, the error performance is tightly bounded and the decoding is terminated at the stage where either near-optimum error performance or a desired level of error performance is achieved. As a result, more flexibility in the tradeoff between performance and decoding complexity is provided. The decoding is based on the reordering of the received symbols according to their reliability measure. The statistics of the noise after ordering are evaluated. Based on these statistics, two monotonic properties which dictate the reprocessing strategy are derived. Each codeword is decoded in two steps: (1) hard-decision decoding based on reliability information and (2) reprocessing of the hard-decision-decoded codeword in successive stages until the desired performance is achieved. The reprocessing is based on the monotonic properties of the ordering and is carried out using a cost function. A new resource test tightly related to the reprocessing strategy is introduced to reduce the number of computations at each reprocessing stage. For short codes of lengths N/spl les/32 or medium codes with 32>