write code for divide by 3 of infinite binary input stream in verilog
- User
write code for divide by 3 of infinite binary input stream in verilog
Assistant
Designing a Verilog module to divide an infinite binary input stream by 3 is an interesting problem. Since the input is a continuous (infinite) stream of bits, we need to process the number serially — one bit at a time — and compute the quotient of dividing the accumulated binary number by 3.
🔢 Problem Summary:
- Input: A serial bit stream (MSB first).
- Output: The result of dividing the accumulated value by 3.
- Constraint: We cannot store the entire number due to its infinite length.
- Goal: Compute the division modulo 3 on-the-fly using finite state logic.
✅ Key Insight
We can use modular arithmetic properties:
(A * B + C) mod N = ((A mod N) * (B mod N) + C) mod NFor binary numbers being built bit by bit:
- At each step, shift current value left (
*2), then add new bit (+ bit) - So:
value = value * 2 + new_bit
Then, since we only care about
value % 3, we can keep track of just that:remainder = (remainder * 2 + new_bit) % 3;This way, we never need to store the full number — only the current remainder modulo 3.
🧠 Verilog Implementation Overview
- Input:
clk,rst,in_bit,valid_in - Output:
remainder [1:0](since 3 needs 2 bits),valid_out - Use a 2-bit register to hold the current remainder modulo 3.
- Update it every clock cycle using the above formula.
📄 Verilog Code
module divide_by_3 ( input clk, input rst, input in_bit, // Serial input bit (MSB first) input valid_in, // Indicates valid input bit output reg [1:0] remainder = 2'd0, // Remainder of division by 3 output reg valid_out = 1'b0 // Valid output after first bit ); always @(posedge clk or posedge rst) begin if (rst) begin remainder <= 2'd0; valid_out <= 1'b0; end else if (valid_in) begin remainder <= ( {remainder, in_bit} ) % 3; valid_out <= 1'b1; end end endmodule
📈 Notes:
- This module outputs the remainder of dividing the input binary number by 3.
- If you want the quotient, not the remainder, you’ll also need to compute and track the quotient as you go. That’s more complex but doable.
- You can modify this to output both quotient and remainder with additional registers and logic.
🧮 Example:
Let's say the input stream is:
1 1 0 0→ which is12in decimal.- 12 % 3 = 0 → Output:
2'b00
Another example:
1 0 1→5 % 3 = 2→ Output:2'b10
🔄 Optional: Quotient Output
If you want the actual quotient instead of remainder, you need to build a serial divider that tracks the quotient bits as they are formed. That would require a more complex state machine or a pipeline approach.
Would you like code for computing the quotient as well?
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.