Kaoru WATANABE Hiroshi TAMURA Masakazu SENGOKU
The p-collection problem is where to locate p sinks in a flow network such that the value of a maximum flow is maximum. In this paper we show complexity results of the p-collection problem. We prove that the decision problem corresponding to the p-collection problem is strongly NP-complete. Although location problems (the p-center problem and the p-median problem) in networks and flow networks with tree structure is solvable in polynomial time, we prove that the decision problem of the p-collection problem in networks with tree structure, is weakly NP-complete. And we show a polynomial time algorithm for the subproblem of the p-collection problem such that the degree sum of vertices with degree3 in a network, is bound to some constant K0.
Teruo AJIMURA Isao YAMADA Kohichi SAKANIWA
It is thought that we have generally succeeded in establishing learning algorithms for neural networks, such as the back-propagation algorithm. However two major issues remain to be solved. First, there are possibilities of being trapped at a local minimum in learning. Second, the convergence rate is too slow. Chang and Ghaffar proposed to add a new hidden node, whenever stopping at a local minimum, and restart to train the new net until the error converges to zero. Their method designs newly generated weights so that the new net after introducing a new hidden node has less error than that at the original local minimum. In this paper, we propose a new method that improves their convergence rate. Our proposed method is expected to give a lower system error and a larger error gradient magnitude than their method at a starting point of the new net, which leads to a faster convergence rate. Actually, it is shown through numerical examples that the proposed method gives a much better performance than the conventional Chang and Ghaffar's method.
Mamoru SAWAHASHI Yoshinori MIKI Hidehiro ANDOH Kenichi HIGUCHI
A pilot symbol-assisted coherent multistage interference canceller (PSA-COMSIC) using recursive channel estimation is proposed for DS-CDMA mobile radio cellular systems. In the proposed scheme, since the channel variation due to fading is recursively estimated at each interference canceling stage, the accuracy of channel estimation is successively improved. The bit error rate (BER) performances against average Eb/N0 (signal energy per bit-to-noise power spectral density ratio) and capacity in the isolated cell are investigated by computer simulations. The simulations demonstrate that the capacity using the PSA-COMSIC with recursive channel estimation is about 1.6 times higher than that of the conventional matched filter receiver with channel coding and bit-interleaving in the interference-limited environments.
Many numerical simulation problems of natural phenomena are formulated by large tridiagonal and block tridiagonal linear systems. In this paper, an efficient parallel algorithm to solve a tridiagonal linear system is proposed. The algorithm named bi-recurrence algorithm has an inherent parallelism which is suitable for parallel processing. Its time complexity is 8N - 4 for a tridiagonal linear system of order N. The complexity is little more than the Gaussian elimination algorithm. For parallel implementation with two processors, the time complexity is 4N - 1. Based on the bi-recurrence algorithm, a VLSI oriented tridiagonal solver is designed, which has an architecture of 1-D linear systolic array with three processing cells. The systolic tridiagonal solver completes finding the solution of a tridiagonal linear system in 3N + 6 units of time. A highly parallel systolic tridiagonal solver is also presented. The solver is characterized by highly parallel computability which originates in the divide-and-conquer strategy and high cost performance which originates in the systolic architecture. This solver completes finding the solution in 10(N/p) + 6p + 23 time units, where p is the number of partitions of the system.
Antonio Di CRESCENZO Luigi M. RICCIARDI
For two devices whose quality is described by non-negative one-dimensional time-homogeneous diffusion processes of the Wiener and Ornstein-Uhlenbeck types sufficient conditions are given such that their failure times, modeled as first-passage times through the zero state, are ordered according to the likelihood ratio ordering.
Ian OPPERMANN Benjamin WHITE Branka S. VUCETIC
This paper presents a model for a wide-band fading channel for terrestrial mobile applications. The model is based on the results of measurements made in a heavily built-up urban environment using a 25 MHz signal centred at approximately 2.6 GHz. This paper presents measured impulse responses and details the parameter extraction process used to determine the characteristics of the channel. These parameters are used in the channel simulation package and the output of these simulations are compared to the original data.
Tomoaki OHTSUKI Iwao SASASE Shinsaku MORI
Cutoff rate of overlapping multi-pulse pulse position modulation (OMPPM) is analyzed in the quantum-limited and the background noise cases. Our results suggest that the derived cutoff rate is higher than conventional one because of the infinite quantization at the demodulator and the definition of the erasure event in conventional analysis.
Tomohiro DOHI Yukihiko OKUMURA Akihiro HIGASHI Koji OHNO Fumiyuki ADACHI
Direct sequence code division multiple access (DS-CDMA) is a promising candidate for 3rd generation mobile communications systems. We recently proposed a coherent multicode DS-CDMA (CM-CDMA) scheme that uses pilot symbol-aided coherent RAKE, interference power measurement based transmit power control, orthogonal multicode transmission, and concatenated channel coding. We have implemented a CM-CDMA test-bed for a series of laboratory and field tests using the 2 GHz band. This paper describes the test-bed system and experimental results are presented. It is confirmed that pilot symbol-aided coherent RAKE can reduce the required signal energy per bit-to-interference plus background noise spectrum density ratio (Eb/Io) by 2-3 dB from that achievable with differential detection. Also shown is that by using both RAKE combining and SIR-based power control the transmit power of mobile stations can be significantly reduced. Measurement results show that the required Eb/Io degrades only slightly when 24 code-channels (768 kbps) are used since orthogonal Gold sequences are used as short spreading codes.
Koichiro DEGUCHI Tsuyoshi SASANO Himiko ARAI Hiroshi YOSHIKAWA
A new application of the factorization method is reported for 3-D shape reconstruction from endoscope image sequences. The feasibility of the method is verified with some theoretical considerations and results of extensive experiments. This method was developed by Tomasi and Kanade, and improved by Poelman and Kanade, with the aim of achieving accurate shape reconstruction by using a large number of points and images, and robustly applying well-understood matrix computations. However, the latter stage of the method, called normalization, is not as easily understandable as the use of singular value decomposition in the first stage. In fact, as shown in this report, many choices are possible for this normalization and a variety of results have been obtained depending on the choice. This method is easy to understand, easy to implement, and provides sufficient accuracy when the approximation used for the optical system is reasonable. However, the details of the theoretical basis require further study.
Tomoko K. MATSUSHIMA Toshiyasu MATSUSHIMA Shigeichi HIRASAWA
Recently, the high-speed data transmission techniques that have been developed for communication systems have in turn necessitated the implementation of high-speed error correction circuits. Parallel processing has been found to be an effective method of speeding up operarions, since the maximum achievable clock frequency is generally bounded by the physical constraints of the circuit. This paper presents a parallel encoder and decoder architecture which can be applied to both binary and nonbinary cyclic codes. The architecture allows H symbols to be processed in parallel, where H is an arbitrary integer, although its hardware complexity is not proportional to the number of parallel symbols H. As an example, we investigate hardware complexity for a Reed-Solomon code and a binary BCH code. It is shown that both the hardware complexity and the delay for a parallel circuit is much less than that with the parallel operation of H conventional circuits. Although the only problem with this parallel architecture is that the encoder's critical path length increases with H, the proposed architecture is more efficient than a setup using H conventional circuits for high data rate applications. It is also suggested that a parallel Reed-Solomon encoder and decoder, which can keep up with optical transmission rates, i.e., several giga bits/sec, could be implemented on one LSI chip using current CMOS technology.
Motohiro ICHIBA Masaaki KATAYAMA Takaya YAMAZATO Akira OGAWA
In this study, we analyze the system which simultaneously transmits spread-spectrum signals with different processing gains. The main purpose of this study is to give an analytical framework that describes the influence of the interfering signals with different processing gains. For this purpose, we define a crosscorrelation function between the spreading sequences with different code lengths, and discuss the effects of interaction between the signals. As the results, we show that the power of the interference component after despreading procedure, the power ratio of the desired to undesired components, and thus the bit error rate are not constant but vary symbol by symbol.
Masazumi KURIHARA Shojiro SAKATA Kingo KOBAYASHI
In this paper we propose a class of byte-error-correcting codes derived from algebraic curves which is a generalization on the Reed-Solomon codes, and present their fast parallel decoding algorithm. Our algorithm can correct up to (m + b -θ)/2b byte-errors for the byte length b, where m + b -θ + 1dG for the Goppa designed distance dG. This decoding algorithm can be parallelized. In this algorithm, for our code over the finite field GF (q), the total complexity for finding byte-error locations is O (bt(t + q - 1)) with time complexity O (t(t + q - 1)) and space complexity O(b), and the total complexity for finding error values is O (bt(b + q - 1)) with time complexity O (b(b + q - 1)) and space complexity O (t), where t(m + b -θ)/2b. Our byte-error-correcting algorithm is superior to the conventional fast decoding algorithm for randomerrors in regard to the number of correcting byte-errors in several cases.
Suichi TAHARA Shuichi NAGASAWA Hideaki NUMATA Yoshihito HASHIMOTO Shinichi YOROZU
Superconductive LSIs with Josephson junctions have features such as low power dissipation and high switching speed. In this paper, we review our developed 4-Kbit RAM with vortex transitional memory cells as an illustration of superconductive LSIs with Josephson junctions. We have developed a fabrication process technology for the 4-Kbit RAM. In the 4-Kbit RAM, 380ps access time and 9.8 mW power dissipation have been experimentally obtained. And also, we have estimated a suitable moat structure to reduce the influence of trapped magnetic structure. The 4-Kbit RAM has been successfully operated with a bit yield of 99.8%. Furthermore, we discuss GHz testing which is one of the most significant issues concerning superconductive digital LSIs.
Shigefusa SUZUKI Takao NAKANISHI
Personal communication systems (PCS) have more signalling traffic than conventional fixed networks and require large-scale databases to manage users' profiles, which are sets of data items, such as the location the user is currently visiting and the user's authentication key, necessary for a PCS user to be provided with PCS services. This paper focuses on inter-network roaming in PCS environments. In designing a PCS supporting roaming service, it is essential to avoid increased signalling traffic and data searching time in the database. We first identify the appropriate domains for three routing schemes-Direction Routing, Redirection Routing, and Look-ahead Routing-from the viewpoints of the number of signals for inter-network roaming and roaming probability. We do this for two kinds of PCS database network architecture, Home Location Register (HLR) and Visitor Location Register (VLR), and show that Look-ahead Routing is the best scheme for the HLR network architecture (considering the number of signals for intra-network and inter-network database access) and that in the VLR network architecture, the decreasing of the roaming probability expands domains for which Redirection Routing is appropriate. We also propose a generic PCS data model that inter-network roaming interfaces can use to search effectively for a user's profile. The data model clarifies the contents of a set of data items which share certain characteristics, data items that the contents compose, and the relationships (data structures) between sets of data items. The model is based on the X. 500 series recommendations, which are applied for an Intelligent Network. We also propose a data structure between sets of data items using the directory information tree and show the ASN. 1 notations of the data model.
An individual identification system is developed. In this system, we unify profile curve identification and full face image identification to obtain more successful recognition rate. In profile cruve identification process, the P-type Fourier descriptor is made use of. In full face image identification process, mosaic density values are made use of. A combination of the two processes shows higher recognition rates than those obtained by each single process.
Shin NAKAMURA Eiji UCHINO Takeshi YAMAKAWA
C1 class smooth interpolation by a fuzzy reasoning for a small data set is proposed. The drafting technique of a human expert is implemented by using a set of fuzzy rules. The effectiveness of the present method is verified by computer simulations and by applications to the practical interpolation problem in a power system.
Katsumi SUZUKI Seiichi TOKUNAGA Masahito BAN Masashi OHTSUKA Youichi ENOMOTO
Here we report on a fabrication and a millimeter-wave performance of reliable and reproducible high-Tc superconducting (HTS) Josephson junctions on MgO substrates using a focused Ga ion beam (FIB). The junction normal resistance Rn can be controlled by making the junction in a series. The Rn depends on space between each junction in the series structure. A mechanism of the junction is proposed by measuring cross-sectional transmission electron microscopy (TEM) images and their X-ray spectra of Ga, Y, Ba, Cu, Mg and O. The junctions with more than 1 µm spaces, and flat and lateral structure are independent each other for the crystallization process. We observe the HTS mixer-antenna performance as fundamental/harmonic mixers in the wide frequency range up to 100 GHz.
For Nakagami-Rice fading environment which seems to become a principle propagation environment in the next generation wideband and high-capacity mobile systems such as personal communications, we have previously proposed an approximated evaluation scheme for wideband digital transmission characteristics such as errors due to intersymbol interference of multipath waves. We called the scheme 'Equivalent Transmission-Path (ETP) Model.' In this paper, through a discussion about more general equivalent propagation channel expressions, we clarify a theoretical foundation of the ETP model and extend the model to have an ability of expression of instantaneous fading condition varying with time. Also the appropriateness of the instantaneous expression is examined by a computer simulation analysis. Based on this model, statistics of link quality and service availability in Nakagami-Rice fading environments are discussed.
Hiroyuki OHMINE Yonehiko SUNAHARA Makoto MATSUNAGA
This paper presents a configuration of circularly polarized annular-ring microstrip antenna (ARMSA) and its design method to obtain high gain and low axial ratio including the analysis of finite ground plane effect using G.T.D. for personal satellite communication use. The ARMSA excited at TM21 mode through co-planar branch-line hybrid coupler for circular polarization produces a conical pattern which has high gain in low elevation angle. The relation of gain and axial ratio versus the dielectric constant of substrate are shown and the existence of the dielectric constant which satisfies two requirements, that is, high gain and low axial ratio are clarified. For car-top application, experimental results in the L-band showed satisfactory characteristics for vehicle antenna.
Kay NOGUCHI Makoto ANDO Nao-hisa GOTO Masa-nobu HIROSE Toru UNO Yoshi-tsugu KAMIMURA
The advantages of the use of directional antennas for portable telephones are demonstrated. They contribute to (1) reduction of power absorption into a head, (2) reduction of multi-path interference, and (3) power saving and increase of a battery life time. This paper compares directional and omni-directional antennas existing near the head of operator, in terms of radiation patterns with a head and the power absorbed into a head. It is pointed out that radiation patterns with a head are more or less directive for both types of antennas, while the power absorbed into a head is much smaller for directional antennas.