This paper examines the problem of finding an optimal generator matrix of a linear block code C over a binary symmetric channel in the quiet region (i.e., crossover probability p/spl rarr/0) when the goal is to minimize the probability of an information bit error. We present an infinite class of cyclic codes whose optimal generator matrices are nonseparable. The problem is linked to whether the minimum weight codewords form a basis of C.
This paper examines the problem of finding an optimal generator matrix of a linear block code C over a binary symmetric channel in the quiet region (i.e., crossover probability p/spl rarr/0) when the goal is to minimize the probability of an information bit error. We present an infinite class of cyclic codes whose optimal generator matrices are nonseparable. The problem is linked to whether the minimum weight codewords form a basis of C.
This paper considers the optimal generator matrices of a binary cyclic code over a binary symmetric channel with crossover probability p rarr 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. We derive some sufficient conditions for a binary cyclic code to have systematic optimal generator matrices under bounded distance decoding and determine many binary cyclic codes satisfying these properties.
We consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range p/spl isin/[p/sub i-1/, p/sub i/]. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the first region [0, p/sub 1/] and the region [p/sub max/, 1/2] for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p>p/sub max/ is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. The optimal decoding strategy varies with the generator matrix used in general, but it is demonstrated that the optimal generator matrix is separable when d/sup /spl perp//>2. The results are shown to extend in a natural way to the case where the goal is to minimize the probability that arbitrary collections of information bits are in error. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.>
Decoding rules for linear block codes used over binary symmetric channels with crossover probability p when the goal is to minimize the probability that sub-blocks of information bits are in error are considered, with application to the (24,12,8) Golay code. (The optimal rules to minimize the probability of individual bits being in error are known for all p.) The results require detailed knowledge of the weight enumerators of given sub codes, which can be calculated from knowledge of the orbit and coset structure of the code. It is interesting that in all cases examined, the rule in decoding a block given the coset received is to select the symbol that is optimal as p → 0 or the symbol that is optimal as p → 1/2, depending on p.
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.
The number of iterations of an iterative optimal or suboptimal decoding scheme for binary linear block codes without any effect on its error performance can be reduced by testing a sufficient condition on the optimality of a candidate codeword. The least stringent sufficient condition on the optimality of a decoded codeword is investigated under the assumption that the available information on the code is restricted to (1) the minimum weight or the distance profile and (2) for a given positive integer h, h or fewer already generated candidate codewords. The least stringent sufficient conditions of optimality for 1/spl les/h/spl les/3 are presented. Cond/sub 1/ is the same as the one given by Taipale and Pursley (1991), Cond/sub 2/ is less stringent than the one given by Kaneko, Nishijima, Inazumi and Hirasawa (see IEEE Trans. Inform. Theory, vol.IT-40, no.3, p.320, 1994), and Cond/sub 1/ and Cond/sub 2/ are derived from Cond/sub 3/ as special cases. These conditions can be used effectively to save computer simulation time for evaluating the error probability for maximum likelihood decoding.
The performance of optimum linear block codes has been examined by computer simluation, and the error distribution at the decoder output, the block-error probability and the bit-error probability have been determined for the codes when they are used on a binary symmetric channel with random errors. A table showing the distribution of errors in the decoder output is presented, and it is shown how the table can be used to determine exact values for the bit-error probability and the block-error probability. The exact values of bit-error probability computed from the table are compared with values obtained using a known theoretical approximation to the bit-error probability, and some conclusions are drawn as to the general usefulness of the theoretical approximation. Also, block-error probabilities are computed from the information presented in the table and these values are compared with the estimates of block-error probability obtained from minimumdistance considerations.