Search

It is well-known that cyclic codes have efficient encoding and decoding algorithms. In recent years, antiprimitive BCH codes have attracted a lot of attention. The objective of this paper is to study BCH codes of this type over finite fields and analyse their parameters. Some lower bounds on the minimum distance of antiprimitive BCH codes are given. The BCH codes presented in this paper have good parameters in general, containing many optimal linear codes. In particular, two open problems about the minimum distance of BCH codes of this type are partially solved in this paper.

Self-orthogonal codes are an important type of linear codes due to their wide applications in communication and cryptography. The Euclidean (or Hermitian) hull of a linear code is defined to be the intersection of the code and its Euclidean (or Hermitian) dual. It is clear that the hull is self-orthogonal. The main goal of this paper is to obtain self-orthogonal codes by investigating the hulls. Let $\mathcal {C}_{(r,r^{m}-1,\delta,b)}$ be the primitive BCH code over $\mathbb {F}_{r}$ of length $r^{m}-1$ with designed distance $\delta $ , where $\mathbb {F}_{r}$ is the finite field of order $r$ . In this paper, we will present Euclidean (or Hermitian) self-orthogonal codes and determine their parameters by investigating the Euclidean (or Hermitian) hulls of some primitive BCH codes. Several sufficient and necessary conditions for primitive BCH codes with large Hermitian hulls are developed by presenting lower and upper bounds on their designed distances. Furthermore, some Hermitian self-orthogonal codes are proposed via the hulls of BCH codes and their parameters are also investigated. In addition, we determine the dimensions of the code $\mathcal {C}_{(r,r^{2}-1,\delta,1)}$ and its hull in both Hermitian and Euclidean cases for $2 \le \delta \le r^{2}-1$ . We also present two sufficient and necessary conditions on designed distances such that the hull has the largest dimension.

In this paper, a family of $[{q}^{2}-1, 4, {q}^{2}-{q}-2]$ cyclic codes over ${\mathbb F}_{{q}}$ meeting the Griesmer bound is presented. Their duals are $[{q}^{2}-1,{q}^{2}-5,4]$ almost MDS codes and are optimal with respect to the sphere-packing bound. The ${q}_{0}$ -ary subfield codes of this family of cyclic codes are also investigated, where ${q}_{0}$ is any prime power such that q is power of ${q}_{0}$ . Some of the subfield codes are optimal and some have the best known parameters. It is shown that the subfield codes are equivalent to a family of primitive BCH codes and thus the parameters of the BCH codes are solved. The duals of the subfield codes are also optimal with respect to the sphere-packing bound. A family of $[{q}^{2}, 4, {q}^{2}-{q}-1]$ linear codes over ${\mathbb F}_{{q}}$ meeting the Griesmer bound is presented. Their duals are $[{q}^{2},{q}^{2}-4,4]$ almost MDS codes and are optimal with respect to the sphere-packing bound. The ${q}_{0}$ -ary subfield codes of this family of linear codes are also investigated, where ${q}_{0}$ is any prime power such that q is power of ${q}_{0}$ . Five infinite families of 2-designs are also constructed with three families of linear codes of this paper.

BCH codes are an important class of cyclic codes which have applications in satellite communications, DVDs, disk drives, and two-dimensional bar codes. Although BCH codes have been widely studied, their parameters are known for only a few special classes. Recently, Ding et al. made some new progress in BCH codes. However, we still have very limited knowledge on the dimension of BCH codes, not to mention the weight distribution of BCH codes. In this paper, we generalize the results on BCH codes from several previous papers. 1) The dimension of narrow-sense BCH codes of length $((q^{m}-1)/{\lambda })$ with designed distance $2\leq \delta \leq (({q^{\lceil (m+1)/2 \rceil }-1})/(\lambda)+1)$ is settled, where $\lambda $ is any factor of $(q-1)$ . 2) The weight distributions of two classes of narrow-sense BCH codes of length $(({q^{m}-1})/2)$ with designed distance $\delta =(({(q-1)q^{m-1}-q^{\lfloor (m-1)/2\rfloor }-1})/2)$ and $\delta =(({(q-1)q^{m-1}-q^{\lfloor (m+1)/2\rfloor }-1})/2)$ are determined. 3) The weight distribution of a class of BCH codes of length $((q^{m}-1)/({q-1}))$ is determined. In particular, a subclass of this class of BCH codes is optimal with respect to the Griesmer bound. Some optimal linear codes obtained from this class of BCH codes are characterized.

Cyclic codes are widely employed in communication systems, storage devices, and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over $ {\mathrm {GF}}(q)$ with length $n=(q^{m}-1)/(q-1)$ . Little is known about this class of BCH codes when $q>2$ . The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length $n=(3^{m}-1)/2$ are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated.

Because of their efficient encoding and decoding algorithms, cyclic codes—an interesting class of linear codes—are widely used in communication systems, storage devices, and consumer electronics. BCH codes form a special class of cyclic codes, and are usually among the best cyclic codes. A subclass of good BCH codes is the narrow-sense primitive BCH codes. However, the dimension and minimum distance of these codes are not known in general. The main objective of this paper is to study the dimension and minimum distances of a subclass of the narrow-sense primitive BCH codes with design distance $\delta =(q-\ell _{0})q^{m-\ell _{1}-1}-1$ for certain pairs $(\ell _{0}, \ell _{1})$ , where $0 \leq \ell _{0} \leq q-2$ and $0 \leq \ell _{1} \leq m-1$ . The parameters of other related classes of BCH codes are also investigated, and some open problems are proposed in this paper.

Several new families of multi-memory classical convolutional Bose-Chaudhuri-Hocquenghem (BCH) codes as well as families of unit-memory quantum convolutional codes are constructed in this paper. Our unit-memory classical and quantum convolutional codes are optimal in the sense that they attain the classical (quantum) generalized Singleton bound. The constructions presented in this paper are performed algebraically and not by computational search., Comment: Accepted for publication in IEEE-Transactions on Information Theory

Binary primitive triple-error-correcting Bose-Chaudhuri-Hocquenghem (BCH) codes of length n=2/sup m/-1 have been the object of intensive studies for several decades. In the 1970s, their covering radius was determined in a series of papers to be /spl rho/=5. However, one problem for these codes that has been open up to now is to find their coset distribution. In this paper this problem is solved and the number of cosets of each weight in any binary primitive triple-error-correcting BCH code is determined. As a consequence this also gives the coset distribution of the extended codes of length N=2/sup m/ with minimum distance 8.

As a special subclass of cyclic codes, BCH codes have wide applications in communication and storage systems. A BCH code of length n over Fq is always relative to an n-th primitive root of unity β in an extension field of Fq, and is called a dually-BCH code if its dual is also a BCH code relative to the same β. The question as to whether a BCH code is a dually-BCH code is in general very hard to answer. In this paper, an answer to this question for primitive narrow-sense BCH codes and projective narrow-sense ternary BCH codes is given. Sufficient and necessary conditions in terms of the designed distances δ will be presented to ensure that these BCH codes are dually-BCH codes. In addition, the parameters of the primitive narrow-sense BCH codes and their dual codes are investigated. Some lower bounds on minimum distances of the dual codes of primitive and projective narrow-sense BCH codes are developed. Especially for binary primitive narrow-sense BCH codes, the new bounds on the minimum distances of the dual codes improve the classical Sidel’nikov bound, and are also better than the Carlitz and Uchiyama bound for large designed distances δ. The question as to what subclasses of cyclic codes are BCH codes is also answered to some extent. As a byproduct, the parameters of some subclasses of cyclic codes are also investigated.

In a previous paper, No, Golomb, Gong, Lee and Gaal (see ibid., vol.44, p.814-17, 1998) conjectured that certain binary sequences having a simple trace description possess the ideal autocorrelation property. In the present paper it is shown that each such sequence is balanced and, moreover, that the dual of the linear cyclic code generated by the sequence and its cyclic shifts, is a triple-error correcting code having the same weight distribution as the triple-error correcting Bose-Chaudhuri-Hocquenghem (BCH) code. This cyclic code also contains a cyclic subcode that yields a new family of sequences having the same size and correlation parameters as does the family of Gold sequences.

The paper proposes an improved difference-of-syndromes decoding algorithm for decoding quadratic residue codes up to half the minimum distance. Therein, soft-decision information is not essential, but it can be used to speed up the computations. The improvement over the prior art is demonstrated by simulations. Moreover, the proposed algorithm is also compared with the classic Berlekamp-Massey algorithm by taking two BCH codes as examples.

Let $q$ be a prime power and $m\geq 3$ be odd. Suppose that $n=\frac {q^{2m}-1}{a}$ with $a|(q^{m}+1)$ and $3\leq a \leq 2(q^{2}-q+1)$ . This paper mainly determines the actual maximum designed distance of Hermitian dual-containing Bose-Chaudhuri-Hocquenghem (BCH) codes over $\mathbb {F}_{q^{2}}$ of length $n$ . Firstly, we give the maximum designed distance $\delta _{m,a}^{R}$ of narrow-sense Hermitian dual-containing BCH codes. Secondly, we show that there are also non-narrow-sense ones of designed distance up to $\delta _{m,a}^{R}$ . It is worth mentioning that our maximum designed distance $\delta _{m,a}^{R}>\lceil \frac {a}{2}\rceil \delta _{m}^{A}$ , where $\delta _{m}^{A}$ is given by Aly et al. (IEEE Trans. Inf. Theory, vol. 53, no. 3, pp. 1183-1188, 2007). Thus, many families of Hermitian dual-containing BCH codes with relatively large designed distance are obtained. Using the Hermitian construction to them, we can subsequently construct different classes of nonprimitive quantum codes, which are new in the sense that their parameters are not covered in the literature.

In this paper, we first study deviations of the complete weight distribution of a linear code from that of a random code. Then, we consider a large family of subfield subcodes of algebraic-geometric codes over prime fields which include BCH codes and Goppa codes and prove that the complete weight distribution is close to that of a random code if the code length is large compared with the genus of the curve and the degree of the divisor defining the code.

A common way to protect data stored in DRAM and related memory systems is through the use of an error-correcting code such as the extended Hamming code. Traditionally, these error-correcting codes provide equal protection guarantees to all messages. In this paper, we focus on unequal message protection (UMP), in which a subset of messages is deemed as special, and is afforded additional error-correction protection while maintaining the same number of redundancy bits as the baseline code. UMP is a powerful approach when the special messages are chosen based on the knowledge of data patterns in context. Our objective is to construct deterministic, algebraic codes with guaranteed UMP properties, derive their cardinality bounds using novel combinatorial techniques, and to demonstrate their efficacy for realistic memory benchmarks. We first introduce a UMP alternative to the single-bit parity-check code, and then we generalize to a broader UMP code family, including a UMP alternative to the extended Hamming code, offering full double-error correction protection to special messages. Our UMP constructions, applied to main memory in high-performance computing applications, could lead to significant system-level benefits such as less frequent checkpoints in supercomputers and decreased risk of catastrophic failure from erroneous special messages.

BCH codes are an interesting type of cyclic codes and have wide applications in communication and storage systems. Generally, it is very hard to determine the minimum distances of BCH codes. In this paper, we determine the weight distributions of two classes of primitive BCH codes $\mathcal C_{(q, m, \delta _{2})}$ and $\mathcal C_{(q, m, \delta _{3})}$ and their extended codes, which solve two problems proposed by Ding et al. It is shown that the extended codes $\overline {\mathcal C}_{(q, m, \delta _{2})}$ have four nonzero weights. We also employ the Hartmann-Tzeng bound to present the minimum distance of the dual code $\mathcal C_{(q, m, \delta _{2})}^\perp $ for $q \ge 5$ . Inspired by the idea, we then determine the dimensions of a class of cyclic codes and give lower bounds on their minimum distances, which is greatly improved comparing with the BCH bound. Some optimal codes are obtained.

In this paper, we construct a new family of quantum synchronizable codes from repeated-root cyclic codes of lengths $p^{s}$ and $lp^{s}$ over $\mathbb {F}_{q}$ , where $s\geq 1~and l\geq 2$ are integers, and $p\geq 3$ is the odd characteristic. Within some loose limitations, these synchronizable codes can possess the best possible capability in synchronization recovery, and therefore, enriches the variety of good quantum synchronizable codes. Furthermore, by using known techniques in classical coding theory which convert the computation of the minimum distance of a repeated-root cyclic code to that of a shorter simple-root cyclic code, we prove that the repeated-root cyclic codes of lengths $p^{s}$ and $lp^{s}$ are in general better than narrow-sense BCH codes of close lengths in terms of minimum distances, and thereby enable the obtained synchronizable codes to correct more Pauli errors.

For original paper see van der Vlugt (IEEE Trans. Inform. Theory, vol.42, p.1612-14, 1996). One of the subjects in the above-mentioned paper is the determination of the weight distribution of the dual code C/sup /spl perp// of the binary cyclic codes C of length n=2/sup m/-1 with zeros /spl alpha/, /spl alpha//sup 2(t-1+1)/, /spl alpha/(2/sup t/+1). Here m=2t+1 and /spl alpha/ generate the multiplicative group of the finite field F/sub 2m/. After the publication of van der Vlugt (1996), Tor Helleseth drew the present author's attention to the fact that Kasami's paper (1969) contains the key to an essentially different way of deriving the weight enumerator of C/sup /spl perp//. Indeed, combining theorem 15 (ii)-1 in Kasami with the fact that the minimum distance d/sub min/=7 (see MacWilliams and Sloane, 1983) also yields the weight distribution of C/sup /spl perp//.

The Rosenbloom–Tsfasman metric has attracted the attention of many researchers as a generalization of the Hamming metric that is relevant to practical problems. Codes for this metric were considered. In particular, Reed–Solomon codes were generalized to be compatible with this metric. In this paper, a generalization of BCH codes for the Rosenbloom–Tsfasman metric is proposed. This generalization is based on considering BCH codes as subfield subcodes of Reed–Solomon codes. By characterizing these subfield subcodes, an explicit construction of BCH codes for the Rosenbloom–Tsfasman metric is provided. Two important properties of Reed–Solomon codes and BCH codes for the Rosenbloom–Tsfasman metric are studied and compared with those for the Hamming metric. These properties are cyclic structure and duality. The approach is based on Galois-Fourier transforms associated with Hasse derivatives.

This paper is devoted to studying two main problems: 1) computing the apparent distance of an Abelian code and 2) giving a notion of Bose, Ray-Chaudhuri, Hocquenghem (BCH) multivariate code. To do this, we first strengthen the notion of an apparent distance by introducing the notion of a strong apparent distance; then, we present an algorithm to compute the strong apparent distance of an Abelian code, based on some manipulations of hypermatrices associated with its generating idempotent. Our method uses less computations than those given by Camion and Sabin; furthermore, in the bivariate case, the order of computation complexity is reduced from exponential to linear. Then, we use our techniques to develop a notion of a BCH code in the multivariate case, and we extend most of the classical results on cyclic BCH codes. Finally, we apply our method to the design of Abelian codes with maximum dimension with respect to a fixed apparent distance and a fixed length.

In this paper, we obtain upper and lower bounds on the designed and actual distances of any sequence of extended primitive BCH codes of increasing lengths n and fixed rate R . The results of this paper are based on [1, ch. 12], which gives an exact expression for the rates of any sequence of extended primitive BCH codes of increasing length and fixed ratio of distance/length.

Cyclic codes are an interesting class of linear codes due to their efficient encoding and decoding algorithms. Bose-Ray-Chaudhuri-Hocquenghem (BCH) codes form a subclass of cyclic codes and are very important in both theory and practice as they have good error-correcting capability and are widely used in communication systems, storage devices, and consumer electronics. However, the dimension and minimum distance of BCH codes are not known in general. The objective of this paper is to determine the Bose and minimum distances of a class of narrow-sense primitive BCH codes.

Chase decoding is a prevalent soft-decision decoding method for algebraic codes where an efficient bounded-distance decoder is available. Essentially, it repeatedly applies bounded-distance decoding upon combinatorially flipping certain least reliable bits (or patterns for nonbinary case). In this paper, we devise a one-pass Chase decoding algorithm of Reed-Solomon codes such that the desired error locator polynomial by flipping an error pattern is obtained in one pass (when operated in parallel) through utilizing the preceding results. This is effectively achieved through cumulative interpolation and linear-feedback-shift-register (LFSR) synthesis techniques. Furthermore, through converting the algorithm into the transform domain, exhaustive root search for each error locator polynomial is circumvented. Computationally, the new algorithm exhibits linear complexity , in attempting to determine a candidate codeword associated with each additionally flipped symbol/pattern; it compares favorably to quadratic complexity by straightforwardly utilizing hard-decision decoding, where and denote the code length and minimum distance, respectively. We also reveal a corrected algorithm for one-pass generalized minimum distance (GMD) decoding for Reed-Solomon codes from Koetter's original work. In addition, we devise a highly efficient one-pass Chase decoding algorithm for binary Bose-Chaudhuri-Hocquenghem (BCH) codes by taking advantage of a key characteristic of the Berlekamp algorithm. Finally, we present a systolic very large-scale integration (VLSI) decoder architecture through slightly compromising the proposed one-pass Chase decoding algorithm. It takes clock cycles to complete one iteration by flipping one error pattern. Both circuit and memory complexities are dictated by the dimension of flipping patterns; in particular, they are independent of the code length or the minimum distance , rendering it highly attractive for various applications.

Novel coding schemes for noiseless and noisy asynchronous code division multiple access (A-CDMA) systems are presented in this paper. The schemes use Wu-Chang spreading code, block interleaver, and synchronizable channel codes to support A-CDMA communications with random delays. For the noiseless case, each active user generates one of M messages, M = ⌊(2T-D -1)/(D + 1)⌋ , and a (T-D)-stage MLSR encoder encodes the message into a codeword of length T. Given a maximum random delay of D chips, the receiver can decode messages of all active users without ambiguity. For the noisy case, extended Bose-Caldwell cyclic codes are used to encode messages. The extended cyclic codes provide error correction and delay recovery effectively. By using a BCH code of length n as the cyclic code, the extended code can correct up to τ ≤ ⌊n/4⌋ errors and recover a maximum random delay of n -1 chips.

We give a new method in order to obtain Weil-Serre type bounds on the minimum distance of arbitrary cyclic codes over $\mathbb{F}_{p^e}$ of length coprime to $p$, where $e\geq 1$ is an arbitrary integer. In an earlier paper we obtained Weil-Serre type bounds for such codes only when $e = 1$ or $e = 2$ using lengthy explicit factorizations, which seems hopeless to generalize. The new method avoids such explicit factorizations and it produces an effective alternative. Using our method we obtain Weil-Serre type bounds in various cases. By examples we show that our bounds perform very well against Bose-Chaudhuri-Hocquenghem bound and they yield the exact minimum distance in some cases.

In this paper, we devise a rational curve fitting algorithm and apply it to the list decoding of Reed-Solomon and Bose-Chaudhuri-Hocquenghen (BCH) codes. The resulting list decoding algorithms exhibit the following significant properties.

In this paper, we prove the following two results that expose some combinatorial limitations to list decoding Reed-Solomon codes. 1) Given n distinct elements alpha1,...,alphan from a field F, and n subsets S1,...,Sn of F, each of size at most l, the list decoding algorithm of Guruswami and Sudan can in polynomial time output all polynomials p of degree at most k that satisfy p(alphai)isinSi for every i, as long as l 0 (agreement of k is trivial to achieve). Such a bound was known earlier only for a nonexplicit center. Finding explicit bad list decoding configurations is of significant interest-for example, the best known rate versus distance tradeoff, due to Xing, is based on a bad list decoding configuration for algebraic-geometric codes, which is unfortunately not explicitly known

The Viterbi algorithm (1967) and conventional serial concatenated codes (CSCC) have been widely applied in digital communication systems over the last 30 years. We show that the Shannon capacity of additive white Gaussian noise (AWGN) channels can be approached by CSCCs and the iterative VA (IVA). We firstly study the algebraic properties of CSCCs. We then present the IVA to decode these codes. We also analyze the performance of the IVA and conclude that a better performance can be achieved if we replace the powerful block codes by some simple parity codes. One of the key results in this paper shows that by using a proper design for the decoding method, codes with small loops can be very efficiently decoded using a min-sum type algorithm. The numerical results show that the IVA can closely approach the Shannon sphere-packing lower bound and the Shannon limit. For block sizes ranging from 56 information bits to 11970 information bits, the IVA can perform to within about 1 dB of the Shannon sphere-packing lower bound at a block error rate of 10/sup -4/. We show that the IVA has a very low complexity and can be applied to many current standard systems, for example, the Qualcomm code-division multiple-access (CDMA) system and the NASA concatenated system, with very little modification or, for some cases, without any modification.

Historically, LCD cyclic codes were referred to as reversible cyclic codes, which had applications in data storage. Due to a newly discovered application in cryptography, there has been renewed interest in LCD codes. In this paper, we explore two special families of LCD cyclic codes, which are both BCH codes. The dimensions and the minimum distances of these LCD BCH codes are investigated.

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.

Motivated by the paper of Calderbank, McGuire, Kumar, and Helleseth (see ibid., vol.42, no.1, p.217-26, Jan. 1996) we prove the following result: for any given positive integer l/spl ges/3, the minimum Lee weights of Hensel lifts (to Z/sub 4/) of binary primitive BCH codes of length 2/sup m/-1 and designed distance 2/sup l/-1 is just 2/sup l/-1 when (a) m can be divided by l or (b) m is sufficiently large. For Hensel lifts of binary primitive BCH codes of arbitrary designed distance /spl delta//spl ges/4, we also prove that their minimum Lee weight d/sub L//spl les/2([log/sub 2//spl delta/]+1)-1 when m is sufficiently large. Moreover, a result about minimum Lee weights of certain Z/sub 4/ codes defined by Galois rings, which is similar to the result in Calderbank et al., is proved.

The theory of error-correcting codes derived from curves in an algebraic geometry was initiated by the work of Goppa as generalizations of Bose-Chaudhuri-Hocquenghem (BCH), Reed-Solomon (RS), and Goppa codes. The development of the theory has received intense consideration since that time and the purpose of the paper is to review this work. Elements of the theory of algebraic curves, at a level sufficient to understand the code constructions and decoding algorithms, are introduced. Code constructions from particular classes of curves, including the Klein quartic, elliptic, and hyperelliptic curves, and Hermitian curves, are presented. Decoding algorithms for these classes of codes, and others, are considered. The construction of classes of asymptotically good codes using modular curves is also discussed.

Newton's identities have played a significant role in decoding and minimum distance determination of cyclic and BCH codes. The present paper carries the notion over from cyclic codes to algebraic-geometric (AG) codes and introduces Newton's identities for AG codes, also for the purpose of minimum distance determination and decoding.

Linear codes over F/sub p/ often admit a natural representation as trace codes of codes that are defined over an extension field F/sub p/m. In the paper, the authors obtain estimates for the weights of subcodes of such trace codes. Their main result is a far-reaching generalization of the Carlitz-Uchiyama bound for the duals of binary BCH codes. In particular, they prove sharp bounds for the generalized Hamming weights of a large class of codes, including duals of BCH codes, classical Goppa codes, Melas codes, and arbitrary cyclic codes of length n=p/sup m/-1. The main tool is the theory of algebraic functions over finite fields, in particular the Hasse-Weil bound for the number of places of degree one. >

The paper presents a new procedure for decoding cyclic and BCH codes up to their actual minimum distance. It generalizes the Peterson decoding procedure and the procedure of Feng and Tzeng (1991) using nonrecurrent syndrome dependence relations. For a code with actual minimum distance d to correct up to t=[(d-1)/2] errors, the procedure requires a (2t+1)/spl times/(2t+1) syndrome matrix with known syndromes above the minor diagonal and unknown syndromes and their conjugates on the minor diagonal. In contrast to previous procedures, this procedure is primarily aimed at solving for the unknown syndromes instead of determining an error-locator polynomial. Decoding is then accomplished by determining the error vector as the inverse Fourier transform of the syndrome vector (S/sub 0/, S/sub 1/, S/sub n-1/). The authors show that with this procedure, all binary cyclic and BCH codes of length >

An interesting class of linear error-correcting codes has been found by Goppa [3], [4]. This paper presents algebraic decoding algorithms for the Goppa codes. These algorithms are only a little more complex than Berlekamp's well-known algorithm for BCH codes and, in fact, make essential use of his procedure. Hence the cost of decoding a Goppa code is similar to the cost of decoding a BCH code of comparable block length.

This paper deals with soft decision as a means to bridge the gap in performance between a receiver using hard decision symbol estimation followed by an algebraic decoder and a maximum-likelihood receiver. A measure of the reliability of the code symbol estimates is introduced to facilitate the decoding process. The decoding operation studied erases the least reliable received symbols and then applies an algorithm capable of correcting errors and erasures. This procedure, termed successive-erasure decoding (SED), was introduced by G. D. Forney in connection with general minimum-distance decoding (GMD). It is studied for binary and nonbinary transmission using polyphase signals on the additive white Gaussian noise (AWGN) channel. The exponential behavior of the error probability at high signal-to-noise ratio (SNR) is calculated and is supplemented by computer simulations. The results indicate that soft decision by successive erasures for binary transmission has properties not present in the nonbinary case. In the binary case the procedure is asymptotically optimum for increasing SNR's. On the nonbinary channel, however, the procedure is only capable of bridging part of the gap in performance between maximum-likelihood decoding (MLD) and hard decision decoding (HDD).

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, where r \geq 3 is odd and the exponents are relatively prime, together with the corresponding nonexpurgated codes.

This paper describes the application of selected block and convolutional coding techniques to digital transmission over an HF radio channel. Performance results are presented for interleaved binary Bose-Chaudhuri-Hocquenghem (BCH) codes, interleaved two-stage concatenated codes, and diffuse convolutional codes. The performance results are based upon raw error data recorded in transmission over a 640-km HF path, with various data runs representing the typical effects of frequency-selective and non-selective fading, atmospheric impulse noise, and interference from other users of the HF band. The performance of binary BCH codes with bit interleaving is presented and the selection of a code to meet a specified performance criterion is described. The sensitivity of specific codes to changing channel conditions is presented, along with the cost, in terms of interleaving, of designing for one set of channel conditions rather than others. Concatenated codes are discussed as a means of effective error control on channels with clustered errors. Performance data are presented for selected two-stage codes used with inner-stage word interleaving and the effects of varying certain of the code parameters are shown. Emphasis is placed on code designs that use the inner-stage code only for error detection and the outer-stage code mainly for erasure filling with only a small amount of symbol error correction. The impact of error clustering on the performance of concatenated codes is discussed. Two diffuse convolutional codes are evaluated with the use of recorded error data in computer simulations of their threshold-decoding algorithms. Performance of various configurations of these convolutional codes is given and a comparison is made with that of a simple block coding scheme having the same decoder storage requirements. The various coding techniques studied are compared on the basis of achievable performance as well as certain factors affecting the feasibility of implementation.