Golomb ruler

A Golomb ruler or Golomb ruler (also Golomb Ruler after the English technical term frequently ) is in number theory a ruler, which is at integer positions at the same distance are no two marks each.

Golomb rulers take their name from Solomon W. Golomb, an American professor of mathematics and electrical engineering at the University of Southern California.

Golomb rulers are categorized according to their order and their length. The order of an Golomb Ruler is defined by the number of marks, the length of the greatest distance between two markers. As parallel shift, and reflection are considered in Golomb rulers as trivial operations, the smallest marker is usually set to 0, and the subsequent labeling of the smaller of the two possible positions.

It is not necessary that a Golomb ruler can measure all distances up to its length, so that all distances between all markers - in ascending order - an unbroken series of numbers (1,2,3,4,5, ... ) result. However, if this is the case, it is called a perfect Golomb Ruler. A Golomb ruler is optimal if there is no shorter rulers of the same order. Optimal Golomb rulers can be found for a given order, as opposed to creating Golomb rulers with property, a computationally intensive task. Using distributed computing optimal Golomb rulers have so far been confirmed up to order 27 by the distributed.net project. The follow-on to order 27 confirmed by a total duration of almost five years, the shortest hitherto known ruler. The search for an optimal ruler of length 28 was started in February 2014, there will be a similar processing time as for the previous project expected.

Application

Golomb Rulers find application in the design of array antennas such as radio telescopes. Antennas in [ 0,1,4,6 ] Golomb arrangement is often found in cell towers. The arrangement of field sensors in MRI uses properties of Golomb rulers.

In both applications, the target having a minimum number of elements ( antennas and sensors) is a maximum number of different distances in three-dimensional and to achieve a maximum number of emission and reception at different angles. Are the Golomb rulers used optimally, the expansion of the measuring system and the array antenna is also minimized, which improves the handling, or use one in the first place.

Known optimal Golomb rulers

The table shows the values ​​for all the currently known optimum Golomb rulers to the order 27, wherein equivalent Ruler (i.e. in the reverse order to the one shown ) are not included. The first four make it perfect Golomb ruler dar.