Паритетні коди. Кодування за парністю та непарністю повідомлень і блоків даних

Паритетні коди є найбільш простою реалізацією перешкодостійкого кодування. Прикладом паритетних кодів можуть служити: коди з кодуванням за парністю; коди з кодуванням за непарністю; коди Хеммінга.

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

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

Приклад 6.1. Закодувати повідомлення 010101, використовуючи метод кодування:

а) за парністю;

б) за непарністю.

Розв’язок.

а) Для того, щоб закодувати повідомлення за парністю, необхідно до нього додати контрольний розряд таким чином, щоб загальна кількість одиниць в кодовій комбінації була парною. Оскільки в повідомленні 010101 значення 1 мають три розряди (непарна кількість), щоб загальна кількість одиниць в кодовій комбінації була парною значення контрольного розряду повинне дорівнювати 1.

Закодоване за парністю повідомлення буде мати вигляд 0101011.

б) Для того, щоб закодувати повідомлення за непарністю, необхідно до нього додати контрольний розряд таким чином, щоб загальна кількість одиниць в кодовій комбінації була непарною. Оскільки в повідомленні 010101 значення 1 мають три розряди (непарна кількість), щоб загальна кількість одиниць в кодовій комбінації була непарною значення контрольного розряду повинне дорівнювати 0.

Закодоване за непарністю повідомлення буде мати вигляд 0101010.

Декодування повідомлень, закодованих паритетним кодом, зводиться до перевірки відповідності кількості одиниць (включаючи контрольний розряд) використаному методу кодування. При отриманні повідомлення, закодованого за парністю (непарністю), приймач аналізує на парність кількість одиниць в ньому. Якщо кількість одиниць парна (непарна для кодування за непарністю), повідомлення визнається прийнятим вірно, а інакше – прийнятим з помилкою.

Приклад 6.2. Перевірити повідомлення на наявність помилки, якщо для кодування повідомлень використано метод кодування за непарністю. Отримані повідомлення мають вигляд: 00000; 10101.

Розв’язок.

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

В першому повідомлені 00000 кількість одиниць дорівнює 0, тобто, не відповідає вимогам непарності. Робимо висновок, що повідомлення 00000 містить помилку.

В повідомлені 10101 кількість одиниць дорівнює 3, що відповідає вимогам непарності. Робимо висновок, що повідомлення 10101 не містить помилок.

Недоліком наведених методів кодування за парністю та за непарністю є низька перевіряюча здатність. Легко побачити, що ці методи кодування спроможні виявляти лише непарну кількість помилок (1,3,5...), але не виявляють парні помилки (2,4,6..), оскільки вони не впливають на парність контрольної суми.

Більш ефективним є блочне кодування повідомлень за парністю (непарністю). При такому кодуванні принцип розрахунку значень контрольних розрядів залишається тим самим, але контрольні розряди приписуються до блоку повідомлень як по горизонталі (для рядків), так і по вертикалі (для стовпчиків). Останній контрольний розряд по вертикалі відповідає контрольній сумі за парністю (непарністю) останнього стовпчика, тобто визначається для контрольних розрядів, доданих по горизонталі. Таким чином, в результаті кодування цим методом блок даних розмірності MxN перетворюється в закодований блок розмірності (M+1)x(N+1).

Приклад 6.3. Закодувати за парністю блок даних

0000

1010

1111

1100

Розв’язок.

Виконаємо кодування за парністю блок даних по горизонталі (рядки блоку). Отримуємо наступний результат (додані контрольні розряди підкреслено):

0000 0

1010 0

1111 0

1100 0

Кодування блоку по вертикалі визначає кінцевий результат:

0000 0

1010 0

1111 0

1100 0

1001 0

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

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

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

00000

10100

10110

11000

10010

Розв’язок.

Щоб визначити наявність помилки в блоці даних, закодованому методом блочного кодування за парністю, виконаємо повторне кодування отриманого блока за аналогічною методикою (напівжирним шрифтом визначено вихідний блок даних; однією лінією підкреслені контрольні розряди, які були додані при передачі повідомлення; подвійною лінією підкреслені контрольні розряди, які були додані при повторному кодуванні для пошуку помилок):

0000 0 0

1010 0 0

1011 0 1

1100 0 0

1001 0

0100 0

Як видно, додатковий контрольний розряд в третьому рядку та в другому стовпчику дорівнюють 1. Це свідчить про наявність одиночної помилки на їх перетині. В результаті корегування помилки відновлюємо блок даних, що передавався:

0000 0

1010 0

1111 0

1100 0

1001 0

Вихідний блок даних має наступний вигляд:

0000

1010

1111

1100