10
правок
Изменения
Новая страница: «== Граница Хемминга == Для составления верхних и нижних оценок на параметры кодирования н…»
== Граница Хемминга ==
Для составления верхних и нижних оценок на параметры кодирования нам понадобится понятие шара.
{{Определение
|neat = 1
|definition=
Рассмотрим <tex> B^n </tex>.
Булевым шаром в <tex> B^n </tex> радиуса <tex> r </tex> с центром <tex> x </tex> называется множество <tex> S(x,r) = \{ y : H(x,y) \leqslant r\} </tex>.
}}
{{Определение
|neat = 1
|definition=
Обьёмом шара <tex>S(x,r)</tex> в <tex>B^n</tex> называется его мощность <tex>|S(x,r)|</tex> и обозначается <tex>V(n,r)</tex>.
}}
{{Утверждение
|statement= Обьём шара не зависит от его центра.
|proof=
Заметим, что шар <tex>S(x,r)</tex> всегда можно получить из другого шара <tex>S(y,r)</tex> с помощью "параллельного переноса" на вектор <tex>x\oplus y</tex>, т.е.
<tex> S(x, r) = \{z : z = t \oplus x \oplus y, t \in S(y,r) \} </tex>.
Покажем это.
Необходимо доказать, что <tex>H(x,z) = H(y,t)</tex> при <tex>t = z \oplus (x \oplus y)</tex> и <tex>y = x \oplus (x \oplus y)</tex>.
<tex>H(y,t) = |\{i : y[i] \neq t[i]\}| = |\{i : x[i] \oplus (x[i] \oplus y[i]) \neq z[i] + (x[i] + y[i]) \}|
= |\{ i : x[i] \neq z[i]\}| = H(z,t) </tex>.
}}
Можно переформулировать условие на исправление кодом <tex>k</tex> ошибок в терминах булевых шаров.
{{Лемма
|id=boolean_balls_coding
|statement= Пусть <tex>c:\Sigma \to B^n</tex> — код, исправляющий <tex>k</tex> ошибок.
Тогда для любых неравных <tex>x,y\in \Sigma</tex> выполнено <tex>S(c(x), k) \cap S(c(y), k) = \emptyset</tex>.
}}
{{Теорема
|about=Граница Хемминга.
|statement= Пусть <tex>c: \Sigma \to B^n</tex> — код для <tex>m</tex> символьного алфавита, исправляющий <tex>k</tex> ошибок.
Тогда выполнено неравенство <tex>mV(n,k) \leqslant 2^n</tex>.
|proof= Это прямое следствие [[#boolean_balls_coding|предыдущей]] леммы.
}}
Для составления верхних и нижних оценок на параметры кодирования нам понадобится понятие шара.
{{Определение
|neat = 1
|definition=
Рассмотрим <tex> B^n </tex>.
Булевым шаром в <tex> B^n </tex> радиуса <tex> r </tex> с центром <tex> x </tex> называется множество <tex> S(x,r) = \{ y : H(x,y) \leqslant r\} </tex>.
}}
{{Определение
|neat = 1
|definition=
Обьёмом шара <tex>S(x,r)</tex> в <tex>B^n</tex> называется его мощность <tex>|S(x,r)|</tex> и обозначается <tex>V(n,r)</tex>.
}}
{{Утверждение
|statement= Обьём шара не зависит от его центра.
|proof=
Заметим, что шар <tex>S(x,r)</tex> всегда можно получить из другого шара <tex>S(y,r)</tex> с помощью "параллельного переноса" на вектор <tex>x\oplus y</tex>, т.е.
<tex> S(x, r) = \{z : z = t \oplus x \oplus y, t \in S(y,r) \} </tex>.
Покажем это.
Необходимо доказать, что <tex>H(x,z) = H(y,t)</tex> при <tex>t = z \oplus (x \oplus y)</tex> и <tex>y = x \oplus (x \oplus y)</tex>.
<tex>H(y,t) = |\{i : y[i] \neq t[i]\}| = |\{i : x[i] \oplus (x[i] \oplus y[i]) \neq z[i] + (x[i] + y[i]) \}|
= |\{ i : x[i] \neq z[i]\}| = H(z,t) </tex>.
}}
Можно переформулировать условие на исправление кодом <tex>k</tex> ошибок в терминах булевых шаров.
{{Лемма
|id=boolean_balls_coding
|statement= Пусть <tex>c:\Sigma \to B^n</tex> — код, исправляющий <tex>k</tex> ошибок.
Тогда для любых неравных <tex>x,y\in \Sigma</tex> выполнено <tex>S(c(x), k) \cap S(c(y), k) = \emptyset</tex>.
}}
{{Теорема
|about=Граница Хемминга.
|statement= Пусть <tex>c: \Sigma \to B^n</tex> — код для <tex>m</tex> символьного алфавита, исправляющий <tex>k</tex> ошибок.
Тогда выполнено неравенство <tex>mV(n,k) \leqslant 2^n</tex>.
|proof= Это прямое следствие [[#boolean_balls_coding|предыдущей]] леммы.
}}
