This paper gives an O(n log n)-time algorithm for the following problem: min Σni=1|xi-ai| s.t.x1x2xn where ai(i=1, , n) are given constants and xi(i=1, , n) are variables. There has been given an O(n2)-time incremental algorithm, and we improve it by using the heap as a data structure and modify the incremental algorithm partly. This problem is a kind of the geometric fitting problem between two corresponding sets of points on a line which is related to some VLSI layout design problem.

In location problems, the outtransmission and intransmission numbers are important indices to evaluate a directed network. We formulate and consider a new problem of fault diagnosis in a system modeled by a directed network in which to each edge a positive real number called the length of edge is assigned and to each vertex a positive real number called the weight of vertex is assigned. By a fault in a directed network, we mean any increase in the length of an edge with respect to its nominal length. A theory and an algorithm for detecting a fault edge in a directed network in which the above indices, i.e. outtransmission and/or intransmission numbers, are measurable, are presented.

Consider a connected network N. With each edge of N we associate a nonnegative real number called the length of the edge. Let N be a network obtained from N by adding new edges and/or by decreasing the lengths of some edges. For a generalized transmission number cf(N, v) defined on vertex v in N, we call Δc(v)=cf(N, v)-cf(N ,v) the Sabidussi difference of vertex v. In this note, we present a new theorem and its corollaries on the Sabidussi difference.

This paper shows that the strong Minkowski decomposition problem is NP-complete. Given two convex polygons α and β, the Minkowski sum α+β is a convex polygon defined by {(ax+bx, ay+by|(ax+ay)α, (bxby)β}. The Minkowski decomposition problem is for a given convex polygon γ to find two non-trivial convex polygons α and β whose Minkowski sum is γ. Silverman and Stein gave a linear-time algorithm for this problem. The strong Minkowski decomposition problem is to decompose a given convex polygon into two convex polygons in such a way that any pair of edges of two polygons are not in parallel. It is well known that the Minkowski sum of two convex polygons can be computed in linear time with respect to the number of edges involved. The NP-completeness result of the strong Minkowski decomposition problem shows interesting contrast to the following two results: One is that its inverse operation, the Minkowski sum operation, can be computed in linear-time; Another result, recently obtained by Mount and Silverman, is that the strong Minkowski operation for a convex polyhedron in R3 is also linear-time computable.

In this paper we present polynomial time algorithms for the following three problems on a Hamilton graph with a prescribed Hamilton circuit: (1) Given a Hamilton graph G with a prescribed Hamilton circuit, find a maximal planar Hamilton subgraph of G, (2) Given a Hamilton graph G and a planar Hamilton subgraph H of G, find a maximal planar Hamilton subgraph of G that contains H, and (3) Given an edge-weighted Hamilton graph G=(V, E), find a planar Hamilton subgraph G=(V, E) of G such that the addition of an edge e E-Edestroys the planarity, unless we delete an edge from Ehaving no less weight than e. The time complexities of the algorithms are O(n+m), O(m3/2) and O(m5/3), respectively, where n(resp., m) is the number of vertices (resp., edges) of the Hamilton graph. These algorithms are applicable to the Topological Via Minimization problem.

In audio teleconference systems, speech quality may be degraded due to acoustic echo in the conference room. Echo control devices, such as echo cancellers, can be used to improve the speech quality. This paper describes the echo return loss required for acoustic echo controllers used in audio teleconferencing based on subjective assessment. In particular, far-end or talker echo is subjectively evaluated using a simulated audio teleconference system constructed in our laboratory. Test conditions are given as combinations of transmission delay and insertion loss. The subjective tests were also evaluated under three different reverberation times of echo path. The thresholds of detectable and/or objectionable echoes and mean opinion score in view of acoustic echo and reverberation in audio teleconferencing are clarified. From this, we can ascertain that an echo objection limit that 90% of the subjects consider to be permissible leads to a required echo return loss of more than 40 dB when the overall round-trip delay time Tord is 100 ms and the reverberation time Trev is 400 ms.

A new algebraic solution is developed for nonlinear integral/ differential equations including power-law or product-type nonlinearities. The new method performs the computation via PL transform using multiplication operator with the aid of integral operator through iterative calculations. This method is capable of solving integral or integro-differential equations without converting the equation into a equivalent differential equation. The method is also capable of solving higher-order differential equations without converting the equation into a set of simultaneous first order differential equations. Examples show that a good accuracy was obtained using a limited length PL transform through a small number of iterations.

We report the results of experiments on a Josephson RAM having an access time of 590 ps and a power dissipation of 19 mW. To design such high-speed memory, we developed new gates and circuits and used high-speed techniques. This paper details the design of the 4K bit Josephson RAM.

Leakage current in SCC DRAM was reduced by optimizing implant conditions to form channel stopper, node connection and Hi-C boron. To reduce leakage current, the implantation doses should be reduced to reduce implant induced damages. These implant dose reductions are compromised to the necessities of high p type concentration to prevent punch-throughs at several parts of the cell. Near the deep trench bottom, damaged region due to Hi-C boron implant is separated from the bottom edge of the n+ storage node to suppress the gate controlled leakage current. By the improvements, the retention time of the 16 M SCC DRAM becomes over 30 sec at room temperature. It is also shown that folded bit line structure could be adopted easily for SCC.

Most of the late generation nonvolatile memories with moderate access speed are designed with divided memory matrix NOR type cell structure because word and bit-lines carry a uniform array of parasitic capacitance which delays the signal propagation and causes the slow down of data access time. Even though divided memory matrix has short matrix drive a chip size penalty is large. Data read function of conventional ROM devices is performed by applying VSS voltage at source of each memory cell MOS transistor. Selected memory cells are applied with a predetermined high-detecting bias (HDB) at the drain through selected bit-line. The current detector connected to these bit-lines detectes the level of current to maintain the bias against cell current. New low detecting bias (LDB) technology improves the data access time from wide memory cell matrix area that must be driven by long-word lines (row) and long bit-lines (column). By implementing the (LDB) ROM architecture, voltage transient time of a word line, transition period of voltage against parasitic capacitance and detection period of bit-line voltage deviation can be improved significantly.

This paper approximations to the transient probabilities Pij (t) (i, j=0, 1, 2, , n) for a transition from state i at t=0 to state j at time t in the n-channel birthdeath processes. First, P0n(t) is considered as an extension of Gnedenko's approximate expressions when state n is regarded as an absorbing state for the models M/M/1/n/, M/M/1/n/N, M/M/n/n/, and M/M/n/n/N. That is to say, if Pn is the steady-state probability of state n, the approximations P0n(t)/Pn when state n is not an absorbing state can be obtained from the function 1-exp{-Q(t)} (Q(t)0 is an analytic function). Based on these considerations, transition diagrams are derived to obtain P0n (t) for the models M/M/S/n/ and M/M/S/n/N. Finally, Pij(t) can be expressed with this P0n(t). Several examples show that the approximations of the transient probabilities are nearly equal to the exact values calculated numerically using the Runge-Kutta method on a personal computer. As the approximations in this paper are very precise and calculable instantaneously on a personal computer, they may be applicable for time-dependent traffic theory which will be useful, for instance, in real-time network management technology.

A 369Kbit SRAM configurable up to four ports, namely, a Port-Configurable (PC) SRAM embedded in 235 KG track-free gate array has been newly developed. The chip fabricated with 0.5 µm double polysilicon and aluminum process technology showed 5 ns on-chip access time. This is considered to be one of the solutions for many applications that require memory system of high speed, large density and high flexibility in configuration such as number of ports, words and bits. The basic PC SRAM cell is a polysilicon resistor load SRAM cell with port customization terminals which are connected by standard gate array customization layers, first and second Al and via hole. In order that a high flexibility in column partitioning is available, a column-sliceable design is employed. Two column-sliceable sense amplifier, Trip Point Controlled CMOS (TPCC) sence amp and Symmetric Current Mirror (SCM) sense amp, are proposed to be laid out wihtin a single column pitch. One basic PC SRAM building block of 123 Kbit consists of 4 sets of decoders, 512 rows each, and 240 columns. For low power and high speed operation, double word line structure with section driving 40 columns are employed. Therefore, in addition to the port configurability, a high flexibility in row and column is available. The maximum word depth is 6 k words with 60 column single port memory. The maximum number of independently operating memory is twelve in case of single port. The chip contains three blocks of 369 kbit so that wide range of selection of cache, TLB and resistor files are integrated with MPU and other logic circuits.

This paper describes the Hierarchical Module Generation Technique capable of creating a high performance memory macrocell. The technique features: (a) automatic generation of macrocells with multi-level hierarchies that achieves the same performance as manually designed macrocells; (b) flexible configuration of macrocells in terms of word-length, bit-width, and cell-shape; and (c) equivalent logic description is created simultaneously with generated patterns that can be used for logic or delay simulation is ASIC design. Several kinds of memory macrocells have been developed as a library including a 1-port RAM, a 2-port RAM, and a ROM using 0.8-µm CMOS technology to verify the effectiveness of this technique.

An 85 ns 16 Mb CMOS EPROM has been realized. It can be hard-ware configured as either 1 M 16 bits or 2 M 8 bits by controlling an input signal. An unique redundancy circuit, which includes two types of PROM cell fuses, allow testing the device completely before assembly. Bit-line division and tungsten polycide wordline are keys to achieve an 85 ns access time. A scaled EPROM cell of 3.6µm is realized with a 0.6 µm N-well CMOS technology with trench-self-aligned isolation and oxide-nitride-oxide interpoly dielectrics. The chip size is 7.1 17.1 mm.

A 4096-channel time-switch LSI with switching address protection is described. To achieve the large switching capacity, a double buffer architecture was adopted, and divided cell array structures were implemented using an automatic layout method. A 4096 w 1 b protection memory is included in the control memory to avoid snappings of paths through fixed switching addresses. The memory area and design complexity were reduced by developing a new method for constructing a memory array with variable capacities and multiple-WE (Write-Enable Signal) control systems. The chip was fabricated with 0.8 µm BiCMOS technology and operates at over 32 Mb/s with a power consumption of 1.2 W.

In this paper, we consider an automatic warehouse, in which rc-k palettes are arranged two-dimensionally on a grid with r rows c columns. The palettes in the warehouse can slide independently and simultaneously with the use of k spaces, unless they come into collision. Then, we show the minimum number of sliding operations required to move a specified palette to a specified position, where one sliding operation is a set of slides of palettes which are executed simultaneously in a unit time withouto any collision.

The paper proves the polynomiality of the multiplicative penalty function method for linear programming proposed by Iri and Imai. This is accomplished by considering ellipsoids determined by the Hessian at an interior point and centered at the point, and showing that, for any interior point, there is such an ellipsoid contained in the feasible region in which the penalty function is well approximated by a linear function determined by the gradient at the point.

Recent technical trends of electrically programmable ROM (E-PROM) and electrically erasable and programmable PROM (EE-PROM) are reviewed in this paper. The reduction of the cell size and high speed access have been realized by the several breakthroughs of the device structure. The invention of the Flash EE-PROM makes the cell size same as that of E-PROM. Therefore, the bit capacity of Flash EE-PROM is supposed to be quadrupled every three years, same as DRAM's and E-PROM's scaling speed. Furthermore, the much higher density EE-PROM can be realized by the use of the NAND EE-PROM, recently. The invention of the NAND EE-PROM has enabled the semiconductor device engineers to replace the magnetic memory with Si device in very near future.

With the great leaps forward in standard memories like DRAMs and SRAMs, demands for a dedicated memory oriented to special applications have become increasingly strong. This paper presents the state of the art of ASIC memories, explaining the key points needed to implement additional features. Trends are outlined and technological issues concerning device choice, circuit technique, and design methodology are discussed. Through consideration of future trends in ASIC memories, it's clarified that achieving high-speed performance as well as high memory capacity with sophisticated logic fills most of the special applications.

State-of-the-art dynamic random access memory (DRAM) technologies are reviewed, focusing on circuit design issues. In addition to density increase, clear trends indicated in recent reports are: (1) low-voltage and low-power DRAMs, e.g. a 1.5-3.6 V 64-Mb DRAM and a 4-Mb DRAM with a 3-µA retention current. Lowering the operating voltage is essential in termss of the reliability of miniaturized devices and the power dissipation of the chip. Besides, the resultant low operating current and the low retention current are keys to meeting the increasing demand for battery-backed or battery-operated DRAMs. Important technologies are high-speed sensing, a high-speed low-power internal voltage generator, a word-line booster, and a refresh timer; (2) High-speed DRAMs with half the access times of standard ones, e.g. 17-ns 4-Mb DRAMs. Many efforts have been made to enhance random and serial access rates, such as direct sensing and on-chip interleaving techniques. In addition to high-speed operation, the movement towards larger bit width requires a means of suppressing the noise increased due to a larger peak current. Waveform control for date-line and output charging current is essential; (3) Yield improvement and test cost reduction techniques, e.g. on-chip ECC, parallel testing, and built-in self-testing. These are becoming more and more important for reducing cost.