MIT EECS Event

MASTERWORKS98

A PRESENTATION OF MASTER'S THESIS RESEARCH
IN
ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

Monday, April 27, 1998
from
3:00 to 5:00 pm
in
Building 34
(3rd and 4th floors).

Masterworks is an annual presentation of thesis research by Master's students in the Department of Electrical Engineering and Computer Science. It is open to the public; students, undergraduate and graduate, are particularly welcome.

Students who are nearing the end of their thesis research and who wish to make a presentation submit an abstract to Masterworks and those who are selected present a 15-minute talk on their research. Prizes are awarded for the best presentations.

The talks are scheduled in 12 1-hour sessions of 3 talks each; 6 sessions occur simultaneously.

Abstracts

SESSION A

Development of Calibration Standards for Accurate Measurement of Geometry in Microelectromechanical Systems
Erik R. Deutsch

Microelectromechanical Systems (MEMS) is an expanding technology for mechanical sensors and actuators. Post-process information such as the measurements of device geometry and mechanical properties are necessary to be able to design and model these devices. The MIT-developed material test procedure (M-Test) is an in-situ measurement of a set of simple test structures consisting of cantilever and doubly supported beams, and circular diaphragms. An electromechanical instability point, called the pull-in voltage, and device geometry, enable process monitoring and extraction of mechanical properties. Accurate thickness and gap measurements are necessary due to a high dependence on geometry. This thesis reports the development of calibration standards which are used to calibrate a surface profilometer so that accurate measurements of device thickness and gap can be made to within one percent using a beam deflection technique. The results of this new level of accuracy are applied to M-Test in order to extract Young's modulus and axial residual stress from test structures consisting of doubly supported beams.

A Nonintrusive Load Monitor is a device that determines the operating schedule of electric loads by analyzing turn-on transients in the current at the utility service entry of a building. Analysis is made easier by using the spectral envelopes of the current instead of the instantaneous current itself. A spectral envelope of a waveform is the integral, over an appropriate time interval, of the waveform mixed with a basis sinusoid of a chosen frequency and phase. These integrals, and thus the spectral envelopes themselves, can be estimated by low-pass filtering the mixed signals. In this thesis, I have designed a spectral envelope pre-processor implemented entirely in software on a powerful digital signal processor. Digital pre-processing begins with a phase correcting high-pass filter that eliminates any DC offset present in the samples of the service voltage and current while minimizing phase distortion among frequencies of interest. A discrete-time phase-locked loop is responsible for the generation of basis sinusoids, which are synchronized with the service voltage. These sinusoids are mixed with the current and passed through a low-pass filter to obtain the preliminary spectral envelope estimates. These initial results are downsampled and notch filtered to reduce mixing artifacts present in the final envelopes sent to a PC via a parallel port interface. Each of these processes is reviewed in detail, and the overall performance is analyzed to determine the extent to which limitations plaguing previous designs have been alleviated.

Capacitive Position-Sensing System and Electronics for a Linear Electrostatic Micromotor
Lily Y. Kim

In the past ten years, many designs for electrostatic micromotors have emerged. Recently, a new linear electrostatic micromotor has been designed which, unlike most micromotors, is actuated by both in-plane and out-of-plane forces. However, using repulsive out-of-plane forces introduces an instability into the motor. This instability must be corrected using closed-loop control, which becomes an essential part of the design. In this project, a milli-scale model of the micromotor was built, and all electronics for the model were designed and built. In particular, position-sensing circuitry was designed to provide the feedback signal for the control loop. The position-sensing scheme works by inferring the motor's position from capacitance measurements. Using the position-sensing circuitry and the milli-scale motor, a method was experimentally demonstrated for detecting the motor position in two directions: in-plane and out-of-plane.

Supervisors: Prof. Jeffrey H. Lang and Dr. Carl Taussig, Hewlett-Packard Laboratories

SESSION B

Complexity and compounding effort can severely restrict the scope of future VLSI designs. This work quantifies the limits of cell-based design methods and introduces a "crafted-cell" solution to enable full-custom quality with standard cell effort. Exploring the layout area and circuit performance of cell-based designs results in two observations: area utilization is an insufficient measure of layout efficiency and the composition of traditional standard cells inherently restricts the quality of cell-based datapaths. A new efficiency metric (eta_layout) is proposed to reflect the interplay between device fill and interconnect. The crafted-cell approach is introduced to overcome the identified cell restrictions. This work tests the effectiveness of the crafted-cell approach by re-implementing two full-custom datapaths. The resulting crafted-cell designs use less than 2x the area and have at most a 17% longer critical path when compared to the full-custom originals. They are between 1x and 8x smaller and have at least a 43% shorter critical timing path when compared to traditional standard cell implementations.

The NetLog: An Efficient, Highly Available Stable Storage Abstraction
Arvind Parthasarathi

In this thesis I present the NetLog, an efficient, highly available, stable storage abstraction for distributed computer systems. The NetLog interface is more suited to application requirements than other proposed log interfaces. Unlike traditional storage mediums, such as magnetic disks, that provide only reliability, the NetLog provides both reliable and available storage through the use of primary copy replication. By hiding all details of processing from applications and implementing a generic interface, the NetLog can be used by any application and applications that accessed reliable storage now get the benefits of availability with little code change. Within Thor, I developed a disk based log as well as NetLog implementations that survive one and two server failures. I developed a model of both logs to extend the comparison to other system and technology configurations. My performance results, from experiments and modeling, show that the availability provided by the NetLog comes for free as the NetLog always performs faster than the disk log, and performs an order of magnitude faster for small data sizes.

Having seen its low value-added manufacturing sector migrate to low-cost China, leading Hong Kong politicians and industrialists believe a software industry is one of the keys to reinvigorating Hong Kong's domestic industry. Software is particularly attractive to Hong Kong because barriers to entry for individual firms are low, allowing small firms to thrive, and production of software doesn't require large amounts of space or public investments in infrastructure. However, a vibrant Hong Kong software industry has not yet emerged. What is preventing Hong Kong's software industry from growing? Many leading Hong Kong politicians and industrialists point to the lack of technology focused venture capital funds in Hong Kong's capital markets and Hong Kong's small domestic market size as the key variables that are inhibiting the local software industry's growth. However, initial findings in this research show that fundamental variables blocking the growth of the Hong Kong software industry lie in the area of human resources and in the lack of source organizations. This has important implications for Hong Kong, considering that politicians and industrialists are now dedicating resources to address the venture capital and domestic market size issues while virtually ignoring the issues surrounding human resources and source organizations.

SESSION C

Propagation Properties of Duobinary Transmission in Optical Fibers
Leaf Jiang

As the demand for faster communications increases, there has been a natural evolution towards a better usage of channel bandwidth. Optical fiber communications offers such a large usable bandwidth that efficient channel usage has not been an issue until recently. Duobinary modulation may be the next step in the evolution of spectrally more efficient formats in optical fibers. Duobinary format is a binary NRZ signal with spectral shaping due to correlation between adjacent bits. This modulation scheme has four attractive features: (1) narrower bandwidth than binary format and hence suffers less from dispersion, (2) greater spectrum efficiency than binary format and hence allows tighter packing of wavelength division multiplexed channels, (3) less stimulated Brillouin backscattering, the major limiting factor in repeaterless transmission, and (4) ease of implementation. Duobinary format is new to the optical communications community and hence there are many unresolved issues. This thesis discusses the issue of optimal filtering from a set of popular, physically realizable filters. The spectrum efficiency of duobinary and binary format using optimized filters is then computed and compared to NRZ binary modulation. The optical power at which stimulated Brillouin backscattering (SBS) becomes a problem in a transmission system is called the SBS threshold. The SBS threshold is determined both experimentally and theoretically for duobinary format and is shown to be much higher than binary NRZ format, especially at high bit rates.

Supervisors: Prof. Erich Ippen, Prof. Hermann Haus, and Dr. Per B. Hansen, Bell Laboratories, Lucent Technologies

Impacts of Coherent Crosstalk on the Performance and Scalability of WDM AONs
Can Emre Koksal

There are multiple causes of signal degradation that occur as optical signals propagate between two users in a WDM-AON, the most important of which is crosstalk. In previous research work, the analysis of crosstalk was developed employing Gaussian and worst case assumptions for the interference portion of the detected signal. Furthermore, the crosstalk-crosstalk beat which occurs due to the square-law nature of the optical detector was neglected and the interferers were assumed to be at the same rate and synchronous with the signal. This thesis presents rigorous crosstalk analysis techniques starting from a worst case approach for one interferer, to more general cases which account for the rate differences of the signal and the crosstalk, the asynchronousness of their bit slots and the randomnesses of their phases and polarizations. In each step, the error probability of the optimum detector is evaluated. Finally, an accurate analysis is performed for multiple crosstalk sources employing an MMSE estimation for the crosstalk-crosstalk beat terms and the tightest Chernoff bound for the error probability. The error probability curves for three practical examples were illustrated, including a system using Lucent 000371695 WGR whose specifications are experimentally determined. Furthermore, the validity of the Gaussian approximation and the neglection of crosstalk-crosstalk beat terms are argued and the regions of system parameters which make these assumptions valid are illustrated. In all these steps, we try to be very accurate and do not make any assumptions and approximations without making sure that they are reasonable and work in the regions that they are good.

All-Optical Switching Using Semiconductor Optical Amplifiers Biased at Transparency
Bryan S. Robinson

All-optical switches have many applications in the development of ultrahigh speed multi-access time-division multiplexing networks. Semiconductor optical amplifiers biased in the gain regime have been employed in switches operating at rates up to 100 Gbps. However, these devices suffer from the effects of long-lived carrier population dynamics. In this thesis, we explore the use of passive semiconductor waveguides and semiconductor optical amplifiers biased at the transparency point in all-optical switches. We discuss how the nonlinear refractive index, linear and nonlinear loss, and dispersion of a waveguide affect all-optical switching performance. Using a spectral interferometric technique, we measure the nonlinear refractive index and dispersion characteristics of semiconductor waveguides biased at transparency. We demonstrate 10 Gbps all-optical switching using a semiconductor optical amplifier biased at the transparency current.

SESSION D

With current networking advances, distributed computing is becoming more commonplace. Distributed systems are hard to design and reason about because they exhibit arbitrary interleaving. In order to design and analyze distributed systems, Professor Lynch's group developed a formal mathematical model, the Input/Output (I/O) automaton model, for describing asynchronous concurrent systems. Based on the I/O model, a new programming language, IOA language, together with a suite of tools for testing, verifying, and analyzing distributed algorithms are being developed. The topic of this thesis is a simulation tool for the IOA language. Simulation allows one to test and debug algorithms, and can provide insight that is helpful in understanding algorithms and constructing correctness proofs for them. The simulator can be used to study the performance of an algorithm under varying conditions. In addition, implementing the IOA simulator proved to be very useful in the design of the IOA language, since writing a simulation tool is an excellent way to evaluate and explore the language design space. Another contribution of this thesis is the design of an intermediate language that can be used by other IOA tools, and the development of a tool that transforms an IOA program into the intermediate representation.

In traditional polygon rendering systems, the goals of high quality images and real time rendering tend to be mutually exclusive on all but the most expensive platforms, as rendering time is directly proportional to scene complexity. Image based graphics algorithms offer an alternative to traditional rendering techniques whereby views of complex objects and scenes may be reconstructed extremely quickly from previously obtained views. However, these algorithms suffer from an insatiable appetite for memory, noticeable artifacts from many viewing directions, and an inability to handle dynamic lighting. Point Sample Rendering is an algorithm which features the speed of image based graphics with quality, flexibility and memory requirements approaching those of traditional graphics. Objects are represented as a dense set of surface point samples which contain color, depth and normal information, enabling Z-buffer composition, phong shading with arbitrary light sources, and other effects such as shadows. These point samples are obtained by sampling orthographic views on an equilateral triangle lattice. They are rendered directly and independently without any knowledge of surface topology. We introduce a novel solution to the problem of surface reconstruction using a hierarchy of Z-buffers to detect tears. Our algorithm is fast, easily vectorizable, and requires only modest resources.

Debugging Multithreaded Programs that Incorporate User-Level Locking
Andrew F. Stark

The Cilk multithreaded language is designed to allow users to parallelize C code. Parallelization, however, introduces a new kind of bug, known as a data race bug. A data race occurs when two parallel threads holding no locks in common access the same memory location and at least one of the threads writes the location. Data races may cause programs to behave nondeterministically. We present the Nondeterminator tool for automatically detecting data races in Cilk programs. The Nondeterminator has provable bounds on its running time and memory usage. Furthermore, we prove that the Nondeterminator can verify the determinacy of an "abelian" Cilk program, one whose critical sections commute, on a given input. Using the Nondeterminator, we were able to parallelize a large radiosity application by changing less than five percent of the original C code.

SESSION E

Formal Verification of Safety of Automated Vehicle Maneuvers
Ekaterina Dolginova

A system consisting of two platoons of vehicles on a single track, plus controllers that operate the vehicles, plus communication channels, is modeled formally, using the hybrid input/output automaton model of Lynch, Segala, Vaandrager and Weinberg. A key safety requirement of such a system is formulated, namely, that the two platoons never collide at a relative velocity greater than a given bound. Conditions on the controller of the second platoon are given, designed to ensure the safety requirement regardless of the behavior of the first platoon. The fact that these conditions suffice to ensure safety is proved. It is also proved that these conditions are ``optimal'', in that any controller that does not satisfy them can cause the safety requirement to be violated. The model includes handling of communication delays and uncertainty. The proofs use composition, invariants, levels of abstraction, together with methods of mathematical analysis. This case study is derived from the California PATH intelligent highway project.

This thesis research investigates a new approach to learning grammars automatically for use in speech recognition and natural language processing systems. Unlike some other approaches, this one recognizes that language serves to convey meaning, not syntax, and thus uses meaning as the fundamental component driving the grammar induction process. In our research, we develop a semantic parser which parses utterances based on meaning, not syntax, only combining words and phrases which "make sense" to combine. The system subsequently extracts a grammar from the resulting semantic-level phrases. Finally, we test the grammar both with different utterances from the same domain, as well as utterances from a new domain, assessing the portability of the grammar. Semantic parsing proves to be a very powerful mechanism, providing nice "meaning-representations" directly. Further, by recording how words and phrases combine, the parsing enables several grammar induction techniques; one such technique we developed makes full use of the semantic-level information available in order to create a compact, recursive grammar. This resulting grammar is indeed usable and useful, performing quite well in tests of new utterances in the same domain, as well as performing reasonably well in a different domain.

Supervisors: Dr. James R. Glass and Dr. David Goddeau, DEC Cambridge Research Labs

Generating Threads for Programs Written in Non-strict Functional Languages
Christiana V. Toutet

In order to run non-strict functional programs efficiently on ordinary hardware which is adapted to exploiting sequential instructions, the compiler must find an ordering on instructions. This task is not straightforward for non-strict languages, where functions may return values before all their arguments are available, and data structures may be defined before all their components are. In fact, the compiler is not always able to determine a total compile ordering. Partitioning therefore corresponds to breaking a program into sequential parts, threads, whose relative ordering will be dictated at run-time. Unlike previous work, the dependence analysis algorithm for partitioning proposed in this thesis integrates basic blocks, conditionals, and multiple procedures by using a representation, predicated sets, which distinguishes distinct flows of control within a function. In order to handle recursion, the analysis is built within an abstract interpretation framework. Since the predicated set domain is infinite, a special termination condition for fixpointing based on the use of the analysis results is introduced.

SESSION F

Silicon is the most popular material for today's integrated circuits because of its low cost and widespread use. It has traditionally been considered to be too slow for applications operating in the gigahertz frequency range. Thus, faster, yet more expensive, substrates, such as Gallium Arsenide, have been necessary for high-frequency applications. A good example of this need is that cellular phones utilize silicon chips for the bulk of the signal processing circuitry, and use a few Gallium Arsenide chips for the high-speed transmission and reception of signals. However, as silicon MOSFETs become faster due to device scaling, they may be a viable solution to high-frequency applications. Silicon devices show ever increasing values of fT and fmax, two metrics which are widely regarded as good indicators of high-frequency performance for a given technology. While fT is now at an acceptable level for circuits operating in the lower gigahertz regime, fmax is relatively low. In this talk, I will discuss the limiting factors of high fmax in silicon n-FETs. I have characterized experimental devices and performed computer simulations to reveal that the gate resistance, output resistance, and overlap capacitance, are primarily responsible for hindering fmax. Then, I will show how silicon-on-insulator (SOI) devices demonstrate degraded high frequency operation potential due to their floating body effect.

AlGaAs/GaAs Heterostructure Bipolar Transistors (HBT) are important for high performance power amplifiers (PA) and are especially attractive because of their superior linearity properties. There are several performance figures of merit that the HBT must be designed for. These include the gain (G), power output (Pout), power added efficiency (PAE), and third-order intermodulation distortion (IMD3). A high G is desired so that the PA can be constructed with a minimum number of stages to reduce the size and weight. A high PAE is necessary for long talk times on battery operated systems. POUT is in general a design parameter that is imposed by the system requirements. A low IMD3 is needed so that the signal spillover to an adjacent channel is minimized. To assess linearity it was first important to set up an environment where the linearity as well as POUT, G, and PAE can be predicted with a simple well accepted model such as the Gummel-Poon (GP) model. This GP model must be able to accurately predict the figures of merit of interest over a wide range of bias conditions. After the verification of the model and simulation environment with measurements, it was necessary to investigate different sources of nonlinearity in this model. This has been done to formulate a simple analytical method of predicting the linearity from the simple model parameters. This model was then tested for several bias conditions and frequencies.

The field emission display (FED) is being widely studied as a viable alternative to existing flat panel technologies for portable applications. Power consumption in portable flat panel display systems has become a primary concern because it reduces battery lifetime, impacts circuit reliability, and generates heat. The FED is an emissive display that has inherent advantages over the existing flat panel displays such as AMLCD's. The display electronics of the FED are responsible for addressing and controlling the matrix of pixels that compose the display screen. To perform this crucial addressing function, modern flat panel display electronics can consume up to one-third of the power dissipation in the display. The power dissipation in the display electronics has therefore emerged as an important aspect of the FED subsystem to investigate. The motivation for this thesis is to develop low-power row and column driver circuits based upon the specific functional requirements of the field emission display. These functional requirements include matrix-addressing ability and the ability to implement multi-bit gray scale. Two system-level techniques, half-power point switching and charge conservation, were investigated as possible methods to reduce the dynamic power dissipation of the circuit. Architectural features such as dynamic shift registers were implemented in a further effort to minimize the power consumption of the circuit.

SESSION G

Probabilistic Segmentation for Segment-Based Speech Recognition
Steven C. Lee

Segment-based speech recognition systems must explicitly hypothesize segment start and end times. The purpose of the segmentation algorithm is to hypothesize those times and to compose a graph of segments from them. During recognition, this graph is an input to a search that finds the optimal alignment of sound units through the graph. The goal of this thesis is to create a high-quality real-time segmentation algorithm for summit, a segment-based speech recognition system. A high-quality segmentation algorithm produces a sparse network of segments that contains most of the actual segments in the speech utterance. In this thesis, the goal of creating a high-quality network is accomplished by using a probabilistic approach that only hypothesizes the most probable segments based on trained acoustic and language models. A real-time algorithm implies two properties. One is that the algorithm be fast. The other is that it be able to produce an output in a pipelined manner. These properties are built into the algorithm by employing the use of efficient landmark-based Viterbi and A* searches that incorporate broad-class acoustic and phonetic constraints to locate probable segments, and by processing the speech signal in reliably detected blocks. For phonetic recognition on the TIMIT corpus, the algorithm produces a segment graph that has over 60% less segments and achieves a 3.8% improvement in error rate over a baseline algorithm based on acoustic change and heuristics. For word recognition on the JUPITER corpus, a telephone-based weather information domain, the algorithm produces a segment graph containing over 40% less segments and achieves a comparable error rate as the baseline. If the real-time constraint is slightly relaxed for word recognition, the algorithm can produce a segment graph that contains over 30% less segments and still achieves a 7.9% improvement in word error rate over the baseline.

Intonational information is vital in the interpretation of meaning in human speech. People engaged in conversation exchange vast amounts of information through speech, gesture, intonation, and facial expression. An examination of the intonational structure of speech should help a computer system to be more responsive to human users. For this thesis, I created a system which determines whether an utterance is a yes/no question or a statement by looking at the underlying speech signal, but without looking at the words. This can help to provide redundancy and additional information within a system for human/computer interaction.

The goal of this work was to develop a speech synthesis system which concatenates variable-length units to create natural sounding speech. Our initial work in this area showed that by careful design of system responses to ensure consistent intonation contours, natural-sounding speech synthesis was achievable with word- and phrase-level concatenation. In order to extend the flexibility of this framework, subsequent work focused on the problem of generating novel words from a pre-recorded corpus of sub-word units. The design of the sub-word units was motivated by perceptual experiments that investigated where speech could be spliced with minimal distortion and what contextual constraints were necessary to maintain in order to produce natural sounding speech. This sub-word corpus is then searched at synthesis time with a Viterbi search which selects a sequence of units based on how well they individually match the input specification and on how well they sound as an ensemble. This concatenative speech synthesis system, Envoice, has been used in a conversational information retrieval system in two application domains to convert meaning representations into speech waveforms.

SESSION H

Framework for Characterization of Copper Interconnect in Damascene CMP Processes
Tae H. Park

Aluminum interconnect has started to reach its performance and process limits for high performance circuits, and the new copper interconnect is being developed using a damascene or in-laid metal process with chemical mechanical polishing (CMP). Understanding process and integration issues as well as problems is critical in successfully developing copper metallization. To characterize in-laid metal polishing behaviors, a methodology is developed that builds upon the statistical metrology framework for oxide polishing. Previous works show characterizations of pattern dependencies for copper damascene CMP planarization but do not clearly examine important parameters such as density and interaction distance. The degree of dishing within individual copper lines and erosion (undesired polishing of surrounding oxide), two primary pattern dependencies, depends strongly on the specifics of the pattern being polished. This pattern dependency is a difficult implementation and process integration obstacle, with both yield and circuit performance impact. The central focus of this thesis is the development of methods to characterize and understand these pattern dependencies in copper CMP. This new methodology is carried out by experiments using a CMP characterization mask set and a newly designed electrical test mask through a collaborative work with SEMATECH. The new electrical test mask for the copper damascene process combines two main patterns of density and pitch into one mask and focuses on the rapid evaluation of dishing and erosion phenomena. In addition to density and pitch patterns, the mask also includes electrical serpentine and comb test structures to characterize electrical yield for minimum pitch and fine linewidth metal lines.

Non-Perfluorocompound Chemistries for Dielectric Etching Applications
Laura C. Pruette

Currently, the semiconductor industry relies on a class of chemistries, known as perfluoro-compounds (PFCs), to etch dielectrics. Specific applications that utilize PFCs include wafer patterning and plasma enhanced chemical vapor deposition (PECVD) chamber cleaning. These compounds have long atmospheric lifetimes, and are suspected to contribute to global warming. Work is underway to identify alternative, non-perfluorocompound chemistries that achieve equivalent processes with substantially reduced global warming emissions. Experiments have been performed to evaluate the etch viability of a number of candidates. Alternatives that demonstrated a comparable etch rate to a PFC baseline process were moved on to the next phase of the project: etch process development or PECVD chamber clean development. Preliminary work on process development has been completed; further work, including industry beta-testing of alternative processes, will constitute the author's Ph.D. research.

Evaluation of Compartmentalization as an Explanation of Discrepancies Calculating Fixed Charge Density in Cartilage
Arun Thomas

The use of sodium (Na +) NMR, along with an ideal Donnan single compartment (which supposes a completely homogenous material) model of cartilage, has already been validated as a means of evaluating cartilage fixed charge density (FCD). Similar calculations of FCD from gadopentate (Gd-DTPA 2-) NMR and the same model are correlated with, but 50% below, values derived from sodium NMR. Since the water content of cartilage is known to be divided between two physiologically distinct regions with different FCDs, use of an oversimplified (single rather than double compartmental) model of cartilage was one possible reason for the 50% factor. It was hypothesized that calculations of FCD in a cartilage simulacrum consisting of only one compartment would not result in this 50% factor. Solutions of proteoglycans, the components of cartilage responsible for FCD, were placed within dialysis tubing bags and equilibrated in solutions containing sodium and gadopentate ions. FCD calculations based on ion concentration measurements continued to yield a 50% factor, invalidating the hypothesis.

SESSION J

A Highly Integrated Adiabatic Charge Recovery Digital to Analog Converter (ACRDAC)
M. Josie Ammer

We have developed the first digital to analog converter (DAC) that uses an adiabatic ramp to perform charge recovery for low power operation. Charge recovery has proven successful as a low power technique for high-capacitance digital circuits. The ACRDAC is the first application of charge recovery to DACs. The ACRDAC is immediately suitable for many existing applications and will also enable future applications which require low power digital to analog conversion. A miniature liquid crystal display (MLCD) drive circuit has been chosen as a testbed for the ACRDAC technique. The ACRDAC is an excellent match for the application because it can be parallelized and integrated on the same chip as the display. The integrated chip is not only the first physical implementation of the ACRDAC but is also the first ever MLCD which incorporates charge recovery. The chip has been designed, is currently in fabrication, and is scheduled for delivery by May 1998. This talk describes the ACRDAC and the MLCD and compares our approach to conventional techniques.

A/D converters for CMOS imagers have traditionally been designed using the column-parallel approach, requiring a slow A/D converter for each column of the sensor array. This thesis investigates a serial approach utilizing a single fast A/D converter to process all of the imager pixels. If power scales linearly with frequency in a given A/D architecture, power dissipation for the two approaches should be comparable. However, the serial approach should occupy less area since only the cost of one A/D converter is incurred. Camera system specifications require a single serial A/D converter to have 10b resolution at a 3MHz sampling rate for a CIF (352x288) imager array running at 30 frames per second. Calibration is flexible. Area minimalization, power minimalization, and the ability to build the A/D in a standard CMOS process are extremely important for consumer product applications. A figure of merit (1/(power*area)) is introduced to compare different A/D architectures after appropriate technology, speed, and supply scaling. A single slope A/D architecture with a subnanosecond time digitizer showed promise for optimizing this figure of merit over pipelined and folding interpolating approaches. The 3MHz converter was designed, simulated and laid out in a 0.35um CMOS technology. At 3.3V supply, 25C and nominal process conditions, the converter dissipates about 29 mW in 0.27 mm2. This gives an estimated 37 mW in 0.4 mm2 for the 12MHz converter.

Supervisors: Prof. Charles G. Sodini and Dr. Marc Loinaz, Bell Laboratories, Lucent Technologies

A Single Supply Wide Bandwidth 4:1 Video Multiplexer in an 8 GHz Dielectrically Isolated Complementary Bipolar Process
Shan J. Wang

A high performance monolithic 4:1 analog multiplexer implemented in an 8 GHz dielectrically isolated complementary bipolar process was designed and simulated. It is useful in many general purpose high-speed applications such as driving an 150 ohm cable or an analog to digital (A/D) converter. This switched transconductance amplifier 4:1 video multiplexer has a current mode decoder, a voltage feedback amplifier and four PNP-differential-pair input stages. It has a -3 dB small signal bandwidth of 148 Mhz and a slew rate of greater than 170 V/us. It has a differential gain and a differential phase error of 0.03% and 0.03 degree. With -113 dB of all-hostile crosstalk and 91 dB of off isolation at 10 MHz, this multiplexer is compatible with a 10 bits A/D converter. It has a channel switching time to 0.1% of 15 ns and consumes less than 6.4 mA on a 5 V single supply voltage. The output voltage swing of this multiplexer extends to within 50 mV of each rail, providing a wide output dynamic range. It offers a high-speed disable feature allowing the output to be put into a high impedance state for multi-stages so that the off channel does not load the output bus. This shutdown feature also reduces the supply current to less than 2.6 mA.

SESSION K

An Improved Lost-Packet Recovery Technique for the ITU-T G.723.1 Speech Coding System
Grant Ho

The G.723.1 dual rate speech coder was ratified by the ITU in 1996 to encode voice for low bit-rate multimedia services over IP, ATM, and Frame Relay. The near toll quality of the G.723.1 standard is ideal for real-time voice transmission over LANs where packet loss is minimal. However, over WANs and GANs, congestion can be severe, and packet loss may result in heavily degraded speech if left untreated. This thesis presents the design and implementation of a lost-packet recovery (LPR) technique to reconstruct missing speech packets. LPR combines three original algorithms -- linear interpolation, selective energy attenuation, and energy tapering -- to successfully recover missing packets and maintain an acceptable degree of speech quality for the end user. Informal listening tests were performed on nine subjects to quantitatively and qualitatively determine the performance of LPR over the method of packet recovery described in the G.723.1 standard. For uniformly distributed packet loss rates up to 15%, LPR was shown to achieve up to a 20% increase in speech quality over the G.723.1 standard by eliminating unnatural-sounding speech, metallic-sounding artifacts, high-energy spikes, and choppy synthesized speech. Overall, the quality achieved with LPR was shown to be preferred by 100% of the subjects, with 66% of the subjects strongly preferring the quality of LPR over that delivered by the G.723.1 standard.

Packet Delay and Sequence Number Space in the Radio Link Protocol Layer
Euree Y. Kim

The problem of queuing delay through the two-queue model consisting of the M/D/m and the M/G/1 queues is relevant to the Radio Link Protocol (RLP) layer implementation of a high speed wireless packet data service system. The frame round trip delay is an important performance measure of such system, and it influences the size of the sequence number space. The analysis of the frame delay and ultimately the sequence number space size in the RLP layer for a wireless CDMA packet data system is the topic of study in this thesis project. The round trip delay is taken to be the time between the issuance of a NAK by the mobile station and the time that the retransmitted frame leaves the base station transmitter. The M/D/m and the M/G/1 queues together model the base station's channel to transmit an RLP frame whose retransmission is requested in a negative acknowledgment from a mobile station. The queuing analysis of the two-queue model quantifies the round trip delay, and the results are then used to arrive at the adequate size of the sequence number space that brings the probability of protocol failure to an acceptably low level.

Analysis and Detection of Jamming Attacks in All-Optical Networks
Poompat Saengudomlert

This work concentrates on the detection of attacks in which a malicious user with legitimate node access inserts a jamming signal to interfere with other communication paths. While existing failure detection schemes in all-optical networks (AONs) can be used to detect overt attacks of this nature, they are not adequate for detecting covert attacks which cause bit-error-rate (BER) degradation in a communication path. A bit error rate tester (BERT) can detect the BER degradation but requires too long an observation time. In the first part, we first present a novel attack detection scheme and analyze its performance for a specific implementation. Using our scheme, each node detects whether the data stream was corrupted by traversing it. Since we observe the degradation of transmitted signals rather than the bit errors, the detection time is much shorter than that of a BERT. In the second part, we analyze the performance limit of our approach without any implementation constraint. Our goal is to provide, in the absence of an alarm notifying an attack, an absolute guarantee on the BER regardless of the sophistication of an attack. In doing so, we find the worst case jamming attack scenario in which an attacker degrades the BER to a specified level while minimizing the probability of being detected. Finally, we demonstrate that our attack detection scheme can detect the worst case attack scenario with high reliability, and the associated detection time is as much as 5 to 6 orders of magnitude shorter than that of a BERT for the detection of BER degradation above 1E-10.

SESSION L

Consistent Hashing and Random Trees: Algorithms for Caching in Distributed Networks
Daniel Lewin

In this thesis we develop the algorithmic foundation of a large scale distributed caching system for the World Wide Web. In particular, we focus on developing hashing and replication mechanisms that are robust under rapidly changing environments such as the Internet. Two tools are developed: Consistent Hashing, a new hashing technique, and Random Trees, a new replication and load balancing technique. These algorithms have already sparked commercial interest, and are currently being implemented at LCS as part of a distributed caching system.

This thesis demonstrates that "channels" created by dynamically filtering Web content are a viable large-scale information delivery mechanism. Using the techniques developed here, three desktop computers can, in one day, alert every Internet user to information of interest from 10,000 different Internet hosts. Similarly, in one day, nine desktop computers could be used to inform 100,000 users of all information of interest to them on the entire World Wide Web. The core of this project is a profile store that converts user profiles expressed as PICSRules into efficient, equivalent C programs. These programs use metadata as input (in the form of PICS labels) to describe the content of Web pages. A series of careful measurements shows that the system scales linearly in both the number of labels and the number of users (profiles).

Diffusion of Network Innovation: Implications for Adoption of Internet Services
Marc Shuster

The Internet and network applications have achieved significant growth. This thesis reviews the historical development of the Internet and projects future expansion of network application usage. Observed data points for Internet hosts, World Wide Web servers, the Multicasting Backbone, USENET, and Internet telephony were fit to an s-shaped logistic curve. The results of the model predict the applications' growth rate, halfway points of growth, and saturation limits. The number of Internet hosts is expected to saturate at about 39 million hosts by the early part of the next century, while the number of Web servers will saturate at about 40% of responding Internet hosts. The adoption rate of Internet Telephony was estimated by analogy to adoption patterns of more established applications. The factors necessary for successful deployment of Internet telephony were addressed in terms of network architecture and user interface. Internet telephony and multicast applications that require reserved network resources were concluded to be in very early stages of development. At the time of this writing, only a small fraction of the users who have knowledge and have tried telephony applications are willing to adopt and actively use the technology. This indicates that augmentations to Internet services are necessary to improve the usability of realtime applications, such as Internet telephony.

SESSION M

The problem is enabling a computer to recognize and locate models "in" observations. We are given a space F of features, for example the plane. We are also given a set A of parameterized mappings form F to F, called the space of allowable transformations, for example planar rigid motions. The model and the observation are both finite subsets of F. The model is subject to deformation by transformations in A, and one or more noisy deformed version of the model might be a subset of the observation. In addition to being noisy, some points of those deformed versions might be missing, this phenomenon is called occlusion. The objective is to find an algorithm that has the ability to decide if a given observation contains noisy, deformed, and occluded versions of a given model. If so, the algorithm should be also able to report their locations. The problem being considered has applications in Pattern Recognition, Image Understanding, and Robotics. The contribution of this work is a robust and efficient algorithmic solution for the problem. The solution is general enough to handle different cases of allowable transformations, such as: planar scaled rigid motions, planar affine transformations, and scaled rigid motions in R^d.

Parallel FFTCAP: A Parallel Precorrected FFT Based Capacitance Extraction Program for Signal Integrity Analysis
Vivek Nadkarni

Finding signal integrity problems in high performance integrated circuits and integrated circuit packaging is extremely difficult, primarily because these problems are typically created by the detailed interactions between hundreds of conductors. Although 3-D simulation tools can help designers find signal integrity problems, even the fastest of these tools running on a scientific workstation are too slow to allow a designer to quickly investigate a variety of conductor layouts. Therefore, reducing analysis turn-around time is critical, and can result in 3-D simulation being used as part of design optimization rather than just a-posteriori verification. We demonstrate that the turn-around time for fast 3-D capacitance extraction can be substantially reduced using a cluster-of-workstations based parallel computer, such as an IBM SP2. We first present one of the recently developed fast methods for computing capacitances, the precorrected FFT accelerated method. We then describe the algorithms we developed to parallelize the precorrected FFT based capacitance extraction program and to balance the computational and memory load across the processors. Computational results demonstrating a nearly linear parallel speedup are presented. We show that Parallel FFTCAP can be extremely useful for performing signal integrity analysis, when the problem size becomes too large to be solved on a single processor using FFTCAP or FASTCAP.

Using Multiresolution Range-Profiled Real Imagery in a Statistical Object Recognition System
Asuman E. Koksal

Recognizing 3-D objects from range imagery has received considerable attention in the last few years. Laser radar range imagery is degraded by the combined effects of laser speckle and local oscillator shot noise, resulting in range anomalies and Gaussian noise in the local accuracy of the range measurements. Our objective was to develop a statistically optimum approach for doing model-based object recognition using low-resolution, noise-degraded laser radar range images. The object recognition system consists of preprocessing, segmentation, feature extraction and alignment/scoring steps. For the preprocessor, we have employed the fast ML/EM algorithm, which is an essentially optimal anomaly suppression scheme. The resulting range profile is segmented using planar range profiling to estimate and isolate the target region from the background. The feature extraction module provides the relevant edge-based features. The alignment/scoring step estimates the pose of the target in the image, based on posterior marginal pose estimation method (PMPE) and performs matching between image and model features. The output of the system is the value of the objective function of the PMPE matcher, which gives an indication of the degree of alignment between the image and each member of the object-model data base. In this talk, we will describe and illustrate the behavior of the preceding modules. We will also present performance results from preliminary object recognition experiments using laser radar data from the MIT Lincoln Laboratory Infrared Airborne Radar data release.

MIT Department of Electrical Engineering & Computer Science