Celebratio Mathematica

[1] E. R. Berlekamp: Machine solution of no-trump double-dummy bridge problems. Master's thesis, Massachussetts Institute of Technology, 20 August 1962. Advised by J. McCarthy. A summary of this thesis appeared in J. Assoc. Comput. Mach. 10:3 (1963). mastersthesis

[2] E. R. Berlekamp: “Program for double-dummy bridge problems: A new strategy for mechanical game playing,” J. Assoc. Comput. Mach. 10 : 3 (July 1963), pp. 357–364. Summary of the author’s 1962 Masters thesis. Zbl 0109.35206 article

[3] E. R. Berlekamp: Probabilistic mazes. Technical report 20878-4, Bell Telephone Laboratories, 20 June 1963. techreport

[4] E. R. Berlekamp: “A class of convolution codes,” Inform. Control 6 : 1 (March 1963), pp. 1–13. MR 0159718 Zbl 0214.47201 article

[5] E. R. Berlekamp: Block coding with noiseless feedback. Ph.D. thesis, Massachussetts Institute of Technology, 1964. Advised by R. G. Gallager. phdthesis

This thesis is concerned with the use of block codes to transmit information over two-way communication systems which have a discrete memoryless, noisy channel in the forward direction and a reverse channel which is noiseless and undelayed and has unlimited capacity. It has been known that the capacity in the forward direction is not increased by the reverse channel. It has also been known that the probability of error approaches zero exponentially with increasing block length at any fixed rate less than capacity. For a region of rates between a critical rate and capacity it has been known that the exponent with which the probability of error approaches zero cannot be improved by the use of feedback, and there was some question whether the feedback channel could be made to serve any useful purpose at all, either to improve the probability of error or to decrease the complexity of the coding and decoding operations.

In view of these results, we focus on primary attention on low rate codes, including zero-rate codes whose block length approaches infinity while the number of codewords remains fixed. We succeed in obtaining several new and improved bounds on the probability of error for such codes, both within and without feedback.

We evaluate the zero-rate exponents for arbitrary one-way channels. This new general result leads to improved lower bounds on the probability of error at low rates, via techniques recently introduced by C. E. Shannon and R. G. Gallager. We evaluate the zero-rate exponent for large classes of feedback channels, including all binary-input channels which satisfy certain symmetry requirements. These results lead to strengthened bounds on the probability of error for channels with feedback. We find that at low rates it is possible to obtain substantially improved error probabilities with the use of feedback. Although our results may be invalidated if the feedback channel is noisy, we show that the results are not effected by a delay in the feedback channel unless the delay is comparable to the block length.

Several constructive feedback coding strategies are presented. Using elaborate inductive arguments, we derive a class of coding strategies which are asymptotically optimum for the binary symmetric channel with feedback over a large region of rates. It is felt that these strategies could be profitably applied to problems in the statistical design of experiments whenever the situation is such that successive experiments may be modified according to the results of previous ones. Most previous studies in the statistical design of experiments have not permitted such modificiations. By utilizing this “feedback”, we not only find that it is possible to achieve much smaller error probability, but we show how.

[6] E. R. Berlekamp: “Note on recurrent codes,” IEEE Trans. Inf. Theory 10 : 3 (July 1964), pp. 257–258. Zbl 0124.11602 article

[7] E. R. Berlekamp: “On decoding binary Bose–Chaudhuri–Hocquenghem codes,” IEEE Trans. Information Theory 11 : 4 (October 1965), pp. 577–579. MR 0189921 Zbl 0143.41402 article

[8] E. R. Berlekamp, E. N. Gilbert, and F. W. Sinden: “A polygon problem,” Am. Math. Mon. 72 : 3 (March 1965), pp. 233–241. MR 0179680 Zbl 0132.41105 article

Edgar Nelson Gilbert	Related
F. W. Sinden	Related

[9] E. R. Berlekamp: Two identical binary erasure channels with feedback are exponentially better than one channel at low rates. Technical report SPS 37-37, Jet Propulsion Laboratory, 28 February 1966. Vol. IV, Section XXXI, Task No. 325-10701-1-3310 (125-21-01-01). techreport

[10] E. R. Berlekamp: “Distribution of cyclic matrices in a finite field,” Duke Math. J. 33 : 1 (1966), pp. 45–48. MR 0184934 Zbl 0138.01301 article

[11] R. Berlekamp, Elwyn: Nonbinary BCH decoding. Technical report 502, University of North Carolina, Chapel Hill, December 1966. Institute of Statistics Mimeo Series. An abstract for this was published in IEEE Trans. Inform. Theory 14:2 (1968). techreport

This paper shows that 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, we give a complete statement of the algorithm and proofs of its principal properties.

Additional sections of this paper then discuss the relationship of this algorithm to the classical matrix methods, the simplification which the algorithm takes in the special case of binary codes, 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 than \( t \) errors in certain cases. Each of these final sections of the paper may be read independently of the others.

[12] E. R. Berlekamp and L. Kleinrock: Analysis of channels with unidirectional drift. Space programs summary 37-39, Jet Propulsion Laboratory, 30 June 1966. Volume IV. techreport

[13] C. E. Shannon, R. G. Gallager, and E. R. Berlekamp: “Lower bounds to error probability for coding on discrete memoryless channels, II,” Inform. Control 10 : 5 (May 1967), pp. 522–552. MR 0216899 article

New lower bounds are presented for the minimum error probability that can be achieved through the use of block coding on noisy discrete memoryless channels. Like previous upper bounds, these lower bounds decrease exponentially with the block length \( N \). The coefficient of \( N \) in the exponent is a convex function of the rate. From a certain rate of transmission up to channel capacity, the exponents of the upper and lower bounds coincide. Below this particular rate, the exponents of the upper and lower bounds differ, although they approach the same limit as the rate approaches zero. Examples are given and various incidental results and techniques relating to coding theory are developed. The paper is presented in two parts: the first, appearing in the January issue, summarizes the major results and treats the case of high transmission rates in detail; the second, appearing here, treats the case of low transmission rates.

Claude Elwood Shannon	Related
Robert Gray Gallager	Related

[14] E. Berlekamp and I. M. Jacobs: “A lower bound to the distribution of computation for sequential decoding,” IEEE Trans. Inform. Theory 13 : 2 (April 1967), pp. 167–174. A Russian translation was published in Nekotoryye Voprosy Teorii Kodirovaniya (1970). article

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 that \[ P[C > L]L^{-\rho} ,\] where \( C \) is the number of computations which the sequential decoder must perform to decode a block of \( \Lambda \) transmitted 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.

[15] E. R. Berlekamp, H. Rumsey, and G. Solomon: “On the solution of algebraic equations over finite fields,” Inform. Control 10 : 6 (June 1967), pp. 553–564. MR 0230706 Zbl 0166.04803 article

This article gives new fast methods for decoding certain error-correcting codes by solving certain algebraic equations. As described by Peterson [1961], the locations of a Bose–Chaudhuri–Hocquenghem code over a field of characteristic \( p \) are associated with the elements of an extension field, \( \operatorname{GF}(p^k) \). The code is designed in such a way that the weighted power-sum symmetric functions of the error locations can be obtained directly by computing appropriately chosen parity checks on the received word. Good methods for computing the elementary symmetric functions from the weighted power-sum symmetric functions have been presented by Berlekamp [1967]. The elementary symmetric functions, \( \sigma_1 \), \( \sigma_2,\dots \), \( \sigma_t = 0 \) are the coefficients of an algebraic equation whose roots are the error locations \[ xt + \sigma_1xt - 1 + \sigma_2xt - 1 + \cdots + \sigma_t = 0. \]

Previous methods for finding the roots of this equation have searched all of the elements in \( \operatorname{GF}(p^k) \) [Chien 1964] or looked up the answer in a large table [Polkinghorn 1966]. We present here improved procedures for extracting the roots of algebraic equations of small degrees.

H. Rumsey	Related
Gustave Solomon	Related

[16] E. R. Berlekamp: “The enumeration of information symbols in BCH codes,” Bell Syst. Tech. J. 46 : 8 (October 1967), pp. 1861–1880. MR 0219344 Zbl 0173.21202 article

This paper presents certain formulas for \( I(q,n,d) \), the number of information symbols in the \( q \)-ary Bose–Chaudhuri–Hocquenghem code of block length \( n = q^m - 1 \) and designed distance \( d \). By appropriate manipulations on the \( m \)-digit \( q \)-ary representation of \( d \), we derive a simple linear recurrence for a sequence whose \( m \)th term is the number of information symbols in the BCH code.

In addition to an exact solution of all finite cases, we obtain exact asymptotic results, as \( n \) and \( d \) go to infinity while their ratio \( n/d \) remains fixed. In this limit, the number of information symbols increases as \( n^s \). Specifically, we show that for fixed \( u \), \( 0 \leq u \leq 1 \), \[ \lim_{m \rightarrow \infty} q^{-ms}I(q,q^m-1,uq^m) = 1 \] where \( s \) is a singular function of \( u \). The function \( s(u) \) is continuous and monotonic nonincreasing; it has derivative zero almost everywhere. Yet \( s(0) = 1 \) and \( s(1) = 0 \). For \( q=2 \), \( s(u) \) is plotted in Fig. 1.

[17] C. E. Shannon, R. G. Gallager, and E. R. Berlekamp: “Lower bounds to error probability for coding on discrete memoryless channels, I,” Inform. Control 10 : 1 (January 1967), pp. 65–103. MR 0210513 Zbl 0245.94007 article

New lower bounds are presented for the minimum error probability that can be achieved through the use of block coding on noisy discrete memoryless channels. Like previous upper bounds, these lower bounds decrease exponentially with the block length \( N \). The coefficient of \( N \) in the exponent is a convex function of the rate. From a certain rate of transmission up to channel capacity, the exponents of the upper and lower bounds coincide. Below this particular rate, the exponents of the upper and lower bounds differ, although they approach the same limit as the rate approaches zero. Examples are given and various incidental results and techniques relating to coding theory are developed. The paper is presented in two parts: the first, appearing here, summarizes the major results and treats the case of high transmission rates in detail; the second, to appear in the subsequent issue, treats the case of low transmission rates.

Claude Elwood Shannon	Related
Robert Gray Gallager	Related

[18] E. R. Berlekamp: “Factoring polynomials over finite fields,” Bell Syst. Tech. J. 46 : 8 (October 1967), pp. 1853–1859. MR 0219231 Zbl 0166.04901 article

[19] E. R. Berlekamp: “Weight enumeration theorems,” pp. 161–170 in Proceedings of the sixth annual Allerton conference on circuit and system theory (Monticello, IL, 2–4 October 1968). Edited by T. N. Trick and R. T. Chien. University of Illinois (Urbana, IL), 1968. MR 0263534 incollection

Robert T. Chien	Related
Timothy N. Trick	Related

[20] E. R. Berlekamp: Combinatorial games, I: Hex, Bridgit, and Shannon’s switching game. Technical report, Bell Telephone Laboratories, 1968. techreport

[21] E. R. Berlekamp: Grundy functions for certain classes of vines. Technical memo, Bell Telephone Laboratories, 1968. techreport

[22] E. R. Berlekamp: Algebraic coding theory. McGraw-Hill (New York), 1968. A 2nd revised edition was published in 1984 and a revision of that in 2015. A Russian translation was published in 1984. MR 0238597 Zbl 0988.94521 book

[23] E. R. Berlekamp: “A construction for partitions which avoid long arithmetic progressions,” Canad. Math. Bull. 11 (1968), pp. 409–414. MR 0232743 Zbl 0169.31905 article

[24] E. R. Berlekamp: “Nonbinary BCH decoding,” IEEE Trans. Inform. Theory 14 : 2 (March 1968), pp. 242. Abstract only. Abstract for a 1966 technical report. article

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 than \( t \) errors in certain eases are also presented.

[25] E. R. Berlekamp: “Block coding for the binary symmetric channel with noiseless, delayless feedback,” pp. 61–88 in Error correcting codes (Madison, WI, 6–8 May 1968). Edited by H. B. Mann. Publications of the Mathematics Research Center, United States Army, University of Wisconsin 21. John Wiley (New York), 1968. A Russian translation was published in Kibern. Sb. 9 (1972). MR 0234756 Zbl 0176.49404 incollection

[26] E. R. Berlekamp: “A survey of coding theory,” pp. 3–11 in Recent progress in combinatorics (Waterloo, ON, 20–31 May 1968). Edited by W. T. Tutte. Academic Press (New York), 1969. MR 0252090 Zbl 0199.54101 incollection

[27] E. R. Berlekamp: Techniques for computing weight enumerators. Technical report, Bell Telephone Laboratories, 1969. techreport

[28] E. R. Berlekamp and N. J. A. Sloane: “Restrictions on weight distribution of Reed–Muller codes,” Inform. Control 14 : 5 (May 1969), pp. 442–456. MR 0243897 Zbl 0179.49101 article

[29] E. R. Berlekamp: “Negacyclic codes for the Lee metric,” pp. 298–316 in Combinatorial mathematics and its applications (Chapel Hill, NC, 10–14 April 1967). Edited by R. C. Bose and T. A. Dowling. UNC Monograph Series in Probability and Statistics 4. University of North Carolina Press (Chapel Hill, NC), 1969. MR 0250738 Zbl 0304.94018 incollection

Thomas A. Dowling	Related
Raj Chandra Bose	Related

[30] E. R. Berlekamp: The probabilities of certain bridge hands. Technical report, Bell Telephone Laboratories, 1969. techreport

[31] E. R. Berlekamp: “On subsets with intersections of even cardinality,” Canad. Math. Bull. 12 (1969), pp. 471–474. MR 0249303 Zbl 0272.05004 article

[32] E. R. Berlekamp: On the Carlitz–Uchiyama bound. Technical report, Bell Telephone Laboratories, 1969. techreport

[33] E. R. Berlekamp: Burst properties of certain linear binary codes. Technical report MM70-1216-2, Case 20878-4, Bell Telephone Laboratories, 15 January 1970. techreport

[34] E. R. Berlekamp and R. L. Graham: “Irregularities in the distributions of finite sequences,” J. Number Theory 2 : 2 (May 1970), pp. 152–161. MR 0269605 Zbl 0201.05001 article

[35] E. R. Berlekamp: “The weight enumerators for certain subcodes of the second order binary Reed–Muller codes,” Inform. Control 17 : 5 (December 1970), pp. 485–500. MR 0290857 Zbl 0211.51304 article

[36] E. Berlekamp and I. M. Jacobs: “A lower bound to the distribution of computation for sequential decoding,” pp. 230–248 in Nekotoryye voprosy teorii kodirovaniya [Some problems of coding theory]. Edited by E. L. Bloch and M. S. Pinsker. Mir (Moscow), 1970. Russian translation of an article published in IEEE Trans. Inform. Theory 13:2 (1970). Zbl 0221.94011 incollection

E. L. Bloch	Related
Mark Shlemovich Pinsker	Related
I. M. Jacobs	Related

[37] E. R. Berlekamp: “Some mathematical properties of a scheme for reducing the bandwidth of motion pictures by Hadamard smearing,” Bell Syst. Tech. J. 49 : 6 (July–August 1970), pp. 969–986. MR 0270810 Zbl 0197.45401 article

M. R. Schroeder recently proposed a scheme for compression of motion picture data by taking the difference of two successive frames and then smearing. The smearing is accomplished by a Hadamard matrix. If the Hadamard matrix is of a certain particularly well-understood type, then we show that if the input differential picture consists of a small odd number of large pulses of identical magnitudes (but arbitrary signs), then the output will consist of three components:

Large pulses of equal magnitude and the correct signs, matching each of the input pulses.
One additional “stray” large pulse, of magnitude equal to the others, but located at a point where the input was zero.
Scattered pulses of amplitude low relative to the pulses of types i and ii, but so numerous that they consume \( (\pi - 2)/\pi \) of the total energy of the output differential picture.

We give an explicit formula for the amplitude of each of these pulses. The problem of determining the distributions of all possible outputs of the proposed system for other classes of inputs is shown to be equivalent to the unsolved problem of finding the weight enumerators for the cosets of the first order Reed–Muller codes.

[38] N. J. A. Sloane and E. R. Berlekamp: “Weight enumerator for second-order Reed–Muller codes,” IEEE Trans. Information Theory 16 : 6 (November 1970), pp. 745–751. MR 0274196 Zbl 0205.20701 article

[39] E. R. Berlekamp: Doubly extended RS codes are cyclic after prenormalization. Technical report, Bell Telephone Laboratories, 1970. techreport

[40] E. R. Berlekamp: “On sets of ternary vectors whose only linear dependencies involve an odd number of vectors,” Canad. Math. Bull. 13 : 3 (1970), pp. 363–366. MR 0277544 Zbl 0233.15004 article

[41] E. R. Berlekamp: “Factoring polynomials over large finite fields,” Math. Comp. 24 : 111 (July 1970), pp. 713–735. MR 0276200 Zbl 0247.12014 article

This paper reviews some of the known algorithms for factoring polynomials over finite fields and presents a new deterministic procedure for reducing the problem of factoring an arbitrary polynomial over the Galois field \( \operatorname{GF}(p^m) \) to the problem of finding the roots in \( \operatorname{GF}(p) \) of certain other polynomials over \( \operatorname{GF}(p) \). The amount of computation and the storage space required by these algorithms are algebraic in both the degree of the polynomial to be factored and the logarithm of the order of the finite field.

Certain observations on the application of these methods to the factorization of polynomials over the rational integers are also included.

[42] E. R. Berlekamp and D. D. Sullivan: “Some results on normalized truncation groups,” pp. 1–11 in Proceedings of the UMR Mervin J. Kelly communications conference (Rolla, MO, 5–7 October 1970). Edited by J. R. Betten and W. H. Tranter. IEEE (New York), 1970. incollection

Mervin Joe Kelly	Related
Josef Betten	Related
Daniel D. Sullivan	Related

[43] E. R. Berlekamp: “Coding theory and the Mathieu groups,” Inform. Control 18 : 1 (February 1971), pp. 40–64. MR 0275981 Zbl 0217.28602 article

Let \( \mathscr{M}_{24} \) denote the Mathieu group on 24 points. Let \( \mathscr{G} \) be the subgroup of \( \mathscr{M}_{24} \) which has three sets of transitivity, the eight points on a Golay code-word (or Steiner octuple), one additional point, and the remaining 15 points. Using elementary results from the subject of algebraic coding theory, we present a new proof of the fact that \( \mathscr{G} \) acts on the eight points as the alternating group, \( \mathscr{A}_8 \), and on the 15 points as the general linear group, \( \mathscr{GL}(4,2) \). This result and other properties of the Mathieu groups obtained from it are then used to obtain the symmetry groups of the Nordstrom–Robinson nonlinear \( (15,8) \) code and the linear, cyclic \( (15,7) \) and \( (21,12) \) BCH codes and the \( (21, 10) \) dual of a projective geometry code, all of which have distance 5.

[44] È. Berlekèmp: Algebraicheskaya teoriya kodirovaniya [Algebraic coding theory]. Edited by S. D. Berman. Mir (Moscow), 1971. Russian translation of 1968 original. MR 0282723 Zbl 0256.94006 book

[45] A. M. Kerdock: “A class of low-rate nonlinear binary codes,” Inform. Control 20 : 2 (March 1972), pp. 182–187. ghost-written and communicated by Berlekamp. MR 0345707 Zbl 0271.94016 article

[46] E. R. Berlekamp and L. R. Welch: “Weight distributions of the cosets of the \( (32,6) \) Reed–Muller code,” IEEE Trans. Information Theory 18 : 1 (January 1972), pp. 203–207. MR 0396054 Zbl 0228.94003 article

In this paper we present the weight distribution of all \( 2^2\,6 \) cosets of the \( (32,6) \) first-order Reed–Muller code. The code is invariant under the complete affine group, of order \[ 32 \times 31 \times 30 \times 28 \times 24 \times 16 .\] In the Appendix we show (by hand computations) that this group partitions the \( 2^2\,6 \) cosets 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 in each of the 48 cosets. These coset enumerations also answer this equivalent problem: how well are the \( 2^3\,2 \) Boolean functions of five variables approximated by the \( 2^5 \) linear functions and their complements?

[47] E. R. Berlekamp: “Factoring polynomials,” pp. 1–7 in Proceedings of the third southeastern conference on combinatorics, graph theory and computing (Boca Raton, FL, 28 February–2 March 1972). Edited by F. Hoffman, R. B. Levow, and R. S. D. Thomas. Congressus Numeratium 6. Utilitas Mathematica (Winnipeg), 1972. MR 0349641 Zbl 0262.12011 incollection

R. B. Levow	Related
Frederick Ludwig Hoffman	Related
Robert S. D. Thomas	Related

[48] E. R. Berlekamp and F. K. Hwang: “Constructions for balanced Howell rotations for bridge tournaments,” J. Comb. Theory A 12 : 2 (March 1972), pp. 159–166. MR 0309757 Zbl 0238.05012 article

[49] E. R. Berlekamp: A survey of algebraic coding theory: Lectures held at the Department for Automation and Information (Udine, Italy, July 1970). Courses and Lectures, International Centre for Mechanical Sciences 28. Springer (Vienna), 1972. Zbl 0286.94008 book

[50] E. R. Berlekamp: “Long primitive binary BCH codes have distance \( d\leq 2n \) \( \ln R^{-1}/\log n\cdots \),” IEEE Trans. Information Theory 18 : 3 (May 1972), pp. 415–426. MR 0335129 Zbl 0237.94002 article

[51] E. R. Berlekamp, F. J. MacWilliams, and N. J. A. Sloane: “Gleason’s theorem on self-dual codes,” IEEE Trans. Information Theory 18 : 3 (May 1972), pp. 409–414. MR 0335128 Zbl 0239.94005 article

The weight enumerator of a code is the polynomial \[ W(x,y) = \sum_{r=0}^n A_r x^{n-r} y^r \] where \( n \) denotes the block length and \( A_r \) denotes the number of codewords of weight \( r \). Let \( C \) be a self-dual code over \( \operatorname{GF}(q) \) in which every weight is divisible by \( c \). Then Gleason’s theorem states that

if \( q = 2 \) and \( c = 2 \), the weight enumerator of \( C \) is a sum of products of the polynomials \[ x^2 + y^2 \quad\text{and}\quad x^2 y^2 (x^2 - y^2 )^2 ;\]
if \( q = 2 \) and \( c = 4 \), the weight enumerator is a sum of products of \[ x^8 + 14x^4 y^4 + y^8 \quad\text{and}\quad x^4 y^4 (x^4 - y^4)^4 ;\]
if \( q = 3 \) and \( c = 3 \), the weight enumerator is a sum of products of \[ x^4 + 8xy^3 \quad\text{and}\quad y^3(x^3 - y^3)^3 .\]

In this paper we give several proofs of Gleason’s theorem.

Jessie MacWilliams	Related
Neil James Alexander Sloane	Related

[52] E. R. Berlekamp: “A survey of coding theory,” J. Roy. Statist. Soc. Ser. A 135 : 1 (1972), pp. 44–73. MR 0449862 article

[53] E. R. Berlekamp: “Some recent results on the combinatorial game called ‘Welter’s Nim’,” pp. 203–204 in Proceedings of the sixth annual conference on information sciences and systems (23–24 March 1972, Princeton, NJ). Edited by M. E. Van Valkenburg and M. Edelberg. Department of Electrical Engineering, Princeton University, 1972. incollection

Murray Edelberg	Related
Mac Elwyn Van Valkenburg	Related

[54] E. R. Berlekamp: “Block coding for the binary symmetric channel with noiseless, delayless feedback,” Kibern. Sb., Nov. Ser. 9 (1972), pp. 5–29. Russian translation of an article published in Error correcting codes (1968). Zbl 0253.94006 article

[55] E. R. Berlekamp: An asymptomatic expansion for the quantization error of closely spaced uniform quantizers with Gaussian input. Memo ERL-M381, UCB College of Engineering and Electronic Research Lab, 1973. techreport

[56] E. R. Berlekamp and O. Moreno: “Extended double-error-correcting binary Goppa codes are cyclic,” IEEE Trans. Information Theory 19 : 6 (November 1973), pp. 817–818. MR 0368919 Zbl 0276.94004 article

The class of codes introduced by Goppa [1970, 1971] and Berlekamp [1973] 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 [1970], 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) \), where \( f(x) \) is an irreducible polynomial of period \( 2^m+1 \).

[57] E. R. Berlekamp: “Goppa codes,” IEEE Trans. Information Theory 19 : 5 (September 1973), pp. 590–592. MR 0378991 Zbl 0269.94003 article

Goppa described a new class of linear noncyclic error-correcting codes in [1970] and [1971]. This paper is a summary of Goppa’s work, which is not yet available in English. We prove the four most important properties of Goppa codes.

There exist \( q \)-ary Goppa codes with lengths and redundancies comparable to BCH codes. For the same redundancy, the Goppa code is typically one digit longer.
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.
For binary Goppa codes, the algebraic decoding algorithm assumes a special form.
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.

[58] E. R. Berlekamp, J. H. van Lint, and J. J. Seidel: “A strongly regular graph derived from the perfect ternary Golay code,” pp. 25–30 in A survey of combinatorial theory (Fort Collins, CO, 9–11 September 1971). Edited by J. N. Srivastava. North-Holland (Amsterdam), 1973. MR 0364015 Zbl 0258.05129 incollection

Jagdish N. Srivastava	Related
Johan Jacob Seidel	Related
Jacobus Hendricus van Lint	Related

[59] E. R. Berlekamp: “Engineering and public service,” The Bridge 69 (1973), pp. 1–3. article

[60] E. R. Berlekamp: “Book review: Jacobus H. van Lint, ‘Coding theory’,” IEEE Trans. Inform Theory 19 : 1 (January 1973), pp. 138. article

[61] E. R. Berlekamp: The Golay–Viterbi concatenation scheme. Technical report 32-1526, Jet Propulsion Laboratory, 1973. Vol. XVI. techreport

[62] E. R. Berlekamp: “The Hackenbush number system for compression of numerical data,” Inform. Control 26 : 2 (October 1974), pp. 134–140. MR 0354140 Zbl 0286.68037 article

The Hackenbush number system is a method of representing numbers by expressing the integer part in unary and the fractional part in binary. The representation absorbs the sign bit and binary point into the string of binary digits which represents the number. Conversion between the Hackenbush representation and the more conventional fixed and floating point representations requires approximately the same small amount of computation as is required to convert between the fixed and floating representations. If the numbers to be represented are selected from a known zero-mean distribution which has bounded height and tails that fall off exponentially or faster, the \( m \)-bit Hackenbush representation is typically more accurate than any floating point representation. For example, if the numbers are selected from the normal Gaussian distribution, the mean-square error of the \( m \)-bit Hackenbush representation is less than the mean-square error of any (arbitrarily complex) (\( m-1 \))-bit representation, and it is comparable to the mean square quantization error of the (\( m+n \))-bit normalized floating point representation which has 1 bit of sign, \( n+1 \) bits of exponent, and \( (m-2) \) bits of characteristic, for all \( n \).

[63] E. R. Berlekamp and J. Justesen: “Some long cyclic linear binary codes are not so bad,” IEEE Trans. Information Theory 20 : 3 (May 1974), pp. 351–356. MR 0381820 Zbl 0309.94023 article

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 over \( \operatorname{GF}(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 length \( N \), rate \( R \), and distance \[ D \geq (1 - 2R)N/\sqrt{2\log N} ,\] which compares favorably with the BCH distance \[ D \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 than \( 10^{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 primes \( p \) for which the index of 2 is \( (p-1)/2 \).

[64] Key papers in the development of coding theory. Edited by E. R. Berlekamp. IEEE Press Selected Reprint Series. IEEE Press (New York), 1974. MR 0384299 Zbl 0910.94001 book

[65] E. R. Berlekamp, H. M. Fredricksen, and R. C. Proto: “Minimum conditions for uniquely determining the generator of a linear sequence,” Utilitas Math. 5 (1974), pp. 305–315. MR 0412158 Zbl 0284.12010 article

R. C. Proto	Related
H. M. Fredricksen	Related

[66] E. R. Berlekamp, D. E. Knuth, J. Lederberg, R. A. Liebler, H. Rosenblum, and V. A. Vyssotsky: Report of the DARPA study group on advanced computer memory concepts, 1975. misc

H. Rosenblum	Related
Donald Ervin Knuth	Related
Joshua Lederberg	Related
Richard A. Leibler	Related
Victor Alexander Vyssotsky	Related

[67] E. R. Berlekamp: “Algebraic codes For improving the reliability of tape storage,” pp. 497–499 in National computer conference (Anaheim, CA, 19–22 May 1975). AFIPS Conference Proceedings 44. AFIPS Press (Montvale, NJ), 1975. incollection

[68] E. R. Berlekamp: “The design of slowly shrinking labelled squares,” pp. 25–27 in Special issue dedicated to Derrick Henry Lehmer, published as Math. Comp. 29 : 129. American Mathematical Society (Providence, RI), January 1975. MR 0373933 Zbl 0341.05019 incollection

[69] E. R. Berlekamp: Speedup for the CDC 6600. Working paper 463, Institute For Defense Analysis, 1976. techreport

[70] E. R. Berlekamp: “Making change,” Math. Mag. 49 : 4 (September 1976), pp. 195–198. MR 0410846 Zbl 0342.60066 article

[71] E. R. Berlekamp: “An analog to the discriminant over fields of characteristic two,” J. Algebra 38 : 2 (February 1976), pp. 315–317. MR 0404197 Zbl 0327.12101 article

[72] E. R. Berlekamp: Merging and sorting on Cray I. Working paper 464, Institute For Defense Analysis, 1976. techreport

[73] E. R. Berlekamp: “Cooperative bridge bidding,” IEEE Trans. Inform. Theory 22 : 6 (November 1976), pp. 753–756. correspondence. article

[74] E. R. Berlekamp: Speedup for the Cray I. Working paper 465, Institute For Defense Analysis, 1976. techreport

[75] E. R. Berlekamp: “Long block codes which use soft decisions and correct erasure bursts without interleaving,” pp. 1–2 in NTC ’77 conference record (Los Angeles, 5–7 December 1977), vol. 1. IEEE (New York), 1977. National Telecommunications Conference. incollection

[76] E. R. Berlekamp and J. L. Ramsey: “Readable erasures improve the performance of Reed–Solomon Codes,” IEEE Trans. Inform. Theory 24 : 5 (September 1978), pp. 632–633. article

Since well-known decoding algorithms [Fornery 1966; Berlekamp 1968] are able to correct both character errors and character erasures with \( q \)-ary Reed–Solomon codes, some modulation and demodulation schemes designed to be used with such codes provide a channel that has \( q \) inputs and \( q + 1 \) outputs, \( q \) of which correspond to the \( q \) inputs 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 has \( q \) inputs and \( 2_q \) outputs, \( q \) of which correspond to “strong” receptions of the inputs and \( q \) of which correspond to “weak” receptions of the inputs. For decoding purposes, all \( q \) weak 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.

[77] E. R. Berlekamp, R. J. McEliece, and H. C. A. van Tilborg: “On the inherent intractability of certain coding problems,” IEEE Trans. Information Theory 24 : 3 (1978), pp. 384–386. MR 0495180 Zbl 0377.94018 article

Robert J. McEliece	Related
Henk C. A. van Tilborg	Related

[78] E. R. Berlekamp: “Book Review: Robert J. McEliece, ‘The theory of information and coding: A mathematical framework for communication’,” Bull. Am. Math. Soc. 84 : 6 (1978), pp. 1351–1353. MR 1567098 article

[79] E. R. Berlekamp: “The technology of error-correcting codes,” Proc. IEEE 68 : 5 (May 1980), pp. 564–593. article

This paper is a survey of error-correcting codes, with emphasis on the costs of encoders and decoders, and the relationship of these costs to various important system parameters such as speed and delay. Following an introductory overview, the remainder of this paper is divided into three sections corresponding to the three major types of channel noise: white Gaussian noise, interference, and digital errors of the sort which occur in secondary memories such as disks. Appendix A presents some of the more important facts about modern implementations of decoders for long high-rate Reed–Solomon codes, which play an important role throughout the paper. Appendix B investigates some important aspects of the tradeoffs between error correction and error detection.

[80] P. J. Denning, D. H. Brandin, D. C. Schwartz, and G. I. Davida: “Report of the public cryptography study group,” Comm. ACM 24 : 7 (July 1981), pp. 434–449. 1979–1981 report of an American Council of Education study group. article

Daniel C. Schwartz	Related
David H. Brandin	Related
George I. Davida	Related
Peter J. Denning	Related

[81] E. R. Berlekamp, J. H. Conway, and R. K. Guy: Winning ways for your mathematical plays, vol. 1: Games in general. Academic Press (London and New York), 1982. A German translation of this volume was published in two parts as Gewinnen: Strategien für mathematische Spiele Band 1: Von der Pike auf (1985) and Band 2: Bäumchen-wechsle-dich (1985). Likewise, a second English edition was published in two parts in 2001 (“Volume 1”) and 2003 (“Volume 2”). MR 654501 Zbl 0485.00025 book

John Horton Conway	Related
Richard K. Guy	Related

[82] E. R. Berlekamp, J. H. Conway, and R. K. Guy: Winning ways for your mathematical plays, vol. 2: Games in particular. Academic Press (London and New York), 1982. A German translation of this volume was published in two parts as Gewinnen: Strategien für mathematische Spiele Band 3: Fallstudien (1986) and Band 4: Solitairspiele (1985). Likewise, a second English edition was published in 2003 (“Volume 3”) and 2003 (“Volume 4”). MR 654502 book

John Horton Conway	Related
Richard K. Guy	Related

[83] E. Berlekamp: “Bit-serial Reed–Solomon encoders,” IEEE Trans. Inf. Theory 28 : 6 (November 1982), pp. 869–874. Zbl 0492.94016 article

[84] E. R. Berlekamp: “The construction of fast, high-rate, soft decision block decoders,” IEEE Trans. Inform. Theory 29 : 3 (May 1983), pp. 372–377. MR 712403 article

[85] E. R. Berlekamp: “Error-correcting codes for digital audio,” pp. 127–139 in Digital audio (Rye, NY, 3–6 June 1982). Edited by B. Blesser, B. Locanthi, and T. G. Stockham, Jr. Audio Engineering Society (New York), 1983. incollection

Barry Blesser	Related
Thomas G. Stockham, Jr.	Related
Bartholomew Nicholas Locanthi	Related

[86] E. R. Berlekamp: Algebraic coding theory, 2nd revised edition. Aegean Park Press (Laguna Hills, CA), 1984. Revised republication of 1968 original. Zbl 1320.94002 book

[87] E. R. Berlekamp and R. J. McEliece: “Average case optimized buffered decoders,” pp. 145–158 in The impact of processing techniques on communications (Chateau de Bonas, France, 11–22 July 1983). Edited by J. K. Skwirzynski. NATO ASI Series 91. Springer (Dordrecht), 1985. incollection

Robert J. McEliece	Related
J. K. Skwirzynski	Related

[88] E. R. Berlekamp, J. H. Conway, and R. K. Guy: Gewinnen. Strategien für mathematische Spiele [Winning. Strategies for mathematical games], vol. 1: Von der Pike auf [From the ground up]. Friedrich Vieweg & Sohn (Braunschweig), 1985. With a foreword by Konrad Jacobs, Maria Reményi and Gerta Seiffert. German translation (with adapted title) of the first half of Winning ways for your mathematical plays, vol. 1 (1982). MR 830941 Zbl 0584.00006 book

Maria Reményi	Related
Konrad Jacobs	Related
Gerta Seiffert	Related
Richard K. Guy	Related
John Horton Conway	Related

[89] E. R. Berlekamp, J. H. Conway, and R. K. Guy: Gewinnen. Strategien für mathematische Spiele [Winning. Strategies for mathematical games], vol. 4: Solitairspiele [Solitaire games]. Friedrich Vieweg & Sohn (Braunschweig), 1985. German translation (with adapted title) of (approximately) the second half of Winning ways for your mathematical plays vol. 2 (1982). MR 838083 Zbl 0584.00009 book

John Horton Conway	Related
Richard K. Guy	Related

[90] E. R. Berlekamp, R. J. Currie, R. J. McEliece, C. K. Rushforth, and P. Tong: “An error-control code with an imbalance of ones and zeros to provide a residual carrier component,” pp. 31.1.1–31.1.4 in Communications-computers: Teamed for the ’90’s (Monterey, CA, 5–9 October 1986), vol. 2. IEEE (Piscataway, NJ), 1986. incollection

We consider in this paper a direct sequence spread-spectrum communication system employing an error-control code having an imbalance of ones and zeroes. The primary motivation for using such a code is to provide a carrier component for synchronization as an alternative to the transmisson of a separate pilot tone. We evaluate the performance of this system when a concatenated code whose inner code is a constant-weight subcode of the \( (24,12) \) extended Golay code and whose outer code is a Reed–Solomon code. We consider the effects of both white Gaussian noise and burst jamming, and we evaluate several decoding algorithms with different complexities and different coding gains. Near-maximum-likelihood decoding can be realized at the lowest data rates of interest, while successively less complicated algorithms achieving corresponding smaller coding gains must be used as the data rate increases. The performance of this system compares favorably with that of a more conventional pilot-tone system.

Craig K. Rushforth	Related
Robert J. McEliece	Related
R. J. Currie	Related
Po Tong	Related

[91] E. R. Berlekamp, J. H. Conway, and R. K. Guy: Gewinnen. Strategien für mathematische Spiele [Winning. Strategies for mathematical games], vol. 3: Fallstudien [Case studies]. Friedrich Vieweg & Sohn (Braunschweig), 1986. German translation (with adapted title) of (approximately) the first half of Winning ways for your mathematical plays vol. 2 (1982). MR 838082 Zbl 0584.00008 book

John Horton Conway	Related
Richard K. Guy	Related

[92] E. R. Berlekamp: If tennis players are equally good, server has no advantage. Technical memo, Cyclotomics, Inc., 22 September 1986. techreport

[93] E. R. Berlekamp, J. H. Conway, and R. K. Guy: Gewinnen. Strategien für mathematische Spiele [Winning. Strategies for mathematical games], vol. 2: Bäumchen-wechsle-dich. Friedrich Vieweg & Sohn (Braunschweig), 1986. With a foreword by Konrad Jacobs, Maria Reményi and Gerta Seiffert. German translation (with adapted title) of the second half of Winning ways for your mathematical plays, vol. 1 (1982). MR 830940 Zbl 0584.00007 book

Maria Reményi	Related
Konrad Jacobs	Related
Gerta Seiffert	Related
Richard K. Guy	Related
John Horton Conway	Related

[94] E. R. Berlekamp: Variable depth helical interleavers. Technical report, Cyclotomics, Inc., 1986. report to NSF. techreport

[95] E. R. Berlekamp, R. E. Peile, and S. P. Pope: “The application of error control to communications,” IEEE Comm. Mag. 25 : 4 (April 1987), pp. 44–57. article

Robert E. Peile	Related
S. P. Pope	Related

[96] E. R. Berlekamp: “Blockbusting and domineering,” J. Combin. Theory Ser. A 49 : 1 (1988), pp. 67–116. What the author describes as an “introductory advertisement” to this article was published in The lighter side of mathematics (1994). MR 957210 Zbl 0651.90092 article

We introduce a new game called blockbusting and a generalization of “overheating” which solves this game precisely. We then exhibit a blockbusting-based strategy for playing sums and differences of many types of \( 2\times n \) and \( 3\times n \) domineering positions. We prove this strategy to be worthwhile under certain restrictive circumstances, and we then remove these restrictions and determine the values of certain variations of the \( 2\times n \) and \( 3\times n \) domineering games, as cataloged in Appendix A. Our formulas involving generalized overheating and heating give precise values for these games, even though these games have many descendant positions whose values remain unknown. Our formulas also give the values of other classes of \( 2\times n \) and \( 3\times n \) domineering games to within tiny-ish infinitesimals of known sign. Appendix B gives three such classes of games and a fourth (closely related) class for which the tempting conjectures fail.

[97] E. R. Berlekamp and P. T. Liu: “Elongated burst correction with Reed–Solomon codes” in International conference on communication technology (Beijing, China, 12–14 July 1989). Publishing House of Electronics Industry (Beijing), 1989. incollection

[98] E. Berlekamp: “Two-person, perfect-information games,” pp. 275–287 in The legacy of John von Neumann (Hempstead, NY, 29 May–4 June 1988). Edited by J. Glimm, J. Impagliazzo, and I. Singer. Proceedings of Symposia in Pure Mathematics 50. American Mathematical Society (Providence, RI), 1990. Parts of this are identical to an article published in The lighter side of mathematics (1994). MR 1067762 Zbl 0714.90109 incollection

John Impagliazzo	Related
James G. Glimm	Related
Isadore M. Singer	Related	Volume
John von Neumann	Related

[99] E. Berlekamp: “Introductory overview of mathematical Go endgames,” pp. 73–100 in Combinatorial games (Columbus, OH, 6–7 August 1990). Edited by R. K. Guy. Proceedings of Symposia in Applied Mathematics 43. American Mathematical Society (Providence, RI), 1991. MR 1095541 Zbl 0744.90103 incollection

[100] E. Berlekamp and D. Wolfe: Mathematical Go: Chilling gets the last point. A K Peters (Wellesley, MA), 1994. With a foreword by James Davies. MR 1274921 Zbl 0852.90149 book

James Davies	Related
David Wolfe	Related

[101] E. R. Berlekamp: “Introduction to blockbusting and domineering,” pp. 137–148 in The lighter side of mathematics: Proceedings of the Eugène Strens memorial conference on recreational mathematics and its history. Edited by R. K. Guy and R. E. Woodrow. MAA Spectrum. Cambridge University Press, 1994. The author describes this as an “introductory advertisement” to an article published in J. Combin. Theory Ser. 49:1 (1988). Parts of it are identical to an article published in Proceedings of the John von Neumann Symposium (1988). incollection

R. E. Woodrow	Related
Richard K. Guy	Related
Eugène Strens	Related

[102] E. R. Berlekamp and Y. Kim: “Where is the thousand dollar ko?,” Go World 71 (1994), pp. 65–80. A later version of this was published in More games of no chance (1996). article

[103] E. Berlekamp, G. Seroussi, and P. Tong: “A hypersystolic Reed–Solomon decoder,” pp. 205–241 in Reed–Solomon codes and their applications. Edited by S. B. Wicker and V. K. Bhargava. IEEE Press (Piscataway, NJ), 1994. Zbl 1126.94356 incollection

Vijay K. Bhargava	Related
Gadiel Seroussi	Related
Po Tong	Related
Stephen B. Wicker	Related

[104] H. Kressel, E. R. Berlekamp, H. K. Bowen, R. M. Davis, J. F. Engelberger, G. D. Laubach, R. A. Pritzker, R. W. Schmitt, and G. L. Turin: Risk and innovation: The role and importance of small, high-tech companies in the U.S. economy. The National Academies Press (Washington, DC), 1995. by the National Academy of Engineering’s Committee on Technology, Management, and Capital in Small High-Tech Companies. book

R. W. Schmitt	Related
H. K. Bowen	Related
H. Kressel	Related
G. D. Laubach	Related
George L. Turin	Related
R. M. Davis	Related
R. A. Pritzker	Related
J. F. Engelberger	Related

[105] E. Berlekamp: “The economist’s view of combinatorial games,” pp. 365–405 in More games of no chance (Berkeley, CA, 11–21 July 2000). Edited by R. J. Nowakowski. MSRI Publications 29. Cambridge University Press, 1996. MR 1427978 Zbl 0872.90131 incollection

We introduce two equivalent methodologies for defining and computing a position’s mean (value of playing Black rather than White) and temperature (value of next move). Both methodologies apply in more generality than the classical one. The first, following the notion of a free market, relies on the transfer of a “tax” between players, determined by continuous competitive auctions. The second relies on a generalized thermograph, which reduces to the classical thermograph when the game is loop-free.

When a sum of games is played optimally according the economic rules described, the mean (which is additive) and the temperature determine the final score precisely.

This framework extends and refines several classical notions. Thus, finite games that are numbers in Conway’s sense are now seen to have negative natural temperatures. All games can now be viewed as terminating naturally with integer scores when the temperature reaches \( -1 \).

[106] E. R. Berlekamp, M. Müller, and B. Spight: Generalized thermography: Algorithms, implementation, and application to Go endgames. Technical report TR-96-030, International Computer Science Institute (Berkeley, CA), October 1996. techreport

Thermography [Berlekamp et al. 1982] is a powerful method for analyzing combinatorial games. It has been extended to games that contain loops in their game graph by Berlekamp [1996]. We survey the main ideas of this method and discuss how it applies to Go endgames. After a brief review of the methodology, we develop an algorithm for generalized thermography and describe its implementation.

To illustrate the power and scope of the resulting program, we give an extensive catalog of examples of ko positions and their thermographs.

We introduce a new method related to thermography for analyzing ko in the context of a specific ko threat situation. We comment on some well-known Go techniques, terminology, and “exotic” Go positions from a thermography point of view. Our analysis shows that a framework based on generalized thermography can be useful for the opening and midgame as well. We suggest that such a framework will serve as the basis for future strong Go programs.

Martin Müller	Related
William L. Spight	Related

[107] E. Berlekamp and Y. Kim: “Where is the ‘thousand-dollar ko’?,” pp. 203–226 in More games of no chance (Berkeley, CA, 11–21 July 2000). Edited by R. J. Nowakowski. MSRI Publications 29. Cambridge University Press, 1996. An earlier version of this was published in Go World 71 (1994). MR 1427966 Zbl 0873.90141 incollection

Yonghoan Kim	Related
Richard Joseph Nowakowski	Related

[108] E. Berlekamp: “Bounded distance \( +1 \) soft-decision Reed–Solomon decoding,” IEEE Trans. Inf. Theory 42 : 3 (May 1996), pp. 704–720. Zbl 0860.94032 article

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 \( \operatorname{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\cdot(\textrm{number of errors})+(\textrm{number of erasures}) .\] The new algorithm finds an errata pattern with minimum score among all errata patterns for which ERRATA COUNT \( \leq 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 \( \operatorname{GF}(q) \). The new algorithm also applies very naturally to RS codes which have been doubly extended by the inclusion of 0 and \( \infty \) as additional locations.

[109] E. R. Berlekamp, R. Hill, and J. Karim: “The solution of a problem of Ulam on searching with lies,” pp. 244–247 in 1988 IEEE international symposium on information theory (Cambridge, MA, 16–21 August 1998). IEEE (Piscataway, NJ), 1998. incollection

J. Karim	Related
R. Hill	Related

[110] The mathemagician and pied puzzler: A collection in tribute to Martin Gardner (Atlanta, January 1993). Edited by E. R. Berlekamp and T. Rodgers. A K Peters (Natick, MA), 1999. MR 1678000 Zbl 0926.00006 book

Martin Gardner	Related
Tom Rodgers	Related

[111] E. Berlekamp: The dots-and-boxes game: Sophisticated child’s play. A K Peters (Natick, MA), 2000. MR 1780088 Zbl 1058.00500 book

[112] E. Berlekamp: “Unimodular arrays,” pp. 77–88 in Sol Golomb’s 60th birthday symposium (Oxnard, CA, 29–31 May 1992), published as Comput. Math. Appl. 39 : 11. Issue edited by H. Taylor. Elsevier (Amsterdam), June 2000. MR 1766383 Zbl 0953.05010 incollection

Solomon Wolf Golomb	Related
Herbert Taylor	Related

[113] E. R. Berlekamp: “Sums of \( N\times 2 \) Amazons,” pp. 1–34 in Game theory, optimal stopping, probability and statistics: Papers in honor of Thomas S. Ferguson. Edited by F. T. Bruss and L. M. Le Cam. IMS Lecture Notes Monograph Series 35. Institute of Mathematical Statistics (Beachwood, OH), 2000. MR 1833848 Zbl 0988.91012 incollection

Amazons is a board game which has enjoyed some popularity since its appearance on the Internet a few years ago. It can be played on boards of arbitrary size. Like subtraction games studied by Ferguson [1974], Amazons is two-person, perfect-information, and zero-sum. Nevertheless, sums of games such as Amazons offer very interesting examples of “central limit theorems” which turn out to be considerably stronger than those encountered in probability theory.

As an illustration of the power of combinatorial game theory, we offer an analysis of all starting positions of Amazons played on sums of \( N\times 2 \) rectangles, in which each player has one Amazon in each rectangle. The analysis reveals two common yet important phenomena which many players overlook.

Although we assume no special background, seasoned combinatorial game theorists will find that Amazons provides our motivation for a novel exposition of the subject, starting with “results-oriented” thermography. This approach gets to the main results about hot games much more directly than prior expositions, which begin with Conway’s theory of canonical forms and a special emphasis on numbers. From the new perspective, numbers appear much later as a special case: they are the games whose temperatures are negative.

Thomas S. Ferguson	Related
Franz Thomas Bruss	Related
Lucien Marie Le Cam	Related

[114] E. R. Berlekamp, J. H. Conway, and R. K. Guy: Winning ways for your mathematical plays, 2nd edition, vol. 1. A K Peters (Natick, MA), 2001. Expanded republication of (approximately) the first half of the original volume 1 (1982). MR 1808891 Zbl 1005.00004 book

John Horton Conway	Related
Richard K. Guy	Related

[115] E. Berlekamp: “The 4G4G4G4G4 problems and solutions,” pp. 231–241 in More games of no chance (Berkeley, CA, 24–28 July 2000). Edited by R. J. Nowakowski. MSRI Publications 42. Cambridge University Press, 2002. This is related to an article published in Puzzlers’ tribute: A feast for the mind (2002). MR 1973015 Zbl 1062.91522 incollection

[116] E. Berlekamp and K. Scott: “Forcing your opponent to stay in control of a loony dots-and-boxes endgame,” pp. 317–330 in More games of no chance (Berkeley, CA, 24–28 July 2000). Edited by R. J. Nowakowski. MSRI Publications 42. Cambridge University Press, 2002. MR 1973020 Zbl 1062.91523 incollection

The traditional children’s pencil-and-paper game called Dots-and-Boxes is a contest to outscore the opponent by completing more boxes. It has long been known that winning strategies for certain types of positions in this game can be copied from the winning strategies for another game called Nimstring, which is played according to similar rules except that the Nimstring loser is whichever player completes the last box. Under certain common but restrictive conditions, one player (Right) achieves his optimal Dots-and-Boxes score, \( v \), by playing so as to win the Nimstring game. An easily computed lower bound on \( v \) is known as the controlled value, \( cv \). Previous results asserted that \( v = cv \) if \( cv \geq c/2 \), where \( c \) is the total number of boxes in the game.

In this paper, we weaken this condition from \( cv \geq c \) to \( cv \geq 10 \), and show this bound to be best possible.

Katherine Scott	Related
Richard Joseph Nowakowski	Related

[117] S. W. Golomb, E. Berlekamp, T. M. Cover, R. G. Gallager, J. L. Massey, and A. J. Viterbi: “Claude Elwood Shannon (1916–2001),” Notices Am. Math. Soc. 49 : 1 (2002), pp. 8–16. MR 1871259 Zbl 1126.01319 article

Robert Gray Gallager	Related
Thomas M. Cover	Related
Claude Elwood Shannon	Related
Solomon Wolf Golomb	Related
James Lee Massey	Related
Andrew James Viterbi	Related

[118] E. Berlekamp: “Idempotents among partisan games,” pp. 3–23 in More games of no chance (Berkeley, CA, 24–28 July 2000). Edited by R. J. Nowakowski. MSRI Publications 42. Cambridge University Press, 2002. MR 1973000 Zbl 1047.91521 incollection

[119] E. Berlekamp: “The performance of block codes,” Notices Am. Math. Soc. 49 : 1 (2002), pp. 17–22. MR 1871260 Zbl 1126.94300 article

In his classic paper [1948], Claude Shannon introduced the notions of communication channels and codes to communicate over them. During the following two decades, he remained active in refining and extending the theory. One of Shannon’s favorite research topics was the fundamental performance capabilities of long block codes. In the 1950s and 1960s this topic also attracted the active involvement of several of Shannon’s distinguished colleagues both at Bell Telephone Laboratories and at MIT, including P. Elias, R. M. Fano, R. G. Gallager, E. N. Gilbert, R. W. Hamming, I. M. Jacobs, B. Reiffen, D. Slepian, and J. M. Wozencraft, and several graduate students, including G. D. Forney and me. The work culminated in a book by Gallager [1968] and in a sequence of two “Information and Control” papers by Shannon, Gallager, and Berlekamp [1967a, 1967b]. In this article I present an overview of some of the more salient results and their impact.

[120] E. Berlekamp: “Four games for Gardner,” pp. 383–386 in Puzzlers’ tribute: A feast for the mind. Edited by D. Wolfe and T. Rodgers. A K Peters (Natick, MA), 2002. A related article was published in More games of no chance (2002). incollection

Martin Gardner	Related
Tom Rodgers	Related
David Wolfe	Related

[121] E. R. Berlekamp, J. H. Conway, and R. K. Guy: Winning ways for your mathematical plays, 2nd edition, vol. 2. A K Peters (Natick, MA), 2003. Expanded republication of (approximately) the first half of the original volume 1 (1982). MR 1959113 Zbl 1011.00009 book

John Horton Conway	Related
Richard K. Guy	Related

[122] E. Berlekamp: “Introduction,” pp. xi–xiii in Mathematical properties of sequences and other combinatorial structures (Los Angeles, 30 May–1 June 2002). Edited by J.-S. No, H.-y. Song, T. Helleseth, and P. V. Kumar. International Series in Engineering and Computer Science 726. Kluwer Academic (Dordrecht), 2003. Conference dedicated to the 70th birthday of Solomon W. Golomb. Zbl 1042.01512 incollection

Tor Helleseth	Related
P. Vijay Kumar	Related
Hong-yeop Song	Related
Solomon Wolf Golomb	Related
Jong-Seon No	Related

[123] T. Nakamura and E. Berlekamp: “Analysis of composite corridors,” pp. 213–229 in Computers and games: Third international conference (Edmonton, AB, 25–27 July 2002). Edited by J. Schaeffer, M. Müller, and Y. Björnsson. Lecture Notes in Computer Science 2883. Springer (Berlin), 2003. incollection

This work began as an attempt to find and catalog the mean values and temperatures of a well-defined set of relatively simple common Go positions, extending a similar but smaller catalog in Table E.10, Appendix E of the book Mathematical Go [Berlekamp and Wolf 1994].

The major surprises of our present work include the following

A position of chilled value *2 (previously unknown in Mathematical Go), shown at the end of Sect. 3.1.
A surprisingly “warm” position, whose temperature is routinely underestimated even by very strong Go players, shown in Sect. 4.
More insights into decompositions.

It is hoped that these results may someday provide the basis for further new insights and generalizations.

Jonathan Schaeffer	Related
Yngvi Björnsson	Related
Martin Müller	Related

[124] E. R. Berlekamp, J. H. Conway, and R. K. Guy: Winning ways for your mathematical plays, 2nd edition, vol. 3. A K Peters (Natick, MA), 2003. Expanded republication of (approximately) the first half of the original volume 2 (1982). MR 2006327 Zbl 1083.00003 book

John Horton Conway	Related
Richard K. Guy	Related

[125] E. R. Berlekamp, J. H. Conway, and R. K. Guy: Winning ways for your mathematical plays, 2nd edition, vol. 4. A K Peters (Wellesley, MA), 2004. Expanded republication of (approximately) the second half of the original volume 2 (1982). MR 2051076 Zbl 1084.00002 book

John Horton Conway	Related
Richard K. Guy	Related

[126] E. R. Berlekamp: “Bettor math,” Am. Sci. (November–December 2005). Book review: W. Poundstone, “Fortune’s formula: The untold story of the scientific betting system that beat the casinos and Wall Street”. article

[127] E. Berlekamp: “Baduk + coupons,” pp. 39–55 in Proceedings ICOB 2006: The 4th international conference on Baduk (Jeon-ju, Korea, 22–23 October 2006). Department of Baduk Studies, Myongji University (Seoul), 2006. incollection

[128] E. R. Berlekamp: Review of mathematics programs of Air Force Office of Scientific Research by National Research Council. The National Academies Press (Washington, DC), 2006. book

[129] R. Berlekamp, Elwyn: Mathematics and Go, 2006. DVD of lecture given at UC-Berkeley Faculty Club, Letters & Science Faculty Forum, 6 February 2006. misc

[130] E. Berlekamp: “Yellow-brown Hackenbush,” pp. 413–418 in Games of no chance 3 (Banff, AB, June 2005). Edited by M. H. Albert and R. J. Nowakowski. MSRI Publications 56. Cambridge University Press, 2009. Zbl 1192.91048 incollection

Michael Henry Albert	Related
Richard Joseph Nowakowski	Related

[131] E. Berlekamp: “The Galetron,” Games Econom. Behav. 66 : 2 (July 2009), pp. 598. In memoriam: David Gale. MR 2543261 Zbl 1165.01312 article

[132] E. R. Berlekamp: Some common misconceptions, 5 April 2013. 49 minute video of Stanford University’s 2013 Kailath Lecture. misc

[133] E. Berlekamp: Algebraic coding theory, revised edition. World Scientific Publishing (Hackensack, NJ), 2015. Revision of 2nd edition of 1968 original. MR 3380755 Zbl 1320.94001 book

Elwyn Berlekamp

Complete Bibliography