본문 바로가기
KERD
논문KCI 등재

유한체상의 여분기저를 사용한 효율적인 멀티플렉서 기반 AB2 곱셈기

An Efficient Multiplexer-based AB2 Multiplier Using Redundant Basis over Finite Fields

김기원
한국컴퓨터정보학회 (The Korean Society Of Computer And Information)|2020.01|한국컴퓨터정보학회논문지 (Journal of The Korea Society of Computer and Information)|제25권 제1호|pp. 13-19|DOI https://doi.org/10.9708/jksci.2020.25.01.013

0

조회

0

다운로드

1

인용

0

참고문헌

키워드

시스톨릭 어레이Finite fields곱셈MultiplicationRedundant basisSystolic array유한체여분 기저멀티플렉서기반Multiplexer-based
주제분류컴퓨터학

초록

본 논문에서는 유한체상의 여분 기저(redundant basis)를 사용한 모듈러 AB2 곱셈을 수행하는 멀티플렉서(multiplexer) 기반의 기법을 제안한다. 그리고 제안한 기법을 사용하여 효율적인 멀티플렉서 기반의 세미-시스톨릭(semi-systolic) AB2 곱셈기를 제안한다. 모듈러 AB2 곱셈기의 셀 내부의연산을 멀티플렉서로 처리할 수 있는 수식을 유도한다. 멀티플렉서를 이용하여 셀을 구현하여, 셀의 지연시간을 감소시킨다. 기존의 구조들과 비교하면, 제안한 AB2 곱셈기는 Liu 등, Lee 등, Ting 등, 및 Kim-Kim의 곱셈기들의 AT 복잡도보다 약 80.9%, 61.8%, 61.8%, 및 9.5% 가량이 감소되었다. 따라서, 제안한 곱셈기는 VLSI(very large scale integration) 구현에 적합하며 다양한 응용에 쉽게 적용할 수 있다.

Abstract

In this paper, we propose a multiplexer based scheme that performs modular AB2 multiplication using redundant basis over finite field. Then we propose an efficient multiplexer based semi-systolic AB2 multiplier using proposed scheme. We derive a method that allows the multiplexers to perform the operations in the cell of the modular AB2 multiplier. The cell of the multiplier is implemented using multiplexers to reduce cell latency. As compared to the existing related structures, the proposed AB2 multiplier saves about 80.9%, 61.8%, 61.8%, and 9.5% AT complexity of the multipliers of Liu et al., Lee et al., Ting et al., and Kim-Kim, respectively. Therefore, the proposed multiplier is well suited for VLSI implementation and can be easily applied to various applications.

참고문헌 (29)

  1. A. J. Menezes, "Handbook of Applied Cryptography" (1996), CRC Press
  2. R. E. Blahut, "Theory and Practice of Error Control Codes" (1983), Addison-Wesley
  3. Neal Koblitz, "Elliptic curve cryptosystems", Mathematics of Computation, 48(177), pp.203~203 (1987), American Mathematical Society (AMS)[DOI]
  4. Peter L. Montgomery, "Modular multiplication without trial division", Mathematics of Computation, 44(170), pp.519~519 (1985), American Mathematical Society (AMS)[DOI]
  5. Cetin K. Koc, "Montgomery Multiplication in GF(2k)", Designs, Codes and Cryptography, 14(1), pp.57~69 (1998), Springer Science and Business Media LLC[DOI]
  6. Chiou-Yng Lee, "Low-complexity bit-parallel systolic Montgomery multipliers for special classes of GF(2", sup m, IEEE Transactions on Computers, pp.2005, 54(9)[DOI]
  7. C. W. Chiou, "Concurrent Error Detection in Montgomery Multiplication over GF(2m)", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E89-A(2), pp.566~574 (2006)[DOI]
  8. Arash Hariri, "Bit-Serial and Bit-Parallel Montgomery Multiplication and Squaring over GF(2^m)", IEEE Transactions on Computers, 58(10), pp.1332~1345 (2009), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
  9. Arash Hariri, "Concurrent Error Detection in Montgomery Multiplication over Binary Extension Fields", IEEE Transactions on Computers, 60(9), pp.1341~1353 (2011), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
  10. Kee-Won Kim, "Efficient Cellular Automata Based Montgomery AB2 Multipliers over GF(2m)", IETE Technical Review, 31(1), pp.92~102 (2014), Informa UK Limited[DOI]
  11. Kee-Won Kim, "Polynomial Basis Multiplier Using Cellular Systolic Architecture", IETE Journal of Research, 60(2), pp.194~199 (2014), Informa UK Limited[DOI]
  12. Se-Hyu Choi, "Low complexity semi–systolic multiplication architecture over GF(2m)", IEICE Electronics Express, 11(20), pp.20140713~20140713 (2014), Institute of Electronics, Information and Communications Engineers (IEICE)[DOI]
  13. Kee-Won Kim, "A Semi-systolic Montgomery Multiplier over GF(2m)", IEICE Electronics Express, 12(21), pp.20150769~20150769 (2015), Institute of Electronics, Information and Communications Engineers (IEICE)[DOI]
  14. Shyue-Win Wei, "A systolic power-sum circuit for GF(2", sup m, IEEE Transactions on Computers, pp.1994, 43(2)[DOI]
  15. Jyh-Huei Guo, "New systolic arrays for C+AB", sup 2, sup m, pp.), IEEE Transactions on Computers[DOI]
  16. C. H. Liu, "Computation of AB2Multiplier in GF(2m)Using an Efficient Low-complexity Cellular Architecture", IEICE Transactions on Fundamentals of Electronics, E83-A(2), pp.2657~2663 (2000)
  17. Chiou Yag Lee, "Low-complexity bit-parallel systolic architecture for computing AB", sup 2, sup m, pp.), IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing[DOI]
  18. Yeun-Renn Ting, "Low complexity bit-parallel systolic architecture for computing C+AB2 over a class of GF(2 )", Integration, 37(3), pp.167~176 (2004), Elsevier BV[DOI]
  19. C.-Y. Lee, "Low-complexity bit-parallel systolic architectures for computing A(x)B2(x) over GF(2m)", IEE Proceedings - Circuits, Devices and Systems, 153(4), pp.399~406 (2006), Institution of Engineering and Technology (IET)[DOI]
  20. Kee-Won Kim, "Low-complexity Parallel and Serial Systolic Architectures for AB2 Multiplication in GF(2m)", IETE Technical Review, 30(2), pp.134~141 (2013), Medknow[DOI]
  21. Kee-Won Kim, "An efficient parallel systolic array for AB2 over GF(2m)", IEICE Electronics Express, 10(20), pp.20130585~20130585 (2013), Institute of Electronics, Information and Communications Engineers (IEICE)[DOI]
  22. 김태완, "GF(2m) 상의 여분 표현을 이용한 낮은 지연시간의 몽고메리 AB2 곱셈기", 대한임베디드공학회논문지, 12(1), pp.11~18 (2017), 대한임베디드공학회[DOI]
  23. K.Z. Pekmestzi, "Multiplexer-based array multipliers", IEEE Transactions on Computers, 48(1), pp.15~23 (1999), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
  24. H. W. Chang, "Low Cost Dual-Basis Multiplier over GF(2m) Using Multiplexer Approach", Knowledge Discovery and Data Mining. Advances in Intelligent and Soft Computing, 135, pp.185~192 (2012)[DOI]
  25. S. S. Priya, "Multiplexer Based High Throughput S-box for AES Application", 2nd International Conference on Electronics and Communication Systems (ICECS), pp.242~247 (2015)
  26. G. Drolet, "A new representation of elements of finite fields GF(2", sup m, IEEE Transactions on Computers, pp.1998, 47(9)[DOI]
  27. Huapeng Wu, "Finite field multiplier using redundant representation", IEEE Transactions on Computers, 51(11), pp.1306~1316 (2002), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
  28. R. J. Baker, "CMOS Circuit, Design, Layout, and Simulation" (1998), IEEE Press
  29. "STMicroelectronics"[URL]

관련 논문AI추천

여분 기저를 이용한 멀티플렉서 기반의 유한체 곱셈기김기원대한임베디드공학회 · 대한임베디드공학회논문지2019 · 제14권 제6호유한체상의 효율적인 세미-시스톨릭 AB2 곱셈기김기원한국컴퓨터정보학회 · 한국컴퓨터정보학회논문지2020 · 제25권 제1호GF(2m) 상의 여분 표현을 이용한 낮은 지연시간의 몽고메리 AB2 곱셈기김기원, 김태완대한임베디드공학회 · 대한임베디드공학회논문지2017 · 제12권 제1호유한체 GF(2m)상의 낮은 지연시간의 AB2 곱셈 구조 설계김기원, 김현성, 이원진대한임베디드공학회 · 대한임베디드공학회논문지2012 · 제7권 제2호GF(2^m)상의 효율적인 세미-시스톨릭 몽고메리 곱셈기김기원한국컴퓨터정보학회 · 한국컴퓨터정보학회논문지2023 · 제28권 제2호유한체상의 낮은 복잡도를 갖는 비트-병렬 시스톨릭 다항식 곱셈기이건직(사)디지털산업정보학회 · (사)디지털산업정보학회 논문지2025 · 제21권 제2호

이 간행물의 다른 논문 (25건)

메모리 중심 컴퓨터 구조에서 MPI 병렬 프로그램의 효율적인 수행에 관한 연구신동하, 이승철, 이제만pp. 1-11전투관리체계 자원관리를 위해 Hysteresis를 이용한 DWDRR기반의 혼합 스케줄링 알고리즘이기엽pp. 21-27An Aging Measurement Scheme for Flash Memory Using LDPC Decoding Information강태근, 이현빈pp. 29-36유한체상의 효율적인 세미-시스톨릭 AB2 곱셈기김기원pp. 37-43CNN 알고리즘의 개선을 통한 대형 이미지에서의 객체식별양성봉, 이수진pp. 45-53
원문 보기