Lyons needs help with a homework problem

Greetings Earthlings,

   Recently I've been thinking about the phase 
response of tapped-delay line FIR filters whose 
coefficients are complex-valued.  What I know for 
sure is that the well-known rule for real-valued 
linear-phase FIR filters (i.e., symmetrical or 
anti-symmetrical coefficients) does *NOT* apply 
to complex-valued FIR filters.

So I was trying to learn what is the "restriction" 
on complex-valued FIR filter coefficients that ensues 
phase linearity.  Because I'm unwilling to pay the 
exorbitant cost to access to IEEE papers, 
I discovered there is shockingly little information 
on the Internet regarding the phase of complex-valued 
FIR filters.  However, I did find that subject 
briefly mentioned on page 37 in Chapter 2 of 
Vaidyanathan's "Multirate Systems and Filter 
Banks" textbook.

Vaidyanathan claims that an N-tap complex-valued FIR 
filter will have linear phase if its h(k) coefficients 
satisfy:

   h(k) = ch*(N-1-k),  for all k       (1)

where k = 0,1,2,..., N-1.  The variable 'c' is a complex 
number whose magnitude is equal to one, and the '*' 
symbol means conjugation.  I was very thankful that 
Vaidyanathan supplied Eq. (1) but he gave no proof of 
its validity.  In fact, he left the proof of Eq. (1) 
as his Homework Problem 2.12.

I spent a fair amount of time producing my solution to 
Problem 2.12 but, Good Hell, my solution is long and 
rather complicated.  My solution is too complicated, 
I believe, to expect from a college DSP student.  
(I reviewed Vaidyanathan's Chapter 2 material to what 
information he provided that would enable a student 
to solve Problem 2.12, but I found nothing helpful.) 
I'm now thinking that there MUST be a solution to 
Problem 2.12 that's algebraically-simpler than my solution.

So here's my question guys, Have any of you, by any 
chance, generated a solution to Vaidyanathan's 
Problem 2.12?  If so, I'd be tickled to read a general 
description of how you solved that homework problem.

Thanks a lot guys,
[-Rick-]
PS.  And yes, I modeled my solution to Problem 2.12 using 
software (Matlab).  Under the risky assumption that my 
code is correct, my Problem 2.12 solution appears to 
be valid (that is, a correct solution).

On 8/2/2014 11:09 PM, Rick Lyons wrote:
>
> Greetings Earthlings,
>
>     Recently I've been thinking about the phase
> response of tapped-delay line FIR filters whose
> coefficients are complex-valued.  What I know for
> sure is that the well-known rule for real-valued
> linear-phase FIR filters (i.e., symmetrical or
> anti-symmetrical coefficients) does *NOT* apply
> to complex-valued FIR filters.
>
> So I was trying to learn what is the "restriction"
> on complex-valued FIR filter coefficients that ensues
> phase linearity.  Because I'm unwilling to pay the
> exorbitant cost to access to IEEE papers,
> I discovered there is shockingly little information
> on the Internet regarding the phase of complex-valued
> FIR filters.  However, I did find that subject
> briefly mentioned on page 37 in Chapter 2 of
> Vaidyanathan's "Multirate Systems and Filter
> Banks" textbook.
>
> Vaidyanathan claims that an N-tap complex-valued FIR
> filter will have linear phase if its h(k) coefficients
> satisfy:
>
>     h(k) = ch*(N-1-k),  for all k       (1)
>
> where k = 0,1,2,..., N-1.  The variable 'c' is a complex
> number whose magnitude is equal to one, and the '*'
> symbol means conjugation.  I was very thankful that
> Vaidyanathan supplied Eq. (1) but he gave no proof of
> its validity.  In fact, he left the proof of Eq. (1)
> as his Homework Problem 2.12.
>
> I spent a fair amount of time producing my solution to
> Problem 2.12 but, Good Hell, my solution is long and
> rather complicated.  My solution is too complicated,
> I believe, to expect from a college DSP student.
> (I reviewed Vaidyanathan's Chapter 2 material to what
> information he provided that would enable a student
> to solve Problem 2.12, but I found nothing helpful.)
> I'm now thinking that there MUST be a solution to
> Problem 2.12 that's algebraically-simpler than my solution.
>
> So here's my question guys, Have any of you, by any
> chance, generated a solution to Vaidyanathan's
> Problem 2.12?  If so, I'd be tickled to read a general
> description of how you solved that homework problem.
>
> Thanks a lot guys,
> [-Rick-]
> PS.  And yes, I modeled my solution to Problem 2.12 using
> software (Matlab).  Under the risky assumption that my
> code is correct, my Problem 2.12 solution appears to
> be valid (that is, a correct solution).

Obviously I am just kidding... I just couldn't resist the opportunity to 
channel Valdimir.

-- 

Rick

Hi Rick,

I think I can solve it as follows. Don't know if it's exactly simple, needs
about half a page.

I look at pairs of taps at delay n0-d and n0+d, respectively.
The frequency responses of the taps are
Ha(omega) = |a| exp(i phi_a) exp(i omega n0 t) exp(- i omega d t)
Hb(omega) = |b| exp(i phi_b) exp(i omega n0 t) exp( i omega d t)

and they sum up to a combined frequency response
Hc(omega) =|c(omega)| exp(i phi_c) exp(i omega n0 t)

Now I demand that the combination of taps is equivalent to a single tap at
the midpoint n0:
Ha(omega) + Hb(omega) = Hc(omega)

The frequency dependent magnitude |c(omega) accounts for the different
magnitude response of the two-tap combination from a single tap at n0. I
only demand that the phase is equal.

Divide both sides by Hc(omega). Now the right-hand side is a real-valued
"1". 
On the left-hand side, the imaginary part must disappear. First, |a| and
|b| must be equal. Then, I look at the imaginary part of the exp() terms,
gives two sin() functions that must add to zero. 
It follows that phi_a = -phi_b, offset by the constant phase shift phi_c.

By superposition, this applies for every pair of taps in the filter.
	 

_____________________________		
Posted through www.DSPRelated.com

>> n0-d and n0+d
with t as sampling time the delay is (n0-d)t and (n0+d)t
	 

_____________________________		
Posted through www.DSPRelated.com

On Sat, 02 Aug 2014 20:09:37 -0700, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:

>So here's my question guys, Have any of you, by any 
>chance, generated a solution to Vaidyanathan's 
>Problem 2.12?  If so, I'd be tickled to read a general 
>description of how you solved that homework problem.

Consider that a set of complex coefficients is the superposition of a set of
real coefficients and a set of imaginary coefficients. We already know what is
necessary and sufficient for linear phase with real coefficients, so let us
ignore that part of the solution and concentrate entirely upon imaginary
coefficients.

That said, let us *start* with a set of *real* coefficients h[n], 0 <= n <= N.
Following Mitra's procedure
(http://sip.cua.edu/res/docs/courses/ee515/chapter04/ch4-4.pdf):
 assume that h[N] = h[0], n[N-1] = h[1], etc.:

h[n] = h[0] + h[1]Z^-1 + ... + h[N-1]Z^-(N-1) + h[N]Z^-(N) {eq 1}

     = h[0] + h[1]Z^-1 + ... + h[1]Z^-(N-1) + h[0]Z^-(N)   {eq 2}

     = h[0][1 + Z^-N] + h[1][Z^-1 + Z^-(N-1)] + ...        {eq 3}

     = Z^-(N/2){h[0][Z^(N\2) + Z^-(N\2)] 
              + h(1)[Z^((N\2)-1) + Z^(-(N\2)+1)] + ...}    {eq 4}

Compute the frequency response:

H(e^(jw)) = e^(-j(N\2)w){h[0][cos(wN\2)+jsin(wN\2)+cos(wN\2)-jsin(wN\2)]+...}

          = e^(-j(N\2)w){h[0][2cos(wN\2)+...}

where "e^(-j(N\2)w)" represents the constant delay term and the terms in
brackets (most not shown, for brevity) represent the real magnitude.

Now, in {eq 1}, multiply h[0] through h[N\2-1] by +j, and h[N\2+1] through h[n]
by -j, to create a set of conjugate-symmetric imaginary coefficients:

h[n] = jh[0] + jh[1]Z^-1 + ... - jh[N-1]Z^-(N-1) - jh[N]Z^-(N) {eq 1j}

     = h[0][j - jZ^-N] + h[1][jZ^-1 - jZ^-(N-1)] + ...         {eq 3j}

     = Z^-(N/2){h[0][jZ^(N\2) - jZ^-(N\2)] 
              + h(1)[jZ^((N\2)-1) - jZ^(-(N\2)+1)] + ...}      {eq 4j}

Compute the frequency response:

H(e^(jw)) =
e^(-j(N\2)w){h[0][j(cos(wN\2)+jsin(wN\2))-j(cos(wN\2)-jsin(wN\2))]+...}

          = e^(-j(N\2)w){h[0][jcos(wN\2)-sin(wN\2))-jcos(wN\2)-sin(wN\2))]+...}

          = e^(-j(N\2)w){h[0][-2sin(wN\2)]+...}

where "e^(-j(N\2)w)" represents the constant delay term and the terms in
brackets represent the real magnitude.

This proves sufficiency, but not necessity.

Greg

On Sunday, August 3, 2014 5:13:34 PM UTC+12, rickman wrote:
> On 8/2/2014 11:09 PM, Rick Lyons wrote:
> 
> >
> 
> > Greetings Earthlings,
> 
> >
> 
> >     Recently I've been thinking about the phase
> 
> > response of tapped-delay line FIR filters whose
> 
> > coefficients are complex-valued.  What I know for
> 
> > sure is that the well-known rule for real-valued
> 
> > linear-phase FIR filters (i.e., symmetrical or
> 
> > anti-symmetrical coefficients) does *NOT* apply
> 
> > to complex-valued FIR filters.
> 
> >
> 
> > So I was trying to learn what is the "restriction"
> 
> > on complex-valued FIR filter coefficients that ensues
> 
> > phase linearity.  Because I'm unwilling to pay the
> 
> > exorbitant cost to access to IEEE papers,
> 
> > I discovered there is shockingly little information
> 
> > on the Internet regarding the phase of complex-valued
> 
> > FIR filters.  However, I did find that subject
> 
> > briefly mentioned on page 37 in Chapter 2 of
> 
> > Vaidyanathan's "Multirate Systems and Filter
> 
> > Banks" textbook.
> 
> >
> 
> > Vaidyanathan claims that an N-tap complex-valued FIR
> 
> > filter will have linear phase if its h(k) coefficients
> 
> > satisfy:
> 
> >
> 
> >     h(k) = ch*(N-1-k),  for all k       (1)
> 
> >
> 
> > where k = 0,1,2,..., N-1.  The variable 'c' is a complex
> 
> > number whose magnitude is equal to one, and the '*'
> 
> > symbol means conjugation.  I was very thankful that
> 
> > Vaidyanathan supplied Eq. (1) but he gave no proof of
> 
> > its validity.  In fact, he left the proof of Eq. (1)
> 
> > as his Homework Problem 2.12.
> 
> >
> 
> > I spent a fair amount of time producing my solution to
> 
> > Problem 2.12 but, Good Hell, my solution is long and
> 
> > rather complicated.  My solution is too complicated,
> 
> > I believe, to expect from a college DSP student.
> 
> > (I reviewed Vaidyanathan's Chapter 2 material to what
> 
> > information he provided that would enable a student
> 
> > to solve Problem 2.12, but I found nothing helpful.)
> 
> > I'm now thinking that there MUST be a solution to
> 
> > Problem 2.12 that's algebraically-simpler than my solution.
> 
> >
> 
> > So here's my question guys, Have any of you, by any
> 
> > chance, generated a solution to Vaidyanathan's
> 
> > Problem 2.12?  If so, I'd be tickled to read a general
> 
> > description of how you solved that homework problem.
> 
> >
> 
> > Thanks a lot guys,
> 
> > [-Rick-]
> 
> > PS.  And yes, I modeled my solution to Problem 2.12 using
> 
> > software (Matlab).  Under the risky assumption that my
> 
> > code is correct, my Problem 2.12 solution appears to
> 
> > be valid (that is, a correct solution).
> 
> 
> 
> Obviously I am just kidding... I just couldn't resist the opportunity to 
> 
> channel Valdimir.
> 
> 
> 
> -- 
> 
> 
> 
> Rick

Is he dead? Is there a God?

On Sun, 03 Aug 2014 01:50:49 -0500, mnentwig wrote:

> Hi Rick,
> 
> I think I can solve it as follows. Don't know if it's exactly simple,
> needs about half a page.
> 
> I look at pairs of taps at delay n0-d and n0+d, respectively.
> The frequency responses of the taps are Ha(omega) = |a| exp(i phi_a)
> exp(i omega n0 t) exp(- i omega d t) Hb(omega) = |b| exp(i phi_b) exp(i
> omega n0 t) exp( i omega d t)
> 
> and they sum up to a combined frequency response Hc(omega) =|c(omega)|
> exp(i phi_c) exp(i omega n0 t)
> 
> Now I demand that the combination of taps is equivalent to a single tap
> at the midpoint n0:
> Ha(omega) + Hb(omega) = Hc(omega)
> 
> The frequency dependent magnitude |c(omega) accounts for the different
> magnitude response of the two-tap combination from a single tap at n0. I
> only demand that the phase is equal.
> 
> Divide both sides by Hc(omega). Now the right-hand side is a real-valued
> "1".
> On the left-hand side, the imaginary part must disappear. First, |a| and
> |b| must be equal. Then, I look at the imaginary part of the exp()
> terms, gives two sin() functions that must add to zero.
> It follows that phi_a = -phi_b, offset by the constant phase shift
> phi_c.
> 
> By superposition, this applies for every pair of taps in the filter.

In other words, ignoring your phi_c, the taps must have conjugate 
symmetry* around the filter center tap point.

* Assuming that conjugate symmetry means what I think it means, given 
that I just made up the term.

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

On Sun, 03 Aug 2014 08:31:46 -0500, Greg Berchin
<gjberchin@chatter.net.invalid> wrote:

>On Sat, 02 Aug 2014 20:09:37 -0700, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:
>
>>So here's my question guys, Have any of you, by any 
>>chance, generated a solution to Vaidyanathan's 
>>Problem 2.12?  If so, I'd be tickled to read a general 
>>description of how you solved that homework problem.
>
>Consider that a set of complex coefficients is the superposition of a set of
>real coefficients and a set of imaginary coefficients. We already know what is
>necessary and sufficient for linear phase with real coefficients, so let us
>ignore that part of the solution and concentrate entirely upon imaginary
>coefficients.
>
>That said, let us *start* with a set of *real* coefficients h[n], 0 <= n <= N.
>Following Mitra's procedure
>(http://sip.cua.edu/res/docs/courses/ee515/chapter04/ch4-4.pdf):
> assume that h[N] = h[0], n[N-1] = h[1], etc.:
>
>h[n] = h[0] + h[1]Z^-1 + ... + h[N-1]Z^-(N-1) + h[N]Z^-(N) {eq 1}
>
>     = h[0] + h[1]Z^-1 + ... + h[1]Z^-(N-1) + h[0]Z^-(N)   {eq 2}
>
>     = h[0][1 + Z^-N] + h[1][Z^-1 + Z^-(N-1)] + ...        {eq 3}
>
>     = Z^-(N/2){h[0][Z^(N\2) + Z^-(N\2)] 
>              + h(1)[Z^((N\2)-1) + Z^(-(N\2)+1)] + ...}    {eq 4}
>
>Compute the frequency response:
>
>H(e^(jw)) = e^(-j(N\2)w){h[0][cos(wN\2)+jsin(wN\2)+cos(wN\2)-jsin(wN\2)]+...}
>
>          = e^(-j(N\2)w){h[0][2cos(wN\2)+...}
>
>where "e^(-j(N\2)w)" represents the constant delay term and the terms in
>brackets (most not shown, for brevity) represent the real magnitude.
>
>Now, in {eq 1}, multiply h[0] through h[N\2-1] by +j, and h[N\2+1] through h[n]
>by -j, to create a set of conjugate-symmetric imaginary coefficients:
>
>h[n] = jh[0] + jh[1]Z^-1 + ... - jh[N-1]Z^-(N-1) - jh[N]Z^-(N) {eq 1j}
>
>     = h[0][j - jZ^-N] + h[1][jZ^-1 - jZ^-(N-1)] + ...         {eq 3j}
>
>     = Z^-(N/2){h[0][jZ^(N\2) - jZ^-(N\2)] 
>              + h(1)[jZ^((N\2)-1) - jZ^(-(N\2)+1)] + ...}      {eq 4j}
>
>Compute the frequency response:
>
>H(e^(jw)) =
>e^(-j(N\2)w){h[0][j(cos(wN\2)+jsin(wN\2))-j(cos(wN\2)-jsin(wN\2))]+...}
>
>          = e^(-j(N\2)w){h[0][jcos(wN\2)-sin(wN\2))-jcos(wN\2)-sin(wN\2))]+...}
>
>          = e^(-j(N\2)w){h[0][-2sin(wN\2)]+...}
>
>where "e^(-j(N\2)w)" represents the constant delay term and the terms in
>brackets represent the real magnitude.
>
>This proves sufficiency, but not necessity.
>
>Greg

Hi Greg,
   Thanks for going to all the trouble to explain 
your thoughts in detail.  I appreciate it.

I'll carefully review your equations later today.

My derivation is based on a generic 5-tap filter 
whose h(k) coefficients are:

     h(0) = r(0)e^jq(0)    
     h(1) = r(1)e^jq(1)    
     h(2) = r(2)e^jq(2)   
     h(3) = ch*(1) = cr(1)e^-jq(1)    
     h(4) = ch*(0) = cr(0)e^-jq(0)       

where c = e^jp.  'q' and 'p' are phase angles, and 
r(k) is a real-valued scalar.

And my derivation proceeds something like:

* Write the z-domain transfer function of the 
   h(k) coefficients.
* Replace 'z' with 'e^jw'.
* Factor out an 'e^jwN/2' term.  (That gives me 
   a phase-shift factor similar to what you did.)
* Use a "half-angle" exponential identity to 
   accommodate the complex 'c' factor in the 
   last two h(k) coefficients.   
* Combine conjugate exponential terms to convert 
   the exponentials to cosine terms.

Anyway Greg, my result looks quite similar in 
format to yours.  I won't worry about any differences 
between your result and mine because, thankfully, 
I think you've answered a main question I had.  
And that question was, "Is there a simple solution 
to Problem 2.12 that I'm failing to recognize?"

You've reinforced my notion that "No. There's no 
simple solution to Problem 2.12."  And I wonder if 
there are any undergraduate EE students that could 
go through all the algebraic acrobatics needed to 
solve that problem.

Ya' know what's interesting Greg?  I see that the two 
most popular college DSP textbooks (Opp & Schafer 
and Proakis & Manolakis) do NOT present an algebraic 
proof that symmetrical real-valued FIR filters 
exhibit linear phase.  That surprised me.  I'm not 
bad-mouthing those good professors because I also 
failed to supply such a proof in my DSP book.  Shame 
on me.

I've also learned that two common ways to compute 
the coefficients of complex FIR filters *always* 
produce coefficients that satisfy Vaidyanathan's 
Eq. (1) in my original post.  And right now I don't 
know why that happens!  I have much more to learn.

Thanks again Greg!!

[-Rick-]

On Sun, 03 Aug 2014 01:50:49 -0500, "mnentwig" <24789@dsprelated>
wrote:

>Hi Rick,
>
>I think I can solve it as follows. Don't know if it's exactly simple, needs
>about half a page.
>
>I look at pairs of taps at delay n0-d and n0+d, respectively.
>The frequency responses of the taps are
>Ha(omega) = |a| exp(i phi_a) exp(i omega n0 t) exp(- i omega d t)
>Hb(omega) = |b| exp(i phi_b) exp(i omega n0 t) exp( i omega d t)
>
>and they sum up to a combined frequency response
>Hc(omega) =|c(omega)| exp(i phi_c) exp(i omega n0 t)
>
>Now I demand that the combination of taps is equivalent to a single tap at
>the midpoint n0:
>Ha(omega) + Hb(omega) = Hc(omega)
>
>The frequency dependent magnitude |c(omega) accounts for the different
>magnitude response of the two-tap combination from a single tap at n0. I
>only demand that the phase is equal.
>
>Divide both sides by Hc(omega). Now the right-hand side is a real-valued
>"1". 
>On the left-hand side, the imaginary part must disappear. First, |a| and
>|b| must be equal. Then, I look at the imaginary part of the exp() terms,
>gives two sin() functions that must add to zero. 
>It follows that phi_a = -phi_b, offset by the constant phase shift phi_c.
>
>By superposition, this applies for every pair of taps in the filter.

Hi Markus,
   Thanks for going to all the trouble to explain 
your solution to me.  I appreciate it.

I'll carefully review your approach later today.

Markus, like Greg Berchin, you're reinforcing my 
idea that "No. There's no simple solution to Problem 
2.12."  And I wonder if it's reasonable to expect 
undergraduate EE students to solve that problem.

Thanks again Markus!!
[-Rick-]

On Sun, 03 Aug 2014 01:13:34 -0400, rickman <gnuarm@gmail.com> wrote:

   [Snipped by Lyons]
>
>Obviously I am just kidding... I just couldn't resist the opportunity to 
>channel Valdimir.

Ha ha Rick.  Cute.

Actually, I was afraid that I was being a Stupident 
and that I somehow missed an easy solution to 
"my" homework problem.  It appears that is not so.

[-Rick-]