Image Processing Reference
In-Depth Information
dynamic range. The most well-known 3 n -bit dynamic range moduli set is {2 n -1, 2 n , 2 n +1}
(Gallaher et al., 1997; Bhardwaj et al., 1998; Wang et al., 2000; Wang et al., 2002). The main
reasons for the popularity of this set are its well-form and balanced moduli. However, the
modulo 2 n +1 has lower performance than the other two moduli. Hence, some efforts have
been done to substitute the modulo 2 n +1 with other well-form RNS moduli, and the resulted
moduli sets are {2 n -1, 2 n , 2 n-1 -1} (Hiasat & Abdel-Aty-Zohdy, 1998; Wang et al., 2000b), {2 n -1,
2 n , 2 n+1 -1} (Mohan, 2007; Lin et al., 2008).
The dynamic ranges provided by these three moduli sets are not adequate for recent
applications which require higher performance. Two approaches have been proposed to
solve this problem. First, using three-moduli sets to provide large dynamic range with some
specific forms like {2 α , 2 β - 1, 2 β + 1} where α < β (Molahosseini et al., 2008) and {2 2 n , 2 n -1, 2 n +1 -
1} (Molahosseini et al., 2009). Second, using four and five moduli sets to increase dynamic
range and parallelism in RNS arithmetic unit. The 4 n -bit dynamic range four-moduli sets are
{2 n -1, 2 n , 2 n +1, 2 n +1 +1} (Bhardwaj et al., 1999; Mohan & Premkumar, 2007) and {2 n -1, 2 n , 2 n +1,
2 n +1 -1} (Vinod et al., 2000; Mohan & Premkumar, 2007). Although, these four-moduli sets
include relatively balanced moduli, their multiplicative inverses are very complicated, and
this results in low-performance reverse converters. Furthermore, some recent applications
require even more dynamic range than 4 n -bit. This demand results in introducing new class
of moduli sets which have been called large dynamic range four-moduli sets . The first one is the
5 n -bit dynamic range moduli set {2 n -1, 2 n , 2 n +1, 2 2n +1} that was proposed by (Cao et al.,
2003). Next, (Zhang et al., 2008) enhanced the dynamic range to 6 n -bit, and introduced the
set {2 n - 1, 2 n +1, 2 2 n -2, 2 2 n +1 -3}. Moreover, (Molahosseini et al., 2010) proposed the four-
moduli sets {2 n -1, 2 n , 2 n +1, 2 2 n +1 -1} and {2 n -1, 2 n +1, 2 2 n , 2 2 n +1} in 5 n and 6 n -bit dynamic
range, respectively.
In this chapter, after an introduction about RNS and reverse conversion algorithms, the
architecture of the state-of-the-art reverse cnverters which have been designed for the
efficient large dynamic range four-moduli sets {2 n -1, 2 n , 2 n +1, 2 2n +1}, {2 n -1, 2 n +1, 2 2 n ,
2 2 n +1} and {2 n -1, 2 n , 2 n +1, 2 2 n +1 -1} will be investigated. Furthermore, a recent contribution
about modified version of the four-moduli set {2 n -1, 2 n , 2 n +1, 2 2 n +1 -1} that is {2 n -1, 2 n +1,
2 2 n , 2 2 n +1 -1} will be studied. Finally, we present performance comparison in terms of
hardware requirements and conversion delays, between the investigated reverse
converters.
2. Background
The fundamental part of RNS (Omondi & Premkumar, 2007) is the moduli set { P 1 , P 2 , …, P n }
where numbers are relatively-prime, i.e. gcd( P i , P j )=1 for i j . The binary weighted number X
can be represented as X =( x 1 , x 2 , … , x n ), where
xX
mod
PX
,0
 
xP
(1)
P
i
i
i
i
i
This representation is unique for any integer number X in the range [0, M -1], where
M = P 1 P 2 P n is the dynamic range of the moduli set { P 1 , P 2 , …, P n } (Taylor, 1984). Addition
(subtraction) and multiplication on RNS numbers can be performed in parallel due to the
absence of carry propagation between residues.
The famous algorithms for performing reverse conversion are Chinese remainder theorem
(CRT), mixed-radix conversion (MRC) and new Chinese remainder theorems (New CRTs).
Search WWH ::




Custom Search