Find a Binary Data Sequence in a Signal

Question

Here's my goal:

I'm trying to find a way to search through a data signal and find (index) locations where a known, repeating binary data sequence is located. Then, because the spreading code and demodulation is known, pull out the corresponding chip of data and read it. Currently, I believe xcorr will do the trick.

Here's my problem:

I can't seem to interpret my result from xcorr or xcorr2 to give me what I'm looking for. I'm either having a problem cross-referencing from the vector location of my xcorr function to my time vector, or a problem properly identifying my data sequence with xcorr, or both. Other possibilities may exist.

Where I am at/What I have:

I have created a random BPSK signal that consists of the data sequence of interest and garbage data over a repeating period. I have tried processing it using xcorr, which is where I am stuck.

Here's my code:

%% Clear Variables

clc;
clear all, close all;

%% Create random data

nbits = 2^10;
ngarbage = 3*nbits;
data = randi([0,1],1,nbits);
garbage = randi([0,1],1,ngarbage);
stream = horzcat(data,garbage); 

%% Convert from Unipolar to Bipolar Encoding

stream_b = 2*stream - 1;

%% Define Parameters

%%% Variable Parameters
nsamples = 20*nbits;
nseq = 5 %# Iterate stream nseq times
T = 10; %# Number of periods
Ts = 1; %# Symbol Duration
Es = Ts/2; %# Energy per Symbol
fc = 1e9; %# Carrier frequency

%%% Dependent Parameters
A = sqrt(2*Es/Ts); %# Amplitude of Carrier
omega = 2*pi*fc %# Frequency in radians
t = linspace(0,T,nsamples) %# Discrete time from 0 to T periods with nsamples samples
nspb = nsamples/length(stream) %# Number of samples per bit

%% Creating the BPSK Modulation
%# First we have to stretch the stream to fit the time vector. We can quickly do this using _
%# simple matrix manipulation.

% Replicate each bit nspb/nseq times
repStream_b = repmat(stream_b',1,nspb/nseq);

% Tranpose and replicate nseq times to be able to fill to t
modSig_proto = repmat(repStream_b',1,nseq);

% Tranpose column by column, then rearrange into a row vector
modSig = modSig_proto(:)';

%% The Carrier Wave

carrier = A*cos(omega*t);

%% Modulated Signal

sig = modSig.*carrier;

Using XCORR

I use xcorr2() to eliminate the zero padding effect of xcorr on unequal vectors. See comments below for clarification.

corr = abs(xcorr2(data,sig); %# pull the absolute correlation between data and sig
[val,ind] = sort(corr(:),'descend') %# sort the correlation data and assign values and indices
ind_max = ind(1:nseq); %# pull the nseq highest valued indices and send to ind_max

Now, I think this should pull the five highest correlations between data and sig. These should correspond to the end bit of data in the stream for every iteration of stream, because I would think that is where the data would most strongly cross-correlate with sig, but they do not. Sometimes the maxes are not even one stream length apart. So I'm confused here.

Question

In a three part question:

1. Am I missing a certain step? How do I use xcorr in this case to find where data and sig are most strongly correlated?

2. Is my entire method wrong? Should I not be looking for the max correlations?

3. Or should I be attacking this problem from another angle, id est, not use xcorr and maybe use filter or another function?

Answer 1

Your overall method is great and makes a lot of sense. The problem you're having is that you're getting some actual correlation with your garbage data. I noticed that you shifted all of your sream to be zero-centered, but didn't do the same to your data. If you zero-center the data, your correlation peaks will be better defined (at least that worked when I tried it).

data = 2*data -1;

Also, I don't recommend using a simple sort to find your peaks. If you have a wide peak, which is especially possible with a noisy signal, you could have two high points right next to each other. Find a single maximum, and then zero that point and a few neighbors. Then just repeat however many times you like. Alternatively, if you know how long your epoch is, only do a correlation with one epoch's worth of data, and iterate through the signal as it arrives.

Answer 2

With @David K 's and @Patrick Mineault's help I manage to track down where I went wrong. First @Patrick Mineault suggested I flip the signals. The best way to see what you would expect from the result is to slide the small vector along the larger, searched vector. So

corr = xcorr2(sig,data);

Then I like to chop off the end there because it's just extra. I did this with a trim function I made that simply takes the signal you're sliding and trims it's irrelevant pieces off the end of the xcorr result.

trim = @(x,s2) x(1:end - (length(s2) - 1));
trim(corr,data);

Then, as @David K suggests, you need to have the data stream you're looking for encoded the same as your searched signal. So in this case

data = 2*data-1;

Second, if you just have your data at it's original bit length, and not at it's stretched, iterated length, it can be found in the signal but it will be VERY noisy. To reduce the noise, simply stretch the data to match it's stretched length in the iterated signal. So

rdata = repmat(data',1,nspb/nseq);
rdata = repmat(rdata',1,nseq);
data = rdata(:)';

Now finally, we should have crystal clear correlations for this case. And to pull out the maxes that should correspond to those correlations I wrote

[sortedValues sortIndex] = sort(corr(:),'descend');
c = 0 ;
for r = 1 : length(sortedValues)
    if sortedValues(r,:) == max(corr)
        c = c + 1;
        maxIndex(1,c) = sortIndex(r,:);
    else break % If you don't do this, you get loop lock
    end
 end 

Now c should end up being nseq for this case and you should have 5 index times where the corrs should be! You can easily pull out the bits with another loop and c or length(maxIndex). I've also made this into a more "real world" toy script, where there is a data stream, doppler, fading, and it's over a time vector in seconds instead of samples.

Thanks for the help!