A routing algorithm, utilizing two-hop relaying when necessary, is proposed to enhance the system capacity of code division multiple access (CDMA) cellular systems. Up to now, multihop relaying is applied to cellular systems mainly with the aim of decreasing the transmit power of each mobile station or extending the cell coverage area. Here, in this paper, potential benefit of multihop relaying is studied so as to increase the system capacity. A condition for the interference to be reduced by changing single-hop connections to two-hop connections is analyzed. In addition, a new route selection criterion maximizing the amount of interference reduction is proposed. Simulation results reveal that the proposed criterion is superior to the conventional criterion minimizing the total transmit power in respect of the amount of interference reduction. By using this criterion, an efficient routing algorithm for two-hop CDMA cellular systems is proposed to enhance the system capacity. Simulation results also indicate that by using the proposed routing algorithm in combination with a call admission control, the system capacity is increased even under heavy traffic conditions.

This paper presents a system for reading comics on cellular phones. It is necessary for comic images to be divided into frames and the contents such as speech text to be displayed at a comfortable reading size, since it is difficult to display high-resolution images in a low resolution cellular phone environment. We have developed a scheme how to decompose comic images into constituent elements frames, speech text and drawings. We implemented a system on the internet for a cellular phone company in our country, that provides downloadable comic data and a program for reading.

The rapid spread of cellular phones in recent years has facilitated not only voice communication but also Internet access via the cellular phone system, and in addition, subscriber demand has led to a diversification in the services provided. One service in high demand is the seamless use of cellular phones in both public and private wireless network areas. In the data world, there is already such an application in the form of public and private use of wireless LAN. However, an increase in the number of users would require the realization of low-cost, easy-to-install very small base stations (VSBS) that use the frequency band efficiently in order to allow private use of ordinary cellular phones. To bring such VSBS into effect, a technology that autonomously selects frequencies which do not interfere with the public communication system from out of the publicly used frequency band is essential for turning such VSBS into reality. This paper proposes a frequency selection algorithm that actively uses cellular phone features such as frequency selection and received signal level measurement, and discusses the results of verification experiments.

Band Division MC-CDM (BD-MC-CDM) has been proposed for high quality wireless communications and has been investigated in terms of link level performance. In this paper, we investigate frequency band and time slot selection technique from the viewpoint of system level performance in order to realize the efficient BD-MC-CDM system under cellular environments. Then a downlink frequency band and time slot selection scheme is proposed for cellular BD-MC-CDM systems. The proposed scheme selects transmission frequency band according to the signal-to-interference ratio (SIR) estimated by using the pilot signal at mobile stations and also selects transmission time slot by using the SIR threshold. Simulation results show that the proposed scheme improves the downlink throughput but degrades delay performance and it has a trade off between throughput and delay performance. By selecting suitable control parameters, the proposed scheme achieves the throughput improvement without sacrificing the delay performance.

This paper presents time slot assignment algorithms applicable to uplink of space division multiple access (SDMA)/time division multiple access (TDMA) systems with adaptive antennas. In the time slot assignment process for a new terminal in a cell, we consider not only the signal quality of the new terminal but also that of active terminals in the same cell. Intra-cell hand over is performed for an active terminal when its signal quality deteriorates. We evaluate the blocking and forced termination probabilities for pure TDMA systems, sectorized systems, and SDMA/TDMA systems in cellular environments by computer simulations. The simulation results show that the SDMA/TDMA systems have much better performance than the pure TDMA and sectorized systems.

This paper studies the propagation and crossing of signals in cellular automata whose cells are updated at random times. The signals considered consist of a core part, surrounded by an insulating sheath that is missing at the side of the core that corresponds to the direction into which the signal moves. We study two types of signals: (1) signals by which the sheath at the left and right sides of the core advance first in a propagation step, followed by the core, and (2) signals by which the core advances first, followed by the sheath at its left and right sides. These types naturally arise in, respectively, Moore neighborhood cellular automata with semi-totalistic rules and von Neumann neighborhood cellular automata with symmetric transition rules. The type of a signal has a profound impact on the way signals cross each other, as we show by the construction of one signal of each type. The results we obtained should be of assistance in constructing asynchronous circuits on asynchronous cellular automata.

The floor field model, which is a cellular automaton model for studying evacuation dynamics, is investigated and extended. A method for calculating the static floor field, which describes the shortest distance to an exit door, in an arbitrary geometry of rooms is presented. The wall potential and contraction effect at a wide exit are also proposed in order to obtain realistic behavior near corners and bottlenecks. These extensions are important for evacuation simulations, especially in the case of panics.

A number-conserving cellular automaton (NCCA) is a cellular automaton (CA) such that all states of cells are represented by integers and the sum of the cell states is conserved throughout its computing process. It can be thought of as a kind of modelization of the physical conservation law of mass or energy. It is known that the local function of a two-dimensional 45-degree reflection-symmetric von Neumann neighbor NCCA can be represented by linear combinations of a binary function. In spite of the number-conserving constraints, it is possible to design an NCCA with complex rules by employing this representation. In this paper, we study the case in which the binary function depends only on the difference of two cell states, i.e., the case in which the function can be regarded as a unary one and its circuit for applying rules to a cell only need adders and a single value table look up module. Even under this constraint, it is possible to construct a logically universal NCCA.

In this paper we study a classical firing squad synchronization problem on a model of fault-tolerant cellular automata that have possibly some defective cells. Several fault-tolerant time-efficient synchronization algorithms are developed based on a simple freezing-thawing technique. It is shown that, under some constraints on the distribution of defective cells, any cellular array of length n with p defective cell segments can be synchronized in 2n - 2 + p steps.

Automata based image compression methods exploit similarities in the images to reduce the amount of memory to the essential. Our cellular automata methods are motivated due to the fact that they may be used to create images on liquid crystal displays when we add some computational functionality to the displays. For this purpose we consider image generation methods in cellular automata with some reasonable restrictions and get a representation where the color values of the images can be derived directly from the single cell states. We are interested in the capabilities of such devices and provide some benefits of this representation in image compression, even in higher dimensions.

The descriptional complexity of iterative arrays (IAs) is studied. Iterative arrays are a parallel computational model with a sequential processing of the input. It is shown that IAs when compared to deterministic finite automata or pushdown automata may provide savings in size which are not bounded by any recursive function, so-called non-recursive trade-offs. Additional non-recursive trade-offs are proven to exist between IAs working in linear time and IAs working in real time. Furthermore, the descriptional complexity of IAs is compared with cellular automata (CAs) and non-recursive trade-offs are proven between two restricted classes. Finally, it is shown that many decidability questions for IAs are undecidable and not semidecidable.

In this paper, we investigate how to initialise cellular automata implemented in the hyperbolic plane. We generalise a technique which was indicated in to the case of any rectangular regular grid of the hyperbolic plane. This allows us to construct the initial configuration of any cellular automaton belonging to a rather large class of problems.

This paper investigates relationships among deterministic, nondeterministic, and alternating complexity classes defined in the hyperbolic space. We show that (i) every t(n)-time nondeterministic cellular automaton in the hyperbolic space (hyperbolic CA) can be simulated by an O(t4(n))-space deterministic hyperbolic CA, and (ii) every t(n)-space nondeterministic hyperbolic CA can be simulated by an O(t2(n))-time deterministic hyperbolic CA. We also show that nr+-time (non)deterministic hyperbolic CAs are strictly more powerful than nr-time (non)deterministic hyperbolic CAs for any rational constants r 1 and > 0. From the above simulation results and a known separation result, we obtain the following relationships of hyperbolic complexity classes: Ph= NPh = PSPACEh EXPTIMEh= NEXPTIMEh = EXPSPACEh , where Ch is the hyperbolic counterpart of a Euclidean complexity class C. Furthermore, we show that (i) NPh APh unless PSPACE = NEXPTIME, and (ii) APh EXPTIME h.

A reversible cellular automaton (RCA) is a computing model having a property analogous to physical reversibility. We investigate the problem of finding simple RCAs in which any circuit composed of rotary elements (REs) can be embedded. Since an RE is known to be a universal reversible logic element, such RCAs are also universal in this respect. In this paper, after giving a survey of known results on RE and its implementation in RCAs, we propose a new RCA model in which REs and some signal routing elements can be embedded. The new model has a simpler local transition function (in the sense it is described by fewer rules) than the previous one, though the number of states is the same. In addition, the patterns realizing an RE and signal routing elements are smaller than those of the previous model.

The capabilities of reliable computations in one-dimensional cellular automata are investigated by means of the Early Bird Problem. The problem is typical for situations in massively parallel systems where a global behavior must be achieved by only local interactions between the single elements. The cells that cause the misoperations are assumed to behave as follows. They run a self-diagnosis before the actual computation once. The result is stored locally such that the working state of a cell becomes visible to its neighbors. A non-working (defective) cell cannot modify information but is able to transmit it unchanged with unit speed. We present an O(n log (n) log (n))-time fault-tolerant solution of the Early Bird Problem.

In this paper, a new grouping method for Group Technology using Self-Organizing Map (SOM) is proposed. The purpose of our study is to divide machines in a factory into any number of cells so that the machines in each cell can process a similar set of parts to increase productivity. A main feature of our method is to specify not only the number of the cells but also the maximum and minimum numbers of machines in a cell. Some experimental results show effectiveness of our proposed algorithm.

A special group of voice application services (VASs) are promising contents for wireless as well as wireline networks. Without a designated call admission policy, VAS calls are expected to suffer from relatively high probability of blocking since they normally require better signal quality than ordinary voice calls. In this letter, we consider a prioritized call admission design in order to reduce the blocking probability of VAS calls, which makes the users feel the newly-provided VAS in belief. The VAS calls are given a priority by reserving a number of channel-processing hardwares. With the reservation, the blocking probability of prioritized VAS calls can be evidently reduced. That of ordinary calls, however, is increasing instead. This letter provides a system model that counts the blocking probabilities of VAS and ordinary calls simultaneously, and numerically examines an adequate level of the prioritization for VAS calls.

In this paper, we propose a new predictive location management strategy that reduces the update cost while restricting the paging load optimized for mobiles roaming with traceable patterns. Enhanced with directional predictive capabilities offered by Kalman filtering, new update boundaries are assigned to better reflect the movement patterns of individual mobiles upon location registration. Thus, while complying with the required delay constraints, QoS measures such as throughput will not need to be sacrificed as a result of increasing update threshold. The contribution of this paper is two-fold: (1) to propose a distribution model that is capable of describing a wide range of movement patterns with varying correlation between traveling directions and (2) to show the capabilities (in terms of reliable performances) of the Kalman filter in predicting future movement patterns. Simulation results have successfully demonstrated the ability of the Kalman filter in assigning update boundaries capable of reflecting a mobile's roaming characteristics. The performance gains achieved mainly through a significant reduction in the number of updates indicate its potential for promoting better bandwidth conservation.

Interference Cancellation (IC) receivers can be used in CDMA cellular systems to improve the capacity. The IC receivers can be divided into two main categories, Single-User Detectors (SUD) and Multi-User Detectors (MUD). They have different characteristics in terms of intra-cell and inter-cell interference cancellation ratios. In this paper we first introduce the Normalized Griffiths' algorithm, a SUD receiver, and compare its basic performance with the well-known Serial IC. Next we examine the multi-cell performance of SUD and MUD receivers by using multi-cell link-level simulations. The results show that even though MUD receiver has clearly better single-cell performance, the SUD receiver will gain in performance in the multi-cell cases. In the three-sector multi-cell case, their performance even becomes very similar. These results are obtained using ideal conditions to be able to study the receivers' basic properties related to intra-cell and inter-cell interference.

In this paper, we propose the soft boundary concept achieved by dynamic tilted antenna to solve the issue of traffic congestion occurred in cellular wireless systems. The tilted antenna array can provide the merit of traffic balance and also achieve the optimization of the signal-to-interference ratio (SIR) at receivers by automatically tilting the antenna and implementing the soft boundary among cells, corresponding to the variation of traffic. According to our results, it is shown that power ratio control do not necessarily improved system performance when there is a large variation in traffic because it only control power levels. Also the properly chosen angle of tilt antenna can relieve the traffic congestion and perform the system performance optimization.