10
правок
Изменения
м
Начало правок
== Граница Определение и устранение ошибок в общем случае ==Пусть <tex>B = \{0, 1\}</tex> — булевое множество. Рассмотрим <tex>B^n</tex> и расстояние (метрику) Хемминга <tex>H(x,y)</tex>.Пусть <tex>c:\Sigma to B^n</tex> {{---}} разделяемый код постоянной длины.Обозначим <tex>\min_{x,y\in \SIgma}H(c(x), c(y)) = d(c)</tex>. {{Определение|neat = 1 |definition=Код <tex>c</tex> обнаруживает <tex>k</tex> ошибок, если <tex>d(c) > k</tex>. }} {{Определение|neat = 1 |definition=Код <tex>c</tex> исправляет <tex>k</tex> ошибок, если <tex>d(c) > 2k</tex>. }} {{Утверждение|statement=Код, исправляющий <tex>k</tex> ошибок, обнаруживает <tex>2k</tex> ошибок.}}
Для составления оценок снизу и сверху на параметры кодирования нам понадобится понятие шара.
{{Определение
|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>r</tex> — радиусом.Булев шар с центром <tex>x</tex> и радиусом <tex>r</tex> обознчается <tex>yS(x,r)</tex>.
}}
|neat = 1
|definition=
Обьёмом шара <tex>S(x,r)</tex> в <tex>B^n</tex> называется его размер величина <tex>|S(x,r)|</tex> и . Обьём шара радиуса <tex>r</tex> в <tex>B^n</tex> обозначается <tex>V(n,r)</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 boolean_balls_coding_rev |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> 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> и вырежем из <tex>B^n </tex> шар <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>i+1</tex>-ого слова доступны <tex>2^n - iV(n,k) \geqslant V(n,k)</tex> вариантов.
Неравенство гарантирует нам, что по каждому символу мы сможем выбрать кодовое слово, чей шар радиуса <tex>2k</tex> не пересекается с шарами всех остальных слов (как того требует исправление <tex>k</tex> ошибок), а значит мы можем построить искомый код.
}}
