HomeBlogAbout UsWorkContentContact Us
 
 Advertisment 

 

An inefficient ruler

A typical ruler has many evenly spaced markings. For instance a standard 12” ruler has 13 marks along its edge, each spaced 1” apart.

This is great, and allows the measurement all (integer) values of length between 1” and 12”.

However, a standard ruler is grossly inefficient. For example, the distance of length 1” can be measured multiple ways on this ruler.

The distance between any two adjacent marks on the ruler is 1”, so this distance can be measured twelve redundant ways.

Similarly, there are multiple ways to measure a distance of 2”, and 3” …

… Is it possible to make a more efficient ruler?

The Golomb Ruler

A mathematician named Solomon W. Golomb had this idea, and rulers of this type are named after him. A Golomb ruler comprises a series of marks such that no two pairs of marks are the same distance apart.

Below is an example. This ruler has markings that allow all integer distances between 1-6 units to be measured. Not only that, but each distance can be measured in only way way.

Golomb rulers are described by their order, which is the number of marks on their edge. The example above is an order 4 ruler. The length of a Golomb ruler is the distance between the outer two marks and, obviously, represents the longest distance it can measure. The above example has a length of 6.

There is no requirement that a Golomb ruler measures all distances up to their length – the only requirement is that each distance is only measured one way. However, if a ruler does measure all distances, it is classified as a perfect Golomb ruler. The above example is a perfect Golumb ruler.

Finally, a Golomb ruler is described as optimal if no shorter ruler of the same order exists.

To the left is an example of an optimal order 6 ruler. It has a length of 17 units. (No shorter ruler with 6 marks exists that does not duplicate any measurement).

This particular ruler is not perfect. It measures all distances up to its length with the exception of 14 and 15.

It has been proven the no perfect Golumb ruler exists that has an order higher than 4.

For certain orders, there is more than one optimal solution, but for most orders, the optimal Golumb ruler is unique (Saving, the trivial reversal obtained by rotating the ruler 180 degrees).

As you can imagine, the calculation of optimal Golomb rulers is computationally complex, and at the time of writing optimal solutions up to order 26 have been discovered.

Known Optimal Golomb Rulers

Here in tabular format are the optimal rulers known:

Order Length Marks
2 1 0 1 (perfect)
3 3 0 1 3 (perfect)
4 6 0 1 4 6 (perfect)
5 11 0 1 4 9 11
0 2 7 8 11
6 17 0 1 4 10 12 17
0 1 4 10 15 17
0 1 8 11 13 17
0 1 8 12 14 17
7 25 0 1 4 10 18 23 25
0 1 7 11 20 23 25
0 1 11 16 19 23 25
0 2 3 10 16 21 25
0 2 7 13 21 22 25
8 34 0 1 4 9 15 22 32 34
9 44 0 1 5 12 25 27 35 41 44
10 55 0 1 6 10 23 26 34 41 53 55
11 72 0 1 4 13 28 33 47 54 64 70 72
0 1 9 19 24 31 52 56 58 69 72
12 85 0 2 6 24 29 40 43 55 68 75 76 85
13 106 0 2 5 25 37 43 59 70 85 89 98 99 106
14 127 0 4 6 20 35 52 59 77 78 86 89 99 122 127
15 151 0 4 20 30 57 59 62 76 100 111 123 136 144 145 151
16 177 0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177
17 199 0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199
18 216 0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216
19 246 0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246
20 283 0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283
21 333 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333
22 356 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356
23 372 0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 372
24 425 0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 425
25 480 0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480
26 492 0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 318 343 356 386 430 440 456 464 475 487 492

Here is the same data depicted in graphical form. Remember, after order 4, there are no perfect rulers. This means there are gaps in the coverage of lengths that can be measured.

The bars below represent the sorted lengths that can be measured using each ruler. Red color represents lengths that can be measured, and white gaps show the awkward lengths that cannot. For each ruler, the number of distinct lengths that can be measured by this ruler is show in the column marked #. An efficiency percentage shows what percentage of the integer lengths from 1 to the ruler length can be measured by this particular ruler (By definition, a perfect ruler is 100% efficient).

Order Length # %  
2 1 1 100.0%
3 3 3 100.0%
4 6 6 100.0%
5 11 10 90.9%
5 11 10 90.9%
6 17 15 88.2%
6 17 15 88.2%
6 17 15 88.2%
6 17 15 88.2%
7 25 21 84.0%
7 25 21 84.0%
7 25 21 84.0%
7 25 21 84.0%
7 25 21 84.0%
8 34 28 82.4%
9 44 36 81.8%
10 55 45 81.8%
11 72 55 76.4%
11 72 55 76.4%
12 85 66 77.6%
13 106 78 73.6%
14 127 91 71.7%
15 151 105 69.5%
16 177 120 67.8%
17 199 136 68.3%
18 216 153 70.8%
19 246 171 69.5%
20 283 190 67.1%
21 333 210 63.1%
22 356 231 64.9%
23 372 253 68.0%
24 425 276 64.9%
25 480 300 62.5%
26 492 325 66.1%

As you can see, where there are multiple optimal solutions for the same length, even though the efficiency of each ruler is the same, the lengths that can be measured are different.

Here are charts of this data:

The efficiency curve is far from smooth and has dips at orders 11, 16, 21 and 25, recovering slightly afterwards, but overall the percentage efficiency decreases with order.

Considering the complexity of the calculation for the optimal rulers, it's not expected that many more data points will be received in the next few years.

The length of the order 26 optimal rule is far shorter than might be predicted by past data points.

Costas Array

Things get a little more interesting when we add in a second dimension.

A Golomb ruler has no identical distances between any of its coordinates in one dimension. A Costas Array is a similar construct but this time, rather than marks on a line, it is a collection of points on a square grid. The points are selected so that there is exactly one point in each row, one point in each column, and importantly the vector displacement between any pair of points on the grid is unique!

(Those interested in this topic, might also be interested in the Eight Queens Puzzle. By definition, a Costa Array must also solve be a solution to an n-rooks problem).

An example order 5 Costas Array is shown on the left.

Here are the displacement vectors for all combinations of points:

{3,1}, {1,2}, {2,3}, {4,4}

{-1,-2}, {2,-1}, {1,1}, {3,2}

{-2,-3}, {-1,-1}, {1,-2}, {2,1}

{-3,-1}, {-2,1}, {-1,2}, {1,3}

{-4,-4}, {-3,-2}, {-2,-1}, {-1,-3}

These vectors are all distinct.

There is no known formula, recursion, or generating function for giving the number of Costas arrays of order, and the number pure solutions (not counting the flips and rotations is know up to order 27. Here is a table of the known results.

Order# solutions
21
31
42
56
617
730
860
9100
10277
11555
12990
131,616
142,168
152,467
162,648
172,294
181,892
191,283
20810
21446
22259
23114
2425
2512
268
2729

Whilst the total number of solutions is not know above order 27, there are an infinite number of Costas arrays. (There are systems that can be used to generate them which work near prime numbers and powers of prime numbers.)

Interestingly, at the current time, there are no known Costas Arrays of order 32 or order 33!

Applications

Allegedly, when the laser was invented, it was a described by someone as “a solution looking for a problem”. I can’t help feeling the same thing about Costas Arrays. They look as though they would be incredible useful at solving many different types of problems. The only main application, however, that I’ve managed to research that uses them is in radar technology. When pulses of radiation leave a radar and are reflected back off a target, there is potentially both a change in frequency (a Doppler Shift) if the target and source are moving relative to each other, as well as the time delay based of their separation. If there is a noise in the system, these changes are hard to determine. Costas Arrays are used on radar systems to assign frequencies for the outbound pulses, and there should be only one unique solution for any pair of pulses.

The principles of Golomb rulers are used for frequency allocation to avoid third-order interference as well as in phased-array radars. They are also used for generating convolutional self-orthogonal codes.

Order 100 Costas Array

Remember, there is only one entry per row, one per column, and the vector distance between any two pair of points is unique.

 

You can find a complete list of all the articles here.      Click here to receive email alerts on new articles.

© 2009-2013 DataGenetics    Privacy Policy