In channel decoding, a decoder with suboptimal metrics may be used because of the uncertainty of the channel statistics or the limitations of the decoder. In this case, the decoding metric is different from the actual channel metric, and thus it is called mismatched decoding. In this paper, applying the technique of the DS2 bound, we derive an upper bound on the error probability of mismatched decoding over a regular channel for the ensemble of linear block codes, which was defined by Hof, Sason and Shamai. Assuming the ensemble of random linear block codes defined by Gallager, we show that the obtained bound is not looser than the conventional bound. We also give a numerical example for the ensemble of LDPC codes also introduced by Gallager, which shows that our proposed bound is tighter than the conventional bound. Furthermore, we obtain a single letter error exponent for linear block codes.

In this letter, we investigate tight analytical and asymptotic upper bounds for bit error rate (BER) of constitutional codes over exponentially correlated Nakagami-m fading channels. Specifically, we derive the BER expression depending on an exact closed-form formula for pairwise error event probabilities (PEEP). Moreover, the corresponding asymptotic analysis in high signal-to-noise ratio (SNR) regime is also explored, which is verified via numerical results. This allows us to have explicit insights on the achievable coding gain and diversity order.

In decision feedback scheme, Forney's decision criterion (Forney's rule: FR) is optimal in the sense that the Neyman-Pearson's lemma is satisfied. Another prominent criterion called LR+Th was proposed by Hashimoto. Although LR+Th is suboptimal, its error exponent is shown to be asymptotically equivalent to that of FR by random coding arguments. In this paper, applying the technique of the DS2 bound, we derive an upper bound for the error probability of LR+Th for the ensemble of linear block codes. Then we can observe the new bound from two significant points of view. First, since the DS2 type bound can be expressed by the average weight distribution whose code length is finite, we can compare the error probability of FR with that of LR+Th for the fixed-length code. Second, the new bound elucidates the relation between the random coding exponents of block codes and those of linear block codes.

Recently, Hof et al. extended the type-2 Duman and Salehi (DS2) bound to generalized decoding, which was introduced by Forney, with decision criterion FR. From this bound, they derived two significant bounds. One is the Shulman-Feder bound for generalized decoding (GD) with the binary-input output-symmetric channel. The other is an upper bound for an ensemble of linear block codes, by applying the average complete weight distribution directly to the DS2 bound for GD. For the Shulman-Feder bound for GD, the authors derived a condition under which an upper bound is minimized at an intermediate step and show that this condition yields a new bound which is tighter than Hof et al.'s bound. In this paper, we first extend this result for non-binary linear block codes used over a class of symmetric channels called the regular channel. Next, we derive a new tighter bound for an ensemble of linear block codes, which is based on the average weight distribution.

In this paper, the Voronoi region of the transmitted codeword is employed to improve the sphere bound on the maximum-likelihood decoding (MLD) performance of binary linear block codes over additive white Gaussian noise (AWGN) channels. We obtain the improved sphere bounds both on the frame-error probability and the bit-error probability. With the framework of the sphere bound proposed by Kasami et al., we derive the conditional decoding error probability on the spheres by defining a subset of the Voronoi region of the transmitted codeword, since the Voronoi regions of a binary linear block code govern the decoding error probability analysis over AWGN channels. The proposed bound improves the sphere bound by Kasami et al. and the sphere bound by Herzberg and Poltyrev. The computational complexity of the proposed bound is similar to that of the sphere bound by Kasami et al.

This paper generalizes parallel error correcting codes proposed by Ahlswede et al. over a new type of multiple access channel called parallel error channel. The generalized parallel error correcting codes can handle with more errors compared with the original ones. We show construction methods of independent and non-independent parallel error correcting codes and decoding methods. We derive some bounds about the size of respective parallel error correcting codes. The obtained results imply a single parallel error correcting code can be constructed by two or more kinds of error correcting codes with distinct error correcting capabilities.

This paper considers the optimal generator matrices of a given binary cyclic code over a binary symmetric channel with crossover probability p→0 when the goal is to minimize the probability of an information bit error. A given code has many encoder realizations and the information bit error probability is a function of this realization. Our goal here is to seek the optimal realization of encoding functions by taking advantage of the structure of the codes, and to derive the probability of information bit error when possible. We derive some sufficient conditions for a binary cyclic code to have systematic optimal generator matrices under bounded distance decoding and determine many cyclic codes with such properties. We also present some binary cyclic codes whose optimal generator matrices are non-systematic under complete decoding.

Reliability-based maximum likelihood decoding (MLD) algorithms of linear block codes have been widely studied. These algorithms efficiently search the most likely codeword using the generator matrix whose most reliable and linearly independent k (dimension of the code) columns form the identity matrix. In this paper, conditions for omitting unnecessary metrics computation of candidate codewords are derived in reliability-based MLD algorithms. The proposed conditions utilize an order relation of binary vectors. A simple method for testing if the proposed conditions are satisfied is devised. The method for testing proposed conditions requires no real number operations and, consequently, the MLD algorithm employing this method reduces the number of real number operations, compared to known reliability-based MLD algorithms.

A new algorithm for the LogMAP decoding of linear block codes is considered. The decoding complexity is evaluated analytically and by computer simulation. The proposed algorithm is an improvement of the recursive LogMAP algorithm proposed by the authors. The recursive LogMAP algorithm is more efficient than the BCJR algorithm for low-rate codes, but the complexity grows considerably large for high-rate codes. The aim of the proposed algorithm is to solve the complexity explosion of the recursive LogMAP algorithm for high-rate codes. The proposed algorithm is more efficient than the BCJR algorithm for well-known linear block codes.

Several reliability based code search algorithms for maximum likelihood decoding have been proposed. These algorithms search the most likely codeword, using the most reliable information set where the leftmost k (the dimension of code) columns of generator matrix are the most reliable and linearly independent. Especially, D. Gazelle and J. Snyders have proposed an efficient decoding algorithm and this algorithm requires small number of candidate codewords to find out the most likely codeword. In this paper, we propose new efficient methods for both generating candidate codewords and computing metrics of candidate codewords to obtain the most likely codeword at the decoder. The candidate codewords constructed by the proposed method are identical those in the decoding algorithm of Gazelle et al. Consequently, the proposed decoding algorithm reduces the time complexity in total, compared to the decoding algorithm of Gazelle et al. without the degradation in error performance.

This paper presents an iterative algorithm for decoding product codes based on syndrome decoding of component codes. This algorithm is devised to achieve an effective trade-off between error performance and decoding complexity. A simplified list decoding algorithm, which uses a modified syndrome decoding method, for linear block codes is devised to deliver soft outputs for iterative decoding of product codes. By adjusting the size of the list, the decoder can achieve a proper trade-off between decoding complexity and performance. Compared to the other iterative decoding algorithms for product codes, the proposed algorithm has lower complexity while offers at least the same performance, which is demonstrated by analyses and simulations. The proposed algorithm has been simulated for BPSK and 16-QAM modulations over both the additive white Gaussian noise (AWGN) and Raleigh fading channels. This paper also presents an efficient scheme for applying product codes and their punctured versions. This scheme can be implemented with variable packet size and channel data block.

This paper treats weight distributions of the coset leaders of binary linear block codes. We first present a method for computing the weight distribution of the coset leaders of a given code using two tables each of which stores the weights of the coset leaders of a related code of the code. Then, the weight distributions of the coset leaders of the (N,K) Reed-Muller codes, binary primitive BCH codes, and their extended codes with N 128 and 29 N-K 42 that are obtained by using the computing method are given.

An algorithm for finding the optimal sectionalization for sectionalized trellises with respect to distinct optimality criterions was presented by Lafourcade and Vardy. In this paper, for linear block codes, we give a direct method for finding the optimal sectionalization when the optimality criterion is chosen as the total number |E| of the edges, the expansion index |E|-|V|+1, or the quantity 2|E|-|V|+1, only using the dimensions of the past and future sub-codes. A more concrete method for determining the optimal sectionalization is given for the Reed-Muller codes with the natural lexicographic coordinate ordering.

New algorithms for the MAP (also known as the APP) decoding and the MAX-LogMAP decoding of linear block codes are presented. The algorithms are devised based on the structural properties of linear block codes, and succeeds in reducing the decoding complexity without degrading the error performance. The proposed algorithms are suitable for the parallel and pipeline processing which improves the throughput of the decoder. To evaluate the decoding complexity of the proposed algorithms, simulation results for some well-known codes are presented. The results show that the algorithms are especially efficient than the conventional BCJR-based algorithms for codes whose rate are relatively low.

In this paper, soft decision decoding of linear block codes based on the reprocessing of several information sets is considered. These information sets are chosen according to the reliability measures of the received symbols and constructed from the most reliable information set, referred to as the most reliable basis. Each information set is then reprocessed by a multi-stage decoding algorithm until either the optimum error performance, or a desired level of error performance is achieved. General guidelines for the trade-offs between the number of information sets to be processed, the number of computations for reprocessing each information set, and the error performance to be achieved are provided. It is shown that with a proper selection of few information sets, low-complexity near-optimum soft decision decoding of relatively long block codes (64 N 128) can be achieved with significant reduction in computation complexity with respect to other known algorithms. This scheme, which generalizes the reprocessing of the most reliable basis with the ordered statistic algorithm proposed by Fossorier and Lin, is particularly efficient for codes with rate R 1/2.

In this paper cosets of the second order Reed-Muller code of length 2m, denoted RMm,2, in the third order Reed-Muller code of the same length, denoted RMm,3, are studied. The set of cosets, RMm,3/RMm,2 is partitioned into blocks. Two cosets are in the same block, if and only if there is a transformation in the general linear group by which one coset is transformed into the other. Two cosets in the same block have the same weight distribution. For the code length less than or equal to 128, the representative coset leader of each block is presented and the weight distribution of cosets in the block is computed. By using these results, the extended code of a cyclic code of length 128 between RM7,2 and RM7,3 can be decomposed into a set of cosets in RM7,3/RM7,2, and its weight distribution can be derived. Several cyclic codes to length 127 are shown to be equivalent and some new linear unequal error protection codes are found.

This letter is concerned with the evaluation of the average computational complexity of the maximum likelihood decoding of a linear block code using its trellis diagram. Each section of the L-section minimal trellis diagram for a linear block code consists of parallel components which are structurally identical subgraphs without cross connection between them. A parallel component is also known to be decomposed into subgraphs, and a decoding algorithm by using the structure of the subgraphs of parallel components was proposed, and an upper bound on the worst case computational complexity was derived. In this letter, the average computational complexity of the decoding algorithm is evaluated by computer simulation. We evaluated the average numbers of additions and comparisons performed in the decoding algorithm for example codes, (64,45) extended and permuted binary primitive BCH code, the third order Reed-Muller (64,42) code and its (64,40) subcode. It is shown that the average numbers are much smaller than those for the worst case, and hence the decoding algorithm is efficient when the number of sections, L, is small, say 4 or 8, for the example codes. Especially, for the (64,45) extended binary primitive BCH code with L4, the average numbers of additions and comparisons in the decoding algorithm for finding the survivor's metric of each state after finding the smallest metric among parallel branches are about 1/50 and 17/100 of those in the conventional exhaustive search, respectively. The number of additions and comparisons by the conventional search for all the example codes is smallest when L is 4. As a result, the decoding algorithm with L4 gives the smallest number of operations among those decoding methods considered here.

The word error probability of linear block codes is computed for diversity systems with maximal ratio combining in mobile communications with three decoding algorithms: error correction (EC), error/erasure correction (EEC), and maximum likelihood (ML) soft decoding algorithm. Ideal interleaving is assumed. EEC gives 0.1-1.5dB gain over EC. The gain of EEC over EC decreases as the number of diversity channels increases. ML soft gives 1.8-5.5dB gain over EC.

In an earlier paper, we have shown that each section of the L-section minimal trellis diagram for a linear block code consists of parallel and structurally identical (except branch labels) subgraphs without cross connections. These parallel subgraphs are called parallel components of the section. In this paper, it is shown that if the sets of path label sequences of two parallel components have a common sequence, then the parallel components have the same branch labels, and the number of parallel components with the same branch labels in each section and the detail structure of each parallel component up to its branch labels are analyzed and expressed in terms of the dimensions of specific linear codes related to the given code. As an example, the 2i-section minimal trellis diagram for a Reed-Muller code is analyzed. Complexity measures of soft-decision maximum likelihood decoding for binary linear block codes are also discussed.