10
правок
Изменения
м
Булевым шаром в В <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>.
Небольшой фикс
|definition=
Рассмотрим <tex> B^n </tex>.
}}
|neat = 1
|definition=
Обьёмом шара <tex>S(x,r)</tex> в <tex>B^n</tex> называется его мощность размер <tex>|S(x,r)|</tex> и обозначается <tex>V(n,r)</tex>.
}}
}}
Можно переформулировать свойство кодов, исправляющих <tex>k</tex>ошибок, ошибок в терминах булевых шаров.
{{Лемма
|id=boolean_balls_coding
Прологарифмировав неравнество, получим <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=
Построим этот код жадным алгоритмом.
