ROUGH DRAFT authorea.com/105459
Main Data History
Export
Show Index Toggle 2 comments
  •  Quick Edit
  • Bits, bytes and friends

    Bits standard operations and logic

    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,

    \begin{equation} \mathbb{F}_{2}=\{0,1\}\nonumber \\ \end{equation}

    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.

    \label{SumProd}Sum and product
    \(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\).

    \label{FirstSumMult}

    Compute the following operations in \(\mathbb{F}_{2}\):

    • \((1+1)+0\)

    • \((1+1)+1\)

    • \((1+1)\cdot 1\)

    • \((0+0)+1+(1+0)\cdot 1\)

    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

    \begin{equation} (1+0)+1=1+1=0=1+(0+1)=1+0+1\,.\nonumber \\ \end{equation}

    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

    \begin{equation} \forall a,b,c,\quad(a+b)+c\,=\,a+(b+c)\,=\,a+b+c\,,\nonumber \\ \end{equation}

    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

    \begin{equation} a+b\,=\,b+a\,.\nonumber \\ \end{equation}
    \label{CommAssoc}

    Compute the following operations

    • a.

      \(1+1+1+0+0+0+0+1\)

    • b.

      \(1+1+1+1+0+0+0+0\)

    May you argue the result of b. once knowing a.? If so, which properties of bits are you using?

    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

    \begin{equation} 0+0\,=\,0\quad\textrm{ and }\quad 1+1\,=\,0\,\nonumber \\ \end{equation}

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

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

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

    \label{Opposto}

    What is the opposite of

    • \((1+0)\cdot 1\)?

    • \((0+0)\cdot 0\)?

    • \(1+1+1+1+0+1+(1\cdot 1)\)?

    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.

    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

    \begin{equation} (2\cdot 3)\cdot 4=6\cdot 4=24=2\cdot(3\cdot 4)=2\cdot 12,\nonumber \\ \end{equation}

    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

    \begin{equation} (a\cdot b)\cdot c\,=\,a\cdot(b\cdot c)\,=\,a\cdot b\cdot c\,.\nonumber \\ \end{equation}

    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

    \begin{equation} a\cdot b=b\cdot a.\nonumber \\ \end{equation}

    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.

    \begin{equation} \forall a\in\mathbb{Q}\setminus\{0\}\,(\textrm{ resp }\mathbb{F}_{2}\setminus\{0\}),\,\exists a^{-1}\in\mathbb{Q}\setminus\{0\}\,(\textrm{ respectively }\mathbb{F}_{2}\setminus\{0\})\textrm{ s.t. }a\cdot a^{-1}=a^{-1}\cdot a=1.\nonumber \\ \end{equation}

    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

    \begin{equation} 2\cdot(3+4)=2\cdot 7=14=(2\cdot 3)+(2\cdot 4)=6+8.\nonumber \\ \end{equation}

    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

    \begin{equation} \forall a,b,c\in\mathbb{Q}\quad(\textrm{respectively }\mathbb{F}_{2})\quad a\cdot(b+c)\,=\,(a\cdot b)+(a\cdot c)\,.\nonumber \\ \end{equation}
    \label{Distr}

    Apply the distributive property to the following expressions:

    • \(1\cdot(1+0)\)

    • \(1\cdot(0+1)+0\cdot(1+1)\)

    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 distribu