Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[robert bristow-johnson]

�
i thought i understood Tchebyshev polynomials well. �including their trig 
definitions (for |x|<1), but if what you're trying to do is generate a sinusoid 
from polynomials, i don't understand where the "Tchebyshev" (with or without 
the "T") comes
in.
is it min/max error (a.k.a. Tchebyshev norm)?
�
if you want a quick 'n clean polynomial for sin(x), there is a very low-order 
optimized polynomial implementation for |x|http://dsp.stackexchange.com/questions/20444/books-resources-for-implementing-various-mathematical-functions-in-fixed-point-a/20482#20482
 .
�
is the purpose to generate a sinusoidal waveform or perhaps to do math with 
(like in the generation of filter
coefficients)?
�
--

r b-j � � � � � � � � � r...@audioimagination.com


"Imagination is more important than knowledge."




 Original Message 

Subject: Re: [music-dsp] Anyone using Chebyshev polynomials to approximate 
trigonometric functions in FPGA DSP

From: "Bogac Topaktas" 

Date: Wed, January 20, 2016 6:12 pm

To: music-dsp@music.columbia.edu

--



> Jack Crenshaw's book "Math Toolkit for Real-Time Programming"

> contains all the information you need: "Chapter 5 - Getting the

> Sines Right" provides theory and practice of approximating

> sines & cosines with various methods including Chebyshev polynomials.

>

> Another good resources is Jean-Michel Muller's book

> "Elementary Functions: Algorithms and Implementation".

>

�
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Generating pink noise in Python

[Nigel Redmon]

Very nice, Stefan!

Thanks for bring it up, I hadn’t seen it before.

Nigel


> On Jan 20, 2016, at 2:59 PM, Stefan Stenzel  
> wrote:
> 
> Allen,
> 
> Did you consider the recipe for pink noise I published recently?
> It performs better in terms of precision and performance than all others.
> 
> https://github.com/Stenzel/newshadeofpink
> 
> Regards,
> Stefan
> 
> 
> 
>> On 20 Jan 2016, at 21:41 , Allen Downey  wrote:
>> 
>> Hi Music-DSP,
>> 
>> Short version: I've got a new blog post about generating pink noise in 
>> Python:
>> 
>> http://www.dsprelated.com/showarticle/908.php
>> 
>> Longer version:
>> 
>> If you set the WABAC machine for 1978, you might remember Martin Gardner's 
>> column in Scientific American about pink noise and fractal music.  It 
>> presented material from a paper by Voss and Clarke that included an 
>> algorithm for generating pink noise.
>> 
>> Then in 1999 there was a discussion on this very mailing list about the Voss 
>> algorithm, which included a message from James McCartney that suggested an 
>> improvement to the algorithm.  This page explains the details: 
>> http://www.firstpr.com.au/dsp/pink-noise/
>> 
>> And in 2006 there was another discussion on this very mailing list, where 
>> Larry Trammell suggested a stochastic version of the algorithm.  This page 
>> has the details:  http://home.earthlink.net/~ltrammell/tech/pinkalg.htm
>> 
>> As an exercise in my book, Think DSP, I challenge the reader to implement 
>> one of these algorithms in Python, using NumPy for reasonable performance.  
>> I present my implementation in a new blog post at
>> 
>> http://www.dsprelated.com/showarticle/908.php
>> 
>> From there, there's a link to the IPython notebook with all the details.
>> 
>> Hope you find it interesting!
>> 
>> Allen
>> 
>> ___
>> dupswapdrop: music-dsp mailing list
>> music-dsp@music.columbia.edu
>> https://lists.columbia.edu/mailman/listinfo/music-dsp
> 
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
> 

___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[Ross Bencina]

On 21/01/2016 2:36 PM, robert bristow-johnson wrote:
> i thought i understood Tchebyshev polynomials well.  including their
> trig definitions (for |x|<1), but if what you're trying to do is
> generate a sinusoid from polynomials, i don't understand where the
> "Tchebyshev" (with or without the "T") comes in.
>
> is it min/max error (a.k.a. Tchebyshev norm)?

Here's the relevant passage from p. 119:

"""
An article about sines and cosines wouldn’t be complete without some 
mention of the use of Chebyshev polynomials. Basically, the theory of 
Chebyshev polynomials allows the programmer to tweak the coefficients a 
bit for a lower error bound overall. When I truncate a polynomial, I 
typically get very small errors when x is small, and the errors increase 
dramatically and exponentially outside a certain range near x = 0. The 
Chebyshev polynomials, on the other hand, oscillate about zero with peak 
deviations that are bounded and equal. Expressing the power series in 
terms of Chebyshev polynomials allows you to trade off the small errors 
near zero for far less error near the extremes of the argument range. I 
will not present a treatise on Chebyshev polynomials here; for now, I’ll 
only give the results of the process.


You don’t need to know how this is done for the purposes of this 
discussion, but the general idea is to substitute every power of x by 
its equivalent in terms of Chebyshev polynomials, collect the terms, 
truncate the series in that form, and substitute back again. When all 
the terms have been collected, you’ll find that you are back to a power 
series in x again, but the coefficients have been slightly altered in an 
optimal way. Because this process results in a lower maximum error, 
you’ll normally find you can drop one term or so in the series expansion 
while still retaining the same accuracy

"""

R.



if you want a quick 'n clean polynomial for sin(x), there is a very
low-order optimized polynomial implementation for |x|http://dsp.stackexchange.com/questions/20444/books-resources-for-implementing-various-mathematical-functions-in-fixed-point-a/20482#20482
.

is the purpose to generate a sinusoidal waveform or perhaps to do math
with (like in the generation of filter coefficients)?

___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[robert bristow-johnson]

 Original Message 

Subject: Re: [music-dsp] Anyone using Chebyshev polynomials to approximate 
trigonometric functions in FPGA DSP

From: "Ross Bencina" 

Date: Wed, January 20, 2016 11:00 pm

To: "A discussion list for music-related DSP" 

--



> On 21/01/2016 2:36 PM, robert bristow-johnson wrote:

> > i thought i understood Tchebyshev polynomials well. including their

> > trig definitions (for |x|<1), but if what you're trying to do is

> > generate a sinusoid from polynomials, i don't understand where the

> > "Tchebyshev" (with or without the "T") comes in.

> >

> > is it min/max error (a.k.a. Tchebyshev norm)?

>

> Here's the relevant passage from p. 119:

>

> An article about sines and cosines wouldnt be complete without some

> mention of the use of Chebyshev polynomials. Basically, the theory of

> Chebyshev polynomials allows the programmer to tweak the coefficients a

> bit for a lower error bound overall. When I truncate a polynomial, I

> typically get very small errors when x is small, and the errors increase

> dramatically and exponentially outside a certain range near x = 0. The

> Chebyshev polynomials, on the other hand, oscillate about zero with peak

> deviations that are bounded and equal. Expressing the power series in

> terms of Chebyshev polynomials allows you to trade off the small errors

> near zero for far less error near the extremes of the argument range.
okay, i guess. �i'll have to do a bit more internet research, because stated as 
such, this isn't exactly in my "Approximation Theory" book (Cheney). �the 
"Tchebyshev norm" for error is
mentioned. �but the technique is the "Remes" (with an "s") algorithm.
�
so, the fundamental thing that i don't understand, is that given the same order 
N for the polynomials, whether your basis set are the Tchebyshevs, T_n(x), or 
the basis is just set of
x^n, if you come up with a min/max optimal fit to your data, how can the two 
polynomials be different? �i know that Parks-McClellan use the Tchebyshevs to 
convert an optimized polynomial to a sum of cosines (of which a symmetrical FIR 
filter comes forth), but i am curious how the technique that
Jack shows you gets a different answer than the Remes alg, after the sum of 
Tchebyshevs is expanded and converted to a sum of x^n.



--
�
r b-j � � � � � � � � � r...@audioimagination.com
�


"Imagination is more important than knowledge."
�
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[Ethan Duni]

>given the same order N for the polynomials, whether your basis set are
> the Tchebyshevs, T_n(x), or the basis is just set of x^n, if you come up
>with a min/max optimal fit to your data, how can the two polynomials be
>different?

Right, if you do that you'll end up with equivalent answers (to within
numerical precision).

The idea is that you avoid the cost of doing the iterative algorithm to get
the optimal polynomial, and instead you simply truncate the Chebyshev
expansion to the desired order to get an approximation. For well-behaved
target functions it should be quite close. The justification is that the
Chebyshev polynomials each look like solutions to the minimax problem (they
oscillate between +-1 and the Nth polynomial has N+1 extrema), and the
error from truncating a series is approximately proportional to the last
retained term, so truncating a Chebyshev expansion should resemble the
optimal polynomial.

E

On Wed, Jan 20, 2016 at 10:32 PM, robert bristow-johnson <
r...@audioimagination.com> wrote:

>
>
>  Original Message 
> Subject: Re: [music-dsp] Anyone using Chebyshev polynomials to approximate
> trigonometric functions in FPGA DSP
> From: "Ross Bencina" 
> Date: Wed, January 20, 2016 11:00 pm
> To: "A discussion list for music-related DSP" <
> music-dsp@music.columbia.edu>
> --
>
> > On 21/01/2016 2:36 PM, robert bristow-johnson wrote:
> > > i thought i understood Tchebyshev polynomials well. including their
> > > trig definitions (for |x|<1), but if what you're trying to do is
> > > generate a sinusoid from polynomials, i don't understand where the
> > > "Tchebyshev" (with or without the "T") comes in.
> > >
> > > is it min/max error (a.k.a. Tchebyshev norm)?
> >
> > Here's the relevant passage from p. 119:
> >
> > An article about sines and cosines wouldn’t be complete without some
> > mention of the use of Chebyshev polynomials. Basically, the theory of
> > Chebyshev polynomials allows the programmer to tweak the coefficients a
> > bit for a lower error bound overall. When I truncate a polynomial, I
> > typically get very small errors when x is small, and the errors increase
> > dramatically and exponentially outside a certain range near x = 0. The
> > Chebyshev polynomials, on the other hand, oscillate about zero with peak
> > deviations that are bounded and equal. Expressing the power series in
> > terms of Chebyshev polynomials allows you to trade off the small errors
> > near zero for far less error near the extremes of the argument range.
>
> okay, i guess.  i'll have to do a bit more internet research, because
> stated as such, this isn't exactly in my "Approximation Theory" book
> (Cheney).  the "Tchebyshev norm" for error is mentioned.  but the technique
> is the "Remes" (with an "s") algorithm.
>
>
>
> so, the fundamental thing that i don't understand, is that given the same
> order N for the polynomials, whether your basis set are the Tchebyshevs,
> T_n(x), or the basis is just set of x^n, if you come up with a min/max
> optimal fit to your data, how can the two polynomials be different?  i know
> that Parks-McClellan use the Tchebyshevs to convert an optimized polynomial
> to a sum of cosines (of which a symmetrical FIR filter comes forth), but i
> am curious how the technique that Jack shows you gets a different answer
> than the Remes alg, after the sum of Tchebyshevs is expanded and converted
> to a sum of x^n.
>
>
>
> --
>
>
>
> r b-j   r...@audioimagination.com
>
>
>
>
> "Imagination is more important than knowledge."
>
>
>
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[robert bristow-johnson]

 Original Message 

Subject: Re: [music-dsp] Anyone using Chebyshev polynomials to approximate 
trigonometric functions in FPGA DSP

From: "Ethan Duni" 

Date: Thu, January 21, 2016 2:34 am

To: "A discussion list for music-related DSP" 

--



>>given the same order N for the polynomials, whether your basis set are

>> the Tchebyshevs, T_n(x), or the basis is just set of x^n, if you come up

>>with a min/max optimal fit to your data, how can the two polynomials be

>>different?

>

> Right, if you do that you'll end up with equivalent answers (to within

> numerical precision).

>

> The idea is that you avoid the cost of doing the iterative algorithm to get

> the optimal polynomial, and instead you simply truncate the Chebyshev

> expansion to the desired order to get an approximation. For well-behaved

> target functions it should be quite close. The justification is that the

> Chebyshev polynomials each look like solutions to the minimax problem (they

> oscillate between +-1 and the Nth polynomial has N+1 extrema), and the

> error from truncating a series is approximately proportional to the last

> retained term, so truncating a Chebyshev expansion should resemble the

> optimal polynomial.
got it. �thanks for the explanation, Ethan.



--
�
r b-j � � � � � � � � � r...@audioimagination.com
�


"Imagination is more important than knowledge."
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Fully Funded PhDs in Media and Arts Technology at Queen Mary - Closing Date 31/1/16

[JER BOK]

dreamtime

On Wed, Jan 20, 2016 at 2:58 AM, Mark Sandler 
wrote:

> Hello
>
> i’d be grateful if you could forward this email to interested people.
> Music and Audio Research are very much part of what this programme caters
> for.
>
> Further information can be found via
>
> http://www.findaphd.com/search/PhdDetails.aspx?CAID=515
>
>
>
> best wishes
>
> mark
>
> --
> professor mark sandler, CEng, FIEEE, FAES, FIET, FBCS
> royal society wolfson research merit award holder
>
> director of the EPSRC/AHRC CDT in media and arts technology (MAT)
> director of the centre for digital music (c4dm)
>
> school of electronic engineering and computer science
> queen mary university of london
>
> mark.sand...@qmul.ac.uk
> +44 (0)20 7882 7680; +44 (0)7775 016715
>
> twitter: @markbsandler,
> follow the FAST-IMPACt Programme Grant @semanticaudio
>
>
>
>
>
>
>
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

[music-dsp] Generating pink noise in Python

[Allen Downey]

Hi Music-DSP,

Short version: I've got a new blog post about generating pink noise in
Python:

http://www.dsprelated.com/showarticle/908.php

Longer version:

If you set the WABAC machine for 1978, you might remember Martin Gardner's
column in *Scientific American* about pink noise and fractal music.  It
presented material from a paper by Voss and Clarke that included an
algorithm for generating pink noise.

Then in 1999 there was a discussion on this very mailing list about the
Voss algorithm, which included a message from James McCartney that
suggested an improvement to the algorithm.  This page explains the details:
http://www.firstpr.com.au/dsp/pink-noise/

And in 2006 there was another discussion on this very mailing list, where
Larry Trammell suggested a stochastic version of the algorithm.  This page
has the details:  http://home.earthlink.net/~ltrammell/tech/pinkalg.htm

As an exercise in my book, *Think DSP*, I challenge the reader to implement
one of these algorithms in Python, using NumPy for reasonable performance.
I present my implementation in a new blog post at

http://www.dsprelated.com/showarticle/908.php

>From there, there's a link to the IPython notebook with all the details.

Hope you find it interesting!

Allen
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Generating pink noise in Python

[Stefan Stenzel]

Allen,

Did you consider the recipe for pink noise I published recently?
It performs better in terms of precision and performance than all others.

https://github.com/Stenzel/newshadeofpink

Regards,
Stefan



> On 20 Jan 2016, at 21:41 , Allen Downey  wrote:
> 
> Hi Music-DSP,
> 
> Short version: I've got a new blog post about generating pink noise in Python:
> 
> http://www.dsprelated.com/showarticle/908.php
> 
> Longer version:
> 
> If you set the WABAC machine for 1978, you might remember Martin Gardner's 
> column in Scientific American about pink noise and fractal music.  It 
> presented material from a paper by Voss and Clarke that included an algorithm 
> for generating pink noise.
> 
> Then in 1999 there was a discussion on this very mailing list about the Voss 
> algorithm, which included a message from James McCartney that suggested an 
> improvement to the algorithm.  This page explains the details: 
> http://www.firstpr.com.au/dsp/pink-noise/
> 
> And in 2006 there was another discussion on this very mailing list, where 
> Larry Trammell suggested a stochastic version of the algorithm.  This page 
> has the details:  http://home.earthlink.net/~ltrammell/tech/pinkalg.htm
> 
> As an exercise in my book, Think DSP, I challenge the reader to implement one 
> of these algorithms in Python, using NumPy for reasonable performance.  I 
> present my implementation in a new blog post at
> 
> http://www.dsprelated.com/showarticle/908.php
> 
> From there, there's a link to the IPython notebook with all the details.
> 
> Hope you find it interesting!
> 
> Allen
> 
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp

___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[Bogac Topaktas]

Jack Crenshaw's book "Math Toolkit for Real-Time Programming"
contains all the information you need: "Chapter 5 - Getting the
Sines Right" provides theory and practice of approximating
sines & cosines with various methods including Chebyshev polynomials.

Another good resources is Jean-Michel Muller's book
"Elementary Functions: Algorithms and Implementation".

On Tue, January 19, 2016 8:05 pm, Theo Verelst wrote:
> Hi all,
>
>
> Maybe a bit forward, but hey, there are PhDs here, too, so here it goes:
> I've played a
> little with the latest Vivado HLx design tools fro Xilinx FPGAs and the
> cheap Zynq implementation I use (a Parallella board), and I was looking
> for interesting examples to put in C-to_chip compiler that I can connected
> over AXI bus to a Linux program running on the ARM cores in the Zynq chip.
>
>
> In other words, computations and manipulations with additions, multiplies
> and other logical operations (say of 32 bits) that compile nicely to for
> instance the computation of y=sin(t) in such a form that the Silicon
> Compiler can have a go at it, and produce a nice
> relative low-latency FPGA block to connect up with other blocks to do nice
> (and very low
> latency) DSP with.
>
> Regards,
>
>
> Theo V.
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
>
>


___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

[music-dsp] Fully Funded PhDs in Media and Arts Technology at Queen Mary - Closing Date 31/1/16

[Mark Sandler]

Hello

i’d be grateful if you could forward this email to interested people. Music and 
Audio Research are very much part of what this programme caters for.

Further information can be found via

http://www.findaphd.com/search/PhdDetails.aspx?CAID=515



best wishes

mark

--
professor mark sandler, CEng, FIEEE, FAES, FIET, FBCS
royal society wolfson research merit award holder

director of the EPSRC/AHRC CDT in media and arts technology (MAT)
director of the centre for digital music (c4dm)

school of electronic engineering and computer science
queen mary university of london

mark.sand...@qmul.ac.uk
+44 (0)20 7882 7680; +44 (0)7775 016715

twitter: @markbsandler,
follow the FAST-IMPACt Programme Grant @semanticaudio






___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp