On 12/23/2014 1:40 AM, rickman wrote:> On 12/23/2014 1:20 AM, Rob Doyle wrote: >> On 12/22/2014 8:57 PM, rickman wrote: >>> On Monday, December 22, 2014 5:17:30 PM UTC-5, Rob Doyle wrote: >>>> On 12/21/2014 5:13 PM, Eric Jacobsen wrote: >>>>> On Sun, 21 Dec 2014 14:52:40 -0500, robert bristow-johnson >>>>> <rbj@audioimagination.com> wrote: >>>>> >>>>>> On 12/19/14 11:04 PM, Eric Jacobsen wrote: >>>>>>> On Fri, 19 Dec 2014 18:19:24 -0500, robert bristow-johnson >>>>>>> <rbj@audioimagination.com> wrote: >>>>>>> >>>>>>>> On 12/19/14 10:06 AM, rickman wrote: >>>>>>>>> I want to analyze the output of a DDS circuit and am wondering >>>>>>>>> if an FFT >>>>>>>>> is the best way to do this. I'm mainly concerned with the "close >>>>>>>>> in" >>>>>>>>> spurs that are often generated by a DDS. >>>>>>>> >>>>>>>> i still get the concepts of DDS and NCO mixed up. what are the >>>>>>>> differences? >>>>>>> >>>>>>> One is spelled DDS and the other is spelled NCO. >>>>>> >>>>>> is the NCO the typical table-lookup kind (with phase >>>>>> accumulator)? or >>>>>> can it be algorithmic? like >>>>>> >>>>>> y[n] = (2*cos(omega_0))*y[n-1] - y[n-2] >>>>>> >>>>>> where omega_0 is the normalized angular frequency of the sinusoid and >>>>>> with appropriate initial states, y[-1] and y[-2] to result in the >>>>>> amplitude and initial phase desired. >>>>>> >>>>>> is that an NCO that can be used in this DDS? or must it be LUT? >>>>> >>>>> Generally NCO or DDS refers to a phase accumulator with a LUT, since >>>>> it is easily implemented in hardware. That's a general architecture >>>>> that is well-known and can be adjusted to produce very clean local >>>>> oscillators. If somebody tried to sell me a block of IP with an >>>>> "NCO" built some other way I'd be asking a lot of questions. >>>> >>>> I have built NCOs using CORDIC rotators. No lookup tables. They >>>> pipeline >>>> nicely and are therefore very fast, they require no multipliers [1], >>>> they generate quadrature outputs for free, they can perform frequency >>>> translations for free (again no multipliers), and they are simple prove >>>> numerical accuracy. >>>> >>>> [1] Maybe not a huge issue these days. The LUT-based NCOs requires two >>>> multipliers to combine the coarse and fine LUTs (four multipliers if >>>> you >>>> need a complex NCO output) and perhaps another four multipliers if you >>>> need to do a frequency translation. >>>> >>>> Rob. >>>> >>>>>> anyway, in either case, the oscillator frequency is well defined >>>>>> and i >>>>>> don't understand why rickman would just put in a simple sharp notch >>>>>> filter tuned to the very same frequency and whack the sinusoid and >>>>>> analyze (however he does) what is residual. >>>>> >>>>> It could be because the phase accumulator/LUT architecture is general >>>>> and the range of operation of the output frequency is pretty broad. >>>>> A more generalized test approach is more flexible to testing over a >>>>> broader range of outputs. >>> >>> By fine and coarse LUTS, I assume you are referring to a linear >>> interpolation? That is what I did in a design working at audio >>> rates. With the data being shifted serially I was able to perform a >>> step and add multiply as the prior sample was being shifted out. >> >> Not linear interpolation. Simple trig identities. >> >> cos(u+v) = cos(u)cos(v) - sin(u)sin(v) >> >> where u is the coarse phase and v is the fine phase. >> >> You can get whatever accuracy you want using more and more cascaded >> lookup tables with finer and finer phase resolution. > > So the tables would be sin(u) and sin(v) with the cosine calculated by > manipulating the phase as in cos(u) = sin(u+pi/2)?Actually, I see an issue. If v is the lower bits of the phase word only v inputs would be implemented in the lower sin table. So cos(v) would require a third table. But... cos(v) ~= 1, so cos(u)cos(v) ~= cos(u) and sin(v) ~= v, which gives us cos(u) - v sin(u) with v in radians, a pretty good approximation with only 1 multiply and two tables. Likewise with the sin rule sin(a+b) = sin(u)cos(v) + cos(u)sin(v) the same approximations give us sin(u) + v cos(u). These are essentially the linear approximation I am using with one multiply and two tables.> Yeah, I can see the difference is that this requires two multiplications > and has no built in error, while linear interp only requires one > multiply but has some error which is easy to define. > > >>> Any idea of the spurs for a CORDIC technique? >> >> As you mentioned previously, there are two sources of spurs - phase >> truncation and amplitude truncation. You don't want the phase >> truncation to dominate the spurs - it is so inexpensive to remedy. >> >> The CORDIC will give you 1 bit of accuracy per iteration - i.e., the >> numerical error is cut in half with each iteration. This corresponds >> to 6dB spurious reduction per iteration (assuming no phase truncation). >> >> -120 dBc spurious requires 20 iterations. More or less. > > So phase truncation in CORDIC is determined by a constant in the math? > Make the constant and the arithmetic longer and you get better phase error?Maybe I wasn't understanding properly. Does the CORDIC algorithm process 1 bit of the input on each iteration, so that the number of iterations gives the number of phase bits used? -- Rick
Spectral Purity Measurement
Started by ●December 19, 2014
Reply by ●December 23, 20142014-12-23
Reply by ●December 23, 20142014-12-23
On 12/23/2014 10:35 AM, Eric Jacobsen wrote:> On Mon, 22 Dec 2014 15:17:23 -0700, Rob Doyle <radioengr@gmail.com> > wrote: > >> On 12/21/2014 5:13 PM, Eric Jacobsen wrote: >>> On Sun, 21 Dec 2014 14:52:40 -0500, robert bristow-johnson >>> <rbj@audioimagination.com> wrote: >>> >>>> On 12/19/14 11:04 PM, Eric Jacobsen wrote: >>>>> On Fri, 19 Dec 2014 18:19:24 -0500, robert bristow-johnson >>>>> <rbj@audioimagination.com> wrote: >>>>> >>>>>> On 12/19/14 10:06 AM, rickman wrote: >>>>>>> I want to analyze the output of a DDS circuit and am wondering if an FFT >>>>>>> is the best way to do this. I'm mainly concerned with the "close in" >>>>>>> spurs that are often generated by a DDS. >>>>>> >>>>>> i still get the concepts of DDS and NCO mixed up. what are the differences? >>>>> >>>>> One is spelled DDS and the other is spelled NCO. >>>> >>>> is the NCO the typical table-lookup kind (with phase accumulator)? or >>>> can it be algorithmic? like >>>> >>>> y[n] = (2*cos(omega_0))*y[n-1] - y[n-2] >>>> >>>> where omega_0 is the normalized angular frequency of the sinusoid and >>>> with appropriate initial states, y[-1] and y[-2] to result in the >>>> amplitude and initial phase desired. >>>> >>>> is that an NCO that can be used in this DDS? or must it be LUT? >>> >>> Generally NCO or DDS refers to a phase accumulator with a LUT, since >>> it is easily implemented in hardware. That's a general architecture >>> that is well-known and can be adjusted to produce very clean local >>> oscillators. If somebody tried to sell me a block of IP with an >>> "NCO" built some other way I'd be asking a lot of questions. >> >> I have built NCOs using CORDIC rotators. No lookup tables. They pipeline >> nicely and are therefore very fast, they require no multipliers [1], >> they generate quadrature outputs for free, they can perform frequency >> translations for free (again no multipliers), and they are simple prove >> numerical accuracy. > > CORDICs are fine when and where they make sense, but they are often > not the best tradeoff. If you have no memory, no multipliers, or > gates are way cheaper than memory, and if the latency is tolerable, > then a CORDIC may be a good option. > >> [1] Maybe not a huge issue these days. The LUT-based NCOs requires two >> multipliers to combine the coarse and fine LUTs (four multipliers if you >> need a complex NCO output) and perhaps another four multipliers if you >> need to do a frequency translation. > > Many applications don't need separate LUTs to get the required > performance, and even then, or even in the case of complex output, it > can be done without multipliers.Care to elaborate on this? I'm not at all clear on how you make a LUT based NCO without LUTs and unless you are using a very coarse approximation, without multipliers.> As is often the case, there are many ways to get the job done. > Sometimes the complications aren't necessary, they're just convenient.Yes, there is more than one way to skin a goose. But they all have their issues. CORDIC for example, has no multiplier... but has an iteration that is essentially the same as multiplication by iteration. -- Rick
Reply by ●December 23, 20142014-12-23
rickman <gnuarm@gmail.com> wrote: (snip)> Actually, I see an issue. If v is the lower bits of the phase word only > v inputs would be implemented in the lower sin table. So cos(v) would > require a third table.> But... cos(v) ~= 1, so cos(u)cos(v) ~= cos(u) and sin(v) ~= v, which > gives us cos(u) - v sin(u) with v in radians, a pretty good > approximation with only 1 multiply and two tables.There is one from a MOS handbook many years ago. (The days when MOS needed +12V power.) One ROM does the sin(u), and additional roms v*cos(u), dividing the address bits up appropriately. Then there is a TTL adder following. But that was when ROMs were smaller.> Likewise with the sin rule sin(a+b) = sin(u)cos(v) + cos(u)sin(v) the > same approximations give us sin(u) + v cos(u).> These are essentially the linear approximation I am using with one > multiply and two tables.-- glen
Reply by ●December 23, 20142014-12-23
On Tue, 23 Dec 2014 11:06:39 -0500, rickman <gnuarm@gmail.com> wrote:>On 12/23/2014 10:35 AM, Eric Jacobsen wrote: >> On Mon, 22 Dec 2014 15:17:23 -0700, Rob Doyle <radioengr@gmail.com> >> wrote: >> >>> On 12/21/2014 5:13 PM, Eric Jacobsen wrote: >>>> On Sun, 21 Dec 2014 14:52:40 -0500, robert bristow-johnson >>>> <rbj@audioimagination.com> wrote: >>>> >>>>> On 12/19/14 11:04 PM, Eric Jacobsen wrote: >>>>>> On Fri, 19 Dec 2014 18:19:24 -0500, robert bristow-johnson >>>>>> <rbj@audioimagination.com> wrote: >>>>>> >>>>>>> On 12/19/14 10:06 AM, rickman wrote: >>>>>>>> I want to analyze the output of a DDS circuit and am wondering if an FFT >>>>>>>> is the best way to do this. I'm mainly concerned with the "close in" >>>>>>>> spurs that are often generated by a DDS. >>>>>>> >>>>>>> i still get the concepts of DDS and NCO mixed up. what are the differences? >>>>>> >>>>>> One is spelled DDS and the other is spelled NCO. >>>>> >>>>> is the NCO the typical table-lookup kind (with phase accumulator)? or >>>>> can it be algorithmic? like >>>>> >>>>> y[n] = (2*cos(omega_0))*y[n-1] - y[n-2] >>>>> >>>>> where omega_0 is the normalized angular frequency of the sinusoid and >>>>> with appropriate initial states, y[-1] and y[-2] to result in the >>>>> amplitude and initial phase desired. >>>>> >>>>> is that an NCO that can be used in this DDS? or must it be LUT? >>>> >>>> Generally NCO or DDS refers to a phase accumulator with a LUT, since >>>> it is easily implemented in hardware. That's a general architecture >>>> that is well-known and can be adjusted to produce very clean local >>>> oscillators. If somebody tried to sell me a block of IP with an >>>> "NCO" built some other way I'd be asking a lot of questions. >>> >>> I have built NCOs using CORDIC rotators. No lookup tables. They pipeline >>> nicely and are therefore very fast, they require no multipliers [1], >>> they generate quadrature outputs for free, they can perform frequency >>> translations for free (again no multipliers), and they are simple prove >>> numerical accuracy. >> >> CORDICs are fine when and where they make sense, but they are often >> not the best tradeoff. If you have no memory, no multipliers, or >> gates are way cheaper than memory, and if the latency is tolerable, >> then a CORDIC may be a good option. >> >>> [1] Maybe not a huge issue these days. The LUT-based NCOs requires two >>> multipliers to combine the coarse and fine LUTs (four multipliers if you >>> need a complex NCO output) and perhaps another four multipliers if you >>> need to do a frequency translation. >> >> Many applications don't need separate LUTs to get the required >> performance, and even then, or even in the case of complex output, it >> can be done without multipliers. > >Care to elaborate on this? I'm not at all clear on how you make a LUT >based NCO without LUTs and unless you are using a very coarse >approximation, without multipliers.Not sure what you're asking. You a need a LUT, but just one in many cases. Having a dual-ported single LUT is easy in an FPGA and usually in silicon as well. What makes a multiplier necessary? I've never found the need, but my apps are limited to comm.>> As is often the case, there are many ways to get the job done. >> Sometimes the complications aren't necessary, they're just convenient. > >Yes, there is more than one way to skin a goose. But they all have >their issues. > >CORDIC for example, has no multiplier... but has an iteration that is >essentially the same as multiplication by iteration.Yup.>-- > >RickEric Jacobsen Anchor Hill Communications http://www.anchorhill.com
Reply by ●December 23, 20142014-12-23
On 12/23/2014 3:30 PM, glen herrmannsfeldt wrote:> rickman <gnuarm@gmail.com> wrote: > > (snip) > >> Actually, I see an issue. If v is the lower bits of the phase word only >> v inputs would be implemented in the lower sin table. So cos(v) would >> require a third table. > >> But... cos(v) ~= 1, so cos(u)cos(v) ~= cos(u) and sin(v) ~= v, which >> gives us cos(u) - v sin(u) with v in radians, a pretty good >> approximation with only 1 multiply and two tables. > > There is one from a MOS handbook many years ago. (The days when MOS > needed +12V power.) > > One ROM does the sin(u), and additional roms v*cos(u), dividing the > address bits up appropriately. Then there is a TTL adder following. > > But that was when ROMs were smaller. > >> Likewise with the sin rule sin(a+b) = sin(u)cos(v) + cos(u)sin(v) the >> same approximations give us sin(u) + v cos(u). > >> These are essentially the linear approximation I am using with one >> multiply and two tables.Yea, I think I've seen that or a similar one from TI. They have maybe 4 inputs to each table, really small. I saw one recently that split the phase into three ranges (again 4 bits each I believe) addressing a pair of 8 bit address ROMs. It was LUT(a+b) for the coarse sine and LUT(a+c) for the fine adjustment. -- Rick
Reply by ●December 23, 20142014-12-23
On 12/23/2014 4:48 PM, Eric Jacobsen wrote:> On Tue, 23 Dec 2014 11:06:39 -0500, rickman <gnuarm@gmail.com> wrote: > >> On 12/23/2014 10:35 AM, Eric Jacobsen wrote: >>> On Mon, 22 Dec 2014 15:17:23 -0700, Rob Doyle <radioengr@gmail.com> >>> wrote: >>> >>>> On 12/21/2014 5:13 PM, Eric Jacobsen wrote: >>>>> On Sun, 21 Dec 2014 14:52:40 -0500, robert bristow-johnson >>>>> <rbj@audioimagination.com> wrote: >>>>> >>>>>> On 12/19/14 11:04 PM, Eric Jacobsen wrote: >>>>>>> On Fri, 19 Dec 2014 18:19:24 -0500, robert bristow-johnson >>>>>>> <rbj@audioimagination.com> wrote: >>>>>>> >>>>>>>> On 12/19/14 10:06 AM, rickman wrote: >>>>>>>>> I want to analyze the output of a DDS circuit and am wondering if an FFT >>>>>>>>> is the best way to do this. I'm mainly concerned with the "close in" >>>>>>>>> spurs that are often generated by a DDS. >>>>>>>> >>>>>>>> i still get the concepts of DDS and NCO mixed up. what are the differences? >>>>>>> >>>>>>> One is spelled DDS and the other is spelled NCO. >>>>>> >>>>>> is the NCO the typical table-lookup kind (with phase accumulator)? or >>>>>> can it be algorithmic? like >>>>>> >>>>>> y[n] = (2*cos(omega_0))*y[n-1] - y[n-2] >>>>>> >>>>>> where omega_0 is the normalized angular frequency of the sinusoid and >>>>>> with appropriate initial states, y[-1] and y[-2] to result in the >>>>>> amplitude and initial phase desired. >>>>>> >>>>>> is that an NCO that can be used in this DDS? or must it be LUT? >>>>> >>>>> Generally NCO or DDS refers to a phase accumulator with a LUT, since >>>>> it is easily implemented in hardware. That's a general architecture >>>>> that is well-known and can be adjusted to produce very clean local >>>>> oscillators. If somebody tried to sell me a block of IP with an >>>>> "NCO" built some other way I'd be asking a lot of questions. >>>> >>>> I have built NCOs using CORDIC rotators. No lookup tables. They pipeline >>>> nicely and are therefore very fast, they require no multipliers [1], >>>> they generate quadrature outputs for free, they can perform frequency >>>> translations for free (again no multipliers), and they are simple prove >>>> numerical accuracy. >>> >>> CORDICs are fine when and where they make sense, but they are often >>> not the best tradeoff. If you have no memory, no multipliers, or >>> gates are way cheaper than memory, and if the latency is tolerable, >>> then a CORDIC may be a good option. >>> >>>> [1] Maybe not a huge issue these days. The LUT-based NCOs requires two >>>> multipliers to combine the coarse and fine LUTs (four multipliers if you >>>> need a complex NCO output) and perhaps another four multipliers if you >>>> need to do a frequency translation. >>> >>> Many applications don't need separate LUTs to get the required >>> performance, and even then, or even in the case of complex output, it >>> can be done without multipliers. >> >> Care to elaborate on this? I'm not at all clear on how you make a LUT >> based NCO without LUTs and unless you are using a very coarse >> approximation, without multipliers. > > Not sure what you're asking. You a need a LUT, but just one in many > cases. Having a dual-ported single LUT is easy in an FPGA and > usually in silicon as well. > > What makes a multiplier necessary? I've never found the need, but my > apps are limited to comm.Maybe we aren't on the same page. The multiplier is there for the fine adjustment. If you are happy with some -60 or -80 dB spurs one LUT is fine. But if you want better performance the single LUT approach requires *very* large tables. -- Rick
Reply by ●December 23, 20142014-12-23
this did not seem to get posted so i am reposting. sorry for any
repeated post.
On 12/22/14 5:17 PM, Rob Doyle wrote:
> On 12/21/2014 5:13 PM, Eric Jacobsen wrote:
>> On Sun, 21 Dec 2014 14:52:40 -0500, robert bristow-johnson
>> <rbj@audioimagination.com> wrote:
>>
>>> On 12/19/14 11:04 PM, Eric Jacobsen wrote:
>>>> On Fri, 19 Dec 2014 18:19:24 -0500, robert bristow-johnson
>>>> <rbj@audioimagination.com> wrote:
>>>>
>>>>> On 12/19/14 10:06 AM, rickman wrote:
>>>>>> I want to analyze the output of a DDS circuit and am wondering if
>>>>>> an FFT
>>>>>> is the best way to do this. I'm mainly concerned with the "close in"
>>>>>> spurs that are often generated by a DDS.
>>>>>
>>>>> i still get the concepts of DDS and NCO mixed up. what are the
>>>>> differences?
>>>>
>>>> One is spelled DDS and the other is spelled NCO.
>>>
>>> is the NCO the typical table-lookup kind (with phase accumulator)? or
>>> can it be algorithmic? like
>>>
>>> y[n] = (2*cos(omega_0))*y[n-1] - y[n-2]
>>>
>>> where omega_0 is the normalized angular frequency of the sinusoid and
>>> with appropriate initial states, y[-1] and y[-2] to result in the
>>> amplitude and initial phase desired.
>>>
>>> is that an NCO that can be used in this DDS? or must it be LUT?
>>
>> Generally NCO or DDS refers to a phase accumulator with a LUT, since
>> it is easily implemented in hardware. That's a general architecture
>> that is well-known and can be adjusted to produce very clean local
>> oscillators. If somebody tried to sell me a block of IP with an
>> "NCO" built some other way I'd be asking a lot of questions.
>
> I have built NCOs using CORDIC rotators. No lookup tables. They pipeline
> nicely and are therefore very fast, they require no multipliers [1],
???
i don't s'pose Ray Andraka is hanging around (he was Dr. CORDIC here a
while back), but i always thought that CORDIC did essentially
x[n] = cos(2*pi*f0/Fs) * x[n-1] - sin(2*pi*f0/Fs) * y[n-1]
y[n] = sin(2*pi*f0/Fs) * x[n-1] + cos(2*pi*f0/Fs) * y[n-1]
or, as complex numbers:
(x[n] + j*y[n]) = exp(j*2*pi*f0/Fs) * (x[n-1] + j*y[n-1])
doesn't that require a few multiplications?
> they generate quadrature outputs for free, they can perform frequency
> translations for free (again no multipliers), and they are simple prove
> numerical accuracy.
>
> [1] Maybe not a huge issue these days. The LUT-based NCOs requires two
> multipliers to combine the coarse and fine LUTs
even for linear interpolation? i think one multiplier is enough. the
higher order the interpolation, the more multipliers needed (and the
fewer points int he LUT are needed).
> (four multipliers if you need a complex NCO output) and perhaps another
> four multipliers if you need to do a frequency translation.
--
r b-j rbj@audioimagination.com
"Imagination is more important than knowledge."
Reply by ●December 24, 20142014-12-24
On 12/23/2014 6:10 PM, robert bristow-johnson wrote:> > this did not seem to get posted so i am reposting. sorry for any > repeated post. > > On 12/22/14 5:17 PM, Rob Doyle wrote: >> On 12/21/2014 5:13 PM, Eric Jacobsen wrote: >>> On Sun, 21 Dec 2014 14:52:40 -0500, robert bristow-johnson >>> <rbj@audioimagination.com> wrote: >>> >>>> On 12/19/14 11:04 PM, Eric Jacobsen wrote: >>>>> On Fri, 19 Dec 2014 18:19:24 -0500, robert bristow-johnson >>>>> <rbj@audioimagination.com> wrote: >>>>> >>>>>> On 12/19/14 10:06 AM, rickman wrote: >>>>>>> I want to analyze the output of a DDS circuit and am >>>>>>> wondering if an FFT is the best way to do this. I'm >>>>>>> mainly concerned with the "close > in" >>>>>>> spurs that are often generated by a DDS. >>>>>> >>>>>> i still get the concepts of DDS and NCO mixed up. what are >>>>>> the differences? >>>>> >>>>> One is spelled DDS and the other is spelled NCO. >>>> >>>> is the NCO the typical table-lookup kind (with phase >>>> accumulator)? or can it be algorithmic? like >>>> >>>> y[n] = (2*cos(omega_0))*y[n-1] - y[n-2] >>>> >>>> where omega_0 is the normalized angular frequency of the >>>> sinusoid and with appropriate initial states, y[-1] and y[-2] >>>> to result in the amplitude and initial phase desired. >>>> >>>> is that an NCO that can be used in this DDS? or must it be >>>> LUT? >>> >>> Generally NCO or DDS refers to a phase accumulator with a LUT, >>> since it is easily implemented in hardware. That's a general >>> architecture that is well-known and can be adjusted to produce >>> very clean local oscillators. If somebody tried to sell me a >>> block of IP with an "NCO" built some other way I'd be asking a >>> lot of questions. >> >> I have built NCOs using CORDIC rotators. No lookup tables. They >> pipeline nicely and are therefore very fast, they require no >> multipliers [1], > > ??? > > i don't s'pose Ray Andraka is hanging around (he was Dr. CORDIC here > a while back), but i always thought that CORDIC did essentially > > x[n] = cos(2*pi*f0/Fs) * x[n-1] - sin(2*pi*f0/Fs) * y[n-1] > y[n] = sin(2*pi*f0/Fs) * x[n-1] + cos(2*pi*f0/Fs) * y[n-1]Yes. So far. So good. These are my notes if anyone is interested... [snip] Assume theta = 2*pi*f0*t/fs, i.e., theta is the output of a phase accumulator for an NCO application. Factor out the cos(theta): x[n] = cos(theta) {x[n-1] - y[n-1] tan(theta)} y[n] = cos(theta) {y[n-1] + x[n-1] tan(theta)} If you select tan(theta) from the set of 1/(2**i) then [1] this becomes: x[n] = cos(theta) {x[n-1] - y[n-1] / 2**i} y[n] = cos(theta) {y[n-1] + x[n-1] / 2**i} At this point you might be thinking "Holy crap. That's one heck of a constraint!" Yeh... but keep reading anyway. You can drop the cos(theta) common term. It's just a gain term that rapidly converges to 1.647. Therefore the gain of a CORDIC is not 0 dB. x[n] = x[n-1] - y[n-1] / 2**i y[n] = y[n-1] + x[n-1] / 2**i or (assuming twos complement math) - simply: x[n] = x[n-1] - y[n-1] >> i y[n] = y[n-1] + x[n-1] >> i where >> is a shift right operation [1] As this point it seems as if an *extreme* limitation has been placed on the selection of rotation angles. The equation above only describes how to rotate an input signal by tan(theta) = 1/(2**i) - or by one of the following angles: atan(1) (45.000000000000000000000000000000 degrees) atan(1/2) (26.565051177077989351572193720453 degrees) atan(1/4) (14.036243467926478582892320159163 degrees) atan(1/8) (7.1250163489017975619533008412068 degrees) atan(1/16) (3.5763343749973510306847789144588 degrees) atan(1/32) (1.7899106082460693071502497760791 degrees) ...and so forth. The equation above does not describe how to rotate an input signal an arbitrary angle! Although this is true; all is not lost. Notice that in general that theta/2 < tan(theta). This truth allows the CORDIC to be used iteratively to rotate any input to any angle with any precision. IMO this is the genius of the CORDIC. I probably should have mentioned that you swap the rotation direction by flipping the additions and subtractions. The term z[n] is introduced to accumulate the angle as the CORDIC iterates. The term d[n] swaps the direction of rotation. Finally the familiar recursive CORDIC equation can be written as follows: x[n] = x[n-1] - d[n] y[n-1] >> i y[n] = y[n-1] + d[n] x[n-1] >> i z[n] = z[n-1] - d[n] tan(1/2**i) where: d[n] is +1 for z[n-1] < theta. Clockwise rotation next. d[n] is -1 for z[n-1] > theta. Counter-clockwise rotation next. No multiplies here. The CORDIC simply does a successive approximation to the angle - rotating the angle clockwise or counter-clockwise by these limited selection of angles as necessary to converge on the desired angle. Each time the iteration occurs, the angle error is reduced by at least half.> doesn't that require a few multiplications?Nope. Just adds/subtracts - the sign of the angle error determines which direction to rotate on the next iteration. If this is pipelined, the shifts aren't real - they just select which bits of the previous iteration are used on the next iteration. The tan(1/2**i) term is a constant for each iteration. As an implementation detail, it saves hardware if you iterate from the angle toward zero instead of from zero toward the angle. If you do that, the sign of z[i] is the direction of rotation. It saves a magnitude compare for each iteration. Rob.
Reply by ●December 24, 20142014-12-24
On 12/23/2014 11:02 PM, Rob Doyle wrote:> On 12/23/2014 6:10 PM, robert bristow-johnson wrote: >> >> this did not seem to get posted so i am reposting. sorry for any >> repeated post. >> >> On 12/22/14 5:17 PM, Rob Doyle wrote: >>> On 12/21/2014 5:13 PM, Eric Jacobsen wrote: >>>> On Sun, 21 Dec 2014 14:52:40 -0500, robert bristow-johnson >>>> <rbj@audioimagination.com> wrote: >>>> >>>>> On 12/19/14 11:04 PM, Eric Jacobsen wrote: >>>>>> On Fri, 19 Dec 2014 18:19:24 -0500, robert bristow-johnson >>>>>> <rbj@audioimagination.com> wrote: >>>>>> >>>>>>> On 12/19/14 10:06 AM, rickman wrote: >>>>>>>> I want to analyze the output of a DDS circuit and am >>>>>>>> wondering if an FFT is the best way to do this. I'm >>>>>>>> mainly concerned with the "close >> in" >>>>>>>> spurs that are often generated by a DDS. >>>>>>> >>>>>>> i still get the concepts of DDS and NCO mixed up. what are >>>>>>> the differences? >>>>>> >>>>>> One is spelled DDS and the other is spelled NCO. >>>>> >>>>> is the NCO the typical table-lookup kind (with phase >>>>> accumulator)? or can it be algorithmic? like >>>>> >>>>> y[n] = (2*cos(omega_0))*y[n-1] - y[n-2] >>>>> >>>>> where omega_0 is the normalized angular frequency of the >>>>> sinusoid and with appropriate initial states, y[-1] and y[-2] >>>>> to result in the amplitude and initial phase desired. >>>>> >>>>> is that an NCO that can be used in this DDS? or must it be >>>>> LUT? >>>> >>>> Generally NCO or DDS refers to a phase accumulator with a LUT, >>>> since it is easily implemented in hardware. That's a general >>>> architecture that is well-known and can be adjusted to produce >>>> very clean local oscillators. If somebody tried to sell me a >>>> block of IP with an "NCO" built some other way I'd be asking a >>>> lot of questions. >>> >>> I have built NCOs using CORDIC rotators. No lookup tables. They >>> pipeline nicely and are therefore very fast, they require no >>> multipliers [1], >> >> ??? >> >> i don't s'pose Ray Andraka is hanging around (he was Dr. CORDIC here >> a while back), but i always thought that CORDIC did essentially >> >> x[n] = cos(2*pi*f0/Fs) * x[n-1] - sin(2*pi*f0/Fs) * y[n-1] >> y[n] = sin(2*pi*f0/Fs) * x[n-1] + cos(2*pi*f0/Fs) * y[n-1] > > Yes. So far. So good. These are my notes if anyone is interested... > > [snip] > > Assume theta = 2*pi*f0*t/fs, i.e., theta is the output of a phase > accumulator for an NCO application. > > Factor out the cos(theta): > > x[n] = cos(theta) {x[n-1] - y[n-1] tan(theta)} > y[n] = cos(theta) {y[n-1] + x[n-1] tan(theta)} > > If you select tan(theta) from the set of 1/(2**i) then [1] this becomes: > > x[n] = cos(theta) {x[n-1] - y[n-1] / 2**i} > y[n] = cos(theta) {y[n-1] + x[n-1] / 2**i} > > At this point you might be thinking "Holy crap. That's one heck of a > constraint!" Yeh... but keep reading anyway. > > You can drop the cos(theta) common term. It's just a gain term that > rapidly converges to 1.647. Therefore the gain of a CORDIC is not 0 dB. > > x[n] = x[n-1] - y[n-1] / 2**i > y[n] = y[n-1] + x[n-1] / 2**i > > or (assuming twos complement math) - simply: > > x[n] = x[n-1] - y[n-1] >> i > y[n] = y[n-1] + x[n-1] >> i > > where >> is a shift right operation > > [1] As this point it seems as if an *extreme* limitation has been placed > on the selection of rotation angles. The equation above only describes > how to rotate an input signal by tan(theta) = 1/(2**i) - or by one of > the following angles: > > atan(1) (45.000000000000000000000000000000 degrees) > atan(1/2) (26.565051177077989351572193720453 degrees) > atan(1/4) (14.036243467926478582892320159163 degrees) > atan(1/8) (7.1250163489017975619533008412068 degrees) > atan(1/16) (3.5763343749973510306847789144588 degrees) > atan(1/32) (1.7899106082460693071502497760791 degrees) > > ...and so forth. > > The equation above does not describe how to rotate an input signal an > arbitrary angle! Although this is true; all is not lost. > > Notice that in general that theta/2 < tan(theta). > > This truth allows the CORDIC to be used iteratively to rotate any input > to any angle with any precision. IMO this is the genius of the CORDIC. > > I probably should have mentioned that you swap the rotation direction by > flipping the additions and subtractions. > > The term z[n] is introduced to accumulate the angle as the CORDIC > iterates. The term d[n] swaps the direction of rotation. Finally the > familiar recursive CORDIC equation can be written as follows: > > x[n] = x[n-1] - d[n] y[n-1] >> i > y[n] = y[n-1] + d[n] x[n-1] >> i > z[n] = z[n-1] - d[n] tan(1/2**i) > > where: > > d[n] is +1 for z[n-1] < theta. Clockwise rotation next. > d[n] is -1 for z[n-1] > theta. Counter-clockwise rotation next. > > No multiplies here.But this is the same as a multiply in terns of complexity, no? One large difference is that a multiply can be supported in commonly available hardware while this algorithm requires dedicated hardware or iterative software.> The CORDIC simply does a successive approximation to the angle - > rotating the angle clockwise or counter-clockwise by these limited > selection of angles as necessary to converge on the desired angle. Each > time the iteration occurs, the angle error is reduced by at least half. > >> doesn't that require a few multiplications? > > Nope. Just adds/subtracts - the sign of the angle error determines which > direction to rotate on the next iteration. If this is pipelined, the > shifts aren't real - they just select which bits of the previous > iteration are used on the next iteration. The tan(1/2**i) term is a > constant for each iteration. > > As an implementation detail, it saves hardware if you iterate from > the angle toward zero instead of from zero toward the angle. If you do > that, the sign of z[i] is the direction of rotation. It saves a > magnitude compare for each iteration. > > Rob.-- Rick
Reply by ●December 24, 20142014-12-24
On 12/23/2014 9:40 PM, rickman wrote:> On 12/23/2014 11:02 PM, Rob Doyle wrote: >> On 12/23/2014 6:10 PM, robert bristow-johnson wrote: >>> >>> this did not seem to get posted so i am reposting. sorry for any >>> repeated post. >>> >>> On 12/22/14 5:17 PM, Rob Doyle wrote: >>>> On 12/21/2014 5:13 PM, Eric Jacobsen wrote: >>>>> On Sun, 21 Dec 2014 14:52:40 -0500, robert bristow-johnson >>>>> <rbj@audioimagination.com> wrote: >>>>> >>>>>> On 12/19/14 11:04 PM, Eric Jacobsen wrote: >>>>>>> On Fri, 19 Dec 2014 18:19:24 -0500, robert bristow-johnson >>>>>>> <rbj@audioimagination.com> wrote: >>>>>>> >>>>>>>> On 12/19/14 10:06 AM, rickman wrote: >>>>>>>>> I want to analyze the output of a DDS circuit and am >>>>>>>>> wondering if an FFT is the best way to do this. I'm >>>>>>>>> mainly concerned with the "close >>> in" >>>>>>>>> spurs that are often generated by a DDS. >>>>>>>> >>>>>>>> i still get the concepts of DDS and NCO mixed up. what are >>>>>>>> the differences? >>>>>>> >>>>>>> One is spelled DDS and the other is spelled NCO. >>>>>> >>>>>> is the NCO the typical table-lookup kind (with phase >>>>>> accumulator)? or can it be algorithmic? like >>>>>> >>>>>> y[n] = (2*cos(omega_0))*y[n-1] - y[n-2] >>>>>> >>>>>> where omega_0 is the normalized angular frequency of the >>>>>> sinusoid and with appropriate initial states, y[-1] and y[-2] >>>>>> to result in the amplitude and initial phase desired. >>>>>> >>>>>> is that an NCO that can be used in this DDS? or must it be >>>>>> LUT? >>>>> >>>>> Generally NCO or DDS refers to a phase accumulator with a LUT, >>>>> since it is easily implemented in hardware. That's a general >>>>> architecture that is well-known and can be adjusted to produce >>>>> very clean local oscillators. If somebody tried to sell me a >>>>> block of IP with an "NCO" built some other way I'd be asking a >>>>> lot of questions. >>>> >>>> I have built NCOs using CORDIC rotators. No lookup tables. They >>>> pipeline nicely and are therefore very fast, they require no >>>> multipliers [1], >>> >>> ??? >>> >>> i don't s'pose Ray Andraka is hanging around (he was Dr. CORDIC here >>> a while back), but i always thought that CORDIC did essentially >>> >>> x[n] = cos(2*pi*f0/Fs) * x[n-1] - sin(2*pi*f0/Fs) * y[n-1] >>> y[n] = sin(2*pi*f0/Fs) * x[n-1] + cos(2*pi*f0/Fs) * y[n-1] >> >> Yes. So far. So good. These are my notes if anyone is interested... >> >> [snip] >> >> Assume theta = 2*pi*f0*t/fs, i.e., theta is the output of a phase >> accumulator for an NCO application. >> >> Factor out the cos(theta): >> >> x[n] = cos(theta) {x[n-1] - y[n-1] tan(theta)} >> y[n] = cos(theta) {y[n-1] + x[n-1] tan(theta)} >> >> If you select tan(theta) from the set of 1/(2**i) then [1] this becomes: >> >> x[n] = cos(theta) {x[n-1] - y[n-1] / 2**i} >> y[n] = cos(theta) {y[n-1] + x[n-1] / 2**i} >> >> At this point you might be thinking "Holy crap. That's one heck of a >> constraint!" Yeh... but keep reading anyway. >> >> You can drop the cos(theta) common term. It's just a gain term that >> rapidly converges to 1.647. Therefore the gain of a CORDIC is not 0 dB. >> >> x[n] = x[n-1] - y[n-1] / 2**i >> y[n] = y[n-1] + x[n-1] / 2**i >> >> or (assuming twos complement math) - simply: >> >> x[n] = x[n-1] - y[n-1] >> i >> y[n] = y[n-1] + x[n-1] >> i >> >> where >> is a shift right operation >> >> [1] As this point it seems as if an *extreme* limitation has been placed >> on the selection of rotation angles. The equation above only describes >> how to rotate an input signal by tan(theta) = 1/(2**i) - or by one of >> the following angles: >> >> atan(1) (45.000000000000000000000000000000 degrees) >> atan(1/2) (26.565051177077989351572193720453 degrees) >> atan(1/4) (14.036243467926478582892320159163 degrees) >> atan(1/8) (7.1250163489017975619533008412068 degrees) >> atan(1/16) (3.5763343749973510306847789144588 degrees) >> atan(1/32) (1.7899106082460693071502497760791 degrees) >> >> ...and so forth. >> >> The equation above does not describe how to rotate an input signal an >> arbitrary angle! Although this is true; all is not lost. >> >> Notice that in general that theta/2 < tan(theta). >> >> This truth allows the CORDIC to be used iteratively to rotate any input >> to any angle with any precision. IMO this is the genius of the CORDIC. >> >> I probably should have mentioned that you swap the rotation direction by >> flipping the additions and subtractions. >> >> The term z[n] is introduced to accumulate the angle as the CORDIC >> iterates. The term d[n] swaps the direction of rotation. Finally the >> familiar recursive CORDIC equation can be written as follows: >> >> x[n] = x[n-1] - d[n] y[n-1] >> i >> y[n] = y[n-1] + d[n] x[n-1] >> i >> z[n] = z[n-1] - d[n] tan(1/2**i) >> >> where: >> >> d[n] is +1 for z[n-1] < theta. Clockwise rotation next. >> d[n] is -1 for z[n-1] > theta. Counter-clockwise rotation next. >> >> No multiplies here. > > But this is the same as a multiply in terns of complexity, no? One > large difference is that a multiply can be supported in commonly > available hardware while this algorithm requires dedicated hardware or > iterative software.I agree that the CORDIC has the same complexity as a multiply. I agree that table-based algorithms using multipliers use less FPGA fabric. I was simply pointing out that there might be places where a CORDIC has advantages over LUT-based NCOs. Especially if have ROM or multiplier limitations. I also wanted to point out that if you need to do a 20-bit (using your 120dB example) complex downconversion for example, the CORDIC still requires zero multipliers. If you want to do a 20-bit complex downconversion using a table-based NCO followed by a complex mixer, you might need a *lot* of multipliers. If you only have an 18-bit multiplier, each multiplication requires (maybe up to) 4 multiplier blocks and you need 8 multiplications. I also /suspect/ that for any given device technology the CORDIC will execute at higher speeds. Thats all...>> The CORDIC simply does a successive approximation to the angle - >> rotating the angle clockwise or counter-clockwise by these limited >> selection of angles as necessary to converge on the desired angle. Each >> time the iteration occurs, the angle error is reduced by at least half. >> >>> doesn't that require a few multiplications? >> >> Nope. Just adds/subtracts - the sign of the angle error determines which >> direction to rotate on the next iteration. If this is pipelined, the >> shifts aren't real - they just select which bits of the previous >> iteration are used on the next iteration. The tan(1/2**i) term is a >> constant for each iteration. >> >> As an implementation detail, it saves hardware if you iterate from >> the angle toward zero instead of from zero toward the angle. If you do >> that, the sign of z[i] is the direction of rotation. It saves a >> magnitude compare for each iteration. >> >> Rob. > >
