Jump to content

Talk:Golomb ruler

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Practical applications

[edit]

This page doesn't answer a query of mine.

Ok I can see it being used with large arrays of telescopes, but are there (or is there planned) arrays of 25 telescopes? I guess what I'm trying to ask is is there a need to find Golomb rulers of such high orders? I'm assuming there is if distributed.net is putting power behind it, but there is no clear reason on that either. Smremde 13:53, 25 September 2006 (UTC)[reply]

This page: http://faq.distributed.net/cache/134.html from the distributed.net site lists a few uses: "OGR's have many applications including sensor placements for X-ray crystallography and radio astronomy. Golomb rulers can also play a significant role in combinatorics, coding theory and communications." Someone with more of a clue might want to add a note to that effect. 62.79.64.148 04:43, 23 August 2007 (UTC)[reply]

http://en.wikipedia.org/wiki/Very_Large_Array http://www.vla.nrao.edu/ is a 27 radio telescope array. Each scope is movable, theoretically you could arrange them into a Golomb ruler if you convinced them to do so (that would provide extremely high resolution in only one dimension, perhaps beyond practical engineering limits, so they may not want to do that just for fun) 24.160.224.134 (talk) 21:34, 11 October 2010 (UTC)[reply]

Golomb ruler - applications @ IBM research lists at least 3 book references to applications of Golomb rulers. Abstracts and relevant text selection are available online...

From such it would seem Golumb Rulers may have practical applications in...

  • Radio, frequency selection to avoid intermodulation interference both on Earth and across space
  • Information Theory Error Codes, codes used to detect and correct data errors

Kolano (talk) 21:36, 14 March 2011 (UTC)[reply]

How about replacing the text with:

While low-order Golomb rulers are used in the design of phased array radio antennas such as radio telescopes, there is limited practical application of high-order Golomb rulers in such technology. Antennas in a [0,1,4,6] Golomb ruler configuration can often be seen at cell sites. ((original research}} --74.83.16.145 (talk) 16:22, 26 April 2012 (UTC)[reply]

Perfect rulers in table

[edit]

The table says it contains all optimal rulers of a given order: maybe someone with more time to spare than I have right now could check which ones are perfect and come up with a way of distinguishing them? —Phil | Talk 08:59, 14 November 2005 (UTC)[reply]

It has been proven that no perfect Golomb ruler exists for five or more ticks., as we only list one ruler for each of 4 and below, I think it's clear. :) --Gmaxwell 00:06, 7 April 2006 (UTC)[reply]

The real use of such a device is to measure the distance between yourself and THE PRECIOUS!! —Preceding unsigned comment added by 75.13.135.142 (talk) 05:35, 26 October 2008 (UTC)[reply]

Name conflict on "OGR"

[edit]

As of 20:29, 22 September 2006 (UTC), OGR links to this page. However, I suggest replacing the redirect page with a disambiguation page, because OGR can also refer to several other things. See: google:OGR. Examples: the OGR library which comes with GDAL/OGR; International Order of the Golden Rule; Online Gaming Resource; Office of Government Relations. — Teratornis 20:29, 22 September 2006 (UTC)[reply]

I have created a new disambiguation page at OGR. --Ghewgill 01:00, 24 September 2006 (UTC)[reply]

Are Golomb rulers symmetric?

[edit]

Say, you'd rewrite 0 1 4 10 18 23 25 as 25 24 21 15 7 2 0 by using 25 - x on each element, it would still be a Golomb ruler, right? Are there any standards on which version should be used?

Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values. or use the basic arithmetic: if two elements are x and y do what you said so x -> 25 - x and y -> 25 - y now check the differences: x - y and (25 - x) - (25 - y) = 25 - x - 25 + y = -x + y = y - x which is still the same because this problem is about ABSOLUTE differences (and |x - y| = |y - x|, any map of X -> Constant -/+ X is a OGR if X is an OGR. 94.208.111.0 (talk) 20:24, 26 October 2008 (UTC)[reply]

Utility and limitations for radio telescope arrays

[edit]

Linear arrays of radio telescopes can in principle be configured according to the values of a Golomb ruler. In practice, however, one of the most important properties of a telescope (its resolving power) is not consistent with the defining properties of the Golomb ruler. If the configuration of a linear array radio telescope was determined by a Golomb ruler, then the telescope's resolution would be proportional to the maximum difference between elements of the ruler for which all differences less than it are also present. The fact that Golomb ruler designs attempt to produce as large a maximum difference as possible makes them attractive for radio telecope designs. The problem is that one of the defining property of the Golomb ruler is the requirement that no difference be generated by more than one pair of its elements. In radio telescope parlance, these would be called redundant baselines. The avoidance of redundant baselines is generally not considered a driving requirement in the design of radio telescope arrays, and the presence of redundancies would be considered perfectly acceptable if they enabled an improvement in resolving power. For this reason, if a Golomb ruler were used to determine the placement of elements in a linear array of telescopes, it would in most cases be considered sub-optimal.

A counterexample to the Golomb ruler with 10 elements illustrates this point. The Golomb ruler has elements

[0 1 6 10 23 26 34 41 53 55]

The maximum difference below which all differences are present is 35 (generated by 41 minus 6). This is the maximum because all differences below 35 are present but there is no difference of 36. An alternate configuration for a linear array of 10 radio telescopes is

[0 1 3 6 13 20 27 31 35 36]

The maximum difference in this case is 36, which is one more than the Golomb ruler and hence would produce a radio telescope with 36/35 times better resolution. This alternate configuration does have some redundant baselines and so it would not qualify as a Golomb ruler. But it would be the preferred configuration for most radio telescope designers.

Large linear arrays radio telescopes for Earth environmental monitoring from aircraft have been built with 5, 10 and 14 elements. In each case, the Golomb ruler design has not been used because it does not optimize the resolution. Satellite versions of these telescopes with significantly larger numbers of elements are currently being designed that also do not use Golomb ruler configurations for the same reason.

There is one other practical reason why Golomb ruler configurations are generally considered sub-optimal for aircraft and satellite applications. The maximum difference between all possible elements in the Golomb ruler is often much larger than the maximum difference below which all differences are present. If the Golomb ruler configuration was used, the telescope would end up being much larger than it would have been if the maximum possible difference was the same as the maximum difference below which all differences are present. The two 10 element configurations listed above illustrate this. The Golomb ruler has a maximum difference of 55 whereas the alternate configuration has a maximum of 36. A linear array based on the Golomb ruler would be 55/36 times larger and have slightly poorer resolution. Since unnecessarily large structures on satellites are generally avoided whenever possible, a telescope designer would be unlikely to chose the Golomb ruler configuration. CR (talk) 17:28, 30 October 2008 (UTC)[reply]

Suggested Edits

[edit]

In the external links, the link to "James B. Shearer's Golomb ruler pages" appears to no longer go directly to the indicated page, but to a generic page at IBM for their labs. I suspect having this link on this page no longer offers any value, other than free advertising for IBM. —Preceding unsigned comment added by 67.193.106.116 (talk) 14:52, 6 September 2010 (UTC)[reply]

The dates need updating with original discovery dates and proof dates. For example, OGR-24 result was verified 1 November 2004, but it was originally discovered in 1967 by John P. Robinson and Arthur J. Bernstein. OGR 25-27 were all found by Atkinson and Hassenklover in 1984. They also gave results up to 100 marks, with results for 48, 72, and 98 added in 1986. Then there is T. Rokicki and G. Dogon, "Possibly Optimal Golomb Rulers Calculated for 160 to 40,000 Marks," (Jul 7, 2016) cube20.org/golomb. EdPeggJr (talk) 19:59, 25 October 2020 (UTC)[reply]

almost-Golomb ruler

[edit]

Is there something like ruler where a condition that no distance are coded twice can be relaxed? It could in principle bring more flexibility and possibly encode more distances using same number of marks. —Preceding unsigned comment added by 91.213.255.7 (talk) 20:28, 3 May 2011 (UTC)[reply]

Example program

[edit]

There's a page here with a program relating to Golomb rulers. Maybe we could add it somewhere? — Preceding unsigned comment added by 82.23.61.36 (talk) 01:04, 2 March 2017 (UTC)[reply]

Dubious claim about cell phone antennas

[edit]

I've removed the following deeply suspect claim from the article:

Antennas in a [0,1,4,6] Golomb ruler configuration can often be seen at AM tower or cell sites.

Why would a broadcast antenna or cell tower, which are required to have omnidirectional coverage, use a phased array configuration? And why would it need to have a choice of six different spacings? Also, having browsed through several of the images of cell phone base stations to be found on Wikipedia, I found no examples of Golomb ruler configurations, which would seem to disprove the "often" part at the very least. (Not that finding something that did look like one would actually prove anything, of course, since there would be no evidence that the arrangement was deliberate.)
By the way, the text had previously been tagged as [dubiousdiscuss], but the tag was quietly removed - and an additional unsourced factoid inserted - without any discussion. Well, maybe now someone will discuss it.
I was tempted to remove the part about transformers too, but it at least seems plausible, so I left it in. But it really does need a reference. 88.144.54.111 (talk) 19:08, 9 April 2022 (UTC)[reply]