Groupe d’études et de recherche en analyse des décisions

G-2003-79

On the Design of Optimum Order 2 Golomb Ruler

, et

A Golomb ruler with M marks can be defined as a set {ai} of integers so that all differences δij = aj - ai, ij, are distinct. An order 2 Golomb ruler is a Golomb ruler such that all differences δijkl = |δkl - δij|, {i,j} ≠ {k,l}, are distinct as much as possible. Construction of optimum order 2 Golomb ruler, i.e., of rulers of minimum length, is a highly combinatorial problem which has applications, e.g.,
in the design of convolutional self doubly orthogonal codes (CSO2C). We propose here a first exact algorithm, different from a pure exhaustive search, for building optimum order 2 Golomb rulers and provide optimal rulers for up to 9 marks and new rulers which improve on the previous ones for up to 20 marks.

, 19 pages