Зразки розв'язування задач до розділу 11

 

Приклад 1  Закодувати повідомлення 11001010110 двійковим кодом Хеммінга. Побудувати твірну матрицю коду. Навести приклад виправлення помилки і декодування повідомлення. Визначити надлишковість коду.

Розв'язання

                При використанні завадостійкого (k, n)- коду Хеммінга контрольні суми, що додаються до інформаційного повідомлення, необхідно розмістити не в правій частині кодового слова, а в позиціях цілого степеня 2. Тоді стовпці перевірної матриці коду H(n-k)n будуть двійковим поданням номера розряду кодової комбінації, в якому виникла помилка.

У даному випадку кількість інформаційних елементів k=11.

Необхідна кількість перевірних розрядів r=4 (див. табл.3.3).

Отже, потрібно побудувати (11, 15) -код Хеммінга для заданого повідомлення. 

Перевірна матриця (11, 15) -коду Хеммінга має вигляд

.

                Систему перевірних рівнянь, що визначає правила знаходження перевірних розрядів (контрольних сум), дістанемо з рівняння кодового синдрому

S=uH=0,

де u – кодове слово лінійного блокового коду, заданого перевірною матрицею H.

S=(u1, u2, …, u15) = (u8+u9+u10+u11+ +u12+u13+u14+u15,, u4+u5+u6+u7+u12+u13+u14+u15, u2+u3+u6+u7+ +u10+u11+u14+ u15,,  u1+ u3+u5+u7+u9+u11+ u13+u15) = 0.

                Звідси випливає система рівнянь

                              

                Перевірні розряди - це біти з номерами цілого степеня 2 – u1, u2, u4, u8, інші розряди - символи інформаційного повідомлення, тобто кодове слово будується так:

,

де m=(m1, m2, …, m11) – інформаційне повідомлення; r1, r2, r3, r4 – контрольні суми.

                Система перевірних рівнянь коду має вигляд

                                                                  ()

                Закодуємо задане повідомлення: 

.

                Скориставшись системою перевірних рівнянь (), знайдемо контрольні суми:

                               r1=1+1+0+1+1+1+0=1;

                               r2=1+0+0+0+1+1+0=1;

                               r3=1+0+0+0+1+1+0=1;

                               r4=1+0+1+0+1+1+0=0.

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

                (11001010110) (111110001010110).

                Нехай у цьому кодовому слові при передачі виникла помилка, наприклад, прийнятий вектор y=(111110101010110).

                На прийомній стороні обчислюється синдром 

                               S = yH = (111110101010110)

                 =  (0111).

                Ненульове значення кодового синдрому означає наявність помилки у прийнятій послідовності. Вектор синдрома відповідає номеру помилкового розряду у двійковому вигляді: у даному випадку (0111)2=710 – отже, помилка виникла у 7-му розряді.

                Змінюємо значення помилкового біта і декодуємо кодову послідовність, вилучивши з неї контрольні суми, так:

(111110101010110)(111110001010110)

 (11 001010110).

                Твірна матриця коду будується таким чином, щоб стовпці з номерами нестепеня 2 відповідали інформаційним елементам повідомлення, тобто утворювали одиничну підматрицю, а стовпці з номерами степеня 2 (перевірна частина матриці) визначалися рівняннями знаходження відповідних контрольних сум.

                У такий спосіб, твірна матриця (11, 15) -коду Хеммінга має вигляд

.

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

                u=(m1, m2, ..., m11) =

=

 

 

                Звідси випливає система перевірних рівнянь коду ().

                Надлишковість коду .