For multimedia communications, the computational scalability of a multimedia codec is required to match with different working platforms and integrated services of media sources. In this paper, two condensed stochastic codebook search approaches are proposed to progressively reduce the computation required for the algebraic code excited linear predictive (ACELP) and multi-pulse maximum likelihood quantization (MP-MLQ) coders. By reducing the candidates of the codebook before search procedure, the proposed methods can effectively diminish the computation required for the ITU-T G.723.1 dual rate speech coder. Simulation results show that the proposed methods can save over 50 percent for the stochastic codebook search with perceptually intangible degradation in speech quality.

Complex-valued region-based-coupling image clustering (continuous soft segmentation) neural networks are proposed for interferometric radar image processing. They deal with the amplitude and phase information of radar data as a combined complex-amplitude image. Thereby, not only the reflectance but also the distance (optical length) are consistently taken into account for the clustering process. A continuous complex-valued label is employed whose structure is the same as that of input raw data and estimation image. Experiments demonstrate successfully the clustering operations for interferometric synthetic aperture radar (InSAR) images. The method is applicable also to future radar systems for image acquisition in, e.g., invisible fire smoke places and intelligent transportation systems by generating a processed image more recognizable by human and automatic recognition machine.

There exist some results showing that quantum communications are more powerful than classical communications. Moreover, although quantum entangled states do not give extra information, by using prior entanglement the quantum communication complexity of some functions is less than the classical communication complexity. The communications with prior entanglement can be regarded as a type of public coin models. In this paper, we investigate quantum communications for multi-party with prior entanglement, and show that there exists a generalized inner product function for k-party such that the quantum communication complexity is at most k bits, but the classical communication complexity needs at least 3k/2 bits. Moreover, we also provide a generalized form of prior entanglements that is effective in order to compute some type of Boolean functions.

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.

In the theory of average-case NP-completeness, Levin introduced the polynomial domination and Gurevich did the average polynomial domination. Ben-David et al. proved that if P-samp (the class of polynomial-time samplable distributions) is polynomially dominated by P-comp (the class of polynomial-time computable distributions) then there exists no strong one-way function. This result will be strengthened by relaxing the assumption from the polynomial domination to the average polynomial domination. Our results also include incompleteness for average polynomial-time one-one reducibility from (NP,P-samp) to (NP,P-comp). To derive these and other related results, a prefix-search algorithm presented by Ben-David et al. will be modified to survive the average polynomial domination.

Analysis of electromagnetic wave propagation and scattering in a random medium is a field of great interest. This research field becomes more important if we consider the study of phsyical effects on wave propagation and scattering from targets in random media. Curvature of the targets' cross-sections plays an important parameter in the radar detection problem. In previous study, analysis of scattering data from nonconvex conducting targets has pointed out to the effect of target configuration together with both effects of the spatial coherence length of incident waves around the target and the double passage on the backscattering enhancement. Here, we make sure this fact by considering targets with relatively large sizes in continuous random media for H-wave incidence. We assume the cross-section of targets to be smoothly deformed contour comprising concave and convex portions.

This paper considers a high-rate turbo code which employs high-rate convolutional codes as component codes, and presents a novel method of reducing the decoding complexity of the codes. By eliminating some of branches that have the lowest reliabilities among all the branches entering each node, the proposed algorithm reduces the complexity in the process of the add-compare-select (ACS) between the consecutive stages of iterative decoding. That is, the complexity gradually decreases as the number of iterations increases. We compare the unpunctured high-rate turbo code with a classical punctured high-rate turbo code in terms of performance/complexity trade-off under the same code rate. Simulation results show that the proposed approach with a good trade-off provides an alternative coding scheme to the classical punctured high-rate turbo coding for the application to high-data-rate wireless communication systems.

This paper presents a new class of complex-valued compact-supported orthonormal symmlets. Firstly, some properties of complex-valued compact-supported orthonormal symmlets are investigated, and then it is shown that complex-valued symmlets can be generated by real-valued half-band filters. Therefore, the construction of complex-valued symmlets can be reduced to the design of real-valued half-band filters. Next, a design method of real-valued half-band FIR filters with some flatness requirements is proposed. For the maximally flat half-band filters, a closed-form solution is given. For the filter design with a given degree of flatness, the design problem is formulated in the form of linear system by using the Remez exchange algorithm and considering the given flatness condition. Therefore, a set of filter coefficients can be easily computed by solving a set of linear equations, and the optimal solution is obtained through a few iterations. Finally, some design examples are presented to demonstrate the effectiveness of the proposed method.

Conventional adaptive array antenna processing must access signals on all of the array antenna elements. However, because the low-cost electronically steerable passive array radiator (ESPAR) antenna only has a single-port output, all of the signals on the antenna elements cannot be observed. In this paper, a technique for adaptively controlling the loaded reactances on the passive radiators, thus forming both beam and nulls, is presented for the ESPAR antenna. The adaptive algorithm is based on the steepest gradient theory, where the reactances are sequentially perturbed to determine the gradient vector. Simulations show that the ESPAR antenna can be adaptive. The statistical performance of the output SIR of the ESPAR antenna is also given.

Currently, the most popular model in data compression theory is that of stationary ergodic sources. But there do exist sequences each of which is not emitted from any stationary ergodic source but can be compressed sufficiently by a certain algorithm. We estimate the size of the set of such sequences in terms of Hausdorff dimension.

A method for estimating complex permittivity of a material using a rectangular waveguide with a flange is presented by the finite difference time domain (FDTD) method. An advantage of the present method is that it is not necessary to vary the material structure in order to insert it into the waveguide. Therefore estimation errors related to the dimensions of the material are almost negligible. In this case, fluoridated rubber is chosen as the low-loss material. The comparison of the complex permittivity of the material determined by the present method with FDTD and the conventional waveguide method at 10 GHz is performed. It was confirmed that the present method is effective for estimating the complex permittivity under the condition that the length of the flange is about 50 mm (1.7λ) square.

An important goal in communication theory is to construct good minimum squared Euclidean distance (MSED) codes for transmission over additive white Gaussian noise (AWGN) channels. In this paper, a new construction method for the M-ary phase-shift-keyed (M-PSK) codes over the ring structure ZM, the ring of integers modulo M, with a good minimum Euclidean distance, is proposed. The proposed codes are linear when multiple coset leaders are considered. The characteristics and performance levels of the newly constructed codes are analyzed for code length up to n 8. It is found that the proposed codes compare favorably with Piret's codes and Graeffe's method codes on Gaussian channels in terms of decoding complexity, coding gain, and error performance.

A complex coefficient filter obtained by directly exchanging several reactance elements included in a real coefficient BPF for imaginary valued resistors is described. By using the proposed method, we obtain four varieties of complex coefficient filters. The stability problem is examined.

Method invocation mechanism is one of the essential features in object-oriented programming languages. This mechanism contributes to data encapsulation and code reuse, but there is a risk of runtime type errors. In the case of object-oriented databases (OODBs), a runtime error causes rollback. Therefore, it is desirable to ensure that a given OODB schema is consistent, i.e., no runtime error occurs during the execution of queries under any database instance of the OODB schema. This paper discusses the computational complexity of the type-consistency problem. As a model of OODB schemas, we adopt update schemas introduced by Hull et al., which have all of the basic features of OODBs such as class hierarchy, inheritance, complex objects, and so on. The type-consistency problem for update schemas is known to be undecidable. We introduce a subclass of update schemas, called acyclic schemas, and show that the type-consistency problem for acyclic schemas is in coNEXPTIME. Furthermore, we show that the problem for recursion-free acyclic schemas is coNEXPTIME-hard and the problem for retrieval acyclic schemas is PSPACE-complete.

The transmission S-parameter, S21, between dipole elements on a rectangular finite ground plane is calculated by the MoM with planar-segments in the horizontally and vertically polarized configurations. Supposed a 1/10 scaling, the frequency range is selected 0.15-0.8 GHz. The size of the finite ground plane is 40 cm 100 cm. The dipole-element length is 18.8 cm (half-wavelength at 0.8 GHz). The distance between dipole elements is 30 cm. The results are compared to the calculated results with the conventional MoM-GTD hybrid method and also the measured results with a TRL-calibrated network analyzer. It makes clear that the MoM-GTD hybrid method is not applicable to a small ground plane in the vertically polarized configuration. The results calculated by the MoM with planar-segments agree well to the measured results both in the horizontal and vertical polarizations. The results show that the size of the finite ground plane for the vertical polarization should be much larger than for the horizontal polarization.

Private information retrieval for k 1 databases (denoted by (k,l)-PIR for short) is a protocol that (1) a user sends an l tuple query to each of k noncommunicating replicated databases; (2) each database responds the user with an answer corresponding to the l tuple query; (3) the user privately retrieve any single bit out of the n bits of data stored in k databases. In this model, "privacy" implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he wishes to get. In general, the efficiency of (k,l)-PIR is measured by the total amount of bits exchanged between the user and the k databases, but few about its lower bounds are known except for restricted cases. In this paper, we classify (k,l)-PIR into a linear type, a multilinear type, and an affine type with respect to the relationship between queries to each database (made by the user) and answers to the user (made by each database), and show that (1) the lower bound for the communication complexity of any multilinear type (k,l)-PIR is Ω(n1/(l+1)) (Theorem 3.1); (2) the lower bound for the communication complexity of any linear type (k,l)-PIR is Ω(n) (Corollary 3.2); (3) the lower bound for the communication complexity of any affine type (k,l)-PIR is Ω(n1/(l+1)) (Theorem 4.2).

This paper investigates a hierarchical property based on the number of inkdots in the accepting powers of sublogarithmic space-bounded multi-inkdot two-way alternating Turing machines with only universal states. For each k1 and any function L(n), let strong-2UTMk(L(n)) (weak-2UTMk(L(n))) be the class of sets accepted by strongly (weakly) L(n) space-bounded k-inkdot two-way alternating Turing machines with only universal states. We show that for each k1, strong-2UTMk+1(log log n) - weak-2UTMk(o(log n)) Ø.

Can we find in polynomial time an elliptic curve of a given order over a finite field? This paper is concerned with this question which is open since 1986. Consider the partial multivalued function that outputs such an elliptic curve. We characterize the difficulty of computing this function, and show that the polynomial time hierarchy collapses if sat reduces to this function with respect to the polynomial time Turing reducibility, where sat is the partial multivalued function that on input a Boolean formula, outputs a satisfying assignment. We also give a problem that is equivalent to the open question under the Extended Riemann Hypothesis.

Data mining is to analyze all the data in a huge database and to obtain useful information for database users. One of the well-studied problems in data mining is the search for meaningful association rules in a market basket database which contains massive amounts of sales transactions. The problem of mining meaningful association rules is to find all the large itemsets first, and then to construct meaningful association rules from the large itemsets. In our previous work, we have shown that it is NP-complete to decide whether there exists a large itemset with a given size. Also, we have proposed a subclass of databases, called k-sparse databases, for which we can efficiently find all the large itemsets. Intuitively, k-sparsity of a database means that the supports of itemsets of size k or more are sufficiently low in the database. In this paper, we introduce the notion of (k,c)-sparsity, which is strictly weaker than the k-sparsity in our previous work. The value of c represents a degree of sparsity. Using (k,c)-sparsity, we propose a larger subclass of databases for which we can still efficiently find all the large itemsets. Next, we propose alternative measures to the support. For each measure, an itemset is called highly co-occurrent if the value indicating the correlation among the items exceeds a given threshold. In this paper, we define the highly co-occurrent itemset problem formally as deciding whether there exists a highly co-occurrent itemset with a given size, and show that the problem is NP-complete under whichever measure. Furthermore, based on the notion of (k,c)-sparsity, we propose subclasses of databases for which we can efficiently find all the highly co-occurrent itemsets.

We propose an adaptive complex-amplitude texture classifier that takes into consideration height as well as reflection statistics of interferometric synthetic aperture radar (SAR) images. The classifier utilizes the phase information to segment the images. The system consists of a two-stage preprocessor and a complex-valued SOFM. The preprocessor extracts a complex-valued feature vectors corresponding to height and reflectance statistics of blocks in the image. The following SOFM generates a set of templates (references) adaptively and classifies a block into one of the classes represented by the templates. Experiment demonstrates that the system segments an interferometric SAR image successfully into a lake, a mountain, and so on. The performance is better than that of a conventional system dealing only with the amplitude information.