We present a new Reed-Solomon decoding algorithm, which embodies several refinements of an earlier algorithm. Some portions of this new decoding algorithm operate on symbols of length lgq bits; other portions operate on somewhat longer symbols. In the worst case, the total number of calculations required by the new decoding algorithm is proportional to nr, where n is the code's block length and r is its redundancy. This worst case workload is very similar to prior algorithms. But in many applications, average-case workload and error-correcting performance are both much better. The input to the new algorithm consists of n received symbols from GF(q), and n nonnegative real numbers, each of which is the reliability of the corresponding received symbol. Any conceivable errata pattern has a "score" equal to the sum of the reliabilities of its locations with nonzero errata values. A max-likelihood decoder would find the minimum score over all possible errata patterns. Our new decoding algorithm finds the minimum score only over a subset of these possible errata patterns. The errata within any candidate errata pattern may be partitioned into "errors" and "erasures," depending on whether the corresponding reliabilities are above or below an "erasure threshold." Different candidate errata patterns may have different thresholds, each chosen to minimize its corresponding ERRATA COUNT, which is defined as 2/spl middot/(number of errors)+(number of erasures). The new algorithm finds an errata pattern with minimum score among all errata patterns for which ERRATA COUNT/spl les/r+1 where r is the redundancy of the RS code. Conventional algorithms also require that the erasure threshold be set a priori; the new algorithm obtains the best answer over all possible settings of the erasure threshold. Conventional cyclic RS codes have length n=q-1, and their locations correspond to the nonzero elements of GF(q). The new algorithm also applies very naturally to RS codes which have been doubly extended by the inclusion of 0 and /spl infin/ as additional locations.

A detailed description is given of a fast soft decision decoding procedure for high-rate block codes. The high speed is made possible (in part) by using the symmetries of the code to simplify the syndrome decoding by table look-up and by making the best use of the soft decision information. The(128,106,8)BCH code is used as an example.

The fact that the general decoding problem for linear codes and the general problem of finding the weights of a linear code are both NP-complete is shown. This strongly suggests, but does not rigorously imply, that no algorithm for either of these problems which runs in polynomial time exists.

Since well-known decoding algorithms [1],[2] are able to correct both character errors and character erasures withq-ary Reed-Solomon codes, some modulation and demodulation schemes designed to be used with such codes provide a channel that hasqinputs andq + 1outputs,qof which correspond to theqinputs and one of which corresponds to the "erasure" symbol. This correspondence points om the relative advantages offered by a slightly more refined demodulation scheme, which creates a digital channel that hasqinputs and2_{q}outputs,qof which correspond to "strong" receptions of the inputs andqof which correspond to "weak" receptions of the inputs. For decoding purposes, allqweak outputs may be treated as erasures, but the fact that the channel now provides additional information facilitates improved decoding performance by reading the weak characters under the erasures.

A strategy is given for cooperative bidding by the players which results in the location of all 52 cards being encoded into a valid bridge auction which always terminates with a contract of six diamonds. Strategies are also given for encoding the card locations into auctions in which "double" and/or "redouble" are prohibited bids.

We show that when an inner linear cyclic binary code which has an irreducible check polynomial is concatenated with an appropriately chosen maximal-distance-separable outer code, then the overall code is cyclic OverGF(2). Using this theorem, we construct a number of linear cyclic binary codes which are better than any previously known. In particular, by taking the inner code to be a quadratic residue code, we obtain linear cyclic binary codes of lengthN, rateR, and distanceD \geq (1 - 2R)N/ \sqrt{2 \log N}, which compares favorably with the BCH distanceD \sim (2 \ln R^{-1})N/\log N, although it still fails to achieve the linear growth of distance with block length which is possible with noncyclic linear concatenated codes. While this construction yields many codes, including several with block lengths greater than10^{10^5}, we have not been able to prove that there are arbitrarily long codes of this type without invoking the Riemann hypothesis or the revised Artin conjecture, as the existence of long codes of our type is equivalent to the existence of large primespfor which the index of 2 is(p - 1)/2.

Goppa described a new class of linear noncyclic error-correcting codes in [1] and [2]. This paper is a summary of Goppa's work, which is not yet available in English.^1We prove the four most important properties of Goppa codes. 1) There existq-ary Goppa codes with lengths and redundancies comparable to BCH codes. For the same redundancy, the Goppa code is typically one digit longer. 2) All Goppa codes have an algebraic decoding algorithm which will correct up to a certain number of errors, comparable to half the designed distance of BCH codes. 3) For binary Goppa codes, the algebraic decoding algorithm assumes a special form. 4) Unlike primitive BCH codes, which are known to have actual distances asymptotically equal to their designed distances, long Goppa codes have actual minimum distances much greater than twice the number of errors, which are guaranteed to be correctable by the algebraic decoding algorithm. In fact, long irreducible Goppa codes asymptotically meet the Gilbert bound.

The class of codes introduced by Goppa [1]-[3] includes the BCH codes as a proper subset. It also includes a large subset of asymptotically good codes, each of which has an algebraic decoding algorithm for correcting some smaller number of errors. In Section 7 of [1], Goppa gives necessary and sufficient conditions for his codes to be isomorphic to cyclic codes under a certain correspondence. In this correspondence, we exhibit another correspondence which reveals that certain other Goppa codes (including the example of Goppa's Section 6) become cyclic when extended by an overall parity check. In particular, the extended Goppa codes with(n,k,d) = (2^m + 1, 2^m - 2m, 6)are isomorphic to the reversible cyclic codes with check polynomial(x + 1)f(x), wheref(x)is an irreducible polynomial of period2^m + 1.

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 lengthsnand fixed rateR. 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.

The weight enumerator of a code is the polynomial \begin{equation} W(x,y)= \sum_{r=0}^n A_r x^{n-r} y^r, \end{equation} wherendenotes the block length andA_r, denotes the number of codewords of weightr. LetCbe a self-dual code overGF(q)in which every weight is divisible byc. Then Gleason's theorem states that 1) ifq= 2 andc= 2, the weight enumerator ofCis a sum of products of the polynomialsx^2 + y^2andx^2y^2 (x^2 - y^2 )^2ifq= 2 andc= 4, the weight enumerator is a sum of products ofx^8 + 14x^4 y^4 + y^8andx^4 y^4 (x^4 - y^4)^4; and 3) ifq= 3 andc= 3, the weight enumerator is a sum of products ofx^4 + 8xy^3andy^3(x^3 - y^3)^3. In this paper we give several proofs of Gleason's theorem.

In this paper we present the weight distribution of all2^26cosets of the (32,6) first-order Reed-Muller code. The code is invariant under the complete affine group, of order32 \times 31 \times 30 \times 28 \times 24 \times16. In the Appendix we show (by hand computations) that this group partitions the2^26cosets into only 48 equivalence classes, and we obtain the number of cosets in each class. A simple computer program then enumerated the weights of the 32 vectors ih each of the 48 cosets. These coset enumerations also answer this equivalent problem: how well are the2^32Boolean functions of five variables approximated by the2^5linear functions and their complements?

In this paper, we establish the following result. Theorem:A_i, the number of codewords of weightiin the second-order binary Reed-Muller code of length2^mis given byA_i = 0unlessi = 2^{m-1}or2^{m-1} \pm 2^{m-l-j}, for somej, 0 \leq j \leq [m/2], A_0 = A_{2^m} = 1, and \begin{equation} \begin{split} A_{2^{m-1} \pm 2^{m-1-j}} = 2^{j(j+1)} &\{\frac{(2^m - 1) (2^{m-1} - 1 )}{4-1} \} \\ .&\{\frac{(2^{m-2} - 1)(2^{m-3} -1)}{4^2 - 1} \} \cdots \\ .&\{\frac{(2^{m-2j+2} -1)(2^{m-2j+1} -1)}{4^j -1} \} , \\ & 1 \leq j \leq [m/2] \\ \end{split} \end{equation} \begin{equation} A_{2^{m-1}} = 2 \{ 2^{m(m+1)/2} - \sum_{j=0}^{[m/2]} A_{2^{m-1} - 2^{m-1-j}} \}. \end{equation}

The decoding of BCH codes readily reduces to the solution of a certain key equation. An iterative algorithm is presented for solving this equation over any field. Following a heuristic derivation of the algorithm, a complete statement of the algorithm and proofs of its principal properties are given. The relationship of this algorithm to the classical matrix methods and the simplification which the algorithm takes in the special case of binary codes is then discussed. The generalization of the algorithm to BCH codes with a slightly different definition, the generalization of the algorithm to decode erasures as well as errors, and the extension of the algorithm to decode more thanterrors in certain eases are also presented.

In sequential decoding, the number of computations which the decoder must perform to decode the received digits is a random variable. In this paper, we derive a Paretian lower bound to the distribution of this random variable. We show thatP [C > L]L^{-\rho}, whereCis the number of computations which the sequential decoder must perform to decode a block of\Lambdatransmitted bits, and is a parameter which depends on the channel and the rate of the code. Our bound is valid for all sequential decoding schemes and all discrete memoryless channels. In Section II we give an example of a special channel for which a Paretian bound can be easily derived. In Sections III and IV we treat the general channel. In Section V we relate this bound to the memory buffer requirements of real-time sequential decoders. In Section VI, we show that this bound implies that certain moments of the distribution of the computation per digit are infinite, and we determine lower bounds to the rates above which these moments diverge. In most cases, our bounds coincide with previously known upper bounds to rates above which the moments converge. We conclude that the performance of systems using sequential decoding is limited by the computational and buffer capabilities of the decoder, not by the probability of making a decoding error. We further note that our bound applies only to sequential decoding, and that, in certain special cases (Section II), algebraic decoding methods prove superior.

The solution of Newton's identities over a field of characteristic two is the key step in decoding Bose-Chaudhuri-Hocquenghem codes. This paper introduces a simple transformation of variables which halves the size of the resulting matrix. This transformation can increase the decoder's speed by almost a factor of eight and decrease the decoder's storage requirements by almost a factor of four.

article Free Access Share on Program for Double-Dummy Bridge Problems—A New Strategy for Mechanical Game Playing Author: Elwyn R. Berlekamp Department of Electrical Engineering at Massachusetts Institute of Technology, Cambridge 39, Massachusetts Department of Electrical Engineering at Massachusetts Institute of Technology, Cambridge 39, MassachusettsView Profile Authors Info & Claims Journal of the ACMVolume 10Issue 3July 1963 pp 357–364https://doi.org/10.1145/321172.321182Published:01 July 1963Publication History 11citation514DownloadsMetricsTotal Citations11Total Downloads514Last 12 Months21Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF