Edge-Cell Graph Encoding and Fixed-Point Arithmetic for FPGA Growing Neural Gas

Problem & Motivation

Edge robots and micro-UAVs need unsupervised learning close to the sensor, where communication links, payload, and energy are limited. GNG is a strong candidate because it learns both prototypes and topology online, but its graph operations are not naturally matched to a small FPGA fabric.

Problem 1

Dynamic topology on static hardware

GNG continually creates, ages, reconnects, and removes graph edges. These data-dependent operations are simple in software, but they create irregular memory access and control-flow pressure on a small FPGA.

Problem 2

Dense adjacency wastes graph memory

A conventional Nmax by Nmax adjacency matrix stores both halves of an undirected graph. At Nmax = 40, the dense edge table alone consumes 1,600 B before any node coordinate or error state is stored.

Problem 3

Floating-point units are too costly

Winner search, distance evaluation, and learning-rate updates are repeated for every input sample. Floating-point datapaths increase area and latency, limiting their usefulness on a sub-10K-LUT FPGA.

Motivation

Make online GNG practical at the edge

The design target is a bounded-memory, integer-only GNG accelerator that keeps the dynamic topology behavior of the algorithm while fitting the Tang Nano 9K resource envelope.

Constrained embedded environment with geometric obstacles — Unstructured field scene

Sipeed Tang Nano 9K FPGA board — Tang Nano 9K FPGA

Growing Neural Gas topology graph over a navigation-like map — Online topology graph

Motivation: convert continuous, sensor-like spatial observations into a compact GNG graph directly on a small FPGA, without floating-point hardware or dynamic memory.

Abstract

Growing Neural Gas (GNG) is a self-organizing clustering algorithm that incrementally learns a graph representation from unlabeled data. Its dynamic topology is attractive for edge robotics and field systems, but conventional implementations rely on dense adjacency structures, floating-point arithmetic, and dynamic memory patterns that do not map cleanly to small FPGAs.

This project implements GNG on a Sipeed Tang Nano 9K FPGA using a bounded-memory datapath. Edge-cell graph encoding stores only the upper triangle of the adjacency as 8-bit age+1 values, while Q8/Q16 fixed-point updates replace floating-point learning rates. The design fits within the GW1NR-9C resource budget and preserves topology quality on Two Moons and Concentric Circles benchmarks.

Method Overview

Fused update pass

Error decay, edge aging, neighbor movement, and over-age pruning are combined inside one NB_SCAN sweep. Per-node degree counters support isolated-node monitoring without scanning the full edge array.

Edge-cell encoding

The graph stores one byte per undirected node pair. A zero value means no edge; a nonzero value stores edge age plus one. At Nmax = 40, edge storage drops from 1,600 B to 780 B.

Fixed-point arithmetic

Node coordinates are signed integers normalized to [-1000, 1000]. Winner and neighbor adaptation use Q8/Q16 shift-scaled learning rates with DSP-friendly multiply-and-shift operations.

GNG Loop & Fused FPGA Update

In the paper, the current implementation is a sequential single-clock FSM. UPDATE handles the winner first: accumulate err_s1, apply winner error decay, and move s₁ with the Q8 learning rate.

The fused part is the NB_SCAN pass. While scanning each active node slot n ≠ s₁, the FSM decays that node's error, probes edge_cell[idx(s1,n)], and only for active winner-incident edges performs aging, neighbor movement, and old-edge pruning inline.

FPGA implication: the current paper reports this as a bounded sequential read-modify-write pipeline; the same regular per-node/per-edge-cell structure is the path to wider parallel datapaths when BRAM ports and resources are provisioned.

Sample input ξ SAMPLE

↓

Find winner s₁, runner-up s₂ WIN_SCAN

↓

Update winner s₁: err + decay + Q8 move UPDATE

↓

Fused NB_SCAN pass

Decay node error Probe edge cell Age/prune active edge Move neighbor

one N_max scan replaces separate decay + neighbor-edge passes

↓

Connect (s₁, s₂) · reset edge age CONNECT

↓

Insert node @ λ · split max-error edge INSERT

Each BRAM read-modify-write takes at least three cycles, so the implemented loop remains deterministic and bounded per sample even before wider parallel datapaths are introduced.

Edge-Cell Encoding

Edges are undirected, so the FPGA stores only the upper triangle of the adjacency matrix. Each one-byte cell codes presence and age together.

cell = age + 1 stored edge cell = 0 no edge Lower triangle and diagonal are never stored

node j →

← node

0 1 2 3 4 5 0 3 1 0 0 0 1 0 7 0 0 2 2 5 0 3 0 1 4 4 5

Half-adjacency indexing

Flatten the 2D upper triangle into one 1D array, row by row.

00,1 10,2 20,3 30,4 40,5 51,2 61,3 71,4 81,5 92,3 102,4 112,5 123,4 133,5 144,5

idx(i,j) = i(2N_max - i - 1) 2 + (j - i - 1) (1,3) → cell 6

Implementation	Node	Edge	Total
Dense adjacency (baseline)	400 B	1,600 B	2,000 B
Edge-cells (proposed)	400 B	780 B	1,180 B

-51.25% edge storage and -41% total graph state at Nmax = 40.

Fixed-Point Arithmetic

Integer-only datapath - no floating-point unit. The whole engine runs on a Tang Nano 9K at 27 MHz as a single FSM with 3 BRAMs and 1 Mbit/s UART streaming.

Tang Nano 9K FPGA board used by the fixed-point GNG accelerator — Tang Nano 9K - GW1NR-9C

Coordinate representation - 16-bit signed integers in [-1000, 1000] after min-max normalization:

x_norm = x - x_min x_max - x_min · 2s - s s = 1000

80-bit node word - one BRAM entry per node:

x [16] y [16] deg [8] err [32] act + pad

Squared-distance unit - maps directly onto a 9x9 DSP multiplier, overflow-free:

Δx = ξ_x - x_n, Δy = ξ_y - y_n 17-bit signed d² = Δx² + Δy² 35-bit unsigned

Parametric learning rates - one multiply + shift each (single DSP cycle):

Winner (Q8)

Δx_s1 = ⌊ EPS_WIN_Q8(ξ_x - x_s1) 2⁸ ⌋ ε_w = EPS_WIN_Q8 / 2⁸

Neighbor (Q16)

Δx_n = ⌊ EPS_N_Q16(ξ_x - x_n) 2¹⁶ ⌋ ε_n = EPS_N_Q16 / 2¹⁶

Multiplierless error decay err_n -= err_n >> 8 no multiplier, beta = 0.9961

Fused update: winner move, edge aging, neighbor move, error decay, and pruning all run in one NB_SCAN sweep, so per-edge operations remain regular and FPGA-friendly.

Parameter	Value	Hardware mapping
N_max (max nodes)	40	node BRAM depth
A_max (max edge age)	50	A_MAX_STORED = 51
λ (insertion period)	100	lambda counter
ε_w (winner lr)	0.301	EPS_WIN_Q8 = 77, >> 8
ε_n (neighbor lr)	0.001	EPS_N_Q16 = 66, >> 16
α (error split)	0.5	INS_ALPHA_SHIFT = 1
β (error decay)	0.9961	ERR_DECAY_SHIFT = 8
ERR_SHIFT (acc. scale)	4	d² >> 4 before accumulation

Where 77 and 66 come from: the author selected fixed-point coefficients that approximate the target learning rates, namely a winner rate close to ε_w = 0.3 and a neighbor rate close to ε_n = 0.001. In a Q-format implementation, EPS_Q = round(ε · 2^Q), so EPS_WIN_Q8 = round(0.3 · 256) = 77 and EPS_N_Q16 = round(0.001 · 65536) = 66.

Experiments

The prototype is evaluated on two 2D topology-learning benchmarks using FPGA snapshots and an on-chip cycle counter. The measured latency remains near-identical across datasets because execution is bounded by O(Nmax) BRAM scans.

Integer-only GNG learns dynamic topology on a sub-10K-LUT FPGA.

Two Moons topology learned by FPGA GNG — Two Moons learned topology

Concentric Circles topology learned by FPGA GNG — Concentric Circles learned topology

The FPGA streams node and edge snapshots through UART. The host reconstructs the learned topology and evaluates quantization error, topological error, and runtime.

-41% total graph-state memory

~625 us deterministic latency per sample

~1,600/s measured sample throughput

38% LUT utilization on GW1NR-9C

Training dynamics for the Two Moons experiment — Training dynamics for Two Moons: graph growth, quantization error convergence, and topological error.

Takeaway & Future Work

Future Prospects

Self-organizing clustering with dynamic topology is feasible on a sub-10K-LUT FPGA, making it relevant for robots and embedded devices with strict power, weight, physical-size, compute, and memory limits.

Compact exploration robot operating inside a constrained pipe — Confined-space exploration robot

Why this hardware direction matters

Robots for pipe inspection, exploration, long-term deployment, and distributed sensing cannot assume large batteries, high-end processors, or abundant memory. A bounded-memory FPGA GNG module can keep learning local topology while staying lightweight, low power, and physically compact.

Pipe inspection image source: JET Manufacturing, accessed June 2026.

Low power Lightweight Strict physical size Long-term mission Exploration Swarm devices Distributed intelligence Compute constrained Low memory

Topological mapping for lightweight flapping robot prospective application — Topological mapping for lightweight flapping robot Credit: EPFL / Raphael Zufferey

Bio-inspired robot prospective application — Bio-inspired robot The Pleurobot. Photo: Hillary Sanctuary & BioRob

Swarm robot prospective application — Swarm robot Kilobot swarm. Photo: Mike Rubenstein and Science/AAAS; Harvard SEAS

Long-term exploration robot prospective application — Long-term exploration robot Credit: Canadian Space Agency

Lightweight flapping robots

Map local topology on tiny aerial platforms where payload and compute budget are minimal.

Bio-inspired physical constraints

Support compact robots whose body shape, actuator layout, and memory budget are tightly limited.

Swarm intelligence

Let many small robots learn local structure with distributed intelligence and limited communication.

Low-power long missions

Keep exploration robots adapting over long deployments without high-power processors or large RAM.

Poster

Resources

The paper, poster, slide deck, source code, and reproducibility report are available from the links below.

Paper PDF Poster PPTX Slidev Web Report GitHub