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.