codierungstheorie.tex

\documentclass{cheat-sheet}

\pdfinfo{
  /Title (Zusammenfassung Codierungstheorie)
  /Author (Tim Baumann)
}

\usepackage{nicefrac}
\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage[normalem]{ulem} % \sout
\usepackage{multirow}
\usepackage{upgreek} % für \upsigma
\usepackage{stmaryrd} % für \llbracket

% Kleinere Klammern
\delimiterfactor=701

\newcommand{\K}{\mathbb{K}} % Körper
\newcommand{\F}{\mathbb{F}} % endlicher Körper
\newcommand{\GF}{\mathbb{GF}} % endlicher Körper
\renewcommand{\P}{\mathbb{P}} % Wahrscheinlichkeit
\newcommand{\CP}[2]{\P({#1}\mid{#2})} % Conditional Probability
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\newcommand{\err}{\text{err}} % Fehler
\newcommand{\ceil}[1]{\lceil #1 \rceil} % Aufrunden
\newcommand{\floor}[1]{\lfloor #1 \rfloor} % Abrunden
\DeclareMathOperator{\wt}{wt} % Hamming-Gewicht
\DeclareMathOperator{\spann}{span} % aufgespannte (lineare) Hülle
\newcommand{\lin}{\text{lin}} % linear
\newcommand{\scp}[2]{\left\langle #1, #2 \right\rangle} % Skalarprodukt
\newcommand{\homogen}{\text{hom}} % homogen
\newcommand{\divides}{|} % teilt
\DeclareMathOperator{\Ham}{Ham} % Hamming-Code (was sonst?)
\DeclareMathOperator{\Sim}{Sim} % Simplex-Code
\newcommand{\Proj}{\mathbb{P}} % Projektiver Raum
\newcommand{\Golay}{\mathcal{G}} % Golay-Code
\newcommand{\Design}{\mathcal{D}} % Design, Inzidenzstruktur
\newcommand{\Blocks}{\mathcal{B}} % Blöcke einer Inzidenzstruktur
\newcommand{\Pow}{\mathcal{P}} % Potenzmenge (powerset)
\newcommand{\Geraden}{\mathcal{G}} % Geraden in Blocksystem
\newcommand{\RM}{\mathcal{R}} % Reed-Muller-Code
\newcommand{\PCE}[1]{\widehat{#1}} % Parity-Check-Erweiterung
\DeclareMathOperator{\trace}{trace} % Spur
\DeclareMathOperator{\ggT}{ggT} % größter gemeinsamer Teiler
\DeclareMathOperator{\kgV}{kgV} % kleinstes gemeinsames Vielfaches
\DeclareMathOperator{\ord}{ord} % Ordnung
\newcommand{\rez}{\mathrm{rez}} % reziprok

% http://tex.stackexchange.com/a/7045
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=1pt] (char) {\scriptsize #1};}}

\begin{document}

\raggedcolumns % stretche Inhalt nicht über die gesamte Spaltenhöhe

\maketitle{Zusammenfassung Codierungstheorie}

Diese Zusammenfassung basiert auf der Vorlesung von Prof. Dr. Dirk Hachenberger an der Universität Augsburg im WS\,15/16.

% Vorlesung vom 13. Oktober 2015

% §1. Grundproblemstellung
\section{§1. Grundproblemstellung}

% §1.1 Aufgaben der Codierungstheorie

\[
  \text{Datenquelle} \enspace
  \xrightarrow{\text{senden}} \enspace
  \text{Kanal} \enspace
  \xrightarrow{\text{empfangen}} \enspace
  \text{Senke}
\]
Die Daten liegen bereits digitalisiert vor.
Mit dem Problem wie Daten wie bspw. nat. Sprache möglichst effizient codiert werden, befasst sich die Informationstheorie.
In der Codierungstheorie geht es darum, Daten mit einer Kanalcodierung so zu übersetzen, dass Fehler, die bei einer Übertragung über einen fehlerhaften Kanal, korrigiert oder zumindest bemerkt werden.

% (1.1) Bsp
% Nord = 00
% Ost = 01
% Süd = 10
% West = 11
%
% Nachrichtenmenge = Sendermenge = Empfängermenge

% §1.2 Einführende Beispiele

\begin{align*}
  \text{Datenquelle} \enspace
  & \xrightarrow[E]{\text{codieren}}
  \text{Code} \enspace
  \xrightarrow{\text{senden}} \enspace
  \text{Kanal} \enspace
  \xrightarrow{\text{empfangen}} \enspace
  \square \enspace \\
  & \xrightarrow[D]{\text{decodieren}} \enspace
  \text{Code}
  \xrightarrow[E^{-1}]{} \enspace
  \text{Senke}
\end{align*}

% (1.2) Bsp (Fortsetzung von (1.1))

% (1) Einführung eines Paritätsbit: $ab \mapsto c \coloneqq a+b (mod 2)$
% Nachrichtenmenge = {00,01,10,11}
% Sendermenge = {000,011,101,110}
% Empfängermenge = {000,001,010,011,100,101,110,111}

% 110 --> 010

% (2) Triple-Repetition

% Codieren

% 00 \mapsto 000000
% 01 \mapsto 010101
% 10 \mapsto 101010
% 11 \mapsto 111111

% decodieren mit dem Nächster-Nachbar-Prinzip
% Informationsrate 1/3

% (3) Optimaler Code zur 1-Fehlerkorrektur: Ein (5,4,3)-Code, binär

% 00 \mapsto 00000
% 01 \mapsto 01101
% 10 \mapsto 10110
% 11 \mapsto 11011

% 2^2 aus 2^5: Die Codes unterscheiden sich paarweise an mindestens 3 Positionen
% Informationsrate: 2/5

% §2. Formalisierung der Grundbegriffe
\section{§2. Formalisierung der Grundbegriffe}

% §2.1 q-närer Code und Hamming-Abstand

\begin{defn}
  Ein \emph{Alphabet} ist eine Menge $Q$ mit $q > 1$ Elementen, typischerweise $\{ 0, 1, \ldots, q-1 \} \cong \Z_q$.
\end{defn}

\begin{bem}
  $\Z_q$ trägt die Struktur eines Ringes.
  Falls $q$ eine Primzahlpotenz ist, so gibt es einen Körper $\F_q$ mit $q$ Elementen.
\end{bem}

\begin{defn}
  Sei $n \geq 1$. Eine nichtleere Menge $C \subseteq Q^n$ mit $q = \abs{Q}$ heißt \emph{Blockcode} der Länge $n$ über $Q$ oder \emph{$q$-närer Code} der Länge $n$. Jedes $c = (c_1, \ldots, c_n) \in C$ heißt ein \emph{Codewort}.
  Falls $M = \abs{C}$, so nennt man $C$ einen \emph{$(n, M)$-Code} über $Q$.
\end{defn}

\begin{defn}
  Die \emph{Informationsrate} von $C$ ist dann $R(C) \coloneqq \nicefrac{\log_q(M)}{n}$.
  Falls $\abs{C} = M = q^k$, dann ist $R(C) = k/n$.
\end{defn}

\begin{bem}
  Ist $Q \cong \F_q$, dann ist $Q^n$ ein $\F_q$-VR. Falls $C$ ein Unterraum von $Q^n$ ist, so ist $R(C) = \nicefrac{\dim_{\F_q}(C)}{n}$.
\end{bem}

\begin{samepage}

\begin{defn}
  Der \emph{Hamming-Abstand} von $u, v \in Q^n$ ist
  \[ d(u, v) \coloneqq \abs{\Set{i=1,\ldots,n}{u_i \neq v_i}}. \]
\end{defn}

\begin{lem}
  Der Hamming-Abstand ist eine Metrik auf $Q^n$.
\end{lem}

% §2.2 Das Decodierprinzip des nächsten Nachbarn
\subsection{Das Decodierprinzip des nächsten Nachbarn}

\end{samepage}

\begin{nota}
  Es sei $C \subseteq Q^n$ ein Code.
  Wenn $y \in Q^n$ empfangen wurde, so geht man davon aus, dass das gesendete Wort dasjenige des Codes mit den wenigsten Unterschieden zu $y$ ist, also ein Wort, welches den Hamming-Abstand $d(y, C) \coloneqq {\min}_{c \in C} d(y, c)$ von $y$ zu $C$ realisiert.
  Es existiert i.\,A. kein eindeutiges solches Element, sondern eine Menge
  \[ N_C(y) \coloneqq \Set{\overline{c}}{d(y, C) = d(y, \overline{c})}. \]
\end{nota}

\begin{defn}
  \begin{itemize}
    \item Man nennt einen Kanal einen \emph{$q$-nären symmetrischen Kanal}, falls ein $p \in \R$ mit $0 < p < (q-1)/q$ existiert, sodass
    \[ \CP{\text{$\beta$ empfangen}}{\text{$\alpha$ gesendet}} = \nicefrac{p}{q-1} \]
    für alle $\beta \neq \alpha \in Q$, also $\CP{\text{$\alpha$ empfangen}}{\text{$\alpha$ gesendet}} = 1-p$.
    \item Ein Kanal heißt \emph{gedächtnislos}, falls für alle $y \in Q^n$ gilt:
    \[ \CP{\text{$y$ empfangen}}{\text{$c$ gesendet}} = \prod_{i=1}^n \CP{\text{$y_i$ empfangen}}{\text{$c_i$ gesendet}} \]
  \end{itemize}
\end{defn}

\begin{defn}[\emph{Maximum-Likelihood-Prinzip}]
  Gegeben sei ein Code $C \subseteq Q^n$ und $y \in Q^n$.
  Gesucht ist $\hat{c} = {\argmax}_{c \in C} \CP{y}{c}$.
\end{defn}

\begin{satz}
  Es seien ein $q$-närer symm, gedächtnisloser Kanal und ein Code $C \subseteq Q^n$ gegeben.
  Sei $y \in Q^n$ und $\hat{c} \in C$.
  Dann sind äquivalent:
  \begin{itemize}
    \miniitem{0.48 \linewidth}{$\CP{y}{\hat{c}} = {\max}_{c \in C} \CP{y}{c}$}
    \miniitem{0.48 \linewidth}{$\hat{c} \in N_c(y)$}
  \end{itemize}
\end{satz}

% Vorlesung vom 15. Oktober 2015

\begin{defn}
  $D : Q^n \to C$ heißt \emph{vollständige Decodierabbildung}, falls
  \[ \fa{y \in Q^n} D(y) \in N_C(y). \]
\end{defn}

\iffalse
\begin{bem}
  Es gilt
  \[ \CP{y}{c} = \CP{c}{y} \cdot \tfrac{\P(y)}{\P(c)} = \CP{c}{y} \cdot \P(y) \cdot M \]
  Also: Ist $y$ gegeben, so wird $\CP{y}{c}$ genau dann maximal, wenn $\CP{c}{y}$ maximal ist.
\end{bem}
\fi

% §2.3 Shannons Hauptsatz der Kanalcodierung
\subsection{Shannons Hauptsatz der Kanalcodierung}

\begin{defn}
  Die \emph{Kanalkapazität} eines $q$-nären symmetrischen Kanal ist
  \[ \kappa(q, p) \coloneqq \log_2(q) + p \cdot \log_2 (\nicefrac{p}{q-1}) + (1-p) \cdot \log_2 (1-p). \]
  Sie ist ein Maß für die maximale Information, die über den Kanal übertragen werden kann.
  Die \emph{Entropiefunktion} ist
  \[ H(q, p) \coloneqq 1 - \kappa(q, p). \]
\end{defn}

% q=2. \kappa(2,p) = 1 + p \log_2(p) + (1-p) \log_2(1-p)
% \kappa(2, \tfrac{1}{2}) = 1 + \tfrac{1}{2} \cdot (-1) + \tfrac{1}{2} \cdot (-1) = 0

% Ausgelassen: Skizze von \kappa(2, p)

\begin{defn}
  Sei $C$ ein Code und $D$ sei eine zugehörige (vollständige) Decodierabbildung.
  Die \emph{Restfehlerwahrscheinlichkeit} zu $(C, D)$:
  \[ \P_{\text{err}}(C) \coloneqq {\max}_{y \in Q^n, c \in C} \, \CP{D(y) \neq c}{\text{$c$ gesendet, $y$ empfangen}} \]
\end{defn}

\begin{samepage}

% 2.9
\begin{satz}[\emph{Shannon}]
  Sei $0 < R < \kappa(q, p)$.
  Dann gibt es eine Folge $(C_n)_{n \in \N}$ von Codes und zugehörigen Decodierabbildungen $D_n$ mit: %folgenden Eigenschaften:
  \begin{itemize}
    \item $C_n$ ist ein $(n, M_n)$-Code mit Informationsrate $R \!\leq\! R(C_n) \!<\! \kappa(q, p)$
    \item $\lim_{n \to \infty} \left( \P_\err(C_n) \right) = 0$
  \end{itemize}
\end{satz}

% 3. Korrektureigenschaften und zwei Schranken
\section{§3. Fehlerkorrektur und zwei Schranken}

\end{samepage}

% §3.1 Fehlererkennung und -korrektur

% 3.1
\begin{defn}
  Der \emph{Minimalabstand} eines $(n, M)$-Codes $C$ über $Q$ ist
  \[ d \coloneqq d(C) \coloneqq {\min}_{c,c' \in C, c \neq c'} \, d(c,c'). \]
  Man sagt dann, $C$ ist ein $q$-närer $(n, M, d)$-Code.
\end{defn}

\begin{nota}
  Für $u \in Q^n$, $\ell \in \N$ sei $B_\ell(u) \coloneqq \Set{x \in Q^n}{d(x, u) \leq \ell}$.
\end{nota}

\begin{defn}
  \begin{itemize}
    \item Ein Code $C$ heißt \emph{$\ell$-fehlerkorrigierend}, falls $B_\ell(c) \cap B_\ell(c') = \emptyset$ für alle $c, c' \in C$ mit $c \neq c'$.
    \item $C$ heißt \emph{$m$-fehlererkennend}, wenn $B_m(c) \cap C = \{ c \}$ f.\,a. $c \in C$.
    \item $C$ heißt \emph{genau $\ell$-fehlerkorrigierend/-erkennend}, falls $C$ $m$-fehlerkorr./-erkennend für $m \coloneqq \ell$ aber nicht $m \coloneqq \ell+1$ ist.
  \end{itemize}
\end{defn}

% 3.3
\begin{satz}
  Jeder $(n, M, d)$-Code $C$ ist genau
  \begin{itemize}
    \miniitem{0.46 \linewidth}{$(d{-}1)$-fehlererkennend und}
    \miniitem{0.52 \linewidth}{$(t \coloneqq \floor{\nicefrac{(d-1)}{2}})$-fehlerkorrigierend.}
  \end{itemize}
\end{satz}

\begin{bsp}
  $C = \{ 000, 111 \}$ ist ein binärer $(3, 2, 3)$-Code.
\end{bsp}

% Hauptproblemstellung
\begin{prob}
  Gegeben: $q$, Länge $n$, Minimalabstand $d$.
  Gesucht:
  \[ A_q(n, d) \coloneqq \max \, \Set{M}{\exists\,\text{$(n,M,d)$-Code}} \]
\end{prob}

\begin{defn}
  Ein $(n, M, d)$-Code heißt \emph{optimal}, falls $M = A_q(n, d)$.
\end{defn}

\columnbreak

% §3.2 Singleton-Schranke
\subsection{Die Singleton-Schranke}

% 3.5
\begin{lem}
  Seien $q, n \in \N$, $q \geq 2$, $n \geq 1$.
  \begin{itemize}
    \item $A_q(n,1) = q^n$, realisiert durch $C = Q^n$.
    \item $A_q(n,n) = q$, realisiert durch $C = \Set{(a, \ldots, a)}{a \in Q} \subseteq Q^n$
    \item $d \leq d' \implies A_q(n, d) \geq A_q(n, d')$
    \item Sei $n \geq 2$ und $d \geq 2$. Dann gilt $A_q(n, d) \leq A_q(n-1,d-1)$.
  \end{itemize}
\end{lem}

Letztere Aussage bekommt man durch \textit{Punktieren}, \dh{} Streichen einer Koordinate von~$Q^n$.

% 3.6
\begin{kor}[\emph{Singletonschranke}]
  $A_q(n, d) \leq q^{n-d+1}$
\end{kor}

% 3.7
\begin{defn}
  Ein Code, der die Singletonschranke mit Gleichheit erfüllt, heißt ein \emph{MDS-Code} (MDS = \textit{maximum distance separable}).
\end{defn}

\begin{samepage}

\begin{bem}
  Sei $C \subseteq Q^n$ ein $(n, M, d)$-Code,
  $T = \{ 1 \!\leq t_1 < \ldots < t_{\abs{T}} \leq\! n \}$ und
  $\pi_T : C \to Q^{\abs{T}}, \enspace c \mapsto (c_{t_1}, \ldots, c_{t_{\abs{T}}})$.
  Ist $C$ ein MDS-Code, so ist $\pi_T$ bijektiv für alle $T$ mit $\abs{T} = n - d + 1$.
\end{bem}

% Vorlesung vom 20.10.2015
% §3.3. Abelsche Gruppen als Alphabete
\subsection{Abelsche Gruppen als Alphabete}

\end{samepage}

\begin{defn}
  Sei $(G, +, 0)$ eine kommutative Gruppe. \\
  Das \emph{Hamming-Gewicht} von $x \in G^n$ ist
  \[
    \wt(x) \coloneqq \abs{\supp(x)},
    \quad \text{wobei} \quad
    \supp(x) \coloneqq \Set{i}{x_i \neq 0}.
  \]
\end{defn}

\begin{lem}
  Sei $G$ wie oben, $x, y \in G^n$.
  Dann ist $\wt(x-y) = d(x, y)$.
\end{lem}

\begin{satz}
  $A_q(n, 2) = q^{n-1}$ für alle $q \geq 2$ und alle $n \geq 2$.
\end{satz}

\begin{proof}
  Wir konstruieren einen $(n, q^{n-1}, 2)$-Code.
  Sei $R$ ein kommutativer Ring mit $q$ Elementen, $\lambda_1, \ldots, \lambda_{n-1} \in R$ Einheiten und $\lambda_n \coloneqq -1$. Wir betrachten die Kontrollgleichung
  \[
    \kappa : R^n \to R, \quad
    z \mapsto \lambda_1 z_1 + \ldots + \lambda_n z_n.
  \]
  Dann ist $C \coloneqq \ker(\kappa)$ ein 1-fehlererkennender Code.
\end{proof}

\begin{lem}
  Falls $\lambda_2 - \lambda_1, \ldots, \lambda_n - \lambda_{n-1}$ ebenfalls Einheiten sind, so sind Nachbarvertauschungen als Fehler erkennbar.
\end{lem}

\begin{bspe}
  \begin{itemize}
    \item Für $q=2, R=\Z_2, \lambda_1 = \ldots = \lambda_{n-1} = 1$ heißt $C \coloneqq \ker(\kappa)$ \emph{Parity-Check-Erweiterung}.
    \item Beim ISBN-Code ist $R \!=\! \Z_{11}$, $\lambda_1 \!=\! 1, \nldots, \lambda_9 \!=\! 9$, also $\kappa(z) = \sum_{i=1}^{10} i z_i$.
  \end{itemize}
\end{bspe}

% Betrachte nun q=2

\begin{lem}
  Für $x, y \in \Z_2^n$ gilt $d(x,y) = \wt(x) + \wt(y) - 2 \cdot \wt(x \cdot y)$.
\end{lem}

\begin{satz}
  Für alle $n \geq 1$ und $d$ ungerade gilt $A_2(n, d) = A_2(n+1,d+1)$, realisiert durch die Parity-Check-Erweiterung.
\end{satz}

\begin{defn}
  Zwei $(n,M)$-Codes $C$, $C'$ über $Q$ heißen \emph{äquivalent}, falls gilt:
  Es gibt eine Permutation $\gamma$ auf $\{ 1, \ldots, n \}$ und Permutationen $\sigma_1, \ldots, \sigma_n$ auf $Q$, sodass
  \[
    \alpha : Q^n \to Q^n, \quad
    (x_1, \ldots, x_n) \mapsto (\sigma_1(x_{\gamma(1)}), \ldots, \sigma_n(x_{\gamma(n)}))
  \]
  den Code $C$ auf $C'$ abbildet.
\end{defn}

% Ausgelassen: Beispiel

% Vorlesung vom 22.10.2015

% 3.16 Beispiel

\begin{bsp}
  $A_2(5, 3) = 4$ realisiert durch $\{ 00000, 11100, 00111, 11011 \}$
\end{bsp}

% §3.5 Kugelpackungsschranke
\subsection{Die Kugelpackungsschranke}

% Ausgelassen: Zeichnung

% 3.17
\begin{lem}
  Sei $Q$ ein Alphabet, $u \in Q^n$. %$B_l(u) \coloneqq \Set{x \in Q^n}{d(x,u) \leq l}$.
  Dann gilt
  \[ \abs{B_\ell(u)} = \sum_{j=0}^\ell \binom{n}{j} (\abs{Q}-1)^j. \]
\end{lem}

% 3.18
\begin{satz}[\emph{Kugelpackungsschranke} (KPS)] \mbox{} \\
  Sei $q \geq 2$, $n \geq 2$, $1 \leq d \leq n$, $t \coloneqq \floor{\tfrac{d-1}{2}}$. Dann ist
  \[ A_q(n, d) \leq q^n / \sum_{j=0}^t \binom{n}{j} (q-1)^j. \]
\end{satz}

\begin{defn}
  Ein $q$-närer $(n, M, d)$-Code $C$ heißt \emph{perfekt}, falls $M$ gleich der Kugelpackungsschranke ist.
\end{defn}

\iffalse
\begin{bsp}
  $n = 6$, $q = 2$, $d = 3$. \\
  Singleton-Schranke: $A_2(6, 3) \leq 2^{6-3+1} = 2^4 = 16$ \\
  Kugelpackungsschranke: $A_2(6, 3) \leq \floor{\frac{\floor{2^6}}{\binom{6}{0} (2-1)^0 + \binom{6}{1} (2-1)^1}} = 9$
\end{bsp}
\fi

\begin{samepage}

\begin{bem}
  Die KPS kann zur \emph{Johnsen-Schranke} verbessert werden.
  Zusammen mit dem letzten Beispiel liefert diese $A_2(6, 3) = 8$.
\end{bem}

% 3.21
\begin{bsp}
  Für $q{=}2$, $n{=}7$, $d{=}3$ liefert die KGS genau $A_2(7,3) \leq 16$.
  % Später: Tatsächlich gilt $A_2(7,3) = 16$.
\end{bsp}

% §4. Grundlagen zu linearen Codes
\section{§4. Grundlagen zu linearen Codes}

\end{samepage}

% §4.1. Grundlagen zu endlichen Körpern

\begin{bem}
  Zu jeder Primzahlpotenz $q = p^m \geq 2$ gibt es bis auf Isomorphie genau einen Körper $\GF_q = \F_q$ mit $q$ Elementen. \\
  Die Charakteristik dieses Körpers ist $p$. Ist $q$ keine Primzahlpotenz, so gibt es auch keinen Körper mit $q$ Elementen.
\end{bem}

\begin{konstr}
  Sei $q = p^m$, $p$ prim. Dann gibt es ein irreduzibles Polynom $g(x) \in \Z_p [x]$ mit $\deg(g) = m$.
  Dann ist $\F_q \coloneqq \Z_p[x]/(g(x))$.
\end{konstr}

% §4.2. Das Minimalgewicht eines linearen Codes

% $q \geq 2$ sei eine Primzahlpotenz

\begin{defn}
  Ein \emph{$\F_q$-linearer Code} der Länge $n$ ist ein $\F_q$-Teilraum $\F_q^n$.
\end{defn}

\begin{nota}
  Sei $C$ ein $\F_q$-linearer Code.
  Sei $k \coloneqq \dim(C)$.
  Dann ist $\abs{C} = q^k$, also $C$ ein $(n, q^k)$-Code.
  Man sagt, $C$ ist ein $[n, k]$-Code. \\
  Ist $d$ der Minimalabstand von $C$, so: $C$ ist ein $[n,k,d]$-Code.
\end{nota}

\begin{defn}
  Sei $C$ ein $\F_q$-linearer Code mit $\dim(C) \geq 1$. \\
  Das \emph{Minimalgewicht} von $C$ ist $\min \Set{\wt(c)}{c \in C, c \neq 0}$.
\end{defn}

% 4.4
\begin{lem}
  Sei $C$ ein $\F_q$-linearer Code mit $\dim(C) \geq 1$.
  Dann:
  \[ \text{Minimalgewicht von $C$ = Minimalabstand von $C$.} \]
\end{lem}

\begin{bsp}
  Folgender Code ist ein bin. $(6, 8, 3)$-Code bzw. $[6, 3, 3]$-Code:
  \[
    \arraycolsep=1pt
    \left\{ \begin{array}{rl}
      000000,
      100101,
      & 010110,
      001111, \\
      110011,
      101010,
      & 011001,
      111100
    \end{array} \right\} \!=\! \spann \{ 100101, 010110, 001111 \}
  \]
\end{bsp}

% §4.3 Hauptproblemstellung für lineare Codes

% Gegeben: $\F_q$, Länge $n$, Minimalabstand $d$
% Gewicht: $A_q^{\lin}(n, d) \leq $

\begin{prob}
  Gegeben sei $\F_q$, die Länge $n$ und der Minimalabstand $d$. \\
  Gesucht ist $A_q^\lin(n, d)$, die bestmögliche Anzahl Wörter eines Codes mit diesen Parametern.
\end{prob}

\begin{bem}
  Klar ist $A_q^\lin(n, d) \leq A_q(n, d)$.
\end{bem}

% 4.6
\begin{lem}
  \inlineitem{$A_q^\lin(n, 1) = q^n = A_q(n, 1)$} \quad
  \inlineitem{$A_q^\lin(n, n) = q = A_q(n, n)$}
  \begin{itemize}
    \item $d \leq d' \implies A_q^\lin(n, d) \geq A_q^\lin(n, d')$
    \item Für $n \geq 2$, $d \geq 2$ ist $A_q^\lin(n, d) \leq A_q^\lin(n-1, d-1)$.
  \end{itemize}
\end{lem}

Da die Parity-Check-Erw. durch eine lin. Abb. geschieht, gilt:

\begin{satz}
  $A_1^\lin(n, 2) = q^{n-1} = A_q(n,2)$
\end{satz}

\begin{satz}
  Falls $d$ ungerade, so ist $A_2^\lin(n, d) = A_2^\lin(n+1, d+1)$
\end{satz}

\columnbreak

% Nordstrom-Robinson-Code:
% Ein (16, 256, 6)-Code über $\F_2$

% Vorlesung vom 27.10.2015

% §4.4 Die Generatormatrix
\subsection{Die Generatormatrix}

\begin{defn}
  Sei $C$ ein $[n,k]$-Code über $\F_q$, \dh{} es gibt eine injektive Codierabbildung $E : \F_q^k \to \F_q^n$ mit $\im(E) = C$.
  Dann heißt für jede Basis $g^1, \ldots, g^k \in C$ von $C$ die Matrix
  \[
    G \coloneqq \begin{psmallmatrix}
      g^1 \\ \vdots \\ g^k
    \end{psmallmatrix} \in \F_q^{k \times n} \qquad
    \text{eine \emph{Generatormatrix} von $C$.}
  \]
\end{defn}

\begin{bem}
  Dann ist folgende Abbildung eine Codierabbildung:
  \[
    E : \F_q^k \to C, \quad
    u \mapsto uG = {\sum}_{j=1}^k u_j g^j \in C.
  \]
\end{bem}

% Ausgelassen: Bspe Parity-Check-Erweiterung und 5-Wiederholungscode

\begin{defn}
  Zwei $[n,k]$-Codes $C, C' \subseteq \F_q^n$ heißen \emph{linear äquivalent}, falls es~$\gamma \in S_n$ und $\lambda_1, \ldots, \lambda_n \in \F_q^{\times}$ gibt, sodass die monomiale Transf. \[ \alpha : \F_q^n \to \F_q^n, \enspace (x_1, \ldots, x_n) \mapsto (\lambda_1 x_{\gamma(1)}, \ldots, \lambda_n x_{\gamma(n)}) \]
  den Code $C$ in $C'$ überführt.
\end{defn}

\iffalse
\begin{bspe}
  binäre $[5, 2, 3]$-Codes
  
  $C_1$ hat Generatormatrix $G_1 = \begin{psmallmatrix}
    11100 \\
    00111
  \end{psmallmatrix}$,
  $C_1 = \{ 00000, 111100, 00111, 11011 \}$
  
  $C_2$ hat Generatormatrix $G_2 = \begin{psmallmatrix}
    011001 \\
    10110
  \end{psmallmatrix}$
  $C_2 = \{ 00000, 01101, 10110, 11011 \}$
\end{bspe}
\fi

\begin{defn}
  Ein $[n,k]$-Code heißt \emph{systematisch}, falls die ersten $k$ Spalten seiner Generatormatrix die Standardbasisvektoren sind.
\end{defn}

% §4.5 Gewichtsminimale Repräsentanten und Standard-Array-Decodierung
\subsection{Gewichtsminimale Repräsentanten}

\begin{nota}
  Sei $C \subset \F_q^n$ ein UVR. Für $x, y \in \F_q^n$ schreiben wir
  \[ x \equiv y \pmod{C} \coloniff x-y \in C. \]
  Die zu $x \in \F_q^n$ gehörende Kongruenzklasse modulo $C$ ist $x + C$.
\end{nota}

\begin{defn}
  Ein Repräsentantensystem $\mathcal{R}$ dieser Klassen heißt \emph{gewichtsminimal}, falls $\wt(r) = \min_{c \in C} \wt(r+c)$ für alle $r \in \mathcal{R}$.
\end{defn}

\begin{satz}
  Sei $C$ ein $[n, k]$-Code über $\F_q$, $\mathcal{R}$ ein gewichtsmin. Repräsen- tantensystem mod $C$.
  Zu $y \in \F_q^n$ sei $\mathcal{R}(y) \in \mathcal{R}$ mit $\mathcal{R}(y) + C = y + C$.
  Dann ist $D : \F_q^n \to C, \enspace y \mapsto y - \mathcal{R}(y)$ eine Decodierabbildung.
\end{satz}

\begin{samepage}

\begin{verf}[\emph{Standard-Array-Decodierung}]
  Speichere die Werte der Funktion $y \mapsto \mathcal{R}(y)$ in einer Lookup-Tabelle. \\
  Dann müssen wir zum Decodieren von~$y$ nur noch in dieser Tabelle den Wert von $\mathcal{R}(y)$ nachschlagen und $c \coloneqq y - \mathcal{R}(y)$ berechnen.
\end{verf}

% Ausgelassen: Beispiel

% §4.6 Dualer Code: Kontrollmatrix und Syndromdecodierung
\subsection{Dualer Code: Kontrollmatrix, Syndromdecod.}

\end{samepage}

\begin{bem}
  Sei $\F$ ein Körper, $n \in \N^*$.
  Das Standard-Skalarprodukt
  \[
    \scp{\blank}{\blank} : \F^n \times \F^n \to \F,
    \enspace (x, y) \mapsto {\sum}_{i=1}^n x_i y_i
  \]
  ist eine nicht-ausgeartete, symmetrische Bilinearform.
\end{bem}

% Ausgelassen: Definition des Orthogonalraums

\begin{defn}
  Sei $C$ ein $[n,k]$-Code über $\F_q$.
  Dann heißt $C^\perp$ der zu $C$ gehörende \emph{duale Code}.
\end{defn}

\begin{acht}
  Es ist $\dim(U^\perp) = n - k$, im Allgemeinen gilt aber $U \cap U^\perp \neq 0$, \zB{} ist $11011 \in \F_2^5$ senkrecht zu sich selbst.
\end{acht}

\begin{defn}
  Die Generatormatrix~$H$ von~$C^\perp$ heißt \emph{Kontrollmatrix} zu~$C$.
\end{defn}

\begin{lem}
  $\fa{x \in \F_q^n} x \in C \iff H x^T = 0$
\end{lem}

\begin{alg}[\emph{Syndromdecodierung}] \mbox{} \\
  Sei $C$ ein $[n,k]$-Code, $H \in \F_q^{n-k \times n}$ die Kontrollmatrix.
  Dann ist
  \[ \psi_H : \F_q^n \to \F_q^{n-k}, \enspace x \mapsto H x^T \]
  eine surjektive lineare Abbildung mit $\ker(\psi_H) = C$.
  \begin{itemize}
    \item Sei $c \in C$ gesendet, $y \in \F_q^n$ empfangen, etwa $y = c + e$.
    Wir als Empfänger kennen jedoch $c$ und $e$ nicht, nur $y$.
    Trotzdem können wir das \emph{Syndrom} $s \coloneqq \psi_H(y) = H c^T + H e^T = H e^T \in \F_q^{n-k}$ berechnen.
    \item Wahrscheinlich ist $e$ ein gewichtsminimaler Repräsentant von $y$.
    Sei also $\mathcal{R}$ ein minimales Repräsentantensystem. \\
    Dann ist $\psi \coloneqq \psi_H|_{\mathcal{R}} : \mathcal{R} \to \F_q^{n-k}$ bijektiv. \\
    Dann definiert $D(y) \coloneqq y - \psi^{-1}(s)$ eine Decodierabbildung.
  \end{itemize}
\end{alg}

% Vorlesung vom 29.10.2015

\begin{satz}
  Sei~$C$ ein linearer $[n, k, d]$-Code über $\F_q$, $H$~eine Kontroll- matrix zu~$C$.
  Dann gilt:
  \begin{align*}
    d &= 1 + \max \, \Set{a \in \N}{\text{je $a$ Spalten von $H$ sind linear unabhängig}} \\
    &= \min \, \Set{m \in \N}{\text{es gibt $m$ linear abhängige Spalten in $H$}}
  \end{align*}
\end{satz}

\begin{defn}
  Sei~$C$ ein linearer Code der Länge~$n$ über $\F_q$. \\
  Die \emph{Gewichtsverteilung von~$C$} ist
  $A = A_C \in \N^{\{ 0, 1, \ldots, n \}}$ mit
  \[
    A(i) \coloneqq \abs{\Set{w \in C}{\wt(w) = i}}, \quad
    0 \leq i \leq n.
  \]
\end{defn}

\begin{bem}
  Es gilt $A_0 = 1$ und $A_1 = A_2 = \ldots = A_{d-1} = 0$ für $d = d(C)$.
\end{bem}

\begin{defn}
  $A_C(Z) \coloneqq {\sum}_{i=0}^k A_i Z^k \in \C[Z]$ heißt \emph{Gewichtszählpolynom},
  \[ A_C^\homogen(X, Y) \coloneqq {\sum}_{i=0}^n A_i X^{n-i} \cdot Y^i \in \C[X, Y] \]
  heißt \emph{homogenes Gewichtszählpolynom}.
\end{defn}

\begin{samepage}

\begin{bem}
  \inlineitem{$A_C(Z) = A_C^\homogen(1, Z)$} \quad
  \inlineitem{$A_C^\homogen(X, Y) = X^n \cdot A_C(\tfrac{Y}{X})$}
\end{bem}

% §5. Hamming-Codes
\section{§5. Hamming-Codes}

\end{samepage}

% §5.1. Die Parameter eines 1-fehlerkorrigierenden perfekten linearen Codes

\begin{lem}
  Sei $C$ ein perfekter $(n, M, d)$-Code. %über $Q$ mit $q = \abs{Q}$.
  Dann ist $d$ ungerade.
\end{lem}

\begin{bem}
  Wir betrachten nun perfekte Codes $C$ mit $t=1$, also $d=3$.
  Es gilt dann $\abs{C} = \nicefrac{q^n}{1 + n(q-1)}$, es ist also $1+n(q-1)$ ein Teiler von~$q^n$.
  Beispielsweise ist für~$q \geq 2$ und~$n = q+1$ die Zahl $1 + n(q-1) = q^2$ ein Teiler von~$q^n$.
  Diese Teilbarkeit ist eine notwendige, aber nicht hinreichende Bedingung für die Existenz eines perfekten $(n, M, 3)$-Codes über $Q$ mit $q = \abs{Q}$.
  %Zum Bsp gibt es keinen perfekten Code bei $q=6$.
\end{bem}

\begin{lem}
  Seien $p, u, v \in \N$, $p \geq 2$. Dann gilt $u \divides v \iff (p^u - 1) \divides (p^v - 1)$.
\end{lem}

\begin{prop}
  Sei $C$ perfekt mit $t=1$ über $Q$, wobei $\abs{Q} = q$ eine Primzahlpotenz ist.
  Dann ist $\abs{C}$ eine $q$-Potenz.
\end{prop}

\begin{bem}
  Sei nun $q \geq 2$ eine Primzahlpotenz, $C$ ein $q$-närer perfekter $(n, M, 3)$-Code.
  Dann ist
  \[ q^k = \abs{C} = M = \nicefrac{q^n}{1 + n(q-1)} \iff n = \nicefrac{(q^{n-k} - 1)}{q - 1} \]
  Wie viele Lösungspaare $(n, k)$ gibt es bei festem $q$?
  Wir setzen $m \coloneqq n - k$.
  Dann ist $k(m) \coloneqq n - m$ und $n(m) \coloneqq \tfrac{q^m - 1}{q - 1}$.
  Die Lösungspaare hängen damit nur noch vom Parameter $m$ ab.
\end{bem}

% Vorlesung vom 3.11.2015

% 5.5
\begin{satz}
  Zu jedem $m \geq 2$ und zu jeder Primzahlpotenz $q \geq 2$ gibt es einen linearen perfekten $[\tfrac{q^m - 1}{q - 1}, \tfrac{q^m - 1}{q - 1} - m, 3]$-Code über $\F_q$.
\end{satz}

% 5.6
\begin{kor}
  Ist $q \geq 2$ eine Primzahlpotenz, so gilt
  \[
    A^\lin_q \left( \tfrac{q^m - 1}{q - 1}, 3 \right) =
    A_q \left( \tfrac{q^m - 1}{q - 1}, 3 \right) =
    q^{q^0 + \ldots + q^{m-1} - m}
    \quad
    \forall m \geq 2, m \in \N
  \]
\end{kor}

% §5.2 Konstruktion und Decodierung der binären Hamming-Codes
\subsection{Der binäre lineare Hamming-Code}

% ausgelassen: Tabelle von binären Hamming-Codes

\begin{konstr}
  Ein  \emph{bin. Hamming-Code} $\Ham_2(m)$ (ein $[n, n {-} m, 3]$- Code mit $n \coloneqq 2^m - 1$) ist geg. durch die Kontrollmatrix $H \in \F_2^{m \times n}$, welche jeden Vektor aus $\F_2^m \setminus \{ 0 \}$ in genau einer Spalte stehen hat.
\end{konstr}

\begin{alg}[Decodierung von binären Hamming-Codes]\mbox{}\\
  Angenommen, die Spalten der Kontrollmatrix $H$ codieren die Zahlen $1, \ldots, 2^m - 1$ im Binärsystem und sind geordnet.
  Sei $y \in \F_2^n$ empfangen worden.
  Falls $Hy = 0$, so wurde wsl. $y$ gesendet.
  Falls das Syndrom $Hy$ ungleich null ist, so ist vermutlich das $j$-te Bit gekippt, wobei $j$ die Zahl ist, deren Binärcodierung $Hy$ ist.
\end{alg}

% §5.3 Untersuchung des binären [7,4]-Hamming-Codes

% 5.2
\begin{prop}
  Sei $m \geq 2$, $n = 2^m - 1$ und $A \in \N^{0, 1, \ldots, \N}$ die Gewichtsverteilung des $[n, n - m, 3]$-Hamming-Codes. \\
  Dann gilt $A_{n-j} = A_j$ für alle $j = 0, 1, \ldots, 2^{m-1} - 1$.
\end{prop}

% 5.11
\begin{satz}
  Die Gewichtsverteilung des binären $[7,4]$-Hamming-Codes ist
  \[ A = (1, 0, 0, 7, 7, 0, 0, 1). \]
\end{satz}

\begin{bem}
  Sei $C = \Ham_2(3)$, $C_3 \coloneqq \Set{c \in C}{\wt(c) = 3}$.
  Für $c \in C_3$ seien $P(c) \coloneqq \Set{i = 1, \ldots, 7}{c_i = 1}$ die Positionen der in $c$ gesetzten Bits. \\
  Falls $i \in P(c)$, so sagen wir, dass $i$ auf der Geraden $c$ liege. \\
  Dies definiert die folgende geometrische Struktur:
\begin{center}
  % http://tex.stackexchange.com/a/208907
  \begin{tikzpicture}[scale=0.6]
    \draw (30:1)  -- (210:2)
          (150:1) -- (330:2)
          (270:1) -- (90:2)
          (90:2)  -- (210:2) -- (330:2) -- cycle
          (0:0)   circle (1);
    \fill (0:0)   circle(3pt)
          (30:1)  circle(3pt)
          (90:2)  circle(3pt)
          (150:1) circle(3pt)
          (210:2) circle(3pt)
          (270:1) circle(3pt)
          (330:2) circle(3pt);
    \node at (2,2) [right] {\sout{Die Heiligtümer des Todes}};
    \node at (2,1.25) [right] {\emph{Fano-Ebene}};
    \node at (2,0.5) [right] {$S_1(2,3,7)$-Blockplan};
    \node at (2,-0.25) [right] {Steinersystem};
    \node at (2,-1) [right] {Projektive Ebene $PG(2, \F_2)$};
  \end{tikzpicture}
\end{center}
  Wir bemerken, dass jede Gerade drei Punkte enthält, jeder Punkt auf drei Geraden liegt, durch je zwei verschiedene Punkte genau eine Gerade verläuft und jedes Paar von Geraden sich in genau einem Punkt schneidet.
  Die Vierecke in der Fano-Ebene sind die Komplemente von Geraden.
  Sie entsprechen den Codeworten mit Hamming-Gewicht 4.
  % ausgelassen: andere Möglichkeit, wie man aus $C$ die Fano-Ebene erhält
\end{bem}

% Vorlesung vom 5.11.2015

\begin{samepage}

% 5.14
\begin{satz}
  Die Parity-Check-Erweiterung des $[7, 4]$-Hamming-Codes ist ein binärer $[8, 4, 4]$-Code.
  Dieser ist selbst-dual und optimal. \\
  Sein homogenes Gewichtszählpolynom ist $X^8 + 14 X^4 Y^4 + Y^8$.
\end{satz}

% §5.4 q-näre lineare Hamming-Codes
\subsection{$q$-näre lineare Hamming-Codes}

\end{samepage}

\begin{konstr}
  Wir definieren auf $A \coloneqq \F_q^m \setminus \{ 0 \}$ eine Äq'relation durch
  \[ u \sim v \coloniff \ex{\lambda \in \F_q^{\times}} u = \lambda v. \]
  Wir setzen $\Proj \coloneqq PG(m-1, \F_q) \coloneqq A/{\sim}$.
  Es gilt $\abs{\Proj} = \nicefrac{q^m - 1}{q - 1} = n$. \\
  Sei $v_1, \ldots, v_n$ ein Representantensystem der Äquivalenzklassen. \\
  Dann definiert die Kontrollmatrix $H_q(m) \coloneqq (v_1 \cdots v_n)^T \in \F_q^{m \times n}$ den \emph{$q$-nären Hamming-Code} $\Ham_q(n)$.
\end{konstr}

\begin{bem}
  % Wir wählen das Representantensystem so, dass für alle $i = 1, \ldots, n$ gilt:
  % Sei $j$ minimal mit $(v_i)_j \neq 0$. Dann ist $v_i = 1$.
  Wir wählen das Representantensystem wie folgt:
  \[
    \left\{ \begin{psmallmatrix} 0 \\ \vdots \\ 0 \\ 0 \\ 1 \end{psmallmatrix} \right\} \cup
    \left\{ \begin{psmallmatrix} 0 \\ \vdots \\ 0 \\ 1 \\ * \end{psmallmatrix} \right\} \cup \ldots \cup
    \left\{ \begin{psmallmatrix} 1 \\ * \\ \vdots \\ * \\ * \end{psmallmatrix} \right\},
  \]
  also so, dass der erste Eintrag $\neq 0$ jedes Vektors eine 1 ist.
\end{bem}

% 5.16
\begin{alg}[Decodieren des $q$-nären Hamming-Codes] \mbox{} \\
  Sei $y$ empfangen mit höchstens einem Fehler.
  Berechne das Syndrom $s = H_q(m)y^T$.
  Falls $s = 0$, so ist $D(y) \coloneqq y$.
  Angenommen, $s \neq 0$.
  Sei $i$ minimal mit $s_i \neq 0$.
  Dann ist $\nicefrac{s}{s_i}$ eine Spalte von $H_q(m)$, etwa die $\ell$-te Spalte.
  Decodiere $D(y) \coloneqq y - s_i \cdot e_\ell$.
\end{alg}

% §5.5 Die Familie der Simplex-Codes
\subsection{Die Familie der Simplex-Codes}

\begin{defn}
  Sei $q \geq 2$ eine Primzahlpotenz und $m \geq 2$. \\
  Der Code $\Sim_q(m) \coloneqq \Ham_q(m)^\perp$ heißt \emph{Simplex-Code}.
\end{defn}

\begin{bem}
  $\Sim_q(m)$ ist ein $[n, m]$-Code.
\end{bem}

\begin{satz}
  $\Sim_q(m)$ ist \emph{gewichtskonstant}, \dh{} jedes vom Nullwort verschiedene Codewort hat Gewicht $q^{m-1}$.
\end{satz}

\begin{samepage}

\begin{bem}
  Also ist $A_{\Sim_q(m)}(z) = 1 + (q^m - 1) \cdot z^{q^{m-1}}$.
\end{bem}

% §5.6 Gewichtsverteilung der binären Hamming-Codes
\subsection{Gewichtsverteilung der binären Hamming-Codes}

Wir betrachten den binären Hamming-Code $C = \Ham_2(m) \subset \F_2^n$ mit $n = 2^m - 1$.

\begin{lem}
  Für $2 \leq \ell \leq n$ gilt die Rekursionsgleichung
  \[
    \binom{n}{\ell-1} = (n-\ell+2) \cdot A_{\ell-2} + A_{\ell-1} + \ell \cdot A_\ell.
  \]
\end{lem}

\begin{satz}
  Das Gewichtszählpolynom von $C$ ist
  \[
    A_C(z) = \tfrac{1}{n+1} (1+z)^n + \tfrac{n}{n+1} (1+z)^{\nicefrac{(n-1)}{2}} \cdot (1-z)^{\nicefrac{(n+1)}{2}}.
  \]
\end{satz}

% Vorlesung vom 10.11.2015

% §6. Die Golay-Codes und deren Erweiterungen
\section{§6. Golay-Codes und ihre Erweiterungen}

\begin{ziel}
  Konstruktion des binären Golay-Codes $\Golay(23)$ und seiner Erweiterung $\Golay(24)$ und des ternären Golay-Codes~$\Golay(11)$ und seiner Erweiterung~$\Golay(12)$.
  Diese vier Codes sind optimal, $\Golay(23)$ und $\Golay(11)$ sogar perfekt.
\end{ziel}

% §6.1. Übersicht über die Existenz perfekter Codes
\subsection{Existenz perfekter Codes}

\end{samepage}

\begin{prop}
  Ist $n \geq 3$ ungerade, so ist der binäre $n$-Wiederholungscode ein perfekter Code, der sogenannte \emph{triviale perfekte} Code.
\end{prop}

\begin{bem}
  Es sei $d \geq 5$ (\dh{} wir schließen \zB{} die Hamming-Codes aus), $q$ eine Primzahlpotenz.
  Durch Computer-Suche kann man zeigen:
  Für $n \leq 1000$, $\log_q(M) \leq 1000$ und $q \leq 1000$ könnte es nur perfekte lineare Codes mit folgenden Parametern geben:
  \begin{itemize}
    \item $q=2$, $n=23$, $d=7$, $M=2^{12} = 4096$ % \Golay(24)
    \item $q=2$, $n=90$, $d=5$, $M=2^{78}$
    \item $q=3$, $n=11$, $d=5$, $M=3^6=729$ % \Golay(12)
  \end{itemize}
\end{bem}

\begin{satz}
  Es gibt keinen binären $(90, 2^{78}, 5)$-Code.
\end{satz}

\begin{beweisidee}
  Angenommen, $C$ wäre ein solcher Code.
  Man zeigt, dass es für jedes $w \in \F_2^{90}$ mit $\wt(w) = 3$ genau ein $\varphi(w) \in C$ mit $\supp(w) \subset \supp(\varphi(w))$ und $\wt(\varphi(w)) = 5$ gibt.
  Somit ist die Abbildung $\varphi : X \to Y$ mit
  \begin{align*}
    X & \coloneqq \Set{w \in \F_2^{90}}{\wt(w) = 3 \text{ und } w_1 = w_2 = 1}, \\
    Y & \coloneqq \Set{c \in C}{\wt(c) = 6 \text{ und } c_1 = c_2 = 1}
  \end{align*}
  surjektiv.
  Die Fasern $\varphi^{-1}(c)$ haben je drei Elemente. \\
  Wegen $\tfrac{\abs{X}}{\abs{\varphi^{-1}(c)}} = \tfrac{88}{3} \not\in \N$ folgt der Widerspruch. \qed
\end{beweisidee}

\begin{bem}
  Tietäväinen sowie Zinov'ev und Leont'ev konnten zeigen, dass jeder $q$-näre $t$-fehlerkorrigierende perfekte Code mit Primzahlpotenz $q \geq 2$ und $t \geq 2$ entweder ein binärer $(23, 2^{12}, 7)$-Code oder ein ternärer $(11, 3^6, 5)$-Code ist.
\end{bem}

Mit einer Methode aus ihrem Beweis lässt sich ein alternativer Beweis des letzten Satzes führen:

\begin{satz}
  Sei $q$ eine Primzahlpotenz, $C$ ein perfekter $q$-närer $(n, M, 2t+1)$-Code.
  Dann hat das \emph{Lloyd-Polynom}
  \[ L_t(X) \coloneqq \sum_{j=0}^t (-1)^j \cdot (q-1)^{t-j} \cdot \binom{X-1}{j} \binom{n-1-X}{t-j} \]
  mindestens $t$ verschiedene Nullstellen in $\{ 1, \ldots, n \}$.
\end{satz}

\begin{samepage}

\begin{bsp}
  Für $n=90$, $q=2$, $t=2$ ist $L_2(X) = 2 (X^2 - 90 + 2003)$.
  Dessen Diskriminante ist $88$, also keine Quadratzahl.
  Somit besitzt $L_2(X)$ keine natürlichen Nullstellen.
\end{bsp}

% §6.3. Grundlagen über selbstduale Codes
\subsection{Selbstduale Codes}

\begin{defn}
  Ein Code $C$ heißt \emph{selbstdual}, falls $C = C^\perp$.
\end{defn}

\begin{prop}
  Sei $C$ ein binärer selbst-dualer Code (insb. linear).
  Dann gilt:
  \begin{itemize}
    \item Jedes Codewort hat ein gerades Gewicht.
    \item $\fa{c \in C} 4 \divides \wt(c) \iff$ $C$ hat eine Basis $B$ mit $\fa{b \in B} 4 \divides \wt(b)$
  \end{itemize}
\end{prop}

\begin{prop}
  Für jeden ternären selbstdualen Code $C$ gilt $\fa{c \!\in\! C\!}\! 3 \divides \wt(c)$.
\end{prop}

% §6.3. Der binäre Golay-Code und seine Erweiterung
\subsection{Der binäre Golay-Code und seine Erweiterung}

\end{samepage}

\begin{konstr}
  Sei $C_1$ der $[7, 4, 3]$-Hamming-Code und $\overline{C}_1$ dessen Parity-Check-Erweiterung.
  Die Generatormatrizen dieser Codes sind
  \[
    G_1 = \begin{pmatrix}
      1 & 1 & 0 & 1 & 0 & 0 & 0 \\
      0 & 1 & 1 & 0 & 1 & 0 & 0 \\
      0 & 0 & 1 & 1 & 0 & 1 & 0 \\
      0 & 0 & 0 & 1 & 1 & 0 & 1
    \end{pmatrix}
    \quad \text{bzw.} \quad
    \overline{G}_1 = \left( \begin{array}{c | c}
      \multirow{4}{*}{$G_1$} & 1 \\
      & 1 \\
      & 1 \\
      & 1
    \end{array} \right).
  \]
  Dann ist $\overline{C}_1$ eine selbstdualer $[8,4,4]$-Code über $\F_2$.
  
  Sei $G_2$ die Matrix $G_1$ mit Spalten in umgekehrter Reihenfolge,
  \[
    G_2 = \begin{pmatrix}
      0 & 0 & 0 & 1 & 0 & 1 & 1 \\
      0 & 0 & 1 & 0 & 1 & 1 & 0 \\
      0 & 1 & 0 & 1 & 1 & 0 & 0 \\
      1 & 0 & 1 & 1 & 0 & 0 & 0
    \end{pmatrix}
  \]
  der Code $C_2$ von $G_2$ erzeugt, $\overline{C}_2$ die Parity-Check-Erw. von $C_2$.
  Dann ist $\overline{C}_2$ ein selbstdualer $[8, 4, 4]$-Code.
\end{konstr}

\begin{satz}
  Sei $\Gamma \subset \F_2^{24}$ definiert durch
  \[ \Gamma \coloneqq \Set{(a+f, b+f, a+b+f)}{a, b \in \overline{C}_1, f \in \overline{C}_2} \]
  Dann ist $\Gamma$ ein selbst-dualer binärer $[24, 12, 8]$-Code.
\end{satz}

\begin{defn}
  $\Gamma$ wird \emph{erweiterter binärer Golay-Code $\Golay(24)$} genannt.
\end{defn}

% Vorlesung vom 12.11.2015

\begin{satz}
  Es gibt einen perfekten binären $[23, 12, 7]$-Code, den \emph{Golay-Code $\Golay(23)$}.
  Diesen erhält man aus $\Golay(24)$ durch Streichen einer Koordinate.
\end{satz}

\begin{bem}
  Umgekehrt ist $\Golay(24)$ eine Parity-Check-Erw. von $\Golay(23)$.
\end{bem}

\begin{satz}
  \begin{itemize}
    \item $A_{\Golay(24)}(z) = 1 (z^0 + z^{24}) + 759 (z^8 + z^{16}) + 2576 z^{12}$
    \item $A_{\Golay(23)}(z) = 1 (z^0 \!+\! z^{23}) + 253 (z^7 \!+\! z^{16}) + 506 (z^8 \!+\! z^{15}) + 1288 (z^{11} \!+\! z^{12})$
  \end{itemize}
\end{satz}

\begin{bem}
  $\Golay(24)$ hat eine Generatormatrizen der Form $G_1 = [E|M]$ und $G_2 = [M|E]$, wobei $M$ symmetrisch ist.
  Beide Matrizen sind gleichzeitig auch Kontrollmatrizen.
  Die Matrix $M$ hat dabei besondere Eigenschaften, die man zum Decodieren ausnutzen kann.
\end{bem}

\iffalse
  Decodierung: Schreibe $x \in \F_2^{24}$ als $x_1 | x_2$ mit $x_1, x_2 \in \F_2^{12}$.
  % Fall (a)
  Berechne Syndome $S_1 = G_1 y = G_1 e = e_1 + M e_2$ und $S_2 = G_2 y = M e_1 + e_2$.
  Es gilt:
  \begin{itemize}
    \item $\wt(S_1) \leq 3 \iff e_2 = 0 \implies S_1 = e_1 \implies e = e_1 | 0 = S_1 | 0$
    \item $\wt(S_2) \leq 3 \implies e_1 = 0 \implies S_2 = e_2 \implies e = 0 | S_2$
  \end{itemize}
  % Fall (b)
  $\wt(S_1), \wt(S_2) \geq 4$.
  Berechne $S_i = G_2 \cdot (y + (\epsilon_i|0)) = m(e_1 + \epsilon_i) + e_2$
  Beachte: $(\wt(e_1), \wt(e_2)) \in \{ (1,2), (1,1), (2,1) \}$
  $\wt(e_1) = 2 \iff \wt(S_i) \geq 4$ für alle $i = 1, \ldots, 12$
  $\wt(e_1) = 1 \iff$ es gibt genau ein $l$ mit $\wt(s_l) \leq 2$ nämlich das $l$ wodurch $e_1 = \epsilon_l$
  % Falls (b_2)
\fi

% Vorlesung vom 17.11.2015

% §6.4. Der ternäre Golay-Code und seine Erweiterung
\subsection{Der ternäre Golay-Code und seine Erweiterung}

% 6.12
\begin{satz}
  $\Golay(12) \coloneqq \Omega \subset \F_3^{12}$ sei der Code mit Generatormatrix $G=[E_6|M] \in \F_3^{6 \times 12}$, wobei
  \[
    M = \begin{pmatrix}
      1 & 1 & 1 & 1 & 1 & 0 \\
      0 & 1 & 2 & 2 & 1 & 2 \\
      1 & 0 & 1 & 2 & 2 & 2 \\
      2 & 1 & 0 & 1 & 2 & 2 \\
      2 & 2 & 1 & 0 & 1 & 2 \\
      1 & 2 & 2 & 1 & 0 & 2
    \end{pmatrix}
  \]
  Dann ist $\Omega$ ein selbstdualer $[12, 6, 6]$-Code über $\F_3$.
\end{satz}

% 6.13

\begin{satz}
  Es gibt einen $[11, 6, 5]$-Code über $\F_3$. Dieser ist perfekt und heißt \emph{ternärer Golay-Code $\Golay(11)$}.
\end{satz}

\begin{konstr}
  Streichen der letzten Koordinate von $\Golay(12)$.
\end{konstr}

% §7. Grundlagen aus der Designtheorie
\section{§7. Verbindungen mit der Designtheorie}

\begin{defn}
  Eine \emph{Inzidenzstruktur} (IS) ist ein Tupel $\Design = (V, \Blocks, I)$ mit
  \begin{itemize}
    \item einer (nichtleeren) Menge von \emph{Punkten} (oder \textit{Knoten}) $V$,
    \item einer (nichtleeren) Menge von \emph{Blöcken} (oder \textit{Geraden}) $\Blocks$ und
    \item einer \emph{Inzidenzrelation} $I \subseteq V \times \Blocks$.
  \end{itemize}
\end{defn}

\begin{nota}
  $p I B \coloniff (p, B) \in I$
\end{nota}

\begin{bem}
  Wir können die Inzidenzrelation durch eine Matrix $M \in \C^{\abs{V} \times \abs{\Blocks}}$ darstellen, welche Einträge in $\{ 0, 1 \}$ besitzt.
\end{bem}

\begin{defn}
  $\sigma(p) \coloneqq \Set{B \in \Blocks}{p I B}$,
  $\upsigma(B) \coloneqq \Set{p \in V}{p I B}$
  heißen \emph{Bahnen}.
\end{defn}

\begin{defn}
  $\Design$ heißt \emph{einfach}, falls $\upsigma$ injektiv ist.
\end{defn}

\begin{nota}
  Falls $\Design$ einfach ist, kann man $\Blocks$ als Teilmenge von~$\Pow(V)$ auffassen. Man schreibt daher
  $p \in B \coloniff p I B$.
\end{nota}

\begin{nota}
  $v \coloneqq \abs{V}$, \enspace
  $b \coloneqq \abs{\Blocks}$
\end{nota}

\begin{defn}
  Eine endl. IS $\Design = (V, \Blocks, I)$ heißt \emph{linearer Raum}, falls
  \begin{itemize}
    \item $\abs{\upsigma(B)} \geq 2$ für alle $B \in \Blocks$
    \item $\abs{\sigma(x) \cap \sigma(y)} = 1$ für alle $x \neq y \in V$.
  \end{itemize}
\end{defn}

% ausgelassen: langweiliges Bsp

\begin{satz}
  Sei $\Design$ ein lin. Raum.
  Dann gilt entweder $b = 1$ oder $b \geq v$.
\end{satz}

% Dieser Satz motiviert die Betrachtung von linearen Räumen mit $b = v$.

\begin{bsp}
  Die Inzidenzstruktur
  \[
    \begin{array}{l l}
      V = \{ x_1, \ldots, x_{v-1}, x_v \},
      & \Blocks = \{ L_1, \ldots, L_{v-1}, B \} \\
      \upsigma(L_i) = \{ x_i, x_v \},
      & \upsigma(B) = \{ x_1, \ldots, x_{v-1} \}
    \end{array}
  \]
  ist ein linearer Raum mit $b = v$.
  Dieser besitzt einen Block, der alle Pkte bis auf einen enthält und dual einen Punkt, der in allen Blöcken bis auf einen liegt.
  Solche Inzidenzstrukturen heißen \emph{entartet}.
\end{bsp}

\begin{lem}
  Für je zwei Punkte $x$, $y$ eines nicht-entarteten Raumes gibt es eine Gerade, die weder $x$ noch $y$ enthält.
\end{lem}

\begin{defn}
  Ein nicht-entarteter linearer Raum mit $v = b$ heißt eine (endliche) \emph{projektive Ebene}.
\end{defn}

\begin{satz}
  Sei $\pi = (V, G, {\in})$ eine projektive Ebene.
  Dann gilt:
  \begin{itemize}
    \item Je zwei verschiedene Geraden schneiden sich in genau einem Pkt.
    \item Es gibt ein $n \in \N$ mit $n \geq 2$, sodass:
    \begin{itemize}
      \item Jede Gerade enthält $n+1$ Punkte.
      \item Jeder Punkt liegt auf genau $n+1$ Geraden.
      \item $b = v = n^2 + n + 1$
    \end{itemize}
  \end{itemize}
\end{satz}

\begin{defn}
  $n$ heißt \emph{Ordnung} von $\pi$.
\end{defn}

\begin{bsp}
  Die Fano-Ebene ist die projektive Ebene der Ordnung 2.
\end{bsp}

% Vorlesung vom 19.11.2015

% Existenz projektiver Ebenen

\begin{fakten}
  \begin{itemize}
    \item Es gibt keine proj. Ebene der Ordnung 10.
    \item Jede \textit{heute bekannte} proj. Ebene hat Primzahlpotenzordnung.
    \item Zu jeder Primzahlpotenz $q \geq 2$ ex. eine proj. Ebene der Ord. $q$.
    %\item Alle weiteren $n$, die ausgeschlossen sind, entsprechen dem Resultat von Bruck und Roger
    \item Es ist nicht bekannt, ob eine proj. Ebene mit $n = 12$ existiert.
  \end{itemize}
\end{fakten}

\begin{satz}[\emph{Bruck, Ryser}]
  Sei $n \geq 2$.
  Angenommen, $n \equiv 1 \bmod 4$ oder $n \equiv 2 \bmod 4$.
  Sei $n = p_1^{a_1} \cdot \ldots \cdot p_l^{a_l}$ eine Primfaktorzerlegung von $n$.
  Gibt es ein $i$ mit $p_i \equiv 3 \bmod 4$ und $a_i$ ungerade, so existiert keine projektive Ebene der Ordnung $n$.
\end{satz}

\begin{kor}
  Ist $n \equiv 6 \bmod 8$, so gibt es keine proj. Ebene der Ordung~$n$.
\end{kor}

\begin{satz}
  Sei $q \geq 2$ eine Primzahlpotenz.
  Dann gibt es eine projektive Ebene der Ordnung $q$.
\end{satz}

\begin{konstr}
  $\begin{array}[t]{r l}
    \text{Punkte } p & \coloneqq \text{die ein-dim. Teilräume von $\F_q^3$,} \\
    \text{Geraden } \Blocks & \coloneqq \text{die zwei-dim. Teilräume von $\F_q^3$,} \\
    p \in B & \!\!\!\coloniff p \subseteq B.
  \end{array}$
\end{konstr}

\begin{defn}
  Sei $\Design = (V, \Blocks, I)$ eine endl. Inzidenzstruktur.
  Es gebe $r, k \in \N$ mit $r \geq 2$ und $k \geq 2$ mit $\abs{\sigma(x)} = r$ für alle $x \in V$ und $\abs{\upsigma(B)} = k$ für alle $B \in \Blocks$.
  Dann heißt $\Design$ eine \emph{taktische Konfiguration}.
\end{defn}

\begin{bem}
  Doppeltes Zählen der Inzidenzen $I$ ergibt: \enspace
  $v \cdot r = \abs{I} = b \cdot k$.
\end{bem}

\begin{defn}
  Sei $\Design = (V, \Blocks, I)$ eine endliche IS.
  Es gebe $k, t, \lambda \in \N$ mit:
  \begin{itemize}
    \miniitem{0.4 \linewidth}{$v = \abs{V} \geq k \geq t$,}
    \miniitem{0.4 \linewidth}{$\abs{\upsigma(B)} = k$ für alle $B \in \Blocks$,}
    \item Zu jeder $t$-elementigen Teilmenge $T \subseteq V$ gibt es genau $\lambda$ Blöcke aus $\Blocks$ mit $T \subseteq \upsigma(B)$.
  \end{itemize}
  Dann heißt $\Design$ ein \emph{$t$-$(v, k, \lambda)$-Blockplan}, \emph{$S_\lambda(t, k, v)$-Steinersystem} oder \emph{$t$-Design}.
\end{defn}

\begin{bsp}
  Eine proj. Ebene der Ordnung $n$ ist ein $S_1(2, n + 1, n^2 + n + 1)$.
\end{bsp}

\begin{bsp}
  Sei $V$ eine Menge, $v \geq 2$, $t \leq k$.
  Sei $\Blocks \coloneqq \Set{B \subseteq V}{\abs{B} = k}$.
  Dann ist $(V, \Blocks, {\in})$ ein $t$-Design mit $\lambda = \binom{v - t}{k - t}$.
\end{bsp}

\begin{prop}
  Sei $\Design = (V, \Blocks, I)$ ein $S_\lambda(t, k, v)$.
  Ist $s \in \N$ mit $s \leq t$, dann ist~$\Design$ auch ein $s$-Design und zwar mit $\lambda_s = \frac{\lambda \cdot \binom{v - s}{t-s}}{\binom{k-s}{t-s}}$.
\end{prop}

\begin{kor}
  Ist $t \geq 1$, so ist $\Design$ eine taktische Konf. mit \textit{Replikationszahl}
  \[ r = \lambda_1 = \frac{\lambda \binom{v-1}{t-1}}{\binom{k-1}{t-1}} \]
  Die Anzahl der Blöcke in einem Blockplan ist
  \[ b = \lambda_0 = \frac{\lambda \binom{v}{t}}{\binom{k}{t}}. \]
\end{kor}

% Bem: für $\lambda=1$, $t \geq 4$ kennt man $S_1(4,5,11)$, $S_1(4,7,23)$, $S_1(5,6,12)$, $S_1(5,8,24)$

\begin{satz}
  Sei $C$ ein bin. perfekter $(n, M, d)$-Code wobei $d = 2t+1$.
  Setze
  \[
    V \coloneqq \{ 1, \ldots, n \}, \quad
    \Blocks \coloneqq \Set{\supp(c)}{c \in C \text{ mit } \wt(c) = d}.
  \]
  Dann ist $(V, \Blocks, {\in})$ ein $S_1(\tau, d, n)$ wobei $\tau \coloneqq t+1$.
\end{satz}

\begin{bspe}
  \begin{itemize}
    \item Ein $[2^m-1, 2^m-1-m, 3]$-Hamming-Code über~$\F_2$ liefert ein $S_1(2, 3, 2^m-1)$-Steinersystem.
    % ~> $\tau = 1+t = t+1 = 2$, $k=3$, $v = 2^m-1$.
    % Vorlesung vom 24.11.2015
    \item $\Golay(23)$ ist ein perfekter, binärer $[23, 12, 7]$-Code $\implies$ $\exists$ $S_1(4, 7, 23)$.
    \item Angenommen, es gibt einen bin. $(90, 2^{78}, 5)$-Code (also perfekt).
    Dann $\exists$ ein $S_1(3, 5, 90)$, etwa $\Design$.
    Dann ist $\Design$ ein $S_{\lambda_2}(2, 5, 90)$ mit
    \[ \lambda_2 = \frac{\lambda \binom{v-2}{t-2}}{\binom{k-2}{t-2}} = \frac{1 \binom{88}{1}}{\binom{3}{1}} = \tfrac{88}{3} \not\in \N. \]
  \end{itemize}
\end{bspe}

\begin{bem}
  Sei $C$ ein binärer perfekter $(n, M, d)$-Code, $\overline{C}$ dessen Parity-Check-Erweiterung (ein $(n+1, M, d+1)$-Code).
  Dann gibt es ein $S(t+2, d+1, n+1)$.
  Konstruktion:
  \[
    \Blocks = \Set{\supp(\overline{c})}{\overline{c} \in \overline{C}, \wt(\overline{c}) = d+1}, \quad
    V = \{ 1, \ldots, n+1 \}
  \]
  Insbesondere $\Golay(23) \rightsquigarrow \Golay(24)$ $\implies$ $\exists$ $S_1(5, 8, 24)$
\end{bem}

\begin{satz}
  Es gibt ein $S_1(5, 6, 12)$
\end{satz}

\begin{konstr}
  Sei $\Golay(12)$ der ternäre $[12,6,6]$-Code.
  \[
    V = \{ 1, \ldots, 12 \}, \quad
    \Blocks = \Set{\supp(c)}{c \in \Golay(12), \, \wt(c) = 6}
  \]
\end{konstr}

\begin{satz}
  Es gibt ein $S_1(4, 5, 11)$
\end{satz}

% §7.5

\begin{defn}
  Sei $n \geq 2$.
  Ein $S_1(2, n, n^2)$ heißt \emph{affine Ebene} der Ord. $n$.
\end{defn}

\begin{satz}
  $\exists \, S_1(2, n, n^2) \iff \exists \, S_1(2, n+1, n^2 + n + 1)$
\end{satz}

\begin{konstr}
  \begin{itemize}
    \item Sei zunächst $(V, \Geraden, \in)$ eine projektive Ebene der Ord. $n$.
    Wähle eine Gerade $L \in \Geraden$.
    Dann ist
    \[ \alpha \coloneqq (V', \Geraden', \in) \coloneqq (V \setminus L, \Geraden \setminus \{ L \}, \in) \]
    eine affine Ebene der Ordnung $n$. \\
    \item Sei umgekehrt $(W, \mathcal{H}, \in)$ eine aff. Ebene der Ord. $n$.
    Dann def.
    \[ L \text{ ist parallel zu } K \coloniff L \parallel K \coloniff (L = K) \vee (L \cap K = \emptyset) \]
    eine Äquivalenzrelation auf $\mathcal{H}$.
    Dann ist
    \[
      (V, \Geraden, \in)
      \enspace \text{mit} \enspace
      V \coloneqq W \,\amalg\, (\mathcal{H}/{\parallel}), \enspace
      \Geraden \coloneqq \Set{K \,\amalg\, \{ [K] \}}{K \in \mathcal{H}} \,\amalg\, \{ \mathcal{H}/{\parallel} \}
    \]
    eine projektive Ebene der Ordnung $n$.
  \end{itemize}
\end{konstr}

\begin{defn}
  $\Design$ sei ein $S_\lambda(t, k, v)$, wobei $t \geq 2$.
  Sei $x \in V$.
  Dann heißt
  %Definiere $\Design' \coloneqq (V', \Blocks', \in)$, wobei $V' \coloneqq V \setminus \{ x \}$, $\Blocks' \coloneqq \Set{B \setminus \{ x \}}{B \in \Blocks, x \in B}$
  \[
    \Design' \coloneqq (V', \Blocks', \in),
    \enspace \text{wobei } V' \coloneqq V \setminus \{ x \},
    \quad \Blocks' \coloneqq \Set{B \setminus \{ x \}}{B \in \Blocks, x \in B}
  \]
  das nach $x$ \emph{abgeleitete Design}.
  Es ist $\Design'$ ein $S_\lambda(t-1, k-1, v-1)$.
\end{defn}

\begin{bem}
  Wie in Analysis gilt: Ableiten ist leicht, "`Integrieren"' schwer.
\end{bem}

\begin{bsp}
  $S_1(5,6,12)'''' = S_1(4,5,11)''' = S_1(3,4,10)'' = S_1(2,3,9)' = S_1(1,2,8)$
\end{bsp}

% Vorlesung vom 26.11.2015

% 7.7 Elementares über symmetrische Blockpläne

\begin{lem}[\emph{Fisher}]
  Für jeden $2$-$(v,k,\lambda)$-Blockplan mit $v \!>\! k$ gilt $b \geq v$. \\
  Falls $v = b > k$, so ist die Inzidenzmatrix invertierbar.
\end{lem}

\begin{defn}
  Ein $2$-$(v, k, \lambda)$-Blockplan mit $v = b > k$ heißt \emph{symmetrisch} mit \emph{Ordnung} $n \coloneqq k - \lambda$.
\end{defn}

\begin{acht}
  "`symmetrisch"' bezieht sich nicht auf die Inzidenzmatrix!
\end{acht}

\begin{bsp}
  Endliche projektive Ebenen sind symmetrisch (mit $\lambda = 1$).
\end{bsp}

\begin{satz}[\emph{Ryser}]
  Sei $\Design = (V, \Blocks, I)$ ein symm. $2$-$(v, k, \lambda)$-Blockplan.
  Dann gilt $r = k$ und je zwei verschiedene Blöcke haben genau $\lambda$ gemeinsame Punkte.
\end{satz}

\begin{bem}
  Somit ist der duale Blockplan zu $\Design$, der durch Vertauschen der Rollen von Blöcken und Punkten entsteht, ebenfalls ein $2$-$(v = b, k = r, \lambda)$-Blockplan.
  Darauf bezieht sich das "`symmetrisch"'.
\end{bem}

% Bruck, Ryser, Chowla
\begin{satz}
  Sei $\Design$ ein symm. $2$-$(v, k, \lambda)$-Blockplan der Ordung $n$.
  \begin{itemize}
    \item Ist $n$ gerade, so ist $n$ eine Quadratzahl.
    \item Ist $v$ ungerade, so gibt es ein ganzzahliges Tripel $z = (z_1, z_2, z_3) \neq (0, 0, 0)$ mit
    \[ z_1^2 = n \cdot z_2^2 + (-1)^{\nicefrac{(v-1)}{2}} \lambda \cdot z_3^2. \]
  \end{itemize}
\end{satz}

\begin{bem}
  Der Satz von Bruck und Ryser ist ein Korollar hiervon.
\end{bem}

\begin{bem}
  Sei $\Design = (V, \Blocks, I)$ ein symm. $2$-$(v, k, \lambda)$-Blockplan.
  Das zu $\Design$ \emph{komplementäre Design} ist $\Design^c \coloneqq (V, \Blocks, I^c)$, $p I^c B \!\!\coloniff\!\! \neg (p I B)$.
  Dann ist $\Design^c$ ein $2$-$(v, v-k, \lambda^c)$-Blockplan mit $\lambda^c = v - 2n - \lambda$.
\end{bem}

\begin{satz}
  Sei $\Design$ ein symmetrischer $2$-$(v, k, \lambda)$-Blockplan der Ordnung $n$ mit $1 < k < v - 1$.
  Dann gilt \enspace
  $4n - 1 \leq v \leq n^2 + n + 1$.
  Das Polynom $X^2 + (2n - v) X + (n-1) n = 0$ besitzt die Nullstellen $\lambda$ und $\lambda^c$.
\end{satz}

\begin{bem}
  Projektive Ebenen besitzen also die maximale Anzahl an Punkten unter allen symmetrischen Blockplänen der Ordnung $n$. \\
  Blockpläne, deren Punktanzahl die untere Schranke erfüllt, besitzen auch eine eigene Bezeichnung:
\end{bem}

\begin{defn}
  $2$-$(4n{-}1, 2n{-}1, n{-}1)$-Designs heißen \emph{Hadamard-Designs}.
\end{defn}

% Vorlesung vom 1.12.2015

% §8. Reed-Muller-Codes
\section{§8. Reed-Muller-Codes}

% Mars-Sonde "Mariner-9": Informationsraum $\F_2^6$, Anforderung an Code: $d = 16$
% $A_q(n, d) = \max \Set{M}{\text{es gibt einen $q$-nären $(n, M, d)$-Code}}$
% $q = 2$, $\min \Set{n \in \N}{A_2(n, 16) \geq 64} = 32$
% In der Tat: $A_2(32, 16) = 64$, sogar $A_2^\lin(32, 16) = 64$.
% Es gibt also einen $[32, 6, 16]$-Code über $\F_2$.
% Informationsrate dieses Codes: $\tfrac{6}{32} = 18,75$
% Zum Vergleich die Informationsrate des Wiederholungscodes $[6 \cdot 16, 6, 16] über $\F_2$: $\tfrac{6}{6 \cdot 16} = 6,25$

% §8.2 Die Plotkin-Schranke
\subsection{Die Plotkin-Schranke}

\begin{satz}[\emph{Plotkin-Schranke}]
  Sei $q \geq 2$, $d > \tfrac{q-1}{q} \cdot n$.
  Dann gilt
  \[ A_q(n, d) \leq \tfrac{d}{d - \tfrac{q-1}{q} \cdot n}. \]
\end{satz}

\begin{lem}
  Sei $n \geq 2$, $1 \leq d < n$.
  Dann: $A_2(n, d) \leq 2 \cdot A_2(n-1, d)$
\end{lem}

\begin{satz}
  Für $l \geq 1$ gilt $A_2(4 l, 2 l) \leq 8 l$.
\end{satz}

\iffalse
\begin{bsp}
  Für $l=8$ gilt $A_2(32, 16) \leq 64$.
\end{bsp}

\begin{bsp}
  %Sei $m = 2$.
  $G_2 \coloneqq \begin{psmallmatrix}
    0 & 0 & 1 & 1 \\
    0 & 1 & 0 & 1 \\
    1 & 1 & 1 & 1
  \end{psmallmatrix}$
  erzeugt einen $[4, 3, 2]$-Code $C_2$ über $\F_2$.
\end{bsp}

\begin{bsp}
  %Sei $m = 3$.
  Die Parity-Check-Erw. von $\Ham_2(3)$ ist ein $[8, 4, 4]$-Code $C_3$ über $\F_2$.
\end{bsp}

\begin{kor}
  $A_2(4, 2) = A_2^\lin(4, 2) = 8$, \enspace
  $A_2(8, 4) = A_2^\lin(8, 4) = 16$
\end{kor}
\fi

\begin{satz}
  Für $m \geq 1$ gilt $A_2^\lin(2^m, 2^{m-1}) = A_2(2^m, 2^{m-1}) = 2^{m+1}$, \dh{} es existiert ein $[2^m, m+1, 2^{m-1}]$-Code.
\end{satz}

\begin{konstr}
  Man definiert rekursiv Generatormatrizen durch
  \[
    G_{m+1} = \left( \begin{array}{c c c | c c c}
      0 & \cdots & 0 & 1 & \cdots & 1 \\ \hline
      \multicolumn{3}{c}{G_m} & \multicolumn{3}{c}{G_m}
    \end{array} \right), \quad
    G_1 \coloneqq \begin{pmatrix}
      0 & 1 \\
      1 & 1
    \end{pmatrix}
  \]
\end{konstr}

% §8.3 Die Algebra der Booleschen Funktionen
\subsection{Die Algebra der Booleschen Funktionen}

% Sei $M$ eine Menge, $\F_2^M = $ der $\F_2$-Vektorraum aller Abb. von $M$ nach $\F_2$.

\begin{defn}
  Sei $m \geq 1$.
  Eine \emph{Boolesche Funktion} in $m$ Variablen ist eine Abbildung von $\F_2^m$ nach $\F_2$.
\end{defn}

\begin{nota}
  $\mathcal{B}_m \coloneqq \F_2^{\F_2^m} = $ Algebra der Booleschen Fktn in $m$ Var.
\end{nota}

\begin{defn}
  % Führe Variablen $x_1, \ldots, x_m$ ein.
  % Betrachte die Polynomalgebra über $\F_2$ in diesen Variablen, $\F_2[x_1, \ldots, x_m]$.
  %Die Abbildung
  $
    \Gamma : \F_2[x_1, \ldots, x_m] \to \mathcal{B}_m, \quad
    f(x) \mapsto (\overline{f} : v \mapsto f(v_1, \ldots, v_m))
  $
\end{defn}

% Vorlesung vom 3.12.2015

\begin{satz}
  $\Gamma$ ist ein surjektiver Algebra-Homomorphismus mit
  \[ \ker \Gamma = \langle x_1^2 + x_1, \ldots, x_m^2 + x_m \rangle \subset \F_2[x_1, \ldots, x_m] = \F_2[\vec{x}]. \]
\end{satz}

\begin{kor}
  $
    \arraycolsep=2pt
    \begin{array}[t]{r c l}
      \mathcal{B}_m & \cong & \F_2[\vec{x}] / \langle x_1^2 + x_1, \ldots, x_m^2 + x_m \rangle \\
      & \cong & \F_2[\vec{x}]_{\text{red}} \coloneqq \text{span} \{ \text{Monome } x^\alpha \text{ mit } \alpha \leq (1, \nldots, 1) \}
    \end{array}
  $
\end{kor}

\begin{nota}
  $x_I \coloneqq \prod_{i \in I} x_i$ für $I \subset \{ 1, \ldots, m \}$
\end{nota}

% §8.4 Die binären Reed-Muller-Codes
\subsection{Die binären Reed-Muller-Codes}

\begin{defn}
  Der (binäre) \emph{Reed-Muller-Code} zu $(r, m)$ ist
  \[
    \RM(r, m) \coloneqq \Gamma(X(r, m))
    \enspace \text{mit }
    X(r, m) \coloneqq \spann \Set{x_I}{I \subset \{ 1, \nldots, m \}, \abs{I} \leq r}
  \]
\end{defn}

\begin{bspe}
  \begin{itemize}
    \item $\RM(0, m) = \{ 0 \cdots 0, 1 \cdots 1 \} = (2^m)\text{-Wiederholungscode}$
    \miniitem{0.4 \linewidth}{$\RM(-1, m) \coloneqq \{ 0 \cdots 0 \}$}
    \miniitem{0.4 \linewidth}{$\RM(m, m) \coloneqq \mathcal{B}_m$}
  \end{itemize}
\end{bspe}

\begin{bem}
  \begin{itemize}
    \item 
    $
      \arraycolsep=3pt
      \begin{array}[t]{c c c c c c c}
        \RM(-1, m) & \subseteq & \RM(0, m) & \subseteq & \RM(1, m) & \subseteq & \cdots \\
        \perp && \perp && \perp \\
        \RM(m, m) & \supseteq & \RM(m-1, m) & \supseteq & \RM(m-2, m) & \supseteq & \cdots
      \end{array}
    $
    \item $\dim \RM(r, m) = \sum_{j=0}^r \binom{m}{j}$
  \end{itemize}
\end{bem}

\begin{satz}
  $\RM(1, m)$ hat Minimalgewicht $2^{m-1}$.
  Gewichtsverteilung: $A_0 = 1$, $A_{2^m} = 1$, $A_{2^{m-1}} = 2^{m+1} - 2$, $A_i = 0$ für alle anderen $i$.
\end{satz}

% $\RM(1, m)$ entspricht dem Vektorraum aller affinen Linearformen in $m$ Variablen

\begin{bem}
  %$\Ham_2(m) : [2^m - 1, 2^m - 1 - m, 3]$
  %$\Sim_2(m) = \Ham_2(m)^\perp : [2^m - 1, m, 2^{m-1}]$
  %$\widehat{\Sim_2(m)} : [2^m, m, 2^{m-1}]$
  %Es gilt
  $\RM(1, m) = \Gamma(\spann \{ 1 \}) \oplus \widehat{\Sim_2(m)}$
\end{bem}

\begin{satz}
  $\RM(r, m)^\perp = \RM(m - r - r, m)$ für alle $r$
\end{satz}

\begin{kor}
  Ist $m$ ungerade, so ist $\RM(\tfrac{m-1}{2}, m)$ selbstdual.
\end{kor}

% Vorlesung vom 8.12.2015

\begin{bsp}
  $\RM(1, 3) = \PCE{\Ham_2}(3)$ ist ein selbst-dualer $[2^3, 3 + 1, 2^2]$-Code.
\end{bsp}

\begin{lem}
  $\PCE{\Ham_2(m)} = \RM(m-2, m)$
\end{lem}

\begin{satz}
  Sei $0 \leq r \leq m \geq 1$. Der binäre Reed-Muller-Code $\RM(r, m)$ hat das Minimalgewicht $2^{m-r}$
\end{satz}

\begin{kor}
   $\RM(r, m)$ ist ein $[2^m, \sum_{i=0}^r \binom{m}{i}, 2^{m-r}]$-Code
\end{kor}

% §8.5 Hadamard-Matrizen und Hadamard-Designs
\subsection{Hadamard-Matrizen und Hadamard-Designs}

\begin{satz}
  Für $A \in \R^{n \times n}$ mit $\abs{A_{ij}} \leq 1$ gilt $\abs{\det(A)} \leq \sqrt{n^n}$. \\
  Gleichheit liegt genau dann vor, wenn $\abs{A_{ij}} = 1$ für alle $i$, $j$ und wenn $A A^T = n E_n$.
\end{satz}

\begin{defn}
  Eine Matrix $H \in \R^{n \times n}$ mit $H_{ij} \in \{ \pm 1 \}$ heißt \emph{Hadamard-Matrix} der Ordnung $n$, falls $H H^T = n E_n$.
\end{defn}

\begin{bsp}
  $H_2 = \begin{psmallmatrix}
    1 & 1 \\
    1 & -1
  \end{psmallmatrix}$
  ist eine Hadamard-Matrix.
\end{bsp}

\begin{satz}
  Ist $H \!\in\! \R^{n \times n}$ eine Hadamard-Matrix, so gilt $n \!\in\! \{ 1, 2 \} \cup 4 \N$.
\end{satz}

\begin{satz}
  Sei $l \geq 1$ und $H$ eine Hadamard-Matrix der Ordnung $4 l$.
  %Dann gilt:
  \begin{itemize}
    \item Es gibt einen symmetrischen $S_{l-1}(2, 2l - 1, 4l - 1)$-Blockplan.
    \item Es gibt einen binären $(4l, 8l, 2l)$-Code. \\
    Dieser ist optimal, also $A_2(4l, 2l) = 8l$.
  \end{itemize}
\end{satz}

\begin{konstr}
  \begin{itemize}
    \item Wir können davon ausgehen, dass die erste Zeile und Spalte von $H$ nur Einsen enthalten (durch Multiplizieren mit $-1$).
    Durch Streichen der ersten Zeile und Spalte erhalten wir aus $H$ eine Matrix $M \in \R^{(4l - 1) \times (4l - 1)}$.
    In $M$ ersetzen wir $-1$ durch $0$ und bekommen so die Inzidenzmatrix des gesuchten Blockplans.
    (Diese Konstruktion lässt sich umkehren.)
    \item Der Code besteht aus den Zeilen von $H$ und $-H$ (wobei wir $\{ 0, 1 \} \leftrightarrow \{ -1, 1 \}$ anwenden).
  \end{itemize}
\end{konstr}

\begin{lem}[\emph{Produktkonstruktion}]
  Das Kronecker-Produkt $H \otimes L$ von Hadamard-Matrizen $H$ und $L$ der Ordnung $n$ bzw. $m$ ist selbst eine Hadamard-Matrix der Ordnung $n \cdot m$.
\end{lem}

% Ausgelassen: Beispiel

% Vorlesung vom 10.12.2015

\begin{satz}[\emph{Paley}]
  Sei $p > 2$ prim, $q = p^k$.
  Sei $\epsilon \in \N$ sodass $4 \divides 2^\epsilon \cdot (q + 1)$.
  Dann existiert eine Hadamard-Matrix der Ord. $n = 2^\epsilon \cdot (q+1)$.
\end{satz}

\begin{konstr}
  Der \emph{quadratische Charakter} von $\F_q$ ist die Abbildung
  \[
    \psi : \F_q \to \C, \quad
    x \mapsto \begin{cases}
      0 & \text{falls } x = 0, \\
      1 & \text{falls } \ex{y \in \F_q \setminus \{ 0 \}} x = y^2, \\
      -1 & \text{sonst.}
    \end{cases}
  \]
  \begin{itemize}
    \item Falls $q \equiv 3 \bmod{4}$: Dann definiert
    \[
      M_{xy} \coloneqq \begin{cases}
        \psi(x - y) & \text{falls } x \neq y \\
        -1 & \text{falls } x = y
      \end{cases}
    \]
    eine Matrix $M \in \{ \pm 1 \}^{\F_q \times \F_q}$.
    Durch Hinzufügen einer $1$-Spalte und $1$-Zeile erhalten wir eine Hadamard-Matrix $H \in \R^{q+1 \times q+1}$.
    Durch die Produkt- konstruktion mit $H_2$ erhält man die gesuchten Matrizen.
    \item Falls $q \equiv 1 \bmod{1}$:
    Dann ist $2 (q+1)$ durch $4$ teilbar.
    Setze $\F_q' \coloneqq \F_q \cup \{ \infty \}$.
    Wir definieren $M \in \{ -1, 0, 1 \}^{\F_q' \times \F_q'}$ durch
    \[
      M_{xy} \coloneqq \begin{cases}
        1 & \text{falls } \infty \in \{ x, y \} \neq \{ \infty \}, \\
        0 & \text{falls } x = y = \infty, \\
        \psi(x - y) & \text{sonst.}
      \end{cases}
    \]
    Weiter sei \enspace
    $
      A = H_2 = \begin{psmallmatrix}
        1 & 1 \\ 1 & -1
      \end{psmallmatrix}, \enspace
      B = \begin{psmallmatrix}
        1 & -1 \\ -1 & -1
      \end{psmallmatrix}.
    $ \\[2pt]
    Schließlich bestehe $H = (H_{xy})_{x, y \in \F_q'}$ aus den $(2 \times 2)$-Blöcken
    \[
      H_{xy} \coloneqq \begin{cases}
        B & \text{falls } M_{xy} = 0, \\
        A & \text{falls } M_{xy} = 1, \\
        -A & \text{falls } M_{xy} = -1.
      \end{cases}
    \]
    Dann ist $H$ eine Hadamard-Matrix der Größe $2 (q + 1)$.
    Durch Produktbildung mit $H_2$ erhält man Hadamard-Matrizen der gesuchten Ordung.
  \end{itemize}
\end{konstr}

% §8.6 Zur Decodierung der binären Reed-Muller-Codes erster Ordnung

\begin{prop}
  Sei $H \in \{ 1, -1 \}^{\F_2^m \times \F_2^m}$ definiert durch $H_{uv} \coloneqq (-1)^{\scp{u}{v}}$ für alle $u, v \in \F_2^m$.
  Dann ist $H$ eine Hadamard-Matrix der Ordnung $2^m$.
\end{prop}

% Vorlesung vom 15.12.2015

\begin{defn}
  Sei $F \in \R^{\F_2^m} = \text{Abbildungen } \F_2^m \to \R$.
  Die \emph{Hadamard-Transformierte} von $F$ ist
  \[
    \hat{F} : \F_2^m \to \R, \enspace
    u \mapsto \sum_{v \in \F_2^m} (-1)^{\scp{u}{v}} F(v).
  \]
  Die \emph{inverse Hadamard-Transformation} ist gegeben durch
  \[
    G \in \R^{\F_2^m} \mapsto G^* \in \R^{\F_2^m}
    \enspace \text{mit} \enspace
    G^*(u) = \tfrac{1}{2^m} \cdot \sum_{v \in \F_2^m} (-1)^{\scp{u}{v}} G(v).
  \]
\end{defn}

\begin{nota}
  Für $\beta \in \mathcal{B}_m$, also eine boolsche Funktion in $m$ Variablen, sei $B_\beta$ definiert durch $B_\beta(u) \coloneqq (-1)^{\beta(u)}$.
\end{nota}

% Bem: Die Hadamard-Transformierte von $B_\beta$ ist
% $\hat{B}_\beta$ mit $\hat{B}_\beta(u) = \sum_{v \in \F_2^m} (-1)^{\scp{u}{v} + \beta(v)}$.

\begin{align*}
  \RM(1, m) & \widehat{=} \spann \{ 1, x_1, \ldots, x_m \} \\
  & = \spann \{ 1 \} \oplus \underbrace{\spann \{ x_1, \ldots, x_m \}}_{O(1, m) \coloneqq} = O(1, m) \sqcup [1 + O(1, m)]
\end{align*}

Sei $\phi \in \RM(1, m)$ gesendet, $\beta \in \mathcal{B}_m$ empfangen.
Gesucht: $\gamma \in \RM(1, m)$ mit $d(\gamma, \beta)$ minimal.

\begin{satz}
  Sei $\beta \in \mathcal{B}_m$, $\gamma \in O(1, m)$; schreibe $\gamma = \lambda_1 x_1 + \ldots + \lambda_m x_m$.
  %Dann gilt
  \begin{itemize}
    \miniitem{0.48 \linewidth}{$d(\beta, \gamma) = \tfrac{1}{2} (2^m - \hat{B}_\beta(\lambda))$}
    \miniitem{0.48 \linewidth}{$d(\beta, 1+\gamma) = \tfrac{1}{2} (2^m + \hat{B}_\beta(\lambda))$}
  \end{itemize}
\end{satz}

Zur Decodierung von $\RM(1, m)$: Dies ist ein $[2^m, 1+m, 2^{m-1}]$-Code, also $t = \tfrac{2^{m-1} - 1}{2} < 2^{m-2}$.
Angenommen, $\phi \in \RM(1, m)$ ist gesendet, es sind höchstens $t$ Fehler aufgetreten, $\beta$ empfangen.
Dann gilt $d(\phi, \beta) \leq t$ und
\begin{itemize}
  \item Falls $\phi \in O(1, m)$: $\phi = \sum_{i=1}^m \alpha_i x_i$, $\hat{B}_\beta(\alpha) = 2^m - 2 \cdot d(\beta, \phi) > 0$.
  \item Falls $\phi \in 1 + O(1, m)$: $\phi = 1 + \sum_{i=1}^m \alpha_i x_i$.
\end{itemize}

Beachte: $\min \{ d(\beta, \gamma), d(\beta, 1 + \gamma) \} = \tfrac{1}{2} \cdot (2^m - \abs{\hat{B}_\beta(\lambda)})$ für $\gamma \in O(1, m)$.
Gesucht ist ein $\gamma$ mit $\tfrac{1}{2} (2^m - \abs{\hat{B}_\beta(\lambda)})$ minimal $\iff$ $\abs{\hat{B}_\beta(\lambda)}$ maximal.

(Beachte: $\hat{B}_\beta = H \cdot B_\beta$ mit $H = H_2 \otimes \ldots \otimes H_2$ ($m$-mal) mit schneller Hadamard-Transformation berechenbar.)

$\hat{B}_\beta$ liegt vor, das heißt $\hat{B}_\beta(\lambda)$ ist bekannt für alle $\lambda \in \F_2^m$.

Suche nun ein $\lambda \in \F_2^m$ mit $\abs{\hat{B}_\beta(\lambda)}$ ist minimal.

\begin{itemize}
  \item Annahme, $\hat{B}_\beta(\lambda) > 0$.
  Decodiere $\beta$ zu $\sum_{i=1}^m \lambda_i x_i \in o(1, m)$.
  \item Annahme, $\hat{B}_\beta(\lambda) < 0$. Decodiere $\beta$ zu $1 + \sum_{i=1}^m \lambda_i x_i \in 1 + o(1, m)$.
\end{itemize}

% ausgelassen: Beispiel

% §9. Die Gewichtsverteilung von dualen Codes
\section{§9. Die Gewichtsvert. von dualen Codes}

% §9.1 Die MacWilliams-Transformation

\begin{defn}
  Betrachte einen Code $C \subseteq \F_q^n$.
  Für $j = 0, \ldots, n$ sei
  \[
    \Delta_C(j) \coloneqq \tfrac{1}{\abs{C}} \abs{\Set{(x, y) \in C \times C}{d(x, y) = j}}.
  \]
  $\Delta_C \in \Q^{\{0, \ldots, n\}}$ heißt \emph{Distanzverteilung} von $C$.
\end{defn}

\begin{prop}
  Ist speziell $C$ ein $\F_q$-linearer Code, dann gilt: $\Delta_C = A_C = $ Gewichtsverteilung von $C$.
\end{prop}

% §9.2 Additive Charaktere

\begin{defn}
  Ein \emph{additiver Character} von $\F_q$ ist eine Gruppen-Homomorphismus von $(\F_q, +, 0)$ nach $(\C^*, \cdot, 1)$.
\end{defn}

\begin{nota}
  $\hat{\F_q} \coloneqq $ Menge aller additiven Charactere
\end{nota}

\begin{bem}
  $\hat{\F_q}$ ist eine Gruppe mit
  \[
    [\chi \cdot \psi](x) \coloneqq \chi(x) \cdot \psi(x), \quad
    \chi_0(x) \coloneqq 1.
  \]
  Es gilt $(\hat{\F_q}, \cdot, \chi_0) \cong (\F_q, +, 0)$.
\end{bem}

% Vorlesung vom 17.12.2015

Für $q = p$ prim ist

\[
  \gamma : (\F_p = \Z_p, +, 0) \to (\C^*, \cdot, 1), \quad
  z \mapsto \exp(\tfrac{2 \pi z i}{p})
\]

ein additiver Charakter.

Für $q = p^k$, $k \geq 2$ verwenden wir die Spurabbildung
$\trace : \F_q \to \F_p, \enspace x \mapsto \sum_{j=0}^{k-1} x^{p^j}$.
(Dies ist eine nicht-triviale Linearform.)
Dann ist
\[
  \chi : \F_q \to \C^*, \quad
  x \mapsto \gamma \circ \trace(x)
\]
eine nicht-triavialer Charakter, der sogenannte \emph{Hauptcharakter}.

\begin{bem}
  Zu jedem $y \in \F_q$ ist $\chi_y : \F_q \to \C^*, \enspace x \mapsto \exp(\frac{2 \pi \trace(xy) i}{p})$ ein weiterer Charakter und es gilt
  \[ \hat{\F_q} = \Set{\chi_y}{y \in \F^q}. \]
\end{bem}

Sei $V$ ein $\C$-Vektorraum.
Wir betrachten Abbildungen von $\F_q^n$ nach $V$.
Sei $\chi \hat{\F_q}$, $\chi \neq \chi_0$
Zu $f : \F_q^n \to V$ definieren wir eine \emph{transformierte Abbildung} durch
\[ \hat{f} : \F_q^n \to V, \enspace u \mapsto \sum_{v \in \F_q^n} \chi(\scp{u}{v}) \cdot f(v). \]

\begin{satz}
  Sei $U$ ein $\F_q$-Teilraum von $\F_q^n$ und $f : \F_q^n \to V$ eine Abbildung.
  Dann gilt
  \[
    \sum_{u \in U} \hat{f}(u) = \abs{U} \cdot \sum_{w \in U^\perp} f(w).
  \]
\end{satz}

\begin{satz}[\emph{Mac-Williams-Transformation}]
  Sei $C \subseteq \F_q^m$ ein linearer Code.
  Betrachte den dualen Code $C^\perp$ zu $C$.
  Dann gilt:
  \begin{align*}
    A_{C^\perp}^\homogen(X, Y) & = \tfrac{1}{\abs{C}} \cdot A_C^\homogen(X + (q-1)Y, X-Y), \\
    A_{C^\perp}(Z) & = \tfrac{1}{\abs{C}} \cdot (1 + (q-1) Z)^n \cdot A_C \left( \frac{1-Z}{1+(q-1)Z} \right).
  \end{align*}
\end{satz}

\begin{beweisidee}
  Verwende den letzten Satz mit $V = \C[X, Y]$ und $f(v) \coloneqq X^{n - \wt(v)} Y^{\wt(v)}$.
\end{beweisidee}

\begin{bsp}
  Sei $m \geq 1$.
  Für den Simplex-Code gilt
  \[
    A_{\Sim_q(m)}^\homogen (X, Y) = X^n + (q^m - 1) X^{n - q^{m-1}} Y^{q^{m-1}}.
  \]
  Somit gilt für den Hamming-Code $\Ham_q(m) = \Sim_q(m)^\perp$:
  \begin{align*}
    A_{\Ham_q(m)}^\homogen & (X, Y) = 
    \tfrac{1}{q^m} \left( [X+(q-1)Y]^n + \vphantom{[X + (q-1) Y]^{n - q^{m-1}}} \right. \\
    + & \left. (q^m - 1) \cdot [X + (q-1) Y]^{n - q^{m-1}} \cdot [X-Y]^{q^{m-1}} \right).
  \end{align*}
\end{bsp}

\begin{bsp}
  Wir betrachten den $[24, 8, 12]$-Code $C = \Golay(24) = C^\perp$.
  Es gilt
  \[
    A_C^\homogen (X, Y) = X^{24} + A_8 X^{16} Y^8 + A_{12} X^{12} Y^{12} + A_8 X^8 Y^{16} + Y^{24}.
  \]
  TODO: weiter?
\end{bsp}

% Vorlesung vom 22.12.2015

% §10. MDS-Codes
\section{§10. MDS-Codes}

% §10.1 MDS-Codes der Länge 4

\begin{defn}
  Eine Matrix $A \in \Z_q^{q \times q}$ heißt \emph{lateinisches Quadrat} der Ordnung $q$, falls in jeder Zeile und Spalte jede Zahl aus $\Z_q$ genau einmal vorkommt.
\end{defn}

\begin{defn}
  Zwei lateinische Quadrate $A, B \in \Z_q^{q \times q}$ heißen \emph{orthogonal} ($A \perp B$), falls folgende Abbildung bijektiv ist:
  \[
    \{ 1, \ldots, q \}^2 \to \Z_q^2, \quad
    (i, j) \mapsto (A_{ij}, B_{ij})
  \]
\end{defn}

\begin{satz}
  Es gibt genau dann ein Paar orthogonaler Quadrate der Ordnung~$q$, wenn $q \not\in \{ 2, 6 \}$.
\end{satz}

\begin{satz}
  Sei $n=4$, $d=3$.
  Dann gilt
  \begin{itemize}
    \item $A_2(4, 3) = 2 < 4 = 2^{4-3+1}$
    \item $A_6(4,3) = 34 < 36 = 6^{4-3+1}$
    \item $A_q(4,3) = q^2 = q^{4-3+1}$ für $q \geq 3$, $q \neq 6$
  \end{itemize}
\end{satz}

\begin{beweisidee}
  Man zeigt: Existenz eines MDS-Codes $\iff$ es gibt ein Paar orthogonaler lateinischer Quadrate der Ordnung $q$.
\end{beweisidee}

\begin{satz}
  Es gibt keinen (perfekten) $6$-ären $(7, 6^5, 3)$-Code.
\end{satz}

\begin{defn}
  Seien $\psi_1, \ldots, \psi_l$ lateinische Quadrate der Ordnung $q$ über $\Z_q$.
  Diese heißen \emph{paarweise orthogonal}, falls $\psi_i \perp \psi_j$ für alle $i \neq j$.
  Man sagt, $\psi_1, \ldots, \psi_l$ ist eine Liste von MOLS (mutually orthogonal latin squares) der Ordnung $q$.
\end{defn}

\begin{bem}
  Sei $N(q) \coloneqq $ die maximale Anzahl von MOLS der Ordnung~$q$.
  \begin{itemize}
    \item Es gilt $N(q) \leq q - 1$.
    \item Eine Produkt-Konstruktion liefert: $N(q) \geq \min \{ N(r), N(s) \}$, falls $q = rs$ mit $\ggT(r, s) = 1$.
    $q = \prod_{i=1}^m p_i^{a_i}$ Primfaktorzerlegung.
    Dann: $N(q) \geq \min \Set{N(p_i^{a_i})}{i = 1, \ldots, m}$.
    % In dieser Formel kann Ungleichheit gelten!
    \item Sei $q \geq 2$ eine Primzahlpotenz. Dann ist $N(q) = q-1$.
    \item $N(q) = q - 1$ $\iff$ $\exists$ projektive Ebene der Ordnung $q$
  \end{itemize}
\end{bem}

% Vorlesung vom 7.1.2015

% §10.2. Verfeinerung der Gewichtsverteilung eines linearen Codes

\begin{nota}
  $[n] \coloneqq \{ 1, \ldots, n \}$ \\
  Für $I \subseteq [n]$ sei $U_I \coloneqq \spann \Set{e_i}{i \in I} \subseteq \F_q^n$
\end{nota}


\begin{defn}
  Sei $C$ ein lin. Code.
  Dann sei $\delta_C(I) \coloneqq \delta(I) \coloneqq \dim(C \cap U_i)$.
\end{defn}

% 10.4
\begin{prop}
  \begin{itemize}
    \item $\delta(I) = 0$ falls $\abs{I} < d$
    \item $\ex{I \subseteq [n]} \abs{I} = d \wedge \delta(I) = 1$
    \item $\fa{I \subseteq [n]} \abs{I} = d \wedge \delta(I) = 1 \implies \delta(I) = 1$
  \end{itemize}
\end{prop}

\begin{defn}
  \begin{minipage}[t]{0.88 \linewidth}
    \begin{itemize}
      \item Für $i \in [n]$ sei $A_C(i) \coloneqq A_i \coloneqq \abs{\Set{w \in C}{\wt(w) = i}}$
      \item Für $I \subseteq [n]$ sei $a_C(I) \coloneqq a(I) \coloneqq \abs{\Set{w \in C}{\supp(w) = I}}$
    \end{itemize}
  \end{minipage}
\end{defn}

\begin{bem}
  $A_i = \sum_{I \subseteq [n], \abs{I} = i} a(I)$
\end{bem}

% 10.5
\begin{satz}
  Sei $C$ ein $[n, k, d]$-Code über $\F_q$.
  Dann ist
  \[
    a(I) = \sum_{K \subseteq I} (-1)^{\abs{I} - \abs{K}} \cdot q^{\delta(K)}.
  \]
\end{satz}

\begin{bem}
  Es gibt auch eine invertierte Formel:
  \[
    \abs{C \cap U_I} = q^{\delta(I)} = \sum_{K \subseteq I} a(K).
  \]
\end{bem}

% §10.3. 

% 10.6 und 10.7
\begin{satz}
  Sei $C$ ein $[n, k, d]$-MDS-Code über $\F_q$. % (\dh{} $k = n - d + 1$).
  Dann gilt
  \begin{itemize}
    \item $\delta(I) = \max ( 0, \abs{I} - (d-1) )$ \enspace
    für alle $I \subseteq [n]$
    \item $A_j = \binom{n}{j} \sum_{l=d}^j \binom{j}{l} \cdot (-1)^{j-l} \cdot (q^{l-d+1} - 1)$ \enspace
    für $j \geq d$
  \end{itemize}
\end{satz}

% Vorlesung vom 12.1.2015

Sei $C$ ein $[n, k, d]$-Code über $\F_q$.
Dann ist $C^\perp$ ein $[n, k^\perp, d^\perp]$-Code mit $k^\perp = n - k$.
Frage: Was ist $d^\perp$?
Falls $C$ ein MDS-Code ist, so ist $k = n - d + 1$, also $k^\perp = n - k = d - 1$

\begin{satz}
  Ist $C$ ein linearer MDS-Code, so ist auch $C^\perp$ ein linearer MDS-Code.
\end{satz}

% §10.4. Reed-Solomon-Codes

\begin{lem}
  $(\Z_{q-1}, +, 0) \cong (\F_q^{\times}, \cdot, 1)$.
  Der Isomorphismus ist gegeben durch $1 \mapsto \beta$, wobei $\beta \in \F_q^{\times}$ mit $\ord{\beta} = q-1$.
  Solche $\beta$ heißen \emph{primitive Elemente}.
\end{lem}

\begin{bem}
  Die Anzahl primitiver Elemente in $\F_q^{\times}$ ist $\phi(q-1)$, wobei $\phi$ die Eulersche $\phi$-Funktion ist.
\end{bem}

\begin{defn}
  Wähle $n, \ell \in \N$ mit $1 \leq \ell \leq n < q$.
  Sei $\beta \in \F_q$ ein primitives Element.
  Setze $P_\ell \coloneqq \Set{f(x) \in \F_q[x]}{\deg(f) < \ell}$.
  Betrachte
  \[
    \epsilon = \epsilon_\beta : P_\ell \to \F_q^n, \quad
    f(x) \mapsto (f(\beta), f(\beta^2), \ldots, f(\beta^n)).
  \]
  Dann heißt $C \coloneqq \im \epsilon$ ein \emph{Reed-Solomon-Code}.
\end{defn}

\begin{satz}
  Der konstruierte Reed-Solomon-Code ist ein linearer $[n, \ell, n - \ell + 1]$-MDS-Code.
\end{satz}

% Beweis: $\epsilon$ ist injektiv

\begin{bsp}
  Sei $q = 8$, $n = 7$.
  Wir wollen einen 2-Fehler-korrigierenden MDS-Code $C$ über $\F_8$ konstruieren.
  Somit $t = 2$, also $d = 2t + 1 = 5$.
  Dann: $k = n - d + 1 = 7 - 5 + 1 = 3$.
  Dann ist
  \[
    \begin{pmatrix}
      1 & 1 & 1 & 1 & 1 & 1 & 1 \\
      1 & \beta & \beta^2 & \beta^3 & \beta^4 & \beta^5 & \beta^6 \\
      1 & \beta^2 & \beta^4 & \beta^6 & \beta & \beta^3 & \beta^5
    \end{pmatrix}
  \]
  eine Generatormatrix von $C$.
\end{bsp}

\begin{bsp}
  Sei $q = 11$, $\F_{11} \cong \Z_{11}$.
  Gesucht ist ein $[10, 6, 5]$-MDS-Code $C$ über $\F_{11}$.
  Wir wissen, dass $C^\perp$ dann ein $[10, 4, 7]$-Code ist.
  Diesen können wir als Reed-Solomon-Code konstruieren.
\end{bsp}

TODO: Rest des Beispiels, insbesondere Decodierung

% Vorlesung vom 14.1.2016

% §11. Zyklische Codes
\section{§11. Zyklische Codes}

% §11.1. Beschreibung zyklischer Codes

\begin{defn}
  Ein linearer Code $C \subseteq \F_q^n$ heißt \emph{zyklischer Code}, falls
  \[
    (c_0, c_1, \ldots, c_{n-1}) \in C \implies
    (c_{n-1}, c_0, \ldots, c_{n-2}) \in C.
  \]
\end{defn}

\begin{bem}
  Als Koordinaten verwenden wir $\{ 0, \ldots, n-1 \} \cong \Z_n$. \\
  Der \emph{Shift-Operator} ist $S : \F_q^n \to \F_q^n, \enspace e^i \mapsto e^{i+1 \pmod{n}}$. \\
  Ein zyklischer Code ist ein $S$-invarianter Teilraum von $\F_q^n$.
\end{bem}

\begin{nota}
  Wir identifizieren Wörter $v \in \F_q^n$ mit Polynomen $v(x) \in \F_q[x]_{< n} \coloneqq \Set{f \in \F_q[x]}{\deg(f) < n}$ vermöge
  \[
    \F_q^n \to \F_q[x]_{< n}, \enspace
    v \mapsto v(x) \coloneqq v_0 + v_1 x + \ldots + v_{n-1} x^{n-1}.
  \]
\end{nota}

\begin{fakt}
  $\F_q[x]$ ist ein euklidischer Hauptidealbereich.
\end{fakt}

\begin{bem}
  Für $c \in \F_q^n$ gilt für $c(x)$ und $ \overline{c}(x) \coloneqq (S c)(x) \in \F_q[x]$:
  \[
    x \cdot c(x) = \overline{c}(x) \pmod{x^n - 1}.
  \]
  Somit gilt: $C \subseteq \F_q[x]_{< n}$ ist genau dann ein zyklischer Code, wenn $x \cdot c(x) \bmod{(x^n - 1)} \in C$ für alle $c(x) \in C$.
\end{bem}

% ausgelassen: einige (etwas unnötige) Sätze

\begin{nota}
  $\mathcal{R} \coloneqq \mathcal{R}_{q,n} \coloneqq \F_q[x] / (x^n - 1)$
\end{nota}

% 11.5 und 11.6
\begin{satz}
  Es gibt kanonische bijektive Korrespondenzen
  \begin{align*}
    & \{ \text{ zyklische Codes der Länge $n$ über $\F_q$ } \} \\
    \cong \enspace & \{ \text{ Ideale $J \subseteq \mathcal{R}_{q,n}$ } \} \\
    \cong \enspace & \{ \text{ Ideale $I \subseteq \F_q[x]$ mit $(x^n - 1) \in I$ } \} \\
    \cong \enspace & \{ \text{ monische Polynome $g(x) \in \F_q[x]$ mit $g(x) \divides (x^n - 1)$ } \}
  \end{align*}
  Das zu einem Code $C \subseteq \F_q[x]_{< n}$ zugehörige monische Polynom ist das (eindeutige!) monische Polynom~$g(x) \in C$ mit minimalem Grad.
  Es gilt $C = \Set{f(x) g(x)}{f(x) \in \F_q[x] \text{ mit } \deg(f) < n - \deg(g)}$ und $\dim(C) = n - \deg(g)$.
\end{satz}

\begin{defn}
  \begin{minipage}[t]{0.8 \linewidth}
    $g(x)$ heißt das \emph{Generatorpolynom} zu~$C$. \\
    $h(x) \coloneqq \nicefrac{(x^n - 1)}{g(x)}$ heißt \emph{Kontrollpolynom} zu $C$.
  \end{minipage}
\end{defn}

\begin{lem}
  $c(x) \in C \iff h(x) c(x) \equiv 0 \pmod{x^n - 1}$
\end{lem}

\begin{nota}
  $k \coloneqq n - \deg(g)$
\end{nota}

\begin{bem}
  Die Generatormatrix von $C$ ist
  \[
    G = \begin{pmatrix}
      g_0 & g_1 & \cdots & g_{n-k} & 0 & \cdots & 0 \\
      0 & g_0 & g_1 & \cdots & g_{n-k} & \cdots & 0 \\
      \vdots & \ddots & \ddots & \ddots & \cdots & \ddots & \vdots \\
      0 & \cdots & 0 & g_0 & g_1 & \cdots & g_{n-k}
    \end{pmatrix} \in \F_q^{k \times n}.
  \]
\end{bem}

% 10.9
\begin{prop}
  Sei $h(x) = h_0 + h_1 x + \ldots + h_k x^k$.
  Dann ist die Kontrollmatrix von $C$
  \[
    H = \begin{pmatrix}
      h_k & h_{k-1} & \cdots & h_0 & 0 & \cdots & 0 \\
      0 & h_k & h_{k-1} & \cdots & h_0 & \cdots & 0 \\
      \vdots & \ddots & \ddots & \ddots & \cdots & \ddots & \vdots \\
      0 & \cdots & 0 & h_k & h_{k-1} & \cdots & h_0
    \end{pmatrix} \in \F_q^{n - k \times n}.
  \]
\end{prop}

% Vorlesung vom 19.1.2016

\begin{defn}
  Sei $f(x) = f_d x^d + \ldots + f_0 \in \F_q[x]$ mit $f_0 \neq 0$ (also $f(0) \neq 0$). \\
  Das zu~$f(x)$ \emph{reziproke Polynom} ist
  \[
    f^\rez(x) = f(\tfrac{1}{x}) \cdot x^d = f_0 x^d + f_1 x^{d-1} + \ldots + f_{n-1} x + f_n.
  \]
\end{defn}

\begin{satz}
  Sei $C$ ein zyklischer Code der Länge $n$ über $\F_q$ mit Generatorpolynom $g(x)$ und Kontrollpolynom $h(x)$. \\
  Dann ist $C^\perp$ ebenfalls zyklisch mit Generatorpolynom $h^*(x)$ und Kontrollpolynom $g^*(x)$, wobei
  \[
    h^*(x) \coloneqq \tfrac{1}{h_0} \cdot h^\rez(x), \qquad
    g^*(x) \coloneqq \tfrac{1}{g_0} \cdot g^\rez(x).
  \]
\end{satz}

\begin{bsp}
  Sei $q=2$, $n=7$.
  Wir wählen
  \[
    x^7 - 1 = \underbrace{(x-1) \cdot (x^3 + x^2 + 1)}_{h(x) \coloneqq x^4 + x^2 + x + 1 =} \cdot \underbrace{(x^3 + x + 1)}_{g(x) \coloneqq}
  \]
  Die Generator- und Kontrollmatrix zu $C_g$ sind
  \[
    G = \begin{psmallmatrix}
      1 & 1 & 0 & 1 & 0 & 0 & 0 \\
      0 & 1 & 1 & 0 & 1 & 0 & 0 \\
      0 & 0 & 1 & 1 & 0 & 1 & 0 \\
      0 & 0 & 0 & 1 & 1 & 0 & 1
    \end{psmallmatrix}, \quad
    H = \begin{psmallmatrix}
      1 & 0 & 1 & 1 & 1 & 0 & 0 \\
      0 & 1 & 0 & 1 & 1 & 1 & 0 \\
      0 & 0 & 1 & 0 & 1 & 1 & 1
    \end{psmallmatrix}.
  \]
  $C_g$ ist ein $[7, 4, 3]$-Code und äquivalent zu~$\Ham_2(3)$.
\end{bsp}

\begin{bsp}
  Sei $q = 3$, $n = 11$.
  Wir wählen
  \[
    x^{11} - 1 = \underbrace{(x-1) \cdot (x^5 + x^4 - x^3 + x^2 - 1)}_{h(x) \coloneqq x^6 + x^4 - x^3 - x^2 - x + 1 =} \cdot \underbrace{(x^5 - x^3 + x^2 - x - 1)}_{g(x) \coloneqq}.
  \]
  Betrachte die Parity-Check-Erw.~$\hat{C}_g$ von~$C_g$.
  Die Generatormatrix ist
  \[
    \setcounter{MaxMatrixCols}{20} % LaTeX ist so ein Scheiß!
    \hat{G} = \begin{psmallmatrix}
      -1 & -1 & 1 & -1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\
      0 & -1 & -1 & 1 & -1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\
      0 & 0 & -1 & -1 & 1 & -1 & 0 & 1 & 0 & 0 & 0 & 1 \\
      0 & 0 & 0 & -1 & -1 & 1 & -1 & 0 & 1 & 0 & 0 & 1 \\
      0 & 0 & 0 & 0 & -1 & -1 & 1 & -1 & 0 & 1 & 0 & 1 \\
      0 & 0 & 0 & 0 & 0 & -1 & -1 & 1 & -1 & 0 & 1 & 1
    \end{psmallmatrix}
  \]
  $\hat{C}_g$ ist selbstdual, da $\hat{G} \cdot \hat{G} = 0$.
  Das Minimalgew. von~$\hat{C}_g$ ist somit durch drei teilbar.
  Je drei Spalten von~$\hat{G}$ sind lin. unabhängig.
  Daher ist das Minimalgewicht $\geq 6$.
  Wegen der Kugelpackungsschranke gilt Gleichheit.
  Somit ist $\hat{C}_g$ ein $[12, 6, 6]$-Code und $C_g$ ein $[11, 6, 5]$-Code über~$\F_3$.
  Letzterer ist perfekt.
  Also $C_g = \Golay(11)$ und $\hat{C}_g = \Golay(12)$.
\end{bsp}

\begin{bsp}
  Sei $q = 2$, $n = 23$.
  Die Zerlegung von $x^{23} - 1 \in \F_2[x]$ in irreduzible Faktoren ist
  \begin{align*}
    x^{23} - 1 = \enspace & (x-1) \cdot (x^{11} + x^9 + x^7 + x^6 + x^5 + x + 1) \\
    & \cdot \, \underbrace{(x^{11} + x^{10} + x^6 + x^5 + x^4 + x^2 + 1)}_{g(x) \coloneqq}
  \end{align*}
  Es stellt sich heraus, dass $C_g = \Golay(23)$.
\end{bsp}

% §11.3 CRC-Codes (cyclic redundancy check codes)
\subsection{CRC-Codes (\textit{cyclic redundancy check})}

\begin{verf}[CRC-Codierung]
  Sei $g(x) \in \F_q[x]_{< n}$ das Generatorpolynom des zyklischen $[n, k]$-Codes $C_g \subset \F_q^n$ mit $\deg(g) = n - k$.
  Der Nachrichtenraum sei $\F_q^k \hat{=} \F_q[x]_{< k}$.
  \begin{itemize}
    \item Codierungsabbildung: \enspace $E : \F_q[x]_{< k} \to C_g, \enspace m(x) \mapsto c(x)$ \enspace mit
    \[
      c(x) \coloneqq m(x) \cdot x^{n-k} - [ m(x) \cdot x^{n-k} \pmod{g(x)} ].
    \]
    \item Decodierung und Fehlererkennung: \\
    Angenommen, $y(x) = y_0 + y_1 x + \ldots + y_{n-1} x^{n-1} \in \F_q[x]_{< n}$ wurde empfangen.
    Gilt $g(x) \divides y(x)$, also $y(x) \in C$, so wurde wahrscheinlich auch~$y(x)$ gesendet.
    Die zugehörige Nachricht ist
    \[
      m(x) = y_{n-k} + y_{n-k+1} x + \ldots + y_{n-1} x^{n-1}.
    \]
  \end{itemize}
\end{verf}

\begin{defn}
  Sei $2 \leq b \leq n$.
  Eine Teilmenge $I \subseteq \Z_n$ heißt ein \emph{zyklisches Intervall der Länge~$b$}, falls ein $\ell \in \Z_n$ existiert mit
  \[
    I = [\ell, \ell + b - 1]_{\bmod n} \coloneqq \Set{\ell + j \bmod n}{0 \leq j \leq b-1}.
  \]
  Ein $v \in \F_q^n$ ist ein \emph{Fehlerbündel der Länge~$b$}, falls $b$ minimal ist mit:
  Es existiert ein zyklisches Intervall $I$ der Länge $b$ mit $v_\ell \neq 0$, $v_{\ell+b-1 \pmod{n}} \neq 0$ und $\supp(v) \subseteq I$.
\end{defn}

\begin{bsp}
  $v = (0,2,0,0,0,0,1,1,0)$ ist ein Fehlerbündel der Länge $b = 5$.
\end{bsp}

\begin{prop}
  Sei $g(x)$ wie oben und $n \geq 3$.
  Dann erkennt $C_g$ \textit{Einzelfehler} und Fehlerbündel der Länge~$b$, falls $b \leq n - k < n$, \dh{} ist~$v$ ein solches Fehlerbündel, so gilt $v \not\in C_g$.
\end{prop}

\begin{bem}
  Diese Eigenschaft ist nützlich bei Transportmedien, bei denen sich Fehler lokal häufen \zB{} bei CDs durch Kratzer.
\end{bem}

\begin{bspe}
  Folgende CRC-Codes mit $q = 2$ sind standardisiert:

  \begin{tabular}{l | l | l}
    Name & $g(x)$ & $\min \, \Set{\ell}{g(x) \divides (x^\ell - 1)}$ \\ \hline
    CRC-12 & $x^{12} + x^4 + x^3 + x^2 + x + 1$ & $n = 511 = 2^9 - 1$ \\
    CRC-16 & $x^{16} + x^{15} + x^2 + 1$ & $n = 32767 = 2^{15} - 1$ \\
    CRC-16' & $x^{16} + x^{12} + x^5 + 1$ & $n = 32767 = 2^{15} - 1$
  \end{tabular}
\end{bspe}

% Vorlesung vom 21.1.2016

% §11.4. Nullstellen von zyklischen Codes
\subsection{Nullstellen von zyklischen Codes}

\begin{ziel}
  Ein zyklischer Code $C \subseteq \F_q^n$ ist gegeben durch sein Generator- polynom $g(x) \in \F_q[x]$ mit $g(x) \divides (x^n - 1)$.
  Dieses $g(x)$ können wir als Produkt einer Auswahl von irred. Faktoren von $x^n - 1$ schreiben.
  Wir können also die zyklischen Codes $C \subseteq \F_q^n$ studieren, indem wir die irreduziblen Faktoren von $x^n - 1$ herausfinden.
\end{ziel}

\begin{bem}
  Sei $n = p^s \cdot \ell$, wobei~$\ell$ nicht durch~$p$ teilbar ist.
  \[
    x^n - 1 = (x^\ell - 1)^{p^s}.
  \]
  Die irreduziblen Faktoren von $(x^n - 1)$ sind also die gleichen wie von $(x^\ell - 1)$, jeweils mit $p^s$-facher Vielfachheit.
\end{bem}

\begin{voraussetzung}
  Wir können daher im Folgenden annehmen, dass~$n$ nicht durch~$p$ teilbar ist.
\end{voraussetzung}

\begin{bem}
  Wegen $\ggT(x^n - 1, n x^{n - 1}) = 1$ treten die irreduziblen Faktoren von $(x^n - 1)$ in einfacher Vielfachheit auf.
\end{bem}

\begin{defn}
  Die \emph{Ordnung von $q$ modulo $n$} ist
  \[
    m \coloneqq \ord_n(q) \coloneqq \min \, \Set{\ell \geq 1}{q^\ell \equiv 1 \pmod{n}}.
  \]
\end{defn}

\begin{bem}
  Betrachte die Erweiterung $\F_{q^m} \supseteq \F_q$.
  Die Einheitengruppe $(\F_{q^m}^{\times}, \cdot, 1)$ ist zyklisch, also isomorph zu $(\nicefrac{\Z}{q^m - 1}, +, 0)$. \\
  Für $d \divides n$ gibt es wegen $d \divides (q^m - 1)$ genau eine Untergruppe $Z_d \subset \F_{q^m}^{\times}$ mit~$d$ Elementen, nämlich
  \[
    Z_d = \Set{\alpha \in \F_{q^m}^{\times}}{\alpha^d = 1} = \Set{\alpha \in \F_{q^m}^{\times}}{\ord(\alpha) \divides d}.
  \]
\end{bem}
  
\begin{defn}
  Die Elemente $\alpha \in Z_d$ heißen \emph{$d$-te Einheitswurzeln}.
\end{defn}

\begin{bem}
  Da jedes $\alpha \in Z_n$ eine Wurzel von $(x^n - 1)$ ist, gilt
  \[
    x^n - 1 = \prod_{\mathclap{\alpha \in Z_n}} \, (x - \alpha)
  \]
  Es ist $\F_{q^m}$ sogar der kleinste Erweiterungskörper von $\F_q$, in dem $(x^n - 1)$ in Linearfaktoren zerfällt.
  Man nennt ihn deshalb \textit{Zerfällungskörper} von $(x^n - 1)$ über $\F_q$.
  Wir müssen jetzt also noch die Teilmengen $J \subset Z_n$ mit $\prod_{\mathclap{\alpha \in J}} \, (x - \alpha) \in \F_q[x]$ bestimmen.
\end{bem}

\begin{defn}
  Eine \emph{primitive $d$-te Einheitwurzel} ist ein Erzeuger von $Z_d$, also ein Element von
  $
    \Gamma_d \coloneqq \Set{\alpha \in \F_{q^m}^{\times}}{\ord(\alpha) = d}
  $.
\end{defn}

\begin{bem}
  Sei $\zeta$ eine primitive $n$-te Einheitswurzel.
  Für jeden Teiler $d$ von $n$ ist dann $\zeta^{\nicefrac{n}{d}}$ eine primitive $d$-te Einheitswurzel.
  Es gilt
  \[
    Z_n = \bigsqcup_{d \divides n} \Gamma_d
    \enspace \text{und} \enspace
    \abs{\Gamma_d} = \phi(n) \coloneqq \abs{\Set{1 \leq \ell \leq n}{\ggT(n, \ell) = 1}}.
  \]
\end{bem}

\begin{defn}
  Gelte $d \divides n$.
  Das \emph{$d$-te Kreisteilungspolynom} ist
  \[
    \Phi_d(x) \coloneqq \prod_{\alpha \in \Gamma_d} (x - \alpha).
  \]
\end{defn}

\begin{lem}
  Es gilt sogar $\Phi_d(x) \in \F_q[x]$.
\end{lem}

\begin{kor}
  $x^n - 1 = \prod_{d \divides n} \Phi_d(x)$
\end{kor}

\begin{bem}
  Es bleibt zu untersuchen, wie $\Phi_d(x)$ über $\F_q$ zerfällt.
\end{bem}

\begin{defn}
  Sei $\zeta$ eine primitive $d$-te Einheitswurzel. \\
  Die zu $\zeta^i$ gehörende \emph{Kreisteilungsklasse} ist
  \[
    \Gamma_{d,i} \coloneqq \Gamma^{(\zeta)}_{d,i} \coloneqq \Set{\zeta^{i q^\ell}}{\ell \geq 1} \subseteq \Gamma_d.
  \]
\end{defn}

\begin{bem}
  Für versch. Wahlen $\zeta$ und $\zeta'$, bzw. $i$ und $i'$ sind $\Gamma^{(\zeta)}_{d,i}$ und $\Gamma^{(\zeta')}_{d,i'}$ entweder gleich oder disjunkt.
  Die Kreisteilungsklassen sind daher wohldefiniert.
  Es gilt $\abs{\Gamma_{d,i}} = \ord_d(q)$.
  Es zerfällt $\Gamma_d$ in $\nicefrac{\phi(d)}{\ord_d(q)}$ Kreisteilungsklassen.
  Sei nun~$\zeta$ fest gewählt.
\end{bem}

\begin{lem}
  $\mu^{(d)}_i(x) \coloneqq \prod_{\mathclap{\alpha \in \Gamma_{d,i}}} (x - \alpha)$ ist ein irreduzibles Polynom in $\F_q [x]$
\end{lem}

\begin{kor}
  Sei $K_d$ ein Repräsentantensystem von Kreisteilungsklassen, also
  $\Gamma_d = \bigsqcup_{\mathclap{i \in K_d}} \Gamma_{d,i}$.
  Dann ist $\Phi_d(x) = \prod_{\mathclap{i \in K_d}} \mu^{(d)}_i(x)$.
\end{kor}

\begin{fazit}
  Sei $n = \ell p^s$ mit $\ggT(p, \ell) = 1$.
  Die Zerlegung von $x^n - 1$ in irreduzible Faktoren über $\F_q$ ist dann
  \[
    x^n - 1 \enspace = \enspace \prod_{d \divides \ell} \enspace \prod_{i \in K_d} \enspace \left( \mu^{(d)}_i(x) \right)^{p^s}.
  \]
\end{fazit}

% Vorlesung vom 16.1.2016

% (drei Beispiele ausgelassen)

\begin{bsp}
  Sei $q = 2$ und $n = 2^m - 1$ mit $m \geq 2$.
  Dann ist $\ord_n(2) = m$.
  Sei $\zeta \in \F_{2^m}$ eine primitive $n$-te Einheitswurzel und $g(x)$ das Minimalpolynom von $\zeta$.
  Betrachte den zyklischen Code $C_g$.
  Man kann zeigen, dass das Minimalgewicht $\geq 3$ ist.
  Wegen der Kugelpackungsschranke gilt Gleichheit.
  Der Code $C_g$ besitzt die gleichen Parameter wie der Hamming-Code~$\Ham_2(m)$.
\end{bsp}

\TODO{Sind diese Codes äquivalent?}

% §12. BCH-Codes
\section{§12. BCH-Codes}

% §12.1 Die BCH-Schranke

\begin{situation}
  Sei $\F_q$ der endliche Körper mit $q$ Elementen.
  Gelte $\ggT(q, n) = 1$ und $m \coloneqq \ord_n(q)$.
  Dann ist $\F_{q^m}$ der Zerfällungskörper von $x^n - 1$.
  Sei $\zeta \in \F_{q^m}$ eine primitive $n$-te Einheitswurzel und $Z_n = \{ \zeta^0, \ldots, \zeta^{n-1} \}$ die Menge aller $n$-ten Einheitswurzeln.
\end{situation}

\begin{konstr}
  Sei $\mathcal{N} \subseteq Z_n$ eine Teilmenge.
  Wir setzen
  \begin{align*}
    N(\mathcal{N}) & \coloneqq \Set{i = 0, \ldots, n-1}{\zeta^i \in \mathcal{N}} \subset \Z_n, \\
    g_N(x) & \coloneqq \kgV \Set{\mu_i(x)}{i \in N},
  \end{align*}
  wobei $\mu_i(x)$ das Minimalpolynom von~$\zeta^i$ sei.
  Zuletzt sei $C(\mathcal{N}) \coloneqq C(g_N)$ der von $g_N$ erzeugte zyklische Code.
\end{konstr}

\begin{bem}
  $C(\mathcal{N})$ ist der kleinste Code, der die Elemente von $\mathcal{N}$ als Nullstellen besitzt. 
  Für ein Wort $c(x) \in \F_q[x]{< n}$ gilt dann:
  \[
    c(x) \in C(\mathcal{N}) \iff c(\zeta^i) = 0 \quad \text{für alle $i \in N$}.
  \]
\end{bem}

\begin{defn}[\emph{B}ose, Ray-\emph{C}haudhuri, \emph{H}ocquenghem] \mbox{} \\
  Sei $b \in \{ 0, \ldots, n-1 \}$ und $\delta \in \N$ mit $2 \leq \delta \leq n$.
  Setze
  \[
    L \coloneqq [b, b + \delta - 2] \coloneqq \Set{i \bmod{n}}{b \leq i \leq b + \delta - 2}.
  \]
  Dann heißt $C(L)$ ein \emph{BCH-Code} mit \emph{designiertem Abstand}~$\delta$.
  Für $b=1$ heißt~$C(L)$ ein BCH-Code \textit{im engeren Sinne}. \\
  Falls $n = q^m - 1$, so ist~$\zeta$ ein primitives Element in $\F_{q^m}$ und $C(L)$ heißt ein \emph{primitiver BCH-Code}.
\end{defn}

\begin{satz}[BCH-Schranke]
  Für den Minimalabstand~$d$ und die Dimension~$k$ von $C(L)$ gilt: \quad
  $d \geq \delta$, \enspace
  $k \geq n - m \cdot (\delta - 1)$.
\end{satz}

\begin{samepage}

\begin{satz}
  Sei $q = 2$, $\delta = 2 \epsilon + 1$ und $L = [1, \delta - 1]_{\bmod{n}}$. \\
  Dann gilt \enspace $\dim(C(L)) \geq n - m \cdot \epsilon$.
\end{satz}

% ausgelassen: erstes Beispiel

\begin{bsp}
  Die Nullstellenmenge des ternären Golay-Code~$\Golay(11)$ ist $\{ \zeta, \zeta^3, \zeta^5, \zeta^9 \}$.
  Dies ist ein BCH-Code mit $b = 3$ und $\delta = 4$. \\
  Die Parity-Check-Erweiterung von $\Golay(11)$ hat damit Minimalgewicht mindestens~$4$, also~$6$ wegen Selbstdualität. \\
  Für den Minimalabstand~$d$ von $C(L)$ gilt daher $d \geq 5$. \\
  Aus der Kugelpackungsschranke folgt Gleichheit.
\end{bsp}

% ausgelassen: drittes Beispiel

% Vorlesung vom 28.1.2016

% ausgelassen: Beispiel 12.5

% §12.5 Die Methode von Lint und Wilson
\subsection{Die Methode von Lint und Wilson}

\end{samepage}

\begin{defn}
  Sei $\mathcal{N} \subseteq \F_{q^m}^*$ nichtleer.
  Das bzgl. $\mathcal{N}$ \emph{unabhängige Mengensystem}~$U(\mathcal{N})$ ist rekursiv definiert durch
  \begin{enumerate}[label=\alph*), leftmargin=1.8em]
    \miniitem{0.3 \linewidth}{$\emptyset \in U(\mathcal{N})$}
    \miniitem{0.6 \linewidth}{$A \in U(\mathcal{N}), \, \gamma \in \F_{q^m}^* \implies \gamma A \in U(\mathcal{N})$}
    \item $A \in U(\mathcal{N}), \, A \subseteq \mathcal{N}, \, \beta \in \F_{q^m}^* \setminus \mathcal{N} \implies A \cup \{ \beta \} \in U(\mathcal{N})$
  \end{enumerate}
\end{defn}

\begin{prop}[Lint, Wilson]
  Sei $f(x) \in \F_q[x]$, $f \neq 0$, und $\mathcal{N}$ die Nullstellenmenge von~$f$ innerhalb~$\F_{q^m}^*$.
  Dann gilt
  \[
    \wt(f) \geq \max \Set{\abs{A}}{A \in U(\mathcal{N})}.
  \]
\end{prop}

\begin{bem}
  Die BCH-Schranke ist ein Korollar hiervon.
\end{bem}

\begin{bsp}
  Der binäre Golay-Code $\Golay(23)$ ist der von
  \[
    g(x) \coloneqq x^{11} + x^{10} + x^6 + x^5 + x^4 + x^2 + 1
  \]
  erzeugte Code.
  Die zugehörige Nullstellenmenge ist
  \[
    \Set{\zeta^i}{i \in \Gamma_1}
    \quad \text{mit} \quad
    \Gamma_1 \coloneqq \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \}.
  \]
  Sei $c(x) \in \Golay(23)$ und $\mathcal{N}$ dessen Nullstellenmenge.
  Es sei $c(x)$ kein Vielfaches von $\Phi_{23}(x)$ und damit $\Gamma_1 \subseteq \mathcal{N} \cap Z_n \subseteq \Gamma_1 \cup \{ 1 \}$.
  Man schließt nun, dass folg. Teilmengen von~$\F_{2048}$ in $U(\mathcal{N})$ liegen:
  \begin{align*}
    & \emptyset
    \xra{c}
    \{ \zeta^5 \}
    \xra{b}
    \{ \zeta^4 \}
    \xra{c}
    \{ \zeta^4\!, \zeta^5 \}
    \xra{b}
    \{ \zeta, \zeta^2 \}
    \xra{c}
    \{ \zeta, \zeta^2\!, \zeta^5 \}
    \xra{b}
    \{ \zeta^8\!, \zeta^9\!, \zeta^{12} \} \\
    & \xra{c}
    \{ \zeta^8\!, \zeta^9\!, \zeta^{12}\!, \zeta^{14} \}
    \xra{b}
    \{ \zeta^{12}\!, \zeta^{13}\!, \zeta^{16}\!, \zeta^{18} \}
    \xra{c}
    \{ \zeta^5\!, \zeta^{12}\!, \zeta^{13}\!, \zeta^{16}\!, \zeta^{18} \} \\
    & \xra{b}
    \{ \zeta^{18}\!, \zeta^2\!, \zeta^3\!, \zeta^6\!, \zeta^8 \}
    \xra{c}
    \{ \zeta^2\!, \zeta^3\!, \zeta^5\!, \zeta^6\!, \zeta^8\!, \zeta^{18} \}
    \xra{b}
    \{ 1, \zeta^1\!, \zeta^3\!, \zeta^4\!, \zeta^6\!, \zeta^{16} \}
  \end{align*}
  Aus der Prop folgt, dass $c(x)$ Gewicht $\geq 6$ hat.
  \begin{itemize}
    \item Falls $c(1) = \wt(c) = 0$, so ist $\{ 1, \zeta^1, \zeta^3, \zeta^4, \zeta^6, \zeta^{16} \} \in \mathcal{N}$ und somit $\{ 1, \zeta^1, \zeta^3, \zeta^5, \zeta^4, \zeta^6, \zeta^{16} \} \in U(\mathcal{N})$.
    Mit der Prop folgt, dass $c(x)$ Gewicht $\geq 7$ hat.
    \item Falls $c(1) = \wt(c) = 1 \bmod{2}$, so hat $c(x)$ ungerades Gewicht, also Gewicht $\geq 7$.
  \end{itemize}
  Somit hat $\Golay(23)$ das Minimalgewicht $\geq 7$. \\
  Aus der Kugelpackungsschranke folgt Gleichheit.
\end{bsp}

\TODO{Beispiel}

\begin{konstr}[von MDS-Codes]
  Angenommen, $n \divides q - 1$.
  Dann ist $m = \ord_n(q) = 1$ und $x^n - 1$ zerfällt über~$\F_q$ in Linearfaktoren. \\
  Sei~$\zeta$ eine prim. $n$-te Einheitswurzel, $b \geq 1$ und $2 \leq \delta \leq n$.
  Dann ist
  \[
    g(x) \coloneqq (x - \zeta^b) \cdot (x - \zeta^{b+1}) \cdot \ldots \cdot (x - \zeta^{b + \delta - 2})
  \]
  das kleinste mon. Polynom aus~$\F_q[x]$ mit $\mathcal{N} = \{ \zeta^b, \ldots, \zeta^{b+\delta-2} \}$ als Nullstellen.
  Für BCH-Code $C = C(\mathcal{N}) = C_g$ gilt
  \[
    \wt(g) \leq \deg(g) + 1 = \delta \leq d(C) \leq \wt(g),
  \]
  also $d(C) = \delta$.
  Es handelt sich darum um einen MDS-Code, da
  \[
    \dim(C) = n - \deg(g) = n - (\delta - 1) = n - d + 1.
  \]
\end{konstr}

\begin{defn}
  Im Falle $n = q - 1$ spricht man hier auch von einem \emph{Reed-Solomon-Code}.
\end{defn}

% §12.3. Einiges zu binären BCH-Codes
\subsection{Einiges zu binären BCH-Codes}

Sei $q = 2$ und $C$ ein binärer BCH-Code im engeren Sinne.
Gelte $n = 2^m - 1$.
Sei $\zeta \in \F_{2^m}$ eine primitive $n$-te Einheitswurzel.

\begin{satz}
  $C$ hat ungerades Minimalgewicht.
\end{satz}

Zusammen mit der Kugelpackungsschranke folgt:

\begin{prop}
  Hat $C$ den designierten Abstand $\delta = 2 \epsilon + 1$ und gilt $2^{m \epsilon} < {\sum}_{i=0}^{\epsilon + 1} \binom{n}{i}$, so hat $C$ das Minimalgewicht~$\delta$.
\end{prop}

\begin{satz}
  Gelte $m \geq 4$.
  Der designierte Abstand von~$C$ sei $\delta = 5$.
  Dann:
  \begin{itemize}
    \miniitem{0.3 \linewidth}{$d = d(C) = 5$}
    \miniitem{0.5 \linewidth}{$k = \dim(C) = 2^m - 1 - 2m$}
  \end{itemize}
\end{satz}

\begin{bem}
  Der Code $C$ mit $\delta = 5$ wird von $g(x) = \mu_1(x) \mu_3(x)$ erzeugt.
\end{bem}

\begin{defn}
  Sei $C$ ein $q$-närer Code der Länge~$n$.
  Dann heißt
  \begin{align*}
    \rho(C) & \coloneqq \max \Set{r \!\geq\! 0}{\forall \, c, c' \in C : B_r(c) \cap B_r(c') \!=\! \emptyset} \enspace
    \text{\emph{Packungsradius}} \\
    \sigma(C) & \coloneqq \min \Set{s \geq 0}{\F_q^n = \bigcup_{c \in C} B_s(c)} \geq \rho(C) \quad
    \text{\emph{Überdeckungsradius}}
  \end{align*}
\end{defn}

\begin{bem}
  $\rho(C) = \sigma(C) \iff $ $C$ ist ein perfekter Code
\end{bem}

\begin{defn}
  Codes mit $\rho + 1 = \sigma$ heißen \emph{quasi-perfekt}.
\end{defn}

\begin{bsp}
  Man kann zeigen: Binäre, primitive BCH-Codes im engeren Sinne mit $\delta = 5$ sind quasi-perfekt.
  % siehe Buch von MacWilliams und Sloane auf Seite 279
\end{bsp}

\begin{prop}
  Sei~$C$ ein primitiver BCH-Code im engeren Sinne der Länge $n = q^m - 1$ und designiertem Abstand~$\delta$ über~$\F_q$.
  Falls $\delta \divides n$, so ist $\delta$ das Minimalgewicht von~$C$.
\end{prop}

\TODO{Wo ist der folgende Satz im Skript?}

\begin{satz}
  Sei $q = 2$, $\delta = 2 \epsilon + 1$, $L = \Set{i \bmod{n}}{1 \leq i \leq \delta - 1}$ und $C = C(L)$ der zugehörige BCH-Code.
  Dann gilt $\dim(C) \geq n - m \cdot \epsilon$.
\end{satz}

% vorher nur: $\dim(C) \geq n - m \cdot 2 \epsilon$

% §12.4. Zur Decodierung von BCH-Codes
\subsection{Decodierung von BCH-Codes}

\begin{satz}
  Sei $m \geq 4$ und $C$ der binäre, primitive BCH-Code im engeren Sinne mit Minimalabstand~$d = 5$, \dh{}~$C$ hat $\zeta, \zeta^2, \zeta^3, \zeta^4$ als Null- stellen für ein prim. Element $\zeta \in \F_{2^m}$.
  Angenommen, $c(x)$ wurde gesendet und $u(x) = c(x) + e(x)$ empfangen, wobei für das Fehlerpo- lynom $\wt(e(x)) \leq 2$ gilt.
  Setze $s_1 \coloneqq u(\zeta)$ und $s_3 \coloneqq u(\zeta^3)$.
  Dann gilt:
  \begin{itemize}
    \item Falls $s_1 = 0$, so ist $e(x) = 0$.
    \item Falls $s_3 = s_1^3 \neq 0$, so ist $e(x) = x^\ell$, wobei $s_1 = \zeta^\ell$.
    \item Falls $s_1 \neq 0$ und $s_1^3 \neq s_3$, so gilt $e(x) = x^i + x^j$, wobei $\zeta^{-i}$ u. $\zeta^{-j}$ die Nullstellen von $L(z) = 1 - s_1 z + (\tfrac{s_3}{s_1} - s_1^2) z^2 \in \F_{2^m}[z]$ sind.
  \end{itemize}
\end{satz}

% ausgelassen: Beispiel

\begin{situation}
  Sei $C$ ein BHC-Code im engeren Sinne mit designiertem Abstand~$\delta$.
  Wir nehmen an, dass $c(x) \in C$ gesendet und $u(x) = c(x) + e(x) \in \F_q[x]_{< n}$ empfangen wurde.
  Dabei habe das Fehlerpolynom~$e(x)$ das Gewicht $w \coloneqq \wt(e(x)) \leq \tau \coloneqq \floor{\tfrac{\delta-1}{2}}$. \\
  Die Fehlerstellen seien $1 \leq \varphi(1) < \ldots < \varphi(w) \leq n$, also
  \[
    e(x) = \sum_{i=1}^w e_{\varphi(i)} x^{\varphi(i)}
    \quad \text{mit} \quad
    e_{\varphi(i)} \in \F_q^*.
  \]
\end{situation}

\begin{ziel}
  Bestimmung \circled{1} der Anzahl~$w$ von Fehlern, \circled{2} der Fehlerpo- sitionen $\varphi(i)$ und \circled{3} der nötigen Korrekturen~$e_{\varphi(i)}$ gegeben~$u(x)$.
\end{ziel}

\begin{nota}
  \begin{minipage}[t]{0.7 \linewidth}
    \begin{itemize}
      \item $X_i \coloneqq \zeta^{\varphi(i)}$,
      $Y_i \coloneqq e_{\varphi(i)}$ für $1 \leq i \leq w$,
      \item $X_j \coloneqq Y_j \coloneqq 0$ für $w < j \leq \tau$,
      \item $s_k \coloneqq u(\zeta^k)$ für $1 \leq k \leq \delta - 1$ \quad (\textit{Syndrom})
    \end{itemize}
  \end{minipage}
\end{nota}

\begin{bem}
  Die $X_i$'s codieren \circled{2}, die $Y_i$'s \circled{3}.
  Für $1 \leq j \leq \delta - 1$ gilt
  \[
    s_j = u(\zeta^j) = e(\zeta^j) = \sum_{i=1}^w e_{\varphi(i)} \zeta^{j \varphi(i)} = \sum_{i=1}^w Y_i X_i^j = \sum_{i=1}^\tau Y_i X_i^j
  \]
\end{bem}

\begin{satz}
  Für $\ell \in \N$ mit $w \leq \ell \leq \tau$ sei
  \[
    M_\ell \coloneqq \begin{psmallmatrix}
      s_1 & s_2 & \cdots & s_\ell \\
      s_2 & s_3 & \cdots & s_{\ell + 1} \\
      \vdots & \vdots & \ddots & \vdots \\
      s_\ell & s_{\ell + 1} & \cdots & s_{2 \ell - 1}
    \end{psmallmatrix}.
  \]
  Dann gilt: \enspace
  \inlineitem{$M_w$ ist invertierbar} \\
  \inlineitem{$M_{w+1}, \ldots, M_\tau$ sind nicht invertierbar (falls $w < \tau$)}
\end{satz}

\begin{kor}
  $w = \max \, \Set{\ell \leq \tau}{\det(M_\ell) \neq 0}$
  \hfill (Lsg von \circled{1})
\end{kor}

\begin{defn}
  Das \emph{Lokatorpolynom} ist
  \[
    L(z) \coloneqq (1 - X_1 z) \cdot \ldots \cdot (1 - X_w z) \in \F_{q^m} [z].
  \]
\end{defn}

\begin{bem}
  Die Nullstellen von $L(z)$ sind $\zeta^{- \varphi(1)}$, \ldots, $\zeta^{- \varphi(w)}$.
  Es gilt
  \[
    L(z) = \sum_{i=0}^w (-1)^i \cdot p_i \cdot z^i
    \quad \text{wobei} \quad
    p_i \coloneqq \enspace \sum_{\mathclap{I \subseteq [w], \enspace \abs{I} = i}} \enspace X_I, \quad
    X_I \coloneqq \prod_{j \in I} X_j
  \]
\end{bem}

\begin{satz}
  Die eindeutige Lösung des linearen Gleichungssystems
  \[
    M_w \cdot x = - \begin{psmallmatrix}
      s_{w+1} \\ s_{w+2} \\ \vdots \\ s_{2w-1} \\ s_{2w}
    \end{psmallmatrix}
    \qquad \text{ist} \qquad
    P \coloneqq \begin{psmallmatrix}
      (-1)^w p_w \\
      (-1)^{w-1} p_{w-1} \\
      \vdots \\
      p_2 \\
      - p_1
    \end{psmallmatrix}.
  \]
\end{satz}

\begin{folgerung}
  Die elementarsymm. Fktn $p_0, \ldots, p_w$ in $X_1, \ldots, X_w$ kann man aus $s_1, \ldots, s_{2 w}$ berechnen.
  Gleiches gilt somit für $L(z)$.
  Die Exponenten in der Darstellung der Nullstellen von $L(z)$ als $\zeta$-Potenz geben dann die Fehlerstellen an.
  \hfill (Lsg von \circled{2})
\end{folgerung}

\begin{satz}
  Die eindeutige Lösung des linearen Gleichungssystems
  \[
    \begin{psmallmatrix}
      X_1 & X_2 & \cdots & X_w \\
      X_1^2 & X_2^2 & \cdots & X_w^2 \\
      \vdots & \vdots & \ddots & \vdots \\
      X_1^w & X_2^w & \cdots & X_w^w
    \end{psmallmatrix} \cdot z = \begin{psmallmatrix}
      s_1 \\ s_2 \\ \vdots \\ s_w
    \end{psmallmatrix}
    \qquad \text{ist} \qquad
    z = \begin{psmallmatrix}
      Y_1 \\ Y_2 \\ \vdots \\ Y_w
    \end{psmallmatrix}
  \]
\end{satz}

\begin{folgerung}
  Da sich, wie schon gesehen, die Werte~$X_i$ aus den Syndromen~$s_k$ berechnen lassen, liefert dies eine Methode, die Werte~$Y_i$ aus den Syndromen zu berechnen.
  \hfill (Lsg von \circled{3})
\end{folgerung}

% §12.5. Ein weiteres Decodierverfahren
\subsection{Ein weiteres Decodierverfahren}

\begin{ziel}
  Entwicklung eines effizienteren Decodierverfahrens für die gleiche Situation wie im letzten Abschnitt.
\end{ziel}

\begin{defn}
  Das \emph{Fehlerauswertungspolynom} ist
  \[
    F(z) \coloneqq \sum_{i=1}^w Y_i X_i \cdot \prod_{\ell = 1, \ell \neq i} (1 - X_\ell \cdot z) \in \F_{q^m} [z].
  \]
\end{defn}

\begin{satz}
  Sei $L'(z)$ die formale Ableitung des Lokatorpolynoms.
  Dann:
  \[
    Y_k = - \frac{F(X_k^{-1})}{L'(X_k^{-1})} \qquad
    \text{für alle } k = 1, \ldots, w.
  \]
\end{satz}

\begin{defn}
  Das \emph{Syndrompolynom} ist
  \[
    S(z) \coloneqq \sum_{j=1}^{\delta - 1} s_j z^{j-1} \in \F_{q^m} [z].
  \]
\end{defn}

\begin{prop}
  $F(z) = S(z) \cdot L(z) \pmod{z^{\delta - 1}}$
\end{prop}

\begin{bem}
  In anderen Worten: Es gibt ein Polynom~$v(z) \in \F_{q^m} [z]$ mit
  \[
    v(z) \cdot z^{\delta - 1} + L(z) \cdot S(z) = F(z).
  \]
  Der erweiterte euklidische Algorithmus berechnet eine \textit{Bézout-Darstellung} des ggT, \dh{} Polynome $a(z), b(z) \in \F_{q^m} [z]$ mit
  \[
    a(z) \cdot z^{\delta - 1} + b(z) \cdot S(z) = \ggT(z^{\delta - 1}, S(z)).
  \]
\end{bem}

\begin{alg}
  Wir initialisieren dazu
  \[
    \begin{psmallmatrix}
      r_{-1} (z) \\ r_0 (z)
    \end{psmallmatrix} \coloneqq \begin{psmallmatrix}
      z^{\delta - 1} \\ S(z)
    \end{psmallmatrix}
    \quad \text{sowie} \quad
    \begin{psmallmatrix}
      a_{-1} (z) & b_{-1} (z) \\
      a_0 (z) & b_0 (z)
    \end{psmallmatrix} \coloneqq \begin{psmallmatrix}
      1 & 0 \\
      0 & 1
    \end{psmallmatrix}
  \]
  Solange $r_k (z) \neq 0$ ist, führen wir eine Division von $r_{k-1} (z)$ durch $r_k (z)$ mit Rest durch und erhalten $q_{k+1} (z), r_{k+1} (z) \in \F_{q^m} [z]$ mit
  \[
    r_{k-1} (z) = q_{k+1} (z) \cdot r_k (z) + r_{k+1} (z)
    \enspace \text{und} \enspace
    \deg(r_{k+1} (z)) < \deg(r_k (z)).
  \]
  Wir setzen \enspace $
    \arraycolsep=1pt
    \begin{array}[t]{l l}
      a_{k+1} (z) & \coloneqq a_{k-1} (z) - q_{k+1} (z) \cdot a_k (z), \\
      b_{k+1} (z) & \coloneqq b_{k-1} (z) - q_{k+1} (z) \cdot b_k (z).
    \end{array}
  $ \\[2pt]
  Man prüft leicht nach, dass bei dieser Update-Regel die Invariante
  \[
    a_k (z) \cdot z^{\delta - 1} + b_k (z) \cdot S(z) = r_k (z)
  \]
  erhalten bleibt.
  Sei $m$ maximal unter $r_m (z) \neq 0$.
  Dann ist
  \[
    a_m (z) \cdot z^{\delta - 1} + b_m (z) \cdot S(z) = r_m (z) = \ggT(z^{\delta - 1}, S(z))
  \]
  die gesuchte Bézout-Darstellung des ggT.
\end{alg}

\begin{satz}
  Sei $\ell$ minimal unter $\deg(r_\ell (z)) < \nicefrac{(\delta - 1)}{2}$.
  Dann gilt:
  \begin{itemize}
    \miniitem{0.45 \linewidth}{$L(z) = b_\ell(0)^{-1} \cdot b_\ell(z)$}
    \miniitem{0.45 \linewidth}{$F(z) = b_\ell(0)^{-1} \cdot r_\ell(z)$}
  \end{itemize}
\end{satz}

\begin{folgerung}
  Man kann aus den Syndromen das Lokatorpolynom $L(z)$ mit hilfe des erweiterten euklidischen Algorithmus berechnen. \\
  Dieses enthält alle Informationen über \circled{1} und \circled{2}.
  Mit dem letzten Satz aus dem letzen Abschnitt kann man \circled{3} bestimmen.
\end{folgerung}

% ausgelassen: Beispiel

% §12.6. Abschließende Bemerkungen

\begin{satz}[\emph{Newton-Identitäten}]
  Sei $\K$ ein Körper und $x_1, \ldots, x_t$ sowie~$z$ Variablen.
  Für $k \in \N$ sei
  $\sigma_k \coloneqq x_1^k + \ldots + x_t^k$ (insb. $\sigma_0 = t$).
  Wir betrachten
  \begin{alignat*}{3}
    S(z) & \coloneqq \sum_{k=0}^\infty \sigma_k z^k && \in \K [x_1, \ldots, x_t] \llbracket z \rrbracket \subseteq \K (x_1, \ldots, x_t) \llbracket z \rrbracket, \\
    L(z) & \coloneqq \prod_{j=1}^t (1 - x_j z) && \in \K [x_1, \ldots, x_t] [z] \subseteq \K (x_1, \ldots, x_t) \llbracket z \rrbracket.
  \end{alignat*}
  Dann ist $L(z) \cdot S(z)$ ein Polynom mit Grad $\leq t - 1$.
  Genauer gilt
  \[
    L(z) \cdot S(z) = \sum_{r=0}^{t-1} (-1)^{r} \cdot p_r \cdot (t - r) \cdot z^r,
  \]
  wobei $p_0, \ldots, p_t$ die elementarsymm. Fktn in $x_1, \ldots, x_t$ sind.
\end{satz}

\end{document}