CAPACITY COMPLEXITY AND EMBEDDED ERROR DETECTION OF DEVICES FOR EXTENDED GALOIS FIELDS ELEMENTS PROCESSING

Abstract

For extended Galois fields GF(dm) of about the same order (number of field elements) the amount of memory required to store elements codes (capacitive complexity) will be different for each field. Each digit of extended Galois field GF(dm) element code is represented by nb = élog2dù bits, by which you can encode dt = 2 élog2dù > d of different code combinations. At the same time, dd =  dt – d code combinations remain, which will never be encountered in the normal operation of processor and memory units and data channels. These unused (forbidden) code combinations can be used to control the work of these devices in the course of performing their basic functions, that is, to organize in-built testing, so called concurrent error detection (CED). Appearance of any forbidden combination in any Galois field element code digit will be the sign of error.  In this paper, various extended Galois fields with approximately the same number of elements are compared by the capacitive complexity and concurrent error detection ability of the devices for such fields elements processing.

To date, the use of Galois GF(2m) binary fields has been standardized for the processing of digital signatures. In addition, there are standards that determine the use of the fields GF(pm) with the characteristic p > 3 (p is a prime number), although they do not deny the use of ternary fields with the characteristic p = 3. Fields with characteristic p ≈ 2768 are now being analyzed for use in post-quantum cryptography. For applied research of universal algorithmic computing systems models are needed that combine the achievements of the theory of abstract algorithms with the practice of designing and solving problems on real computers. The SH-model of the algorithm (software-hardware model) can be one. In the processes of synthesis, analysis and optimization of SH-models, it is proposed to use five complexity characteristics: hardware, time, capacitive, programmatic and structural ones, which are connected with each other and depend on each other.

Comparison of devices that process elements of extended Galois fields by the indicator of structural, hardware and time complexities was carried out in earlier works. Analysis of the capacity complexity and concurrent error detection ability of mentioned devices was not carried out.

Therefore, in the work in terms of capacitive complexity and concurrent error detection ability of devices that process Galois fields elements the next extended fields are considered: binary Galois field GF(2m), since they are now practically used; ternary fields GF(3m) - for use in the near future; other fields with high characteristics GF(pm) which are supposed to be involved in post-quantum cryptography.

It is shown in this paper that extended binary and prime Galois fields have the smallest length of elements codes (the smallest capacitive complexity), but the use of other extended Galois fields will not increase the length of the elements codes (capacitive complexity) by more than 30%. In order to increase the concurrent error detection ability of devices that process the extended Galois fields elements, it is recommended to use fields with characteristic d, which is the first prime number greater than power of 2, for example d = 3 or d = 5. Fields with characteristics d, which are either of power of 2 (d = 2), or are the first number smaller than the power of 2, but greater than 3, for example, d = 127, have the least concurrent error detection ability.  From the standpoint of concurrent error detection cost, the field with a characteristic d = 3 (the extended ternary Galois GF(3m)) is the best. The redundancy of the extended Galois fields with characteristics d > 2 does

Author Biographies

Еліас Родріг Митрі, Lebanese International University

PhD, an instructor at the School of Engineering at the Lebanese International University,  School of Engineering, Block G, Lebanese International University

Валерій Сергійович Глухов, Lviv Polytechnic National University

Dr. of Science, Professor, Professor of the Department of Computer Engineering, Lviv Polytechnic National University

Мохаммед Кадім Рахма, Lviv Polytechnic National University

PhD student of the Department of Computer Engineering, Lviv Polytechnic National University

Иван Михайлович Жолубак, Lviv Polytechnic National University

assistant of the Department of Computer Engineering, Lviv Polytechnic National University

Published
2019-01-22
How to Cite
Митрі, Е. Р., Глухов, В., Рахма, М., & Жолубак, И. (2019). CAPACITY COMPLEXITY AND EMBEDDED ERROR DETECTION OF DEVICES FOR EXTENDED GALOIS FIELDS ELEMENTS PROCESSING. Electrotechnic and Computer Systems, (29(105), 95-102. https://doi.org/10.15276/eltecs.29.105.2018.10
Section
Protection of an information in computer systems