During the summers (1951–1954) that I was a graduate student in “pure mathematics,” I worked in the Systems Engineering Section of the Glenn L. Martin Company. I began to notice the applicability of supposedly pure topics like prime number theory and finite field theory to problems in communications. My first major applied effort involved developing the theory of “Shift Register Sequences.” (My book with this title will soon see its third edition, with a third publisher.) Much of my work has been in response to practical questions I was asked, for which I had the necessary mathematical tools. These topics have included comma-free codes, Costas arrays, Tuscan squares, Golomb rulers, zero-sidelobe radar, etc. My shift register work has had the broadest impact: to cell phone signals, the GPS system, error-correcting codes, radar, cryptography, etc. I am fortunate to have lived long enough to get some recognition for my work.

We show that a p-ary polyphase sequence of period p2from the Fermat quotients is perfect. That is, its periodic autocorrelation is zero for all non-trivial phase shifts. We call this Fermat-quotient sequence. We propose a collection of optimal families of perfect polyphase sequences using the Fermatquotient sequences in the sense of the Sarwate bound. That is, the cross correlation of two members in a family is upper bounded by p. To investigate some relation between Fermat-quotient sequences and Frank-Zadoff sequences and to construct optimal families including these sequences, we introduce generators of p-ary polyphase sequences of period p2using their p × p array structures. We call an optimal generator to be the generator of some p-ary polyphase sequences which are perfect and which gives an optimal family by the proposed construction. Finally, we propose an algebraic construction for optimal generators as another main result. A lot of optimal families of size p - 1 can be constructed from these optimal generators, some of which are known to be from the Fermat-quotient sequences or from the Frank-Zadoff sequences, but some families are new for p ≥ 11. The relation between the Fermat-quotient sequences and the Frank-Zadoff sequences is determined as a by-product.

In this paper, we present two generators for the group of symmetries of the generic (m+1) -dimensional periodic Costas arrays over elementary abelian (\BBZp)mgroups: one that is defined by multiplication onmdimensions and the other by shear (addition) onmdimensions. Through exhaustive search, we observe that these two generators characterize the group of symmetries for the examples we were able to compute. Following the results, we conjecture that these generators characterize the group of symmetries of the generic (m+1) -dimensional periodic Costas arrays over elementary abelian (\BBZp)mgroups.

We present a new 16-QAM near complementary sequence construction where the length of the sequences is n = 2m. The 16-QAM near complementary sequences are constructed by nonlinear offsets. But the peak-to-mean envelope power ratio bounds for these 16-QAM near complementary sequences is as low as 2.4. The number of newly constructed 16-QAM near complementary sequences is ([(m!)/2])4m+1.

We present a new 16-QAM near complementary sequence construction where the length of the sequences is n = 2m. The number of newly constructed 16-QAM near complementary sequences is (m!/2)4m+1, and the PMEPR bounds for newly constructed 16-QAM near complementary sequences is 2.4.

Given anmtimesnarray andkdistinct colors with 2lesmlesnand 2leskmn, we consider the problem of marking each location in the array using one of thekgiven colors such that any two locations in the array marked by the same color are separated as much as possible. This problem is related to two-dimensional (2-D) interleaving schemes for correcting cluster errors where the goal is to rearrange the codeword symbols so that an arbitrarily shaped error cluster of sizetcan be corrected for the largest possible value oft. In a recent paper, the authors have shown that, for the case 2lesklesmn/2, the maximum coloring distance is given by lfloorradic2krfloor ifkleslceilm2/2rceil, and bym+lfloor(k-lceilm2/2rceil)/mrfloor if lceilm2/2rceillesklesmn/2. In this work, we extend these results to the casemn/2kmn. We show that in such cases, the maximum coloring distance is given by tom+lfloor(k-lceilm2/2rceil)/mrfloor ifmn/2kmn-lfloorm2/2rfloor, and bym+n-lceilradic2(mn-k)rceil ifmn-lfloorm2/2rfloorleskmn. In particular, we generalize the partial sphere packing argument to derive the new bound and consequently propose a new type of construction achieving optimal coloring for the casekgesmn-lceilm2/2rceil.

This paper investigates how irreducibility and primitivity can be preserved when the unitary group acts on irreducible or primitive polynomials. Applying these operators to sequences and their discrete Fourier spectra, the weight preserving property is obtained. Some new randomness criteria are introduced in terms of these operators, which are suitable for measuring unpredictibility of pseudo-random sequences employed in stream ciphers.

In 1977, G. S. Bloom, in theJ. Combinatorial Theory, showed that Sophie Piccard's “theorem” had counterexamples for six-mark rulers. Subsequent research into finding additional counterexamples has focused on a variety of computer algorithms, such as searching the space of rulers with relatively few marks in an attempt to find another counterexample. Recent analytic effort has made use of Golomb's “Polynomial Method,” which made strides in eliminating specific types of rulers which cannot contain counterexamples. The question as to whether other larger length ruler counterexamples exist, however, was left unanswered. In this correspondence, a geometric manipulation of the “Polynomial Method” is used to demonstrate that no additional counterexamples are possible.

The definition, the basic properties, and all the currently known systematic constructions for Costas arrays are presented, as well as a table of the number C(n) of Costas arrays of order n, for 2 les n les 26. It is proved that lim supnrarrinfinC(n) = infin, and the conjecture liminfnrarrinfinC(n) = 0 is discussed. A Costas array of order n is known to be equivalent to a permutation {1,2,...,n} for which the difference triangle contains no repeated elements in any row. A generalized Costas array of order n = q-1(or n=q -2) is defined as a permutation of the nonzero elements (or also excluding 1) of the q-element field for which the difference triangle contains no repeated elements in any row. Two new constructions for these generalized Costas arrays are described and illustrated.

The simplest linear shift registers to generate binary sequences involve only two taps, which corresponds to a trinomial over GF(2). It is therefore of interest to know which irreducible polynomials f(x) divide trinomials over GF(2), since the output sequences corresponding to f(x) can be obtained from a two-tap linear feedback shift register (with a suitable initial state) if and only if f(x) divides some trinomial t(x)=xm+xa+1 over GF(2). In this paper, we develop the theory of which irreducible polynomials do, or do not, divide trinomials over GF(2). Then some related problems such as Artin's conjecture about primitive roots, and the conjectures of Blake, Gao, and Lambert, as well as of Tromp, Zhang, and Zhao are discussed

In this correspondence, we present a connection between designing low-correlation zone (LCZ) sequences and the results of correlation of sequences with subfield decompositions presented in a recent book by the first two authors. This results in LCZ signal sets with huge sizes over three different alphabetic sets: finite field of size$q$, integer residue ring modulo$q$, and the subset in the complex field which consists of powers of a primitive$q$th root of unity. We show a connection between these sequence designs and “completely noncyclic” Hadamard matrices and a construction for those sequences. We also provide some open problems along this direction.

The cyclic difference sets constructed by Singer are also examples of perfect distinct difference sets (DDS). The Bose construction of distinct difference sets, leads to a relative difference set. In this paper we introduce the concept of partial relative DDS and prove that an optical orthogonal code (OOC) construction due to Moreno et. al., is a partial relative DDS. We generalize the concept of ideal matrices previously introduced by Kumar and relate it to the concepts of this paper. Another variation of ideal matrices is introduced in this paper: Welch ideal matrices of dimension n by (n - 1). We prove that Welch ideal matrices exist only for n prime. Finally, we recast an old conjecture of Golomb on the Welch construction of Costas arrays using the concepts of this paper. This connection suggests that our construction of partial relative difference sets is in a sense, unique

Given an mtimesn array of k single random error correction (or erasure) codewords, each having length l such that mn=kl, we construct optimal interleaving schemes that provide the maximum burst error correction power such that an arbitrarily shaped error burst of size t can be corrected for the largest possible value of t. We show that for all such mtimesn arrays, the maximum possible interleaving distance, or equivalently, the largest value of t such that an arbitrary error burst of size up to t can be corrected, is bounded by lfloorradic2krfloor if kleslceil(min{m,n})2/2rceil, and by min{m,n}+lfloor(k-lceil(min{m,n})2/2rceil)/min{m,n}rfloor if kgeslceil(min{m,n})2/2rceil. We generalize the cyclic shifting algorithm developed by the authors in a previous paper and construct, in several special cases, optimal interleaving arrays achieving these upper bounds. Additionally, for codewords of variable lengths, we solve a related array coloring problem for which the same upper bounds hold and can be achieved

In this correspondence, we present a new construction for 64-QAM Golay sequences of length n=2/sup m/ for integer m. The peak envelope power (PEP) of 64-QAM Golay sequences is shown to be bounded by 4.66n. The new construction of 64-QAM Golay sequences of length n=2/sup m/ is based on our earlier construction of new offsets of 16-QAM Golay sequences which are also presented here. The total number of offsets of 64-QAM Golay sequences is 496 for m=2,808 for m=3 and 976 for m=4, obtained by computer search. We also computed the PEP distribution for 64-QAM Golay sequences for m=2, m=3, and m=4.

A difference triangle set (D$\Delta$S) is a collection of sets of integers having the property that every integer can be written in at most one way as the difference of two elements within a set of the collection. The standard objective is to minimize the largest difference represented, given a specified size of the collection and sizes of the sets that it contains. In order to construct D$\Delta$Ss, we present a new type of combinatorial design, monotonic directed $(v,k,\lambda)$-designs (MDDs). Using MDDs, we give a general recursive construction for difference triangle sets (D$\Delta$Ss). Several instances of this main construction are derived. One of these, the perfect construction, leads to an infinite family of regular (optimal) D$\Delta$Ss if the existence of a single regular D$\Delta$S is known.

One of the key problems in the study of optimal interleaving schemes for correcting two-dimensional (2-D) cluster errors is how to place, say, n distinct symbols, each appearing m times, in an m/spl times/n array such that the resulting array has the maximum possible burst error-correcting power. In a previous paper, the authors have proved that for any given m, n, the maximum possible interleaving distance, and hence, the largest possible value t such that an arbitrary error burst of size t can be corrected in an m/spl times/n interleaved array, is given by t=/spl lfloor//spl radic/2n/spl rfloor/ for n = /spl les/ /spl lceil/m/sup 2//2/spl rceil/, and t=m+/spl lfloor/(n-/spl lceil/m/sup 2//2/spl rceil/)/m/spl rfloor/ for n /spl ges/ /spl lceil/m/sup 2//2/spl rceil/. In this work, we extend these results and show that for all m, n with n /spl ges/ m, an optimal m/spl times/n interleaving array can always be obtained by a Latin rectangle in which each row and each column contains each symbol at most once. This provides additional error-correcting power to the array in that all linear error bursts occupying a whole row or column can also be corrected.

This paper presents a new optimal double periodical construction of optical orthogonal codes for multiple and two-dimensional double-periodic arrays with auto and cross correlation constraints. The new construction is optimal in the Johnson bound to obtain an optimal family of extended sonar type arrays with the property of double periodicity. The equivalence theorem used to obtain the signal pattern provides families of multiple target arrays.

Given an m/spl times/n array of n single-random-error-correcting codewords of length m, we present optimal interleaving schemes that achieve maximum possible interleaving distance t =/spl lfloor//spl radic/2n/spl rfloor/ for n/spl les//spl lceil/m/sup 2//2/spl rceil/, and t = m+/spl lfloor/(n-/spl lceil/m/sup 2//2/spl rceil/)/m/spl rfloor/ for n/spl ges//spl lceil/m/sup 2//2/spl rceil/. These interleaving schemes provide maximum burst error-correcting power without requiring prior knowledge of the size or shape of an error burst.

Zhang (see IEEE Trans. Commun., vol.47, p.967-973, July 1999) proposed a special family of optical address codes, called strict optical orthogonal codes (S-OOCs), was proposed for fiber-optic code-division multiple-access (FO-CDMA) networks. Such codes can strictly guarantee both cross-correlation and autocorrelation functions constrained to have the value one in fully asynchronous data communications and ultra fast switching. In Zhang's work the theory and designs of S-OOC, plus several examples, comparison tables, and performance analyses were presented. In this article, we set up the equivalence between S-OOC and so-called difference triangle sets (DTS), which have been extensively studied previously. Thus, all the known constructions, bounds, and analyses for DTS can be directly applied to S-OOC.

We present a new recursive construction for (n,/spl omega/,/spl lambda//sub a/,/spl lambda//sub c/) optical orthogonal codes. For the case of /spl lambda//sub a/ = /spl lambda//sub c/ = /spl lambda/, this recursive construction enlarges the original family with /spl lambda/ unchanged, and produces a new family of asymptotically optimal codes, if the original family is asymptotically optimal. We call a code asymptotically optimal, following the definition of O. Moreno et al. (see ibid., vol.41, p.448-55, 1995), if, as n, the length of code, goes to infinity, the ratio of the number of codewords to the corresponding Johnson bound approaches unity.

A new method to study and search for two-level autocorrelation sequences for both binary and nonbinary cases is developed. This method iteratively applies two operations: decimation and the Hadamard transform based on general orthogonal functions, referred to as the decimation-Hadamard transform (DHT). The second iterative DHT can transform one class of such sequences into another inequivalent class of such sequences, a process called realization. The existence and counting problems of the second iterative DHT are discussed. Using the second iterative DHT, and starting with a single binary m-sequence (when n is odd), we believe one can obtain all the known two-level autocorrelation sequences of period 2/sup n/-1 which have no subfield factorization. We have verified this for odd n/spl les/17. Interestingly, no previously unknown examples were found by this process for any odd n/spl les/17. This is supporting evidence (albeit weak) for the conjecture that all families of cyclic Hadamard difference sets of period 2/sup n/-1 having no subfield factorization are now known, at least for odd n. Experimental results are provided.

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.

Gordon-Mills-Welch (GMW) sequences (also called cascaded GMW sequences) have two-level autocorrelations. This property makes them widely used in various communication and cryptographic systems. The generation of q-ary GMW sequences of period q/sup n-1/ involves three types of parameters. To determine whether GMW sequences are cyclically shift-distinct for differing parameters has remained an open question until now. In this paper, we completely solve this problem for varying all three types of parameters. We find a criterion for cyclically shift-distinct q-ary GMW sequences of period q/sup n-1/, and obtain the number of such sequences. For the special case of q=2, this solution facilitates counting the number of cyclic Hadamard difference sets which correspond to binary GMW sequences of period 2/sup n-1/.

Periodic binary sequences with the "trinomial property" are considered. Some necessary and sufficient conditions for "trinomial pairs" of a nonlinear sequence of period 2/sup n/-1 as well as classifications for trinomial pairs are derived. Complete searches for trinomial pairs of sequences have been completed for 3/spl les/n/spl les/17. We list them here for n/spl les/12.

We derive the values of the Fourier spectrum, a decomposition, and an achievable upper bound on the linear span, for binary sequences with two-level autocorrelation.

Certain three-term sequences of period 2/sup n/-l are conjectured to have the two-level autocorrelation property. In this note, a formula involving Hadamard transforms of three-term sequences is presented. Its validity has been verified by computer on the range of 5/spl les/n/spl les/23.

The Data Encryption Standard (DES) can be regarded as a nonlinear feedback shift register (NLFSR) with input. From this point of view, the tools for pseudo-random sequence analysis are applied to the S-boxes in DES. The properties of the S-boxes of DES under the Fourier transform, Hadamard transform, extended Hadamard transform, and the Avalanche transform are investigated. Two important results about the S-boxes of DES are found. The first result is that nearly two-thirds of the total 32 functions from GF (2/sup 6/) to GF(2) which are associated with the eight S-boxes of DES have the maximal linear span G3, and the other one-third have linear span greater than or equal to 57. The second result is that for all S-boxes, the distances of the S-boxes approximated by monomial functions has the same distribution as for the S-boxes approximated by linear functions. Some new criteria for the design of permutation functions for use in block cipher algorithms are discussed.

A polyphase sequence of length n+1, A={a/sub j/}/sub j=0//sup n/, is a sequence of complex numbers, each of unit magnitude. The (unnormalized) aperiodic autocorrelation function of a sequence is denoted by C(/spl tau/). Associated with the sequence A, the sequence polynomial f/sub A/(z) of degree n and the correlation polynomial g/sub A/(z) of degree 2n are defined. For each root /spl alpha/ of f/sub A/(z), 1//spl alpha/* is a corresponding root of f*/sub A/(z/sup -1/). Transformations on the sequence A which leave |C(/spl tau/)| invariant are exhibited, and the effects of these transformations on the roots of f/sub A/(z) are described. An investigation of the set of roots A of the polynomial f/sub A/(z) has been undertaken, in an attempt to relate these roots to the behavior of C(/spl tau/). Generalized Barker (1952, 1953) sequences are considered as a special case of polyphase sequences, and examples are given to illustrate the relationship described above.

In this correspondence, we present five new classes of binary sequences of period 2/sup n/-1 with ideal autocorrelation. These sequences, which correspond to new cyclic Hadamard difference sets, were found by extensive computer search. Conjectures on the general construction of these sequences are formulated.

Sonar sequences were introduced by Golomb and Taylor in 1982. We introduce the concept of extended sonar sequences, which is similar to that of sonar sequences except that blank columns are permitted. Several constructions for extended sonar sequences are offered here. Some of these are close to constructions for ordinary sonar sequences, but they provide improvements to the list of best sonar sequences with up to 100 symbols.

We present 7200-phase generalized Barker sequences with lengths from 19 to 31. Also, we show the number of known M-phase generalized Barker sequences (M=7200), inequivalent under the group of "Barker-preserving transformations". The autocorrelation values of Barker sequences are also presented.

Golomb and Taylor (1984) conjectured that single periodicity characterizes the Welch construction of Costas arrays. In this correspondence, we present a weakened version of this conjecture and partial results on it. Furthermore, we prove that our conjecture is equivalent to a conjecture concerning permutation polynomials and give partial results on the latter.

An n-phase Barker sequence can be easily distinguished from the time-shifted versions of itself. This property is important for such applications as radar systems, synchronization systems, and spread-spectrum communications systems. The authors study some transformations on n-phase Barker sequences. Also, they give an efficient algorithm for finding sextic Barker sequences. Through an exhaustive computer search, numerical data for n-phase Barker sequences are given. Specifically, they extend the list of known n-phase Barker sequences to length L=19.>

Three constructions for n-dimensional regular simplex codes /spl alpha//sub i/, 0/spl les/i/spl les/n, are proposed, two of which have the property that /spl alpha//sub i/ for 1/spl les/i/spl les/n is a cyclic shift of /spl alpha//sub 1/. The first method is shown to work for all the positive integers n=1,2,... using only three real values. It turns out that these values are rational whenever n+1 is a square of some integer. Whenever a (v,k,/spl lambda/) cyclic (or Abelian) difference set exists, this method is generalized so that a similar method is shown to work with /spl nu/=n (the number of dimensions).>

The main conjecture of this article is the following: if a cyclic (v=4n-1, k=2n-1, /spl lambda/=n-1) Hadamard difference set exists, the the value of v must be either a prime, or a product of "twin primes," or one less than a power of 2. Six cases, v=399, 495, 627, 651, 783, and 975, which were once listed as the possible exceptions for v>

Picking up exactly one member from each of the nonperiodic cyclic equivalence classes of an (n, k+1) Reed-Solomon code E over GF(q) gives a code, E", which has bounded Hamming correlation values and the self-synchronizing property. The exact size of E" is shown to be (1/n) Sigma /sub d mod n/ mu (d)q/sup 1+k/d/, where mu (d) is the Mobius function, (x) is the integer part of x, and the summation is over all the divisors d of n=q-1. A construction for a subset V of E is given to prove that mod E" mod >or= mod V mod =(q/sup k+1/-q/sup k+1-N/)/(q-1) where N is the number of integers from 1 to k which are relatively prime to q-1. A necessary and sufficient condition for mod E" mod = mod V mod is proved and some special cases are presented with examples. For all possible values of q>2, a number B(q) is determined such that mod E" mod = mod V mod for 1mod V mod for k>B(q).>

It is proved that Golomb sequences have perfect periodic autocorrelation. It is also proved that the magnitudes of the out-of-phase aperiodic autocorrelation values of Golomb sequences of length L for all L>or=14 are bounded by square root (L/3). It is shown that B/sub g/(L) is asymptotic to square root (L/c) (where c approximately=4.348. . .), as L goes to infinity.>

Two of the algebraic constructions for Costas arrays, designated as T/sub 4/ and G/sub 4/, are described in detail, and necessary and sufficient conditions are given for the sizes of Costas arrays for which these constructions occur. These constructions depend on the existence of primitive roots satisfying certain equations in finite fields.>

Order n modified de Bruijn sequences are created by removing a single zero from the longest run of zeros in period 2/sup n/ de Bruijn sequences. The M sequences are then the natural undisguised linear subset of modified de Bruijn sequences. Theorems are given on the linear spans of modified de Bruijn sequences and data are presented for 4>

It is proved that for 3>

It is proven that there is a unique generalized Barker sequence of length 6, modulo the group of Barker-preserving transformations.>

Some communication systems require sets of signals in which each signal can be easily distinguished from all time-shifted versions of itself, and from every other signal in the set. A generalized Barker sequence can be easily distinguished from the time-shifted versions of itself. It is shown that distinguishing between a generalized Barker sequence and any other generalized Barker sequence of the same length is inherently harder than distinguishing the sequence from time-shifted versions of itself.>

The extension of the list of known generalized Barker sequences to length 19 is proposed. Examples for all lengths up to 19 where the terms of the sequence are sixtieth roots of unity are given.>

Balanced binary sequences of period2^{n}-1with the run property and the two-level autocorrelation property are not necessarily PN sequences.

A number of closely related combinatorial problems corresponding to specific assumptions about the type of time-frequency sequence which may be appropriate in a particular application, are formulated in terms of square or rectangular arrays of dots with appropriate constraints on the two-dimensional correlation function. The current state of knowledge concerning each of these problems is summarized. It is hoped that more general constructions may be found, leading to larger families of solutions, as well as better computational algorithms for finding individual solutions which may lie outside of the general families.

LetUbe the set of all binary sequences of periodp=2^{n}-1containing(p+1)/2ones and(p-1)/2zeros per period. There is a lattice of interesting subsets ofU, the smallest of which is the setPN(the maximum-length linear shift register sequences of periodp). In between are sets with the run statistics ofPN, with the correlation properties ofPN, with the "span-nproperty" (that every nonzero subseqnonce of lengthnoccurs in each period), and others. Results concerning the interrelationships of these subsets are obtained, examples are given to show that certain intersections of subsets are nonempty, and conjectures are formulated regarding other intersections of subsets. For example, it is conjectured that all span-nsequences with the two-level autocorrelation property are in classPN. Some relationships between run properties and correlation properties of binary sequences are also obtained.

Given a binary data streamA = \{a_i\}_{i=o}^\inftyand a filterFwhose output at timenisf_n = \sum_{i=0}^{n} a_i \beta^{n-i}for some complex\beta \neq 0, there are at most2^{n +1)distinct values off_n. These values are the sums of the subsets of\{1,\beta,\beta^2,\cdots,\beta^n\}. It is shown that all2^{n+1}sums are distinct unless\betais a unit in the ring of algebraic integers that satisfies a polynomial equation with coefficients restricted to +1, -1, and 0. Thus the size of the state space\{f_n\}is2^{n+1}if\betais transcendental, if\beta \neq \pm 1is rational, and if\betais irrational algebraic but not a unit of the type mentioned. For the exceptional values of\beta, it appears that the size of the state space\{f_n\}grows only as a polynomial innif\mid\beta\mid = 1, but as an exponential\alpha^nwith1 < \alpha < 2if\mid\beta\mid \neq 1.

A general definition of error metrics is given, based on a distance function\mu(a, b)for symbols of the code alphabet, and extended to entire codewords by a Lebesgue normL_{\alpha}. It is shown that error metrics considered by Hamming, Lee, Shannon, and Stein are special cases, and a geometric interpretation of the "error spheres" for these metrics is presented.

One of the characteristic problems involved in design is geometric arrangement. Components must be fitted onto a circuit card, or rooms must be fitted together to form a livable house, subject to certain constraints. These arrangement problems appear particularly difficult when viewed from the stand point of the traditional tools of mathematical analysis, analytical geometry, differential calculus, etc. However, there are various combinatorial procedures and algorithms, which are suitable for programming on a computer for dealing with such problems.There are also numerous design problems in which the basic requirements involve connectivity, rather than packing. For example, the elements may be located on the printed circuit card, but the interconnecting wires must be fitted in to make specified contacts, with desired side-constraints involving minimum length, or minimum over crossing, or other economic criteria. The electrical wiring or plumbing conduits for a building involve the same type of considerations.

A widely used method of efftcient search is examined in detail.This examination provides the opportunity to formulate its scope and methods in their full generality.In addL tion to a general exposition of the basic process, some important refinemertts are indicated.Examples are given which illustrate the salient features of this searching process.

A generalized Barker sequence is a finite sequence\{a_{r}\}of complex numbers having absolute value1, and possessing a correlation functionC(\tau)satisfying the constraint|C(\tau)| \leq 1, \tau \neq 0. Classes of transformations leaving|C(\tau)|invariant are exhibited. Constructions for generalized Barker sequences of various lengths and alphabet sizes are given. Sextic Barker sequences are investigated and examples are given for all lengths through thirteen. No theoretical limit to the length of sextic sequences has been found.

A problem originally suggested in the context of genetic coding leads naturally to the concept of {\em rook packing} and {\em error-distributing codes}. It is shown how various concepts in the theory of Latin squares, and also in coding theory, are best expressed in the form of questions about the placing of rooks onk-dimensional hyperchessboards of siden. A new species of combinatorial design suggested by this is the concept of {\em optimal coloring}. It is shown that the optimal colorings in certain cases correspond to duals of desarguian projective planes. Light is thereby shed on the problems of the existence of both finite projective planes and close-packed single-error-correcting codes. In particular, the existence of a certain close-packed nonbinary single-error-correcting code, listed by Golay as the first unknown case, has been ruled out by a well-known result concerning Latin squares.

In the discrete case, the Shannon expression for entropy is obtained as a line integral in probability space. The integrand is the "information density vector" (\log p_1, \log p_2, \cdots, \log p_n). In the continuous case, the continuous analog of information density is integrated to obtain the entropy expression for continuous probability distributions.

Two Boolean functions which differ only by permutation and complementation of their n input variables belong to the same symmetry class. Methods are described for determining the number of symmetry classes for functions of n variables, and for ascertaining whether or not two functions belong to the same class. This classification is achieved via a complete set of invariants, characteristic of the class, and easily computable from any function in it. The invariants also provide information concerning the size and symmetry properties of the class. Analogous techniques apply to other symmetry classifications of Boolean functions, and to more general categories of discrete mappings.