Die größte Mächtigkeit eines Codes mit vorgegebener Blocklänge und Minimalabstand

Wir definieren ${\displaystyle {\mathcal {A}}_{q}(n,d)}$ als die größte Mächtigkeit eines Codes über ${\displaystyle K}$ mit Blocklänge ${\displaystyle n}$ und Minimalabstand ${\displaystyle d}$, genauer also ${\displaystyle {\mathcal {A}}_{q}(n,d):=\max\{|C|:~C\subseteq K^{n}{\text{ und }}\operatorname {d} (C)=d\}}$. Merke, dass ${\displaystyle {\mathcal {A}}_{q}(n,d)}$ ausschließlich von der Mächtigkeit von ${\displaystyle K}$, der Blocklänge und vom Minimalabstand abhängt.

Kugeln mit Radius r und ihr Volumen

Es sei ${\displaystyle B_{r}(c):=\{y\in K^{n}:~d(c,y)\leq r\}}$ die Kugel um das Wort ${\displaystyle c\in K^{n}}$. Die Mächtigkeit (oder auch das Volumen) von ${\displaystyle B_{r}(c)}$ ist gegeben durch

${\displaystyle V_{q}(n,r):=|B_{r}(c)|=\sum \limits _{j=0}^{r}{\binom {n}{j}}(q-1)^{j}}$.

Beweis

Es sei ${\displaystyle C\subseteq K^{n}}$ ein Code mit Minimalabstand ${\displaystyle d}$, Blocklänge ${\displaystyle n}$ und Mächtigkeit ${\displaystyle |C|={\mathcal {A}}_{q}(n,d)}$. ${\displaystyle C}$ ist also ein ${\displaystyle (n,d)}$-Code mit größter Mächtigkeit. Dann gilt, dass ${\displaystyle \textstyle \bigcup _{c\in C}B_{d-1}(c)=K^{n}}$. Denn angenommen, das wäre nicht der Fall, so gibt es ein ${\displaystyle \textstyle y\in K^{n}\setminus \bigcup _{c\in C}B_{d-1}(c)}$. Dieses ${\displaystyle y}$ erfüllt ${\displaystyle d(y,C):=\min\{d(y,c):~c\in C\}\geq d}$, womit ${\displaystyle C\cup \{y\}}$ ein Code mit Minimalabstand ${\displaystyle d}$ über ${\displaystyle K^{n}}$ wäre, der eine größere Mächtigkeit als ${\displaystyle C}$ hat. Das kann nach Definition von ${\displaystyle {\mathcal {A}}_{q}(n,d)}$ nicht sein. Daher bekommen wir ${\displaystyle \textstyle |\bigcup _{c\in C}B_{d-1}(c)|=|K^{n}|=q^{n}}$ und somit insgesamt:

${\displaystyle q^{n}=|\bigcup _{c\in C}B_{d-1}(c)|\leq \sum _{c\in C}|B_{d-1}(c)|=|C|\cdot |B_{d-1}(c^{\ast })|={\mathcal {A}}_{q}(n,d)\cdot V_{q}(n,d-1)}$,

wobei ${\displaystyle c^{\ast }\in K^{n}}$ irgendein Wort ist. Nach Umstellen erhalten wir unsere Behauptung.

Konstruktion eines (n,d)-Codes über K

Der Beweis der Schranke liefert einen Greedy-Algorithmus zur Konstruktion eines Codes ${\displaystyle C\subseteq K^{n}}$, der die Gilbert-Varshamov-Schranke erfüllt, das heißt ${\displaystyle |C|\geq {\tfrac {q^{n}}{V_{q}(n,d-1)}}}$. Dabei startet man mit einem beliebigen Wort ${\displaystyle y_{0}\in K^{n}}$ und setzt ${\displaystyle C_{0}:=\{y_{0}\}}$. Danach wählt man ${\displaystyle y_{i}\in K^{n}}$, ${\displaystyle i\in \mathbb {N} \setminus \{0\}}$, so dass ${\displaystyle d(y_{i},C_{i-1}):=\min\{d(y_{i},c):~c\in C_{i-1}\}\geq d}$. Man stoppt, sobald man kein ${\displaystyle y\in K^{n}}$ mit ${\displaystyle d(y,C_{i})\geq d}$ mehr wählen kann.