---
title: "FSM for binary serial addition"
subject: "Discrete Structure"
chapter: 2
key: "semester_4/discrete_structure:fsm-binary-serial-addition"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/fsm-binary-serial-addition
site: BCT Engineering
---

# FSM for binary serial addition

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2070 Bhadra, 3 marks
- Video: [1-23 Design of Mealy Machine for Addition of Two Binary Numbers](https://www.youtube.com/watch?v=SGRlmLIgUoM) — Dr. Sagarkumar Badhiye
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/fsm-binary-serial-addition
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2

## Question

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

## 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.

## Answer

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)**

| State | 00 | 01 | 10 | 11 |
|---|---|---|---|---|
| → s₀ (carry 0) | s₀ / 0 | s₀ / 1 | s₀ / 1 | s₁ / 0 |
| s₁ (carry 1) | s₀ / 1 | s₁ / 0 | s₁ / 0 | s₁ / 1 |

**State diagram** (edge label: input / output)

```text
  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):

| Step | Input (x,y) | State before | Output | State after |
|---|---|---|---|---|
| 1 | (1,1) | s₀ | 0 | s₁ |
| 2 | (1,0) | s₁ | 0 | s₁ |
| 3 | (1,1) | s₁ | 1 | s₁ |
| 4 | (0,0) | s₁ | 1 | s₀ |

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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does the serial adder need to remember between steps?
   A. The whole first number
   B. The carry (0 or 1), so two states are enough
   C. The previous sum bit
   D. The number of bits read
   Answer: B. Each sum bit depends only on x, y and the carry. (Key point: What is remembered)

2. Which rule gives the output and next state?
   A. output = x AND y; carry = x OR y
   B. output = floor(t/2); carry = t mod 2
   C. t = x + y + carry; output = t mod 2; new carry = floor(t/2)
   D. output = x + y; carry unchanged
   Answer: C. This is the full-adder rule, with sum bit and carry out. (Key point: Rule)

3. From s1 (carry 1), what happens on input 00?
   A. Output 1 and go to s0
   B. Output 0 and stay in s1
   C. Output 1 and stay in s1
   D. Output 0 and go to s0
   Answer: A. t = 0 + 0 + 1 = 1, so sum bit 1 and carry 0. (Key point: Transition from carry state)

4. In which order are the bits fed in?
   A. Most significant bit first
   B. Least significant bit first
   C. Alternating from both ends
   D. Any order
   Answer: B. Carries propagate from low to high bits. (Key point: Bit order)

## Related in Discrete Structure

- [Differentiate Finite State Machine and Automata](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsm-vs-fsa-difference) — Discrete Structure, chapter 2, asked 2×
- [Define FSM; design FSA with two consecutive a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-two-consecutive-a) — Discrete Structure, chapter 2, asked 4×
- [Design NFA for strings ending with aba](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Anfa-strings-ending-aba) — Discrete Structure, chapter 2
- [Design FSA for strings beginning with baa](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-strings-beginning-baa) — Discrete Structure, chapter 2

## Related in other subjects

- [39 to binary/hex and 2's complement addition](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Aconvert-39-binary-hex-addition) — Digital Logic, chapter 1
- [Create classes from design class diagrams](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Aclasses-from-design-class-diagram) — Object Oriented Analysis and Design, chapter 4, asked 2×
- [Sequence detector 1101 FSM and VHDL](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-sequence-detector-1101) — Embedded System, chapter 9
- [Ageing, its minimization and silicon addition](https://www.bctengineer.com/question.md?key=semester_5%2Felectric_machine_design%3Aageing-minimize-silicon-merits) — Electric Machine Design, chapter 1