Binary Neural Networks: Replacing MAC with XNOR

Binary Neural Networks (BNNs) dramatically improve computational efficiency and reduce memory footprints by quantizing both continuous weights and activations to single-bit values. By constraining these values to either \(+1\) or \(-1\) (mapped to logical \(1\) and \(0\)), the standard, resource-heavy floating-point Multiply-Accumulate (MAC) operations are replaced with bitwise XNOR gates and population count (popcount) instructions. This article explains how BNNs perform 1-bit binarization, map arithmetic multiplication to boolean logic, and aggregate binary products using standard hardware operations.

Binarization of Weights and Activations

Traditional deep neural networks rely on 32-bit floating-point (FP32) or 16-bit floating-point (FP16) representations. BNNs constrain these continuous numbers to a 1-bit discrete set \(\{-1, +1\}\).

The standard approach uses a deterministic sign function:

\[x_b = \text{Sign}(x) = \begin{cases} +1 & \text{if } x \ge 0 \\ -1 & \text{if } x < 0 \end{cases}\]

During the forward pass: 1. Activation Binarization: Continuous activations generated by previous layers pass through the sign function, transforming them into a vector of \(+1\)s and \(-1\)s. 2. Weight Binarization: Continuous latent weights stored during training are binarized using the same sign function before inference or forward computation.

Mapping \(\{-1, +1\}\) Multiplication to Boolean XNOR

In arithmetic multiplication over the domain \(\{-1, +1\}\), the product rules are: * \((+1) \times (+1) = +1\) * \((-1) \times (-1) = +1\) * \((+1) \times (-1) = -1\) * \((-1) \times (+1) = -1\)

When mapped to the binary boolean domain \(\{1, 0\}\) where \(+1 \rightarrow 1\) and \(-1 \rightarrow 0\), this exact truth table corresponds to the logical XNOR (exclusive NOR) operation: * \(1 \text{ XNOR } 1 = 1\) (True/Match) * \(0 \text{ XNOR } 0 = 1\) (True/Match) * \(1 \text{ XNOR } 0 = 0\) (False/Mismatch) * \(0 \text{ XNOR } 1 = 0\) (False/Mismatch)

Because digital hardware operates natively on bits, mapping \(\{-1, +1\}\) arithmetic to \(\{1, 0\}\) boolean space allows the hardware to evaluate scalar multiplications using a single logic gate.

Replacing MAC with XNOR and Popcount

The standard inner product in a neural network layer computes the sum of products:

\[\text{Output} = \sum_{i=1}^{N} W_i \cdot A_i\]

In a BNN, where both \(W\) and \(A\) are vectors of \(N\) binary values represented as bit arrays:

Bitwise Parallel XNOR: Hardware registers pack 32, 64, or more binary values into standard words. A single bitwise XNOR instruction computes the multiplication of all elements simultaneously.
Population Count (popcount): The sum of the resulting vector is determined by counting the number of set bits (1s) using a hardware popcount instruction, which indicates how many element pairs had identical signs.
Accumulation Conversion: The scalar dot product over \(\{-1, +1\}\) is reconstructed algebraically from the popcount value:

\[\text{Dot Product} = 2 \times \text{popcount}(W_{\text{bits}} \text{ XNOR } A_{\text{bits}}) - N\]

Where: * \(W_{\text{bits}}\) and \(A_{\text{bits}}\) are the bit-packed representations of the weights and activations. * \(N\) is the total number of elements in the vector.

Hardware and Performance Impact

Replacing standard floating-point arithmetic with binary logic provides three core advantages:

Computational Speed: Modern CPUs, GPUs, and custom ASICs can evaluate 64 parallel multiplications and partial additions in just two clock cycles (XNOR followed by popcount).
Energy and Area Efficiency: 1-bit XNOR gates consume significantly less silicon area and power compared to 32-bit floating-point multipliers and adders.
Memory Reduction: Storing weights and intermediate feature maps as 1-bit values reduces memory and cache bandwidth requirements by up to 32x compared to standard FP32 implementations.