In this paper we give a simple algorithm to generate all partitions of a positive integer n. The problem is one of the basic problems in combinatorics, and has been extensively studied for a long time. Our algorithm generates each partition of a given integer in constant time for each without repetition, while best known algorithm generates each partition in constant time on "average." Also, we propose some algorithms to generate all partitions of an integer with some additional property in constant time.

For an integer d > 0, a d-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into d sets of non-nested edges with respect to the vertex ordering. Recently V. Dujmovi and D. R. Wood showed that for every integer d ≥ 2, every graph G has a d-queue layout of a subdivision of G with 2log_d qn(G)+1 division vertices per edge, where qn(G) is the queue number of G. This paper improves the result for the case of a bipartite graph, and shows that for every integer d ≥ 2, every bipartite graph G_m,n has a d-queue layout of a subdivision of G_m,n with log_d n-1 division vertices per edge, where m and n are numbers of vertices of the partite sets of G_m,n (m ≥ n).

We consider the capacitated multi-source multicast tree routing problem (CMMTR) in an undirected graph G=(V,E) with a vertex set V, an edge set E and an edge weight w(e) ≥ 0, e ∈ E. We are given a source set S ⊆ V with a weight g(e) ≥ 0, e ∈ S, a terminal set M ⊆ V-S with a demand function q : M → R⁺, and a real number κ > 0, where g(s) means the cost for opening a vertex s ∈ S as a source in a multicast tree. Then the CMMTR asks to find a subset S′⊆ S, a partition {Z₁,Z₂,...,Z_l} of M, and a set of subtrees T₁,T₂,...,T_l of G such that, for each i, ∑_t∈Z_iq(t) ≤ κ and T_i spans Z_i∪{s} for some s ∈ S′. The objective is to minimize the sum of the opening cost of S′and the constructing cost of {T_i}, i.e., ∑_s∈S′g(s)+w(T_i), where w(T_i) denotes the sum of weights of all edges in T_i. In this paper, we propose a (2ρ_UFL+ρ_ST)-approximation algorithm to the CMMTR, where ρ_UFL and ρ_ST are any approximation ratios achievable for the uncapacitated facility location and the Steiner tree problems, respectively. When all terminals have unit demands, we give a ((3/2)ρ_UFL+(4/3)ρ_ST)-approximation algorithm.

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring for given L. In this paper, we give a sufficient condition for a series-parallel graph to have a list total coloring, and we present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G and L satisfy the sufficient condition.

It is well known that a basic version (i.e., maximizing the number of base-pairs) of the RNA secondary structure prediction problem can be solved in O(n³) time by using simple dynamic programming procedures. For this problem, an O(n³(log log n)^1/2/(log n)^1/2) time exact algorithm and an O(n^2.776+(1/ε)^O(1)) time approximation algorithm which has guaranteed approximation ratio 1-ε for any positive constant ε are also known. Moreover, when two RNA sequences are given, there is an O(n⁶) time exact algorithm which can optimize structure and alignments. In this paper, we show an O(n⁵) time approximation algorithm for optimizing structure and alignments of two RNA sequences with assuming that the optimal number of base-pairs is more than O(n^0.75). We also show that the problem to optimize structure and alignments for given N sequences is NP-hard and introduce a constant-factor approximation algorithm.

Lately, time-multiplexed I/Os for multi-device implementations (e.g., multi-FPGA systems), have come into practical use. They realize multiple I/O signal transmissions between two devices in one system clock cycle using one I/O wire between the devices and multiple I/O clock cycles. Though they ease the limitation of the number of I/O-pins of each device, the system clock period becomes much longer approximately in proprotion to the maximum number of multiplexed I/Os on a signal path. There is no conventional partitioning algorithm considering the effect of time-multiplexed I/Os directly. We introduce a new cost function for evaluating the suitability of a bipartition for multi-device implementations with time-multiplexed I/Os. We propose a performance-driven bipartitioning method VIOP which minimizes the value of the cost function. Our method VIOP combines three algorithms, such that i) min-cut partitioning, ii) coarse performance-driven partitioning, iii) fine performance-driven partitioning. For min-cut partitioning and coarse performance-driven partitioning, we employ a well-known conventional bipartitioning algorithms CLIP-FM and DUBA, respectively. For fine performance-driven partitioning for the final improvement of a partition, we propose a partitioning algorithm CAVP. By our method VIOP, the average cost was improved by 10.4% compared with the well-known algorithms.

This paper presents a design method for AND-OR-EXOR three-level networks, where a single two-input exclusive-OR (EXOR) gate is used. The network realizes an EXOR of two sum-of-products expressions (EX-SOPs). The problem is to minimize the total number of products in the two sum-of-products expressions (SOPs). We introduce the notion of µ-equivalence of logic functions to develop exact minimization algorithms for EX-SOPs with up to five variables. We minimized all the NP-representative functions for up to five variables and showed that five-variable functions require 9 or fewer products in minimum EX-SOPs. For n-variable functions, minimum EX-SOPs require at most 9·2^n-5 (n ≤ 6) products. This upper bound is smaller than 2^n-1, which is the upper bound for SOPs. We also found that, for five-variable functions, on the average, minimum EX-SOPs require about 40% fewer literals than minimum SOPs.

In this paper, we introduce a new decision problem associated with lattices, named the Exact Length Vector Problem (ELVP), and prove the NP-completeness of ELVP in the _∞ norm. Moreover, we define two variants of ELVP. The one is a binary variant of ELVP, named the Binary Exact Length Vector Problem (BELVP), and is shown to be NP-complete in any _p norm (1 ≤ p ≤ ∞). The other is a nonnegative variant of ELVP, named the Nonnegative Exact Length Vector Problem (NELVP). NELVP is defined in the ₁ norm, and is also shown to be NP-complete.

The aim of our paper is to show how Partially Balanced Incomplete Block Designs (PBIBD) may be used to construct (2,n) visual cryptographic schemes for black and white images with small pixel expansion. In situations where uniformity of the participants with respect to the relative contrast is not important, our schemes work well since by allowing the relative contrast to vary depending on which two participants are recovering the image, they can keep the pixel expansion quite small. Thus our schemes have considerably smaller pixel expansion than many of the existing schemes. For some n and some pairs of participants recovering the image, our schemes have larger relative contrast than some existing schemes.

The most time consuming operation to verify a signature with the Elliptic Curve Digital Signature Algorithm is a multi-scalar multiplication with two scalars. Efficient methods for its computation are the Shamir method and the Interleave method, whereas the performance of those methods can be improved by using general base-2 representations of the scalars. In exchange for the speed-up, those representations require the precomputation of several points that must be stored. In the case of two precomputed points, the Interleave method and the Shamir method provide the same, optimal efficiency. In the case of more precomputed points, only the Interleave method can be sped-up in an optimal way and is currently more efficient than the Shamir method. This paper proposes a new general base-2 representation of the scalars that can be used to speed up the Shamir method. It requires the precomputation of ten points and is more efficient than any other representation that also requires ten precomputed points. Therefore, the proposed method is the first to improve the Shamir method such that it is faster than the Interleave method.

We propose constant-round protocols for interval tests, equality tests, and comparisons where shared secret inputs are not given bitwise. In [9]. Damgård et al. presented a novel protocol called the bit-decomposition, which can convert a polynomial sharing of an element in prime field Z_p into sharings of bits. Though, by using the bit-decomposition protocol, those protocols can be constructed with constant round complexities theoretically, it involves expensive computation, leading to relatively high round and communication complexities. In this paper, we construct more efficient protocols for those protocols without relying on the bit-decomposition protocol. In the interval test protocol, checking whether a shared secret exists in the known interval is reduced to checking whether a bitwise-shared random secret exists in the appropriate interval. In the comparison protocol, comparing two shared secrets is reduced to comparing the two secrets viaindirectly where p is an odd prime for an underlying linear secret sharing scheme. In the equality test protocol, checking whether two shared secrets are equal is reduced to checking whether the difference of the two secrets is zero and furthermore checking whether the difference is a zero is reduced to checking quadratice residuosity of a random secret in a probabilistic way.

Chen et al. introduced a new notion of a concurrent signature scheme for a fair exchange of signatures with two parties. Chen et al. also proposed a concrete scheme and proved its security under the assumption of discrete logarithm problem. Recently, Hiwatari and Tanaka extended the concept of concurrent signature to many-to-one setting. Hiwatari and Tanaka also proposed a concrete scheme; however, it requires some strong assumption to achieve the fair exchange and it is not efficient. This paper gives another construction of concurrent signature for many-to-one setting with multisignature scheme. Hereafter, we call it (n,1) concurrent signature scheme. The proposed scheme is more efficient than the scheme of Hiwatari and Tanaka in computation complexity and signature size, and achieves the fair exchange without the assumption required for the scheme of Hiwatari and Tanaka. This paper also gives a construction for the fair exchange of signatures in many-to-many setting, called (n,m) concurrent signature scheme, in appendix.

Although a great deal of research has been done on electronic cash schemes with blind multisignatures to prevent an insider attack, there is no discussion of a formal security model in the literature. Firstly we discussed the security model of e-cash schemes based on the blind multisignature scheme against a (restricted) attack model and proposed a concrete scheme proven to be secure in the model [1]; however, this attack model disallows an attacker from corrupting an issuing bank and shops in the forgery game. In this paper, first, we reconsider the security model to remove the restriction of the attack model. Second, we propose a new untraceable e-cash scheme with a blind multisignature scheme and prove that the proposed scheme is secure against the (non-restricted) attacks under the DDH assumption in the random oracle model.

It is widely believed to take exponential time to find a solution of a system of random multivariate polynomials because of the NP-completeness of such a task. On the other hand, in most of multivariate public key cryptosystems proposed so far, the computational complexity of cryptanalysis is polynomial time due to the trapdoor structure. In this paper, we introduce a new concept, piece in hand (soldiers in hand) matrix, which brings the computational complexity of cryptanalysis of multivariate public key cryptosystems close to exponential time by adding random polynomial terms to original cryptosystems. This is a general concept which can be applicable to any type of multivariate public key cryptosystems for the purpose of enhancing their security. As an implementation of the concept, we propose the linear PH matrix method with random variables. In 2003 Faugere and Joux broke the first HFE challenge (80 bits), where HFE is one of the major variants of multivariate public key cryptosystem, by computing a Grobner basis of the public key of the cryptosystem. We show, in an experimental manner, that the linear PH matrix method with random variables can enhance the security of HFE even against the Grobner basis attack. In what follows, we consider the strength of the linear PH matrix method against other possible attacks.

Copyright protection is a major issue in distributing content on Internet or broadcasting service. One well-known method of protecting copyright is a traitor tracing scheme. With this scheme, if a pirate decoder is made, the content provider can check the secret key contained in it and trace the authorized user/subscriber (traitor). Furthermore, users require that they could obtain services anywhere they want (Anywhere TV). For this purpose, they would need to take along their secret keys and therefore key exposure has to be kept in mind. As one of countermeasures against key exposure, a forward secure public key cryptosystem has been developed. In this system, the user secret key remains valid for a limited period of time. It means that even if it is exposed, the user would be affected only for the limited time period. In this paper, we propose a traitor tracing scheme secure against adaptive key exposure (TTaKE) which contains the properties of both a traitor tracing scheme and a forward secure public key cryptosystem. It is constructed by using two polynomials with two variables to generate user secret keys. Its security proof is constructed from scratch. Moreover we confirmed its efficiency through comparisons. Finally, we show the way how its building blocks can be applied to anywhere TV service. Its structure fits current broadcasting systems.

We study quantum entanglement by Schmidt decomposition for some typical quantum algorithms. In the Shor's exponentially fast algorithm the quantum entanglement holds almost maximal, which is a major factor that a classical computer is not adequate to simulate quantum efficient algorithms.

Acoustic field analysis results of surface acoustic wave dispersive delay lines using inclined chirp IDTs on a Y-Z LiNbO₃ substrate are described. The calculated results are compared with optical measurements. The angular spectrum of the plane wave method is applied to calculation of the acoustic fields considering the anisotropy of the SAW velocity by using the polynomial approximation. Acoustic field propagating along the Z-axis of the substrate, which is the main beam excited by the inclined chirp IDT, shows asymmetric distribution between the +Z and -Z directions. Furthermore the SAW beam propagating in a slanted direction with an angle of +18 from the Z axis to the X-axis is observed. It is described that the SAW beam propagating in a slanted direction is the first side lobe excited by the inclined chirp IDT. The acoustic field shows asymmetric distribution along the X-axis because of the asymmetric structure of the inclined chirp IDT. Finally, acoustic field of a two-IDT connected structure which consists of the same IDTs electrically connected in series is presented. The acoustic field of the two-IDT connected structure is calculated to be superposed onto the calculated result of the acoustic field exited by one IDT on the calculated result shifted along the X-axis. Two SAW beams excited by IDTs are observed. The distributions of the SAW beams are not in parallel. The calculated results show good agreement with the optical measurement results.

A nonlinear harmonic estimator (NHE) is proposed for extracting a harmonic signal and its fundamental frequency in the presence of white noise. This estimator is derived by applying an extended complex Kalman filter (ECKF) to a multiple sinusoidal model with state-representation and then efficiently specializing it for the case of harmonic estimation. The effectiveness of the NHE is verified using computer simulations.

Buffer insertion plays a great role in modern global interconnect optimization. But too many buffers exhaust routing resources, and result in the rise of the power dissipation. Unfortunately, simplified delay models used by most of the present buffer insertion algorithms may introduce redundant buffers due to the delay estimation errors, whereas accurate delay models expand the solution space significantly, resulting in unacceptable runtime. Moreover, the power dissipation problem becomes a dominant factor in the state-of-the-art IC design. Not only transistor but also interconnect should be taken into consideration in the power calculation, which makes us have to use an accurate power model to calculate the total power dissipation. In this paper, we present two stochastic optimization methods, simulated annealing and solution space smoothing, which use accurate delay and power models to construct buffered routing trees with considerations of buffer/wire sizing, routing obstacles and delay and power optimization. Experimental results show our methods can save much of the buffer area and the power dissipation with better solutions, and for the cases with pins ≤ 15, the runtime of solution space smoothing is tens of times faster.

Embedded memories have been used extensively in modern SoC designs. In order to estimate the power consumption of an entire design correctly, an accurate memory power models are needed. However, the memory power model that is commonly used in commercial EDA tools is too simple to estimate the power consumption accurately. In this work, we develop two methods to improve the accuracy of memory power estimation. Our enhanced memory power model can consider not only the operation mode of memory access, but also the address switching effects with scaling capability. The proposed approach is very useful to be combined with the memory compiler to generate accurate power model for any specified memory size without extra characterization costs. Then the proposed dummy modular approach can link our enhanced memory power model into the existing power estimation flow smoothly. The experimental results have shown that the average error of our memory power model is only less than 5%.

This paper describes a semi-fragile watermarking scheme for image authentication and tamper-proofing. Each watermark bit is duplicated and randomly embedded in the original image in the discrete wavelet domain by modifying the corresponding image coefficients through quantization. The modifications are made so that they have little effect on the image and that the watermarking is robust against tampering. The watermark image for authentication is reconstructed by taking a weighted vote on the extracted bits. The bits that lose the vote are treated as having been tampered with, and the locations of the lost bits as indicating tampered positions. Thus, authentication and tamper-proofing can be done by observing the images of watermarks that win and lose votes. Sieving, emphasis, and weighted vote were found to be effectively make the authentication and tamper detection more accurate. The proposed scheme is robust against JPEG compression or acceptable modifications, but sensitive to malicious attacks such as cutting and pasting.

In this paper we propose a method of constructing quasi-cyclic regular LDPC codes from a cyclic difference family, which is a kind of combinatorial design. The resulting codes have no 4-cycle, i.e. cycles of length four and are defined by a small set of generators of codes with high rate and large code length. In particular, for LDPC codes with column weight three, we clarify the conditions on which they have no 6-cycle and their minimum distances are improved. Finally, we show the performance of the proposed codes with high rates and moderate lengths.

Two-dimensional discrete wavelet transform (DWT) for processing image is conventionally designed by line-based architectures, which are simple and have low complexity. However, they suffer from two main shortcomings - the memory required for storing intermediate data and the long latency of computing wavelet coefficients. This work presents a new block-based architecture for computing lifting-based 2-D DWT coefficients. This architecture yields a significantly lower buffer size. Additionally, the latency is reduced from N² down to 3N as compared to the line-based architectures. The proposed architecture supports the JPEG2000 default filters and has been realized in ARM-based ALTERA EPXA10 Development Board at a frequency of 44.33 MHz.

To keep in step with the rapid progress of high quality imaging systems, the Digital Cinema Initiative (DCI) has been issuing digital cinema standards that cover all processes from production to distribution and display. Various evaluation measurements are used in the assessment of image quality, and, of these, the required number of quantization bits is one of the most important factors in realizing the very high quality images needed for cinema. While DCI defined 12 bits for the bit depth by applying Barten's model to just the luminance signal, actual cinema applications use color signals, so we can say that this value has an insufficient theoretical basis. This paper, first of all, investigates the required number of quantization bits by computer simulations in discrete 3-D space for the color images defined using CIE's XYZ signal. Next, the required number of quantization bits is formulated by applying Taylor's development in the continuous value region. As a result, we show that 13.04 bits, 11.38 bits, and 10.16 bits are necessary for intensity, density, and gamma-corrected signal quantization, respectively, for digital cinema applications. As these results coincide with those from calculations in the discrete value region, the proposed analysis method enables a drastic reduction in the computer simulation time needed for obtaining the required number of quantization bits for color signals.

In this paper, we propose a stochastic dynamic local search (SDLS) method for Multiple-Valued Logic (MVL) learning by introducing stochastic dynamics into the traditional local search method. The proposed learning network maintains some trends of quick descent to either global minimum or a local minimum, and at the same time has some chance of escaping from local minima by permitting temporary error increases during learning. Thus the network may eventually reach the global minimum state or its best approximation with very high probability. Simulation results show that the proposed algorithm has the superior abilities to find the global minimum for the MVL network learning within reasonable number of iterations.

This paper investigates a scheme to improve a location estimation method for higher estimation accuracy in sensor networks. For the location estimation method, we focus on the maximum likelihood method based on the measurements of received signal strength and its known probability distribution. Using some statistical properties of the estimate obtained by the maximum likelihood method in a simplified situation, we propose a modification of likelihood function in order to improve the estimation accuracy for arbitrary situation. However, since the proposed scheme is derived under a special assumption for the simplification, we should examine the impact of the proposed scheme in more general situations by numerical simulation. From the simulation results, we show the effectiveness of the proposed modification especially in the cases of small number of samples (namely, the measurements of received signal strength) and the channel model with exponential distribution.

The quantization error of phase delay in an ultrasonic annular arrays imaging system is analyzed which impairs image resolution, and proper sampling rate is considered to reduce system complexity.

The present paper introduces the construction of a class of sequence sets with zero-correlation zones called zero-correlation zone sequence sets. The proposed zero-correlation zone sequence set can be generated from an arbitrary perfect sequence, the length of which is longer than 4. The proposed sets of ternary sequences, which can be constructed from an arbitrary perfect sequence, can successfully provide CDMA communication without co-channel interference. In an ultrasonic synthetic aperture imaging system, the proposed sequence set can improve the signal-to-noise ratio of the acquired image.

In H.264/AVC, the quantized coefficients are scanned in a zigzag pattern. But the zigzag scanning is not always efficient for the directional spatial predictions in the intra coding of H.264/AVC. In this letter, we propose an adaptive scanning using the pixel similarity of the neighboring pixels to achieve enhanced intra coding performance. The proposed method reduces the bit rate approximately 2% compared with H.264/AVC without video quality degradation.

In this paper, we use a modified Gaussian filter to improve enlargement accuracy of the arbitrary scale LP enlargement method, which is based on the Laplacian pyramid representation (so called "LP method"). The parameters of the proposed algorithm are extracted through a theoretical analysis and an experimental estimation. Experimental results show that the proposed modified Gaussian filter is effective for the arbitrary scale LP enlargement method.