Abstract

With increase in technology scaling, semiconductor devices are becoming increasingly less predictable. The device failure rates increase significantly with decrease in device sizes. Memory unit usually has more hardware components than other circuits and therefore is the most unreliable part. The SRAM memory cell has highest density and is more vulnerable to defects compared to other logic circuits. As the technology scales the process variations also affect the functionality of the memory. There are computer applications where extreme reliability of computing system is essential. Even with advances in manufacturing technology to reduce the faults occurring, the errors in memory are still present. So, methods to increase reliability by providing some internal fault-tolerance are gaining importance in memories. This thesis focuses on developing a memory architecture which enables self test of the memories after manufacturing and avoids the faulty rows by incorporating additional test circuits. The effectiveness of the proposed circuits is checked on a word oriented two port memory. We assume that a single fault in any memory cell within a particular row makes the entire row faulty. During the isolation and replacement, the entire row is isolated and replaced with a healthy row. To carry out the replacement, some spare rows are provided in the memory array. A row can have a single or multiple faulty cells within it; it is replaced by a spare row. The fault model considered in this thesis is the stuck-at-fault i.e., stuck-at-0 and stuck-at-1 faults occurring in the SRAM cell. The stuck-at-faults present in the SRAM cell alone are considered in this thesis for testing, isolation and replacement process. The idea has been demonstrated through the simulation for a word oriented two port memory architecture and additional circuits were designed which incorporate all the above discussed facilities. In a word oriented memory the entire row is written or read at a time in a clock cycle. In the two port memories, the read and write ports are completely independent and hence the read and write operations can be performed simultaneously though simultaneous reading and writing of same row cannot be performed. The architecture proposed in this thesis consists of word oriented two port SRAM memory cells consisting of 4 words, and each word consists of 4bits. The memory further has additional circuits for fault detection, fault isolation and replacement of faulty rows. During testing it is assumed that a Built-in Self Test (BIST) controller is present which includes circuits to generate the signals necessary to start and end the test mode in the memory; a Test Pattern Generator (TPG) to generate the necessary test addresses and test input vectors necessary to carry out the testing during the test mode. The BIST controller signals the start of testing process at every power-on of the memory. First the testing is carried which provides the input vectors which sensitize the fault present in the memory and allows to identify them. A compare circuit is used to identify the faulty row(s) in the memory. The signal generated from the compare circuit is used by the isolation circuit to isolate the faulty row from the SRAM array. The same signal generated from the compare circuit is used by the replacement circuit to redirect the signals corresponding to the faulty row to the healthy row. Additional spare rows are provided in the memory architecture which are used during the replacement process. The self healing structure proposed in this thesis enables one to have reliable memory after the testing and replacement process. It helps in improving the memory yield which directly translates into chip yield and chip reliability. The circuits that are proposed and tested through simulation are designed with the same technology as the SRAM memory is designed. Hence it is possible to integrate them with the SRAM memory. The architecture is designed at circuit level and the simulations are carried using HSPICE. The circuit is designed at 65nm technology node and the 65nm Predictive Technology Model (PTM) is used as the model for simulation. Thus the thesis proposes a self healing architecture through BIST and additional circuits proposed for memories which may result in considerable improvement in yield of memories manufactured in the latest technology nodes.

Abstract

The importance of environment modelling as a prerequisite for the navigation of mobile robots can- not be understated. It is essential for a mobile robot to have the ability to autonomously build a model of the environment, as human intervention is not practical in all circumstances. The unavailability of environment modelling algorithms until recently, has hampered the feasibility of the envisaged vision of mobile robotics. A robot has to address both the mapping and the localization problems in order to au- tonomously solve the map learning problem. Due to the coupling between these two tasks, autonomous map learning has been a challenging problem. This thesis is primarily focused on the implementation of an environment modelling technique based on the Extended Kalman Filter(EKF). The mapping and localization problem, called Simultaneous Localization And Mapping(SLAM) is defined as the process of concurrently building a map of the environment while using this map to obtain improved estimates of the robot location. The SLAM algorithm begins with the mobile robot in an unknown location, with no a priori knowledge of the map. The robot then uses a sensor to model the visible environment and simul- taneously computes an estimate of its own position. Continuing in motion, the mobile robot eventually builds a model of the environment which is useful for navigation. In spite of the ample literature available on SLAM, there is hardly any literature on the development of a real SLAM system. A majority of the work in this thesis is attributed to filling the gap between theory and implementation by the identification and diagnosis of the issues faced during implementation. The work in this thesis can be divided into two sections: contributions in the implementation front and those in the theoretical front. The implementation part deals with the system specific customization of the algorithm, a novel calibration method for the sensor with respect to the robot, extraction and parametrization of features, provision for manual exploration during map building among other issues. This part of the thesis concludes with successful demonstrations of robust EKF-SLAM implementation on the Pioneer P3-Dx mobile robot using a SICK LMS200 range scanning sensor. The theoretical work in this thesis deals with better map building by novel parametrizations of features to keep error estimates low, representative features for better association and trajectory estimation from the online SLAM problem.

Abstract

The present work attempts to build an automatic translation system of nominal compound (NC) from English to Hindi. A noun compound is a sequence of nouns acting as a single noun, e.g., colon cancer, suppressor protein, colon cancer tumor suppressor protein. They comprise 3.9% and 2.6% of all tokens in the Reuters corpus and the British National Corpus (BNC), respectively. As of today, no good system exists for the translation of multi-word expressions from English to any Indian languages. We have evaluated two state-of-the-art systems, Moses and Google Translation system, to check the Noun Compound translation accuracy from English to Hindi. Google translation system results in an accuracy of 57% while Moses, a statistical machine translation system, returns an accuracy of 48% on a test data of 300 Noun Compounds. The above figures indicate that automatic NC translation from English to Hindi is an important subtask of machine translation system. We build a Noun Compound Translation system (NCT) which returns an accuracy of 64% on the same set of test data. This thesis examines two approaches for translation of Noun Compounds from English to Hindi. We have done a manual study on 50K parallel sentences from English to Hindi and have found out that Noun Compounds in English are translated into Noun Compound in Hindi in over 40% of the cases. In other cases they are translated into varied syntactic constructs. Among them the most frequent construction type is “Modifier + Post-Position + Head” which occurs in 35% of all the cases. Some examples are “cow milk” ! “gAya kA dUXa”, “wax work” ! “mOMa para ciwroM”. This observation motivates both the approaches for translation in the present thesis. The approaches are called in this work as: a) Translation of NC by paraphrasing on source side and mapping the paraphrase to target construct and b) Context based translation by searching and ranking translation candidate on target side. In the first approach English nominal compounds are automatically paraphrased and the paraphrases are translated into Hindi constructions. The paraphrasing is done with prepositions following [Lauer 1995] approach of paraphrasing of nominal compound. For example, “cow milk” is paraphrased as ‘milk from cow’, “blood sugar” is paraphrased as ‘sugar in blood’. Since English prepositions have one-to-one mapping to post-position in Hindi, English paraphrases are easily translated into Hindi using the mapping schema. Assuming that lexical substitution for component nouns of the compound is correct, this method examines how paraphrasing of English nominal compound acts as an aid for translation. In the second approach, we, at first, generate translation templates for the target language. These templates are all possible Hindi construction types that English nominal compounds can be translated into. Context based translation system take context into consideration while translating. We translate noun compound by taking the sentence in which the compound occurs as the context. For example, the expression “finance minister” is the nominal compound to be translated in the sentence “The finance minister declared the financial budget for this year”. Other content words in the sentence such as ‘declared’, ‘financial’, ‘budget’, ‘year’ form the context. We apply a Word-sense-disambiguation tool for selecting the correct sense of the component nouns of NC in the given context. We use a bilingual dictionary to get the Hindi translation of the component nouns in the sense selected by WSD tool. Thus context based lexical substitution is accomplished for the target language. The output of lexical substitution is placed in the translation templates and the resulted construction is searched on a Hindi indexed corpus of 28 million words. For ranking, a reference ranking based on the frequency of occurrence of the translate candidates in full in the TL corpora is taken as baseline. To improve on the baseline, a stronger ranking measure is borrowed from [Tanaka & Baldwin 2003b]. The context based translation system approach is adopted in the present work for building the noun compound translation system (NCT) which is integrated to Moses. The outputs of Moses and Moses integrated with NCT are compared. Evaluation of the system is carried out at two levels: by automatic evaluation metric BLEU and by manual evaluation technique. The issue of automatic evaluation is discussed in detail which motivates manual evaluation under the given circumstance.

Abstract

Byzantine Agreement (BA) and reliable Point-to-point communication are two of the most important and well-studied problems in distributed computing. Informally, the challenge of BA is to maintain a coherent view of the world among non-faulty players interacting over a network with few players (possibly with malicious intent) trying to disrupt the entire process. In a synchronous network over n nodes of which up to any t are corrupted by a Byzantine adversary, BA is possible only if all pair point-to-point reliable communication is possible [Dol82, DDWY93]. Specically, in the standard unauthenticated model, (2t + 1)- connectivity is necessary whereas in the authenticated setting (t+1)-connectivity is required. Thus, a folklore is that maintaining global consistency is at least as hard as the problem of all pair point-to-point communication. Equivalently, it is widely believed that protocols for BA over incomplete graphs exist only if it is possible to simulate an overlay-ed complete graph. Surprisingly, we show that the folklore is far from true | achieving global consistency can be strictly easier than all-pair point-to-point communication. In the authenticated model, it is assumed that the adversary can forge the signatures of only those nodes under its control. In contrast, the unauthenticated model assumes that the adversary can forge the signatures of all the nodes (that is, secure signatures are not used). We initiate a study on the entire gamut of BA's in between, viz., the adversary can forge the signatures of up to any k nodes apart from the up to t nodes that it can actively corrupt. We completely characterize the possibility of BA across the spectrum. Thus, our work attempts to unify the extant literature on agreement. It is, however, more than a mere attempt towards unication as it provides insights into the eld. Specically, apart from the extremes (of k = 0 and k = n

Abstract

Autonomous driving is a long-standing problem in robotics, interest in which has spiked in recent years due to the series of DARPA Grand Challenges. One of the basic components in the operation of such autonomous vehicles is the capability to autonomously navigate in terrains particularly in ex- ploratory applications, the robots must deal with terrains whose models at best are only partially-known. On-road navigation is a crucial component of autonomous navigation outdoors and presents interesting challenges, the prominent among those being the ability to discern the traversability of a terrain patch. Modified cars became the new platform in robotics for outdoor navigation which has the possibility to travel longer distances, carry more sensors and thus being more suitable for mapping larger areas. This offers the opportunity to address robotic tasks on a larger scale but on the other hand requires efficient solutions to common problems like mapping or localization. The objective of the work is to develop. simulate and test a terrain modelling system based on laser range data for slow moving vehicles. The terrain modelling system will enable the unmanned ground vehicle to identify the next best way-point to reach. More formally, given a laser range finder fitted on a vehicle moving largely on flat terrain and a pose measurement system that is accurate enough up to a bounded error, develop a terrain modelling system based on laser range data for the vehicle. Robot must possess that enable it to perceive the outside world. We have used three sensors namely GPS, IMU and LIDAR for estimating pose of the vehicle, its orientation and the range measurements respectively. All these devices are mounted on top of a vehicle to acquire data from the sensors. After processing and applying transformations over the data, we will get the map representation in the form of point cloud. Two algorithms for terrain classification for a single tilted laser are developed and extensively tested. One algorithm is plane extraction which will represent the local terrain of the vehicle in terms of planes and points to discern the traversable region. Efficient detection and plane parametrization from scan-line data obtained incrementally to discern the navigable and non-navigable regions confirms the efficacy of the proposed method. However, plane detection is less convincing when dealing with certain structures that arise in natural environments like poles etc. Another algorithm is Spatio-temporal classification which is not too constrained by the nature of the structure of the environment. The essential assumption is that corresponding laser readings in two successive scans are correlated and in general see neighbouring areas. An obstacle or non-navigable region is detected when the sequence indicates decreasing laser distances with corresponding increase in height.This method needs extra rules like searching neighbourhood, relative thresholding to classify obstacles that are not in the frontal viewing cone of the laser. The map obtained is too sparse as we have used a single LIDAR. So, the techniques we have used were not able to overcome few sensor noises. Also, AHRS was giving angle errors while the vehicle pitches and rolls over bumps. This work has lot of future scope by deploying state of the art sensors and multiple laser scanners.

Abstract

In web search, understanding the intent behind a user query can help in tasks such as placing of ads relevant to the query, routing the query to an appropriate vertical search to enrich web search results and building a user profile for personalization. Such an intent could be represented by categories of the information a user is looking for, often expressed through a short query. Here, we consider the categorical representation of the intent. That is, the intent behind the query is represented as a set of pre-defined categories. In this work, we address query categorization, which involves classifying a given query into one or more pre-defined categories. Such a categorization gives web search engines a means of quantizing the user’s information need as expressed through a query. As an example, consider the query “serena williams”. This query belongs to “sports” category, or more specifically “sports/tennis”. Such an understanding of the query can have many applications as far as web search engines are concerned. First, knowing the categories of a query can help in determining the sources of evidence for vertical selection by web search engines. Advertisements relevant to the user query can be placed on the search results page, thus enriching the users search experience. Other areas which can benefit from query categorization include personalization—for building user profiles to personalize the search results, analysis of user behavior over time, among many others. We propose an information retrieval based approach similar to document retrieval to solve query categorization. To carry out categorization, we first represent a category by a set of web documents (from Open Directory Project) that best describes the semantics of the category. This results in a corpus where each document is categorized. For a given query, we do a simple “idf” based query expansion and we retrieve and rank the categories just as in document retrieval, effectively resulting in query categorization. These categories may have to be mapped to the categories of the application under consideration. Unlike previous works, the simplicity and the unsupervised nature of this proposed approach makes it practical in a web search scenario, while achieving performance comparable with other systems, when evaluated on KDD Cup 2005 data set. Further, we investigate if we can learn the category rankings for the queries by applying “learning to rank” techniques. We show improvements on two datasets: a popular search engine’s dataset of 7K classified queries and publicly available KDD Cup dataset. Our experiments suggest that learning to rank could be a key in improving precision of query categorization systems for applications such as federated search where precision is important.

Abstract

The main goal of data visualization is to communicate information clearly and effectively through images. Data visualization can help user to: understand the output better, compare alternative results, and evaluate the results. Importance of data visualization, in the process of knowledge discovery, is accepted and acknowledged. Heidi is a high dimensional data visualization system that captures and visualizes the closeness of points across various subspaces of the dimensions; thus, helping the users to understand the distribution of data in different subspaces. Heidi has certain issues: (i) can not handle large data sets, (ii) Heidi images use too many colors, and (iii) restricted to displaying clustering results. In this thesis, we propose techniques to address the issues: (i) scaling up Heidi visualization for large number of dimensions and large number of points, (ii) Heidi images use too many colors, which are reduced by highlighting only prominent colors, and (iii) customizing Heidi to display other hierarchical multi dimensional structure like R-Tree index structures and subspace clusters. Heidi is enhanced in terms of memory and efficiency through an implementation over the MapReduce framework. Through our empirical study, we demonstrate that Heidi++ (our new system) achieves virtually linear speedup. For very large data sets, a new representative Heidi visualization is proposed which is more scalable and efficient. High dimensional index structures are used to efficiently answer range queries in large databases. Visualization of such index structures helps in: (i) visualization of the data set in a structured format of the index structure, (ii) “explorative querying” on the data set, (iii) index structure diagnostics: visualizing the structure along with its performance statistics enables the user to determine values of parameters for index structure for better performance. Heidi++ could be extended for various other applications of presenting interesting visualizations about multi-dimensional index structures. In this thesis, we demonstrate the use of Heidi++ Visualization over the R-Tree and R*-Tree.

Abstract

Designing Radio Frequency Identification (RFID) tag antenna for metallic objects is a challenging task. The reason is that the antenna parameters like gain and radiation pattern are highly affected by metallic surface. This thesis presents two different designs of miniature RFID tag antenna for metallic objects. They can be used for different tag Integrated Circuits (ICs) having different input impedances simply by varying slot length and keeping other dimensions intact. The proposed antennas are designed specifically to eliminate interference effect caused due to metallic objects. By eliminating this limitation the tag proves to be a uniquely good solution that enables the use of UHF RFID efficiently for metallic applications like aerospace or automobile industry. In this thesis firstly a slotted RFID tag antenna is designed whose size is 33 mm x 16 mm x 3.2 mm, and secondly a modified slotted RFID tag antenna is designed whose size is 64 mm x 24 mm x 1.6 mm. The proposed slotted RFID tag antenna design contains three metallic layers. Top layer consists of two metallic rectangular patches which are electrically connected to the ground plane through copper vias. Multiple slots are created on metallic patches and a non-connected metallic plate is placed between the ground and the patches. The antenna design is simulated, fabricated and its performance is analyzed in an Anechonic Chamber. The read range of the proposed slotted RFID tag antenna for a slot length of 7 mm, mounted on the metallic surface is approximately 80 cm when. Next we presented a modified slotted RFID tag antenna with lower antenna thickness. This design contains two metallic layers. Top layer consists of two coplanar metallic patches with two slots on each patches and bottom layer is a ground layer. In this design copper vias are placed at extreme end corners of the patches. Experimental results show that the same antenna can be used for metallic as well as for non-metallic cases because the read range of the proposed design is 1.7 m when the tag is mounted on a metallic sheet and 1.1 m without any metal sheet. In this work we also proposed a mathematical model for slotted as well as for non-slotted RFID tag antenna to enhance the computation speed of antenna design. RLC circuit model proposed in this thesis can be used to develop slotted as well as for unslotted RFID tag antenna for various frequencies and for different tag ICs having different input impedances. This work is expected to contribute to improvement in antenna design automation.

Abstract

Pounding between adjacent structures is commonly observed phenomenon during major earthquakes which may cause both architectural and structural damages. To satisfy the functional requirements, the adjacent buildings are constructed with equal and unequal heights, which may cause great damage to structures during earthquakes. To mitigate the amount of damage from pounding, the most simplest and effective way is to provide minimum separation distance. Generally most of the existing buildings in seismically moderate regions are built without codal provisions. Past earthquakes have shown an evidence that the buildings are more vulnerable to pounding. Building codes provide a set of guidelines for the practice of structural engineering and play an important role of transferring technology from research to practice. In numerical modeling, different combination of structures are considered for doing the analysis using Applied Element Method (AEM). The separation distance between the structures is provided according to various codes from different countries and are subjected to ten different ground motions. Some codal provisions failed to satisfy the requirements. The shortcomings in codal provisions are identified and provided with proper suggestions to them

Abstract

We consider a distributed setting where a subset of nodes are under the control of a malicious ad- versary with unbounded computational powers. The problem of simulating a directed reliable channel from a sender S to a receiver R in the absence of a true physical point to point channel is fundamental to the area of Distributed Computing and is popularly known as ”Unconditionally Reliable Message Transmission” (URMT). Analogous to randomized sequential algorithms, we distinguish between two variants of reliability: while the weaker variant allows R to output an incorrect message with small probability (Monte Carlo), the stronger variant allows the protocol to only abort with a small probability but never output an incor- rect message (Las Vegas). We consider these variants in two popular timing models: synchronous and asynchronous. The former has a fixed upper bound on the amount of time it takes to transmit a message over any physical channel of the network whereas the latter doesn’t have any such upper bound. We focus on the possibility of Las Vegas and Monte Carlo protocols by modeling the network as a synchronous or asynchronous directed graph. Unlike the approach taken in literature where a digraph is abstracted as a collection of disjoint wires and the nodes along the wires are mere routers, we consider digraphs in their entirety – every node can potentially do arbitrary computations on the messages i.e. every node is as powerful as a Turing Machine. In this work, we establish a novel hierarchy with respect to the minimum connectivity requirements for the existence of synchronous Las Vegas, asynchronous Monte Carlo and asynchronous Las Vegas protocols for URMT. We show that, with respect to URMT, the (minimum) connectivity requirements for the existence of synchronous Las Vegas protocols are the same as those for asynchronous Monte Carlo protocols i.e. one is possible if and only the other is possible – a pleasantly surprising equivalence between two very different models. Furthermore, the connectivity requirements for asynchronous Las Vegas URMT (which are strictly higher than those for Monte Carlo URMT) are the same as those required for perfect protocols over synchronous networks! While it is well-known that, in synchronous networks, the minimum connectivity requirements for Monte Carlo URMT protocols to exist is strictly less than those where for perfect protocols, we establish the fact that the connectivity requirements for the case of Las Vegas URMT are strictly more than that of Monte Carlo URMT. We further improve our insight (into URMT) by studying how sparse a digraph that permits URMT can be. Specifically, we say that an edge is critical if its removal renders the graph insufficiently con- nected for URMT protocols (though before its removal the connectivity was sufficient). Ironically, it turns out that for digraphs over n nodes, the number of critical edges is always O(n) for perfect pro- tocols whereas for the “easier” randomized protocols (the ones demanding lesser connectivity require- ments compared to the perfect ones), we give a family of digraphs with Ω(n2) critical edges! Hence, establishing an interesting interplay, for the case of URMT.