An algebraic framework unifying most binary encodings

Abbreviations

Shorthand	Meaning
uint	Unsigned integer
2C	Two's complement
1C	One's complement

Binary numbers as linear transforms

Binary to decimal conversion can be seen as a dot product between the binary values and a weight vector.

E.g., when , we get the unsigned integer representation.

A similar, slightly more abstract view is to look at it as a linear transform with the weights as the spanning set. This shift in view illuminates the structure of binary representations. Their properties such as their range, injectivity, and behavior under addition can be derived from the corresponding linear functionals.

Under this view, different binary representations - uint, 2C, 1C and fixed-point - correspond to different choices of weight vectors.

The top three encodings differ only in their last weight while fixed-point differs in all weights:

Encoding	Weights
uint
2C
1C
fixed-point

Setup for the example below

An example is shown for 3-bit binary strings. Each column applies a different weight vector to decode the same bits.

• integers to
• convert to 3-bit binary strings
• unsigned:
• two's complement:
• one's complement:

An example for 3-bits

• Click to show the table: the columns correspond to uint, 2C, and 1C.

Note how the first two transforms - uint and 2C - are injective: each of the 8 input strings maps to a distinct output value. The third one - 1C - is not injective: both these input strings map to .

This mapping also highlights that uint and 2C are isomorphic i.e. they have the same structure, which is why the same hardware can implement both.

---

The "independence" of weights

Strictly speaking, the rank of these linear transforms is , and the 1D weight vectors are not linearly independent over real numbers. However, if the only inputs allowed are either or then the weights are effectively independent for uint and 2C.

The weights of 1C have a linear dependence: the last weight is the negative sum of the previous weights, which is why maps to :

---

The ring of binary representations

Another algebriac structure that helps understand the properties of these representations is the ring. Both uint and 2C representations can be seen as the ring .

Setup

Visualizing the ring structure

• Create ring

Note that each element in the underlying set is equivalent to , and that in this ring.

Thus from the last half of the elements one can subtract , which gives us the familiar two's complement representation. This makes the isomorphism between the two representation clear: it is the same underlying set and the same addition operation, just with a different choice of representatives for each equivalence class.

---

Correspondence between weights and ring elements

Note that:

Thus adding to any of the weights does not change the transform's value in the ring (i.e. mod ), which is why we can have different weight vectors corresponding to the same underlying ring structure.

This can be visualized by showing the weights first. Now we modify these weights:

---

Connection between two's complement and one's complement

Since in the ring, we have:

This equation explains the well known relationship: that to get the two's complement representation of a number, you can take the one's complement and add 1. This can be seen by setting the weights to two's complement and looking at pairs :

• 1 and -1: ;
• 2 and -2: ;
• 3 and -3: ;

---

Bias as an affine transform

Another common encoding scheme is to add a bias (or shift) to the unsigned representation so that the bits represent values from to in that order:

• : bias = 1
• : bias = 2
• : bias = 3

It is used to represent the exponent of a floating point number (in IEEE 754 representation), where it is called the exponent bias.

In this transform, the input does not map to . Thus it is not a linear transform. It is instead an affine transform. Decimal to binary conversion in this case is done by simply adding the bias to the number, then applying the same linear transform as unsigned.