Вбудований контроль пристроїв для опрацювання елементів розширених полів Галуа
Date
2018-02-26
Journal Title
Journal ISSN
Volume Title
Publisher
Видавництво Національного університету “Львівська політехніка”
Abstract
Двійкові коди елементів розширених полів Галуа є надлишковими, частина з них
ніколи не з’являються при нормальній роботі пристроїв опрацювання елементів таких
полів. Невикористані (заборонені) кодові комбінації можна задіяти для робочого
діагностування (вбудованого контролю) цих пристроїв. Ознакою помилки буде поява
будь-якої забороненої комбінації. У роботі порівнюються різні розширені поля Галуа за
можливістю організації робочого діагностування, визначаються поля, які якнайкраще
забезпечують його проведення. Зазначено, що для кодів елементів полів Галуа не існує
бітів, які мають суворо різні значення в дозволених та заборонених кодах. Можливість
діагностування пропонується оцінювати відношенням кількості заборонених комбі-
націй до загальної кількості комбінацій або до кількості дозволених комбінацій. Для
досягнення найбільшого ефекту діагностування рекомендується використовувати поля
з характеристиками, які є першим простим числом, більшим за степінь 2. З погляду
ціни діагностування, найкращим є поле GF(3m), для якого необхідно визначати лише
одну заборонену кодову комбінацію, що забезпечує виявлення усіх заборонених кодів. З
використанням розглянутих полів Галуа GF(dm) мінімальна кодова відстань для кодів
кожної цифри коду дорівнює 1. Це вказує на те, що виявити 100 % усіх навіть пооди-
ноких помилок у роботі розглянутих пристроїв запропонованим способом неможливо.
Пошук логічного виразу для позначення помилки ґрунтується на поділі групи
послідовних заборонених кодів на підгрупи. Для кожної підгрупи розряди її кодів ділять
на дві частини так, щоб старші розряди кожного коду з підгрупи залишалися
незмінними, а молодші - пробігали всі значення від 0...0 до 1...1. Тоді до мінімізованого
логічного виразу помилки у цій підгрупі кодів увійдуть тільки незмінні старші розряди.
Апаратна складність запропонованого методу квадратично залежить від кількості бітів,
якими кодується один розряд коду елементів розширених полів Галуа.
Binary codes of extended Galois fields elements are redundant, some of them never appear at the normal operation of the devices for processing of such field elements. Unused (forbidden) code combinations can be used to organize on-line testing (concurrent error detection) of the specified devices. The appearance of any forbidden combination will be a sign of error. The paper compares the various extended Galois fields with the possibility of on-line testing organization, the fields that best ensure its holding are determined. It is noted that there are no bits for the codes of the Galois field elements that have strictly different values in the allowed and prohibited codes. It is suggested to evaluate the possibility of realizing the testing by the ratio of the number of forbidden combinations to the total number of combinations or to the number of permitted combinations. To achieve the greatest diagnostic effect, it is recommended to use fields with characteristics that are the first prime number greater than degree of 2. In terms of testing price, the best is the GF(3m) field, for which it is necessary to define only one forbidden code combination, which provides detection of all forbidden codes. When using the Galois GF(dm) fields under consideration, the minimum coding distance for the codes of each digit of the code is 1. This indicates that it is impossible to detect 100 % of all even single errors in the work of the considered devices in the proposed way. Searching for a logical expression for an error sign is based on the division of groups of consecutive forbidden codes into subgroups. For each subgroup, the bits of its codes are divided into 2 parts, so that the senior bits of each subgroup code remain unchanged, and the younger ones acquire all possible values from 0...0 to 1...1. Then, to the minimized logical error expressions in this subgroup of codes, only the unchanged top bits will enter. Then only the immutable older bits will enter the minimized error expression in this subgroup of codes. The hardware complexity of the proposed method quadratically depends on the number of bits, which encodes one section of the extended Galois fields elements code.
Binary codes of extended Galois fields elements are redundant, some of them never appear at the normal operation of the devices for processing of such field elements. Unused (forbidden) code combinations can be used to organize on-line testing (concurrent error detection) of the specified devices. The appearance of any forbidden combination will be a sign of error. The paper compares the various extended Galois fields with the possibility of on-line testing organization, the fields that best ensure its holding are determined. It is noted that there are no bits for the codes of the Galois field elements that have strictly different values in the allowed and prohibited codes. It is suggested to evaluate the possibility of realizing the testing by the ratio of the number of forbidden combinations to the total number of combinations or to the number of permitted combinations. To achieve the greatest diagnostic effect, it is recommended to use fields with characteristics that are the first prime number greater than degree of 2. In terms of testing price, the best is the GF(3m) field, for which it is necessary to define only one forbidden code combination, which provides detection of all forbidden codes. When using the Galois GF(dm) fields under consideration, the minimum coding distance for the codes of each digit of the code is 1. This indicates that it is impossible to detect 100 % of all even single errors in the work of the considered devices in the proposed way. Searching for a logical expression for an error sign is based on the division of groups of consecutive forbidden codes into subgroups. For each subgroup, the bits of its codes are divided into 2 parts, so that the senior bits of each subgroup code remain unchanged, and the younger ones acquire all possible values from 0...0 to 1...1. Then, to the minimized logical error expressions in this subgroup of codes, only the unchanged top bits will enter. Then only the immutable older bits will enter the minimized error expression in this subgroup of codes. The hardware complexity of the proposed method quadratically depends on the number of bits, which encodes one section of the extended Galois fields elements code.
Description
Keywords
розширені поля Галуа, ємнісна складність, вбудоване тестування, extended Galois fields, capacitive complexity, built-in testing
Citation
Вбудований контроль пристроїв для опрацювання елементів розширених полів Галуа / Р. М. Еліас, В. С. Глухов, М. Рахма, І. М. Жолубак // Вісник Національного університету “Львівська політехніка”. Серія: Комп’ютерні системи та мережі. — Львів : Видавництво Національного університету “Львівська політехніка”, 2018. — № 905. — С. 64–72.