Хеммингова сфера

Сферы Хемминга для двоичного двумерного векторного пространства с центрами в различных точках (отмечены чёрным). Сферам принадлежат точки, отмеченные чёрным и зелёным. Точки, отмеченные белым не принадлежат сферам. В каждом из примеров сферам принадлежит ровно три точки (вектора).

Хеммингова сфера $S_t\left(\stackrel{\to <!--\; \to \; -->}{v}\right)$$S_{t}\left({\vec {v}}\right)$ радиуса $t$$t$ c центром в точке $\stackrel{\to <!--\; \to \; -->}{v}$${\vec {v}}$ — множество всех векторов (точек) в двоичном векторном пространстве $V_2$$V_{2}$ на расстоянии не более $t$$t$ от заданного вектора $\stackrel{\to <!--\; \to \; -->}{v}$${\vec {v}}$:

$S_t\left(\stackrel{\to <!--\; \to \; -->}{v}\right)=\left\{\stackrel{\to <!--\; \to \; -->}{x}\in <!--\; \in \; -->C|d_H\left(\stackrel{\to <!--\; \to \; -->}{x},\stackrel{\to <!--\; \to \; -->}{v}\right)\le <!--\; \le \; -->t\right\}$$S_{t}\left({\vec {v}}\right)=\left\{{\vec {x}}\in C|d_{H}\left({\vec {x}},{\vec {v}}\right)\leq t\right\}$

Если размерность двоичного векторного пространства $V_2$$V_{2}$ равна $n$$n$, то количество точек (векторов), принадлежащих сфере $S_t\left(\stackrel{\to <!--\; \to \; -->}{v}\right)$$S_{t}\left({\vec {v}}\right)$ равно:

$\left|S_t\left(\stackrel{\to <!--\; \to \; -->}{v}\right)\right|=\underset{i=0}{\overset{t}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{i})$$\left|{S_{t}\left({\vec {v}}\right)}\right|=\sum \limits _{i=0}^{t}{\binom {n}{i}}$

ЛитератураПравить

• Морелос-Сарагоса Р. 1.1.2. Хеммингово расстояние, Хемминговы сферы и корректирующая способность // Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — С. 20—23. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0.