Merge branch 'master' of https://github.com/AndreasFMueller/SeminarMatrizen

3 files changed, 368 insertions, 0 deletions

diff --git a/buch/chapters/30-endlichekoerper/euklid.tex b/buch/chapters/30-endlichekoerper/euklid.tex
index db326f8..8aa2f71 100644
--- a/buch/chapters/30-endlichekoerper/euklid.tex
+++ b/buch/chapters/30-endlichekoerper/euklid.tex
@@ -431,6 +431,7 @@ zur Bestimmung des grössten gemeinsamen Teilers von $76415$ und $23205$
 zur Berechnung der Koeffizienten $c_k$ und $d_k$
 Wir schreiben die gefundenen Zahlen in eine Tabelle:
 \begin{center}
+\label{buch:endlichekoerper:beispiel1erweitert}
 \renewcommand{\arraystretch}{1.1}
 \begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
 \hline
@@ -614,4 +615,219 @@ Aus den letzten zwei Zeilen folgt
 $ua-vb = ab/g - ab/g = 0$, wie erwartet.
 \end{beispiel}
 
+%
+% Das kleinste gemeinsame Vielfache
+%
+\subsection{Das kleinste gemeinsame Vielfache
+\label{buch:subsection:daskgv}}
+Das kleinste gemeinsame Vielfache zweier Zahlen $a$ und $b$ ist
+\[
+\operatorname{kgV}(a,b)
+=
+\frac{ab}{\operatorname{ggT}(a,b)}.
+\]
+Wir suchen nach einen Algorithmus, mit dem man das kleinste gemeinsame
+Vielfache effizient berechnen kann.
+
+Die Zahlen $a$ und $b$ sind beide Vielfache des grössten gemeinsamen
+Teilers $g=\operatorname{ggT}(a,b)$, es gibt also Zahlen $u$ und $v$ derart,
+dass $a=ug$ und $b=vg$.
+Wenn $t$ ein gemeinsamer Teiler von $u$ und $v$ ist, dann ist $tg$ ein
+grösserer gemeinsamer Teiler von $a$ und $b$.
+Dies kann nicht sein, also müssen $u$ und $v$ teilerfremd sein.
+Das kleinste gemeinsame Vielfache von $a$ und $b$ ist dann $ugv=av=ub$.
+Die Bestimmung des kleinsten gemeinsamen Vielfachen ist also gleichbedeutend
+mit der Bestimmung der Zahlen $u$ und $v$.
+
+Die definierende Eigenschaften von $u$ und $v$ kann man in Matrixform als
+\begin{equation}
+\begin{pmatrix}
+a\\b
+\end{pmatrix}
+=
+\underbrace{
+\begin{pmatrix}
+u&?\\
+v&?
+\end{pmatrix}}_{\displaystyle =K}
+\begin{pmatrix}
+\operatorname{ggT}(a,b)\\ 0
+\end{pmatrix}
+\label{buch:eindlichekoerper:eqn:uvmatrix}
+\end{equation}
+geschrieben werden, wobei wir die Matrixelemente $?$ nicht kennen.
+Diese Elemente müssen wir auch nicht kennen, um $u$ und $v$ zu bestimmen.
+
+Bei der Bestimmung des grössten gemeinsamen Teilers wurde der Vektor auf
+der rechten Seite von~\eqref{buch:eindlichekoerper:eqn:uvmatrix} bereits
+gefunden.
+Die Matrizen $Q(q_i)$, die die einzelne Schritte des euklidischen
+Algorithmus beschreiben, ergeben ihn als
+\[
+\begin{pmatrix}
+\operatorname{ggT}(a,b)\\0
+\end{pmatrix}
+=
+Q(q_n)Q(q_{n-1}) \dots Q(q_1)Q(q_0)
+\begin{pmatrix}a\\b\end{pmatrix}.
+\]
+Indem wir die Matrizen $Q(q_n)$ bis $Q(q_0)$ auf die linke Seite der
+Gleichung schaffen, erhalten wir
+\[
+\begin{pmatrix}a\\b\end{pmatrix}
+=
+Q(q_0)^{-1}
+Q(q_1)^{-1}
+\dots
+Q(q_{n-1})^{-1}
+Q(q_n)
+\begin{pmatrix}\operatorname{ggT}(a,b)\\0\end{pmatrix}.
+\]
+Eine mögliche Lösung für die Matrix $K$ in
+\eqref{buch:eindlichekoerper:eqn:uvmatrix}
+ist der die Matrix
+\[
+K
+=
+Q(q_0)^{-1}
+Q(q_1)^{-1}
+\dots
+Q(q_{n-1})^{-1}
+Q(q_n).
+\]
+Insbesondere ist die Matrix $K$ die Inverse der früher gefundenen
+Matrix $Q$.
+
+Die Berechnung der Matrix $K$ als Inverse von $Q$ ist nicht sehr
+effizient.
+Genauso wie es möglich war, das Produkt $Q$ der Matrizen
+$Q(q_k)$ iterativ zu bestimmen, muss es auch eine Rekursionsformel
+für das Produkt der inversen Matrizen $Q(q_k)^{-1}$ geben.
+
+Schreiben wir die gesuchte Matrix 
+\[
+K_k
+=
+Q(q_0)^{-1}\dots Q(q_{k-1})^{-1}
+=
+\begin{pmatrix}
+e_k & e_{k-1}\\
+f_k & f_{k-1}
+\end{pmatrix},
+\]
+dann kann man $K_k$ durch die Rekursion
+\begin{equation}
+K_{k+1}
+=
+K_{k} Q(q_k)^{-1} 
+=
+K_k K(q_k)
+\qquad\text{mit}\qquad
+K_0 = \begin{pmatrix}1&0\\0&1\end{pmatrix} = I
+\label{buch:endlichekoerper:eqn:kgvrekursion}
+\end{equation}
+berechnen.
+Die Inverse von $Q(q)$ ist
+\[
+K(q)
+=
+Q(q)^{-1}
+=
+\frac{1}{\det Q(q)}
+\begin{pmatrix}
+q&1\\
+1&0
+\end{pmatrix}
+\quad\text{denn}\quad
+K(q)Q(q)
+=
+\begin{pmatrix}
+q&1\\
+1&0
+\end{pmatrix}
+\begin{pmatrix}
+0&1\\
+1&-q
+\end{pmatrix}
+=
+\begin{pmatrix}
+1&0\\
+0&1
+\end{pmatrix}.
+\]
+Da die zweite Spalte von $K(q)$ die erste Spalte einer Einheitsmatrix
+ist, wird die zweite Spalte des Produktes $AK(q)$ immer die erste Spalte
+von $A$ sein.
+In $K_{k+1}$ ist daher nur die erste Spalte neu, die zweite Spalte ist
+die erste Spalte von $K_k$.
+
+Aus der Rekursionsformel \eqref{buch:endlichekoerper:eqn:kgvrekursion}
+für die Matrizen $K_k$ kann man jetzt eine Rekursionsbeziehung
+für die Folgen $e_k$ und $f_k$ ablesen, es gilt
+\begin{align*}
+e_{k+1} &= q_ke_k + e_{k-1} \\
+f_{k+1} &= q_kf_k + f_{k-1}
+\end{align*}
+für $k=0,1,\dots ,n$.
+Damit können $e_k$ und $f_k$ gleichzeitig mit den Zahlen $c_k$ und $d_k$
+in einer Tabelle berechnen.
+
+\begin{beispiel}
+Wir erweitern das Beispiel von
+Seite~\pageref{buch:endlichekoerper:beispiel1erweitert}
+um die beiden Spalten zur Berechnung von $e_k$ und $f_k$:
+\begin{center}
+\renewcommand{\arraystretch}{1.1}
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
+\hline
+k&   a_k&   b_k&    q_k&  r_k&     c_k&     d_k&   e_k&   f_k\\
+\hline
+ &      &      &       &     &       1&       0&     0&     1\\
+0& 76415& 23205&      3& 6800&       0&       1&     1&     0\\
+1& 23205&  6800&      3& 2805&       1&      -3&     3&     1\\
+2&  6800&  2805&      2& 1190&      -3&      10&    10&     3\\
+3&  2805&  1190&      2&  425&       7&     -23&    23&     7\\
+4&  1190&   425&      2&  340&     -17&      56&    56&    17\\
+5&   425&   340&      1&   85&      41&    -135&   135&    41\\
+6&   340&    85&      4&    0&     -58&     191&   191&    58\\
+7&    85&     0&       &     &     273&    -899&   899&   273\\
+\hline
+\end{tabular}
+\end{center}
+Der grösste gemeinsame Teiler ist $\operatorname{ggT}(a,b)=85$.
+Aus der letzten Zeile der Tabelle kann man jetzt die Zahlen $u=e_7=899$
+und $v=f_7=273$ ablesen, und tatsächlich ist
+\[
+a=76415 = 899\cdot 85
+\qquad\text{und}\qquad
+b=23205 = 273 \cdot 85.
+\]
+Daraus kann man dann auch das kleinste gemeinsame Vielfache ablesen, es ist
+\[
+\operatorname{kgV}(a,b)
+=
+\operatorname{kgV}(76415,23205)
+=
+\left\{
+\begin{aligned}
+ub
+&=
+899\cdot 23205\\
+va
+&=
+273\cdot 76415
+\end{aligned}
+\right\}
+=
+20861295.
+\qedhere
+\]
+\end{beispiel}
+
+Der erweiterte Algorithmus kann auch dazu verwendet werden,
+das kleinste gemeinsame Vielfache zweier Polynome zu berechnen.
+Dies wird zum Beispiel bei der Decodierung des Reed-Solomon-Codes in
+Kapitel~\ref{chapter:reedsolomon} verwendet.
+
+
 
diff --git a/buch/papers/reedsolomon/experiments/f.m b/buch/papers/reedsolomon/experiments/f.m
new file mode 100644
index 0000000..6bdc741
--- /dev/null
+++ b/buch/papers/reedsolomon/experiments/f.m
@@ -0,0 +1,61 @@
+#
+# f.m -- Reed-Solomon-Visualisierung mit FFT
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+N = 64;
+b = 32;
+l = N + b;
+
+signal = zeros(l,1);
+signal(1:N,1) = round(10 * rand(N,1));
+signal
+
+plot(abs(signal));
+xlim([1, l]);
+title("Signal");
+pause()
+
+codiert = fft(signal)
+
+plot(abs(codiert));
+xlim([1, l]);
+title("Codiert");
+pause()
+
+fehler = zeros(l,1);
+fehler(21,1) = 2;
+fehler(75,1) = 1;
+fehler(7,1) = 2;
+
+plot(fehler);
+xlim([1, l]);
+title("Fehler");
+pause()
+
+empfangen = codiert + fehler;
+
+plot(abs(empfangen));
+xlim([1, l]);
+title("Empfangen");
+pause()
+
+decodiert = ifft(empfangen)
+plot(abs(decodiert));
+xlim([1, l]);
+title("Decodiert");
+pause()
+
+syndrom = decodiert;
+syndrom(1:N,1) = zeros(N,1)
+plot(abs(syndrom));
+xlim([1, l]);
+title("Syndrom");
+pause()
+
+locator = abs(fft(syndrom))
+
+plot(locator);
+xlim([1, l]);
+title("Locator");
+pause()
diff --git a/buch/test3.tex b/buch/test3.tex
new file mode 100644
index 0000000..71b1529
--- /dev/null
+++ b/buch/test3.tex
@@ -0,0 +1,91 @@
+%
+% test3.tex -- Test 3
+%
+% (c) 2021 Prof. Dr. Andreas Mueller, OST
+%
+%\documentclass[a4paper,12pt]{book}
+\documentclass[a4paper,12pt]{article}
+\usepackage{geometry}
+\geometry{papersize={210mm,297mm},total={165mm,260mm}}
+\usepackage{ngerman}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{times}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{amsfonts}
+\usepackage{amsthm}
+\usepackage{graphicx}
+\usepackage{fancyhdr}
+\usepackage{textcomp}
+\usepackage[all]{xy}
+\usepackage{txfonts}
+\usepackage{alltt}
+\usepackage{verbatim}
+\usepackage{paralist}
+\usepackage{makeidx}
+\usepackage{array}
+\usepackage{hyperref}
+\usepackage{caption}
+\usepackage{subcaption}
+\usepackage{standalone}
+\usepackage{environ}
+\usepackage{tikz}
+\input{../common/linsys.tex}
+\newcounter{beispiel}
+\newenvironment{beispiele}{
+\bgroup\smallskip\parindent0pt\bf Beispiele\egroup
+
+\begin{list}{\arabic{beispiel}.}
+  {\usecounter{beispiel}
+  \setlength{\labelsep}{5mm}
+  \setlength{\rightmargin}{0pt}
+}}{\end{list}}
+\newcounter{uebungsaufgabe}
+% environment fuer uebungsaufgaben
+\newenvironment{uebungsaufgaben}{
+\begin{list}{\arabic{uebungsaufgabe}.}
+  {\usecounter{uebungsaufgabe}
+  \setlength{\labelwidth}{2cm}
+  \setlength{\leftmargin}{0pt}
+  \setlength{\labelsep}{5mm}
+  \setlength{\rightmargin}{0pt}
+  \setlength{\itemindent}{0pt}
+}}{\end{list}\vfill\pagebreak}
+\newenvironment{teilaufgaben}{
+\begin{enumerate}
+\renewcommand{\labelenumi}{\alph{enumi})}
+}{\end{enumerate}}
+% Loesung
+\NewEnviron{loesung}{%
+\begin{proof}[Lösung]%
+\renewcommand{\qedsymbol}{$\bigcirc$}
+\BODY
+\end{proof}}
+\NewEnviron{bewertung}{\relax}
+\NewEnviron{diskussion}{
+\BODY
+}
+\RenewEnviron{loesung}{\relax}
+\RenewEnviron{diskussion}{\relax}
+\newenvironment{hinweis}{%
+\renewcommand{\qedsymbol}{}
+\begin{proof}[Hinweis]}{\end{proof}}
+
+\begin{document}
+{\parindent0pt\hbox to\hsize{%
+Name: \hbox to7cm{\dotfill} Vorname: \dotfill}}
+\vspace{0.5cm}
+
+\section*{Kurztest 3}
+
+\begin{uebungsaufgaben}
+
+\item
+\input chapters/60-gruppen/uebungsaufgaben/6001.tex
+%\item
+%\input chapters/60-gruppen/uebungsaufgaben/6002.tex
+
+\end{uebungsaufgaben}
+
+\end{document}