Bits, bytes and friends

A *bit* (binary digit) is a unit of measure for information, introduced
by C. Shannon in 1948.

It might be seen as the minimal amount of
information needed in order to distinguish among two events occurring with the
same probability.

Bits are used in Information Theory and - in general - in
most of Computer Science applications.

They are denoted with the constants \(0\) and \(1\), representing the two events with the
same probability. Their set is often denoted with \(\{0,1\}\), but we need another notation, that is,

Indeed, with this different notation we mean that we can perform operations on bits.
More precisely, we want to introduce two operations, *sum* and *multiplication*, retaining some
similarity with the usual operations of sum and product for numbers.
The numbers we are interested in are integers, which we collect in a set called
\(\mathbb{Z}=\{\ldots,-1,0,1,2,\ldots\}\), non-negative integers, which we collect in a set called
\(\mathbb{N}=\{0,1,2,\ldots\}\), and rational numbers, which we collect in a set called \(\mathbb{Q}=\{\ldots,\frac{-5}{101},0,\frac{1}{2},3,\ldots\}\).

Since \(\mathbb{F}_{2}\) is so small, we can use the following table to show how to sum and multiply bits.

\(a\) | \(b\) | \(a+b\) | \(a\times b\) |
---|---|---|---|

0 | 0 | 0 | 0 |

0 | 1 | 1 | 0 |

1 | 0 | 1 | 0 |

1 | 1 | 0 | 1 |

The first column and the second contain the values of two input variables, \(a\) and \(b\), representing the two bits we sum or multiply; the third and the fourth, respectively, contain the sum and the product of \(a\) and \(b\).

Operations on bits share properties with those involving integer or rational numbers.

Let us start with a comparison between the sum in \(\mathbb{F}_{2}\) and the sum in \(\mathbb{Z}\).

We can sum \(2,3\) and \(4\) in \(\mathbb{Z}\) and it happens that

\begin{equation} (2+3)+4=5+4=9=2+7=2+(3+4),\nonumber \\ \end{equation}so we can write also \(9=2+3+4\), omitting the parentheses. Actually, this holds for any three numbers in \(\mathbb{Z}\).

We claim that this holds *also* for the sum of bits. For example

The reader can verify our claim for any \(a,b,c\in\mathbb{F}_{2}\).

Any time we have a set and a sum operation which satisfies the general property

we say that the operation is *associative*.

Therefore, we can conclude that both the sum in \(\mathbb{Z}\) and the sum in \(\mathbb{F}_{2}\) are associative operations.

Consider now \(2,3\in\mathbb{Z}\). We know that \(2+3=3+2=5\) and this holds for any pair of integers. We claim that this holds also for bits, as for example

\begin{equation} 0+1\,=\,1+0\,=\,1\,.\nonumber \\ \end{equation}We leave to the reader the verification of this statement for each \(a,b\in\mathbb{F}_{2}\).

We can formalize this property by saying that both the sum in \(\mathbb{Z}\) and the sum in \(\mathbb{F}_{2}\) are
*commutative* operations. In a more general setting, a sum operation on a set is called commutative if for any \(a,b\) in
that set we have

Now we take a close look at \(0\in\mathbb{Z}\). Considering any integer \(a\), we have that \(a+0=0+a=a\), as for example \(3+0=0+3=3\). In other words, summing a number with zero leaves the number unchanged (and this happens *only* for \(0\)).

The same happens with \(0\in\mathbb{F}_{2}\), since in \(\mathbb{F}_{2}\) \(0+0=0\) and \(0+1=1+0=1\).

In a general setting, if we have a sum operation with a special element \(e\) such that
\(a+e=e+a=a\) for any \(a\) in the set, then we say that \(e\) is the *neutral element* of the operation.

Therefore, we can say that \(0\in\mathbb{F}_{2}\) is the neutral element of the sum in \(\mathbb{F}_{2}\), while \(0\in\mathbb{Z}\)
is the neutral element in \(\mathbb{Z}\).

When there is a set with a sum operation, it is usual to call \(0\) the neutral element. This is unfortunate because for example the \(0\) in \(\mathbb{F}_{2}\) and the \(0\) are in \(\mathbb{Z}\) are two totally different objects. We are confident that the readers will soon be accustomed to this abuse of notation.

Another important property of the sum in \(\mathbb{Z}\) is that, given an element \(a\in\mathbb{Z}\), we can always find an element \(b\in\mathbb{Z}\) such that \(a+b=b+a=0\). For example, for \(a=3\), we have \(b=-3\), getting \(3+(-3)=(-3)+3=0.\)

In the general case, when there is a set with a sum, if for any element \(a\) there is another element
\(b\) such that \(a+b=0\) and this element is unique, then we say that \(b\) is the *opposite* of \(a\) and we
write \(b=-a\).

Opposites exist also for the sum in the set of bits, indeed

and so in \(\mathbb{F}_{2}\):

- •
the opposite of \(1\) is \(1\) (and \(-1=1\)),

- •
the opposite of \(0\) is \(0\) (and \(-0=0\)).

It is time that we introduce more formalism. We can consider any set \(G\) endowed with an operation \(*\) such that for any \(a,b\) in \(G\) the operation outputs another element \(a*b\) of \(G\). If the operation satisfies the following stringent properties

- i)
\(*\) is associative;

- ii)
\(*\) is commutative;

- iii)
\(*\) has a neutral element;

- iv)
each element of \(G\) has an opposite w.r.t. \(*\)

then \(G\) (with the operation \(*\)) is called an *abelian group*.

The adjective ”abelian” indicates that ii) holds, i.e. that the operation \(*\) is commutative. If only i), iii) and iv) hold, \(G\) is only a group.

Our previous observations about the sum in \(\mathbb{Z}\) and the sum in \(\mathbb{F}_{2}\) lead us to claim that both \(\mathbb{Z}\) and \(\mathbb{F}_{2}\) are *abelian groups w.r.t. their sum*.

Is \(\mathbb{Q}\), the set of rational numbers, an abelian group w.r.t. the sum? Give detailed comments.

Having dealt with the sum, we pass now to compare the multiplication of integers and that of bits.

Consider again \(2,3,4\in\mathbb{Z}\). We have that

so, as it was for the sum, we can remove the parentheses and write

\begin{equation} 2\cdot 3\cdot 4=24.\nonumber \\ \end{equation}The same holds for bits, for example

\begin{equation} (0\cdot 1)\cdot 1=0\cdot 1=0=0\cdot(1\cdot 1)=0\cdot 1=0\cdot 1\cdot 1.\nonumber \\ \end{equation}We leave to the reader the verification that this holds for each bit triplet.

This property can be formalized by saying that both the multiplication in \(\mathbb{Z}\) and the multiplication in \(\mathbb{F}_{2}\) are *associative*. In formulas, we say that for any \(a,b,c\) (which are elements of \(\mathbb{Z}\) or of \(\mathbb{F}_{2}\)), we have

Consider now \(2,3\in\mathbb{Z}\). We know that \(2\cdot 3=3\cdot 2=6\) and this holds for every pair of integers. We claim the same for bits, since for example

\begin{equation} 0\cdot 1\,=\,1\cdot 0\,=\,0\,.\nonumber \\ \end{equation}We leave, as an exercise to the reader, to verify this for each \(a,b\in\mathbb{F}_{2}\).

Again, this property can be formalized by saying that both the product in \(\mathbb{Z}\) and the product in \(\mathbb{F}_{2}\) are *commutative*. In formulas, we say that for any \(a,b\) (which are elements of \(\mathbb{Z}\) or of \(\mathbb{F}_{2}\)), we have

We examine now the behaviour of \(1\in\mathbb{Z}\).
Taken any other integer number \(a\), we have that \(a\cdot 1=1\cdot a=a\), for example \(3\cdot 1=1\cdot 3=3\), so multiplying a number with \(1\) gives, as result, again that number.

Also the bit \(1\in\mathbb{F}_{2}\), has the same behaviour, since \(1\cdot 0=0\cdot 1=0\) and \(1\cdot 1=1.\)

We can formalize this statement by saying that \(1\) is the *neutral element* of the product, both in \(\mathbb{Z}\) and in \(\mathbb{F}_{2}\).

Once we have introduced a neutral element, we might wish to go on and define a group, as we did
with the sum. Unfortunately, this cannot always be done, as we will see from now on.

Given \(2\in\mathbb{Z}\), we know that we *cannot* find any integer \(b\) such that \(2\cdot b=b\cdot 2=1\).
It is still possible to find such a number \(b\), but we need to move to *fractions* i.e. consider the set of *rational numbers* \(\mathbb{Q}\) instead of \(\mathbb{Z}\). The set \(\mathbb{Q}\) is not so different from \(\mathbb{Z}\), in particular
all the properties previously stated for \(\mathbb{Z}\) also hold for \(\mathbb{Q}\). Still, if we consider \(2\in\mathbb{Q}\) we can easily find \(b=\frac{1}{2}\in\mathbb{Q}\), for which \(2\cdot\frac{1}{2}=\frac{1}{2}\cdot 1=1\).

We can easily find a similar rational for each *nonzero* element of \(\mathbb{Q}\) (while we cannot for \(0\)).

It is of utmost interest to observe that bits behave like rational numbers rather than integers.
Indeed, \(1\cdot 1=1\) in \(\mathbb{F}_{2}\), but we cannot find any bit \(b\) such that \(1\cdot b=b\cdot 1=1\).

We can formalize this property, saying that each nonzero element of \(\mathbb{Q}\) (respectively \(\mathbb{F}_{2}\)) has a *multiplicative inverse*, i.e.

In \(\mathbb{F}_{2}\), the (multiplicative) inverse of \(1\) is \(1\) and \(0\) has no (multiplicative) inverse
(but keep in mind that the opposite of \(0\) exists: \(-0=0\) in \(\mathbb{F}_{2}\)).

Finally, we show how sum and multiplication interact. Taken \(2,3,4\in\mathbb{Q}\), we have that

This holds in general for three elements of \(\mathbb{Q}\) and we can notice the same good property also in \(\mathbb{F}_{2}\), for example:

\begin{equation} 1\cdot(0+1)=1\cdot 1=1=(1\cdot 0)+(1\cdot 1)=0+1.\nonumber \\ \end{equation}We can formalize this property, saying that, both in \(\mathbb{Q}\) and in \(\mathbb{F}_{2}\), the multiplication is *distributive* w.r.t. the sum.
In formulas

A set \(G\), endowed with two operations (sum and multiplication), denoted by \(+,\cdot\), is called *field* if

- i)
\(G\) is an abelian group w.r.t. \(+\); let \(0\) be the neutral element;

- ii)
\(G\setminus\{0\}\) is an abelian group w.r.t. \(\cdot\);

- iii)
\(\cdot\) is distributive w.r.t. \(+\).

According to the above definition, we can say that both \(\mathbb{Q}\) and \(\mathbb{F}_{2}\) are fields, whereas \(\mathbb{Z}\) is not a field.

The notation \(\mathbb{F}_{2}\) for the set of bits (that - from now on - we will call the *field of bits*), reflects this fact, since \(\mathbb{F}\) stands for ”field” and the subscript \(2\) stands for its size.

Is \(\mathbb{Q}\) an abelian group with respect to the multiplication? If so, prove it; if not, provide a counterexample.

Bits can also be seen as a way to represent the logical values TRUE/FALSE. The
usual notation is \(0=\textrm{FALSE}\) and \(1=\textrm{TRUE}\).

Once fixed this notation,
we have the following well known truth tables:

a | b | a OR b | a AND b | a XOR b |

0 | 0 | 0 | 0 | 0 |

0 | 1 | 1 | 0 | 1 |

1 | 0 | 1 | 0 | 1 |

1 | 1 | 1 | 1 | 0 |

What can you observe by comparing tables \ref{SumProd} and \ref{Logic}?

Can you represent NOT by some expression?

a | NOT a |
---|---|

0 | 1 |

1 | 0 |

Hint: Try to complete the following expression

\begin{equation} \textrm{NOT}\;a=a\_\_\nonumber \\ \end{equation}where \(a\) is in \(\mathbb{F}_{2}=\{0,1\}\) and using \(0,1,+,\cdot\).

Can you represent OR using some expression on bits?

Hint: consider \(a\,\textrm{OR}\,b=\textrm{NOT}\,[(\textrm{NOT}\,a)\,\textrm{AND}\,(\textrm{NOT}\,b)]\) and use the results in \ref{Not}.

## Share on Social Media