circuit-fibsqrt

name

circuit-fibsqrt

description

Guide for implementing combinational/sequential logic circuits using gate-level descriptions in text-based simulators. This skill applies when building circuits for mathematical functions like integer square root, Fibonacci sequences, or similar computations that require both combinational logic (arithmetic operations) and sequential logic (feedback loops, state machines). Use this skill when the task involves generating gate netlists, implementing multi-bit arithmetic circuits, or debugging event-driven circuit simulators.

Circuit-Fibsqrt

Overview

This skill provides guidance for implementing mathematical computations as gate-level circuits. It covers combinational logic (adders, comparators, multiplexers) and sequential logic (feedback-based iteration) in text-based circuit simulators that use event-driven simulation.

When to Use This Skill

Use this skill when:

• Building circuits that compute mathematical functions (square root, Fibonacci, etc.)
• Working with text-based gate netlists (e.g., gates.txt format)
• Implementing multi-bit arithmetic operations at the gate level
• Debugging circuits in event-driven simulators with feedback loops
• Optimizing gate counts to meet resource constraints

Approach: Component-First Development

Step 1: Understand the Simulator Semantics

Before writing any circuit code:

1. Read example files carefully - Examine any provided example gate files to understand:

   • Input signal handling (e.g., out{i} = out{i} pattern for preserving inputs)
   • Gate syntax and argument ordering
   • How feedback loops are represented

2. Establish conventions - Document clearly:

   • Mux semantics: Does mux(sel, a, b) select a when sel=0 or sel=1?
   • Signal naming conventions
   • Bit ordering (LSB vs MSB first)

3. Test simulator behavior - Create minimal test circuits to verify:

   • Feedback loop behavior (toggle tests)
   • Multi-cycle convergence
   • Event-driven vs synchronous semantics

Step 2: Paper-Trace Algorithms First

Before implementing complex algorithms:

1. Work through small examples by hand - For integer square root, trace through isqrt(16), isqrt(17), isqrt(100)
2. Verify mathematical correctness - Ensure formulas are correct before coding (e.g., Newton-Raphson, binary search bounds)
3. Identify iteration counts - Determine how many iterations are needed for the input range

Step 3: Estimate Resource Usage

Before implementation:

1. Calculate expected gate counts - A 32-bit multiplier may require 30,000+ gates
2. Compare against limits - If limit is 32,000 gates, avoid multiplication-heavy approaches
3. Choose appropriate algorithms - Binary search isqrt avoids multiplication; comparison-based approaches are gate-efficient

Step 4: Build and Test Components Independently

Implement in isolation before combining:

1. Primitive gates first:

   • AND, OR, XOR, NOT
   • MUX (multiplexer)

2. Arithmetic building blocks:

   • Half adder, full adder
   • N-bit ripple-carry adder
   • N-bit subtractor (adder with inverted operand + carry-in)
   • N-bit comparator (A < B, A == B)

3. Test each component:

   • Unit test adders with known values
   • Verify comparators with edge cases (0, max value, equal values)
   • Test mux selection in both directions

Step 5: Implement Algorithm-Specific Logic

For isqrt (integer square root):

• Binary search approach: Start with bounds [0, 2^16], narrow by comparing mid^2 with input
• Avoid direct multiplication if gate-constrained; use iterative addition or precomputed squares
• Handle edge cases: isqrt(0)=0, isqrt(1)=1

For Fibonacci:

• Implement as sequential state machine using feedback
• Two registers: fib_prev and fib_curr
• Iterate based on iteration count from isqrt result
• Handle edge cases: fib(0)=0, fib(1)=1

Step 6: Combine and Integrate

When combining components:

• Use clear signal naming to track data flow
• Verify interface widths match between components
• Test the combined circuit with known input/output pairs

Verification Strategies

Unit Testing

1. Test primitives in isolation - Create separate test scripts for each component
2. Use known test vectors - For adders: 0+0=0, 1+1=2, max+1=overflow
3. Edge case coverage:
   • Zero inputs
   • Maximum value inputs
   • Boundary conditions (e.g., perfect squares for isqrt)

Integration Testing

1. Test with small inputs first - Verify fib(isqrt(1)), fib(isqrt(4)), fib(isqrt(9))
2. Verify intermediate values - Check isqrt output before Fibonacci computation
3. Test large inputs - Ensure overflow handling works correctly

Debugging Techniques

1. Add debug outputs - Temporarily expose internal signals for inspection
2. Trace signal propagation - Follow a known input through the circuit manually
3. Binary search for bugs - If output is wrong, test intermediate stages to isolate the issue

Common Pitfalls

Input Signal Handling

Mistake: Not preserving input signals in the gate file.

Solution: Many simulators require explicit input preservation:

out0 = out0   # Preserve input bit 0
out1 = out1   # Preserve input bit 1
...

Read example files to identify this pattern before implementation.

Algorithm Implementation Errors

Mistake: Implementing formulas without verification.

Example: Using test_val = 2*res + 1 when the correct formula is different for the chosen iteration method.

Solution: Paper-trace the algorithm with concrete values before coding.

Gate Count Explosion

Mistake: Using multiplication without estimating gate cost.

Example: A 32x32 multiplier can require 30,000+ gates, exceeding typical limits.

Solution:

• Estimate gates before implementation
• Prefer comparison-based or additive approaches when possible
• Consider iterative algorithms that reuse circuitry

Off-by-One Errors

Mistake: Getting fib(k-1) instead of fib(k) due to iteration count errors.

Solution:

• Clearly define what iteration 0, 1, 2, ... produce
• Trace through fib(0), fib(1), fib(2) by hand to verify indexing

Feedback Loop Confusion

Mistake: Misunderstanding how feedback stabilizes in event-driven simulation.

Example: A toggle test showing 0 after even iterations is correct, not broken.

Solution:

• Test feedback loops with minimal circuits first
• Understand that value after N steps depends on initial value and operation

Mux Argument Order

Mistake: Confusing which input is selected when selector is 0 vs 1.

Solution:

• Establish and document convention at the start
• Test with a minimal mux circuit before using in larger designs

Recommended Workflow

1. Read all provided examples and documentation
2. Paper-trace the algorithm with test values
3. Estimate gate counts for chosen approach
4. Build and test primitive gates
5. Build and test arithmetic components
6. Build and test algorithm-specific logic
7. Integrate components
8. Test with edge cases
9. Optimize if needed (reduce gates, fix bugs)

Testing Checklist

• Input signals preserved correctly
• Adder produces correct sums
• Comparator handles all cases (less, equal, greater)
• isqrt(0) = 0
• isqrt(1) = 1
• isqrt(perfect square) = exact root
• fib(0) = 0
• fib(1) = 1
• Combined circuit matches expected outputs
• Gate count within limits