DIGITAL FREQUENCY SYNTHESIZER

CROSS-REFERENCE TO RELATED APPLICATIONS

This application incorporates by reference U.S. Patent No. 6,556,089, issued on April 29, 2003, titled "Electronic Circuitry".

FIELD OF THE INVENTION

The present invention relates generally to digital frequency synthesis and more particularly to synthesized frequencies that have high accuracy and low jitter.

DESCRIPTION OF THE RELATED ART

It is desirable to create a frequency synthesis circuit having integer inputs M, N, with M/N < 1, so that a lower frequency clock can be synthesized from a rotary clock, usually running at a high frequency. Conventional synthesizers, shown in FIGs. IA and IB have problems with both jitter and cumulative inaccuracy.

Jitter results from having only a limited number of phases, as shown in FIG. IA and IB, such that if the synthesized frequency requires a phase that is not present, phases on either side of the missing phase must be used. For example, if it is desired to synthesize Tl = 4.25To, and only four phases are available, then sometimes a phase giving Tl = 4To and sometimes a phase giving Tl = 5To must be chosen to achieve the correct average period of the synthesized waveform.

Cumulative inaccuracy results from the state machine 22, in FIG. IB, using its own output as the clock. In the given example, each time the state machine 22 clocks itself from a phase that is either earlier than the correct phase or later than the correct phase, that error persists and accumulates in the output signal.

Both the jitter and cumulative inaccuracy limit the applications for such a frequency divider. Thus, it is desirable to have a digital frequency synthesizer that has lower cumulative inaccuracy and lower jitter to extend the range of applications to which such a divider an be applied.

BRIEF SUMMARY OF THE INVENTION

The present invention is directed toward such a need. The present invention employs an oscillator with p phases (as many as 32 or more) and uses a state machine that uses the p phases of the oscillator (one of which is the clock to the state machine) to synthesize a new waveform having a frequency that is controlled by two integer values, M and N, with M/N less than one. The state machine is designed to eliminate any cumulative error that can result in the synthesis operation.

Additional components, a retiming network and a combining network, achieve a synthesized clock with low jitter (low phase noise).

One embodiment of the present invention is a frequency synthesizer circuit for synthesizing a waveform having an output frequency fo. The circuit includes phase selection circuitry, a re-timing network, and clock construction circuitry. The phase selection circuitry has a clock input for receiving at least one of the plurality of phase signals of a multi-phase oscillator having a frequency fi, a pair of inputs for receiving a first integer M and a second integer N, and a plurality of phase select outputs, each of which is designed to select a phase signal of the multiphase oscillator. The phase selection circuitry is operative to activate one of the phase select outputs when a transition in the waveform of the output frequency is needed, such that there are M cycles of the output frequency for N cycles of the input frequency, and the ratio M/N is less than one. The re-timing network has a plurality of inputs that receive the plurality of signals of the multi-phase oscillator and is operative to re-time the plurality of outputs of the phase selection circuitry, such that a signal on each output is phase synchronous with the phase signal of the multi-phase oscillator that the particular output is designed to select. The clock construction circuitry is operative to construct the output frequency waveform based on the outputs of the re-timing network.

Another embodiment of the present invention is a method of synthesizing a waveform of an output frequency from the phase signals of a multi-phase oscillator which oscillates at frequency fi. The method includes (i) activating one of a plurality of phase selection output signals, where each phase selection output signal is designed to select one of the phase signals of the multi-phase oscillator, where the activated selection output signal is operative to select a

phase signal of the multi-phase oscillator on which a transition of the synthesized waveform should occur, such that there are M cycles of the output frequency for N cycles of the input frequency and the ratio M/N is less than one, and where the selected phase signal is such as to prevent accumulation of any error in the output frequency, (ii) retiming the activated phase selection output signal to be synchronous with the phase signal of the multi-phase oscillator the selection signal is designed to select, (iii) selecting a phase signal of the multi-phase oscillator using the retimed phase selection output signal, (iv) and combining each selected phase signal of the multi-phase oscillator to form the waveform of the output frequency.

Yet another embodiment of the present invention is a method of synthesizing a waveform of an output frequency from the phase signals of a multi-phase oscillator that includes (i) activating one of a plurality of phase selection output signals, where the activated selection output signal selects a phase signal of the multi-phase oscillator on which a transition of the synthesized waveform should occur, such that there are M cycles of the output frequency for every N cycles of the input frequency and the ratio M/N is less than one, where the activated selection output signal selecting the phase signal that prevents any accumulation of error in output frequency, (ii) retiming the activated phase selection output signal to be synchronous with the phase signal of the multi-phase oscillator the selection signal is designed to select, (iii) and combining each retimed activated phase selection output signal to form the waveform of the output frequency.

An advantage of the present invention is that there is no accumulation of error in the synthesized output frequency leading to greater accuracy in the output frequency, which makes the invention useful for a greater variety of applications.

Another advantage of the present invention is that jitter can be held to a minimum by using a large number of phase signals.

Yet another advantage is that the amount of circuitry needed to implement the present invention does not increase by a large factor when a large number of phase signals of a multiphase oscillator is used.

Yet another advantage is that, because of the small amount of circuitry needed to implement the present invention, the invention can be used in multiple places in a design to create a fully phase coherent system.

Yet another advantage is that the state machine in the phase selection circuitry need only operate at the frequency of the multiphase oscillator, no matter how many phases of the oscillator are available.

BRIEF DESCRIPTION OF THE DRAWINGS These and other features, aspects and advantages of the present invention will become better understood with regard to the following description, appended claims, and accompanying drawings where:

FIGs. IA and IB show block diagrams of conventional circuitry for creating a waveform having a desired frequency;

FIG. 2 A shows block diagram in accordance with an embodiment of the present invention;

FIG. 2B shows an embodiment of the state machine circuitry for use in the phase selection circuitry of the present invention;

FIG. 2C shows an embodiment of the encoding and decoding circuitry for use in the phase selection circuitry of the present invention;

FIG. 2D shows a general embodiment of the encoding and decoding circuitry for use in the phase selection circuitry of the present invention;

FIG. 2E shows the algorithm implemented by state machine circuitry of the present invention;

FIG. 3A shows a timing chart for the phase selection algorithm described in the flow chart of FIG. 2E;

FIG. 4 shows an embodiment of the retiming network of the present invention;

FIG. 5 shows a timing diagram for an embodiment of the retiming network of the present invention;

FIG. 6A shows a first embodiment of a clock edge combiner network for use in the clock construction circuitry;

FIG. 6B shows a second embodiment of a clock edge combiner network for use in the clock construction circuitry;

FIG. 7 shows one application of the frequency synthesizer of the present invention; and

FIG. 8 shows another application of the frequency synthesizer of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 2A shows block diagram the circuitry 50 of the present invention. The blocks include a multi-phase oscillator 52, phase selection circuitry 56, a retiming network block 64, and clock construction circuitry 68.

The multi-phase oscillator 52 provides a plurality p of phases, (p _v ..p _p ) 54, at a given frequency / ₀ . In one embodiment, the multi-phase oscillator 52 is a rotary traveling wave oscillator described in U.S. Patent No. 6,556,089.

The phase selection circuitry 56 is clocked by one of the phases (pi is shown) of the oscillator and, using the two integers M 58 and N 60, provides the p phase select signals S ₁ ... s _p

62, only one of which is active at any given time. The phase selection circuitry 56 implements an algorithm that prevents errors from accumulating in the synthesized frequency by selecting, at each selection time, a phase with the least error. A selection time is the point in time at which a transition of the output frequency is required. Thus, if the output frequency has a period that is 4.25 times the period of the input frequency, then there is a selection point every 4.25 cycles of the input frequency.

The retiming network 64 receives thep phase select signals (S ₁ ...s _p ) 62 from the phase selection circuitry 56 and the p phases (p _x - --p _p ) 54 of the multi-phase oscillator 52 and positions, in time, the phase select signals to have a phase that is consistent with the phase being selected by the signal. Thus, if a phase 2 select signal is active, then it is re-timed to occur on phase 2 of the multi-phase oscillator. The re-timed signals 66 are designated (rs _λ ...rs _p ).

The clock construction circuitry 68 receives the p retimed select signals (Vs ₁ ...rs _p ) 66 and optionally, the phase signals 54 from the multi-phase oscillator 52, to construct the synthesized clock Z ₁ 70 at the desired frequency /j = (M /N)f ₀ , where M 58 and N 60 are integers and the ratio M/N is less than 1.

FIG. 2B shows an embodiment of the state machine circuitry 80 for use in the phase selection circuitry 56 of the present invention. The state machine circuitry 80 comprises a collection of adders and multipliers 82, 84, 86 and an accumulator, called the D-register, for holding an accumulating decision parameter used by the phase select retiming network to create the phase select outputs. The adders and multipliers 82, 84, 86 operate on the integers M and N supplied to the state machine to implement an algorithm for selecting the phase with the least error in the construction of the new frequency. In one embodiment, the Bresenham line drawing algorithm is used.

In a rasterization application there are a limited number of pixel locations in an array available for selection when drawing a straight line. This requires, for most lines, that a choice be made of the pixel closest to the desired line. The Bresenham algorithm is designed to make these choices so as to prevent the cumulative error when drawing the line. Ideally, for line drawing, each step (1...n) in the x-direction (assuming a slope less than one) is taken to be a unit step and each increment in the y-direction is taken to be the slope m of the line, according to the equation y = mx . However, because there is a discrete number of pixels available, selection of an actual pixel at the exact position needed in the y-direction is usually not possible. In the y- direction, either the current or next pixel in the y-direction must be chosen (i.e., y-value must be incremented by 0 or 1), because of the lack of intermediate values. In the Bresenham algorithm, the rule for the first pixel is the following:

0 ≤ m < > y = y + 0 (1)

- ≤ m ≤ l -> y = y + l (2)

Thus, if the y-increment is closer to zero than to 1, zero is chosen, otherwise 1 is chosen. This guarantees that the error is never more than 1/2 of a pixel. To simplify the test, the slope m is restricted, {m : 0 < m ≤ 1} , and the quantity 1/2 is subtracted from the inequality, resulting in the following tests:

I m — ) < 0 -> y = y + O (3)

0 < \ m — I → y = y + l (4).

Given that the slope m = Ay/Ax where δx is the total integer number of steps in the x- direction and Ay is the total integer number of steps in the y-direction, if the tests are scaled with the quantity 2Ax , then only integer calculations are needed. Tests (3) and (4), which are for the first pixel, then become

(e = 2δy - δx) < 0 → y = y + 0 (5) (e = 2Ay - Ax) ≥ 0 -> ^ = .y + l (6).

Thus, for n = 1 , e _x = 2Ay — Ax is tested. For n > 1 , the quantity e _n = e _n _ _x + 2Ay is tested. If y is incremented (because the tested quantity is positive), an adjustment is made e _n = e _n _ _j + 2Ay - 2δx: prior to the next test (so that the same test applies after y is incremented).

In the case of synthesizing a new frequency, instead of drawing a line, there is a limited number of phase steps (instead of pixels) that are available.

FIG. 2E shows the algorithm 160 implemented by state machine circuitry of the present invention as applied to phase steps. In step 162, the parameter e is initialized to 2Mp-Np. A loop 164 is then entered. In the loop the following occur. For each phase step from 1 to Np phases, the parameter e is tested, in step 166, to see if it is greater than zero. If the parameter e is negative,

then the current phase is used at the transition of the output frequency, in step 168, and the parameter e is modified by adding, in step 172, the quantity 2Mp to it. The counter is incremented and the loop continues. If the parameter e is positive (as a result of adding quantity Mp to e a number of times), as determined in step 166, then a new phase is selected at the transition of the output waveform, in step 170. The parameter e is modified by subtracting -2Np, in step 174, and adding 2Mp, in step 172. The -Np corrects the parameter e so that the same test works after the phase is advanced.

The result is that the algorithm selects a phase that minimizes the error in the output frequency, i.e., it selects the phase that maintains the line in FIG. 3A, if possible. (There is no error if the new frequency can be synthesized using the existing phases. The error occurs when a needed phase is not present for a given M/N ratio.) Referring to the figure, a number of phase steps is advanced along the x-axis for a period T ₀ of the input frequency / ₀ , and a number of phase steps is advanced along the y-axis for a period T ₁ of the output frequency /j , according to the integer ratio M/N. For example, suppose the output period is desired to be 4.25T ₀ , i.e.,

TV 17 T ₁ = — T ₀ or T _x = — T ₀ , using integers. Then, there are 17 periods of To advanced for every for M 4 four periods of Tl. If the multi-phase oscillator has four phases in its period, the slope, m = Ay/ Ax = Mp I Np , of the phase line is 16/68, as shown in FIG. 3A. As can be observed from the figure, the phase selections pi, p2, p3 and p4, maintain a linear relationship between the input period and output period, hi this case, there is no error in the output frequency.

The numeric values for 2Mp, 2Np, the initial value Q _\ , and the correction when y is incremented, respectively, are:

2Mp= 32, 2Np = 136 e _x = 2Mp - Np -= -36, 2Mp - 2Np = -104

Applying the algorithm shown in FIG. 2E for each To clock yields the following table.

Inspection of the table and FIGs. 3 A, 3B and 5 shows how the phase to be selected advances every 17 phase steps. For the first 17 phases, phase 2 is the proper selection for the transition of the output frequency. For the second 17 phases, phase 3 is the proper selection for the transition; for the third 17 phases, phase 4, and for the fourth 17 phases, phase 1. To make the generation of the phase select signals easier, the error value e has the initial offset e; removed in the D column, and the implementation in FIG. 2B reflects this. Also, it should be noted that the numbers in the/ ₀ cycle column of the table represent a count of the cycles of the input oscillator, which is 1/4 the number of phase steps, in the example. This has the advantage of filtering out all but one point at which the parameter e (D-register less the initial offset) turns positive during the output period.

FIG. 2C shows an embodiment of the encoding and decoding circuitry 120 for use in the phase selection circuitry of the present invention. The encoding and decoding circuitry includes a D-to-binary conversion block 122 that receives the contents of the D register, less the quantity Np (vx bus), and creates a p-bit binary number 126 (two bits, blbO, for the example shown) for the next phase select signal to be activated. While the example shown is for two bits, the number of bits depends on the number of phases into which a cycle of the multi-phase clock is divided.

The binary decoder 128 then receives the binary number for the next phase select signal and decodes it into the p phase select signals (s _x .. ,s _p ) 54. According to the diagram, the p phase select signals 54 are enabled to be active from the decoder 128 when the circuitry 90 in FIG. 2B detects a greater than zero condition for the current value of D+2Mp-Np (decision = true).

Continuing with the example above, where p = 4, the binary conversion block 122 implements the map (D+2Mρ-Np) → blbO: 64→ 11, 56-> 10, 48 -> 01, 40 → 00.

In one embodiment, the binary conversion block includes a plurality of adder/subtractor units and pipeline registers, 130a,b, 132a,b 134a,b. Adder/subtractor unit 130a adds the product 2Mp to the quantity (D-Np) on the vx bus 124 to start the calculations. Adder/subtractor units 132a and 134a implement the map (D+2Mρ-Np) → blbO, for the different values of D. The pipeline registers capture the value of the adder/subtractor units in parallel with the update to the accumulator 88. (This means that the binary conversion block operates on D values that are one clock cycle prior to the point at which the parameter e goes positive). The advantage of the embodiment in FIG. 2C is that no binary dividers, which can slow down the calculations, are used; the only divisions, divide by 2 and divide by 4, that are needed are ones that can be performed by a shift register. Another advantage of this embodiment is that only log ₂ p stages of adders/subtractor circuits are needed to implement the map, which makes it feasible to have a large number of phases in the multiphase oscillator. For example, if the multi-phase oscillator has a 1024 phases, only 10 stages are needed (in addition to the first).

Continuing with the example,

when D = 32 (value of D before e goes positive) then:

and these values are latched into the pipeline registers and the accumulator on the next clock edge.

When D = 24, then:

As is clear, from FIGs. 2B and 2C, the parameter e (D+2Mp-Np) is used to start the calculations. The quantities 2Mp, 2Np, and Np are computed by binary multiplication, preferably by using a shift register when p is a power of 2. The quantities 2Mp/2...2Mp/p can also be computed by using shift registers when p is a power of 2.

The binary decoder in FIG. 2C then decodes the binary number for the next phase select signal to create the four phase select signals {s _λ ... s _p ) . In the example shown in the figure, the decoder implements the map, blbO — > (s, ... S ₄ ) :

OO→IOOO (which selects phase 1) 01 ->0100 (which selects phase 2)

10 →OOIO (which selects phase 3)

11 -»0001 (which selects phase 4).

Thus, at any point in time at which a transition must be created, one of the phase select signals is chosen, based on the algorithm, to select the phase with the least error.

FIG. 2D shows a general embodiment 140 of the encoding decoding circuitry for use in the phase selection circuitry of the present invention. There is an initial stage for computing the

parameter e, and thenlog ₂ p subsequent stages in the encoding block 142. The decoder decodes the log ₂ p binary signals, one from each of the stages.

FIG. 4 shows an embodiment of the retiming network 64 of the present invention. The phase select signals 62 leaving the arithmetic unit are synchronous with the clock used for that unit, specifically one of the phases of the multi-phase clock (phase 1 53 is shown in FIG. 2A). In order to synthesize to the desired frequency, with the phase accuracy available from the multiphase clock, these signals must be made synchronous with the phase signals they select, if active. The network 64 thus includes circuitry that receives each of the phase select signals 62 and re- clocks the signals to have the actual phase that the name of the phase select signal implies. Thus, phase select signal J ₁ is re-clocked so that it exits the retiming network as rsl, with phase 1 timing; phase select signal S ₂ is re-clocked to exit the network as rs2 with the timing of phase 2; and similarly for the other ones. The circuitry included in this stage includes a chain of flip-flops 200, 202, each clocked with a different phase signal of the multiphase oscillator such that the re- clocked signal that emerges has the proper timing. For a signal that is distant in phase from the clock for the arithmetic unit (phase I) ₅ several ranks 204, 206, 208 of flip-flops in the chain, clocked from different phases of the multi-phase clock, may be needed to properly retime the signal. For example, the signal S ₄ , which starts synchronous to the pi phase, needs to be reclocked with the p2 phase, the p3 phase, and the p4 phase to emerge with correct timing. Signals that do not need as many ranks of flip-flops must have delays 210, 212 inserted so that these signals emerge with the proper relationship to the other retimed signals. Optimizations of the re-timing network are possible for phase select signals requiring a phase distant in time from the clock that is used to run the state machine. For example, a signal si 6, which starts synchronous to pi, would, in one embodiment, require p2, p3, p4, p5, p6, p7, p8, p9, plO, pi 1, pl2, pl3, pl4, pl5 and pl6 to exit with the timing of pl6. However, it may be possible, with 16 phases, to skip every other phase, in synchronizing to pi 6. In general, not all phases of the multiphase clock may be needed to re-time such signals, when there are a large number of phases, thus making the chain of flip-flops smaller.

FIG. 5 shows a timing diagram for an embodiment of the retiming network of the present invention in which there are four phase signals pi, p2, p3, p4 available from the multiphase

oscillator. Signals si, s2, s3 and s4 are synchronous with the edges of one of the phases (pi in this case) of the multiphase oscillator. Signals rsl, rs2, rs3, and rs4 are synchronous with the phase for which they are labeled. Signals rsl, rs2, rs3 are thus positioned to properly select the corresponding phases of the multi-phase clock. Signals rsl ...rs4 are used to construct the waveform of the output clock.

After retiming, the re-timed signals (^ ₁ ... rs _p ) 66 are then used to construct the synthesized output clock. FIG. 6A shows a first embodiment of a clock edge combiner network for use in the clock construction circuitry and FIG. 6B shows a second embodiment of a clock edge combiner network for use in the clock construction circuitry.

Li FIG. 6 A, each of the retimed signals is taken from the last rank of the retiming network 64 and buffered by buffers 240 to control switches 242 that enable the actual phase signals 54 (p _v ..p _p ) of the multi-phase oscillator 52 to be multiplexed into the output clock node

70.

In FIG. 6B, the re-timed signals taken from the last rank of the retiming network 64 are simply OR'ed together in gate 244. This is not as accurate as the first embodiment, as there is a flip-flop delay between the actual phase signal of the multi-phase oscillator and the output, but may be acceptable in some circumstances.

FIG. 7 shows one of many applications 260 of the frequency synthesizer of the present invention. A multiphase clock such as a rotary traveling wave oscillator 262 is setup to provide and distribute multiple phases to a plurality of blocks 264, 266, 268, 270 on an integrated circuit. Each of the blocks, a PCI block 264, a Graphics Interface block 266, a Co-processor block 268, and a memory bus block 270, has a need for a different frequency of operation which may be optimal for the functions the block carries out. A PCI block 264 for example, may need to operate at 2.5 GHz, the Graphics Interface block 266 may need to operate at 8 GHz, the Co- processor 268 may need to operate at 3.0 GHz and the memory block 270 may need to operate at 1.25 GHz. This creates a problem when the blocks need to communicate between each other. If the different frequencies are not coherent, synchronizers must be used. This causes a loss in communication speed between communicating blocks and introduces a serious chance of

communication error, unless careful design techniques are followed. However, using the frequency synthesizer of the present invention, these problems are avoided, because the entire system 260 is phase coherent. This is true because the output frequencies fl, f2, f3, and f4 of the present invention synthesizer are phase coherent with the multi-phase oscillator 262. Thus, phase coherent communication is always possible between the blocks 264, 266, 268, 270. The particular phase in each block in which safe communication to another block is allowed can be known by the blocks and only in that phase will the block permit communication to the other block. The particular phase for which communication is safe between blocks may be different for each different pair of blocks. Coherent communication speeds up the interaction between the blocks and eliminates a source of error in design.

FIG. 8 shows another application of the frequency synthesizer of the present invention. This application, a phase locked loop, includes a multiphase oscillator 302 providing p phases, a frequency synthesizer 304 with input M and N that determine the output frequency of the synthesizer, a phase/frequency comparator 306, and low pass filter 308 for controlling the frequency and phase of the multiphase oscillator. The phase locked loop 300, when locked, causes the output frequency of the multiphase oscillator to be coherent with the reference REF and a multiple of the output frequency of the frequency synthesizer. In this case the multiple is N/M. Thus, the output frequency is a phase coherent multiple of the reference signal REF.

Although the present invention has been described in considerable detail with reference to certain preferred versions thereof, other versions are possible. Therefore, the spirit and scope of the appended claims should not be limited to the description of the preferred versions contained herein.