An algorithm for finding the optimal sectionalization for sectionalized trellises with respect to distinct optimality criterions was presented by Lafourcade and Vardy. In this paper, for linear block codes, we give a direct method for finding the optimal sectionalization when the optimality criterion is chosen as the total number |E| of the edges, the expansion index |E|-|V|+1, or the quantity 2|E|-|V|+1, only using the dimensions of the past and future sub-codes. A more concrete method for determining the optimal sectionalization is given for the Reed-Muller codes with the natural lexicographic coordinate ordering.

The transmission S-parameter between two dipole-elements is a measure to evaluate sites for measuring complex antenna factors (CAF). In this paper, the S-parameter between two dipole-elements on a ground plane is measured using a network analyzer with its TRL (Thru-Reflect-Line) calibration. The S-parameter is also calculated by the method of moment (MoM) and compared to the measurement results. The comparison shows that the calculated S-parameter is usable as a reference value in the evaluation of CAF measurement sites. As an example of the evaluation and selection of measurement sites, the transmission S-parameter on a finite ground plane is calculated using the hybrid method combined the geometrical theory of diffraction (GTD) and MoM. As a result, a preferable antenna setting on the finite ground plane is recommended.

In this paper we study general complex eigenvalue problems in engineering fields. The eigenvalue problems can be transformed into the associated problems for solving large systems of nonlinear ordinary differential equations (dynamic equations) by optimization techniques. The known waveform relaxation method in circuit simulation can then be successfully applied to compute the resulting dynamic equations. The approach reported here, which is implemented on a message passing multi-processor system, can determine all eigenvalues and their eigenvectors for general complex matrices without any restriction on the matrices. The numerical results are provided to confirm the theoretical analysis.

This paper presents an application of Complex-Valued Associative Memory Model(CAMM) for image processing. An image association system applying CAMM, combined with a 2-dimensional discrete Fourier transform (2-D DFT) process is proposed. Discussed are how a gray level image can be expressed using CAMM, and the image association that can be performed by CAMM. In the proposed system, input images are transformed to phase matrices and the image association can be performed by making use of the phase information. Practical examples are also presented.

Simulation of multi-band quantum transport based on a non-equilibrium Green's functions is presented in resonant tunneling diodes (RTD's), where realistic band structures and space charge effect are taken into account. To include realistic band structure, we have used a multi-band (MB) tight binding method with an sp3s* hybridization. As a result, we have found that the multiband nature significantly changes the results of conventional RTD simulations specifically for the case with indirect-gap barriers.

In this paper, we investigate multilevel coding and multistage decoding for satellite broadcasting with moderate decoding complexity. An unconventional signal set partitioning is used to achieve unequal error protection capabilities. Two possibilities are shown and analyzed for practical systems: (i) linear block component codes with near optimum decoding, (ii) punctured convolutional component codes with a common trellis structure.

This letter empirically evaluates the way how to calculate the complexity of methods, that is used in the definition of WMC(Weighted Method per Class), one of the Chidamber and Kemerer's metrics. With respect to the results of our experiment, Halstead's Software Science metric is the most appropriate one to evaluate the complexity of the methods.

In visual servoing, most studies are concerned with robotic application with known objects. In this paper, the problem of controlling a motion by visual servoing around an unknown object is addressed. In this case, the approach is interpreted as an initial step towards a perception goal of an unmodeled object. The main goal is to perform motion with regard to the object in order to discover several viewpoint of the object. An adaptive visual servoing scheme is proposed to perform such task. The originality of our work is based on the choice and extraction of visual features in accordance with motions to be performed. The notion of invariant feature is introduced to control the navigational task around the unknown object. During experimentation, a cartesian robot connected to a real time vision system is used. A CCD camera is mounted on the end effector of the robot. The experimental results present a linkage of desired motion around different kind of objects.

This paper introduces the construction of a family of complex-valued scaling functions and wavelets with symmetry/antisymmetry, compact support and orthogonality from the Daubechies polynomial, and applies them to solve electromagnetic scattering problems. For simplicity, only two extreme cases in the family, maximum-localized complex-valued wavelets and minimum-localized complex-valued wavelets are investigated. Regularity of root location of the Daubechies polynomial in spectral factorization are also presented to construct these two extreme genus of complex-valued wavelets. When wavelets are used as basis functions to solve electromagnetic scattering problems by the method of moment (MoM), they often lead to sparse matrix equations. We will compare the sparsity of MoM matrices by the real-valued Daubechies wavelets, minimum-localized complex-valued Daubechies and maximum-localized complex-valued Daubechies wavelets. Our research summarized in this paper shows that the wavelets with smaller signal width will result in a more sparse MoM matrix, especially when the scatterer is with many corners.

In this paper, a new frequency transformation for complex analog filter design which is suitable for integration is discussed. Arbitrary specified passband and stopband edges are easily transformed into those of the normalized LPF by solving simultaneous equations with four unknowns. Different from previous methods, the proposed transformation provides better performance in active realization of complex filters.

In this paper, a realization of an imaginary resistor using an ideal transformer is proposed. In the same fashion as the conventional method, a signal path is divided into a real signal path and an imaginary path. We name circuits which constitute a real signal path and an imaginary signal path, a real circuit and an imaginary circuit, respectively. An imaginary resistor is converted into an ideal transformer embedded between the imaginary circuit and the real circuit. The imaginary circuit becomes a dual circuit of the real circuit. This filter consists of terminating resistors, inductors, capacitors and ideal transformers. This prototype circuit is simulated by using operational amplifiers. A 3rd-order complex Chebyshev bandpass filter is designed and its frequency response is measured. Finally, the sensitivity property of the proposed filter is evaluated by a computer simulation.

Asynchronous, distributed, decision-making (ADDM) systems constitute a special class of distributed problems and are characterized as large, complex systems wherein the principal elements are the geographically-dispersed entities that communicate among themselves, asynchronously, through message passing and are permitted autonomy in local decision-making. A fundamental property of ADDM systems is stability that refers to their behavior under representative perturbations to their operating environments, given that such systems are intended to be real, complex, and to some extent, mission critical systems, and are subject to unexpected changes in their operating conditions. ADDM systems are closely related to autonomous decentralized systems (ADS) in the principal elements, the difference being that the characteristics and boundaries of ADDM systems are defined rigorously. This paper introduces the concept of stability in ADDM systems and proposes an intuitive yet practical and usable definition that is inspired by those used in Control Systems and Physics. A comprehensive stability analysis on an accurate simulation model will provide the necessary assurance, with a high level of confidence, that the system will perform adequately. An ADDM system is defined as a stable system if it returns to a steady-state in finite time, following perturbation, provided that it is initiated in a steady-state. Equilibrium or steady-state is defined through placing bounds on the measured error in the system. Where the final steady-state is equivalent to the initial one, a system is referred to as strongly stable. If the final steady-state is potentially worse then the initial one, a system is deemed marginally stable. When a system fails to return to steady-state following the perturbation, it is unstable. The perturbations are classified as either changes in the input pattern or changes in one or more environmental characteristics of the system such as hardware failures. Thus, the key elements in the study of stability include steady-state, perturbations, and stability. Since the development of rigorous analytical models for most ADDM systems is difficult, if not impossible, the definitions of the key elements, proposed in this paper, constitute a general framework to investigate stability. For a given ADDM system, the definitions are based on the performance indices that must be judiciously identified by the system architect and are likely to be unique. While a comprehensive study of all possible perturbations is too complex and time consuming, this paper focuses on a key subset of perturbations that are important and are likely to occur with greater frequency. To facilitate the understanding of stability in representative real-world systems, this paper reports the analysis of two basic manifestations of ADDM systems that have been reported in the literature --(i) a decentralized military command and control problem, MFAD, and (ii) a novel distributed algorithm with soft reservation for efficient scheduling and congestion mitigation in railway networks, RYNSORD. Stability analysis of MFAD and RYNSORD yields key stable and unstable conditions.

In this paper, we present a new approach for the design of partially adaptive broadband beamformers with the generalized sidelobe canceller (GSC) as an underlying structure. The approach designs the blocking matrix involved by utilizing a set of P-regular, M-band wavelet filters, whose vanishing moment property is shown to meet the requirement of a blocking matrix in the GSC structure. Furthermore, basing on the subband decomposition property of these wavelet filters, we introduce a new dynamic subband selection scheme succeeding the blocking matrix. The scheme only retains the principal subband components of the blocking matrix outputs based on a prescribed statistical hypothesis test and thus further reduces the dimension of weights in adaptive processing. As such, the overall computational complexity, which is mainly dictated by the dimension of adaptive weights, is substantially reduced. The furnished simulations show that this new approach offers comparable performance as the existing fully adaptive beamformers but with reduced computations.

A reallocation problem is defined as determining whether blocks can be moved from their current boxes to their destination boxes in the number of moves less than or equal to a given positive integer. This problem is defined simply and has many practical applications. We previously proved the following results: The reallocation problem such that the block volume is restricted to one volume unit for all blocks can be solved in linear time. But the reallocation problem such that the block volume is not restricted is NP-complete, even if no blocks have bypass boxes. But the computational complexity of the reallocation problems such that the range of the block volume is restricted has not yet been known. We prove that the reallocation problem is NP-complete even if the block volume is restricted to one or two volume units for all blocks and no blocks have bypass boxes. Furthermore, we prove that the reallocation problem is NP-complete, even if there are only two blocks such that each block has the volume units of fixed positive integer greater or equal than two, the volume of the other blocks is restricted to one volume unit, and no blocks have bypass boxes. Next, we consider such a block that must stays in a same box both in the initial state and in the final state but can be moved to another box for making room for other blocks. We prove that the reallocation problem such that an instance has such blocks is also NP-complete even if the block volume is restricted to one volume unit for all blocks.

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.

This paper analyzes what structural features of graph problems allow efficient parallel algorithms. We survey some parallel algorithms for typical problems on three kinds of graphs, outerplanar graphs, trapezoid graphs and in-tournament graphs. Our results on the shortest path problem, the longest path problem and the maximum flow problem on outerplanar graphs, the minimum-weight connected dominating set problem and the coloring problem on trapezoid graphs and Hamiltonian path and Hamiltonian cycle problem on in-tournament graphs are adopted as working examples.

The subject of the paper is to give an overview and latest results on the Legal Firing Sequence Problem of Petri nets (LFS for short). LFS is very fundamental in the sense that it appears as a subproblem or a simpler form of various basic problems in Petri net theory, such as the well-known marking reachability problem, the minimum initial resource allocation problem, the liveness (of level 4) problem, the scheduling problem and so on. However, solving LFS generally is not easy: it is NP -hard even for Petri nets having very simple structures. This intractability of LFS may have been preventing us from producing efficient algorithms for those problems. So research on LFS from computational complexity point of view seems to be rewarding.

The invariant polynomials of discrete systems such as graphs, matroids, hyperplane arrangements, and simplicial complexes, have been theoretically investigated actively in recent years. These invariants include the Tutte polynomial of a graph and a matroid, the chromatic polynomial of a graph, the network reliability of a network, the Jones polynomial of a link, the percolation function of a grid, etc. The computational complexity issues of computing these invariants have been studied and most of them are shown to be #P-complete. But, these complexity results do not imply that we cannot compute the invariants of a given instance of moderate size in practice. To meet large demand of computing these invariants in practice, there have been proposed a framework of computing the invariants by using the binary decision diagrams (BDD for short). This provides mildly exponential algorithms which are useful to solve moderate-size practical problems. This paper surveys the BDD-based approach to computing the invariants, together with some computational results showing the usefulness of the framework.

We sketch two algorithms that solve the undirected st-connectivity problem in a small amount of space. One is due to Nisan, Szemeredy and Wigderson, and takes space O(log3/2n), where n denotes the number of nodes in a give undirected graph. This is the first algorithm that overcame the Savitch barrier on the space complexity of the problem. The other is due to Tarui and this author, and takes space O(sw(G)2 log2 n), where sw(G) denotes the separation-width of a given graph G. Their result implies that the st-connectivity problem can be solved in logarithmic space for any class of graphs with separation-width bounded above by a predetermined constant. This class is one of few nontrivial classes for which the st-connectivity problem can be solved in logarithmic space.

In this paper, a puzzle called Cell-Maze is analyzed. In this puzzle, cells are arranged in checker board squares. Each cell is rotated when a player arrives at the cell. Cell-Maze asks whether or not a player started from a start cell can reach a goal cell. The reachability problem for ordinary graphs can be easily solved in linear time, however a reachability problem for the network such as Cell-Maze may be extremely difficult. In this paper, NP-hardness of this puzzle is proved. It is proved by reducing Hamiltonian Circuit Problem of directed planar graph G such that each vertex involved in just three arcs. Furthermore, we consider subproblems, which can be solved in polynomial time.