Редактирование: Участник:Feorge
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
| − | + | == Граница Хемминга == | |
| − | + | Для составления оценок снизу и сверху на параметры кодирования нам понадобится понятие шара. | |
| − | |||
| − | |||
| − | |||
| − | |||
{{Определение | {{Определение | ||
| − | |definition= | + | |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>y</tex>. | |
| − | |||
}} | }} | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{{Определение | {{Определение | ||
| + | |neat = 1 | ||
|definition= | |definition= | ||
| − | Обьёмом шара <tex>S(x,r)</tex> в <tex>B^n</tex> называется | + | Обьёмом шара <tex>S(x,r)</tex> в <tex>B^n</tex> называется его размер <tex>|S(x,r)|</tex> и обозначается <tex>V(n,r)</tex>. |
| − | |||
}} | }} | ||
| + | |||
{{Утверждение | {{Утверждение | ||
|statement= Обьём шара не зависит от его центра. | |statement= Обьём шара не зависит от его центра. | ||
| − | |proof=Заметим, что шар <tex>S(x,r)</tex> всегда можно получить из другого шара <tex>S(y,r)</tex> с помощью "параллельного переноса" на вектор <tex>x\oplus y</tex> | + | |proof= |
| − | <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)</tex> всегда можно получить из другого шара <tex>S(y,r)</tex> с помощью "параллельного переноса" на вектор <tex>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])\}| | + | <tex> S(x, r) = \{z : z = t \oplus x \oplus y, t \in S(y,r) \} </tex>. |
| − | = |\{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> ошибок, в терминах булевых шаров. |
| + | {{Лемма | ||
| + | |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 | + | |id=boolean_balls_coding |
| − | |statement= | + | |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> ошибок. |
| − | |||
| − | |||
| − | |||
}} | }} | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{{Теорема | {{Теорема | ||
| − | |about=Граница | + | |about=Граница Хемминга |
| − | |statement= Пусть <tex>c: \Sigma \to B^n</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> это плотность кодирования, количество информации в одном символе алфавита на размер кода. | ||
| Строка 71: | Строка 58: | ||
|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> ошибок), а значит мы можем построить искомый код. | ||
}} | }} | ||
| − | |||
| − | |||
