Is it divisible by 3? X80381

Design a circuit that, given an input sequence of bits, determines whether the binary number represented by the input sequence received so far is divisible by 3.

The circuit reads a new binary digit every clock cycle, corresponding to the least significant digit of the number read so far. At each clock cycle, the circuit must assert signal d if the number formed by the sequence received so far is divisible by 3.

In cycle 2, the sequence received is 110; $d$ is 1 because the binary number is divisible by 3. However, in cycle 5, the sequence received is 110100 and $d$ is 0 because the binary number is not divisible by 3.

Specification

module div3(in, d, clk, rst);
    input in, clk, rst;
    output d;

Hint

Try not to store the entire binary number, because it might be infinitely long. Also remember that 0 is divisible by 3.

Input

• clk is the clock signal.

• rst is the synchronous reset signal.

• in receives the input sequence of digits.

Output

• d is the output that indicates when the received number is divisible by 3.