BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

N. J. A. Sloane

N. J. A. Sloane appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.NTInformation Theorymath.ITDiscrete Mathematicsmath.MG

Catalog footprint

What is connected

39works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

39 published item(s)

preprint2023arXiv

"A Handbook of Integer Sequences" Fifty Years Later

Until 1973 there was no database of integer sequences. Someone coming across the sequence 1, 2, 4, 9, 21, 51, 127,... would have had no way of discovering that it had been studied since 1870 (today these are called the Motzkin numbers, and form entry A001006 in the database). Everything changed in 1973 with the publication of "A Handbook of Integer Sequences", which listed 2372 entries. This report describes the fifty-year evolution of the database from the "Handbook" to its present form as "The On-Line Encyclopedia of Integer Sequences" (or OEIS), which contains 360,000 entries, receives a million visits a day, and has been cited 10,000 times, often with a comment saying "discovered thanks to the OEIS".

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Binary Two-Up Sequence

The Binary Two-Up Sequence is the lexicographically earliest sequence of distinct nonnegative integers with the property that the binary expansion of the n-th term has no 1-bits in common with any of the previous floor(n/2) terms. We show that the sequence can be decomposed into ``atoms'', which are sequences of 4, 6, or 8 numbers whose binary expansions match certain patterns, and that the sequence is the limiting form of a certain ``word'' involving the atoms. This leads to a fairly explicit formula for the terms, and in particular establishes the conjecture that every nonzero term is the sum of at most two powers of 2.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Automated Proof (or Disproof) of Linear Recurrences Satisfied by Pisot Sequences

Pisot sequences (sequences $a_n$ with initial terms $a_0=x, a_1=y$, and defined for $n>1$ by $a_n= \lfloor a_{n-1}^2/a_{n-2} + \frac{1}{2} \rfloor$) often satisfy linear recurrences with constant coefficients that are valid for all $n \geq 0$, but there are also cautionary examples where there is a linear recurrence that is valid for an initial range of values of $n$ but fails to be satisfied beyond that point, providing further illustrations of Richard Guy's celebrated "Strong Law of Small Numbers". In this paper we present a decision algorithm, fully implemented in an accompanying Maple program ({\tt Pisot.txt}), that first searches for a putative linear recurrence and then decides whether or not it holds for all values of $n$. We also explain why the failures happen (in some cases the `fake' linear recurrence may be valid for thousands of terms). We conclude by defining, and studying, higher-order analogs of Pisot sequences, and point out that similar phenomena occur there, albeit far less frequently. This article is dedicated to Richard K. Guy (b. Sept. 30, 1916) on his 100th birthday.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata

We develop a meta-algorithm that, given a polynomial (in one or more variables), and a prime p, produces a fast (logarithmic time) algorithm that takes a positive integer n and outputs the number of times each residue class modulo p appears as a coefficient when the polynomial is raised to the power n and the coefficients are read modulo p.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Odd-Rule Cellular Automata on the Square Grid

An "odd-rule" cellular automaton (CA) is defined by specifying a neighborhood for each cell, with the rule that a cell turns ON if it is in the neighborhood of an odd number of ON cells at the previous generation, and otherwise turns OFF. We classify all the odd-rule CAs defined by neighborhoods which are subsets of a 3 X 3 grid of square cells. There are 86 different CAs modulo trivial symmetries. When we consider only the different sequences giving the number of ON cells after n generations, the number drops to 48, two of which are the Moore and von Neumann CAs. This classification is carried out by using the "meta-algorithm" described in an earlier paper to derive the generating functions for the 86 sequences, and then removing duplicates. The fastest-growing of these CAs is neither the Fredkin nor von Neumann neighborhood, but instead is one defined by "Odd-rule" 365, which turns ON almost 75% of all possible cells.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Number of ON Cells in Cellular Automata

If a cellular automaton (CA) is started with a single ON cell, how many cells will be ON after n generations? For certain "odd-rule" CAs, including Rule 150, Rule 614, and Fredkin's Replicator, the answer can be found by using the combination of a new transformation of sequences, the run length transform, and some delicate scissor cuts. Several other CAs are also discussed, although the analysis becomes more difficult as the patterns become more intricate.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Yellowstone Permutation

Define a sequence of positive integers by the rule that a(n) = n for 1 <= n <= 3, and for n >= 4, a(n) is the smallest number not already in the sequence which has a common factor with a(n-2) and is relatively prime to a(n-1). We show that this is a permutation of the positive integers. The remarkable graph of this sequence consists of runs of alternating even and odd numbers, interrupted by small downward spikes followed by large upward spikes, suggesting the eruption of geysers in Yellowstone National Park. On a larger scale the points appear to lie on infinitely many distinct curves. There are several unanswered questions concerning the locations of these spikes and the equations for these curves.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

2178 And All That

For integers g >= 3, k >= 2, call a number N a (g,k)-reverse multiple if the reversal of N in base g is equal to k times N. The numbers 1089 and 2178 are the two smallest (10,k)-reverse multiples, their reversals being 9801 = 9x1089 and 8712 = 4x2178. In 1992, A. L. Young introduced certain trees in order to study the problem of finding all (g,k)-reverse multiples. By using modified versions of her trees, which we call Young graphs, we determine the possible values of k for bases g = 2 through 100, and then show how to apply the transfer-matrix method to enumerate the (g,k)-reverse multiples with a given number of base-g digits. These Young graphs are interesting finite directed graphs, whose structure is not at all well understood.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Curling Numbers of Integer Sequences

Given a finite nonempty sequence S of integers, write it as XY^k, where Y^k is a power of greatest exponent that is a suffix of S: this k is the curling number of S. The Curling Number Conjecture is that if one starts with any initial sequence S, and extends it by repeatedly appending the curling number of the current sequence, the sequence will eventually reach 1. The conjecture remains open. In this paper we discuss the special case when S consists just of 2's and 3's. Even this case remains open, but we determine how far a sequence of n 2's and 3's can extend before reaching a 1, conjecturally for n <= 80. We investigate several related combinatorial problems, such as finding c(n,k), the number of binary sequences of length n and curling number k, and t(n,i), the number of sequences of length n which extend for i steps before reaching a 1. A number of interesting combinatorial problems remain unsolved.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Curling Number Conjecture

Given a finite nonempty sequence of integers S, by grouping adjacent terms it is always possible to write it, possibly in many ways, as S = X Y^k, where X and Y are sequences and Y is nonempty. Choose the version which maximizes the value of k: this k is the curling number of S. The Curling Number Conjecture is that if one starts with any initial sequence S, and extends it by repeatedly appending the curling number of the current sequence, the sequence will eventually reach 1. The conjecture remains open, but we will report on some numerical results and conjectures in the case when S consists of only 2's and 3's.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Toothpick Sequence and Other Sequences from Cellular Automata

A two-dimensional arrangement of toothpicks is constructed by the following iterative procedure. At stage 1, place a single toothpick of length 1 on a square grid, aligned with the y-axis. At each subsequent stage, for every exposed toothpick end, place an orthogonal toothpick centered at that end. The resulting structure has a fractal-like appearance. We will analyze the toothpick sequence, which gives the total number of toothpicks after n steps. We also study several related sequences that arise from enumerating active cells in cellular automata. Some unusual recurrences appear: a typical example is that instead of the Fibonacci recurrence, which we may write as a(2+i) = a(i) + a(i+1), we set n = 2^k+i (0 <= i < 2^k), and then a(n)=a(2^k+i)=2a(i)+a(i+1). The corresponding generating functions look like Prod{k >= 0} (1+x^{2^k-1}+2x^{2^k}) and variations thereof.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Seven Staggering Sequences

When my "Handbook of Integer Sequences" came out in 1973, Philip Morrison gave it an enthusiastic review in the Scientific American and Martin Gardner was kind enough to say in his Mathematical Games column that "every recreational mathematician should buy a copy forthwith." That book contained 2372 sequences. Today the "On-Line Encyclopedia of Integer Sequences" contains 117000 sequences. This paper will describe seven that I find especially interesting. These are the EKG sequence, Gijswijt's sequence, a numerical analog of Aronson's sequence, approximate squaring, the integrality of n-th roots of generating functions, dissections, and the kissing number problem. (Paper for conference in honor of Martin Gardner's 91st birthday.)

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Constant Weight Codes: A Geometric Approach Based on Dissections

We present a novel technique for encoding and decoding constant weight binary codes that uses a geometric interpretation of the codebook. Our technique is based on embedding the codebook in a Euclidean space of dimension equal to the weight of the code. The encoder and decoder mappings are then interpreted as a bijection between a certain hyper-rectangle and a polytope in this Euclidean space. An inductive dissection algorithm is developed for constructing such a bijection. We prove that the algorithm is correct and then analyze its complexity. The complexity depends on the weight of the code, rather than on the block length as in other algorithms. This approach is advantageous when the weight is smaller than the square root of the block length.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Descending Dungeons and Iterated Base-Changing

For real numbers a, b> 1, let as a_b denote the result of interpreting a in base b instead of base 10. We define ``dungeons'' (as opposed to ``towers'') to be numbers of the form a_b_c_d_..._e, parenthesized either from the bottom upwards (preferred) or from the top downwards. Among other things, we show that the sequences of dungeons with n-th terms 10_11_12_..._(n-1)_n or n_(n-1)_..._12_11_10 grow roughly like 10^{10^{n log log n}}, where the logarithms are to the base 10. We also investigate the behavior as n increases of the sequence a_a_a_..._a, with n a's, parenthesized from the bottom upwards. This converges either to a single number (e.g. to the golden ratio if a = 1.1), to a two-term limit cycle (e.g. if a = 1.05) or else diverges (e.g. if a = frac{100{99).

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Generalizations of Schöbi's Tetrahedral Dissection

Let v_1, ..., v_n be unit vectors in R^n such that v_i . v_j = -w for i != j, where -1 <w < 1/(n-1). The points Sum_{i=1..n} lambda_i v_i, where 1 >= lambda_1 >= ... >= lambda_n >= 0, form a ``Hill-simplex of the first type'', denoted by Q_n(w). It was shown by Hadwiger in 1951 that Q_n(w) is equidissectable with a cube. In 1985, Schöbi gave a three-piece dissection of Q_3(w) into a triangular prism c Q_2(1/2) X I, where I denotes an interval and c = sqrt{2(w+1)/3}. The present paper generalizes Schöbi's dissection to an n-piece dissection of Q_n(w) into a prism c Q_{n-1}(1/(n-1)) X I, where c = sqrt{(n-1)(w+1)/n}. Iterating this process leads to a dissection of Q_n(w) into an n-dimensional rectangular parallelepiped (or ``brick'') using at most n! pieces. The complexity of computing the map from Q_n(w) to the brick is O(n^2). A second generalization of Schöbi's dissection is given which applies specifically in R^4. The results have applications to source coding and to constant-weight binary codes.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

A Slow-Growing Sequence Defined by an Unusual Recurrence

The sequence starts with a(1) = 1; to extend it one writes the sequence so far as XY^k, where X and Y are strings of integers, Y is nonempty and k is as large as possible: then the next term is k. The sequence begins 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, ... A 4 appears for the first time at position 220, but a 5 does not appear until about position 10^{10^{23}}. The main result of the paper is a proof that the sequence is unbounded. We also present results from extensive numerical investigations of the sequence and of certain derived sequences, culminating with a heuristic argument that t (for t=5,6, ...) appears for the first time at about position 2^(2^(3^(4^(5^...^({(t-2)}^{(t-1)}))))), where ^ denotes exponentiation. The final section discusses generalizations.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Gleason's Theorem on Self-Dual Codes and Its Generalizations

One of the most remarkable theorems in coding theory is Gleason's 1970 theorem about the weight enumerators of self-dual codes. In the past 36 years there have been hundreds of papers written about generalizations and applications of this theorem to different types of codes, always on a case-by-case basis. In this paper I state the theorem and then describe the far-reaching generalization that Gabriele Nebe, Eric Rains and I have developed which includes all the earlier generalizations at once. The full proof has just appeared in our book "Self-Dual Codes and Invariant Theory" (Springer, 2006). This paper is based on my talk at the conference on Algebraic Combinatorics in honor of Eiichi Bannai, held in Sendai, Japan, June 26-30, 2006.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

On the Integrality of n-th Roots of Generating Functions

Motivated by the discovery that the eighth root of the theta series of the E_8 lattice and the 24th root of the theta series of the Leech lattice both have integer coefficients, we investigate the question of when an arbitrary element f in R (where R = 1 + xZ[[x]]) can be written as f = g^n for g in R, n >= 2. Let P_n := {g^n : g in R} and let mu_n := n Product_{p|n} p. We show among other things that (i) for f in R, f in P_n <=> f mod mu_n in P_n, and (ii) if f in P_n, there is a unique g in P_n with coefficients mod mu_n/n such that f == g^n (mod mu_n). In particular, if f == 1 (mod mu_n) then f in P_n. The latter assertion implies that the theta series of any extremal even unimodular lattice in R^n (e.g. E_8 in R^8) is in P_n if n is of the form 2^i 3^j 5^k (i >= 3). There do not seem to be any exact analogues for codes, although we show that the weight enumerator of the r-th order Reed-Muller code of length 2^m is in P_{2^r}. We give a number of other results and conjectures, and establish a conjecture of Paul D. Hanna that there is a unique element f in P_n (n != 2) with coefficients restricted to the set {1, 2, ..., n}.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

Complete Weight Enumerators of Generalized Doubly-Even Self-Dual Codes

For any q which is a power of 2 we describe a finite subgroup of the group of invertible complex q by q matrices under which the complete weight enumerators of generalized doubly-even self-dual codes over the field with q elements are invariant. An explicit description of the invariant ring and some applications to extremality of such codes are obtained in the case q=4.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

Nonintersecting Subspaces Based on Finite Alphabets

Two subspaces of a vector space are here called ``nonintersecting'' if they meet only in the zero vector. The following problem arises in the design of noncoherent multiple-antenna communications systems. How many pairwise nonintersecting M_t-dimensional subspaces of an m-dimensional vector space V over a field F can be found, if the generator matrices for the subspaces may contain only symbols from a given finite alphabet A subseteq F? The most important case is when F is the field of complex numbers C; then M_t is the number of antennas. If A = F = GF(q) it is shown that the number of nonintersecting subspaces is at most (q^m-1)/(q^{M_t}-1), and that this bound can be attained if and only if m is divisible by M_t. Furthermore these subspaces remain nonintersecting when ``lifted'' to the complex field. Thus the finite field case is essentially completely solved. In the case when F = C only the case M_t=2 is considered. It is shown that if A is a PSK-configuration, consisting of the 2^r complex roots of unity, the number of nonintersecting planes is at least 2^{r(m-2)} and at most 2^{r(m-1)-1} (the lower bound may in fact be the best that can be achieved).

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

Numerical Analogues of Aronson's Sequence

Aronson's sequence 1, 4, 11, 16, ... is defined by the English sentence ``t is the first, fourth, eleventh, sixteenth, ... letter of this sentence.'' This paper introduces some numerical analogues, such as: a(n) is taken to be the smallest positive integer greater than a(n-1) which is consistent with the condition ``n is a member of the sequence if and only if a(n) is odd.'' This sequence can also be characterized by its ``square'', the sequence a^(2)(n) = a(a(n)), which equals 2n+3 for n >= 1. There are many generalizations of this sequence, some of which are new, while others throw new light on previously known sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

On Non-Squashing Partitions

A partition n = p_1 + p_2 + ... + p_k with 1 <= p_1 <= p_2 <= ... <= p_k is called non-squashing if p_1 + ... + p_j <= p_{j+1} for 1 <= j <= k-1. Hirschhorn and Sellers showed that the number of non-squashing partitions of n is equal to the number of binary partitions of n. Here we exhibit an explicit bijection between the two families, and determine the number of non-squashing partitions with distinct parts, with a specified number of parts, or with a specified maximal part. We use the results to solve a certain box-stacking problem.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

The Number of Hierarchical Orderings

An ordered set-partition (or preferential arrangement) of n labeled elements represents a single ``hierarchy''; these are enumerated by the ordered Bell numbers. In this note we determine the number of ``hierarchical orderings'' or ``societies'', where the n elements are first partitioned into m <= n subsets and a hierarchy is specified for each subset. We also consider the unlabeled case, where the ordered Bell numbers are replaced by the composition numbers. If there is only a single hierarchy, we show that the average rank of an element is asymptotic to n/(4 log 2) in the labeled case and to n/4 in the unlabeled case.

0 citations0 reviewsNo code linkedOpen access
preprint2002arXiv

A Zador-Like Formula for Quantizers Based on Periodic Tilings

We consider Zador's asymptotic formula for the distortion-rate function for a variable-rate vector quantizer in the high-rate case. This formula involves the differential entropy of the source, the rate of the quantizer in bits per sample, and a coefficient G which depends on the geometry of the quantizer but is independent of the source. We give an explicit formula for G in the case when the quantizing regions form a periodic tiling of n-dimensional space, in terms of the volumes and second moments of the Voronoi cells. As an application we show, extending earlier work of Kashyap and Neuhoff, that even a variable-rate three-dimensional quantizer based on the ``A15'' structure is still inferior to a quantizer based on the body-centered cubic lattice. We also determine the smallest covering radius of such a structure.

0 citations0 reviewsNo code linkedOpen access
preprint2002arXiv

Multiple Description Vector Quantization with Lattice Codebooks: Design and Analysis

The problem of designing a multiple description vector quantizer with lattice codebook Lambda is considered. A general solution is given to a labeling problem which plays a crucial role in the design of such quantizers. Numerical performance results are obtained for quantizers based on the lattices A_2 and Z^i, i=1,2,4,8, that make use of this labeling algorithm. The high-rate squared-error distortions for this family of L-dimensional vector quantizers are then analyzed for a memoryless source with probability density function p and differential entropy h(p) < infty. For any a in (0,1) and rate pair (R,R), it is shown that the two-channel distortion d_0 and the channel 1 (or channel 2) distortions d_s satisfy lim_{R -> infty} d_0 2^(2R(1+a)) = (1/4) G(Lambda) 2^{2h(p)} and lim_{R -> infty} d_s 2^(2R(1-a)) = G(S_L) 2^2h(p), where G(Lambda) is the normalized second moment of a Voronoi cell of the lattice Lambda and G(S_L) is the normalized second moment of a sphere in L dimensions.

0 citations0 reviewsNo code linkedOpen access
preprint2002arXiv

On Asymmetric Coverings and Covering Numbers

An asymmetric covering D(n,R) is a collection of special subsets S of an n-set such that every subset T of the n-set is contained in at least one special S with |S| - |T| <= R. In this paper we compute the smallest size of any D(n,1) for n <= 8. We also investigate ``continuous'' and ``banded'' versions of the problem. The latter involves the classical covering numbers C(n,k,k-1), and we determine the following new values: C(10,5,4) = 51, C(11,7,6,) =84, C(12,8,7) = 126, C(13,9,8)= 185 and C(14,10,9) = 259. We also find the number of nonisomorphic minimal covering designs in several cases.

0 citations0 reviewsNo code linkedOpen access
preprint2002arXiv

Quantizing Using Lattice Intersections

The usual quantizer based on an n-dimensional lattice L maps a point x in R^n to a closest lattice point. Suppose L is the intersection of lattices L_1, ..., L_r. Then one may instead combine the information obtained by simultaneously quantizing x with respect to each of the L_i. This corresponds to decomposing R^n into a honeycomb of cells which are the intersections of the Voronoi cells for the L_i, and identifying the cell to which x belongs. This paper shows how to write several standard lattices (the face-centered and body-centered cubic lattices, the root lattices D_4, E_6*, E_8, the Coxeter-Todd, Barnes-Wall and Leech lattices, etc.) in a canonical way as intersections of a small number of simpler, decomposable, lattices. The cells of the honeycombs are given explicitly and the mean squared quantizing error calculated in the cases when the intersection lattice is the face-centered or body-centered cubic lattice or the lattice D_4.

0 citations0 reviewsNo code linkedOpen access
preprint2002arXiv

The Lattice of N-Run Orthogonal Arrays

If the number of runs in a (mixed-level) orthogonal array of strength 2 is specified, what numbers of levels and factors are possible? The collection of possible sets of parameters for orthogonal arrays with N runs has a natural lattice structure, induced by the ``expansive replacement'' construction method. In particular the dual atoms in this lattice are the most important parameter sets, since any other parameter set for an N-run orthogonal array can be constructed from them. To get a sense for the number of dual atoms, and to begin to understand the lattice as a function of N, we investigate the height and the size of the lattice. It is shown that the height is at most [c(N-1)], where c= 1.4039... and that there is an infinite sequence of values of N for which this bound is attained. On the other hand, the number of nodes in the lattice is bounded above by a superpolynomial function of N (and superpolynomial growth does occur for certain sequences of values of N). Using a new construction based on ``mixed spreads'', all parameter sets with 64 runs are determined. Four of these 64-run orthogonal arrays appear to be new.

0 citations0 reviewsNo code linkedOpen access
preprint2002arXiv

The Primary Pretenders

We call a composite number q such that there exists a positive integer b with b^p == b (mod q) a prime pretender to base b. The least prime pretender to base b is the primary pretender q_b. It is shown that there are only 132 distinct primary pretenders, and that q_b is a periodic function of b whose period is the 122-digit number 19568584333460072587245340037736278982017213829337604336734362- 294738647777395483196097971852999259921329236506842360439300.

0 citations0 reviewsNo code linkedOpen access
preprint2002arXiv

The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson, Kerdock, Preparata, Goethals, and Delsarte-Goethals. It is shown here that all these codes can be very simply constructed as binary images under the Gray map of linear codes over Z_4, the integers mod 4 (although this requires a slight modification of the Preparata and Goethals codes). The construction implies that all these binary codes are distance invariant. Duality in the Z_4 domain implies that the binary images have dual weight distributions. The Kerdock and "Preparata" codes are duals over Z_4 -- and the Nordstrom-Robinson code is self-dual -- which explains why their weight distributions are dual to each other. The Kerdock and "Preparata" codes are Z_4-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z_4, which greatly simplifies encoding and decoding. An algebraic hard-decision decoding algorithm is given for the "Preparata" code and a Hadamard-transform soft-decision decoding algorithm for the Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z_4, but extended Hamming codes of length n >= 32 and the Golay code are not. Using Z_4-linearity, a new family of distance regular graphs are constructed on the cosets of the "Preparata" code.

0 citations0 reviewsNo code linkedOpen access