Recent work in the area of ultrafast optical time-division multiplexed (OTDM) networking at MIT Lincoln Laboratory is presented. A scalable helical local area network or HLAN architecture, presented elsewhere as an architecture well-suited to ultrafast OTDM LANs and MANs, is considered in the context of wide area networking. Two issues arise in scaling HLAN to the wide area. The first is protocol extension, and the second is supporting the required bandwidth on the long-haul links. In this paper we discuss these challenges and describe progress made in both architecture and technologies required for scaling HLAN to the wide area.

A photonic ATM switch based on wavelength-division multiplexing will include several lossy passive devices, erbium-doped fiber amplifiers, and semiconductor optical amplifiers (SOAs) in a cascade configuration for fast switching of ns order. Its level diagram, which is very different from those of optical transmission links, has not been adequately studied. This paper investigates the concept of basing the level design of the photonic asynchronous-transfer-mode (ATM) switch we are developing on its Q-factor. First, we derive formulation of the Q-factor in a single PD and a dual-PD in a Manchester-encoded signal, which has several merits in packet switching and that we believe will become popular in photonic packet switches. Using this formula, we show an example of the level-diagram design including the Q factor calculation in an optical combiner and distributor section without SOA in our photonic ATM switch. Next, we showed experimentally that the pattern effect in SOAs can be suppressed by using a Manchester-encoded signal. Finally, we confirm that the allowable minimum level diagram in the switch can be based on a simple Q calculation and easy measurement of a bit error rate (BER) in a back-to-back configuration when using a Manchester-encoded signal. These results show that basing the level design of photonic ATM switches on the Q factor is feasible when using a Manchester signals. This approach can be applied to various types of photonic packet switches.

A direct conversion transmitter IC including a proposed frequency doubler, a quadrature modulator, and a 3-bit variable attenuator was fabricated using BiCMOS technology with fT of 12 GHz. This architecture employing frequency doubler is intended for realizing wireless terminals that are low in cost and small in size. The architecture is effective for reducing serious interference between PA and VCO by making the VCO frequency different from that of PA. The proposed frequency doubler comprises a current-driven 90 phase-shifter and an ECL-EXOR circuit for both low power operation and wide input power range of local oscillator (LO). The proposed frequency doubler keeps high output power even when rectangular wave from LO is applied owing to use of the current-driven 90 phase-shifter instead of a voltage-driven 90 phase-shifter. An LO leakage of less than -25 dBc, an image rejection ratio in excess of 45 dBc, and a maximum attenuation of 21 dB were measured. The transmitter IC successfully operates at LO power above -15 dBm and consumes 68 mA from 2.7 V power supply voltage. An active die size is 1.5 mm3 mm.

A photonic ATM switch based on wavelength-division multiplexing will include several lossy passive devices, erbium-doped fiber amplifiers, and semiconductor optical amplifiers (SOAs) in a cascade configuration for fast switching of ns order. Its level diagram, which is very different from those of optical transmission links, has not been adequately studied. This paper investigates the concept of basing the level design of the photonic asynchronous-transfer-mode (ATM) switch we are developing on its Q-factor. First, we derive formulation of the Q-factor in a single PD and a dual-PD in a Manchester-encoded signal, which has several merits in packet switching and that we believe will become popular in photonic packet switches. Using this formula, we show an example of the level-diagram design including the Q factor calculation in an optical combiner and distributor section without SOA in our photonic ATM switch. Next, we showed experimentally that the pattern effect in SOAs can be suppressed by using a Manchester-encoded signal. Finally, we confirm that the allowable minimum level diagram in the switch can be based on a simple Q calculation and easy measurement of a bit error rate (BER) in a back-to-back configuration when using a Manchester-encoded signal. These results show that basing the level design of photonic ATM switches on the Q factor is feasible when using a Manchester signals. This approach can be applied to various types of photonic packet switches.

In this letter, a new scheme of designing two-level minimum mean square error quantizer for image coding is proposed. Genetic algorithm is applied to achieve this goal. Comparisons of results with various methods have verified, the proposed method can reach nearly optimal quantization with only less iterations.

Critical properties of real-time embedded systems must be verified before these systems are deployed as failing to meet these properties may cause considerable property damages and/or human casualties. Although Statechart is one of the most popular languages for modeling behavior of real-time systems, proof systems and analysis tools for Statechart so far are in research and do not fully support the semantics of the original Statechart, or have limited capabilities for proving real-time properties. This paper introduces a toolset ASADAL/PROVER for verifying temporal properties of Statechart extended with justice and compassion properties. ASADAL/PROVER is composed of two subsystems, RTTL-Prover and Model-Checker. The RTTL-Prover converts Statechart specifications into real-time temporal logic (RTTL) formulas of Ostroff, and then checks if the formulas satisfy a temporal property (also in RTTL) using theorem proving techniques. The Model-Checker supports verification of a predefined set of real-time properties using a model checking technique. The RTTL-Prover can support verification of any real-time properties as long as they can be specified in RTTL and, therefore, messages generated by the tool are general and may not be of much help in debugging Statechart specifications. The Model-Checker, however, can provide detailed information for debugging. ASADAL/PROVER has been applied successfully to some experimental systems. One of on-going researches in this project is to apply the symbolic model-checking technique by[3]to support Statecharts with a much larger global-state space. We are also extending the types of temporal properties supported by the Model-Checker.

Real-time services, including constant bit rate (CBR) and real-time variable bit rate traffic (rt-VBR), have become increasingly important owing to the rapid proliferation of multimedia applications. A cell multiplexing method capable of handling real-time traffic should satisfy related quality of service (QoS) requirements, including cell transfer delay (CTD), cell delay variation (CDV) and cell loss ratio (CLR). In this paper, we present an efficient cell multiplexing method, called longest delay beyond expectation (LDBE), to schedule real-time and non-real-time traffic in ATM networks. For the real-time traffic, LDBE scheme can minimize the CDV, and reduce the CLR and CTD, particularly when different CDV tolerance (CDVT) values are applied at each node along the path of a connection. Simulation results demonstrate that the proposed LDBE performs better than other multiplexing methods regarding these CLR, CDV and CTD criteria for real-time traffic. Furthermore, the proposed LDBE is also suitable for scheduling non-real-time traffic by providing a low CLR for non-real-time variable bit rate (nrt-VBR) and minimizing the CTD for unspecified bit rate (UBR) traffic.

We propose a real-time low-rate video compression algorithm using fixed-rate multi-stage hierarchical vector quantization. Vector quantization is suitable for mobile computing, since it demands small computation on decoding. The proposed algorithm enables transmission of 10 QCIF frames per second over a low-rate 29.2 kbps mobile channel. A frame is hierarchically divided by sub-blocks. A frame of images is compressed in a fixed rate at any video activity. For active frames, large sub-blocks for low resolution are mainly transmitted. For inactive frames, smaller sub-blocks for high resolution can be transmitted successively after a motion-compensated frame. We develop a compression system which consists of a host computer and a memory-based processor for the nearest neighbor search on VQ. Our algorithm guarantees real-time decoding on a poor CPU.

In 1992 Burmester studied how to adapt the Guillou-Quisquater identification scheme to a proven zero-knowledge proof without significantly increasing the communication complexity and computational overhead. He proposed an almost constant round version of Guillou-Quisquater. Di Crescenzo and Persiano presented a 4-move constant round zero-knowledge interactive proof of membership for the corresponding language. A straightforward adaptation of the ideas of Bellare-Micali-Ostrovsky will also give a constant round protocol. However, these protocols significantly increase the communication and computational complexity of the scheme. In this paper we present constant round variants of the protocols of Guillou-Quisquater and Schnorr with the same (order-wise) communication and computational complexity as the original schemes. Note that in our schemes the probability that a dishonest prover will fool a honest verifier may be exponentially small, while it can only be one over a superpolynomial in Burmester's scheme. Our protocols are perfect zero-knowledge under no cryptographic assumptions.

The goal of this paper is to present algorithms for creating an optimized query plan for retrieving maximum information from multiple relations, using outerjoins. Especially we focus on conjunctive queries in the presence of predicates and foreign functions. We show first with examples that retrieving maximum information by integrating multiple relations requires outerjoin operators. The outerjoin is essential to prevent information loss that would be caused by the inner join. We also show that predicates and foreign functions are useful to mediate the discrepancy among the relations and to create arbitrary views. Outerjoins and foreign functions, together with predicates, make it difficult to create query processing plans since they impose restrictions on the order of query processing. The rest of this paper describes algorithms for creating such query processing plans for conjunctive queries expressed in extended Datalog. First, we show simple algorithms for creating query plans with outerjoins, but without predicates and foreign functions. We use the hypergraph representation of the relations to explain an optimized algorithm. Then, we show a more complex algorithm that works for query plans with predicates and foreign functions. In our algorithm, we create an initial expression graph whose nodes represent query processing units, including outerjoin, predicate and foreign function operators. Then, we convert the initial expression graph into an executable, optimized expression tree. This algorithm is implemented and deployed in a mediation system that integrates heterogeneous information sources.

High-speed and low-power techniques are described for megabit-class size-configurable CMOS SRAM macrocells. To shorten the design turn-around-time, the methodology of abutting nine kinds of leaf cells is employed; two-level via-hole programming and the array-address decoder embedded in each control leaf cell present a divided-memory-array structure. A new squashed-memory-cell architecture using trench isolation and stacked-via-holes is proposed to reduce access times and power dissipation. To shorten the time for writing data, per-bitline architecture is proposed, in which every bitline has a personal writing driver. Also, read-out circuitry using a current-sense-type two-stage sense amplifier is designed. The effect of the non-multiplexed bitline scheme for fast read-out is shown in a simulation result. To reduce the noise from the second- to first-stage amplifier due to a feedback loop, current paths are separated so as not to cause common impedance. To confirm the techniques described in this paper, a 1-Mb SRAM test chip was fabricated with an advanced 0.35-µm CMOS/bulk process. The SRAM has demonstrated 250-MHz operation with a 2.5-V typical power supply. Also, 100-mW power dissipation was obtained at a practical operating frequency of 150-MHz.

This paper discusses a new form of network database access with mobile agent technology, where many small database servers are distributed geographically, and are accessed through dial-up network on-demand. Coined "scattered database access" here, it enables such interesting ways of data access as asynchronous, circulatory, and the-more-you-spend-the-more-you-get kind of access. Databases to be accessed are relational databases, possibly from many different vendors, and PDM databases, also from several vendors. Relational databases, or RDBs, can be accessed by the SQL, an international standard that allows the interoperability of different RDB products in general. On the other hand, PDM databases, the data-stores for Product Data Management software, are not as inter-operable as RDBs, since the product-specific set of APIs has to be used to access them. An SQL-like language and a parser framework have been introduced to solve this problem. By implementing the parser as an object-oriented framework, the workload to adapt to many PDM products has been greatly reduced. The design and preliminary implementation has been carried out in a government-sponsored CALS project in Japan, and has been proven viable in the field, where a large steel-making company gathering information from many subordinate companies around the steel plant, and from other steel companies and equipment manufacturers.

The Web is a collection of multimedia documents in the form of HTML pages connected through hyperlinks. Unlike most search engines, which focus on information retrieval based on keywords, WebDB aims at supporting database-like comprehensive query functionalities as well navigation, and document generation functionalities with customizability. To support hypermedia database functionalities, we augment the traditional concepts of tables in relational databases and classes in object-oriented databases with notions of document formats and navigation. We design WQL (Web Query Language) as an HTML document manipulation language. WQL language statements contain two parts: SELECT. . . FROM. . . WHERE clauses for specifying retrieval of data contents from hypermedia databases and CREATE. . . AS. . . clauses for specifying the output HTML format and navigation of the query results. This paper presents the architecture of WebDB and its functionalities. The extension to SQL for hypermedia document manipulation, query, and navigation and implementation on NEC PERCIO OODBMS are described in detail.

Digital logic frequency detector whose operation is based on the analog quadricorrelator is presented. Proposed circuit consists of conventional digital logic devices without an alog elements. Therefore, it has superior reliabilities over component drifts or aging effects. Frequency linear discrimination range is 100% of the reference clock rate.

We present a receiver structure with joint blind equalization, carrier recovery, and timing recovery. The blind equalizer employs a decomposition transversal filtering technique which can reduce the complexity of convolution to about a half. We analyze the performance surface of the equalizer cost function and show that the global minima correspond to perfect equalization. We also derive proper initial tap settings of the equalizer for convergence to the global minima. We describe the timing recovery and the carrier recovery methods employed. And we describe a startup sequence to bring the receiver into full operation. The adaptation algorithms for equalization, carrier recovery, and timing recovery are relatively independent, resulting in good operational stability of the overall receiver. Some simulation results for cable-modem type of transmission are presented.

In order to exploit fully the frequency diversity benefits of multicarrier modulation (MCM), and the very nature of the frequency selective radio channel, we investigate an erasure decoded π/4 QDPSK MCM (ED-MCM) by employing simple Hamming (block) code. We propose the threshold-free criteria, i. e. relative minimum receive power test (RMRPT) and relative maximum decision error test (RMDET) for erasure generation and evaluate ED-MCM's performance by applying these tests to average received power, average decision error, instantaneous symbol/bit decision errors. At a normalized delay spread of 1/64, computer simulation results indicate a coding gains of 6.0 - 7.0 dB with ED-MCM at a BER of 10-3. RMDET/RMRPT based erasure decoding yields a 1.5 - 2.5 dB improvement over the conventional forward error correction (FEC) decoding at a BER of 10-5. The simulation results at other normalized delay spreads, i. e. , 1/32, 1/16 are also obtained. The erasure criteria (RMRPT and RMDET) applied to average values of received power/decision error yield consistently better performance over error only decoding. The results indicate that the erasure decoding based on relative (threshold-free) measures clearly promises an improved performance of the MCM system.

This paper proposes a multiple open-loop frequency estimation scheme based on differential detection for M-ary phase shift keying (MPSK), which accomplishes fast initial acquisition, precise frequency estimation and wide frequency coverage at the same time. The proposed scheme, which has a good trade-off between complexity and performance, operates as follows: 1) it consists of several frequency error detectors (FEDs) based on differential detection with different delays; 2) it precisely estimates frequency in a wide range (the same range of one symbol differential detection) by open-loop according to frequency errors detected by the FEDs. For real-time symbol-by-symbol operation in order to track fast time-varying frequency, it has a smaller complexity than the other frequency estimation schemes. It is confirmed by analysis, numerical calculation and computer simulation that the frequency estimation error of the proposed scheme is close to the Cramer-Rao lower bound (CRLB) (asymptotic degradation of the proposed scheme from the CRLB is about 0. 5 dB) while keeping a wide frequency coverage and this scheme can track fast time-varying frequency.

In geographical databases for navigation, users raise various types of queries concerning route guidance. The most fundamental query is a shortest-route query, but, as dynamical traffic information newly becomes available and the static geographical database of roads itself has grown up further, more flexible queries are required to realize a user-friendly interface meeting the current settings. One important query among them is a detour query which provides information about detours, say listing several candidates for useful detours. This paper first reviews algorithms for the shortest and k shortest paths, and discusses their extensions to detour queries. Algorithms for finding a realistic detour are given. The efficiency and property of the algorithms are examined through experiments on an actual road network.

This paper focuses on the problems how to organize and retrieve video data in an effective manner. First we identify several issues to be solved for the problems. Next, we overview our current research results together with a brief survey in the research area of video databases. We especially describe the following research results obtained by the the Japanese Ministry of Education under Grant-in-Aid for Scientific Research on Priority Area: "Advanced Databases" concerned with organization and retrieval of video data: Instance-Based Video Annotation Models, Self-Organization of Video Data, and A Query Model for Fragmentally Indexed Video.

Decision trees are used as a convenient means to explain given positive examples and negative examples, which is a form of data mining and knowledge discovery. Standard methods such as ID3 may provide non-monotonic decision trees in the sense that data with larger values in all attributes are sometimes classified into a class with a smaller output value. (In the case of binary data, this is equivalent to saying that the discriminant Boolean function that the decision tree represents is not positive. ) A motivation of this study comes from an observation that real world data are often positive, and in such cases it is natural to build decision trees which represent positive (i. e. , monotone) discriminant functions. For this, we propose how to modify the existing procedures such as ID3, so that the resulting decision tree represents a positive discriminant function. In this procedure, we add some new data to recover the positivity of data, which the original data had but was lost in the process of decomposing data sets by such methods as ID3. To compare the performance of our method with existing methods, we test (1) positive data, which are randomly generated from a hidden positive Boolean function after adding dummy attributes, and (2) breast cancer data as an example of the real-world data. The experimental results on (1) tell that, although the sizes of positive decision trees are relatively larger than those without positivity assumption, positive decision trees exhibit higher accuracy and tend to choose correct attributes, on which the hidden positive Boolean function is defined. For the breast cancer data set, we also observe a similar tendency; i. e. , positive decision trees are larger but give higher accuracy.