diff options
Diffstat (limited to '')
| -rw-r--r-- | buch/chapters/30-endlichekoerper/euklid.tex | 216 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/experiments/f.m | 61 | ||||
| -rw-r--r-- | buch/test3.tex | 91 |
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} |