\documentclass[german]{tutstyle} \usepackage[ansinew]{inputenc} \usepackage{amssymb} \usepackage[fleqn,intlimits]{amsmath} \usepackage{amsthm} \newcommand{\x}{\cdot} \DeclareMathOperator{\ld}{ld} \tutno{1} \topic{Stellenwertsysteme, Binäres Rechnen, Codierung} \date{20. Oktober 2003} \begin{document} \title{Info I -- Tutorium 1} \author{Markus Westphal\\ tut01@markuswestphal.de } % \maketitle \section*{Zahlendarstellung, Stellenwertsystem} Unterscheide zwischen \begin{itemize} \item dem \emph{Zahlenwert} selbst ("`Zweiundzwanzig"') und \item der \emph{Darstellung} (z.B. $22_{10}$ aber auch $10110_{2}$ oder gar XXII). \end{itemize} Wir verwenden das \emph{Stellenwertsystem} bezüglich einer \emph{Basis} $b$. \begin{itemize} \item Darstellung als geordnete Reihung der Länge $n$ von Ziffern \item Mögliche Werte für Ziffern: $0, \ldots ,b-1$ \item Zusätzlich: der $i$--ten Stelle vor dem Komma wird der Wert $b^i$ zugeordnet ($i = 0, \ldots ,n-1$) \item Multipliziere Ziffern mit jeweiligem Stellenwert und addiere auf \end{itemize} Dies ergibt für eine $n$-stellige Zahl den Zahlenwert \[ x = (x_{n-1} x_{n-2} \ldots x_1 x_0)_b = x_{n-1} b^{n-1} + x_{n-2} b^{n-2} + \ldots + x_1 b^1 + x_0 b^0 \] Der Stellenwert der $i$--ten Stelle nach dem Komma ist $b^{-i}$ (mit $i = 1, \ldots, m$ bei $m$ Stellen nach dem Komma) also \[ y = (0, y_1 y_2 \ldots y_m)_b = y_1 b^{-1} + y_2 b^{-2} + \ldots + y_m b^{-m} \] \textbf{Beispiel:} \begin{align*} 111,01_2 & = 1 \x 2^2 + 1 \x 2^1 + 1 \x 2^0 + 0 \x 2^{-1} + 1 \x 2^{-2} = 7,25 \\ 201,22_3 & = 2 \x 3^2 + 0 \x 3^1 + 1 \x 3^0 + 2 \x 3^{-1} + 2 \x 3^{-2} = 19,\bar{8} \end{align*} %% Hinweis auf Unterschied: Information <-> Codierung der Information in einer Nachricht \pagebreak \subsection*{Umrechen zwischen verschiedenen Basen} \parbox{3cm}{\emph{Gegeben:}} Darstellung einer Zahl zur Basis $b_1$ \par \parbox{3cm}{\emph{Gesucht:}} Darstellung dieser Zahl zur Basis $b_2 \neq b_1$ \subsubsection*{Rechnen im Quellsystem} Betrachte Vor-- und Nachkommastellen getrennt; für die Vorkommastellen: \begin{enumerate} \item Teile Zahl durch Basis des Zielsystems \item Notiere ganzahligen Anteil des Ergebnisses und den Rest \item Wiederhole die bisherigen Schritte mit dem ganzzahligen Anteil des Ergebnisses solange bis dieser $0$ ist \item Die "`Reste"' bilden von unten nach oben gelesen die Ziffern der Darstellung (des Vorkomma--Anteils) im Zielsystem \end{enumerate} Für die Nachkommastellen: \begin{enumerate} \item Multipliziere mit Basis des Zielsystems \item Notiere Vorkomma--Anteil des Multiplikationsergebnisses \item Wiederhole die bisherigen Schritte mit dem Nachkomma--Anteil des Multiplikationsergebnisses solange bis dieser $0$ ist \item Die in $2.$ notierten Ergebnisse bilden von oben nach unten gelesen die Ziffern der Darstellung (des Nachkomma--Anteils) im Zielsystem \end{enumerate} %% Hinweis: Das funktionier durchaus auch, wenn es im Zielsystem mehr Ziffern als im Quellsystem gibt - die Darstellung %% der Ziffern und der Basis des Zielsystems im Quellsystem müssen dann aber bekannt sein (siehe folgendes Beispiel). \textbf{Beispiel:} Stelle $2012_3$ im Fünfersystem dar. Für die Ziffen und die Basis des Fünfersystems gilt: \[ 0_5 \triangleq 0_3 \quad 1_5 \triangleq 1_3 \quad 2_5 \triangleq 2_3 \quad 3_5 \triangleq 10_3 \quad 4_5 \triangleq 11_3 \quad \text{Basis } 5 \triangleq 12_3 \] \begin{align*} \left. \begin{array}{rlrlrl} 2012_3 & : 12_3 = & 102_3 & \text{ Rest} & 11_3 & \leadsto 4_5 \\ 102_3 & : 12_3 = & 2_3 & \text{ Rest} & 1_3 & \leadsto 1_5 \\ 2_3 & : 12_3 = & 0_3 & \text{ Rest} & 2_3 & \leadsto 2_5 \end{array} \right\} \Rightarrow 2012_3 \triangleq 214_5 \end{align*} \subsubsection*{Rechnen im Zielsystem} Verwende das \emph{\textsc{Horner}schema}.\par Betrachte dazu Vor-- und Nachkommastellen erneut getrennt; für die Ziffern vor dem Komma von links nach rechts: \[ \text{neues Ergebnis = altes Ergebnis $\x$ Basis + Ziffer} \] Für die Ziffern nach dem Komma von rechts nach links: \[ \text{neues Ergebnis = altes Ergebnis $:$ Basis + Ziffer} \] Wobei im ersten Schritt für das alte Ergebnis jeweils $0$ zu wählen ist. Beachte außerdem, dass bei den Nachkommastellen die $0$ vor dem Komma trotzdem als letzte Ziffer zu berücksichtigen ist. \pagebreak %% Hinweis: Das funktionier wiederuch durchaus auch dann, wenn es im Quellsystem mehr Ziffern als im Zielsystem gibt - die Darstellung %% der Ziffern und der Basis des Quellsystems im Zielsystem müssen dann aber bekannt sein (siehe folgendes Beispiel). \textbf{Beispiel:} Stelle $312_{4}$ im Zweiersystem dar. Für die Ziffern und die Basis des Vierersystems gilt: \[ 0_4 \triangleq 0_2 \quad 1_4 \triangleq 1_2 \quad 2_4 \triangleq 10_2 \quad 3_4 \triangleq 11_2 \quad \text{Basis } 4 \triangleq 100_2 \] \[ \begin{array}{r||l|l|l} \text{\small{Quellziffer}} & 3_4 & 1_4 & 2_4 \\ \hline \text{\small{Altes Erg. $\x$ Basis}} & - & 11_2 \x 100_2 = 1100_2 & 1101_2 \x 100_2 = 110100_2 \\ \hline \text{\small{Neues Erg.}} & 11_2 & 1100_2 + 1_2 = 1101_2 & 110100_2 + 10_2 = \underline{110110_2} \end{array} \] %% Zum Horner-Schema: für eine Zahl mit drei Ziffern mal ausführlich hinschreiben (also %% z.B. 1402_5 = ((1*5 + 4)*5 + 0)*5 + 2 = 1*5^3 + 4*5^2 + 0*5^1 + 2*5^0 - aber das ist ja genau...) %% Trick: z.B. zwischen 2er und 8er System: eine Stelle im 8er System entspricht 3 Stellen im 2er System (2^3 = 8) -> fasse in der %% 2er Darstellung je 3 Bits zusammen und berechne Zahlenwert -> ergbit die Ziffer im 8er System. %% (Funktioniert auch mit 4er und 16er System, 3er und 9er; Frage ans Publikum: allgemein?) %% Für die Praxis: schreibe Stellenwertigkeiten hin (1,2,4,8... bzw 1,7,49,343) und schaue: %% - wie oft geht die 8 in die 13 -> 1 mal %% - wie oft geht die 4 in die 5 (=13-8*1) -> 1 mal %% - wie oft geht die 2 in die 1 (=5-4*1) -> 0 mal %% - wie oft geht die 1 in die 1 (=1-0*2) -> 1 mal %% => damit 13_10 = 1101_2 \pagebreak \section*{Binärsystem, Binäres Rechnen} Addition, Subtraktion, Multiplikation und Division von positiven Binärzahlen ohne Komplikationen durchführbar.\par Negative Zahlen bereiten Probleme. Zunächst: Darstellung von negativen Zahlen \begin{enumerate} \item \emph{Einerkomplement:} Invertiere jedes Bit \[ z = 0100110 \quad \leadsto \quad -z = 1011001 \] \item \emph{Zweierkomplement (ZK):} Addiere $1$ zum Einerkomplement \[ z = 0100110 \quad \leadsto \quad -z = 1011010 \] Zweimaliges Bilden des ZKs liefert ursprüngliche Zahl \end{enumerate} % Frage: wieviele Darstellungen der 0 gibt es im ZK und EK? Damit gelingt die Addition von negativen Zahlen: \begin{itemize} \item Wähle Darstellung fester Breite so, dass das vorderste Bit nicht von der eigentlichen Zahlendarstellung belegt werden kann (\emph{Vorzeichenbit}); nicht benötigte Bits werden auf $0$ gesetzt. \item Wandle negative Zahlen ins Zweierkomplement um; das Vorzeichenbit wird dabei immer $1$ -- daher der Name: bei positiven Zahlen $0$, bei negativen Zahlen $1$ \item Addiere dann ganz normal und ignoriere dabei den \emph{Überlauf} (d.h. alles das, was über die fest vereinbarte Breite hinausgeht) \item Am Vorzeichenbit des Ergebnisses sieht man dann, ob dieses positiv oder negativ ist. Ist es negativ, so liegt es auch automatisch als Zweierkomplement vor \end{itemize} \textbf{Beispiele:} (wir verwenden eine feste Darstellung der Breite 6 - dabei wird das sechste Bit nicht zur Darstellung benötigt) \begin{itemize} \item Berechne $9+12$. Es ist $9_{10} \triangleq 001001_2$ und $12_{10} \triangleq 001100_2$ \[ \begin{array}{cccccccc} & 0 & 0 & 1 & 0 & 0 & 1 \\ + & 0 & 0 & 1 & 1 & 0 & 0 \\ & & 1 & & & & \\ \hline & 0 & 1 & 0 & 1 & 0 & 1 \end{array} \] Das sechste Bit (das Vorzeichenbit) ist 0, das Ergebnis damit positiv und $010101_2 \triangleq 21_{10}$. \item Berechne $(-7) + (-13)$. Es ist $7_{10} \triangleq 000111_2$ und $13_{10} \triangleq 001101_2$. Die Zweierkomplemente sind $-7_{10} \triangleq 111001_{\bar{2}}$ sowie $-13_{10} \triangleq 110011_{\bar{2}}$ \[ \begin{array}{cccccccc} & 1 & 1 & 1 & 0 & 0 & 1 \\ + & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & & & 1 & 1 & \\ \hline (1) & 1 & 0 & 1 & 1 & 0 & 0 \end{array} \] Das Vorzeichenbit ist $1$, das Ergebnis also negativ und $101100_{\bar{2}} \triangleq -010100_2 \triangleq -20_{10}$. \item Berechne $8 + (-17)$. Es ist $8 \triangleq 001000_2$ und $ -17 \triangleq 101111_{\bar{2}}$ \[ \begin{array}{cccccccc} & 0 & 0 & 1 & 0 & 0 & 0 \\ + & 1 & 0 & 1 & 1 & 1 & 1 \\ & & 1 & & & & \\ \hline & 1 & 1 & 0 & 1 & 1 & 1 \end{array} \] Das Vorzeichenbit ist $1$, das Ergebnis also negativ und $110111_{\bar{2}} \triangleq -001001_2 \triangleq -9_{10}$. \item Berechne $25 + (-18)$. Es ist $25 \triangleq 011001_2$ und $-18 \triangleq 101110_{\bar{2}}$ \[ \begin{array}{cccccccc} & 0 & 1 & 1 & 0 & 0 & 1 \\ + & 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & & & & \\ \hline (1) & 0 & 0 & 0 & 1 & 1 & 1 \end{array} \] Das Vorzeichenbit ist $0$, das Ergebnis also positiv und $0000111_2 \triangleq 7_{10}$. \end{itemize} %% Fragen zum Zweierkomplement und Rechnen mit fester Breite: %% - beim Invertieren wird das Vorzeichenbit - bisher 0 - nun auf 1 gesetzt; kann es passieren, dass durch das %% anschließende Addieren von 1 ein Übertrag bis nach vorne wandert und das Vorzeichenbit wieder 0 wird? %% (Antwort: nein, denn dazu müssten alle Bits 1 sein - das entspräche dann aber der Null und die wird nicht %% im Zweierkomplement dargestellt, bzw es ist egal, weil dann wieder Null bei rauskommt) %% - was passiert, wenn die zur Zahlendarstellung veranschlagte Bitzahl für das Ergebnis der Addition nicht ausreicht, %% d.h. mehr als die n-1 Bits notwendig wären? %% (Antwort: das Vorzeichenbit kann überschrieben werden, so dass evtl die Summer zweier großer Zahlen plötzlich negativ %% wird oder umgekehrt - Beispiel dazu: [PENDING: Bsp ausdenken]) %% Nachfragen: interessiert sich jemand für den Mathematischen Grundlagen (also -z = 2^n -z = sum(1-z_i) ...)? -> ggf an die Tafel pinslen %% (für die Zukunft: Interesse an mathematischen Grundlagen?) \pagebreak \section*{Codierung} Zwei (von vielen) Möglichkeiten zur Codierung $c : \Sigma \rightarrow \{0, 1\}^*$: \begin{enumerate} \item Nummeriere Zeichen aus $\Sigma$ durch und stelle $z \in \Sigma$ durch binäre Darstellung seiner Nummer dar (feste Länge nötig). \item \textsc{Huffman}--Verfahren \end{enumerate} \subsection*{Huffman--Verfahren} \begin{enumerate} \item Ordne Zeichen nach Wahrscheinlichkeit des Auftretens \item Fasse die beiden Zeichen mit der kleinsten Wahrscheinlichkeit zu neuem Zeichen zusammen und ordne diesem die Summe der Wahrscheinlichkeiten zu \item Wiederhole dies bis nur noch ein Zeichen übrig ist \item Konstruiere Codebaum \item Codierung eines Zeichens wird durch den Pfad von der Wurzel bis zu diesem Zeichen festgelegt \end{enumerate} \subsection*{Shannonsche Informationstheorie} In aller Kürze: $\Sigma = \{z_1, \ldots, z_m\}$; Informationsgehalt eines Zeichens: \[ H = - \sum_{i=1}^m p_i \x \ld p_i \quad p_i = p(z_i) \;\text{ (rel. Häufigkeit von $z_i$)} \] \end{document}