1. CSN
  2. All Volumes and Issues
  3. Number 905, 2018
  4. Concurrent error detaction of devices for extended galois fields elements processing

Concurrent error detaction of devices for extended galois fields elements processing

CSN.
2018;
, Number 905
: pp. 64 - 72
https://doi.org/10.23939/csn2018.905.064
Authors:
  1. Rodrigue Elias
  2. Valerii Hlukhov
  3. Mohammed Kadhim Rahma
  4. Ivan Zholubak
1
Lebanese International University, Department of Electrical and Electronic Engineering
2
Lviv Polytechnic National University, Department of Electronic Computing Machines
3
Lviv Polytechnic National University, Computer Engineering Department
4
Lviv Polytechnic National University, Ukraine

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.

extended Galois fields
capacitive complexity
built-in testing
  1. IEEE 1363–2000 (2000). Standard Specifications for Public-Key Cryptography. Copyright © 2000 IEEE. All rights reserved.
  2. DSTU 4145–2002. Informatsiini tekhnolohii. Kryptohrafichnyi zakhyst informatsii. ETsP, shcho gruntuietsia na eliptychnykh kryvykh. Formuvannia ta pereviriannia. Kyiv. 2003.
  3. DSTU ISO/IEC 15946–1:2015 Informatsiini tekhnolohii. Metody zakhystu. Kryptohrafichni metody, shcho gruntuiutsia na eliptychnykh kryvykh. Chastyna 1. Zahalni polozhennia.
  4. De Feo, L. Towards quantum– resistant cryptosystems from supersingular elliptic curve isogenies / L. De Feo, D. Jao, J. Plut // PQCrypto. – 2011.–24 p.
  5. Cherkaskyi M. V. SH–model alhorytmu // Visnyk Natsionalnoho universytetu “Lvivska politekhnika” No 433. Vydavnytstvo Natsionalnoho universytetu “Lvivska politekhnika”. 2001. S. 127–134.
  6. Cherkaskyi M. V., Khusein Khalid Murad. Universalna SH-model // Visnyk Natsionalnoho universytetu “Lvivska politekhnika” No 523 “Kompiuterni systemy ta merezhi”. Lviv. Vydavnytstvo Natsionalnoho universytetu “Lvivska politekhnika”. 2004. S. 150–154.
  7. Hlukhov V. S., Hlukhova O. V. Rezultaty otsiniuvannia strukturnoi skladnosti pomnozhuvachiv elementiv poliv Halua [Tekst] / V. S. Hlukhov, O. V. Hlukhova // Visnyk Natsionalnoho universytetu “Lvivska politekhnika” “Kompiuterni systemy ta merezhi”. – Lviv: – 2013. – Vyp. 773.– S. 27-32.
  8. Hlukhov V. S., Trishch H. M. Otsinka strukturnoi skladnosti bahatosektsiinykh pomnozhuvachiv elementiv poliv Halua [Tekst] / V. S. Hlukhov, H. M. Trishch // Visnyk Natsionalnoho universytetu “Lvivska politekhnika” “Kompiuterni systemy ta merezhi”. – Lviv: – 2014. – Vyp. 806. – S. 27–33.
  9. Hlukhova, O. V., Lozynskyi, A. Ya., Yaremkevych, R. I., Ihnatovych, A. O. Analitychna otsinka strukturnoi skladnosti pomnozhuvachiv elementiv poliv Halua [Tekst]. / O. V. Hlukhova, A. Ya. Lozynskyi, R. I. Yaremkevych, A. O. Ihnatovych // Materialy V Vseukrainskoi shkoly-seminaru molodykh vchenykh i studentiv. Suchasni kompiuterni informatsiini tekhnolohii. ACIT2015. 22–23 travnia 2015 roku. Ternopil. TNEU. 2015. S. 166–167.
  10. R. Elias, M. Rakhma, V. Hlukhov. Strukturna skladnist pomnozhuvachiv elementiv poliv Halua u normalnomu ta polinomialnomu bazysakh. Elektrotekhnichni ta kompiuterni cystemy. – Odesa: – 2017. Vyd-vo Nauka i tekhnika. – No 25 (101). – S. 324–331.
  11. Sholohon O.Z. Obchyslennia strukturnoi skladnosti pomnozhuvachiv u polinomialnomu bazysi elementiv poliv Halua GF(2m) [Tekst] / O. Z. Sholohon // Visnyk Natsionalnoho universytetu “Lvivska politekhnika” “Kompiuterni systemy ta merezhi”. – Lviv: – 2014. – Vyp. 806. – S. 284–289.
  12. Sholohon Yu. Z. Otsiniuvannia strukturnoi skladnosti pomnozhuvachiv poliv Halua na osnovi elementarnykh peretvoriuvachiv [Tekst] / Yu. Z. Sholohon // Visnyk Natsionalnoho universytetu “Lvivska politekhnika” “Kompiuterni systemy ta merezhi”. – Lviv: – 2014. – Vyp. 806. – S. 290–295.
  13. Hlukhov V. S. Porivniannia polinomialnoho ta normalnoho bazysiv predstavlennia elementiv poliv Halua // Visnyk Natsionalnoho universytetu “Lvivska politekhnika” “Kompiuterni systemy proektuvannia. Teoriia i praktyka”. No591, s. 22–27. Lviv, 2007.
  14. V. S. Hlukhov. Otsinka aparatnykh vytrat na realizatsiiu bahatorivnevoi kompiuternoi systemy // Visnyk Natsionalnoho universytetu “Lvivska politekhnika” “Kompiuterni nauky ta informatsiini tekhnolohii” No 629. Lviv, 2008. S. 13–20.
  15.  Zholubak, I. M., Hlukhov, V. S. Vyznachennia rozshyrenoho polia Halua GF(dm) z naimenshoiu aparatnoiu skladnistiu pomnozhuvacha [Tekst] / I. M. Zholubak, V. S. Hlukhov // Visnyk Natsionalnoho universytetu “Lvivska politekhnika” “Informatsiini systemy ta merezhi”, No 854. Lviv, 2016. S. 63 – 69.
  16. Hlukhov V. S.,Elias R. M., Rakhma M. K. R. Chasova skladnist oriientovanykh na vykonannia kryptohrafichnykh peretvoren v skladi kiberfizychnykh system pomnozhuvachiv na osnovi modyfikovanykh komirok Hilda. Materialy druhoho naukovoho seminaru Kiber-fizychni systemy: dosiahnennia ta vyklyky, Lviv, Natsionalnyi universytet “Lvivska politekhnika”, 21–22 chervnia 2016 r. S. 36–42.
  17. R. Elias, M. Rakhma, V. S. Hlukhov. Chasova skladnist pomnozhuvachiv dlia poliv Halua. Elektrotekhnichni ta kompiuterni cystemy. – Odesa: – 2016. Vyd-vo Nauka i tekhnika. – No 22 (98). – S. 323–327.
  18. Mohammed Kadhim Rahma, Valeriy S. Hlukhov. Time complexity of multipliers for Galois fields. INTERNATIONAL YOUTH SCIENCE FORUM ”LITTERIS ET ARTIBUS”, 24–26 NOVEMBER 2016, LVIV, UKRAINE. Proceedings, pp. 52–53.
  19. R. Elias, V. Hlukhov, M. Rakhma, I. Zholubak. Yemnisna skladnist prystroiv dlia opratsiuvannia elementiv rozshyrenykh poliv Halua. Elektrotekhnichni ta kompiuterni cystemy. – Odesa: – 2018. Vyd-vo Nauka i tekhnika. – No 29 (105) (drukuietsia).
  20. Rabochee dyahnostyrovanye bezopasnыkh ynformatsyonno-upravliaiushchykh system / A. B. Drozd, B. C. Kharchenko, S. H Antoshchuk y dr. / Pod red A. B. Drozda, B. C. Kharchenko – Kh. Nats. aэrokosmycheskyi un-t ym. N. E. Zhukovskoho “KhAY”, 2012–614 s.
  21. Metodychni vkazivky do kursovoi roboty “Aryfmetychni ta lohichni osnovy kompiuternykh tekhnolohii” z dystsypliny “Kompiuterna lohika” bazovoho napriamku 6.050102 “Kompiuterna inzheneriia” / Ukl. V. S. Hlukhov, V. A. Holembo. Lviv: NU“LP”, 2014. – 96 s.