Лабораторна робота №4

Визначення 4.1. Мінімальна кількість символів, в яких всі кодові комбінації відрізняються один від одного, називається кодовою відстанню.

Для виправлення однієї помилки кодове відстань повинна бути не менше 3 ().

Для того щоб в ухваленому повідомленні можна було виправляти помилки, кодова комбінація повинна володіти деякою надмірністю, яка досягається за рахунок додавання контрольних розрядів. Число коригувальних розрядів повинно відповідати таким вимогам.

Нехай r- число коригувальних символів, k- кількість інформаційних розрядів, n- довжина коду, тоді

Код Хеммінга є типовим прикладом систематичного коду і може будуватися на основі виробляє матриці. Породжує матриця має k рядків і n стовпців.

Породжує матриця G може бути представлена ​​двома матрицями, одиничною і додаткової. При виборі додаткової матриці враховують, що вага (вагою довічного вектора називається величина відстані Хеммінга від нього до нульового вектора) кожного рядка не повинен бути менше.

Кодування реалізується за допомогою множення інформаційної комбінації # 945; на породжує матрицю

Перевірочна матриця Н при довічним кодуванні є транспоновану додаткову матрицю, доповнену одиничної. Перевірочна матриця має r рядків і n стовпців. Причому стовпці представляють собою значення синдрому для розряду, що відповідає номеру цього стовпчика.

Для визначення синдрому необхідно помножити кодову комбінацію на транспоновану перевірочну матрицю

Завдання. Методом Хемминга закодувати комбінацію # 945; = 1101, побудувавши породжує перевірочну матриці. Внести помилку в один з розрядів кодового вектора; знайти синдром; знайти і виправити помилку.

Неважко бачити, що число інформаційних розрядів k = 4, визначимо r, n.

Для розрахунку r можемо використовувати емпіричну формулу. Отримаємо r = 3, n = 7.

Маємо (7,4) - кодування. Породжує матриця G має розмірність 4 × 7, а перевірочна - 3 × 7.

Побудуємо перевірочну матрицю Н, так щоб її стовпці були різні і не містили нульову комбінацію:

Будуємо породжує матрицю G:

кодова комбінація # 946; має вигляд # 946; = # 945; G = 1101010,

Внесемо помилку в третій розряд = 1111010, обчислимо синдром = 101, що відповідає помилку в третьому розряді. Виправлена ​​кодова комбінація # 946; ісп = 1101010.

Методом Хемминга закодувати зазначені інформаційні комбінації, побудувавши породжує перевірочну матриці. Внести помилку в один з розрядів кодового вектора; знайти синдром; знайти і виправити помилку.

Схожі статті