МЕТОД ВИЧИСЛЕННЯ ІНТЕРВАЛЬНОГО НОМЕРУ У МОДУЛЯРНИХ КОДАХ ТА ЙОГО МОДИФІКАЦІЯ - Міжнародний журнал
Використання паралельних модульних кодів дозволяє не тільки підвищити швидкість обробки даних, але й забезпечити властивість відмовостійкості спеціалізованим обчислювальним пристроям, що функціонують у реальному масштабі часу. Серед модульних кодів займають коди поліноміальної системи класів відрахувань (ПСКВ). Дані коди, володіючи властивістю арифметичності, дозволяють будувати стійкі до відмови спецпроцесори, які здатні зберігати працездатний стан за рахунок зниження в допустимих межах основних показників якості. Щоб забезпечити корекцію результату в кодах використовують позиційні характеристики (ПХ), які дозволяють визначити місцезнаходження та глибину помилки. Розробка та модифікація методів обчислення позиційної характеристики – інтервальний номер, дозволять виконувати корекцію результату за менших апаратних та часових витрат, що є актуальним.
Діяльність розглянуто метод обчислення позиційної характеристики – інтервальний номер. Дана позиційна характеристика дозволяє здійснювати пошук та корекцію помилок у кодах ПСКВ. З метою зниження схемних витрат на реалізацію проведено модифікацію цього методу. Розроблені модифікації методу обчислення інтервального номера в кодах ПСКВ дозволили знизити схемні витрати на 3-5% порівняно з класичним методом при обробці 15-розрядних даних.
Паралельні непозиційні коди є базою для побудови стійких до відмови спеціалізованих обчислювальних пристроїв, що функціонують в реальному масштабі часу [1-3]. Коди поліноміальної системи класів відрахувань (ПСКВ), володіючи властивістю арифметичності, дозволяють будувати стійкі до відмови спецпроцесори, які здатні зберігати працездатний стан за рахунок зниження в допустимих межах основних показниківякості. Щоб забезпечити корекцію результату в кодах використовують позиційні характеристики (ПХ), які дозволяють визначити місцезнаходження та глибину помилки. Розробка та модифікація методів обчислення позиційної характеристики – інтервальний номер, дозволять виконувати корекцію результату за менших апаратних та часових витрат, що є актуальним.
У коді ПСКВ позиційний двійковий код, представляється в поліноміальній формі, а потім цього полінома у відповідність ставиться набір залишків [4-6]
, (1)
де; pi(z) – поліноми поля GF(2), що не наводяться; i = 1, ..., k.
Цей набір основ коду ПСКВ утворює робочий діапазон системи.
, (2)
Так як порівняння по тому самому модулю можна почленно складати, то для двох поліномів
і , справедливо
, (3)
, (4)
. (5)
де + і - Операція підсумовування та віднімання по модулю р.
Паралельна і незалежна обробка залишків є ідеальною основою для корекції помилок, що виникають через збої в роботі системи [7]. При цьому в кодах ПСКВ немає обміну даних між модулями. Цю властивість кодів ПСКВ використовують для виявлення та корекції помилки. Але для цього необхідно запровадити контрольні підстави.
Введення r контрольних підстав ПСКВ, які повинні задовольняти умову
, (6)
призводить до розширення робочого діапазону до повного діапазону
. (7)
В основу більшості алгоритмів та методів пошуку та корекції помилок у модулярних кодах покладено процедуру обчислення позиційної характеристики. Оскільки помилка перекладає правильний поліном , що лежить поза робочим діапазоном, то, знаючи номер інтервалу, куди потрапив спотворений поліном , можна визначити підставу, за якою сталася помилка, а такожїї глибину. Таким чином, для визначення розташування полінома, представленого кодом ПСКВ, потрібно обчислення позиційної характеристики (ПХ). При цьому немодульні операції визначення ПХ необхідно замінити на модульні операції, які успішно реалізуються в модулярних кодах [6-10].
Ця властивість модулярних кодів і зумовила підвищений інтерес розробників до позиційної характеристики - інтервальний номер полінома lінт (z). Процес визначення даної характеристики здійснюється згідно з виразом
. (8)
Незважаючи на те, що процедура (8) відноситься до немодульної, її зводять до сукупності модульних операцій. У роботі [6] представлено пристрій, що здійснює виявлення та корекцію помилки у модулярному коді на основі обчислення інтервального номера. В основу даного алгоритму покладено властивість подібності ортогональних базисів повної, що містить контрольні основи, та надмірної ПСКВ, згідно з яким
, (9)
де Bi*(z) та Bi(z) – ортогональні базиси надмірної та повної системи.
(10)
де.
Підставивши останню рівність у вираз (8) отримуємо
. (11)
де K(z) – ранг повної системи основ ПСКВ.
Оскільки безліч значень інтервального номера lінт(z) являє собою кільце по модулю Pконт(z), то вираз (11) перетворюється на вигляд
, (12)
де ранг надлишкової системи визначається виразом
. (13)
Якщо lінт(z) = 0, то вихідний поліном А(z) лежить усередині робочого діапазону і не є забороненим. Інакше А(z) – хибна комбінація. У табл. 1 представлені номери інтервалів, які потрапляють помилкові поліноми Al*(z),при виникненні одноразової помилки з підстав ПСКВ. У цьому поліноми p1(z) = z + 1, p2(z) = z2+ z + 1 та p3(z) = z4 + z3 + z2 + z + 1 є робочими основами. Як контрольні підстави обрані поліноми p4(z) = z4 + z3 + 1 і p5(z) = z4 + z + 1.
Розподіл одноразових помилок коду ПСКВ GF(24)
Інтервал, представлений у поліноміальній формі