Image Processing Reference
In-Depth Information
In order to design a reverse converter, we have to select appropriate moduli set with
considering the required parallelism and dynamic range requirements. Next, the moduli
should be substituted in one of mentioned conversion algorithm formulas, and the resulted
conversion equations should be simplified using some modulo arithmetic properties to
reduce hardware complexity. Finally, hardware implementation of the simplified equations
can be done using binary hardware's such as full adders, half adders, logic gates or lock-up
tables. In the following, we briefly review the formulas of reverse conversion algorithms for
four-moduli RNSs. Hence, consider the moduli set ( P 1 , P 2 , P 3 , P 4 ) with corresponding RNS
number ( x 1 , x 2 , x 3 , x 4 ).
By CRT (Parhami, 2000) the weighted number X can be calculated by
4
Xx NM
(2)
P
i
i
i
i
i
1
M
Where
M = P 1 P 2 P 3 P 4
(3)
MMP
(4)
i
i
NM
||
(5)
i
i
P i
The CRT has capability of parallel implementation; however its final big modulo adder
results in inefficient hardware realization if it is considered in direct form.
By MRC (Koc, 1989) the conversion can be done using the following equation:
XvPPP vPP vP v
(6)
4321
321
21
1
The v i 's coefficients are as follows
v 1 = x 1
(7)
vxv

(
)
1
(8)
2
2
1
1
P
2
P
2
v

((
x
v
)
P v
1
)
P
1
(9)
3
3
1
1
2
2
P
P
3
3
P
3
v
(((
x
v
)
P
1
v
)
P
1
v
)
P
1
(10)
4
4
1
1
2
2
3
3
P
P
P
4
4
4
P
4
Although MRC implies a sequential process, for two and three-moduli sets it can be lead to
simple and efficient reverse conversion equations.
The New CRT-I (Wang, 2000; Molahosseini et al., 2010) uses a more efficient conversion
formula
Xx Pkx x

(
 
)
kPx x
(
 
)
kPPx x
(
) PPP
(11)
1
1
1
2
1
2
2
3
2
3
2
3
4
3
234
Search WWH ::




Custom Search