Skip to main content

FSM for binary serial addition

Short answer

A Mealy machine with states s0 (carry 0, start) and s1 (carry 1). On input (x,y) LSB first, output sum = (x+y+carry) mod 2; next carry = floor((x+y+carry)/2). Example: 0111+0101 = 1100.

Design a Finite State Machine (FSM) that performs binary serial addition. Show only necessary figures and state diagrams.

Binary serial addition adds two binary numbers bit by bit, starting from the least significant bit (LSB). At each step the machine receives one bit of each number (x, y) and outputs one sum bit, and it must remember only the carry. So two states are enough.

Machine (Mealy type, output on the transition)

  • States: s₀ = carry 0, s₁ = carry 1. Start state s₀.
  • Input: a pair (x, y), x, y ∈ {0, 1}. Output: the sum bit.
  • Rule: t = x + y + carry; output = t mod 2; new carry = ⌊t/2⌋.

State table (next state / output)

State00011011
→ s₀ (carry 0)s₀ / 0s₀ / 1s₀ / 1s₁ / 0
s₁ (carry 1)s₀ / 1s₁ / 0s₁ / 0s₁ / 1

State diagram (edge label: input / output)

  00/0, 01/1, 10/1                01/0, 10/0, 11/1
       +--+                            +--+
       v  |                            v  |
    ->( s0 )-------- 11/0 ------------>( s1 )
         ^                               |
         +----------- 00/1 -------------+

Example: 0111 (7) + 0101 (5)

Feed pairs from the right (LSB first):

StepInput (x,y)State beforeOutputState after
1(1,1)s₀0s₁
2(1,0)s₁0s₁
3(1,1)s₁1s₁
4(0,0)s₁1s₀

Outputs read from the last to the first: 1100 = 12 = 7 + 5. The machine was checked against ordinary addition for all pairs of 4-bit numbers. To get a final carry, feed an extra (0,0) pair; its output is the carry.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 2 questions →