## Код Хэмминга (n,k)

- $n$ - число бит в кодовой последовательности
- $k$ - число информационных бит
- $r = n - k$ - число контрольных бит



```python
import numpy as np
from sympy import *
from functools import reduce
from IPython.display import Math
```

### Пример для (7,4)


```python
n,k = (7,4)
r = n - k
```

Контрольные биты четности $p_{1..r}$ вычисляются из битов данных $d_{1..k}$ следующим образом:

> $p_1 = d_1 \oplus d_2 \oplus d_4$  
> $p_2 = d_1 \oplus d_3 \oplus d_4$  
> $p_3 = d_2 \oplus d_3 \oplus d_4$  

Вектор кодовой последовательности $\langle d_1, d_2, d_3, d_4, p_1, p_2, p_3 \rangle$ можно получить умножением вектора исходных данных $\langle d_1, d_2, d_3, d_4 \rangle$ на матрицу-генератор $G$, где $P$ - матрица перестановки, соответствующая вышеупомянутым комбинациям информационных битов для вычисления битов четности:

> $G = \begin{bmatrix}I_{k} ~\vdots~ P\end{bmatrix}$

Для проверки наличия ошибок в кодовой последовательности вычисляется вектор синдромов $\vec{S} = \langle S_1, S_2, S_3 \rangle$, такой что:
 
> $S_1 = p_1 \oplus d_1 \oplus d_2 \oplus d_4$  
> $S_2 = p_2 \oplus d_1 \oplus d_3 \oplus d_4$  
> $S_3 = p_3 \oplus d_2 \oplus d_3 \oplus d_4$  

Если вектор синдромов равен нулевому вектору $\langle 0, 0, 0 \rangle$, то кодовая последовательность не содержит ошибок. Вектор синдромов можно получить умножением вектора кодовой последовательности на матрицу контроля четности:

> $H = \begin{bmatrix}P \\ \cdots \\ I_{r}\end{bmatrix}$
 

---
#### Матрица-генератор:


```python
Ik = np.eye(k, dtype='B')
P = np.array([[1,1,0],[1,0,1],[0,1,1],[1,1,1]], dtype='B')

G = np.hstack((Ik, P))

display(Math('G = ' + latex(Matrix(G))))
```


$\displaystyle G = \left[\begin{matrix}1 & 0 & 0 & 0 & 1 & 1 & 0\\0 & 1 & 0 & 0 & 1 & 0 & 1\\0 & 0 & 1 & 0 & 0 & 1 & 1\\0 & 0 & 0 & 1 & 1 & 1 & 1\end{matrix}\right]$


#### Матрица контроля чётности:


```python
Ir = np.eye(r, dtype='B')
H = np.vstack((P, Ir))

display(Math('H = ' + latex(Matrix(H))))
```


$\displaystyle H = \left[\begin{matrix}1 & 1 & 0\\1 & 0 & 1\\0 & 1 & 1\\1 & 1 & 1\\1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{matrix}\right]$


#### Произвольный вектор с информационными битами: $\vec{D}$


```python
D = np.random.randint(0, 2, (1, k), dtype='B')

display(Math('\\vec{D} = ' + latex(Matrix(D))))
```


$\displaystyle \vec{D} = \left[\begin{matrix}0 & 1 & 1 & 0\end{matrix}\right]$


#### Вычисление кодовой последовательности: $\vec{C} = \vec{D} \times G$


```python
C = np.dot(D, G) % 2

display(Math('\\vec{C} = ' + latex(Matrix(C))))
```


$\displaystyle \vec{C} = \left[\begin{matrix}0 & 1 & 1 & 0 & 1 & 1 & 0\end{matrix}\right]$


#### Проверка кодовой последовательности, вычисление вектора синдромов: $\vec{S} = \vec{C} \times H$


```python
S = np.dot(C, H) % 2

display(Math('\\vec{S} = ' + latex(Matrix(S))))
```


$\displaystyle \vec{S} = \left[\begin{matrix}0 & 0 & 0\end{matrix}\right]$


---
#### Исправление ошибок в кодовой последовательности

Для обнаружения и исправления единичной ошибки в кодовой последовательности удобно распологать в ней биты в таком порядке, чтобы контрольные биты $p_{1..r}$ находились на позициях кратных степени двойки: $2^{x}, \{ x \in \mathbb{N}, 0 \leq x \lt r \}$.
В этом случае полученный при декодировании вектор синдромов $\langle S_1, S_2, S_3 \rangle$ будет являться двоичным представлением индекса ошибочного символа в кодовой последовательности.

Переставим столбцы в матрице-генераторе и строки в матрице контроля четности таким образом, чтобы результирующий вектор кодовой последовательности содержал биты в упомянутом порядке:

> $\langle d_1, d_2, d_3, d_4, p_1, p_2, p_3 \rangle \mapsto \langle p_1, p_2, d_1, p_3, d_2, d_3, d_4 \rangle$


```python
Gp = G[:,(4,5,0,6,1,2,3)]
Hp = H[(4,5,0,6,1,2,3),:]

display(Math('Gp = ' + latex(Matrix(Gp)) +'; ~~~ Hp = ' + latex(Matrix(Hp))))
```


$\displaystyle Gp = \left[\begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0\\1 & 0 & 0 & 1 & 1 & 0 & 0\\0 & 1 & 0 & 1 & 0 & 1 & 0\\1 & 1 & 0 & 1 & 0 & 0 & 1\end{matrix}\right]; ~~~ Hp = \left[\begin{matrix}1 & 0 & 0\\0 & 1 & 0\\1 & 1 & 0\\0 & 0 & 1\\1 & 0 & 1\\0 & 1 & 1\\1 & 1 & 1\end{matrix}\right]$


Вычислим кодовую последовательность и синдром используя обновленные матрицы:


```python
Cp = np.dot(D, Gp) % 2
Sp = np.dot(Cp, Hp) % 2
display(Math('\\vec{Cp} = ' + latex(Matrix(Cp))))
display(Math('\\vec{Sp} = ' + latex(Matrix(Sp))))
```


$\displaystyle \vec{Cp} = \left[\begin{matrix}1 & 1 & 0 & 0 & 1 & 1 & 0\end{matrix}\right]$



$\displaystyle \vec{Sp} = \left[\begin{matrix}0 & 0 & 0\end{matrix}\right]$


Тест: Имитация единичной ошибки в кодовой последовательности и вычисление индекса ошибочного символа:


```python
for i in range(7):
    Cp[0,i] ^= 1
    Sp = np.dot(Cp, Hp) % 2
    Cp[0,i] ^= 1
    err = np.packbits(Sp, bitorder='little')
    display(Math("\\vec{Sp} = " + latex(Matrix(Sp)) + " \\implies \\text{ошибка в символе}~\\vec{Cp_{%d}}" % err))
```


$\displaystyle \vec{Sp} = \left[\begin{matrix}1 & 0 & 0\end{matrix}\right] \implies \text{ошибка в символе}~\vec{Cp_{1}}$



$\displaystyle \vec{Sp} = \left[\begin{matrix}0 & 1 & 0\end{matrix}\right] \implies \text{ошибка в символе}~\vec{Cp_{2}}$



$\displaystyle \vec{Sp} = \left[\begin{matrix}1 & 1 & 0\end{matrix}\right] \implies \text{ошибка в символе}~\vec{Cp_{3}}$



$\displaystyle \vec{Sp} = \left[\begin{matrix}0 & 0 & 1\end{matrix}\right] \implies \text{ошибка в символе}~\vec{Cp_{4}}$



$\displaystyle \vec{Sp} = \left[\begin{matrix}1 & 0 & 1\end{matrix}\right] \implies \text{ошибка в символе}~\vec{Cp_{5}}$



$\displaystyle \vec{Sp} = \left[\begin{matrix}0 & 1 & 1\end{matrix}\right] \implies \text{ошибка в символе}~\vec{Cp_{6}}$



$\displaystyle \vec{Sp} = \left[\begin{matrix}1 & 1 & 1\end{matrix}\right] \implies \text{ошибка в символе}~\vec{Cp_{7}}$


4fd55ce7b831caec0dea8abef81c0ba5ff6e95a9
ipynb
Jupyter Notebook
hamming-code.ipynb
afedotov/scipy-notebooks
de30a4e826a027618b3e07e072adaa007305ff3e
Unlicense
hamming-code.ipynb
afedotov/scipy-notebooks
de30a4e826a027618b3e07e072adaa007305ff3e
Unlicense
hamming-code.ipynb
afedotov/scipy-notebooks
de30a4e826a027618b3e07e072adaa007305ff3e
Unlicense
Qwen/Qwen-72B
1. YES
2. YES