삼항 다항식을 이용한 효율적인 비트-병렬 구조의 곱셈기
Design of an Efficient Bit-Parallel Multiplier using Trinomials
0
조회
0
다운로드
1
인용
0
참고문헌
초록
최근 빠른 하드웨어의 구현은 속도의 효율성을 중시하는 환경에서 큰 관심의 대상이 되고 있다. 유한체 연산기는 연산과정이 복잡한 곱셈 연산에 의해 속도가 결정된다. 연산 수행 속도를 빠르게 개선하기 위해 본 논문에서는 하드웨어 구조를 기존의 Mastrovito방법을 이용하여 제안하고자 한다. 삼항기약다항식(trinomial) 를 이용하여 제안하는 곱셈기의 시간 복잡도를 기존의 복잡도[14] 에서 으로 감소시킨다. 그러나 공간 복잡도를 살펴보면 AND 게이트 수가 기존의 복잡도와 으로 같지만, XOR 게이트의 수는 기존 복잡도[14]인 에서 으로 기약다항식의 중간항 차수인 에 따라 약간 증가된다. 기약다항식의 최고차 항을 표준에서 권장하는 차수와 그에 준하는 다항식의 차수에 대해 XOR 공간 복잡도가 평균적으로 1.18% 증가하는 데 비해, 시간 복잡도는 평균적으로 9.036% 정도 감소한다.
Abstract
Recently efficient implementation of finite field operation has received a lot of attention. Among the GF(2m) arithmetic operations, multiplication process is the most basic and a critical operation that determines speed-up hardware. We propose a hardware architecture using Mastrovito method to reduce processing time. Existing Mastrovito multipliers using the special generating trinomial p(x)=xm+xn+1 require m2-1 XOR gates and m2 AND gates. The proposed multiplier needs m2 AND gates and XOR gates that depend on the intermediate term xn. Time complexity of existing multipliers is and that of proposed method is . The proposed architecture is efficient for the extension degree m suggested as standards: SEC2, ANSI X9.63. In average, XOR space complexity is increased to 1.18% but time complexity is reduced 9.036%.