How to detect if binary number divides by 3 if transmitted MSB first

Question

How to detect if a sequence of bits, transmitted MSB first, divides by 3 ? The FSM in below question solves the problem if LSB first. FSM doesn't seem to work because adding '0' bit to left of number doesn't change the value but when adding '1' we get a new value. Why does this FSM accept binary numbers divisible by three?

Answer 1

Hint: I'm assuming you want a FSM that solves the problem, not just any algorithm. Then you can do it by using 6 states. The powers of 2 alternate between 1 and 2 modulo 3, so you need the state to store both the current reminder, and whether you have read odd or even number of digits so far.

Note: The FSM you linked works well if you pass to it the the most significant bit first. Rather, it doesn't work in reverse, so the hint is for FSM that works in reverse.