In this paper the decoding capabilities of convolutional codes over the erasure channel are studied. More precisely we focus on local erasures correction. We present special decoders that are able to correct significantly more erasures locally than block codes of the same rate. We also present some expressions that connect the number of possible corrected erasures with memory, rate and free distance of convolutional codes.

In this paper we propose a woven block code construction based on two convolutional outer codes and a single inner code. We proved lower and upper bounds on this construction's code distance. The lower bound is shown to be higher than the product of the free distances of inner and outer constituent codes. Since this construction uses well-developed convolutional constituent codes, we believe that it would be competitive to turbo codes in the future mobile communication systems.

We consider the decoding of LDPC codes over GF(q) with the low-complexity majority algorithm from [1]. A modification of this algorithm with multiple thresholds is suggested. A lower estimate on the decoding radius realized by the new algorithm is derived. The estimate is shown to be better than the estimate for a single threshold majority decoder. At the same time the transition to multiple thresholds does not affect the order of complexity.

In this paper we propose to consider a generalized error-locating code (GEL-code) as a possible candidate for data transmission systems that require high code rates along with strict requirements on wrong decoding probability. GEL codes are one of a few that allow analytical computation of code error probability bounds and have practical construction method. The paper describes the construction of the GEL-code and the algorithms for encoding and decoding. It represents the upper and lower bounds on wrong decoding probability. It gives a method for constructing such GEL code (with the minimal redundancy) that guarantees that the probability of wrong decoding will be less than required one (for a given channel error probability). Numerical results for the upper and lower bounds for the various GEL-codes and the analysis of the energy gain for the different signal-code structures are given.

The paper addresses the problem of constructing an asynchronous multiple access system for a multi-user Q-frequency channel with additive white Gaussian noise (AWGN). We propose a coding scheme for the channel which allows a large number of users to work simultaneously in the system. The scheme combines the ideas of Frequency Shift Keying (FSK) and Frequency Hopping Spread Spectrum (FHSS). The major component of the scheme is a non-binary low-density parity-check (LDPC) code. The efficiency of the resulting multiple-access system is shown by simulations.

This paper deals with the method of undetected error probability estimation for a low-density parity-check (LDPC) code under any given iterative decoding algorithm. We propose such modification of a given iterative decoding algorithm, that almost preserves a decoding failure exponent and decoding complexity of this algorithm. We obtain the upper bound on the undetected error probability for the modified algorithm. We show how to use the proposed method to estimate the undetected error probability of LDPC code under the belief propagation (BP) algorithm at the end of this paper.

We address the problem of increasing the sum rate in a multiple-access system from [1] for small number of users. We suggest an improved signal-code construction in which in case of a small number of users we give more resources to them. For the resulting multiple-access system a lower bound on the relative sum rate is derived. It is shown to be very close to the maximal value of relative sum rate in [1] even for small number of users. The bound is obtained for the case of decoding by exhaustive search. We also suggest reduced-complexity decoding and compare the maximal number of users in this case and in case of decoding by exhaustive search.

The minimum distance of expander codes over GF(q) is studied. A new upper bound on the minimum distance of expander codes is derived. The bound is shown to lie under the Varshamov-Gilbert (VG) bound while q ≥ 32. Lower bounds on the minimum distance of some families of expander codes are obtained. A lower bound on the minimum distance of low-density parity-check (LDPC) codes with a Reed-Solomon constituent code over GF(q) is obtained. The bound is shown to be very close to the VG bound and to lie above the upper bound for expander codes.

In this paper we describe ensemble of binary partial unit memory (PUM) codes based on Low-Density Parity-Check (LDPC) block codes. We study the lower bound on the free distance of the proposed codes and show that the increase α of these codes has positive value.

This paper considers new lower bound on fraction of guaranteed corrected errors while decoding the same binary low-density parity-check (LDPC) codes with constituent single parity-check (SPC) and Hamming codes using the same iterative low-complex hard-decision algorithm as in previous works of V. Zyablov and M. Pinsker in 1975 and V. Zyablov, R. Johannesson and M. Loncar in 2009. The number of decoding iterations, required to correct the errors, is a logarithmic function of the code length. The fraction of guaranteed correctable errors computed numerically for various choices of LDPC code parameters with constituent SPC and Hamming codes shows that proposed lower bound gives the better results than previously known best lower bounds obtained by V. Zyablov and M. Pinsker in 1975 for Gallager's LDPC codes and A. Barg and A. Mazumrad for Hamming code-based LDPC (H-LDPC) codes in 2011. Some of obtained numerical results are represented at the end of the paper to demonstrate these improvements.

Traditionally, multi-trial error/erasure decoding of Reed-Solomon (RS) codes is based on Bounded Minimum Distance (BMD) decoders with an erasure option. Such decoders have error/erasure tradeoff factor λ = 2, which means that an error is twice as expensive as an erasure in terms of the code's minimum distance. The Guruswami-Sudan (GS) list decoder can be considered as state of the art in algebraic decoding of RS codes. Besides an erasure option, it allows to adjust λ to values in the range 1BMDdecoding trials can result in lower residual codeword error probability than GS decoders with zGStrials, if zBMDis only slightly larger than zGS. This is of practical interest since BMD decoders generally have lower computational complexity than GS decoders.

(Partial) Unit Memory ((P)UM) codes provide a powerful possibility to construct convolutional codes based on block codes in order to achieve a high decoding performance. In this contribution, a construction based on Gabidulin codes is considered. This construction requires a modified rank metric, the so-called sum rank metric. For the sum rank metric, the free rank distance, the extended row rank distance and its slope are defined. Upper bounds for the free rank distance and the slope of (P)UM codes in the sum rank metric are derived. The construction of PUM codes based on Gabidulin codes achieves the upper bound for the free rank distance.

We investigate threshold-based multi-trial decoding of concatenated codes with an inner Maximum-Likelihood decoder and an outer error/erasure ℓ+1/ℓ-extended Bounded Distance decoder, i.e. a decoder which corrects ε errors and τ erasures if ℓ+1/ ℓε+τ≤ do-1, where dois the minimum distance of the outer code and ℓ ∈ ℕ\{0}. This is a generalization of Forney's GMD decoding, which was considered only for ℓ = 1, i.e. outer Bounded Minimum Distance decoding. One important example for ℓ+1/ℓ-extended Bounded Distance decoders is decoding of ℓ-Interleaved Reed-Solomon codes. Our main contribution is a threshold location formula, which allows to optimally erase unreliable inner decoding results, for a given number of decoding trials and parameter ℓ. Thereby, the term optimal means that the residual codeword error probability of the concatenated code is minimized. We give an estimation of this probability for any number of decoding trials.

We investigate adaptive single-trial error/erasure decoding of binary codes whose decoder is able to correct ε errors and τ erasures if λε + ≤min-1. Thereby, dminis the minimum Hamming distance and λ ϵ R, 1 <; λ <; 2, is the tradeoff parameter between errors and erasures. The error/erasure decoder allows to exploit soft information by treating a set of most unreliable received symbols as erasures. The obvious question here is, how this erasing should be performed, i.e. how the unreliable symbols that must be erased in order to obtain the smallest possible residual codeword error probability can be determined. This was answered before for the case of fixed erasing, where only the channel state and not the individual symbol reliabilities of each received vector are taken into consideration. In this paper, we address the adaptive case, where the optimal erasing strategy is determined for every given received vector.

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.

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.

Generalized Concatenated codes are a code construction consisting of a number of outer codes whose code symbols are protected by an inner code. As outer codes, we assume the most frequently used Reed-Solomon codes; as inner code, we assume some linear block code which can be decoded up to half its minimum distance. Decoding up to half the minimum distance of Generalized Concatenated codes is classically achieved by the Blokh-Zyablov-Dumer algorithm, which iteratively decodes by first using the inner decoder to get an estimate of the outer code words and then using an outer error/erasure decoder with a varying number of erasures determined by a set of pre- calculated thresholds. In this paper, a modified version of the Blokh-Zyablov-Dumer algorithm is proposed, which exploits the fact that a number of outer Reed-Solomon codes with average minimum distance d macr can be grouped into one single Interleaved Reed-Solomon code which can be decoded beyond d macr/2. This allows to skip a number of decoding iterations on the one hand and to reduce the complexity of each decoding iteration significantly - while maintaining the decoding performance - on the other.

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.

In this correspondence, unequal error-correcting capabilities of convolutional codes are studied. For errors in the information symbols and code symbols, the free input- and output-distances, respectively, serve as "unequal" counterparts to the free distance. When communication takes place close to or above the channel capacity the error bursts tend to be long and the free distance is not any longer useful as the measure of the error correcting capability. Thus, the active burst distance for a given output and the active burst distance for a given input are introduced as "unequal" counterparts to the active burst distance and improved estimates of the unequal error-correcting capabilities of convolutional codes are obtained and illustrated by examples. Finally, it is shown how to obtain unequal error protection for both information and code symbols using woven convolutional codes.

In this paper unequal error-correcting capabilities of convolutional codes are studied. State-transition graphs are used for investigating the error-correcting capabilities for specific inputs or outputs of given convolutional encoding matrices. Active burst input- and output-distances are defined and shown to be generalizations of the active burst distance. These new distances provide better estimates of the error-correction capability, especially when we communicate close to or above the channel capacity and they are connected to the corresponding free input- and output-distances via lower bounds

This paper describes the active burst distance for convolutional codes. The unequal error protection for information sequences are used to formulate a theorem on the error-correcting capability of the generator matrix and set state paths in the encoder state-transition diagram correspond to code sequences. Therefore the active-distance concepts are used to characterize the error patterns.

To find the best path in a trellis, the Viterbi algorithm can be used. We present an algorithm to find not only the best, but a sorted list of the /spl lscr/ best paths. Our algorithm is based on the Viterbi algorithm and iteratively applies a back-tracing procedure to find the /spl lscr/ best paths.

An error exponent for woven convolutional codes (WCC) with one tailbiting component code is derived. This error exponent is compared with that of the original WCC. It is shown that for WCC with outer warp, a better error exponent is obtained if the inner code is terminated with the tailbiting method. Furthermore, it is shown that the decoding error probability decreases exponentially with the square of the memory of the constituent convolutional encoders, while the decoding complexity grows exponentially only with the memory.

An iterative decoding scheme for woven convolutional codes is presented. It operates in a window sliding over the received sequence. This exploits the nature of convolutional codewords as infinite sequences and reflects the concept of considering convolutional encoding and decoding as a continuous process. The decoder is analyzed in terms of decoding delay and decoding complexity. Its basic building block is a symbol-by-symbol a posteriori probability (APP) decoder for convolutional codes, which is a windowed variant of the well-known Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm. Additional interleaving for the woven constructions is introduced by employing convolutional scramblers. It is shown that row-wise random interleaving preserves the lower bound on the free distance of the original woven constructions. Based on the properties of the interleavers, new lower bounds on the free distance of woven constructions with both outer warp and inner warp are derived. Simulation results for woven convolutional codes with and without additional interleaving are presented.

The slope is an important distance parameter for a convolutional code. It can be used to obtain a lower bound on the active burst distance and in this respect essentially determines the error-correcting capability of the code. An upper bound on the slope of rate R=b/c convolutional codes is derived. A new family of convolutional codes, called the maximum slope (MS) code family, is introduced. Tables for rate R=1/2 MS codes with memory 1/spl les/m/spl les/6 are presented. Additionally, some new rate R=(c-1)/c, 3/spl les/c/spl les/6, punctured convolutional codes with rate R=1/2 optimum free distance (OFD) and MS mother codes are presented. Simulation results for the bit error performance of serially concatenated turbo codes with MS component codes are presented.

Tailbiting is an attractive method to terminate convolutional codes without reducing the code rate. Maximum-likelihood and exact a posteriori probability decoding of tailbiting codes implies, however, a large computational complexity. Therefore, suboptimal decoding methods are often used in practical coding schemes. It is shown that suboptimal decoding methods work better when the slope of the active distances of the generating convolutional encoder is large. Moreover, it is shown that considering quasi-cyclic shifts of the received channel output can increase the performance of suboptimal tailbiting decoders. The findings are most relevant to tailbiting codes where the number of states is not small relative to the block length.

Encoders for convolutional codes with large free distances can be constructed by combining several less powerful convolutional encoders. This paper is devoted to constructions in which the constituent convolutional codes are woven together in a manner that resembles the structure of a fabric. The general construction is called twill and it is described together with two special cases, viz., woven convolutional encoders with outer warp and with inner warp. The woven convolutional encoders inherit many of their structural properties, such as minimality and catastrophicity, from their constituent encoders. For all three types of woven convolutional codes upper and lower bounds on their free distances as well as lower bounds on the active distances of their encoders are derived.

We consider convolutional and block encoding schemes which are variations of woven codes with outer warp. We propose methods to evaluate the distance characteristics of the considered codes on the basis of the active distances of the component codes. With this analytical bounding technique, we derived lower bounds on the minimum (or free) distance of woven convolutional codes, woven block codes, serially concatenated codes, and woven turbo codes. Next, we show that the lower bound on the minimum distance can be improved if we use designed interleaving with unique permutation functions in each row of the warp of the woven encoder. Finally, with the help of simulations, we get upper bounds on the minimum distance for some particular codes and then investigate their performance in the Gaussian channel. Throughout this paper, we compare all considered encoding schemes by means of examples, which illustrate their distance properties.

In this correspondence, the error exponents and decoding complexity of binary woven convolutional codes with outer and inner warp are studied. It is shown that for both constructions an error probability that is exponentially decreasing with the memory of the woven convolutional codes can be achieved with a nonexponentially increasing decoding complexity. Furthermore, the error exponent for woven convolutional codes with inner warp is larger than the one for woven convolutional codes with outer warp.

We show that the generator matrix of a generalized concatenated code (GCC code) of order L consists of L submatrices, where the lth submatrix is the Kronecker product of the generator matrices of the lth inner code and the lth outer code. In a similar way we show that the parity-check matrix of a generalized error location code (GEL code) of order L consists of L submatrices, where the lth submatrix is the Gronecker product of the parity-check matrices of the lth inner code and the lth outer code. Then we use these defining matrices to show that for any GCC code there exists an equivalent GEL code and vice versa.

A family of active distance measures for general convolutional codes is defined. These distances are generalizations of the extended distances introduced by Thommesen and Justesen (1983) for unit memory convolutional codes. It is shown that the error correcting capability of a convolutional code is determined by the active distances. The ensemble of periodically time-varying convolutional codes is defined and lower bounds on the active distances are derived for this ensemble. The active distances are very useful in the analysis of concatenated convolutional encoders.

In this correspondence the error exponent and the decoding complexity of binary woven convolutional codes with outer warp and with binary convolutional codes as outer and inner codes are studied. It is shown that an error probability that is exponentially decreasing with the product of the outer and inner code memories can be achieved with a nonexponentially increasing decoding complexity.

A novel construction method is presented for array codes correcting a single rectangular error cluster of size b/sub 1//spl times/b/sub 2/ or less. Encoding is done in such a way that parity check symbols are calculated row-or columnwise which are a word of a one-dimensional code correcting a phased burst. These parity check symbols are not transmitted but can be calculated by the receiver. Corresponding decoding algorithms are given. A code is constructed with maximum size n/sub 1/=b/sub 1/2/sup b2/, n/sub 2/=b/sub 2/2/sup b1/, and r=3b/sub 1/b/sub 2/ redundancy symbols which is close to the generalized Singleton bound r/spl ges/2b/sub 1/b/sub 2/. Its encoding and decoding complexity are low.

We study the performance of MC-FDMA when applied in mobile communications. We describe two MC-FDMA strategies with control from the base station, telling the users which channels to use. Then we describe a strategy without control from the base station, where the users randomly select their subchannels. For this strategy we describe a joint-detection decoding algorithm with interference cancellation which increases the performance. We compute the optimum number of selected subchannels per user for the random strategy, and describe an adaptive optimum random strategy. In order to compare the different strategies we compute the user capacity, that is the amount of information per transmitted block. Since the number of users in cities is bigger, we consider typical urban channels (TUX) for our simulations.

Soft-decision maximum-likelihood decoding of convolutional codes using the Viterbi algorithm with a syndrome trellis is proposed. The parity check matrix of a convolutional code is used to construct the trellis. This trellis is minimal. The number of operations for the decoding of one block of a q-ary rate k/n convolutional code is /spl sim/nq/sup min(k,n-k)/q/sup /spl nu//, where /spl nu/ is the memory size of the code. When the code rate satisfies k/n> 1/2 , the proposed algorithm is simpler than the classical Viterbi algorithm that has complexity /spl sim/nq/sup k/q/sup /spl nu//.>

The minimum distance of concatenated codes with Reed-Solomon outer codes and convolutional inner codes is studied. For suitable combinations of parameters the minimum distance can be lower-bounded by the product of the minimum distances of the inner and outer codes. For a randomized ensemble of concatenated codes a lower bound of the Gilbert-Varshamov type is proved.>