This paper presents a new routing method that takes into account neighboring-wire-capacitance (inter-layer and intra-layer) constraints. Intermediate routing (IR) assigns each H/V wire segment to the detailed routing (DR) grid using global routing (GR) results, considering the neighboring-wire constraints (NWC) for critical nets. In DR, the results of IR for constrained nets and their neighboring wires are preserved, and violations that occur in IR are corrected. A simple method for setting NWC that satisfy the initial wire capacitance given in a set-wire-load (SWL) file is also presented. The routing method enables more accurate delay evaluation by considering inter-wire capacitance before DR, and avoids long and costly turnaround in deepsubmicron layout design. Experimental results using MCNC benchmark test data shows that the errors between the maximum delay from IR and that from DR for each net were less than 5% for long (long delay) nets.

This paper proposes a novel ultra high-speed file server based on a personal computer (PC) to provide the instantaneous delivery of huge files, like movie files, graphic images and computer programs, over high-speed networks. In order to improve the sustained sequential read speed from arrays of hard drives to host memory in the server, two key techniques are proposed: "multi-stage striping (MSS)" and the "sequential file system (SFS)." An experimental file server based on a general-purpose PC is constructed and its performance is measured. The results show that the server offers ultra high read speeds, up to 105Mbytes/s, with just 8 hard drives.

The software requirements specification process consists of three steps; requirements capture and analysis, requirements definition and specification, and requirements validation. At the beginning of the second step which this paper focuses on, there have been several types of massive documents generated in the first step. Since the developers and the clients/users of the new software system may not have common knowledge in the field which the system deals with, it is difficult for the developers to produce correct requirements specification by using these documents. There has been few research work to solve this problem. The authors have developed a support tool to produce correct requirements specification by arranging and restructuring those documents into clearly understandable forms. In the second step, the developers must specify the functions and their constraints of the new system from those documents. Analyzing the developers' real activities for designing the support tool, the authors propose a model of this step as the following four activities. To specify the functions of the new system, the developers must collect the sentences which may suggest the functions scattering those documents. To define the details of each function, the developers must gather the paragraphs including the descriptions of the functions. To verify the correctness of each function, the developers must survey all related documents. To perform above activities successfully, the developers must manage various versions of those documents correctly. According to these four types of activities, the authors propose the effective ways to support the developers by arranging those documents. This paper shows algorithms based on this model by using the structures of the documents and keywords which may suggest the functions or constraints. To examine the feasibility of their proposal, the authors implemented a prototype tool. Their tool extracts complete information scattering those documents. The effectiveness of their proposal is demonstrated by their experiments.

A zerotree image-coding scheme is introduced that effectively exploits the inter-scale self-similarities found in the octave decomposition by a wavelet transform. A zerotree is useful for efficiently coding wavelet coefficients; its efficiency was proved by Shapiro's EZW. In the EZW coder, wavelet coefficients are symbolized, then entropy-coded for further compression. In this paper, we analyze the symbols produced by the EZW coder and discuss the entropy for a symbol. We modify the procedure used for symbol-stream generation to produce lower entropy. First, we modify the fixed relation between a parent and children used in the EZW coder to raise the probability that a significant parent has significant children. The modified relation is flexibly modified again based on the observation that a significant coefficient is more likely to have significant coefficients in its neighborhood. The three relations are compared in terms of the number of symbols they produce.

The mapping from a global routing to a feasible detailed routing in a number of 2D array routing structures has been shown to be an NP-complete problem. These routing structures include the Xilinx style routing architecture, as well as architectures with significantly higher switching flexibility. In response to this complexity, a different class of FPGA routing structures called Greedy Routing Architectures (GRAs) have been proposed. On GRAs, optimally routing each switch box, in a specified order, leads to an optimal chip routing. Because routing each switch box takes polynomial time, the mapping problem on GRAs can be solved in polynomial time. In particular, an H-tree GRA with W2+2W switches per switch box (SpSB) and a 2D array GRA with 4W2+2W SpSB have been proposed. In this paper, we improve on these results by introducing an H-tree GRA with W2/2+2W SpSB and a 2D array GRA with 3.5W2+2W SpSB. These new GRAs have the same desirable mapping properties of the previously described GRAs, but use fewer switches.

Parallel multiple context-free grammar (PMCFG) and multiple context-free grammar (MCFG) were introduced to denote the syntax of natural languages. By the known fastest algorithm, the recognition problem for multiple context-free language (MCFL) and parallel multiple context-free language (PMCFL) can be solved in O(ne) time and O(ne+1) time, respectively, where e is a constant which depends only on a given MCFG or PMCFG. In this paper, we propose the following two algorithms. (1) An algorithm which reduces the recognition problem for MCFL to the boolean matrices multiplication problem. (2) An algorithm which reduces the recognition problem for PMCFL to the recognition problem for MCFL. The time complexity of these algorithms is O(ne-3i+1 M(ni)) where e and i are constants which depend only on a given MCFG or PMCFG, and M(k) is the time needed for multiplying two k k boolean matrices. The proposed algorithms are faster than the known fastest algorithms unless e=e, i=1 for MCFG, and e=e, i=0 for PMCFG.

In this paper, a new method is proposed for solving forbidden state problems in non-ordinary controlled Petri nets (NCPNs) with uncontrollable transitions. Using a precedence subnet and a boundary subnet with decision-free properties, the behavior of markings are analyzed structurally. An efficient algorithm is presented for calculating the number of total tokens in forbidden places reachable from a marking. This paper derives necessary and sufficient conditions for identifying admissible markings and boundary markings in terms of the precedence subnet and the boundary subnet.

A simple near-orthogonal code is used as frequency-hopping patterns for the frequency-hopped multiple access systems. Extended RS code is used as channel coding to deplete the effects of hits from simultaneous users. Packet error probability and channel throughput for the system utilizing the near-orthogonal code are evaluated and compared to the corresponding values obtained from the system utilizing random patterns. Results show that the former can provide substantial improvement over the latter. In our illustrated examples, we also show that under the constraint of packet error probability PE 10-2, the maximum achievable number of users with most (n,k) RS codes of interest is less than the number of distinct codewords in the near-orthogonal code. Thus, the number of codewords of the near-orthogonal code is large enough to support the practical application.

In this paper, a novel pass-transistor logic with an efficient level restoration circuit, named Power Saved Pass-transistor Logic (PSPL), is proposed. It is shown how, through the use of regenerative feedback with pMOS switches, we reduce the power consumption and propagation delay compared to conventional pass-transistor logic. To demonstrate the performance of PSPL, a 5454-bit multiplier is designed. For speed and power optimization, the multiplier uses high compression-rate compressors without Booth Encoding, and a 108-bit conditional sum adder with separated carry generation block. The measured multiplication time was 13. 5 ns in a 0. 6 µm single-poly triple-metal 3. 3 V CMOS process. Furthermore, a sequential circuit of a low power 7-bit serial counter is designed and fabricated in a 0. 6 µm single-poly triple-metal 3. 3 V CMOS process. The measured operating speed was 250 MHz.

This letter reports on the condition for applying a feedback connection to a deterministic finite automata. First we define the partial delayed dependence condition for the feedback connection, and then consider problems related to the completeness problem of automata.

This paper explores a relationship between parameters for the context tree weighting and weights for a general model weighting technique. In particular, an algorithm is proposed that approximately computes the parameters from the weights, and a condition under which no error for the approximation occurs is derived.

Reentrant delay line memories using narrow YBa2Cu3O7-δ (YBCO) coplanar transmission lines are proposed. The proposed memory is composed of a looped YBCO coplanar delay line and a 22 semiconductor crossbar switch. This type of memory is superior to semiconductor memories in operating speed, the number of logic gates, power dissipation, and so on. We have also developed narrow and low-loss YBCO coplanar transmission lines for use in these reentrant delay line memories. Etch-back planarization and a patterning process combining Ar-ion milling and wet-etching enabled us to fabricate 18-cm-long YBCO coplanar transmission lines as narrow as 5 µm, and these lines did not suffer from electrical shorts even when the spacing was only 2. 5 µm. The surface resistances calculated from the attenuation constants of 5-, 10-, and 25-µm-wide lines provide similar low values of 0. 18-0. 26 mΩ at 10 GHz and 55 K. This indicates that the process damage was sufficiently suppressed despite the narrow line widths. The 5-µm-wide line attained a low attenuation constant of 2. 7 dB/m, which is similar to that in Cu coaxial cables. Even in the 5-µm-wide line, no significant increase in transmission loss was observed up to an input power level of 16 mW at 10 GHz and 55 K. This input power is comparable to that required to propagate digital signals from semiconductor circuits. Therefore high-speed digital signals can propagate through these narrow YBCO coplanar lines without significant attenuation of the signal pulses. Thus, these narrow YBCO coplanar lines can be used in the reentrant delay line memories.

This paper introduces a probabilistic rebound automaton (pra), and investigates its accepting power and closure property. We show that (1) the class of languages recognized by pra's with error probability less than 1/2, PRA, is incomparable with the class of context-free languages, (2) there is a language accepted by a two-way nondeterministic one counter automaton, but not in PRA, and (3) there is a language accepted by a deterministic one-marker rebound automaton, but not in PRA. We also show that PRA is not closed under concatenation and Kleene + .

A fault-tolerant wormhole routing algorithm on mesh-connected processors is proposed. The proposed algorithm is based on the solid fault model and allows the fault polygons to be overlapped. The algorithm compares the position of fault region relative to current channel with the fault direction field of a misrouted message to route around overlapped fault polygons. A node deactivating algorithm to convert non-solid fault region into solid fault region is also proposed. The proposed routing algorithm uses four virtual channels and is deadlock and livelock free.

In this paper, we consider linear subcodes of RMr,m whose bases are formed from the monomial basis of RMr,m by deleting ΔK monomials of degree r where ΔK < . For such subcodes, a procedure for computing the number of minimum weight codewords is presented and it is shown how to delete ΔK monomials in order to obtain a subcode with the smallest number of codewords of the minimum weight. For ΔK 3, a formula for the number of codewords of the minimum weight is presented. A (64,40) subcode of RM3,6 is being considered as an inner code in a concatenated coding system for NASA's high-speed satellite communications. For (64,40) subcodes, there are three equivalent classes. For each class, the number of minimum weight codewords, that of the second smallest weight codewords and simulation results on error probabilities of soft-decision maximum likelihood decoding are presented.

In this paper, we present a method for evaluating the minimum free Chernov distance of trellis-codes for a discrete memoryless channels (DMC). In order to design an efficient trellis-code for the DMC, we need to evaluate the minimum free Chernov distance of the target code. However, the lack of the additive property of the Chernov distance prevents a conventional branch-and-bound search for evaluating the minimum distance. To overcome the difficulty, we present a lower bound on the Chernov distance with an additive property. The lower bound plays a key role in the minimum distance evaluation algorithm presented here. By using the proposed algorithm, we have derived the minimum free Chernov distance of some binary linear convolutional codes over Z-channel.

We have designed rapid single-flux-quantum (RSFQ) adder circuits using two different architectures: one is the conventional architecture employing globally synchronous clocking and the other is the data-driven self-timed (DDST) architecture. It has been pointed out that the timing margin of the RSFQ logic is very sensitive to the circuit parameter variations which are induced by the fabrication process and the device parameter uncertainty. Considering the physical timing in the circuits, we have shown that the DDST architecture is advantageous for realizing RSFQ circuits operating at very high frequencies. We have also calculated the theoretical circuit yield of the DDST adders and shown that a four-bit system operating at 10 GHz is feasible with sufficient operating margin, considering the present 1 kA/cm2 Nb Josephson technology.

This paper presents the performance of FH/MFSK systems, which exploit silent gaps in speech to accommodate more users, over Rayleigh fading channels. Two kinds of receivers are considered: one uses a threshold on the received signal strength to declare whether the signals were present or not, and the other is assumed to have perfect transmitter-state information obtained from using additional bandwidth. Results show that, if the codeword dropping and codeword error are assumed to be equally costly, the former can achieve slightly better performance than the latter in the decoding error probability. This finding suggests that, for the system to exploit silent gaps in speech, it is advantageous for the receiver to use a threshold to declare whether signals were present or not instead of relying on the transmitter-state information.

The DC component suppressing method, called Guided Scrambling (GS), has been proposed, where a source bit stream within a data block is subjected to several kinds of scrambling and a RLL (Run Length Limited) coding to make the selection set of channel bit streams, then the one having the least DC component is selected. Typically, this technique uses a convolutional operation or GF (Galois field) conversion. A review of their respective symbol error properties has revealed important findings. In the former case, the RS (Reed-Solomon) decoding capability is reduced because error propagation occurs in descrambling. In the latter case, error propagation of a data block length occurs when erroneous conversion data occurs after RS decoding. This paper introduces expressions for determining the decoded symbol error probabilities of the two schemes based on these properties. The paper also discusses the difference in code rates between the two schemes on the basis of the result of calculation using such expressions.

In this paper, we propose a new conference key distribution scheme and the supervision of a conference when users are in a level-based hierarchy. In a conference key distribution system, one message is transmitted to the participants from a chairman, a legitimate member can decrypt it and reveal the common session key. The proposed scheme can be implemented without using any tamper-proof hardware. For users in a level-based hierarchy, by applying the key distribution scheme, the higher priority users can derive the conference key and supervise the lower level users' communications. Further, the users in the same level who are not members of the conference or in lower levels can not expose the conference key. To break the common session key, a malicious user has to suffer from the difficulty of factorization and discrete logarithm problems.