Hardware LDS with CORDIC

---

# 🧮 Hardware Low-Discrepancy Sequences

### van der Corput → CORDIC → Unit Sphere 🌍

### From C++ to Silicon 🔄

@luk036 · 2026-06-17

---

### 📋 Agenda

**1. Low-Discrepancy Sequences** 🎯
- van der Corput base-2 🔄
- Base-3 / Base-7 with 2^n-1 trick ✨
- Pre-computed integer factors 📦

**2. CORDIC Algorithm** ⚙️
- Circular mode: sin / cos 🔄
- Hyperbolic mode: sqrt(x) 🌊
- Hardware architecture 🏗️

]

**3. Hardware Modules** 🧩
- Circle: unit circle points 🌐
- Disk: unit disk points 🥏
- Sphere: unit sphere points 🌍
- Module reuse map 🗺️

**4. Tool Flow** 🔬
- iverilog testbenches ✅
- Yosys synthesis 🛠️
- JSON netlist validation 📋

**5. Bug Stories** 🐛

]

---

## 🎯 Low-Discrepancy Sequences

### 🤔 What is a van der Corput Sequence?

Reverse integer n in base b, map to [0, 1):

```
VdC<2>(1) = 0.1(2) = 0.50     binary: 1 -> 0.1
VdC<2>(2) = 0.01(2) = 0.25    binary: 10 -> 0.01
VdC<2>(3) = 0.11(2) = 0.75    binary: 11 -> 0.11
VdC<2>(4) = 0.001(2) = 0.125  binary: 100 -> 0.001
```

The sequence fills [0, 1) more evenly than random sampling 📊

---

### 🪄 Base-2: Pure Bit Reversal

.mermaid[
<pre>
graph LR
    subgraph "16-bit Counter"
        C["cnt = 3 = 0000 0000 0000 0011"]
    end
    subgraph "vdc_out = Bit-Reverse"
        R["vdc_out = 1100 0000 0000 0000 = 0xC000"]
    end
    C -->|"wire permutation"| R
    style C fill:#2e3440,stroke:#88c0d0,color:#eceff4
    style R fill:#2e3440,stroke:#a3be8c,color:#eceff4
</pre>
]

**Hardware cost: ZERO logic gates** 🔥

```verilog
// vdc_16.v -- bit reversal is pure wiring
assign vdc_out = {
    cnt[ 0], cnt[ 1], cnt[ 2], cnt[ 3],
    cnt[ 4], cnt[ 5], cnt[ 6], cnt[ 7],
    cnt[ 8], cnt[ 9], cnt[10], cnt[11],
    cnt[12], cnt[13], cnt[14], cnt[15]
};
```

Only 17 DFFs needed (16-bit counter + valid flag) ✅

---

### ✨ Base-3 and Base-7: The 2^n - 1 Trick

When base = 2^n - 1, modulo uses **bit-chunk summation** instead of division:

```
Base 3 = 4 - 1  (n=2): sum 2-bit chunks
Base 7 = 8 - 1  (n=3): sum 3-bit chunks
```

.mermaid[
<pre>
graph TD
    subgraph "Modulo 3 via 2-bit chunks"
        X["16'hCAFE"] --> S["split into 2-bit groups"]
        S --> A["10 + 10 + 10 + 11 + 11 + 11 + 11 + 10"]
        A --> R["result = sum mod 3"]
    end
    style X fill:#2e3440,stroke:#88c0d0,color:#eceff4
    style R fill:#2e3440,stroke:#a3be8c,color:#eceff4
</pre>
]

**Division via magic constant** (x * C) >> S:

| Base | Magic Constant | Shift | Verified |
|:----:|:--------------:|:-----:|:--------:|
| 3 | 0x0000AAAB | 17 | ALL 65536 values ✅ |
| 7 | 0x00004925 | 17 | (split-byte method) ✅ |

---

### 📦 Pre-computed Integer Factors (ILDS)

No 64K-entry ROM! Instead: store exact powers of the base ✨

```
For base 3, scale = 10:
  factor[0] = 3^9 = 19683
  factor[1] = 3^8 = 6561
  ...
  factor[9] = 3^0 = 1

Processing n=2:
  digit 0 = 2, digit 1 = 0
  result = 2 x 19683 + 0 = 39366
  VdC(2) = 39366 / 59049 = 0.666... (exact!)
```

| Method | Storage | Ratio |
|:-------|:-------:|:-----:|
| Full ROM | 65536 x 16-bit = 128 KB | 1x |
| ILDS factors | 10 x 16-bit = **160 bits** | **6400x smaller** 🔥 |

---

### ⚙️ CORDIC Algorithm

CORDIC = Coordinate Rotation Digital Computer.
**No multipliers.** Only shift-and-add!

```
for i = 0 to N-1:
    d = +1 if z >= 0 else -1
    x' = x - d * y * 2^(-i)
    y' = y + d * x * 2^(-i)
    z' = z - d * atan(2^(-i))
```

After N iterations: (x, y) = (cos(z0), sin(z0)) * K

CORDIC gain K = 1.647 (pre-scale x by 1/K to cancel) 🔄

.mermaid[
<pre>
graph LR
    A["Angle z"] --> C["CORDIC\n16 iterations\n(shift-add)"]
    I["x0 = 1/K\ny0 = 0"] --> C
    C --> CO["cos(z)"]
    C --> SI["sin(z)"]
    style C fill:#2e3440,stroke:#ebcb8b,color:#eceff4
</pre>
]

---

### 🏗️ CORDIC Hardware Architecture

.mermaid[
<pre>
graph LR
    IDLE["💤 IDLE\nwait for en"] -->|"en=1"| LOAD["📥 LOAD\nz = angle\nx = 1/K\ny = 0"]
    LOAD --> ITER["🔄 ITERATE\n16 iterations\nshift-add per cycle"]
    ITER -->|"iter < 15"| ITER
    ITER -->|"iter = 15"| DONE["✅ DONE\ncos = x[17:2]\nsin = y[17:2]"]
    DONE --> IDLE
    style IDLE fill:#3b4252,stroke:#88c0d0,color:#eceff4
    style LOAD fill:#2e3440,stroke:#ebcb8b,color:#eceff4
    style ITER fill:#2e3440,stroke:#a3be8c,color:#eceff4
    style DONE fill:#2e3440,stroke:#bf616a,color:#eceff4
</pre>
]

**Specifications:**
- Internal: 18-bit signed Q1.17 🧮
- Output: 16-bit signed Q1.15 (range [-1, 1)) 📐
- Latency: 17 cycles ⏱️
- **Zero ROM**: 16 atan constants (256 bits) 💾

---

### 📐 Quadrant Reduction

Fold [0, 2*pi) into [0, pi/2] using symmetry:

| Bits[15:14] | Quadrant | Reduced z | cos sign | sin sign |
|:-----------:|:--------:|:----------|:--------:|:--------:|
| 00 | Q1 [0, pi/2) | angle[13:0] | + | + |
| 01 | Q2 [pi/2, pi) | pi/2 - sub | - | + |
| 10 | Q3 [pi, 3pi/2) | sub | - | - |
| 11 | Q4 [3pi/2, 2pi) | pi/2 - sub | + | - |

where sub = angle[13:0].

⚠️ **Pitfall:** pi/2 - sub can equal 0x4000 (15-bit).
Must use full 16-bit z, NOT 14-bit truncation!

---

### 🌊 Hyperbolic Mode: sqrt(x)

For square root, use **hyperbolic CORDIC in vectoring mode**.

```
for i = [1,2,3,4,4,5,6,7,8,9,10,11,12,13,13,14,...,18]:
    d = -1 if y >= 0 else +1
    x' = x + d * y * 2^(-i)
    y' = y + d * x * 2^(-i)
```

**Initialization:**
```
x = w + 0.25,  y = w - 0.25    (w in [0, 1))

After convergence: sqrt(w) = x / K_h
```

Hyperbolic gain K_h = 0.828... 🔄

**Critical: input normalization!**
- Multiply w by 4 until w >= 0.25
- Divide result by 2 per normalization step ✅

---

### ⚔️ Circular vs Hyperbolic CORDIC

| Property | 🔄 Circular | 🌊 Hyperbolic |
|:---------|:----------:|:------------:|
| Purpose | sin / cos | sqrt(x) |
| Mode | Rotation (z -> 0) | Vectoring (y -> 0) |
| Repeated iters | none | i = 4, 13 |
| Gain K | 1.647 | 0.828 |
| Initial x | 1/K | w + 0.25 |
| Initial y | 0 | w - 0.25 |
| Output scale | x >> 2 | x * 1/K_h >> 16 |

**Same hardware structure** 🔧 — only constants and mode differ!

---

## 🧩 Hardware Modules

### 🌐 Circle: Unit Circle Points

```cpp
template <unsigned long Base = 2> class Circle {
    VdCorput<Base> vdc;
    auto pop() {
        auto theta = this->vdc.pop() * TWO_PI;
        return {cos(theta), sin(theta)};  // unit circle point
    }
};
```

.mermaid[
<pre>
graph LR
    en["en 🚀"] --> V["vdc_16\nVdC<2>\nbit-rev"]
    V -->|"angle 0-65535"| C["cordic_16\nCORDIC\nsin/cos"]
    C -->|"cos, sin"| CO["cos, sin"]
    style V fill:#2e3440,stroke:#88c0d0,color:#eceff4
    style C fill:#2e3440,stroke:#a3be8c,color:#eceff4
</pre>
]

circle_2_16 = vdc_16 + cordic_16 ✅

---

### 🥏 Disk: Unit Disk Points

```cpp
template <unsigned long Base0 = 2, unsigned long Base1 = 3>
class Disk {
    auto pop() {
        auto theta = this->vdc0.pop() * TWO_PI;  // angle
        auto radius = sqrt(this->vdc1.pop());     // radius (sqrt!)
        return {radius * cos(theta), radius * sin(theta)};
    }
};
```

.mermaid[
<pre>
graph LR
    en["en 🚀"] --> C2["circle_2_16"]
    en --> V3["vdc_3_ilds"]
    V3 -->|"raw"| SC["scale\nx72736>>16"]
    SC --> SQ["cordic_sqrt_16\n√"]
    C2 -->|"cos, sin"| M["×"]
    SQ -->|"radius"| M
    M --> OUT["x, y"]
    style SQ fill:#2e3440,stroke:#bf616a,color:#eceff4
    style M fill:#2e3440,stroke:#ebcb8b,color:#eceff4
</pre>
]

The sqrt(r) transform ensures uniform disk distribution ✅

---

### 🌍 Sphere: Unit Sphere Points

```cpp
template <unsigned long Base0 = 2, unsigned long Base1 = 3>
class Sphere {
    auto pop() {
        auto cosphi = 2 * this->vdcgen.pop() - 1;  // [-1, 1]
        auto sinphi = sqrt(1 - cosphi * cosphi);
        auto [cx, cy] = this->cirgen.pop();        // Circle<3>
        return {sinphi * cx, sinphi * cy, cosphi};
    }
};
```

.mermaid[
<pre>
graph LR
    en["en 🚀"] --> V2["vdc_16"]
    en --> C3["circle_3_16"]
    V2 --> CP["cosphi = angle - 0x8000"]
    CP --> Z["z = cosphi"]
    CP --> SQIN["1 - cosphi^2"]
    SQIN --> SQ["cordic_sqrt_16\n√"]
    SQ -->|"sinphi"| MX["×"]
    SQ -->|"sinphi"| MY["×"]
    C3 -->|"cos(theta)"| MX
    C3 -->|"sin(theta)"| MY
    MX --> X["x"]
    MY --> Y["y"]
    Z --> ZO["z"]
    style SQ fill:#2e3440,stroke:#bf616a,color:#eceff4
    style CP fill:#2e3440,stroke:#ebcb8b,color:#eceff4
</pre>
]

---

### 🗺️ Module Reuse Map

.mermaid[
<pre>
graph TD
    V16["🔷 vdc_16\nVdC<2> bit-rev"] --> C16["🔷 cordic_16\nCORDIC sin/cos"]
    V16 -.-> Z["z = cosphi"]
    V16 -.-> SPH["sphere_23"]
    V3I["🔷 vdc_3_ilds\nVdC<3> 2^2-1"] -.-> C16
    V3I --> SQRT["🔷 cordic_sqrt_16\nhyperbolic CORDIC sqrt"]
    C16 --> C216["circle_2_16"]
    C16 --> C316["circle_3_16"]
    C216 --> DISK["disk_23"]
    C316 --> SPH
    SQRT --> DISK
    SQRT --> SPH
    style V16 fill:#5e81ac,stroke:#88c0d0,color:#eceff4
    style V3I fill:#5e81ac,stroke:#88c0d0,color:#eceff4
    style C16 fill:#5e81ac,stroke:#a3be8c,color:#eceff4
    style SQRT fill:#5e81ac,stroke:#bf616a,color:#eceff4
    style C216 fill:#4c566a,stroke:#ebcb8b,color:#eceff4
    style C316 fill:#4c566a,stroke:#ebcb8b,color:#eceff4
</pre>
]

**5 base modules -> 5 composite modules** 🔧
**All share the same CORDIC core** 💪

---

## 🔬 Verification with iverilog

Each module has a testbench checking against C++ reference values 📋

.mermaid[
<pre>
graph TD
    subgraph "Testbench"
        TB["🚀 Assert en"] --> DUT["DUT"]
        DUT -->|"valid"| CAP["Capture outputs"]
        REF["Expected values\n(from C++)"] --> CMP["Compare"]
        CAP --> CMP
        CMP -->|"error < 10"| PASS["✅ PASS"]
        CMP -->|"error > 10"| FAIL["❌ FAIL"]
    end
    style PASS fill:#2e3440,stroke:#a3be8c,color:#eceff4
    style FAIL fill:#2e3440,stroke:#bf616a,color:#eceff4
</pre>
]

Testbench pattern:
```verilog
en = 1; @(posedge clk); #1; en = 0;
@(posedge valid); #1;
err = $signed(got) - $signed(exp);
if (err < 0) err = -err;
if (err < 10) $display("PASS");
```

---

## 🛠️ Yosys Logic Synthesis

RTL to gate-level netlist in one script 🏗️

```tcl
read_liberty -lib ../tutorial_tech.lib   # read std-cell library
read_verilog ../rtl/circle_2_16.v        # read RTL
hierarchy -top circle_2_16              # elaborate
synth -top circle_2_16                  # coarse synthesis
dfflibmap -liberty ../tutorial_tech.lib # map DFFs
abc -liberty ../tutorial_tech.lib       # map combinational
stat                                      # report area
write_verilog circle_2_16_synth.v       # gate-level netlist
write_json circle_2_16_synth.json       # JSON netlist
```

Synthesized netlist verified with iverilog + Yosys simlib.v:

```
iverilog -o test tb.v synth.v /path/to/simlib.v
vvp test  --> same 12/12 PASS ✅
```

---

### 📊 Synthesis Results

| Module | Cells | DFFs | Key Logic |
|:-------|:-----:|:----:|:----------|
| vdc_16 | **72** | 17 | bit-reversal = **0 gates!** 🔥 |
| vdc_3_ilds | 1443 | 70 | 2^2-1 trick + 10-factor MAC |
| vdc_7_ilds | 1025 | 69 | 2^3-1 trick + 5-factor MAC |
| cordic_16 | ~1000 | ~70 | 16 shift-add iterations |
| cordic_sqrt_16 | ~1000 | ~67 | 20 hyperbolic iterations |

**Key insight:** Base-2 VdC costs only a counter (72 cells).
Base-3 needs 20x more logic (1443 cells) for div/mod/MAC.

CORDIC dominates area for Circle/Disk/Sphere (~70% of total).

---

### 📋 JSON Netlist Validation

```json
{
  "creator": "Yosys 0.9+2406",
  "modules": {
    "vdc_16": {
      "ports": { "clk": "input", "rst_n": "input", ... },
      "cells": { ... },   // 72 cell instances
      "netnames": { ... }
    }
  }
}
```

Schema validation:

```
$ python validate_yosys_json.py
Validating against yosys_schema.json...
*** SCHEMA VALIDATION PASSED ***
```

Both schema check and netlistx loading pass ✅
Netlist simulation with simlib.v: **all tests pass** ✅

---

### 🎉 Verification Results: 88 Tests All Pass

| Module | Tests | RTL | Synth | Max Error |
|:-------|:-----:|:---:|:-----:|:---------:|
| vdc_16 (bit-reversal) | 20 | ✅ | ✅ | 0 (exact) |
| vdc_3_ilds (2^2-1 trick) | 12 | ✅ | ✅ | 0 (exact) |
| vdc_7_ilds (2^3-1 trick) | 12 | ✅ | ✅ | 0 (exact) |
| circle_2_16 | 12 | ✅ | ✅ | 5 LSB |
| circle_3_16 | 12 | ✅ | ✅ | 6 LSB |
| disk_23 | 10 | ✅ | -- | 11 LSB |
| sphere_23 | 10 | ✅ | -- | 11 LSB |

**Flow:** C++ -> Python -> Verilog (iverilog) -> Yosys -> JSON -> netlist sim 🔄

---

## 🐛 Bug Stories: 6 Bugs Found & Fixed

### 🐛 Bug #1: Missing reg signed

```verilog
// WRONG -- unsigned! >>> does LOGICAL shift
reg [17:0] x, y;

// CORRECT -- signed! >>> does ARITHMETIC shift
reg signed [17:0] x, y;
```

x goes negative during CORDIC iterations.
With unsigned reg, >>> zero-fills instead of sign-extending.
All subsequent iterations compute with wrong values! 💥

---

### 🐛 Bug #2: Quadrant Truncation

```verilog
// WRONG -- 14-bit truncation
z <= {2'b00, 16'h4000 - angle[13:0]};

// CORRECT -- full 16-bit
z <= 16'h4000 - {2'b00, angle[13:0]};
```

For angle = 0xC000 (3*pi/2): 0x4000 - 0 = 0x4000 = 16384.
BUT 0x4000 is 15 bits! {2'b00, 14-bit} drops bit 14.
z becomes 0 instead of pi/2. 😱

---

### 🐛 Bug #3: Python Serial vs Verilog Parallel

```python
# WRONG -- sequential!
x -= (y >> i)
y += (x >> i)   # x already changed!
```

CORDIC requires BOTH x and y to use ORIGINAL values (parallel).
Verilog NBA (<=) does this correctly. Python = does NOT! 💥

```python
# CORRECT -- use temporaries
xn = x - (y >> i)
yn = y + (x >> i)   # uses original x!
x, y = xn, yn
```

---

### 🐛 Bug #4: 16-bit Multiply Truncation

```verilog
// WRONG -- 16-bit x 16-bit = 16-bit result!
wire signed [31:0] sq = a * b;   // truncated!
```

(-16384)^2 = 268435456 = 0x10000000. But 16-bit result = 0x0000! 💥

```verilog
// CORRECT -- 32-bit operands
wire signed [31:0] a_ext = {{16{a[15]}}, a};
wire signed [31:0] sq = a_ext * a_ext;
```

**Lesson:** Verilog multiply width = max operand width,
NOT twice the width. Always widen! 🧠

---

### 🐛 Bug #5: Saturation Threshold Typo

```verilog
// WRONG -- 28-bit threshold (missing two Fs!)
(tmp > 32'h3FFFFFF) ? 65535 : (tmp >> 14);

// CORRECT -- 32-bit threshold
(tmp > 32'h3FFFFFFF) ? 65535 : (tmp >> 14);
```

0x3FFFFFF = 67 million. Typical tmp = 805 million.
805M > 67M --> always saturates to 65535! 💥

Count your hex digits! 🧠

---

### 🐛 Bug #6: State Machine Losing Handshake

.mermaid[
<pre>
graph TD
    subgraph "Bug: en arrives in S_DONE"
        IDLE1["S_IDLE"] -->|"en"| WAIT1["S_WAIT"]
        WAIT1 -->|"both done"| DONE1["S_DONE"]
        DONE1 -->|"valid=0, go IDLE"| IDLE1
        EN["🚀 en (2nd pulse)"] -.-> DONE1
        DONE1 -.->|"❌ S_IDLE never runs"| NO["Flags never reset!"]
    end
    style NO fill:#3b4252,stroke:#bf616a,color:#eceff4
</pre>
]

**Fix:**
1. Capture valid signals UNCONDITIONALLY (outside case statement)
2. Transition from S_DONE to S_WAIT directly when en is high

```verilog
always @(posedge clk) begin
    if (circle_valid) circle_done <= 1;  // unconditional!
    if (sqrt_valid)   sqrt_done   <= 1;
    case (state)
        S_DONE: if (en) state <= S_WAIT;  // skip S_IDLE!
```

---

## 📝 Summary

### 🔑 Key Techniques

| Technique | Application | Area Impact |
|:-----------|:------------|:-----------:|
| 🪄 Bit reversal | Base-2 VdC | **0 logic cells** 🔥 |
| ✨ 2^n-1 trick | Base-3/7 div/mod | ~1400 cells |
| 📦 Integer factors | ROM replacement | **160 bits** vs 128 KB |
| 🔄 Circular CORDIC | sin / cos | ~1000 cells |
| 🌊 Hyperbolic CORDIC | sqrt(x) | ~1000 cells |
| 🧩 Module reuse | Circle/Disk/Sphere | cascaded |

### 🎯 Accuracy
All errors < 0.04% (CORDIC approximation + fixed-point truncation).
Z-axis (Sphere): **exact** ✅

### 💾 Zero ROM
No lookup tables anywhere. Pure shift-add computation! 💪

---

# 🙏 Thank You!

### github.com/luk036/lds-hdl

**Verification:** 88 tests via iverilog ✅
**Synthesis:** Yosys -> gate-level netlist -> JSON ✅
**Validation:** Schema match + netlist loading ✅

### Questions? 🤔