Adaptive Filter for Binary Signal?

Hello,

I'm taking an adaptive filter course, and have been given a desired
signal and a distorted signal.  The desired signal is non-return-to-
zero purely random binary data, i.e. -1, 1, 1, -1, 1, -1 etc.  The
distorted is this exact same signal, but filtered and added with
noise.  We are to filter the distorted signal using adaptive filter
methods that we learned, namely steepest descent, LMS, RLS, etc.

My question is, is this AT ALL realistic?  Would you ever equalize a
binary signal?  I thought equalizers and adaptive filters would run on
a modulated waveform signal, not pure binary.  Unfortunately, I'm
beginning to doubt my teachers wisdom in giving us this project!

For example, the BER on the distorted signal is about 0.48.  I used
the optimal Wiener filter (not-adaptive, I know), and the MSE went
from about 4 down to 0.995.  But that is HORRIBLE for binary data!
The BER went down to only like 0.478.  And of course stuff like LMS,
steepest descent, etc, which also try to minimize MSE are never going
to be better than the Wiener filter, so this seems like a meaningless
pursuit!

My Wiener filter is good.  I tried it on some distorted audio, and the
result was fantastic.  It took out almost all the distortion.  So
that's not my problem.

I'm trying to understand why these methods don't work on binary data.
Could anyone explain this to me?  Is there something inherent in the
mean square minimizing filters that takes advantage of the fact that
consecutive samples are dependent on each other. (Obviously, with the
data I've been given, the previous sample has no bearing on the
next.)  In class examples we always used AR process type signals,
which have samples that are always correlated with the previous
sample.  We never had a single example with abrupt binary data, as
this is.

To be clear, here is an actual excerpt of some part of the desired
signal and the distorted:

    1.0000   -1.0000    1.0000    1.0000   -1.0000   -1.0000
-1.0000    1.0000    1.0000    1.0000   -1.0000
   -0.1417    1.0748   -0.0883   -1.1488    0.8724    0.0210
0.9441   -0.9969   -1.1470   -0.8130    1.0622

basically, it's the same 1's and -1's, but scaled by the channel and
noise.

Would you EVER send data in this form over a noisy/fading channel such
as this one??  Should adaptive filtering techniques work in this case?

jerothb <jerothb@gmail.com> wrote:
 
> I'm taking an adaptive filter course, and have been given a desired
> signal and a distorted signal.  The desired signal is non-return-to-
> zero purely random binary data, i.e. -1, 1, 1, -1, 1, -1 etc.  The
> distorted is this exact same signal, but filtered and added with
> noise.  We are to filter the distorted signal using adaptive filter
> methods that we learned, namely steepest descent, LMS, RLS, etc.
 
> My question is, is this AT ALL realistic?  Would you ever equalize a
> binary signal?  I thought equalizers and adaptive filters would run on
> a modulated waveform signal, not pure binary.  Unfortunately, I'm
> beginning to doubt my teachers wisdom in giving us this project!

This sounds pretty much like the problem of data coming off
tape or disk.  Though people learned a long time ago that NRZ
wasn't the best choice, it is still a choice.

-- glen

But for something like that, wouldn't you just use error control
coding?  Did they actually run adaptive filters for this type of
situation?


> This sounds pretty much like the problem of data coming off
> tape or disk. =A0Though people learned a long time ago that NRZ
> wasn't the best choice, it is still a choice.
>
> -- glen

jerothb wrote:

> Hello,
> 
> I'm taking an adaptive filter course, and have been given a desired
> signal and a distorted signal.  The desired signal is non-return-to-
> zero purely random binary data, i.e. -1, 1, 1, -1, 1, -1 etc.  The
> distorted is this exact same signal, but filtered and added with
> noise.  We are to filter the distorted signal using adaptive filter
> methods that we learned, namely steepest descent, LMS, RLS, etc.
> 
> My question is, is this AT ALL realistic?   Would you ever equalize a
> binary signal?  I thought equalizers and adaptive filters would run on
> a modulated waveform signal, not pure binary.  Unfortunately, I'm
> beginning to doubt my teachers wisdom in giving us this project!

Not to worry. It is you who is the idiot. Filters are agnostic to the 
waveform.

VLV

On 12/01/2010 09:31 AM, jerothb wrote:
> Hello,
>
> I'm taking an adaptive filter course, and have been given a desired
> signal and a distorted signal.  The desired signal is non-return-to-
> zero purely random binary data, i.e. -1, 1, 1, -1, 1, -1 etc.  The
> distorted is this exact same signal, but filtered and added with
> noise.  We are to filter the distorted signal using adaptive filter
> methods that we learned, namely steepest descent, LMS, RLS, etc.
>
> My question is, is this AT ALL realistic?  Would you ever equalize a
> binary signal?  I thought equalizers and adaptive filters would run on
> a modulated waveform signal, not pure binary.  Unfortunately, I'm
> beginning to doubt my teachers wisdom in giving us this project!

1: Yes, there are still binary signals out there (see Glen's response).

2: After carrier recovery and downconversion, a PSK signal appears as an 
NRZ binary signal to subsequent stages of a receiver; if my head has not 
become buried in my (admittedly hasty -- you're not paying for this) 
assumptions then applying the equalizer at this point is just as 
effective as trying to do so in the modulated carrier domain, and is 
potentially much cheaper.

3: The purpose of doing the exercise isn't to design a whiz-bang working 
system, the purpose is to learn the semantics and mechanics of adaptive 
filtering.  Ever notice how many 4th-year control systems classes 
demonstrate how state-space design techniques can be used to balance an 
inverted pendulum?  Ever went walking through any city in the world and 
counted all the inverted pendulums in use every day?

> For example, the BER on the distorted signal is about 0.48.  I used
> the optimal Wiener filter (not-adaptive, I know), and the MSE went
> from about 4 down to 0.995.  But that is HORRIBLE for binary data!
> The BER went down to only like 0.478.  And of course stuff like LMS,
> steepest descent, etc, which also try to minimize MSE are never going
> to be better than the Wiener filter, so this seems like a meaningless
> pursuit!

The teacher probably added too much noise -- try the same problem, only 
with less noise.  Take it from me -- designing homework problems that 
are clear, that make the student work hard at what you want to teach 
him, and that don't require him to know things that are unrelated to the 
course prerequisites is _hard work_, and fraught with error.  Making a 
problem that is also realistic and fun is all the harder.  When you've 
walked a mile in those shoes, then criticize.

Consider, too, that the point of an adaptive filter in this context is 
that you don't have a clue what the channel distortion is before you 
design the system.  Because a Wiener filter demands prior knowledge of 
the channel, you cannot, by definition, design it ahead of time.

> My Wiener filter is good.  I tried it on some distorted audio, and the
> result was fantastic.  It took out almost all the distortion.  So
> that's not my problem.
>
> I'm trying to understand why these methods don't work on binary data.

You are extrapolating from one data point.

> Could anyone explain this to me?

Extrapolate from more data points -- try whomping up your own related 
problem(s).  Vary the amount of filtering in the channel, and the amount 
of noise.  See how well your methods work then.

> Is there something inherent in the
> mean square minimizing filters that takes advantage of the fact that
> consecutive samples are dependent on each other. (Obviously, with the
> data I've been given, the previous sample has no bearing on the
> next.)  In class examples we always used AR process type signals,
> which have samples that are always correlated with the previous
> sample.  We never had a single example with abrupt binary data, as
> this is.
>
> To be clear, here is an actual excerpt of some part of the desired
> signal and the distorted:
>
>      1.0000   -1.0000    1.0000    1.0000   -1.0000   -1.0000
> -1.0000    1.0000    1.0000    1.0000   -1.0000
>     -0.1417    1.0748   -0.0883   -1.1488    0.8724    0.0210
> 0.9441   -0.9969   -1.1470   -0.8130    1.0622
>
> basically, it's the same 1's and -1's, but scaled by the channel and
> noise.
>
> Would you EVER send data in this form over a noisy/fading channel such
> as this one??  Should adaptive filtering techniques work in this case?

These days, maybe not.  But maybe if the channel dispersion isn't too 
severe then the receiver overhead of adaptive filtering may well be 
lower than the receiver overhead of spread spectrum or whatever.

Before folks figured out how to make spread spectrum work reliably it 
was common to frame communications problems as "well, this here PSK 
works pretty darn well in the clear; let's use it on this here 
dispersive channel and figure out how to patch up the receiver so's it 
all comes out right in the end".  For some systems that may still be the 
answer.

-- 

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

Then why does it work so poorly?  I'm just trying to come up with a
mathematical reason.  Yes, it lowers the MSE, as it should, but who
cares?  The BER is still crap.

Also, I would not even call this a waveform.  These are NOT pulses of
x-sample length.  These are literally random samples of either 1 or
-1.

On Dec 1, 3:03=A0pm, Vladimir Vassilevsky <nos...@nowhere.com> wrote:
> Not to worry. It is you who is the idiot. Filters are agnostic to the
> waveform.
>
> VLV

Knowlegde is power. Power is 10c per KW/h. My power is mere 10 MW, and I 
bet I can fix your problem in less then 1 hour. Ready?


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com




jerothb wrote:

> Then why does it work so poorly?  I'm just trying to come up with a
> mathematical reason.  Yes, it lowers the MSE, as it should, but who
> cares?  The BER is still crap.
> 
> Also, I would not even call this a waveform.  These are NOT pulses of
> x-sample length.  These are literally random samples of either 1 or
> -1.
> 
> On Dec 1, 3:03 pm, Vladimir Vassilevsky <nos...@nowhere.com> wrote:
> 
>>Not to worry. It is you who is the idiot. Filters are agnostic to the
>>waveform.
>>
>>VLV
> 
> 

Well, it requires the autocorrelation matrix of the input, and the
cross-correlation of the input and the desired signal.  All of this, I
do have.  That's where the knowledge of the channel is taken from.

Create the correlation matrix of the input signal, u(n):

r=3Dxcorr(u,M-1);
r=3Dr(M:end);
R=3Dtoeplitz(r, conj(r));

then create the cross-correlation vector between the signal u(n), and
the desired signal d(n):

p=3Dxcorr(u,d,M-1);
p=3Dp(M:end);

so the wiener filter coefficients are simply

w =3D (R^-1)*p;

then I just do

estimate =3D conv(w,u);

Am I wrong?  I mean this is simple, and the wiener filter is the
optimum benchmark.  But since the BER didn't lower, the recursive
algorithms aren't going to do anything better.

> Consider, too, that the point of an adaptive filter in this context is
> that you don't have a clue what the channel distortion is before you
> design the system. =A0Because a Wiener filter demands prior knowledge of
> the channel, you cannot, by definition, design it ahead of time.

Dude, wtf are you talking about?  I'm not interested in anyone doing
my work...

On Dec 1, 3:20=A0pm, Vladimir Vassilevsky <nos...@nowhere.com> wrote:
> Knowlegde is power. Power is 10c per KW/h. My power is mere 10 MW, and I
> bet I can fix your problem in less then 1 hour. Ready?
>

I see. You are interested in anyone doing your work for free. Fuck off.


jerothb wrote:

> Dude, wtf are you talking about?  I'm not interested in anyone doing
> my work...
> 
> On Dec 1, 3:20 pm, Vladimir Vassilevsky <nos...@nowhere.com> wrote:
> 
>>Knowlegde is power. Power is 10c per KW/h. My power is mere 10 MW, and I
>>bet I can fix your problem in less then 1 hour. Ready?
> 
>>