correlate.go

package correlate

import (
	"dft"
	"fmt"
	"math/cmplx"
)

// Cross-correlation is a measure of similarity of two waveforms as a function
// of a time-lag applied to one of them. Aka the sliding dot product. This is
// useful for determining the alignment between two signals, in our case a
// data signal and a template signal.

// A correlator is a structure which contains a single DFT and a template.
type Correlator struct {
	dft.DFT
	Template []complex128
}

func (corr Correlator) String() string {
	return fmt.Sprintf("{DFT:%s Tempate:%0.3f}", corr.DFT, corr.Template[:4])
}

// Takes a Templater and produces a correlator.
func NewCorrelator(t Templater) (corr Correlator) {
	// Get the template
	template := t.Template()

	// Plan the DFT according to template length.
	corr.Plan(len(template))

	// Compute the frequency-domain
	copy(corr.Time, template)
	corr.Forward.Execute()

	// Store conjugated frequency-domain signal as the template.
	corr.Template = make([]complex128, len(corr.Freq))
	for i := range corr.Freq {
		corr.Template[i] = cmplx.Conj(corr.Freq[i])
	}

	return
}

// Assumes signal has been copied into corr.Time (or corr.DFT.Time, same thing).
func (corr Correlator) Execute() {
	// Compute forward-dft
	corr.Forward.Execute()

	// Convolve signal with template
	for i := range corr.Freq {
		corr.Freq[i] *= corr.Template[i]
	}

	// Compte reverse-dft
	corr.Backward.Execute()
}

// A templator is any type which knows how to produce a time-domain template.
type Templater interface {
	Template() []float64
}

dft.go

package dft

import (
	"fmt"
	fft "github.com/runningwild/go-fftw"
)

// Encapsulates forward and backward DFT into single structure
type DFT struct {
	Time []float64
	Freq []complex128

	Forward  *fft.Plan
	Backward *fft.Plan
}

func (dft DFT) String() string {
	return fmt.Sprintf("{Time:%d Freq:%d}", len(dft.Time), len(dft.Freq))
}

// Allocates time and frequency data, plans real-to-complex and complex-to-real dft's
func (dft *DFT) Plan(n int) {
	// Time is just length n.
	dft.Time = fft.Alloc1dDouble(n)
	// Frequency is half length of time plus one.
	dft.Freq = fft.Alloc1d((n >> 1) + 1)

	// Plan both dft's.
	dft.Forward = fft.PlanDftR2C1d(dft.Time, dft.Freq, fft.Measure)
	dft.Backward = fft.PlanDftC2R1d(dft.Freq, dft.Time, fft.Measure)

	// Zero out the time and frequency data.
	for i := range dft.Time {
		dft.Time[i] = 0
	}
	for i := range dft.Freq {
		dft.Freq[i] = 0
	}
}

preamble_detector.go

package main

import (
	"correlate"
	"fmt"
	"log"
	"math"
	"strconv"
)

const (
	BlockSize = 1 << 15

	SampleRate = 2.4e6
	DataRate   = 32.768e3

	SymbolLength = SampleRate / DataRate

	PacketSymbols = 192
	PacketLength  = PacketSymbols * SymbolLength

	Tolerance  = 0
	TimeFormat = "2006-01-02T15:04:05.000"

	CenterFreq = 916400471
	Local      = 17581447
	Preamble   = 0x1F2A60

	RestrictLocal = true
)

// Compute this once. Wish golang supported constants assigned by expression
// or function, oh well.
var IntSymbolLength = IntRound(SymbolLength)

// A Preamble Detector is just a correlator, but we store Preamble so it can
// be used in Template method.
type PreambleDetector struct {
	preamble uint32
	correlate.Correlator
}

// Store the preamble
func NewPreambleDetector(preamble uint32) (pd PreambleDetector) {
	pd.preamble = preamble
	pd.Correlator = correlate.NewCorrelator(pd)
	return
}

// SignalTime -> SignalFreq * PreambleFreq.Conj -> OutputTime
func (pd PreambleDetector) Template() (template []float64) {
	// Allocate template data
	template = make([]float64, BlockSize)

	// Convert preamble to bits
	bits := strconv.FormatUint(uint64(pd.Preamble), 2)

	// For each bit
	for idx, bit := range bits {
		// Manchester encoding translates bits into transitions. Direction of edge determines value transmitted.
		lower := IntRound(float64(idx<<1) * SymbolLength)
		upper := lower + IntSymbolLength
		for i := 0; i < IntSymbolLength; i++ {
			// 1 -> 0 == 1, 0 -> 1 == 0.

			// For detection we don't care so much what the values actually
			// are, just that the transition characteristic exists. Looking
			// for a block of large values followed by a block of small values
			// with a steep transition produces good results for detecting
			// this feature.
			if bit == '1' {
				template[lower+i] = 1.0
				template[upper+i] = -1.0
			} else {
				template[lower+i] = -1.0
				template[upper+i] = 1.0
			}
		}
	}

	return
}

// Returns the index of the largest value the cross-correlation produced. This
// corresponds to maximum alignment between the two signals, basically: we
// found the location with highest probabilty of being a preamble.
func (pd PreambleDetector) ArgMax() (idx int) {
	max := float64(0.0)
	for i, v := range pd.Correlator.Time {
		if max < v {
			max, idx = v, i
		}
	}
	return idx
}

// Rounds to nearest integer.
func IntRound(i float64) int {
	return int(math.Floor(i + 0.5))
}

func init() {
	log.SetFlags(log.Lshortfile)
}

func main() {
	pd := NewPreambleDetector(Preamble)
	fmt.Printf("%+v\n", pd)
}