본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

타입 II ONB를 이용한 GF($2^m$)상의 곱셈에 대한 낮은 복잡도와 작은 지연시간을 가지는 시스톨릭 어레이
A Low Complexity and A Low Latency Systolic Arrays for Multiplication in GF($2^m$) Using An Optimal Normal Basis of Type II

권순학   (성균관대학교 수학과UU0000759  ); 권윤기   (성균관대학교 수학과UU0000759  ); 김창훈   (대구대학교 컴퓨터IT공학부UU0000355  ); 홍춘표   (대구대학교 정보통신공학부UU0000355  );
  • 초록

    타입 II ONB(optimal normal basis)의 자기쌍대성(self duality)을 이용하여 낮은 하드웨어 복잡도와 작은 지연시간을 가지는 GF( $2^m$ )상의 비트 패러럴, 시리얼 시스톨릭 어레이를 제안하였다. 제안된 곱셈기는 m+1의 지연시간을 가지며 각 셀은 5개의 래치(플립-플롭)로 구성된다. 제안된 어레이는 다른 어레이와 비교하여 공간 복잡도와 지연시간을 줄임을 알 수 있다.


    Using the self duality of an optimal normal basis(ONB) of type II, we present a bit parallel and bit serial systolic arrays over GF( $2^m$ ) which has a low hardware complexity and a low latency. We show that our multiplier has a latency m+1 and the basic cell of our circuit design needs 5 latches(flip-flops). Comparing with other arrays of the same kinds, we find that our array has significantly reduced latency and hardware complexity.


  • 주제어

    ONB .   Finite Field .   Multiplication .   Systolic Array.  

  • 참고문헌 (21)

    1. A.J. Menezes, Applications of finite fields, Kluwer Academic Publisher, 1993 
    2. S. Kwon and H. Ryu, "Efficient bit serial multiplication using optimal normal bases of type II in GF$(2^{m})$," Lecture Notes in Computer Science, vol. 2433, pp. 300-308, 2002 
    3. C.K. Koc and B. Sunar, "Low complexity bit paraller canonical and normal basis multipliers for a class of finite fields," IEEE Trans. Computers, vol. 47, pp. 353-356, 1998 
    4. A. Reyhani-Masoleh and M.A. Hasan, "A new construction of Massey-Omura parallel multiplier over GF$(2^{m})$," IEEE Trans. Computers, vol. 51, pp. 511-520, 2002 
    5. C.Y. Lee, E.H. Lu and J.Y. Lee, "Bit parallel systolic multipliers for GF$(2^{m})$ fields defined by all one and equally spaced polynomials," IEEE Trans. Computers, vol. 50, pp. 385-393, 2001 
    6. H. Wu, M.A. Hasan, I.F. Blake and S. Gau, "Finite field multiplier using redundant representation," IEEE Trans. Computers, vol. 51, pp. 1306-1316, 2002 
    7. G.B. Agnew, R.C. Mullin, I. Onyszchuk and S.A. Vanstone, "An implementation for a fast public key cryptosystem," J. Cryptology, vol. 3, pp. 63-79, 1991 
    8. S.K. Jain, L. Song and K.K. Parhi, "Efficient semisystolci architectures for finite field arithmetic," IEEE Trans. VLSI Syst., vol. 6, pp. 101-113, 1998 
    9. M. Wang and I.F. Blake, "Bit serial multiplication in finite fields," SIAM J. Disc. Math., vol. 3, pp. 140-148, 1990 
    10. S. Gao, J. von zur Gathen and D. Panario, "Gauss periods and fast exponentiation in finite fields," Lecture Notes in Computer Science, vol. 911, pp. 311-322, 1995 
    11. J.H. Guo and C.L. Wang, "Systolic array implementation of Euclid's algorithm for inversion and division in GF$(2^{m})$," IEEE Trans. Computers, vol. 47, pp. 1161-1167, 1998 
    12. C.S. Yeh, I.S. Reed and T.K. Troung, "Systolic multipliers for finite fields GF$(2^{m})$," IEEE Trans. Computers, vol. C-33, pp. 357-360, 1984 
    13. S.T.J. Fenn, M. Benaissa and D. Taylor, "Dual basis systolic multipliers for GF$(2^{m})$," IEE Proc. Comput. Digit. Tech., vol. 144, pp. 43-46, 1997 
    14. C.W. Wei, "A systolic power sum circuit for GF$(2^{m})$," IEEE Trans. Computer, vol. 43, pp. 226-229, 1994 
    15. E.R. Berlekamp, "Bit-serial Reed-Solomon encoders," IEEE Trans. Inform. Theory, vol. 28, pp. 869-874, 1982 
    16. T. Itoh and S. Tsujii, "Sturcture of parallel multipliers for a class of finite fields GF$(2^{m})$," Information and computation, vol. 83, pp. 21-40, 1989 
    17. C.Y. Lee, E.H. Lu and L.F. Sun, "Low complexity bit parallel systolic architecture for computing $AB^{2}+C$ in a class of finite field GF$(2^{m})$," IEEE Trans. Circuits Syst. II, vol. 48, pp. 519-523, 2001 
    18. C. Paar, P. Fleischmann and P. Roelse, "Efficient multiplier architectures for Galois fields $GF(2^{4n})$," IEEE Trans. Computers, vol. 47, pp. 162-170, 1998 
    19. C.L. Wang and J.L. Lin, "Systolic array implementation of multipliers for finite fields GF$(2^{m})$," IEEE Trans. Circuits Syst., vol. 38, pp. 796-800, 1991 
    20. W.C. Tsai, C.B. Shung and S.J. Wang, "Two systolic architectures for modular multiplication," IEEE Trans. VLSI Syst., vol. 8, pp. 103-107, 2000 
    21. B. Sunar and C.K. Koc, "An efficient optimal normal basis type II multiplier," IEEE Trans. Computers, vol 50, pp. 83-87, 2001 

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기