Skip to main content
Erschienen in:

07.08.2024

Input–Output Scheduling and Control for Efficient FPGA Realization of Digit-Serial Multiplication Over Generic Binary Extension Fields

verfasst von: Dibakar Pradhan, Pramod Kumar Meher, Bimal Kumar Meher

Erschienen in: Circuits, Systems, and Signal Processing | Ausgabe 12/2024

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper, we propose an energy-efficient design of architecture for digit-serial multiplication over generic GF(\(2^m\)), which could be used for different fields as and when required and to enhance the security by changing the fields. An efficient input scheduling scheme is proposed to reduce the required number of input pins and a digit extraction circuit for digit-serial multiplication. Besides, to reduce the dynamic power consumption, we have proposed a simple technique using an array of m AND gates that minimizes the output bit-switching. To study the impact of digit size, the digit-serial multipliers for \(m=163\) and 233 are synthesised by Xilinx Vivado for FPGA implementation. It is found that the required number of slices, power consumption, and energy per multiplication increase while the computational delay falls with the increase in digit size. Therefore, larger digit sizes could be considered only when fast multiplication is necessary. The array of AND gates for output bit control helps in reducing the dynamic power consumption and energy per multiplication, respectively, by 50.4% and 57.7% for \(m=163\) and \(49.8\%\) and \(51.8\%\), for \(m=233\), on average, for different digit sizes over the conventional least-significant-digit-first design.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

ATZelektronik

Die Fachzeitschrift ATZelektronik bietet für Entwickler und Entscheider in der Automobil- und Zulieferindustrie qualitativ hochwertige und fundierte Informationen aus dem gesamten Spektrum der Pkw- und Nutzfahrzeug-Elektronik. 

Lassen Sie sich jetzt unverbindlich 2 kostenlose Ausgabe zusenden.

ATZelectronics worldwide

ATZlectronics worldwide is up-to-speed on new trends and developments in automotive electronics on a scientific level with a high depth of information. 

Order your 30-days-trial for free and without any commitment.

Weitere Produktempfehlungen anzeigen
Literatur
1.
Zurück zum Zitat L. Batina, N. Mentens, S.B. Ors, B. Preneel, Serial multiplier architectures over GF(\(2^m\)) for elliptic curve cryptosystems, in Proceedings of the\(12{th}\)IEEE Mediterranean Electrotechnical Conference (IEEE Cat. No. 04CH37521), vol. 2 (2004), pp. 779–782 L. Batina, N. Mentens, S.B. Ors, B. Preneel, Serial multiplier architectures over GF(\(2^m\)) for elliptic curve cryptosystems, in Proceedings of the\(12{th}\)IEEE Mediterranean Electrotechnical Conference (IEEE Cat. No. 04CH37521), vol. 2 (2004), pp. 779–782
2.
Zurück zum Zitat T. Beth, D. Gollmann, Algorithm engineering for public key algorithms. IEEE J. Sel. Areas Commun. 7(4), 458–466 (1989)CrossRef T. Beth, D. Gollmann, Algorithm engineering for public key algorithms. IEEE J. Sel. Areas Commun. 7(4), 458–466 (1989)CrossRef
3.
Zurück zum Zitat M.A. García-Martínez, R. Posada-Gómez, G. Morales-Luna, F. Rodríguez-Henríquez, FPGA implementation of an efficient multiplier over finite fields GF (\(2^m\)), in 2005 International Conference on Reconfigurable Computing and FPGAs (ReConFig’05) (2005), pp. 5–26.https://doi.org/10.1109/RECONFIG.2005.18 M.A. García-Martínez, R. Posada-Gómez, G. Morales-Luna, F. Rodríguez-Henríquez, FPGA implementation of an efficient multiplier over finite fields GF (\(2^m\)), in 2005 International Conference on Reconfigurable Computing and FPGAs (ReConFig’05) (2005), pp. 5–26.https://​doi.​org/​10.​1109/​RECONFIG.​2005.​18
4.
Zurück zum Zitat J.-H. Guo, C.-L. Wang, Digit-serial systolic multiplier for finite fields GF(\(2^m\)). IEE Proc.-Comput. Digit. Tech. 145(2), 143–148 (1998)CrossRef J.-H. Guo, C.-L. Wang, Digit-serial systolic multiplier for finite fields GF(\(2^m\)). IEE Proc.-Comput. Digit. Tech. 145(2), 143–148 (1998)CrossRef
5.
Zurück zum Zitat D. Hankerson, A.J. Menezes, S. Vanstone, Guide to Elliptic Curve Cryptography (Springer, Berlin, 2003) D. Hankerson, A.J. Menezes, S. Vanstone, Guide to Elliptic Curve Cryptography (Springer, Berlin, 2003)
7.
Zurück zum Zitat M. Heidarpur, M. Mirhassani, An efficient and high-speed overlap-free Karatsuba-based finite-field multiplier for FPGA implementation. IEEE Trans. Very Large Scale Integr. VLSI Syst. 29(4), 667–676 (2021)CrossRef M. Heidarpur, M. Mirhassani, An efficient and high-speed overlap-free Karatsuba-based finite-field multiplier for FPGA implementation. IEEE Trans. Very Large Scale Integr. VLSI Syst. 29(4), 667–676 (2021)CrossRef
8.
Zurück zum Zitat A. Ibrahim, Low-space bit-serial systolic array architecture for interleaved multiplication over GF (\(2^m\)). IET Comput. Digit. Tech. 15(3), 223–229 (2021)CrossRef A. Ibrahim, Low-space bit-serial systolic array architecture for interleaved multiplication over GF (\(2^m\)). IET Comput. Digit. Tech. 15(3), 223–229 (2021)CrossRef
9.
Zurück zum Zitat A. Ibrahim, Low-complexity systolic array structure for field multiplication in resource-constrained IoT nodes. Ain Shams Eng. J. 14(10), 102188 (2023)CrossRef A. Ibrahim, Low-complexity systolic array structure for field multiplication in resource-constrained IoT nodes. Ain Shams Eng. J. 14(10), 102188 (2023)CrossRef
10.
Zurück zum Zitat A. Ibrahim, F. Gebali, Scalable and unified digit-serial processor array architecture for multiplication and inversion over GF (\(2^m\)). IEEE Trans. Circuits Syst. I Regul. Pap. 64(11), 2894–2906 (2017)MathSciNetCrossRef A. Ibrahim, F. Gebali, Scalable and unified digit-serial processor array architecture for multiplication and inversion over GF (\(2^m\)). IEEE Trans. Circuits Syst. I Regul. Pap. 64(11), 2894–2906 (2017)MathSciNetCrossRef
11.
Zurück zum Zitat J.L. Imaña, J.M. Sanchez, F. Tirado, Bit-parallel finite field multipliers for irreducible trinomials. IEEE Trans. Comput. 55(5), 520–533 (2006)CrossRef J.L. Imaña, J.M. Sanchez, F. Tirado, Bit-parallel finite field multipliers for irreducible trinomials. IEEE Trans. Comput. 55(5), 520–533 (2006)CrossRef
12.
Zurück zum Zitat S.K. Jain, L. Song, K.K. Parhi, Efficient semi-systolic architectures for finite-field arithmetic. IEEE Trans. Very Large Scale Integr. VLSI Syst. 6(1), 101–113 (1998)CrossRef S.K. Jain, L. Song, K.K. Parhi, Efficient semi-systolic architectures for finite-field arithmetic. IEEE Trans. Very Large Scale Integr. VLSI Syst. 6(1), 101–113 (1998)CrossRef
14.
Zurück zum Zitat C.H. Kim, S. Kwon, C.P. Hong, A fast digit-serial systolic multiplier for finite field GF\((2^m)\), in Proceedings of the 2005 Asia and South Pacific Design Automation Conference (2005), pp. 1268–1271 C.H. Kim, S. Kwon, C.P. Hong, A fast digit-serial systolic multiplier for finite field GF\((2^m)\), in Proceedings of the 2005 Asia and South Pacific Design Automation Conference (2005), pp. 1268–1271
15.
Zurück zum Zitat K.-W. Kim, J.-C. Jeon, Polynomial basis multiplier using cellular systolic architecture. IETE J. Res. 60(2), 194–199 (2014)CrossRef K.-W. Kim, J.-C. Jeon, Polynomial basis multiplier using cellular systolic architecture. IETE J. Res. 60(2), 194–199 (2014)CrossRef
16.
Zurück zum Zitat C.H. Kim, C.P. Hong, S. Kwon, A digit-serial multiplier for finite field GF(\(2^m\)). IEEE Trans. Very Large Scale Integr. VLSI Syst. 13(4), 476–483 (2005)CrossRef C.H. Kim, C.P. Hong, S. Kwon, A digit-serial multiplier for finite field GF(\(2^m\)). IEEE Trans. Very Large Scale Integr. VLSI Syst. 13(4), 476–483 (2005)CrossRef
17.
Zurück zum Zitat C.-Y. Lee, J. Xie, Efficient subquadratic space complexity digit-serial multipliers over GF\((2^m)\) based on bivariate polynomial basis representation, in 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC) (2020), pp. 253–258 C.-Y. Lee, J. Xie, Efficient subquadratic space complexity digit-serial multipliers over GF\((2^m)\) based on bivariate polynomial basis representation, in 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC) (2020), pp. 253–258
18.
Zurück zum Zitat C.-Y. Lee, P.K. Meher, Subquadratic space-complexity digit-serial multipliers over \(GF(2^m)\) using generalized \((a, b)\)-way Karatsuba algorithm. IEEE Trans. Circuits Syst. I Regul. Pap. 62(4), 1091–1098 (2015)MathSciNet C.-Y. Lee, P.K. Meher, Subquadratic space-complexity digit-serial multipliers over \(GF(2^m)\) using generalized \((a, b)\)-way Karatsuba algorithm. IEEE Trans. Circuits Syst. I Regul. Pap. 62(4), 1091–1098 (2015)MathSciNet
19.
Zurück zum Zitat P.K. Meher, Systolic formulation for low-complexity serial-parallel implementation of unified finite field multiplication over GF(\(2^m\)), in 2007 IEEE International Conf. on Application-Specific Systems, Architectures and Processors (ASAP) (2007), pp. 134–139 P.K. Meher, Systolic formulation for low-complexity serial-parallel implementation of unified finite field multiplication over GF(\(2^m\)), in 2007 IEEE International Conf. on Application-Specific Systems, Architectures and Processors (ASAP) (2007), pp. 134–139
20.
Zurück zum Zitat B.K. Meher, P.K. Meher, Analysis of systolic penalties and design of efficient digit-level systolic-like multiplier for binary extension fields. Circuits Syst. Signal Process. 38, 774–790 (2019)CrossRef B.K. Meher, P.K. Meher, Analysis of systolic penalties and design of efficient digit-level systolic-like multiplier for binary extension fields. Circuits Syst. Signal Process. 38, 774–790 (2019)CrossRef
21.
Zurück zum Zitat M. Mekhallalati, M. Ibrahim, A. Ashur, New low complexity bidirectional systolic structures for serial multiplication over the finite field GF(\(q^m\)). IEE Proc. -Circuits Devices Syst. 145(1), 55–60 (1998)CrossRef M. Mekhallalati, M. Ibrahim, A. Ashur, New low complexity bidirectional systolic structures for serial multiplication over the finite field GF(\(q^m\)). IEE Proc. -Circuits Devices Syst. 145(1), 55–60 (1998)CrossRef
22.
Zurück zum Zitat J.-S. Pan, C.-Y. Lee, A. Sghaier, M. Zeghid, J. Xie, Novel systolization of subquadratic space complexity multipliers based on toeplitz matrix-vector product approach. IEEE Trans. Very Large Scale Integr. VLSI Syst. 27(7), 1614–1622 (2019)CrossRef J.-S. Pan, C.-Y. Lee, A. Sghaier, M. Zeghid, J. Xie, Novel systolization of subquadratic space complexity multipliers based on toeplitz matrix-vector product approach. IEEE Trans. Very Large Scale Integr. VLSI Syst. 27(7), 1614–1622 (2019)CrossRef
24.
Zurück zum Zitat A. Reyhani-Masoleh, M.A. Hasan, Low complexity bit parallel architectures for polynomial basis multiplication over GF (\(2^m\)). IEEE Trans. Comput. 53(8), 945–959 (2004)CrossRef A. Reyhani-Masoleh, M.A. Hasan, Low complexity bit parallel architectures for polynomial basis multiplication over GF (\(2^m\)). IEEE Trans. Comput. 53(8), 945–959 (2004)CrossRef
25.
Zurück zum Zitat L. Song, K.K. Parhi, Low-energy digit-serial/parallel finite field multipliers. J. VLSI Signal Process. Syst. Signal Image Video Technol. 19, 149–166 (1998)CrossRef L. Song, K.K. Parhi, Low-energy digit-serial/parallel finite field multipliers. J. VLSI Signal Process. Syst. Signal Image Video Technol. 19, 149–166 (1998)CrossRef
26.
Zurück zum Zitat W. Tang, H. Wu, M. Ahmadi, VLSI implementation of bit-parallel word-serial multiplier in GF(\(2^{233}\)), in The\(3^{rd}\)International IEEE-NEWCAS Conference, 2005 (2005), pp. 399–402 W. Tang, H. Wu, M. Ahmadi, VLSI implementation of bit-parallel word-serial multiplier in GF(\(2^{233}\)), in The\(3^{rd}\)International IEEE-NEWCAS Conference, 2005 (2005), pp. 399–402
27.
Zurück zum Zitat M. Thirumoorthi, A.J. Leigh, M. Heidarpur, M. Khalid, M. Mirhassani, Novel formulations of \(m\)-term overlap-free Karatsuba binary polynomial multipliers and their hardware implementations. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 31, 1509–1522 (2023) M. Thirumoorthi, A.J. Leigh, M. Heidarpur, M. Khalid, M. Mirhassani, Novel formulations of \(m\)-term overlap-free Karatsuba binary polynomial multipliers and their hardware implementations. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 31, 1509–1522 (2023)
28.
Zurück zum Zitat X. Wang, N. Wu, F. Zhou, F. Ge, Efficient configurable digit-serial multiplier based on improved Karatsuba algorithm over GF\((2^m)\), in 2022 IEEE 22nd International Conference on Communication Technology (ICCT) (2022), pp. 1531–1535 X. Wang, N. Wu, F. Zhou, F. Ge, Efficient configurable digit-serial multiplier based on improved Karatsuba algorithm over GF\((2^m)\), in 2022 IEEE 22nd International Conference on Communication Technology (ICCT) (2022), pp. 1531–1535
29.
Zurück zum Zitat H. Wu, Low complexity bit-parallel multiplier for a class of finite fields, in 2006 International Conference on Communications, Circuits and Systems, vol. 4 (2006), pp. 2565–2568 H. Wu, Low complexity bit-parallel multiplier for a class of finite fields, in 2006 International Conference on Communications, Circuits and Systems, vol. 4 (2006), pp. 2565–2568
30.
Zurück zum Zitat H. Wu, Bit-parallel finite field multiplier and squarer using polynomial basis. IEEE Trans. Comput. 51(7), 750–758 (2002)MathSciNetCrossRef H. Wu, Bit-parallel finite field multiplier and squarer using polynomial basis. IEEE Trans. Comput. 51(7), 750–758 (2002)MathSciNetCrossRef
31.
Zurück zum Zitat J. Xie, P.K. Meher, M. Sun, Y. Li, B. Zeng, Z.-H. Mao, Efficient FPGA implementation of low-complexity systolic Karatsuba multiplier over \(GF(2^m)\) based on NIST polynomials. IEEE Trans. Circuits Syst. I Regul. Pap. 64(7), 1815–1825 (2017)MathSciNetCrossRef J. Xie, P.K. Meher, M. Sun, Y. Li, B. Zeng, Z.-H. Mao, Efficient FPGA implementation of low-complexity systolic Karatsuba multiplier over \(GF(2^m)\) based on NIST polynomials. IEEE Trans. Circuits Syst. I Regul. Pap. 64(7), 1815–1825 (2017)MathSciNetCrossRef
32.
Zurück zum Zitat J. Xie, C.-Y. Lee, P.K. Meher, Z.-H. Mao, Novel bit-parallel and digit-serial systolic finite field multipliers over GF\((2^m)\) based on reordered normal basis. IEEE Trans. Very Large Scale Integr. VLSI Syst. 27(9), 2119–2130 (2019)CrossRef J. Xie, C.-Y. Lee, P.K. Meher, Z.-H. Mao, Novel bit-parallel and digit-serial systolic finite field multipliers over GF\((2^m)\) based on reordered normal basis. IEEE Trans. Very Large Scale Integr. VLSI Syst. 27(9), 2119–2130 (2019)CrossRef
Metadaten
Titel
Input–Output Scheduling and Control for Efficient FPGA Realization of Digit-Serial Multiplication Over Generic Binary Extension Fields
verfasst von
Dibakar Pradhan
Pramod Kumar Meher
Bimal Kumar Meher
Publikationsdatum
07.08.2024
Verlag
Springer US
Erschienen in
Circuits, Systems, and Signal Processing / Ausgabe 12/2024
Print ISSN: 0278-081X
Elektronische ISSN: 1531-5878
DOI
https://doi.org/10.1007/s00034-024-02793-0