Переваги та недоліки кодування у системі залишкових класів

 

Таким чином, виконання арифметичних операцій у модулярному коді відбувається незалежно по кожному з модулів, що й вказує на паралелізм даної системи. Ця обставина визначає порозрядне виконання операцій. Дана властивість позбавляє від необхідності «позичати» або «переносити» одиницю старшого розряду, що приводить до появи кодів з паралельною структурою. Це дозволяє розпаралелити алгоритми при виконанні арифметичних операцій.

Звичайно, і ця система не позбавлена недоліків. До них ставиться неможливість візуального порівняння чисел, відсутність ознак виходу результатів за межі діапазону, обмеженість дії системи сферою цілих додатних чисел. Основним недоліком СЗК є відсутність операції ділення. Однак СЗК можна успішно використовувати у спеціалізованих обчислювальних машинах для виконання операцій додавання, віднімання та множення, наприклад, у задачах криптографії. Необхідно відмітити, що ця система особливо ефективна при обчисленнях з великими числами.

 

3. Ефективність математичних операцій у системі залишкових класів

 

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

Нехай операнди А та В, а також результати операцій додавання й множення А + В и А·В представлені відповідно залишками , , за модулями , причому обидва числа та результати перебувають у діапазоні [0, P), то .

Справедливість цих правил виконання арифметичних дій у СЗК безпосередньо випливає із властивостей конгруенцій.

 

4. Надлишковість та здатність виявляти та виправляти помилки

 

Під узагальненими розумітимемо коди, призначені для виявлення (виявлення й виправлення) пакетних викривлень, у яких використовуються алгоритми кодування й декодування, аналогічні відповідним алгоритмам двійкових кодів, але по відношенню до b-розрядних, узагальнених символів (УС).

У цих кодах початкова двійкова кодова послідовність — базове кодове слово І1, І2, …, Іn розбивається на n= k/b узагальнених b-розрядних символів — груп двійкових розрядів з розрядністю b, в яких передбачається виявлення та виправлення викривлень: І1………Іb, Іb+1…………І2b,…, Іm-b+1 ……Іn.

Двійкові символи, що входять до однієї b-розрядної групи, розглядаються як b-значний УС, який може приймати будь-яке із s значень від 0 до s – 1, де s = 2b.

Код умовних лишків (лишків умовних код — ЛУ-код) є одним із прикладів узагальнених кодів. Теоретичною основою ЛУ-коду є теорія залишкових класів. Із цієї теорії відомо, що будь-яке число можна представити у вигляді набору лишків від розподілу цього числа на набір взаємно простих чисел, які мають назву основ системи числення, — pi, де і = 1, 2, …, n, n — кількість таких основ. Вибір величини nздійснюється з умови, яка викладена нижче. Тоді: А = α1, α2, …, αn,
де α = А – [А/pi]·pi, а позначка [А/pi] означає операцію розрахунку цілої частини від дробового числа А/pi. При цьому між числом А та його уявленням існує взаємна однозначна відповідність якщо:

.

У цьому виразі величина Р — діапазон представлення або робочий діапазон чисел. Звернемо увагу на те, що величина αі представляє собою групу двійкових розрядів, кількість яких не перевищує розрядності відповідної основи pi.

Чудовою властивістю системи залишкових класів (СЗК) є те, що до неї легко вводяться властивості виявлення та виправлення викривлень. Відомо, що якщо ввести ще одну, контрольну, основу рk, то уявлення А в розширеному діапазоні R = P·рk, у вигляді А = α1, α2, …, αn, αk,
де αk — лишок по основі рk,має чудову для побудови корегуючих кодів властивість: при pk > pn будь-яке викривлення в одному з лишків αі може бути знайденим, а при pk >2·pn·pn–1, де pn, pn–1 — найбільші з основ, може бути й виправленим. Це означає, що при представленні чисел створюється завадостійкий код із можливостями або виявлення викривлень, або їхньої корекції.

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

Нехай існує код деякого числа А, представленого в будь-якій системі числення, зокрема, позиційній, наприклад, двійковій. Для визначеності, нехай це число А представлено послідовністю з нулів і одиниць. Розіб’ємо цю послідовність певним (у загальному випадку довільним) чином на n груп, як і для решти узагальнених кодів.

Як показано вище, код кожного i-го УС слід розглядати як s-значний УС αi, який може приймати будь-яке зs значень від 0 до s - 1, де s = 2b. Будемо умовно вважати цей код лишком деякого умовного числа А по основі pi. Оскільки величина αi, як елемент початкового числа 0 ≤ αi ≤ s - 1, а як лишок від ділення А на pi≤ αi ≤ pi, то для представлення коду будь-якої групи у вигляді лишку по основі pi необхідно, щоб виконувалася умова:
pi > s – 1, інакше в групу з b розрядів може бути записаним код αі ≥ pi, що в лишкових класах не припустимо.

При такому підході будь-які комбінації початкового коду числа А «вписуються» в систему числення з основами pi (і = 1, 2,...). Якщо розширити систему основ на контрольну pk і для одержаного набору умовних лишків αi (і = 1, 2,...) розрахувати умовний лишок αk, то на одержане умовне число А = α1, α2, …, αn, αk (3) розповсюджуються всі можливості СЗК по виявленню й виправленню викривлень, тобто одержаний код має всі властивості попереднього коду, але останній код може бути отриманим для будь-якої двійкової послідовності, а не тільки по відношенню до чисел у лишкових класах.

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

Слід звернути увагу на те, що при кодуванні ЛУ-кодом початкова послідовність не змінюється, до неї тільки приформовуються додаткові, обчислені за окремими правилами, контрольні символи. Такий код дозволяє знаходити й виправляти b-розрядні пакети викривлень, згруповані в межах будь-якого зn УС, і потребує при цьому надмірності біля
r ≈ 2b + 1 двійкових розрядів (оскільки , . У конкретних випадках ця надмірність може відхилятися в ту або іншу сторону, що залежить також від алгоритмів кодування–декодування.

 

Тема 17. Коди Галуа.

План

1. Методика формування кодів Галуа, їх переваги.

2. Надлишковість та здатність виявляти та виправляти помилки