Search

We consider generalized error locating (GEL) codes over the same alphabet for both component codes. We propose an algorithm for computing an upper bound on the decoding error probability under known input symbol error rate and code parameters. Is is used to construct an algorithm for selecting code parameters to maximize the code rate for a given construction and given input and output error probabilities. A lower bound on the decoding error probability is given. Examples of plots of decoding error probability versus input symbol error rate are given, and their behavior is explained.

We obtain bounds on the rate of (optimal) list-decoding codes with a fixed list size L ≥ 1 for a q-ary multiple access hyperchannel (MAHC) with s ≥ 2 inputs and one output. By definition, an output signal of this channel is the set of symbols of a q-ary alphabet that occur in at least one of the s input signals. For example, in the case of a binary MAHC, where q = 2, an output signal takes values in the ternary alphabet {0, 1, {0, 1}}; namely, it equals 0 (1) if all the s input signals are 0 (1) and equals {0, 1} otherwise. Previously, upper and lower bounds on the code rate for a q-ary MAHC were studied for L ≥ 1 and q = 2, and also for the nonbinary case q ≥ 3 for L = 1 only, i.e., for so-called frameproof codes. Constructing upper and lower bounds on the rate for the general case of L ≥ 1 and q ≥ 2 in the present paper is based on a substantial development of methods that we designed earlier for the classical binary disjunctive multiple access channel.

Two ensembles of low-density parity-check (LDPC) codes with low-complexity decoding algorithms are considered. The first ensemble consists of generalized LDPC codes, and the second consists of concatenated codes with an outer LDPC code. Error exponent lower bounds for these ensembles under the corresponding low-complexity decoding algorithms are compared. A modification of the decoding algorithm of a generalized LDPC code with a special construction is proposed. The error exponent lower bound for the modified decoding algorithm is obtained. Finally, numerical results for the considered error exponent lower bounds are presented and analyzed.

A novel soft-decision decoding algorithm for Reed-Solomon codes over GF(2 m ) is proposed, which is based on representing them as polar codes with dynamic frozen symbols and applying the successive cancellation method. A further performance improvement is obtained by exploiting multiple permutations of codewords which are taken from the automorphism group of Reed-Muller codes. It is also shown that the proposed algorithm can be simplified in the case of decoding a binary image of the Reed-Solomon code.

We complete the derivation of a formula for the reliability function of a q-ary symmetric channel under list decoding at zero rate.

We complete deriving a formula for the reliability function of a binary symmetric channel (BSC) for list decoding in the case of zero rate.

For decoding concatenated codes up to half their designed distance, generalized minimum distance (GMD) decoding can be used. GMD decoding applies multitrial error/erasure decoding of the outer code, where erased symbols depend on some reliability measure stemming from the inner decoders. We consider the case where the outer decoder is able to decode beyond half the minimum distance of the outer code. For a given number of outer decoding trials, we derive achievable decoding radii for GMD decoding. Vice versa, we give a lower bound on the number of required outer decoding trials to obtain the greatest possible decoding radius.

We consider problems of detecting errors in combinational circuits and algorithms for the decoding of linear codes. We show that a totally self-checking combinatorial circuit for the decoding of a binary Hamming [n, k] code can be constructed if and only if n = 2 r ? 1, r = n?k. We introduce the notion of a totally self-checking combinational circuit detecting error clusters of size at most µ; for shortened Hamming [n,k] codes, we construct totally self-checking decoding combinational circuits detecting error clusters of size at most µ, 2 ? µ < n?k. We describe single-error protected and self-checking algorithms: the extended Euclidean algorithm and decoding algorithms for binary BCH codes and Reed-Solomon codes over GF(2 m ).

A list decoding algorithm is designed for the first-order binary Reed-Muller codes of length n that reconstructs all codewords located within the ball of radius n/2(1 ? ?) about the received vector and has the complexity of O(n ln2(min{? ?2, n})) binary operations.

We consider the problem of efficient implementation of two-dimensional interpolation in the Guruswami-Sudan list decoding algorithm for Reed-Solomon codes. We show that it can be implemented by computing the product of ideals of interpolation polynomials constructed for subsets of interpolation points. A method for fast multiplication of coprime zero-dimensional ideals is proposed.

An upper bound on the error probability (first error event) of product convolutional codes over a memoryless binary symmetric channel, and the resulting error exponent are derived. The error exponent is estimated for two decoding procedures. It is shown that, for both decoding methods, the error probability exponentially decreasing with the constraint length of product convolutional codes can be attained with nonexponentially increasing decoding complexity. Both estimated error exponents are similar to those for woven convolutional codes with outer and inner warp.

A lower bound for the number of iteratively correctable erasures is given, with application to the ensemble of LDPC codes with parity-check matrices composed of permutation matrices [1]. We assume that the Zyablov-Pinsker iterative decoding algorithm [2] is used. Its complexity is O(N log N), where N is the block length.

We suggest a new approach to constructing a lower bound on the decoding error probability in a discrete memoryless channel at zero transmission rate. This approach considerably simplifies derivation of the bound, making it more natural, and simultaneously improves the remainder term of the estimate for the decoding error exponent.

We consider the problem of symbol-by-symbol a posteriori probability (APP) decoding for information symbols of nonsystematically encoded block codes. This problem arises at soft concatenated decoding of generalized concatenated block codes. The well-known BCJR algorithm for efficient APP decoding is not able to solve the problem if it runs on the minimal code trellis of a block code. We introduce an extended trellis representation for block codes, which includes encoding information and thus makes it possible to apply the BCJR algorithm as well as trellis-based decoding in the dual code space. Complexity properties of the extended trellis are investigated.

We prove that the expurgation bound on the error probability exponent for list-of-L decoding is tight at zero rate.

We address the problem of joint source-channel coding when variable-length codes are used for information transmission over a discrete memoryless channel. Data transmitted over the channel are interpreted as pairs (mk,tk), where mk is a message generated by the source and tk is a time instant when the transmission of the kth codeword begins. The decoder constructs an estimate of the transmitted sequence of pairs, and the kth decoding error is introduced as the event that the pair (mk,tk) does not belong to this sequence. We describe the maximum likelihood decoding algorithm and prove a lower bound on the exponent of the decoding error probability. For a subclass of discrete memoryless sources and discrete memoryless channels, this bound is asymptotically tight.