Изменения
Новая страница: «Пусть <tex>B = \{0, 1\}</tex> — булевое множество. Рассмотрим <tex>B^n</tex> и Расстояние Хэмминга#def1|ра…»
Пусть <tex>B = \{0, 1\}</tex> — булевое множество. Рассмотрим <tex>B^n</tex> и [[Расстояние Хэмминга#def1|расстояние Хемминга]] <tex>H(x,y)</tex>. Пусть <tex>c:\Sigma \to B^n</tex> {{---}} разделяемый код постоянной длины. Обозначим <tex>\min\limits_{\substack{x, y\in \Sigma \\ x\neq y}}H(c(x), c(y)) = d(c)</tex>.
{{Определение
|definition=
Код <tex>c</tex> ''обнаруживает'' <tex>k</tex> ошибок, если <tex>d(c) > k</tex>.
}}
{{Определение
|definition=
Код <tex>c</tex> ''исправляет'' <tex>k</tex> ошибок, если <tex>d(c) > 2k</tex>.
}}
{{Утверждение
|statement= Код, исправляющий <tex>k</tex> ошибок, обнаруживает <tex>2k</tex> ошибок.
}}
Для составления оценок снизу и сверху на параметры кодирования нам понадобится понятие шара.
{{Определение
|definition=
Булев шар {{---}} подмножество <tex>B^n</tex> вида <tex> \{ y : H(x,y) \leqslant r\}</tex>. <tex>x</tex> называется его центром, <tex>r</tex> {{---}} радиусом. Булев шар с центром <tex>x</tex> и радиусом <tex>r</tex> обознчается <tex>S(x,r)</tex>.
}}
{{Определение
|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>.
}}
{{Утверждение
|statement= Обьём шара не зависит от его центра.
|proof=Заметим, что шар <tex>S(x,r)</tex> всегда можно получить из другого шара <tex>S(y,r)</tex> с помощью "параллельного переноса" на вектор <tex>x\oplus y</tex> (здесь <tex>\oplus</tex> обозначает побитовый <tex>XOR</tex>), т.е.
<tex> S(x, r) = \{z : z = t \oplus x \oplus y, t \in S(y,r) \} </tex>. Покажем это. Необходимо доказать, что <tex>H(x,z) = H(y,t)</tex> при <tex>t = z \oplus (x \oplus y)</tex> и <tex>y = x \oplus (x \oplus y)</tex>.
<tex>H(y,t) = |\{i : y[i] \neq t[i]\}| = |\{i : x[i] \oplus (x[i] \oplus y[i]) \neq z[i] + (x[i] + y[i])\}|
= |\{i : x[i] \neq z[i]\}| = H(z,t) </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>.
|proof=Т.к код <tex>c</tex> исправляет <tex>k</tex> ошибок, по определению <tex>d(c)>2k</tex>.
Допустим, <tex>x, y</tex> такие, что <tex>x \neq y</tex> и <tex>S(c(x), k) \cap S(c(y), k)\neq \emptyset</tex>, т.е существует <tex>z</tex>, такой что <tex>H(c(x), z) \leqslant k</tex> и <tex>H(c(y), z) \leqslant k</tex>. Тогда по неравенству треугольника <tex>H(c(x), c(y)) \leqslant 2k</tex>. Это противоречит тому, что <tex>d(c)>2k</tex>.
}}
== Определение и устранение ошибок в общем случае ==
Пусть <tex>\Sigma</tex> — исходный алфавит, <tex>c: \Sigma \to B^m</tex> — кодирование, <tex>B=(0,1)</tex>
<tex>d: B^m \times B^m \to \mathbb{R}</tex> — [[расстояние Хэмминга]] между двумя кодами. <br>
Код, <tex>c: \Sigma \to B^m</tex> может исправлять <math>~[</math><tex dpi = 150> {d_0-1}\over{2}</tex><math>~]</math> и обнаруживать <tex>[d_0-1]</tex> ошибок. Действительно, при любом натуральном количестве допустимых ошибок <tex>r</tex> любоое кодовое слово <tex>S</tex> образует вокруг себя проколотый шар таких строк <tex>S_i</tex>, что <tex>0<d(S,S_i)\leqslant r</tex>. Если этот шар не содержит других кодов (что выполняется при <tex>r<d_0</tex>) , то можно утверждать, что если в него попадает строка, то она ошибочна. Если шары всех кодов не пересекаются (что выполняется при <tex dpi = 150>r \leqslant {{d_0-1}\over{2}} </tex>), то попавшую в шар строку <tex>S_i</tex> можно считать ошибочной и исправить на центр шара — строку <tex>S</tex>.<br>
[[Файл:Ham.png|350px]]
== Граница Хэмминга, граница Гильберта ==
{{Теорема
|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> это плотность кодирования, количество информации в одном символе алфавита на размер кода.
Таким образом, при кодировании с защитой от ошибок падает скорость передачи.
Аналогично составляется оценка в другую сторону.
{{Теорема
|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> ошибок.
}}
Примером кода для случая <tex>k=1</tex> является [[Избыточное кодирование, код Хэмминга#def1|код Хэмминга]].
{{Определение
|definition=
Код <tex>c</tex> ''обнаруживает'' <tex>k</tex> ошибок, если <tex>d(c) > k</tex>.
}}
{{Определение
|definition=
Код <tex>c</tex> ''исправляет'' <tex>k</tex> ошибок, если <tex>d(c) > 2k</tex>.
}}
{{Утверждение
|statement= Код, исправляющий <tex>k</tex> ошибок, обнаруживает <tex>2k</tex> ошибок.
}}
Для составления оценок снизу и сверху на параметры кодирования нам понадобится понятие шара.
{{Определение
|definition=
Булев шар {{---}} подмножество <tex>B^n</tex> вида <tex> \{ y : H(x,y) \leqslant r\}</tex>. <tex>x</tex> называется его центром, <tex>r</tex> {{---}} радиусом. Булев шар с центром <tex>x</tex> и радиусом <tex>r</tex> обознчается <tex>S(x,r)</tex>.
}}
{{Определение
|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>.
}}
{{Утверждение
|statement= Обьём шара не зависит от его центра.
|proof=Заметим, что шар <tex>S(x,r)</tex> всегда можно получить из другого шара <tex>S(y,r)</tex> с помощью "параллельного переноса" на вектор <tex>x\oplus y</tex> (здесь <tex>\oplus</tex> обозначает побитовый <tex>XOR</tex>), т.е.
<tex> S(x, r) = \{z : z = t \oplus x \oplus y, t \in S(y,r) \} </tex>. Покажем это. Необходимо доказать, что <tex>H(x,z) = H(y,t)</tex> при <tex>t = z \oplus (x \oplus y)</tex> и <tex>y = x \oplus (x \oplus y)</tex>.
<tex>H(y,t) = |\{i : y[i] \neq t[i]\}| = |\{i : x[i] \oplus (x[i] \oplus y[i]) \neq z[i] + (x[i] + y[i])\}|
= |\{i : x[i] \neq z[i]\}| = H(z,t) </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>.
|proof=Т.к код <tex>c</tex> исправляет <tex>k</tex> ошибок, по определению <tex>d(c)>2k</tex>.
Допустим, <tex>x, y</tex> такие, что <tex>x \neq y</tex> и <tex>S(c(x), k) \cap S(c(y), k)\neq \emptyset</tex>, т.е существует <tex>z</tex>, такой что <tex>H(c(x), z) \leqslant k</tex> и <tex>H(c(y), z) \leqslant k</tex>. Тогда по неравенству треугольника <tex>H(c(x), c(y)) \leqslant 2k</tex>. Это противоречит тому, что <tex>d(c)>2k</tex>.
}}
== Определение и устранение ошибок в общем случае ==
Пусть <tex>\Sigma</tex> — исходный алфавит, <tex>c: \Sigma \to B^m</tex> — кодирование, <tex>B=(0,1)</tex>
<tex>d: B^m \times B^m \to \mathbb{R}</tex> — [[расстояние Хэмминга]] между двумя кодами. <br>
Код, <tex>c: \Sigma \to B^m</tex> может исправлять <math>~[</math><tex dpi = 150> {d_0-1}\over{2}</tex><math>~]</math> и обнаруживать <tex>[d_0-1]</tex> ошибок. Действительно, при любом натуральном количестве допустимых ошибок <tex>r</tex> любоое кодовое слово <tex>S</tex> образует вокруг себя проколотый шар таких строк <tex>S_i</tex>, что <tex>0<d(S,S_i)\leqslant r</tex>. Если этот шар не содержит других кодов (что выполняется при <tex>r<d_0</tex>) , то можно утверждать, что если в него попадает строка, то она ошибочна. Если шары всех кодов не пересекаются (что выполняется при <tex dpi = 150>r \leqslant {{d_0-1}\over{2}} </tex>), то попавшую в шар строку <tex>S_i</tex> можно считать ошибочной и исправить на центр шара — строку <tex>S</tex>.<br>
[[Файл:Ham.png|350px]]
== Граница Хэмминга, граница Гильберта ==
{{Теорема
|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> это плотность кодирования, количество информации в одном символе алфавита на размер кода.
Таким образом, при кодировании с защитой от ошибок падает скорость передачи.
Аналогично составляется оценка в другую сторону.
{{Теорема
|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> ошибок.
}}
Примером кода для случая <tex>k=1</tex> является [[Избыточное кодирование, код Хэмминга#def1|код Хэмминга]].
