2.Алгоритми кодування-декодування лу-коду

Оскільки в основі ЛУ-коду лежать властивості CЛК, то в цьому коді принципово можуть бути використані відомі алгоритми кодування-декодування. У основі цих алгоритмів лежить той факт, що будь-яке спотворення в одній з груп розрядів α_і переводить початкове число з робочого діапазону [0, P = ) у діапазон [P, R = p_k∙Р), тобто приводить до збільшення початкового числа А < Р на деяку величину ΔА = l_i·R_i. Тут l_i та R_i = R/ p_i – цілі числа. Дійсно, якщо початкове число

А = α₁, α₂ ., α_i…,α_m, α_k

спотворено по основі p_i і має вигляд

= α₁, α₂ ., ,…, α_m, α_k

де

_і = {α_i + Δα_i } (mod p_i),

то це еквівалентно наступному перетворенню

= (α₁, α_2, ..., α_і,…, α_m, α_k) + (0, 0, ..., Δα_i,…, 0, 0) =

= (α₁, α₂ ,..., { α_i + Δα_i } (mod p_i),…, α_m, α_k)

При цьому величина спотворення перевищує величину робочого діапазону Р

ΔА = (0, 0 ..., Δα_i ..., 0, 0) > Р

оскільки тільки число виду

ΔА = l_i·R_i = l_i·R/p_i

має всі лишки, окрім лишку по основі p_i, такі, що дорівнюють нулю. Але ΔА = l_i·R/p_i > P = R/p_k оскільки навіть при l_i = 1 величина R/p_i > R/p_k з тієї причини, що p_k > p_i .

Отже, сума = А + ΔА > Р, тобто спотворене число вийшло за межі робочого діапазону Р і потрапило в діапазон [P, R).

Відомі з алгоритми кодування-декодування якраз і використовують цей факт. Найбільш опрацьований і реалізований практично алгоритм нулізації.

2.1.Алгоритм нулізації

Суть алгоритму нулізації зводиться до того, що як при кодуванні, так і при декодуванні по першим m лишкам α_i (i = 1, 2,..., m) із спотвореного числа

= (α₁, α₂ ..., { α_i + Δα_i } (mod p_i),…, α_m, α_k)

послідовно формуються, так звані мінімальні числа вигляду

t₁ = (α₁, , , _{..., ,} ),

t₂ = (0, (α₂ – ) (mod p₂), _,…, , ),

t₃ = (0, 0, (α₃ - - ) (mod p₃), _., , ),

........................

t_n = (0, 0, 0 ...,(α_n - ) (mod p_m), ),

де t_і (наприклад, t₃) – мінімальне із усіх можливих чисел, які мають лишок по основі p_і (наприклад, р₃) такий, що на і – тому кроці нулізації дорівнює різниці по відповідному модулю між початковим значенням цього символу (наприклад, а₃) і сумою значень символів із цим же номером, які одержані на попередній кроках (наприклад, + ). Звернемо увагу також на те, що оскільки на цьому кроці нулізації усі символи із номерами (наприклад, із = 1, 2) дорівнюють нулю, то це означає, що відповідне мінімальне число є кратним усім p_і із номерами (наприклад, р_1, р₂), тобто є кратним добутку (наприклад, р_1∙ р₂).

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

Cума мінімальних чисел Т = має наступні дві властивості. По-перше, лишки цієї суми по всіх основах, окрім р_k завжди дорівнюють лишкам початкового числа Р. По-друге, відомо, що величина цієї суми завжди менше величини робочого діапазону Т < Р, тобто величина Т лежить а межах робочого діапазону і для неспотворених чисел Т = А.

Неважко помітити, що в останньому випадку в разі відсутності спотворень Т = А процес одержання величини α_k є процесом кодування початкового числа ЛУ-кодом, оскільки значення А залежить тільки від цього початкового числа і не залежить від невідомої при кодуванні величини лишку по контрольному модулю р_к (це означає, що знати значення α_к до кодування не має потреби). Цей лишок (шукана контрольна ознака) α_к формується як сума по модулю р_к проміжних величин t_і (і = 1, 2, ..., n) чи їх лишків по основі р_к, тобто

α_k = (mod р_к) = (mod р_к).

Після кодування цілком сформоване число як набір лишків по усім основам, включаючи контрольну:

А = (α₁, α₂ ..., { α_i + Δα_i } (mod p_i),…, α_m, α_k)

передається в канал.

При декодуванні по прийнятому, можливо спотвореному числу знову формується величина T, яка віднімається з числа . Це приводить до того, що отримана різниця

Г = – T = (0, 0, 0 ..., , γ) = k∙Р

має по всіх основах, окрім контрольної, лишки, що дорівнюють нулю, а по контрольній

γ = (α_k – (Т mod р_к )) (mod р_к) = (k∙Р) (mod р_к),

тобто

- T = (0, 0 ., 0, ...,0, (k·Р) (mod р_к)),

де k може приймати будь-яке значення із діапазону k = 0, 1, 2, ..., р_k –1.

Для неспотворених чисел, тобто при k = 0, величина γ = 0, для спотворених − γ ≠ 0. Вище доведено, що при р_k ≥ 2·р_m·p_m-1 є взаємно однозначна відповідність між величиною помилки Δα_i і величиною γ, що дає можливість, отримавши γ, визначити місце і величину помилки, тобто здійснити її виправлення.

Недоліками цього алгоритму є:

1) обчислення величини T здійснюється послідовно, оскільки значення чергової величини t_j може бути визначеним тільки при відомих попередніх t_i (і = 1, 2, ..., j -1), що виключає можливість розпаралелювання процесу і досягнення при цьому високої швидкодії алгоритму;

2) багаторозрядність мінімальних чисел t_j, оскільки перше мінімальне число потребує N розрядів, друге – (N – b)..., m - не – (N – (m – 1)∙b) розрядів, що вимагає наявність ЗП великій ємності;

3) відсутність розрахункових співвідношень між Δα_i і γ, що потребує використовувати таблиці відповідності типу (γ→ Δα_i).

Для ілюстрації можливостей алгоритму розглянемо два приклади.

Приклад 2. Хай необхідно закодувати з використанням алгоритму нулізації початковий код 110110, вважаючи, що можлива тривалість пакету спотворень b = 2. Тоді можливе розбиття початкового коду на три (n = 3) дворозрядні групи α₁ =11, α₂ =01, α₃ =10, s = 4, а як умовні основи можна вибрати р₁ = 4, р₂ = 5, р₃ = 7. При цьому значення контрольної основи (р_к > 2·р_n ·р_n-1 = 2·5·7 = 70) можна вибрати р_к = 71, що вимагає для свого відображення семи розрядів. В результаті цього для кодування формується код

А = 11.01.10.0000000.

Перше мінімальне число t₁ повинне мати залишок по першій основі, який дорівнює 11₍₂₎= 3₍₁₀₎. Таким числом є t₁ = 3 або при представленні в СЛК з вибраними основами

t₁ = 11.11.011.0000011.

Друге мінімальне число t₂ повинне мати залишок по першій основі, рівний нулю (тобто число, яке є кратним 4), а по другій

((α₂ - ) (mod p₂) = (1 – 3) (mod 5) = 11₍₂₎.

Мінімальним числом, що має такі залишки по першій і другій основах, є t₂ = 8, тобто

t₂ = 00.11.001.0001000.

Третє мінімальне число t₃ повинне мати нульові залишки по перших двох основах (тобто число, яке є кратним 20), а по третьому

((α₃ - - ) (mod p₃) = (2 – 3 - 1) (mod 7) = 5 = 101₍₂₎.

Мінімальним числом, що має такі залишки, є t₃ = 40, тобто

t₃ = 00.00.101.0101000.

Тоді сума цих чисел Т= рівна 51, тобто

Т = 11.01.10.0110011.

Код Т = А є шуканим результатом кодування.

Звернемо увагу на те, що величини t₁, t₂, t₃ формуються послідовно, а також на їх велику розрядність.

Приклад 3. Декодувати з використанням алгоритму нулізації для умов прикладу 2 код = 11.01.01.0110011, в якому спотворена третя пара розрядів. Як і раніше

t₁ = 11.11.011.0000011 = 3₁₀.

t₂ = 00.11.001.0001000 = 8₁₀.

Для третього мінімального числа t₃

((α₃ - - ) (mod p₃) = (1 – 3 - 1) (mod 7) = 4 = 100₍₂₎.

Мінімальним числом (тобто числом, яке є кратним 20), що має такі залишки, є t₃ = 60, тобто

t₃ = 00.00.100. 0111100

При цьому

Т = =71,

тобто оскільки Т (mod 71) = 0, то

Т = 11.01.01.0000000

і

γ = (α_k – (Т mod р_к )) (mod р_к) = (0110011 - 0000000) (mod 71) = 51.

Оскільки γ ≠ 0, то робиться вивід про наявність в декодованому числі помилки. Оскільки, при цьому

γ = (k·Р) (mod р_к) = (k·140) (mod 71),

то k = 10, тому що 1400 (mod 71) = 51.

Нескладно переконатися в тому, що декодоване число A = 1471 може бути отримано тільки в результаті спотворення початкового числа А = 51 на величину ΔА = 1420 = = 00.00.110.0000000, тобто при спотворенні третьої групи розрядів на величину Δα₃ = 110, після чого корекція результату здійснюється просто:

α₃ = ( ₃ - Δα₃ ) (mod 7) – (1 – 6) (mod 7) = 2 = 10₍₂₎.

Порівнявши набутого значення з початковим, неспотвореним (умова прикладу 1), переконуємося в тому, що корекція проведена вірно.