The traceability of data flow diagrams against structure charts is very important for large software development. Specifying if there is a relationship between a data flow diagram and a structure chart is a time consuming task. Existing CASE tools provide a way to maintain traceability. If we can extract the input-output relationship of a system from a structure chart, the corresponding data flow diagram can be automatically generated from the relationship. For example, Benedusi et al. proposed a reverse engineering methodology to reconstruct a data flow diagram from existing code. The methodology develops a hierarchical data flow diagram from dependency relationships between the program variables. The methodology, however, transforms each module in structure charts into a process in data flow diagrams. The reconstructed diagrams may have different processes with the same name. This paper proposes a transformation algorithm that solves these problems. It analyzes the structure charts and extracts the input and ouput relationships, then determines how the set of outputs depends on the set of inputs for the data flow diagram process. After that, it produces a data flow diagram based on the include operation between the sets of output items. The major characteristics of the algorithm are that it is simple, because it only uses the basic operations of sets, it generates data flow diagrams with deterministic steps, and it can generate minimal data flow diagrams. This process will reduce the cost of traceability between data flow diagrams and structure charts.

Distributed computing over a network of workstations continues to be an illusive goal. Its main obstacle is the delay penalty due to network protocol and OS overhead. We present in this paper a low level hardware supported scheme for managing distributed shared memory (DSM), as an underlying paradigm for distributed computing. The proposed DSM is novel in that it employs a two-tier paging scheme that reduces the probability of false sharing and facilitates an efficient hardware implementation. The scheme employs a standard OS page and divides it into fixed smaller memory units called paragraphs, similar to cache lines. This scheme manages the shared data regions only, while other regions are handled by the OS in the standard manner without modification. A hardware extension of a traditional MMU, namely Distributed MMU or DMMU, is introduced to support the DSM. Shared memory coherency is maintained through a write-invalidate protocol. An analytical model is built to evaluate the system sensitivity to various parameters and to assess its performance.

In this paper, we presented an analysis of single and coupled microstrip lines covered with protective dielectric film which is usually used in the microwave integrated circuits. The method employed in the characterization is called partial-boundary element method (p-BEM). The p-BEM provides an efficient means to the analysis of the structures with multilayered media or covered with protective dielectric film. The numerical results show that by changing the thickness of the protective dielectric films such as SiO2, Si and Polyimide covered on these lines on a GaAs substrate, the coupled microstrip lines vary within 10% on the characteristic impedance and within 25% on the effective dielectric constant for the odd mode of coupled microstrip line, respectively, in comparison with the structures without the protective dielectric film. In contrast, the single microstrip lines vary within 4% on the characteristic impedance and within 8% on the effective dielectric constant, respectively. The protective dielectric film affects the odd mode of the coupled lines more strongly than the even mode and the characteristics of the single microstrip lines.

A bottleneck identification methodology is proposed for the performance-oriented design of shared-bus multiprocessors, which are composed of several major subsystems (e.g. off-chip cache, bus, memory, I/O). A subsystem with the longest access time per instruction is the one that limits processor performance and creates a bottleneck to the system. The methodology also facilitates further refined analysis on the access time of the bottleneck subsystem to help identify the causes of the bottleneck. Example performance model of a particular shared-bus multiprocessor architecture with separate address bus and data bus is developed to illustrate the key idea of the bottleneck identification methodology. Accessing conflicts in subsystems and DMA transfers are also considered in the model.

A rat-race hybrid-ring which includes a coupled-line called microwave C-section is proposed for size reduction. The perfect input match, isolation, equal power split and certain phase differences between two output ports can be satisfied at center frequency as in a normal hybrid-ring. The size of the proposed circuit becomes smaller than that of a normal rat-race built up with a folded non-coupled 3/4-wavelength transmission line, although the frequency characteristics are slightly damaged by the electromagnetic coupling between two folded strips. Theoretical results based on the even and odd mode decomposition method are in good agreement with those of the experimental circuit fabricated at 1 GHz.

This paper proposes a high throughput small latent IP packet delivery architecture using ATM technology in a large scaled internet. Data-link network segments, including ATM network segments, are interconnected through routers. A connection oriented IP packet delivery will be provided by IP (including both IPv4 and IPv6) with a certain resource reservation protocol (e.g. RSVP). When the router attached to ATM network segment has a mapping function between the flow-ID (e.g. in the SIPP header) and the VPI/VCI value, the small latent connection oriented IP forwarding can be provided. Also, when the router has cell-relaying functionality, the small latent connectionless IP forwarding can be provided, even in IPv4. The source router, where the source end-station belongs to, will be able to transfer the connectionless IP packet to the destination router, where the destination end-station belongs to, through the concatenated ATM connections (ATM-VCCs) without any ATM-VCC termination point. When all of the network segments are ATM-LAN, the proposed architecture can accommodate about up to 222 (4106) end-stations with two network layer processing points. And when the network is scaled up hierarchally, we can accommodate larger number of end-stations. For example, we can accommodate 1015 end-stations by a three layered network. Then the maximum number of actual network layer processing points between source and destination end-stations can be ten. Here, 1015 is the maximum number of end-stations in ISDN and also it is the target number of accommodated end-stations for IPv6.

This paper deals with a high-speed digital circuit for discrete cosine transform (DCT). We propose a new algorithm that reduces the number of calculations for partial sum-of-products in the DCT and synthesize the small gate depth circuit of DCT by using carry-propagation-free adders based on redundant binary {1,0,1} representation. The gate depth is only half to one third that of the conventional algorithms with the same number of gates.

Concerning the complexity of tree drawing, the following result of Supowit and Reingold is known: the problem of minimum drawing binary trees under several constraints is NP-complete. There remain, however, many open problems. For example, is it still NP-complete if we eliminate some constraints from the above set? In this paper, we treat tree-structured diagrams. A tree-structured diagrm is a tree with variably sized rectangular nodes. We consider the layout problem of tree-structured diagrams on Z2 (the integral lattice). Our problems are different from that of Supowit and Reingold, even if our problems are limited to binary trees. In fact, our set of constraints and that of Supowit and Reingold are incomparable. We show that a problem is NP-complete under a certain set of constraints. Furthermore, we also show that another problem is still NP-complete, even if we delete a constraint concerning with the symmetry from the previous set of constraints. This constraint corresponds to one of the constraints of Supowit and Reingold, if the problem is limited to binary trees.

Retiming is a technique to resynthesize a synchronous sequential circuit by rearranging flip-flops. In view of logic optimization, retiming can potentially derive a circuit which is more simplified and testable because retiming can convert several sequential redundancies into combinational redundancies. Retiming methods proposed before have no guarantee to generate the same output sequences when the circuit start from a specified initial state such as the reset state. If the circuit with a specified initial state must have the same output sequences after retiming, rearrangement of flip-flops should be restricted. This paper presents a retiming method for circuits with a specified initial state so that retimed circuits give the same output sequences of the original circuits for any input sequences. In the proposed method, during the procedure of retiming each flip-flop keeps a value corresponding to the initial state and unification of flip-flops with different value is avoided. Our procedures uses 5-valued logic on gate level implementation to describe and calculate the values of flip-flops. Therefore after optimization using our method, the circuit has completely the same behavior as that of the original. Experimental results for ISCAS'89 benchmark circuits show the method can be used to optimize the circuits as well as a method without considering the initial state. And testability of the retimed circuit is more enhanced than that of the original circuit.

Some undetectable stuck-at faults called the redundant faults are included in practical combinational circuits. The redundant fault does not affect the functional behavior of the circuit even if it exists. The redundant fault, however, causes undesirable effects to the circuit such as increase of delay time and decrease of testability of the circuit. It is considered that some redundant faults may cause the logical defects in the future. In this paper, firstly, we study the testability of the redundant fault in the combinational circuit by using delay effects. Secondly, we propose a method for generating a test-pair of a redundant fault by using an extended seven-valued calculus, called TGRF (Test-pair Generation for Redundant Fault). TGRF generates a dynamically sensitizable path for the target line which propagates the change in the value on the target line to a primary output. Finally, we show experimental results on the benchmark circuits under the assumptions of the unit delay and the fanout weighted delay models. It shows that test-pairs for some redundant faults are generated theoretically.

This paper describes new modeling methods combining neural network and hidden Markov model applicable to modeling a time series such as speech signal. The idea assumes that the sequence is nonstationary and is a nonlinear autoregressive process whose parameters are controlled by a hidden Markov chain. One is the model where a non-linear predictor composed of a multi-layered neural network is defined at each state, another is the model where a multi-layered neural network is defined so that the path from the input layer to the output layer is divided into path-groups each of which corresponds to the state of the Markov chain. The latter is an extended model of the former. The parameter estimation methods for these models are shown, and other previously proposed models--one called Neural Prediction Model and another called Linear Predictive HMM--are shown to be special cases of the NPHMM proposed here. The experimental result affirms the justification of these proposed models.

This paper describes a method for predicting the user's next utterances in spoken dialog based on the topic transition model, named TPN. Some templates are prepared for each utterance pair pattern modeled by SR-plan. They are represented in terms of five kinds of topic-independent constituents in sentences. The topic of an utterance is predicted based on the TPN model and it instantiates the templates. The language processing unit analyzes the speech recognition result using the templates. An experiment shows that the introduction of the TPN model improves the performance of utterance recognition and it drastically reduces the search space of candidates in the input bunsetsu lattice.

Recent works have shown that the size reduction of printed dipole antennas was possible thanks to a proper shaping of the radiating element. Following the same idea (choice of suitable shape), a shortened slot fed patch antenna exhibiting two step discontinuities, is described, analysed and optimized with a simple transmission line model. The shortening ratio (ρ) can reach 80% for matched antenna, printed on a substrate with a low dielectric constant (εr=2.2). The calculated results of input impedance are validated by experiment.

The performance of coded multi-pulse pulse position modulation (MPPM) consisting of m slots and 2 pulses, denoted as (m, 2) MPPM, with imperfect slot synchronization is analyzed. Convolutional codes and Reed-Solomon (RS) codes are employed for (m, 2) MPPM, and the bit error probability of coded (m, 2) MPPM in the presence of the timing offset is derived. In each coded (m, 2) MPPM, we compare the performance of some different code rate systems. Moreover, we compare the performance of both systems at the same information bit rate. It is shown that in both coded systems, the performance of code rate-1/2 coded (m, 2) MPPM is the best when the timing offset is small. Wheji the timing offset is somewhat large, however, uncoded (m, 2) MPPM is shown to perform better than coded (m, 2) MPPM. Further, convolutional coded (m, 2) MPPM with the constraint length k7 is shown to perform better than RS coded (m, 2) MPPM for the same code rate.

This paper proposes a functional video handling technique based on structured video. The video handling architecture, which includes a video data structure, file management structure, and visual interface structure, is introduced as the core concept of this technique. One of the key features of this architecture is that the newly proposed video indexing method is performed automatically based on image processing. The video data structure, which plays an important role in the architecture, has two kinds of data structures: content and node. The central idea behind these structures is to separate the video contents from the processing operations and to create links between them. Video indexes work as a backend mechanism in structuring video content. A prototype video handling system called the MediaBENCH, a hypermedia basic environment for computer and human interactions, which demonstrates the actual implementation of the proposed concept and technique, is described. Basic functions such as browsing and editing, which are achieved based on the architecture, exhibit the advantages of structured video handling. The concept and the methods proposed in this paper assure various video-computer applications, which will play major roles in the multimedia field.

This paper proposes a new pitch prediction method for 4 kbps CELP (Code Excited LPC) speech coding with 20 msec frame, for the future ITU-T 4 kbps speech coding standardization. In the conventional CELP speech coding, synthetic speech quality deteriorates rapidly at 4 kbps, especially for female and children's speech with short pitch period. The pitch prediction performance is significantly degraded for such speech. The important reason is that when the pitch period is shorter than the subframe length, the simple repetition of the past excitation signal based on the estimated lag, not the pitch prediction, is usually carried out in the adaptive codebook operation. The proposed pitch prediction method can carry out the pitch prediction without the above approximation by utilizing the current subframe excitation codevector signal, when the pitch prediction parameters are determined. To further improve the performance, a split vector synthesis and perceptually spectral weighting method, and a low-complexity perceptually harmonic and spectral weighting method have also been developed. The informal listening test result shows that the 4 kbps speech coder with 20 msec frame, utilizing all of the proposed improvements, achieves 0.2 MOS higher results than the coder without them.

This paper proposes a practical training algorithm for artificial neural networks, by which both the optimally pruned model and the optimally trained parameter for the minimum prediction error can be found simultaneously. In the proposed algorithm, the conventional information criterion is modified into a differentiable function of weight parameters, and then it is minimized while being controlled back to the conventional form. Since this method has several theoretical problems, its effectiveness is examined by computer simulations and by an application to practical ultrasonic image reconstruction.

The recent progress of B-ISDN signaling systems has enabled networks to handle calls which require a wide variety of ATM connection sets. This paper is concerned with the circuit group which handles calls requesting asymmetric forward and backward multi-connections, and has the capability of both bandwidth negotiation and bandwidth reservation as a traffic control for enhancing call blocking performance. A model of the circuit group is first established focusing on the call level characteristics of the group, and then a method based on the reduced load approximation and an approximate analysis of a multirate group is proposed for calculating approximate blocking probabilities. The accuracy of the approximation method is evaluated numerically by comparing with an exact method and simulation. Further the impact of bandwidth negotiation and reservation on call blockings is examined based on numerical examples.

This paper deals with an efficient radix-2 divider design theory that uses carry-propagation-free adders based on redundant binary{1, 0, 1} representation. In order to compute the division fast, we look ahead to the next step quotient-digit selection embedded in the current partial remainder calculation. The solution is a function of the four most significant digits of the current partial remainder, when scaling the divisor in the range [1, 9/8). In gate depth, this result is better than the higher radix-4 case without the look-ahead quotient-digit selection and the design is simple.

This paper describes an advanced rule-embedded neural network (RENN+) that has an extended framework for achieving a very tight integration of learning-based neural networks and rule-bases of existing if-then rules. The RENN+ is effective in pattern recognition with ill-posed conditions. It is basically composed of several component RENNs and an output RENN, which are three-layer back-propagation (BP) networks except for the input layer. Each RENN can be pre-organized by embedding the if-then rules through translation of the rules into logic functions in a disjunctive normal form, and can be trainded to acquire adaptive rules as required. A weight-modification-reduced learning algorithm (WMR) capable of standard regularization is used for the post-training to suppress excessive modification of the weights for the embedded rules. To estimate the effectiveness of the proposed RENN+, it was used for pattern recognition in a radar system for detection of buried pipes. This trial showed that a RENN+ with two component RENNs had good recognition capability, whereas a conventional BP network was ineffective.