This paper proposes the binary second-order recurrent neural networks (BSRNN) equivalent to the modified finite automata (MFA) and presents the learning algorithm to construct the stable BSRNN for inferring regular grammar. This network combines two trends; one is to transform strings of a regular grammar into a recurrent neural network through training with no restriction of the number of neurons, the number of strings, and the length of string and the other is to directly transform itself into a finite automaton. Since neurons in the BSRNN employ a hard-limiter activation functions, the proposed BSRNN can become a good alternative of hardware implementation for regular grammars and finite automata as well as grammatical inference.

Numerous scientific and engineering fields extensively utilize optimization techniques for finding appropriate parameter values of models. Various optimization methods are available for practical use. The optimization algorithms are classified primarily due to the rates of convergence. Unfortunately, it is often the case in practice that the particular optimization method with specified convergence rates performs substantially differently on diverse optimization tasks. Theoretical classification of convergence rates then lacks its relevance in the context of the practical optimization. It is therefore desirable to formulate a novel classification framework relevant to the theoretical concept of convergence rates as well as to the practical optimization. This article introduces such classification framework. The proposed classification framework enables specification of optimization techniques and optimization tasks. It also underlies its inherent relationship to the convergence rates. Novel classification framework is applied to categorizing the tasks of optimizing polynomials and the problem of training multilayer perceptron neural networks.

In Optimistic Two-Phase Locking (O2PL), when a transaction requests a commit, the transaction can not be committed until all requested locks are obtained. By this reason, O2PL leads to unnecessary waits and operations even though it adopts an optimistic approach. This paper suggests an efficient optimistic cache consistency protocol that provides serializability of committed transactions. Our cache consistency scheme, called PCP (Preemptive Cache Protocol), decides whether to commit or abort without waiting when transactions request commits. In PCP, some transactions that read stale data items can not be aborted, because it adopts a re-ordering scheme to enhance the performance. In addition, for re-ordering, PCP stores only one version of each data item. This paper presents a simulation-based analysis on the performance of PCP with other protocols such as O2PL, Optimistic Concurrency Control and Caching Two-Phase Locking. The simulation experiments show that PCP performs as well as or better than other schemes with low overhead.

The interconnect analysis of on- and off-chips is very important in the design of high-speed signal processing, digital communication, and microwave electronic systems. When the interconnects are characterized by sampled data via electromagnetic analysis, the circuit-level simulation of the network requires rational approximation of the sampled data. Since the frequency band of the sampled data is more than 10 GHz, the rational function must fit into it at many frequency points. The rational function is approximated using the orthogonal least-squares method. With an increase in the number of the fitting data, the least-squares method suffers from a singularity problem. To avoid this, the sampled data are hierarchically approximated in this paper. Moreover, to reduce the computational cost of the circuit-level simulation, the parameter matrix of the interconnects is approximated by a rational matrix with one common denominator polynomial, and the selective orthogonalization procedure is presented.

The optimization of channel assignment in cellular mobile networks is an NP-complete combinatorial optimization problem. For any reasonable size network, only sub-optimal solutions can be obtained by heuristic algorithms. In this paper, six channel assignment heuristic algorithms are proposed and evaluated. They are the combinations of three channel assignment strategies and two cell ordering methods. What we found are (i) the node-color ordering of cells is a more efficient ordering method than the node-degree ordering; (ii) the frequency exhaustive strategy is more suitable for systems with highly non-uniformly distributed traffic, and the requirement exhaustive strategy is more suitable for systems with less non-uniformly distributed traffic; and (iii) the combined frequency and requirement exhaustive strategy with node-color re-ordering is the most efficient algorithm. The frequency spans obtained using the proposed algorithms are much lower than that reported in the literature, and in many cases are equal to the theoretical lower bounds.

The blind separation of sources is a recent and important problem in signal processing. Since 1984, it has been studied by many authors whilst many algorithms have been proposed. In this paper, the description of the problem, its assumptions, its currently applications and some algorithms and ideas are discussed.

To improve the resolution capability of the directions-of-arrival (DOA) estimation, some subspace-based methods have recently been developed by exploiting the specific signal properties (e.g. non-Gaussian property and cyclostationarity) of communication signals. However, these methods perform poorly as the ordinary subspace-based methods in multipath propagation situations, which are often encountered in mobile communication systems because of various reflections. In this paper, we investigate the direction estimation of coherent signals by jointly utilizing the merits of higher-order statistics and cyclostationarity to enhance the performance of DOA estimation and to effectively reject interference and noise. For estimating the DOA of narrow-band coherent signals impinging on a uniform linear array, a new higher-order cyclostationarity based approach is proposed by incorporating a subarray scheme into a linear prediction technique. This method can improve the resolution capability and alleviate the difficulty of choosing the optimal lag parameter. It is shown numerically that the proposed method is superior to the conventional ones.

This paper proposes higher-order spread spectrum direct optical switching CDMA system and an aliasing canceler to remove the aliasing distortion caused by higher-order bandpass sampling. Theoretical analysis of the signal quality shows that the 3rd order bandpass sampling scheme can improve the carrier-to-interference-power ratio compared with the conventional 1st order bandpass sampling scheme, by 5 dB.

The reorder buffer is usually employed to maintain the instruction execution in the correct order for a superscalar pipeline with out-of-order issue. In this paper, we propose a reorder buffer structure with shelter buffer for out-of-order issue superscalar processors not only to control stagnation efficiently, but also to reduce the buffer size. We can get remarkable performance improvement with only one or two buffers. Simulation results show that if the size of reorder buffer is between 8 and 32, performance gain obtained from the shelter is noticeable. For the shelter buffer of size 4, there is no performance improvement compared to that of size 2, which means that the shelter buffer of size 2 is large enough to handle most of the stagnation. If the shelter buffer of size 2 is employed, we can reduce the reorder buffer by 44% in Whetstone, 50% in FFT, 60% in FM, and 75% in Linpack benchmark program without loss of any throughput. Execution time is also improved by 19.78% in Whetstone, 19.67% in FFT, 23.93% in FM, and 8.65% in Linpack benchmark when the shelter buffer is used.

This paper proposes a fast method of calculating high-order backward Linear Prediction (LP) coefficients for wideband Code Excited LP (CELP) coders operating at around 16 kbit/s. The fast calculation is achieved by a recursive calculation for the high-order autocorrelation of the decoded signal. The recursive calculation can be employed thanks to a novel method of converting the autocorrelation of the decoded signal to that of the residual signal. High-order backward LP coefficients are computed from the autocorrelation of the residual signal using the Levinson-Durbin (LD) procedure. The conversion approximately performs inverse-filtering using LP coefficients representing a corresponding envelope spectrum. Due to the recursive calculation, the proposed fast calculation method achieves 30% to 45% reduction in computations to calculate the high-order backward LP coefficients compared to the conventional method. Subjective tests show that a wideband Multi-Pulse based CELP (MP-CELP) coder at 16 kbit/s with the proposed method achieves comparable coding quality to that with the conventional one with 35% reduction in computations needed for calculation of the backward LP coefficients.

The VSOP terminal is a new data-acquisition system for the Very-Long-Baseline Interferometry (VLBI). This terminal was primarily designed for ground telescopes in the VLBI Space Observatory Programme (VSOP). New technologies; higher-order sampling and digital filtering techniques, were introduced in the development. A cassette cart was also introduced, which supports 24-hour unattended operations at the maximum data rate of 256 Mbps. The higher-order sampling and digital filtering techniques achieve flat and constant phase response over bandwidth of 32 MHz without using expensive wide base-band converters. The digital filtering technique also enables a variety of observing modes defined on the VSOP terminal, even with a fixed sampling frequency in an A/D converter. The new terminals are installed at Nobeyama, Kashima, Usuda, Mizusawa, and Kagoshima radio observatories in Japan, and are being used in VSOP and other domestic VLBI observations. In this paper the key features of the VSOP terminal focusing on these advanced technologies are presented, and the results of performance tests are shown.

Interpolation attack was presented by Jakobsen and Knudsen at FSE'97. Interpolation attack is effective against ciphers that have a certain algebraic structure like the PURE cipher which is a prototype cipher, but it is difficult to apply the attack to real-world ciphers. This difficulty is due to the difficulty of deriving a low degree polynomial relation between ciphertexts and plaintexts. In other words, it is difficult to evaluate the security against interpolation attack. This paper generalizes the interpolation attack. The generalization makes easier to evaluate the security against interpolation attack. We call the generalized interpolation attack linear sum attack. We present an algorithm that evaluates the security of byte-oriented ciphers against linear sum attack. Moreover, we show the relationship between linear sum attack and higher order differential attack. In addition, we show the security of CRYPTON, E2, and RIJNDAEL against linear sum attack using the algorithm.

An efficient procedure is presented to determine the implicit exact solution of an arbitrary nonuniform transmission line (NTL), and its first order approximation (F. O. A. ) as an explicit expression. The method of the solution is based on the steplines approximation of the nonuniform transmission lines and quasi-TEM assumptions. Using steplines approximation the NTL is subdivided into a large number of uniform line segments (steps). Using time-domain approach and invoking the boundary conditions at the discontinuities of the adjacent steps, each step is modeled as continuous time domain linear filter characterized by a transfer function. The frequency domain transfer function of this filter is then obtained for linear termination networks. For very large number of steplines this transfer function approaches transfer function of the NTL. In the next step a F. O. A. , as an explicit expression of the exact response will be obtained. This F. O. A. is more suitable for very short transmission lines which is often the case in integrated circuits and some of printed circuit boards. Then, the F. O. A. of the ABCD matrix will be obtained.

This paper proposes a method to construct smaller binary decision diagrams for characteristic functions (BDDs for CFs). A BDD for CF represents an n-input m-output function, and evaluates all the outputs in O(n+m) time. We derive an upper bound on the number of nodes of the BDD for CF of n-bit adders (adrn). We also compare complexities of BDDs for CFs with those of shared binary decision diagrams (SBDDs) and multi-terminal binary decision diagrams (MTBDDs). Our experimental results show: 1) BDDs for CFs are usually much smaller than MTBDDs; 2) for adrn and for some benchmark circuits, BDDs for CFs are the smallest among the three types of BDDs; and 3) the proposed method often produces smaller BDDs for CFs than an existing method.

The Matrix-Pencil (MP) method is applied to the estimation of the undesired radiation from the microstrip line discontinuities. The Q factors are obtained from the complex resonant frequencies estimated from FDTD transient field by using MP. The number of the damped oscillations is estimated by using MDL which is widely used as an information theoretic criterion for the model order estimation.

In this paper, soft decision decoding of linear block codes based on the reprocessing of several information sets is considered. These information sets are chosen according to the reliability measures of the received symbols and constructed from the most reliable information set, referred to as the most reliable basis. Each information set is then reprocessed by a multi-stage decoding algorithm until either the optimum error performance, or a desired level of error performance is achieved. General guidelines for the trade-offs between the number of information sets to be processed, the number of computations for reprocessing each information set, and the error performance to be achieved are provided. It is shown that with a proper selection of few information sets, low-complexity near-optimum soft decision decoding of relatively long block codes (64 N 128) can be achieved with significant reduction in computation complexity with respect to other known algorithms. This scheme, which generalizes the reprocessing of the most reliable basis with the ordered statistic algorithm proposed by Fossorier and Lin, is particularly efficient for codes with rate R 1/2.

For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66], several simple proofs have been presented so far. This paper gives yet another simple proof. As a byproduct, it can provide an O(m log n) time algorithm that outputs a maximum flow between the pair of vertices s and t selected by the algorithm, where n and m are the numbers of vertices and edges, respectively. This algorithm can be used to speed up the algorithm to compute DAGs,t that represents all minimum cuts separating vertices s and t in a graph G, and the algorithm to compute the cactus Γ(G) that represents all minimum cuts in G.

This paper deals with a method of estimating the parameters and the order of a linear system using differential digital filters and the resultant. From the observed signals of the input and output of an objective system, we extract the differential signals from the zero order to an appropriate high order with the same phase characteristics, using several digital filters. On the assumption that the system order is known, we estimate the parameters of the transfer function and evaluate the estimation error bounds. We propose a criterion function generated by the product of the highest order coefficients and the resultant of the numerator and denominator of the estimated transfer function. Applying this criterion function, we can estimate the order of the objective system. The threshold corresponding to this criterion function is evaluated from the deviation in the frequency characteristics of the used differential filters and the error bound of the estimated parameters. In order to demonstrate the propriety of the proposed method, some numerical simulations are presented.

Since the proposal of differential cryptanalysis and linear cryptanalysis in 1991 and 1993, respectively, the resistance to these cryptanalysis has been studied. In FSE2, Knudsen proposed a method of attacking block ciphers that used the higher order differential, and in FSE4, Jakobsen and Knudsen applied it to a cipher proposed by Nyberg and Knudsen. Their approach, however, requires large complexity of running time. In this paper, we improve this attack and show that our improved algorithm requires much fewer chosen texts and much less complexity than those of previous works.

We analyze the dispersion-managed optical transmission system for the non-return-to-zero (NRZ) pulse format. First, we investigate the physical image of dispersion management by computing small-signal-based transfer functions, and summarize the dependence of transmission performance on system parameters. Next, the Q-map is computed numerically to design long-distance large-capacity dispersion-managed transmission systems for a single channel in a more detailed manner. It is shown that the third-order dispersion of fibers negatively influences transmission performance, and third-order dispersion compensation is proved to be an effective method for extending the transmission distance of high bit-rate systems. Utilizing these results, guidelines can be derived for the optimal design of long-distance large-capacity NRZ transmission systems.