BitFlow

Serial Two's Complement Converter (Moore & Mealy)

advanced · state_machine · 350 XP

Sign in to write your solution, run it in the simulator and submit it for grading.

Sign in or create a free account →

Problem

Serial Two's Complement Converter — Moore & Mealy FSMs A **serial bit stream** arrives LSB-first. Output the two's complement of that number, also bit-serial. **Algorithm:** Pass bits unchanged until the first 1 is seen. After that, invert all subsequent bits. **Example:** `8'h05 = 0b00000101` - Bits in (LSB first): 1, 0, 1, 0, 0, 0, 0, 0 - Process: 1 (first 1, pass) → 0 (after first 1, invert) → 0 (invert) → 1 (invert) → 1 (invert) → 1 (invert) → 1 (invert) → 1 (invert) - Bits out: 1, 1, 1, 1, 1, 1, 1, 1 = `0xFB` (two's complement of 5) **Your task:** 1. **Part A:** Implement as a **Moore FSM** 2. **Part B:** Implement as a **Mealy FSM** 3. **Compare:** Count states. Explain why Mealy needs fewer states. **Interface (same for both)** | Port | Direction | Description | |------------|-----------|--------------------------------------| | `clk` | input | Clock | | `rst` | input | Async reset (both FSMs) | | `bit_in` | input | Serial input (LSB first) | | `bit_out` | output | Serial output (Moore or Mealy) | **Testbench:** Send `8'h05, 8'hFF, 8'h00` and 50 random 8-bit values. Verify output matches expected two's complement. **Professional note:** This exact problem appears verbatim in Qualcomm and MediaTek interviews.

Constraints

  • Input is LSB-first (bit 0 first, then bit 1, etc.)
  • Output is also LSB-first (same timing as input).
  • Algorithm: pass until first 1, then invert all following bits.
  • Implement both Moore and Mealy versions.
  • For Moore: output depends only on state. For Mealy: output depends on state + input.

Examples

Input: 8'h05 (LSB-first: 1,0,1,0,0,0,0,0)

Output: 8'hFB (LSB-first: 1,1,1,1,1,1,1,1)

Two's complement of 5

Input: 8'hFF (all 1s: 1,1,1,1,1,1,1,1)

Output: 8'h01 (LSB-first: 1,0,0,0,0,0,0,0)

Two's complement of -1 is 1

Input: 8'h00 (all 0s: 0,0,0,0,0,0,0,0)

Output: 8'h00 (all 0s)

Zero's two's complement is zero

Common questions

What does the Serial Two's Complement Converter (Moore & Mealy) problem ask you to build?
Serial Two's Complement Converter — Moore & Mealy FSMs A **serial bit stream** arrives LSB-first. Output the two's complement of that number, also bit-serial. **Algorithm:** Pass bits unchanged until the first 1 is seen. After that, invert all subsequent bits.
What constraints does Serial Two's Complement Converter (Moore & Mealy) have?
Input is LSB-first (bit 0 first, then bit 1, etc.); Output is also LSB-first (same timing as input).; Algorithm: pass until first 1, then invert all following bits.; Implement both Moore and Mealy versions.; For Moore: output depends only on state. For Mealy: output depends on state + input.
What is an example input and output for Serial Two's Complement Converter (Moore & Mealy)?
Input 8'h05 (LSB-first: 1,0,1,0,0,0,0,0) gives output 8'hFB (LSB-first: 1,1,1,1,1,1,1,1). Two's complement of 5
Which Verilog concepts does Serial Two's Complement Converter (Moore & Mealy) practise?
state_machine, capstone, Moore, Mealy, interview.