We show a method to determine a Steiner Minimum Tree (SMT) and a necessary and sufficient condition that an SMT is a full Steiner tree for three given points in -geometry ( = 3m, m is a positive integer). The -geometry allows only orientations with angles i/ (i and ( 2) are integers), and fill up the gap between the rectilinear geometry ( = 2) and the Euclidean geometry ( = ). An SMT in -geometry ( = 3m) has a similar property to that in the Euclidean geometry. The method to determine an SMT in -geometry is an extension of the well-known method in the Euclidean geometry. The Steiner point in -geometry is any point in the intersection area with a parallelogram and a Steiner locus. Then there are infinite candidate locations of the Steiner point. The Steiner point in the Euclidean geometry is that in -geometry ( = 3m).

In this paper, we propose a novel higher order time-frequency distribution (GDH) for a discrete time signal. This distribution is defined over the original discrete time-frequency grids through a delicate discretization of an equivalent expression of a higher order distribution, for a continuous time signal, in [4]. We also present a constructive design method, for the kernel of the GDH, by which the distribution satisfies (i) the alias free condition as well as (ii) the marginal conditions. Numerical examples show that the proposed distributions reasonably suppress the artifacts which are observed severely in the Wigner distribution and its simple higher order generalization.

Software with design flaws increases maintenance costs, decreases component reuse, and reduces software life. Even well-designed software tends to deteriorate with time as it undergoes maintenance. Work on restructuring object-oriented designs involves estimating the quality of the designs using metrics, and automating transformations that preserve the behavior of the designs. However, these factors have been treated almost independently of each other. A long-term goal is to define transformations preserving the behavior of object-oriented designs, and automate the transformations using metrics. In this paper, we describe a genetic algorithm based restructuring approach using metrics to automatically modify object-oriented designs. Cohesion and coupling metrics based on abstract models are defined to quantify designs and provide criteria for comparing alternative designs. The abstract models include a call-use graph and a class-association graph that represent methods, attributes, classes, and their relationships. The metrics include cohesion, inheritance coupling, and interaction coupling based on the behavioral similarity between methods extracted from the models. We define restructuring operations, and show that the operations preserve the behavior of object-oriented designs. We also devise a fitness function using cohesion and coupling metrics, and automatically restructure object-oriented designs by applying a genetic algorithm using the fitness function.

On the basis of generalized theory of system design the behavior of the different design trajectories in the design phase space was analyzed. An additional acceleration effect of the design process has been discovered by the analysis of various design strategies with different initial points. This effect can be understood well on the basis of the elaborated design methodology by means of the different design trajectory analysis. This effect is displayed for all analyzed circuits and it reduces additionally the total computer time for the system design.

In this letter a low-complexity and low-power realization of the 2D discrete-cosine-transform and its inverse (DCT/IDCT) is presented. A VLSI circuit based on the Chen algorithm with the distributed arithmetic approach is described. Furthermore low-power design techniques, based on clock gating and data driven switching activity reduction, are used to decrease the circuit power consumption. To this aim, input signal statistics have been extracted from H.263/MPEG verification models. Finally, circuit performance is compared to known software solutions and dedicated full-custom ones.

In this paper, we present a new approach to the construction of a set of binary sequences with a zero-correlation zone. The set consists of n pairs of binary sequences and the length of each binary sequence is n2(m+2) for some integers m and n. The Hadamard sequences with length n are used to construct the set. Any sequence in the set has 2(m+1) subsequences, each of length 2n. The author proves that any two subsequences are orthogonal if they belong to different pairs of binary sequences in the set.

This paper introduces the concept of hierarchical testability of data paths for delay faults. A definition of hierarchically two-pattern testable (HTPT) data path is developed. Also, a design for testability (DFT) method is presented to augment a data path to become an HTPT one. The DFT method incorporates a graph-based analysis of an HTPT data path and makes use of some graph algorithms. The proposed method can provide similar advantages to the enhanced scan approach at a much lower hardware overhead cost.

We consider the polymatroid packing and covering problems. The polynomial time algorithm with the best approximation bound known for either problem is the greedy algorithm, yielding guaranteed approximation factors of 1/k for polymatroid packing and H(k) for polymatroid covering, where k is the largest rank of an element in a polymatroid, and H(k)=Σi=1k 1/i is the kth Harmonic number. The main contribution of this note is to improve these bounds by slightly extending the greedy heuristics. Specifically, it will be shown how to obtain approximation factors of 2/(k+1) for packing and H(k)-1/6 for covering, generalizing some existing results on k-set packing, matroid matching, and k-set cover problems.

In this paper the authors propose a method for designing the Virtual Private Network (VPN) that guarantees a strict Quality of Service (QoS) over IP networks. The assumed QoS metric is PLP (Packet Loss Probability), and it is guaranteed probabilistically by the provision of an appropriate equivalent bandwidth. We consider two network architectures for constructing VPN, the customer pipe scheme and the Hose scheme, and we present an analytic model to compute the amount of the required bandwidth for the two schemes. Finally, we investigate the validity of the proposition via numerical experiments.

In computer-aided drafting and design, interactive graphics is used to design components, systems, layouts, and structures. There are several approaches for using automated graphical layout tools currently. Our approach employs a genetic algorithm to implement a tool for automated 3D graphical layout design and presentation. The effective use of a genetic algorithm in automated graphical layout design relies on defining a fitness function that reflects user preferences. In this paper, we describe a method to define fitness functions and chromosome structures of selected objects. A learning mechanism is employed to adjust the fitness values of the objects in the selected layout chosen by the user. In our approach, the fitness functions can be changed adaptively reflecting user preferences. Experimental results revealed good performance of the adaptive fitness functions in our proposed mechanism.

This paper proposes a method for mapping a finite state machine (FSM) into a two-dimensional array of LUTs, which is a part of our plastic cell architecture (PCA). LSIs based on the PCA have already implemented as asynchronous devices. Functions that run on the LSIs must also be asynchronous. In order to make good use of the LSIs, a system that translates functions into circuit information for the PCA is needed. We introduce a prototype system that maps an asynchronous FSM onto the PCA. First, a basic mapping method is considered, and then we create three methods to minimize circuit size. Some benchmark suites are synthesized to estimate their efficiency. Experimental results show that all the methods can map an asynchronous FSM onto the PCA and that the three methods can effectively reduce circuit size.

In this paper, we propose an improved network-flow based multi-way circuit partitioning algorithm whose objective is to minimize the number of sub-circuits. It iteratively extracts a size-maximal feasible sub-circuit one at a time. In our approach, two devices are applied. One is in the use of an exact min-cut graph, and the other is in the idea of keeping the number of I/O pins of the residual circuit as small as possible after one-time extraction. We implemented our algorithm in C for experiments, and tested it with several industrial cases and MCNC benchmarks. Compared to the known approach, we observed more than 10% reduction in average of the sub-circuit number.

We describe the logic design of a single-flux-quantum (SFQ) 22 unit switch. It is the main component of the SFQ Banyan packet switch we are developing that enables a switching capacity of over 1 Tbit/s. In this paper, we focus on the design of the controller in the unit switch. The controller does not have a simple "off-the-shelf" conventional circuit, like those used in shift registers or adders. To design such a complicated random logic circuit, we need to adopt a systematic top-down design approach. Using a graphical technique, we first obtained logic functions. Next, to use the deep pipeline architecture, we broke down the functions into one-level logic operations that can be executed within one clock cycle. Finally, we mapped the functions on to the physical circuits using pre-designed SFQ standard cells. The 22 unit switch consists of 59 logic gates and needs about 600 Josephson junctions without gate interconnections. We tested the gate-level circuit by logic simulation and found that it operates correctly at a throughput of 40 GHz.

This paper describes the circuit design procedure of the zero-current soft switching (ZCS) high frequency inverter for induction heating uses. Its output power can be regulated from its maximum to minimum by the instantaneous current vector control scheme using phase shift control between switching units at a fixed frequency. In addition, it can be safely operated since no extraordinarily high voltage or current results even at a short-circuit period at the load. Also, its overall efficiency reaches 90%. The detailed load and frequency characteristics of the inverter are elucidated by the computer-aided simulation. Then, the circuit design procedure is presented, and practical numerical examples are obtained according to this procedure which reveal that the inverter is highly practical and the design procedure is effective. The trial inverters yielding 2 kW or 4 kW were actually prepared. The observed values of the voltages and currents of the inverters were found to be in good agreement with the calculated ones. These facts certificate the validity of the proposed design procedure.

This paper proposes constructive timing-violation (CTV) and evaluates its potential. It can be utilized both for increasing clock frequency and for reducing energy consumption. Increasing clock frequency over that determined by the critical paths causes timing violations. On the other hand, while supply voltage reduction can result in substantial power savings, it also causes larger gate delay and thus clock must be slow down in order not to violate timing constraints of critical paths. However, if any tolerant mechanisms are provided for the timing violations, it is not necessary to keep the constraints. Rather, the violations would be constructive for high clock frequency or for energy savings. From these observations, we propose the CTV, which is supported by the tolerant mechanism based on contemporary speculative execution mechanisms. We evaluate the CTV using a cycle-by-cycle simulator and present its considerably promising potential.

This paper proposes a statistical design approach for Non-Return-to-Zero (NRZ) 40 Gbit/s systems with Forward Error Correction (FEC); the approach considers Polarization Mode Dispersion (PMD). We introduce a fluctuating PMD emulator to experimentally clarify FEC performance in PMD-limited systems. By using the proposed design approach, and considering the FEC relaxation effect on PMD, the maximum transmission distance of an NRZ 40 Gbit/s system without PMD compensation is estimated as several hundreds of km depending on the number of cable concatenations per link and the probability threshold of system acceptance.

Much has been said and written about the changes in analog IC technology such as shrinking line widths, vanishingly low supply voltages, severe power limitations, and digital noise. But beyond these technology changes and their subsequent methodology changes, a far more subtle revolution is happening in the nature of the profession itself. Technology, software, and product evolution have all conspired to create a new kind of analog IC designer, one very different from the IC designers of the past.

We consider to design approximation algorithms for the survivable network design problem in hypergraphs (SNDPHG) based on algorithms developed for the survivable network design problem in graphs (SNDP) or the element connectivity problem in graphs (ECP). Given an instance of the SNDPHG, by replacing each hyperedge e={v1,,vk} with a new vertex we and k edges {we, v1},, {we, vk}, we define an SNDP or ECP in the resulting graph. We show that by approximately solving the SNDP or ECP defined in this way, several approximation algorithms for the SNDPHG can be obtained. One of our results is a dmax+-approximation algorithm for the SNDPHG with dmax 3, where dmax (resp. dmax+) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a dmax+(rmax)-approximation algorithm for the SNDPHG, where (i)=j=1i(1/j) is the harmonic function and rmax is the maximum connectivity requirement.

This paper reports on clich and related mechanisms appearing in a process of human design of software. During studies on human design knowledge, the authors found frequent instance of same pattern of detailing, named clich. In our study, clich is an intermediate level of design knowledge, during a hierarchical detailing step, residing in between simple reuse and creation by micro design rules, which have already been reported. These three kinds of design knowledge are of various types and have different complexities. Discussions on them, focusing on clich type, with procedures of formation of a simple clich skeleton and generation of a clich are given. The studies show a working model of Zipf's principle, and are some trials to reveal a more detail of human designs.

We present the new 128-bit block cipher called Camellia. Camellia supports 128-bit block size and 128-, 192-, and 256-bit key lengths, i.e. the same interface specifications as the Advanced Encryption Standard (AES). Camellia was carefully designed to withstand all known cryptanalytic attacks and even to have a sufficiently large security leeway. It was also designed to suit both software and hardware implementations and to cover all possible encryption applications that range from low-cost smart cards to high-speed network systems. Compared to the AES finalists, Camellia offers at least comparable encryption speed in software and hardware. An optimized implementation of Camellia in assembly language can encrypt on a Pentium III (1.13 GHz) at the rate of 471 Mbits per second. In addition, a distinguishing feature is its small hardware design. A hardware implementation, which includes encryption, decryption, and the key schedule for 128-bit keys, occupies only 9.66 K gates using a 0.35 µm CMOS ASIC library. This is in the smallest class among all existing 128-bit block ciphers. It perfectly meets the current market requirements in wireless cards, for instance, where low power consumption is essential.