🔢 mathematics

Codes for Metastability-Containing Addition

This paper addresses the challenge of adding uncertain values represented as intervals by establishing an upper bound on code rates for preserving uncertainty and designing an asymptotically optimal recoverable code that prevents the amplification of imprecision caused by metastable bits.

Original authors: Johannes Bund, Christoph Lenzen, Moti Medina

Published 2026-02-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Johannes Bund, Christoph Lenzen, Moti Medina

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Problem: Adding "Fuzzy" Numbers

Imagine you are trying to add two numbers together, but you don't know the exact values. Instead, you only know they fall within a small range.

Number A is somewhere between 25 and 26.
Number B is exactly 37.

In a perfect world, you would just add the ranges: $25+37=62$ and $26+37=63$ . So, your answer is "somewhere between 62 and 63." This is called interval addition.

However, in the world of computer chips, things get messy. Sometimes, a signal (a bit) gets stuck in a state of confusion called metastability. It's like a light switch that is stuck halfway between "on" and "off." It might settle on 0, or it might settle on 1, but right now, it's "X" (unknown).

The paper shows that if you try to add these "fuzzy" numbers using the standard way computers do math (binary code), the confusion explodes.

The Analogy: Imagine you are trying to add two blurry photos. If you use a standard camera filter, the blur doesn't just stay in one spot; it smears across the entire picture. A single blurry pixel in the input can make the entire output image unreadable. In the paper's example, one unstable bit turned a clear answer (62) into a total guess (any number from 0 to 127).

The Goal: A "Fuzzy-Proof" Code

The researchers wanted to find a new way to write numbers (an encoding) so that when you add them, the "fuzziness" (uncertainty) doesn't get worse. They call this preserving precision.

They also wanted a way to look at the messy result and say, "Okay, even though this is fuzzy, I can still tell you for sure that the answer is between 62 and 63." They call this recoverability.

The Solution: The "Hybrid" Code

The team invented a new way to write numbers called a Hybrid Code. Think of it as a two-part address system for numbers:

The "Coarse" Part (The Neighborhood): This part uses a special code called a Gray Code. In a Gray Code, when you count up (1, 2, 3...), you only change one bit at a time. It's like walking down a street where you only change your house number by one digit at a time. This ensures that if you are slightly confused about where you are, you only get confused about your immediate neighbors, not the whole city.
The "Fine" Part (The House Number): This part uses a Unary Code. Imagine a row of light switches. To represent the number 3, you turn on the first three switches (111000). To represent 4, you turn on the first four (111100). This is very redundant (uses many bits), but it's very robust. If one switch is stuck in the middle (metastable), you can still tell exactly which range of numbers you are in.

How they work together:
The Hybrid Code combines these two. The Gray Code part tells you the "big picture" (the neighborhood), and the Unary part tells you the "details" (the specific house).

The Magic Trick: The researchers designed it so that the "fuzziness" in the Gray Code part is handled by the stability of the Unary part, and vice versa.
The Result: When you add two fuzzy numbers using this code, the "fuzziness" in the answer is exactly the sum of the fuzziness in the inputs. It doesn't explode.

The Trade-off: Redundancy

To make this work, you have to pay a price: Redundancy.

Standard Binary: To write the number 100, you need 7 bits ($1100100$).
Hybrid Code: To write the number 100 with this new safety feature, you need more bits (the 7 bits for the neighborhood + extra bits for the house details).

The paper proves a mathematical rule: You cannot have a code that is perfectly precise and perfectly recoverable without adding extra bits. If you want to handle a certain amount of "fuzziness," you must use extra space to store that information.

The Circuit: How to Add Them

The paper also describes how to build a physical circuit (a machine) to do this addition.

Translation: First, the machine translates the Hybrid Code into standard binary numbers (so it can use a normal calculator).
Addition: It adds the numbers.
Translation Back: It translates the result back into the Hybrid Code.
Safety Net: They designed the machine so that even if the input signals are "stuck" (metastable), the machine doesn't crash or output garbage. It outputs the best possible "fuzzy" answer that matches the inputs.

Real-World Example Mentioned in the Paper

The authors mention one specific place where this is useful: Fault-tolerant Clock Synchronization.

Imagine a network of computers trying to agree on the exact time. They use sensors to measure time differences.
These sensors can be slightly off (fuzzy) due to physical limitations.
The computers need to add these measurements together to adjust their clocks.
Using standard math, the small errors could add up to a huge mistake. Using this new Hybrid Code, the computers can add the measurements and know exactly how much their final time estimate might be off, without the error blowing up.

Summary

The Problem: Standard computer math breaks when inputs are slightly uncertain (metastable), causing errors to explode.
The Fix: A new "Hybrid Code" that mixes two different ways of writing numbers.
The Benefit: It keeps the uncertainty contained. If you add two numbers with small errors, the result has a small, predictable error, not a massive one.
The Cost: You need to use more bits (more space) to store the numbers.
The Proof: The paper mathematically proves you can't do this without using extra bits, and their code is the most efficient way to do it.

Technical Summary: Codes for Metastability-Containing Addition

Problem Statement
The paper addresses the fundamental challenge of performing addition on inputs carrying uncertainty, specifically when discrete-valued measurements of analog values are prone to metastability. In standard digital circuits, metastable signals (represented as the ternary value $M$ or $X$ ) disrupt binary representations. When such unstable bits interfere with computation, standard binary encoding leads to an amplification of uncertainty. For instance, a single metastable input bit in a standard binary adder can cause all output bits to become metastable, rendering the result completely uninformative (e.g., an output interval spanning the entire range $[0, 2^n-1]$ ).

While unary (thermometer) encoding preserves precision under metastability, it suffers from exponential overhead in circuit size and latency. Conversely, standard binary codes and Gray codes offer high rates (efficiency) but fail to preserve the implicit lower and upper bounds of input intervals when metastability occurs. The core problem is to devise an encoding scheme that maintains the precision of input intervals (preventing information loss) while achieving a high rate (minimizing redundancy) and allowing for efficient circuit implementation.

Methodology and Definitions
The authors formalize the problem using Kleene's ternary logic ( $T = \{0, 1, M\}$ ), where $M$ represents a metastable signal. They introduce two critical properties for codes in this context:

Preservation: A code is $k$ -preserving if the resolution of an extended codeword (the superposition of all codewords in an interval of size $k+1$ ) does not introduce new codewords outside the original interval. This ensures that the output uncertainty matches the sum of input uncertainties.
Recoverability: A code is $k$ -recoverable if there exists a mapping from all binary strings (including non-codewords resulting from metastability resolution) back to the original interval range. This allows the system to deterministically recover a value consistent with the input uncertainty after metastability resolves.

The paper establishes a theoretical lower bound, proving that any $k$ -recoverable code requires redundancy. Specifically, an $n$ -bit code that is $k$ -recoverable can encode at most $2^{n-k}(k+1)$ values, implying a rate upper bound of $O(2^{n-k}k/n)$ .

Key Contributions and Results
The primary contribution is the design of a "hybrid" code ( $\gamma^h_{n,k}$ ) that achieves asymptotically optimal rates while satisfying the preservation and recoverability constraints.

Hybrid Code Construction: The code combines an $n$ -bit Binary Reflected Gray Code (BRGC) part with a $k$ -bit unary thermometer part. The specific flavor of the unary encoding (either $1^i0^{k-i}$ or $0^i1^{k-i}$ ) is determined by the parity of the BRGC part.
Performance Guarantees: The hybrid code is proven to be $k$ -preserving and $\lceil k/2 \rceil$ -recoverable. This means it can tolerate up to $k$ unstable bits in the input without amplifying the output imprecision, and it can deterministically recover intervals of size up to $\lceil k/2 \rceil$ .
Circuit Implementation: The authors design an addition circuit for this code.
- For stable inputs, the circuit translates the BRGC and unary parts to binary, performs standard binary addition, and translates the result back. This scheme has size $O(n+k)$ and depth $O(\log n + \log k)$ .
- To handle metastable inputs (extended codewords), the authors apply known constructions for metastability-containing (mc) circuits. Using a general construction by Ikenmeyer et al., they obtain a purely combinational mc adder of size $(n+k)^{O(k)}$ and depth $O(k \log n + \log k)$ . Alternatively, using masking registers, they achieve a size of $O(k(n+k))$ and depth $O(\log n + \log k)$ .
Optimality: The paper proves that the rate of their code matches the theoretical upper bound derived for $k$ -preserving codes, making it asymptotically optimal.

Significance and Claims
The paper claims that this work bridges the gap between the inefficiency of unary encoding and the information loss of binary encoding in the presence of metastability.

Theoretical Significance: It formalizes the trade-off between precision preservation, recoverability, and code rate, proving that redundancy is strictly necessary for higher-order recoverability.
Practical Application: The authors highlight the application of this code in fault-tolerant hardware clock synchronization (specifically the Lynch-Welch algorithm). In this context, Time-to-Digital Converters (TDCs) produce phase measurements with at most one metastable bit. The proposed hybrid code allows these measurements to be summed and averaged (divided by 2) in a fully metastability-containing digital fashion without resorting to inefficient unary adders or falling back to synchronizers that increase latency.
Future Outlook: The authors conjecture that careful design based on existing techniques could lead to significant latency reductions. They suggest that combining these codes with synchronizer-based designs or masking storage elements could improve the latency-MTBF (Mean Time Between Failures) trade-off compared to purely synchronizer-based approaches, though they note that quantitative validation requires further post-layout analysis.

The paper concludes that while the hybrid code introduces a slight asymmetry (tolerating $k$ imprecisions but only recovering $\lceil k/2 \rceil$ ), it provides a robust, high-rate solution for addition under uncertainty, enabling digital control loops to operate correctly even with metastable inputs.