10
правок
Изменения
м
Добавлена Лемма
}}
Можно переформулировать свойство свойства кодов, исправляющих <tex>k</tex> ошибок, в терминах булевых шаров.
{{Лемма
|id=boolean_balls_coding
Тогда для любых неравных <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> ошибок.
}}
{{Теорема
Граница Хемминга даёт верхнюю оценку на скорость передачи сообщений в канале с ошибками.
Прологарифмировав неравнествонеравенство, получим <tex>\frac{\log(m)}{n} \leqslant 1 - \frac{V(n, k)}{n}</tex>.
Здесь <tex>\frac{\log(m)}{n}</tex> это плотность кодирования, количество информации в одном символе алфавита на размер кода.
Таким образом, при кодировании с защитой от ошибок падает скорость передачи.
Сопоставим первому символу <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> ошибок), а значит мы можем построить искомый код.
}}
