IEEE Communications Letters

Using the Fourier transform to compute the weight distribution of a binary linear block code

Pragat Chaudhari, Amir Keyvan Khandani

Published Jan 1, 2001• 4 citations

Abstract

An analytical technique is presented to compute the weight distribution of a linear block code by performing a Fourier analysis involving certain matrices obtained from the code trellis. The proposed method is general, easy to implement, and can be used without having to traverse the trellis or carry out tedious analytical work. The introduced technique can be used as a flexible analytical tool to capture the weight structure of the code with application to problems involving analysis and/or design.

DOI: 10.1109/4234.901815

Related papers

New Methods for Computing the Weight Distribution of a Linear Block Code Based on Its Trellis Structure

Toru Fujiwara, Tadao Kasami, Yoshihisa Desaki +1 more

International Symposium on Information Theory and its ApplicationsJan 1, 19943 citations

A low-weight trellis-based iterative soft-decision decoding algorithm for binary linear block codes

Takuya Koumoto, T. Takata, Tadao Kasami +1 more

This paper presents a new low-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. The algorithm is devised based on a set of optimality conditions and the generation of a sequence of candidate codewords for an optimality test. The initial candidate codeword is generated by a simple decoding method. The subsequent candidate codewords, if needed, are generated by a chain of low-weight trellis searches, one at a time. Each search is conducted through a low-weight trellis diagram centered around the latest candidate codeword and results in an improvement over the previous candidate codewords that have been already tested. This improvement is then used as the next candidate codeword for a test of optimality. The decoding iteration stops whenever a candidate codeword is found to satisfy a sufficient condition on optimality or the latest low-weight trellis search results in a repetition of a previously generated candidate codeword. A divide-and-conquer technique is also presented for codes that are not spanned by their minimum-weight codewords. The proposed decoding algorithm has been applied to some well-known codes of lengths 48, 64, and 128. Simulation results show that the proposed algorithm achieves either practically optimal error performance for the example codes of length 48 and 64 or near optimal error performance for the (128, 29, 32) RM code with a significant reduction in computational decoding complexity.

IEEE Transactions on Information TheoryMar 1, 199913 citations

A Probabilistic Algorithm for Computing the Weight Distribution of LDPC Codes

Masanori Hirotomo, Masami Mohri, Masakatu Morii

Low-density parity-check (LDPC) codes are linear block codes defined by sparse parity-check matrices. The codes exhibit excellent performance under iterative decoding, and the weight distribution is used to analyze lower error probability of their decoding performance. In this paper, we propose a probabilistic method for computing the weight distribution of LDPC codes. The proposed method efficiently finds low-weight codewords in a given LDPC code by using Stern's algorithm, and stochastically computes the low part of the weight distribution from the frequency of the found codewords. It is based on a relation between the number of codewords with a given weight and the rate of generating the codewords in Stern's algorithm. In the numerical results for LDPC codes of length 504, 1008 and 4896, we could compute the weight distribution by the proposed method with greater accuracy than by conventional methods.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesJan 1, 20096 citations

An Iterative Soft-Decision Decoding Algorithm

Shu Wen Lin, Takuya Koumoto, Toyoo Takata +1 more

This paper presents a new minimum-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. Simulation results for the RM(64,22), EBCH(64,24), RM(64,42) and EBCH(64,45) codes show that the proposed decoding algorithm achieves practically (or near) optimal error performance with significant reduction in decoding computational complexity. The average number of search iterations is also small even for low signal-to-noise ratio.

Jul 10, 19967 citations

On computing the performance of linear block codes in nonindependent channel errors

Hans‐Jürgen Zepernick

We present an analytical method to compute the exact performance of algebraically decoded linear block codes in nonindependent channel errors. Performance is computed by rating decoding events. The block error distribution and the coset probabilities are of fundamental interest. A recursion in matrix notation is taken to compute the block error distribution. By using an automata model of the channel-decoder-cascade, coset probabilities can be computed directly in an original domain. Alternatively, the analysis can be performed in a spectral domain having a simpler structure. The relationship between both domains is given by a Walsh-Hadamard transform. Aspects of implementation are discussed and examples are presented to illustrate the efficiency of the method.

International Conference on CommunicationsDec 23, 20023 citations

Optimal encoding, trellis structure, and normalized weight of linear block codes.

Houshou Chen

This thesis concentrates on studying three problems in error-correcting codes: optimal encoding, trellis structure, and normalized weight of linear block codes. In general, the research in error-correcting codes can be roughly classified into coding practice and coding theory. The problems in coding practice focus on codes and decoders with more attention on the subject of the tradeoffs between performance and complexity, e.g., soft-decision decoding, bit error probability, or trellis of the codes. On the other hand, coding theory concentrates on the structure of codes based on sophisticated mathematical techniques, with little concern for the decoding complexity, e.g., coset weight distribution, algebraic constructions, or bounds on possible parameters of the codes. In this dissertation, we will present three fundamental topics in coding practice: optimal encoding of linear block codes for bit error probability, trellis structure of linear block codes for trellis-based decoding, and normalized weight of block coded modulation for bandwidth efficient communication systems. The central theme of the thesis is to transform the problems of the above three topics in coding practice into problems in coding theory and to develop the theory associated with the problems. Much of this thesis is devoted to studying what 'optimal' means in different contexts. In summary, we investigated the optimal information bit encoding of a given linear block code for minimizing the probability of an information bit error, with the goal of determining an optimal generator matrix by using the structure of the code. We showed that many natural codes have systematic optimal generator matrices in the quiet region. We analyzed the trellis structure of a self-dual code C to minimize the trellis complexity of the code by considering all equivalent codes of C, with the goal of reducing the soft-decision decoding complexity via permutations on the codeword coordinates. We determined the length/dimension profile of all eight [32, 16, 8] self-dual codes, and find their corresponding optimum permutations. We examined the performance gains achievable by adding interblock memory to block coded modulation systems, with the goal of finding the best codes for normalized distance rather than Hamming distance. We found a large number of best codes for normalized distance for the cases of practical interest.

Jan 1, 19993 citations