This letter treats computational complexity of bounded asymmetric choice (AC) net. AC net is a subclass of Petri net that properly includes the class of well-known extended free choice net. It is shown that satisfiability problem of Boolean expressions is polynomial time reducible to liveness problem of bounded AC nets. This implies that the problem is NP-hard.

Petri net is a powerful modeling tool for concurrent systems. Liveness, which is a problem to verify there exists no local deadlock, is one of the most important properties of Petri net to analyze. Computational complexity of liveness of a general Petri net is deterministic exponential space. Liveness is studied for subclasses of Petri nets to obtain necessary and sufficient conditions that need less computational cost. These are mainly done using a subset of places called siphons. CS-property, which denotes that every siphon has token(s) in every reachable marking, in one of key properties in liveness analysis. On the other hand, normal Petri net is a subclass of Petri net whose reachability set can be effectively calculated. This paper studies computational complexity of liveness problem of normal Petri nets. First, it is shown that liveness of a normal Petri net is equivalent to cs-property. Then we show this problem is co-NP complete by deriving a nondeterministic algorithm for non-liveness which is similar to the algorithm for liveness suggested by Howell et al. Lastly, we study structural feature of bounded Petri net where liveness and cs-property are equivalent. From this consideration, liveness problem of bounded normal Petri net is shown to be deterministic polynomial time complexity.

This paper proposes a new multi-task synchronization scheme for packet mode orthogonal frequency division multiplexing (OFDM) signals in multi-input multi-output (MIMO) transmission systems; it targets high-rate wireless LANs that offer over 100 Mbit/s. In addition, this paper introduces a packet format for MIMO-OFDM signals that ensures backward compatibility with IEEE 802.11a. The proposed synchronization scheme has simple open-loop construction and consists of automatic frequency control (AFC), symbol timing detection, MIMO channel estimation, and phase tracking. AFC and symbol timing detection are carried out in the time-domain. After OFDM demodulation, the proposed scheme performs MIMO channel estimation and phase tracking in the frequency-domain. Considering all of the above synchronization tasks, we evaluate the packet error rate (PER) performance using the IEEE 802.11 TGn-defined channel model-D and model-E. In channel model-D with the RMS delay spread = 50 ns, the proposed scheme shows superior performance; it suppress the required Eb/N0 degradation to within 0.4 dB with 1000 byte packets compared to the performance achieved if only MIMO channel estimation is considered. Moreover, in channel model-E with the RMS delay spread = 100 ns, it is found that the proposed scheme degrades the required Eb/N0 only by approximately 1.5 dB compared to the MIMO channel estimation only case, even if the packet length is 1000 bytes with 64QAM and coding-rate = 7/8.

This paper presents experimental results of our proposed null-space expansion scheme for multiuser massive multiple-input multiple-output (MIMO) in time varying channels. Multiuser MIMO transmission with the proposed scheme can suppress the inter-user interference (IUI) caused by outdated channel state information (CSI). The excess degrees of freedom (DoFs) of massive MIMO is exploited to perform additional null-steering using past estimated CSI. The signal-to-interference power ratio (SIR) and spectral efficiency performances achieved by the proposed scheme that uses measured CSI is experimentally evaluated. It is confirmed that the proposed scheme shows performance superior to the conventional channel prediction scheme. In addition, IUI can be stably suppressed even in high mobility environments by further increasing the null-space dimension.

This paper proposes a practical application of Massive MIMO technology, Massive Antenna Systems for Wireless Entrance (MAS-WE), and along with related inter-user interference cancellation (IUIC) and scheduling techniques. MAS-WE, in which the entrance base station (EBS) employs a large number of antennas, can effectively provide high capacity wireless entrance links to a large number of access points (APs) distributed over a wide coverage area. The proposed techniques are simplified to practical implementation; EBS side uses around 100 antenna elements to spatially multiplex more than 16 signal streams. SIR performance is evaluated by system level simulations that consider imperfect channel state information (CSI). The results show that MAS-WE with the proposed techniques can reliably achieve high spectral efficiency with high level space division multiplexing.

This paper proposes an antenna selection method for terminal antennas employing orthogonal polarizations and patterns, which is suitable for outdoor MultiUser Multi-Input Multi-Output (MU-MIMO) systems. In addition, this paper introduces and verifies two other antenna selection methods for comparison. For the sake of simplicity, three orthogonal dipoles are considered, and this antenna configuration using the proposed selection method is compared to an antenna configuration with three vertical or horizontal dipoles. In the proposed antenna selection method, we always choose the vertical dipole, and choose one of two horizontal dipoles, which are orthogonal to each other, based on the Signal-to-Noise Ratio (SNR). We measured the MU-MIMO transmission properties and found that the proposed selection method employing the antenna with orthogonal polarizations and patterns can offer fairly high channel capacity in a multiuser scenario.

Most of scientists except computer scientists do not want to make efforts for performance tuning with rewriting their MPI applications. In addition, the number of processing elements which can be used by them is increasing year by year. On large-scale parallel systems, the number of accumulated messages on a message buffer tends to increase in some of their applications. Since searching message queue in MPI is time-consuming, system side scalable acceleration is needed for those systems. In this paper, a support function named LHS (Limited-length Head Separation) is proposed. Its performance in searching message buffer and hardware cost are evaluated. LHS accelerates searching message buffer by means of switching location to store limited-length heads of messages. It uses the effects such as increasing hit rate of cache on host with partial off-loading to hardware. Searching speed of message buffer when the order of message reception is different from the receiver's expectation is accelerated 14.3 times with LHS on FPGA-based network interface card (NIC) named DIMMnet-2. This absolute performance is 38.5 times higher than that of IBM BlueGene/P although the frequency is 8.5times slower than BlueGene/P. LHS has higher scalability than ALPU in the performance per frequency. Since these results are obtained with partially on loaded linear searching on old Pentium®4, performance gap will increase using state of art CPU. Therefore, LHS is more suitable for larger parallel systems. The discussions for adopting proposed method to state of art processors and systems are also presented.

Petri net is an efficient model for concurrent systems. Liveness is one of analysis properties of Petri net. It concerns with potential fireability of transitions. Many studies have been done on liveness of Petri nets and subclasses are suggested with liveness criteria. In this paper, extended partially ordered condition (EPOC) net is suggested and its liveness is studied. Equivalence of liveness and place-liveness is derived. Analysis using siphon and traps are done. Liveness under the earliest firing rule, where transition must fire as soon as it is enabled, is also studied.

Petri net is a mathematical model for concurrent systems. Petri net is known to have less modeling power than that of Turing machine. Lack of zero testing ability is the main reason of this fact. Indeed, every extended Petri net model that can perform zero testing is equivalent to Turing machine. Time Petri net is one of the models with ability of zero testing. It is of theoretical interest what structure enables zero testing. This paper shows that time asymmetric choice net can simulate register machines. The result implies reachability problem of this subclass of time Petri net is undecidable.

Petri net is a graphical and mathematical modeling tool for discrete event systems. This paper treats analysis problems of time Petri nets. In this model, a minimal and a maximal firing delays are assigned to each transition. If a transition is 'enabled' it can fire after minimal delay has passed and must fire before maximal delay has elapsed. Since time Petri net can simulate register machines, it has equivalent modeling power to that of Turing machine. It means, however, that most of the analysis problems of time Petri nets with general net structures are undecidable. In this paper, net structures are restricted to a subclass called partially ordered condition (POC) nets and dissynchronous choice (DC) nets. Firing delays are also restricted to satisfy 'static fair condition' which assures chance to fire for all transitions enabled simultaneously. First, a sufficient condition of liveness of time POC net with the static fair condition is derived. Then it is shown that liveness of time DC net with static fair condition is equivalent to liveness of the underlying nontime net. This means that liveness problem of this class is decidable. Lastly, liveness problem of extended free choice (EFC) net is shown to be decidable.

Petri net is a powerful modeling tool for concurrent systems. Subclasses of Petri net are suggested to model certain realistic applications with less computational cost. Structurally weakly persistent net (SWPN) is one of such subclasses where liveness is verified in deterministic polynomial time. This paper studies the computational complexity to verify whether a give net is SWPN. 3UNSAT problem is reduced to the problem to verify whether a net is not SWPN. This implies co-NP completeness of verification problem of SWPN.

Petri net is a mathematical model for concurrent systems. Liveness is one of important properties of Petri net. Liveness problem of general Petri net is of exponential space complexity and subclasses are suggested with less computational complexity. It is well known that liveness problem of bounded (extended) free choice net is solved in deterministic polynomial time. This paper treats liveness problem of AC/DC nets. AC/DC net is a subclass of Petri net that exhibits no confusion (mixture of concurrency and conflict). This class properly includes the class of free choice nets. It is shown that every minimal siphon of an AC/DC net is trap if and only if every strongly connected siphon is a trap. This result shows that monotone liveness of bounded AC/DC net is solved in deterministic polynomial time. It is shown that this result is true of bounded time AC/DC net with static fair condition.

A propagation experiment on an actual channel is conducted to confirm the effectiveness of the 1-tap time domain beamforming (TDBF) technique we proposed in previous work. This technique offers simple beamforming for the millimeter waveband massive multiple-input multiple-output (MIMO) applied wireless backhaul and so supports the rapid deployment of fifth generation mobile communications (5G) small cells. This paper details propagation experiments in the 75GHz band and the characteristics evaluations of 1-tap TDBF as determined from actual channel measurements. The results show that 1-tap TDBF array gain nearly equals the frequency domain maximal ratio combining (MRC) value, which is ideal processing; the difference is within 0.5dB. In addition, 1-tap TDBF can improve on the signal-to-interference power ratio (SIR) by about 13% when space division multiplexing (SDM) is performed assuming existing levels of channel estimation error.

This paper proposes a simple and feasible decision-feedback channel tracking scheme for multiple-input multiple-output orthogonal frequency division multiplexing (MIMO-OFDM) systems designed for wireless local area networks (LANs). In the proposed scheme, the channel state matrix for each subcarrier is tentatively estimated from a replica matrix of the transmitted signals. The estimated channel matrices, each derived at a different timing, are combined, and the previously estimated channel matrices are replaced with the latest ones. Unlike conventional channel tracking schemes based on a Kalman filter, the proposed scheme needs no statistical information about a MIMO channel, which makes the receiver structure quite simple. The packet error rate (PER) performances for the proposed scheme are evaluated on computer simulations. When there are three transmit and receive antennas, the subcarrier modulation scheme is 64 QAM, and the coding rate is 3/4, the proposed scheme keeps the SNR degradation at PER of 1e-2 less than 0.1 dB when the velocity of receiver is 3 km/h in an indoor office environment at 5 GHz band. In addition, compared to the conventional channel tracking scheme based on known pilot symbols, the proposed scheme improves throughput performance by 13.8% because it does not need pilot symbols. These results demonstrate that the proposed channel tracking scheme is simple and feasible for implementation in MIMO-OFDM systems based on wireless LANs.

It is indispensable to establish a multi-access protocol and resource management technique that can assure transmission quality and efficiently utilize the radio frequency spectrum for ATM-based wireless access systems. This paper proposes dynamic time-slot assignment schemes for the forward link from a user to a central station (CS): (1) the centralized assignment and release scheme (CAR), and (2) the centralized-assignment and autonomous-release scheme (CAAR). In the proposed schemes, a central station dynamically assigns time-slots based on traffic information obtained by monitoring the input traffic in each radio module (RM). In addition, forward protection is used to prevent false-release of assigned time-slots. Performance evaluations have been carried out by analysis as well as computer simulations. They show that the proposed schemes achieve good performance in delay, link stability, and utilization efficiency of radio resources with an optimized number of forward protection steps.

Multiuser multiple input multiple output (MU-MIMO) systems are attracting attention due to their frequency efficiency. However, in uplink MU-MIMO systems, different frequency offsets among multiple mobile stations (MSs) significantly degrade the transmission quality, especially when orthogonal frequency division multiplexing (OFDM) is used. In this paper, the influence of these frequency offsets is first analyzed in a frequency selective fading environment. Numerical analysis shows that an error floor occurs in the bit error rate and the influence of the frequency offset becomes larger in short delay spread environments. To overcome this problem, a new beamforming method is proposed to compensate for the frequency offset by introducing an auto frequency controller after frequency-space equalization in each data stream. The effect of the proposed method is evaluated in a frequency selective fading environment by computer simulations and measured results.

Multiuser -- Multiple Input Multiple Output (MU-MIMO) techniques were proposed to increase spectrum efficiency; a key assumption was that the Mobile Terminals (MTs) were simple with only a few antennas. This paper focuses on the Block Diagonalization algorithm (BD) based on the equal power allocation strategy as a practical MU-MIMO technique. When there are many MTs inside the service area of the access point (AP), the AP must determine, at each time slot, the subset of the MTs to be spatially multiplexed. Since the transmission performance depends on the subsets of MTs, the user selection method needs to use the Channel State Information (CSI) obtained in the physical layer to maximize the Achievable Transmission Rate (ATR). In this paper, we clarify the relationship between ATR with SU-MIMO and that with MU-MIMO in a high eigenvalue channel. Based on the derived relationship, we propose a new measure for user selection. The new measure, the eigenvalue decay factor, represents the degradation of the eigenvalues in null space compared to those in SU-MIMO; it is obtained from the signal space vectors of the MTs. A user selection method based on the proposed measure identifies the combination of MTs that yields the highest ATR; our approach also reduces the computational load of user selection. We evaluate the effectiveness of user selection with the new measure using numerical formulations and computer simulations.

This paper proposes a graph-theory-based Euler number computing algorithm. According to the graph theory and the analysis of a mask's configuration, the Euler number of a binary image in our algorithm is calculated by counting four patterns of the mask. Unlike most conventional Euler number computing algorithms, we do not need to do any processing of the background pixels. Experimental results demonstrated that our algorithm is much more efficient than conventional Euler number computing algorithms.