Digital clock synthesis

This is leftover from a couple of discussions a week or two ago.
There is something interesting that I don't understand.

In general, if I have an input clock and I want to generate
an output clock, and the output clock is (much) slower than
the input clock, I can do that with a FSM.

The jitter on the output clock can be up to 1/2 of the input
clock off.  (If it's off more, move it over by one.)  If you
are lucky and the numbers work out exactly, you get no jitter.
(For example, dividing by 4.)

But how close is the frequency?  The output frequency is
  out = in * X / Y
Y is the number of states in the FSM.

Some combinations of X and Y give a better match to the
target frequency.  I'm pretty sure a math wizard would use
continued fractions to explain it.

I know how to implement this if Y is a power of 2.  That's
just an adder and it generally fits well into FPGA.  Given
a minute or 3, I can work out the value of the constant to
add.

It's easy to get closer to the target frequency by using more
bits in the adder.  If the bottom bit of the constant isn't a
1, then the adder will skip 1/2 (or 3/4 or..) of the states.
So there are sweet spots where the bottom bit of the constant
is a 1.

  This approach is also convenient if you want to make
  a sine wave rather than a square wave since you can
  feed the top N bits of the adder to a ROM lookup table.

But powers of 2 may not work as well as some simple pairs
of X and Y.  Is there a simple implementation technique
for arbitrary Y that fits well into FPGAs?  Is it something
as simple as use an adder and reset it back to 0 after Y
steps?

Is there a good web page or book that covers this area?

Next step is to understand the spectrum of the synthesised
clock.

-- 
The suespammers.org mail server is located in California.  So are all my
other mailboxes.  Please do not send unsolicited bulk e-mail or unsolicited
commercial e-mail to my suespammers.org address or any of my other addresses.
These are my opinions, not necessarily my employer's.  I hate spam.

Use Direct Digital Synthesis (DDS) which really means that you
accumulate phase angles.

Think of a 10-bit binary accumulator.
If the value you accumulate is 1, then it will take 1024 clock pulses
to overflow.
If you accumulate a 2, it will take 512 clock ticks etc.
The overflow frequency is thus determined by the 10-bit value you are
accumulating, with a resolution of 1 part in 1024 (but also with a max
jitter of half a clock period.)
With a 27-bit accumulator clocked at 100 MHz, you can generate any
integer Hz frequency, but with 5 ns jitter.
Peter Alfke, Xilinx Applications

"Hal Murray" <hmurray@suespammers.org> schrieb im Newsbeitrag
news:beudnbybkd66N13cRVn-qg@megapath.net...

> The jitter on the output clock can be up to 1/2 of the input
> clock off.  (If it's off more, move it over by one.)  If you
> are lucky and the numbers work out exactly, you get no jitter.
> (For example, dividing by 4.)
>
> But how close is the frequency?  The output frequency is
>   out = in * X / Y
> Y is the number of states in the FSM.

What you describe is called DDS, Direct Digital Synthesis. Go to
www.analog.com, they have plenty of stuff for that. And also a very good
tutorial on the toppic.

>   This approach is also convenient if you want to make
>   a sine wave rather than a square wave since you can
>   feed the top N bits of the adder to a ROM lookup table.
>
> But powers of 2 may not work as well as some simple pairs
> of X and Y.  Is there a simple implementation technique
> for arbitrary Y that fits well into FPGAs?  Is it something

Again, DDS. It look a little bit weired on the first sight, but then turn
out to a (almost) perfect oscillator.

Regards
Falk

You hit on an excellent point, that non binary values of Y indicated below
CAN be easily implemented by adding a different value to the phase
accumulator on one cycle after the phase accumulator overflows.  I used this
technique explicitly years ago to avoid some problems, adding a small delta
so I repeated the same phase values over and over.  The technique can apply
to fractions with much smaller accumulators with the added benefit of no
very-close-in spurs in your spectrum that can't be filtered out.  I put
together an Excel spreadsheet for figuring the best fractions (in order) for
a given value with nice results.  It's pretty easy to have a bound value for
most fractions with a very acceptable accuracy without the extremely low
frequency spurs.

The one caution with the overflow-based correction is that 50% duty cycle is
degraded in the simplest implementation.  If all you need is an edge or a
pulse, it's great.  If you need (closer to) 50%, you need an overflow
correction for each half of the clock cycle.

For X/Y = 12/1021, the phase accumulator normally adds 12 to a 10 bit
accumulator.  On overflow, the phase value is "behind" by 3 bits so the
phase accumulator gets 15 added for that round.  In 1021 cycles, there are
12 overflows resuling in a phase accumulator value of (1021-12)*12 + 12*15 =
12*1024.  Modulo 1024, that's back to 0.



"Hal Murray" <hmurray@suespammers.org> wrote in message
news:beudnbybkd66N13cRVn-qg@megapath.net...
> This is leftover from a couple of discussions a week or two ago.
> There is something interesting that I don't understand.
>
> In general, if I have an input clock and I want to generate
> an output clock, and the output clock is (much) slower than
> the input clock, I can do that with a FSM.
>
> The jitter on the output clock can be up to 1/2 of the input
> clock off.  (If it's off more, move it over by one.)  If you
> are lucky and the numbers work out exactly, you get no jitter.
> (For example, dividing by 4.)
>
> But how close is the frequency?  The output frequency is
>   out = in * X / Y
> Y is the number of states in the FSM.
>
> Some combinations of X and Y give a better match to the
> target frequency.  I'm pretty sure a math wizard would use
> continued fractions to explain it.
>
> I know how to implement this if Y is a power of 2.  That's
> just an adder and it generally fits well into FPGA.  Given
> a minute or 3, I can work out the value of the constant to
> add.
>
> It's easy to get closer to the target frequency by using more
> bits in the adder.  If the bottom bit of the constant isn't a
> 1, then the adder will skip 1/2 (or 3/4 or..) of the states.
> So there are sweet spots where the bottom bit of the constant
> is a 1.
>
>   This approach is also convenient if you want to make
>   a sine wave rather than a square wave since you can
>   feed the top N bits of the adder to a ROM lookup table.
>
> But powers of 2 may not work as well as some simple pairs
> of X and Y.  Is there a simple implementation technique
> for arbitrary Y that fits well into FPGAs?  Is it something
> as simple as use an adder and reset it back to 0 after Y
> steps?
>
> Is there a good web page or book that covers this area?
>
> Next step is to understand the spectrum of the synthesised
> clock.
>
> -- 
> The suespammers.org mail server is located in California.  So are all my
> other mailboxes.  Please do not send unsolicited bulk e-mail or
unsolicited
> commercial e-mail to my suespammers.org address or any of my other
addresses.
> These are my opinions, not necessarily my employer's.  I hate spam.
>

On Wed, 15 Dec 2004 15:18:31 -0600, hmurray@suespammers.org (Hal
Murray) wrote:

>This is leftover from a couple of discussions a week or two ago.
>There is something interesting that I don't understand.
>
>In general, if I have an input clock and I want to generate
>an output clock, and the output clock is (much) slower than
>the input clock, I can do that with a FSM.
>
>The jitter on the output clock can be up to 1/2 of the input
>clock off.  (If it's off more, move it over by one.)  If you
>are lucky and the numbers work out exactly, you get no jitter.
>(For example, dividing by 4.)

The peak to peak output jitter at the output can be up to 1 period of
the input clock.

You can use both edges of the input clock to halve this (assuming a
50% duty cycle).

>But how close is the frequency?  The output frequency is
>  out = in * X / Y
>Y is the number of states in the FSM.
>
>Some combinations of X and Y give a better match to the
>target frequency.  I'm pretty sure a math wizard would use
>continued fractions to explain it.
>
>I know how to implement this if Y is a power of 2.  That's
>just an adder and it generally fits well into FPGA.  Given
>a minute or 3, I can work out the value of the constant to
>add.
>
>It's easy to get closer to the target frequency by using more
>bits in the adder.  If the bottom bit of the constant isn't a
>1, then the adder will skip 1/2 (or 3/4 or..) of the states.
>So there are sweet spots where the bottom bit of the constant
>is a 1.
>
>  This approach is also convenient if you want to make
>  a sine wave rather than a square wave since you can
>  feed the top N bits of the adder to a ROM lookup table.
>
>But powers of 2 may not work as well as some simple pairs
>of X and Y.  Is there a simple implementation technique
>for arbitrary Y that fits well into FPGAs?

Yes.

The phase accumulator will always produce a frequency of the form

      c
--------------- * Fin
(2 ** num_bits)

As you point out, increasing num_bits improves the accuracy, but can
never give an exact result for some ratios.

There's a different archicture that produces a frequency of the form:

      (a + b)
----------------------- * Fin
(a * n) + (b * (n + 1))

This uses a dual modulus prescaler that divides the input clock by
either n or n+1.  An FSM twiddles the control of the prescaler to
produce the correct average division.

For a lot of practical ratios (such as those met in telecommunications
circuits) this can produce the exact ratio with the minimum jitter,
often using fewer flip flops than a comparable phase accumulator
solution.

>Is there a good web page or book that covers this area?

http://fractional-divider.tripod.com/

contains a perl script that works out the nasty details for you, then
generates synthesisable VHDL and Verilog code.

Disclaimer: I wrote the script.

>Next step is to understand the spectrum of the synthesised
>clock.

That's a little tricky, but can be done.

Regards,
Allan

>With a 27-bit accumulator clocked at 100 MHz, you can generate any
>integer Hz frequency, but with 5 ns jitter.

Thanks, but that looks like a variation on what I was asking about.

I can't see how to make a 1 Hz output with a 27 bit phase accumulator
running at 100 MHz.  Works great if I have a 134.217728 MHz clock.

If I have a 27 bit accumulator and I add 1 each cycle with a
100 MHz clock, I get 0.745 Hz.  Adding 2 makes 1.490 Hz.

Is there some variation of the simple phase accumulator that I
haven't stumbled into yet?  If so, what's the magic word?

-- 
The suespammers.org mail server is located in California.  So are all my
other mailboxes.  Please do not send unsolicited bulk e-mail or unsolicited
commercial e-mail to my suespammers.org address or any of my other addresses.
These are my opinions, not necessarily my employer's.  I hate spam.

Hal,
Make the accumulator overflow at 100,000,000 rather than at 134217728.
HTH, Syms.
"Hal Murray" <hmurray@suespammers.org> wrote in message 
news:G8udnZiTqfj5wlzcRVn-2g@megapath.net...
> >With a 27-bit accumulator clocked at 100 MHz, you can generate any
>>integer Hz frequency, but with 5 ns jitter.
>
> Thanks, but that looks like a variation on what I was asking about.
>
> I can't see how to make a 1 Hz output with a 27 bit phase accumulator
> running at 100 MHz.  Works great if I have a 134.217728 MHz clock.
>
> If I have a 27 bit accumulator and I add 1 each cycle with a
> 100 MHz clock, I get 0.745 Hz.  Adding 2 makes 1.490 Hz.
>
> Is there some variation of the simple phase accumulator that I
> haven't stumbled into yet?  If so, what's the magic word?

>What you describe is called DDS, Direct Digital Synthesis. Go to
>www.analog.com, they have plenty of stuff for that. And also a very good
>tutorial on the toppic.

Thanks.  In case anybody else gets curious:

Ask The Application Engineer-33
  All About Direct Digital Synthesis
  http://www.analog.com/library/analogDialogue/archives/38-08/dds.html

A Technical Tutorial on Digital Signal Synthesis (120 pages)
  http://www.analog.com/UploadedFiles/Tutorials/450968421DDS_Tutorial_rev12-2-99.pdf
(I haven't read it carefully yet.  Lots of good stuff.)



>> But powers of 2 may not work as well as some simple pairs
>> of X and Y.  Is there a simple implementation technique
>> for arbitrary Y that fits well into FPGAs?  Is it something
>
>Again, DDS. It look a little bit weired on the first sight, but then turn
>out to a (almost) perfect oscillator.

How do I implement a phase accumulator if Y is not a power of 2?

Suppose I want an output that is exactly 4/17 of the input.
That's almost a divide by 4.  Just need to insert an extra
stutter every 17 cycles.  I can do that with a 17 state FSM.
(34 states gets DC ballance.)

For the simple phase accumulator, the magic number to add
is 0.3C3C3C3... (hex, decimal point on the left edge)
That's a repeating fraction.  Making the accumulator bigger
will get closer, but never an exact match.  Yet a simple
17 state FSM is right on.  Is there a term for something
like that?  Is there an easy way to implement them?
(Simpler than a table driven FSM for large numbers of states.)

-- 
The suespammers.org mail server is located in California.  So are all my
other mailboxes.  Please do not send unsolicited bulk e-mail or unsolicited
commercial e-mail to my suespammers.org address or any of my other addresses.
These are my opinions, not necessarily my employer's.  I hate spam.

Hal,
For 4/17 you should implement

accum <= (accum + 4) mod 17;

Generate your output enable with an overflow signal.

Cheers, Syms.

"Hal Murray" <hmurray@suespammers.org> wrote in message 
news:ufWdnSQ3WaVF_1zcRVn-rg@megapath.net...
>
> How do I implement a phase accumulator if Y is not a power of 2?
>
> Suppose I want an output that is exactly 4/17 of the input.
> That's almost a divide by 4.  Just need to insert an extra
> stutter every 17 cycles.  I can do that with a 17 state FSM.
> (34 states gets DC ballance.)
>

>Make the accumulator overflow at 100,000,000 rather than at 134217728.

Ahh.  That seems like a key idea.  Is there a name/term for this
variation?

I've been stuck in the rut of thinking of the decimal point
to the left of the accumulator.  The top bit is the output
if you want a square wave.  Use the top N bits and a ROM
if you want a sine wave.

If I want a 50% duty cycle, I think I have to move the decimal
point 1 step to the right and "overflow" the fraction at 50,000,000.
Move it more for the sine/ROM trick.  Or something like that.
But that's just a scaling factor.

I still don't see how to easily implement "overflow" at an
arbitrary value.  Time to sleep on it.

-- 
The suespammers.org mail server is located in California.  So are all my
other mailboxes.  Please do not send unsolicited bulk e-mail or unsolicited
commercial e-mail to my suespammers.org address or any of my other addresses.
These are my opinions, not necessarily my employer's.  I hate spam.