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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Небольшой фикс)
м (Добавлена Лемма)
Строка 25: Строка 25:
 
}}
 
}}
  
Можно переформулировать свойство кодов, исправляющих <tex>k</tex> ошибок, в терминах булевых шаров.
+
Можно переформулировать свойства кодов, исправляющих <tex>k</tex> ошибок, в терминах булевых шаров.
 
{{Лемма
 
{{Лемма
 
|id=boolean_balls_coding   
 
|id=boolean_balls_coding   
Строка 31: Строка 31:
 
Тогда для любых неравных <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>.  
 
}}
 
}}
 +
 +
{{Лемма
 +
|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> ошибок.
 +
}}
 +
  
 
{{Теорема  
 
{{Теорема  
Строка 42: Строка 48:
  
 
Граница Хемминга даёт верхнюю оценку на скорость передачи сообщений в канале с ошибками.  
 
Граница Хемминга даёт верхнюю оценку на скорость передачи сообщений в канале с ошибками.  
Прологарифмировав неравнество, получим <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> это плотность кодирования, количество информации в одном символе алфавита на размер кода.
 
Таким образом, при кодировании с защитой от ошибок падает скорость передачи.
 
Таким образом, при кодировании с защитой от ошибок падает скорость передачи.
Строка 56: Строка 62:
 
Сопоставим первому символу <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_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_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>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>2k</tex> не пересекается с шарами всех остальных слов (как того требует исправление <tex>k</tex> ошибок), а значит мы можем построить искомый код.
 
}}
 
}}

Версия 01:32, 26 июня 2021

Граница Хемминга

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

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


Определение:
Обьёмом шара [math]S(x,r)[/math] в [math]B^n[/math] называется его размер [math]|S(x,r)|[/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] 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]c:\Sigma \to B^n[/math]. Пусть для любых неравных [math]x,y \in \Sigma[/math] выполнено [math] S(c(x), 2k) \cap S(c(y), 2k) = \emptyset [/math]. Тогда [math]c[/math] — код, исправляющий [math]k[/math] ошибок.


Теорема (Граница Хемминга):
Пусть [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]\triangleright[/math]

Построим этот код жадным алгоритмом. Сопоставим первому символу [math]x_1[/math] из [math]\Sigma[/math] в [math]B^n[/math] кодовое слово [math]c(x_1)\in B^n[/math] и вырежем из B^n шар [math]S(x_1,2k)[/math]. Для второго символа [math]x_2[/math] повторим ту же процедуру, выберем ему кодовое слово [math]c(x_2)\in B^n \setminus S(x_1, 2k)[/math]. На каждом шаге будем выбирать для каждого символа [math]x_{i+1}[/math] некоторое слово [math]c(x_{i+1}) \in B^n \setminus \bigcup_{j=1}^{i} S(x_j, 2k) [/math].

Неравенство гарантирует нам, что по каждому символу мы сможем выбрать кодовое слово, чей шар радиуса [math]2k[/math] не пересекается с шарами всех остальных слов (как того требует исправление [math]k[/math] ошибок), а значит мы можем построить искомый код.
[math]\triangleleft[/math]