BROWSE
Detail
Journal Article
Low Space Complexity GF (2m) Multiplier for Trinomials Using n-Term Karatsuba Algorithm
- 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
- 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)
