Digital Design / Module 5: Counters and frequency dividers
30. Odd division with 50% duty cycle
Solve a favourite interview problem.
Lab: Frequency divider lab
The idea
Dividing by an odd number with a 50% duty cycle is a favourite interview question. It is hard because the output must change at a mid-cycle point. For divide-by-3, the output should be high for 1.5 input cycles, and using only rising edges you can only change on whole cycles. The answer is to use both clock edges.
The method for divide-by-3
- With rising-edge flops, make a waveform
pthat is high for 1 cycle and low for 2. - Pass it through a falling-edge flop, to get
n: the same waveform, half a cycle later. - OR the two together.
p | nstays high for 1.5 cycles out of 3, which is exactly 50%.
module div3 (input clk, rst, output out);
reg [1:0] cnt;
reg p, n;
always_ff @(posedge clk)
if (rst) begin
cnt <= 2'd0;
p <= 1'b0;
end else begin
cnt <= (cnt == 2'd2) ? 2'd0 : cnt + 2'd1;
p <= (cnt == 2'd2);
end
always_ff @(negedge clk)
if (rst) n <= 1'b0;
else n <= p;
assign out = p | n;
endmoduleOther odd numbers
For any odd N, make a rising-edge waveform high for (N-1)/2 cycles. Its half-cycle-delayed copy overlaps it, and the OR is high for N/2 cycles. Check divide-by-5: high for 2, plus half a cycle, gives 2.5 of 5.
Caveats in silicon
The result depends on both clock edges, so its duty cycle follows the input clock's duty cycle. The two paths into the OR should also be balanced, since any mismatch shifts the output edges. Combining signals with a gate on a clock path also needs care, which is why real designs use a specially built clock divider cell.
Common mistake
Quoting the design without saying how long it takes to start. It needs a reset to give a known phase. Mention that the input duty cycle must be close to 50%, too. These details are what interviewers listen for.
Key ideas
- Plain odd division can't be 50% from one edge.
- Combine a rising-edge and a falling-edge waveform.
- OR-ing them gives the 50% output, assuming matching delays.
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
always @(negedge clk)
Why it failed
The trick needs a copy delayed by half a cycle, which only a falling-edge flop can produce. With posedge, n is p delayed by a whole cycle, and OR-ing them gives 2 high cycles out of 3, or 67% duty.
Interview questions
coreDivide-by-3 with 50% duty?
Make a 1-high, 2-low waveform with posedge flops, delay it half a cycle with a negedge flop, then OR the two: high for 1.5 of every 3 cycles.
basicWhy can't a divide-by-3 with 50% duty cycle be built from rising-edge flops alone?
Rising-edge flops can only change on whole input cycles. For divide-by-3 the output period is 3 cycles, and 50% duty means high for 1.5 cycles, which needs a change in the middle of a cycle. The only edge in the middle of a cycle is the falling edge, so the design must use it.
basicFor a divide-by-5 with 50% duty cycle using the rising-edge and falling-edge method, how long is the rising-edge waveform high, and how long is the final output high?
The rising-edge waveform is high for (5 - 1) / 2 = 2 input cycles. Its copy delayed by half a cycle on the falling edge overlaps it, and the OR of the two is high for 2.5 cycles. That is 2.5 out of 5, exactly 50%.
coreIn a divide-by-3, someone takes the copy n from a rising-edge flop instead of a falling-edge flop. What duty cycle results?
always @(posedge clk) n <= p; // should be negedge assign out = p | n;
The copy is then delayed by a whole cycle instead of half a cycle. p is high for 1 cycle and n for the following cycle, so p | n is high for 2 cycles out of 3, about 67%, not 50%. Only the falling edge gives the half-cycle shift the method needs.
coreA 300 MHz clock is divided by 3 with 50% duty cycle. What are the output frequency and its high time?
300 / 3 = 100 MHz, so the period is 10 ns. With 50% duty the output is high for 5 ns, which is 1.5 input periods of 3.33 ns each.
coreThe divide-by-3 is simulated without a reset, and its output stays x. Why, and what does that tell you about the hardware?
The counter starts as x, so the compare and the increment both give x, and the counter never gets a known value; p and n follow. In hardware the flops would start at some value, but the phase relationship between p and n, and when a clean output first appears, would be unknown. A reset gives a known starting phase, which is worth mentioning whenever you present this design.
coreThis divider works for any odd N. For N = 7, how long is p high and how long is out high?
always @(posedge clk)
if (rst) begin cnt <= 0; p <= 0; end
else begin
cnt <= (cnt == N-1) ? 0 : cnt + 1;
p <= (cnt < (N-1)/2);
end
always @(negedge clk)
if (rst) n <= 0; else n <= p;
assign out = p | n;p is high when the previous count was below (7 - 1) / 2 = 3, so for 3 input cycles out of 7. n is the same waveform delayed by half a cycle, and p | n stays high for 3.5 cycles. 3.5 out of 7 is 50%, which simulation confirmed for N = 3, 5 and 7.
advancedThe divide-by-3 is fed a clock with a 40% duty cycle: high for 40% of each period, low for 60%. What duty cycle does the output have?
p is high for one full input period, from one rising edge to the next. n rises at the falling edge 0.4 of a period after p rises, and stays high one full period, so p | n is high from p's rise until 1.4 periods later. The output is high 1.4 periods out of 3, about 46.7%. The method's 50% depends on the input clock having a 50% duty cycle.
advancedCould you build the 50% divide-by-3 with an AND gate instead of an OR?
Yes, if the rising-edge waveform is changed to be high for (N + 1) / 2 cycles instead of (N - 1) / 2. For divide-by-3 it is then high for 2 cycles, its half-cycle-delayed copy overlaps it for 1.5 cycles, and the AND is high for those 1.5 cycles out of 3. Simulation gave 50% for N = 3, 5 and 7 this way. The same cautions apply: balanced paths into the gate and a 50% input clock.