bluuebunny/crossref_metadata_2025 huggingface dataset:
Evaluation of TiW + Al/Cu electromigration performance
Authors: Armstrong N. P.
Published: July 2007

Al/4 per cent Cu tracks with a TiW underlayer have been life‐tested for electromigration between 180° and 235°C, and activation energy for EM in the tracks has been obtained. Comparison with other life‐test data has shown that the previous omission of a vacuum break between TiW and Al/Cu depositions resulted in 10x improvement int50. However, the present films remain greatly superior to Al/Cu alone: the improved slope implies a 10x increase int0.1%—an appropriate benchmark for circuit failure. Secondary ion mass spectrometry and X‐TEM have been used to investigate reasons for the large observed effect of vacuum break on EM life. Results lead to the suggested use of Al/Cu/Ti alloys in future.
Evaluation of E2PROM data retention by field acceleration
Authors: Lanzoni M. , Menozzi R. , Riva C. , Olivo P. , Riccò B.
Published: July 2007

This work presents an improved theoretical analysis of the physical mechanisms leading to charge loss from the floating gate of electrically erasable PROMs (E2PROMs). The analysis is applied to a simplified model of a FLOTOX cell in order to evaluate data retention characteristics using the applied field as an accelerating factor. A set of experimental results (obtained on virgin as well as on aged cells) is presented and degradation of data retention due to cell aging is examined.
Proportional hazards modelling versus two‐sample tests: A case study
Authors: Bohoris G. A. , Leitao A. L. F.
Published: July 2007

The aim of this paper is to illustrate primarily the suitability and secondly the ability of both PHM and ‘two‐sample’ tests in answering problems in the reliability field. The findings stress the fact that ‘two‐sample’ tests should be preferred for comparison purposes and PHM for modelling the behaviour of the equipment in the presence of various factors.
ESD in integrated circuits
Authors: Amerasekera Ajith , Verwey Jan
Published: July 2007

A review of the effects of electrostatic discharge (ESD) on semiconductor integrated circuits is presented. The principles of the human body model (HBM), the machine model (MM) and the charged device model (CDM) test methods are outlined, and their relative merits and drawbacks are discussed. Techniques, such as the transmission line pulse method, which may be used to characterise ESD protection circuit elements are also presented. The concept of ESD protection circuit designs and some typical ESD protection circuit elements are presented. The main design and process parameters are identified, and the main categories of damage under ESD conditions are shown. Models of the behaviour of the protection circuit elements under high current conditions are presented, and the boundary conditions for damage are discussed. The issues that will influence ESD protection circuit behaviour in the future are discussed.
Combined hardware and software aspects of reliability
Authors: Keene Samuel , Lane Chris
Published: July 2007

This paper presents the similarities and differences between hardware, software and system reliability. Relative contributions to system failures are shown for software and hardware and failure and recovery propensities are also discussed. Reliability, availability and maintainability (RAM) concepts have been broadly developed for software reliability than hardware reliability. Extending these software concepts to hardware and system reliability helps in examining the reliability of complex systems.

The paper concludes with assurance techniques for defending against faults. Most of the techniques discussed originate in software reliability but apply to all aspects of a system. Also, the effects of redundancy on overall system availability are shown.
A computer‐controlled environmental test system for high pin‐count integrated circuit packages
Authors: Barrett John , Donavan John Ó , Hayes Thomas , Mathúna Seán C.Ó
Published: July 2007

An automated environmental stress testing system, designed and assembled for testing of high pin‐count integrated circuit packages and surface mount solder joint reliability is described. Details are given of the software and hardware used in the control of the environment chambers used, in monitoring of test specimen reliability parameters and in control and monitoring of special purpose integrated circuits for testing of IC package reliability. In addition, an automatic system for monitoring of the resistance of fine pitch surface mount solder joints and for detection and recording of thermally induced intermittent open circuits in these joints is described.
Quality and reliability: Illusions and realities
Authors: O'Connor Patrick D. T.
Published: July 2007

The paper reviews the role of quantitative and ‘systems’ methods that have been developed, and in many cases standardized, for application in quality assurance and reliability engineering. It proposes that these should be discarded in favour of a return to traditional engineering and management values, and emphasis on the methods that have driven the quality revolution. These include the use of statistical methods for preventing failure and for optimising designs and processes.
Total quality management in Hong Kong industry and its subsidiaries in China
Authors: Lee Tat Y.
Published: July 2007

This paper reviews the findings of a survey on the use of quality management techniques in Hong Kong industry and its investment in China. It reflects the attitude of industry towards the new quality management concepts, particularly ISO 9000. The second part of the paper reports some observations of auditing some companies in Hong Kong and south China and discusses the weaknesses of the quality systems in these areas.
Electromigration, models and atomistic interpretation
Authors: Kirchheim Reiner
Published: July 2007

Fundamental aspects of electromigration in Al‐lines of integrated circuits are reviewed, including vacancy diffusion, vacancy generation and annihilation. The latter processes give rise to the generation of mechanical stresses. Various models and computer simulations on electromigration are compiled and their influence on the parameters in Black's equations is discussed. The beneficial effect of a (111) texture is explained by the concomitant formation of a large number of tilt grain boundaries and the low diffusivity of atoms perpendicular to the tilt axis of these boundaries.
Breakdown characteristics of gate and tunnel oxides versus field and temperature
Authors: Monsérié Christophe , Mortini Patrick , Ghibaudo Gérard , Pananakakis Georges
Published: July 2007

The wearout and breakdown parameters of representative gate and tunnel oxides are evaluated versus temperature, electric field and polarity. A frontier close to 127°C between two regions with different activation energies is clearly demonstrated. However, the negative charge build‐up under high field stress is correlated with the breakdown. The field acceleration factor is found to be constant in the range 8·5–12·5 MV/cm. The time‐to‐breakdown distributions can be described both by theEand the 1/Emodels. Finally, the thickness dependence of the field acceleration factor is quantified for oxide layers with a thickness in the range between 10 nm and 50 nm.
Failure mechanisms in life‐tested hemts
Authors: Anderson W. T. , Christianson K. A. , Moglestue C.
Published: July 2007

Failure mechanisms in RF life‐tested high electron mobility transistors (HEMTs) were investigated both experimentally and theoretically. As a result of RF life testing the devices degraded by a decrease in drain current, transconductance, and gain and an increase in noise figure. Monte Carlo simulations confirmed the experimental conclusions that degradation resulted from gate metal interdiffusion and ohmic contact degradation.
Knowledge‐based qualification tests for electronic components in harsh environments
Authors: Hu Jimmy M.
Published: July 2007

The objectives of this paper are to propose a practical procedure for knowledge‐based reliability qualification, and provide a checklist of required information for qualification analysis and testing. The paper investigates the common failure mechanisms of electronic components in automotive environments, and addresses the role of physics‐of‐failure approach in component reliability qualification.
Critical area analysis for design‐based yield improvement of vlsi circuits
Authors: Schmitt‐Landsiedel Doris , Keitel‐Schulz Doris , Khare Jitendra , Griep Susanne , Maly Wojciech
Published: July 2007

Yield improvements can be achieved by both contamination control (manufacturing) and defect sensitivity decrease (design). In this paper, the need for critical area analysis is demonstrated for design based yield prediction and improvement. Experimental results for a typical CMOS process are provided.
Hot‐carrier reliability lifetimes as predicted by Berkeley's model
Authors: Meehan Alan , O'Sullivan Paula , Hurley Paul , Mathewson Alan
Published: July 2007

Hot‐carrier effects pose a significant reliability problem in modern MOS processes. An accurate method of predicting hot‐carrier lifetimes is essential for the development of fine‐geometry MOS technology. A hot‐carrier degradation model developed by C. Huet al.at the University of Berkeley is widely used to predict device lifetimes at given operating conditions from the results of accelerated tests. This paper demonstrates a new method of performing hot‐carrier stress measurements which satisfies the key demand of this model. This method involves adjusting device drain voltage in order to maintain a constant ratio of substrate to drain currents. This method is employed to show that the Berkeley model makes a minimum lifetime prediction which is about an order of magnitude too short at accelerated stress conditions. This casts doubt on the suitability of the Berkeley model for use in circuit reliability simulation and for use in setting industrial reliability benchmarks. A new understanding of the importance of the gate‐source voltage during hot‐carrier reliability characterization using the Berkeley model is also discussed.
Behaviour of lasing wavelength change during degradation in a buried‐heterostructure (BH)‐type DFB laser
Authors: Fukuda Mitsuo , Kano Fumiyoshi , Kurosaki Takeshi , Yoshida Junichi
Published: July 2007

The behaviour of lasing wavelength change during degradation is experimentally clarified for a buried heterostructure (BH) InGaAsP/InP DFB laser, and the mechanism of the wavelength change is theoretically analysed.
Relationships between time‐leaf‐and‐space bounded ATMS and reversal‐and‐space bounded NTMs
Authors: Yamamoto Hiroaki , Noguchi Shoichi
Published: July 2007

Until now, discussions have been made for several models of deterministic parallel computation, concerning such items as the trade‐off between the time and the number of processors and the relations among those models. However, few discussions have been made for the nondeterministic case. This paper discusses the nondeterministic case, using ATM (alternating Turing machine) and NTM (nondeterministic Turing machine). The main results are as follows. (1) WhenR(n)=0(S(n)), andR(n)=ω(log(S(n)),S(n) = ω (n), NRS,(Ro(1)(n) andS0(1)(n)) ATBS(R0(1)(n),S0(1)(n),R0(1)(n))NRSR0(1)(n)),S0(1)(n),S0(1)(n)). (2) S(n) = 0(R(n)) andS(n)=ω (log(R(n)),R(n) = ω(n), where NRSR0(1)(n),S0(1)(n))=ATBSR0(1)(n)),S0(1)(n)), where NRS(R(n),S(n) (ATBS )T(n),B(n), S(n)is the class of languages accepted by(R(n),S(n))reversal‐and‐space bounded NTM[(T(n),B(n)]time‐leaf‐and‐space bounded ATM).
Real‐time shuffle stack automaton
Authors: Kosai Shoji , Tsujino Yoshihiro , Araki Toshiro , Tokura Nobuki
Published: July 2007

As models to describe concurrent systems, Petri net, shuffle stack automaton (SSA), flow expression, event expression, and shuffle grammar have been proposed. SSA is an automaton which is obtained by adding to the finite automaton a stack with shuffle function. Its descriptive power has already been discussed. This paper discusses the real‐time shuffle stack automaton (RSSA, which is an SSA without λ‐transition in regard to the input), which is a subclass of SSA. It is shown that RSSA has the same descriptive power, independently of the accepting mode (empty‐stack acceptance or final‐state acceptance), and of whether or not a terminating symbol is provided at the end of the input string. It is also shown that the descriptive power of RSSA is incomparable to that of the push‐down automaton, but is properly contained in that of the linear bounded automaton. If a language is bounded and if the set obtained by applying Parikh mapping to that language is semi‐linear, the language is accepted by RSSA. Another property of the language accepted by RSSA is that if it is a bounded context‐free language, it is accepted by RSSA.
A data tablet using electromagnetic induction
Authors: Aono Yoshihito , Takeda Yukio , Tanabe Naoto , Iwaki Hiroshi
Published: July 2007

A new data tablet using electromagnetic 1 induction is described. The position on the i tablet is detected by the sensor in the pen holder which is coupled with the rotating magnetic field whose phase varies linearly with the position of the pen on the tablet. In this method, the sensor height “h” and the phase change factor “a” of the generated magnetic field are selected as ah ± 1 so that the positional error caused by the pen inclination is readily compensated. The phase change factor of the magnetic field, in addition, is made so large that the reading accuracy is improved. As practical examples, an electromagnetic white hoard (size: 1.4 m x 1.06 m) and a tablet unified with a plasma display panel for teleconferencing equipment are described.
High‐speed fan‐beam reconstruction using direct two‐dimensional fourier transform method
Authors: Niki Noboru , Mizutani Toshio , Takahashi Yoshizo , Inouye Tamon
Published: July 2007

Since the X‐ray CT has been introduced, various efforts have been made to obtain better quality and higher speed [1 ‐ 5]. Development of a high‐resolution CT and a superhigh‐speed CT for heart diagnosis is still required. For this purpose, a highspeed fan‐beam image reconstruction method must be devised. While the two‐dimensional Fourier transformation method much faster than the filtered back projection method has been proposed, it has not given a satisfactory result for fan‐beam projection data [4, 6]. In this paper, a fan‐beam reconstruction using two‐dimensional Fourier transformation method is proposed. The fan‐beam projection data are transformed to parallel beam projection data by a rebinning algorithm. Then a two‐dimensional Fourier transformation method is applied. While in this method high‐speed computation is available by the use of a two‐dimensional Fourier transformation method [6], the rebinning algorithm is enhanced by various interpolation methods; thus the high quality and high speed is obtained [7]. Compared with the filtered back projection algorithm for fan‐beam projection data, the algorithm is proved to be so effective that the image quality is equal and the calculation speed about one‐fifteenth.
Feasibility problem for meeting timetable rearrangement
Authors: Sugihara Kazuo , Kikuno Tohru , Yoshida Noriyoshi , Arame Kazunori
Published: July 2007

Scheduling of meetings is one of the basic functions demanded in office automation. With respect to the automation of this function, the Meeting Timetable Rearrangement problem (MTR) to update a current meeting timetable for an additional meeting has been formulated. However, it has already been shown that MTR is NP‐hard. Consequently, we should develop an approximation algorithm or a heuristic algorithm for MTR. Such an algorithm is required to find a feasible solution which satisfies all constraints, but not necessarily an optimal solution. This paper discusses a problem to determine whether or not there exists a feasible solution for a given instance of MTR. First, we show that this problem is NP‐complete. That is, there is no polynomial‐time approximation algorithm for MTR unless P = NP. This implies that we should develop a heuristic algorithm for MTR. Second, we present a polynomial‐time algorithm which finds a feasible solution for a subproblem of MTR. By combining this algorithm and a hill‐climbing approach, an efficient heuristic algorithm can be developed.
A character segmentation algorithm for mixed‐mode communication
Authors: Nakamura Osamu , Ujiie Makoto , Okamoto Noriyoshi , Minami Toshi
Published: July 2007

In the realization of a mixed‐mode communication, it is necessary before recognizing individual characters, to separate text and black and white figure regions and to extract efficiently the character region. Problems in such a procedure are the detection and correction of the inclination of a document, separation of contact characters, the merge of disconnected characters, and extraction of a letterhead. This paper describes the results of studies on such problems. The document considered is the English text image, containing binary figures and a letterhead. The basic idea is as follows. Connected regions are obtained by directional propagation and shrinking to merge figures. Then: (1) a thinning process is performed to detect the inclination angle of the input text; (2) the sizes of the connected regions and their relative locations are examined to extract the letterhead. Estimation of pitch is performed and statistical data about individual characters are used to separate contact characters or merge disconnected characters. The experiment was made for 10 and 12 pitch printed characters, and the correct extraction rate was 100 percent for individual characters, and 94.6 percent for a letterhead. Thus it was verified that the proposed method is useful in extracting the character region.
Redundancy of projection data and its application to improve the quality of a reconstructed image
Authors: Kumazawa Itsuo , Iijima Taizo
Published: July 2007

This paper attempts to apply the actual redundancy involved in X‐ray CT projection data which have been treated as independent data for the improvement of the image quality of a reconstructed image. It is known that the projection data of an X‐ray CT contains random noise, such as photon noise, which has a negative effect on image quality. A simple smoothing filter which generally is used to reduce this effect, causes the degradation of image resolution. Therefore, it is possible to suppress only high‐frequency noise components. However, when the structure of the projection data was analyzed, it became clear that projection data contain a large redundancy in determining the lower‐frequency components of the image. By properly taking advantage of this redundancy for image reconstruction, it is possible to suppress the low‐frequency component. This paper clarifies quantitatively the noise suppression effect using redundancy by comparing the case where redundancy is not used at all with the case where redundancy is used completely.
Restoration of blurred images using two‐dimensional digital filters with noise suppression
Authors: Yahagi Takashi , Kato Yoichi
Published: July 2007

New two‐dimensional nonrecursive digital filters are proposed for noisy blurred images. A two‐dimensional nonrecursive filter is developed to minimize the mean‐squared error of the restored image. Here, the point spread function of the blurring system and statistics of the original image and noise are assumed to be given. A simplified version of the above filter is also developed and tested for restoring images blurred by a linear blurring system. As a result of their nonrecursive nature the proposed filters are stable and are determined by solving linear systems of equations. The blur by the point spread function and that due to degradation by noise are considered in the design of the filters. Images can be restored while the accompanying noise is suppressed. The filters herein are shown to be more effective if combined with noise‐removal filters. Illustrative examples are included to demonstrate the excellent quality of images restored by the proposed filters.
Interconnection network for bucket collection on relational algebra machine GRACE
Authors: Sakai Shuichi , Kitsuregawa Masaru , Tanaka Hidehiko , Moto‐oka Tohru
Published: July 2007

A database machine is required at present which can process with high speed the complex query to the large‐scale database. We are now developing a high‐performance database machine which can cope with such a requirement. Part of the machine for relational algebraic processing is called GRACE. GRACE is a parallel machine with a multimodule structure, and the interconnection networks among its components are important. From a functional viewpoint, the interconnection networks of GRACE can be divided into the bucket distribution network, which sends data into the staging space, and the bucket collection network, which sends data into the set of processors. This paper proposes the control scheme for the data flow in the bucket collection in GRACE, as well as a method of realizing the bucket collection network. The validity of the proposal was verified by evaluation and examination using simulation. To utilize the features of the processing scheme of GRACE, the indirect binary h‐cube network is used as the interconnection network, which is a kind of multistage interconnection network. A very low transfer overhead was realized. Furthermore, the partitioning of the interconnection network for parallel operations is discussed.
A design of ternary logic circuits using M‐NAND and NOT gates
Authors: Odaka Akio , Satoh Kunio
Published: July 2007

We have proposed the canonical form for the p‐valued logical function (p is a natural number, p > 2), using M‐AND, M‐OR and NOT operations. However, the relations among those operations have been discussed only briefly. This paper discusses in detail the properties of M‐NAND, M‐OR and NOT operations for the ternary case (p = 3), deriving another new canonical form called M‐disjunctive canonical form. Then M‐NAND operation is defined, and a realization of the operation by electronic circuit is presented. The proposed circuit is the circuit by MOSFET, and can realize, in addition to M‐NAND operation, two other logical functions. By using these three kinds of logical functions, the logical circuit can be simplified. The circuit is called M‐NAND gate in this paper. It is possible to construct any ternary logical circuit using only M‐NAND gates. However, the total number of elements can be reduced by combining the proposed circuit with NOT gates by Mouftah and Jordan. Based on these properties and the canonical form, the construction of the logical circuit using M‐NAND and NOT gates is discussed. The circuit has properties which are similar to the well‐known operations such as AND, OR, NOT and NAND, and the construction will be easy for those familiar with such operations.
Reliability design of memory systems considering soft error
Authors: Kaneda Shigeo , Fukuda Haruyuki
Published: July 2007

As semiconductor memory chips become more highly integrated, soft errors in memory chips become a serious problem. In this paper we propose a promising approximation method for calculation of the failure rate of the memory part in semiconductor storage units which are comprised mainly of memory chips. Approximation is performed for the following four methods which have been proposed as countermeasure to soft errors in semiconductor storage units: (1) Error correction by SEC‐DED code. (2) Patrol scan method. (3) Erasure correction method. (4) Chip exchange method. Departure of the approximate formula from the correct solution is not greater than 10% in the case of periodic maintenance with one week interval; therefore, it has sufficient precision for designing units. We compare the effects of those methods and obtain the following conclusions. (1) When only SEC‐DED code is used, the failure rate of the memory part is about 1 + λs/λh times the case with hard errors only (λs is the soft error rate of a memory chip and λh is the hard error rate of a memory chip). (2) When the patrol scan method is used together with SEC‐DED code, the soft error margin is about 2 times the case of SEC‐DED code only. (3) Using the erasure correction method or (4) chip exchange method, the soft error margin increases 10 to 100 times the case of SEC‐DED code only. However, the required amount of hardware doubled because of error correction.
Stability analysis by maclaurin series expansion of system function and its applications
Authors: Hayashi Shinji , Hamada Nozomu
Published: July 2007

It is possible to describe equivalently the input/output relations of a linear time‐invariant system, not by the coefficients of denominator/numerator polynomials of the transfer function, but by the coefficients of Maclaurin expansion of the transfer function. The Maclaurin expansion coefficient is the expansion coefficient of the transfer function in the low‐frequency range. If the system is asymptotically stable, then it is directly related to the time‐moment of impulse response and it is an important parameter in control system design and approximation problems.

This paper introduces an algebraic method which gives a criterion for stability and the gain margin/phase margin of the feedback control systems directly from the Maclaurin expansion coefficients without computing the coefficients of denominator/numerator polynomials. Moreover, by applying the above criterion we give a method of checking the positive reality, which is an important property of the system.
Inspection policies for a computer with (n‐1)/n parallel redundant system
Authors: Yasui Kazumi , Nakagawa Toshio , Sawa Yoshiya
Published: July 2007

The ECC function in a computer system consists of an (n ‐ 1)/n parallel‐redundant system: The unit process in a computer system is performed by data processing N times with n bits as one unit. Then a single‐bit error is corrected automatically by the ECC function, and an automatic retrial is made when a plural‐bit error is detected. This model is one kind of an (n ‐ 1)/n parallel system. Using the elementary reliability theory, the reliability function and the error rate of unit process, and the probability of j times errors during (0, t] are obtained. Further, three inspection policies for such a model are considered. The availability and the expected cost rate are derived and the optimum policies to minimize the cost/availability ratios are discussed. Comparisons between three models are also made in numerical examples.
Delay Analysis of Wait System Model for Window‐Controlled Packet Network and Optimal Window Allocation
Authors: Suzuki Hiroshi , Nakanishi Hikaru , Sanada Hidehiko , Tezuka Yoshikazu , Akiyoshi Ichiro
Published: July 2007

Window allocation is an important problem in designing a window‐controlled packet network. Most of the early studies on this topic deal with the loss system model because of its analytical simplicity. In actual packet switched networks the admission delay of an input‐regulated packet has to be considered and hence its wait system model need be studied. This paper presents delay analysis of the wait system model for a multilogic channel network (multi‐LC model) with each logic channel having its own window. First, the equivalent flow method is validated in a single‐LC model. Then, based on this method, an approximate approach applicable to the multi‐LC model is developed. Our approximate method is evaluated in comparison with simulation results. Then, using this approximate method, the optimal window allocation problem is studied in a general wait system packet network. We obtain an interesting result showing that the optimal allocation with minimum delay can be achieved by equalizing the input regulation degree on each LC.
Switching control multiprocessor system
Authors: Yamada Takahiko , Miki Shuji
Published: July 2007

A multiprocessor architecture for switching systems whose processing volumes increase with network function enhancement is discussed. This architecture allows individual processors to be added without endangering reliability by modifying the already installed multiprocessor system. Essential conditions for the architecture are: An example of switching control multiprocessor system based on this study result will be shown. (1) All network resources must be managed using common memory. (2) Switching control functions must be divided into signaling processing functions and call control processing functions to reduce the processing delay as much as possible. Call control processing functions must be equally shared by the call control processor. (3) Each signaling processor must be associated with a single signaling system.
Optimal‐Time Algorithm for the k‐Node‐Connectivity Augmentation Problem for Ternary Trees
Authors: Masuzawa Toshimitsu , Hagihara Ken'ichi , Tokura Nobuki , Wada Koichi
Published: July 2007

Given a graph and a positive integer k, in the k‐node‐connectivity augmentation problem (k‐NCAP), a set of edges is determined to be added to convert the graph into a k‐node‐connected graph with the minimum sum of the added edge‐weights. It is known that 1‐NCAP, for the directed acyclic graph where the weight is restricted to 1 and 2, is NP‐complete. It is also known that when the weight of the edges are all equal, 1‐NCAP for any directed graph can be solved in O([V] + [E]) time, and when the graph is restricted to the directed binary tree, k‐NCAP (k ≥ 2) is solved in O(k |y|) time. In the preceding, |V and |E are the number of nodes and the number of edges of the given graph, respectively. This paper discusses k‐NCAP (k ≥ 2) for the directed graph, where all edge weights are equal. A solution for k‐NCAP is shown for the family of graphs properly containing the directed ternary trees. It is shown that the problem can be solved in (k ≥ 3) time O(k |V) for the directed ternary tree, which is the optimal‐time algorithm within a constant factor. In this paper, a new family of regular and k‐node‐connected graphs called a k‐bouquet is defined. The solution for k‐NCAP is obtained by constructing a k‐bouquet by adding edges to the given graph.
Syndrome‐testable design and syndrome computing method for large PLA's
Authors: Yamada Teruhiko
Published: July 2007

Numerous studies have been made on a simplified test method and easily testable circuit design to reduce the test cost of logical circuits. In the syndrome test, which is one of the simplified test methods, all input vectors are applied once each and the number of cases is counted where the output is 1. Consequently, in the application of the method to a large‐scale circuit, it is important to perform the test by partitioning the network into subnetworks of appropriate sizes and to compute the number of syndromes (number of output 1′s) efficiently. This paper discusses the syndrome test for the large‐scale PLA (programmable logic array). The scale of hardware to be added for the syndrome test can be reduced compared with the conventional method. Its construction method is presented. Then an efficient computation method is shown for the syndrome in PLA.
Shape recognition by trial and error processes and its hardware realization
Authors: Nagao Makoto
Published: July 2007

The conventional image analysis methods are far from human‐like recognition methods because they require detailed algorithms for all variations of an image. It is thus desirable to develop a recognition method without complicated algorithms which is as human‐like as possible. Towards this end we propose a shape analysis method involving trial and error processes. We propose a new image processing system using hardware in a top‐down manner. Functions largely realized by hardware are: the placing of a local slit of suitable size in a proper position based on high‐level structural description of the objects, extracting local features by automatic position control and returning the information to higher‐level processing. In this way, users need only describe the structure of an object, and the system can interpret the description and automatically execute structure recognition of objects using the feature extraction mechanism.
Analysis of error‐detecting probability of signature circuit for lsi self‐testing and proprosal of new signature circuit
Authors: Iwasaki Kazuhiko , Yamaguchi Noboru , Hagiwara Yoshimune
Published: July 2007

The self‐testing method using a multiple‐input signature register (MISR) has been proposed as a means of testing logic LSI. This paper analyzes the error‐detecting ability when the MISR is used as a pattern compression circuit. Coding theory technique is applied in the analysis. As the first step, assuming that a Hamming code generating polynomial (primitive polynomial) is used as the polynomial in MISR, the error‐detection rates are determined theoretically for single through quadruple errors. Then the error‐detecting rates for single through quadruple errors are calculated for the modified Hamming code generating polynomial. It is indicated as a result that the multiple error‐detection rate, especially the rate for the double error, does not reach 100%. In order to improve the multiple error‐detection rate, a reversely dual MISR is proposed in which a pair of MISRs is used with opposite shift directions. When the Hamming code generating polynomial is employed as the polynomial in the reversely dual MISR, it is shown that single and double errors are always detected. The rate of triple error detection is calculated. It is also shown that if the modified Hamming code generating polynominal is used, all single, double and triple errors are detected.
Throughput analysis of Tree‐Type protocols
Authors: Oie Yuuji , Muro Shojiro , Hasegawa Toshiharu
Published: July 2007

Tree‐type protocols achieve stable throughput even under heavy channel traffic compared with random access protocols such as the ALOHA types which show bistable behavior. Various binary tree‐type protocols have been studied extensively for channel stability and the improvement of throughput performance. In this paper, closed‐form solutions of the collision resolution time of several d‐ary tree type protocols are obtained, and the effect of the degree value of their protocols on the throughput performance is discussed. As d‐ary tree‐type protocols, we consider the tree protocol, improved tree protocol, adaptive tree protocol and tree protocol with control mini‐slot, and compare their performance. Further, by comparing the stability of the binary tree protocol with that of three ALOHA schemes with different backoff algorithms, we show that the binary tree protocol exhibits very stable behavior even for a heavy traffic load.
Design of secondary storage system of database machine grace using generalized KD‐tree
Authors: Fushimi Shinya , Kitsuregawa Masaru , Tanaka Hidehiko , Mota‐oka Tohru
Published: July 2007

The relational database machine GRACE can execute heavy relational operations such as joins quite efficiently, thereby resolving the bottleneck in the relational database processing. A new bottleneck, however, is expected to appear at accesses to the secondary storage system. We can also eliminate this new bottleneck by partitioning the database into multidimensional cells adaptively to the access pattern to data. As a result, the average number of page accesses is reduced. We developed an adaptive multidimensional clustering technique called the generalized KD‐tree method. The method is fully adaptive to the access pattern to data and the distribution of tuples. It was shown that the generalized KD‐tree method can reduce the average number of page accesses considerably, even in comparison with other multidimensional clustering algorithms.
Area‐time complexity on a vlsi model with boundary layout assumption
Authors: Wada Koichi , Hagihara Ken'Ichi , Tokura Nobuki
Published: July 2007

In the VLSI circuit, the area occupied by the circuit and the time required for computation are important measures of evaluation. Thompson, Brent and Kung have proposed a VLSI model to evaluate the VLSI circuit by the area A and the computation time T. It is an important problem to examine the change of the area and the computation time when a certain practical assumption is imposed on the VLSI model. This paper shows that when an assumption that the input and the output are connected at the boundary of the circuit (called boundary‐layout assumption) is imposed on the VLSI model, relations AT = ω(max(n, m)) and ATa = ω(max(n, m)[max(log N, log M)]a) (α > 1) are produced for the nontrivial class of n‐input, m‐output logic functions. Above, N is the maximum of N1, …, Nm, where Ni is the number of inputs on which the ith output depends, and Mj is the maximum of M1, …, Mn, where Mj is the number of outputs which depends on the jth input. When the boundary‐layout assumption is not imposed, ATα = ω(max(n, m){max(log N, log M)}α‐1) (α ≥ 1) holds. Consequently, for this class of functions, the boundary‐layout assumption properly affects ATα (α ≥ 1). It is shown also by an actual example that there exist functions which achieve the lower bounds.
Lower bounds on time complexity for some subgraph detection problems
Authors: Arai Masanari , Yamashita Masafumi , Hirata Tomio , Ibaraki Toshihide , Honda Namio
Published: July 2007

Nontrivial lower bounds of the time complexity are given for a class of problems on graphs. Specifically, given a complete graph with weighted edges, the problem of finding a subgraph satisfying a property π and having edge‐weights that sum exactly to unity is considered. An ω(n3 log n) lower bound is established under the algebraic decision tree model for a property π that satisfies the degree constraint and is closed with respect to isomorphism, where n is the number of vertices in an input graph. This result is a proper generalization of that of Nakayama et al. [8], in which the same lower bound was obtained for π that is hereditary on subgraphs and determined by components. Furthermore, an ω(n3) lower bound is shown for π = “clique” that does not satisfy the degree constraint and hence the above result can not be applied.
An interactive image processing system for microcomputers
Authors: Nagahashi Hiroshi , Nakatsuyama Mikio , Nishizuka Norio
Published: July 2007

This paper considers a symbolic representation of images which is adequate for interactive image processing, and reports an actual system constructed on a minicomputer. The system is closely associated with an LISP. Some attributes of image data and procedures are represented by a frame structure often used in studies of AI or knowledge engineering. Both image data and image processing procedures are managed by frames. Meanwhile, image processing routines can be developed in both low‐and high‐level languages such as ASSEMBLER, FORTRAN or C, and they can easily be linked to the system by specific functions. Consequently, flexible and high‐speed processing can be realized. If some knowledge of image processing is given, this system will be available for fundamental studies of image description and image understanding.
Minimum separation layout for cmos circuits realizing tree‐shape monotone decreasing logic circuits
Authors: Manabe Yoshifumi , Hagihara Ken'Ichi , Tokura Nobuki
Published: July 2007

In CMOS circuits transistors in a p‐MOS circuit and n‐MOS circuit that have a common gate input are often placed next to each other. In such a case, if adjacent diffusion areas are of the same potential, it is possible to merge them to reduce the circuit area. Therefore an important problem is how to obtain efficiently a circuit layout with the minimum number of places (separation) where the merge is impossible. At present, it is known that the minimum separation is zero in a tree‐shape monotone decreasing logic circuit when the fan‐in number of each logic element is odd. However, the time complexity for obtaining the minimum separation for a given arbitrary circuit has not been reported yet. This paper shows that the following problems can be solved in a time linear to the sum of the number of the logical variables and the number of the logic elements where k or h is a constant when a tree‐shape monotone decreasing logic circuit C and a nonnegative integer k are given, determining whether or not there exists a layout of C having separation k or less. If one exists, obtain the minimum separation and a layout with the minimum; and obtain the minimum separation and a layout with the minimum when the fan‐in of each logic element of C is h or less.
Performance evaluation of the binary tree access mechanism in mimd type parallel computers
Authors: Sueyoshi Toshinori , Saisho Keizo , Arita Itsujiro
Published: July 2007

One of the most serious problems in a highly multiple parallel processing system involves memory access contention. In the hierarchically structured access mechanism, the number of simultaneous access paths increases with degree of parallelism. Consequently, it is considered as a configuration suited to a highly multiple parallel system. This paper uses a queue model to analyze the hierarchical routing bus (H‐R bus), which is an access mechanism with a hierarchical structure. The paper further makes a quantitative evaluation of the locality in data access. Based on the derived theoretical expressions and measured results obtained by executing several test programs on the H‐R bus‐connected parallel computer, the H‐R bus performance is evaluated. The results obtained in this paper are as follows: (1) Low external data access rates (i.e., external data access time/processing time) indicate that the H‐R bus‐connected multiprocessor system operates with high efficiency even under high multiplicity. (2) Under sufficient access locality, even high external data access rates do not unduly impair efficiency. Although the above properties have qualitatively been known before, this paper derives theoretical expressions for the properties, supported by experiments.
Event‐driven relaxation method based on asynchronous parallel processing
Authors: Kato Toshikazu , Sakai Toshiyuki
Published: July 2007

The application of the relaxation method to image processing was proposed by Rosenfeld et al. and has been applied in actual problems. One of the problems in the relaxation method concerns computational complexity, where a uniform processing is applied to all objects in each iterative step. From such a viewpoint, the processing speed should be improved. This paper proposes a region‐growing relaxation method, which is an event‐driven relaxation based on asynchronous parallel processing mechanism, and can be applied to the object for which the interpretation should be modified. From the viewpoint of our transformation model representation, the performance of the relaxation method is analyzed. The relaxation model presented by Rosenfeld corresponds to the fixed‐mean oriented procedure for the object, while the proposed model corresponds to a region‐growing one, where the objects of processing are grouped together. The notion of event and eventdriven processing mechanism is introduced into the pattern information processing, and it is shown that the region‐growing relaxation exhibits a high processing efficiency. The region‐growing relaxation is an extension of the discrete model by Rosenfeld, and has the following features: (i) The convergence (termination) is achieved by a finite number of repetitions; (ii) Asynchronous parallel processing can be adopted; (iii) Algorithm is suited to the eventdriven processing; (iv) The convergence is fast compared with the fixed‐mean oriented relaxation; (v) Region segmentation is achieved at the same time. The region‐growing relaxation method is presently adopted in the newspaper layout understanding system EXPRESS.
Reliability evaluation of partitioned TMR systems
Authors: Izawa Nobuyoshi
Published: July 2007

The fault‐tolerant technique has been frequently employed to realize a highly reliable computer system. This paper considers the Triple‐Modular Redundancy (TMR) system, which is one of the fault‐tolerant systems whereby the system is partitioned into several blocks and the majority decision is made in each block. The reliability of such a system is evaluated. Based on the relation between the number of partitions and the failure rate of such a system, the following two types of models are assumed:

(1) TMR network model, where the failure rate of the whole system increases with the number of partitions, when the failure rate of the block is kept constant.

(2) LSI model, where the block failure rate decreases with the number of partitions, when the failure rate of the whole system is kept constant. Especially, in the model (2), the pin‐gate ratio of LSI is taken into consideration. For these models, the expression for the Mean‐Time‐To‐Failure (MTTF), which is the mean operation time until a system failure occurs, is derived. The general tendency of MTTF is analyzed. By numerical examples, the improvement of MTTF by partitioning is demonstrated. The improvement of the TMR system by partitioning is demonstrated quantitatively.
Attenuation correction for infrared rays emission CT
Authors: Uchiyama Hiroki , Kazahaya Kanji , Nakajima Masato , Mizomot Masahiko , Yuta Shinichi
Published: July 2007

We have already proposed the infrared rays emission CT (IRECT) as a method to visualize the temperature distribution inside the flame. IRECT is a method of visualizing the infrared ray source intensity distribution inside the flame in the form of a cross‐sectional image, by numerically processing the one‐dimensional projection data obtained by the external noninvasive measurement of the infrared rays emitted from the flame. Since IRECT is an emission‐type CT, the method contains a problem in that the image quality is degraded by the attenuation of the infrared ray. The correction of the attenuation must be considered for a highly accurate measurement. This paper discusses the application of the attenuation correction method (DMF method) to IRECT, which was recently developed for the application to the gamma ray CT. The result of experimental verification is also presented. A new measurement method is presented for the attenuation coefficient distribution inside the flame, which is needed in the application of the attenuation correction method.
Automatic generation of syntax‐directed editor
Authors: Hamada Takashi , Miyauchi Hiroshi
Published: July 2007

This paper describes the development of the syntax‐directed editor generator system (GED). The earlier syntax‐directed editors have some unsatisfactory points from the viewpoint of the user interface. The editor constructed by GED should realize the following three functions in order to improve the user interface: (1) top‐down programming is possible using the command template; (2) the delete, insert and replace of character strings can be made as the text editor; (3) the command defined by the user can easily be used. Giving the inputs such as syntax rules of the object programming language, the editor of that language is produced. For editing as texts, the incremental parser must be constructed in the generation of the editor. For this purpose, the incremental look‐ahead LR(1) (ILALR(1)) is proposed and applied which is an extension of the early parser.