Участник:Feorge

Материал из Викиконспекты
Версия от 01:34, 25 июня 2021; Feorge (обсуждение | вклад) (Новая страница: «== Граница Хемминга == Для составления верхних и нижних оценок на параметры кодирования н…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

Определение:
Рассмотрим [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]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]m[/math] символьного алфавита, исправляющий [math]k[/math] ошибок. Тогда выполнено неравенство [math]mV(n,k) \leqslant 2^n[/math].
Доказательство:
[math]\triangleright[/math]
Это прямое следствие предыдущей леммы.
[math]\triangleleft[/math]