유한체상의 효율적인 세미-시스톨릭 AB2 곱셈기 (Efficient Semi-systolic AB2 Multiplier over Finite Fields)

서지정보

· 발행기관 : 한국컴퓨터정보학회
· 수록지 정보 : 한국컴퓨터정보학회논문지 / 25권 / 1호 / 37 ~ 43페이지
· 저자명 : 김기원

초록

본 논문에서는 유한체상의 SPB(shifted polynomial basis)를 사용한 효율적인 AB2 곱셈 알고리즘을 제안한다. SPB의 특징을 이용하여, AB2 곱셈을 위한 수식을 두 부분으로 분할하였다. 분할된두 수식은 동시에 실행가능하며, 이를 병렬로 처리하는 알고리즘을 도출하였다. 그리고 제안한 알고리즘을 기반으로 효율적인 세미-시스톨릭(semi-systolic) AB2 곱셈기를 제안한다. 제안한 곱셈기는기존의 곱셈기에 비해 낮은 공간-시간 복잡도(area-time complexity)를 가진다. 기존의 구조들과 비교하면, 제안한 AB2 곱셈기는 공간-시간 복잡도면에서 Wei, Wang-Guo, Kim-Lee, 및 Choi-Lee의 곱셈기들의 약 94%, 87%, 86%, 및 83% 가량이 감소되었다. 따라서 제안한 곱셈기는 VLSI(very large scale integration) 구현에 적합하며 다양한 응용의 기초적인 구성 요소로 쉽게 적용할 수 있다.

영어초록

In this paper, we propose an efficient AB2 multiplication algorithm using SPB(shifted polynomial basis) over finite fields. Using the feature of the SPB, we split the equation for AB2 multiplication into two parts.
The two partitioned equations are executable at the same time, and we derive an algorithm that processes them in parallel. Then we propose an efficient semi-systolic AB2 multiplier based on the proposed algorithm. The proposed multiplier has less area-time (AT) complexity than related multipliers. In detail, the proposed AB2 multiplier saves about 94%, 87%, 86% and 83% of the AT complexity of the multipliers of Wei, Wang-Guo, Kim-Lee, Choi-Lee, respectively. Therefore, the proposed multiplier is suitable for VLSI implementation and can be easily adopted as the basic building block for various applications.

참고자료

· 없음