This paper presents a practical fault-tolerant architecture for mesh parallel machines that has t spare processors and has 2(t+2) communication links per processor while tolerating at most t+1 processor and link faults. We also show that the architecture presented here can be laid out efficiently in a linear area with wire length at most O(t).

A new broadband space diversity (B-SD) combining method, which is a key technique in the growth of digital microwave radio system, is proposed. In this B-SD combining method, two received signals, whose bandwidths are 280 MHz, are combined. To develop this combining method, an optimum control algorithm is developed that monitors power levels of all primary carriers and controls the endless phase shifter so that the higher level signal is decreased and the lower level signal is increased. This paper describes the proposed B-SD combining method which effectively operates over a wide bandwidth. Performance evaluations based on simulations and theoretical estimations are given. It is proven that this combining method offers the same performance obtained by the conventional narrowband SD combining method and can be applied to over 50% cases of the propagation paths observed in Japan. The suitability of the proposed combining method and the calculation methods adopted is demonstrated experimentally.

In Asiacrypt '96, Bleichenbacher et al. showed the upper limit of the efficiency of one-time digital signature scheme using a directed graph of tree structure as its base. They also claimed that there exists more effective signature scheme on general directed graphs, and showed an example of a method to construct more effective signature schemes as a witness. Unfortunately, their example does not achieve the efficiency as they claimed. This paper shows the upper limit of the efficiency of the signature scheme on general directed graphs by showing no signature scheme is more effective than the optimal signature scheme on trees (or forests). Further, we introduce another signature scheme named pseudo k-time signature scheme. This signature scheme allows signers to sign k-time which is no less efficient than the one time signature scheme.

The addition chain (A-chain) and addition-subtraction chain (AS-chain) are efficient tools to calculate power Me (or multiplication eM), where integere is fixed andM is variable. Since the optimization problem to find the shortest A (or AS)-chain is NP-hard, many algorithms to get a sub-optimal A (or AS)-chain in polynomial time are proposed. In this paper, a window method for the AS-chain and an extended window method for the A-chain and AS-chain are proposed and their performances are theoretically evaluated by applying the theory of the optimal variable-to-fixed length code, i. e. , Tunstall code, in data compression. It is shown by theory and simulation that the proposed algorithms are more efficient than other algorithms in practical cases in addition to the asymptotic case.

In the linear cryptanalysis (LC), to decrease the number of plain/cipher text pairs required for successful attack against DES, it is necessary to improve the effectiveness of the linear approximate expression and to decrease the number of key bits in the expression to be exhaustively searched for. In the previous work, we proposed a linear sieve method to improve the effectiveness of the linear approximate expression. On the other hand, the number of key bits increased. To suppress the number of key bits, we propose Fixed Sieve Linear Cryptanalysis (FS-LC) with fixed sieve key of the linear sieve method. With FS-LC against 8-round DES, we showed the number of plain/cipher text pairs required for sucessful attack is less than that of LC. Furthmore, we extended FS-LC with Kaliski's techniques using the multiple linear approximate expressions to intoroduce Fixed Sieve multiple Linear Cryptanalysis (FS-mLC). With FS-mLC against 8-round DES, computer simulation revealed that it is possible to solve its encryption-key with 220 plain/cipher text pairs. The number of pairs is about a half of the Matsui's 1-round linear cryptanalysis cases.

This paper applies linear cryptanalysis to FEAL and describes the experimental results of attacking FEAL-8 by linear cryptanalysis. The following points are important in linear cryptanalysis to reduce the processing amount and memory size in the attack: 1) to find linear expressions with as high a deviation as possible, and 2) to reduce the number of effective key bits and effective text bits. We have succeeded in attacking FEAL-8 in about 1 hour on a low-end workstation (SPARCstation 10 Model 30). We have confirmed that the entire set of subkeys of FEAL-8 can be derived from 225 known plaintexts with a success rate of over 70%, and from 226 known plaintexts with a success rate of almost 100%.

This paper presents the results of the best differential characteristic search of FEAL. The search algorithm for the best differential characteristic (best linear expression) was already presented by Matsui, and improvements on this algorithm were presented by Moriai et al. We further improve the speed of the search algorithm. For example, the search time for the 7-round best differential characteristic of FEAL is reduced to about 10 minutes (Pentium/166 MHz), which is about 212. 6 times faster than Matsui's algorithm. Moreover, we determine all the best differential characteristics of FEAL for up to 32 rounds assuming all S-boxes are independent. As a result, we confirm that the N-round (7N32) best differential characteristic probability of FEAL is 2-2N, which was found by Biham. For N=6, we find 6-round differential characteristics with a greater probability, 2-11, than that previously discovered, 2-12.

For given integerp, a flow networkNwithn vertices, and sources inN, a problem of finding location ofp sinks inN which maximize the value of maximum flow from sources to sinks is calledp-collection problem. This problem is NP-hard even if a given network is a tree, but a pseudo-polynomial time algorithm is possible for such a network. This paper proposes a new pseudo-polynomial time algorithm for a tree-type network, which is simpler and more efficient than the previous algorithm, and has time complexity of O(p2n2Cc min {Cc,Cd}), whereCc andCd are the maximum edge capacity and the maximum vertex weight, respectively.

In the circumstances we want to deal with, transmission channel is limited and global motion can happen by camera movement, and also there exists a region-of-interest (ROI) which is more important than background. So very low bit rate coding algorithm is required and processing of global motion must be considered. Also ROI must be reconstructed with required quality after decoding because of its importance. But the existing methods such as H. 261, H. 263 are not suitable for such situations because they do not compensate global motion, which needs large amount of transmission bits in motion information and degrades image quality. And also they can not reconstruct ROI's with high quality because they do not consider the fact that ROI's are more important than background. So a new coding scheme is proposed that describes a method for encoding image sequences distinguishing bits between ROI and background. Simulations show that the suggested algorithm performs well especially in the circumstances where background changes and the area of ROI is small enough compared with that of background.

A method is proposed for estimating the error of whole-body average specific absorption rate (SAR) of an infinite-length cylindrical model of man exposed to TM microwave. At high frequencies, the average SAR of the infinite-length cylindrical model is approximately 5% smaller than that of the finite-length cylindrical model.

A novel voltage-tunable linear 3-input CMOS Operational Transconductance Amplifier (OTA) suitable for onchip integration of advanced monolithic systems is proposed. When a 3-input OTA is needed, a conventional 3-input OTA uses two 2-input OTA's and either grounds one of the 4 input terminals or ties two terminals. This paper presents a method to reduce the number of MOS transistors and to save chip area by designing a 3-input OTA directly. A CMOS pair technique is introduced s a solution to minimize a matching problem for control voltage sources. Simulation results show that the active chip area of the proposed 3-input OTA is reduced by 25% compared to that of a conventional one. The proposed 3-input OTA is applied to a realization of an OTA-C filter to verify the effectiveness.

The authors report on a 40-Gbit/s superdynamic decision IC fabricated with 0.12-µm GaAs MESFETs. The key to attaining high-speed decision IC is not only high-speed flip-flop circuits but also wideband input and output buffer circuits. 40 Gbit/s is the fastest operating speed of decision ICs fabricated with GaAs MESFETs.

This paper proposes a novel synchronous acquisition method with an adaptive filter in asynchronous direct sequence/code division multiple access (DS/CDMA) communication systems. An adaptive filter is used in a single-user receiver, in complete synchronization of desired user's signal, the tap coefficients of the filter are controlled to orthogonalize to all other user's spreading sequences without knowledge of the sequences, amplitude and time delays of the signals. While, in the proposed system for synchronous acquisition, the tap coefficients are controlled to orthogonalize to all user's sequences including desired user's signal. The synchronous acquisition can be achieved by using the difference of cross-correlation function value between desired user's sequence of inphase and the tap coefficients for each phase. The principle and performance evaluation for the proposed method are shown. As a result, compared to an acquisition method of conventional sliding correlator, considerable improvement of the average acquisition time can be achieved in large power multiple access interference environment.

Fast and low-power circuit techniques suitable for size-configurable SRAM macrocells are described. An SRAM cell architecture using virtual-GND lines along bitlines is proposed; each virtual-GND line switches the potential by inner read-enable and column-address-decoded signals. Reducing the active power dissipation in the memory array and shortening the time for writing data are simultaneously accomplished. The range of available supply voltages is enhanced by adoptive higher virtual-GND level control with a simple voltage limiter. An SRAM-macrocell test chip is designed and fabricated with 0.5-µm CMOS technology. A 4K-word6-bit organization SRAM demonstrates 186-MHz operation at a 3.3-V typical power supply. Its power dissipation at a practical operating frequency, 100-MHz, is reduced to 29% (25-mW) by the proposed virtual-GND line techniques.

This paper first investigates a relationship between inkdot-depth and inkdot-size of inkdot two-way alternating Turing machines and pushdown automata with sublogarithmic space, and shows that there exists a language accepted by a strongly loglog n space-bounded alternating pushdown automaton with inkdot-depth 1, but not accepted by any weakly o (log n) space-bounded and d (n) inkdot-size bounded alternating Turing machine, for any function d (n) such that limn [d (n)log n/n1/2] = 0. In this paper, we also show that there exists an infinite space hierarchy among two-way alternating pushdown automata with sublogarithmic space.

Many rewriting systems, including those of terms, strings, graphs, and conjunction of atoms, are used throughout computer science and artificial intelligence. While the concepts of "substitutions," "places" in objects and the "replacement" of "subobjects" by other objects seems to be common to all rewriting systems, there does not exist a common foundation for such systems. At the present time, many of the theories are constructed independently, one for each kind of rewritten object. In the conventional approach, abstract rewriting systems are used to discuss common properties of all rewriting systems. However, they are too abstract to capture properties relating to substructures of objects. This paper aims to provide a first step towards a unified formalization of rewriting systems. The major problem in their formulation may be the formalization of the concept of "places". This has been solved here by employment of the concept of contexts rather than by formalization of places. Places determine subobjects from objects, while, conversely, contexts determine objects from subobjects. A class of rewriting systems, called β rewriting systems, is proposed. It is defined on axiomatically formulated base structures, called β structures, which are used to formalize the concepts of "contexts" and "replacement" common to many rewritten objects. The class of β rewriting systems includes very important systems such as semi-Thue systems and Petri Nets. Abstract rewriting systems are also a subclass of β rewriting systems.

A new flow algorithm is described on the basis of the primal-dual method, which is to be adopted dedicatedly for the regeneration of optimal layouts for functional cells of the standard-cell level. In advance of discussing this main theme, the present paper first outlines a practical scheme of reusing those layouts which have been once generated for functional cells in an old fabrication technology, and then formulates an optimization problem for regenerating optimal layouts of functional cells under the constraints incurred by the renewal of design rules. An efficient algorithm proposed here aims at solving this optimization problem with the use of solution concepts for the minimum cost flow problem. A part of experimental results is also shown, which indicates that the proposed altorithm is the fastest for this optimization problem.

From the standpoint of reducing the electromagnetic (EM) absorption in the human head for portable telephones, a ferrite sheet is proposed to use as a protection attachment between the antenna and the head. By using an anatomically based head model and a realistic portable telephone model, the effects of the ferrite sheet on both the reduction of EM absorption and antenna radiation pattern are numerically analyzed by the finite-difference time-domain (FDTD) method. The results show that a ferrite sheet can result in a reduction over 13% for the spatial peak SAR averaged over one gram of tissue relative to a degradation below 0.6 dB for the antenna radiation pattern.

Pilot symbol-assisted (PSA) decision-directed coherent adaptive array diversity (CAAD) is proposed for increasing the reverse link capacity of DS-CDMA mobile radio systems. In the proposed scheme, PSA channel estimation is applied to coherent Rake combining, and the weights of the antenna array are adaptively updated using both pilot symbols and decision-directed data symbols after Rake combining as references for minimum mean squared error (MMSE) criteria. The reverse link capacity of a 3-sectored base station is evaluated by computer simulation when fast transmit power control (TPC) based on singal-to-interference plus backgound noise power ratio (SIR) measurement is applied under nultipath Rayleigh fading environments. It is shown that a 6-element (sector) CAAD receiver can increase the capacity to about 4.2 times that with a single antenna (per sector) receiver when links are interference-limited. The link capacity achievable with the 6-element CAAD receiver is 1.2 times that with a 6-branch antenna diversity reciever with antenna spacing of 10 carrier wavelengths, while significantly reducing the strong interference from high bit rate transmission (high transmit power) users.

Many digital signal processors (DSPs) employ indirect addressing using address registers (ARs) to indicate their memory addresses, which often leads to overhead. This paper presents methods to efficiently allocate addresses for variables in a given program so that overhead in AR update operations is reduced. Memory addressing model is generalized in such a way that AR can be updated at the codes without memory accesses. An efficient memory address allocation is obtained by a method based on the graph linearization algorithm, which takes account of the number of possible AR update operations for every memory access. In order to utilize multiple ARs, methods to assign variables into ARs are also investigated. The proposed methods are applied to the compiler for µPD77230 (NEC) and generated codes for several examples prove effectiveness of these methods.