a reasonably bright idea has just struck me. I have been following this
thread for some time and I am familiar with the table method of generating
a sine (quarter wave stored).
My idea is, that since the Bresenham circle algorythm exists, it is
possible to compute the 'next' value for a phase continuous sine wave
without storing any table and by obtaining results directly in integers
(no floats no lookups no nothing).
Any single DTMF tone starts at phase 0. So, one can use the Bresenham
circle algorythm to approximate the 1st quarter wave of a sine. This
should replace the quarter sine table.
Because of the way the Bresenham algorythms work it should be possible
to arrange for only an 8 bit accumulator to be necessary for calculations.
I have not pursued the idea further for now, but based on a paper sketch
it should work out on 8 bit unsigned for an output precision of 6 bits
(for each sine wave). How does this strike you ?
> Hello,
>
> a reasonably bright idea has just struck me. I have been following this
> thread for some time and I am familiar with the table method of generating
> a sine (quarter wave stored).
>
> My idea is, that since the Bresenham circle algorythm exists, it is
> possible to compute the 'next' value for a phase continuous sine wave
> without storing any table and by obtaining results directly in integers
> (no floats no lookups no nothing).
Enlighten my ignorance, what the hell is the 'Brensenham circle
algorithm'? From context, I presume it's a recursive algorithm useful for
computing the x & y coordinates of a circle as you equidistant (i.e.
equiangular) steps. If that's the case, then it's not too unsimilar to the
goertzel algorithm. The problem I've found with the goertzel algorithm is
that round off errors gradually increase to the point where sines and
cosines are no longer produced. If you're computing a few cycles of sines
and cosines, then the goertzel algorithm is great: it's fast and
efficient.
>
> Any single DTMF tone starts at phase 0. So, one can use the Bresenham
> circle algorythm to approximate the 1st quarter wave of a sine. This
> should replace the quarter sine table.
And I suspect because of round off errors you'd have to repeat this
quarter circle calculation every quarter of a circle - unless of course
you store the results in an array. But if you do that, you might as well
implement the array...
It's possible to combine algorithms. For example, if you needed higher
resolution you could store the same number of samples in the table for
just 1/8 of the circle. (Beyond 1/8, you'll have to start using trig
identities that involve irrational numbers.) Then instead of linear
interpolation you may use cubic splines or goertzel steps. But in the few
applications I needed sinewaves, lookup tables and linear interpolation
proved to be fast and accurate enough.
"Peter L. Peres" <spam_OUTplpTakeThisOuTACTCOM.CO.IL> wrote:
> My idea is, that since the Bresenham circle algorythm exists, it is
> possible to compute the 'next' value for a phase continuous sine wave
> without storing any table and by obtaining results directly in integers
> (no floats no lookups no nothing).
[...]
> I have not pursued the idea further for now, but based on a paper sketch
> it should work out on 8 bit unsigned for an output precision of 6 bits
> (for each sine wave). How does this strike you ?
It is a good idea, and I've seen it done before, but I don't recall
where. Maybe in a TI DSP apnote? Anyhow, the one I saw used a 16-bit
accumulator, but perhaps it would work with 8-bit. As long as you can
get through one quadrant correctly, i.e., if your scale is such that
0x3f is 1.0, from (0x00,0x3f) to (03f,0x00), it should work very well.
> My idea is, that since the Bresenham circle algorythm exists, it is
> possible to compute the 'next' value for a phase continuous sine wave
> without storing any table and by obtaining results directly in integers
> (no floats no lookups no nothing).
Ok... Bresenham will get you the appropriate X coordinate for iterative steps in
Y (or vice versa), but then all you have is a pair of coordinates. How are you
going to convert those into sines? If I understand you correctly, you'll have
[r.cos(t),r.sin(t)], but since you don't have t, you don't know the angle for
which you have the sine value. What you've got, for a given Y is
sqrt((r*r)-(Y*Y)).
> Any single DTMF tone starts at phase 0. So, one can use the Bresenham
> circle algorythm to approximate the 1st quarter wave of a sine. This
> should replace the quarter sine table.
>
Do you mean you're going to represent a sine wave as a sequence of quarter
circles?! Hmmmm... perhaps I'm missing something?
Ben Stragnell <.....spareKILLspam@spam@CODEPUPPIES.COM> wrote:
> Ok... Bresenham will get you the appropriate X coordinate for iterative steps
in
> Y (or vice versa), but then all you have is a pair of coordinates. How are you
> going to convert those into sines? If I understand you correctly, you'll have
> [r.cos(t),r.sin(t)], but since you don't have t, you don't know the angle for
> which you have the sine value.
Of course you have t.
You start with t=0, x=1, y=0.
Each iteration of the DDA will increment t by some amount delta.
After each iteration, x will be cos(t) and y will be sin(t).
This is most useful if you need to repeatedly calculate sin(t) and/or cos(t)
for successively increasing (or decreasing) values of t, as would be the
case in sinewave frequency synthesis.
If you just want the sine or cosine of an arbitrary angle, this is probably
not the way to do it.
> Ben Stragnell <spareKILLspamCODEPUPPIES.COM> wrote:
> > Ok... Bresenham will get you the appropriate X coordinate for iterative step
s in
> > Y (or vice versa), but then all you have is a pair of coordinates. How are y
ou {Quote hidden}
> > going to convert those into sines? If I understand you correctly, you'll hav
e
> > [r.cos(t),r.sin(t)], but since you don't have t, you don't know the angle fo
r
> > which you have the sine value.
>
> Of course you have t.
>
> You start with t=0, x=1, y=0.
> Each iteration of the DDA will increment t by some amount delta.
> After each iteration, x will be cos(t) and y will be sin(t).
>
But, each iteration does not increment t by the same amount. Each iteration step
s one
unit along one of the axes, and potentially one unit along the other axis, depen
ding
on the overflow of the error term. This does not correspond to a linear increase
in
the angle.
> On Wed, 4 Nov 1998, Peter L. Peres wrote:
>
> > Hello,
> >
> > a reasonably bright idea has just struck me. I have been following this
> > thread for some time and I am familiar with the table method of generating
> > a sine (quarter wave stored).
> >
> > My idea is, that since the Bresenham circle algorythm exists, it is
> > possible to compute the 'next' value for a phase continuous sine wave
> > without storing any table and by obtaining results directly in integers
> > (no floats no lookups no nothing).
>
> Enlighten my ignorance, what the hell is the 'Brensenham circle
> algorithm'? From context, I presume it's a recursive algorithm useful for
> computing the x & y coordinates of a circle as you equidistant (i.e.
No, it's an incremental algorythm that computes the y for a given x in a
Cartesian space such that when x varies from 0 to N y is the corresp.
sinus. If you plot x,y as you calculate them you obtain 1/8 circle.
There is also one for ellipses, straights and some more stuff. Look it up,
you will like it VERY much, I am sure ;)
> equiangular) steps. If that's the case, then it's not too unsimilar to the
> goertzel algorithm. The problem I've found with the goertzel algorithm is
I don't know the Goertzel. I'll look it up.
> that round off errors gradually increase to the point where sines and
> cosines are no longer produced. If you're computing a few cycles of sines
> and cosines, then the goertzel algorithm is great: it's fast and
> efficient.
Nono. The Bresenham computes nicely. The only problem is the joinery for
1/8 circles which includes a parity problem and must be solved separately
(for 1 point per circle).
> And I suspect because of round off errors you'd have to repeat this
> quarter circle calculation every quarter of a circle - unless of course
> you store the results in an array. But if you do that, you might as well
> implement the array...
It's incremental, mister. You compute it for 1/8 circle = 1/8 sine = 45
degrees. The trick is, that it does not yield a sine directly, but the
sine is included in the result (already scaled and integer). I'll try to
elaborate on this. imho this algorythm can divide the required table space
for a 1/4 sine by 4. On a PIC this should be significant. Later.
> "Peter L. Peres" <.....plpKILLspam.....ACTCOM.CO.IL> wrote:
> > My idea is, that since the Bresenham circle algorythm exists, it is
> > possible to compute the 'next' value for a phase continuous sine wave
> > without storing any table and by obtaining results directly in integers
> > (no floats no lookups no nothing).
> [...]
> > I have not pursued the idea further for now, but based on a paper sketch
> > it should work out on 8 bit unsigned for an output precision of 6 bits
> > (for each sine wave). How does this strike you ?
>
> It is a good idea, and I've seen it done before, but I don't recall
> where. Maybe in a TI DSP apnote? Anyhow, the one I saw used a 16-bit
> accumulator, but perhaps it would work with 8-bit. As long as you can
> get through one quadrant correctly, i.e., if your scale is such that
> 0x3f is 1.0, from (0x00,0x3f) to (03f,0x00), it should work very well.
There is no question about whether Bresenham works well, the question is,
how do you extract the sine from its Cartesian coords and how to do the
'joinery'. Bresenham produces 1/8 circle segments in a Cartesian space.
You supply incremental x and it supplies incremental y. I have no time for
this now, however.
> Peter L. Peres wrote:
>
> > My idea is, that since the Bresenham circle algorythm exists, it is
> > possible to compute the 'next' value for a phase continuous sine wave
> > without storing any table and by obtaining results directly in integers
> > (no floats no lookups no nothing).
>
> Ok... Bresenham will get you the appropriate X coordinate for iterative
> steps in Y (or vice versa), but then all you have is a pair of
> coordinates. How are you going to convert those into sines? If I
The coordinates (one of them) IS the sine corrsponding to that cosine, and
vice versa. I suppose that one could turn the algorythm a little bit to
yield a true sine or cosine, or, use the ellipsis algorythm (by Bresenham)
to approximate the sine using a linear increment. Remains to be seen how
accurate this can be made.
> Do you mean you're going to represent a sine wave as a sequence of quarter
> circles?! Hmmmm... perhaps I'm missing something?
For now, no. But I'll try to elaborate ;) It looks like a good idea,
though. Something might come from it.
> On Wed, 4 Nov 1998, Ben Stragnell wrote:
>
> > Peter L. Peres wrote:
> >
> > > My idea is, that since the Bresenham circle algorythm exists, it is
> > > possible to compute the 'next' value for a phase continuous sine wave
> > > without storing any table and by obtaining results directly in integers
> > > (no floats no lookups no nothing).
> >
> > Ok... Bresenham will get you the appropriate X coordinate for iterative
> > steps in Y (or vice versa), but then all you have is a pair of
> > coordinates. How are you going to convert those into sines? If I
>
> The coordinates (one of them) IS the sine corrsponding to that cosine, and
> vice versa. I suppose that one could turn the algorythm a little bit to
> yield a true sine or cosine, or, use the ellipsis algorythm (by Bresenham)
> to approximate the sine using a linear increment. Remains to be seen how
> accurate this can be made.
Trouble is, even though you're given both the sine and cosine of an angle, I
don't think there's an easy (ie. trivial and PICable) method of knowing what
that angle is, much less of stepping though the algorithm with fixed angular
increments.
I'm not sure about the ellipse algorithm, but I think if you try to approximate
the sine function using the linear steps along an axis that Bresenham gives (as
opposed to a fixed angular increment), you'll wind up approximating the sine
function with straight lines from sin(-45 to 45), and quarter circles from (sin
45 to 135) (the tops and bottoms of the curves). Of course this may be a good
enough approximation for DTMF, and other applications, but it's definately not a
pure tone.
You could always look into simple harmonic motion - keeping track of a point's
position and velocity, and then using position to derive the acceleration each
tick would yield a nice pure sine wave if you get the scalings right. sin''(t) =
-sin(t). Trouble is, to make the frequency adjustable without breaking the
amplitude would probably require a whole nasty bunch of multiplies. Ouch :)
> Trouble is, even though you're given both the sine and cosine of an angle, I
> don't think there's an easy (ie. trivial and PICable) method of knowing what
> that angle is, much less of stepping though the algorithm with fixed angular
> increments.
As long as we talk generating sines with a digital contraption we talk
about approximations all the time. It would help a lot to define just what
exactly a good enough approximation for DTMF is, in terms of bits
resolution and sampling speed. I'll do this here. Very roughly speaking
0.5% distortion is an error of <= 1/200 and an 8 bit digital signal
(1/256) is good enough. BUT the DTMF tones are built out of two tones
each, which must be added. Since the phone digitizers use 7 or 8 bits
(assume 8), and the power needs to be divided by 2 (roughly, between the
two tones) it follows that only 7 bits are needed to generate each DTMF
tone. Further, the tones need not be sent at full line level, and thus we
dare to steal another two bits, which leads to 6 bits per sine for each
tone (signed). Because of symmetry and sign that's 5 bits of table data
per sine. Referencing to a unity circle it follows that we really need to
store 2^5 table entries == 32 of them. With RLL compression it could be
somewhat less (I think we can afford RLL because only 5 bits of each table
entry are used). A 6 bit table stores 64 entries.
The 'better' Bresenham (?) way of getting the sine would be better iff it
would beat these numbers. Since the Bresenham algorythm yields
reasonably good approximations of integer-scaled sinuses for radiuses
larger than 1024 (10 bits) it should work the better, the more bits are to
be generated imho. But this remains to be proved. I think that the error
grows with larger radiuses.
> I'm not sure about the ellipse algorithm, but I think if you try to
> approximate the sine function using the linear steps along an axis that
> Bresenham gives (as opposed to a fixed angular increment), you'll wind
> up approximating the sine function with straight lines from sin(-45 to
> 45), and quarter circles from (sin 45 to 135) (the tops and bottoms of
> the curves). Of course this may be a good enough approximation for DTMF,
> and other applications, but it's definately not a pure tone.
There is NO digital way to obtain a 'pure tone' using a finite number of
bits per sample and a finite sampling frequency. This results directly
from the definition. It's all about approximations.
The ellipse algorythm might approximate a suitable piece of sinus using a
more or less constant step on the (ellipse-distorted) cosine axis used as
phase-incremental input. The lure is again the beauty of the Bresenham
algorythm of course ;) It would be a pity not to try hard.
> You could always look into simple harmonic motion - keeping track of a
> point's position and velocity, and then using position to derive the
> acceleration each tick would yield a nice pure sine wave if you get the
> scalings right. sin''(t) = -sin(t). Trouble is, to make the frequency
> adjustable without breaking the amplitude would probably require a whole
> nasty bunch of multiplies. Ouch :)
imho it would help a lot to start with the idea that leads to the
Bresenham circle algorythm and to develop it in a slightly different
direction. This idea is very much along the lines of using an
approximation function for a derivate of a trigonometric function over a
small (incremental) interval, which, due to the large tolerable error
(select one pixel out of 3 next possibles), leads to a fiendishly simple
algorythm. I have a hunch about being able to derive a 2nd incremental
result at each step, that accumulates to true angle at each step and turn
the equation so the sine results from the angle and the previous sine. It
would be nice to find out whether this leads to the re-discovery of the
Goertzel formula (with which I am not familiar - i.e. I've never seen it -
yet).
Is there any data available on Mr. Bresenham, the person ? Web searches
yielded nothing interesting. Who owns these algorythms anyway ?
> the equation so the sine results from the angle and the previous sine. It
> would be nice to find out whether this leads to the re-discovery of the
> Goertzel formula (with which I am not familiar - i.e. I've never seen it -
> yet).
> On Thu, 5 Nov 1998, Peter L. Peres wrote:
>
> > the equation so the sine results from the angle and the previous sine. It
> > would be nice to find out whether this leads to the re-discovery of the
> > Goertzel formula (with which I am not familiar - i.e. I've never seen it -
> > yet).
>
> check out the 5th method on my sine web page:
>
> http://www.interstice.com/~sdattalo/technical/theory/sinewave.html
I will.
> > Is there any data available on Mr. Bresenham, the person ? Web searches
> > yielded nothing interesting. Who owns these algorythms anyway ?
>
> I did a search and got only a few hits. Are you sure this is how
> Bresenham is spelled?
That and his genius are the only 2 things I am certain of about him. His
circle algorythm is described in at least one Sedgewick algorythm book,
you should be able to get it somewhere near you (I've no idea where you
are vs. libraries/bookstores).
BTW nearly all fast & small (as in: embedded, small footprint, etc)
graphics libraries use his algorythms, or so I'm told.
>Peter L. Peres wrote:
>
>> On Wed, 4 Nov 1998, Ben Stragnell wrote:
>>
>> > Peter L. Peres wrote:
>> >
>> > > My idea is, that since the Bresenham circle algorythm exists, it is
>> > > possible to compute the 'next' value for a phase continuous sine wave
>> > > without storing any table and by obtaining results directly in integers
>> > > (no floats no lookups no nothing).
>> >
>> > Ok... Bresenham will get you the appropriate X coordinate for iterative
>> > steps in Y (or vice versa), but then all you have is a pair of
>> > coordinates. How are you going to convert those into sines? If I
>>
>> The coordinates (one of them) IS the sine corrsponding to that cosine, and
>> vice versa. I suppose that one could turn the algorythm a little bit to
>> yield a true sine or cosine, or, use the ellipsis algorythm (by Bresenham)
>> to approximate the sine using a linear increment. Remains to be seen how
>> accurate this can be made.
>
>Trouble is, even though you're given both the sine and cosine of an angle, I
>don't think there's an easy (ie. trivial and PICable) method of knowing what
>that angle is, much less of stepping though the algorithm with fixed angular
>increments.
>
>I'm not sure about the ellipse algorithm, but I think if you try to approximate
>the sine function using the linear steps along an axis that Bresenham gives (as
>opposed to a fixed angular increment), you'll wind up approximating the sine
>function with straight lines from sin(-45 to 45), and quarter circles from (sin
>45 to 135) (the tops and bottoms of the curves). Of course this may be a good
>enough approximation for DTMF, and other applications, but it's definately
not a
>pure tone.
>
>You could always look into simple harmonic motion - keeping track of a point's
>position and velocity, and then using position to derive the acceleration each
>tick would yield a nice pure sine wave if you get the scalings right.
sin''(t) =
>-sin(t). Trouble is, to make the frequency adjustable without breaking the
>amplitude would probably require a whole nasty bunch of multiplies. Ouch :)
>
>Cheers,
>
>Ben
>
>
I have been watching this for a period of time. Yes the Bresenham stuff will
work and work well, but (don't you like that always a but) this is often
employed as an evaluated polygon with 4 seeding points. (There is some log
calculations in there too) Nominaly this will require that the software uses
floating point to get the accuracy, however if an error of a few degrees is
acceptable then it is possible not too (No calculating moon shoots with this
one!).
As this is all to do with DTMF detection I would say that while well and
good for getting the brain to function correctly, there is not a chance in
*** for the PIC to do this (At present), as the PIC would have to calculate
the 2 mixed frequencies within a frame window of than 150mS. It would be
better tha have lookup table of 90 degress then just calculate the quadrant.
There is also noise and other things to worry about, all of these make it
hard to do, but an accuracy of 99.9% is all that most carriers require.
Also note the number of samples that would be required, as undersampling
could not be used successfuly (due to the short period of the tone).
Sampling would need to be performed at x times the max frequency (1620Hz?)
> As this is all to do with DTMF detection I would say that while well and
NO, generation. The great debate was, whether it would be possible to do
it and have some room left over for something else in the PIC, and not use
an output analog filter.
In theory it is possible to do lookup table magic and use a PIC at 4MHz to
output an (almost) arbitrary waveform using 8kHz (125 usec) sampling at 8
bits parallel (into a R2R D/A or DAC08 or whatever) and have lots of time
left over for other things. This works well, as I have written some FM
code to interface a serial stream to radio in real time at 38400
(simplex) and had room to spare.
Peter
> Also note the number of samples that would be required, as undersampling
> could not be used successfuly (due to the short period of the tone).
> Sampling would need to be performed at x times the max frequency (1620Hz?)
Re: decoding:
Sampling needs to be done at phone digitizer frequency, 8kHz, to get the
most out of the signal. Also, I think that base clipping will yield a very
'loud' two-tone interference pattern in a ring buffer when receiving DTMF,
and that something or other could be done about this. It would be far from
perfect but it could be usable for projects etc. In theory, it should be
enough to have two full periods of the slower signal in the buffer at any
one time to make sense of it. That would be 700Hz -> ~= 1.4msec -> * 2 =
2.8 msec of samples, @ 125 usec ea. ~= 23 samples. Then you'd have 125
usec to make sense of this. Assuming that a decision and an action is to
be made on each item in the buffer while it is run through in 1 pass,
you'd have 3 T cycles per decision + action * 23 = 69 T cycles to make
sense of the buffer contents, leaving 56 T cycles to wait for the next
sample. This is a PIC at 4 MHz ! My hunch is, that this could work as a
crude DTMF decoder on a PIC. The buffer size fits in the RAM of a 16F84 if
I'm not wrong ;)
I hope that I did not goof on the figures. It's late.
> > I did a search and got only a few hits. Are you sure this is how
> > Bresenham is spelled?
>
> That and his genius are the only 2 things I am certain of about him. His
> circle algorythm is described in at least one Sedgewick algorythm book,
> you should be able to get it somewhere near you (I've no idea where you
> are vs. libraries/bookstores).
>
> BTW nearly all fast & small (as in: embedded, small footprint, etc)
> graphics libraries use his algorythms, or so I'm told.
I did a second search, and this time I spelled Bresenham correctly (it's
not spelled Brensenham!). I now recall reading about the algorithm wrt
computer graphics a while back. It's impressive.
>On Fri, 6 Nov 1998, Dennis Plunkett wrote:
>
>> As this is all to do with DTMF detection I would say that while well and
>
>NO, generation. The great debate was, whether it would be possible to do
>it and have some room left over for something else in the PIC, and not use
>an output analog filter.
>
>In theory it is possible to do lookup table magic and use a PIC at 4MHz to
>output an (almost) arbitrary waveform using 8kHz (125 usec) sampling at 8
>bits parallel (into a R2R D/A or DAC08 or whatever) and have lots of time
>left over for other things. This works well, as I have written some FM
>code to interface a serial stream to radio in real time at 38400
>(simplex) and had room to spare.
>
>Peter
>
>> Also note the number of samples that would be required, as undersampling
>> could not be used successfuly (due to the short period of the tone).
>> Sampling would need to be performed at x times the max frequency (1620Hz?)
>
>Re: decoding:
>
>Sampling needs to be done at phone digitizer frequency, 8kHz, to get the
>most out of the signal. Also, I think that base clipping will yield a very
>'loud' two-tone interference pattern in a ring buffer when receiving DTMF,
>and that something or other could be done about this. It would be far from
>perfect but it could be usable for projects etc. In theory, it should be
>enough to have two full periods of the slower signal in the buffer at any
>one time to make sense of it. That would be 700Hz -> ~= 1.4msec -> * 2 =
>2.8 msec of samples, @ 125 usec ea. ~= 23 samples. Then you'd have 125
>usec to make sense of this. Assuming that a decision and an action is to
>be made on each item in the buffer while it is run through in 1 pass,
>you'd have 3 T cycles per decision + action * 23 = 69 T cycles to make
>sense of the buffer contents, leaving 56 T cycles to wait for the next
>sample. This is a PIC at 4 MHz ! My hunch is, that this could work as a
>crude DTMF decoder on a PIC. The buffer size fits in the RAM of a 16F84 if
>I'm not wrong ;)
>
>I hope that I did not goof on the figures. It's late.
>
>Peter
>
>
6/11/'98
Ok so it was for generation, forgive me for skipping over that. As for
reception, the frequency range of DTMF is 697 to 1633, thus we only have to
sample at 3266 (Or slightly higher) the 8kHz is only for the full voice
stuff, in which case it would be connected to a CODEC of some type. This
CODEC will produce Mu LAW or A LAW compression which wouldh ave to be
converted to get the 16 bit value (This we would not want to do as it will
introduce distortion and take up processing time). Then we have the level
problem, a DTMF signal must be received with a level range of 20dBm, and
with high to low frequency tone power of +4 to -8dBm. Also levels of less
than -35dBm must be rejected. On top of that the decoder must see periods of
breaks of 8 to 12mS as non valid loss (Number still OK) And must ignore a
signal with a tone devation of +/- 3.5%.
So while it is possible to do a basic decode I don't think that a PIC could
handle a full decode.
At 02:52 PM 11/5/98 -0800, you wrote:
>One link that explains quite well is:
>
>http://www.am.qub.ac.uk/world/lists/pic/msg00334.html
>
>Yes, this was discussed on the pic list 3 years ago. And (as usual) Andy
>gave a clear explanation.
Hi Scott,
I just went to that link and directly converted Andy's pseudocode into
BASIC code and it produces a diamond for me, not a circle. I tried various
radius settings, yet the figure definately has straight sides. Maybe I'm
doing something wrong? This algorythm just fascinates me because I don't
understand how it works and I don't have time at the moment to figure it
out (have to run to a meeting).
Thanks, Sean
P.S. The BASIC code is given below:
SCREEN 12
WINDOW SCREEN (-100, 100)-(100, -100)
radius = 50
x = 0
y = radius
switch = 3 - 2 * radius
LOP:
PSET (x, y): PSET (x, -y): PSET (-x, y): PSET (-x, -y)
PSET (y, x): PSET (y, -x): PSET (-y, x): PSET (-y, -x)
IF switch < 0 THEN switch = switch + 4 * x + 6 ELSE switch = switch + 4 *
(x - y) + 10
y = y - 1
x = x + 1
IF x <= y THEN GOTO LOP
> Hi Scott,
>
> I just went to that link and directly converted Andy's pseudocode into
> BASIC code and it produces a diamond for me, not a circle. I tried various
> radius settings, yet the figure definately has straight sides. Maybe I'm
> doing something wrong? This algorythm just fascinates me because I don't
> understand how it works and I don't have time at the moment to figure it
> out (have to run to a meeting).
>
> Thanks, Sean
>
> P.S. The BASIC code is given below:
>
> SCREEN 12
> WINDOW SCREEN (-100, 100)-(100, -100)
> radius = 50
> x = 0
> y = radius
> switch = 3 - 2 * radius
> LOP:
> PSET (x, y): PSET (x, -y): PSET (-x, y): PSET (-x, -y)
> PSET (y, x): PSET (y, -x): PSET (-y, x): PSET (-y, -x)
> IF switch < 0 THEN switch = switch + 4 * x + 6 ELSE switch = switch + 4 *
> (x - y) + 10
> y = y - 1
> x = x + 1
> IF x <= y THEN GOTO LOP
I'm not sure (I haven't tried it in other words), but I believe the y=y-1
statement should be part of the ELSE block that is computing 'switch =
switch + 4 * (x - y) + 10'. If you look at Andy's code, that line (i.e.
the y=y-1 line) is indented to the same level.
> So while it is possible to do a basic decode I don't think that a PIC could
> handle a full decode.
Just a hint, but if you use that median filter thingy we've been
discussing in another thread, you'd be surprised how well the pic can
decode DTMF. Granted, there's a little bit of additional (low cost) analog
circuitry required. But it IS possible.
Ben Stragnell <sparespam_OUTCODEPUPPIES.COM> wrote:
> But, each iteration does not increment t by the same amount. Each iteration st
eps one
> unit along one of the axes, and potentially one unit along the other axis, dep
ending
> on the overflow of the error term. This does not correspond to a linear increa
se in
> the angle.
You're right, for the Bresenham-style circle algorithm. But not for
the Goertzel (sp?) algorithm, which has fixed increments of t rather than
of sin(t).
At 03:51 PM 11/5/98 -0800, you wrote:
>I'm not sure (I haven't tried it in other words), but I believe the y=y-1
>statement should be part of the ELSE block that is computing 'switch =
>switch + 4 * (x - y) + 10'. If you look at Andy's code, that line (i.e.
>the y=y-1 line) is indented to the same level.
BINGO! Thanks Scott, that was the problem. I should have been more careful
when editing that code. The circle it produces is a bit rough, with a large
step size between pixels. I guess that could be changed with some editing
of the code. I really need to take a look at it to see how exactly it
works, when I get some time (yeah, right <G>)
At 11:19 AM 11/5/98 -0800, you wrote:
>> Is there any data available on Mr. Bresenham, the person ? Web searches
>> yielded nothing interesting. Who owns these algorythms anyway ?
>
>I did a search and got only a few hits. Are you sure this is how
>Bresenham is spelled?
I have a text file which I DL'd from a BBS back in 1994 which says that he
still works for IBM. Perhaps you could check out that lead.
Sean Breheny wrote:
>
> At 03:51 PM 11/5/98 -0800, you wrote:
> >I'm not sure (I haven't tried it in other words), but I believe the y=y-1
> >statement should be part of the ELSE block that is computing 'switch =
> >switch + 4 * (x - y) + 10'. If you look at Andy's code, that line (i.e.
> >the y=y-1 line) is indented to the same level.
>
> BINGO! Thanks Scott, that was the problem. I should have been more careful
> when editing that code. The circle it produces is a bit rough, with a large
> step size between pixels. I guess that could be changed with some editing
> of the code. I really need to take a look at it to see how exactly it
> works, when I get some time (yeah, right <G>)
Bytecraft has a nifty routine that breaks the t values up
into a smallish lookup table with the slopes rather than
the values. It is extremely short. I can't copy it to the
list though, because the routine is not mine to copy.
Just knocked up the Bresenham algorithm in a VB prog and it works well.
There is an error on the web site pseudo code however. In order to specify
the origin of the circle Andy quotes this as a possibility:
> when editing that code. The circle it produces is a bit rough, with a large
> step size between pixels. I guess that could be changed with some editing
> of the code. I really need to take a look at it to see how exactly it
> works, when I get some time (yeah, right <G>)
Since you are so unhappy with the rough circle, why not plot another
circle using BASIC's sin/cos right on top of it for comparison. Tell me
what you see ? ;)
> Ok so it was for generation, forgive me for skipping over that. As for
> reception, the frequency range of DTMF is 697 to 1633, thus we only have to
> sample at 3266 (Or slightly higher) the 8kHz is only for the full voice
> stuff, in which case it would be connected to a CODEC of some type. This
> CODEC will produce Mu LAW or A LAW compression which wouldh ave to be
> converted to get the 16 bit value (This we would not want to do as it will
Why 16 bit value ? What for ? I was cutting every corner that came my way
just to avoid anything that may generate a carry on 8 bits when added, and
you'd like to consider 16 bits ?
> introduce distortion and take up processing time). Then we have the level
> problem, a DTMF signal must be received with a level range of 20dBm, and
> with high to low frequency tone power of +4 to -8dBm. Also levels of less
> than -35dBm must be rejected. On top of that the decoder must see periods of
And this is ablessing, and this is what I had referred to when mentioning
clipping decimation and a buffer storage. If all this pre-processing is
done correctly then the lower energy frequency can probably be deduced
from the buffer contents after the high frequency component was selected
and removed by substraction in the first pass. Low amplitudes are rejected
by decimation etc.
> breaks of 8 to 12mS as non valid loss (Number still OK) And must ignore a
> signal with a tone devation of +/- 3.5%.
3.5% is easy to decode with a 8kHz sample as I had described. The other
option is, to sync the buffer fill with the higher frequency tone and
analyze the buffer contents to get the lower frequency tone.
> So while it is possible to do a basic decode I don't think that a PIC could
> handle a full decode.
If by 'full decode' you mean, read all the 16 DTMF symbols, I think it can
be done. If you mean, meet all the specs of a phone connectable device,
the answer is: yes, but with some pre-filtering. This is my opinion only.
> discussing in another thread, you'd be surprised how well the pic can
> decode DTMF. Granted, there's a little bit of additional (low cost) analog
> circuitry required. But it IS possible.
At 04:47 PM 11/6/98 +0000, you wrote:
>On Thu, 5 Nov 1998, Sean Breheny wrote:
>
>> when editing that code. The circle it produces is a bit rough, with a large
>> step size between pixels. I guess that could be changed with some editing
>> of the code. I really need to take a look at it to see how exactly it
>> works, when I get some time (yeah, right <G>)
>
>Since you are so unhappy with the rough circle, why not plot another
>circle using BASIC's sin/cos right on top of it for comparison. Tell me
>what you see ? ;)
Hi Peter,
When I do that, I DO get a better looking circle. However, I don't really
blame this on the algorythm, but on the constants used in this particular
implementation. If they are changed, I bet that the step size can be changed.
> At 04:47 PM 11/6/98 +0000, you wrote:
> >On Thu, 5 Nov 1998, Sean Breheny wrote:
> >
> >> when editing that code. The circle it produces is a bit rough, with a large
> >> step size between pixels. I guess that could be changed with some editing
> >> of the code. I really need to take a look at it to see how exactly it
> >> works, when I get some time (yeah, right <G>)
> >
> >Since you are so unhappy with the rough circle, why not plot another
> >circle using BASIC's sin/cos right on top of it for comparison. Tell me
> >what you see ? ;)
>
> Hi Peter,
>
> When I do that, I DO get a better looking circle. However, I don't really
> blame this on the algorythm, but on the constants used in this particular
> implementation. If they are changed, I bet that the step size can be changed.
How did you plot with sin/cos ? dots, back-joining lines and closure, what
step did you use ? Using the machine's native circle command is cheating
because it is optimized to look good not be 'right' vs. sin/cos.
At 16:33 6/11/98 +0000, you wrote:
>On Fri, 6 Nov 1998, Dennis Plunkett wrote:
>
>> Ok so it was for generation, forgive me for skipping over that. As for
>> reception, the frequency range of DTMF is 697 to 1633, thus we only have to
>> sample at 3266 (Or slightly higher) the 8kHz is only for the full voice
>> stuff, in which case it would be connected to a CODEC of some type. This
>> CODEC will produce Mu LAW or A LAW compression which wouldh ave to be
>> converted to get the 16 bit value (This we would not want to do as it will
>
>Why 16 bit value ? What for ? I was cutting every corner that came my way
>just to avoid anything that may generate a carry on 8 bits when added, and
>you'd like to consider 16 bits ?
No, but I wouldn't like to add in the alternate bit inversion stuff to get
the "real" value as this too will take processing (Unless you use a look-up
table) time
>
>> introduce distortion and take up processing time). Then we have the level
>> problem, a DTMF signal must be received with a level range of 20dBm, and
>> with high to low frequency tone power of +4 to -8dBm. Also levels of less
>> than -35dBm must be rejected. On top of that the decoder must see periods of
>
>And this is ablessing, and this is what I had referred to when mentioning
>clipping decimation and a buffer storage. If all this pre-processing is
>done correctly then the lower energy frequency can probably be deduced
>from the buffer contents after the high frequency component was selected
>and removed by substraction in the first pass. Low amplitudes are rejected
>by decimation etc.
No, the levels from high to low can vary from +4dBm more to -8dBm less. The
dynamic range is 20dBm with -35dBm being the lowest value i.e The DTMF tone
can range from 0dBm0 to -20dBmO (0dBmO is typically -15dBm) this means the
DTMF decoder will have to operate in the nominal VF power range.
Noise is one of the biggest problems when detecting DTMF, on long lines the
detect period is often short, whereas on short lines the period is long.
>
>> breaks of 8 to 12mS as non valid loss (Number still OK) And must ignore a
>> signal with a tone devation of +/- 3.5%.
>
>3.5% is easy to decode with a 8kHz sample as I had described. The other
>option is, to sync the buffer fill with the higher frequency tone and
>analyze the buffer contents to get the lower frequency tone.
>
Not when you have a long line and the group delays that it encures and
attenuation distortion, frequency distortion etc. Especially if the line is
not equalized and more than 4.2Km long. These can make the simple, actually
quite hard. And on top of that the QDU (Quantization Distortion Unit) may be
high, and effect the tones.
>> So while it is possible to do a basic decode I don't think that a PIC could
>> handle a full decode.
>
>If by 'full decode' you mean, read all the 16 DTMF symbols, I think it can
>be done. If you mean, meet all the specs of a phone connectable device,
>the answer is: yes, but with some pre-filtering. This is my opinion only.
>
No by a full decode I mean one that meats all standards!
Just knocked up the Bresenham algorithm in a VB prog and it works well.
There is an error on the web site pseudo code however. In order to specify
the origin of the circle Andy quotes this as a possibility:
Sean Breheny wrote:
>
> At 03:51 PM 11/5/98 -0800, you wrote:
> >I'm not sure (I haven't tried it in other words), but I believe the y=y-1
> >statement should be part of the ELSE block that is computing 'switch =
> >switch + 4 * (x - y) + 10'. If you look at Andy's code, that line (i.e.
> >the y=y-1 line) is indented to the same level.
>
> BINGO! Thanks Scott, that was the problem. I should have been more careful
> when editing that code. The circle it produces is a bit rough, with a large
> step size between pixels. I guess that could be changed with some editing
> of the code. I really need to take a look at it to see how exactly it
> works, when I get some time (yeah, right <G>)
Bytecraft has a nifty routine that breaks the t values up
into a smallish lookup table with the slopes rather than
the values. It is extremely short. I can't copy it to the
list though, because the routine is not mine to copy.
--
Friendly Regards /"\
\ /
Tjaart van der Walt X ASCII RIBBON CAMPAIGN EraseMEtjaartwasp.co.za / \ AGAINST HTML MAIL
At 11:19 AM 11/5/98 -0800, you wrote:
>> Is there any data available on Mr. Bresenham, the person ? Web searches
>> yielded nothing interesting. Who owns these algorythms anyway ?
>
>I did a search and got only a few hits. Are you sure this is how
>Bresenham is spelled?
I have a text file which I DL'd from a BBS back in 1994 which says that he
still works for IBM. Perhaps you could check out that lead.
> On Thu, 5 Nov 1998, Peter L. Peres wrote:
>
> > the equation so the sine results from the angle and the previous sine. It
> > would be nice to find out whether this leads to the re-discovery of the
> > Goertzel formula (with which I am not familiar - i.e. I've never seen it -
> > yet).
>
> check out the 5th method on my sine web page:
>
> http://www.interstice.com/~sdattalo/technical/theory/sinewave.html
I will.
> > Is there any data available on Mr. Bresenham, the person ? Web searches
> > yielded nothing interesting. Who owns these algorythms anyway ?
>
> I did a search and got only a few hits. Are you sure this is how
> Bresenham is spelled?
That and his genius are the only 2 things I am certain of about him. His
circle algorythm is described in at least one Sedgewick algorythm book,
you should be able to get it somewhere near you (I've no idea where you
are vs. libraries/bookstores).
BTW nearly all fast & small (as in: embedded, small footprint, etc)
graphics libraries use his algorythms, or so I'm told.
> the equation so the sine results from the angle and the previous sine. It
> would be nice to find out whether this leads to the re-discovery of the
> Goertzel formula (with which I am not familiar - i.e. I've never seen it -
> yet).
At 03:51 PM 11/5/98 -0800, you wrote:
>I'm not sure (I haven't tried it in other words), but I believe the y=y-1
>statement should be part of the ELSE block that is computing 'switch =
>switch + 4 * (x - y) + 10'. If you look at Andy's code, that line (i.e.
>the y=y-1 line) is indented to the same level.
BINGO! Thanks Scott, that was the problem. I should have been more careful
when editing that code. The circle it produces is a bit rough, with a large
step size between pixels. I guess that could be changed with some editing
of the code. I really need to take a look at it to see how exactly it
works, when I get some time (yeah, right <G>)
Ben Stragnell <EraseMEsparespamspamBeGoneCODEPUPPIES.COM> wrote:
> But, each iteration does not increment t by the same amount. Each iteration st
eps one
> unit along one of the axes, and potentially one unit along the other axis, dep
ending
> on the overflow of the error term. This does not correspond to a linear increa
se in
> the angle.
You're right, for the Bresenham-style circle algorithm. But not for
the Goertzel (sp?) algorithm, which has fixed increments of t rather than
of sin(t).
> So while it is possible to do a basic decode I don't think that a PIC could
> handle a full decode.
Just a hint, but if you use that median filter thingy we've been
discussing in another thread, you'd be surprised how well the pic can
decode DTMF. Granted, there's a little bit of additional (low cost) analog
circuitry required. But it IS possible.
> Hi Scott,
>
> I just went to that link and directly converted Andy's pseudocode into
> BASIC code and it produces a diamond for me, not a circle. I tried various
> radius settings, yet the figure definately has straight sides. Maybe I'm
> doing something wrong? This algorythm just fascinates me because I don't
> understand how it works and I don't have time at the moment to figure it
> out (have to run to a meeting).
>
> Thanks, Sean
>
> P.S. The BASIC code is given below:
>
> SCREEN 12
> WINDOW SCREEN (-100, 100)-(100, -100)
> radius = 50
> x = 0
> y = radius
> switch = 3 - 2 * radius
> LOP:
> PSET (x, y): PSET (x, -y): PSET (-x, y): PSET (-x, -y)
> PSET (y, x): PSET (y, -x): PSET (-y, x): PSET (-y, -x)
> IF switch < 0 THEN switch = switch + 4 * x + 6 ELSE switch = switch + 4 *
> (x - y) + 10
> y = y - 1
> x = x + 1
> IF x <= y THEN GOTO LOP
I'm not sure (I haven't tried it in other words), but I believe the y=y-1
statement should be part of the ELSE block that is computing 'switch =
switch + 4 * (x - y) + 10'. If you look at Andy's code, that line (i.e.
the y=y-1 line) is indented to the same level.
At 02:52 PM 11/5/98 -0800, you wrote:
>One link that explains quite well is:
>
>http://www.am.qub.ac.uk/world/lists/pic/msg00334.html
>
>Yes, this was discussed on the pic list 3 years ago. And (as usual) Andy
>gave a clear explanation.
Hi Scott,
I just went to that link and directly converted Andy's pseudocode into
BASIC code and it produces a diamond for me, not a circle. I tried various
radius settings, yet the figure definately has straight sides. Maybe I'm
doing something wrong? This algorythm just fascinates me because I don't
understand how it works and I don't have time at the moment to figure it
out (have to run to a meeting).
Thanks, Sean
P.S. The BASIC code is given below:
SCREEN 12
WINDOW SCREEN (-100, 100)-(100, -100)
radius = 50
x = 0
y = radius
switch = 3 - 2 * radius
LOP:
PSET (x, y): PSET (x, -y): PSET (-x, y): PSET (-x, -y)
PSET (y, x): PSET (y, -x): PSET (-y, x): PSET (-y, -x)
IF switch < 0 THEN switch = switch + 4 * x + 6 ELSE switch = switch + 4 *
(x - y) + 10
y = y - 1
x = x + 1
IF x <= y THEN GOTO LOP
>On Fri, 6 Nov 1998, Dennis Plunkett wrote:
>
>> As this is all to do with DTMF detection I would say that while well and
>
>NO, generation. The great debate was, whether it would be possible to do
>it and have some room left over for something else in the PIC, and not use
>an output analog filter.
>
>In theory it is possible to do lookup table magic and use a PIC at 4MHz to
>output an (almost) arbitrary waveform using 8kHz (125 usec) sampling at 8
>bits parallel (into a R2R D/A or DAC08 or whatever) and have lots of time
>left over for other things. This works well, as I have written some FM
>code to interface a serial stream to radio in real time at 38400
>(simplex) and had room to spare.
>
>Peter
>
>> Also note the number of samples that would be required, as undersampling
>> could not be used successfuly (due to the short period of the tone).
>> Sampling would need to be performed at x times the max frequency (1620Hz?)
>
>Re: decoding:
>
>Sampling needs to be done at phone digitizer frequency, 8kHz, to get the
>most out of the signal. Also, I think that base clipping will yield a very
>'loud' two-tone interference pattern in a ring buffer when receiving DTMF,
>and that something or other could be done about this. It would be far from
>perfect but it could be usable for projects etc. In theory, it should be
>enough to have two full periods of the slower signal in the buffer at any
>one time to make sense of it. That would be 700Hz -> ~= 1.4msec -> * 2 =
>2.8 msec of samples, @ 125 usec ea. ~= 23 samples. Then you'd have 125
>usec to make sense of this. Assuming that a decision and an action is to
>be made on each item in the buffer while it is run through in 1 pass,
>you'd have 3 T cycles per decision + action * 23 = 69 T cycles to make
>sense of the buffer contents, leaving 56 T cycles to wait for the next
>sample. This is a PIC at 4 MHz ! My hunch is, that this could work as a
>crude DTMF decoder on a PIC. The buffer size fits in the RAM of a 16F84 if
>I'm not wrong ;)
>
>I hope that I did not goof on the figures. It's late.
>
>Peter
>
>
6/11/'98
Ok so it was for generation, forgive me for skipping over that. As for
reception, the frequency range of DTMF is 697 to 1633, thus we only have to
sample at 3266 (Or slightly higher) the 8kHz is only for the full voice
stuff, in which case it would be connected to a CODEC of some type. This
CODEC will produce Mu LAW or A LAW compression which wouldh ave to be
converted to get the 16 bit value (This we would not want to do as it will
introduce distortion and take up processing time). Then we have the level
problem, a DTMF signal must be received with a level range of 20dBm, and
with high to low frequency tone power of +4 to -8dBm. Also levels of less
than -35dBm must be rejected. On top of that the decoder must see periods of
breaks of 8 to 12mS as non valid loss (Number still OK) And must ignore a
signal with a tone devation of +/- 3.5%.
So while it is possible to do a basic decode I don't think that a PIC could
handle a full decode.
> > I did a search and got only a few hits. Are you sure this is how
> > Bresenham is spelled?
>
> That and his genius are the only 2 things I am certain of about him. His
> circle algorythm is described in at least one Sedgewick algorythm book,
> you should be able to get it somewhere near you (I've no idea where you
> are vs. libraries/bookstores).
>
> BTW nearly all fast & small (as in: embedded, small footprint, etc)
> graphics libraries use his algorythms, or so I'm told.
I did a second search, and this time I spelled Bresenham correctly (it's
not spelled Brensenham!). I now recall reading about the algorithm wrt
computer graphics a while back. It's impressive.
> As this is all to do with DTMF detection I would say that while well and
NO, generation. The great debate was, whether it would be possible to do
it and have some room left over for something else in the PIC, and not use
an output analog filter.
In theory it is possible to do lookup table magic and use a PIC at 4MHz to
output an (almost) arbitrary waveform using 8kHz (125 usec) sampling at 8
bits parallel (into a R2R D/A or DAC08 or whatever) and have lots of time
left over for other things. This works well, as I have written some FM
code to interface a serial stream to radio in real time at 38400
(simplex) and had room to spare.
Peter
> Also note the number of samples that would be required, as undersampling
> could not be used successfuly (due to the short period of the tone).
> Sampling would need to be performed at x times the max frequency (1620Hz?)
Re: decoding:
Sampling needs to be done at phone digitizer frequency, 8kHz, to get the
most out of the signal. Also, I think that base clipping will yield a very
'loud' two-tone interference pattern in a ring buffer when receiving DTMF,
and that something or other could be done about this. It would be far from
perfect but it could be usable for projects etc. In theory, it should be
enough to have two full periods of the slower signal in the buffer at any
one time to make sense of it. That would be 700Hz -> ~= 1.4msec -> * 2 =
2.8 msec of samples, @ 125 usec ea. ~= 23 samples. Then you'd have 125
usec to make sense of this. Assuming that a decision and an action is to
be made on each item in the buffer while it is run through in 1 pass,
you'd have 3 T cycles per decision + action * 23 = 69 T cycles to make
sense of the buffer contents, leaving 56 T cycles to wait for the next
sample. This is a PIC at 4 MHz ! My hunch is, that this could work as a
crude DTMF decoder on a PIC. The buffer size fits in the RAM of a 16F84 if
I'm not wrong ;)
I hope that I did not goof on the figures. It's late.
>Peter L. Peres wrote:
>
>> On Wed, 4 Nov 1998, Ben Stragnell wrote:
>>
>> > Peter L. Peres wrote:
>> >
>> > > My idea is, that since the Bresenham circle algorythm exists, it is
>> > > possible to compute the 'next' value for a phase continuous sine wave
>> > > without storing any table and by obtaining results directly in integers
>> > > (no floats no lookups no nothing).
>> >
>> > Ok... Bresenham will get you the appropriate X coordinate for iterative
>> > steps in Y (or vice versa), but then all you have is a pair of
>> > coordinates. How are you going to convert those into sines? If I
>>
>> The coordinates (one of them) IS the sine corrsponding to that cosine, and
>> vice versa. I suppose that one could turn the algorythm a little bit to
>> yield a true sine or cosine, or, use the ellipsis algorythm (by Bresenham)
>> to approximate the sine using a linear increment. Remains to be seen how
>> accurate this can be made.
>
>Trouble is, even though you're given both the sine and cosine of an angle, I
>don't think there's an easy (ie. trivial and PICable) method of knowing what
>that angle is, much less of stepping though the algorithm with fixed angular
>increments.
>
>I'm not sure about the ellipse algorithm, but I think if you try to approximate
>the sine function using the linear steps along an axis that Bresenham gives (as
>opposed to a fixed angular increment), you'll wind up approximating the sine
>function with straight lines from sin(-45 to 45), and quarter circles from (sin
>45 to 135) (the tops and bottoms of the curves). Of course this may be a good
>enough approximation for DTMF, and other applications, but it's definately
not a
>pure tone.
>
>You could always look into simple harmonic motion - keeping track of a point's
>position and velocity, and then using position to derive the acceleration each
>tick would yield a nice pure sine wave if you get the scalings right.
sin''(t) =
>-sin(t). Trouble is, to make the frequency adjustable without breaking the
>amplitude would probably require a whole nasty bunch of multiplies. Ouch :)
>
>Cheers,
>
>Ben
>
>
I have been watching this for a period of time. Yes the Bresenham stuff will
work and work well, but (don't you like that always a but) this is often
employed as an evaluated polygon with 4 seeding points. (There is some log
calculations in there too) Nominaly this will require that the software uses
floating point to get the accuracy, however if an error of a few degrees is
acceptable then it is possible not too (No calculating moon shoots with this
one!).
As this is all to do with DTMF detection I would say that while well and
good for getting the brain to function correctly, there is not a chance in
*** for the PIC to do this (At present), as the PIC would have to calculate
the 2 mixed frequencies within a frame window of than 150mS. It would be
better tha have lookup table of 90 degress then just calculate the quadrant.
There is also noise and other things to worry about, all of these make it
hard to do, but an accuracy of 99.9% is all that most carriers require.
Also note the number of samples that would be required, as undersampling
could not be used successfuly (due to the short period of the tone).
Sampling would need to be performed at x times the max frequency (1620Hz?)
> Trouble is, even though you're given both the sine and cosine of an angle, I
> don't think there's an easy (ie. trivial and PICable) method of knowing what
> that angle is, much less of stepping though the algorithm with fixed angular
> increments.
As long as we talk generating sines with a digital contraption we talk
about approximations all the time. It would help a lot to define just what
exactly a good enough approximation for DTMF is, in terms of bits
resolution and sampling speed. I'll do this here. Very roughly speaking
0.5% distortion is an error of <= 1/200 and an 8 bit digital signal
(1/256) is good enough. BUT the DTMF tones are built out of two tones
each, which must be added. Since the phone digitizers use 7 or 8 bits
(assume 8), and the power needs to be divided by 2 (roughly, between the
two tones) it follows that only 7 bits are needed to generate each DTMF
tone. Further, the tones need not be sent at full line level, and thus we
dare to steal another two bits, which leads to 6 bits per sine for each
tone (signed). Because of symmetry and sign that's 5 bits of table data
per sine. Referencing to a unity circle it follows that we really need to
store 2^5 table entries == 32 of them. With RLL compression it could be
somewhat less (I think we can afford RLL because only 5 bits of each table
entry are used). A 6 bit table stores 64 entries.
The 'better' Bresenham (?) way of getting the sine would be better iff it
would beat these numbers. Since the Bresenham algorythm yields
reasonably good approximations of integer-scaled sinuses for radiuses
larger than 1024 (10 bits) it should work the better, the more bits are to
be generated imho. But this remains to be proved. I think that the error
grows with larger radiuses.
> I'm not sure about the ellipse algorithm, but I think if you try to
> approximate the sine function using the linear steps along an axis that
> Bresenham gives (as opposed to a fixed angular increment), you'll wind
> up approximating the sine function with straight lines from sin(-45 to
> 45), and quarter circles from (sin 45 to 135) (the tops and bottoms of
> the curves). Of course this may be a good enough approximation for DTMF,
> and other applications, but it's definately not a pure tone.
There is NO digital way to obtain a 'pure tone' using a finite number of
bits per sample and a finite sampling frequency. This results directly
from the definition. It's all about approximations.
The ellipse algorythm might approximate a suitable piece of sinus using a
more or less constant step on the (ellipse-distorted) cosine axis used as
phase-incremental input. The lure is again the beauty of the Bresenham
algorythm of course ;) It would be a pity not to try hard.
> You could always look into simple harmonic motion - keeping track of a
> point's position and velocity, and then using position to derive the
> acceleration each tick would yield a nice pure sine wave if you get the
> scalings right. sin''(t) = -sin(t). Trouble is, to make the frequency
> adjustable without breaking the amplitude would probably require a whole
> nasty bunch of multiplies. Ouch :)
imho it would help a lot to start with the idea that leads to the
Bresenham circle algorythm and to develop it in a slightly different
direction. This idea is very much along the lines of using an
approximation function for a derivate of a trigonometric function over a
small (incremental) interval, which, due to the large tolerable error
(select one pixel out of 3 next possibles), leads to a fiendishly simple
algorythm. I have a hunch about being able to derive a 2nd incremental
result at each step, that accumulates to true angle at each step and turn
the equation so the sine results from the angle and the previous sine. It
would be nice to find out whether this leads to the re-discovery of the
Goertzel formula (with which I am not familiar - i.e. I've never seen it -
yet).
Is there any data available on Mr. Bresenham, the person ? Web searches
yielded nothing interesting. Who owns these algorythms anyway ?
> On Wed, 4 Nov 1998, Ben Stragnell wrote:
>
> > Peter L. Peres wrote:
> >
> > > My idea is, that since the Bresenham circle algorythm exists, it is
> > > possible to compute the 'next' value for a phase continuous sine wave
> > > without storing any table and by obtaining results directly in integers
> > > (no floats no lookups no nothing).
> >
> > Ok... Bresenham will get you the appropriate X coordinate for iterative
> > steps in Y (or vice versa), but then all you have is a pair of
> > coordinates. How are you going to convert those into sines? If I
>
> The coordinates (one of them) IS the sine corrsponding to that cosine, and
> vice versa. I suppose that one could turn the algorythm a little bit to
> yield a true sine or cosine, or, use the ellipsis algorythm (by Bresenham)
> to approximate the sine using a linear increment. Remains to be seen how
> accurate this can be made.
Trouble is, even though you're given both the sine and cosine of an angle, I
don't think there's an easy (ie. trivial and PICable) method of knowing what
that angle is, much less of stepping though the algorithm with fixed angular
increments.
I'm not sure about the ellipse algorithm, but I think if you try to approximate
the sine function using the linear steps along an axis that Bresenham gives (as
opposed to a fixed angular increment), you'll wind up approximating the sine
function with straight lines from sin(-45 to 45), and quarter circles from (sin
45 to 135) (the tops and bottoms of the curves). Of course this may be a good
enough approximation for DTMF, and other applications, but it's definately not a
pure tone.
You could always look into simple harmonic motion - keeping track of a point's
position and velocity, and then using position to derive the acceleration each
tick would yield a nice pure sine wave if you get the scalings right. sin''(t) =
-sin(t). Trouble is, to make the frequency adjustable without breaking the
amplitude would probably require a whole nasty bunch of multiplies. Ouch :)
> Peter L. Peres wrote:
>
> > My idea is, that since the Bresenham circle algorythm exists, it is
> > possible to compute the 'next' value for a phase continuous sine wave
> > without storing any table and by obtaining results directly in integers
> > (no floats no lookups no nothing).
>
> Ok... Bresenham will get you the appropriate X coordinate for iterative
> steps in Y (or vice versa), but then all you have is a pair of
> coordinates. How are you going to convert those into sines? If I
The coordinates (one of them) IS the sine corrsponding to that cosine, and
vice versa. I suppose that one could turn the algorythm a little bit to
yield a true sine or cosine, or, use the ellipsis algorythm (by Bresenham)
to approximate the sine using a linear increment. Remains to be seen how
accurate this can be made.
> Do you mean you're going to represent a sine wave as a sequence of quarter
> circles?! Hmmmm... perhaps I'm missing something?
For now, no. But I'll try to elaborate ;) It looks like a good idea,
though. Something might come from it.
> "Peter L. Peres" <plpSTOPspamspam_OUTACTCOM.CO.IL> wrote:
> > My idea is, that since the Bresenham circle algorythm exists, it is
> > possible to compute the 'next' value for a phase continuous sine wave
> > without storing any table and by obtaining results directly in integers
> > (no floats no lookups no nothing).
> [...]
> > I have not pursued the idea further for now, but based on a paper sketch
> > it should work out on 8 bit unsigned for an output precision of 6 bits
> > (for each sine wave). How does this strike you ?
>
> It is a good idea, and I've seen it done before, but I don't recall
> where. Maybe in a TI DSP apnote? Anyhow, the one I saw used a 16-bit
> accumulator, but perhaps it would work with 8-bit. As long as you can
> get through one quadrant correctly, i.e., if your scale is such that
> 0x3f is 1.0, from (0x00,0x3f) to (03f,0x00), it should work very well.
There is no question about whether Bresenham works well, the question is,
how do you extract the sine from its Cartesian coords and how to do the
'joinery'. Bresenham produces 1/8 circle segments in a Cartesian space.
You supply incremental x and it supplies incremental y. I have no time for
this now, however.
> On Wed, 4 Nov 1998, Peter L. Peres wrote:
>
> > Hello,
> >
> > a reasonably bright idea has just struck me. I have been following this
> > thread for some time and I am familiar with the table method of generating
> > a sine (quarter wave stored).
> >
> > My idea is, that since the Bresenham circle algorythm exists, it is
> > possible to compute the 'next' value for a phase continuous sine wave
> > without storing any table and by obtaining results directly in integers
> > (no floats no lookups no nothing).
>
> Enlighten my ignorance, what the hell is the 'Brensenham circle
> algorithm'? From context, I presume it's a recursive algorithm useful for
> computing the x & y coordinates of a circle as you equidistant (i.e.
No, it's an incremental algorythm that computes the y for a given x in a
Cartesian space such that when x varies from 0 to N y is the corresp.
sinus. If you plot x,y as you calculate them you obtain 1/8 circle.
There is also one for ellipses, straights and some more stuff. Look it up,
you will like it VERY much, I am sure ;)
> equiangular) steps. If that's the case, then it's not too unsimilar to the
> goertzel algorithm. The problem I've found with the goertzel algorithm is
I don't know the Goertzel. I'll look it up.
> that round off errors gradually increase to the point where sines and
> cosines are no longer produced. If you're computing a few cycles of sines
> and cosines, then the goertzel algorithm is great: it's fast and
> efficient.
Nono. The Bresenham computes nicely. The only problem is the joinery for
1/8 circles which includes a parity problem and must be solved separately
(for 1 point per circle).
> And I suspect because of round off errors you'd have to repeat this
> quarter circle calculation every quarter of a circle - unless of course
> you store the results in an array. But if you do that, you might as well
> implement the array...
It's incremental, mister. You compute it for 1/8 circle = 1/8 sine = 45
degrees. The trick is, that it does not yield a sine directly, but the
sine is included in the result (already scaled and integer). I'll try to
elaborate on this. imho this algorythm can divide the required table space
for a 1/4 sine by 4. On a PIC this should be significant. Later.