Dr-Jiunn DENG Ruay-Shiung CHANG
IEEE 802. 11 is a standard for wireless LANs. The basic access method in its MAC layer protocol is the distributed coordination function (DCF) for the ad hoc networks. It is based on the mechanism of carrier sense multiple access with collision avoidance (CSMA/CA). DCF is used to support asynchronous data transmission. However, frames in DCF do not have priorities, making it unsuitable for real-time applications. With a little bad luck, a station might have to wait arbitrarily long to send a frame. In this paper, we propose a method to modify the CSMA/CA protocol such that station priorities can be supported. The method is simple, efficient and easy to implement in comparison to point coordination function (PCF), another access method in IEEE 802. 11 based on access points (base stations). Simulations are conducted to analyze the proposed scheme. The results show that DCF is able to carry the prioritized traffic with the proposed scheme.
Nobutaro SHIBATA Hiroshi INOKAWA Keiichiro TOKUNAGA Soichi OHTA
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.
Masatoshi ARIKAWA Shinji SHIMOJO Akira AMANO Kaori MAEDA Reiji AIBARA Kouji NISHIMURA Kaduo HIRAKI Kazutoshi FUJIKAWA
This paper proposes a new framework of managing virtual spaces based on spatial databases as an extension of VRML-based systems. The framework is suitable for treating continuous virtual spaces and for managing the quality of service (QoS) of the virtual spaces depending on user's operations and situations of computer resources. Levels of detail (LoD) of 3D objects is the most important rule for rendering scenes dynamically while managing the QoS. This paper describes a method of managing the QoS depending on the LoD in the form of spatial queries. An advantage of the framework is that spatial databases can incrementally construct virtual spaces in clients using differential descriptions based on VRML, that is, DVRML, proposed in this paper. Dynamic spatial data such as avatar's movement and real-time multimedia data such as videos should be shared by all participants in a virtual space in real time. Our framework can also handle dynamic spatial data by means of real-time updating of some spatial objects in spatial databases as well as static spatial data. We developed some experimental applications based on the framework in order to prove that it is feasible for networked virtual spaces with video components.
Jun AMAGAI Hiroo KUNIMORI Hitoshi KIUCHI
We investigated a radio interferometer for geodetic use that incorporates commercially available fiber-optic links modulated in the radio-frequency range, and a method for compensating for the delay occurring in the links. With this type of radio interferometer, we can perform baseline analysis without the need for estimating the clock difference between observation stations, which causes a relatively large error in the vertical component of the estimated position of the station. Another advantage of the interferometer is utilization of phase delay, which improves the accuracy of delay determination considerably. By analyzing the interferometer's signal-to-noise ratio, we estimated the practicable cable length to be 58.0 km. The results of preliminary experiments with short optical fiber links show that the differences in the cable delays of the fiber-optic links can be compensated for by calibration signals which make a round trip between the analysis station and the observation sites, and that phase delay can be measured successfully.
Akira KAWAGUCHI Kui W. MOK Calton PU Kun-Lung WU Philip S. YU
Epsilon serializability (ESR) was proposed to relax serializability constraints by allowing transactions to execute with a limited amount of inconsistency (ε-spec). Divergence control algorithms, viewed as extensions of concurrency control algorithms, enable read-only transactions to complete if their inconsistencies do not exceed ε-spec. This paper studies the performance of two-phase locking divergence control (2PLDC) and optimistic divergence control (ODC) algorithms. We develop a central part of the ESR transaction processing system that runs with 2PLDC and ODC. We applied a comprehensive centralized database simulation model to measure the performance. Evaluations are conducted with multi-class workloads where on-line update transactions and long-duration queries progress under various ε-spec. Our results demonstrate that significant performance enhancements are achieved with a non-zero tolerable inconsistency. With sufficient ε-spec and limited system resources, both algorithms result in comparable performance. However, with low resource contention, ODC performs significantly better than 2PLDC. Furthermore, in the range of small ε-spec, the queries committed by ODC have more accurate results than those committed by 2PLDC.
Toshiyuki MORITA Yasunori ISHIHARA Hiroyuki SEKI Minoru ITO
Detecting security flaws is important in order to keep the database secure. A security flaw in object-oriented databases means that a user can infer the result of an unpermitted method only from permitted methods. Although a database management system enforces access control by an authorization, security flaws can occur under the authorization. The main aim of this paper is to show an efficient decision algorithm for detecting a security flaw under a given authorization. This problem is solvable in polynomial time in practical cases by reducing it to the congruence closure problem. This paper also mentions the problem of finding a maximal subset of a given authorization under which no security flaw exists.
Internet users have become well acquainted with the World Wide Web (WWW) system, and WWW has become the most significant service on the Internet. In the near future, the importance of large scale hypermedia database systems based on WWW technologies is expected to continue to increace. The present study focuses on the issue of managing hyperlink integrity constraints on WWW like hypermedia database systems. After formally defining path existence constraint definitions(PEDs) using intuitive examples, we apply the notion of PEDs to represent hyperlink integrity constraints. Intuitively, a PED can be used to represent the following integrity constraint. If a reference path exists in a given database, then another corresponding reference path must also exist. An outline of a prototype hypermedia database system, AYATORI, which is based on the proposed model and under development, is also mentioned.
Let f be a one-to-one encryption function. Given f(m) and a string K, can we efficiently determine whether m contains K as a substring or not? We investigate the computational complexity of this problem, and show that it is equivalent to not only computing f-1 but also counting the number of K contained as substrings in m. Thus it is not determined in polynomial-time if f is in fact one-way.
Kiyoshi KOBAYASHI Tomoaki KUMAGAI Shuji KUBOTA Shigeaki OGOSE Takeshi HATTORI
This paper proposes a new cell station (CS) configuration for personal communication systems. The proposed CS employs a modified coherent demodulator with 4-branch maximal ratio combining diversity and a burst-by-burst automatic frequency control (AFC) to enhance the coverage. The proposed CS also employs an antenna-sharing diversity transmission to incorporate more than one transceiver block into a small unit with high power efficiency. With these techniques, the BER performance of the uplink control channel (CCH) is flattened regardless of carrier frequency errors within 12 kHz; the diversity gain of uplink traffic channel (TCH) is improved by 2 dB; the downlink transmission power is reduced by 1.9 dB.
Michio TONAMI Shuji HARASHIMA Noriyoshi WATANABE Toshiki KOBAYASHI Kozo NAGAI
This paper introduces a material management system for newspapers that was developed for The Yomiuri Shimbun. Material transferred to the system is stored in a material database and sent to terminals located in the related sections. The material can be processed effectively just by checking information on the terminals. Special requirements for this system will be discussed first in the paper, then problem-solving will be explored.
This paper presents a high-level test synthesis algorithm for operation scheduling and data path allocation. Data path allocation is achieved by a controllability and observability balance allocation technique which is based on testability analysis at register-transfer level. Scheduling, on other hand, is carried out by rescheduling transformations which change the default scheduling to improve testability. Contrary to other works in which the scheduling and allocation tasks are performed independently, our approach integrates scheduling and allocation by performing them simultaneously so that the effects of scheduling and allocation on testability are exploited more effectively. Additionally, since sequential loops are widely recognized to make a design hard-to-test, a complete (functional and topological) loop analysis is performed at register-transfer level in order to avoid loop creation during the integrated test synthesis process. With a variety of synthesis benchmarks, experimental results show clearly the advantages of the proposed algorithm.
We introduce a new methodology for designing block ciphers with provable security against differential and linear cryptanalysis. It is based on three new principles: change of the location of round functions, round functions with recursive structure, and substitution boxes of different sizes. The first realizes parallel computation of the round functions without losing provable security, and the second reduces the size of substitution boxes; moreover, the last is expected to make algebraic attacks difficult. This structure gives us a simple and effective method for designing secure and fast block ciphers in hardware as well as in software implementation. Block encryption algorithm MISTY was designed on the basis of this methodology.
The applicability of composite materials containing laminar solid lubricants to sliding contacts was studied. Performances of several composite materials prepared by incorporating solid lubricants with the basic alloys of the Cu-Nb system and Cu-Sn system were investigated to test the suitability of the composite materials as sliding contacts. As a result, it was clarified that the composite materials based on Cu-Sn alloy were superior to those based on Cu-Nb alloy and those containing only WS2 and not MoS2 were more effective in reducing both the contact resistance and the coefficient of friction. Based on the relationship between the contact resistance and the coefficient of friction obtained in this experimental study, the author proposed a new model for electric contact of composite materials.
Simple expressions for constriction resistance of multitude conducting spots were analytically formulated by Greenwood. These expressions, however, include some approximations. Nakamura presented that the constriction resistance of one circular spot computed using the BEM is closed to Maxwell's exact value. This relative error is only e=0. 00162 [%]. In this study, the constriction resistances of two, five and ten conducting spots are computed using the boundary element method (BEM), and compared with those obtained using Greenwood's expressions. As the conducting spots move close to each other, the numerical deviations between constriction resistances computed using Greenwood's expressions and the BEM increase. As a result, mutual resistance computed by the BEM is larger than that obtained from Greenwood's expressions. The numerical deviations between the total resistances computed by Greenwood's expressions and that by the BEM are small. Hence, Greenwood's expressions are valid for the total constriction resistance calculation and can be applied to problems where only the total resistance of two contact surfaces, such as a relay and a switch, is required. However, the numerical deviations between the partial resistances computed by Greenwood's expression and that by the BEM are very large. The partial resistance calculations of multitude conducting spots are beyond the applicable range of Greenwood's expression, since Greenwood's expression for constriction resistance of two conducting spots is obtained by assuming that the conducting spots are equal size. In particular, the deviation between resistances of conducting spots, which are close to each other, is very large. In the case of partial resistances which are significant in semiconductor devices, Greenwood's expressions cannot be used with high precision.
Yasuo EBARA Toshiaki KOIZUMI Hideaki SONE Yoshiaki NEMOTO
The authors observed the correlation between electromagnetic noise and trace of discharge on surface for various surface areas of Cu in opening copper (Cu)-carbon (C) electrodes. In the case of Cu (anode)-C (cathode), the duration of sporadic burst noise generated by discharge becomes longer when Cu surface area is increased, and trace of discharge (melting area) distribute widely on electrodes. Also the forms of the burst noise in the start of arc are classified, and the traces of discharge correspond to each forms. The forms of the burst noise depend on the pattern which the trace of discharge are formed. As these results, the authors showed the correlation between form of burst noise and trace of discharge on electrode surface.
This paper proposes genetic algorithms (GAs) for path planning and trajectory planning of an autonomous mobile robot. Our GA-based approach has an advantage of adaptivity such that the GAs work even if an environment is time-varying or unknown. Therefore, it is suitable for both off-line and on-line motion planning. We first presents a GA for path planning in a 2D terrain. Simulation results on the performance and adaptivity of the GA on randomly generated terrains are shown. Then, we discuss an extension of the GA for solving both path planning and trajectory planning simultaneously.
Akihisa CHIKAMURA Koji NAKAMAE Hiromu FUJIOKA
we evaluate the effect of express lots on production dispatching rule scheduling and cost in VLSI manufacturing final test process. In the assignment of express lots, we make comparisons of two rules, First In First Out (FIFO) rule which is widely used and WEIGHT+RPM rule which considers the time required for jig and temperature exchanges, the remaining processing time of the machine in use and the lot waiting time in queue. When using FIFO rule, the test efficiency begins to deteriorate and the test cost per chip begins to increase, if the content of express lots exceeds 15%. Furthermore, for 30% of express lots' content, the number of total processed lots decreases by 19% and the test cost per chip increases by 22% in comparison to the cases including no express lots. For WEIGHT+RPM rule, however, the test efficiency does not deteriorate and the test cost per chip does not increase even if the content of express lots is increased up to 50%. When we use WEIGHT+RPM rule, Express Lots Tolerances (ELTs), defined as the maximum content of express lots which permits the deterioration of the system characteristics by 5%, are about three times as high as ones when using FIFO rule. It is also found that WEIGHT+RPM rule maintains higher ELTs against the changes in the numbers of planned chips and prepared jigs as compared with FIFO rule.
Kagehiro ITOYAMA Takeshi YANOBE
This paper proposed the method as an estimation on the size of discharge spots through observation on traces after the discharge arose in circumstances gases mixed hydrocarbon gas. Namely, the circular carbonaceous deposit and the carbonaceous heap are observed on cathode and anode surface, respectively, after the short gap discharge arises in N2+NO+CH4 gases. The current density, which is the normal conversion current density, is calculated from the size of the trace of discharge and its value is about 1.010-9 A/(cm2 Pa2) in case that the concentration of CH4 is 0.6%. The value is about 1/5 of values that are reported in the former articles and is reasonable one.
To provide users with database-like query interfaces on HTML data, several systems have been developed to extract structures from HTML pages. Among them, tree-like structures and path expressions are the most popular modeling and navigating tools, respectively. Although path expressions are straightforward in representing top-down search patterns, they provide very limited help in representing bottom-up and in-breadth search patterns. In this paper, a lattice model is proposed to store Web data. The model provides an integrated mechanism to store text, linking information, HTML hierarchy, and sequence order of HTML data. By incorporating lattice operators with comprehension syntax, we show that the query language can represent top-down, bottom-up, and in-breadth searching patterns with uniform operators. It will be also shown that lattice comprehensions can represent all operators of path expressions, except Kleen closure.
Hiroshi SUNAGA Tetsuyasu YAMADA Kenji NISHIKAWARA Tatsuro MURAKAMI
The productivity of developing software for switching systems and the effects of using advanced software development methods were evaluated and analyzed. Productivity was found to be improved by using automatic code generation, simulator debugging, a hierarchical object-oriented software structure, and software-development-support tools. The evaluation showed that the total productivity was improved by about 20%, compared with a case where these efforts were not introduced. It also showed each effect of these methods and tools by evaluating their manpower saving ratios. These results are expected to benefit the development of various types of communication-switching and multimedia service systems. Also, our development-support tools and methods are expected to be the basis for attaining higher software development productivity.