Golomb Rulers

by James Buckland

Golomb rulers are mathematical structures (rulers, really) which almost perfectly demonstrate my earlier article on the oft-delayed values of pure mathematics. A perfect Gombol ruler will be a set of markings which can measure every consecutive integer distance below its total length. For example: the gombol ruler of order four (four markings) and length six (in total, six units long) contains, within it, the measurements: 

golomb_4_optimal

which are consecutive, optimal, and non-repeating. This is a fascinating mathematical structure — particularly the proof that a perfect (non-repeating) Golomb ruler with more than four marks on it cannot exist.

However, it is the applications, as duly noted in Bill Rankin’s 1993 thesis on the topic (section 1.2), that are of particular interest — indeed, it has applications in radio telecommunications, x-ray crystallography, radio arrays, and anything else which requires the deliberate and efficient mechanical use of integer-valued nodes on wavelengths — that is, the need for an apparent continuum to be split into integer values. In addition, Golomb rulers can be used by information theory to produce efficient error-correcting codes (transmissions with additional information about their coherent communication) as a sort of hash function; a self-orthogonal structure which reacts predictably to any errors in communication.

In conclusion — Golomb rulers are wicked cool.

Advertisements