Scientific and Technical Journal

ELECTROTECHNIC AND COMPUTER SYSTEMS

ISSN Print 2221-3937
ISSN Online 2221-3805
GALOIS FIELDS ELEMENTS MULTISECTION MULTIPLIERS STRUCTURAL COMPLEXITY REDUCTION
Abstract:

This article discusses an approach to reducethe structural complexity of binary Galois fields GF(2m) elements multisection multipliers. Elements of fields are represented in a normal basis of type 2. The orderof the fieldreaches998. Multipliers hardware complexity allow their implementation in FPGA. But because of the large structural complexity for some combinations of the fields order and sections number it is almost impossible to make it. The main focus is on reducing of multiplicative matrix structural complexity, which is main part of the multiplier. The article offers a matrix preliminary ordering by special interleaver. Sorting allows to implement a matrix as set of N identical matrixes of AND elements. As a result, it is possible to reduce their number N, hardware and structural complexity by reuse of only one AND matrix. The expected reduction of structural complexity is proportional to N2, one of combinational circuits delay – at times.At the same time, it increases the time complexity of multiplication in N times.Usage of ordered access memory as interleaver should keep multiplier running with different Galois fields.

Authors:
Keywords
DOI
References
  1. Omura J., and Massey J., (1986), Computational Method and Apparatus for Finite Field Arithmetic. U.S. Patent Number 4,587,627, May 1986 (In English).
  2. Hlukhov V.S. Osoblyvosti vykonannya operatsiy nad matrytsyamy v polyakh Halua [Operations over Matrices in Galois Fields Features], (2006), “Komp’yuterni Systemy Proektuvannya. Teoriya i praktyka”. Visnyk Natsional’noho Universytetu “L'vivs'ka Politekhnika”,Lviv, Ukraine, Vol. 564. pp. 35 – 39 (In Ukrainian).
  3. DSTU 4145-2002. Informatsiyni tekhnolohiyi. Kryptohrafichnyy zakhyst informatsiyi. Tsyfrovyy pidpys, shcho gruntuyet'sya na eliptychnykh kryvykh. Formuvannya ta pereviryannya [Information Technology. Cryptographic Techniques. Digital Signatures Based on Elliptic Curves. Generation and Verification], (2003), Derzhavnyy Komitet Ukrayiny z Pytan' Tekhnichnoho Rehulyuvannya ta Spozhyvchoyi Polityky, Kiev, Ukraine (In Ukrainian).
  4. Hlukhov V.S., Elias R.M., and Mel'nyk A.O. Osoblyvosti realizatsiyi na PLIS sektsiynykh pomnozhuvachiv elementiv poliv Halua GF(2m) z nadvelykym stepenem [Features of the FPGA-based Galois field GF(2m) Elements Sectional Multipliers with Extra Large Exponent], (2013), Komp’yuterno-intehrovani Tekhnolohiyi:Osvita, Nauka, Vyrobnytstvo – Naukovyy Zhurnal, Luts’kyy Natsional'nyy Tekhnichnyy Universytet. Luts’k, Ukraine, Vol. 12, pp. 103 – 106 (In Ukrainian).
  5. Hlukhov V.S., and Hlukhova O.V. Rezul'taty otsinky strukturnoyi skladnosti pomnozhuvachiv elementiv poliv Halua [Structural Complexity of Galois Field Elements Multipliers Evaluation Results], (2013), Komp’yuterni Systemy ta Merezhi”. Visnyk Natsional’noho Universytetu “L’vivs’ka politekhnika”, Lviv, Ukraine, Vol. 773, pp. 27 – 32 (In Ukrainian).
  6. Hlukhov V.S., and Trishch H.M. Otsinka strukturnoyi skladnosti bahatosektsiynykh pomnozhuvachiv elementiv poliv Halua [Structural Complexity of Multisection Galois Field Elements Multipliers Evaluation], (2014), Komp’yuterni Systemy ta Merezhi”. Visnyk Natsional’noho Universytetu “L’vivs'ka politekhnika”, Lviv, Ukraine, Vol. 806, pp. 27 – 33 (In Ukrainian).
  7. Sholohon O.Z. Obchyslennya strukturnoyi skladnosti pomnozhuvachiv u polinomial'nomu bazysi elementiv poliv Halua GF(2m) [Structural Complexity of Galois Field GF(2m) Elements Multipliers in Polynomial Basis Calculation]. Komp’yuterni Systemy ta Merezhi”. Visnyk Natsional’noho Universytetu “L’vivs'ka politekhnika”, Lviv, Ukraine, 2014,Vol. 806, pp. 284 – 289 (In Ukrainian).
  8. Sholohon Yu.Z. Otsinyuvannya strukturnoyi skladnosti pomnozhuvachiv poliv Halua na osnovi elementarnykh peretvoryuvachiv [Based on Elementary Transducers Structural Complexity of Galois Field Multipliers Evaluation], (2014), Komp’yuterni Systemy ta Merezhi”. Visnyk Natsional’noho Universytetu “L’vivs'ka politekhnika”, Lviv, Ukraine, Vol. 806, pp. 290 – 295 (In Ukrainian).
  9. Mel'nyk A.O. Pam"yat' iz vporyadkovanym dostupom [Tekst]: monohrafiya / [Orderly Access Memory], (2014), Natsionalnu Universytet “L’vivs'ka Рolitekhnika” Vyd-vo L'vivska Politekhniky, 294 p. ISBN 978-617-607-540-0 (In Ukrainian).
  10. Hlukhova O.V., Lozyns'kyy A.Ya., Yaremkevych R.I., and Ihnatovych A.O. Analitychna otsinka strukturnoyi skladnosti pomnozhuvachiv elementiv poliv Halua [Galois Field Elements Multipliers Structural Complexity Analytical Evaluation], (2015), Materialy V Vseukrayins’koyi Shkoly-seminaru Molodykh Vchenykh i Studentiv “Suchasni Komp’yuterni Informatsiyni Tekhnolohiyi” ASIT’2015, Ternopil, Ukraine, TNEU, 2015, May 22-23, pp. 168 – 169.
Published:
Last download:
2017-11-22 16:45:07

[ © KarelWintersky ] [ All articles ] [ All authors ]
[ © Odessa National Polytechnic University, 2014. Any use of information from the site is possible only under the condition that the source link! ]
Яндекс.Метрика