Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Using correlation to search for subvector within a binary time series (bitstream)

Subject: Using correlation to search for subvector within a binary time series (bitstream)

From: Matthew

Date: 9 Apr, 2013 16:30:28

Message: 1 of 10

I understand how the correlation between two time series is found. I am wondering if it is possible to use a correlation method in order to find a particular sub-vector within a binary time series (e.g., a bitstream).

For example, given a pseudo-random bitstream of length 1,500, say, can one use a correlation technique to see if the vector v = [1 1 1 1 0 1] appears somewhere in the bitstream?

I am aware of Matlab's "find" function and its other built-in functions; I am curious to see if this approach is valid as well. Thanks!

Subject: Using correlation to search for subvector within a binary time series (bitstream)

From: Roger Stafford

Date: 9 Apr, 2013 17:52:13

Message: 2 of 10

"Matthew" wrote in message <kk1fn4$nrr$1@newscl01ah.mathworks.com>...
> I understand how the correlation between two time series is found. I am wondering if it is possible to use a correlation method in order to find a particular sub-vector within a binary time series (e.g., a bitstream).
>
> For example, given a pseudo-random bitstream of length 1,500, say, can one use a correlation technique to see if the vector v = [1 1 1 1 0 1] appears somewhere in the bitstream?
>
> I am aware of Matlab's "find" function and its other built-in functions; I am curious to see if this approach is valid as well. Thanks!
- - - - - - - - -
  Using correlation with something as discrete as a bitstream seems inappropriate to me. Why not use a direct equality test? Let row vectors u and v be the long and short time series, respectively.

 m = length(u);
 n = length(v);
 f = find(all(bsxfun(@eq,hankel(u(1:n),u(n:m)),v),2));
 
Roger Stafford

Subject: Using correlation to search for subvector within a binary time

From: dpb

Date: 9 Apr, 2013 18:03:27

Message: 3 of 10

On 4/9/2013 11:30 AM, Matthew wrote:
> I understand how the correlation between two time series is found. I am
> wondering if it is possible to use a correlation method in order to find
> a particular sub-vector within a binary time series (e.g., a bitstream).
>
> For example, given a pseudo-random bitstream of length 1,500, say, can
> one use a correlation technique to see if the vector v = [1 1 1 1 0 1]
> appears somewhere in the bitstream?
>
> I am aware of Matlab's "find" function and its other built-in functions;
> I am curious to see if this approach is valid as well. Thanks!

Agree wholeheartedly w/ Roger's comments; I'll simply note that from a
computational results perspective the correlation will smear the
locations of correspondence significantly as opposed to the actual
pattern-matching which is also discrete.

Now if it is "similarity" rather than exact in case of (say) a noisy
signal, then there may be some advantage/reason to do something other
than the exact match. But, be aware it won't be a series of '1's at the
locations where the overlap occurs even in a noiseless signal and even
less for noisy so interpretation can be a problem.

--

Subject: Using correlation to search for subvector within a binary time series (bitstream)

From: Matthew

Date: 9 Apr, 2013 18:04:06

Message: 4 of 10

I agree; a variation of "find" would be more appropriate. Is there a way to determine this using correlation (or cross-correlation)?

Thanks,

FYI, I wasn't aware of the Hankel function, but I do not have an equation to use. How does your idea apply?

"Roger Stafford" wrote in message <kk1kgd$aon$1@newscl01ah.mathworks.com>...
> "Matthew" wrote in message <kk1fn4$nrr$1@newscl01ah.mathworks.com>...
> > I understand how the correlation between two time series is found. I am wondering if it is possible to use a correlation method in order to find a particular sub-vector within a binary time series (e.g., a bitstream).
> >
> > For example, given a pseudo-random bitstream of length 1,500, say, can one use a correlation technique to see if the vector v = [1 1 1 1 0 1] appears somewhere in the bitstream?
> >
> > I am aware of Matlab's "find" function and its other built-in functions; I am curious to see if this approach is valid as well. Thanks!
> - - - - - - - - -
> Using correlation with something as discrete as a bitstream seems inappropriate to me. Why not use a direct equality test? Let row vectors u and v be the long and short time series, respectively.
>
> m = length(u);
> n = length(v);
> f = find(all(bsxfun(@eq,hankel(u(1:n),u(n:m)),v),2));
>
> Roger Stafford

Subject: Using correlation to search for subvector within a binary time series (bitstream)

From: Bruno Luong

Date: 9 Apr, 2013 18:26:11

Message: 5 of 10

"Matthew" wrote in message <kk1fn4$nrr$1@newscl01ah.mathworks.com>...

> I am aware of Matlab's "find" function and its other built-in functions; I am curious to see if this approach is valid as well. Thanks!

Of course.

% Fake binary data
a = round(rand(1,1e3));
v = [1 1 1 1 0 1];

% Correlation
c=conv(a,fliplr(v),'valid');
p=conv(a, ones(size(v)),'valid');
q=sum(v);
idx = find(c.^2==p*q & c>0)

% Builtin function
strfind(a, v)

% Bruno

Subject: Using correlation to search for subvector within a binary time series (bitstream)

From: willi

Date: 9 Apr, 2013 19:37:35

Message: 6 of 10


"Matthew " <mamorena12@gmail.com> wrote in message
news:kk1fn4$nrr$1@newscl01ah.mathworks.com...
>I understand how the correlation between two time series is found. I am
>wondering if it is possible to use a correlation method in order to find a
>particular sub-vector within a binary time series (e.g., a bitstream).
>
> For example, given a pseudo-random bitstream of length 1,500, say, can one
> use a correlation technique to see if the vector v = [1 1 1 1 0 1] appears
> somewhere in the bitstream?
>
> I am aware of Matlab's "find" function and its other built-in functions; I
> am curious to see if this approach is valid as well. Thanks!

Try:

v = [1 1 1 1 0 1];
vv = [round(rand(1,250)) v round(rand(1,250-numel(v)))];
xc = xcorr(2*vv-1,2*v-1); % make it a +1/-1-vector
xc = xc(500:end);
plot(xc/numel(v), '.-');grid

This algorithm will also find the inverse pattern.

--
Best rgds

Subject: Using correlation to search for subvector within a binary time series (bitstream)

From: Roger Stafford

Date: 9 Apr, 2013 19:50:21

Message: 7 of 10

> > m = length(u);
> > n = length(v);
> > f = find(all(bsxfun(@eq,hankel(u(1:n),u(n:m)),v),2));
- - - - - - -
  I didn't get that right. It should be:

 f = find(all(bsxfun(@eq,hankel(u(1:m-n+1),u(m-n+1:m)),v),2));

Roger Stafford

Subject: Using correlation to search for subvector within a binary time series (bitstream)

From: Roger Stafford

Date: 9 Apr, 2013 21:04:06

Message: 8 of 10

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kk1mg3$hgg$1@newscl01ah.mathworks.com>...
> % Correlation
> c=conv(a,fliplr(v),'valid');
> p=conv(a, ones(size(v)),'valid');
> q=sum(v);
> idx = find(c.^2==p*q & c>0)
- - - - - - - - -
  That's very clever, Bruno. Still, couldn't you get the same result with just one call on 'conv':

 idx = find(conv(a-1/2,fliplr(v-1/2),'valid')==length(v)/4);

Subject: Using correlation to search for subvector within a binary time series (bitstream)

From: Bruno Luong

Date: 9 Apr, 2013 21:25:05

Message: 9 of 10

"Roger Stafford" wrote in message <kk1vo6$iv0$1@newscl01ah.mathworks.com>...

> That's very clever, Bruno. Still, couldn't you get the same result with just one call on 'conv':
>
> idx = find(conv(a-1/2,fliplr(v-1/2),'valid')==length(v)/4);

Simple and nice.

Bruno

Subject: Using correlation to search for subvector within a binary time series (bitstream)

From: Matthew

Date: 10 Apr, 2013 01:13:13

Message: 10 of 10

These suggestions are all very helpful...thank you Roger, Bruno, willi, and dpb.

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kk20vh$me6$1@newscl01ah.mathworks.com>...
> "Roger Stafford" wrote in message <kk1vo6$iv0$1@newscl01ah.mathworks.com>...
>
> > That's very clever, Bruno. Still, couldn't you get the same result with just one call on 'conv':
> >
> > idx = find(conv(a-1/2,fliplr(v-1/2),'valid')==length(v)/4);
>
> Simple and nice.
>
> Bruno

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us