Кодирование. 
Код Хемминга

Закодируем сообщение [0110]. В полиноминальном виде этому сообщению соответствует многочлен:

I (x) = x + x².

Для того чтобы закодировать исходное сообщение при несистематическом кодировании информационный многочлен I (x) умножается на порождающий многочлен:

g (x) = x³ + x +1.

Полученный многочлен r (x) назовем кодовым словом.

r (x) = I (x) * g (x); r (x) = x + x³ + x⁴ + x⁵

или соответствующее кодовое слово [101 110].

Рис. 3. Схема умножения многочлена на многочлен.

Листинг 1. Результат работы кодера.

for (int i = 0; i< 1; i++).

for (int j = 0; j< 7; j++).

{.

bool x = 0;

for (int k = 0; k< 4; k++) // Блок программы, который выполняет.

x ^= Is [i] [k]* Pm [k] [j]; // Умножение многочлена на многочлен.

Ks [i] [j]= x;

}.

Рис. 4. Принципиальная схема кодера несистематического кода Хэмминга: C — синхросигнал; R — активный сигнал сброса; In — информационный сигнал; Out — выход кодера

Декодирование

Алгоритм декодирования следующий:

1) Найти синдром или синдромный многочлен.

s (x) = r (x)mod g (x),.

где r (x) полученное кодовое слово.

2) Для каждого i = 0… j, вычислять.

s_i(x) = xⁱs (x)mod g (x).

до тех пор, пока не будет найден, s_j такой, что для него (вес) wt (s_j)? t, где t — максимальное число ошибок (в данной работе t = 1), исправляемых кодом. Таким образом полином ошибки есть:

e (x) = x^n-js_j(x)mod (1 + xⁿ).

Декодируем полученное сообщение [101 111]. Заметим, что седьмой бит изменен на противоположный, т. е. сообщение было принято с ошибкой. Соответствующий вектору многочлен:

r (x) = x + x³ + x⁴ + x⁵ + x⁶.

Найдем синдромный многочлен, для этого нужно найти остаток от деления многочлена r (x) на многочлен g (x).

s (x) = r (x)mod g (x); s (x) = x² + 1.

Как известно, если синдром равен 0, то кодовое слово получено без искажений. В этом случае это не так.

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

s_i(x) = xⁱ(x + 1) mod g (x).

для последовательных возрастающих значений i пока не найдем многочлен степени меньшей или равной одному (число ошибок t = 1).

s₁ = xs (x)mod g (x) = 1.

1 имеет вес 1 для нахождения многочлена ошибок вычисляем:

e (x) = x⁷⁻¹(1)mod (xⁿ + 1) = x⁶

Итак, если отправленное кодовое слово имеет не более двух ошибок, то оно было таким:

r (x) = x + x³ + x⁴ + x⁵ + x⁶ + x⁶ = x + x³ + x⁴ + x⁵

Чтобы получить исходное слово делим кодовый многочлен r (x) на порождающий многочлен g (x).

I (x) = x + x².

Из Листинга 3 видно, что расчётные данные совпали с данными программы. Следовательно, алгоритм декодирования корректен и работает правильно.

Листинг 3. Декодер, принявший сообщение с ошибкой и исправивший ее.

Также следует отметить, что если синдром будет равен 1, x или x², то полный алгоритм исправления ошибочного бита выполнять не нужно. Можно сразу сказать то, что номер ошибочного бита равен 1, 2 или 3 соответственно.

Рис. 6. Принципиальная схема декодера несистематического кода Хэмминга.

Пример. Для примера изменим 5-й бит в исходном кодовом слове. На вход декодера получаем сообщение [101 010]. Делим полученное сообщение.

r (x) = x + x³ + x⁵ на g (x). s (x) = x + x².

Найдем синдромный многочлен:

• 1) xs (x)mod g (x) = 1 + x².
• 2) x²s (x)mod g (x) = 1 + x²
• 3) x³s (x)mod g (x) = 1

e (x) = x⁷⁻³(1)mod (xⁿ + 1) = x⁴.

Итак, если отправленное кодовое слово имеет не более двух ошибок, то оно было таким:

r (x) = x + x³ + x⁵ + x⁴ = x + x³ + x⁴ + x⁵

Чтобы получить исходное слово делим кодовый многочлен r (x) на порождающий многочлен g (x).

I (x) = x + x².

Листинг 4. Декодер, принявший ошибку в пятом бите и исправивший ее.

Из листинга 4 видно, что расчётные данные совпали с данными программы.