A reverse converter for the 4-moduli superset {2n-1, 2 n, 2n+1, 2n+1+1}

M Bhardwaj, T Srikanthan, Christopher T Clarke

Research output: Contribution to conferencePaper

  • 27 Citations

Abstract

The authors propose an extension to the popular {2n-1, 2n, 2n+1} moduli set by adding a fourth modulus 2n+1+1. This extension leads to higher parallelism while keeping the forward conversion and modular arithmetic units simple. The main challenge of efficient reverse conversion is met by three techniques described for the first time. Firstly, we reverse convert linear combinations of moduli hence reducing the number of non-zero bits in the Booth encoded multiplicands from n to merely 2. Secondly, it is shown that division by 3, if introduced at the right stage, can be implemented very efficiently and can, in turn, reduce the cost of the converter. To implement VLSI efficient modulo reduction, we propose two techniques-multiple split tables (MST) and a modified division algorithm (MDA). It is shown that the MST can reduce exponential ROM requirements to quadratic ROM requirements while the MDA can reduce these further to linear requirements. As a result of these innovations, the proposed reverse converter uses simple shift and add operations and needs a lookup with only 6 entries. The delay of the converter is approximately 10n+13 full adder delays and the area cost is quadratic in n
LanguageEnglish
Pages168-175
Number of pages8
StatusPublished - Apr 1999
Event14th IEEE Symposium on Computer Arithmetic - Adelaide, Australia
Duration: 14 Apr 199916 Apr 1999

Conference

Conference14th IEEE Symposium on Computer Arithmetic
CountryAustralia
CityAdelaide
Period14/04/9916/04/99

Fingerprint

ROM
Adders
Costs
Innovation

Cite this

Bhardwaj, M., Srikanthan, T., & Clarke, C. T. (1999). A reverse converter for the 4-moduli superset {2n-1, 2 n, 2n+1, 2n+1+1}. 168-175. Paper presented at 14th IEEE Symposium on Computer Arithmetic, Adelaide, Australia.

A reverse converter for the 4-moduli superset {2n-1, 2 n, 2n+1, 2n+1+1}. / Bhardwaj, M; Srikanthan, T; Clarke, Christopher T.

1999. 168-175 Paper presented at 14th IEEE Symposium on Computer Arithmetic, Adelaide, Australia.

Research output: Contribution to conferencePaper

Bhardwaj, M, Srikanthan, T & Clarke, CT 1999, 'A reverse converter for the 4-moduli superset {2n-1, 2 n, 2n+1, 2n+1+1}' Paper presented at 14th IEEE Symposium on Computer Arithmetic, Adelaide, Australia, 14/04/99 - 16/04/99, pp. 168-175.
Bhardwaj M, Srikanthan T, Clarke CT. A reverse converter for the 4-moduli superset {2n-1, 2 n, 2n+1, 2n+1+1}. 1999. Paper presented at 14th IEEE Symposium on Computer Arithmetic, Adelaide, Australia.
Bhardwaj, M ; Srikanthan, T ; Clarke, Christopher T. / A reverse converter for the 4-moduli superset {2n-1, 2 n, 2n+1, 2n+1+1}. Paper presented at 14th IEEE Symposium on Computer Arithmetic, Adelaide, Australia.8 p.
@conference{3c7b1cd1fea44e1d859457c9efaf7a9a,
title = "A reverse converter for the 4-moduli superset {2n-1, 2 n, 2n+1, 2n+1+1}",
abstract = "The authors propose an extension to the popular {2n-1, 2n, 2n+1} moduli set by adding a fourth modulus 2n+1+1. This extension leads to higher parallelism while keeping the forward conversion and modular arithmetic units simple. The main challenge of efficient reverse conversion is met by three techniques described for the first time. Firstly, we reverse convert linear combinations of moduli hence reducing the number of non-zero bits in the Booth encoded multiplicands from n to merely 2. Secondly, it is shown that division by 3, if introduced at the right stage, can be implemented very efficiently and can, in turn, reduce the cost of the converter. To implement VLSI efficient modulo reduction, we propose two techniques-multiple split tables (MST) and a modified division algorithm (MDA). It is shown that the MST can reduce exponential ROM requirements to quadratic ROM requirements while the MDA can reduce these further to linear requirements. As a result of these innovations, the proposed reverse converter uses simple shift and add operations and needs a lookup with only 6 entries. The delay of the converter is approximately 10n+13 full adder delays and the area cost is quadratic in n",
author = "M Bhardwaj and T Srikanthan and Clarke, {Christopher T}",
year = "1999",
month = "4",
language = "English",
pages = "168--175",
note = "14th IEEE Symposium on Computer Arithmetic ; Conference date: 14-04-1999 Through 16-04-1999",

}

TY - CONF

T1 - A reverse converter for the 4-moduli superset {2n-1, 2 n, 2n+1, 2n+1+1}

AU - Bhardwaj,M

AU - Srikanthan,T

AU - Clarke,Christopher T

PY - 1999/4

Y1 - 1999/4

N2 - The authors propose an extension to the popular {2n-1, 2n, 2n+1} moduli set by adding a fourth modulus 2n+1+1. This extension leads to higher parallelism while keeping the forward conversion and modular arithmetic units simple. The main challenge of efficient reverse conversion is met by three techniques described for the first time. Firstly, we reverse convert linear combinations of moduli hence reducing the number of non-zero bits in the Booth encoded multiplicands from n to merely 2. Secondly, it is shown that division by 3, if introduced at the right stage, can be implemented very efficiently and can, in turn, reduce the cost of the converter. To implement VLSI efficient modulo reduction, we propose two techniques-multiple split tables (MST) and a modified division algorithm (MDA). It is shown that the MST can reduce exponential ROM requirements to quadratic ROM requirements while the MDA can reduce these further to linear requirements. As a result of these innovations, the proposed reverse converter uses simple shift and add operations and needs a lookup with only 6 entries. The delay of the converter is approximately 10n+13 full adder delays and the area cost is quadratic in n

AB - The authors propose an extension to the popular {2n-1, 2n, 2n+1} moduli set by adding a fourth modulus 2n+1+1. This extension leads to higher parallelism while keeping the forward conversion and modular arithmetic units simple. The main challenge of efficient reverse conversion is met by three techniques described for the first time. Firstly, we reverse convert linear combinations of moduli hence reducing the number of non-zero bits in the Booth encoded multiplicands from n to merely 2. Secondly, it is shown that division by 3, if introduced at the right stage, can be implemented very efficiently and can, in turn, reduce the cost of the converter. To implement VLSI efficient modulo reduction, we propose two techniques-multiple split tables (MST) and a modified division algorithm (MDA). It is shown that the MST can reduce exponential ROM requirements to quadratic ROM requirements while the MDA can reduce these further to linear requirements. As a result of these innovations, the proposed reverse converter uses simple shift and add operations and needs a lookup with only 6 entries. The delay of the converter is approximately 10n+13 full adder delays and the area cost is quadratic in n

M3 - Paper

SP - 168

EP - 175

ER -