Завадостійке кодування та декодування. Загальний підхід щодо формування надлишкових символів

Зрозуміло, що надлишкові символи в загальному випадку при контролі цілісності інформаційних об’єктів повинні дозволити:

1. Виявити наявність спотворення (є порушення цілісності чи немає);

2. Виявити місце спотворення;

3. Виявити величину спотворення;

4. Виправити виявлені спотворення.

Для цього, як уже наголошено, в будь-якому завадостійкому коді до інформаційного об’єкту необхідно додати контрольну ознаку (R), яка є функцією від цієї інформації.

,

де: А – вихідний інформаційний об’єкт (чи його певна частина);

R – контрольна ознака, деякий образ, відображення інформаційного об’єкту, сформоване у відповідності із процедурою (протоколом) .

Однією з найпростіших процедур, яка може бути застосована як , є додавання інформаційних символів:

, (1)

де R – контрольна ознака, і – номер символу інформації, m – кількість інформаційних символів, – чисельне значення і –го символу вихідного інформаційного об’єкта.

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

. (2)

Нехай така контрольна ознака є k – символьним кодом. Цей k – символьний код якимось чином приформовується до початкової послідовності. Для спрощення, в межах цих міркувань, будемо вважати, що приформування здійснюється у молодші розряди, коли контрольні символи набувають номери від 1 до k. Це є еквівалентним зсуву інформаційних символів на k позицій, так що інформаційні символи набувають номери від до . В останніх виразах: , m – кількість символів в інформаційній частині, k – кількість надлишкових символів, – значення і – го символу інформаційного об’єкта, – їх вагові коефіцієнти.

Ця процедура носить назву завадостійкого кодування інформаційних об’єктів, а одержана послідовність є завадостійким кодом в разі, коли при спотворенні будь-якого з символів цієї послідовності існує можливість виявити чи виявити й усунути таке спотворення.

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

Як перший операнд можуть обиратися сукупність символів чи окремі символи, що, в загальному випадку, можуть мати однакову чи різну розрядність. В найпростішому випадку розрядність символів може бути однаковою і дорівнювати, наприклад, b = 1, 2, … двійковим символам.

Дата добавления: 2014-01-04