ETRI-Knowledge Sharing Plaform

KOREAN
논문 검색
Type SCI
Year ~ Keyword

Detail

Journal Article Low Space Complexity GF (2m) Multiplier for Trinomials Using n-Term Karatsuba Algorithm
Cited 6 time in scopus Download 27 time Share share facebook twitter linkedin kakaostory
Authors
Sun-Mi Park, Ku-Young Chang, Dowon Hong, Changho Seo
Issue Date
2019-02
Citation
IEEE Access, v.7, pp.27047-27064
ISSN
2169-3536
Publisher
IEEE
Language
English
Type
Journal Article
DOI
https://dx.doi.org/10.1109/ACCESS.2019.2901242
Abstract
We propose bit-parallel GF(2{m}) multipliers for irreducible trinomials using an n -term Karatsuba algorithm and Mastrovito approach, which are generalizations of the newly proposed multiplication scheme for a specific trinomial. The complexities of the proposed multipliers for GF(2{m}) depend on the choice of an irreducible trinomial x{m}+x{k}+1 defining GF(2{m}) and values n , m-{0} such that m=nm-{0} or m=nm-{0}+1. It is possible to achieve a space-time tradeoff by choosing proper values for k,~n , and m-{0}. For the purpose of a specific comparison, we compare the proposed multipliers with the best-known multipliers for an odd m\in [{399,450}] for which there exists an irreducible trinomial of degree m. As a result, the proposed multipliers achieve the lowest space complexities among similar bit-parallel multipliers (they have roughly 40% reduced space complexities compared with the fastest multiplier). On the other hand, their time complexities match or are at most 2T-{X} higher than the fastest multipliers, where T-{X} is the delay of one 2-input XOR gate.
KSP Keywords
Karatsuba algorithm, Sampling Time(Ts), Space Complexity, Space time(ST), XOR gate, bit-parallel
This work is distributed under the term of Creative Commons License (CCL)
(CC BY NC ND)
CC BY NC ND