On generating optimal signal probabilities for random tests: A genetic approach

Genetic Algorithms are robust search and optimization techniques. A Genetic Algorithm based approach for determining the optimal input distributions for generating random test vectors is proposed in the paper. A cost function based on the COP testability measure for determining the efficacy of the input distributions is discussed, A brief overview of Genetic Algorithms (GAs) and the specific details of our implementation are described. Experimental results based on ISCAS-85 benchmark circuits are presented. The performance pf our GA-based approach is compared with previous results. While the GA generates more efficient input distributions than the previous methods which are based on gradient descent search, the overheads of the GA in computing the input distributions are larger. To account for the relatively quick convergence of the gradient descent methods, we analyze the landscape of the COP-based cost function. We prove that the cost function is unimodal in the search space. This feature makes the cost function amenable to optimization by gradient-descent techniques as compared to random search methods such as Genetic Algorithms.

Design and realization of high-performance wave-pipelined 8×8 b multiplier in CMOS technology

Wave pipelining is a design technique for increasing the throughput of a digital circuit or system without introducing pipelining registers between adjacent combinational logic blocks in the circuit/system. However, this requires balancing of the delays along all the paths from the input to the output which comes the way of its implementation. Static CMOS is inherently susceptible to delay variation with input data, and hence, receives a low priority for wave pipelined digital design. On the other hand, ECL and CML, which are amenable to wave pipelining, lack the compactness and low power attributes of CMOS. In this paper we attempt to exploit wave pipelining in CMOS technology. We use a single generic building block in Normal Process Complementary Pass Transistor Logic (NPCPL), modeled after CPL, to achieve equal delay along all the propagation paths in the logic structure. An 8×8 b multiplier is designed using this logic in a 0.8 ?m technology. The carry-save multiplier architecture is modified suitably to support wave pipelining, viz., the logic depth of all the paths are made identical. The 1 mm×0.6 mm multiplier core supports a throughput of 400 MHz and dissipates a total power of 0.6 W. We develop simple enhancements to the NPCPL building blocks that allow the multiplier to sustain throughputs in excess of 600 MHz. The methodology can be extended to introduce wave pipelining in other circuits as well

Delay constrained optimal relay placement for planned wireless sensor networks

In this paper, we study the problem of wireless sensor network design by deploying a minimum number of additional relay nodes (to minimize network design cost) at a subset of given potential relay locationsin order to convey the data from already existing sensor nodes (hereafter called source nodes) to a Base Station within a certain specified mean delay bound. We formulate this problem in two different ways, and show that the problem is NP-Hard. For a problem in which the number of existing sensor nodes and potential relay locations is n, we propose an O(n) approximation algorithm of polynomial time complexity. Results show that the algorithm performs efficiently (in over 90% of the tested scenarios, it gave solutions that were either optimal or exceeding optimal just by one relay) in various randomly generated network scenarios.

Optimal allocation of carbon credits to emitting agents in a carbon economy

Reduction of carbon emissions is of paramount importance in the context of global warming. Countries and global companies are now engaged in understanding systematic ways of achieving well defined emission targets. In fact, carbon credits have become significant and strategic instruments of finance for countries and global companies. In this paper, we formulate and suggest a solution to the carbon allocation problem, which involves determining a cost minimizing allocation of carbon credits among different emitting agents. We address this challenge in the context of a global company which is faced with the challenge of determining an allocation of carbon credit caps among its divisions in a cost effective way. The problem is formulated as a reverse auction problem where the company plays the role of a buyer or carbon planning authority and the different divisions within the company are the emitting agents that specify cost curves for carbon credit reductions. Two natural variants of the problem: (a) with unlimited budget and (b) with limited budget are considered. Suitable assumptions are made on the cost curves and in each of the two cases we show that the resulting problem formulation is a knapsack problem that can be solved optimally using a greedy heuristic. The solution of the allocation problem provides critical decision support to global companies engaged seriously in green programs.

Neural network based optimal routing algorithm for communication networks

This paper presents the capability of the neural networks as a computational tool for solving constrained optimization problem, arising in routing algorithms for the present day communication networks. The application of neural networks in the optimum routing problem, in case of packet switched computer networks, where the goal is to minimize the average delays in the communication have been addressed. The effectiveness of neural network is shown by the results of simulation of a neural design to solve the shortest path problem. Simulation model of neural network is shown to be utilized in an optimum routing algorithm known as flow deviation algorithm. It is also shown that the model will enable the routing algorithm to be implemented in real time and also to be adaptive to changes in link costs and network topology. (C) 2002 Elsevier Science Ltd. All rights reserved.

Optimal crop planning and conjunctive use of water resources in a coastal river basin

Due to increasing trend of intensive rice cultivation in a coastal river basin, crop planning and groundwater management are imperative for the sustainable agriculture. For effective management, two models have been developed viz. groundwater balance model and optimum cropping and groundwater management model to determine optimum cropping pattern and groundwater allocation from private and government tubewells according to different soil types (saline and non-saline), type of agriculture (rainfed and irrigated) and seasons (monsoon and winter). A groundwater balance model has been developed considering mass balance approach. The components of the groundwater balance considered are recharge from rainfall, irrigated rice and non-rice fields, base flow from rivers and seepage flow from surface drains. In the second phase, a linear programming optimization model is developed for optimal cropping and groundwater management for maximizing the economic returns. The models developed were applied to a portion of coastal river basin in Orissa State, India and optimal cropping pattern for various scenarios of river flow and groundwater availability was obtained.

Optimal feature extraction for bilingual OCR

Feature extraction in bilingual OCR is handicapped by the increase in the number of classes or characters to be handled. This is evident in the case of Indian languages whose alphabet set is large. It is expected that the complexity of the feature extraction process increases with the number of classes. Though the determination of the best set of features that could be used cannot be ascertained through any quantitative measures, the characteristics of the scripts can help decide on the feature extraction procedure. This paper describes a hierarchical feature extraction scheme for recognition of printed bilingual (Tamil and Roman) text. The scheme divides the combined alphabet set of both the scripts into subsets by the extraction of certain spatial and structural features. Three features viz geometric moments, DCT based features and Wavelet transform based features are extracted from the grouped symbols and a linear transformation is performed on them for the purpose of efficient representation in the feature space. The transformation is obtained by the maximization of certain criterion functions. Three techniques : Principal component analysis, maximization of Fisher's ratio and maximization of divergence measure have been employed to estimate the transformation matrix. It has been observed that the proposed hierarchical scheme allows for easier handling of the alphabets and there is an appreciable rise in the recognition accuracy as a result of the transformations.

Explicit and Optimal Codes for Distributed Storage

In the distributed storage coding problem we consider, data is stored across n nodes in a network, each capable of storing � symbols. It is required that the complete data can be reconstructed by downloading data from any k nodes. There is also the key additional requirement that a failed node be regenerated by connecting to any d nodes and downloading �symbols from each of them. Our goal is to minimize the repair bandwidth d�. In this paper we provide explicit constructions for several parameter sets of interest.

Optimal Power and Noise for Analog and Digital Sections of a Low Power Radio Receiver

We determine the optimal allocation of power between the analog and digital sections of an RF receiver while meeting the BER constraint. Unlike conventional RF receiver designs, we treat the SNR at the output of the analog front end (SNRAD) as a design parameter rather than a specification to arrive at this optimal allocation. We first determine the relationship of the SNRAD to the resolution and operating frequency of the digital section. We then use power models for the analog and digital sections to solve the power minimization problem. As an example, we consider a 802.15.4 compliant low-IF receiver operating at 2.4 GHz in 0.13 μm technology with 1.2 V power supply. We find that the overall receiver power is minimized by having the analog front end provide an SNR of 1.3dB and the ADC and the digital section operate at 1-bit resolution with 18MHz sampling frequency while achieving a power dissipation of 7mW.

Viscoelastic phenomenology based structure assignment for closed-loop vibration control of a beam with sensors and actuators

In this paper we incorporate a novel approach to synthesize a class of closed-loop feedback control, based on the variational structure assignment. Properties of a viscoelastic system are used to design an active feedback controller for an undamped structural system with distributed sensor, actuator and controller. Wave dispersion properties of onedimensional beam system have been studied. Efficiency of the chosen viscoelastic model in enhancing damping and stability properties of one-dimensional viscoelastic bar have been analyzed. The variational structure is projected on a solution space of a closed-loop system involving a weakly damped structure with distributed sensor and actuator with controller. These assign the phenomenology based internal strain rate damping parameter of a viscoelastic system to the usual elastic structure but with active control. In the formulation a model of cantilever beam with non-collocated actuator and sensor has been considered. The formulation leads to the matrix identification problem of two dynamic stiffness matrices. The method has been simplified to obtain control system gains for the free vibration control of a cantilever beam system with collocated actuator-sensor, using quadratic optimal control and pole-placement methods.

Design and Characterization of Stabilized Derivatives of Human CD4D12 and CD4D1

CD4 is present on the surface of T-lymphocytes and is the primary cellular receptor for HIV-1. CD4 consists of a cytoplasmic tail, one transmembrane region, and four extracellular domains, D1-D4. A construct consisting of the first two domains of CD4 (CD4D12) is folded and binds gp120 with similar affinity as soluble 4-domain CD4 (sCD4). However, the first domain alone (CD4D1) was previously shown to be largely unfolded and had 3-fold weaker affinity for gp120 when compared to sCD4 [Sharma, D.; et al. (2005) Biochemistry 44, 16192-16202]. We now report the design and characterization of three single-site mutants of CD4D12 (G6A, L51I, and V86L) and one multisite mutant of CD4D1 (G6A/L511/L5K/F98T). G6A, L51I, and V86L are cavity-filling mutations while L5K and F98T are surface mutations which were introduced to minimize the aggregation of CD4D1 upon removal of the second domain. Two mutations, G6A and V86L in CD4D12 increased the stability and yield of the protein relative to the wild-type protein. The mutant CD4D1 (CD4D1a) with the 4 mutations was folded and more stable compared to the original CD4D1, but both bound gp120 with comparable affinity. In in vitro neutralization assays, both CD4D1a and G6A-CD4D12 were able to neutralize diverse HIV-1 viruses with similar IC(50)s as 4-domain CD4. These stabilized derivatives of human CD4 can be useful starting points for the design of other more complex viral entry inhibitors.