This paper studies distance properties of coded modulation systems with shaping. The relation between Hamming spectra of a code and its squared Euclidean distance (SED) spectra is analyzed. The main focus of the paper is the so-called shaping after coding. Three shaping schemes based on different mappings of the code symbols onto the shaped QAM signals are proposed and analyzed. Examples of NB LDPC codes used in communication standards are considered. An approach to optimization of shaping books, which combines a genetic algorithm with optimization of the SED for the NB LDPC coded shaped signal sets, is studied. An approximation of the two-dimensional moment generating function for pairs of Hamming distances and SEDs for coded shaped signal sets is derived. A comparison of the estimated SED spectra for coded shaped signal sets with different mappings are presented.

In this work, we propose a system for joint security and error correction at the physical layer. The proposed approach combines the ideas from the area of wiretap channel coding together with a variant of the McEliece public key cryptosystem. The system makes use of randomly chosen nonbinary low-density parity-check codes with quasi-cyclic base matrices. Such a choice allows for efficient hiding of the structure of the generator matrix of the code, thus allowing for protection of the data against the eavedropper's attacks. At the same time, it also supports an efficient error correction. The analysis of the complexity of the attacks and the simulation results demonstrate the advantages of the proposed system.

An approach for estimation of the maximum-likelihood (ML) decoding error probability for coded shaped QAM signals is proposed. It is based on approximation of the squared Euclidean distance spectra of the coded shaped signal constellations. Two variants of shaping used in the communication system with coded QAM signaling are studied: shaping before coding (SBC) and shaping after coding (SAC). First, the new approach is verified by applying it to short codes. Then, it is used to derive a random coding bound on the ML decoding error probability for the ensemble of binary linear codes. Simulation results for the frame error rate (FER) performance of belief-propagation decoding for the optimized nonbinary (NB) quasicyclic (QC)-LDPC codes used with SBC and SAC, as well as the same performance of the binary QC-LDPC block codes in the 5G standard are compared to the new bound.

This paper studies specific properties of nonbinary low-density parity-check (NB LDPC) codes when used in coded modulation systems. The paper is focused on the practically important NB LDPC codes over the Galois extension fields GF$(2^{m})$with$m\le 6$used with QAM signaling. Performance of NB LDPC coded transmission strongly depends on the mapping of nonbinary symbols to signal constellation points. We obtain a random coding bound on the maximum-likelihood decoding error probability for an ensemble of random irregular NB LDPC codes used with QAM signaling for specific symbol-to-signal point mappings. This bound is based on the ensemble average squared Euclidean distance spectra derived for these mappings. The simulation results for the belief-propagation decoding in the coded modulation schemes with the NB quasi-cyclic (QC)-LDPC codes under different mappings are given. Comparisons with the optimized binary QC-LDPC codes in the WiFi and 5G standards, as well as with the new bound, are performed.

In some lattice-based cryptosystems, the encryption and decryption processes can be interpreted as a noisy communication channel. In this work, we focus on cryptosystems based on the ring learning with errors (RLWE) and module learning with errors (MLWE) problems, e.g. Kyber. We provide new coding schemes for the communication channel involved in these cryptosystems. For encoding we use an error-correction code (ECC) along with modulo Q pulse amplitude modulation (PAM) (for some fixed small prime power Q), and vector dequantization. For decoding we perform vector quantization followed by hard/soft decision decoding (HDD/SDD) for the ECC. This construction provides remarkable reduction in the decryption failure rate (DFR), compared to some earlier proposed coding schemes for the same bitrate. For example, in Kyber encryption scheme, we reduce the DFR from 2−174(uncoded) to 2−1325(using HDD) or 2−1414(using SDD).

High-rate irregular Generalized LDPC (GLDPC) codes with low-complexity constituent codes are studied. The main area of focus is the optimization of the underlying irregular binary LDPC codes and their matching with constituent codes. Finite length random coding bound on the maximum-likelihood decoding error probability of a random ensemble of irregular GLDPC codes is derived and compared with a similar bound for non-binary (NB) LDPC codes over small alphabets.A new algorithm for assigning columns of the parity-check matrix of a constituent code to nonzero elements of a base matrix of the quasi-cyclic (QC)-GLDPC code is presented. Examples of the constructed QC-GLDPC codes are given. The simulation results for frame error rate (FER) performance of the belief-propagation (BP) decoding for the QC-GLDPC codes are presented and compared with the same performance of NB QC-LDPC codes over small alphabets and binary LDPC codes in the WiFi and 5G standards.Both GLDPC codes and NB LDPC codes with sufficiently low decoding complexity are shown to outperform their binary LDPC counterparts, while GLDPC codes appear to be more advantageous in terms of decoding complexity.

We propose a novel approach to optimization of irregular nonbinary (NB) quasi-cyclic (QC)-LDPC codes over small alphabets. In this approach, first, the base parity-check matrices are constructed by a simulated annealing method, and then these matrices are labeled by the field elements while maximizing the so- called generalized girth of the Tanner graph. In order to analyze the performance of the constructed irregular NB LDPC codes, a new ensemble of irregular NB LDPC codes over the extensions of the binary Galois field is introduced. A finite-length random coding bound on the error probability of the maximum-likelihood (ML) decoding over the binary phase shift keying (BPSK) input AWGN channel for the new code ensemble is derived. The frame error rate (FER) performance of the sum-product belief-propagation (BP) decoding of the constructed NB QC-LDPC block codes is compared to that of both the optimized binary QC-LDPC block codes in the 5G standard and the best known NB QC-LDPC codes as well as to the derived random coding bound on the ML decoding error probability. It is shown that the obtained bound predicts the behavior of BP decoding performance of practical NB QC-LDPC codes more accurately than the BP decoding thresholds do.

Properties of non-binary (NB) LDPC codes used in conjunction with coded modulation systems are studied. It is observed that the performance of the NB LDPC coded transmission schemes strongly depends on the mapping between the NB symbols and the signal constellation points. The Euclidean distance spectra for an ensemble of random NB LDPC codes for specific mappings are derived. The simulation results for belief-propagation decoding in the coded modulation schemes with the NB QC-LDPC codes under different mappings are presented.

A new “Weighted Bit-flipping” (WBF) iterative decoder is presented and analyzed with respect to its Decoding Failure Rate (DFR). We show that the DFR is indeed lower than that of the BGF decoder as suggested by the BIKE third round submission to the NIST PQC standardization process. The WBF decoder requires more iterations to complete than BGF, but by creating a hybrid decoder we show that a lower DFR compared to that of the BGF decoder can still be achieved while keeping the computational tradeoff to a minimum.

A finite-length random coding bound on the maximum-likelihood decoding error probability for an ensemble of irregular nonbinary (NB) low-density parity-check (LDPC) codes with QAM signaling for specific code symbol-to-signal mappings is derived. Simulation results for the frame error rate (FER) performance of belief-propagation decoding for the optimized NB quasi-cyclic (QC)-LDPC codes used in various coded modulation schemes are presented. Comparison with the same performance of the optimized binary QC-LDPC block codes in the WiFi and 5G standards, as well as with the new bound, is performed.

We propose a novel approach for optimization of nonbinary (NB) quasi-cyclic (QC)-LDPC codes. In this approach, the base parity-check matrices are constructed by the simulated annealing method, and then labeled while maximizing the so-called generalized girth of the NB LDPC code Tanner graph. Random coding bounds on the ML decoding error probability for ensembles of "almost regular" NB LDPC codes of finite lengths over extensions of the binary Galois field are derived. These bounds are based on the average bit weight spectra for the ensembles of NB LDPC codes. The observed FER performance of the sum-product BP decoding of "almost regular" NB QC-LDPC block codes is presented and compared to the finite-length random coding bounds, as well as to the performance of the optimized binary QC-LDPC block code in the 5G standard. In the waterfall region, the gap between the finite-length bounds on the error probability of the ML decoding and the simulation performance of the BP decoding is about 0.1 – 0.2 dB.

We improve iterative decoding of the moderate density parity-check codes, recently suggested as code candidates in the McEliece public key cryptosystem. In case of bit-flipping (BF) decoder failure, the code parity-check matrix is extended by adding auxiliary variable nodes based on reliability information from the BF decoder. Then iterative decoding is applied to the extended parity-check matrix. The proposed decoding algorithm is analyzed and its frame error rate performance is compared to the same performance of both the best implementations of BF decoding and its modifications. It is demonstrated an improved performance for the iterative decoding step in decryption, which allows to increase the resistance against recent attacks based on taking advantage of the somewhat large failure probability of the BF algorithm.

An approach to constructing discrete models of packet losses suitable for a wide variety of communication network applications is studied. It is based on estimating parameters of probabilistic automata described via so-called pseudo-Markov chains. The new technique is applied both to approximating a discrete time analog process at the output of known channel models and to the experimental data stream. Comparison of models is performed by computing probabilities of more than m losses out of n transmitted packets (P (≥ m, n)). It is shown that for the Rician fading channel with exponential correlation and correlation determined by a Bessel filter, the obtained rank-two and rank-three discrete modes, respectively, provide high accuracy coincidence of P (≥ m, n) performances. The rank-three discrete model computed on the experimental data stream obtained from the LTE network provides significantly better approximation of P (≥ m, n) performance than that obtained by the Baum-Welch algorithm.

One of the most efficient approaches to improving the frame error rate (FER) performance of low-density parity-check (LDPC) codes is based on adding both auxiliary variable nodes (AVN) and the corresponding redundant parity checks (RPC) to the binary parity-check matrices of the code. It is known that for the LDPC codes, whose Tanner graphs contain length four cycles, this technique allows for substantial improvement in the FER performance of the belief-propagation (BP) decoding on the binary erasure channel (BEC) channel. The AVN-based technique followed by adding orthogonal redundant parity-checks is known to be efficient for both the BEC and additive white Gaussian noise (AWGN) channels. In this paper, firstly, the AVN-based approach is generalized to efficiently removing cycles of length larger than four. Secondly, the AVN-based technique is reformulated in terms of labeled base matrices of quasi-cyclic (QC) LDPC codes. An improved iterative decoding of QC LDPC codes is proposed, which is applied to the labeled base matrices of QC LDPC codes extended by the AVN-RPC technique.

In this paper, we study a classical problem of source coding with side information available at the decoder. This problem is known as the Wyner-Ahlswede-Korner (WAK) problem. Nowadays, the interest in this problem is related to the concept of distributed source coding which implies coding of correlated sources under restriction that their encoders cannot cooperate. Most of the practical coding schemes consider a specific case of the binary symmetric source with uniform distribution and side information assumed to be perfectly known to the decoder. In this paper, we concentrate on a more complicated model of the binary source. Moreover, we consider a case when side information is lossy encoded. First we generalize the approach by Gu et al. [1] in order to obtain a lower bound on the achievable rates for a general binary source. Then, a new practical “multi-class” coding scheme for this binary source with uncoded binary side information is suggested. Simulation results for LDPC-based coding for both binary symmetric and general binary sources are presented for scenarios with trellis-coded and uncoded side information, respectively. Comparisons with the previously known numerical results are presented.

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

A new method is presented for low-complexity near-maximum-likelihood (ML) decoding of low-density parity-check (LDPC) codes over the additive white Gaussian noise channel. The proposed method termed belief-propagation-list erasure decoding (BP-LED) is based on erasing carefully chosen unreliable bits performed in case of BP decoding failure. A strategy of introducing erasures into the received vector and a new erasure decoding algorithm are proposed. The new erasure decoding algorithm, called list erasure decoding, combines ML decoding over the BEC with list decoding applied if the ML decoder fails to find a unique solution. The asymptotic exponent of the average list size for random regular LDPC codes from the Gallager ensemble is analyzed. Furthermore, a few examples of irregular quasi-cyclic LDPC as well as randomly constructed regular LDPC codes of short and moderate lengths are studied by simulations and their performance is compared to the tightened upper bound on the LDPC ensemble-average performance and the upper bound on the average performance of random linear codes under ML decoding. A comparison of the BP decoding and BP-LED performance of the WiMAX standard codes and performance of the near-ML BEAST decoding are presented. The new algorithm is applied to decoding a short nonbinary (NB) LDPC code over extensions of the binary Galois field. The obtained simulation results are compared to the tightened upper bound on the ensemble-average performance of the binary image of regular NB LDPC codes.

Stopping sets play a crucial role in failure events of iterative decoders over a binary erasure channel (BEC). The ℓth stopping redundancy is the minimum number of rows in the parity-check matrix of a code, which contains no stopping sets of size up to ℓ. In this paper, a notion of coverable stopping sets is defined. In order to achieve maximum-likelihood performance under iterative decoding over the BEC, the parity-check matrix should contain no coverable stopping sets of size ℓ, for 1 ≤ ℓ ≤ n-k, where n is the code length, k is the code dimension. By estimating the number of coverable stopping sets, we obtain upper bounds on the ℓth stopping redundancy, 1 ≤ ℓ ≤ n-k. The bounds are derived for both specific codes and code ensembles. In the range 1 ≤ ℓ ≤ d-1, for specific codes, the new bounds improve on the results in the literature. Numerical calculations are also presented.

A new decoding algorithm for LDPC codes on the AWGN channel is proposed. The algorithm is based on the idea of using redundant parity checks and additional variable nodes. The new key element in the proposed algorithm is the use of the orthogonal subsets of parity checks for computing soft decisions for different variable nodes. This allows for significant improvement in the decoding error performance of the algorithm compared to the known counterparts. Furthermore, new bounds on the error performance of the BP decoding applied to the parity-check matrices with redundant parity-checks are obtained.

The Gallager ensembles of binary regular LDPC codes and binary images of nonbinary regular LDPC codes are studied. Recurrent procedure for computing average spectra for these two ensembles is presented. By using the existing bounding techniques, estimates on the error probability of the maximum-likelihood (ML) decoding over an AWGN channel with BPSK signaling for short codes from different ensembles of LDPC codes are obtained. The numerical results show performance of the ML decoding for different code ensembles. Conclusions drawn based on the average code spectra are then verified by near-ML decoding simulations for both randomly selected and the best known short codes. The asymptotic ML decoding thresholds for AWGN and BSC channels are calculated. As expected, codes with the ML decoding performance superior to that of the average code in the ensemble, are easy to find. However, comparison of the the presented results with simulation results for belief propagation (BP) decoding shows that the ML decoding performance should not be used as a target for searching for good iteratively decodable codes.

The exact values of finite length average weight distributions for both binary ensembles and binary images of nonbinary ensembles of regular LDPC codes are computed. The exact average stopping set size distribution for the binary ensemble is also obtained. The computed spectra are applied in order to bound from above the average stopping redundancy of the ensemble of binary regular LDPC codes. The asymptotic typical normalized minimum distances for the binary image of the ensemble of nonbinary regular LDPC codes and the typical minimum stopping distances for the binary regular LDPC codes are also presented.

A novel method for decoding of low-density parity-check codes on the AWGN channel is presented. In the proposed method, first, a standard belief-propagation decoder is applied, then a certain number of positions is erased using a combination of a reliability criterion and a set of masks. A list erasure decoder is then applied to the resulting word. The performance of the proposed method is analyzed mathematically and demonstrated by simulations.

This paper studies an almost-lossless source-channel coding scheme in which source messages are assigned to different classes and encoded with a channel code that depends on the class index. The code performance is analyzed by means of random-coding error exponents and validated by simulation of a low-complexity implementation using existing source and channel codes. While each class code can be seen as a concatenation of a source code and a channel code, the overall performance improves on that of separate source-channel coding and approaches that of joint source-channel coding when the number of classes increases.

A unified approach to search for and optimize codes determined by their sparse parity-check matrices is presented. Replacing the nonzero elements of a binary parity-check matrix (the base or parent matrix) either by circulants or by companion matrices of elements from a finite field GF(2m), we obtain quasi-cyclic low-density parity-check (LDPC) block codes and binary images of nonbinary LDPC block codes, respectively. By substituting monomials of a formal variable D, we obtain the polynomial description of an LDPC convolutional code. A set of performance measures applicable to different classes of LDPC codes is considered, and a greedy algorithm for code performance optimization is presented. The heart of the new optimization algorithm is a fast procedure for searching for LDPC codes with large girth of their Tanner graphs. For a few classes of LDPC codes, examples of codes combining good error-correcting performance with compact representation are obtained. In particular, we present optimized convolutional LDPC codes and conclude that the LDPC block codes are still superior to their convolutional counterparts if both decoding complexity and coding delay are considered. Moreover, a specific channel model can easily be embedded into the optimization loop. Thereby, the code can be optimized for a specific channel. The efficiency of such an optimization is demonstrated via an example of faster than Nyquist (FTN) signaling using LDPC codes. The FTN strategy combined with a rate R = 1/2 LDPC code of length 64800 optimized for effective data rate R = 3/4 gains more than 0.5 dB compared with the standard LDPC codes of the same rate and length. The obtained gain corresponds to transmission at the capacity of the binary input additive white Gaussian noise channel. In most numerical examples, we consider codes with bidiagonal structure of the parity-check matrix. This restriction preserves low encoding complexity and allows fair comparison with codes selected for communication standards.

We study a source-channel coding scheme in which source messages are assigned to classes and encoded using a channel code that depends on the class index. While each class code can be seen as a concatenation of a source code and a channel code, the overall performance improves on that of separate source-channel coding and approaches that of joint source-channel coding as the number of classes increases. The performance of this scheme is studied by means of random-coding bounds and validated by simulation of a low-complexity implementation using existing source and channel codes.

Outstanding asymptotical performance demonstrated by low-density parity-check (LDPC) convolutional codes (CC) makes them strong competitors with respect to quasi-cyclic (QC) LDPC block codes (BC) currently used in a variety of communication standards. However, typically communication standards, for example, DVB-S2 or WIMax standards impose rather serious restrictions on the structure of the employed codes. These restrictions are related to different implementation issues such as existence of low-complexity encoding and decoding, short decoding delay etc. Two scenarios are considered. In one scenario, short-delay and low-complexity constraints are taken into account. In the other scenario, the complexity requirement is relaxed. Both LDPC CCs and QC LDPC BCs with optimized degree distribution and girth profile, which enable low-complexity encoding, are constructed for these scenarios. Having both delay and complexity constraints yields QC LDPC BCs that outperform the LDPC CCs. In this scenario LDPC CCs play an important role mostly for constructing tailbiting QC LDPC BCs. On the other hand, assuming only a decoding delay constraint the LDPC CCs can be superior compared to the QC LDPC BCs at the relatively low signal-to-noise ratio region. Moreover, under practically acceptable decoding delays also the LDPC CCs with low-complexity encoding structure beat records in approaching the Shannon limit. A new LDPC CC is presented achieving the BER 10-7with decoding delay 96000 bits at 0.62 dB, that is, performing only about 0.43 dB from the Shannon limit.

In this paper we investigate the highly bandwidth-efficient Faster-than-Nyquist (FTN) signaling scheme under high order modulations. The FTN system is an emerging technology which has drawn attention in the contemporary spectrum-saving communication environment. Since FTN traditionally achieves high bandwidth efficiency through increased baud-rate, binary modulation is assumed in most research of FTN. The contribution of this paper lies in the extension into high order modulations and its assessment. This enables the communication systems to achieve higher data rates for the same bandwidth and receiver complexity than binary Nyquist signaling systems. Moreover, it is shown that an additional efficiency gain can be achieved by replacing the LDPC codes from the DVB-S2 standard by new optimized quasi-cyclic (QC) LDPC codes whose parameters are matched with FTN signaling.

Techniques for searching for good quasi-cyclic (QC) LDPC block codes of short and moderate lengths which are suitable for practical purposes are studied. To facilitate implementations only codes whose parity-check matrices having bidiagonal structure of their submatrices and consequently having low encoding complexity are considered. The problem of finding QC LDPC codes with the near-optimum frame or bit error rate performance is split into two independent steps: searching for the near-optimum column degree distribution of the parity-check matrix together with the best base matrix for this degree distribution and searching for the near-optimum labeling of the chosen base matrix. Sets of parameters and criteria for both steps are introduced and discussed. They allow further reduction of the search complexity without significant loss of the search optimality. New QC LDPC block codes of various code rates are obtained and their BER and FER performances are compared with those of the LDPC block codes as well as the turbo codes defined in the IEEE 802.16 WiMAX standard.

Relations between Generalized LDPC codes, nonbinary LDPC codes, and woven graph codes are considered. Focus is on rather short codes suitable, for example, for coding control signaling information in mobile communications. In particular, codes of lengths less than 200 bits are studied. Low-complexity near maximum-likelihood (ML) decoding for these classes of codes is introduced and analyzed. Frame error rate (FER) performance of the new decoding procedure is compared with the same performance of ML and belief propagation (BP) decoding. It is shown that unlike BP decoding whose performances are mainly governed by the girth of the Tanner graph the new decoding procedure has performances which significantly depend on the minimum distance and spectrum of the woven code. Short woven graph codes with large minimum distances are tabulated.

The girth profile is introduced and search algorithms for regular and irregular quasi-cyclic LDPC block codes with both good girth profile and good degree distribution are presented. New QC LDPC block codes of various code rates are obtained and their bit error rate performance is compared with that of the corresponding LDPC block codes defined in the IEEE 802.16 WiMAX standard of the same block length and code rate.

In 1995, Bestpublished a formula for the exact bit error probability for Viterbi decoding of the rate$R=1/2$, memory$m=1$(two-state) convolutional encoder with generator matrix$G(D)=(1 \quad 1+D)$when used to communicate over the binary symmetric channel. Their formula was later extended to the rate$R=1/2$, memory$m=2$(four-state) convolutional encoder with generator matrix$G(D)=(1+D^{2} \quad 1+D+D^{2})$by LentmaierIn this paper, a different approach to derive the exact bit error probability is described. A general recurrent matrix equation, connecting the average information weight at the current and previous states of a trellis section of the Viterbi decoder, is derived and solved. The general solution of this matrix equation yields a closed-form expression for the exact bit error probability. As special cases, the expressions obtained by Bestfor the two-state encoder and by Lentmaierfor a four-state encoder are used. The closed-form expression derived in this paper is evaluated for various realizations of encoders, including rate$R=1/2$and$R=2/3$encoders, of as many as 16 states. Moreover, it is shown that it is straightforward to extend the approach to communication over the quantized additive white Gaussian noise channel.

The relation between parity-check matrices of quasi-cyclic (QC) low-density parity-check (LDPC) codes and biadjacency matrices of bipartite graphs supports searching for powerful LDPC block codes. Using the principle of tailbiting, compact representations of bipartite graphs based on convolutional codes can be found. Bounds on the girth and the minimum distance of LDPC block codes constructed in such a way are discussed. Algorithms for searching iteratively for LDPC block codes with large girth and for determining their minimum distance are presented. Constructions based on all-one matrices, Steiner Triple Systems, and QC block codes are introduced. Finally, new QC regular LDPC block codes with girth up to 24 are given.

A new method using Hamming codes to construct base matrices of (J,K)-regular LDPC convolutional codes with large free distance is presented. By proper labeling the corresponding base matrices and tailbiting these parent convolutional codes to given lengths, a large set of quasi-cyclic (QC) (J,K)-regular LDPC block codes with large minimum distance is obtained. The corresponding Tanner graphs have girth up to 14. This new construction is compared with two previously known constructions of QC (J,K)-regular LDPC block codes with large minimum distance exceeding (J + 1)!. Applying all three constructions, new QC (J,K)-regular block LDPC codes with J = 3 or 4, shorter codeword lengths and/or better distance properties than those of previously known codes are presented.

The relation between the parity-check matrices of quasi-cyclic (QC) low-density parity-check (LDPC) codes and the biadjacency matrices of bipartite graphs supports searching for powerful LDPC block codes. Algorithms for searching iteratively for LDPC block codes with large girth are presented and constructions based on Steiner Triple Systems and short QC block codes are introduced, leading to new QC regular LDPC block codes with girth up to 24.

The relation between low-density parity-check (LDPC) codes and hypergraphs supports searching for powerful LDPC codes based on hypergraphs. On the other hand, coding theory methods can be used in searching for hypergraphs with large girth. Moreover, compact representations of hypergraphs based on convolutional codes can be found. Algorithms for iteratively constructing LDPC codes with large girth and for determining their minimum distance are introduced. New quasi-cyclic (QC) LDPC codes are presented, some having both optimal girth and optimal minimum distance.

Constructions of woven graph codes based on constituent block and convolutional codes are studied. It is shown that within the random ensembles of such codes based on$s$-partite,$s$-uniform hypergraphs, where$s$depends only on the code rate, there exist codes satisfying the Gilbert—Varshamov (GV) and the Costello lower bound on the minimum distance and the free distance, respectively. A connection between regular bipartite graphs and tailbiting (TB) codes is shown. Some examples of woven graph codes are presented. Among them, an example of a rate$R_{\rm wg}=1/3$woven graph code with$d_{\rm free}=32$based on Heawood's bipartite graph, containing$n=7$constituent rate$R^{\rm c}=2/3$convolutional codes with overall constraint lengths$\nu^{\rm c}=5$, is given.

A rate R=5/20 hypergraph-based woven convolutional code with overall constraint length 67 and constituent convolutional codes is presented. It is based on a 3-partite, 3-uniform, 4-regular hypergraph and contains rate Rc=3/4 constituent convolutional codes with overall constraint length 5. Although the code construction is based on low-complexity codes, the free distance of this construction, computed with the BEAST algorithm, is dfree=120, which is remarkably large.

We search for good regular quasi-cyclic (QC) LDPC codes with J = 2 ones in each column. In order to simplify the search, QC LDPC codes are represented in the form of tail-biting (TB) convolutional codes. A modified BEAST algorithm is used for finding the free distance (minimum distance) and the girth of both parent convolutional and block LDPC codes. Representations of known bipartite graphs and LDPC based on finite geometries in the form of TB convolutional codes are found. This approach is further generalized for J = 3 QC LDPC codes. Examples of good short LDPC codes with large girth and minimum distance are given. For example, we present a rate 2=5 J = 3 QC LDPC (225, 92)- code with girth 8 and minimum distance 24.

Rate R = (c-1)/c convolutional codes of constraint length ν can be represented by conventional syndrome trellises with a state complexity of s = ν or by binary syndrome trellises with a state complexity of s = ν or s = ν + 1, which corresponds to at most 2sstates at each trellis level. It is shown that if the parity-check polynomials fulfill certain conditions, there exist binary syndrome trellises with optimum state complexity s = ν. The BEAST is modified to handle parity-check matrices and used to generate code tables for optimum free distance rate R = (c - 1)=c, c = 3; 4; 5, convolutional codes for conventional syndrome trellises and binary syndrome trellises with optimum state complexity. These results show that the loss in distance properties due to the optimum state complexity restriction for binary trellises is typically negligible.

Constructions of woven graph codes based on constituent block and convolutional codes are studied. It is shown that within the random ensemble of such codes based on s-partite, s-uniform hypergraphs, where s depends only on the code rate, there exist codes satisfying the Varshamov-Gilbert (VG) and the Costello lower bound on the minimum distance and the free distance, respectively.

List decoding of binary block codes for the additive white Gaussian noise (AWGN) channel is considered. The output of a list decoder is a list of the$L$most likely codewords, that is, the$L$signal points closest to the received signal in the Euclidean-metric sense. A decoding error occurs when the transmitted codeword is not on this list. It is shown that the list error probability is fully described by the so-called list configuration matrix, which is the Gram matrix obtained from the signal vectors forming the list. The worst case list configuration matrix determines the minimum list distance of the code, which is a generalization of the minimum distance to the case of list decoding. Some properties of the list configuration matrix are studied and their connections to the list distance are established. These results are further exploited to obtain a new upper bound on the list error probability, which is tighter than the previously known bounds. This bound is derived by combining the techniques for obtaining the tangential union bound with an improved bound on the error probability for a given list. The results are illustrated by examples.

A Bidirectional Efficient Algorithm for Searching code Trees (BEAST) is proposed for efficient soft-output decoding of block codes and concatenated block codes. BEAST operates on trees corresponding to the minimal trellis of a block code and finds a list of the most probable codewords. The complexity of the BEAST search is significantly lower than the complexity of trellis-based algorithms, such as the Viterbi algorithm and its list generalizations. The outputs of BEAST, a list of best codewords and their metrics, are used to obtain approximatea posterioriprobabilities (APPs) of the transmitted symbols, yielding a soft-input soft-output (SISO) symbol decoder referred to as the BEAST-APP decoder. This decoder is employed as a component decoder in iterative schemes for decoding of product and incomplete product codes. Its performance and convergence behavior are investigated using extrinsic information transfer (EXIT) charts and compared to existing decoding schemes. It is shown that the BEAST-APP decoder achieves performances close to the Bahl–Cocke–Jelinek–Raviv (BCJR) decoder with a substantially lower computational complexity.

A construction of woven graph codes based on constituent convolutional codes is studied. It is shown that within the random ensemble of such codes there exist asymptotically good codes with short fixed constituent codes. An example of a rate R = 1/3 woven graph code with free distance equal to 32 based on rate Rc= 2/3 constituent convolutional codes with overall constraint length 5 is given.

This paper reviews soft-input soft-output (SISO) algorithms that have been recently proposed as reduced-complexity alternatives to maximumaposteriori(MAP) trellis-based decoding or equalization. The M*-BCJR, LISS, and BEAST algorithms are chosen as representatives of reduced-state trellis- and tree- search procedures. The former two algorithms have been initially developed for intersymbol interference (ISI) equalization, while BEAST is tailored for decoding. All three algorithms are modified for either application and their advantages and shortcomings are studied for each case. Comparisons in terms of performance and complexity are presented.

An extended table of Shuurman's bounds on the state complexity of short binary linear codes is presented. Some new lower and upper bounds are obtained. Most of the newly found codes are based on the so-called double zero-tail termination (DZT) construction.

A new upper bound on the list error probability is presented. This bound is derived by combining the techniques for obtaining the tangential union bound with an improved bound on the error probability with respect to a given list. Connections between the list distance and the eigenvalues of the covariance matrix of the code are studied.

The performance and convergence behavior of the iterative schemes for decoding two-dimensional product codes are investigated. The decoding trajectories of the extrinsic and the a posteriori information are used as a main tool for predicting and explaining the behavior of the iterative decoding process. The component-wise optimal BCJR decoder is compared to the suboptimal max-log-MAP decoder and the list-based BEAST-APP decoder in terms of convergence and bit-error-rate performance. The results are illustrated by examples, which show that the BEAST-APP decoder achieves near-BCJR performance with significantly lower complexity.

The BEAST-APP decoding algorithm is a low-complexity bidirectional algorithm that searches code trees to find the list of the most likely codewords, which are used to compute approximate a posteriori probabilities (APPs) of the transmitted symbols. It can be applied to APP-decoding of any linear block code, as well as in iterative structures for decoding concatenated block codes. Previous work has shown that the list size sufficient to achieve the performance of true-APP decoding is very small. This paper aims at providing a theoretical justification for this result. The sufficient list size is estimated first via the minimum list distance - a parameter that is defined and analyzed as a key factor that governs the performance of list-based algorithms. Additionally, statistical properties of the codeword likelihoods are investigated and the typical list structure is presented. Preliminary simulation results for iterative BEAST decoding confirm the list-size estimates obtained from both approaches.

BEAST is a bidirectional efficient algorithm for searching trees that performs soft-decision maximum-likelihood (ML) decoding of block codes. The decoding complexity of BEAST is significantly reduced compared to the Viterbi algorithm. An analysis of the asymptotic BEAST decoding complexity verifies BEAST's high efficiency compared to other algorithms. The best of the obtained asymptotic upper bounds on the BEAST decoding complexity is better than previously known bounds for ML decoding in a wide range of code rates.

BEAST is a bidirectional efficient algorithm for searching trees. In this correspondence, BEAST is extended to maximum-likelihood (ML) decoding of block codes obtained via convolutional codes. First it is shown by simulations that the decoding complexity of BEAST is significantly less than that of the Viterbi algorithm. Then asymptotic upper bounds on the BEAST decoding complexity for three important ensembles of codes are derived. They verify BEAST's high efficiency compared to other algorithms. For high rates, the new asymptotic bound for the best ensemble is in fact better than previously known bounds.

Good approximations of code-symbol a-posteriori probabilities (APPs) are obtained using a list of the most likely codewords, instead of the whole code-book. This list is found by Bidirectional Efficient Algorithm for Searching code Trees (BEAST), whose complexity is shown to be lower than of the known trellis-based algorithms.

When searching for convolutional codes and tailbiting codes of high complexity it is of vital importance to use fast algorithms for computing their weight spectra, which corresponds to finding low-weight paths in their code trellises. This can be efficiently done by a combined search in both forward and backward code trees. A bidirectional efficient algorithm for searching such code trees (BEAST) is presented. For large encoder memories, it is shown that BEAST is significantly more efficient than comparable algorithms. BEAST made it possible to find new convolutional and tailbiting codes that have larger free (minimum) distances than the previously best known codes with the same parameters. Tables of such codes are presented.

A new class of block codes with low state complexity of their conventional trellis representations called double zero-tail terminated convolutional codes (DZT codes) is introduced. It is shown that there exist DZT-codes meeting the Varshamov-Gilbert bound on the minimum distance and having asymptotically optimal state complexity. Two ways of constructing DZT-codes are considered. Examples of DZT-codes meeting a lower bound on the state complexity are given.

The slope of the active distances is an important parameter when investigating the error-correcting capability of convolutional codes and the distance behavior of concatenated convolutional codes. The slope of the active distances is equal to the minimum average weight cycle in the state-transition diagram of the encoder. A general upper bound on the slope depending on the free distance of the convolutional code and new upper bounds on the slope of special classes of binary convolutional codes are derived. Moreover, a search technique, resulting in new tables of rate R=1/2 and rate R=1/3 convolutional encoders with high memories and large active distance-slopes is presented. Furthermore, we show that convolutional codes with large slopes can be used to obtain new tailbiting block codes with large minimum distances. Tables of rate R=1/2 and rate R=1/3 tailbiting codes with larger minimum distances than the best previously known quasi-cyclic codes are given. Two new tailbiting codes also have larger minimum distances than the best previously known binary linear block codes with same size and length. One of them is also superior in terms of minimum distance to any previously known binary nonlinear block code with the same set of parameters.

Tailbiting trellis representations of linear block codes with an arbitrary sectionalization of the time axis are studied. The notations of regular and irregular tailbiting codes are introduced and their maximal state complexities are lower-bounded. The asymptotic behavior of the derived bound is investigated. Furthermore, for regular tailbiting codes the product state complexity is lower-bounded. Tables of new tailbiting trellis representations of linear block codes of rates 1/2, 1/3, and 1/4 are presented. Almost all found trellises are optimal in the sense of the new bound on the state complexity and for most codes with nonoptimal trellises there exist time-varying trellises which are optimal. Five of our newly found tailbiting codes are better than the previously known linear codes with the same parameters. Four of them are also superior to any previously known nonlinear code with the same parameters. Also, more than 40 other quasi-cyclic codes have been found that improve the parameter set of previously known quasi-cyclic codes.

We present rational rate k/n punctured convolutional codes (n up to 8, k=1, /spl middot//spl middot//spl middot/, n-1, and constraint length /spl nu/ up to 8) with good performance. Many of these codes improve the free distance and (or) weight spectra over previously reported codes with the same parameters. The tabulated codes are found by an exhaustive (or a random) search.