Estimation Method of Structural Complexity of Mastrovito Multiplier in \[GF(p^{m})\] in Response to the Internal Elements

Ольга Зіновіївна Шологон, Юлія Зіновіївна Шологон

Abstract


Background. In the multipliers which use Galois filed \[GF(p^{m})\] with large order the hardware complexity allows implementation on FPGA chip, but high structural complexity prevents to do it. That’s why it is important to conduct research in Galois field \[GF(p^{m})\] to determine the field in which the structural complexity is the lowest.

Objective. Develop the method for evaluating structural complexity of Mastrovito multiplier in response to the internal elements.

Methods. Structural complexity of Mastrovito multiplier in Galois fields was determined by combining VHDL and SH models in a VHDL-SH model. In order to find the field with the least structural complexity, the extended Galois field \[GF(p^{m})\] with the same number of elements was analysed.

Results. The relationship between structural complexity of Mastrovito multiplier in Galois fields \[GF(p^{m})\] and number of field bit in the capacity of the field was identified. The results for structural complexity of Mastrovito multiplier in Galois field \[GF(p^{m})\] using internal elements were modified.

Conclusions.Method for calculating the structural complexity of Mastrovito multiplier in \[GF(p^{m})\] was developed. The structural complexity was calculated by combining VHDL and SH models in a VHDL-SH model. It was determined that structural complexity of the multiplier depends on capacity of the field \[GF(p^{m}),\] wherein the calculations are carried out. The structural complexity of Mastrovito multiplier in \[GF(p^{m})\] with approximately the same number of elements was calculated, where

\[p^{m}\approx 625,\]

\[p^{m}\approx 78502725751,\]

\[p^{m}\approx 1,93485E+15.\]

In calculating the structural complexity without internal elements the structural complexity of the multiplier is less, when the difference between the capacity of the field and number of field bit in the field order is growing. In calculating the structural complexity with internal elements, structural complexity of multiplier is less when the difference between number of field bit and field capacity is equal. This method application can help to develop Galois field \[GF(p^{m})\] multipliers  with big order.


Keywords


Galois Field \[GF(p^{m});\] VHDL-SH Model; Mastrovito multiplier; Structural complexity

References


V. Glukhov and A. Glukhov, “The results of evaluation of structural complexity multipliers elements of Galois fields”, Visnyk NU “L'vivs'ka Politekhnika” “Komp"yuterni Systemy ta Merezhi”, no. 773, pp. 27–32, 2013 (in Ukrainian).

Y. Sholohon, “Evaluation of structural complexity Galois field multipliers based on the elementary transducers”, Visnyk NU “L'vivs'ka Politekhnika” “Komp"yuterni Systemy ta Merezhi”, no. 806, pp. 150–154, 2014 (in Ukrainian).

M. Cherkaskyy and Mourad Houssein Khalil, “Universal SH-model”, Visnyk NU “L'vivs'ka Politekhnika” “Komp"yuterni Systemy ta Merezhi”, no. 523, pp. 150–154, 2004 (in Ukrainian).

O. Sholohon, “Structural complexity of Galois field GF(2m) elements multipliers in polynomial basis calculation”, Visnyk NU “L'vivs'ka Politekhnika” “Komp"yuterni Systemy ta Merezhi”, no. 806, pp. 284–289, 2014 (in Ukrainian).

Bahram Rashidi et al., “Efficient implementation of bit-parallel fault tolerant polynomial basis multiplication and squaring over GF(2 m )”, IET Computers & Digital Techniques, vol. 10, no. 1, pp. 18–29, 2016. doi:10.1049/iet-cdt.2015.0020

Anan Lu et al., “Low complexity polynomial expansion detector with deterministic equivalents of the moments of channel gram matrix for massive MIMO uplink”, IEEE Trans. Commun., vol. 64, no. 2, pp. 586–600, 2016. doi: 10.1109/ TCOMM.2015.2506700

Yin Li et al., “Low complexity bit-parallel GF(2m) multiplier for all-one polynomials”, J. Cryptography, pp. 410–415, 2012.

S. Shelly and B.T. Chacko, “Fault detection multipliers in polynomial and normal basis”, Int. J. Com. Applications, vol. 1, no. 5, pp. 102–106, 2010. doi: 10.5120/114-229

P. Kitsos et al., “An efficient reconfigurable multiplier architecture for Galois field GF(2m)”, Microelectronics J., vol. 34, no. 10, pp. 975–980, 2003. doi: 10.1016/S0026-2692(03)00172-1

A. Al-Rabadi and M.A. Perkowski, “Multiple-valued galois field S/D trees for GFSOP minimization and their complexity”, in Proc. 31st IEEE Int. Symposium on Multiple-Valued Logic, 2010, pp. 159–166. doi: 10.1109/ISMVL.2001.924567


GOST Style Citations


  1. Глухов В.С., Глухова О.В. Результати оцінки структурної складності помножувачів елементів полів Галуа // Вісник НУ “Львівська політехніка” “Комп’ютерні системи та мережі”. – 2013. – № 773. – С. 27–32.
     
  2. Шологон Ю.З. Оцінювання структурної складності помножувачів полів Галуа на основі елементарних перетворювачів // Вісник НУ “Львівська політехніка” “Комп’ютерні системи та мережі”. – 2014. – № 806. – С. 290–296.
     
  3. Черкаський М. В., Мурад Хусейн Халіл. Універсальна SH-модель // Вісник НУ “Львівська політехніка” “Комп’ютерні системи та мережі”. – 2004. – № 523. – С. 150–154.
     
  4. Шологон О.З. Обчислення структурної складності помножувачів у поліноміальному базисі елементів полів Галуа GF(2^m) // Вісник НУ “Львівська політехніка” “Комп’ютерні системи та мережі”. – 2014. – № 806. – С. 284–289.
     
  5. Bahram Rashidi, Sayed Masoud Sayedi, Reza Rezaeian Farashahi. Efficient implementation of bit-parallel fault tolerant polynomial basis multiplication and squaring over GF(2m) // IET Computers & Digital Techniques. – 2016. – 10, № 1. – P. 18–29.
     
  6. Low complexity polynomial expansion detector with deterministic equivalents of the moments of channel gram matrix for massive MIMO uplink / Anan Lu, Xiqi Gao, Yahong Rosa Zheng, Chengshan Xiao // IEEE Trans. Commun. – 2016. – 64, № 2. – P. 586–600.
     
  7. Yin Li, Gong-liang Chen, Xiaoning Xie. Low complexity bit-parallel GF(2m) multiplier for all-one polynomials // J. Cryptography. – 2012. –  P. 410–415.
     
  8. Shelly S., Chacko B.T. Fault detection multipliers in polynomial and normal basis // Int. J. Comp. Applications. – 2010. – 1, № 5. – P. 102–106.
     
  9. Kitsos P., Theodoridis G., Koufopavlou O.G. An efficient reconfigurable multiplier architecture for Galois field GF(2m) // Microelectronics J. – 2003. – 34, № 10. – P. 975–980.
     
  10. Al-Rabadi A., Perkowski M.A. Multiple-valued galois field S/D trees for GFSOP minimization and their complexity // Proc. 31st IEEE Int. Symp. Multiple-Valued Logic, May 22–24, 2001. – P. 159–166.




DOI: https://doi.org/10.20535/1810-0546.2016.6.79723

Refbacks

  • There are currently no refbacks.




Copyright (c) 2017 NTUU KPI