An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's algorithm was proposed by Han, Hartmann, and Chen (1993). We prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10/sup -3/ by finding an upper bound of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code, and within 0.5 dB of the optimal performance for the (128, 64) binary BCH code, respectively.

Efficient new algorithms are presented for maximum-likelihood and suboptimal soft-decision decoding algorithms for linear block codes. The first algorithm, MA*, improves the efficiency of the A* decoding algorithm, conducting the heuristic search through a code tree while exploiting code-specific properties. The second algorithm, H*, reduces search space by successively estimating the cost of the minimum-cost codeword with a fixed value at each of the most reliable and linearly independent components of the received message. The third algorithm, directed search, finds the codeword closest to the received vector by exploring a continuous search space. The strengths of these three algorithms are combined in a hybrid algorithm, applied to the (128,64), the (256,131), and the (256,139) binary-extended Bose-Chaudhuri-Hocquenghem (BCH) codes. Simulation results show that this hybrid algorithm can efficiently decode the (128,64) code for any signal-to-noise ratio, with near-optimal performance. Previously, no practical decoder could have decoded this code with such a performance for all ranges of signal-to-noise ratio.

We present some properties of an improved version of the zero-neighbors algorithm-the zero-guards algorithm. These properties can be used to find a zero-guards. A new decoding procedure using a zero-guards is also given.

Algorithm-based fault tolerance (ABFT) can provide a low-cost error protection for array processors and multiprocessor systems. Several ABFT techniques (weighted check-sum) have been proposed to design fault-tolerant matrix operations. In these schemes, encoding/decoding uses either multiplications or divisions so that overhead is high. In this paper, new encoding/decoding methods are proposed for designing fault-tolerant matrix operations. The unique feature of these new methods is that only additions and subtractions are used in encoding/decoding. In this paper, new algorithms are proposed to construct error detecting/correcting codes with the minimum Hamming distance 3 and 4. We will show that the overhead introduced due to the incorporation of fault tolerance is drastically reduced by using these new coding schemes.

The authors present a novel and efficient maximum-likelihood soft-decision decoding algorithm for linear block codes. The approach used here converts the decoding problem into a search problem through a graph that is a trellis for an equivalent code of the transmitted code. A generalized Dijkstra's algorithm, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to reduce drastically the search space and to make the decoding efforts of this decoding algorithm adaptable to the noise level. For example, for most real channels of the 35 000 samples tried, simulation results for the (128,64) binary extended BCH code show that the proposed decoding algorithm is fifteen orders of magnitude more efficient in time and in space than that proposed by Wolf (1978). Simulation results for the (104, 52) binary extended quadratic residue code are also given.>

The algorithm-based fault tolerance techniques have been proposed to obtain reliable results at very low hardware overhead. Even though 100% fault coverage can be theoretically obtained by using these techniques, the system performance, i.e., fault coverage and throughput, can be drastically reduced due to many practical problems, e.g., round-off errors. A novel algorithm-based fault tolerance scheme is proposed for fast Fourier transform (FFT) networks. It is shown that the proposed scheme achieves 100% fault coverage theoretically. An accurate measure of the fault coverage for FFT networks is provided by taking the round-off error into account. The proposed scheme is shown to provide concurrent error detection capability to FFT networks with low hardware overhead, high throughput, and high fault coverage.>

An efficient technique for designing a totally self-checking checker for 1/n code (n>3) with minimum possible gate delay is proposed. The checker consists of a 1/n to k/2k translator and a k/2k code checker. The translator is implemented using a NOR array and checker using a NOR-NOR PLA. The design technique is applicable for all but a few values of n. It has been shown that the checkers constructed using the proposed technique occupy minimum or near-minimum chip area depending on the value of n. This new technique also has the advantage over existing ones in terms of speed or hardware.>

Four random test generation strategies are compared to determine their relative effectiveness: equiprobable 0s and 1s; two weighted random pattern generation algorithms; and the maximum output information entropy principle. The test generation strategies are compared at a variety of target fault coverages. Two statistically based metrics are used to evaluate the techniques: a large-sample test of the difference of means and an upper confidence limit. The two weighted random test pattern generation strategies are found to be generally superior to equiprobable 0s and 1s and maximum output entropy. For a given logic circuit, the same technique is not necessarily optimal at every fault coverage.>

Recently D.J. Lin and B. Bose, (1988) proposed a class of t error correcting and d unidirectional error detecting codes (t-EC/d-UED codes) where d>t. The authors refine the codes in such a way that the error detecting capability of the resulting codes is considerably better than the existing codes in many cases. The decoding algorithm is described. The proposed codes are compared to the Lin-Bose codes.>

A method for constructing a class of t-error correcting and all unidirectional error-detecting systematic codes is proposed. These codes have been shown to be more efficient than codes constructed using other methods proposed in the literature. In a special case, the code constructed is the Berger code.>

The authors propose a class of spherical codes which can be easily decoded by an efficient iterative maximum likelihood decoding algorithm. A necessary and sufficient condition for a spherical code to be iteratively maximum likelihood decodable is formulated. A systematic construction method for such codes based on shrinking of Voronoi corners is analyzed. The base code used for construction is the binary maximal length sequence code. The second-level construction is described. Computer simulation results for selected codes constructed by the proposed method are given.>

Minimum distance decoding (MDD) for a general error-correcting linear code is a hard computational problem that recently has been shown to beNP-hard. The complexity of known decoding algorithms is determined by\min (2^{k},2^{n-k}), wherenis the code length andkis the number of information digits. Two new algorithms are suggested that reduce substantially the complexity of MDD. The algorithms use a new concept of zero neighbors--a special set of codewords. Only these codewords (which can be computed in advance) should be stored and used in the decoding procedure. The number of zero neighbors is shown to be very small compared with\min (2^{k},2^{n-k})forn \gg 1and a wide range of code ratesR = k/n. For example, forR \approx 0.5this number grows approximately as a square root of the number of codewords.

In this correspondence, we present an algorithm based on information theoretic concepts for the design of efficient sequential fault diagnosis experiments for permanent faults in modular systems.

Soft decision decoding of binary linear block codes transmitted over the additive white Gaussian channel (AWGN) using antipodal signaling is considered. A set of decoding algorithms called generalized Chase algorithms is proposed. In contrast to Chase algorithms, which require a\lfloor (d- 1)/2 \rfloorbinary error-correcting decoder for decoding a binary linear block code of minimum distanced, the generalized Chase algorithms can use a binary decoder that can correct less than\lfloor ( d - 1)/2 \rfloorhard errors. The Chase algorithms are particular cases of the generalized Chase algorithms. The performance of all proposed algorithms is asymptotically optimum for high signal-to-noise ratio (SNR). Simulation results for the(47, 23)quadratic residue code indicate that even for low SNR the performance level of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.

The maximum likelihood decoding problem for linear binary(n,k)codes is reformulated as a continuous optimization problem in ak-dimensional solid cube. We obtain a near optimum solution of this problem by use of a simple gradient local optimization algorithm. Computer simulation results are presented for the(21,11)projective geometry code and the(47,23)quadratic-residue code.

In this correspondence we consider the problem of the construction of efficient sequential fault location experiments for permanent faults. The construction of optimum sequential experiments is an NP-complete problem and, therefore, a heuristic approach for the design of near-optimum sequential experiments is considered. The approach is based on information theoretic concepts and the suggested algorithm for the construction of near-optimum sequential fault location experiments is systematic, has a sound theoretical justification, and yet has low design complexity.

The problem of conversion of decision tables to decision trees is treated. In most cases, the construction of optimal decision trees is an NP-complete problem and, therefore, a heuristic approach to this problem is necessary. In this heuristic approach, an application of information theoretic concepts to construct efficient decision trees for decision tables which may include "don't care" entries is made. In contrast to most of the existing heuristic algorithms, this algorithm is systematic and is intuitively appealing from an information theoretic standpoint. The algorithm has low design complexity and yet provides near-optimal decision trees.

This correspondence presents a oncept of function-independent testing of digital networks. It is based on the idea of dual-mode logic where the network is tested in one mode while the normal function of the network is performed in another mode, with neither mode interfering with the other. This correspondence simultaneously defines the structure of modules with the above characteristics such that combinational and sequential networks built with them can be tested with two and six function-independent tests, respectively.

Bit-by-bit soft-decision decoding of binary cyclic codes is considered. A significant reduction in decoder complexity can be achieved by requiring only that the decoder correct all analog error patterns which fall within a Euclidean sphere whose radius is equal to half the minimum Euclidean distance of the code. Such a "maximum-radius" scheme is asymptotically optimum for the additive white Gaussian noise (AWGN) channel. An iterative extension of the basic algebraic analog decoding scheme is discussed, and performance curves are given for the (17,9), (21,11), and (73,45) codes on the AWGN channel.

A new upper bound on the minimum distance of binary cyclic arithmetic codes of composite length is derived. New classes of binary cyclic arithmetic codes of composite length are introduced. The error correction capability of these codes is discussed, and in some cases the actual minimum distance is found. Decoding algorithms based on majority-logic decision are proposed for these codes.

This correspondence presents an optimal algorithm to detect any single stuck-at-1 (s-a-1), stuck-at-0 (s-a-0) fault in a random access memory using only the n-bit memory address register input and m-bit memory buffer register input and output lines. It is shown that this algorithm requires 4 X 2nmemory accesses.

This correspondence presents an optimal algorithm to detect any single "stuck-at-i," "stuck-at-O" fault and any combination of "stuck-at-I," "stuck-at-O" multiple faults in a random access memory using only the n-bit memory address register input and m-bit memory buffer register input and output lines. It is shown that this algorithm requires 4 X 2n memory accesses.

Asymptotic expressions are derived for the probability of bit error for optimum bit-by-bit decoding of a linear binary block code for the white Gaussian noise channel.

In this paper we investigate the weight structure of cyclic codes of composite lengthn = n_{1} n_{2}. The actual minimum distances of some classes of binary cyclic codes of composite length are derived. For other classes, new lower bounds on the minimum distance are obtained. These new lower bounds improve on the BCH bound for a considerable number of binary cyclic codes.

A decoding rule is presented which minimizes the probability of symbol error over a time-discrete memory]ess channel for any linear error-correcting code when the codewords are equiprobable. The complexity of this rule varies inversely with code rate, making the technique particularly attractive for high rate codes. Examples are given for both block and convolutional codes.

Leth_1(x)h_2(x)be the parity-check polynomial of a binary cyclic code. This correspondence presents a formula for decomposing words in the code as sums of multiples of words in the codes whose parity-check polynomials areh_1(x)andh_2(x). This decomposition provides information about the weight distribution of the code.

Some new results on the structure of generalized finite-geometry codes are presented.

Many cyclic codes are generated by polynomials possessing more than one set of consecutive roots. Thus more than one set of syndrome sequences are available for decoding. In this correspondence, a decoding method based on Berlekamp's iterative algorithm is presented which makes use of the multiple sets of syndrome sequences for decoding such cyclic codes beyond the BCH bound.

This paper presents majority-decoding algorithms for four classes of binary cyclic codes. The classes are those for which the parity-check polynomial is: 1) the product of two primitive polynomials with relatively prime exponents and 2) the product of(x^r + 1)/(x + 1)and a primitive polynomial, wherer \geq 3is odd and the exponents are relatively prime, together with the corresponding nonexpurgated codes.

Some new lower bounds on the minimum distance of cyclic codes of composite length are presented. These bounds generalize some existing bounds and give better estimates of the minimum distance for a wide range of cyclic codes, Lower bounds on the random-error-correction capability of a particular class of cyclic codes of composite lengthn = n_1n_2, wheren_1andn_2are relatively prime, are easily derived.

A general decoding method for cyclic codes is presented which gives promise of substantially reducing the complexity of decoders at the cost of a modest increase in decoding time (or delay). Significant reductions in decoder complexity for binary cyclic finite-geometry codes are demonstrated.

In this correspondence the Mattson-Solomon formulation is applied to cyclic codes with multiple sets of consecutive roots of the generator polynomial and better estimates of the minimum distance of many cyclic codes are obtained.

In this correspondence, a decoding algorithm to decode beyond the BCH bound is introduced. It gives a complete minimum distance decoding for any cyclic code. A comparison between this decoding algorithm and previously existing ones is also given.

An upper bound on the minimum distance of cyclic codes of composite length is presented. This upper bound proves the BCH bound to be exact for many cyclic codes.

This correspondence presents an upper bound on the minimum distance of arithmetic codes of composite lengthn = n_1 n_2. The tightness of this bound gives a rather good working estimate of the minimum distance of a prospective code.

This paper presents a number of interesting results relating to the determination of actual minimum distance of cyclic codes. Codes with multiple sets of consecutive roots are constructed. A bound on the minimum weight of odd-weight codewords is determined. Relations on the distribution of roots of the generator polynomial are investigated. Location polynomials of reversible codes are examined. These results are used to obtain better estimates of the minimum distance of many new cyclic codes.

In this correspondence a complete decoding algorithm for double-error-correcting binary BCH codes of lengthn = 2^m - 1is introduced. It corrects all patterns of one and two errors and all patterns of three errors that belong to cosets that have a coset leader of weight three. This algorithm is based on the step-by-step decoding algorithm introduced by Prange and the decoding algorithm introduced by Meggitt, which makes use of the cyclic properties of the code. A comparison between this method and previously existing ones is also given.

The minimum distance of a class of reversible cyclic codes has been proved to be greater than that given by the BCH bound. It is also noted that this class of codes includes the class of primitive double-error-correcting binary codes of Melas as well as the class of nonprimitive double-error-correcting binary codes discovered by Zetterberg as special cases.