Based on the known quadriphase zero correlation zone (ZCZ) sequences ZCZ4(N,M,T), four families of 16-QAM sequences with ZCZ are presented, where the term "QAM sequences" means the sequences over the quadrature amplitude modulation (QAM) constellation. When the quadriphase ZCZ sequences employed by this letter arrive at the theoretical bound on the ZCZ sequences, and are of the even family size M or the odd width T of ZCZ, two of the resulting four 16-QAM sequence sets satisfy the bound referred to above. The proposed sequences can be potentially applied to communication systems using 16-QAM constellation as spreading sequences so that the multiple access interference (MAI) and multi-path interference (MPI) are removed synchronously.

Bounded model checking is a widely used formal technique in both hardware and software verification. However, it cannot be applied if the bounds (number of time frames to be analyzed) become large, and deep bugs which are observed only through very long counter-examples cannot be detected. This paper presents a method concatenating multiple bounded model checking results efficiently with symbolic simulation. A bounded model checking with a large bound is recursively decomposed into multiple ones with smaller bounds, and symbolic simulation on each counterexample supports smooth connections to the others. A strong heuristic for the proposed method that targets deep bugs is also presented, and can be applied together with other efficient bounded model checking methods since it does not touch the basic bounded model checking algorithm.

This paper presents a formulation of two-dimensional photonic crystal waveguide devices formed by circular cylinders. The device structures are considered as cascade connections of straight waveguides. Decomposing the structure into layers of the cylinder arrays, the input/output properties of the devices are obtained using an analysis method of multilayer structure. We introduce periodic boundary conditions in the direction perpendicular to the wave propagation, and the Floquet-modes of each layer are calculated by the Fourier series expansion method with the help of the recursive transition-matrix algorithm. Then, the input/output properties of the devices are obtained by recursive calculation of scattering matrix with each layer. The presented formulation is validated by numerical experiments by comparing with the previous works.

We revisit the double-pipe construction introduced by Lucks at Asiacrypt 2005. Lucks originally studied the construction for iterated hash functions and showed that the approach is effective in improving security against various types of collision and (second-)preimage attacks. Instead, in this paper we apply the construction to the secret-key setting, where the underlying FIL (fixed-input-length) compression function is equipped with a dedicated key input. We make some adjustments to Lucks' original design so that now the new mode works with a single key and operates as a domain extension of MACs (message authentication codes). Though more than twice as slow as the Merkle-Damgård construction, the double-piped mode enjoys security strengthened beyond the birthday bound. More specifically, when iterating an FIL-MAC whose output size is n-bit, the new double-piped mode yields an AIL-(arbitrary-input-length-)MAC with security up to O(2n) query complexity. This bound contrasts sharply with the birthday bound of O(2n/2), which was the best MAC security accomplished by earlier constructions.

In the localized Discrete Fourier Transform-Spread-Orthogonal Frequency Division Multiplexing (DFT-S-OFDM) uplink cooperative system, multiple carrier frequency offsets (MCFO), arising from the nodes' separate oscillators and Doppler spreads, drastically degrade the performance of the receiver. To solve the problem, this letter proposes an efficient MCFO compensation method which fully exploits the diversity gain of space frequency block coded (SFBC) and the characteristic of inter-carrier interference (ICI). Moreover, the bit error ratio (BER) lower bound of the proposed algorithm is theoretically derived. Simulation results validate the theoretical analysis and demonstrate that the proposed MCFO compensation method can achieve robust BER performance in a wide range of MCFO in the multipath Rayleigh fading channel.

Multiple-input multiple-output (MIMO) repeater systems have been discussed in several published papers. When a repeater has only one antenna element, the propagation environment is called keyhole. In this kind of scenario the achievable channel capacity and link quality are decreased. Another limit is when the number of the antenna elements of a repeater is larger than that of a MIMO transceiver, the channel capacity cannot be increased. In this paper, in order to obtain an upper bound of the channel capacity, we express a propagation process of the distributed MIMO repeater system with amplify-and-forward method by the numerical formular, and optimize the position of each repeater.

For cyclic codes some well-known lower bounds and some decoding methods up to the half of the bounds are suggested. Particularly, the shift bound is a good lower bound of the minimum distance for cyclic codes, Reed-Muller codes and geometric Goppa codes. In this paper we consider cyclic codes defined by their defining set, and new simple derivation of the shift bound using the discrete Fourier transform with unknown elements and the Blahut theorem is shown. Moreover two examples of binary cyclic codes are given.

The planar Hajos calculus (PHC) is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. The degree-d planar Hajos calculus (PHC(dd)) is PHC with the restriction that all the graphs that appear in the construction (including a final graph) must have maximum degree at most d. We prove the followings: (1) If PHC is polynomially bounded, then for any d ≥ 4, PHC(dd+2) can generate any non-3-colorable planar graphs of maximum degree at most d in polynomial steps. (2) If PHC can generate any non-3-colorable planar graphs of maximum degree 4 in polynomial steps, then PHC is polynomially bounded.

A dependency structure interprets modification relationships between words or phrases and is recognized as an important element in semantic information analysis. With the conventional approaches for extracting this dependency structure, it is assumed that the complete sentence is known before the analysis starts. For spontaneous speech data, however, this assumption is not necessarily correct since sentence boundaries are not marked in the data. Although sentence boundaries can be detected before dependency analysis, this cascaded implementation is not suitable for online processing since it delays the responses of the application. To solve these problems, we proposed a sequential dependency analysis (SDA) method for online spontaneous speech processing, which enabled us to analyze incomplete sentences sequentially and detect sentence boundaries simultaneously. In this paper, we propose an improved SDA integrating a labeling-based sentence boundary detection (SntBD) technique based on Conditional Random Fields (CRFs). In the new method, we use CRF for soft decision of sentence boundaries and combine it with SDA to retain its online framework. Since CRF-based SntBD yields better estimates of sentence boundaries, SDA can provide better results in which the dependency structure and sentence boundaries are consistent. Experimental results using spontaneous lecture speech from the Corpus of Spontaneous Japanese show that our improved SDA outperforms the original SDA with SntBD accuracy providing better dependency analysis results.

We try to use a computer algebra system Mathematica as a test case generation system. In test case generation, we generally need to solve equations and inequalities. The main reason why we take Mathematica is because it has a built-in function to solve equations and inequalities. In this paper, we deal with both black-box testing and white-box testing. First, we show two black-box test case generation procedures described in Mathematica. The first one is based on equivalence partitioning. Mathematica explicitly shows a case that test cases do no exist. This is an advantage in using Mathematica. The second procedure is a modification of the first one adopting boundary value analysis. For implementation of boundary value analysis, we give a formalization for it. Next, we show a white-box test case generation procedure. For this purpose, we also give a model for source programs. It is like a control flow graph model. The proposed procedure analyzes a model description of a program.

The access privileges in distributed systems can be effectively organized as a partial-order hierarchy that consists of distinct security classes, and the access rights are often designated with certain temporal restrictions. The time-bound hierarchical key assignment problem is to assign distinct cryptographic keys to distinct security classes according to their privileges so that users from a higher class can use their class key to derive the keys of lower classes, and these keys are time-variant with respect to sequentially allocated temporal units called time slots. In this paper, we present the involved principle, survey the state of the art, and particularly, look into two representative approaches to time-bound hierarchical key assignment for in-depth case studies.

Ray tracing is one of the most popular techniques for generating photo-realistic images. Extensive research and development work has made interactive static scene rendering realistic. This paper deals with interactive dynamic scene rendering in which not only the eye point but also the objects in the scene change their 3D locations every frame. In order to realize interactive dynamic scene rendering, RTRPS (Ray Tracing based on Ray Plane and Bounding Sphere), which utilizes the coherency in rays, objects, and grouped-rays, is introduced. RTRPS uses bounding spheres as the spatial data structure which utilizes the coherency in objects. By using bounding spheres, RTRPS can ignore the rotation of moving objects within a sphere, and shorten the update time between frames. RTRPS utilizes the coherency in rays by merging rays into a ray-plane, assuming that the secondary rays and shadow rays are shot through an aligned grid. Since a pair of ray-planes shares an original ray, the intersection for the ray can be completed using the coherency in the ray-planes. Because of the three kinds of coherency, RTRPS can significantly reduce the number of intersection tests for ray tracing. Further acceleration techniques for ray-plane-sphere and ray-triangle intersection are also presented. A parallel projection technique converts a 3D vector inner product operation into a 2D operation and reduces the number of floating point operations. Techniques based on frustum culling and binary-tree structured ray-planes optimize the order of intersection tests between ray-planes and a sphere, resulting in 50% to 90% reduction of intersection tests. Two ray-triangle intersection techniques are also introduced, which are effective when a large number of rays are packed into a ray-plane. Our performance evaluations indicate that RTRPS gives 13 to 392 times speed up in comparison with a ray tracing algorithm without organized rays and spheres. We found out that RTRPS also provides competitive performance even if only primary rays are used.

A method to construct Boolean functions with maximum algebraic immunity have been proposed in . Based on that method, we propose a different method to construct Boolean functions on even variables with maximum algebraic immunity in this letter. By counting on our construction, a lower bound of the number of such Boolean functions is derived, which is the best among all the existing lower bounds.

In this paper, we study lower bounds on the query complexity of testing algorithms for various problems. Given an oracle that returns information of an input object, a testing algorithm distinguishes the case that the object has a given property P from the case that it has a large distance to having P with probability at least . The query complexity of an algorithm is measured by the number of accesses to the oracle. We introduce two reductions that preserve the query complexity. One is derived from the gap-preserving local reduction and the other is from the L-reduction. By using the former reduction, we show linear lower bounds on the query complexity for testing basic NP-complete properties, i.e., 3-edge-colorability, directed Hamiltonian path/cycle, undirected Hamiltonian path/cycle, 3-dimensional matching and NP-complete generalized satisfiability problems. Also, using the second reduction, we show a linear lower bound on the query complexity of approximating the size of the maximum 3-dimensional matching.

In and we have presented a simulation-based algorithm for optimizing the average reward in a parameterized continuous-time, finite-state semi-Markov Decision Process (SMDP). We approximated the gradient of the average reward. Then, a simulation-based algorithm was proposed to estimate the approximate gradient of the average reward (called GSMDP), using only a single sample path of the underlying Markov chain. GSMDP was proved to converge with probability 1. In this paper, we give bounds on the approximation and estimation errors for GSMDP algorithm. The approximation error of that approximation is the size of the difference between the true gradient and the approximate gradient. The estimation error, the size of the difference between the output of the algorithm and its asymptotic output, arises because the algorithm sees only a finite data sequence.

This paper presents unconditionally stable and conformal FDTD schemes which are based on the alternating-direction implicit finite difference time domain (ADI-FDTD) method for accurate modeling of perfectly electric conducting (PEC) objects. The proposed schemes are formulated within the framework of the matrix-vector notation of the finite integration technique (FIT), which allows a systematic and consistent extension of finite difference solution of Maxwell's equations on dual grids. As possible choices of second-order convergent conformal method, we apply the partially filled cell (PFC) and the uniformly stable conformal (USC) schemes for the ADI-FDTD method. The unconditional stability and the rates of convergence of the proposed conformal ADI-FDTD (CADI-FDTD) schemes are verified by means of numerical examples of waveguide problems.

In this paper, we propose a method for extracting an object boundary from a low-quality image such as an infrared one. To take full advantage of a training set, the overall shape is modeled by incorporating statistical characteristics of moments into the point distribution model (PDM). Furthermore, a differential equation for the moment of overall shape is derived for shape refinement, which leads to accurate and rapid deformation of a boundary template toward real object boundary. The simulation results show that the proposed method has better performance than conventional boundary extraction methods.

While classification techniques can be applied for automatic unknown word recognition in a language without word boundary, it faces with the problem of unbalanced datasets where the number of positive unknown word candidates is dominantly smaller than that of negative candidates. To solve this problem, this paper presents a corpus-based approach that introduces a so-called group-based ranking evaluation technique into ensemble learning in order to generate a sequence of classification models that later collaborate to select the most probable unknown word from multiple candidates. Given a classification model, the group-based ranking evaluation (GRE) is applied to construct a training dataset for learning the succeeding model, by weighing each of its candidates according to their ranks and correctness when the candidates of an unknown word are considered as one group. A number of experiments have been conducted on a large Thai medical text to evaluate performance of the proposed group-based ranking evaluation approach, namely V-GRE, compared to the conventional naive Bayes classifier and our vanilla version without ensemble learning. As the result, the proposed method achieves an accuracy of 90.930.50% when the first rank is selected while it gains 97.260.26% when the top-ten candidates are considered, that is 8.45% and 6.79% improvement over the conventional record-based naive Bayes classifier and the vanilla version. Another result on applying only best features show 93.930.22% and up to 98.85 0.15% accuracy for top-1 and top-10, respectively. They are 3.97% and 9.78% improvement over naive Bayes and the vanilla version. Finally, an error analysis is given.

In recent VLSI systems, signal propagation delays are requested to achieve the specifications with very high accuracy. In order to meet the specifications, the routing of a net often needs to be detoured in order to increase the routing delay. A routing method should utilize a routing area with obstacles as much as possible in order to realize the specifications of nets simultaneously. In this paper, a fast longer path algorithm that generates a path of a net in routing grid so that the length is increased as much as possible is proposed. In the proposed algorithm, an upper bound for the length in which the structure of a routing area is taken into account is used. Experiments show that our algorithm utilizes a routing area with obstacles efficiently.

The purpose of the paper is to show that boundary implication results hold for complex-valued uncertain linear time-delay systems. The results are derived by the Lambert W function and yield tractable robust stability criteria for simultaneously triangularizable linear time-delay systems. The setting is similar to a recently reported extreme-point result, but the assumed uncertainty sets can be much more free in shape.