Masahiko TAKENAKA Takeshi SHIMOYAMA Takeshi KOSHIBA
In this paper, we give a theoretical analysis of χ2 attack proposed by Knudsen and Meier on the RC6 block cipher. To this end, we propose a method of security evaluation against χ2 attack precisely including key dependency by introducing a method "Transition Matrix Computing." Previously, no theoretical security evaluation against χ2 attack was known, it has been done by computer experiments. We should note that it is the first result concerning the way of security evaluation against χ2 attack is shown theoretically.
Masakazu SOSHI Mamoru MAEKAWA Eiji OKAMOTO
The safety problem in access matrix models determines whether a given subject can eventually obtain access privilege to a given object. Generally speaking, the safety problem is, unfortunately undecidable. Not much is known about protection systems for which the safety problem is decidable, except for strongly constrained systems (e.g., monotonic systems). Therefore, we propose the Dynamic-Typed Access Matrix (DTAM) Model, which extends the Typed Access Matrix model of Sandhu by allowing the type of an object to change dynamically. The DTAM model has an advantage that it can describe non-monotonic protection systems for which the safety problem is decidable. In particular, with further restrictions, we can show that the problem becomes NP-hard. In this paper, we formally define the DTAM model and then discuss various aspects of it thoroughly.
Chih-Peng HUANG Shi-Ting WANG Yau-Tarng JUANG
This paper presents a distinct approach to the robustness stability analysis and design of linear uncertain systems. Based on the extension version of the projection method, the specific stability issue, which ensures the poles within a specific region, can be efficiently analyzed. Furthermore, we derive a simple design scheme for a class of uncertain systems. By the proposed numerical algorithm, some examples are given to demonstrate the validity and effectiveness.
Takeshi TATEYAMA Seiichi KAWATA Hideaki OHTA
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.
Mostafa SOLIMAN Stanislav SEDUKHIN
Within a few years it will be possible to integrate a billion transistors on a single chip operating at frequency more than 10 GHz. At this integration level, we propose using a multi-level ISA to express fine-grain data parallelism to hardware instead of using a huge transistor budget to dynamically extract it. Since the fundamental data structures for a wide variety of data parallel applications are scalar, vector, and matrix, our proposed Trident processor extends a scalar ISA with vector and matrix instruction sets to effectively process matrix formulated applications. Like vector architectures, the Trident processor consists of a set of parallel lanes (each lane contains a set of vector pipelines and a slice of register file) combined with a fast scalar core. However, Trident processor can effectively process on the parallel lanes not only vector but also matrix data. One key point of our architecture is the local communication within and across lanes to overcome the limitations of the future VLSI technology. Another key point is the effective execution of a mixture of scalar, vector, and matrix operations. This paper describes the architecture of the Trident processor and evaluates its performance on BLAS and on the standard matrix bidiagonalization algorithm. The last one is evaluated as an example of an entire application based on a mixture of scalar, vector, and matrix operations. Our results show that many data parallel applications, such as scientific, engineering, multimedia, etc., can be speeded up on the Trident processor. Besides, the scalability of the Trident processor does not require more fetch, decode, or issue bandwidth, but requires only replication of parallel lanes.
The concept of an Ω-matrix was introduced by Nishi in order to estimate the number of solutions of a resistive circuit containing active elements. He gave a finite characterization by means of four conditions which are all satisfied if and only if the matrix under investigation is an Ω-matrix. In this note we show that none of the four conditions can be omitted.
Shin-ichi YAMAMOTO Jiro HIROKAWA Makoto ANDO
The authors proposed a switching beam slot array antenna with a 4-way Butler matrix. All are integrated in one substrate with post-wall waveguide techniques. The planar Butler matrix is realized by using short slot directional couplers (cross coupler). Experiments in 26GHz band confirmed the key operation of this antenna; almost identical four beams are switched to cover the total of horizontal 90-degree sector with equal angular spacing.
N. M. Alam CHOWDHURY Jun-ichi TAKADA Masanobu HIROSE
In this letter, we propose a new technique that reduces the computation time to derive the MEI coefficients in solving scattering problems by the Measured Equation of Invariance (MEI) methods. Methods that use the MEI technique spend most of the computation time in the integration process to derive the MEI coefficients. Moreover, in the conventional solution process, some repeated computation of metron fields to derive the MEI coefficients is included. To avoid the repeated operations and thus save computation time, we propose a matrix localization technique in computing the MEI coefficients. The time comparison for the computation of MEI coefficients of a cylinder and a sphere is given to verify the CPU time reduction of our new technique.
Andrzej CICHOCKI Pando GEORGIEV
In many applications of Independent Component Analysis (ICA) and Blind Source Separation (BSS) estimated sources signals and the mixing or separating matrices have some special structure or some constraints are imposed for the matrices such as symmetries, orthogonality, non-negativity, sparseness and specified invariant norm of the separating matrix. In this paper we present several algorithms and overview some known transformations which allows us to preserve several important constraints.
Yoji ISOTA Osami ISHIDA Fumio TAKEDA
Adaptive antenna is a promising to increase the spectral efficiency of mobile radio systems. We developed a compact, cost effective planar Butler Matrix as a beam forming network of a multi beam antenna. This circuit consists of a thin substrate that the conductor attaches to both sides, and two thick substrates that the ground conductor attaches to one side. In this circuit, coupling by crossover causes amplitude and phase error of the Butler Matrix. By narrowing the strip width of the crossover, crossover coupling can be suppressed 10 dB. The measurement results of the experimental 88 Butler Matrix were 0.75 dB amplitude deviation, 9.5 degree phase deviation and VSWR of less than 1.15 within the relative bandwidth of 10% at 900 MHz band.
Digital halftoning is a technique to convert a continuous-tone image into a binary image consisting of black and white dots. It is an important technique for printing machines and printers to output an image with few intensity levels or colors which looks similar to an input image. This paper surveys how algorithm engineering can contribute to digital halftoning or what combinatorial problems are related to digital halftoning. A common criterion on optimal digital halftoning leads to a negative result that obtaining an optimal halftoned image is NP-complete. So, there are two choices: approximation algorithm and polynomial-time algorithm with relaxed condition. Main algorithmic notions related are geometric discrepancy, matrix (or array) rounding problems, and network-flow algorithms.
Takashi MAEBA Mitsuyoshi SUGAYA Shoji TATSUMI Ken'ichi ABE
This letter presents parallel algorithms for matrix multiplication and the fast Fourier transform (FFT) that are significant problems arising in engineering and scientific applications. The proposed algorithms are designed on a 3-dimensional processor array with separable buses (PASb). We show that a PASb consisting of N N h processors can compute matrix multiplication of size N N and the FFT of size N in O(N/h+log N) time, respectively. In order to examine ease of hardware implementation, we also evaluate the VLSI complexity of the algorithms. A result obtained achieves an optimal bound on area-time complexity when h=O(N/log N).
Satoshi KUROSAKI Yusuke ASAI Takatoshi SUGIYAMA Masahiro UMEHIRA
This paper proposes a space division multiplexed - coded orthogonal frequency division multiplexing (SDM-COFDM) scheme for multi-input multi-output (MIMO) based broadband wireless LANs. The proposed scheme reduces inter-channel interference in SDM transmission with a simple feed-forward canceller which multiplies the received symbols by the estimated propagation inverse matrix for each OFDM subcarrier. This paper proposes a new preamble pattern in order to improve power efficiency in the estimation of the propagation matrix. Moreover, the proposed likelihood-weighting scheme, which is based on signal-to-noise power ratio (SNR) of each OFDM subcarrier, improves the error correction performance of soft decision Viterbi decoding. Computer simulation shows that the proposed SDM-COFDM scheme with two transmitting/receiving antennas doubles the transmission rate without increasing the channel bandwidth and achieves almost the same PER performance as the conventional single-channel transmission in frequency selective fading environments. In particular, it achieves more than 100 Mbit/s per 20 MHz by using 64QAM with the coding rate of 3/4.
Qiang CHEN Qiaowei YUAN Kunio SAWAYA
A new iterative algorithm based on the Gauss-Seidel iteration method is proposed to solve the matrix equation in the MoM analysis of the array antennas. In the new algorithm, the impedance matrix is decomposed into a number of sub matrices, which describe the self and mutual impedance between the groups of the array, and each sub matrix is regarded as a basic iteration unit rather than the matrix element in the ordinary Gauss-Seidel iteration method. It is found that the convergence condition of the ordinary Gauss-Seidel iteration scheme is very strict for the practical use, while the convergence characteristics of the present algorithm are greatly improved. The new algorithm can be applied to the sub domain MoM with a fast convergence if the grouping technique is properly used. The computation time for solving the matrix equation is reduced to be almost proportional to the square of the number of the array elements. The present method is effective in MoM analysis of solving large-scale array antennas.
Bong Dae CHOI Dong Bi ZHU Chang Sun CHOI
We propose and analyze a new efficient handoff scheme called Splitted-Rating Channel Scheme in UMTS networks, and we analyze the call level performance of splitted-rating channel scheme and then packet level performance of downlink traffic at UMTS circuit-switched networks. In order to reduce the blocking probability of originating calls and the forced termination probability of handoff calls, a splitted-rating channel scheme is applied to the multimedia UMTS networks. This multimedia network supports two classes of calls; narrowband call requiring one channel and wideband call requiring multiple channels. The channels in service for wideband call are splitted its channels for lending to originating call and handoff call according to threshold control policy. By assuming that arrivals of narrowband calls and arrivals of wideband calls are Poisson, we model the number of narrowband calls and the number of wideband calls in the one cell by Level Dependent Quasi-Birth-Death (QBD) process and obtain their joint stationary distribution. For packet level analysis, we first describe the downlink traffic from the base station to a mobile terminal in UMTS networks, and calculate the mean packet delay of a connected wideband call by using QBD analysis. Numerical examples show that our splitted-rating channel scheme reduces the blocking probability of originating call and the forced termination probability of handoff call with a little degradation of packet delay.
Shigeru YAMAMOTO Toshimitsu USHIO
In this paper, we present new stability conditions for a class of large-scale hybrid dynamical systems composed of a number of interconnected hybrid subsystems. The stability conditions are given in terms of discontinuous Lyapunov functions of the stable hybrid subsystems. Furthermore, the stability conditions are represented by LMIs (Linear Matrix Inequalities) which are computationally tractable.
This paper presents a new method of designing a dither matrix based on simulated annealing. An obtained dither matrix (halftone screen/mask) is appropriate for press printing. Because of several physical reasons, halftoning for press printing is more difficult than halftoning for electronic displays, or ink-jet printers. Even if stochastic dispersed-dot screening (so-called FM-screening) is one of the best solutions for halftoning, that is not appropriate for press printing. On the other hand, classical periodic clustered-dot screening (so-called AM-screening) is more important and is widely used even now. We recognize unfavorable quality of AM-screening, but we can not ignore its productive stability in printing section. The proposed halftone dither matrix has aperiodic clustered-dot pattern, and size of cluster can be controlled by a weighting parameter of a cost function. We will obtain a dither matrix which consists of clustered-dots. Some characteristics of the design algorithm and halftoned images are investigated in detail. As a result, the fact that an obtained dither matrix is superior to AM-screen and comparable to FM-screen in visual quality, and the matrix is comparable to AM-screen and superior to FM-screen in press printability is confirmed.
In this paper, we propose the code orthogonalizing filter (COF) based adaptive array antenna using sample matrix inversion with common correlation matrix (CCM-SMI) of time domain signals for multicarrier DS/CDMA systems. The conventional array antenna system calculates the weight using the correlation matrix of individual subcarrier's signals. On the other hand, our proposed system calculates the weight using the correlation matrix of time domain signals before FFT operation, so it can reduce the calculation time and the complexity of weight calculation than the conventional scheme, to maintain the system performance. Moreover, we consider the code orthogonalizing filter to reduce the demerit of adaptive array antenna system using sample matrix inversion algorithm with common correlation matrix that requires heavy computational complexity while the signal environment frequently changes. Our proposed system obtains more accurate channel response vector using COF than that of the conventional CCM-SMI based on the matched filter, without increasing the matrix size. The performance is evaluated in term of bit error probability. From the analysis and simulation results, it is shown that our proposed scheme achieves better BER performance than that of the conventional system.
Jian YANG Yingning PENG Yoshio YAMAGUCHI Wolfgang-Martin BOERNER
The concept of the equi-phase curve is introduced for the cross-polarized channel case. It is proved that the equi-phase curves are a series of half circles on the Poincare sphere, and that all these curves have two common ends. Based on the introduced concept, this letter demonstrates the distribution of the received voltage's phases on the Poincare sphere. In addition, it is shown theoretically that the cross-polarized phase of the off-diagonal elements of a scattering matrix is unstable for most natural targets. Therefore, the cross-polarized phase information cannot be used for extracting target characteristics in polarimetric radar remote sensing.
Chien-Hsing WU Chien-Ming WU Ming-Der SHIEH Yin-Tsung HWANG
In this paper, we present the division algorithm (DA) for the computation of b=c/a over GF(2m) in two aspects. First, we derive a new formulation for the discrete-time Wiener-Hopf equation (DTWHE) Ab = c in GF(2) over any basis. Symmetry of the matrix A is observed on some special bases and a three-step procedure is developed to solve the symmetric DTWHE. Secondly, we extend a variant of Stein's binary algorithm and propose a novel iterative division algorithm EB*. Owing to its structural simplicity, this algorithm can be mapped onto a systolic array with high speed and low area complexity.