%--*- latex -*----------------------------------------------------------------- %$Author: saulius $ %$Date: 2020-06-04 14:58:32 +0300 (Thu, 04 Jun 2020) $ %$Revision: 1524 $ %$URL: svn+ssh://saulius-grazulis.lt/home/saulius/svn-repositories/seminarai/2020-verifikacjos-seminarui/slides.tex $ %------------------------------------------------------------------------------ \documentclass[mathserif]{beamer} \usetheme{Warwick} \useoutertheme{infolines} \setbeamertemplate{headline}{} % removes the headline the infolines inserts %\setbeamertemplate{footline}[frame number] \renewcommand\familydefault{\rmdefault} % For XeLaTeX: % https://tex.stackexchange.com/questions/452151/how-do-i-render-the-word-v%C7%ABlundarkvi%C3%B0a-with-bookman-and-xelatex % "Use an OpenType clone of Bookman, for instance TeX Gyre Bonum": \usepackage{fontspec} \setmainfont{TeX Gyre Bonum} \usepackage[style=authoryear,maxnames=1,doi=true,url=true,backend=biber]{biblatex} %\addbibresource{bibliography/citations.bib} \addbibresource{bibliography/Mitasiunas.bib} %\addbibresource{bibliography/Murdocca.bib} %\addbibresource{bibliography/Walker.bib} \newcommand{\mycite}{\parencite} \usepackage{multirow} \usepackage{colordvi} \usepackage{graphicx} \usepackage{tikz} \usetikzlibrary{matrix} \usetikzlibrary{positioning} \usepackage{verbatim} \usepackage{listings} \usepackage{chemfig} \usepackage{listings} % https://en.wikibooks.org/wiki/LaTeX/Algorithms % http://mirror.datacenter.by/pub/mirrors/CTAN/macros/latex/contrib/algorithmicx/algorithmicx.pdf \usepackage{algpseudocode} \usepackage{algorithm} \usepackage{amssymb} \include{commands} % https://tex.stackexchange.com/questions/595/how-can-i-get-bold-math-symbols: \newcommand{\boldm}[1]{\mathversion{bold}#1\mathversion{normal}} \newcommand{\RCSid}[1]{\fontsize{7pt}{7pt}\selectfont $#1$ \today} %%BEGIN LANGUAGE en \title{Number systems. Binary arithmetic} %%END LANGUAGE en \author{Saulius Gražulis} \date{Vilnius, 2020} % Define colors as in % https://venngage.com/blog/color-blind-friendly-palette/ ``Retro'' \definecolor{Bluish}{HTML}{63ACBE} \definecolor{Magentish}{HTML}{601A4A} \definecolor{Orangish}{HTML}{EE442F} \begin{document} \colorlet{OnesComplementColor}{Magentish} \colorlet{TwosComplementColor}{Bluish} \colorlet{TwoToNthColor}{Orangish} \colorlet{IdentifierColor}{red!40!black} \colorlet{StringColor}{green!70!black} \colorlet{KwdColor}{Bluish} \colorlet{CommentColor}{Orangish} %------------------------------------------------------------------------------ \begin{frame} \titlepage \input{affiliation} \begin{center} \mbox{} \hfill\hfill\hfill \includegraphics[height=1.5cm]{images/sp_VU_zenklas.eps} \hfill \includegraphics[height=1.5cm]{images/2019-05-02_Melynas_MIF-zenklas242x244.png} \hfill\hfill\hfill \mbox{} \end{center} \vfill %% \tiny %% \RCSid{ %% $Id: slides.tex 1524 2020-06-04 11:58:32Z saulius $ %% } \begin{flushright} \begin{minipage}[c]{0.67\textwidth} \tiny\raggedright %%BEGIN LANGUAGE en This set of slides may be copied and used as specified in the %%END LANGUAGE en \myhref{http://creativecommons.org/licenses/by-sa/4.0/}{Attribution-ShareAlike 4.0 International} license \end{minipage} %% \begin{minipage}[c]{1.5cm} \myhref{http://creativecommons.org/licenses/by-sa/4.0/}{ \includegraphics[width=1.5cm]{images/CC-BY-SA.eps} } \end{minipage} \end{flushright} \end{frame} %============================================================================== \begin{frame} \frametitle{Binary arithmetic} \begin{center} \small %%BEGIN LANGUAGE en Representable digits in our hardware: \textbf{0} and \textbf{1} %%END LANGUAGE en \end{center} %% \footnotesize \scriptsize %% \fontsize{9}{10}\selectfont \newcommand{\rr}{\rule{4em}{0pt}} \newcommand{\rp}{\rule{2em}{0pt}} \begin{center} \begin{tabular}{|r|r|r|r|r|} \hline System: & dec & bin & oct & hex \\ Base: & \rp{}10 & \rr{}2 & \rp{}8 & \rp{}16 \\ \hline & \only<2->{0} & \only<10->{ 0} & \only<21->{ 0} & \only<24->{ 0} \\ & \only<3->{1} & \only<11->{ 1} & \only<21->{ 1} & \only<24->{ 1} \\ & \only<33>{\bf\em} \only<4->{2} & \only<33>{\bf\color{red}} \only<12>{\color{red}\bf} \only<12->{1}\only<12>{\color{black}}\only<12->{0} & \only<21->{ 2} & \only<24->{ 2} \\ & \only<5->{3} & \only<13->{ 11} & \only<21->{ 3} & \only<24->{ 3} \\ & \only<33>{\bf\em} \only<6->{4} & \only<33>{\bf\color{red}} \only<14>{\color{red}\bf} \only<14->{1}\only<14>{\color{black}}\only<14->{00} & \only<21->{ 4} & \only<24->{ 4} \\ & \only<6->{5} & \only<15->{ 101} & \only<21->{ 5} & \only<24->{ 5} \\ & \only<6->{6} & \only<16->{ 110} & \only<21->{ 6} & \only<24->{ 6} \\ & \only<6->{7} & \only<17->{ 111} & \only<21->{ 7} & \only<24->{ 7} \\ & \only<33>{\bf\em} \only<6->{8} & \only<34>{\bf\color{blue}} \only<33>{\bf\color{red}} \only<18>{\color{red}\bf} \only<18->{1}\only<18>{\color{black}}\only<18->{000} & \only<34>{\bf\color{blue}} \only<33>{\bf\color{red}} \only<22->{ 10} & \only<24->{ 8} \\ & \only<6->{9} & \only<19->{ 1001} & \only<23->{ 11} & \only<24->{ 9} \\ & \only<33>{\bf\color{red}} \only<7>{\color{red}\bf} \only<7->{1}\only<7>{\color{black}}\only<7->{0} & \only<20->{ 1010} & \only<23->{ 12} & \only<25->{ A} \\ & \only<8->{11} & \only<20->{ 1011} & \only<23->{ 13} & \only<26->{ B} \\ & \only<9->{12} & \only<20->{ 1100} & \only<23->{ 14} & \only<27->{ C} \\ & \only<9->{13} & \only<20->{ 1101} & \only<23->{ 15} & \only<28->{ D} \\ & \only<9->{14} & \only<20->{ 1110} & \only<23->{ 16} & \only<29->{ E} \\ & \only<9->{15} & \only<20->{ 1111} & \only<23->{ 17} & \only<30->{ F} \\ & \only<33>{\bf\em} \only<9->{16} & \only<34>{\bf\color{blue}} \only<33>{\bf\color{red}} \only<20->{10000} & \only<34>{\bf\color{blue}} \only<23->{ 20} & \only<34>{\bf\color{blue}} \only<33>{\bf\color{red}} \only<31->{ 10} \\ & \only<9->{17} & \only<20->{10001} & \only<23->{ 21} & \only<32->{ 11} \\ \hline \end{tabular} \end{center} \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Expressing numbers} %%BEGIN LANGUAGE en In base $b$, an $m$-digit number is represented as a polynomial: %%END LANGUAGE en $$ N = a_{m-1}b^{m-1} + a_{m-2}b^{m-2} + \dots + a_2b^2 + a_1b + a_0 $$ Example: $$ \begin{array}{rl} 110101_2 & = 1\cdot2^5 + 1\cdot2^4 + 0\cdot2^3 + 1\cdot2^2 + 0\cdot2^1 + 1\cdot2^0 \\ & = 32_{10} + 16_{10} + 4_{10} + 1_{10} \\ & = 53_{10} \\ \end{array} $$ Another example: $$ 16_{16} = 1\cdot16^1 + 6\cdot16^0 = 16_{10} + 6_{10} = 22_{10} $$ \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Expressing fractions} %%BEGIN LANGUAGE en In base $b$, a fraction $f = 0.a_1a_2\dots{}a_m$ is represented as a polynomial: %%END LANGUAGE en $$ f = a_1b^{-1} + a_2b^{-2} + \dots + a_{m-1}b^{-m+1} + a_mb^{-m} $$ Example: $$ \begin{array}{rcl} 0.0110101_2 & = & 0\cdot2^{-1} + 1\cdot2^{-2} + 1\cdot2^{-3} + 0\cdot2^{-4} + \\ && + 1\cdot2^{-5} + 0\cdot2^{-6} + 1\cdot2^{-7} \\ \\ & = & \frac{1}{4_{10}} + \frac{1}{8_{10}} + \frac{1}{32_{10}} + \frac{1}{128_{10}} \\ \\ & = & 0.4140625_{10} \end{array} $$ \end{frame} %------------------------------------------------------------------------------ \newcommand{\divByTwo}{\multicolumn{1}{|l}{$2_{10}$}} \newcommand{\divByTwoN}[1]{\multicolumn{1}{|l}{\only<#1>{\color{white}}$2_{10}$}} \newcommand{\rmth}[1]{\boldm{$\color{red}#1$}} \newcommand{\rmthN}[2]{\only<#2>{\boldm{$\color{red}#1$}}} \newcommand{\emptycline}[1]{} \begin{frame} \frametitle{Converting into other number systems} \small %%BEGIN LANGUAGE en Division by the system's base gives reminder that is the last digit of the number: %%END LANGUAGE en \only<1>{ $$ \begin{array}{rl} N & = a_{m-1}b^{m-1} + a_{m-2}b^{m-2} + \dots + a_2b^2 + a_1b + a_0 \\ & = b ( a_{m-1}b^{m-2} + a_{m-2}b^{m-3} + \dots + a_2b + a_1 ) + a_0 \end{array} $$ } \only<2->{ $$ 100110_2 / 10_2 = 10011.0_2 \quad \text{(quotient} = 10011_2, \text{reminder} = 0\text{)} $$ $$ 10011_2 / 10_2 = 1001.1_2 \quad \text{(quotient} = 1001_2, \text{reminder} = 1\text{)} $$ } \only<1>{\color{white}} \only<1>{\renewcommand{\cline}{\emptycline}} \only<1>{\renewcommand{\divByTwoN}{}} %%BEGIN LANGUAGE en Thus, repeated division by a \textit{base} gives us digits in that base as \textit{reminders}: %%END LANGUAGE en \begin{center} \begin{tikzpicture} \node (table) { \begin{tabular}{llllllll} $\mathbf{38}$ & \divByTwo \\ \cline{2-2} \only<3->{$\mathbf{38}$} & \only<3->{$19$} & \divByTwoN{1-4} \\ \cline{1-1}\cline{3-3} \rmthN{0}{4-} & \only<6->{$18$} & \only<6->{$9$} & \divByTwoN{1-7} \\ \cline{2-2}\cline{4-4} & \rmthN{1}{7-} & \only<9->{$8$} & \only<9->{$4$} & \divByTwoN{1-10} \\ \cline{3-3}\cline{5-5} & & \rmthN{1}{10-} & \only<12->{$4$} & \only<12->{$2$} & \divByTwoN{1-13} \\ \cline{4-4}\cline{6-6} & & & \rmthN{0}{13-} & \only<15->{$2$} & \only<15->{$1$} & \divByTwoN{1-16} \\ \cline{5-5}\cline{7-7} & & & & \rmthN{0}{16-} & \only<18->{$0$} & \only<18->{$0$} \\ \cline{6-6}\cline{8-8} & & & & & \rmthN{1}{19-} \\ \end{tabular} }; \only<20->{ \draw [red,thick,->] (2,-2) to (-3,0.4); } \node (empty) at (2,-2) {}; \end{tikzpicture} \end{center} \vspace{-\baselineskip} \rule[-0.3\baselineskip]{0pt}{1\baselineskip} \only<21>{$ 100110_2 = 2^5 + 2^2 + 2^1 = 32_{10} + 4_{10} + 2_{10} = \mathbf{38_{10}} $} \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Converting fractions} \small %%BEGIN LANGUAGE en Fractions can be multiplied by the new number base to yield consequently digits after the fraction point: %%END LANGUAGE en \only<1-6>{ \begin{center} \begin{tikzpicture} \node (conv) at (0,0) { \renewcommand{\arraystretch}{1.5} \begin{tabular}{c} \only<1>{\color{white}} $ 0.01101_2 \times 10_2 = 0.1101_2; \quad \lfloor 0.01101_2 \times 10_2 \rfloor = \lfloor 0.1101_2 \rfloor = \mathbf{ \only<2->{\color{red}}0 } $ \\ \only<1-2>{\color{white}} $ \mathbf{0}.1101_2 \times 10_2 = 1.101_2; \lfloor 0.1101_2 \times 10_2 \rfloor = \lfloor 1.101_2 \rfloor = \mathbf{ \only<3->{\color{red}}1 } $ \\ \only<1-3>{\color{white}} $ 1.101_2 - \lfloor 1.101_2 \rfloor = \mathbf{0}.101_2 $ \\ \only<1-4>{\color{white}} $ \mathbf{0}.101_2 \times 10_2 = 1.01_2; \lfloor 1.01_2 \rfloor = \mathbf{ \only<5->{\color{red}}1 } $ \\ \only<6->{\dots} \end{tabular} }; % 'conv.10' means ancor at the node 'conv' rotated 10 degrees % counterclockwise: \only<6->{ \draw [thick,red,->] (conv.5) to ([yshift=1\baselineskip] conv.-30); } % These strategically placed empty nodes keep the size of the image % constant during the '\only<...' cycling: \node (empty) at (-5.5,0) {}; \node (empty) at (5.5,0) {}; \node (empty) at (0,-1.5) {}; \end{tikzpicture} \end{center} } \only<7-16>{ \begin{center} Convert $\mathbf{0.625_{10}}$ to binary. \begin{tikzpicture} \node (conv) at (0,0) { \renewcommand{\arraystretch}{1.5} \begin{tabular}{c} \only<7>{\color{white}} $ 0.625_{10} \times 2_{10} = 1.25_{10}; \quad \lfloor 0.625_{10} \times 2_{10} \rfloor = \lfloor 1.25_{10} \rfloor = \mathbf{ \only<8->{\color{red}}1 } $ \\ \only<7-8>{\color{white}} $ 1.25_{10} - \lfloor 1.25_{10} \rfloor = 0.25_{10} $ \\ \only<7-9>{\color{white}} $ 0.25_{10} \times 2_{10} = 0.5_{10}; \quad \lfloor 0.25_{10} \times 2_{10} \rfloor = \lfloor 0.5_{10} \rfloor = \mathbf{ \only<10->{\color{red}}0 } $ \\ \only<7-10>{\color{white}} $ 0.5_{10} - \lfloor 0.5_{10} \rfloor = 0.5_{10} $ \\ \only<7-11>{\color{white}} $ 0.5_{10} \times 2_{10} = 1.0_{10}; \lfloor 1.0_{10} \rfloor = \mathbf{ \only<12->{\color{red}}1 } $ \\ \only<7-12>{\color{white}} $ 1.0_{10} - \lfloor 1.0_{10} \rfloor = 1 - 1 = 0 \Rightarrow \text{\bf end} $ \end{tabular} }; % 'conv.10' means ancor at the node 'conv' rotated 10 degrees % counterclockwise: \only<14->{ \draw [thick,red,->] (conv.10) to ([yshift=2\baselineskip] conv.-30); } % These strategically placed empty nodes keep the size of the image % constant during the '\only<...' cycling: \node (empty) at (-5.5,0) {}; \node (empty) at (5.5,0) {}; \node (empty) at (0,-2) {}; \end{tikzpicture} \end{center} } \rule[-0.3\baselineskip]{0pt}{1.5\baselineskip} \only<15>{ $0.101_2$ } \only<16>{ $0.101_2 = 1\cdot2^{-1} + 0\cdot2^{-2} + 1\cdot2^{-3} = 0.5_{10} + 0.125_{10} = \mathbf{0.625_{10}}$ } \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Converting to/from base 8 and base 16} \small %%BEGIN LANGUAGE en Dividing by $8_{10}$ gives the \textbf{3} last binary digits as a reminder: %%END LANGUAGE en $$ 1101\,1011_2 / 8_{10} \equiv 1101\,1011_2 / 1000_{2} = 1101\,1.\mathbf{011}_2 $$ %%BEGIN LANGUAGE en Dividing by $16_{10}$ gives the \textbf{4} last binary digits as a reminder: %%END LANGUAGE en $$ 1101\,1011_2 / 16_{10} \equiv 1101\,1011_2 / 10000_{2} = 1101\,.\mathbf{1011}_2 $$ Therefore: \vspace{0.5\baselineskip} \textcolor{blue}{ \fbox{ \parbox{0.94\linewidth}{ %%BEGIN LANGUAGE en To convert to octal (hexadecimal), group your binary digits by 3 (4) and convert each group to a corresponding digit: %%END LANGUAGE en } } } \scriptsize \begin{center} \begin{minipage}{0.2\textwidth} \begin{tabular}{ll} \multicolumn{2}{l}{ Octal digits } \\ 000 & 0 \\ 001 & 1 \\ 010 & 2 \\ 011 & 3 \\ 100 & 4 \\ 101 & 5 \\ 110 & 6 \\ 111 & 7 \\ \end{tabular} \end{minipage} \begin{minipage}{0.45\textwidth} $\longleftarrow$ Example (octal): $ 01011011_2 = \mathbf{{\color{gray}0}01\;011\;011_2} = \mathbf{133_8} $ \vspace{\baselineskip} \rightline{$\longrightarrow$} \rightline{ Example (hexadecimal): } $ 01011011_2 = \mathbf{0101\;1011_2} = \mathbf{5\mathrm{\mathbf{B}}_{16}} $ \end{minipage} \begin{minipage}{0.3\textwidth} \begin{tabular}{ll|ll} \multicolumn{4}{c}{ Hex digits } \\ 0000 & 0 & 1000 & 8 \\ 0001 & 1 & 1001 & 9 \\ 0010 & 2 & 1010 & A \\ 0011 & 3 & 1011 & B \\ 0100 & 4 & 1100 & C \\ 0101 & 5 & 1101 & D \\ 0110 & 6 & 1110 & E \\ 0111 & 7 & 1111 & F \\ \end{tabular} \end{minipage} \end{center} \end{frame} %------------------------------------------------------------------------------ \lstset{ keywordstyle=\color{TwosComplementColor}\bfseries, basicstyle=\ttfamily\footnotesize } \begin{frame}[containsverbatim] \frametitle{XXI century: converting with computer} \small Manual: \begin{lstlisting}[language=bash,frame=trBL,morekeywords={perl,print}] man perlfaq4 \end{lstlisting} Binary $\rightarrow$ decimal: \begin{lstlisting}[language=bash,frame=trBL,morekeywords={perl,print}] perl -le 'print 0b_0110_1011' 107 \end{lstlisting} Hex $\rightarrow$ binary: \begin{lstlisting}[language=bash,frame=trBL,morekeywords={perl,print}] perl -e 'printf "%016b\n", 0x23FF' 0010001111111111 \end{lstlisting} Octal $\rightarrow$ hex: \begin{lstlisting}[language=bash,frame=trBL,morekeywords={perl,print}] perl -e 'printf "%02X\n", 0133' 5B \end{lstlisting} Caution: this works as expected only for small numbers ($|n| < 2^{31}$)! \end{frame} %------------------------------------------------------------------------------ \begin{frame}[containsverbatim] \frametitle{XXI century: converting fractions} \small Convert binary fraction $0.0110\,1011_2 = 0110\,1011_2 / 1\,0000\,0000_2$ to decimal: \vspace{\baselineskip} \begin{lstlisting}[language=bash,frame=trBL,morekeywords={perl,print}] perl -le 'print 0b_0110_1011 / (2**8)' 0.41796875 \end{lstlisting} \end{frame} %------------------------------------------------------------------------------ \begin{frame}[containsverbatim] \frametitle{XXI century: converting fractions} \small Convert binary fraction $0.0110\,1011_2 = 0110\,1011_2 / 1\,0000\,0000_2$ to decimal: \vspace{\baselineskip} \begin{lstlisting}[language=bash,frame=trBL,morekeywords={perl,print}] perl -le 'print 0b_0110_1011 / (2**8)' 0.41796875 \end{lstlisting} Check it: \begin{lstlisting}[basicstyle=\ttfamily\tiny,language=bash,frame=trBL,morekeywords={perl,print}] perl -e '$x=0.41796875; print "0."; while($x) {$x*=2; print int($x); $x-=int($x)}; print "\n"' 0.01101011 \end{lstlisting} %%BEGIN LANGUAGE en Caution: this method (and the check) works \textbf{\textit{only}} if the fraction is \textbf{exactly} representable in our computer! %%END LANGUAGE en \end{frame} %------------------------------------------------------------------------------ \lstset{ language=perl, keywordstyle=\color{KwdColor}, commentstyle=\color{CommentColor}\ttfamily, identifierstyle=\color{IdentifierColor}, stringstyle=\color{StringColor}, basicstyle=\ttfamily\tiny } \begin{frame}[containsverbatim] \frametitle{Convert $0.1_{10}$} \small \vspace{-\baselineskip} $$ 0.1_{10} = 1/10_{10} $$ File: \texttt{"examples/code/one-tenth.c"} \lstinputlisting[language=C,basicstyle=\ttfamily\tiny,frame=trBL, linerange={1-12,17-30}] {examples/code/one-tenth.c} \end{frame} %------------------------------------------------------------------------------ \begin{frame}[containsverbatim] \frametitle{Convert $0.1_{10}$} \small \vspace{-\baselineskip} $$ 0.1_{10} = 1/10_{10} $$ \begin{lstlisting}[basicstyle=\ttfamily\tiny,language=bash,frame=trBL,morekeywords={perl,print}] sh$ examples/code/one-tenth 0.0001 1001 1001 1001 1001 \end{lstlisting} $$ 0.1_{10} = 0.0001\,\overline{1001}_2 $$ Infinite periodic (repeating) binary fraction! \vspace{\baselineskip} \color{blue} \fbox{ \parbox{0.9\textwidth}{ %%BEGIN LANGUAGE en If the fully reduced denominator of a fraction has a prime factor that is \textbf{\textit{not}} a factor of a number base, then expansion is non-terminating in that base. %%END LANGUAGE en } } \vspace{\baselineskip} \color{black} E.g. $1/10_{10}$: $$ \begin{array}{rl} 10_{10} = 2 \times 5; & 5 \ \text{ is not a factor of }\ 2 \\ \Rightarrow & 1/10_{10} = 0.0001\,\overline{1001}_2 \ \text{ is non-terminating } \\ \end{array} $$ \end{frame} %------------------------------------------------------------------------------ % Black digit: \newcommand{\bd}[2]{\only<#1>{#2}} % Red digit: \newcommand{\rd}[2]{\only<#1>{\color{TwoToNthColor}#2}} % Gray digit: \newcommand{\gd}[2]{\only<#1>{\color{gray}#2}} \begin{frame} \frametitle{Binary arithmetic} \only<1-2>{ \begin{quote} \footnotesize /.../ Būtinas minimumas yra sudėtis, nes atimtis tai yra sudėtis su papildomu kodu, daugyba – daug sudėčių cikle, o dalyba – daug atimčių. %%BEGIN LANGUAGE en \vspace{\baselineskip} The single required operation is addition, since subtraction is addition in complementary code, multiplication is multiple additions in a loop and division is multiple subtractions. %%END LANGUAGE en \end{quote} \rightline{ \begin{minipage}{0.4\textwidth} \scriptsize Antanas Mitašiūnas \parencite*{Mitasiunas2016} \\ ``Kompiuterių architektūra“, p.~9 \end{minipage} } \vspace{\baselineskip} } \begin{center} \begin{minipage}{0.4\textwidth} \begin{center} Addition: $$ A + B $$ \begin{tabular}{rr|rr} & \multicolumn{1}{l}{} & \multicolumn{2}{c}{B} \\ & $+$ & 0 & 1 \\ \cline{2-4} \multirow{2}{*}{A} & 0 & 0 & 1 \\ & 1 & 1 & \textcolor{TwoToNthColor}{1}0 \\ \end{tabular} \end{center} \end{minipage} \begin{minipage}{0.4\textwidth} \only<2->{ \begin{center} Multiplication: $$ A \times B $$ \begin{tabular}{rr|rr} & \multicolumn{1}{l}{} & \multicolumn{2}{c}{B} \\ & $\times$ & 0 & 1 \\ \cline{2-4} \multirow{2}{*}{A} & 0 & 0 & 0 \\ & 1 & 0 & 1 \\ \end{tabular} \end{center} } \end{minipage} \end{center} \rule[-1.7cm]{0pt}{3.5cm} \begin{minipage}[t]{0.4\textwidth} \only<3->{ \begin{center} \setlength{\tabcolsep}{0pt} \begin{tabular}{rcccccc} \multirow{4}{*}{$+$} & \rd{8-}{1} & \rd{7-}{1} & & & \rd{4-}{1} & \\ & \color{white}0 & 1 & 1 & 1 & 0 & 1 \\ & & 1 & 1 & 0 & 0 & 1 \\ \hline & \bd{9-}{1} & \bd{8-}{1} & \bd{7-}{0} & \bd{6-}{1} & \bd{5-}{1} & \bd{4-}{0} \\ \end{tabular} \end{center} } \end{minipage} \begin{minipage}[t]{0.4\textwidth} \only<10->{ \begin{center} \setlength{\tabcolsep}{0pt} \begin{tabular}{rccccccc} \multirow{2}{*}{$\times$} \color{white}0 & \color{white}0 & \color{white}0 & 1 & 1 & 0 & 1 \\ && & & 1 & 0 & 1 \\ \hline \only<1-13>{ &&&& \\ } \only<14->{ & \rd{14-}{1} & \rd{14-}{1} & \rd{14-}{1} \\ } && & \bd{11-}{1} & \bd{11-}{1} & \bd{11-}{0} & \bd{11-}{1} \\ && \gd{12-}{0} & \gd{12-}{0} & \gd{12-}{0} & \gd{12-}{0} \\ &\bd{13-}{1} & \bd{13-}{1} & \bd{13-}{0} & \bd{13-}{1} \\ \hline \only<14->{ \bd{14-}{1} & \bd{14-}{0} & \bd{14-}{0} & \bd{14-}{0} & \bd{14-}{0} & \bd{14-}{0} & \bd{14-}{1} & \\ } \end{tabular} \end{center} } \end{minipage} \end{frame} %------------------------------------------------------------------------------ \newcommand{\Rc}{\color{TwoToNthColor}} \newcommand{\Bc}{\color{TwosComplementColor}} \newcommand{\Yc}{\color{black}} \begin{frame} \frametitle{Bitwise logic operations} %%BEGIN LANGUAGE en We will abbreviate the term \textit{binary digit} to \textit{bit}. %%END LANGUAGE en \vfill %%BEGIN LANGUAGE en Useful operations can be performed on the single bits of a number independently. %%END LANGUAGE en \vfill \vfill \begin{minipage}{0.45\textwidth} Mask bits: $$ \begin{array}{rr} &1101\,1010\,0111 \\ \text{AND}& \color{black}000\color{TwoToNthColor}1\,1111\,1\color{black}000 \\ &\text{\rule[0.9\baselineskip]{6em}{0.5pt}} \\ &\color{gray} 000\color{TwosComplementColor}1\,1010\,0\color{gray}000 \end{array} $$ \end{minipage} \hspace{0.5em} \only<2->{ \begin{minipage}{0.45\textwidth} Set bits: $$ \begin{array}{rr} &1101\,1010\,0111 \\ \text{OR}& \color{black}000\color{TwoToNthColor}1\,1111\,1\color{black}000 \\ &\text{\rule[0.9\baselineskip]{6em}{0.5pt}} \\ &\color{gray} 110\color{TwosComplementColor}1\,1111\,1\color{gray}111 \end{array} $$ \end{minipage} } \vfill \parbox[b]{0pt}{ \rule{0pt}{3.2\baselineskip} } \begin{minipage}[b]{0.95\textwidth} \only<3->{ Questions: $$ 2\mathrm{B} \ \text{OR}\ \text{NOT}\ 2\mathrm{B} = \text{??} $$ } \end{minipage} \parbox[c]{0pt}{ \rule[-\baselineskip]{0pt}{2\baselineskip} } \begin{minipage}[c]{0.95\textwidth} \only<4->{ %%BEGIN LANGUAGE en What is the bit mask to check whether the number is odd? %%END LANGUAGE en } \end{minipage} \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Intuitive understanding of information content} %%BEGIN LANGUAGE en Find out which of four symbols was transmitted by asking yes/no questions: %%END LANGUAGE en ``A'', ``B'', ``1'', ``2''. \begin{center} \begin{tikzpicture} \node (A) { letter/digit? }; \node (B) [below left = of A] { vowel/consonant? }; \node (C) [below right = of A] { odd/even? }; \node (D) [below left = of B, xshift=+1cm] {``Α''}; \node (E) [below right = of B, xshift=-1cm] {``Β''}; \node (F) [below left = of C, xshift=+1cm] {``1''}; \node (G) [below right = of C, xshift=-1cm] {``2''}; \draw [->,thick] (node cs: name=A) -- (node cs: name=B); \draw [->,thick] (node cs: name=A) -- (node cs: name=C); \draw [->,thick] (node cs: name=B) -- (node cs: name=D); \draw [->,thick] (node cs: name=B) -- (node cs: name=E); \draw [->,thick] (node cs: name=C) -- (node cs: name=F); \draw [->,thick] (node cs: name=C) -- (node cs: name=G); \end{tikzpicture} \end{center} \vspace{-2\baselineskip} \begin{center} \renewcommand{\arraystretch}{1.2} $$ \begin{array}{c} N_{\text{\rm{symbols}}} = N_{\text{\rm{leaves}}} = 2^{n_{\text{\rm{questions}}}} = 2^{n_{\text{\rm{layers}}}} \\ n_{\text{\rm{questions}}} = n_{\text{\rm{layers}}} = \log_2 N_{\text{\rm{symbols}}} = \log_2 \frac{1}{p_{\text{\rm{symbol}}}} = - \log_2 p_{\text{\rm{symbol}}} \\ n_\text{q} = \log_2 N_\text{s} = \log_2 4 = - \log_2 \frac{1}{4} = \log_2 2^2 = 2 \end{array} $$ \end{center} \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Intuitive understanding of information (2)} %%BEGIN LANGUAGE en One out of 8 symbols: %%END LANGUAGE en ``A'', ``B'', ``E'', ``F'', ``1'', ``2'', ``3'', ``4''. \begin{center} \resizebox{!}{3.5cm}{ %% https://tex.stackexchange.com/questions/4338/correctly-scaling-a-tikzpicture: \begin{tikzpicture} \node (A) { letter/digit? }; \node (B) [below left = of A, xshift=-1cm] { vowel/consonant? }; \node (C) [below right = of A, xshift=+1cm] { odd/even? }; \node (D) [below left = of B, xshift=+2cm] { smaller/larger? }; \node (E) [below right = of B, xshift=-2cm] { smaller/larger? }; \node (F) [below left = of C, xshift=+1.5cm] { smaller/larger? }; \node (G) [below right = of C, xshift=-1.5cm] { smaller/larger? }; \node (n1) [below left = of D, xshift=+2cm] {``Α''}; \node (n2) [below right = of D, xshift=-2cm] {``E''}; \node (n3) [below left = of E, xshift=+2cm] {``B''}; \node (n4) [below right = of E, xshift=-2cm] {``F''}; \node (n5) [below left = of F, xshift=+2cm] {``1''}; \node (n6) [below right = of F, xshift=-2cm] {``3''}; \node (n7) [below left = of G, xshift=+2cm] {``2''}; \node (n8) [below right = of G, xshift=-2cm] {``4''}; \draw [->,thick] (node cs: name=A) -- (node cs: name=B); \draw [->,thick] (node cs: name=A) -- (node cs: name=C); \draw [->,thick] (node cs: name=B) -- (node cs: name=D); \draw [->,thick] (node cs: name=B) -- (node cs: name=E); \draw [->,thick] (node cs: name=C) -- (node cs: name=F); \draw [->,thick] (node cs: name=C) -- (node cs: name=G); \draw [->,thick] (node cs: name=D) -- (node cs: name=n1); \draw [->,thick] (node cs: name=D) -- (node cs: name=n2); \draw [->,thick] (node cs: name=E) -- (node cs: name=n3); \draw [->,thick] (node cs: name=E) -- (node cs: name=n4); \draw [->,thick] (node cs: name=F) -- (node cs: name=n5); \draw [->,thick] (node cs: name=F) -- (node cs: name=n6); \draw [->,thick] (node cs: name=G) -- (node cs: name=n7); \draw [->,thick] (node cs: name=G) -- (node cs: name=n8); \end{tikzpicture} } \end{center} \vspace{-2\baselineskip} \begin{center} \renewcommand{\arraystretch}{1.5} $$ \begin{array}{c} N_{\text{\rm{symbols}}} = N_{\text{\rm{leaves}}} = 2^{n_{\text{\rm{questions}}}} = 2^{n_{\text{\rm{layers}}}} \\ n_{\text{\rm{questions}}} = n_{\text{\rm{layers}}} = \log_2 N_{\text{\rm{symbols}}} = \log_2 \frac{1}{p_{\text{\rm{symbol}}}} = - \log_2 p_{\text{\rm{symbol}}} \\ n_\text{q} = \log_2 N_\text{s} = \log_2 8 = -\log_2 \frac{1}{8} = \log_2 2^3 = 3 \end{array} $$ \end{center} \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Info content depends in probability} %%BEGIN LANGUAGE en One out of 4 symbols: %%END LANGUAGE en ``A'', ``B'', ``1'', ``2'' \begin{center} ``AAA\textcolor{red}{1}AAA\textcolor{red}{B}A\textcolor{red}{1}A\textcolor{red}{2}AAA\textcolor{red}{1}AAAA'' \footnotesize (20 symbols ) \end{center} \begin{center} \resizebox{!}{3.5cm}{ %% https://tex.stackexchange.com/questions/4338/correctly-scaling-a-tikzpicture: \begin{tikzpicture} \node (A) { is it ``A''? }; \node (B) [below left = of A] {``A'' ($p = 0.75$)}; \node (C) [below right = of A] { is it ``1''? }; \node (D) [below left = of C, xshift = +1cm] { is it a digit? }; \node (E) [below right = of C, xshift = -1cm] {``1'' ($p = 0.15$)}; \node (d1) [below left = of D, xshift = +1cm] {``B'' ($p = 0.05$)}; \node (d2) [below right = of D, xshift = -1cm] {``2'' ($p = 0.05$)}; \draw [->,thick] (node cs: name=A) -- (node cs: name=B) node [near start, anchor = east] { \scriptsize \parbox{2cm}{ \begin{center} Yes $p_c = 0.75$ \end{center} } }; \draw [->,thick] (node cs: name=A) -- (node cs: name=C) node [near start, anchor = west, xshift = 0.3cm] { \scriptsize \parbox{2cm}{ \begin{center} No $p_c = 0.25$ \end{center} } }; \draw [->,thick] (node cs: name=C) -- (node cs: name=D) node [near start, anchor = east] { \scriptsize \parbox{2cm}{ \begin{center} No $p_c = 0.4$ \end{center} } }; \draw [->,thick] (node cs: name=C) -- (node cs: name=E) node [near start, anchor = west] { \scriptsize \parbox{2cm}{ \begin{center} Yes $p_c = 0.6$ \end{center} } }; \draw [->,thick] (node cs: name=D) -- (node cs: name=d1) node [near start, anchor = east] { \scriptsize \parbox{2cm}{ \begin{center} No $p_c = 0.5$ \end{center} } }; \draw [->,thick] (node cs: name=D) -- (node cs: name=d2) node [near start, anchor = west] { \scriptsize \parbox{2cm}{ \begin{center} Yes $p_c = 0.5$ \end{center} } }; \end{tikzpicture} } \end{center} \footnotesize \visible<2->{ For equal probabilities: $n_{\mathrm{q}} = \log_2 N_{\mathrm{s}} = \log_2 \frac{1}{p_{\mathrm{s}}} = - \log_2 p_{\mathrm{s}} = \log_2 4 = \mathbf{2}$ } \visible<3->{ For the specified question sequence (Huffman encoding): $n_{\mathrm{q}} = 0.75 + 2 \times 0.15 + 2 \times 3 \times 0.05 = \mathbf{1.35}$ } \visible<4>{ Theoretical limit: $n_{\mathrm{q}} = - \sum_{i=1}^{4} p_i \log_2 p_i = \mathbf{1.15}$ } \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Bits and bytes. Information content} \renewcommand{\arraystretch}{1.5} %%BEGIN LANGUAGE en Assume we have a source that can send messages from the set %%END LANGUAGE en $S = \{ M_1, \dots, M_n \}, \; n \in \mathbb{N}$. Then: $$ \begin{array}{l} S = \{ M_1, \dots, M_n \} \\ p_i = Pr(M_i), \;\; i = 1\dots n\\ I_{M_i} = - \log p_i \\ H = - \displaystyle\sum_{i=1}^{n} p_i \log p_i\\ \end{array} $$ \renewcommand{\arraystretch}{1} Here: $$ \begin{array}{lll} Pr(M_i) & \text{--} & \text{ probability of message $M_i$; }\\ I_{M_i} & \text{--} & \text{ information content of message $M_i$; } \\ H & \text{--} & \text{ \parbox[t]{0.8\textwidth}{ %%BEGIN LANGUAGE en entropy of the source, or average information content per message %%END LANGUAGE en } } \\ \end{array} $$ \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Two level signal $\neq$ 1 bit} \only<1-2>{ \begin{center} Two-wire single bit representation: \end{center} } \only<3-4>{ \begin{center} \begin{tabular}{cc} \scriptsize \begin{minipage}[b]{4cm} $$ \overbrace{\rule{2cm}{0pt}}^{ \begin{aligned} Pr(\text{"0"}) &= Pr(\text{"1"}) = 0.5 \\ H &= - 2 \cdot 0.5 \cdot \log_2 0.5 \\ &= - 2 \cdot (-0.5) \\ &= \mathbf{1} \; \text{\bf bit/message } \\ \end{aligned} } $$ \end{minipage} & \scriptsize \begin{minipage}[b]{4.5cm} $$ \overbrace{\rule{4cm}{0pt}}^{ \begin{aligned} Pr(\text{"01"}) =& Pr(\text{"10"}) = 0.5 \\ Pr(\text{"00"}) =& Pr(\text{"11"}) = 0 \\ H =&- Pr(\text{"01"}) \cdot \log_2 Pr(\text{"01"}) \\ &- Pr(\text{"10"}) \cdot \log_2 Pr(\text{"10"}) \\ &- \displaystyle\lim_{Pr(\text{"00"})\rightarrow0} Pr(\text{"00"}) \cdot \log_2 Pr(\text{"00"}) \\ &- \displaystyle\lim_{Pr(\text{"11"})\rightarrow0} Pr(\text{"11"}) \cdot \log_2 Pr(\text{"11"}) \\ =&-2 \cdot 0.5 \cdot (-1) \\ =& \mathbf{1} \;\text{\bf bit/message } \\ \end{aligned} } $$ \end{minipage} \end{tabular} \end{center} } \only<3->{ \vspace{-3\baselineskip} } \begin{center} \parbox[c]{3.5cm}{ \only<1,3>{ \includegraphics[width=\linewidth]{drawings/decoders/1-out-of-2-select-1.png} } \only<2,4>{ \includegraphics[width=\linewidth]{drawings/decoders/1-out-of-2-select-2.png} } } \end{center} \only<5->{ \begin{center} Decoder 1-of-4 \end{center} \only<5>{ \begin{center} \includegraphics[height=5cm]{drawings/decoders/1-of-4-decoder-select-1.png} \end{center} } \only<6>{ \begin{center} \includegraphics[height=5cm]{drawings/decoders/1-of-4-decoder-select-2.png} \end{center} } \only<7>{ \begin{center} \includegraphics[height=5cm]{drawings/decoders/1-of-4-decoder-select-3.png} \end{center} } \only<8>{ \begin{center} \includegraphics[height=5cm]{drawings/decoders/1-of-4-decoder-select-4.png} \end{center} } } \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Half-adder} \begin{center} \begin{tabular}{rr|rr} \multicolumn{4}{c}{ Addition: } \\ \multicolumn{4}{c}{$ A + B $} \\ & \multicolumn{1}{l}{} & \multicolumn{2}{c}{B} \\ & $+$ & 0 & 1 \\ \cline{2-4} \multirow{2}{*}{A} & 0 & 0 & 1 \\ & 1 & 1 & \textcolor{TwoToNthColor}{1}0 \\ \end{tabular} \hspace{2em} \begin{tabular}{cc|c} \multicolumn{3}{c}{ Sum: }\\ \textbf{A} & \textbf{B} & \textbf{S} \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{tabular} \hspace{2em} \begin{tabular}{cc|c} \multicolumn{3}{c}{ Carry: }\\ \textbf{A} & \textbf{B} & \textbf{C} \\ \hline 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & \textcolor{TwoToNthColor}{1} \\ \end{tabular} \end{center} \begin{center} \parbox{2em}{ \only<2->{ \bf \begin{tabular}{r} A \\ \\ B\\ \\ \\ \end{tabular} } } % \parbox{4cm}{ \only<2>{ \includegraphics[width=\linewidth]{drawings/adders/half-adder-A0-B0.png} } \only<3>{ \includegraphics[width=\linewidth]{drawings/adders/half-adder-A1-B0.png} } \only<4>{ \includegraphics[width=\linewidth]{drawings/adders/half-adder-A0-B1.png} } \only<5>{ \includegraphics[width=\linewidth]{drawings/adders/half-adder-A1-B1.png} } } % \parbox{2em}{ \only<2->{ \bf \begin{tabular}{l} S \\ \\ \\ C\\ \\ \end{tabular} } } \end{center} \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Full adder} \small \begin{center} \begin{tabular}{ccc|c} \multicolumn{4}{c}{ Sum: }\\ \textbf{C$_\text{in}$} & \textbf{A} & \textbf{B} & \textbf{S} \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ \end{tabular} \hspace{2em} \begin{tabular}{ccc|ccc} \multicolumn{4}{c}{ Carry: }\\ \textbf{C$_\text{in}$} & \textbf{A} & \textbf{B} & \textbf{C$_\text{out}$} \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & \textcolor{TwoToNthColor}{1} & $\overline{C_{in}}AB$ & $AB$ \\ \hline 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & \textcolor{TwoToNthColor}{1} & $C_{in}\overline{A}B$ & $C_{in}B$ \\ 1 & 1 & 0 & \textcolor{TwoToNthColor}{1} & $C_{in}A\overline{B}$ & $C_{in}A$ \\ 1 & 1 & 1 & \textcolor{TwoToNthColor}{1} & $C_{in}AB$ \\ \end{tabular} \end{center} \begin{center} \parbox[c]{4cm}{ \includegraphics[width=\linewidth]{drawings/adders/full-adder-sum-A0-B0.png} } \parbox[c]{4.5cm}{ \includegraphics[width=\linewidth]{drawings/adders/full-adder-carry-compact-A0-B0-C0.png} } \end{center} \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Full adder (naïve)} \hfill \begin{minipage}{0.3\textwidth} \scriptsize \begin{tabular}{ccc|cc} \multicolumn{5}{c}{ Sum and Carry: }\\ \textbf{C$_\text{in}$} & \textbf{A} & \textbf{B} & \textbf{C$_\text{out}$} & \textbf{S} \\ \hline \only<1>{\bf} 0 & \only<1>{\bf} 0 & \only<1>{\bf} 0 & \only<1>{\bf} 0 & \only<1>{\bf} 0 \\ \only<3>{\bf} 0 & \only<3>{\bf} 0 & \only<3>{\bf} 1 & \only<3>{\bf} 0 & \only<3>{\bf} 1 \\ {} 0 & {} 1 & {} 0 & {} 0 & {} 1 \\ {} 0 & {} 1 & {} 1 & {} \textcolor{TwoToNthColor}{1} & {} 0 \\ \hline \only<2>{\bf} 1 & \only<2>{\bf} 0 & \only<2>{\bf} 0 & \only<2>{\bf} 0 & \only<2>{\bf} 1 \\ \only<4>{\bf} 1 & \only<4>{\bf} 0 & \only<4>{\bf} 1 & \only<4>{\bf} \textcolor{TwoToNthColor}{1} & \only<4>{\bf} 0 \\ {} 1 & {} 1 & {} 0 & {} \textcolor{TwoToNthColor}{1} & {} 0 \\ \only<5>{\bf} 1 & \only<5>{\bf} 1 & \only<5>{\bf} 1 & \only<5>{\bf} \textcolor{TwoToNthColor}{1} & \only<5>{\bf} 1 \\ \end{tabular} \end{minipage} \hfill \begin{minipage}[t]{2em} \scriptsize \begin{tabular}{r} \\ \textbf{C$_\text{in}$} \\ \\ \bf A \\ \\ \bf B \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \end{tabular} \end{minipage} \begin{minipage}[t]{0.4\textwidth} \begin{center} \parbox{4cm}{ \only<1>{ \includegraphics[width=\linewidth]{drawings/adders/full-adder-naive-A0-B0-C0.png} } \only<2>{ \includegraphics[width=\linewidth]{drawings/adders/full-adder-naive-A1-B0-C0.png} } \only<3>{ \includegraphics[width=\linewidth]{drawings/adders/full-adder-naive-A0-B1-C0.png} } \only<4>{ \includegraphics[width=\linewidth]{drawings/adders/full-adder-naive-A1-B1-C0.png} } \only<5>{ \includegraphics[width=\linewidth]{drawings/adders/full-adder-naive-A1-B1-C1.png} } } \end{center} \end{minipage} \begin{minipage}[t]{2em} \scriptsize \begin{tabular}{l} \bf S \\ \\ \\ \\ \\ \\ \\ \textbf{C$_\text{out}$} \\ \\ \\ \\ \end{tabular} \end{minipage} \hfill \mbox{} \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Full adder} \begin{center} \parbox[c]{4cm}{ \includegraphics[width=\linewidth]{drawings/adders/full-adder-naive-A0-B0-C0.png} } \hspace{2em} \parbox[c]{5cm}{ \includegraphics[width=\linewidth]{drawings/adders/full-adder-A0-B0-C0.png} } \end{center} \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Full adder symbols} \begin{center} \parbox[c]{3cm}{ \begin{center} \includegraphics[width=0.8\linewidth]{drawings/adders/adder-symbol.eps} \vspace{\baselineskip} \includegraphics[width=0.7\linewidth]{drawings/adders/adder-symbol-logisim-A0-B0-C0.png} \end{center} } \hspace{2em} \parbox[c]{5cm}{ \includegraphics[width=\linewidth]{drawings/adders/full-adder-A0-B0-C0.png} } \end{center} \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{4-bit adder} \begin{center} \hfill $ 0101_2 + 1110_2 = \textcolor{TwoToNthColor}{1}\,0011_2 $\hfill $ 5_{16} + \mathrm{E}_{16} = \textcolor{TwoToNthColor}{1}3_{16} $\hfill $ 5_{10} + 14_{10} = 19_{10} $\hfill\mbox{} \vspace{\baselineskip} \hfill \parbox[c]{3.5cm}{ \includegraphics[width=\linewidth]{drawings/adders/full-adder-component-5+E.png} } \hfill \parbox[c]{3.5cm}{ \includegraphics[width=\linewidth]{drawings/adders/full-adder-4-bit-logisim-5+E.png} } \hfill \mbox{} \end{center} \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Single digit multiplier} \only<1>{ \begin{center} \parbox[c]{6cm}{ \includegraphics[width=\linewidth]{drawings/multipliers/operand-times-single-digit-0.png} } \end{center} } \only<2>{ \begin{center} \parbox[c]{6cm}{ \includegraphics[width=\linewidth]{drawings/multipliers/operand-times-single-digit-1.png} } \end{center} } \only<1>{ \begin{center} \parbox[c]{4cm}{ \includegraphics[width=\linewidth]{drawings/multipliers/mult-block-times-single-digit-0.png} } \end{center} } \only<2>{ \begin{center} \parbox[c]{4cm}{ \includegraphics[width=\linewidth]{drawings/multipliers/mult-block-times-single-digit-1.png} } \end{center} } \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{4-bit naïve multiplier} \begin{center} \hfill \only<1>{ $ 1101_2 \times 0101_2 = 0100\,0001_2 $\hfill $ \mathrm{D}_{16} \times 5_{16} = 41_{16} $\hfill $ 13_{10} \times 5_{10} = 65_{10} $\hfill\mbox{} } \only<2>{ $ 1111_2 \times 1100_2 = 1011\,0100_2 $\hfill $ \mathrm{F}_{16} \times \textrm{C}_{16} = \mathrm{B}4_{16} $\hfill $ 15_{10} \times 12_{10} = 180_{10} $\hfill\mbox{} } \vspace{0.5\baselineskip} \parbox[c]{12cm}{ \only<1>{ \includegraphics[width=\linewidth]{drawings/multipliers/simple-multiplier-Dx5.png} } \only<2>{ \includegraphics[width=\linewidth]{drawings/multipliers/simple-multiplier-FxC.png} } } \end{center} \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Subtraction} Subtracting smaller from larger is easy: $$ \renewcommand{\arraystretch}{1.7} \begin{array}{c} 1101_2 - 100_2 = 1001_2 \\ 1101_2 - 11_2 = 1\overset{\textcolor{TwoToNthColor}{1}}{1}\textcolor{TwoToNthColor}{0}1_2 - 11_2 = 1010_2 \\ 10_2 - 11_2 = \text{???} \end{array} $$ What happens if we add? \begin{center} \begin{tabular}{llllll} \multirow{2}{*}{$+$} & & 0 & 0 & 0 & 1 \\ & & 1 & 1 & 1 & 1 \\ \hline & \textcolor{gray}{1} & 0 & 0 & 0 & 0 \\ \end{tabular} \end{center} \end{frame} %------------------------------------------------------------------------------ \definecolor{verylightgray}{rgb}{0.9, 0.9, 0.9} \begin{frame} \frametitle{Negative numbers} Add large numbers so that a carry is generated: \begin{center} \begin{tabular}{llllll} \multirow{2}{*}{$+$} & & 0 & 0 & 0 & 1 \\ & & 1 & 1 & 1 & 1 \\ \hline & \textcolor{verylightgray}{1} & 0 & 0 & 0 & 0 \\ \end{tabular} \end{center} i.e.: $$ 1111_2 + 1_2 = 0_2 $$ but we know that $$ (-1) + 1 = 0 $$ Can we say that $ 1111_2 = -1_2 $ in some sense? \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Two's complement} Adding $1111$ means: $ 1111_2 = \textcolor{TwosComplementColor}{1\,0000_2 - 1} = 2^4 - 1 $ \vspace{\baselineskip} Disregarding the carry digit means subtracting \textcolor{TwoToNthColor}{$ 1\,0000_2 = 2^4 $} \vspace{\baselineskip} Thus $$ { \begin{aligned} 1 + \textcolor{TwosComplementColor}{1111_2} \; \text{\textcolor{TwoToNthColor}{ \footnotesize (disregarding carry) }} &= 1 + (\textcolor{TwosComplementColor}{1\,0000_2 - 1}) - \textcolor{TwoToNthColor}{1\,0000_2} \\ &= 1 - 1 \\ &= 0 \\ \end{aligned} } $$ Let's see – it works for any number of N bits: $$ a + \underbrace{(\textcolor{TwosComplementColor}{2^N - b})}_{\text{ 2's complement of $b$ }} - \;\textcolor{TwoToNthColor}{2^N} = a - b $$ \end{frame} %------------------------------------------------------------------------------ \begin{frame} \frametitle{Take home messages} \begin{itemize} \item %%BEGIN LANGUAGE en Binary is a natural positional number system for digital computations; simple algorithms exist to convert numbers between binary and other number systems, but systems with bases 8 and 16 are the most convenient to represent binary numbers. %%END LANGUAGE en \item %%BEGIN LANGUAGE en Perl one-liners can be useful for number conversions; %%END LANGUAGE en \item %%BEGIN LANGUAGE en Not every conversion can be made exactly! %%END LANGUAGE en \item %%BEGIN LANGUAGE en Not always a two-state signal carries 1 bit of information! %%END LANGUAGE en \item %%BEGIN LANGUAGE en We can construct digital logic circuits to perform binary arithmetic (addition, subtraction, multiplication, etc.) %%END LANGUAGE en \end{itemize} \end{frame} %------------------------------------------------------------------------------ %% \begin{frame} %% %%LANGUAGE en \frametitle{Ternary logic gate} %% %%LANGUAGE lt \frametitle{Trejetainis loginis ventilis} %% %%LANGUAGE ru \frametitle{Троичный логический вентиль} %% %% %% \end{frame} %------------------------------------------------------------------------------ \begin{frame}[allowframebreaks] \frametitle{References} \renewcommand{\bibfont}{\scriptsize} \printbibliography \end{frame} %------------------------------------------------------------------------------ \end{document} % 2023-09-11 08:52:35 EEST