http://www.mathworks.com/matlabcentral/newsreader/view_thread/328189
MATLAB Central Newsreader  Using correlation to search for subvector within a binary time series (bitstream)
Feed for thread: Using correlation to search for subvector within a binary time series (bitstream)
enus
©19942015 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Tue, 09 Apr 2013 16:30:28 +0000
Using correlation to search for subvector within a binary time series (bitstream)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/328189#901946
Matthew
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 subvector within a binary time series (e.g., a bitstream).<br>
<br>
For example, given a pseudorandom 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?<br>
<br>
I am aware of Matlab's "find" function and its other builtin functions; I am curious to see if this approach is valid as well. Thanks!

Tue, 09 Apr 2013 17:52:13 +0000
Re: Using correlation to search for subvector within a binary time series (bitstream)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/328189#901952
Roger Stafford
"Matthew" wrote in message <kk1fn4$nrr$1@newscl01ah.mathworks.com>...<br>
> 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 subvector within a binary time series (e.g., a bitstream).<br>
> <br>
> For example, given a pseudorandom 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?<br>
> <br>
> I am aware of Matlab's "find" function and its other builtin functions; I am curious to see if this approach is valid as well. Thanks!<br>
        <br>
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.<br>
<br>
m = length(u);<br>
n = length(v);<br>
f = find(all(bsxfun(@eq,hankel(u(1:n),u(n:m)),v),2));<br>
<br>
Roger Stafford

Tue, 09 Apr 2013 18:03:27 +0000
Re: Using correlation to search for subvector within a binary time
http://www.mathworks.com/matlabcentral/newsreader/view_thread/328189#901953
dpb
On 4/9/2013 11:30 AM, Matthew wrote:<br>
> I understand how the correlation between two time series is found. I am<br>
> wondering if it is possible to use a correlation method in order to find<br>
> a particular subvector within a binary time series (e.g., a bitstream).<br>
><br>
> For example, given a pseudorandom bitstream of length 1,500, say, can<br>
> one use a correlation technique to see if the vector v = [1 1 1 1 0 1]<br>
> appears somewhere in the bitstream?<br>
><br>
> I am aware of Matlab's "find" function and its other builtin functions;<br>
> I am curious to see if this approach is valid as well. Thanks!<br>
<br>
Agree wholeheartedly w/ Roger's comments; I'll simply note that from a <br>
computational results perspective the correlation will smear the <br>
locations of correspondence significantly as opposed to the actual <br>
patternmatching which is also discrete.<br>
<br>
Now if it is "similarity" rather than exact in case of (say) a noisy <br>
signal, then there may be some advantage/reason to do something other <br>
than the exact match. But, be aware it won't be a series of '1's at the <br>
locations where the overlap occurs even in a noiseless signal and even <br>
less for noisy so interpretation can be a problem.<br>
<br>


Tue, 09 Apr 2013 18:04:06 +0000
Re: Using correlation to search for subvector within a binary time series (bitstream)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/328189#901954
Matthew
I agree; a variation of "find" would be more appropriate. Is there a way to determine this using correlation (or crosscorrelation)?<br>
<br>
Thanks,<br>
<br>
FYI, I wasn't aware of the Hankel function, but I do not have an equation to use. How does your idea apply?<br>
<br>
"Roger Stafford" wrote in message <kk1kgd$aon$1@newscl01ah.mathworks.com>...<br>
> "Matthew" wrote in message <kk1fn4$nrr$1@newscl01ah.mathworks.com>...<br>
> > 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 subvector within a binary time series (e.g., a bitstream).<br>
> > <br>
> > For example, given a pseudorandom 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?<br>
> > <br>
> > I am aware of Matlab's "find" function and its other builtin functions; I am curious to see if this approach is valid as well. Thanks!<br>
>         <br>
> 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.<br>
> <br>
> m = length(u);<br>
> n = length(v);<br>
> f = find(all(bsxfun(@eq,hankel(u(1:n),u(n:m)),v),2));<br>
> <br>
> Roger Stafford

Tue, 09 Apr 2013 18:26:11 +0000
Re: Using correlation to search for subvector within a binary time series (bitstream)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/328189#901957
Bruno Luong
"Matthew" wrote in message <kk1fn4$nrr$1@newscl01ah.mathworks.com>...<br>
<br>
> I am aware of Matlab's "find" function and its other builtin functions; I am curious to see if this approach is valid as well. Thanks!<br>
<br>
Of course.<br>
<br>
% Fake binary data<br>
a = round(rand(1,1e3));<br>
v = [1 1 1 1 0 1];<br>
<br>
% Correlation<br>
c=conv(a,fliplr(v),'valid');<br>
p=conv(a, ones(size(v)),'valid');<br>
q=sum(v);<br>
idx = find(c.^2==p*q & c>0)<br>
<br>
% Builtin function<br>
strfind(a, v)<br>
<br>
% Bruno

Tue, 09 Apr 2013 19:37:35 +0000
Re: Using correlation to search for subvector within a binary time series (bitstream)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/328189#901965
willi
<br>
"Matthew " <mamorena12@gmail.com> wrote in message <br>
news:kk1fn4$nrr$1@newscl01ah.mathworks.com...<br>
>I understand how the correlation between two time series is found. I am <br>
>wondering if it is possible to use a correlation method in order to find a <br>
>particular subvector within a binary time series (e.g., a bitstream).<br>
><br>
> For example, given a pseudorandom bitstream of length 1,500, say, can one <br>
> use a correlation technique to see if the vector v = [1 1 1 1 0 1] appears <br>
> somewhere in the bitstream?<br>
><br>
> I am aware of Matlab's "find" function and its other builtin functions; I <br>
> am curious to see if this approach is valid as well. Thanks!<br>
<br>
Try:<br>
<br>
v = [1 1 1 1 0 1];<br>
vv = [round(rand(1,250)) v round(rand(1,250numel(v)))];<br>
xc = xcorr(2*vv1,2*v1); % make it a +1/1vector<br>
xc = xc(500:end);<br>
plot(xc/numel(v), '.');grid<br>
<br>
This algorithm will also find the inverse pattern.<br>
<br>
<br>
Best rgds

Tue, 09 Apr 2013 19:50:21 +0000
Re: Using correlation to search for subvector within a binary time series (bitstream)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/328189#901968
Roger Stafford
> > m = length(u);<br>
> > n = length(v);<br>
> > f = find(all(bsxfun(@eq,hankel(u(1:n),u(n:m)),v),2));<br>
      <br>
I didn't get that right. It should be:<br>
<br>
f = find(all(bsxfun(@eq,hankel(u(1:mn+1),u(mn+1:m)),v),2));<br>
<br>
Roger Stafford

Tue, 09 Apr 2013 21:04:06 +0000
Re: Using correlation to search for subvector within a binary time series (bitstream)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/328189#901972
Roger Stafford
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kk1mg3$hgg$1@newscl01ah.mathworks.com>...<br>
> % Correlation<br>
> c=conv(a,fliplr(v),'valid');<br>
> p=conv(a, ones(size(v)),'valid');<br>
> q=sum(v);<br>
> idx = find(c.^2==p*q & c>0)<br>
        <br>
That's very clever, Bruno. Still, couldn't you get the same result with just one call on 'conv':<br>
<br>
idx = find(conv(a1/2,fliplr(v1/2),'valid')==length(v)/4);

Tue, 09 Apr 2013 21:25:05 +0000
Re: Using correlation to search for subvector within a binary time series (bitstream)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/328189#901973
Bruno Luong
"Roger Stafford" wrote in message <kk1vo6$iv0$1@newscl01ah.mathworks.com>...<br>
<br>
> That's very clever, Bruno. Still, couldn't you get the same result with just one call on 'conv':<br>
> <br>
> idx = find(conv(a1/2,fliplr(v1/2),'valid')==length(v)/4);<br>
<br>
Simple and nice.<br>
<br>
Bruno

Wed, 10 Apr 2013 01:13:13 +0000
Re: Using correlation to search for subvector within a binary time series (bitstream)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/328189#901979
Matthew
These suggestions are all very helpful...thank you Roger, Bruno, willi, and dpb.<br>
<br>
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kk20vh$me6$1@newscl01ah.mathworks.com>...<br>
> "Roger Stafford" wrote in message <kk1vo6$iv0$1@newscl01ah.mathworks.com>...<br>
> <br>
> > That's very clever, Bruno. Still, couldn't you get the same result with just one call on 'conv':<br>
> > <br>
> > idx = find(conv(a1/2,fliplr(v1/2),'valid')==length(v)/4);<br>
> <br>
> Simple and nice.<br>
> <br>
> Bruno