This paper develops a closed form approximation method for the mean performance measures in a single-server priority queue with batch arrivals of two classes. The batch arrivals queueing model considered here is an extension of the previously analyzed models and it has a potential applicability in packet communication systems. The interarrival time of batches, batch size (the number of customers) and service time of customers are assumed to have a general distribution for each priority class. The head-of-the-line (HL) and preemptive-resume (PR) rules are considered. Qualitative characterization results are presented through a flow-balance argument. Especially, important relationships between the mean performance measures are derived, which enable us to make an approximation. Using a diffusion approximation for the unfinished work and its refinement, and using the qualitative results, new approximate formulas for the mean performance measures, e.g., mean delay time of each priority class are obtained. Some numerical examples are provided and compared with exact and simulation results, confirming the accuracy of the approximation. The proposed approximate formulas are shown to be exact if the arrival streams for both classes are batch Poisson processes.
Masahiro KAWAKITA Takahiro WATANABE
It has been a main subject to reduce design time and cost not only in the field of digital LSI layout but also in the field of analog LSI, due to increasing LSI packing density and circuit complexity. Semicustom approaches are insufficient to design analog LSIs which require higher density chips and have many kinds of design specifications. As for custom approaches, a symbolic layout method is widely used, where an automatic compaction serves to shrink its chip size after placement and routing. However, most of analog LSIs are fabricated by bipolar process technology, which has many kinds of devices with various shaped patterns. And besides, there are many layout specifications, which are peculiar to analog LSIs and directly affect to circuit performance. So, it is necessary taking account of the layout specifications not only for placement and routing but also for compaction. This paper describes an approach for analog compaction. Given a layout pattern of placement and routing satisfying layout specifications, various techniques to take account of such specifications in a compaction method are discussed. This paper also proposes a clean-up function after compaction, which reduces detoured wire patterns and removes unnecessary vias. By the compaction with clean-up function, a final layout pattern becomes refined in quality.
Goichi OOTOMO Kousuke TSUKAMOTO Takeshi WATAHIKI Takeo MIYATA
This paper describes an A/D converter for signal processing applications which has a floating point format. This converter has been implemented using CMOS switches, an operational amplifier, a comparator, a binary weighted capacitor-array, and D/A converter for calibration. A 13-bit accuracy has been achieved with the self-calibration technique although the capacitor-array used has a 9-bit accuracy. Also other errors like stray capacitances, charge injection of the CMOS switches etc. are compensated by calibration circuit.
Fumio UENO Takahiro INOUE Kenichi SUGITANI Shinji ARAKI
New cyclic switched-capacitor (SC) D/A and A/D converters are proposed. In the former, a capacitor-mismatch-compensation technique using additional small capacitors is introduced. With this, a capacitor ratio accuracy as high as twelve bits is possible. And, in the latter, the A/D conversion with ten-bit accuracy is realizable by the simple ratio-independent circuit consuming only a few number of clock cycles for each bit conversion.
Takahiro INOUE Fumio UENO Satoru SONOBE
Switched capacitor (SC) circuits for realizing piecewise-linear S- and Z-shaped variable threshold functions are proposed. With these circuits, basic nonlinear functions in fuzzy logic and neural networks can be synthesized in the form suitable for MOS VLSIs.
Kenji SHIBATA Yoshihiro UEDA Satsuki YUYAMA Haruo HASEGAWA
This paper gives a verification method of a service specification in a communication system by utilizing Petri net. We define a service specification and clarify the feature of the specification. And we discuss a relation between a service specification and Petri net which represents the specification. Furthermore, this paper describes some kinds of verification for the specification and shows several examples. We are now developing a software support system-EXPRESS (EXPeRt system for ESS). EXPRESS designs automatically the service specification from user's requirements. In EXPRESS, each requirement is converted into ISG (Individual Service Graph) and all ISGs are integrated into TSG (Total Service Graph). TSG is the final service specification. ISG and TSG are described by using Petri net. Petri net is used for modeling a communication protocol and an asynchronous system. A service starts from an idle state and returns to the same idle state in a communication system. This means that a service specification should have a t-invariant. And a t-invariant which can not be decomposed is called a prime service. The followings are needed for verification of the specification: verification of ISG, detection of ISG from TSG and detection of other prime services than ISG. These are verified by utilizing an analysis of Petri net.
Tetsurou FUJII Naohisa OHTA Yukiharu KANAYAMA Sadayasu ONO
This paper discusses the architecture and performance of parallel digital signal processing with a multicomputer system. A digital signal processor (DSP) system, called NOVI, has been developed to examine various methods for organizing parallel DSP systems, and for developing parallel programs for a wide range of digital signal processing applications. NOVI adopts multicomputer architecture and presently consists of 36 processing elements (PEs). Its parallel program development assistant (PDA) system facilitates powerful debugging functions to monitor all PEs without any interference in the parallel program execution. A load balancing technique for a multicomputer type DSP is also discussed, focusing on low bit rate motion picture coding. Finally, an example of the measured performance of the NOVI system is presented.
A new class of numerical integral operator for indefinite integral is first derived using piecewise-linear transform. The operator is a matrix by which the piecewise-linear transforms of functions are converted into the transforms of their integrals. The operator is then modified to cover definite integrals. The definite integral operator is a simple row vector. Application of the new operators to integral equations yields simple algebraic solutions for both Volterra's and Fredholm's equations. Initial value and boundary value problems of linear differential equations can also be solved by the use of the new integral operators through the solution of integral equations. The new operators provide wider range of applications with high accuracy than the existing methods using Walsh transform.
A comparison is made for the performance of the relaxation-based circuits simulation algorithms: the iterated timing analysis, the waveform relaxation and the waveform relaxation-Newton, along with the investigation of the following aspects of the convergence properties of these algorithms: (1) variations in their convergence rate with an employed relaxation method, (2) the difference between the speed of convergence of the waveform relaxation and that of the waveform relaxation-Newton, (3) influence of the presence of feedback loops on their convergence rates. In addition the following techniques are surveyed that improve the speed of these algorithms: (1) circuit partitioning, (2) a windowing approach, (3) latency exploitation, (4) iterative stepsize refinement, (5) parallel processing approach.
We analyze the performance of QPSK systems using complex transversal filters with decision-feedback (DF) taps in the presence of multiple continuous wave (CW) interference and Gaussian noise. The general analytic expressions for the optimum tap weights and minimum mean square errors in the presence of multiple CW interference for both one-sided and two-sided transversal filters with and without DF taps are derived. We find that the output signal-to-noise ratio (SNR) of the one-sided DF filter is most improved among the four types of the filter structures and that multiple CW interference can be almost completely rejected. We also consider the transient behavior of the DF filters in the presence of multiple CW interference. It is found that the magnitudes of the tap weights are proportional to the relative multiple interference power ratios, while they converge to their corresponding steady-state values with the equal rate. It is also found that one-sided DF filter has shorter setting time compared to two-sided DF filter.
Kenji NAKAYAMA Atsushi IWATA Takeshi YANAGISAWA
Analog signal processing is important for the following reasons. There exist many analog environments, and integrated analog circuits have several advantages over digital circuits. On the other hand, a digital approach can provide another features, such as accurate operation and programmability. Therefore, both circuits are effectively combined, resulting in high performance LSIs. This tutorial paper provides an overview for the recent and future trends in design and applications of integrated analog signal processing circuits. First, design techniques are reviewed for operational amplifier (Op-Amp), monolithic bipolar active RC circuits, switched-capacitor (SC) circuits, continuous-time MOS circuits, and analog-to-digital converter (ADC). High frequency filter realization, up to 100 MHz, has been tried by bipolar active RC circuits and GaAs circuits. Improved design techniques for SC circuits have been proposed. They include noise cancellation and building blocks with reduced sensitivity to nonideal Op-Amp performance. In order to overcome some SC circuit drawbacks due to a sampled data circuit, continuous-time MOS circuits have been proposed. Successful results have been obtained by using an automatic tuning method. A multi-stage noise shaping ADC is very useful to integrate an accurate ADC. A high signal-to-noise ratio (SNR), more than 91 dB, was obtained by the three-stage ADC, which can be applied to digital audio system. Automatic design and fabrication processes are also important aspects. Silicon compilers for SC circuits are overviewed. Systematic design rule, by which a globally optimum solution can be obtained, requires further investigation. A mixed analog/digital master slice LSI has been proposed to simplify an LSI customizing process. A voice-band MODEM LSI has been developed, resulting in good filter responses and SNR. Finally, promising applications of integrated analog circuits are briefly reviewed. Analog circuits are superior to a digital version in operating speed, power dissipation and integration density. In actuality, however, both approaches will be combined, resulting in mixed analog/digital LSIs where both circuits supplement each other's excellent features and negate drawbacks.
Fractals have been widely applied to picture processings and related fields. They have been particularly successful as computer graphics tools. However, fractal applications to image analysis have not been successful. Because,conventional fractal feature--fractal dimension (F-dim)--is scalar valued, and it is difficult to characterize various image information using the conventional F-dim. In this paper, a new concept of a fractal feature is proposed to overcome the above drawback. The conventional F-dim satisfies a kind of scaling equation. The new fractal feature is a generalization of the conventional F-dim and is defined as a matrix (F-matrix) satisfying the vector scaling equation. The parameter estimation procedure for the F-matrix is also discussed. Texture image analysing experiments were conducted to investigate effectiveness of the F-matrix as an image feature. The main results show that: (1) many texture images fit the F-matrix model well, (2) the F-matrix contains various information that characterize texture images, (3) the F-matrix was useful for texture classification, a 93.8% recognition rate is obtained for 65 samples in 13 categories.
Hiroshi MASUYAMA Tetsuo ICHIMORI Okihiko ISHIZUKA
This paper presents an optimum design method of reliable networks. This paper, first, discusses several design methods for undirected graphs. It is shown that one new method of them gives graphs with the minimum diameter in a certain domain. In order to obtain optimum graph when the number of nodes and degree are given, this paper next discusses a method to obtain modified graphs with larger connectivity and also with the minimum diameter from known graphs which have diameter 1 over the minimum.
A new pulse-width-modulation (PWM) circuit is developed for high efficiency, bidirectional drive of dc servo motors. The circuit generates the positive- and negative-going sweeps shifted each other in time by a half period of the repetition frequency. Compared with these sweeps, a control input is converted into the PWM signal which drives a motor in a push-pull manner. This method of driving a motor consumes no power when it is at rest and reduces the switching loss of power stage to a half that of a conventional PWM scheme. An efficiency higher than 90% is achieved by a prototype PWM driver using power MOSFET's for the switching frequency lower then 60 kHz. Simultaneous conduction of two complementary power transistors in each leg of a power bridge, and thus the short-circuit current, never occurs because of the phase-shift in the two sweeps. Besides the high efficiency, the new scheme features wide dynamic range made possible by nonlinear PWM process.
Katsuhiko TANAKA Hiroyuki SETO Michihiro MURATA
High velocity of more than 20 m/sec and moving direction are measured by using differential signal process. Principles of operation and basic data are presented.
This paper describes a top-down floorplanning scheme for VLSI chips which is constructed on the basis of a heuristic algorithm and an interactive placement improvement process in conjunction with a knowledge-based expert systems approach. This scheme determines not only relative positions of the modules to be mounted on a chip but also shapes and areas of modules, according to specifications imposed on the total chip area, aspect ratios of modules, wire lengths of specific nets, electrical performances, and so forth. Several implementation results are also shown to reveal the performance of this scheme.
Hiroshi OCHI Shigenori KINJYO Noriyoshi KAMBAYASHI Seiki KYAN
The important problems in IIR adaptive equalizers are stability of the adaptive IIR filters and unimodality in the error surface. In this report we propose a new IIR adaptive equalizer which assures the unimodality and the stability.
Kiyonori YOSHIDA Yasuhiko SAITOU
If a Hankel matrix H is constituted by coefficients of x-i in a(x)/f(x), then H-1=B[f, b] were a(x)b(x)=1 mod f(x), and B is a Bezoutiant. We show this fact, and apply it to a calculation of a dual base in GH(pn).
Yoshifumi MANABE Makoto IMASE Terunao SONEOKA
The problem of constructing a reliable and efficient routing ρ in a communications network G is considered. The forwarding index ξ(G, ρ), which is defined as the maximum number of routes which pass through each node, is a criterion of network efficiency. The diameter of the surviving route graph D(R(G, ρ)/F), which is defined as the maximum number of surviving routes needed for communication between each pair of nodes if node and edge faults F occur, is a criterion of network reliability. Routings which minimize ξ(G, ρ) and D(R(G, ρ)/F) are needed. In this paper the following are shown: (1) A sufficient condition for k-connected digraphs (k2, 4) to have a routing ρ such that D(R(G, ρ)/F)6 for |F|k. (2) A method of constructing a digraph G and routing ρ2 such that ξ(G, ρ2)2logdn for any number of nodes n and maximum degree d. (3) A method of constructing a digraph G and routing such that ξ(G, ρ2)3logdn and D(R(G, )/F)3 for |F|d-1 if nd4 and d3.