Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
5213 lines (3890 sloc) 90.5 KB
#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass article
\use_default_options true
\maintain_unincluded_children false
\language german-ch
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize a4paper
\use_geometry true
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date true
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\leftmargin 2cm
\topmargin 2cm
\rightmargin 2cm
\bottommargin 2cm
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style swiss
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\author 193504446 "raf"
\end_header
\begin_body
\begin_layout Title
\series bold
Zusammenfassung INCO
\end_layout
\begin_layout Part
Informationstheorie
\end_layout
\begin_layout Section
Formeln
\end_layout
\begin_layout Description
Informationsgehalt:
\begin_inset Formula $I(X_{n})=\log_{2}\frac{1}{P(X_{n})}$
\end_inset
\end_layout
\begin_layout Description
Entropie
\begin_inset Formula $H(X)=\overset{N-1}{\underset{n=0}{\sum}}P(x_{n})\cdot\log_{2}\frac{1}{P(x_{n})}$
\end_inset
\end_layout
\begin_layout Description
Entropie
\begin_inset space ~
\end_inset
binäre
\begin_inset space ~
\end_inset
Quelle
\end_layout
\begin_layout Description
\begin_inset Graphics
filename Images/entropie_binaere_quelle.png
scale 60
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $H_{\text{min}}=0$
\end_inset
,
\begin_inset Formula $H_{\text{max}}=\log_{2}N$
\end_inset
(N = Anzahl Symbole)
\end_layout
\begin_layout Section
Glossar
\end_layout
\begin_layout Description
\series bold
Discrete
\begin_inset space ~
\end_inset
Memoryless
\begin_inset space ~
\end_inset
Source
\begin_inset space ~
\end_inset
(DMS)
\series default
Quelle, welche einzelne, voneinander unabhängige, Ereignisse liefert.
\end_layout
\begin_layout Description
Binary
\begin_inset space ~
\end_inset
Memoryless
\begin_inset space ~
\end_inset
Source
\begin_inset space ~
\end_inset
(BMS) DMS, die nur zwei verschiedene ereignisse erzeugt.
\end_layout
\begin_layout Part
Digitaltechnik
\end_layout
\begin_layout Section
Boolische Operationen
\end_layout
\begin_layout Subsection
Operatoren
\end_layout
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="3">
<features tabularvalignment="middle">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Operator
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Zeichen
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
NOT
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\series bold
!A
\series default
,¬A,A'
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Graphics
filename Images/NOT_Gate.png
lyxscale 10
scale 5
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
AND
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\series bold
&
\series default
,∩,∧
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Graphics
filename Images/AND_Gate.png
lyxscale 40
scale 20
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
OR
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\series bold
#
\series default
,∪,∨
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Graphics
filename Images/OR_Gate.png
lyxscale 40
scale 20
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
XOR
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\series bold
$
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Graphics
filename Images/XOR_Gate.png
lyxscale 40
scale 20
\end_inset
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\change_inserted 193504446 1578424036
\begin_inset Newline newline
\end_inset
\begin_inset Graphics
filename Images/NAND.png
lyxscale 70
scale 45
\end_inset
\end_layout
\begin_layout Subsection
Regeln
\end_layout
\begin_layout Standard
\noindent
A & A = A
\end_layout
\begin_layout Standard
\noindent
A # A = A
\end_layout
\begin_layout Standard
\noindent
!(!(A)) = A
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
\noindent
A & (A # B) = A
\end_layout
\begin_layout Standard
\noindent
A # (A & B) = A
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
\noindent
A & (!A # B) = A & B
\end_layout
\begin_layout Standard
\noindent
A # (!A & B) = A # B
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
\noindent
A # (B & C) = (A # B) & (A # C)
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
\noindent
Umwandlung negierter Ausdrücke:
\end_layout
\begin_layout Standard
\noindent
!(A & B) = !A # !B
\end_layout
\begin_layout Standard
\noindent
!(A # B) = !A & !B
\end_layout
\begin_layout Section
Glossar
\end_layout
\begin_layout Description
Halbadierer Ein Addierer der nur ein Bit addiert.
Er kann keinen Übertrag addieren, es kann jedoch ein Übertrag enstehen.
Der Halbadierer wird für das Bit Nummer 0 im N-Bit Addierer verwendet.
\end_layout
\begin_layout Description
Volladierer Ein Addierer der den Übertrag aus der vorher gehenden Stufe
addieren kann.
Er wird für alle Bits 0 < k ≤ N im N-Bit Addierer verwendet.
\end_layout
\begin_layout Description
D-Flip-Flop Ein Speicher, welcher ein Bit festhalten kann.
Das jeweils am Dateneingang anliegende Bit wird bei jeder ansteigenden
Flanke des Clock Signals an den Ausgang weitergegeben.
\end_layout
\begin_layout Description
Schieberegister Eine Sequenzielle Schaltung aus Flip-Flops.
\end_layout
\begin_layout Description
Disjunktive
\begin_inset space ~
\end_inset
Normalform Mit OR zusammengefasste zutreffende Zeilen aus der Wahrheitstabelle
z.B.
(A&B) # (B&C) # (X&Y)
\end_layout
\begin_layout Part
Zahlensysteme
\end_layout
\begin_layout Section
Umwandlungen
\end_layout
\begin_layout Subsection
\noindent
\series bold
Zehner- zu Zweiersystem
\end_layout
\begin_layout Standard
\noindent
6 : 2 = 3 Rest
\series bold
0
\series default
| 3 : 2 = 1 Rest
\series bold
1
\series default
| 1 : 2 = 0 Rest
\series bold
1
\end_layout
\begin_layout Standard
\noindent
Ergebnis:
\series bold
110
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Subsection
\noindent
\series bold
Zehner- zu Sechszehnersystem
\end_layout
\begin_layout Standard
\noindent
100 : 16 = 6 Rest
\series bold
4
\series default
| 6 : 16 = 0 Rest
\series bold
6
\end_layout
\begin_layout Standard
\noindent
Ergebnis:
\series bold
64
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Subsection
\noindent
\series bold
Dezimal- ins Zweiersystem
\end_layout
\begin_layout Standard
\noindent
\begin_inset Formula $0.6875\cdot2=0.3750+\boldsymbol{1}$
\end_inset
\end_layout
\begin_layout Standard
\noindent
\begin_inset Formula $0.3750\cdot2=0.7500+\boldsymbol{0}$
\end_inset
\end_layout
\begin_layout Standard
\noindent
\begin_inset Formula $0.7500\cdot2=0.5000+\boldsymbol{1}$
\end_inset
\end_layout
\begin_layout Standard
\noindent
\begin_inset Formula $0.5000\cdot2=0.0000+\boldsymbol{1}$
\end_inset
\end_layout
\begin_layout Standard
\noindent
Ergebnis:
\series bold
0.1011
\end_layout
\begin_layout Section
Darstellung von Zahlen
\end_layout
\begin_layout Subsection
Negative Zahlen
\end_layout
\begin_layout Standard
Um negative Zahlen darzustellen werden Komplemente gebildet.
Beim 10-er System wird zuerst das
\series bold
9-er Komplement
\series default
gebildet.
Durch das hinzufügen von
\series bold
eins
\series default
an der letzten Stelle wird das
\series bold
10-er Komplement
\series default
gebildet.
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="3" columns="3">
<features tabularvalignment="middle">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Ursprüngliche Zahl
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0 0 0 0 0 0
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9-er Komplement
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9 9 9 9 9 8
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
10-er Komplement
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9 9 9 9 9
\series bold
9
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
Im Binärsystem wird zuerst das 1-er Komplement gebildet und anschliessend
ein Bit an der letzten Stelle hinzugefügt um das 2-er Komplement zu erhalten.
Folgendes Beispiel zeigt die Zahl -
\begin_inset Formula $5.25_{d}$
\end_inset
.
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $+5.25_{d}=...00101.01_{b}$
\end_inset
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="3" columns="3">
<features tabularvalignment="middle">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Ursprüngliche Zahl
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0 0 0 1 0 1.
0 1
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1-er Komplement
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1 1 1 0 1 0.
1 0
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2-er Komplement
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1 1 1 0 1 0.1
\series bold
1
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Subsection
Darstellbare Zahlen
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
label{zahlentabelle}
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="7" columns="3">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Register
\end_layout
\end_inset
</cell>
<cell multicolumn="1" alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Maximal darstellbare Zahl
\end_layout
\end_inset
</cell>
<cell multicolumn="2" alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
4 Bit
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $0...15$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\text{−}8...+7$
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
8 Bit
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $0...255$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\text{−}128...+127$
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
16 Bit
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $0...650535$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\text{−}320768...+320767$
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
32 Bit
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $0...4.29\text{·}109^{9}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\text{−}2.15\text{·}109...+2.15\text{·}10^{9}$
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
64 Bit
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $0...1.84\text{·}10^{19}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\text{−}9.22\text{·}1018...+9.22\text{·}10^{18}$
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
128 Bit
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $0...3.40d\text{·}10^{38}$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\text{−}1.70\text{·}1038...+1.70\text{·}10^{38}$
\end_inset
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Section
Rechnen
\end_layout
\begin_layout Subsection
Addition
\end_layout
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="4" columns="8">
<features tabularvalignment="middle">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Erster Summand
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1.
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Zweiter Summand
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
+
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1.
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Übertrag
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Resultat
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0.
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Subsection
Subtraktion
\end_layout
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="4" columns="8">
<features tabularvalignment="middle">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Minuend
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
7
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3.
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $_{o}$
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Subtrahend
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
-
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
4
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
4.
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $_{o}$
\end_inset
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Übertrag
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Resultat
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
4
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
6.
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
7
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $_{o}$
\end_inset
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Subsection
Multiplikation
\end_layout
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="6" columns="10">
<features tabularvalignment="middle">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<column alignment="center" valignment="top" width="0pt">
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\times$
\end_inset
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
+
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
+
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Übertrag
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Resultat
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Section
BCD
\end_layout
\begin_layout Subsection
BCD Tabelle
\end_layout
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="4">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0000
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0101
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0001
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0110
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
6
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0010
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0111
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
7
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0011
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1000
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
8
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0100
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
4
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1001
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Subsection
Darstellung
\end_layout
\begin_layout Standard
\begin_inset Graphics
filename Images/BCD.png
lyxscale 60
scale 40
\end_inset
\end_layout
\begin_layout Section
Codes
\end_layout
\begin_layout Subsection
UTF-8 Codierung
\end_layout
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="3">
<features tabularvalignment="middle">
<column alignment="left" valignment="top" width="0pt">
<column alignment="left" valignment="top" width="0pt">
<column alignment="left" valignment="top" width="0pt">
<row>
<cell alignment="left" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
Unicode-Bereich (hex)
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
UTF-8 Codierung
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
Code-Bits
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
0000’0000 - 0000’007F
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
0xxxxxxx
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
7
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
0000’0080 - 0000’07FF
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
110xxxxx 10xxxxxx
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
11 (5 + 1*6)
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
0000’0800 - 0000’FFFF
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
1110xxxx 10xxxxxx 10xxxxxx
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
11 (5 + 1*6)
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="left" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
0001’0000 - 0010’FFFF
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
\end_layout
\end_inset
</cell>
<cell alignment="left" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\size tiny
21 (3 + 3*6)
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Section
Definitionen
\end_layout
\begin_layout Description
Gray
\begin_inset space ~
\end_inset
Code Benachbarte Codeworte unterscheiden sich nur in einem Bit.
\end_layout
\begin_layout Description
ASCII
\begin_inset space ~
\end_inset
Code Älterer 7 Bit (heute 8 Bit) langer Zeichencode.
Es gibt mehrere Zeichensätze.
\end_layout
\begin_layout Description
Unicode Moderner Zeichensatz, welcher alle bekannten Zeichen zusammenfasst.
\end_layout
\begin_layout Description
UTF-8 Ein Code mit variabler Breite, es werden 1 bis 4 Bytes verwendet,
um die Code Points zu codieren.
Für ASCII-Zeichen (die untersten 128 Code Points, von 0 bis 127) wird ein
Byte verwendet.
Für alle anderen Code Points sind mehrere Bytes nötig.
\end_layout
\begin_layout Description
UTF-16 für die Codierung entweder 2 oder 4 Bytes verwendet.
Für die Zeichen der BMP mit den Code Points von 0000h bis FFFF h genügen
2 Bytes.
\end_layout
\begin_layout Description
Endianness Little-endian heisst, dass das niederstwertige Byte zuerst geschriebe
n (oder übertragen) wird, das “kleine” Ende wird also vorangeschickt.
Die andere Variante heisst big-endian, hier wird das höchstwertige Byte
zuerst gespeichert (also an die niedrigste Adresse).
\end_layout
\begin_layout Description
Überlauf Überläufe passieren, wenn bei einer Verrechnung von zwei Zahlen
die obere oder untere maximal darstellbare Zahl (siehe
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
ref{zahlentabelle}
\end_layout
\end_inset
) überschritten wird.
Der Prozessor setzt in diesem Fall ein Borrow (Unterläuf) oder Carry (Überläuf)
Flag.
\end_layout
\begin_layout Part
Quellencodierung
\end_layout
\begin_layout Section
Definitionen
\end_layout
\begin_layout Description
Codewortlänge Die Codewortlänge
\begin_inset Formula $\boldsymbol{\ell}_{\boldsymbol{n}}$
\end_inset
bezieht sich auf das Codewort
\begin_inset Formula $\boldsymbol{c}_{\boldsymbol{n}}$
\end_inset
eines bestimmten Symbols
\begin_inset Formula $\boldsymbol{x}_{\boldsymbol{n}}$
\end_inset
und gibt an,
\series bold
aus wievielen Bits das Codewort besteht.
\end_layout
\begin_layout Description
Redundanz Solange die Redundanz R eines Codes grösser als null ist, kann
noch verlustfrei komprimiert werden.
Falls R ≤ 0, so kann nur noch verlustbehaftet komprimiert werden.
\end_layout
\begin_layout Description
Lempel
\begin_inset space ~
\end_inset
Ziv
\begin_inset space ~
\end_inset
Codes Jede Sequenz von Quellensymbolen wird durch einen Index in ein Wörterbuch
ersetzt.
\end_layout
\begin_layout Description
Präfixfrei Ein Code ist Präfixfrei, wenn die Codeworte in einem Bitstrom
immer eindeutig identifiziert werden können (z.B.
Hoffman-Code)
\end_layout
\begin_layout Section
Formeln
\end_layout
\begin_layout Description
Mittlere
\begin_inset space ~
\end_inset
Codewortlänge
\begin_inset Formula $L=\underset{n=0}{\overset{n-1}{\sum}}p(x_{n})\cdot\ell_{n}$
\end_inset
in
\begin_inset Formula $\frac{Bit}{Symbol}$
\end_inset
\end_layout
\begin_layout Description
Redundanz
\begin_inset Formula $R=L-H$
\end_inset
in
\begin_inset Formula $\frac{Bit}{Symbol}$
\end_inset
\end_layout
\begin_layout Description
Theorem
\begin_inset space ~
\end_inset
zur
\begin_inset space ~
\end_inset
Quellencodierung Solange die Redundanz R eines Codes grösser als null ist,
kann noch verlustfrei komprimiert werden.
Falls R ≤ 0, so kann nur noch verlustbehaftet komprimiert werden.
\end_layout
\begin_layout Section
Codierungen
\end_layout
\begin_layout Subsection
Lauflängencodierung
\end_layout
\begin_layout Standard
Ketten von identischen Zeichen werden zusammengefasst.
Für die Kompressionsrate gilt
\begin_inset Formula $\frac{Komprimierte\,Bits}{Originale\,Bits}$
\end_inset
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
...TERRRRRRRRRMAUIIIIIIIIIIIIIIIIIWQCSSSSSSSSSSL...
\end_layout
\begin_layout Standard
...TE
\series bold
(9xR)
\series default
MAU
\series bold
(17xI)
\series default
WQC
\series bold
(10xS)
\series default
L...
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
Um noch effizienter zu sein verwendet man einen Marker, welcher bereits
im Zeichensatz vorhanden ist, in folgendem Beispiel ist das A.
\end_layout
\begin_layout Standard
...TE
\series bold
A09R
\series default
M
\series bold
A01A
\series default
U
\series bold
A17I
\series default
WQC
\series bold
A10S
\series default
L...
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Graphics
filename Images/Bild_Lauflaengencodierung.png
scale 35
\end_inset
\end_layout
\begin_layout Standard
(
\series bold
24
\series default
,
\series bold
11
\series default
, 65, 1, 23, 2, 8, 17, 7, 18, 6, 17, 21, 2, 22, 1, 54 )
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
Für die Lauflängencodierung eines Bildes wird folgendermassen vorgegangen:
\end_layout
\begin_layout Enumerate
Definiere vorgängig die Bitbreite des Pixelzählers.
\end_layout
\begin_layout Enumerate
Definiere vorgängig die Pixelfarbe mit der begonnen wird.
\end_layout
\begin_layout Enumerate
Serialisierung des Bildes.
• Falls der erste Pixel nicht die vordefinierte Farbe hat, setze die erste
Pixelzahl auf null.
\end_layout
\begin_layout Enumerate
Zähle jeweils alle Pixel gleicher Farbe bis zum nächsten Farbwechsel.
\end_layout
\begin_layout Enumerate
Sollte eine Pixelzahl grösser werden als das Maximum des Zählers, so teile
die Zahl auf, wie oben gezeigt.
\end_layout
\begin_layout Standard
Soll das Bild zeilenweise codiert werden, muss das Zeilenende jeweils mit
einem reservierten Wert signalisiert werden (normalerweise der max.
Wert).
\end_layout
\begin_layout Subsection
Huffman Codes
\end_layout
\begin_layout Standard
Häufige Symbole erhalten kurze Codes, seltene Symbole erhalten lange Codes.
\end_layout
\begin_layout Standard
\begin_inset Graphics
filename Images/Huffman-Baum.png
scale 40
\end_inset
\end_layout
\begin_layout Standard
Bei einer kleinen Anzahl Codes kann es Sinn machen, Doppelsymbole zu bilden
um die Redundanz zu verringern.
Bei doppelsymbolen rechnet man mit
\begin_inset Formula $\frac{Bit}{\boldsymbol{2\,Symbole}}$
\end_inset
\end_layout
\begin_layout Enumerate
Ordne alle Symbole nach aufsteigenen Auftretenswahrscheinlichkeiten auf
einer Zeile.
Dies sind die Blätter des Huffman-Baums.
Gibt es Symbole mit gleichen Wahrscheinlichkeiten, so spielt die Reihenfolge
unter ihnen keine Rolle.
\end_layout
\begin_layout Enumerate
Notiere unter jedes Blatt seine Wahrscheinlichkeit.
\end_layout
\begin_layout Enumerate
Schliesse die beiden Blätter mit der kleinsten Wahrscheinlichkeit an einer
gemeinsamen Astga- bel an.
Ordne dem Ast die Summe der Wahrscheinlichkeiten der beiden Blätter zu.
Gibt es mehrere mögliche Kombinationen von Blättern mit den kleinsten Wahrschei
nlichkeiten, so spielt es keine Rolle, welche man davon auswählt.
\end_layout
\begin_layout Enumerate
Wiederhole Punkt 3 mit Blättern und Ästen so lange, bis nur noch der Stamm
des Baums übrig bleibt.
\end_layout
\begin_layout Enumerate
Nun wird festgelegt, ob bei jeder Astgabel der linke Zweig eine 0 oder eine
1 erhält.
Der rechte Zweig erhält dann das Komplement.
\end_layout
\begin_layout Enumerate
Nun werden auf dem Pfad vom Stamm zu jedem Blatt die Nullen und Einsen ausgelese
n und von links nach rechts nebeneinander geschrieben.
Dies sind die Huffman-Codeworte.
\end_layout
\begin_layout Subsubsection
LZ77
\end_layout
\begin_layout Standard
Bei LZ77 werden Tokens in der Form (Offset, Länge, Zeichen) verwendet.
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Graphics
filename Images/LZ77.png
scale 50
\end_inset
\end_layout
\begin_layout Standard
(0, 0, A) (0, 0, M) (2, 2, M) (4, 2, A) (6, 4, T)
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
Nehmen wir an, es handle sich um Zeichen, die
\series bold
je 1 Byte
\series default
belegen .
Die ursprünglichen
\series bold
13 Zeichen
\series default
belegen demnach total
\series bold
13 · 8 = 104 Bit
\series default
.
Im Token kommt ebenfalls ein derartiges Zeichen vor.
Zusätzlich muss der Offset gross genug sein, damit der
\series bold
jede Position (1 bis 10) im Such-Buffer
\series default
bezeichnen kann.
Hierfür sind
\series bold
4 Bit
\series default
nötig.
Die Längenangabe muss den gesamten Vorschau-Buffer abdecken können, ohne
das letzte Zeichen, das bestenfalls die Funktion eines zusätzlichen Zeichens
haben kann.
Man muss also bis
\series bold
4 Zählen
\series default
können, wozu
\series bold
3 Bit
\series default
nötig sind.
Ein Token besteht demnach aus total
\series bold
4 + 3 + 8 = 15 Bit.
\series default
Die fünf Token umfassen gesamthaft 5 · 15 = 75 Bit.
\end_layout
\begin_layout Standard
Der Decoder empfängt die oben genannten Token und decodiert diese mithilfe
des Suchbuffers.
\end_layout
\begin_layout Subsubsection
LZ78
\end_layout
\begin_layout Standard
Der LZ78 baut ein eigenes Wörterbuch auf.
Die Token bestehen aus (Index, Zeichen).
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="6" columns="6">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Index
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
String
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Token
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Index
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
String
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
Token
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
0
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
-
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
5
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
AA
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
(1, A)
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
A
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
(0, A)
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
6
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
AMM
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
(3, M)
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
2
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
M
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
(0, M)
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
7
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
MT
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
(2, T)
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
3
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
AM
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
(1, M)
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
8
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
AAT
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
(5, T)
\end_layout
\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
4
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
MM
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
(2, M)
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
9
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text
\begin_layout Plain Layout
...
\end_layout
\end_inset
</cell>
</row>
</lyxtabular>
\end_inset
\end_layout
\begin_layout Subsection
LZW
\end_layout
\begin_layout Standard
Das LZW-Verfahren16 ist eine Weiterentwicklung von LZ78 mit dem Ziel, den
Token zu verkleinern.
Der LZW-Token besteht in der Folge nur noch aus einem Wörterbuch-Index.
Das Wörterbuch von LZW ist vorinitialisiert mit allen Zeichencodes von
0 bis 255 (einschliesslich den ASCII-Zeichen im Bereich 0 bis 127).
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Graphics
filename Images/LZW.png
scale 60
\end_inset
\end_layout
\begin_layout Part
Kanalcodierung
\end_layout
\begin_layout Description
Verbundentropie H(Y,X) ist die bedingte Entropie von Y gegeben X.
Die Mittlere Information resp.
Überraschungseffekt für Y wenn wir X kennen
\end_layout
\begin_layout Description
Bit
\begin_inset space ~
\end_inset
Error
\begin_inset space ~
\end_inset
Rato
\begin_inset space ~
\end_inset
(BER) Die BER ist epsilon:
\begin_inset Formula $\epsilon$
\end_inset
\end_layout
\begin_layout Section
BSC
\end_layout
\begin_layout Standard
\begin_inset Graphics
filename Images/bsc_abbildung.png
scale 50
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Graphics
filename Images/bsc_BER.png
scale 60
\end_inset
\begin_inset Newline newline
\end_inset
Die Fehlerwarscheinlichkeit, dass in einer Seqzuenz von N Datenbits
\series bold
genau F Bitfehler
\series default
auftreten ist:
\begin_inset Newline newline
\end_inset
\begin_inset Graphics
filename Images/Pfn.png
scale 60
\end_inset
\begin_inset Newline newline
\end_inset
Die
\series bold
Totale Wahrscheinlichkeit
\series default
am Ausgang des BSC berechnen sich mit:
\begin_inset Newline newline
\end_inset
\begin_inset Graphics
filename Images/totale_wahrscheinilchkeit_BSC.png
scale 60
\end_inset
\end_layout
\begin_layout Subsection
Entropien BSC
\end_layout
\begin_layout Standard
Die Entropien am
\series bold
Eingang
\series default
\series bold
H(X)
\series default
und
\series bold
Ausgang
\series default
\series bold
H(Y)
\series default
:
\begin_inset Newline newline
\end_inset
\begin_inset Graphics
filename Images/Entropie-ein-ausgang_bsc.png
scale 60
\end_inset
\begin_inset Newline newline
\end_inset
Die
\series bold
Verbund-Entropie
\series default
\series bold
H(X,Y)
\series default
, ist die Gesamt-Entropie des Kanals wenn alle möglichen Übertragungspfade
berücksichtigt werden.
\begin_inset Newline newline
\end_inset
\begin_inset Graphics
filename Images/verbund_entropie_bsc.png
scale 60
\end_inset
\begin_inset Newline newline
\end_inset
Die
\series bold
Bedingte Entropie
\series default
des Ausgangs Y, wenn der Eingang X bekannt ist:
\begin_inset Newline newline
\end_inset
\begin_inset Graphics
filename Images/Bedingte_entropie_augang_bsc.png
scale 60
\end_inset
\begin_inset Graphics
filename Images/verbundentropie_gesammt_bsc.png
scale 60
\end_inset
\begin_inset Newline newline
\end_inset
Die Entropie der Informationen die nicht am Ausgang ankommen, also aufgrund
von Übertragungsfehlern verloren gingen ist
\series bold
H(X|Y)
\series default
= H(X,Y)–H(Y)
\end_layout
\begin_layout Subsection
Gemeinsame Information
\end_layout
\begin_layout Standard
Die Gemeinsame Information ist
\series bold
I(X;Y)
\series default
= H(Y)–H(Y|X) oder
\series bold
I(X;Y)
\series default
= H(X)–H(X|Y)
\begin_inset Newline newline
\end_inset
\series bold
\begin_inset Graphics
filename Images/visualisierung_Information_bsc.png
\end_inset
\end_layout
\begin_layout Subsection
Kanalkapazität
\end_layout
\begin_layout Standard
Die Kanalkapazität definiert, welche gemeinsame Information
\series bold
I(X;Y)
\series default
im besten Fall durch den Kanal übertragen werden kann.
Bei gegebener BER
\begin_inset Formula $\epsilon$
\end_inset
hängt I(X;Y) nur von der Quellenwahrscheinlichkeit P(x) ab, wobei x für
\begin_inset Formula $x_{1}$
\end_inset
und
\begin_inset Formula $x_{2}$
\end_inset
stehen kann.
\end_layout
\begin_layout Standard
\series bold
CBSC = max I(X;Y) = 1 – H
\begin_inset Formula $_{\boldsymbol{b}}$
\end_inset
(
\series default
\begin_inset Formula $\boldsymbol{\epsilon}$
\end_inset
\series bold
) =
\begin_inset Formula $\boldsymbol{\{\epsilon\cdot\log_{2}\frac{1}{\epsilon}+(1-\epsilon)\cdot\log_{2}\frac{1}{1-\epsilon}\}}$
\end_inset
\begin_inset Newline newline
\end_inset
\series default
Die gemeinsame Information wird
\series bold
maximal
\series default
, wenn H(X) maximal, d.h.
=1 wird.
Dies wird erreicht wenn
\series bold
P(x) = 0.5
\series default
ist.
\series bold
\series default
Die Kapazität wird minimal, wenn
\begin_inset Formula $\epsilon=0.5$
\end_inset
\end_layout
\begin_layout Section
Binäre Kanalcodes
\end_layout
\begin_layout Standard
Ein Binärer Kanalcode
\series bold
C
\series default
ist eine Sammlung von
\begin_inset Formula $\psi$
\end_inset
Codeworten
\begin_inset Formula $c_{j}$
\end_inset
mit
\begin_inset Formula $j=0...\psi-1$
\end_inset
.
Jedes Codewort ist eine Bitgruppe.
\end_layout
\begin_layout Description
Hamming-Gewicht
\begin_inset Formula $w_{H}(C_{j})$
\end_inset
gibt an, wieviele Einsen das Codewort
\begin_inset Formula $c_{j}$
\end_inset
enthält.
\end_layout
\begin_layout Description
Hamming-Distanz
\begin_inset Formula $d_{H}(c_{j},c_{k})$
\end_inset
ist die Anzahl Stellen, an denen sich gleich lange Codeworte unterscheiden.
Die Minimale Hamming-Distanz
\begin_inset Formula $d_{\min}(C)$
\end_inset
gibt die kleinste Hamming-Distanz
\begin_inset Formula $d_{H}$
\end_inset
an.
\end_layout
\begin_layout Description
Hamming-Codes Hamming-Codes lineare Blockcodes unterschiedlicher Länge mit
einer minimalen Hamming-Distanz von dmin = 3.
\end_layout
\begin_layout Description
Binäre
\begin_inset space ~
\end_inset
Arithmetik
\begin_inset space ~
\end_inset
(Modulo
\begin_inset space ~
\end_inset
2) Addition und Multiplikation im Modulo 2 (
\begin_inset Formula $\varoplus,\varodot$
\end_inset
)
\end_layout
\begin_layout Description
Repetitions-Code
\begin_inset Formula $R^{x}$
\end_inset
Wiederholt jedes bit x mal.
\end_layout
\begin_layout Description
Erkennbarkeit
\begin_inset space ~
\end_inset
von
\begin_inset space ~
\end_inset
Fehlern
\begin_inset Formula $d_{\min}-1$
\end_inset
Fehler sind sicher erkennbar,
\begin_inset Formula $\lfloor\frac{d_{min}-1}{2}\rfloor$
\end_inset
sicher korrekt korrigierbar (abgerundet).
\end_layout
\begin_layout Description
\end_layout
\begin_layout Section
Theorem der Kanalkodierung
\end_layout
\begin_layout Description
Coderate
\begin_inset Formula $R=\frac{L(U)}{L(C)}$
\end_inset
wobei L(U) = mittlere Länge der Eingangsbitmuster
\begin_inset Formula $u_{j}$
\end_inset
und L(C) die mittlere Länge der Fehlerschutzworte
\begin_inset Formula $c_{j}$
\end_inset
ist.
\end_layout
\begin_layout Description
Restfehlerwahrscheinlichkeit Möchte man die Restfehlerwahrscheinlichkeit
eines Fehlerschutzcodes beliebig klein machen, so muss
\series bold
R < C
\series default
sein.
\begin_inset Newline newline
\end_inset
Die Restfehlerwahrscheinlichkeit
\series bold
nimmt ab
\series default
, wenn der Fehlerschutzcode
\series bold
viele Fehlerschutzbits
\series default
enthält.
\begin_inset Newline newline
\end_inset
Die Restfehlerwahrscheinlichkeit
\series bold
nimmt ab
\series default
, wenn der Fehlerschutzcode nicht nur einzelne Symbole
\series bold
absichert
\series default
, sondern
\series bold
ganze Gruppen
\series default
davon.
\end_layout
\begin_layout Section
Binäre Blockcodes
\end_layout
\begin_layout Standard
Jedes Codewort hat dieselbe Grösse und codiert gleich viele Nutzbits.
\end_layout
\begin_layout Description
(N,K)-Blockcode K Bits aus dem Eingangsstrom werden in Codeworte mit N Bits
verpackt.
Es gibt
\begin_inset Formula $2^{N}$
\end_inset
Codeworte, von denen
\begin_inset Formula $2^{K}$
\end_inset
benutzt weren.
Der Rest dient der Fehlererkennung.
\end_layout
\begin_layout Description
\series bold
Coderate
\begin_inset Formula $R=\frac{K}{N}$
\end_inset
\end_layout
\begin_layout Description
Paritätsbit Jedes Codewort enthällt eine gerade oder ungerade Anzahl Einsen.
\end_layout
\begin_layout Subsection
Linearität
\end_layout
\begin_layout Standard
Ein (N,K)-Blockcode heisst
\series bold
linear
\series default
, wenn jede bitweise Summe von zwei Codeworten wieder ein Codewort ist.
Z.B.
\begin_inset Formula $\boldsymbol{c_{j}\varoplus c_{j}=(000)},\,c_{j}\varoplus(000)=c_{j},\,(110)\varoplus(011)=(101),\,(110)\varoplus(101)=(011),\,(011)\varoplus(101)=(110)$
\end_inset
, jeder liniare Code enthält
\series bold
zwingend das Null-Codewort (000
\series default
).
\end_layout
\begin_layout Description
Minimale
\begin_inset space ~
\end_inset
Hamming-Distanz
\begin_inset Formula $d_{\min}(C)=\min d_{H}(c_{j},c_{k})=\min w_{H}(c_{j}\varoplus c_{k})$
\end_inset
also das minimale Hamming-Gewicht aller Codeworte.
\series bold
Nur für Liniare Codes!
\end_layout
\begin_layout Subsection
Systematik
\end_layout
\begin_layout Standard
Ein (N,K)-Blockcode heisst
\series bold
systematisch
\series default
wenn im Codewort das Bitmuster am
\series bold
Stück sichtbar
\series default
ist.
\end_layout
\begin_layout Subsection
Zyklizität
\end_layout
\begin_layout Standard
Ein (N,K)-Blockcode heisst
\series bold
zyklisch
\series default
, wenn jede zyklische Rotation eines Codeworts wieder ein Codewort ist.
\end_layout
\begin_layout Standard
\series bold
\begin_inset Formula $(000)\rightarrow(000)$
\end_inset
\series default
&
\begin_inset Formula $(110)\rightarrow(011)\rightarrow(101)\rightarrow(110)$
\end_inset
Das Codewort (000) ist in sich zyklisch, alle übrigen Codeworte bilden
eine zyklisch premutierende Kette.
Auch ein
\begin_inset Formula $R^{5}$
\end_inset
Code ist zyklisch.
\end_layout
\begin_layout Subsection
Perfektion
\end_layout
\begin_layout Standard
Ein (N,K)-Blockcode heisst
\series bold
perfekt
\series default
, wenn jedes Bitmuster eine minimale Haemmingdistanz zu genau einem Codewort
aufweist.
Daraus folgt, dass es bei einem perfekten Code mit
\begin_inset Formula $d_{min}\succeq3$
\end_inset
immer genau eine wahrscheinlichste Fehlerkorrektur gibt.
Z.B.
\begin_inset Formula $R^{5}$
\end_inset
\end_layout
\begin_layout Subsection
CRC
\end_layout
\begin_layout Standard
Jedes Codewort wird als Polynom aufgefasst, das durch ein Generatorpolyinom
teilbar ist.
Die Prüfbits werden so gewählt, dass möglichst viele typische Arten von
Übertragungsfehlern erkannt werden.
CRC-Codes sind
\series bold
liniar, systematisch und zyklisch.
\end_layout
\begin_layout Subsubsection
Verfahren
\end_layout
\begin_layout Standard
An die Nutzdaten U(z) wird eine Prüfsumme der Länge
\begin_inset Formula $\bigcurlywedge$
\end_inset
Bit angehängt werden, so dass das entstehende Codewort C(z) ohne Rest durch
G(z) teilbar ist.
\end_layout
\begin_layout Enumerate
Den Nutzdaten
\begin_inset Formula $u_{j}=(1000010)$
\end_inset
werden Nullen der Ordnung des Generatorpolynoms g(10011) angehängt
\series bold
(Länge –1 also 4)
\series default
(100001+0000)
\end_layout
\begin_layout Enumerate
Nun wird das entstandene Codewort durch das Generatorpolynom geteilt.
\begin_inset Newline newline
\end_inset
\begin_inset Graphics
filename Images/beispiel_crc_generieren.png
scale 40
\end_inset
\end_layout
\begin_layout Enumerate
Die angehängten Nullen rechts vom Codewort werden durch den Rest ersetzt.
\begin_inset Formula $c_{j}=(1000010001)$
\end_inset
\end_layout
\begin_layout Standard
\series bold
Übertragung:
\series default
Wenn ein Fehler auftritt wird ein Fehlervektor e der Länge des Codeworts
addiert
\series bold
\begin_inset Formula $c_{b}=c_{j}+e$
\end_inset
\begin_inset Newline newline
\end_inset
Decodierung:
\series default
Das Codewort
\begin_inset Formula $c_{b}$
\end_inset
wird wieder durch das Generatorpolynom
\begin_inset Formula $g$
\end_inset
geteilt.
Ist der Rest 00000, war die Übertragung korrekt.
\end_layout
\begin_layout Subsubsection
Fehlererkennung
\end_layout
\begin_layout Description
Ungerade
\begin_inset space ~
\end_inset
Anzahl
\begin_inset space ~
\end_inset
Fehler Wenn das CRC-Polynom eine gerade Anzahl Termen enthält, werden alle
ungeradzahligen Bitfehler erkannt.
\end_layout
\begin_layout Description
Burstfehler Ein Burstfehler wird erkannt, wenn die Länge des Bursts den
Grad (Länge –1) des CRC-Polynoms nicht übersteigt.
\end_layout
\begin_layout Description
Zwei
\begin_inset space ~
\end_inset
isolierte
\begin_inset space ~
\end_inset
Bitfehler Ob diese erkannt werden hängt sowohl vom Generatorpolynom wie
auch von der Länge der Nachricht ab.
\end_layout
\begin_layout Description
Fehlerkorrektur Fehler können anhand des Rests der Decodierung erkannt werden.
\end_layout
\begin_layout Section
Liniare Blockcodes
\end_layout
\begin_layout Standard
Lineare (N, K)-Blockcodes basieren auf einer Generatormatrix.
\end_layout
\begin_layout Subsection
Encoder
\end_layout
\begin_layout Standard
Der Encoder bildet die
\begin_inset Formula $2^{k}$
\end_inset
möglichen Nutzdatenworte
\begin_inset Formula $u_{j}$
\end_inset
auf
\begin_inset Formula $2^{k}$
\end_inset
N-dimensionale Codeworte
\begin_inset Formula $c_{j}$
\end_inset
ab.
Er verwendet eine Generatormatrix
\begin_inset Formula $G^{KxN}$
\end_inset
, man erhällt das Codewort mit der Multiplikation
\begin_inset Formula $c_{j}=u_{j}\cdot G$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Graphics
filename Images/Beispiel_lineare_blockcodes_generatormatrix.png
scale 60
\end_inset
\begin_inset Newline newline
\end_inset
Die Generatormatrix hat die Dimension 4 x 7 mit K=4 und N=7.
Jedes Codewort ist eine Liniarkombination der Zeilen der Generatormatrix
bei denen
\begin_inset Formula $c$
\end_inset
den Wert 1 hat.
Die Rechten vier Spalten bilden eine Einheitsmatrix
\begin_inset Formula $I^{4x4}.$
\end_inset
\end_layout
\begin_layout Subsection
Decoder
\end_layout
\begin_layout Standard
Zur Prüfung der Codeworte wird eine Paritätsprüfmatrix
\begin_inset Formula $H$
\end_inset
verwendet.
Die Matrix
\begin_inset Formula $H$
\end_inset
hat die Dimension N – K x N.
\end_layout
\begin_layout Standard
\begin_inset Formula $G_{r}=(P\,I)\Rightarrow H_{l}=(I\,P^{T})$
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Graphics
filename Images/paritätsprüfmatrix_Blockcode.png
scale 60
\end_inset
\begin_inset Newline newline
\end_inset
Mit der Paritätsprüfmatrix wird aus dem Bitmuster
\begin_inset Formula $c$
\end_inset
ein Syndrom
\begin_inset Formula $s$
\end_inset
berechnet:
\begin_inset Formula $s=c\cdot H^{T}.$
\end_inset
Ist das Codewort gültig so wird
\begin_inset Formula $s=0$
\end_inset
.
Der Wert des Syndroms
\begin_inset Formula $s$
\end_inset
erhält man auch wenn man den korrespondierenden Fehlervektor mal die Paritätspr
üfmatrix rechnet:
\begin_inset Formula $s=e\cdot H^{T}$
\end_inset
.
\end_layout
\begin_layout Section
Faltungscodes
\end_layout
\begin_layout Standard
Codebits ensteht durch eine Mathematische Faltung.
\end_layout
\begin_layout Description
Coderate
\begin_inset Formula $R=\frac{K}{2\cdot(K+m)}$
\end_inset
Mit Länge des Schieberegisters = m und K = Anzahl Eingangsbits.
\end_layout
\begin_layout Description
Freie
\begin_inset space ~
\end_inset
Distanz
\begin_inset space ~
\end_inset
\begin_inset Formula $d_{\text{free}}$
\end_inset
Anzahl einsen die beim Kürzesten Weg des Zustandsdiagramms von (00) bis
(00) enstehen.
Z.B.
(00 .
.
.
00 11 10 11 00 .
.
.
00)
\begin_inset Formula $\Rightarrow d_{\text{free}}=5$
\end_inset
\end_layout
\begin_layout Description
\begin_inset Graphics
filename Images/faltungscode_encoder_visualisierung.png
scale 60
\end_inset
\begin_inset Graphics
filename Images/Faltungscode_tabelle.png
scale 60
\end_inset
\end_layout
\begin_layout Subsection
Zustandsgiagramm & Trellis-Diagram / Viterbi-Decoder
\end_layout
\begin_layout Standard
Im Kreis: Zustand von
\begin_inset Formula $u_{k-1},u_{k-2}$
\end_inset
und
\begin_inset Formula $\frac{\text{Eingang}u_{k}}{\text{Ausgang}(c_{2k},c_{2k+1}}$
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Graphics
filename Images/faltungscode_zustandsdiagramm.png
scale 60
\end_inset
\begin_inset Graphics
filename Images/faltungscode_decoder.png
scale 40
\end_inset
\end_layout
\begin_layout Part
JPEG
\end_layout
\begin_layout Standard
JPEG heisst Joint Photographics Experts Group.
\end_layout
\begin_layout Section
Schritte des Verfahrens
\end_layout
\begin_layout Enumerate
\series bold
Transformation Farbbilder RGB => Luminanz / Chrominanz
\series default
\begin_inset Newline newline
\end_inset
Das Auge ist viel empfindlicher auf kleine Helligkeitsunterschiede als auf
kleine Farbunterschiede (Irrelevanz à komprimierbar, ohne dass man es merkt)
\begin_inset Newline newline
\end_inset
Vorbereitung für Datenkompression
\end_layout
\begin_layout Enumerate
\series bold
Downsampling der beiden Chrominanz-Komponenten
\series default
\begin_inset Newline newline
\end_inset
2:1 horizontal und vertikal (2h2v oder 4:2:0)
\begin_inset Newline newline
\end_inset
=> Bildgrösse 1/3 + (2/3)·(1/4) = 1/2
\begin_inset Newline newline
\end_inset
2:1 horizontal, 1:1 vertikal (2h1v oder 4:2:2)
\begin_inset Newline newline
\end_inset
=> Bildgrösse 1/3 + (2/3)·(1/2) = 2/3
\end_layout
\begin_layout Enumerate
\series bold
Pixel-Gruppierung Farbkomponenten in 8x8 Blöcke
\series default
\begin_inset Newline newline
\end_inset
Ausnützung der horizontalen und vertikalen Korrelation
\begin_inset Newline newline
\end_inset
Blöcke werden separat komprimiert (Schwachstelle!)
\end_layout
\begin_layout Enumerate
\series bold
Diskrete Cosinus Transformation (8x8 DCT)
\series default
\begin_inset Newline newline
\end_inset
Transformation in den Frequenzbereich
\begin_inset Newline newline
\end_inset
Vorbereitung für die Datenkompression
\begin_inset Newline newline
\end_inset
DC und 3-4 tieffrequente AC-Werte enthalten „Bildinformation“
\end_layout
\begin_layout Enumerate
\series bold
Individuelle Quantisierung einzelner Frequenzkomponenten
\series default
\begin_inset Newline newline
\end_inset
Prinzip: Frequenzkomponenten mit viel bzw.
wenig Bildinformation werden fein bzw.
grob quantisiert
\end_layout
\begin_layout Enumerate
\series bold
Entropy-Coding der quantisierten Frequenzkomponenten
\series default
\begin_inset Newline newline
\end_inset
verlustlos, Kombination von RLE und Huffman encoding
\end_layout
\begin_layout Enumerate
\series bold
Addition von Header und JPEG-Parameter
\end_layout
\begin_layout Section
JPEG Blockverarbeitung
\end_layout
\begin_layout Standard
\begin_inset Graphics
filename Images/JPEG_Blockverarbeitung.png
scale 35
\end_inset
\end_layout
\begin_layout Section
Downsampling beiden Chrominanz-Komponenten
\end_layout
\begin_layout Standard
2:1 horizontal und vertikal 2h2v das Kürzel 4:2:0 verwendet.
Es bedeutet: Erste Zahl 4: = Länge des Blockes, der zusammengefasst wird:
Hier also 4 Bildpunkte, das ist in der untenstehenden Zeichnung links ersichtli
ch Zweite Zahl 2: = Die erste Linie hat zwei Bildpunkte belegt von total
vier (Zeichnung rechts) Dritte Zahl 0: = Die 2.
Linie hat keinen Bildpunkt belegt von total vier (Zeichnung rechts) Das
Format, das damit für 4:2:0 entsteht, ist das folgende:
\end_layout
\begin_layout Standard
\begin_inset Graphics
filename Images/downsampling_formate.png
scale 35
\end_inset
\begin_inset Newline newline
\end_inset
Hier gilt demgemäss: Erste Zahl 4: = Länge des Blockes, der zusammengefasst
wird: Hier also 4 Bildpunkte, das ist in der Zeichnung links ersichtlich
Zweite Zahl 1: = Die erste Linie hat einen Bildpunkt belegt von total vier
(Zeichnung rechts) Dritte Zahl 1: = Die 2.
Linie hat ebenfalls einen Bildpunkt belegt von total vier (Zeichnung rechts)
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
Falls
\series bold
nicht
\series default
\series bold
komprimiert
\series default
wird: 4:4:4
\end_layout
\begin_layout Part
Audio Codierung
\end_layout
\begin_layout Section
Abtastung und Quantisierung
\end_layout
\begin_layout Standard
Um ein analoges Signal in ein digitales Signal zu wandeln, wird der Pegel
periodisch mit einer Tastfrequenz gemessen (abgetastet) und einem Wert
zugewiesen (quantisiert).
\end_layout
\begin_layout Description
Quantisierungsrauschen: Differenz zwischen Quantisierung und Signal
\end_layout
\begin_layout Standard
\begin_inset Graphics
filename Images/Quantisierung_audio.png
scale 60
\end_inset
\end_layout
\begin_layout Description
Puls
\begin_inset space ~
\end_inset
Code
\begin_inset space ~
\end_inset
Modulation
\begin_inset space ~
\end_inset
(unkomprimiert) Z.B.
Telephonie oder Audio-CD
\end_layout
\begin_layout Description
PMC
\begin_inset space ~
\end_inset
(liniar
\begin_inset space ~
\end_inset
quantisiert) Abstand von 0 zu Abtastungshöhe wird mitgegeben
\end_layout
\begin_layout Description
Differential-PCM
\begin_inset space ~
\end_inset
(DPCM) Offset zur nächsten Abtastung wird mitgegeben
\end_layout
\begin_layout Description
Adaptive
\begin_inset space ~
\end_inset
Differential-PCM
\begin_inset space ~
\end_inset
(ADPCM) Es wird der vorhergehende Offset angenommen, die Korrektur wird
gesendet.
\end_layout
\begin_layout Description
Linear
\begin_inset space ~
\end_inset
Prediction
\begin_inset space ~
\end_inset
Coder
\begin_inset space ~
\end_inset
(LPC) Bildet vereinf