Golomb Ruler

A Golomb ruler is a set of Nonnegative integers such that all pairwise Positive differences are distinct. The optimum Golomb ruler with $n$ marks is the Golomb ruler having the smallest possible maximum element (``length''). The set (0, 1, 3, 7) is an order four Golomb ruler since its differences are ($1=1-0$, $2=3-1$, $3=3-0$, $4=7-3$, $6=7-1$, $7=7-0$), all of which are distinct. However, the optimum 4-mark Golomb ruler is (0, 1, 4, 6), which measures the distances (1, 2, 3, 4, 5, 6) (and is therefore also a Perfect Ruler).

The lengths of the optimal $n$-mark Golomb rulers for $n=2$, 3, 4, ... are 1, 3, 6, 11, 17, 25, 34, ... (Sloane's A003022, Vanderschel and Garry). The lengths of the optimal $n$-mark Golomb rulers are not known for $n\geq 20$.

See also Perfect Difference Set, Perfect Ruler, Ruler, Taylor's Condition, Weighings

References

Atkinson, M. D.; Santoro, N.; and Urrutia, J. ``Integer Sets with Distinct Sums and Differences and Carrier Frequency Assignments for Nonlinear Repeaters.'' IEEE Trans. Comm. 34, 614-617, 1986.

Colbourn, C. J. and Dinitz, J. H. (Eds.) CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, p. 315, 1996.

Guy, R. K. ``Modular Difference Sets and Error Correcting Codes.'' §C10 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 118-121, 1994.

Lam, A. W. and D. V. Sarwate, D. V. ``On Optimum Time Hopping Patterns.'' IEEE Trans. Comm. 36, 380-382, 1988.

Robinson, J. P. and Bernstein, A. J. ``A Class of Binary Recurrent Codes with Limited Error Propagation.'' IEEE Trans. Inform. Th. 13, 106-113, 1967.

Sloane, N. J. A. Sequence A003022/M2540 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Vanderschel, D. and Garry, M. ``In Search of the Optimal 20 & 21 Mark Golomb Rulers.'' http://members.aol.com/golomb20/.