Teorie kódování

Tři série domácích cvičení, vyřešit alespoň jednu v každé sérii. Může se na nich spolupracovat, ale sepsat je máme sami.

Motivace: Máme konečnou abecedu

A

(většinou

{0,1}

) a nad ní chceme postavit kódová slova délky

n

, tedy

w \in A^{n}

. Kód je nějaká množina možných slov

C \subset A^{n}

Kódování pomocí paritního bitu:

C = {a_{1} \dots a_{n - 1} s | a_{i} \in {0,1}, (s = \sum_{i = 1}^{n - 1} a_{i}) mod 2}

– lze rozpoznat jednu chybu

Ve zkouškovém testu bude za úkol pro dva dané z parametrů

M, n, d

určit optimální hodnotu třetího.

Komunikace: Odesílatel odešle nějaké slovo

w \in C

, nepřítel ho nějak změní, příjemce dostane slovo

x \in A^{n}

a má odhadnout původní slovo

w

. K tomu použije algoritmus dekódování:

Lineární kódy

Definice. Je-li

T

konečné těleso a kód

C \subset T^{n}

je lineární podprostor, kód se nazývá lineární.

Poznámka. Kód nad

ℤ_{2}

je lineární, právě když obsahuje nulové slovo a je uzavřený na sčítání.

Poznámka. Je-li kód

C \subset T^{n}

lineární, potom

M = {| T |}^{\dim C}

Definice. Generující matice lineárního kódu je matice, jejíž řádky tvoří bázi kódu. Značíme

G

Definice. Kontrolní matice lineárního kódu je matice, jejíž řádky tvoří jádro jeho generující matice.

Příklad. Paritní kód je lineární, jeho generující matice je například

G = (\begin{array}{cccccc} 1 & 0 & 0 & \dots & 0 & 1 \\ 0 & 1 & 0 & \dots & 0 & 1 \\ 0 & 0 & 1 & \dots & 0 & 1 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 0 & 0 & 0 & \dots & 1 & 1 \end{array})

a jeho kontrolní matice je

H = (\begin{array}{cccccc} 1 & 1 & 1 & \dots & 1 & 1 \end{array})

Příklad. Koktavý kód je lineární, jeho generující matice je

G = (\begin{array}{cccccc} 1 & 1 & 1 & \dots & 1 & 1 \end{array})

a jeho kontrolní matice je například

H = (\begin{array}{cccccc} 1 & 0 & 0 & \dots & 0 & 1 \\ 0 & 1 & 0 & \dots & 0 & 1 \\ 0 & 0 & 1 & \dots & 0 & 1 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 0 & 0 & 0 & \dots & 1 & 1 \end{array})

Tedy paritní a koktavý kód jsou k sobě duální.

Věta. Jsou-li

G, H

generující a kontrolní matice lineárního kódu, potom

H \cdot G^{T} = 0

Důkaz. Víceméně plyne z definice kontrolní matice.

Věta. Je-li

C

lineární kód,

H

jeho kontrolní matice a

w \in T^{n}

, potom

w \in C ⟺ H \cdot w = 0

Důkaz. Víceméně plyne z definice kontrolní matice.

Definice. Váha slova

x \in T^{n}

wt (x) ≔ dist (x, 0)

Věta. Je-li

C

lineární kód, potom

d = \min {wt (z) | z \in C ∖ {0}}

Důkaz. Triviální.

Věta. Je-li

C

lineární kód, potom

d = \min {k \in ℕ^{+} | e x i s t u j e k l i n e \overset{ˊ}{a} r n \overset{ˇ}{e} z \overset{ˊ}{a} v i s l \overset{ˊ}{y} c h s l o u p c \overset{˚}{u} H}

Poznámka. To zní podobně jako hodnost, ale vlastně to s ní nemá moc společného.

Důkaz. Označme pravou stranu rovnosti

d^{'}

. Víme, že existuje

x \in C, wt (x) = d

. Potom

H x^{T} = 0

, tudíž nenulové složky

x

určují lineárně závislé sloupce

h

. Z toho plyne

d^{'} \leq d

. Zbývá dokázat druhou nerovnost. Jakákoli lineární kombinace méně než

d

sloupců

H

jde vyjádřit jako

H y^{T}

, kde

wt (y) < d

, tudíž

y \notin C ∴ H y^{T} \neq 0

a jde o nenulovou lineární kombinaci. Z toho plyne

d^{'} \geq d

Definice. Nechť

T

je konečné těleso velikosti

q

m \in ℕ

(q, m)

-Hammingův kód je lineární kód, jehož kontrolní matice má jako sloupce právě všechny nenulové vektory z

T^{m}

, jejichž první nenulový prvek je

1

Věta. Pro Hammingův kód je

d \geq 3

Důkaz. Podle věty o lineárně závislých sloupcích jednoduché.

Věta. Pro Hammingův kód je

n = \frac{q^{m} - 1}{q - 1}

Důkaz. Existuje přesně

q^{m} - 1

nenulových vektorů z

T^{m}

\frac{1}{q - 1}

z nich má jako první nenulový prvek jedničku. Nebo se to dá natvrdo spočítat jako součet geometrické řady.

Věta. Pro Hammingův kód je

k = n - m

Důkaz. Kontrolní matice má

m

řádků a obsahuje jako sloupce všechny jednotkové vektory, tedy nutně

\dim H = m

. Potom

k = \dim G = n - \dim H = n - m

Věta. Hammingův kód je perfektní.

Důkaz. Dosazením

t = 1

do Hammingovy nerovnosti dostáváme

M (1 + n (q - 1)) \leq q^{n}

Použitím již známých tvrzení dostáváme

q^{n - m} (1 + \frac{q^{m} - 1}{q - 1} (q - 1)) \leq q^{n}

Snadnými úpravami zjistíme, že nastává rovnost, tedy kód je perfektní.

Definice. Nechť

C_{1}, C_{2}

jsou kódy délky

n

C_{1}

je ekvivalentní

C_{2}

, jestliže existuje permutace

π \in 𝕊_{n}

taková, že

w_{1} \dots w_{n} \in C_{1} ⟺ w_{π (1)} \dots w_{π (n)} \in C_{2}

Poznámka. I někdo z KDAIZ by možná zvládl dokázat, že je to relace ekvivalence.

Definice. Lineární kód

C \subset T^{n}

dimenze

k

je systematický, pokud

\forall α_{1}, \dots, α_{k} \in T, \exists_{1} α_{k + 1}, \dots, α_{n} : α_{1} \dots α_{n} \in C

Intuitivně: do prvních

k

písmen můžeme zakódovat, co chceme, a poté jen správně doplníme.

Věta. Nechť

C \subset T^{n}

je systematický lineární kód dimenze

k

. Potom pro generující a kontrolní matici můžeme psát

G = (I_{k} | F), H = (- F^{T} | I_{n - k}), F \in T^{k \times (n - k)}

Důkaz. Tvar matice

G

plyne z definice systematického kódu. Stačí tedy ověřit, že

H \cdot G^{T} = 0

Věta. Každý lineární kód je ekvivalentní nějakému systematickému.

Důkaz. Vezmeme nějakou bázi kódu, nastrkáme ji jako řádky do matice a tu upravíme pomocí řádkových úprav do horního trojúhelníkového tvaru. Tím samozřejmě dostaneme bázi toho samého kódu. Teď stačí přeházet sloupce tak, aby prvních

k

sloupců samo o sobě tvořilo matici s plnou hodností. Tím dostaneme bázi nějakého ekvivalentního kódu. Matici si můžeme doupravit, aby těch prvních

k

sloupců byla jednotková matice, z čehož je vidět, že jde o systematický kód.

Věta (Singletonova nerovnost). Nechť

C \subset T^{n}

je lineární kód dimenze

k

s minimální vzdáleností

d

. Potom

n + 1 \geq k + d

Důkaz. Z Frobeniovy věty nebo něčeho takového máme

\dim C = k = n - h (H)

. Z definice hodnosti je

h (H) + 1

minimální číslo takové, že každých tolik sloupců matice

H

je lineárně závislých. Z toho a z naší věty o lineárně závislých sloupcích zjevně plyne

h (H) + 1 \geq d

. Odtud už nějak vyčupčíme žádanou nerovnost.

Věta (Gilbert-Varshamova mez pro binární kódy). Nechť

T = ℤ_{2}, r, n, d \in ℕ

a platí

\sum_{j = 0}^{d - 2} (\binom{n - 1}{j}) < 2^{r}

Potom existuje kontrolní matice

H \in T^{r \times n}

, jejíž kód má minimální vzdálenost alespoň

d

Důkaz. Budeme induktivně konstruovat matici

H

po sloupcích. Nechť již máme

i

sloupců a chceme přidat

(i + 1)

-tý. Ten musíme vybrat tak, aby to nebyl součet nanejvýš

d - 2

existujících sloupců. (

d - 1

už nevadí, protože potom bychom společně s tím nově přidaným měli

d

lineárně závislých a to je v pořádku.) Takových součtů existuje

\sum_{j = 0}^{d - 2} (\binom{i}{j})

. Naše nerovnost nám přesně zajistí, že ještě nějaký povolený zbyde.

Definice. Pro

k, d \in ℕ

označme

N (k, d)

minimální možnou délku lineárního binárního kódu dimenze

k

s minimální vzdáleností

d

Poznámka. Zjevně

N (k, 1) = k, N (1, d) = d

Lemma. Pro

k, d \in ℕ, k \geq 2

N (k, d) \geq d + N (k - 1, ⌈ \frac{d}{2} ⌉)

Důkaz. Nechť

C

je lineární kód délky

n ≔ N (k, d)

. Víme, že pro nějaké

w \in C

wt (w) = d

. Bez újmy na obecnosti předpokládejme

w = 0^{n - d} 1^{d}

. Generující matice bude mít tvar

G = (\begin{array}{cccccc} 0 & \dots & 0 & 1 & \dots & 1 \\ ⋱ & ⋮ & ⋰ & ⋱ & ⋮ & ⋰ \\ \dots & G_{1} & \dots & \dots & G_{2} & \dots \\ ⋰ & ⋮ & ⋱ & ⋰ & ⋮ & ⋱ \end{array})

Dokážeme, že

h (G_{1}) = k - 1

. Kdyby ne, potom by její řádky byly lineárně závislé, tudíž z nich jde nakombinovat nulové slovo. Pokud nakombinujeme odpovídající řádky původní matice, dostaneme buď nulové slovo, což by znamenalo, že

h (G) < k

, nebo slovo začínající

n - d

nulami a následně nenulové, kteréžto má vzdálenost od

w

menší než

d

. Každopádně jsme ve sporáku. TBD Nechť

C_{1}

je kód délky

n - d

a dimenze

k - 1

s generující maticí

G_{1}

d_{1}

je jeho minimální vzdálenost. Dokážeme, že

d_{1} \geq \frac{d}{2}

. Vezměme kódové slovo

u \in C_{1}, wt (u) = d_{1}

a nějaké další slovo

v

???

Věta (Griesmerova mez).

N (k, d) \geq \sum_{i = 0}^{k - 1} ⌈ \frac{d}{2^{i}} ⌉

Důkaz. Indukcí podle

k

. Základní případ již máme. Nechť

k \geq 2

. Z předchozího lemmatu máme

N (k, d) \geq d + N (k - 1, ⌈ \frac{d}{2} ⌉) \overset{IP}{\geq} d + \sum_{i = 0}^{k - 2} ⌈ \frac{⌈ \frac{d}{2} ⌉}{2^{i}} ⌉ \geq d + \sum_{i = 0}^{k - 2} ⌈ \frac{d}{2^{i + 1}} ⌉ = d + \sum_{i = 1}^{k - 1} ⌈ \frac{d}{2^{i}} ⌉ = \sum_{i = 0}^{k - 1} ⌈ \frac{d}{2^{i}} ⌉

Vraťme se k binárnímu Hammingovu kódu. Definujme standardní tabulku, kde na nultém řádku jsou kódová slova a na $i$ -tém řádku jsou slova, která se liší od kódového slova v $i$ -tém bitu.

Věta. U binárního Hammingova kódu pro slova

y, z

H y^{T} = H z^{T}

právě tehdy, pokud leží ve stejném řádku kontrolní tabulky.

Důkaz. Máme

y = u + e_{i}, z = v + e_{j}, u, v \in C

. Potom

H y^{T} - H z^{T} = H (u^{T} - v^{T} + e_{i} - e_{j}) = H (e_{i} - e_{j})

. Toto se rovná nule právě tehdy, pokud

i = j

, protože jinak

wt (e_{i} - e_{j}) = 2

, tedy

e_{i} - e_{j} \notin C

Definice. Nechť

C

je lineární kód a

x

je slovo. Potom syndrom

x

H x^{T}

Poznámka. Obecně definujeme standardní tabulku tak, že v každém řádku budou slova se stejným syndromem.

Věta. Nechť

C

je lineární binární kód s minimální vzdáleností

d

t ≔ ⌊ \frac{d - 1}{2} ⌋

. Potom v každém řádku standardní tabulky je nanejvýš jedno slovo váhy

\leq t

Důkaz. Nechť v

i

-tém řádku jsou slova

a, b

s vahou nanejvýš

t

. Potom

H (a^{T} - b^{T}) = H a^{T} - H b^{T} = 0

. Jelikož

wt (a - b) \leq wt (a) + wt (b) \leq 2 t < d

, musí být

a - b = 0

Cyklické kódy

Definice. Lineární kód

C

délky

n

je cyklický, pokud s každým slovem obsahuje i jeho cyklické permutace, neboli

\forall w_{0} w_{1} \dots w_{n - 1} \in C : w_{1} \dots w_{n - 1} w_{0} \in C

Poznámka. Množinu slov

ℤ_{2}^{n}

můžeme reprezentovat jako okruh polynomů

ℤ_{2} [x] ╱ (x^{n} - 1)

, kde budeme značit

z

formální proměnnou splňující

z^{n} = 1

. Potom pro cyklický kód platí

w \in C ⟺ w \cdot z \in C

Důsledek. Nechť

C

je cyklický kód reprezentovaný jako polynomy a

a \in ℤ_{2} [x] ╱ (x^{n} - 1)

. Potom

w \in C ⟺ a \cdot w \in C

Příklad. Paritní kód délky 4 je cyklický:

\begin{aligned} C & = {0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111} \\ = {0, z^{2} + z^{3}, z + z^{3}, z + z^{2}, 1 + z^{3}, 1 + z^{2}, 1 + z, 1 + z + z^{2} + z^{3}} \end{aligned}

Všimněme si, že jsou to všechno násobky

z + 1

Věta. Nechť

C

je cyklický kód délky

n

a dimenze

k

. Potom existuje

g \in C

stupně

n - k

takový, že

$C = {a \cdot g | a \in ℤ_{2} [x] ╱ (x^{n} - 1)}$
${z^{i} \cdot g | i = 0, \dots, k - 1}$ je báze $C$
$g | (x^{n} - 1)$

Důkaz. Za

g

vezměme jakýkoli nenulový polynom v

C

nejmenšího stupně

s

. Nechť

v \in C

. Vydělíme se zbytkem (pro jednoduchost v celém okruhu

ℤ [x]

v = a \cdot g + r, st r < s

To samé platí i ve faktorokruhu. Z toho máme

r = v - a g \in C

Z toho plyne, že

r = 0

, neboli

g | v

. Zároveň už víme, že

a \cdot g \in C

pro každé

a

, čímž je dokázán první bod věty. Druhý bod plyne z toho, že zapíšeme-li

v = a \cdot g

, dostáváme tím koeficienty pro lineární kombinaci polynomů

z^{i} g, i = 0, \dots, n - s - 1

, tudíž z těchto polynomů dokážeme nakombinovat jakýkoli polynom z

C

. Zřejmě jsou také lineárně nezávislé, protože těžko nějaký z nich nakombinujeme z ostatních, když mají různé stupně. Zároveň z předpokladu

\dim C = k

plyne, že jich musí být

k

, tedy

s = n - k

. Zbývá třetí tvrzení, takže budeme zase dělit se zbytkem:

x^{n} - 1 = h g + r, st r < s

Ve faktorokruhu to znamená

0 = h g + r

Z toho naprosto analogicky jako předtím plyne

r = 0

, což v původním okruhu znamená

r = α (x^{n} - 1), α \in ℤ

. No a zřejmě

α = 0

Definice. Polynomy

g

h

z předchozí věty jsou generující polynom a kontrolní polynom kódu

C

V důsledku předchozí věty se dá určit, kolik existuje cyklických kódů dané délky. Například $x^{5} - 1 = (x - 1) (x^{4} + x^{3} + x^{2} + x + 1)$ , kde oba polynomy na pravé straně jsou ireducibilní, takže existují jen dva cyklické kódy délky 5 (plus dva triviální). Tudíž by nás zajímalo obecně, na co se rozloží $x^{n} - 1$ , a to v nějakém obecném tělese se stejným počtem prvků jako $ℤ_{2} [x] ╱ (x^{n} - 1)$ . Ukazuje se, že to vyjde hezčeji, když místo něj budeme faktorizovat $x^{n + 1} - x$ .

Definice. Nechť

b \in ℤ_{2} [x] ╱ q

, kde

q

je ireducibilní polynom. Potom minimální polynom prvku

b

je polynom minimálního stupně s prvky ze

ℤ_{2}

takový, že

f (b) = 0

Věta. Každé

b \in ℤ_{2} [x] ╱ q

má minimální polynom.

Důkaz.

ℤ_{2} [x] ╱ q

je těleso, takže má multiplikativní grupu. Tato grupa je navíc cyklická, protože je to konečné těleso, tudíž existuje nějaké

α \in ℤ_{2} [x] ╱ q

takové, že

ℤ_{2} [x] ╱ q = {α^{k} | k \in ℕ}

. Nechť

b = α^{l}

. Označme

m ≔ \deg q

a dosaďme

b

do polynomu

x^{2^{m} - 1} - 1

{(α^{l})}^{2^{m} - 1} - 1 = {(α^{2^{m} - 1})}^{l} - 1 = 1^{l} - 1 = 0

Druhá rovnost plyne z toho, že multiplikativní grupa má

2^{m} - 1

prvků. Akorát je problém s tím, že pokud

b = 0

, tak to nefunguje. To vyřešíme tím, že vezmeme polynom

x^{2^{m}} - x

, kterýžto má samozřejmě nulu jako kořen. Našli jsme polynom, který má

b

jako kořen, a sice nemusí být minimální, ale to vyřešíme tím, že ho faktorizujeme.

Poznámka. Dokonce jsme našli univerzální polynom, který funguje pro všechna

b

(i když není minimální). To se bude hodit později.

Příklad. Vezměme konečné těleso

ℤ_{2} [x] ╱ (x^{3} + x + 1)

. To má 8 prvků – všechny polynomy stupně menšího než 3. Zkusíme pro každý najít minimální polynom, tedy takový polynom, že když do něj za

x

dosadíme ten daný polynom, dostaneme polynom, který je násobek

x^{3} + x + 1

$b$	minimální polynom $b$
$0$	$x$
$1$	$x + 1$
$z$	$x^{3} + x + 1$
$z + 1$	$x^{3} + x^{2} + 1$
$z^{2}$	$x^{3} + x + 1$
$z^{2} + 1$	?
$z^{2} + z$	?
$z^{2} + z + 1$	?

Vidíme, že to není úplně jednoduché.

Věta. Ke každému prvku

b \in ℤ^{2} [x] ╱ q

existuje právě jeden minimální polynom

f

. Ten je ireducibilní nad

ℤ_{2}

a dělí každý polynom, který má kořen

b

, speciálně také

x^{2^{m}} + x

. Navíc je také kořenem

b^{2}

Důkaz. Nechť

f, \tilde{f}

jsou dva různé minimální polynomy

b

. Potom

f - \tilde{f}

má taky za kořen

b

a má menší stupeň, protože

f

\tilde{f}

začínají jedničkou. Z minimality tudíž plyne

f - \tilde{f} = 0

. Kdyby

f

bylo reducibilní, potom by

b

bylo kořenem jednoho z jeho faktorů, což je spor s minimalitou. Nechť

p

je libovolný polynom, který má za kořen

b

, potom můžeme vydělit se zbytkem

p \div f

, přičemž zbytek má stupeň menší než

f

a taky má

b

za kořen, tudíž je nulový. Nyní si rozepišme, jak vypadá

f^{2}

f {(x)}^{2} = (\sum_{i = 0}^{s} f_{i} x^{i}) = \sum_{i = 0}^{s} f_{i}^{2} x^{2 i} = \sum_{i = 0}^{s} f_{i} x^{2 i} = f (x^{2})

Speciálně

f (b^{2}) = f {(b)}^{2} = 0

. Podle již dokázaného tvrzení musí minimální polynom

b^{2}

dělit

f

a jelikož

f

je ireducibilní, je to jeho minimální polynom.

Věta. Je-li

q \in ℤ_{2} [x]

ireducibilní polynom stupně

m

, potom

x^{2^{m}} - x

je součin všech různých minimálních polynomů prvků

ℤ_{2} [x] ╱ q

Důkaz. Už jsme si dokázali, že každý minimální polynom dělí

x^{2^{m}} - x

. Stačí tedy dokázat, že se tam nevyskytuje víckrát. Nechť

Π

je součin všech různých minimálních polynomů. Víme, že

Π | (x^{2^{m}} - x)

. Zároveň

p

má za kořeny všechny prvky tělesa, kterých je

2^{m}

, tudíž

\deg Π \geq 2^{m}

, z čehož plyne

Π = x^{2^{m}} - x

Věta. Nechť

b \in ℤ_{2} [x] ╱ q

α

ne nejmenší kladné číslo takové, že

b^{2^{α}} = b

. Potom minimální polynom

b

f ≔ \prod_{i = 0}^{α - 1} (x - b^{2^{i}})

Důkaz. Víme, že minimální polynom

b

má také za kořen

b^{2}

, tudíž i

b^{4}

a tak dále až do

b^{2^{α - 1}}

, tudíž jeho stupeň je alespoň stupeň

f

. Víme tedy, že pokud

f

je vůbec platný polynom, potom už musí být minimální k

b

(protože

b

je jeho kořen). K tomu musíme ověřit, že koeficienty

f

jsou ze

ℤ_{2}

. Máme

f {(x)}^{2} = \sum_{i = 0}^{α - 1} (x^{2} - b^{2^{i + 1}}) = f (x^{2})

Pokud si to rozepíšeme a porovnáme po členech, máme

\forall i : a_{i} = a_{i}^{2}

, z čehož plyne

a_{i} \in ℤ_{2}

Takže teď umíme rozložit $x^{2^{m}} - x$ , ale my chceme obecně $x^{n} - 1$ . Co s tím? Z technických důvodů budeme s újmou na obecnosti uvažovat jen lichá $n$ .

Věta. Nechť

n \in ℕ

je liché. Potom existují

r, m \in ℕ

taková, že

n \cdot r = 2^{m} - 1

Důkaz. Z Eulerovy-Fermatovy věty máme

2^{φ (n)} \equiv 1 (m o d n)

Z toho přímo plyne tvrzení věty.

Vezměme tedy taková $r, m$ . Z algebry nějak víme, že existuje ireducibilní polynom $q$ stupně $m$ (tudíž $ℤ_{2} [x] ╱ q$ je těleso) a $β \in ℤ_{2} [x] ╱ q$ takové, že $β^{i}$ jsou různé pro $i = 1, \dots, 2^{m} - 1$ , přičemž pro $i = 2^{m} = 1$ je to rovno $1$ .

Polynomy $α_{i} ≔ β^{i r}$ pro $i = 1, \dots, n$ jsou různé kořeny rovnice $x^{n} = 1$ . Z toho plyne, že to musí být všechny kořeny. ??? $x^{n} - 1$ je součin minimálních polynomů prvků $b \in ℤ_{2} [x] ╱ q$ , kde řád $b$ dělí $n$ .

Věta. Nechť

C

je cyklický kód liché délky

n

. Potom

g (x)

je součin minimálních polynomů k prvkům

α^{i_{1}}, \dots, α^{i_{s}}

, kde

α

je prvek řádu

n

v nějakém tělese

ℤ_{2} [x] ╱ q

Důkaz. Viz výše.

Definice.

α^{i_{1}}, \dots, α^{i_{s}}

z předchozí věty jsou generující kořeny kódu

C

Teď už máme nějaký cyklický kód a chceme vymyslet způsob, jak zakódovat nějakou informaci. Mějme nějaké datové slovo $d_{0} \dots d_{k - 1}$ . Definujme polynom $a ≔ \sum_{i = 0}^{k - 1} d_{i} x^{i}$ . Jako kódové slovo stačí vzít $a \cdot g$ . To plyne z toho, že tyto výsledky pro různá $a$ právě dávají celý kód.

Ovšem pro pohodlnost by bylo hezké kód přepermutovat, aby byl systematický. To sice umíme pro obecný lineární kód, ale není zaručené, že tím vznikne cyklický kód. Definujme si tentokrát $a ≔ \sum_{i = 0}^{n - 1} d_{i} x^{n - 1 - i}$ . Vydělíme se zbytkem $a = n \overset{ˇ}{e} c o \cdot g + r$ . Jako kódové slovo vezmeme $a - r$ . Jelikož $r$ je menšího stupně než $g$ , nepoškodíme si tím bity na konci, ve kterých je zpráva. Tudíž máme kód, který je „obráceně“ systematický. V případě potřeby ho samozřejmě můžeme obrátit a pořád bude cyklický.

Zajímalo by nás, jestli je Hammingův kóď ekvivalentní cyklickému kódu. Ukazuje se, že pro obecné $q$ nemusí být, ale pro binární Hammingův kód to dokážeme. Máme tedy nějaké $n$ , které se rovná $2^{m} - 1$ , a chceme najít cyklický kód se stejnými parametry jako Hammingův, tudíž dimenze $n - m$ .

BCH kódy

Definice. BCH kód je kód v tělese

𝔽_{2^{m}} ≃ ℤ_{2} [x] ╱ q

generovaný kořeny

α

α^{3}

, kde

α

je prvek řádu

n

Příklad. Méjme

n ≔ 15, m ≔ 4

. Vezmeme ireducibilní polynom

q ≔ x^{4} + x + 1

. Prvky

𝔽_{16}

jsou všechny polynomy stupně nanejvýš

3

, to jest

𝔽_{16} = {0,1, z, z + 1, z^{2}, z^{2} + 1, z^{2} + z, z^{2} + z + 1, z^{3}, z^{3} + 1, z^{3} + z, z^{3} + z + 1, z^{3} + z^{2}, z^{3} + z^{2} + 1, z^{3} + z^{2} + z, z^{3} + z^{2} + z + 1}

Jako generátor můžeme vzít například

α ≔ z

Mocnina	Hodnota	Minimální polynom
$α^{0}$	$1$	$x + 1$
$α^{1}$	$z$	$x^{4} + x + 1$
$α^{2}$	$z^{2}$	$x^{4} + x + 1$
$α^{3}$	$z^{3}$	$x^{4} + x^{3} + x^{2} + x + 1$
$α^{4}$	$z + 1$	$x^{4} + x + 1$
$α^{5}$	$z^{2} + z$	$x^{2} + x + 1$
$α^{6}$	$z^{3} + z^{2}$	$x^{4} + x^{3} + x^{2} + x + 1$
$α^{7}$	$z^{3} + z + 1$
$α^{8}$	$z^{2} + 1$	$x^{4} + x + 1$
$α^{9}$	$z^{3} + z$
$α^{10}$	$z^{2} + z + 1$	$x^{2} + x + 1$
$α^{11}$	$z^{3} + z^{2} + z$
$α^{12}$	$z^{3} + z^{2} + z + 1$	$x^{4} + x^{3} + x^{2} + x + 1$
$α^{13}$	$z^{3} + z^{2} + 1$
$α^{14}$	$z^{3} + 1$

Protože chceme BCH kód, pro generující polynom vezmeme minimální polynomy pro

α

α^{3}

, tedy máme

g = (x^{4} + x^{3} + x^{2} + x + 1) (x^{4} + x + 1)

Jelikož zároveň

n = 14

, kontrolní polynom

h

má stupeň

6

, z čehož plyne, že máme

2^{7}

kódových slov. Teď by nás zajímalo, jaká je minimální vzdálenost. Spočteme si

g = x^{8} + x^{7} + x^{6} + x^{4} + 1

Z toho plyne, že existuje kódové slovo váhy

5

, tudíž

d \leq 5

. Pro dané slovo

w

vyjádřené jako polynom platí

w \in C ⟺ w (α) = 0 \land w (α^{3}) = 0

Na základě tohoto poznatku si definujeme něco jako kontrolní matici tak, aby platilo

w \in C ⟺ \tilde{H} w = 0

\tilde{H} ≔ (\begin{array}{ccccccccc} 1 & α & α^{2} & α^{3} & α^{4} & α^{5} & α^{6} & \dots & α^{14} \\ 1 & α^{3} & α^{6} & α^{9} & α^{12} & 1 & α^{3} & \dots & α^{12} \end{array})

Každý prvek matice si vyjádříme jako čtyřsložkový sloupcový vektor odpovídající koeficientům u polynomu:

H ≔ (\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 1 & \dots & 1 \\ 0 & 1 & 0 & 0 & 1 & \dots & 0 \\ 0 & 0 & 1 & 0 & 0 & \dots & 0 \\ 0 & 0 & 0 & 1 & 0 & \dots & 1 \\ 1 & 0 & 0 & 0 & 1 & \dots & 1 \\ 0 & 0 & 0 & 1 & 1 & \dots & 1 \\ 0 & 0 & 1 & 0 & 1 & \dots & 1 \\ 0 & 1 & 1 & 1 & 1 & \dots & 1 \end{array})

To už je skutečná kontrolní matice. Mějme nějaké slovo

u

, u kterého se staly dvě chyby, tudíž je ve vzdálenosti

2

od nějakého kódového slova:

u = w + e ≔ w + x^{i} + x^{j}, w \in C, i \neq j

. Potom

H u = H e = H x^{i} + H x^{j}

. Zároveň

H u = (\begin{array}{c} u (α) \\ u (α^{3}) \end{array}) = (\begin{array}{c} e (α) \\ e (α^{3}) \end{array}) = (\begin{array}{c} α^{i} + α^{j} \\ α^{3 i} + α^{3 j} \end{array}) ≕ (\begin{array}{c} s_{1} \\ s_{3} \end{array})

Jelikož

α

je generátor, máme

α^{i} \neq α^{j}

a tedy

s_{1} \neq 0

. Z binomické věty

s_{1}^{3} = α^{3 i} + α^{3 j} + α^{2 i} α^{j} + α^{i} α^{2 j} = s_{3} + α^{i} α^{j} s_{1}

α^{i} α^{j} = s_{3} s_{1}^{- 1} + s_{1}^{2}

Zavedeme-li ještě další formální proměnnou

λ

, můžeme psát

(λ + α^{i}) (λ + α^{j}) = λ^{2} + (α^{i} + α^{j}) λ + α^{i} α^{j} = λ^{2} + s_{1} λ + s_{3} s_{1}^{- 1} + s_{1}^{2}

Tudíž pokud umíme řešit takovouto kvadratickou rovnici, můžeme si snadno dopočíst, kde se staly chyby. Uvažujme ještě případ, kdy nastala jen jedna chyba, tedy

e = x^{i}

. Potom máme

s_{1} = α^{i}, s_{3} = α^{3 i}

a dostaneme přesně tu samou rovnici, akorát s nulou místo

x^{j}

. Tedy i tento případ dokážeme detekovat. Celkově umíme rozpoznat a opravit až dvě chyby, tudíž

d = 5

Věta (Davenport). Nechť

𝔽_{q}

je konečné těleso s

q = p^{m}

prvky (tedy

ℤ_{p} ╱ r

, kde

r

je ireducibilní polynom stupně

m

). Potom existuje primitivní prvek

β \in 𝔽_{q}

takový, že

{β^{p^{i}} | i = 0, \dots, m - 1}

je báze

𝔽_{q}

jakožto lineárního prostoru nad

ℤ_{p}

Poznámka. Toto

β

vůbec nesouvisí s generátorem cyklické grupy

𝔽_{q}

Příklad. Pro

𝔽_{16} = ℤ_{2} ╱ (x^{4} + x + 1)

vezměme

β ≔ z^{3}

. Máme

β^{2} = {(z^{3})}^{2} mod (z^{4} + z + 1) = z^{3} + z^{2}

β^{4} = {(z^{3} + z^{2})}^{2} mod (z^{4} + z + 1) = z^{3} + z^{2} + z + 1

β^{8} = {(z^{3} + z^{2} + z + 1)}^{2} mod (z^{4} + z + 1) = z^{3} + z

Ve vektorové podobě máme množinu

{(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \end{array}), (\begin{array}{c} 0 \\ 0 \\ 1 \\ 1 \end{array}), (\begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \end{array}), (\begin{array}{c} 0 \\ 1 \\ 0 \\ 1 \end{array})}

Snadno ověříme, že je to báze.

Lemma. Mějme kvadratickou rovnici tvaru

a λ^{2} + b λ + c, a, b \neq 0

. Potom bez újmy na obecnosti stačí řešit rovnici tvaru

μ^{2} + μ + d

Důkaz. Použijme substituce

d ≔ \frac{c a}{b^{2}}

μ ≔ \frac{a}{b} λ

. Potom rovnice pro

μ

má tvar

\frac{a^{2}}{b^{2}} λ^{2} + \frac{a}{b} λ + \frac{c a}{b^{2}}

Vynásobením

\frac{b^{2}}{a}

dostaneme původní rovnici.

Věta. Mějme v tělese

𝔽_{2^{m}}

kvadratickou rovnici

a λ^{2} + c = 0, a \neq 0

, kterou můžeme substitucí

d ≔ \frac{c}{a}

převést na tvar

λ^{2} + d = 0

. Nechť

d = \sum_{i = 0}^{m - 1} d_{i} β^{2^{i}}

, kde

β

je primitivní prvek z Davenportovy věty. Potom řešení rovnice je

λ = \sum_{i = 0}^{m - 2} d_{i + 1} β^{2^{i}} + d_{0} β^{2^{m - 1}}

Důkaz.

λ^{2} = \sum_{i = 0}^{m - 2} {(d_{i + 1})}^{2} {(β^{2^{i}})}^{2} + d_{0}^{2} {(β^{2^{m - 1}})}^{2} = \sum_{i = 0}^{m - 2} d_{i + 1} β^{2^{i + 1}} + d_{0} β = d

Důsledek. V konečném tělese charakteristiky 2 má každý prvek odmocninu.

Věta. Májme v tělese

𝔽_{2^{m}}

kvadratickou rovnici

μ^{2} + μ + d = 0

. Nechť

d = \sum_{i = 0}^{m - 1} d_{i} β^{2^{i}}

, kde

β

je primitivní prvek z Davenportovy věty. Potom rovnice má řešení, právě když

\sum_{i = 0}^{m - 1} d_{i} \equiv 0 (m o d 2)

V takovém případě jsou dvě řešení ve tvaru

μ^{(k)} ≔ \sum_{i = 0}^{m - 1} (k + \sum_{j = 1}^{i} d_{j}) β^{2^{i}}, k \in {0,1}

Důkaz.

(\Rightarrow)

Nechť

μ = \sum_{i = 0}^{m - 1} μ_{i} β^{2^{i}}

je nějaké řešení rovnice. Potom

d = μ^{2} + μ = μ_{m - 1} β + \sum_{i = 1}^{m - 1} μ_{i - 1} β^{2^{i}} + \sum_{i = 0}^{m - 1} μ_{i} β^{2^{i}}

Porovnáním po koeficientech a sečtením máme

\sum_{i = 0}^{m - 1} d_{i} = 2 \sum_{i = 0}^{m - 1} μ_{i} \equiv 0 (m o d 2)

(\Leftarrow)

Pro výraz

{(μ^{(k)})}^{2} + μ^{(k)}

spočteme koeficient u

β^{2^{i}}

. Pro

μ^{2}

to bude ten, který byl původně u

β^{2^{i - 1}}

(nebo u

β^{m - 1}

, pokud

i = 0

), takže máme pro

i > 0

k + \sum_{j = 1}^{i - 1} d_{j} + k + \sum_{j = 1}^{i} d_{j} = d_{i}

nebo pro

i = 0

k + \sum_{j = 1}^{m - 1} d_{j} + k = d_{0}

Když jsme jako generátor vzali $α$ , dostali jsme Hammingův kód, který umí opravovat jednu chybu. S generátory $α, α^{3}$ jsme dostali kód, který umí opravovat dvě chyby. Co kdybychom zkusili přidávat další liché mocniny?

Definice. Nechť

a_{1}, \dots, a_{d}

jsou prvky nějakého tělesa. Potom Vandermondova matice je

V (a_{1}, \dots, a_{d}) ≔ (\begin{array}{ccc} a_{1}^{0} & \dots & a_{d}^{0} \\ ⋮ & ⋱ & ⋮ \\ a_{1}^{d - 1} & \dots & a_{d}^{d - 1} \end{array})

Lemma.

\det V (a_{1}, \dots, a_{d}) = \det V (a_{1}, \dots, a_{d - 1}) \cdot \prod_{i = 1}^{d - 1} (a_{d} - a_{i})

Důkaz. Za domácí úkol.

Věta.

\det V (a_{1}, \dots, a_{d}) = \prod_{k = 1}^{d} \prod_{i = 1}^{k - 1} (a_{k} - a_{i})

Důkaz. Indukcí z předchozího lemmatu.

Definice. Nechť

d, m \in ℕ

α

je prvek řádu

n

v tělese

𝔽_{2^{m}}

. BCH kód pro vzdálenost

d

je cyklický kód délky

n

s generujícími kořeny

α, α^{2}, \dots, α^{d - 1}

Poznámka. Pro

d = 5

bychom dostali čtyři generátory

α, α^{2}, α^{3}, α^{4}

, ale jelikož generující polynomy pro

α^{2}, α^{4}

jsou stejné jako pro

α, α^{2}

, minimální polynom vyjde stejně, jako kdybychom vzali jenom

α, α^{3}

Věta. BCH kód pro vzdálenost

2 t + 1

má skutečně vzdálenost alespoň

2 t + t

, tedy spravuje

t

chyb.

Důkaz. Kontrolní matice pro BCH kód je z definice

H = (\begin{array}{cccccc} 1 & α & α^{2} & α^{3} & \dots & α^{n - 1} \\ 1 & α^{2} & α^{4} & α^{6} & \dots & α^{2 n - 2} \\ 1 & α^{3} & α^{6} & α^{9} & \dots & α^{3 n - 3} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & α^{2 t} & α^{4 t} & α^{6 t} & \dots & α^{2 t n - 2 t} \end{array})

Podle nějaké dávné věty stačí dokázat, že každých

2 t

sloupců je lineárně nezávislých. Vyberme nějaké sloupce:

M ≔ (\begin{array}{ccc} α^{i_{1}} & \dots & α^{i_{2 t}} \\ α^{2 i_{1}} & \dots & α^{2 i_{2 t}} \\ ⋮ & ⋱ & ⋮ \\ α^{2 t i_{1}} & \dots & α^{2 t i_{2 t}} \end{array})

To je skoro Vandermondova matice, akorát nezačíná jedničkami, takže při počítání determinantu musíme nejdřív vytknout:

\det M = (\prod_{j = 1}^{2 t} α^{i_{j}}) \cdot \det (\begin{array}{ccc} 1 & \dots & 1 \\ α^{i_{1}} & \dots & α^{i_{2 t}} \\ ⋮ & ⋱ & ⋮ \\ α^{(2 t - 1) i_{1}} & \dots & α^{(2 t - 1) i_{2 t}} \end{array}) = (\prod_{j = 1}^{2 t} α^{i_{j}}) \cdot \prod_{k = 1}^{2 t} \prod_{j = 1}^{k - 1} (α^{i_{k}} - α^{i_{j}}) \neq 0

Teď je otázkou, jak nějak efektivně dekódovat BCH kód. Dejme tomu, že bylo vysláno slovo $w \in C$ a přijato slovo $v = w + e, wt (e) \leq p$ . Pomocí kontrolní matice snadno spočteme syndrom ${(s_{1}, \dots, s_{2 t})}^{T} ≔ H e = H v$ . Je-li $ℐ$ množina pozic, na kterých se staly chyby, potom z definice $H$ platí

s_{k} = \sum_{i \in ℐ} α^{k i}

Takže je snadné spočítat syndromy z indexů, ale my chceme udělat přesný opak – známe syndromy a máme určit indexy. Pro $ℐ = {i_{1}, \dots, i_{p}}$ si označme $a_{j} ≔ α^{i_{j}}, j \in \hat{p}$ a definujme lokátor:

f ≔ \prod_{j = 1}^{p} (1 - a_{p} x)

Pokud najdeme kořeny lokátoru $x_{1}, \dots, x_{p}$ , můžeme spočíst $a_{j} = x_{j}^{- 1}$ a to si potom dohledáme v nějaké tabulce, čímž zjistíme $i_{j}$ . Takže úplně stačí najít kořeny lokátoru, který ale samozřejmě neznáme. Jen víme, že má nějaké koeficienty:

f = \sum_{j = 0}^{p} f_{j} x^{j}

Zřejmě $f_{0} = 1$ . Spočteme si z obou tvarů formální derivaci:

f^{'} = \sum_{j = 1}^{p} j f_{j} x^{j - 1} = \sum_{j = 1}^{⌊ \frac{p}{2} ⌋} f_{2 j + 1} x^{2 j}

f^{'} = \sum_{j = 1}^{p} \frac{- a_{j}}{1 - a_{j} x} f = f \cdot \sum_{j = 1}^{p} (- a_{j} \sum_{k = 0}^{\infty} {(a_{j} - x)}^{k}) = f \cdot \sum_{k = 1}^{\infty} x^{k - 1} \sum_{j = 1}^{p} a_{j}^{k} = f \cdot \sum_{k = 1}^{\infty} x^{k - 1} s_{k}

Porovnáme obě vyjádření:

\sum_{j = 1}^{⌊ \frac{p}{2} ⌋} f_{2 j + 1} x^{2 j} = (\sum_{j = 0}^{p} f_{j} x^{j}) \cdot \sum_{k = 1}^{\infty} x^{k - 1} s_{k}

\begin{aligned} f_{1} & = s_{1} \\ 0 & = s_{2} + f_{1} s_{1} \\ f_{3} & = s_{3} + f_{1} s_{2} + f_{2} s_{1} \\ 0 & = s_{4} + f_{1} s_{3} + f_{2} s_{2} + f_{3} s_{1} \\ f_{5} & = s_{5} + f_{1} s_{4} + f_{2} s_{3} + f_{3} s_{2} + f_{4} s_{1} \\ ⋮ \\ 0 & = s_{2 p - 1} + s_{2 p - 2} s_{1} + \dots + s_{p - 1} f_{p} \end{aligned}

Zapíšeme si to do matičkové podoby:

(\begin{array}{c} s_{1} \\ s_{3} \\ s_{5} \\ ⋮ \\ s_{2 p - 1} \end{array}) = (\begin{array}{cccccccc} 1 & 0 & 0 & 0 & 0 & 0 & \dots & 0 \\ s_{2} & s_{1} & 1 & 0 & 0 & 0 & \dots & 0 \\ s_{4} & s_{3} & s_{2} & s_{1} & 1 & 0 & \dots & 0 \\ ⋮ & ⋱ & ⋮ \\ s_{2 p - 2} & s_{2 p - 3} & \dots & s_{p - 1} \end{array}) = (\begin{array}{c} f_{1} \\ f_{2} \\ f_{3} \\ ⋮ \\ f_{p} \end{array})

Akorát je tu trochu problém, že neznáme $p$ . Dá se dokázat, což tady dělat nebudeme, že pokud matici pro dané $p$ označíme $M_{p}$ , potom pro to správné $p$ je $M_{p}$ regulární, $M_{p + 1}$ taky a všechny další už ne. Takže podle toho to už najdeme.

Plotkinova mez

Definice. Pro

n, d \in ℕ

označme

A (n, d)

maximální

M

takové, že existuje

(n, M, d)

kód nad

ℤ_{2}

Poznámka. Teď už nepožadujeme, aby kód byl lineární!

Lemma. Pro každé

n, r \in ℕ

A (n, 2 r - 1) = A (n + 1,2 r)

Důkaz. Nechť

C

(n, M, 2 r - 1)

-kód, kde

M ≔ A (n, 2 r - 1)

je maximální možné. Definujme kód, který je stejný, ale s přidaným paritním bitem:

C^{+} ≔ {w_{1} \dots w_{n + 1} | w_{0} \dots w_{n} \in C, w_{n + 1} ≔ \sum_{i = 1}^{n} w_{i}}

Dokážeme, že

C^{+}

(n + 1, M, 2 r)

-kód. Nechť

u^{+}, w^{+} \in C^{+}

. Zjevně

dist (u, w) \geq 2 r - 1

. Předpokládejme pro spor, že platí rovnost. V takovém případě mají nutně

u, w

stejný paritní bit a liší se v

2 r - 1

„normálních“ bitech, což je liché číslo. Ale to je blbost. Naopak, máme-li

(n + 1, M^{'}, 2 r)

-kód, kde

M^{'} ≔ A (n + 1,2 r)

, umazáním poslední souřadnice z něj vyrobíme

(n, M, 2 r - 1)

-kód.

Lemma. Pro každé

n, d \in ℕ

A (n, d) \leq 2 A (n - 1, d)

Důkaz. Nechť

C

(n, M, d)

-kód, kde

M ≔ A (n, d)

. Pro

i \in {0,1}

definujme

C_{i} ≔ {w_{1} \dots w_{n - 1} | w_{1} \dots w_{n} i \in C}

Jeden z

C_{0}, C_{1}

zjevně musí mít velikost aspoň

\frac{M}{2}

, takže je to alespoň

(n - 1, \frac{M}{2}, d)

-kód.

Lemma. Nechť

n, d \in ℕ, 2 d > n

. Potom

A (n, d) \leq 2 ⌊ \frac{d}{2 d - n} ⌋

Důkaz. Nechť

C

(n, M, d)

-kód, kde

M ≔ A (n, d)

. Zjevně platí

\sum_{u, w \in C} dist (u, w) \geq M (M - 1) d

Pro každé

j = 1, \dots, n

označme

α_{j}

počet kódových slov, která mají na

j

-tém bitu jedničku. Potom počet dvojic slov, která se v

j

-tém bitu liší, je

α_{j} (M - α_{j})

, z čehož plyne

\sum_{u, w \in C} dist (u, w) = 2 \sum_{j = 1}^{n} α_{j} (M - α_{j})

Porovnáním a vydělením dvěma dostaneme

\frac{M (M - 1)}{2} d \leq \sum_{j = 1}^{n} α_{j} (M - α_{j})

Snadno ověříme (třeba pomocí derivace), že

α_{j} (M - α_{j}) \leq ⌊ \frac{M}{2} ⌋ ⌈ \frac{M}{2} ⌉

, takže máme

\frac{M (M - 1)}{2} d \leq n ⌊ \frac{M}{2} ⌋ ⌈ \frac{M}{2} ⌉

Pro

M

sudé máme

\frac{M (M - 1)}{2} d \leq \frac{M^{2}}{4} n

což snadno upravíme do tvaru

\frac{M}{2} \leq \frac{d}{2 d - n}

Jelikož

\frac{M}{2}

je sudé číslo, můžeme pravou stranu bez obav zabalit do dolní celé části. Vynásobením dvěma dostaneme kýženou nerovnost. A co pro liché

M

\frac{M (M - 1)}{2} d \leq \frac{M^{2} - 1}{4} n

Úpravami dostaneme

M \leq \frac{n}{2 d - n} = \frac{2 d}{2 d - n} - 1

Jelikož

M \in ℕ

, můžeme psát

M \leq ⌊ \frac{2 d}{2 d - n} ⌋ - 1

Snadno ověříme, že pro libovolné

x \in ℝ

⌊ 2 x ⌋ \leq 2 ⌊ x ⌋ + 1

. Aplikací tohoto tvrzení dostaneme znění věty.

Věta (Plotkinova mez). Nechť

n, d \in ℕ

. Potom:

Je-li $d$ sudé a $2 d > n$ , potom $A (n, d) \leq 2 ⌊ \frac{d}{2 d - n} ⌋$ .
Je-li $d$ sudé a $2 d = n$ , potom $A (n, d) \leq 4 d$ .
Je-li $d$ liché a $2 d + 1 > n$ , potom $A (n, d) \leq 2 ⌊ \frac{d + 1}{2 d + 1 - n} ⌋$ .
Je-li $d$ liché a $2 d + 1 = n$ , potom $A (n, d) \leq 4 d + 4$ .

Důkaz. Použitím předchozích tří lemmat:

Již dokázáno.
$A (2 d, d) \leq 2 A (2 d - 1, d) \leq 4 ⌊ \frac{d}{2 d - (2 d - 1)} ⌋ = 4 d$
$A (n, d) = A (n + 1, d + 1) \leq 2 ⌊ \frac{d + 1}{2 (d + 1) - (n + 1)} ⌋ = 2 ⌊ \frac{d + 1}{2 d + 1 - n} ⌋$
$A (2 d + 1, d) = A (2 d + 2, d + 1) \leq 4 (d + 1)$

Definice. Hadamardova matice je matice

H \in {\pm 1}^{n \times n}

taková, že

H H^{T} = n I

Poznámka. Označíme-li

v_{1}, \dots, v_{n}

sloupce

H

, potom

v_{i} v_{j}^{T} = n δ_{i, j}

, neboli řádky musí být na sebe kolmé. Jinými slovy, každé dva řádky se musí lišit ve stejném počtu čísel jako shodovat.

Příklad. Pro

n = 1

(\begin{array}{c} 1 \end{array})

Hadamardova matice. Pro

n = 2

(\begin{array}{cc} 1 & 1 \\ - 1 & 1 \end{array})

Hadamardova matice.

Poznámka. Existuje domněnka, že Hadamardova matice existuje pro každé

n = 4 k, k \in ℕ

Lemma. Je-li

n \geq 3

a existuje Hadamardova matice velikosi

n

, potom

n

je násobek

4

Důkaz. Zjevně pokud v Hadamardově matici vynásobíme nějaký řádek nebo sloupec

- 1

, pořád to bude Hadamardova matice. Vynásobme všechny sloupce tak, aby v prvním řádku byly samé jedničky. Označme:

a ≔ p o \overset{ˇ}{c} e t s l o u p c \overset{˚}{u} z a \overset{ˇ}{c} \overset{ˊ}{ı} n a j \overset{ˊ}{ı} c \overset{ˊ}{ı} c h {(\begin{array}{ccc} 1 & 1 & 1 \end{array})}^{T}

b ≔ p o \overset{ˇ}{c} e t s l o u p c \overset{˚}{u} z a \overset{ˇ}{c} \overset{ˊ}{ı} n a j \overset{ˊ}{ı} c \overset{ˊ}{ı} c h {(\begin{array}{ccc} 1 & 1 & - 1 \end{array})}^{T}

c ≔ p o \overset{ˇ}{c} e t s l o u p c \overset{˚}{u} z a \overset{ˇ}{c} \overset{ˊ}{ı} n a j \overset{ˊ}{ı} c \overset{ˊ}{ı} c h {(\begin{array}{ccc} 1 & - 1 & 1 \end{array})}^{T}

d ≔ p o \overset{ˇ}{c} e t s l o u p c \overset{˚}{u} z a \overset{ˇ}{c} \overset{ˊ}{ı} n a j \overset{ˊ}{ı} c \overset{ˊ}{ı} c h {(\begin{array}{ccc} 1 & - 1 & - 1 \end{array})}^{T}

Zjevně platí

a + b + c + d = n

. Z kolmosti prvního a druhého řádku plyne

a + b - c - d = 0

. Z kolmosti prvního a třetího řádku plyne

a - b + c - d = 0

. Z kolmosti druhého a třetího řádku plyne

a - b - c + d = 0

. Sečtením těchto rovností dostaneme

4 a = n

Definice. Nechť

A \in ℝ^{n \times n}, B \in ℝ^{s \times s}

jsou čtvercové matice. Potom jejich tenzorový součin je

A \otimes B ≔ (\begin{array}{ccc} A_{1,1} B & \dots & A_{1, n} B \\ ⋮ & ⋱ & ⋮ \\ A_{n, 1} B & \dots & A_{n, n} B \end{array})

Poznámka. Na TA jsme tomu říkali Kroneckerův součin.

Lemma.

{(A \otimes B)}^{T} = A^{T} \otimes B^{T}

Důkaz. Rozepsáním.

Lemma.

(A \otimes B) (C \otimes D) = A C \otimes B D

Důkaz. Na TA jsme to měli za domácí úkol.

Věta (Sylvesterova konstrukce). Jsou-li

H_{n}

H_{m}

Hadamardovy matice, potom

H_{n} \otimes H_{m}

je Hadamardova matice.

Důkaz. Zřejmě

H_{n} \otimes H_{m} \in {\pm 1}^{m n \times m n}

. Podle předchozích lemmátek máme

(H_{n} \otimes H_{m}) {(H_{n} \otimes H_{m})}^{T} = (H_{n} \otimes H_{m}) (H_{n}^{T} \otimes H_{m}^{T}) = H_{n} H_{n}^{T} \otimes H_{m} H_{m}^{T} = n I_{n} \otimes m I_{m} = m n I_{m n}

Důsledek. Pro každé

n \in ℕ_{0}

existuje Hadamardova matice velikosti

2^{n} \times 2^{n}

Důkaz. Indukcí: Začneme s maticí

(\begin{array}{c} 1 \end{array})

a budeme ji postupně tenzořit

(\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array})

Definice. Nechť

C_{1}

(n_{1}, M_{1}, d_{1})

-kód a

C_{2}

(n_{2}, M_{2}, d_{2})

-kód. Potom

C_{1} \oplus︎ C_{2}

(n_{1} + n_{2}, \min {M_{1}, M_{2}}, d_{1} + d_{2})

-kód, který vytvoříme tak, že nějak seřadíme slova v obou kódech a spojíme ta na stejných indexech (pokud má jeden víc slov, přebytečná zahodíme).

Definice. Nechť

C

(n, M, d)

-kód a

b \in ℕ

. Potom

b C ≔ \underset{n \times}{\underset{⏟}{C \oplus︎ \dots \oplus︎ C}}

(b n, M, b d)

-kód.

Vytvoříme-li kód $A_{n}$ , jehož kódová slova budou řádky Hadamardovy matice velikosti $n \times n$ (s přemapováním $1 \mapsto 0, - 1 \mapsto 1$ ), zjevně to bude $(n, n, \frac{n}{2})$ -kód.

Navíc pokud všechny řádky a sloupce vynásobíme tak, aby začínaly jedničkou, můžeme první sloupec beze strachu smazat a dostaneme tím $(n - 1, n, \frac{n}{2})$ -kód $𝒜_{n}$ , který navíc obsahuje nulové slovo.

A pokud z něj vezmeme jen slova začínající nulou a tyto nuly smažeme, dostaneme $(n - 2, \frac{n}{2}, \frac{n}{2})$ -kód $𝒜_{n}^{'}$ (to, že má přesně $\frac{n}{2}$ slov, plyne z toho, že druhý smazaný sloupec byl kolmý na první smazaný sloupec).

Teď se vraťme k $A_{n}$ a vytvořme kód $B_{n}$ tím, že přidáme ke všem slovům jejich negaci. S trochou přemýšlení ověříme, že je to $(n, 2 n, \frac{n}{2})$ -kód.

Věta (Levenshteinova, napsaná podle Volce). Plotkin s „=“, když Hadamard dá.

Věta (Levenshteinova, napsaná normálně). Nechť

n, d \in ℕ

. Potom

Je-li $d$ sudé a $2 d > n$ a platí Hadamardova domněnka, potom $A (n, d) = 2 ⌊ \frac{d}{2 d - n} ⌋$ .
Je-li $d$ sudé, $2 d = n$ a existuje Hadamardova matice velikosti $n \times n$ , potom $A (n, d) = 4 d$ .
Je-li $d$ liché a $2 d + 1 > n$ a platí Hadamardova domněnka, potom $A (n, d) = 2 ⌊ \frac{d + 1}{2 d + 1 - n} ⌋$ .
Je-li $d$ liché a $2 d + 1 = n$ a existuje Hadamardova matice velikosti $(n + 1) \times (n + 1)$ , potom $A (n, d) = 4 d + 4$ .

Důkaz. Podle jistého lemmatu víme, že stačí uvažovat

d

sudé. Pro

n = 2 d

z kódu

B_{n}

vidíme, že

A (n, d) \geq 4 d

a podle Plotkinovy meze platí rovnost. Nechť

n < 2 d

. Definujme

k ≔ ⌊ \frac{d}{2 d - n} ⌋

. Označme

a ≔ d mod (2 d - n), b ≔ (2 d - n) - a

. Potom z definice dolní celé části platí

k = \frac{d - a}{2 d - n}, k + 1 = \frac{d + b}{2 d - n}

Odečtením téchto rovností dostaneme

1 = \frac{a + b}{2 d - 1} ∴ a + b = 2 d - n

Vynásobením první rovností máme

k (a + b) = d - a

Trochu si upravíme definici

b

a dosadíme do ní tuto rovnost:

n = 2 d - b - a = 2 (d - a) + a - b = 2 k (a + b) + a - b

Ted rozlišíme dva případy:

Je-li $k$ sudé, vezměme kód $b 𝒜_{2 k} \oplus︎ \frac{a}{2} 𝒜_{4 k + 4}^{'}$ . Spočteme si jeho parametry: $n^{*} = b (2 k - 1) + \frac{a}{2} (4 k + 2) = n$ $M^{*} = \min {2 k, \frac{4 k + 4}{2}} = 2 k$ $d^{*} = b \frac{2 k}{2} + \frac{a}{2} \frac{2 k + 2}{2} = d$
Je-li $k$ liché, vezměme kód $\frac{b}{2} 𝒜_{4 k}^{'} \oplus︎ a 𝒜_{2 k + 2}$ . Spočteme si jeho parametry: $n^{*} = \frac{b}{2} (4 k - 2) + a (2 k + 1) = n$ $M^{*} = \min {\frac{4 k}{2}, 2 k + 2} = 2 k$ $d^{*} = \frac{b}{2} \frac{4 k}{2} + a \frac{2 k + 2}{2} = d$