[논문]Efficient Bit-Parallel Multiplier for All Trinomials Based on n-Term Karatsuba Algorithm

Park, Sun-Mi; Chang, Ku-Young; Hong, Dowon; Seo, Changho

doi:10.1109/access.2020.3023804

[해외논문] Efficient Bit-Parallel Multiplier for All Trinomials Based on n-Term Karatsuba Algorithm 원문보기

IEEE access : practical research, open solutions, v.8, 2020년, pp.173491 - 173507

Park, Sun-Mi (Department of Applied Mathematics, Kongju National University, Gongju, South Korea) , Chang, Ku-Young (Cyber Security Research Division, Electronics and Telecommunications Research Institute (ETRI), Daejeon, South Korea) , Hong, Dowon (Department of Applied Mathematics, Kongju National University, Gongju, South Korea) , Seo, Changho (Department of Applied Mathematics, Kongju National University, Gongju, South Korea)

Abstract ▼ AI-Helper

Recently, hybrid multiplication schemes over the binary extension field $GF(2^{m})$ based on $n$-term Karatsuba algorithm (KA) have been proposed for irreducible trinomials. Their complexities depend on a decomposition of $m$ and the choice of a generation polynomial. However, these multipliers have some limitations on a decomposition of $m$ or generation polynomial $x^{m}+x^{k}+1$ such that $m\geq 2k$. In this paper, we loosen such limited conditions. We present a new hybrid bit-parallel multiplier based on $n$-term KA for any irreducible trinomial $x^{m}+x^{k}+1\,\,(0< k< m)$, where $m$ is decomposed as $m=nm_{0}+r$ with $0< r< m_{0}$ and $1< n$. (Here, various values for $n,m_{0}$ and $r$ may be chosen.) To this end, we generalize the previously proposed multiplication scheme for $x^{nm_{0}+1}+x^{k}+1$ into $x^{nm_{0}+r}+x^{k}+1$. We evaluate the explicit complexity of the proposed multiplier. Specific comparisons show that the proposed multiplier achieves the lowest space complexity with the same or lower time complexity among hybrid multipliers. Compared to the fastest multipliers, the time complexity of the proposed multiplier costs only $T_{X}$ higher while its space complexity is much lower (it has roughly 40% reduced space complexity), where $T_{X}$ is the delay of one 2-input XOR gate.

참고문헌 (22)

Reyhani-Masoleh, A., Hasan, M.A.. Low Complexity Bit Parallel Architectures for Polynomial Basis Multiplication over GF(2^{m}). IEEE transactions on computers, vol.53, no.8, 945-959.

상세보기
Hariri, A., Reyhani-Masoleh, A.. Bit-Serial and Bit-Parallel Montgomery Multiplication and Squaring over GF(2^m). IEEE transactions on computers, vol.58, no.10, 1332-1345.

상세보기
Generalizations of the Karatsuba algorithm for efficient implementations weimerskirch 2006
Elia, M., Leone, M., Visentin, C.. Low complexity bit-parallel multipliers for GF(2^m) with generator polynomial x^m+x^k+1. Electronics letters, vol.35, no.7, 551-552.

상세보기
Li, Y., Chen, G.l., Li, J.h.. Speedup of bit-parallel Karatsuba multiplier in GF(2^m) generated by trinomials. Information processing letters, vol.111, no.8, 390-394.

상세보기
Shen, H., Jin, Y.. Low complexity bit parallel multiplier for GF(2^m) generated by equally-spaced trinomials. Information processing letters, vol.107, no.6, 211-215.

상세보기
Li, Yin, Ma, Xingpo, Zhang, Yu, Qi, Chuanda. Mastrovito Form of Non-Recursive Karatsuba Multiplier for All Trinomials. IEEE transactions on computers, vol.66, no.9, 1573-1584.

상세보기
Li, Yin, Zhang, Yu, Guo, Xiaoli, Qi, Chuanda. N-Term Karatsuba Algorithm and its Application to Multiplier Designs for Special Trinomials. IEEE access : practical research, open solutions, vol.6, 43056-43069.

상세보기
Park, Sun-Mi, Chang, Ku-Young, Hong, Dowon, Seo, Changho. Low Space Complexity $GF(2^m)$ Multiplier for Trinomials Using $n$-Term Karatsuba Algorithm. IEEE access : practical research, open solutions, vol.7, 27047-27064.

상세보기
Li, Yin, Sharma, Shantanu, Zhang, Yu, Ma, Xingpo, Qi, Chuanda. On the Complexity of Hybrid $n$-Term Karatsuba Multiplier for Trinomials. IEEE transactions on circuits and systems. a publication of the IEEE Circuits and Systems Society. I, Regular papers, vol.67, no.3, 852-865.

상세보기
Sunar, B.. A generalized method for constructing subquadratic complexity GF(2^k) multipliers. IEEE transactions on computers, vol.53, no.9, 1097-1105.

상세보기
2000
Haining Fan. A Chinese Remainder Theorem Approach to Bit-Parallel $GF(2^{n})$ Polynomial Basis Multipliers for Irreducible Trinomials. IEEE transactions on computers, vol.65, no.2, 343-352.

상세보기
Fan, H., Sun, J., Gu, M., Lam, K.-Y.. Overlap-free Karatsuba-Ofman polynomial multiplication algorithms. IET information security, vol.4, no.1, 8-14.

상세보기
Fan, Haining, Hasan, M. Anwar. Fast Bit Parallel-Shifted Polynomial Basis Multipliers in $GF(2^{n})$. IEEE transactions on circuits and systems. a publication of the IEEE Circuits and Systems Society. I, Regular papers, vol.53, no.12, 2606-2615.

상세보기
Fan, Haining, Dai, Yiqi. Fast bit-parallel GF(2ⁿ) multiplier for all trinomials. IEEE transactions on computers, vol.54, no.4, 485-490.

상세보기
10.1017/CBO9780511525926
10.1017/CBO9781139172769
VLSI architectures for computation in Galois fields mastrovito 1991
Xie, X.n., Chen, G.l., Li, Y.. Novel bit-parallel multiplier for GF(2^m) defined by all-one polynomial using generalized Karatsuba algorithm. Information processing letters, vol.114, no.3, 140-146.

상세보기
Li, Y., Chen, Y.. New bit-parallel Montgomery multiplier for trinomials using squaring operation. Integration, the VLSI journal, vol.52, 142-155.

상세보기
Park, Sun-Mi, Chang, Ku-Young, Hong, Dowon, Seo, Changho. Space Efficient $GF(2^m)$ Multiplier for Special Pentanomials Based on $n$-Term Karatsuba Algorithm. IEEE access : practical research, open solutions, vol.8, 27342-27360.

상세보기

LOADING...

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

원문 보기

AccessON 원문보기

원문 URL 링크

DOI : 10.1109/ACCESS.2020.3023804 [무료]
IEEE : 저널 > 논문 [무료]
AccessON : 저널

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

오픈액세스(OA) 유형

GOLD

오픈액세스 학술지에 출판된 논문

저작권 관리 안내

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

Text(ASCII format)
Excel format
RefWorks Direct Export
RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley

메일정보

받는사람 (필수): @
보내는사람 (선택): @
제목
내용: KISTI 검색결과 이메일 서비스

안내

총 건의 자료가 검색되었습니다.

다운받으실 자료의 인덱스를 입력하세요. (1-10,000)

검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다.

데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요)

다운로드 파일은 UTF-8 형태로 저장됩니다.
파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오.

Text(ASCII format)
Excel format

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증