9.3  Код з перевіркою на парність

 

Найпростіший лінійний блоковий код - це (n-1, n) - код з контролем парності. Цей код, зокрема, широко використовується у модемах.

Кодування полягає у додаванні до кожного байта 9-го контрольного біта так, щоб доповнити кількість одиниць у байті до наперед вибраного для коду парного (even) або непарного (odd) значення.

Наприклад, задана інформаційна послідовність (101), тоді кодовим словом буде (1010), де перевірний символ знаходиться додаванням за mod 2 символів інформаційної послідовності. Якщо число одиниць в інформаційній послідовності парне, то значенням суми за mod 2 буде 0, якщо непарне - то 1, отже, перевірний символ доповнює кодову послідовність так, щоб кількість одиниць в ній була парною.

Математично схему кодування з перевіркою на парність можна записати так:

Е(m1, ... , mk)=(m1, ..., mk, mk+1),

 

де перевірний символ

 

Отже, кількість одиниць в прийнятій послідовності повинна бути парною, тобто .

Схему декодування можна записати так:

 

Уведемо поняття двійкового симетричного каналу, для якого помилки у бітах рівноймовірні й незалежні. Схематично двійковий симетричний канал зображений на рис. 3.1, де р - ймовірність безпомилкової передачі біта повідомлення; q = 1-p - ймовірність помилкової передачі.

 

 

 

 

 

 

 

Для такої схеми передачі даних ймовірність того, що у n-позиційному коді виникне тільки одна помилка, становить .

У загальному випадку ймовірність передачі n бітів з k помилками визначається за формулою Бернуллі

 

                                                   (3.1)

 

де - кількість сполук з n елементів по k.

Додамо, що код з перевіркою парності не виявляє помилки кратності 2, оскільки, якщо у переданій послідовності виникло 2, 4 і т. д. помилки, незалежно, в якій позиції, то загальне число одиниць в прийнятій послідовності стане парним, і помилки виявлені не будуть. Проте ймовірність двократної помилки значно менша, ніж поодинокої. Покажемо це на прикладі.

Приклад  Перевірка парності при k=2 реалізується таким кодом: 00→000, 01→011, 10→101, 11→110.

Позначимо через р ймовірність правильної передачі, q – ймовірність помилки у біті повідомлення.

Тоді ймовірність виникнення хоча б однієї помилки у кодовій послідовності завдовжки 3 біти P=q3+3pq2+3p2q. З них не будуть виявлені помилки у двох бітах, що не змінюють парності, ймовірність яких Pпом=3pq2.

Ймовірність помилкової передачі повідомлення з двох бітів без використання контролю парності Pпом=q2+2pq.

Для достатньо надійного каналу передачі, тобто при q << 1, 3pq2 << q2+2pq, що свідчить про доцільність використання завадостійкого кодування з виявленням поодиноких помилок.

Не зважаючи на простоту і не дуже високу ефективність, коди з перевіркою на парність широко використовуються у системах передачі і зберігання інформації. Їх цінують за невисоку надлишковість: достатньо додати до інформаційної послідовності один перевірний символ - і можна визначити, чи є у прийнятій послідовності помилка. Проте локалізувати місце виникнення помилки, й відтак її виправити неможливо. Можна лише повторити передачу помилкової комбінації.