Linear-phase FIR filter coefficient properties

Thank you very much r b-j.

@Fred
Thank you very much for that comprehensive explanation. I think I get the
idea you are saying, in a sort of theoretical way, but not clear as to use
this in a practical system.

>
>- A purely real sequence can be split into even and odd parts.
>- An even sequence will yield an even and real Fourier Transform.
>- An odd sequence will yield an odd and imaginary Fourier Transform.
>And, you can substitute Inverse Fourier Transform above.

I'm not sure which even and odd you are mentioning here. Is it about how a
sequence can be represented as a sum of conjugate symmetric and conjugate
antisymmetric parts as:

       x[n] = x_e[n] + x_o[n]
where,
       x_e[n] = 0.5*(x[n] + x*[-n])
       x_o[n] = 0.5*(x[n] - x*[-n])

and then
      DFT(x_e[n]) = Re{X[f]}
      DFT(x_o[n]) = Im{X[f]}




>But now one needs to ask what kind of baseband filtering is needed and, 
>by itself, that has nothing to do with whether the baseband signal is 
>real or complex.  It has everything to do with what filtering you want 
>to perform ... an how you want to do it.
>
>One way to think of this situation is to compute an analytic signal that 
>isn't fully "basebanded".  Just move it so the lowest frequencies end up 
>just above zero.  It takes twice the bandwidth but it remains real I 
>believe.  Then you can apply a real filter that is asymmetric relative 
>to the center frequency.  I think this is right .. haven't done it.
>(And then, you might conceptually baseband the result).
>
>But, if you must baseband to center at zero then a channel equalizer may 
>be asymmetric in frequency and, thus have an odd part.  This non-even 
>magnitude response will yield a complex IFT and, thus, a complex-valued 
>filter.
>
>Now, as others have pointed out, if you have a complex signal sequence 
>then, by superposition, you handle it like a "real" sequence and an 
>"imaginary" sequence and you apply "the filter" to both of these 
>sequences. In general, this will yield two complex sequences that would 
>be combined (summed) into one real sequence and one imaginary sequence.
>Now you have a filtered version of the analytic signal sequence.
>

I understand this from a theoretical point, but couldn't grasp the idea
when I use this in a DMT  system. For example, at the transmitter, I get
the output from the IFFT, which is ofcourse complex, and the frequency
spectrum of these complex points are from -N/2 to N/2. Now this would make
the sequence (complex) baseband. Then again, -N/2 to 0 is the same as N/2
to (N-1). This would mean what you said about moving the lowest frequency
just above DC, I suppose.

When calculating (I)DFT, we can choose the summation from -N/2 to N/2, or
just as well use 0 to (N-1). Atleast that was my understanding. But does it
have an impact. For example if feed complex-points to ifft routine, it
outputs N complex values. How would I choose (or know) if it's baseband
(-N/2 to N/2) or not (0 to N-1)? Am I understanding this completely wrong?

As far as the channel goes, the channel gains, or subcarrier values, can go
from (-N/2 to N/2) or from (0 to N-1). What actually matters is that there
is a one-to-one correspondence between the complex-inputs (to the IDFT) and
 the corresponding channel value. I.e. at the output of the channel,
complex-input (-N/2) is multiplied by channel value (-N/2), or if we are
using the shifted one, complex-input point 0 multiplied by channel value at
0.

I'm sorry for the long post, but how does this all line up when we are
working on IDFT output samples?

Thank you very much.

On Aug 19, 1:24=A0am, "m26k9" <maduranga.liyanage@n_o_s_p_a_m.gmail.com>
wrote:
> Thank you very much r b-j.
>
> @Fred
> Thank you very much for that comprehensive explanation. I think I get the
> idea you are saying, in a sort of theoretical way, but not clear as to us=
e
> this in a practical system.
>
>
>
> >- A purely real sequence can be split into even and odd parts.
> >- An even sequence will yield an even and real Fourier Transform.
> >- An odd sequence will yield an odd and imaginary Fourier Transform.
> >And, you can substitute Inverse Fourier Transform above.
>
> I'm not sure which even and odd you are mentioning here. Is it about how =
a
> sequence can be represented as a sum of conjugate symmetric and conjugate
> antisymmetric parts as:
>
> =A0 =A0 =A0 =A0x[n] =3D x_e[n] + x_o[n]
> where,
> =A0 =A0 =A0 =A0x_e[n] =3D 0.5*(x[n] + x*[-n])
> =A0 =A0 =A0 =A0x_o[n] =3D 0.5*(x[n] - x*[-n])
>
> and then
> =A0 =A0 =A0 DFT(x_e[n]) =3D Re{X[f]}
> =A0 =A0 =A0 DFT(x_o[n]) =3D Im{X[f]}
>
>
>
> >But now one needs to ask what kind of baseband filtering is needed and,
> >by itself, that has nothing to do with whether the baseband signal is
> >real or complex. =A0It has everything to do with what filtering you want
> >to perform ... an how you want to do it.
>
> >One way to think of this situation is to compute an analytic signal that
> >isn't fully "basebanded". =A0Just move it so the lowest frequencies end =
up
> >just above zero. =A0It takes twice the bandwidth but it remains real I
> >believe. =A0Then you can apply a real filter that is asymmetric relative
> >to the center frequency. =A0I think this is right .. haven't done it.
> >(And then, you might conceptually baseband the result).
>
> >But, if you must baseband to center at zero then a channel equalizer may
> >be asymmetric in frequency and, thus have an odd part. =A0This non-even
> >magnitude response will yield a complex IFT and, thus, a complex-valued
> >filter.
>
> >Now, as others have pointed out, if you have a complex signal sequence
> >then, by superposition, you handle it like a "real" sequence and an
> >"imaginary" sequence and you apply "the filter" to both of these
> >sequences. In general, this will yield two complex sequences that would
> >be combined (summed) into one real sequence and one imaginary sequence.
> >Now you have a filtered version of the analytic signal sequence.
>
> I understand this from a theoretical point, but couldn't grasp the idea
> when I use this in a DMT =A0system. For example, at the transmitter, I ge=
t
> the output from the IFFT, which is ofcourse complex, and the frequency
> spectrum of these complex points are from -N/2 to N/2. Now this would mak=
e
> the sequence (complex) baseband. Then again, -N/2 to 0 is the same as N/2
> to (N-1). This would mean what you said about moving the lowest frequency
> just above DC, I suppose.
>
> When calculating (I)DFT, we can choose the summation from -N/2 to N/2, or
> just as well use 0 to (N-1). Atleast that was my understanding. But does =
it
> have an impact. For example if feed complex-points to ifft routine, it
> outputs N complex values. How would I choose (or know) if it's baseband
> (-N/2 to N/2) or not (0 to N-1)? Am I understanding this completely wrong=
?
>
> As far as the channel goes, the channel gains, or subcarrier values, can =
go
> from (-N/2 to N/2) or from (0 to N-1). What actually matters is that ther=
e
> is a one-to-one correspondence between the complex-inputs (to the IDFT) a=
nd
> =A0the corresponding channel value. I.e. at the output of the channel,
> complex-input (-N/2) is multiplied by channel value (-N/2), or if we are
> using the shifted one, complex-input point 0 multiplied by channel value =
at
> 0.

i lost track with what you're originally trying to do.  if i remember,
it had something to do with I and Q signals, no?

about complex vs. real signals; here is a little bit of philosophy and
i know some others will disagree.

in physical reality we only have "real quantities".  i know many
disagree, but i think the terms "real number" and "imaginary number"
are very appropriate.  anyway, you can conceptualize a complex signal

    x[n] =3D i[n] + j*q[n]

where i[n] and q[n] are both real and are the real and imaginary parts
of x[n].  if q[n] is non-zero, then we know that the DTFT of x[n] does
not have that conjugate symmetry property, but it is only if the
Hilbert Transform of i[n] is q[n] that the negative frequency
components of x[n] are zero.

anyway, *all* of this is conceptualization.  use it at the chalkboard,
but remember that you're dealing with real signals that are connected
to real I/O devices.  creating a complex signal out of two real
signals is something that exists only in the mind of the designer (and
you can pretend it exists in the mind of the DSP or CPU).

anyway, that's what i think.

r b-j

>anyway, *all* of this is conceptualization.  use it at the chalkboard,
>but remember that you're dealing with real signals that are connected
>to real I/O devices.  creating a complex signal out of two real
>signals is something that exists only in the mind of the designer (and
>you can pretend it exists in the mind of the DSP or CPU).
>
>anyway, that's what i think.
>
>r b-j
>

Thank you very much r b-j.

So in that sense, a complex-filter, is a concept too? I mean we could have
a complex-signal (ex: IDFT output) and send it through a complex-filer.
Convolving two complex sequences. Then again, this is something I can do in
Matlab, not in a DSP I guess.

I guess I'm lost at what's theory and how it is actually done in a DSP. For
example, a Rayleigh channel is a complex filter. If I am going to make a
equalizer for this channel, I would have a complex filter, would I not? 

I guess in a DSP, the IDFT operation returns two real data streams, once
for the real part of the output, and the other for the imaginary part. And
I'm thinking I need to filter these two independently? In theory, when we
take the DFT of these complex signals, it has a frequency spectrum -N/2 to
N/2, or 0 to N-1. That would be different when we take the real and
imaginary parts separately? 

I'm just used to think of complex numbers as one composite number and it is
confusing to think of it as two real numbers. I guess too much Matlab.

Thank you very much again.

m26k9 wrote:
> Thank you very much r b-j.
> 
> @Fred
> Thank you very much for that comprehensive explanation. I think I get the
> idea you are saying, in a sort of theoretical way, but not clear as to use
> this in a practical system.
> 
>> - A purely real sequence can be split into even and odd parts.
>> - An even sequence will yield an even and real Fourier Transform.
>> - An odd sequence will yield an odd and imaginary Fourier Transform.
>> And, you can substitute Inverse Fourier Transform above.
> 
> I'm not sure which even and odd you are mentioning here. Is it about how a
> sequence can be represented as a sum of conjugate symmetric and conjugate
> antisymmetric parts as:
> 
>        x[n] = x_e[n] + x_o[n]
> where,
>        x_e[n] = 0.5*(x[n] + x*[-n])
>        x_o[n] = 0.5*(x[n] - x*[-n])

***Yes, the formulation above.
> 
> and then
>       DFT(x_e[n]) = Re{X[f]}
>       DFT(x_o[n]) = Im{X[f]}

***Yes, as above, by superposition.

***Well, I chose to not get all twisted up with real/imaginary and 
conjugate because they are extensions of the idea.

> I understand this from a theoretical point, but couldn't grasp the idea
> when I use this in a DMT  system. For example, at the transmitter, I get
> the output from the IFFT, which is ofcourse complex, and the frequency
> spectrum of these complex points are from -N/2 to N/2. Now this would make
> the sequence (complex) baseband. This would mean what you said about moving the lowest frequency
> just above DC, I suppose.

***I'm having a bit of a hard time following you here.  I don't much 
care *how* you get the "analytic signal" and don't know exactly *what* 
you're doing an IFFT on.

***I suggest we first settle on what is an analytic signal.  In my 
understanding the analytic signal is what results if you take a bandpass 
signal and move the center frequency to zero.  This makes the time 
series complex in general as the bandpass signal need not be even about 
the center frequency.  If it were, then the analytic signal could be 
real.  Anyway, when a signal is truly "baseband" then this is it.

***What I was suggesting as a "data point", was to shift the center 
frequency down to just >B/2 instead of to zero (where B is the bandwidth 
of the bandpass signal).  Then the component at f=0 would be zero (or 
close enough) and the spectrum would continue to be even about zero and 
the temporal sequence would continue to be real.  So, this isn't really 
a fully "basebanded" signal in normal terminology I think.  It's just a 
signal containing all the information but with a lower overall bandwidth.
And, I'm not even dealing with sampling here....... continuous signals 
are fine for this part of the discussion.

> 
> When calculating (I)DFT, we can choose the summation from -N/2 to N/2, or
> just as well use 0 to (N-1). Atleast that was my understanding. But does it
> have an impact. For example if feed complex-points to ifft routine, it
> outputs N complex values. How would I choose (or know) if it's baseband
> (-N/2 to N/2) or not (0 to N-1)? Am I understanding this completely wrong?

***I think you have it.  This was the "reference point" I mentioned. 
It's best to select a single method and stick with it so that the 
peculiarities will come out.  For example, I normally *think* in terms 
of an even function being even about zero but normally compute from zero 
to N-1.  That means that an even function has its upper half starting at 
zero and going up to N/2 and its lower half starting at N and going down 
to N/2.  Well, actually, there is no sample at N and we assume that it's 
the same value as the sample at zero.

> 
> As far as the channel goes, the channel gains, or subcarrier values, can go
> from (-N/2 to N/2) or from (0 to N-1). What actually matters is that there
> is a one-to-one correspondence between the complex-inputs (to the IDFT) and
>  the corresponding channel value. I.e. at the output of the channel,
> complex-input (-N/2) is multiplied by channel value (-N/2), or if we are
> using the shifted one, complex-input point 0 multiplied by channel value at
> 0.

***As above, it pays to not get wound up around the sequence indices too 
much (just get them correct).  In sampled data it's best to envision 
that the samples fall on a circular axis and repeat infinitely.  The 
question then is only: "where is the orgin?".  I'm still unclear what 
you're transforming and why......  But, this is an issue in the 
mechanics of doing the computations and not more than that.  Presumably 
you are wanting to convolve the signal by the channel unit sample 
response as if any other filter?

Fred

Fred, Thank you very much for all the explanations.

I think I have tangled few things together and looking at this from a wrong
angle. Your explanation actually made it clear. I think I got it to some
extent.

Why I was mentioning IDFT was because I am working with an ADSL system. So
I input 'N' number of QAM points (complex data) to an IFFT routine, and I
get 'N' complex numbers as output. In a DSP this would be 2xN real values.

Now this is where I start to get confused. 

Suppose I get those 'N' complex outputs and put them to an FFT routine
(reverse). I get 'N' complex points (which are same as my QAM points), but
those 'N' points are the "frequency response". This frequency response can
be from -N/2 to N/2, OR it could be 0 to (N-1), depends on the range of the
summation, or the twiddle factors.

My confusion is here:
>***What I was suggesting as a "data point", was to shift the center 
>frequency down to just >B/2 instead of to zero (where B is the bandwidth 
>of the bandpass signal).  Then the component at f=0 would be zero (or 
>close enough) and the spectrum would continue to be even about zero and 
>the temporal sequence would continue to be real.

Now when I have my (I)DFT output points, how would I "shift" them so that
the lowest frequency is just above f=0? Do I multiply by e^(jf)? And isn't
this "shifting" same as doing the DFT summation from 0 to (N-1), instead of
(-N/2) to (N/2)? Because in both case I start with complex sequences and
end up with complex sequences.
Am I doing this all wrong? 

Thank you very much Fred. I will go back and read some again.  

>
> anyway, *all* of this is conceptualization. �use it at the chalkboard,
> but remember that you're dealing with real signals that are connected
> to real I/O devices. �creating a complex signal out of two real
> signals is something that exists only in the mind of the designer (and
> you can pretend it exists in the mind of the DSP or CPU).
>
> anyway, that's what i think.
>
> r b-j- Hide quoted text -
>
> - Show quoted text -

the way I think about it is:

real = one dimensional
complex = two dimensional

you can use two real signal to make a complex signal =
you can use two 1D signals to make a 2 D signal

in the lab, in order to move a 2D (analog) signal from one piece of
gear to another, there are always 2 BNC connectors, (usually labeled I
and Q)

Mark

>
>the way I think about it is:
>
>real =3D one dimensional
>complex =3D two dimensional
>
>you can use two real signal to make a complex signal =3D
>you can use two 1D signals to make a 2 D signal
>
>in the lab, in order to move a 2D (analog) signal from one piece of
>gear to another, there are always 2 BNC connectors, (usually labeled I
>and Q)
>
>Mark
>

Thank you Mark.

I think the problem is me trying to think of a complex number as a one
quantity. 
The problem actually started because I cannot understand why filter
coefficients are real and not complex. I know this is something I cannot do
in a DSP, but theoretically filters could be complex. Example when
equalizing a channel. 

It's quite messed up for me at this moment.

m26k9 wrote:

> 
> Why I was mentioning IDFT was because I am working with an ADSL system. So
> I input 'N' number of QAM points (complex data) to an IFFT routine, and I
> get 'N' complex numbers as output. In a DSP this would be 2xN real values.
> 

Well, this isn't an implementation/application that I'm familiar with 
offhand.  The one paper I scanned quickly says this:
"The size is doubled by mirroring the data to impose conjugate symmetry 
in the frequency domain, which results in real-valued signal in the time 
domain after applying the IDFT."
from:
http://users.ece.utexas.edu/~bevans/courses/ee382c/projects/spring04/MustafaErwa/LitSurveyReport.pdf

I don't know if this helps but it makes some kinda sense to me...

Fred

m26k9 wrote:
> 
> My confusion is here:
>> ***What I was suggesting as a "data point", was to shift the center 
>> frequency down to just >B/2 instead of to zero (where B is the bandwidth 
>> of the bandpass signal).  Then the component at f=0 would be zero (or 
>> close enough) and the spectrum would continue to be even about zero and 
>> the temporal sequence would continue to be real.
> 
> Now when I have my (I)DFT output points, how would I "shift" them so that
> the lowest frequency is just above f=0? Do I multiply by e^(jf)? And isn't
> this "shifting" same as doing the DFT summation from 0 to (N-1), instead of
> (-N/2) to (N/2)? Because in both case I start with complex sequences and
> end up with complex sequences.
> Am I doing this all wrong? 
> 

I may have been confused by the use of the term "baseband" as I 
associated that term with "analytic signal" - which is derived by 
"demodulating" a bandpass signal down to zero center frequency - 
generally resulting in a complex temporal baseband signal which does not 
have frequency symmetry about f=0.

So, my suggestion was to envision what happens when the demodulation is 
such that the lowest frequency components are at a bit higher frequency 
and the resulting temporal "baseband" signal would be purely real and 
the frequency components would be symmetric about f=0 (and maybe 
antisymmetric as well).

The "demodulation" or mixing isn't part of the IDFT - although there may 
be tricks to accomplish this in some combined way.
If one has a bandpass signal with center frequency f0 and bandwidth B, 
then it can be downconverted.  I'm referring here to something like what 
Lyons (2nd ed.) shows in 8.9 Figure 8-24 where, I believe, the result 
has to still be real in time and the important spectral content has 
considerably reduced bandwidth.

But, overall, I think maybe the key here is the "mirroring" before the 
IDFT in DMT in order to keep the temporal samples purely real.  See my 
earlier post.

Fred

>First, what I want to do is to design a simple pre-equalizer for a DMT
>system. I have the frequency transfer function (magnitude) of the channel
>and want to design a pre-equalizer for that.
>
>The main point I want to confirm is:
>
>Does a FIR filter with linear-phase has all-real coefficients?
>
>I know that linear-phase requires that filter coefficients to be
symmetric,
>but does it also need to have real coefficients? Could they be complex
and
>symmetric-conjugate?

a complex filter can have linear phase or nonlinear phase and across
pos/neg frequency range(asymmetric).
>
>Also,
>
>For designing a filter with a frequency response of choice, is "frequency
>sampling method" the best option?
>
>I want to design a simple filter with only very few taps. If somebody
could
>recommend me some text that would also be great.

If you just want a pre-equaliser for amplitude only then there are several
methods:

%examples for fir design for a given amplitude(e.g. inverse sinc)
%method 1: ifft (freq sampling)
n = 31;                  %taps
f =linspace(-.5,.5,n);   %freq grid
A = 1./sinc(f);
h = fftshift(ifft(fftshift(A)));
h = h/sum(h);


%Matlab fir2 is based on ifft. while firpm/cfirpm are iterative...

My favorite method is this:
%inverse sinc design using LMS method
n = 31;                    %number of taps

f =linspace(-.45,.45,n)';
A = 1./sinc(f);

F = exp(-j*2*pi*f*[-(n-1)/2:(n-1)/2]);   
h = pinv(F)*A;       % pseudo inverse

If your signal is complex pair then you need a complex filter to
pre-correct amplitude of final channel signal. You can also include phase
correction by having vector of Amp/phase or I/Q channel data e.g. from
spectrum analyser. When correcting phase make sure you don't correct time
delay as it is unneccessary burden on filter(subtract time delay or use
groupdelay)

The above methods yield real and imaginary h.