[RC5] Golomb stuff

Joe Zbiciak j-zbiciak1 at ti.com
Tue Mar 3 20:05:40 EST 1998

'Dan Nordquist' said previously:
| Thanks for the mini-FAQ... it answered lots of questions.  However, I have
| two more:
| a) What makes anyone think that radio dishes should be spaced out in integer
| intervals?  That seems very odd.  You want a VLA with all inter-dish
| intervals different, wouldn't you want to use all real numbers?  

I'll assume "real" to mean "irrational numbers whose differences are
not rational multiples of a common irrational factor."  That's because
the current set of integer segment lengths in a Golomb ruler can be
transformed into a set of non-integer, irrational lengths through
multiplication with an irrational number (eg. sqrt(2)), but said
lengths are integer multiples of each other.

Suppose the segments on a Golomb ruler were irrational lengths that did
not divide each other by rational factors.  It would be difficult to
correlate measurements between different pairs of marks on such a
ruler.  What good would a ruler with marks at sqrt(2), e, and pi be?
You can measure six distances, none of which is rational.  Making a
correlating filter that would correlate data from four antennas with
this internal spacing would be a mess, I would imagine.   A golomb
ruler with marks at 1, 4, and 6, though, can measure the six lengths 1,
2, 3, 4, 5, and 6.  Correlating data between antennas with this set of
spacings would probably work well with a comb-filter type of

| Some sort
| of Fibonnacci sequence, at least?

Suppose we wanted a six mark ruler.  Lets take the "gap" between the
first few Fibonacci terms.  The classical Fibonacci sequence goes "1,
1, 2, 3, 5, 8, 13, 21..."  The gap between these terms goes "0, 1, 2,
3, 5, 8,...".  We'd throw away the gap of "0" (since it would lead to
two colocated marks) and use the gaps "1, 2, 3, 5, 8".  We'd place our
marks like so:

    0 1   3     6        11              19

Such a ruler is 19 units long, and can measure the following
distances:  1, 2, 3*, 5*, 6, 8*, 10, 11, 13, 16, 18, and 19.  The
distances 3, 5, and 8 can be measured two different ways (eg. 3 can be
measured as [0,3] or as [3,6]).  This ruler measures only 12 unique

Compare this to an optimal 6 mark Golomb Ruler.  One such ruler has
tick spacings 1, 3, 6, 2, 5.  The ruler looks like so, then:

    0 1     4          10  12        17

The first thing to notice is that the ruler is two units shorter.  With
radio telescope arrays, this means either that you've saved land, or
you've placed the dishes more optimally in the space you had.  This
ruler measures the distances 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
16, and 17.  Notice that the array measures no distance twice; rather,
the ruler measures 15 unique distances.

Basically, Golomb rulers represent a sort of discrete number
optimization problem.

Are there any mathemeticians out there cringing yet at my possibly
horribly fractured explanation?  (Go easy on me, I'm only a simple
engineer.  ;-)  I'm almost certain there's another whole level of
detail that I'm missing....  (such as geometric properties of triangles
whose bases are formed by segments on a Golomb ruler that allow such
rulers to perform distance and measurement *perpendicular to the ruler*
or similar, or am I grasping at straws here?  :-)



 +----------- Joseph Zbiciak ----------+  Eliminate idle cycles!
 | - - - -  j-zbiciak1 at ti.com  - - - - |  http://www.distributed.net/
 |- http://www.primenet.com/~im14u2c/ -| 
 | - - -Texas Instruments, Dallas- - - |  "Give them a light, and they'll
 +-----#include "std_disclaimer.h"-----+   follow it anywhere." -- Firesign
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list