Takeo FUJII Yukihiro KAMIYA Yasuo SUZUKI
Post-FFT type orthogonal frequency division multiplexing (OFDM) adaptive array antennas can reduce the co-channel interference with a few antenna elements under multi-path fading environments. However, the Post-FFT type OFDM adaptive array antennas require a lot of pilot symbols in order to determine the optimal weights in each subcarrier. In packet communication systems, since the data are transmitted burst by burst, the ratio of the effective data in a channel decreases when the long pilot symbols are used. Recursive least squares (RLS) algorithm is one of the weight optimization algorithm with fast convergence based on minimum mean square errors (MMSE). However, the optimal weight determination with a few pilot symbols is difficult. Therefore, in this paper, we propose a novel multi-stage RLS OFDM adaptive array antenna for realizing weight determination with a few pilot symbols. In the proposed method, the weights are optimized by using a multiple stage structure with the stored pilot symbols. Here, the initial weights and the initial inverse matrix of correlation matrix are decided by the results of the weight determination in the adjacent subcarriers of the previous stage. As a result, the weight determination with a few pilot symbols can be achieved.
Eduard A. JORSWIECK Holger BOCHE
The average performance of a single-user MIMO system under spatially correlated fading and with different types of CSI at the transmitter and with perfect CSI at the receiver was studied in recent work. In contrast to analyzing a single performance metric, e.g. the average mutual information or the average bit error rate, we study an arbitrary representative of the class of matrix-monotone functions. Since the average mutual information as well as the average normalized MSE belong to that class, this universal class of performance functions brings together the information theoretic and signal processing performance metric. We use Lowner's representation of operator monotone functions in order to derive the optimum transmission strategies as well as to characterize the impact of correlation on the average performance. Many recent results derived for average mutual information generalize to arbitrary matrix-monotone performance functions, e.g. the optimal transmit strategy without CSI at the transmitter is equal power allocation. The average performance without CSI is a Schur-concave function with respect to transmit and receive correlation. In addition to this, we derive the optimal transmission strategy with long-term statistics knowledge at the transmitter and propose an efficient iterative algorithm. The beamforming-range is the SNR range in which only one data stream spatially multiplexed achieves the maximum average performance. This range is important since it has a simple receiver structure and well known channel coding. We entirely characterize the beamforming-range. Finally, we derive the generalized water-filling transmit strategy for perfect CSI and characterize its properties under channel correlation.
Tsunehiro YOSHINAGA Jianliang XU Katsushi INOUE
This paper investigates the accepting powers of two-way alternating Turing machines (2ATM's) with only existential (universal) states which have inkdots and sublogarithmic space. It is shown that for sublogarithmic space-bounded computations, (i) multi-inkdot 2ATM's with only existential states and the ones with only universal states are incomparable, (ii) k-inkdot 2ATM's are better than k-inkdot 2ATM's with only existential (universal) states, k ≥ 0, and (iii) the class of sets accepted by multi-inkdot 2ATM's with only existential (universal) states is not closed under complementation.
Mitsugu IWAMOTO Lei WANG Kazuki YONEYAMA Noboru KUNIHIRO Kazuo OHTA
In this paper, a method is proposed to construct a visual secret sharing (VSS) scheme for multiple secret images in which each share can be rotated with 180 degrees in decryption. The proposed VSS scheme can encrypt more number of secret images compared with the normal VSS schemes. Furthermore, the proposed technique can be applied to the VSS scheme that allows to turn over some shares in decryption. From the theoretical point of view, it is interesting to note that such VSS schemes cannot be obtained from so-called basis matrices straightforwardly.
Dong-Guk HAN Katsuyuki OKEYA Tae Hyun KIM Yoon Sung HWANG Beomin KIM Young-Ho PARK
We propose a new analysis technique against a class of countermeasure using randomized binary signed digit (BSD) representations. We also introduce some invariant properties between BSD representations. The proposed analysis technique can directly recover the secret key from power measurements without information for algorithm because of the invariant properties of BSD representation. Thus the proposed attack is applicable to all countermeasures using BSD representations. Finally, we give the simulation results against some countermeasures using BSD representation such as Ha-Moon method, Ebeid-Hasan method, and the method of Agagliate et al. The results show that the proposed attack is practical analysis method.
Hiro ITO Kazuo IWAMA Takeyuki TAMURA
In STS-based mapping, it is necessary to obtain the correct order of probes in a DNA sequence from a given set of fragments or an equivalently a hybridization matrix A. It is well-known that the problem is formulated as the combinatorial problem of obtaining a permutation of A's columns so that the resulting matrix has a consecutive-one property. If the data (the hybridization matrix) is error free and includes enough information, then the above column order uniquely determines the correct order of the probes. Unfortunately this does not hold if the data include errors, and this has been a popular research target in computational biology. Even if there is no error, ambiguities in the probe order may still remain. This in fact happens because of the lack of some information regarding the data, but almost no further investigation has previously been made. In this paper, we define a measure of such imperfectness of the data as the minimum amount of the additional fragments that are needed to uniquely fix the probe order. Polynomial-time algorithms to compute such additional fragments of the minimum cost are presented. A computer simulation using genes of human chromosome 20 is also noted.
Akihito OKURA Takeshi IHARA Akira MIURA
In this paper, we propose a multicast protocol, called BAM (Branch Aggregation Multicast), for wireless sensor networks. The main contribution of BAM is a reduction in the radio communication load, which is a key determinant of sensor energy consumption. BAM does not use any control packets such as join/leave messages and does not manage multicast groups. BAM is highly compatible with existing wireless sensor protocols, such as routing protocols, MAC protocols, and other kinds of energy efficient protocols. BAM implementation is quite simple and BAM works on various networks even if some sensors are not BAM-capable. BAM is composed of two aggregation techniques. One is single hop aggregation (S-BAM) and the other is multiple paths aggregation (M-BAM). S-BAM aggregates radio transmission within a single hop and enables single transmission to multiple intended receivers. M-BAM aggregates multiple paths into fewer ones and limits the range of radio transmission. S-BAM is designed to reduce redundant communication at every branch while M-BAM is designed to reduce the number of branches. SM-BAM, the combination of S-BAM and M-BAM, can reduce the radio communication load thus enabling energy efficient multicast communication. We evaluate BAM in three ways, qualitative evaluation by theoretical analysis, quantitative evaluation through computer simulations, and experiments using CrossBow's MICA2. Our results show that BAM is a very energy efficient multicast protocol that well supports wireless sensor networks.
Pino CABALLERO-GIL Amparo FUSTER-SABATER
The aim of this research is the efficient cryptanalysis of the Shrinking Generator through its characterization by means of Linear Hybrid Cellular Automata. This paper describes a new known-plaintext attack based on the computation of the characteristic polynomials of sub-automata and on the generation of the Galois field associated to one of the Linear Feedback Shift Registers components of the generator. The proposed algorithm allows predicting with absolute certainty, many unseen bits of the keystream sequence, thanks to the knowledge of both registers lengths, the characteristic polynomial of one of the registers, and the interception of a variable number of keystream bits.
Group signature schemes with membership revocation have been intensively researched. However, signing and/or verification of some existing schemes have computational costs of O(R), where R is the number of revoked members. Existing schemes using a dynamic accumulator or a similar technique have efficient signing and verifications with O(1) complexity. However, before signing, the signer has to modify his secret key with O(N) or O(R) complexity, where N is the group size. Therefore, for larger groups, signers suffer from enormous costs. On the other hand, an efficient scheme for middle-scale groups with about 1,000 members is previously proposed, where the signer need not modify his secret key. However this scheme also suffers from heavy signing/verification costs for larger groups with more than 10,000 members. In this paper, we adapt the middle-scale scheme to larger groups ranging from 1,000 to 1,000,000 members. At the sacrifice of the group manager's slight cost, our signing/verification is sufficiently efficient.
Toshihide KIKKAWA Kazukiyo JOSHIN
Highly reliable GaN high electron mobility transistors (HEMTs) are demonstrated for 3G-wireless base station applications. A state-of-the-art 250-W AlGaN/GaN-HEMTs push-pull transmitter amplifier operated at a drain bias voltage of 50 V is addressed with high efficiency under W-CDMA signals. The amplifier, combined with a digital pre-distortion (DPD) system, also achieved an adjacent channel leakage power ratio (ACLR) of less than -50 dBc for 4-carrier W-CDMA signals. Memory effect and temperature characteristics are also discussed. A stable operation including gate leakage current under RF stress testing for 1000 h is demonstrated at a drain bias voltage of 60 V. AlGaN/GaN HEMTs on an n-type doped 3-inch SiC substrate is introduced towards low cost manufacturing for the first time.
Hidemasa KUBOTA Yuichi TANJI Takayuki WATANABE Hideki ASAI
In this paper, we show the generalized method of the time-domain circuit simulation based on LIM. Our method is applicable to any structure of circuits by combination with the SPICE-like method. In order to show the validity and efficiency of our method, an example circuit is simulated and the proposed method is compared with the conventional ones.
Kiyotaka KOHNO Mitsuru KAWAMOTO Asoke K. NANDI Yujiro INOUYE
The present letter deals with the blind equalization problem of a single-input single-output infinite impulse response (SISO-IIR) channel with additive Gaussian noise. To solve the problem, we propose a new criterion for maximizing constrainedly a fourth-order cumulant. The algorithms derived from the criterion have such a novel property that even if Gaussian noise is added to the output of the channel, an effective zero-forcing (ZF) equalizer can be obtained with as little influence of Gaussian noise as possible. To show the validity of the proposed criterion, some simulation results are presented.
For a property π on graphs, the edge-contraction problem with respect to π is defined as a problem of finding a set of edges of minimum cardinality whose contraction results in a graph satisfying the property π. This paper gives a lower bound for the approximation ratio for the problem for any property π that is hereditary on contractions and determined by biconnected components.
Let H be a graph with a designated vertex s, where edges are weighted by nonnegative reals. Splitting edges e={u,s} and e'={s,v} at s is an operation that reduces the weight of each of e and e' by a real δ>0 while increasing the weight of edge {u,v} by δ. It is known that all edges incident to s can be split off while preserving the edge-connectivity of H and that such a complete splitting is used to solve many connectivity problems. In this paper, we give an O(mn+n2log n) time algorithm for finding a complete splitting in a graph with n vertices and m edges.
Given a graph G=(V,E), a set of vertices S ⊆ V covers v ∈ V if the edge connectivity between S and v is at least a given number k. Vertices in S are called sources. The source location problem is a problem of finding a minimum-size source set covering all vertices of a given graph. This paper presents a new variation of the problem, called maximum-cover source-location problem, which finds a source set S with a given size p, maximizing the sum of the weight of vertices covered by S. It presents an O(np + m + nlog n)-time algorithm for k=2, where n=|V| and m=|E|. Especially it runs linear time if G is connected. This algorithm uses a subroutine for finding a subtree with the maximum weight among p-leaf trees of a given vertex-weighted tree. For the problem we give a greedy-based linear-time algorithm, which is an extension of the linear-time algorithm for finding a longest path of a given tree presented by E. W. Dijkstra around 1960. Moreover, we show some polynomial solvable cases, e.g., a given graph is a tree or (k-1)-edge-connected, and NP-hard cases, e.g., a vertex-cost function is given or G is a digraph.
In this paper, we describe a bootstrapped nMOS switch that is modified to reduce leakage current for nMOS reversible energy recovery logic (nRERL) [1]. Conventional bootstrapped switches are not suitable for nRERL because they have nonadiabatic loss due to leakage current that flows while boosted. Therefore, we lowered the gate voltage of the isolation transistor in each bootstrapped switch to reduce this leakage current. With detailed analysis and simulation, we determined the range of the bias voltage, in which the switches can transfer full-swing input signals. We implemented a simple 8-bit nRERL microprocessor into silicon and measured its energy consumption to confirm our analysis. For the supply voltage of 1.8 V and the operating frequency of 880 kHz, we found that the microprocessor consumed about 8.5 pJ/cycle for 1.3 V < Vbias <1.6 V, which was just about a half of its energy consumption when Vbias = 1.7 V.
Yuthapong SOMCHIT Aki KOBAYASHI Katsunori YAMAOKA Yoshinori SAKAI
Live streaming is delay sensitive and can tolerate some amount of loss. The QoS Multicast for Live Streaming (QMLS) Protocol, focuses on the characteristics of live streaming. It has been shown to improve the performance of live streaming multicast by reducing the end-to-end packet loss probability. However, the placement of active routers performing the QMLS function has not been discussed. This paper proposes a dynamic method to activate and deactivate routers in order to minimize the number of active routers for each QMLS-packet flow and discusses its parameters. The results of an evaluation show that the proposed method can reduce the number of active routers for each flow and adjust the active routers according to changes in the multicast tree.
Yong-Hwa KIM Jong-Ho LEE Seong-Cheol KIM
In orthogonal frequency-division multiplexing (OFDM)-based wireless local area networks (WLANs), phase noise (PHN) and residual frequency offset (RFO) can cause the common phase error (CPE) and the inter-carrier interferences (ICI), which seriously degrade the performance of systems. In this letter, we propose a combined pilot symbol assisted and decision-directed channel estimation scheme based on the least-squares (LS) and the maximum-likelihood (ML) algorithms. Simulation results present that the proposed scheme significantly improves the performance of OFDM-based WLANs.
Toshiya ITOH Noriyuki TAKAHASHI
The recent burst growth of the Internet use overloads networking systems and degrades the quality of communications, e.g., bandwidth loss, packet drops, delay of responses, etc. To overcome such degradation of communication quality, the notion of Quality of Service (QoS) has received attention in practice. In general, QoS switches have several queues and each queue has several slots to store arriving packets. Since network traffic changes frequently, QoS switches need to control arriving packets to maximize the total priorities of transmitted packets, where the priorities are given by nonnegative values and correspond to the quality of service required to each packet. In this paper, we first derive the upper bounds for the competitive ratio of multi-queue preemptive QoS problem with priority between 1/α and 1, i.e., for any α ≥ 1, the algorithm TLH is (3-1/α)-competitive. This is a generalization of known results--for the case that packets have only priority 1 (α =1), the algorithm GREEDY (or TLH) is 2-competitive; for the case that packets have priorities between 0 and 1 (α = ∞), the algorithm TLH is 3-competitive. Then we consider the lower bounds for the competitive ratio of multi-queue preemptive QoS problem with priority between 0 and 1, and show that the competitive ratio of any multi-queue preemptive QoS algorithm is at least 1.514.
I Gusti Bagus Baskara NUGRAHA Sumiya MARUGAMI Mikihiko NISHIARA Hiroyoshi MORITA
In this paper, we propose a protocol for multicast communication called Multicast Datagram Transfer Protocol (MDTP) to provide multicast for video broadcasting service on the Internet. MDTP is a one-to-many multicast communication protocol, which is constructed based on IPv4 unicast protocol by utilizing IP Router Alert Option, and it uses unicast addressing and unicast routing protocol. A mechanism is presented to allow a router to remove identical video stream, to duplicate a video stream, and to forward each copy of the duplicated video stream to its destinations. Ordinary IP routers that do not support MDTP will treat the MDTP packets as normal unicast packets. Hence, gradual deployment is possible without tunneling technique. With a delegation mechanism, MDTP router is also able to handle request from clients, and serve the requested video stream. The simulation results show that the average bandwidth usage of MDTP is close to the average bandwidth usage of IP multicast. MDTP also has greater efficiency than XCAST, and its efficiency becomes significant for a large number of clients.