Discussion Forums

draft of paper containing SETI algorithms

4 replies [Last post]
gerryharp
Offline
Joined: 2010-05-15
Posts: 365

Hi

I'm attaching a (circa 1990) draft of a paper that set out to describe the algorithms used in the SETI search at the SETI Institute. There are many authors who have worked on the paper, it contains much valuable material. Sadly, it was never published before the main authors moved on. Bernie Oliver (RIP) give credit for most of the algorithm development to Kent Cullers, who indeed is the creator of the DaDD algorithm, an NlogN approach to finding straight line signals in SETI waterfalls (section 3.2).

This summer, we plan to work with a GSoC student (and more on other projects) to create reference implementations of many algorithms. I would like to add DADD to the list of algorithms. Probaly this paper will be an excellent source of ideas for other algorithms to choose.

Note that since DADD works on any 2-D matrix, it will be helpful for studies of all kinds of waterfalls including those for conventional SETI, autocorrelation, disperse pulses, and so forth. Dadd is the algorithm that I mentioned in an earlier post relating to Dr. Tarters project.

When the website is fixed to allow uploads of arbitrary files, we'll put a link here. Meanwhile, I've posted another copy of the paper on my FTP site:

ftp://ftp.seti.org/gharp/GSoC/

I'll be happy to hear comments about algorithms that are so useful we should write a reference implementation for them. Also, have these algorithms been scooped in more recent papers?

GErry

sigblips
sigblips's picture
Offline
Joined: 2010-04-20
Posts: 733
The DADD is already

The DADD is already implemented in SonATA:

https://github.com/setiQuest/SonATA/tree/master/sig-pkg/daddLib

gerryharp
Offline
Joined: 2010-05-15
Posts: 365
DADD is already implemented

Yes, that is true.  I am interested in generating a reference implementation of DADD.

sigblips
sigblips's picture
Offline
Joined: 2010-04-20
Posts: 733
What do you mean by reference

What do you mean by reference implementation?

I was under the impression that SonATA's DADD code was operational. It also looks like it is SIMD optimized.

sigblips
sigblips's picture
Offline
Joined: 2010-04-20
Posts: 733
That

That SetiAlgorithms-CullersDeans.pdf document is an impressive collection of papers.  At 100+ pages it is going to take some time to read them, maybe an entire summer? (: I can't believe I've never seen them before. Where have they been hiding all these years?

As I've said before, Project Phoenix's DADD algorithm was my inspiration when I created baudline's Auto Drift feature many years ago. I only had about 3 paragraphs of description from some NASA paper to work with back then.  These documents would of been extremely helpful. It will be interesting reading.  How many similar conclusions did I come to? How many are different? Baudline has many varying constraints so I'll guess they will be more different than similar.