Matched Filter In the Frequency Domain Question

Maybe somebody can help me think about this the right way.  

Ok, it is well known that there is an 'equivalence' in convolution in the
time domain to multiplication in the frequncy domain, so consider this...

Say we have a modulated bitstream of lets say 10 bits and knew what they
were., then did a simple matched filter operation (on the modulated signal
maybe perurbed by noise that corrupted exactly 1 bit), and compared the
bits to the output of the matched filter... we should be able to recover
the bits and see which one was in error.

Now lets try this in the frequency domain... We take the transform of the
10 bitstream. Now since the matched filtering operation is really just
convolution time reversed, we expect to be able to take the transform of
the matched filter and multiply the phase by a -1, then do the
multiplication  F(k)(bits)*H(k)(matched filter negative phase). {please
excuse my crude notation}.

Now what? Will we never be able to find out which bit was in error?, The
way im thinking about it.. I shouldnt have to take the inverse transform,
to get my answer... the 'information' content cant change due to a linear
transform assuming the basis functions are complete.

Any thoughts?

On Apr 6, 9:08&#4294967295;am, "westocl" <cweston_@n_o_s_p_a_m.hotmail.com> wrote:
> Maybe somebody can help me think about this the right way. &#4294967295;
>
> Ok, it is well known that there is an 'equivalence' in convolution in the
> time domain to multiplication in the frequncy domain, so consider this...
>
> Say we have a modulated bitstream of lets say 10 bits and knew what they
> were., then did a simple matched filter operation (on the modulated signal
> maybe perurbed by noise that corrupted exactly 1 bit), and compared the
> bits to the output of the matched filter... we should be able to recover
> the bits and see which one was in error.
>
> Now lets try this in the frequency domain... We take the transform of the
> 10 bitstream. Now since the matched filtering operation is really just
> convolution time reversed, we expect to be able to take the transform of
> the matched filter and multiply the phase by a -1, then do the
> multiplication &#4294967295;F(k)(bits)*H(k)(matched filter negative phase). {please
> excuse my crude notation}.
>
> Now what? Will we never be able to find out which bit was in error?, The
> way im thinking about it.. I shouldnt have to take the inverse transform,
> to get my answer... the 'information' content cant change due to a linear
> transform assuming the basis functions are complete.
>
> Any thoughts?

You are correct in that you can equivalently perform convolution in
the frequency domain. I'm not sure why you think that an inverse
transform shouldn't be needed in order to recover the time-domain
information bits. There is no loss of information in translating
between the two domains (with infinite precision). But that doesn't
change the fact that it's easier to get at certain results in
different domains; that's a large reason for analyzing signals in
multiple contexts. There's no information loss in applying AES
encryption with a known key to ASCII text; that doesn't mean that you
should expect to be able to read a block of ciphertext and get the
same utility that the plaintext gives you.

Jason

On Apr 6, 8:08&#4294967295;am, "westocl" <cweston_@n_o_s_p_a_m.hotmail.com> wrote:
> Maybe somebody can help me think about this the right way. &#4294967295;
>
> Ok, it is well known that there is an 'equivalence' in convolution in the
> time domain to multiplication in the frequncy domain, so consider this...
>
> Say we have a modulated bitstream of lets say 10 bits and knew what they
> were., then did a simple matched filter operation (on the modulated signal
> maybe perurbed by noise that corrupted exactly 1 bit), and compared the
> bits to the output of the matched filter... we should be able to recover
> the bits and see which one was in error.
>
> Now lets try this in the frequency domain... We take the transform of the
> 10 bitstream. Now since the matched filtering operation is really just
> convolution time reversed, we expect to be able to take the transform of
> the matched filter and multiply the phase by a -1, then do the
> multiplication &#4294967295;F(k)(bits)*H(k)(matched filter negative phase). {please
> excuse my crude notation}.
>
> Now what? Will we never be able to find out which bit was in error?, The
> way im thinking about it.. I shouldnt have to take the inverse transform,
> to get my answer... the 'information' content cant change due to a linear
> transform assuming the basis functions are complete.
>
> Any thoughts?

Add up all the Fourier Transform values.  You should
get a real number (the imaginary part should cancel
out in the absence of noise but when noise is present,
you may get a complex number whose imaginary
component should be discarded).  The real number that
you would get in the absence of noise can take on any
one of 2^10 equally spaced values corresponding
to the values of the 10 bits.  The real number you
just got by the summation of Fourier Transform
values will almost surely not be any of these 2^10
equally spaced values because of the presence
of noise.  Now, map the real number you just
computed to the nearest of the 2^10 equally spaced
values, and you will have made a decision as to what
the 10 bits are.

Warning: Do not try this at home.  Even though
I am a trained professional, I would leery of doing
things this way, but since you asked....

Hope this helps

Dilip Sarwate

On 04/06/2011 06:08 AM, westocl wrote:
> Maybe somebody can help me think about this the right way.
>
> Ok, it is well known that there is an 'equivalence' in convolution in the
> time domain to multiplication in the frequncy domain, so consider this...
>
> Say we have a modulated bitstream of lets say 10 bits and knew what they
> were., then did a simple matched filter operation (on the modulated signal
> maybe perurbed by noise that corrupted exactly 1 bit), and compared the
> bits to the output of the matched filter... we should be able to recover
> the bits and see which one was in error.
>
> Now lets try this in the frequency domain... We take the transform of the
> 10 bitstream. Now since the matched filtering operation is really just
> convolution time reversed, we expect to be able to take the transform of
> the matched filter and multiply the phase by a -1, then do the
> multiplication  F(k)(bits)*H(k)(matched filter negative phase). {please
> excuse my crude notation}.
>
> Now what? Will we never be able to find out which bit was in error?, The
> way im thinking about it.. I shouldnt have to take the inverse transform,
> to get my answer... the 'information' content cant change due to a linear
> transform assuming the basis functions are complete.

I think you are misapplying the concept of a matched filter.

You know that a matched filter is one with an impulse response equal to 
the time-reversal of the signal that you're going to detect.  That's 
good.  But you seem to be missing two things: the matched filter is 
optimal when the signal that you're going to detect has no intersymbol 
interference, and when the signal is being corrupted by additive white 
Gaussian noise.

You're not corrupting your signal with white Gaussian noise: you're 
choosing a 10-symbol two-value signal, and you're corrupting it by 
flipping the value of one of the symbols.  That's neither Gaussian, nor 
white, nor additive.  I _think_, without having had any caffeine yet 
this morning, that your signal could be one without intersymbol 
interference, but trying to make my brain spin that fast doesn't seem to 
be having much effect yet.

So I think the answer is that if you already know what the data pattern 
is, if you want to use a matched filter to see if one bit is off you 
should use it as a paperweight while you look at each bit, and choose 
the one that doesn't match the pattern.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

On 4/6/2011 6:08 AM, westocl wrote:
> Maybe somebody can help me think about this the right way.
>
> Ok, it is well known that there is an 'equivalence' in convolution in the
> time domain to multiplication in the frequncy domain, so consider this...
>
> Say we have a modulated bitstream of lets say 10 bits and knew what they
> were., then did a simple matched filter operation (on the modulated signal
> maybe perurbed by noise that corrupted exactly 1 bit), and compared the
> bits to the output of the matched filter... we should be able to recover
> the bits and see which one was in error.
>
> Now lets try this in the frequency domain... We take the transform of the
> 10 bitstream. Now since the matched filtering operation is really just
> convolution time reversed, we expect to be able to take the transform of
> the matched filter and multiply the phase by a -1, then do the
> multiplication  F(k)(bits)*H(k)(matched filter negative phase). {please
> excuse my crude notation}.
>
> Now what? Will we never be able to find out which bit was in error?, The
> way im thinking about it.. I shouldnt have to take the inverse transform,
> to get my answer... the 'information' content cant change due to a linear
> transform assuming the basis functions are complete.
>
> Any thoughts?

If I understand what you'd propose in the time domain is a type of error 
detection.  Is that right?
As you do the convolution you're looking for a peak in order to detect 
the 10-bit sequence when the match is best.  So, presumably you're 
matching over 10-bit sequences?  That is, the convolution integral is 
over a 10-bit sequence?

Consider this:
Take the case where there is no noise and filter two sequences:
- one that is an exact match.
- one that is 1 bit off.
What do you get?  .. a difference in the peak value.  So, a good 
question is: can you reasonably detect the difference in  peak value? 
Usually the matched filter process is looking for temporal peaks and not 
so much for measuring peak amplitudes as such.  Consider channel 
attenuation, etc.

I guess one could filter using *every* 10-bit sequence with a single bit 
that's flipped - so that's 11 replicas if you include the correct one. 
Then you could compare the amplitudes of the same signal with different 
replicas.  At least the amplitudes should have a relation and you might 
be able to tell *which* bit is off this way.  Otherwise with only one 
replica you'd only be able to tell that there was 1 bit off but not 
where... well, as above, maybe you could do that.

So, I'm a bit skeptical that the example is a well posed approach to 
what you want to do.

OK, with that as a starting point, take the FFT of the replica(s) and 
multiply by the signal.

I think you can imagine the answer to your question about "information 
content".
- First of all, as above, the information you seek is tenuous at best.
- Second, the Fourier Transform changes narrow things into wide things 
and vice versa.  You're looking for a narrow thing in time so it's going 
to be wide in frequency.  So, the "result" will be spread over a number 
of spectral samples and I'd worry a lot about SNR - which I don't see 
improving by doing the FT in the first place.
The FT is very often used to find narrow things in frequency and you're 
looking for a narrow thing in time.

Fred

On Wed, 06 Apr 2011 08:08:40 -0500, "westocl" <cweston_@n_o_s_p_a_m.hotmail.com>
wrote:

>Now lets try this in the frequency domain... 

<...>

>Now what? Will we never be able to find out which bit was in error?, The
>way im thinking about it.. I shouldnt have to take the inverse transform,
>to get my answer... the 'information' content cant change due to a linear
>transform assuming the basis functions are complete.

As others have mentioned, matched-filter convolution is probably NOT the best
way to accomplish your goal, that goal being the detection -- in the frequency
domain -- of which bit has been corrupted. But there is a way.

Assume that your 10-bit uncorrupted sequence consists of N "1" bits and (10-N)
"0" bits. 

Now assume that your 10-bit uncorrupted sequence is the sum of N sequences, each
of which has exactly one "1" bit and exactly nine "0" bits, with no overlap
between the "1" bits. That is to say, if one of the sequences contains a "1" in
position "k", then none of the other sequences contains a "1" in position "k".

Now compute the DFT of each of those N unique sequences. You will find that a
sequence consisting of a "1" followed by nine "0" bits will have a DFT
consisting of a constant real part and a zero imaginary part. A sequence
consisting of a "0" followed by a "1" followed by eight "0" bits will have a DFT
consisting of one cycle of a cosine wave in the real part, and one cycle of a
sine wave in the imaginary part. And so on ... a sequence consisting of M "0"
bits followed by a "1" bit followed by (9-M) "0" bits will have a DFT consisting
of M cycles of a cosine in the real part and M cycles of a sine in the imaginary
part.

Now compute the DFT of your complete uncorrupted sequence as the sum of the DFTs
of the individual sequences computed above (or just compute the DFT of the
original sequence).

Now compute the DFT of your CORRUPTED sequence, and subtract that from the DFT
of your UNcorrupted sequence. Compare the difference that you just computed with
the individual DFTs of the unique sequences. Whichever one matches is the bit
that has been corrupted.

Greg