Does anyone know how to find the precise minimum phase discrete-time impulse
response corresponding to a given magnitude spectrum, when the magnitude
spectrum does *not* correspond to rational polynomial transfer function?

Matt:

[snip]
"Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> wrote in message
news:edZnb.2748$Nz5.331406@news20.bellglobal.com...
> Does anyone know how to find the precise minimum phase discrete-time
impulse
> response corresponding to a given magnitude spectrum, when the magnitude
> spectrum does *not* correspond to rational polynomial transfer function?
[snip]

The magnitude and phase of a minimum phase function are related by the
Hilbert Transform Integrals
[if they exist].  Depending upon your function you may be able to compute
this using numerical quadrature.

--
Peter
Consultant
Indialantic By-the-Sea, FL
[peter dot brackett at ieee dot org]

"Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> wrote in message
news:edZnb.2748$Nz5.331406@news20.bellglobal.com...
> Does anyone know how to find the precise minimum phase discrete-time
impulse
> response corresponding to a given magnitude spectrum, when the magnitude
> spectrum does *not* correspond to rational polynomial transfer function?

Matt,

Hmmmmm.... working backwards and using a counter-example:
Starting with the magnitude spectrum
Calculate the magnitude spectrum squared
Now, assuming that there *was* a rational polynomial transfer function, then
the magnitude spectrum squared will have zeros that are arrayed in conjugate
pairs around the unit circle in the z-plane, and will have poles that are
arrayed in duals inside the unit circle, right?
Then, one of the square roots of this rational function will have
approximately 2x fewer poles and 2x fewer zeros.  The zeros will all lie
inside the unit circle for the minimum phase version.
Well, I'm not so sure about the poles but this is certainly correct for the
zeros.

So far, so good .....

Now, if the magnitude spectrum doesn't have a corresponding family of
rational functions that it would result from, then what the heck kind of
"system" does the impulse response you're looking for represent?
In general, it's not a system that can be defined with a set of ordinary,
linear, difference equations with constant coefficients (OLDEWCC) I do
believe.  Otherwise, the difference equations would result in a rational
transfer function wouldn't it?

So, what part of OLDEWCC isn't met?
Ordinary difference equations -> partial difference equations
Linear difference equations -> nonlinear difference equations
Constant coefficients -> time-varying coefficients

If the coefficients aren't constant, then there is no single impulse
response - there's an infinity of them.

If the equations aren't linear then there is no single impulse response in
the normal sense - because the response doesn't scale with the size of the
"unit sample" amplitude input.  The response varies.

If the difference equations are partial difference equations then the notion
of an impulse response doesn't apply because the equations represent a field
and not a single-input, single-output system.  In that case you might look
at the value of each state variable in response to a particular unit sample
"input" somewhere in the field and you will get "impulse responses" for each
of the variables.

So .... are you *sure* that a rational function doesn't describe your
system?

That much said: perhaps you have a measured magnitude spectrum that doesn't
lend itself to the nice mathematics?  In that case you may want to develop
an approximation that's adequate.  To do that, Google on "system
identification" and "deconvolution" .... that sort of thing.  Once you have
a system defined you will have an impulse response.

Now I'm really curious.  Did I cover all the bases or is there such a thing
as described and I missed how that could be?  Where did the magnitude
spectrum come from??

Fred

Thanks, Fred.

comments interleaved below

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
news:T_mdnbL_NpwQtjyiRVn-sg@centurytel.net...
> Now, if the magnitude spectrum doesn't have a corresponding family of
> rational functions that it would result from, then what the heck kind of
> "system" does the impulse response you're looking for represent?

Ah well, that's just it -- I don't know.  What I'm trying to do is make a
special type of low-stop filter.  I want to set a constraint that no more
than x% of the signal power can be in the stop band, and then find the
filter that:

a) satisfies this condition; and

b) packs as much energy as possible into the initial samples.

From (b), I can immediately tell that the best filter will be the minimum
phase filter for its magnitude response, but the constraint leaves a *lot*
of freedom in the magnitude response.

There is no reason to assume that the best filter will have a rational
polynomial transfer function.  Perhaps the best frequency response is
derived from the Gaussian, or perhaps the transfer function will have zeros
bigger than points, like a sinc.

> That much said: perhaps you have a measured magnitude spectrum that
doesn't
> lend itself to the nice mathematics?  In that case you may want to develop
> an approximation that's adequate.  To do that, Google on "system
> identification" and "deconvolution" .... that sort of thing.  Once you
have
> a system defined you will have an impulse response.

Unfortunately, I don't know how to determine when an approximation is
adequate.  I can generate any number of minimum phase filters that satisfy
the constraint on the frequency response, but I don't know how to determine
how close they come to the best filter as defined above.

If I knew how to make the minimum phase impulse response for an arbitrary
frequency response, then I could probably find a way to choose the best
filter from the set that satisfies the constraint.  I'm trying to find out
more about the "real" definition of, instead of the one about poles and
zeros.

Perhaps you can help with another question, from which I can derive an
answer to the original one:

Given the entire complex frequency response for a discrete-time signal, how
can you tell whether or not the signal is causal?

Again, I have no rational polynomials.

Matt,

Comments interspersed below:

"Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> wrote in message
news:P9kob.4987$Nz5.422060@news20.bellglobal.com...
> Thanks, Fred.
>
> comments interleaved below
>
> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
> news:T_mdnbL_NpwQtjyiRVn-sg@centurytel.net...
> > Now, if the magnitude spectrum doesn't have a corresponding family of
> > rational functions that it would result from, then what the heck kind of
> > "system" does the impulse response you're looking for represent?
>
> Ah well, that's just it -- I don't know.  What I'm trying to do is make a
> special type of low-stop filter.  I want to set a constraint that no more
> than x% of the signal power can be in the stop band, and then find the
> filter that:

Please define "low-stop" for me.  Do you mean time domain lowpass lifter.
(lifter means filter but in the time domain)
>
> a) satisfies this condition; and
>
> b) packs as much energy as possible into the initial samples.\\

Well, it appears you want a lowpass filter that is also a lowpass lifter,
right?
I think you will find that an approximation to a Gaussian shape has this
character - being minimum width in both time and frequency at the same time.
Now all you have to do is define a FIR filter that approximates the Gaussian
shape - an the frequency response should do the same.

>
> From (b), I can immediately tell that the best filter will be the minimum
> phase filter for its magnitude response, but the constraint leaves a *lot*
> of freedom in the magnitude response.

I don't know about this one way or another....it seems possible but not a
rigorous statement.

>
> There is no reason to assume that the best filter will have a rational
> polynomial transfer function.  Perhaps the best frequency response is
> derived from the Gaussian, or perhaps the transfer function will have
zeros
> bigger than points, like a sinc.

What do you mean by "zeros bigger than points"?
Yes, there is reason to assume that the best filter will have a rational
transfer function because of all those conditions I enumerated before.  A
filter is a system and is described by ordinary linear difference equations
with constant coefficients.
Now, if you are assuming something else, then perhaps not.  For example, we
can define Fourier transform pairs that don't have anything to do with
"systems".  But, in the end, we are usually interested in systems - and
perhaps systems that approximate ideal Fourier transform pairs.
>
> > That much said: perhaps you have a measured magnitude spectrum that
> doesn't
> > lend itself to the nice mathematics?  In that case you may want to
develop
> > an approximation that's adequate.  To do that, Google on "system
> > identification" and "deconvolution" .... that sort of thing.  Once you
> have
> > a system defined you will have an impulse response.
>
> Unfortunately, I don't know how to determine when an approximation is
> adequate.  I can generate any number of minimum phase filters that satisfy
> the constraint on the frequency response, but I don't know how to
determine
> how close they come to the best filter as defined above.

I don't know why the term "minimum phase" keeps coming up so readily here.
Do you perhaps mean something like "minimum delay" or "maximum integral of
the magnitude squared over a minimum span"?
My recommendation would be to drop the use of that term because it has very
specific meaning or usage - rather than a more general meaning.  Later, when
we agree that we're dealing with system functions and not just abstract
transform pairs, we can talk about minimum phase.

>
> If I knew how to make the minimum phase impulse response for an arbitrary
> frequency response, then I could probably find a way to choose the best
> filter from the set that satisfies the constraint.  I'm trying to find out
> more about the "real" definition of, instead of the one about poles and
> zeros.

Poles and zeros are very "real" in ordinary linear difference equations with
constant coefficients (i.e. "systems")

>
> Perhaps you can help with another question, from which I can derive an
> answer to the original one:
>
> Given the entire complex frequency response for a discrete-time signal,
how
> can you tell whether or not the signal is causal?
>
> Again, I have no rational polynomials.


Well, maybe you do and maybe you don't.  It depends on where you are in the
process of finding a solution to the problem you've posed.  I can understand
that there are optimum functions that aren't system functions but there are
no systems that aren't described by system functions.

First, strictly speaking, there is no such thing as a causal "signal" - only
a causal system response.
A system response is causal if the poles of the frequency response lie
inside the unit circle.
A system is described by an ordinary linear difference equation with
constant coefficients - so it does have a rational system function.
A minimum phase system has all the poles inside the unit circle and all the
zeros inside or on the unit circle.

Take a look at page 199 of Temes, Barcilon and Marshall "The Optimization of
Bandlimited Sytems" Proc IEEE Vol 61 No. 2 Feb 1973 pp 196-234.  Here,
Victor Barcilon discusses time spread and frequency spread, deltaT and
deltaOmega respectively, and shows that the Gaussian is optimum, that
deltaT*deltaOmega>=1/2, etc......  These are optimum functions and not
system functions.
Later in the paper we discuss the realization of system functions - well
things like FIR filters and window functions which are discrete and
continuous versions of the same thing.

Fred

Hi Fred,

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
news:Fr2dnUZI8ZJShD-iRVn-iA@centurytel.net...
> Please define "low-stop" for me.  Do you mean time domain lowpass lifter.
> (lifter means filter but in the time domain)

It means I just want to attenuate low frequencies, and don't care much about
the high frequencies -- I don't require any limits on passband ripple or
other passband errors.

> > From (b), I can immediately tell that the best filter will be the
minimum
> > phase filter for its magnitude response, but the constraint leaves a
*lot*
> > of freedom in the magnitude response.
>
> I don't know about this one way or another....it seems possible but not a
> rigorous statement.
> [...]
> I don't know why the term "minimum phase" keeps coming up so readily here.
> Do you perhaps mean something like "minimum delay" or "maximum integral of
> the magnitude squared over a minimum span"?

See the final paragraphs of this link.  The characteristic "maximum decay"
result for minimum phase filters is exactly what I'm looking for, and
defines the term without reference to poles or zeros.

http://ccrma-www.stanford.edu/~jos/filters/Definition_Minimum_Phase.html

> Now, if you are assuming something else, then perhaps not.  For example,
we
> can define Fourier transform pairs that don't have anything to do with
> "systems".  But, in the end, we are usually interested in systems - and
> perhaps systems that approximate ideal Fourier transform pairs.

Yes.  What I exepect to get at the end is a long FIR filter that truncates
or approximates an infinite response that wasn't generated by differential
equations.  I want to find the ideal so I can tell when the approximation is
good.

> First, strictly speaking, there is no such thing as a causal "signal" -
only
> a causal system response.

One-sided, if you prefer.

> A system response is causal if the poles of the frequency response lie
> inside the unit circle.

An signal is one-sided if it is zero at t<0

By causal freqency response, I mean exactly the Fourier transform of such a
signal.

Hmmm... Now that I put it that way, surely it can't be too hard to state the
necessary condition.

"Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> wrote in message news:<P9kob.4987$Nz5.422060@news20.bellglobal.com>...

> Again, I have no rational polynomials.

Actually, there may be a chance that you do. The Z transform of a FIR filter 
*is* a rational polynomial, though with only a numerator and no denominator.

Rune

Fred Marshall wrote:
   ...



> I think you will find that an approximation to a Gaussian shape has this
> character - being minimum width in both time and frequency at the same time.
> Now all you have to do is define a FIR filter that approximates the Gaussian
> shape - an the frequency response should do the same.

Going off half cocked -- that's "detente" in French -- I think that that
shape is binomial. I mean by that the binomial coefficients on x and y
in (x + y)^n and scaled by 1/2^n, For n = 5, that gives
                    1/32[1, 5, 10, 10, 5, 1]
and so on. I've used these filters before I knew that DSP was a branch
of learning. They can all be derived by repeating the average of two
adjacent values, which is the filter 1/2[1, 1]. Would anyone care to say
that a Pascal filter is the discrete form of an Gaussian? (A la Poisson
and Rayleigh.)

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

allnor@tele.ntnu.no (Rune Allnor) wrote in message news:<f56893ae.0310310733.7b32304f@posting.google.com>...
> "Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> wrote in message news:<P9kob.4987$Nz5.422060@news20.bellglobal.com>...
> 
> > Again, I have no rational polynomials.
> 
> Actually, there may be a chance that you do. The Z transform of a FIR filter 
> *is* a rational polynomial, though with only a numerator and no denominator.

I just couldn't let that go, so here's the results of my "sunday morning
mentals"...

We are concerned with a FIR filter with filter coefficients 

   h(n), n=-N/2,...,N/2                                             [1]

and z transform 

            k=N/2
   H(z) =   sum    h(k)z^(-k).                                      [2]
           k=-N/2

We know that a filters on the form 

   H(z) = +/-H(z^(-1))                                              [3]

have linear phase responses, and we know that filters that have 
all their roots inside the unit circle, 

            k=N/2
   H(z)  =  prod    (z-z_k)      |z_k| < 1 for all k                [4]
            k=-N/2

are "minimum phase". 

So the problem is stated as "given the magnitude spectrum of a FIR filter,
how do we find the filter coefficients that are minimum phase."

Since we start out with a magnitude spectrum, I prefer to express it in 
terms of a non-causal linear-phase FIR filter with zero phase lag at all 
frequencies. This is, by [3] a filter with symmetrical impulse response.

Next, I recall the well-known fact that symmetrical FIR filters have 
reciprocal roots, i.e.

  H(z)=G(z)G(z^-1)                                                  [5]

subject to 

  |H(z)| = |G(z)|^2                                               [6.a]
         = |G(z^-1)|^2                                            [6.b]
         = |G(z)G(z^-1)|                                          [6.c]

where G(z) represents the causal part of H(z) and G(z^-1) represents 
the anticausal part of H(z).

By construction, a naive IDFT of the specified magnitude spectrum would 
yield a filter impulse respone that zero-phase, though circular convolved,
representing |H(z)| by [6.c] above.  

So my very naive idea (concieved before 9 AM on a sunday morning, so no 
guarantees aboute any trace of coherence, or even sanity, apply!) is
to try to extract the causal part of the impulse response, and design 
a causal linear phase FIR filter according to [6.a] above. 

One way of doing this would be to formulate the magnitude spectrum H(z), 
inverse transform the spectrum to find the non-causal imulse tranform 
of the filter and then use the coefficients of the spectrum as 
coefficients of the filter difference equation and solve for the roots 
of that equation. Accepting only the roots z_m such that |z_m| < 1, 
we now should be able to find the coefficients of the "half filter"
G(z), which in turn could be cascaded by itself to find H(z). 

This could work if the number of coefficients in the FIR filter is 
"sufficiently small", whatever that may mean, as I think most of the 
work and most of the inaccuracy would be concerned with rooting the 
polynomial.

My 2 c.

Rune

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message
news:f56893ae.0311020443.7b0bf86b@posting.google.com...
> allnor@tele.ntnu.no (Rune Allnor) wrote in message
news:<f56893ae.0310310733.7b32304f@posting.google.com>...
> > "Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> wrote in message
news:<P9kob.4987$Nz5.422060@news20.bellglobal.com>...
> >
,,,,,,,,,,,,,,,,,,,,,,,,,,,,

> One way of doing this would be to formulate the magnitude spectrum H(z),
> inverse transform the spectrum to find the non-causal imulse tranform
> of the filter and then use the coefficients of the spectrum as
> coefficients of the filter difference equation and solve for the roots
> of that equation. Accepting only the roots z_m such that |z_m| < 1,
> we now should be able to find the coefficients of the "half filter"
> G(z), which in turn could be cascaded by itself to find H(z).
>
> This could work if the number of coefficients in the FIR filter is
> "sufficiently small", whatever that may mean, as I think most of the
> work and most of the inaccuracy would be concerned with rooting the
> polynomial.


Rune,

There are a multiplicity of filters with the same magnitude response -
depending on which zeros are inside and which zeros are outside the unit
circle.  Any pair of zeros with the same real part and imaginary parts of
opposite sign can be replaced by a pair of zeros (switching to polar
coordinates) with the same value for rho and with distance from the orgin of
1/L where L is the original distance.

To get minimum phase from the same magnitude response, all you have to do is
replace the zeros that are outside the unit circle with zeros (as above)
that are inside the unit circle ... that are conjugate to the ones being
replaced.

Fred

Fred Marshall wrote:

> "Rune Allnor" <allnor@tele.ntnu.no> wrote in message
> news:f56893ae.0311020443.7b0bf86b@posting.google.com...
> 
>>allnor@tele.ntnu.no (Rune Allnor) wrote in message
> 
> news:<f56893ae.0310310733.7b32304f@posting.google.com>...
> 
>>>"Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> wrote in message
> 
> news:<P9kob.4987$Nz5.422060@news20.bellglobal.com>...
> 
> ,,,,,,,,,,,,,,,,,,,,,,,,,,,,
> 
> 
>>One way of doing this would be to formulate the magnitude spectrum H(z),
>>inverse transform the spectrum to find the non-causal imulse tranform
>>of the filter and then use the coefficients of the spectrum as
>>coefficients of the filter difference equation and solve for the roots
>>of that equation. Accepting only the roots z_m such that |z_m| < 1,
>>we now should be able to find the coefficients of the "half filter"
>>G(z), which in turn could be cascaded by itself to find H(z).
>>
>>This could work if the number of coefficients in the FIR filter is
>>"sufficiently small", whatever that may mean, as I think most of the
>>work and most of the inaccuracy would be concerned with rooting the
>>polynomial.
> 
> 
> 
> Rune,
> 
> There are a multiplicity of filters with the same magnitude response -
> depending on which zeros are inside and which zeros are outside the unit
> circle.  Any pair of zeros with the same real part and imaginary parts of
> opposite sign can be replaced by a pair of zeros (switching to polar
> coordinates) with the same value for rho and with distance from the orgin of
> 1/L where L is the original distance.
> 
> To get minimum phase from the same magnitude response, all you have to do is
> replace the zeros that are outside the unit circle with zeros (as above)
> that are inside the unit circle ... that are conjugate to the ones being
> replaced.
> 
> Fred

As a practical matter, you can do pretty well by approximating the log
frequency response with piecewise linear segments whose slopes are
integer multiples of 20 dB/decade, then writing the up breaks as poles and
the down breaks as zeros. That's a graphical way to approximate the
Hilbert relation between frequency and minimum phase. It's encapsulated
in the Bode plot.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message news:<IdadneNuWJlF3ziiRVn-sg@centurytel.net>...
> "Rune Allnor" <allnor@tele.ntnu.no> wrote in message
> news:f56893ae.0311020443.7b0bf86b@posting.google.com...
> > allnor@tele.ntnu.no (Rune Allnor) wrote in message
>  news:<f56893ae.0310310733.7b32304f@posting.google.com>...
> > > "Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> wrote in message
>  news:<P9kob.4987$Nz5.422060@news20.bellglobal.com>...
> > >
> ,,,,,,,,,,,,,,,,,,,,,,,,,,,,
> 
> > One way of doing this would be to formulate the magnitude spectrum H(z),
> > inverse transform the spectrum to find the non-causal imulse tranform
> > of the filter and then use the coefficients of the spectrum as
> > coefficients of the filter difference equation and solve for the roots
> > of that equation. Accepting only the roots z_m such that |z_m| < 1,
> > we now should be able to find the coefficients of the "half filter"
> > G(z), which in turn could be cascaded by itself to find H(z).
> >
> > This could work if the number of coefficients in the FIR filter is
> > "sufficiently small", whatever that may mean, as I think most of the
> > work and most of the inaccuracy would be concerned with rooting the
> > polynomial.
> 
> 
> Rune,
> 
> There are a multiplicity of filters with the same magnitude response -
> depending on which zeros are inside and which zeros are outside the unit
> circle.  Any pair of zeros with the same real part and imaginary parts of
> opposite sign can be replaced by a pair of zeros (switching to polar
> coordinates) with the same value for rho and with distance from the orgin of
> 1/L where L is the original distance.
> 
> To get minimum phase from the same magnitude response, all you have to do is
> replace the zeros that are outside the unit circle with zeros (as above)
> that are inside the unit circle ... that are conjugate to the ones being
> replaced.

Eh... I'm not sure if I understand what you mean. Let's see... apparently 
we agree that half of the zeros ensure linear phase (by being the 
reciprocals of the zeros that "define" the filter response) while half 
of the zeros ensure that the filter is noncausal... by being the 
*conjugates* of the "defining" zeros. And these two halves are not the 
same. Is that what you are saying? 

In that case my approach go nowhere, because my filter would be munimum 
phase but noncausal. Right?

OK, the lesson learned is "Don't do DSP at 9 AM sunday morning"... ;)

Rune

Rune Allnor wrote:

  ...
> 
> 
> Eh... I'm not sure if I understand what you mean. Let's see... apparently 
> we agree that half of the zeros ensure linear phase (by being the 
> reciprocals of the zeros that "define" the filter response) while half 
> of the zeros ensure that the filter is noncausal... by being the 
> *conjugates* of the "defining" zeros. And these two halves are not the 
> same. Is that what you are saying? 
> 
> In that case my approach go nowhere, because my filter would be munimum 
> phase but noncausal. Right?
> 
> OK, the lesson learned is "Don't do DSP at 9 AM sunday morning"... ;)
> 
> Rune

I think he means to keep all the zeros, but to reflect the ones outside
the unit circle to the inside

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

"Jerry Avins" <jya@ieee.org> wrote in message
news:bo431e$sp8$1@bob.news.rcn.net...
> Rune Allnor wrote:
>
>   ...
> >
> >
> > Eh... I'm not sure if I understand what you mean. Let's see...
apparently
> > we agree that half of the zeros ensure linear phase (by being the
> > reciprocals of the zeros that "define" the filter response) while half
> > of the zeros ensure that the filter is noncausal... by being the
> > *conjugates* of the "defining" zeros. And these two halves are not the
> > same. Is that what you are saying?
> >
> > In that case my approach go nowhere, because my filter would be munimum
> > phase but noncausal. Right?
> >
> > OK, the lesson learned is "Don't do DSP at 9 AM sunday morning"... ;)
> >
> > Rune
>
> I think he means to keep all the zeros, but to reflect the ones outside
> the unit circle to the inside

Like he (Jerry) sez.

You need to keep them all or the magnitude response changes.
Any zero pair, as those I defined, contribute to the response.
If all the zeros are outside the unit circle, you get maximum phase.
If all the zeros are inside the unit circle, you get minimum phase.
If you have a mix, then something in between re: phase.

Fred

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message news:<BsSdnaJA6oskLziiRVn-sg@centurytel.net>...
> "Jerry Avins" <jya@ieee.org> wrote in message
> news:bo431e$sp8$1@bob.news.rcn.net...
> > Rune Allnor wrote:
> >
> >   ...
> > >
> > >
> > > Eh... I'm not sure if I understand what you mean. Let's see...
>  apparently
> > > we agree that half of the zeros ensure linear phase (by being the
> > > reciprocals of the zeros that "define" the filter response) while half
> > > of the zeros ensure that the filter is noncausal... by being the
> > > *conjugates* of the "defining" zeros. And these two halves are not the
> > > same. Is that what you are saying?
> > >
> > > In that case my approach go nowhere, because my filter would be munimum
> > > phase but noncausal. Right?
> > >
> > > OK, the lesson learned is "Don't do DSP at 9 AM sunday morning"... ;)
> > >
> > > Rune
> >
> > I think he means to keep all the zeros, but to reflect the ones outside
> > the unit circle to the inside
> 
> Like he (Jerry) sez.
> 
> You need to keep them all or the magnitude response changes.
> Any zero pair, as those I defined, contribute to the response.
> If all the zeros are outside the unit circle, you get maximum phase.
> If all the zeros are inside the unit circle, you get minimum phase.
> If you have a mix, then something in between re: phase.

So if I abandon that "noncausal argument", and instead design a causal 
linear phase FIR filter (which essentially amounts to delay the impulse 
response by a filter half-length) and find its roots, I end up with a 
total response as

    |H(z)| = |G(z)*G'(z)|

where G contains all the roots inside the unit circle and G' contains all 
the roots outside the unit circle. I interpret that as the total filter 
H(z) implemented as a cascade coupling of one minimum phase filter G(z) 
and a maximum phase filter G'(z). Do we agree that the same magnitude 
spectrum H(z) can be implemented as a cascade of two similar minimum 
phase filters, G(z) and G(z) such that

    |H(z)| = |G(z)*G(z)|

which appears to meet the specs, H(z)=G^2(z) is causal and also minimum 
phase?

If so, I think Matt's original problem in principle can be solved, though 
with the already stated practical caveat about finding roots of "large"
polynomials.

Rune

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message
news:f56893ae.0311030528.52ac968d@posting.google.com...
> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
news:<BsSdnaJA6oskLziiRVn-sg@centurytel.net>...
> > "Jerry Avins" <jya@ieee.org> wrote in message
> > news:bo431e$sp8$1@bob.news.rcn.net...
> > > Rune Allnor wrote:
> > >
> > >   ...
> > > >
> > > >
> > > > Eh... I'm not sure if I understand what you mean. Let's see...
> >  apparently
> > > > we agree that half of the zeros ensure linear phase (by being the
> > > > reciprocals of the zeros that "define" the filter response) while
half
> > > > of the zeros ensure that the filter is noncausal... by being the
> > > > *conjugates* of the "defining" zeros. And these two halves are not
the
> > > > same. Is that what you are saying?
> > > >
> > > > In that case my approach go nowhere, because my filter would be
munimum
> > > > phase but noncausal. Right?
> > > >
> > > > OK, the lesson learned is "Don't do DSP at 9 AM sunday morning"...
;)
> > > >
> > > > Rune
> > >
> > > I think he means to keep all the zeros, but to reflect the ones
outside
> > > the unit circle to the inside
> >
> > Like he (Jerry) sez.
> >
> > You need to keep them all or the magnitude response changes.
> > Any zero pair, as those I defined, contribute to the response.
> > If all the zeros are outside the unit circle, you get maximum phase.
> > If all the zeros are inside the unit circle, you get minimum phase.
> > If you have a mix, then something in between re: phase.
>
> So if I abandon that "noncausal argument", and instead design a causal
> linear phase FIR filter (which essentially amounts to delay the impulse
> response by a filter half-length) and find its roots, I end up with a
> total response as
>
>     |H(z)| = |G(z)*G'(z)|
>
> where G contains all the roots inside the unit circle and G' contains all
> the roots outside the unit circle. I interpret that as the total filter
> H(z) implemented as a cascade coupling of one minimum phase filter G(z)
> and a maximum phase filter G'(z). Do we agree that the same magnitude
> spectrum H(z) can be implemented as a cascade of two similar minimum
> phase filters, G(z) and G(z) such that
>
>     |H(z)| = |G(z)*G(z)|
>

Rune,

I'd start here just to be complete I guess:

 |H(z)| = |G(z)*F(z)|

where G contains all the roots inside the unit circle and F contains all
the roots outside the unit circle with radii Li.   (I don't yet want to say
that G and F are somehow related).
So, G is minimum phase and F is maximum phase.

Now, it is also correct, subject to the comment below about zeros *on* the
unit circle, that:

|H(z)| = |G(z)*F'(z)|

which is a cascade of two minimum phase filters and is also minimum phase.

where we have replaced F(z) with F'(z) which has polar locations for zeros
at radii 1/Li (inside the unit circle).

So far, so good.

Now, since F(z)=G'(z) and G(z)=F'(z) for a linear phase filter, then what
you say is *also* correct with one minor change.  If there are any zeros
*on* the unit circle, you need to include them in either G or F for this to
make sense.

Only if there are no zeros on the unit circle can you say:

|H(z)| = |G(z)*G(z)|  because now F'(z)=G(z)

Otherwise it's going to be
|H(z)| = |G(z)*F'(z)|  because F'(z) <> G(z) .... one of them has the unit
circle zeros included in it.

Oppenheim & Schafer deal with all this pretty well.

Fred

allnor@tele.ntnu.no (Rune Allnor) wrote in message news:<f56893ae.0311030528.52ac968d@posting.google.com>...
> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message news:<BsSdnaJA6oskLziiRVn-sg@centurytel.net>...
> > "Jerry Avins" <jya@ieee.org> wrote in message
> > news:bo431e$sp8$1@bob.news.rcn.net...
> > > Rune Allnor wrote:
> > >
> > >   ...
> > > >
> > > >
> > > > Eh... I'm not sure if I understand what you mean. Let's see...
>  apparently
> > > > we agree that half of the zeros ensure linear phase (by being the
> > > > reciprocals of the zeros that "define" the filter response) while half
> > > > of the zeros ensure that the filter is noncausal... by being the
> > > > *conjugates* of the "defining" zeros. And these two halves are not the
> > > > same. Is that what you are saying?
> > > >
> > > > In that case my approach go nowhere, because my filter would be munimum
> > > > phase but noncausal. Right?
> > > >
> > > > OK, the lesson learned is "Don't do DSP at 9 AM sunday morning"... ;)
> > > >
> > > > Rune
> > >
> > > I think he means to keep all the zeros, but to reflect the ones outside
> > > the unit circle to the inside
> > 
> > Like he (Jerry) sez.
> > 
> > You need to keep them all or the magnitude response changes.
> > Any zero pair, as those I defined, contribute to the response.
> > If all the zeros are outside the unit circle, you get maximum phase.
> > If all the zeros are inside the unit circle, you get minimum phase.
> > If you have a mix, then something in between re: phase.
> 
> So if I abandon that "noncausal argument", and instead design a causal 
> linear phase FIR filter (which essentially amounts to delay the impulse 
> response by a filter half-length) and find its roots, I end up with a 
> total response as
> 
>     |H(z)| = |G(z)*G'(z)|
> 
> where G contains all the roots inside the unit circle and G' contains all 
> the roots outside the unit circle. I interpret that as the total filter 
> H(z) implemented as a cascade coupling of one minimum phase filter G(z) 
> and a maximum phase filter G'(z). Do we agree that the same magnitude 
> spectrum H(z) can be implemented as a cascade of two similar minimum 
> phase filters, G(z) and G(z) such that
> 
>     |H(z)| = |G(z)*G(z)|
> 
> which appears to meet the specs, H(z)=G^2(z) is causal and also minimum 
> phase?
> 
> If so, I think Matt's original problem in principle can be solved, though 
> with the already stated practical caveat about finding roots of "large"
> polynomials.
> 
> Rune

I guess apart from root finding there are other difficulties while
constructing
the filter back to coefficient form.It is about numerical stability of
the filter.It becomes worser as the number of roots i.e number
co-efficients of the filter(or degree of ploynomial) increases.
 
I googled sometimes back to find one efficient method to design
minimum phase filter using "Hilbert transform".It needs couple of
FFT/IFFT functions,log/sin functions and weight multiplications.It
seems it provides adequate numerical stability.But I am not sure how
best is a design when number of filter taps exceeds 10 ? I have never
dealt with minimum phase filter design requirement with filter taps
more than 10 - I think some reader can give a way out!

santosh

santosh nath wrote:

> allnor@tele.ntnu.no (Rune Allnor) wrote in message news:<f56893ae.0311030528.52ac968d@posting.google.com>...
> 
>>"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message news:<BsSdnaJA6oskLziiRVn-sg@centurytel.net>...
>>
>>>"Jerry Avins" <jya@ieee.org> wrote in message
>>>news:bo431e$sp8$1@bob.news.rcn.net...
>>>
>>>>Rune Allnor wrote:
>>>>
>>>>  ...
>>>>
>>>>>
>>>>>Eh... I'm not sure if I understand what you mean. Let's see...
>>
>> apparently
>>
>>>>>we agree that half of the zeros ensure linear phase (by being the
>>>>>reciprocals of the zeros that "define" the filter response) while half
>>>>>of the zeros ensure that the filter is noncausal... by being the
>>>>>*conjugates* of the "defining" zeros. And these two halves are not the
>>>>>same. Is that what you are saying?
>>>>>
>>>>>In that case my approach go nowhere, because my filter would be munimum
>>>>>phase but noncausal. Right?
>>>>>
>>>>>OK, the lesson learned is "Don't do DSP at 9 AM sunday morning"... ;)
>>>>>
>>>>>Rune
>>>>
>>>>I think he means to keep all the zeros, but to reflect the ones outside
>>>>the unit circle to the inside
>>>
>>>Like he (Jerry) sez.
>>>
>>>You need to keep them all or the magnitude response changes.
>>>Any zero pair, as those I defined, contribute to the response.
>>>If all the zeros are outside the unit circle, you get maximum phase.
>>>If all the zeros are inside the unit circle, you get minimum phase.
>>>If you have a mix, then something in between re: phase.
>>
>>So if I abandon that "noncausal argument", and instead design a causal 
>>linear phase FIR filter (which essentially amounts to delay the impulse 
>>response by a filter half-length) and find its roots, I end up with a 
>>total response as
>>
>>    |H(z)| = |G(z)*G'(z)|
>>
>>where G contains all the roots inside the unit circle and G' contains all 
>>the roots outside the unit circle. I interpret that as the total filter 
>>H(z) implemented as a cascade coupling of one minimum phase filter G(z) 
>>and a maximum phase filter G'(z). Do we agree that the same magnitude 
>>spectrum H(z) can be implemented as a cascade of two similar minimum 
>>phase filters, G(z) and G(z) such that
>>
>>    |H(z)| = |G(z)*G(z)|
>>
>>which appears to meet the specs, H(z)=G^2(z) is causal and also minimum 
>>phase?
>>
>>If so, I think Matt's original problem in principle can be solved, though 
>>with the already stated practical caveat about finding roots of "large"
>>polynomials.
>>
>>Rune
> 
> 
> I guess apart from root finding there are other difficulties while
> constructing
> the filter back to coefficient form.It is about numerical stability of
> the filter.It becomes worser as the number of roots i.e number
> co-efficients of the filter(or degree of ploynomial) increases.
>  
> I googled sometimes back to find one efficient method to design
> minimum phase filter using "Hilbert transform".It needs couple of
> FFT/IFFT functions,log/sin functions and weight multiplications.It
> seems it provides adequate numerical stability.But I am not sure how
> best is a design when number of filter taps exceeds 10 ? I have never
> dealt with minimum phase filter design requirement with filter taps
> more than 10 - I think some reader can give a way out!
> 
> santosh

Here's the cookbook way to convert a filter whose algebraic
representation you know to minimum phase:

Check that the poles are strictly inside the unit circle of the Z
plane, or canceled by a zero of mathematical identity. (Canceled
by a constructed zero isn't good enough. Nothing is that perfect.)

Lay down the zeros on the same plot. To all those outside the unit
circle, draw radii. Replace the outside zero with another on that
radius so located that the product of its radial distance and the
radial distance of the original zero is unity. (The "reciprocal zero
inside the unit circle.")

The new poles and zeros yield the same magnitude response as the
original, but the phase is minimum. I don't remember why, but I have
it on reliable authority (O&S?). Let's see: reciprocating a zero doesn't 
alter the frequency response. (I think I see that.) Of zeros at the same 
angle, those with shorter radii create less phase shift. Q.E.D.!

Is there a z-plane spirule?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins <jya@ieee.org> wrote in message news:<bo6q8i$f3k$1@bob.news.rcn.net>...
> The new poles and zeros yield the same magnitude response as the
> original, but the phase is minimum. I don't remember why, but I have
> it on reliable authority (O&S?). 

With all due respect, Jerry, I get "bad itches" by that sort of argument. 
Please don't misunderstand! I think you are right and I'm not capable 
of doing better myself. 

Nevertheless, refering an argument to "higher authority" is the absolutely 
last way out, and when I see those kinds of things I get instantly 
suspicious about whatever argument is presented. A couple of days ago 
there was a review of a book on "Science History" or "Science Philosophy" 
on the site www.forskning.no (The Norwegian word "forskning" can best be 
translated as "research", although "science" can also be used). In the 
book review the reviewer mentions an affair which is elabortated somewhat 
on the page

http://www.math.ntnu.no/~hanche/blog/trell/

as one way of *not* conducting a scientific dispute. The dispute goes 
over a "simple proof of Fermat's last theorem" (what else...). Harald
Hanche-Olsen, who made the page referenced above and disputes the 
existence of such a proof, is a mathematician while the people who claim 
they have a simple proof are non-mathematicians.

What struck me was that the "proof of the pudding" by the 
non-mathematicians apparently relies on the "authority" of one 
person:

    "Most of the article is classical argumentation by authority, 
     attempting to establish the credibility of journals like Algebras, 
     Groups and Geometries and its publisher, Hadronic Press, the 
     publishing company of "the world spanning elite scientist 
     institution Institute for Basic Research, led by the Master Mind 
     of our times, Ruggero Maria Santilli". (No, I am not making up the 
     "Master Mind" bit.)"

(Cut'n paste from Hanche-Olsen's blog, one of the first entries near the 
bottom of the page)

When things get as pointed as is the case in this dispute, it's more fun 
than anything else (as long as one does not get involved!), but I think 
it's an issue worth being aware of. This "academic hubris" thing has been 
mentioned once or twice here during the past year or so. Things can get 
really destructive when people get infected by the "hubris disease" and 
don't want to listen to critique of the ideas they "know" to be true.

It may not come as a surprise that I have prepared for a boat trip that 
will take all day tomorrow, by getting some books by Thomas S. Kuhn 
and Karl Popper.

> Let's see: reciprocating a zero doesn't 
> alter the frequency response. (I think I see that.) 

I see that too. I think.

> Of zeros at the same 
> angle, those with shorter radii create less phase shift. Q.E.D.!

This is one of those things I never understood. I "learned" this 
from the Proakis/Manolakis book many years ago, but somehow I failed 
to make sense of their exposition. I must, with great shame and reluctance, 
admit that I accept the "all zeros inside the unit circle implies minimum 
phase" argument solely on the basis of the authority of those who 
present it...

> Is there a z-plane spirule?

Spirule? Couldn't find that word in my dictionary?

Rune

In article f56893ae.0311032343.312d19a7@posting.google.com, Rune Allnor at
allnor@tele.ntnu.no wrote on 11/04/2003 02:43:

> Jerry Avins <jya@ieee.org> wrote in message
> news:<bo6q8i$f3k$1@bob.news.rcn.net>...

....

>> Let's see: reciprocating a zero doesn't
>> alter the frequency response. (I think I see that.)
> 
> I see that too. I think.
> 
>> Of zeros at the same
>> angle, those with shorter radii create less phase shift. Q.E.D.!
> 
> This is one of those things I never understood. I "learned" this
> from the Proakis/Manolakis book many years ago, but somehow I failed
> to make sense of their exposition. I must, with great shame and reluctance,
> admit that I accept the "all zeros inside the unit circle implies minimum
> phase" argument solely on the basis of the authority of those who
> present it...

Rune,

do you understand why it is true for the analog s-plane?  why does an analog
filter that has its zeros all on the left half-plane have less phase shift
than one with some reflected to the right half-plane?

let q > 0 and real.


zero in left half-plane:

    arg{j*w - -q)} = arg{q + j*w} = arctan(w/q}

zero in right half-plane:

    arg{j*w - q} = arg{-q + j*w} = pi - arctan(w/q}


since |arctan(w/q)| <= pi/2  then

    pi - arctan(w/q}  >=  arctan(w/q}     and

    arg{j*w - -q)} <= arg{j*w - q}

so the zero in the left half-plane has less phase shift.

now, to go discrete-time and the z-plane, think BiLinear Transform (zeros in
the left-half s-plane get mapped to the interior of the unit circle under
BLT) and the magnitude and phase are preserved, but at different
frequencies.

the hard question is:  how come, for min-phase filters, the natural log of
gain and phase in radians are a Hilbert transform pair?  that's a hard one
to prove.

r b-j

allnor@tele.ntnu.no (Rune Allnor) wrote in message news:<f56893ae.0311032343.312d19a7@posting.google.com>...
> The dispute goes 
> over a "simple proof of Fermat's last theorem" (what else...). Harald
> Hanche-Olsen, who made the page referenced above and disputes the 
> existence of such a proof, 

Ouch! That last sentence can be misunderstood. Hanche-Olsen does not 
dispute Fermat's last theorem being proved, he disputes the existence 
of a *simple* proof. As far as I know, Wiley, who proved the theorem, 
used just about every known aspect of mathemathics to get every piece
in place. Which probably explains why it took 350 years to prove the 
theorem.

Rune

Rune Allnor wrote:

> Jerry Avins <jya@ieee.org> wrote in message news:<bo6q8i$f3k$1@bob.news.rcn.net>...
> 
>>The new poles and zeros yield the same magnitude response as the
>>original, but the phase is minimum. I don't remember why, but I have
>>it on reliable authority (O&S?). 
> 
> 
> With all due respect, Jerry, I get "bad itches" by that sort of argument. 
> Please don't misunderstand! I think you are right and I'm not capable 
> of doing better myself. 
> 

Since I gave it the trappings of a proof with "Q.E.D.!", I sympathize
with your itch. I should have written that visualizing my old Spirule, I
can see that zeros in the right-hand s plane introduce less phase shift
than those reflected into the left, and that in the z plane right becomes
outside and left becomes inside. reflections about the s-plane vertical
axis become reciprocal along a radius in the z plane. So much for the
geometry. I used the knowledge that that reflecting a zero about the jw
axis leaves the magnitude response unchanged. I cited O&S as the source,
but it may be Guillemin.

I am happy to use those guys' results without re-deriving them. I know
how to calculate the section modulus of a beam given its shape, but there
are tables for that and I use them.

Jerry

P.S. Digital calculators are valuable tools, but those who have never
become proficient with slide rule or Spirule lack a powerful way to
visualize simple solutions to otherwise complicated problems.

P.P.S. I know a simple way to trisect an angle with ruler, compass, and
pencil. I sometimes use it. It works well. I'm not (for this) a nut.
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins <jya@ieee.org> wrote in message news:<bo8mp4$3vi$1@bob.news.rcn.net>...
> Rune Allnor wrote:
> 
> > Jerry Avins <jya@ieee.org> wrote in message news:<bo6q8i$f3k$1@bob.news.rcn.net>...
> > 
> >>The new poles and zeros yield the same magnitude response as the
> >>original, but the phase is minimum. I don't remember why, but I have
> >>it on reliable authority (O&S?). 
> > 
> > 
> > With all due respect, Jerry, I get "bad itches" by that sort of argument. 
> > Please don't misunderstand! I think you are right and I'm not capable 
> > of doing better myself. 
> > 
> 
> Since I gave it the trappings of a proof with "Q.E.D.!", I sympathize
> with your itch. I should have written that visualizing my old Spirule, I
> can see that zeros in the right-hand s plane introduce less phase shift
> than those reflected into the left, and that in the z plane right becomes
> outside and left becomes inside. 

Now that you mention it, the 2nd edition of P&M I used when I took that 
class did show some figures with some vectors(?) from the zeros to the 
unit circle. I never understood why those "vectors" had to be moved
counterclockwise around the zero. (My memory may be failing me now, 
I'm not sure if what I remember makes sense at all). If somebody tells
me it had something to do with moving in the complex plane and staying 
on some particular sheet of a Riemann surface, things may not be as 
total voodoo as they appear at the moment.  

> reflections about the s-plane vertical
> axis become reciprocal along a radius in the z plane. So much for the
> geometry. I used the knowledge that that reflecting a zero about the jw
> axis leaves the magnitude response unchanged. I cited O&S as the source,
> but it may be Guillemin.

It was probably O&S. I haven't seen that book, but from what I hear, 
those guys did things the mathemathical way. 
 
> I am happy to use those guys' results without re-deriving them. I know
> how to calculate the section modulus of a beam given its shape, but there
> are tables for that and I use them.

Of course I agree with you. My problem is that I like to understand 
what's going on. Sure, there are plenty of people out there who do the 
maths way better than I will ever be able to. There are thousands of 
people who code up those numerical routines faster and more efficient, in 
any sense of the word, than me. Still, I like to understand how the stuff 
works. By doing that I have a chance of finding out what's easy and what's 
not. Which means I can anticipate problems with either coding the routines 
or using the routines. And I find out who possess actual knowledge and 
skills, and who are merely "politicians" or "imposters", which would be 
very useful knowledge whenever I or my projects get under pressure.

> Jerry
> 
> P.S. Digital calculators are valuable tools, but those who have never
> become proficient with slide rule or Spirule lack a powerful way to
> visualize simple solutions to otherwise complicated problems.

I have no knowledge of either (I never found out what a spirule is), but
I still trust you on this. Not because of any authority you might have, 
but because of the knowledge and skills you consistently demonstrate.

> P.P.S. I know a simple way to trisect an angle with ruler, compass, and
> pencil. I sometimes use it. It works well. I'm not (for this) a nut.

Yeah, right. I suppose the margin of your post was just too small to 
describe your trick?[*] Anyway, if the occation ever arises where you can 
show me your method face to face, I'll by you a beer.

Rune

[*] Yep, you caught me. According to "authorities" (some maths book, I 
    can't remember which one) it has been proven that trisecting the angle
    by means of the mentioned instruments is impossible. I can't give the 
    proof myself, I can only refer to "authority". Somehow I suspect you 
    knew I would respond like that...

Jerry Avins wrote:

> P.P.S. I know a simple way to trisect an angle with ruler, compass, and
> pencil. I sometimes use it. It works well. I'm not (for this) a nut.

(sideways glance)

Using the ruler's scale, or just the straight edge?

"Eric C. Weaver" <weav@sigma.net> wrote in message news:<3fa88fcb$1@news.announcetech.com>...
> Jerry Avins wrote:
> 
> > P.P.S. I know a simple way to trisect an angle with ruler, compass, and
> > pencil. I sometimes use it. It works well. I'm not (for this) a nut.
> 
> (sideways glance)
> 
> Using the ruler's scale, or just the straight edge?

Right... it took me a couple of hours, but if I can use the scale 
I too can trisect the angle. With only the straight edge things can 
become difficult. 

Rune

Dangerously vocal young programmer wrote: 
> > > P.P.S. I know a simple way to trisect an angle with ruler, compass, and
> > > pencil. I sometimes use it. It works well. I'm not (for this) a nut.
> > 
> > (sideways glance)
> > 
> > Using the ruler's scale, or just the straight edge?
> 
> Right... it took me a couple of hours, but if I can use the scale 
> I too can trisect the angle. With only the straight edge things can 
> become difficult. 
> 
> Rune

Hey Rune, 

Archimedes knew how to do this already, with just a straight edge and
(two I think) pencilmarks. Is that hint enough?


Regards,
Andor

Rune Allnor wrote:
> Jerry Avins <jya@ieee.org> wrote in message news:<bo8mp4$3vi$1@bob.news.rcn.net>...
> 
   ...

>>P.P.S. I know a simple way to trisect an angle with ruler, compass, and
>>pencil. I sometimes use it. It works well. I'm not (for this) a nut.
> 
> 
> Yeah, right. I suppose the margin of your post was just too small to 
> describe your trick?[*] Anyway, if the occation ever arises where you can 
> show me your method face to face, I'll by you a beer.
> 
> Rune
> 
> [*] Yep, you caught me. According to "authorities" (some maths book, I 
>     can't remember which one) it has been proven that trisecting the angle
>     by means of the mentioned instruments is impossible. I can't give the 
>     proof myself, I can only refer to "authority". Somehow I suspect you 
>     knew I would respond like that...

Rune,

I wasn't trying to catch you. We needn't be face to face; I'll describe
the method so you can try it yourself. [All geometry problems that are
isomorphic to quadratic or linear equations can be solved with compass
and straightedge. In general, those isomorphic to cubic and higher
equations can not be so solved.]* Trisection is cubic*, so more powerful
tools are needed. Instead of a straightedge, I need a ruler, as I wrote.
A ruler has parallel sides and an end square to them. These extra-
Euclidian features play a part in the construction. I'll give you time
to play with the idea before I thrust it on you. I do not withhold it
now to tease.

The method came to my attention in the late 1940s when it was published
on the front page of the second section of the then two-section New York
Times. It illustrated someone's clam to have solved the trisection
problem; The Times appeared to endorse that claim. Subsequent discussion
was interesting!

Jerry
_______________________________
* I haven't proved that, but accept it from Authority.
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Andor wrote:

> Dangerously vocal young programmer wrote: 
> 
>>>>P.P.S. I know a simple way to trisect an angle with ruler, compass, and
>>>>pencil. I sometimes use it. It works well. I'm not (for this) a nut.
>>>
>>>(sideways glance)
>>>
>>>Using the ruler's scale, or just the straight edge?
>>
>>Right... it took me a couple of hours, but if I can use the scale 
>>I too can trisect the angle. With only the straight edge things can 
>>become difficult. 
>>
>>Rune
> 
> 
> Hey Rune, 
> 
> Archimedes knew how to do this already, with just a straight edge and
> (two I think) pencilmarks. Is that hint enough?
> 
> 
> Regards,
> Andor

That -- and Rune's way -- sounds simpler than my way. Do those ways work
for large angles, say, 90 degrees +/- a little?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

an2or@mailcircuit.com (Andor) wrote in message news:<ce45f9ed.0311050704.1fe1b0af@posting.google.com>...
:
> Dangerously vocal young programmer wrote: 

Yep, that's what I was getting at... ;)

> > > > P.P.S. I know a simple way to trisect an angle with ruler, compass, and
> > > > pencil. I sometimes use it. It works well. I'm not (for this) a nut.
> > > 
> > > (sideways glance)
> > > 
> > > Using the ruler's scale, or just the straight edge?
> > 
> > Right... it took me a couple of hours, but if I can use the scale 
> > I too can trisect the angle. With only the straight edge things can 
> > become difficult. 
> > 
> > Rune
> 
> Hey Rune, 
> 
> Archimedes knew how to do this already, with just a straight edge and
> (two I think) pencilmarks. Is that hint enough?

I am sure he did. Using the scale of a rule or some other length reference, 
it's not difficult at all. However, some problems appear to have haunted 
maths throughout history:

- Trisecting the angle using only a straight-edge (with no scale or length 
  refernce) and compass
- Constructing a square of the same area as a circle with given diameter
  (or was it vice versa?) using only straight-edge and compass
- Proving one of Euclid's postulates on geometry.

Proving that the first two were impossible was apparently among the first 
main contributions of abstract algebra. The disproof of Euclid's 5th(?) 
postulate spawned what we now know as "non-Euclidian geometry", and with 
it, modern mathematics.

My mistake when I (too sarcastically) flamed Jerry's post was that I 
didn't check the basic assumtions of his claim. 

Rune

Rune Allnor wrote:


>   ... Using the scale of a rule or some other length reference, 
> it's not difficult at all.

I don't know that one, unless trial and error is alowed. The usual way
using trial and error -- called by some "successive refinement" -- is
with dividers. Draftsmen do that regularly.


> However, some problems appear to have haunted maths throughout history:
> 
> - Trisecting the angle using only a straight-edge (with no scale or length 
>   refernce) and compass
> - Constructing a square of the same area as a circle with given diameter
>   (or was it vice versa?) using only straight-edge and compass
> - Proving one of Euclid's postulates on geometry.
> 
> Proving that the first two were impossible was apparently among the first 
> main contributions of abstract algebra. The disproof of Euclid's 5th(?) 
> postulate spawned what we now know as "non-Euclidian geometry", and with 
> it, modern mathematics.
> 
> My mistake when I (too sarcastically) flamed Jerry's post was that I 
> didn't check the basic assumtions of his claim. 

Now _that_ was a trap I did lay!

> 
> Rune

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

On Wed, 05 Nov 2003 13:42:12 -0500, Jerry Avins <jya@ieee.org> wrote:
> Rune Allnor wrote:
>> Jerry Avins <jya@ieee.org> wrote in message news:<bo8mp4$3vi$1@bob.news.rcn.net>...
>> 
>    ...
> 
>>>P.P.S. I know a simple way to trisect an angle with ruler, compass, and
>>>pencil. I sometimes use it. It works well. I'm not (for this) a nut.
>> 
>> 
>> Yeah, right. I suppose the margin of your post was just too small to 
>> describe your trick?[*] Anyway, if the occation ever arises where you can 
>> show me your method face to face, I'll by you a beer.
>> 
>> Rune
>> 
>> [*] Yep, you caught me. According to "authorities" (some maths book, I 
>>     can't remember which one) it has been proven that trisecting the angle
>>     by means of the mentioned instruments is impossible. I can't give the 
>>     proof myself, I can only refer to "authority". Somehow I suspect you 
>>     knew I would respond like that...
> 
> Rune,
> 
> I wasn't trying to catch you. We needn't be face to face; I'll describe
> the method so you can try it yourself. [All geometry problems that are
> isomorphic to quadratic or linear equations can be solved with compass
> and straightedge. In general, those isomorphic to cubic and higher
> equations can not be so solved.]* Trisection is cubic*, so more powerful
> tools are needed. Instead of a straightedge, I need a ruler, as I wrote.
> A ruler has parallel sides and an end square to them. These extra-
> Euclidian features play a part in the construction. I'll give you time
> to play with the idea before I thrust it on you. I do not withhold it
> now to tease.
> 
> The method came to my attention in the late 1940s when it was published
> on the front page of the second section of the then two-section New York
> Times. It illustrated someone's clam to have solved the trisection
> problem; The Times appeared to endorse that claim. Subsequent discussion
> was interesting!

A couple of us devised a technique in HS Geometry back in the late
'70's, after the instructor told us it couldn't be done.  After her
disbelief subsided, she had us prove it was correct, and why it did NOT
disprove that it couldn't be done using geometric construction.

The same technique came up in Engineering Graphics my first year of
college, though they extended it to n-section, and weren't especially
rigorous in proving it correct. 

Jerry Avins <jya@ieee.org> wrote in message news:<bobgaa$lvo$1@bob.news.rcn.net>...
> Rune Allnor wrote:
> > Jerry Avins <jya@ieee.org> wrote in message news:<bo8mp4$3vi$1@bob.news.rcn.net>...
> > 
>    ...
> 
> >>P.P.S. I know a simple way to trisect an angle with ruler, compass, and
> >>pencil. I sometimes use it. It works well. I'm not (for this) a nut.
> > 
> > 
> > Yeah, right. I suppose the margin of your post was just too small to 
> > describe your trick?[*] Anyway, if the occation ever arises where you can 
> > show me your method face to face, I'll by you a beer.
> > 
> > Rune
> > 
> > [*] Yep, you caught me. According to "authorities" (some maths book, I 
> >     can't remember which one) it has been proven that trisecting the angle
> >     by means of the mentioned instruments is impossible. I can't give the 
> >     proof myself, I can only refer to "authority". Somehow I suspect you 
> >     knew I would respond like that...
> 
> Rune,
> 
> I wasn't trying to catch you. We needn't be face to face; I'll describe
> the method so you can try it yourself. 

OK. I'll have a beer anyway...

> [All geometry problems that are
> isomorphic to quadratic or linear equations can be solved with compass
> and straightedge. In general, those isomorphic to cubic and higher
> equations can not be so solved.]* Trisection is cubic*, so more powerful
> tools are needed. Instead of a straightedge, I need a ruler, as I wrote.
> A ruler has parallel sides and an end square to them. These extra-
> Euclidian features play a part in the construction. I'll give you time
> to play with the idea before I thrust it on you. I do not withhold it
> now to tease.

Here's my best shot. View with a fixed-width font to see the figure.
There should be an <end line> immediately after each 'x'.

                C                             x
              /                               x
     E-+  -  /- F                             x
       :    /:                                x
       :   / :-                               x
       :  /  :                                x
     D-: /   :- H                             x
       :/    :                                x
   ----/-----+-------- B                      x
      /A     G                                x

Consider the lines AB and AC that intersect at an angle <BAC, to be 
trisected, in the point A.

- Construct a normal to AB that intersects AB in the point A
- Use the scale of the ruler and mark a point D on this normal 
  at a distance L from AB.
- Use the scale of the ruler and mark a point E on this normal 
  at a distance 3L from AB.
- Construct two parallels to AB, one that intersects the normal 
  in the point D (not drawn in the figure), and another one that 
  intersects the normal in point E.
- The parallel through E intersects AC in the point F
- Construct a normal from F to AB that intersects AB in the point G
- This normal also intersects the parallel through D. Designate the 
  intersection point H. 
- Draw the line AH (not shown in the figure). 

- Now we have <BAH = 1/3 <BAC

I've been thinking in terms of compasses and straightedges, and a length 
reference L. It's easy to go through the same procedure if equiped with 
a ruler that is parallel and at right angles at the ends. 

> The method came to my attention in the late 1940s when it was published
> on the front page of the second section of the then two-section New York
> Times. It illustrated someone's clam to have solved the trisection
> problem; The Times appeared to endorse that claim. Subsequent discussion
> was interesting!

I'm once again amazed by what you found in newspapers. You told a similar 
story about how you found that recipe for making a transistor out of two 
tubes, a piece of string and a bent nail, didn't you?

Rune

> Jerry
> _______________________________
> * I haven't proved that, but accept it from Authority.

Rune Allnor wrote:
> 
>                 C                             x
>               /                               x
>      E-+  -  /- F                             x
>        :    /:                                x
>        :   / :-                               x
>        :  /  :                                x
>      D-: /   :- H                             x
>        :/    :                                x
>    ----/-----+-------- B                      x
>       /A     G                                x
> 
> 
> - Now we have <BAH = 1/3 <BAC
> 

Unless I'm missing something, what you actually have is

   tan(<BAH) = 1/3 tan(<BAC)

which is not the same thing.

Paul

Paul Russell wrote:

> Rune Allnor wrote:
> 
>>
>>                 C                             x
>>               /                               x
>>      E-+  -  /- F                             x
>>        :    /:                                x
>>        :   / :-                               x
>>        :  /  :                                x
>>      D-: /   :- H                             x
>>        :/    :                                x
>>    ----/-----+-------- B                      x
>>       /A     G                                x
>>
>>
>> - Now we have <BAH = 1/3 <BAC
>>
> 
> Unless I'm missing something, what you actually have is
> 
>   tan(<BAH) = 1/3 tan(<BAC)
> 
> which is not the same thing.
> 
> Paul

I don't have time now to give it the attention it deserves, but that's 
why I asked how it works for large angles. I can prove the construction
I use. More tomorrow.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Paul Russell <prussell@sonic.net> wrote in message news:<nOfqb.4017$Wy2.46860@typhoon.sonic.net>...
> Rune Allnor wrote:
> > 
> >                 C                             x
> >               /                               x
> >      E-+  -  /- F                             x
> >        :    /:                                x
> >        :   / :-                               x
> >        :  /  :                                x
> >      D-: /   :- H                             x
> >        :/    :                                x
> >    ----/-----+-------- B                      x
> >       /A     G                                x
> > 
> > 
> > - Now we have <BAH = 1/3 <BAC
> > 
> 
> Unless I'm missing something, what you actually have is
> 
>    tan(<BAH) = 1/3 tan(<BAC)
> 
> which is not the same thing.

You didn't miss anything, I did. You are absolutely right.

Rune

Rune Allnor wrote:

   ...

> Here's my best shot. View with a fixed-width font to see the figure.
> There should be an <end line> immediately after each 'x'.
> 
>                 C                             x
>               /                               x
>      E-+  -  /- F                             x
>        :    /:                                x
>        :   / :-                               x
>        :  /  :                                x
>      D-: /   :- H                             x
>        :/    :                                x
>    ----/-----+-------- B                      x
>       /A     G                                x
> 
> Consider the lines AB and AC that intersect at an angle <BAC, to be 
> trisected, in the point A.
> 
> - Construct a normal to AB that intersects AB in the point A
> - Use the scale of the ruler and mark a point D on this normal 
>   at a distance L from AB.
> - Use the scale of the ruler and mark a point E on this normal 
>   at a distance 3L from AB.
> - Construct two parallels to AB, one that intersects the normal 
>   in the point D (not drawn in the figure), and another one that 
>   intersects the normal in point E.
> - The parallel through E intersects AC in the point F
> - Construct a normal from F to AB that intersects AB in the point G
> - This normal also intersects the parallel through D. Designate the 
>   intersection point H. 
> - Draw the line AH (not shown in the figure). 
> 
> - Now we have <BAH = 1/3 <BAC

   ...

Rune,

You must have been Very tired! You indeed have tan(<BAH) = 1/3 tan(<BAC).
Not only do you get the wrong angle, but you produce a right angle if you
start with a one. Moreover, you don't need a marked ruler to trisect a
line; compass and straightedge do nicely.  Four tuts (two tut tuts)!

Bisect the angle in the usual way. Draw two circles on the bisector whose
diameters are the width of the ruler, one of them centered on the vertex.
With the ruler covering both circles, draw lines with both edges, (the
pair being obviously parallel to the bisector).

Even though I didn't prescribe it that way, Euclidean construction could
have been used to draw the figure so far. What follows can't be done with
according to Euclid.

Keeping the ruler centered over the circle about the vertex, slide it
until one corner lies on one of the angle's lines and the other corner on
the same end lies on the closer parallel to the bisector. The end of the
ruler is now the cord of the trisected arc. Take it from there.

An elegant tool to do this job is a ruler with a slit just wide enough to
slide on a pin, and a mark in the middle of its unslit end. After
bisecting the angle, put the pin at the vertex and set the ruler with the
pin in the slit and the end mark on the bisector. Draw [at least one of]
the parallel lines, and move the ruler to the position described above.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins <jya@ieee.org> wrote in message news:<bodjpo$kaq$1@bob.news.rcn.net>...
> Rune Allnor wrote:
> 
>    ...
> 
> > Here's my best shot. View with a fixed-width font to see the figure.
> > There should be an <end line> immediately after each 'x'.
> > 
> >                 C                             x
> >               /                               x
> >      E-+  -  /- F                             x
> >        :    /:                                x
> >        :   / :-                               x
> >        :  /  :                                x
> >      D-: /   :- H                             x
> >        :/    :                                x
> >    ----/-----+-------- B                      x
> >       /A     G                                x
> > 
> > Consider the lines AB and AC that intersect at an angle <BAC, to be 
> > trisected, in the point A.
> > 
> > - Construct a normal to AB that intersects AB in the point A
> > - Use the scale of the ruler and mark a point D on this normal 
> >   at a distance L from AB.
> > - Use the scale of the ruler and mark a point E on this normal 
> >   at a distance 3L from AB.
> > - Construct two parallels to AB, one that intersects the normal 
> >   in the point D (not drawn in the figure), and another one that 
> >   intersects the normal in point E.
> > - The parallel through E intersects AC in the point F
> > - Construct a normal from F to AB that intersects AB in the point G
> > - This normal also intersects the parallel through D. Designate the 
> >   intersection point H. 
> > - Draw the line AH (not shown in the figure). 
> > 
> > - Now we have <BAH = 1/3 <BAC
> 
>    ...
> 
> Rune,
> 
> You must have been Very tired! 

Nope, not tired. Comatose, judging from that attempt...

> You indeed have tan(<BAH) = 1/3 tan(<BAC).
> Not only do you get the wrong angle, but you produce a right angle if you
> start with a one. Moreover, you don't need a marked ruler to trisect a
> line; compass and straightedge do nicely.  Four tuts (two tut tuts)!
> 
> Bisect the angle in the usual way. Draw two circles on the bisector whose
> diameters are the width of the ruler, one of them centered on the vertex.
> With the ruler covering both circles, draw lines with both edges, (the
> pair being obviously parallel to the bisector).
> 
> Even though I didn't prescribe it that way, Euclidean construction could
> have been used to draw the figure so far. What follows can't be done with
> according to Euclid.
> 
> Keeping the ruler centered over the circle about the vertex, slide it
> until one corner lies on one of the angle's lines and the other corner on
> the same end lies on the closer parallel to the bisector. The end of the
> ruler is now the cord of the trisected arc. Take it from there.

Neat! So you essentially use the width of the ruler to divide that arc 
of the angle in three equal parts... your soultion has all the trademarks
of an ingeniousity (if that's a proper word in English): Once you see it, 
it's so obvious that you wonder why there was a problem in the first place. 
And I know there is just no way I could have come up with that myself.

> An elegant tool to do this job is a ruler with a slit just wide enough to
> slide on a pin, and a mark in the middle of its unslit end. After
> bisecting the angle, put the pin at the vertex and set the ruler with the
> pin in the slit and the end mark on the bisector. Draw [at least one of]
> the parallel lines, and move the ruler to the position described above.

After I realized the flaw of my first attempt, I devised a way to trisect
the angle with a piece of string and a compass:

- Use the compass to draw the arc of the angle
- Put a piece of string on the paper along the arc and cut it to the same 
  length as the arc
- Fold the string in three equal lengths, like a "tight Z"
- The length of the folded string is the arc length of the trisected angle

Unfortunately, I could get there without the bent nail...  

Rune

Jerry Avins wrote:
> Andor wrote:
....
> > Archimedes knew how to do this already, with just a straight edge and
> > (two I think) pencilmarks. Is that hint enough?
> 
> That -- and Rune's way -- sounds simpler than my way. Do those ways work
> for large angles, say, 90 degrees +/- a little?

Yep. We did this in algebra class as a special topic - constructable
numbers. That was quite fun. You can see Archimedes solution here:

http://www.cut-the-knot.org/pythagoras/archi.shtml

Regards,
Andor

Andor wrote:

> Jerry Avins wrote:
> 
>>Andor wrote:
> 
> ...
> 
>>>Archimedes knew how to do this already, with just a straight edge and
>>>(two I think) pencilmarks. Is that hint enough?
>>
>>That -- and Rune's way -- sounds simpler than my way. Do those ways work
>>for large angles, say, 90 degrees +/- a little?
> 
> 
> Yep. We did this in algebra class as a special topic - constructable
> numbers. That was quite fun. You can see Archimedes solution here:
> 
> http://www.cut-the-knot.org/pythagoras/archi.shtml
> 
> Regards,
> Andor


That is rich with insights. I particularly like that the reverse
construction -- tripling the angle -- is Euclidean. (Cubing is
easier than taking cube roots.)

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������