A Golomb ruler with M marks can be defined as a set {a_i} of integers so that all differences δ_ij = a_j - a_i, 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 (CSO²C). 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.