This paper presents a codeword metric calculation scheme for two step joint decoding of block coded signals in overloaded multiple-input multiple-output (MIMO) orthogonal frequency division multiplexing (OFDM) systems. A two step joint decoding scheme has been proposed for the complexity reduction as compared to joint maximum likelihood decoding in overloaded MIMO systems. Outer codes are widely used in wireless LANs such as IEEE802.11n. However, the two step joint decoding has not been combined with an outer code. In the first step of the two step joint decoding candidate codewords for metric calculation in the second step are selected. The selection of the candidate codewords in the inner block code may not always be able to provide the metric of a binary coded symbol for the outer code. Moreover, a bit flipping based codeword selection scheme in the two step joint decoding may not always provide the second best candidate codeword. Thus, in the proposed scheme the metric of the binary coded symbol calculated in the first step is reused in the second step of two step joint decoding. It is shown that the two step joint decoding with the proposed metric calculation scheme achieves better performance than that of the joint decoding with the bit flipping based codeword calculation scheme and reduces the complexity by about 0.013 for 4 signal streams with the cost of bit error rate degradation within 0.5dB.

This paper presents a low complexity joint decoding scheme of block coded signals in an overloaded multiple-input multiple-output (MIMO) orthogonal frequency division multiplexing (OFDM) system. In previous literature, a joint maximum likelihood decoding scheme of block coded signals has been evaluated through theoretical analysis. The diversity gain with block coding prevents the performance degradation induced by signal multiplexing. However, the computational complexity of the joint decoding scheme increases exponentially with the number of multiplexed signal streams. Thus, this paper proposes a two step joint decoding scheme for block coded signals. The first step of the proposed scheme calculates metrics to reduce the number of the candidate codewords using decoding based on joint maximum likelihood symbol detection. The second step of the proposed scheme carries out joint decoding on the reduced candidate codewords. It is shown that the proposed scheme reduces the complexity by about 1/174 for 4 signal stream transmission.

In recent wireless communication systems, security is ensured mainly in the upper-layer techniques such as a password or a cryptography processing. However, security needs not be restricted to the upper-layer and the addition of physical-layer security also would yield a much more robust system. Therefore, in this paper, we exploit chaos communication and propose a chaos multiple-input multiple-output (MIMO) transmission scheme which achieves physical-layer security and additional channel-coding gain. A chaotic modulation symbol is multiplied to the data to be transmitted at each MIMO antenna to exploit the MIMO antenna diversity, and at the receiver, the joint MIMO detection and chaos decoding is done by maximum likelihood decoding (MLD). The conventional chaos modulation suffers from bit error rate (BER) performance degradation, while the coding gain is obtained in the proposed scheme by the chaos modulation in MIMO. We evaluate the performances of the proposed scheme by an analysis and computer simulations.

In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.

We consider the reliability-based heuristic search methods for maximum likelihood decoding, which generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Some studies have proposed methods for reducing the space complexity of these algorithms, which is crucially large for long block codes at medium to low signal to noise ratios of the channel. In this paper, we propose a new method for reducing the time complexity of generating candidate codewords by storing some already generated candidate codewords. Simulation results show that the increase of memory size is small.

Irregular Low-Density Parity-Check (LDPC) codes generally achieve better performance than regular LDPC codes at low Eb/N0 values. They have, however, higher error floors than regular LDPC codes. With respect to the construction of the irregular LDPC code, it can achieve the trade-off between the performance degradation of low Eb/N0 region and lowering error floor. It is known that a decoding algorithm can achieve very good performance if it combines the Ordered Statistic Decoding (OSD) algorithm and the Log Likelihood Ratio-Belief Propagation (LLR-BP) decoding algorithm. Unfortunately, all the codewords obtained by the OSD algorithm satisfy the parity check equation of the LDPC code. While we can not use the parity check equation of the LDPC code to stop the decoding process, the wrong codeword that satisfies the parity check equation raises the error floor. Once a codeword that satisfies the parity check equation is generated by the LLR-BP decoding algorithm, we regard that codeword as the final estimate and halt decoding; the OSD algorithm is not performed. In this paper, we propose a new encoding/decoding scheme to lower the error floor created by irregular LDPC codes. The proposed encoding scheme encodes information bits by Cyclic Redundancy Check (CRC) and LDPC code. The proposed decoding scheme, which consists of the LLR-BP decoding, CRC check, and OSD decoding, detects errors in the codewords obtained by the LLR-BP decoding algorithm and the OSD decoding algorithm using the parity check equations of LDPC codes and CRC. Computer simulations show that the proposed encoding/decoding scheme can lower the error floor of irregular LDPC codes.

The reliability-based heuristic search methods for maximum likelihood decoding (MLD) generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Test error patterns are stored in lists and its space complexity is crucially large for MLD of long block codes. Based on the decoding algorithms both of Battail and Fang and of its generalized version suggested by Valembois and Fossorier, we propose a new method for reducing the space complexity of the heuristic search methods for MLD including the well-known decoding algorithm of Han et al. If the heuristic function satisfies a certain condition, the proposed method guarantees to reduce the space complexity of both the Battail-Fang and Han et al. decoding algorithms. Simulation results show the high efficiency of the proposed method.

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.

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.

New algorithms for the soft-decision and the hard-decision maximum likelihood decoding (MLD) for binary linear block codes are proposed. It has been widely known that both MLD can be regarded as an integer programming with binary arithmetic conditions. Recently, Conti and Traverso have proposed an efficient algorithm which uses Grobner bases to solve integer programming with ordinary integer arithmetic conditions. In this paper, the Conti-Traverso algorithm is extended to solve integer programming with modulo arithmetic conditions. We also show how to transform the soft-decision and the hard-decision MLD to integer programming for which the extended Conti-Traverso algorithm is applicable.

In this paper, we present a new soft-decision iterative decoding algorithm using an efficient minimum distance search (MDS) algorithm. The proposed MDS algorithm is a top-down and recursive MDS algorithm, which finds a most likely codeword among the codewords at the minimum distance of the code from a given codeword. A search is made in each divided section by a "call by need" from the upper section. As a consequence, the search space and computational complexity are reduced significantly. The simulation results show that the proposed decoding algorithm achieves near error performance to the maximum likelihood decoding for any RM code of length 128 and suboptimal for the (256, 37), (256, 93) and (256, 163) RM codes.

In this semi-tutorial paper, the reliability-based decoding approaches using the reprocessing of the most reliable information set are investigated. This paper somehow homogenizes and compares former different studies, hopefully improving the overall transparency, and completing each one with tricks provided by the others. A couple of sensible improvements are also suggested. However, the main goal remains to integrate and compare recent works based on a similar general approach, which have unfortunately been performed in parallel without much efforts of comparison up to now. Their respective (dis)advantages, especially in terms of average or maximum complexity are elaborated. We focus on suboptimum decoding while some works to which we refer were developed for maximum likelihood decoding (MLD). No quantitative error performance analysis is provided, although we are in a position to benefit from some qualitative considerations, and to compare different strategies in terms of higher or lower expected error performances for a same complexity. With simulations, however, it turns out that all considered approaches perform very closely to each other, which was not especially obvious at first sight. The simplest strategy proves also the fastest in terms of CPU-time, but we indicate ways to implement the other ones so that they get very close to each other from this point of view also. On top of relying on the same intuitive principle, the studied algorithms are thus also unified from the point of view of their error performances and computational cost.

Y. S. Han et al. have proposed an efficient maximum likelihood decoding (MLD) algorithm using A* algorithm which is the graph search method. In this paper, we propose a new MLD algorithm for linear block codes. The MLD algorithm proposed in this paper improves that given by Han et al. utilizing codewords of dual codes. This scheme reduces the number of generated codewords in the MLD algorithm. We show that the complexity of the proposed decoding algorithm is reduced compared to that given by Han et al. without increasing the probability of decoding error.

A recursive maximum likelihood decoding (RMLD) algorithm is more efficient than the Viterbi algorithm. The decoding complexity of the RMLD algorithm depends on the recursive sectionalization. The recursive sectionalization which minimizes the decoding complexity is called the optimum sectionalization. In this paper, for a class of non-linear codes, called rectangular codes, it is shown that a near optimum sectionalization can be obtained with a dynamic programming approach. Furthermore, for a subclass of rectangular codes, called C-rectangular codes, it is shown that the exactly optimum sectionalization can be obtained with the same approach. Following these results, an efficient algorithm to obtain the optimum sectionalization is proposed. The optimum sectionalizations for the minimum weight subcode of some Reed-Muller codes and of a BCH code are obtained with the proposed algorithm.

Tail-biting trellises of linear and nonlinear block codes are addressed. We refine the information-theoretic approach of a previous work on conventional trellis representation, and show that the same ideas carry over to tail-biting trellises. We present lower bounds on the state and branch complexity profiles of these representations. These bounds are expressed in terms of mutual information between different portions of the code, and they introduce the notions of superstates and superbranches. For linear block codes, our bounds imply that the total number of superstates, and respectively superbranches, of a tail-biting trellis of the code cannot be smaller than the total number of states, and respectively branches, of the corresponding minimal conventional trellis, though the total number of states and branches of a tail-biting trellis is usually smaller than that of the conventional trellis. We also develop some improved lower bounds on the state complexity of a tail-biting trellis for two classes of codes: the first-order Reed-Muller codes and cyclic codes. We show that the superstates and superbranches determine the Viterbi decoding complexity of a tail-biting trellis. Thus, the computational complexity of the maximum-likelihood decoding of linear block codes on a tail-biting trellis, using the Viterbi algorithm, is not smaller than that of the conventional trellis of the code. However, tail-biting trellises are beneficial for suboptimal and iterative decoding techniques.

Recently, a trellis-based recursive maximum likelihood decoding (RMLD) algorithm has been proposed for decoding binary linear block codes. This RMLD algorithm is computationally more efficient than the Viterbi decoding algorithm. However, the computational complexity of the RMLD algorithm depends on the sectionalization of a code trellis. In general, minimization of the computational complexity results in non-uniform sectionalization of a code trellis. From implementation point of view, uniform sectionalization of a code trellis and regularity among the trellis sections are desirable. In this paper, we apply the RMLD algorithm to a class of codes which are transitive invariant. This class includes Reed-Muller (RM) codes, the extended and permuted BCH (EBCH) codes and their subcodes. For this class of codes, the binary uniform sectionalization of a code trellis results in the following regular structure. At each step of decoding recursion, the metric table construction procedure is applied uniformly to all the sections and the size and structure of each metric table are the same. This simplifies the implementation of the RMLD algorithm. Furthermore, for all RM codes of lengths 64 and 128 and EBCH codes of lengths 64 and 128 with relatively low rate, the computational complexity of the RMLD algorithm based on the binary uniform sectionalization of a code trellis is almost the same as that based on an optimum sectionalization of a code trellis.

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.

This paper presents two new maximum likelihood decoding (MLD) algorithms for linear codes over Z-channel, which are much more efficient than conventional exhaustive algorithms for high rate codes. In the proposed algorithms, their complexities are reduced by employing the projecting set Cs of the code, which is determined by the "projecting" structure of the code. Space and computational complexities of algorithms mainly depend upon the size of Cs which is usually several times smaller than the total number of codewords. It is shown that the upper bounds on computational complexities of decoding algorithms are in proportion to the number of parity bits and the distance between an initial estimate of the codeword and the received word, respectively, while space complexities of them are equal to the size of Cs. Lastly, numerical examples clarify the average computational complexities of the proposed algorithms, and the efficiency of these algorithms for high rate codes is confirmed.