Просмотр исходного текста страницы Участник:Feorge

== Граница Хемминга ==
Для составления оценок снизу и сверху на параметры кодирования нам понадобится понятие шара. 
{{Определение
|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>, где <tex>H(x,y)</tex> — расстояние Хемминга между <tex>x</tex> и <tex>y</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>. 
}}

{{Лемма
|id=boolean_balls_coding  
|statement= Рассмотрим код <tex>c:\Sigma \to B^n</tex>. Пусть для любых неравных <tex>x,y \in \Sigma</tex> выполнено <tex> S(c(x), 2k) \cap S(c(y), 2k) = \emptyset </tex>. Тогда <tex>c</tex> — код, исправляющий <tex>k</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|предыдущей]] леммы. 
Всего есть <tex>m = |\Sigma|</tex> попарно непересекающихся шаров. 
Их суммарный обьём равен <tex>mV(n,k)</tex>, и он не может превосходить общее число возможных веткоров <tex>|B| = 2^n</tex>.
}}

Граница Хемминга даёт верхнюю оценку на скорость передачи сообщений в канале с ошибками. 
Прологарифмировав неравенство, получим <tex>\frac{\log(m)}{n} \leqslant 1 - \frac{V(n, k)}{n}</tex>.
Здесь <tex>\frac{\log(m)}{n}</tex> это плотность кодирования, количество информации в одном символе алфавита на размер кода.
Таким образом, при кодировании с защитой от ошибок падает скорость передачи.

Аналогично составляется оценка в другую сторону. 

{{Теорема 
|about=Граница Гильберта
|statement= 
Если выполнено неравенство <tex> mV(n,2k) \leqslant 2^n</tex>, то существует код <tex>c:\Sigma \to B^n</tex> для <tex>m</tex>-символьного алфавита <tex>\Sigma </tex>, исправляющий <tex>k</tex> ошибок.
|proof= 
Построим этот код жадным алгоритмом. 
Сопоставим первому символу <tex>x_1</tex> из <tex>\Sigma</tex> в <tex>B^n</tex> кодовое слово <tex>c(x_1)\in B^n</tex> и вырежем из B^n шар <tex>S(x_1,2k)</tex>. 
Для второго символа <tex>x_2</tex> повторим ту же процедуру, выберем ему кодовое слово <tex>c(x_2)\in B^n \setminus S(x_1, 2k)</tex>. 
На каждом шаге будем выбирать для каждого символа <tex>x_{i+1}</tex> некоторое слово  <tex>c(x_{i+1}) \in B^n \setminus \bigcup_{j=1}^{i} S(x_j, 2k) </tex>.
Неравенство гарантирует нам, что по каждому символу мы сможем выбрать кодовое слово, чей шар радиуса <tex>2k</tex> не пересекается с шарами всех остальных слов (как того требует исправление <tex>k</tex> ошибок), а значит мы можем построить искомый код.
}}