Код умовних лишків
Теорія інформації та кодування
Код умовних лишків. Алгоритми кодування – декодування
Вступ
Нагадаємо, що загальні питання щодо системи числення в лишкових класах були розглянуті в попередній лекції. Варто нагадати, що ця лекція є останньою у модулі 4, а отже наступне лекційне заняття – МКР.
Лекція № 4.8 “Код умовних лишків. Алгоритми кодування – декодування”.В лекції розглядаються наступні питання:
1. Код умовних лишків. 3
2. Алгоритми кодування-декодування ЛУ-коду. 9
2.1. Алгоритм нулізації 10
2.2. Використання z - алгоритму. 13
Чудовою властивістю системи лишкових класів (СЛК) є те, що в неї легко вводяться властивості виявлення і виправлення спотворень. Відомо, що якщо ввести ще одну, контрольну, основу рк, то представлення А в розширеному діапазоні R [0, R) R = P·рк , у вигляді
А = α1, α2 ., αт, αк (1)
де: αк – залишок по основі рк, має чудову властивість для побудови кодів, що коректують.
Це пов’язано із тим, що при певних умовах при зазначеному виборі величини контрольної основи pк будь-яке спотворення в одному із лишків призводить до виходу спотвореного числа (за умовою не спотворене число 
) із робочого діапазону [0, P) за його межі, тобто в контрольний діапазон
[P, R). Такий вихід, як побачимо пізніше, досить легко виявляється.
Звернемо увагу на те, що при цьому повний діапазон [0, R) представлення числа, як сукупності із п = (т + 1) лишків, можна розглядати, по-перше, як сукупність із pк піддіапазонів величиною [0, P) кожен, які можуть бути пронумерованими від 0 до (pк – 1), де перший із них є робочим, а решта як раз і утворюють контрольний діапазон [P, R). По-друге, цей же діапазон [0, R) можна розглядати як сукупність із (pі – 1) піддіапазонів величиною [0, Ri) , де 
, які можуть бути пронумерованими від 0 до (pі – 1).
Рис. 1. До представлення повного діапазону
Залежно від того, які піддіапазони розглядати, розрізняють декілька алгоритмі виявлення чи виявлення та виправлення спотворень. Ці алгоритми розглянемо нижче.
Для визначення ж потрібного значення контрольної основи будемо застосовувати уявлення повного діапазону [0, R) у вигляді сукупності із pі піддіапазонів величиною [0, Ri).
Тоді, як уже розглядалося раніше (лекція 4.4) будь-яке випадкове спотворення можна розглядати у вигляді суми (т+1) символьних векторів – початкового коду А і випадкового вектора Е.
,
де, згідно із правилами виконання операцій в системі лишкових класів, усі операції додавання здійснюються за певним модулем, а відповідні вектори мають наступні значення:
,
.
В останніх виразах: Е – величина спотворення; 
– значення не спотвореного символу (лишку по основі із номером і; 
– номер піддіапазону величиною
[0, Ri), в який потрапляє число, спотворене по основі із номером і; 
– величина цього інтервалу; 
– значення спотвореного символу, 
– величина спотворення і – го символу.
На числовій вісі ці вектори, як числа із діапазону [0, R), можуть мати представлення, наведене на рис. 2.
Рис. 2. До виходу спотвореного числа за межі робочого діапазону
Оскільки, за визначенням, спотворені числа повинні задовольняти умові
> Р, то звідсіля для задач контролю наявності спотворень неважко визначити вимогу до величини контрольної основи цієї системи, і здійснити, в подальшому, її вибір. Отже, для виявлення наявності спотворень досить визначити, в якому із діапазонів (робочому чи контрольному) знаходиться число, правильність якого перевіряється. Для цього слід вимагати, щоби спотворення лишку (символу початкового числа А) по будь-якій основі, наприклад, по основі 
збільшувало б початкове не спотворене число А < P:
А = 
на величину, яка забезпечує вихід спотвореного числа в контрольний діапазон, тобто на величину
.
Тоді, за рахунок цього, спотворене число
,
перейде із початкового діапазону [0, Р) в деякий піддіапазон контрольного діапазону (див. рис. 2), наприклад, в діапазон [
, 
) величиною 
.
Таким чином буде забезпечена умова:
.
Звідси після скорочення на 
витікає:
,
а отже, при найменшому значенні 
= 1,
, (2)
тобто умовою однозначного визначення наявності спотворень є перевищення величиною контрольної основи величини будь-якої із інших основ: при pк > pт, де pт – найбільша із основ, будь-яке спотворення в одному з лишків αі може бути виявленим.
В задачах контролю та поновлення цілісності недостатньо лише установити факт наявності порушення цілісності інформаційного об’єкту, а потрібно визначити місце спотворення та його величину. Зрозуміло, що для вирішення задач виявлення місця та, особливо, величин спотворень, необхідно забезпечити ідентифікацію спотвореного числа (чи величини спотворення) із номером основи (для нашого прикладу – і чи j), по якій таке спотворення має місце, та визначення (в подальшому) величини цього спотворення (відповідно 
чи 
). Для цього можна використати той факт, що спотворення по основі 
переводить спотворене число
(див. рис. 2) в діапазон [
, 
] величиною 
.
Із наведеного витікає, що механізми визначення наявності, місця виникнення та величини спотворення повинні ґрунтуватися на виявленні тим чи іншим шляхом хоча б однієї із таких взаємно пов’язаних величин як і, 
, та, відповідно, 
, 
, 
, 
. Із наведеного витікає також, що для ідентифікації спотвореного числа (чи величини спотворення) із номером основи і слід забезпечити попадання спотворених по різним основам чисел в різні діапазони, що, в свою чергу, є можливим при умові, що відстань між двома довільними діапазонами, в які можуть потрапити спотворені числа, перевищувала б максимальне значення не спотвореного числа (Р). Наприклад, при 
> 
(при зворотному співвідношенні результат не зміниться):
> + P, чи 
– 
> P.
Звідси:
– 
> P,
– 
> 1,
,
.
Оскільки шукане значення контрольної основи повинно перевищувати величину, яка визначається дробовим числом, то для пошуку максимального значення цієї величини слід визначити максимальне значення чисельника та мінімальне значення знаменника. Максимальне значення чисельника в цьому виразі дорівнює добутку двох найбільших із основ системи числення 
, а мінімальне значення знаменника (це цілочисельна величина!):
,
оскільки дорівнювати нулю знаменник може лише тоді, коли:
,
що, в свою чергу, є досяжним лише при 
, а 
, і що є неможливим (нагадаємо, що основи системи числення, наразі це величини 
, є взаємно простими числами). Отже, в разі визначення величини та місця спотворення по факту попадання спотвореного числа до інтервалу 
, вимога до величини контрольної основи із урахуванням, що вираз у знаменнику обраховується за модулем, може бути записаною у вигляді:
. (3)
Це означає, що при представленні чисел у вигляді (1)
А = α1, α2 ., αт, αк (1)
створюється завадостійкий код з можливостями або виявлення спотворень, або і їх корекції (при виборі
у відповідності до (3) ).
Такий код має принаймні 2 недоліки. Перший з них пов’язаний з тим, що можливі спотворення знаходяться і виправляються (спотворений символ поновлюється) тільки в тому випадку, якщо спотворений лише один з символів αі, тобто спотворення повинні бути фіксованими в межах однієї з груп розрядів. Але цей недолік, як ми знаємо, є притаманним будь-якому із відомих нам кодів. Як долати цей недолік ми знаємо.
Другий пов’язаний з необхідністю роботи з числами в системі числення в лишкових класах. Цей недолік досить просто усувається в коді умовних лишків, який вводиться таким чином.
Хай є код деякого числа А, представленого в будь-якій системі числення, зокрема позиційною, наприклад двійковою. Для визначеності, хай це число А представлено послідовністю з нулів і одиниць. Розіб’ємо цю послідовність певним (у загальному випадку довільним) чином на m груп, як і для решти узагальнених кодів.
Як і раніше код кожної i - ї групи (пакету) розглядатимемо як b - значний розряд αi, який може приймати будь-яке із s значень від 0 до (s – 1), де s = 2b, але вважатимемо цей код є залишком деякого умовного числа А по основі pi. Оскільки величина αi, як елемент початкового числа
0 ≤ αi ≤ s - 1
а як залишок від ділення А на pi
0 ≤ αi ≤ pi,
то для представлення коду будь-якої групи у вигляді лишку по основі pi необхідно, щоб виконувалася умова
pi > s – 1,
інакше в групу з b розрядів може бути записаним код αі > pi, що в лишкових класах не допустимо.
Приклад 1. Хай b =3, s = 7, тоді αi може приймати значення 000, 001, 010 ..., 111. При pi = 5 максимальне значення αi обмежується кодом 100, тобто коди 101, 110, 111 є і “неправильними”. Якщо ж узяти pi > 7, наприклад pi = 9, тоді максимальне значення αі обмежується не величиною pi, а розрядністю групи b, тобто αmax = 111.
При такому підході будь-які комбінації початкового коди числа A “вписуються” в систему числення з основами pi (і = 1, 2 ..., m). Якщо розширити систему основ на контрольне pk і для отриманого набору умовних лишків αi (і = 1, 2 ...) розрахувати умовний лишок αk, то на отримане в СЛК умовне число
А’ = α1, α2,.., αm, αk (4)
розповсюджується можливості CЛК по виявленню і виправленню помилок, тобто отриманий код (4) має всі властивості коду (1), але останній код може бути одержаним для будь-якої двійкової послідовності, а не тільки по відношенню до чисел в лишкових класах. Відзначимо, що таким чином усунений другий недолік коду (1).
Оскільки для визначення контрольної ознаки, тобто для кодування будь-якої послідовності двійкових цифр завадостійким кодом, умовно, не реально, не фізично, групи розрядів початкового числа розглядаються як деякі лишки (залишки), то такий код отримав найменування коду умовних лишків (ЛУ – код).
Слід звернути увагу на те, що при кодуванні ЛУ-кодом початкова послідовність не міняється, до неї тільки приформовуются додаткові, обчислювані по окремих правилах, контрольні символи.
Таким чином, ЛУ-код дозволяє виявляти і виправляти b - розрядні пакети помилок, згруповані в межах будь-якої з n груп і потребує при цьому надмірність біля
r ≈ 2b + 1
розрядів (оскільки рk ≥ 2рn∙рn+1, r = [log2рk] + 1). У конкретних випадках ця надмірність може відхилятися в ту або іншу сторону, що залежить також від алгоритмів кодування-декодування.