10
правок
Изменения
Основная часть конспекта по теме ''Булевые шары, граница Хемминга'' выполнена
}}
Можно переформулировать условие на исправление кодом свойство кодов, исправляющих <tex>k</tex> , ошибок в терминах булевых шаров.
{{Лемма
|id=boolean_balls_coding
{{Теорема
|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> это плотность кодирования (количество информации в одном символе алфавита на размер кода).
Таким образом при кодировании с защитой от <tex>k</tex> ошибок падает скорость передачи.
