G-2003-79
On the Design of Optimum Order 2 Golomb Ruler
, et référence BibTeX
A Golomb ruler with M marks can be defined as a set {ai} of integers so that all differences δij = aj - ai, i ≠ j, 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.
Paru en novembre 2003 , 19 pages
Document
G-2003-79.pdf (200 Ko)