Abstract

In a distributed network, where some of the nodes may be corrupt, a sender node s intends to com- municate securely with a distant receiver node r. If the network has sufficient connectivity, a protocol can be designed which enables this communication irrespective of the behaviour of corrupt nodes. In this thesis we consider two very different kinds of networks: synchronous neighbour networks and asynchronous unicast networks. We consider the case where some of the nodes in these networks, whose identities are not known a priori, can behave arbitrarily (or, even maliciously). We investigate the minimum connectivity required to facilitate the design of a protocol which enables a node to com- municate reliably with another node in a network of the former type, and to communicate reliably and privately in a network of the latter type.

Abstract

Synthesis of complex consonant clusters is a challenge in TTS systems, as it is dicult to ensure proper coarticulation. This problem surfaces in the synthesis of missing units in unit concatenation systems. Back-o techniques are used to synthesize these missing units. The current back-o techniques, which use smaller sub-word units to synthesize the missing unit, are found unsuitable for frequent usage causing severe degradation in synthesis quality. However missing units are a frequent occurrence when synthesizing unrestricted text. Hence to build open domain TTS systems, ecient back-o techniques are necessary. This problem is further aggravated when working with under-resourced languages as they lack the manually annotated speech corpora which enable the development of these high quality synthesis techniques. In this thesis we propose a two pronged strategy to improve the quality of back-o techniques. The two pronged strategy consists of rening the boundaries of units in the acoustic inventory to reduce phone insertion errors during back-o and use of a novel back-o technique to ensure coarticulation consistency. A boundary renement algorithm which removes necessity for manually labelled data by relying on a knowledge base of cost functions derived from landmark specic acoustic cues was proposed, to increase the quality of unit boundaries. However increase in accuracy of unit boundaries was insucient when context-dependent units are not available in the database. Hence a back-o technique which synthesizes complex consonant clusters even when the required context-dependent units are not available, was proposed. This technique is motivated from a phenomenon observed during second language acquisition and emulates native speaker intuition in synthesis of these clusters. The technique was proven to be better than the conventional backo  techniques. Further it was proven to be robust to segmentation errors, reducing the reliance on high quality segmentation techniques which require manually labelled data.

Abstract

As the electronics activity is penetrating into various walks of life like electronic governance, banking, reservation systems, the need for higher and higher security in protecting the banking transactions, passwords, PNR numbers, etc. is increasing. The security lapses not only occur through software but also from the hardware circuits that are used for implementing them. One of the methods of breaking the security is through the observations of the pattern of power consumed by the gadget. These methods through which the secured information is obtained are known as Side Channel Attacks (SCA). There is considerable amount of effort that is put in to make the electronic circuits immune to SCA. In this process, bulk of the effort is put in making complementary metal oxide semiconductor (CMOS) circuits immune from these attacks. One of the normal approaches is by having a gate operated with the complementary gate in parallel, like an inverter working in parallel with a buffer, a NAND working in parallel with AND. This combination of circuits may be termed as dual-rail pre-charge (DRP) logic. Because of the additional circuits, the power consumed by the circuit in general gets doubled. So they may not be really suitable for low power applications where the battery life is also important. In view of this, the problem of reducing the power dissipation in DRP logic has been looked at. It has been realized that adiabatic approach is a reasonable method for reducing the power dissipation. In view of this, adiabatic dual-rail inverter-buffer circuit has been built with circuit topology as shown in Figure 4.3. It has been found that this circuit works properly as an inverter, as a buffer and also results in considerable reduction in power dissipation. The current drawn from the power supply has a pattern which is independent of the input signal (0 to 1 or 1 to 0 transitions). Further it has been observed that the input and output logic levels are the same which indicates that these circuits are cascadable. In view of this, it has been concluded that it is possible to realize low power secure circuits based on adiabatic dual-rail approach. To examine whether large scale secure systems can be built with this approach, the universal logic gates, NAND and NOR have been constructed on the lines similar to CMOS NAND, NOR with adiabatic approach. In these circuits there have been certain current patterns that emerged depending on the input signal. This difference in the pattern has been identified to be due to the number of transistors which are in the ON state are different for different input signals. This problem has been overcomed by carefully analyzing the transistors that are put ON for each of the input condition and by balancing the resistances for all the inputs. This called for incorporating additional transistors in some branches. With this balancing technique and adiabatic approach, it has been possible to realize low power secure NAND and NOR gates. Even these gates have the same input and output logic levels which make them suitable for cascadable circuits. Thus it is clearly established that using the dual-rail adiabatic approach, secure digital circuits can be built. Even though cascadability of the individual secure logic gates have been established, when the circuits are really cascaded, it is possible that the currents drawn may depend upon the logic functions that are executed (based on the gates that are used). To avoid this problem, the circuits have been modified to have a structure in which there is always a current drawn by each of the gates for each operation of the signal. This is done by incorporating pre-charge and evaluation steps in these circuits. Using this approach, all the gates (Inverter-Buffer, AND-NAND, OR-NOR, XOR-XNOR) are constructed and it is observed that the current patterns are input independent and a significant amount of power reduction is observed when compared to the existing secure logic styles. Hence, low power secure logic style has been established.

Abstract

A roof with an ability to reflect and emit the sun‘s heat back to the sky instead of transferring it to the buildings is said to be a cool roof. It has high solar reflectance and thermal emittance values. Cool roofs are one of the important energy conservation measures in buildings in countries like India. This thesis presents an assessment of the energy savings potential of cool roof through the analysis of experimental results, and through simulations. Further, a tool has been developed to calculate energy savings, payback and thermal comfort due to cool roof. The work also includes a survey of cool roof in historical and present day context of India, and a field study of performance of various cool roof materials. A survey of various cool roof technologies available across India was done. The study shows the importance of cool roof in historical architecture of India, the current trends, and its relevance in codes and rating systems. Further, several cool roof materials were installed on field, and were tested for performance over a year. From this, it has been observed that ceramic tiles though provide lesser savings compared to the white elastomeric coatings; they tend to have longer life providing a good payback over time. The work includes analysis of the raw data of a parallel experiment conducted in two typical buildings in Hyderabad by IIIT Hyderabad in collaboration with LBNL- USA. The collected data has been analysed based on the operating hours of the building, and the calculated average savings ranged between 0.066-0.072 kWh/m2/day. The work also includes the development of an online cool roof calculator. This cool roof calculator provides the energy savings, payback and thermal comfort achieved due to cool roof for the user specified building parameters and for the specified city. The calculator can be accessed at: http://coolroof.cbs.iiit.ac.in/index.html . This is the first of its kind tool, which performs online simulation using EnergyPlus for all available Indian weather files. Lastly, cool roof was analysed in combination with roof insulation. The impact of cool roof on requirement of roof insulation in office buildings was understood through simulations. Results showed that the savings achieved by increasing the thickness of insulation, has diminishing returns, and the insulation has negligible effect on cooling electrical energy consumption in case of roof with high solar reflectivity. Especially, roofs with very high solar reflectivity values of 0.7 and 0.8, adding roof insulation might increase the cooling energy consumption. This study also suggests that the recommendation by the Energy Conservation Building Code of India for the prescriptive method is to be revisited.

Abstract

There has been a continuous pressure on VLSI chip manufacturing industry to increase the manufacturing yield. Integrated circuit manufacturers are constantly trying to decrease the number of faulty parts they produce. The reliability of System on Chips must be ensured to a certain extent since a single fault is likely to make the whole chip useless. VLSI testing is the backbone of manufacturing reliable integrated circuits. Therefore, fault diagnosis and fault repairing techniques are gaining importance these days. A manufacturer may be able to improve the circuit design or the manufacturing process by analyzing the parts that fail production tests and determining the cause of failure for each part. During the design as well as manufacturing several faults may creep in. Therefore there is a need to test the VLSI chips at the design level as well as after manufacturing. Detection of fault and the type of fault present in a circuit is known as fault diagnosis. With increase in the complexity of the integrated circuits the effort to detect and diagnose the fault is becoming time consuming and demanding more and more resources. There has been continuous effort to develop methods of testing ICs, more efficiently and with less effort. This activity encompasses: 1) Development of methodologies for testing 2) Model the faults 3) Evaluate the effect of the fault on the performance and 4) Diagnosing the fault from the change in performance. With the growth of IC technology and with the advent of reconfigurable circuits like FPGAs, PLAs, PLDs etc. testing only for faulty chip is not adequate. Fault location may be required to identify and then replace or discard the faulty sub-circuit. It can also be used to analyze the defect causing the faulty behavior. Fault diagnosis is executed upon manufactured chips, which are found to be faulty in order to identify the position and types of the faults present in them. This thesis is devoted to new methods of identifying (locating) faults in a conventional IC as well as in programmable ICs like FPGAs. An exhaustive test pattern set for a modern VLSI circuit could result into a hundred million or more vectors. The amount of time that each circuit requires for testing is also an important factor in determining the overall test cost. In order to reduce the test application cost it is important to keep the number of test patterns to a minimum. In this thesis the trade-off between fault coverage and the number of test vectors is studied. A faster algorithm named POTG (Position Oriented Test Generation) algorithm has also been proposed to get the minimum number of test vectors which covers high fault coverage for testing of ASIC designs. There are two types of fault diagnosis which differ in the way they are pre-computed. i) Dictionary based approach which uses a pre-computed dictionary that contains information about the faults and the test vectors. ii) Dynamic or fault simulation based approach which generally does not use any pre-computed information. In this thesis we have used dictionary based approach for fault diagnosis. CONE partitioning technique is used for generation of test vectors in bigger circuits (whose input vector is greater than 22 bits). A modified fault dictionary is prepared that is used to minimize the effort in fault location. For location of a fault a new fault dictionary is proposed in which fault vs test vectors is stored and each test vector is assigned weightage (the number of faults it can detect). The proposed POTG algorithm has two parts: first, generation of optimized fault dictionary, and then usage of this fault dictionary. POTG algorithm essentially finds the intersection of the faults and finally arrives at the minimum number of vector that is needed for locating a particular fault. This modified dictionary also gives a heuristic approach to minimize the number of test vectors required for testing the chip with some trade-off with fault coverage. This proposed algorithm is faster in locating a fault in a chip compared to other classical fault location technique. The effectiveness of this POTG algorithm is checked by applying it to ISCAS’85 Benchmark circuits c432, c499, c880, c1355. There is an increase similar to logarithmic increase in the probability of fault location with the increase in test vectors used. Thus a small drop in fault coverage may results in huge reduction in number of test vectors. For example for circuit c432, 96% of the faults can be located with only 56 test vectors, otherwise for 100% fault coverage we have to apply 240 test vectors. This algorithm takes O (|F| * log2|T|) which is faster in locating a fault compared to those which uses classical fault dictionary which takes O (|F|*|T|*log2|F|) time. Thus the POTG algorithm which is developed enables location of the faults effectively with considerably less effort. Testing an FPGA chip poses a challenging problem for test engineers. A modified BIS

Abstract

Visual representations are ubiquitous in modern day science textbooks and have become an object of much research in recent years. Since textbooks are a primary source of content information in most science classrooms it is therefore particularly important to understand how students integrate words and figures in textbook style learning materials. The quality and utility of visual representations has been subject to much debate. In order to improve design of the instructional material visual representations which make up one third to one half of every page in a science textbook need to be studied in greater depth so that the these visual representations are productive to the learning of scientific ideas.
The research in this dissertation is centered on three parameters of visual representations. The text that is present within visual representation, and how color plays a vital role in information recall. The second parameter studied is the various categories of the visual representations and their effect on different types of learning outcomes. This study focuses on what type of visual representation should accompany the text so that it provides the best support for the learning of scientific ideas. The third study focuses on the placement of the visual representation with respect to the corresponding text. Studying the text –illustration proximity to find out if learning outcome is effected by the placement of the visual representation helps provide insight about learning behaviors and leads to an improved design of instructional material. The results from the three empirical studies help provide useful recommendations to instructional material designers. Modest modifications in the ways that visual representations are presented in textbooks could greatly improve students’ comprehension.

Abstract

Severe Acute Respiratory Syndrome is a respiratory illness that affected more than 8000 patients and caused around 774 deaths in 26 countries, within its first year of emergence. This disease has an average mortality rate of 10% and is caused by an enveloped, single-stranded positive sense RNA (Ribose Nucleic Acid) Corona-virus (Co-V) known as Severe Acute Respiratory Syndrome Corona-virus (SARS-CoV) that has the capacity for human-to-human transmission. In April 2003, the genome of this virus was completely sequenced. The 29.7 kb long genome reveals that the SARS-CoV bears no resemblance to any existing corona-virus, and contains 14 putative open reading frames (ORFs) out of which 6 major ORFs encode the two replicase poly-proteins and four structural proteins; the spike glycoprotein, envelope protein, membrane protein and helical nucleocapsid protein, and the remaining 8 ORFs for unknown proteins. Though the lifecycle of the SARS-CoV is believed to follow that of other corona-virus i.e., release of genetic material into the cytoplasm of the host cell where it directs the production of new virus genetic material and virus proteins, the exact steps and details of the proteins involved are largely unknown. Identification and characterization of new functional proteins from the ORFs will be helpful for understanding the pathogenesis of SARS-CoV. Up till now there are no effective drugs or vaccines against SARS-CoV. The identification of new viral proteins and the understanding of their functions will provide potential targets for design of drugs or vaccines against SARS. The detection of the 3a gene product in SARS-CoV infected cells and in the lungs of SARS patients confirms that the ORF 3a of the SARS-CoV encodes an accessory protein consisting of 274 a.a. that lacks any significant similarities to any known protein. Though the putative full length sequence of 3a protein lacks sequence homology to any other known proteins, topology prediction of 3a proteins based on amino acid (a.a.) sequences suggests that 3a is a type-III transmembrane protein with multi trans-membrane domains. The interaction of the 3a protein with the spike protein suggests that one of the intracellular roles of 3a is to mediate intracellular trafficking of the spike protein in SARS-CoV infected cells. Although the biological role of the 3a protein remains unclear, it is known that 3a also interacts with the membrane protein, envelope protein and genes that are involved in multiple cellular processes. This suggests that the 3a protein functions as both a viral regulatory protein and as a structural protein in infected cells and mature viral particles respectively. Though a contemporary work showed that 3a is a trans-membrane protein that is capable of forming an ion-channel, the exact structure or the process of homo-merization is unknown. The functions of ion-channels vary among one another and a deeper understanding of the ion-channel activity of 3a proteins will help in elucidating its role in viral lifespan and pathogenesis. Further studies on modulation of virus release mediated by 3a protein will provide new prospects to the understanding of the pathogenesis of the SARS-CoV (and other corona-viruses) as well as can serve as a potential target for therapeutic developments. Protein modelling studies have been carried out on the 3a protein. Three-dimensional structures were modelled from the primary sequence of the 3a protein and then evaluated based on non-bonded interactions, RMSD calculations and solvent accessible surface area computations. These studies help in understanding the possible structure of 3a and its ability to function as an ion-channel. The reliability of the structures was also evaluated using graph spectral analysis (Generally mutation studies are conducted on individual amino acids to identify the critical residues that significantly contribute to the structure and thus function of the protein). Centrality measures of a vertex (i.e. amino acid residue) helps in determining the relative importance of a vertex within the graph (protein structure). Degree centrality, betweenness, eigenvector centrality and graph density were calculated for the proposed models to understand their compactness and to identify the critical residues within a model and common to all models. These critical residues can serve as sites for drug targeting.

Abstract

Present day computing systems deal with calculations involving large range of numbers. One of the ways by which such a wide number range can be provided is through the use of floating point format for number representation. Among the floating point operations, floating point multiplication has been a very power hungry operation, having the maximum share in the power consumption in most of the applications. With the advent of mobile devices which have a fixed power budget, there is a need for investigation of low power designs for a floating point multiplier to trim down the power consumption of the whole system. The work presented in this thesis aims at exploring techniques which can be used to reduce the power consumed in a single precision floating point multiplier. We apply a combination of truncation and voltage scaling in the mantissa multiplier to achieve power savings and implement redundancy in the exponent calculation to attain error resilience. With the scaling of technology and the supply voltage of CMOS transistors, it has been predicted that noise will affect the correct functioning of circuits in the future technology nodes. This will lead to computations which may not be deterministic but probabilistic. In such a scenario, the technique of voltage scaling will lead to increased errors due to further reduction of the noise margin. One of the methods by which the effect of the reduced noise margin can be modeled is through introduction of random or Gaussian noise along with the signals. This noise introduction results in erroneous calculation which is referred to as probabilistic computation in this thesis. Each of the low power techniques used (truncation and voltage scaling) lead to power savings at the cost of errors in the computations. Hence, we apply these low power techniques in the mantissa calculation of the floating point multiplier because it is less significant as compared to the other calculations (exponent and sign) and is also the most power consuming calculation of the floating point multiplier. This is done to achieve maximum power savings at the cost of introducing some errors as far as the multiplication result is concerned. We also make the exponent calculations less error prone by implementing redundancy in the exponent block. This leads to substantial error reduction with very nominal increase in power, thereby keeping the overall error in the results low. By the low power techniques and redundancy we realize a multiplier design with error tolerance and considerable power savings. It is then demonstrated that sizeable amount of power savings can be achieved in a Ray Tracing application by replacing a subset of the deterministic multiplications by probabilistic multiplications. This was achieved at the cost of negligible degradation in the quality of the output image generated.

Abstract

Computational Geometry has grown into an independent field in the last two decades. It deals with design and rigorous analysis of sophisticated algorithms for problems which involve geoemtric objects. Apart from trying to come up with efficient algorithms and data structures, a lot of focus is on mathematical analysis for proving the efficiency of the solutions. Computational Geometry problems find a lot of applications in the field of VLSI, Geographic Information Systems (GIS), graphics and databases. In a class of problems named ‘geometric intersection searching problems’ (GISP) orthgonal range searching, halfspace range searching, orthogoanl point enclosure have been some of the most widely studied problems. The inherent beauty in these problems and their applications in various domains have motivated researchers to explore these problems. GISP can be simply stated as follows: Let S be a set of objects in IRd (d-dimensional space). Given a query region q, report or count the number of objects in S q. The objective is to come up with data structures which uses minimal space (ideally linear space) and query algorithms which answer queries fast ! In many applications (which shall be discussed later), it is not sufficient to merely report or count the objects of S intersecting with the query range q. Some form of aggregation (or summarization in some cases) needs to be done on the objects in S q to present the user with more useful information. Range-Aggregate queries are a step in that direction and are the focus of this thesis.A range-aggregate query can be formally defined as follows: Let S be a set of n objects in IRd, where each object p may have a real-valued weight w(p). We would like to preprocess S into a suitable data structure so that for any given query range q  IRd , a certain aggregation function that operates on the objects of S0 = S q can be performed efficiently and output-sensitively. Existing techniques in the literature cannot be directly applied to answer these queries efficiently. Therefore, in each chapter we consider a unique aggregation function and study them in detail. In many applications reporting all the points in S q is not a user-friendly experience since jS qj can be very huge and hence, unmanagable. Therefore, we use the aggregation operator ‘top-k’ to report only the k most significant points based on the weights associated with each point. In many scenarios, the points in S are classified into disjoint groups. We associate a unique color with each group and all the points belonging to that group also inherit that color. Given a query region q, a straightforward query is to report the unique colors of the points in S q. In the range-aggregate versions we considered, additional information would be reported along with each color c such as the point of color c in q with the maximum weight or the sum of the weights of all the points of color c in q. In short, a useful summary of each group is reported. Geometric aggregation functions are relatively more difficult to handle than the regular aggregate functions. We consider some geometric aggregation problems and improve upon the existing solutions in the literature. Finally, we consider a boolean yes or no query asking if jS qj > 0 or not. Though existing structures in the literature can answer this query in reasonable query time and space we made an attempt to further improve them. We come up with efficient data structures and query algorithms to solve these problems. Mathematical analysis is done to show the efficiency of our solutions in terms of space occupied and query time. Real world applications of each type of range-aggregate query is explained as well.

Abstract

Text mining is a subeld of data mining that, in turn, is a component of a more general category of Knowledge Management (KM). In the real world, knowledge is represented not only by the structured data found in traditional databases, but in a wide variety of un-structured sources such as books, research papers, word documents, letters, digital libraries, e-mail messages, news feeds, Web pages, and so forth. Text mining is particularly relevant today because of the enormous amount of knowledge that resides in unstructured collection of text documents. It uncovers relationships in a text collection, and leverages the creativity of the knowledge worker to explore these relationships and discover new knowledge. In recent years, we have witnessed a tremendous growth in the volume of text documents available on the internet, digital libraries, news resources and so on. With the dramatic growth of text information, there is an increasing need for powerful text mining systems that can automatically discover useful knowledge from text. The digital data has become one of the most important resources for information. But the fact that more data is available does not necessarily mean that it is being used in ecient manner. It has been observed that no one is willing to or capable of manually browsing through large data collections. To satisfy user's information need, a system should list a precise and small subset of the data collection. People often interact with these document collections and thus may be interested in methods to help them better use the documents or retrieve the useful knowledge. For retrieving individual documents, search engines have already been very successful. Other methods such as topic modeling can provide a coarse overview of the topics in a document collection. While information retrieval and topic modeling methods have been widely applicable and useful, current methods for drilling deeper to understand the structure and development of research areas in terms of topics and their relationships with each other and their originating documents for each of those topics in a corpus as a whole could still be improved. In this thesis, we provide methods for a set of tasks that seek to identify the important or new keyphrases and corresponding rst originating document, known as Landmark Paper. These methods focus on supplying a ne-grained picture of development of keyphrases over time to help users grasp the keyphrase collection's development as a whole. We focus on the problem of nding novel keyphrases within the document collections, and their originating documents through the multiple conferences with respect to the conference year. In addition to this, we also consider that it is insucient for new researchers who are exploring a research area. It is much more helpful to be able to see the related research areas based on proximity and importance of keyphrases and their originating documents. We investigate the system where the user can enter a set of keyphrases and the system recommend a set of top k - keyphrases by using knapsack approach, corresponding to the user's query and also show the relationships of these topics to each other and nally outputs the landmark paper for each of those topics. This will essentially provide all the material required for the researcher to exhaustively understand the foundations of that research area. This thesis explores text-based approaches for these tasks. For wide applicability, the methods use only document text. We evaluate our methods experimentally on actual research publications from the dierent Data Mining and Databases conferences proceedings available on the Digital Bibliography Library Project (DBLP) website1. We have prepared a cleaned-up dataset with the text proceedings to conduct this evaluation. In addition to the above tasks, we have develop an approach by using knapsack based solution as discussed above in a dierent domain i.e. to recommend set of items to the customers in retail stores such that the prot of the store is maximized.