10
правок
Изменения
Добавлено неравенство Гильберта
== Граница Хемминга ==
Для составления верхних оценок снизу и нижних оценок сверху на параметры кодирования нам понадобится понятие шара.
{{Определение
|neat = 1
{{Теорема
|about=Граница Хемминга.
|statement= Пусть <tex>c: \Sigma \to B^n</tex> — код для <tex>m</tex>-символьного алфавита, исправляющий <tex>k</tex> ошибок.
Тогда выполнено неравенство <tex>mV(n,k) \leqslant 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> ошибок), а значит мы можем построить искомый код.}}
