Участник:Feorge — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Добавлена Лемма)
 
(не показано 9 промежуточных версий 2 участников)
Строка 1: Строка 1:
== Граница Хемминга ==
+
Пусть <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> ошибок.
 +
}}
 +
 
 
Для составления оценок снизу и сверху на параметры кодирования нам понадобится понятие шара.  
 
Для составления оценок снизу и сверху на параметры кодирования нам понадобится понятие шара.  
 
{{Определение
 
{{Определение
|neat = 1
+
|definition=
|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>.   
Рассмотрим <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>y</tex>.   
 
 
}}
 
}}
 
 
{{Определение
 
{{Определение
|neat = 1
 
 
|definition=  
 
|definition=  
Обьёмом шара <tex>S(x,r)</tex> в <tex>B^n</tex> называется его размер <tex>|S(x,r)|</tex> и обозначается <tex>V(n,r)</tex>.  
+
Обьёмом шара <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= Обьём шара не зависит от его центра.
 
|statement= Обьём шара не зависит от его центра.
|proof=
+
|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)</tex> всегда можно получить из другого шара <tex>S(y,r)</tex> с помощью "параллельного переноса" на вектор <tex>x\oplus y</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> S(x, r) = \{z : z = t \oplus x \oplus y, t \in S(y,r) \} </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>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> ошибок, в терминах булевых шаров.
+
Можно сформулировать свойство кодов, исправляющих <tex>k</tex> ошибок, в терминах булевых шаров.
 +
 
 
{{Лемма
 
{{Лемма
|id=boolean_balls_coding
+
|id=boolean_balls_coding  
|statement= Пусть <tex>c:\Sigma \to B^n</tex> код, исправляющий <tex>k</tex> ошибок.  
+
|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>.  
+
Тогда для любых неравных <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>.
 
}}
 
}}
  
{{Лемма
+
== Определение и устранение ошибок в общем случае ==
|id=boolean_balls_coding 
+
Пусть <tex>\Sigma</tex> &mdash; исходный алфавит, <tex>c: \Sigma \to B^m</tex> &mdash; кодирование, <tex>B=(0,1)</tex>
|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>d: B^m \times B^m \to \mathbb{R}</tex> &mdash; [[расстояние Хэмминга]] между двумя кодами. <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> можно считать ошибочной и исправить на центр шара &mdash; строку <tex>S</tex>.<br>
 +
[[Файл:Ham.png|350px]]
  
 +
== Граница Хэмминга, граница Гильберта ==
  
 
{{Теорема  
 
{{Теорема  
|about=Граница Хемминга
+
|about=Граница Хэмминга
|statement= Пусть <tex>c: \Sigma \to B^n</tex> код для <tex>m</tex>-символьного алфавита, исправляющий <tex>k</tex> ошибок.
+
|statement= Пусть <tex>c: \Sigma \to B^n</tex> {{---}} код для <tex>m</tex>-символьного алфавита, исправляющий <tex>k</tex> ошибок.
 
Тогда выполнено неравенство <tex>mV(n,k) \leqslant 2^n</tex>.   
 
Тогда выполнено неравенство <tex>mV(n,k) \leqslant 2^n</tex>.   
|proof= Это прямое следствие [[#boolean_balls_coding|предыдущей]] леммы.  
+
|proof=Это прямое следствие [[#boolean_balls_coding|предыдущей]] леммы.  
 
Всего есть <tex>m = |\Sigma|</tex> попарно непересекающихся шаров.  
 
Всего есть <tex>m = |\Sigma|</tex> попарно непересекающихся шаров.  
 
Их суммарный обьём равен <tex>mV(n,k)</tex>, и он не может превосходить общее число возможных веткоров <tex>|B| = 2^n</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} \leqslant 1 - \frac{V(n, k)}{n}</tex>.
 
Здесь <tex>\frac{\log(m)}{n}</tex> это плотность кодирования, количество информации в одном символе алфавита на размер кода.
 
Здесь <tex>\frac{\log(m)}{n}</tex> это плотность кодирования, количество информации в одном символе алфавита на размер кода.
Строка 58: Строка 71:
 
|statement=  
 
|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> 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> ошибок), а значит мы можем построить искомый код.
 
 
}}
 
}}
 +
 +
Примером кода для случая <tex>k=1</tex> является [[Избыточное кодирование, код Хэмминга#def1|код Хэмминга]].

Текущая версия на 20:17, 12 ноября 2021

Пусть [math]B = \{0, 1\}[/math] — булевое множество. Рассмотрим [math]B^n[/math] и расстояние Хемминга [math]H(x,y)[/math]. Пусть [math]c:\Sigma \to B^n[/math] — разделяемый код постоянной длины. Обозначим [math]\min\limits_{\substack{x, y\in \Sigma \\ x\neq y}}H(c(x), c(y)) = d(c)[/math].

Коды, исправляющие и обнаруживающие ошибки

Определение:
Код [math]c[/math] обнаруживает [math]k[/math] ошибок, если [math]d(c) \gt k[/math].


Определение:
Код [math]c[/math] исправляет [math]k[/math] ошибок, если [math]d(c) \gt 2k[/math].
Утверждение:
Код, исправляющий [math]k[/math] ошибок, обнаруживает [math]2k[/math] ошибок.

Для составления оценок снизу и сверху на параметры кодирования нам понадобится понятие шара.

Определение:
Булев шар — подмножество [math]B^n[/math] вида [math] \{ y : H(x,y) \leqslant r\}[/math]. [math]x[/math] называется его центром, [math]r[/math] — радиусом. Булев шар с центром [math]x[/math] и радиусом [math]r[/math] обознчается [math]S(x,r)[/math].


Определение:
Обьёмом шара [math]S(x,r)[/math] в [math]B^n[/math] называется величина [math]|S(x,r)|[/math]. Обьём шара радиуса [math]r[/math] в [math]B^n[/math] обозначается [math]V(n,r)[/math].
Утверждение:
Обьём шара не зависит от его центра.
[math]\triangleright[/math]

Заметим, что шар [math]S(x,r)[/math] всегда можно получить из другого шара [math]S(y,r)[/math] с помощью "параллельного переноса" на вектор [math]x\oplus y[/math] (здесь [math]\oplus[/math] обозначает побитовый [math]XOR[/math]), т.е. [math] S(x, r) = \{z : z = t \oplus x \oplus y, t \in S(y,r) \} [/math]. Покажем это. Необходимо доказать, что [math]H(x,z) = H(y,t)[/math] при [math]t = z \oplus (x \oplus y)[/math] и [math]y = x \oplus (x \oplus y)[/math].

[math]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) [/math].
[math]\triangleleft[/math]

Можно сформулировать свойство кодов, исправляющих [math]k[/math] ошибок, в терминах булевых шаров.

Лемма:
Пусть [math]c:\Sigma \to B^n[/math] — код, исправляющий [math]k[/math] ошибок. Тогда для любых неравных [math]x,y\in \Sigma[/math] выполнено [math]S(c(x), k) \cap S(c(y), k) = \emptyset[/math].
Доказательство:
[math]\triangleright[/math]

Т.к код [math]c[/math] исправляет [math]k[/math] ошибок, по определению [math]d(c)\gt 2k[/math].

Допустим, [math]x, y[/math] такие, что [math]x \neq y[/math] и [math]S(c(x), k) \cap S(c(y), k)\neq \emptyset[/math], т.е существует [math]z[/math], такой что [math]H(c(x), z) \leqslant k[/math] и [math]H(c(y), z) \leqslant k[/math]. Тогда по неравенству треугольника [math]H(c(x), c(y)) \leqslant 2k[/math]. Это противоречит тому, что [math]d(c)\gt 2k[/math].
[math]\triangleleft[/math]

Определение и устранение ошибок в общем случае

Пусть [math]\Sigma[/math] — исходный алфавит, [math]c: \Sigma \to B^m[/math] — кодирование, [math]B=(0,1)[/math]

[math]d: B^m \times B^m \to \mathbb{R}[/math]расстояние Хэмминга между двумя кодами.

Код, [math]c: \Sigma \to B^m[/math] может исправлять [math]~[[/math][math] {d_0-1}\over{2}[/math][math]~][/math] и обнаруживать [math][d_0-1][/math] ошибок. Действительно, при любом натуральном количестве допустимых ошибок [math]r[/math] любоое кодовое слово [math]S[/math] образует вокруг себя проколотый шар таких строк [math]S_i[/math], что [math]0\lt d(S,S_i)\leqslant r[/math]. Если этот шар не содержит других кодов (что выполняется при [math]r\lt d_0[/math]) , то можно утверждать, что если в него попадает строка, то она ошибочна. Если шары всех кодов не пересекаются (что выполняется при [math]r \leqslant {{d_0-1}\over{2}} [/math]), то попавшую в шар строку [math]S_i[/math] можно считать ошибочной и исправить на центр шара — строку [math]S[/math].
Ham.png

Граница Хэмминга, граница Гильберта

Теорема (Граница Хэмминга):
Пусть [math]c: \Sigma \to B^n[/math] — код для [math]m[/math]-символьного алфавита, исправляющий [math]k[/math] ошибок. Тогда выполнено неравенство [math]mV(n,k) \leqslant 2^n[/math].
Доказательство:
[math]\triangleright[/math]

Это прямое следствие предыдущей леммы. Всего есть [math]m = |\Sigma|[/math] попарно непересекающихся шаров.

Их суммарный обьём равен [math]mV(n,k)[/math], и он не может превосходить общее число возможных веткоров [math]|B| = 2^n[/math].
[math]\triangleleft[/math]

Граница Хэмминга даёт верхнюю оценку на скорость передачи сообщений в канале с ошибками. Прологарифмировав неравенство, получим [math]\frac{\log(m)}{n} \leqslant 1 - \frac{V(n, k)}{n}[/math]. Здесь [math]\frac{\log(m)}{n}[/math] это плотность кодирования, количество информации в одном символе алфавита на размер кода. Таким образом, при кодировании с защитой от ошибок падает скорость передачи.

Аналогично составляется оценка в другую сторону.

Теорема (Граница Гильберта):
Если выполнено неравенство [math] mV(n,2k) \leqslant 2^n[/math], то существует код [math]c:\Sigma \to B^n[/math] для [math]m[/math]-символьного алфавита [math]\Sigma [/math], исправляющий [math]k[/math] ошибок.

Примером кода для случая [math]k=1[/math] является код Хэмминга.