Can. J. Elect. Comput. Eng., Vol. 36, No. 3, Summer 2013
I Introduction
Floating-point multiplication and addition are the most common
fl oating-point operations used in various digital signal processing
techniques. The speed of the Leading-Zero Anticipator (LZA) is
important in designing high speed fl oating-point addition and its
signifi cance is highlighted in [1]. A clear analysis of various application
data show that the signal processing algorithms require, on average, 40%
multiplication and 60% addition operations [2]. As the fl oating-point
multiplication and addition is the most complex part of various DSP
algorithms, it needs to be optimized to overcome the critical bottlenecks
viz., latency and area. LODs and LOPDs determine the location of the
most signifi cant one or a leading bit in a given binary. The position of
leading one is used for the normalization process and shifting process
in the fl oating-point multiplication, fl oating-point addition and also in
binary logarithmic converters [3]. Over the years, the very large scale
integration (VLSI) community has developed various architectures for
LODs and LOPDs, aimed primarily at reducing the overall latency [4].
Research has been going on to evolve various combinatorial circuits
in a constrained space with minimum effort [5]. A modular circuit for
determining the leading one bit in a binary word is discussed and it
is used for fl oating-point normalization [6]. Both leading zero and
leading one anticipation circuits are discussed by Schmookler in [7]
which uses AND gate in the fi nal stage to equalize the total delay. Ji ,
Rong et al [8] provide useful analysis of error in the pre-encoding logic
in the leading one predictor module proposed in [19]. A Hybrid LZA
is proposed in [9] focusing on the improvement of delay and hardware
area in fl oating-point addition. A concurrent position correction logic,
operating in parallel with the LOP, to detect the presence of that error
and produce the correct shift amount is discussed in [10]. By using
binary trees and detecting larger groups of zeros, a better speed up
can be obtained [11], [12]. Mahdiani et al. proposed evolutionary
algorithm based bio-inspired computational blocks which are effi cient
in terms of area, speed and power consumption [13]. Various evolved
gate level architectures of binary multiplier are proposed in [14] but the
effi ciency and tradeoffs with the existing method are not discussed. An
evolvable hardware structure based on a Boolean functions network
is implemented with the basic multiplexer circuit and confi gured by
a hardware genetic algorithm in [15]. A complete survey of evolvable
hardware with emphasis on some of the latest developments shows
certain performance benefi ts exceeding the traditional methods [16].
Nancy Forbes discusses the evolution on a chip to optimize the circuit
design based on fi refl y machine [17]. The on-chip adaptation and
self confi guration of reconfi gurable hardware through evolutionary
algorithms is termed as evolutionary hardware [18]. Adrian Stoica
proposes an evolution-oriented fi eld programmable transistor array
(FPTA), reconfi gurable at transistor level which allows evolutionary
experiments with reconfi guration at various levels of granularity.
Leading one detectors and leading one position
detectors – an evolutionary design methodology
Manuscript received 20-May-2012; accepted 20-Jun-2013.
* K.Kunaraj is a Research Scholar and Senior Research Fellow, ECE,
CEG with Anna University, Chennai – 600025, India. Dr.R.Seshasayanan is
Associate Professor, ECE, CEG with Anna University, Chennai – 600025, India.
Email: k.kunaraj@ieee.org, seshasayanan@annauniv.edu
Associate Editor managing this paper’s review: Ali Miri
Design of leading-one detector (LOD) and leading-one position detector (LOPD) are important as they are used for the normalization process in fl oating-
point multiplication, fl oating-point addition/subtraction and in logarithmic converters. In this paper, the authors propose various gate-level architectures for
LOD and LOPD. The LOD and LOPD circuits are evolved using the evolutionary algorithm (EA) and using the evolved lower-order gate structures, various
higher-order circuits are constructed. To obtain better results, the EA is modifi ed and a novel shuffl ing operation is performed to prevent the algorithm from
settling in the local minima. Then the constructed LOD and LOPD circuit is synthesized using Cadence® RTLCompiler® using TSMC 180nm library. The
LOD and LOPD circuits can be implemented in an Application Specifi c Integrated circuit (ASIC) or in a Field Programmable Gate Array (FPGA), and hence
it is independent of the technology library. Perhaps the evolution can also be made as an intrinsic process during the application run time and the evolved
best gate structure can be chosen. We restrict this paper to the extrinsic evolution of LOD and LOPD gate level architectures.
La conception des détecteurs de bit 1 principal (LOD) et des détecteurs de position de bit 1 principal (LOPD) est importante car ceux-ci sont utilisés dans
le processus de normalisation lors de la multiplication et l’addition/soustraction en virgule fl ottante, ainsi que dans les convertisseurs logarithmiques. Dans
cet article, nous présentons diverses architectures à portes logiques pour LOD et LOPD. Les circuits LOD et LOPD évoluent en utilisant l’algorithme évo-
lutionnaire (AE) et les structures de portes logiques d’ordre inférieur évoluées. Divers circuits d’ordre supérieur sont construits. Pour obtenir de meilleurs
résultats, l’AE est modifi é et une nouvelle opération de brassage est réalisée pour éviter à l’algorithme de passer par un minimum local. Les circuits LOD et
LOPD construits sont ensuite synthétisés en utilisant Cadence® RTLCompiler® qui utilise la librairie TSMC 180nm. Les circuits LOD et LOPD peuvent
être implémentés en ASIC et en FPGA et sont ainsi indépendants de la librairie de la technologie utilisée. Peut-être que l’évolution peut aussi s’effectuer
comme un processus intrinsèque pendant l’exécution de l’application et que la meilleure structure de portes évoluée peut être choisie. Dans cet article, nous
nous limitons à l’évolution extrinsèque des architectures LOD et LOPD à portes logiques.
Keywords: leading one detector, leading one position detector, genetic algorithm, evolvable hardware.
K. Kunaraj and Dr. R. Seshasayanan *
Détecteurs de bit 1 principal et détecteurs de
position de bit 1 principal – une méthodologie
de conception évolutionnaire
Authorized licensed use limited to: Communication University of China. Downloaded on September 11,2020 at 11:00:45 UTC from IEEE Xplore. Restrictions apply.