In this paper, we present a novel energy compaction method, called the selective block-wise reordering, which is used with SPIHT (SBR-SPIHT) coding for low rate video coding to enhance the coding efficiency for motion-compensated residuals. In the proposed coding system, the motion estimation and motion compensation schemes of H.263 are used to reduce the temporal redundancy. The residuals are then wavelet transformed. The block-mapping reorganization utilizes the wavelet zerotree relationship that jointly presents the wavelet coefficients from the lowest subband to high frequency subbands at the same spatial location, and allocates each wavelet tree with all descendents to form a wavelet block. The selective multi-layer block-wise reordering technique is then applied to those wavelet blocks that have energy higher than a threshold to enhance the energy compaction by rearranging the significant pixels in a block to the upper left corner based on the magnitude of energy. An improved SPIHT coding is then applied to each wavelet block, either re-ordered or not. The high energy compaction resulting from the block reordering can reduce the number of redundant bits in the sorting pass and improve the quantization efficiency in the refinement pass of SPIHT coding. Simulation results demonstrate that SBR-SPIHT outperforms H.263 by 1.28-0.69 dB on average for various video sequences at very low bit-rates, ranging from 48 to 10 kbps.

Circuit partition, retiming and state reordering techniques are effective in reducing power consumption of circuits. In this paper, we propose a partition architecture and a methodology to reduce power consumption when designing low power IP, named PRC (Partition and Reordering Circuit). The circuit reordering synthesis flow consists of three phases: first, evenly partition the circuit based on the Shannon expansion; secondly encode the output vectors of each partition to build an equivalent functional logic. Finally, apply reordering algorithm to reorganize the logic function to reduce power consumption and decrease area cost. The validity of our architecture is proven by applying it to MCNC benchmark with simulation environment.

It is known that all minimum cuts in an edge-weighted undirected graph with n vertices and m edges can be represented by a cactus with O(n) vertices and edges, a connected graph in which each edge is contained in an exactly one cycle. In this paper, we show that such a cactus representation can be computed in O(mn+n2log n) time and O(m) space. This improves the previously best complexity of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing a single minimum cut.

OPKFDDs (Ordered Pseudo-Kronecker Functional Decision Diagrams) are a data structure that provides compact representation of Boolean functions. The size of OPKFDDs depends on a variable ordering and on decomposition type choices. Finding an optimal representation is very hard and the size of the search space is n! 32n-1, where n is the number of input variables. To overcome the huge search space of the problem, a genetic algorithm is proposed for the generation of OPKFDDs with minimal number of nodes.

A tunable external-cavity InGaAs/AlGaAs quantum-well laser using a grating coupler monolithically integrated in a selectively disordered waveguide is demonstrated. The laser consists of an amplifier with a narrow channel for lateral single-mode guiding and a tapered section, a grating coupler for output beam collimation and wavelength dispersion, and an external half mirror. Selective quantum-well disordering technique using SiO2 caps of different thicknesses and rapid thermal annealing was employed to reduce the passive waveguide loss in the grating coupler region. Loss reduction from 40 cm-1 to 3 cm-1 was accomplished. Resultant increase of the grating coupler efficiency and expansion of the effective aperture length led to significant improvement of the laser performances. The maximum output power of 105 mW and wide tuning range of 21.1 nm centered at 997 nm were obtained. The well collimated output beam of full diffraction angles at half maximum of 0.16 0.18 was obtained.

In this paper, we propose an efficient linear ordering algorithm for netlist partitioning. The proposed algorithm incrementally merges two segments which are selected based on the proposed cost function until only one segment remains. The final resultant segment then corresponds to the linear order. Compared to the earlier work, the proposed algorithm yields an average of 11.4% improvement for the ten-way scaled cost partitioning.

Causal message ordering in the context of group communication ensures that all the message receivers observe consistent ordering of events affecting a group as a whole. This paper presents a scalable causal multicast protocol for mobile distributed computing systems. In our protocol, only a part of the mobility agents in the system is involved in group computations and the resulting size of control information in messages can be kept small. Our protocol can outperform qualitatively the counterparts in terms of communication overhead and handoff complexity. An analytical model is also developed to evaluate our proposal. The performance results show that the proposed protocol is promising.

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 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.

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.

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.

We present a method for power and delay optimization by input reordering. We observe that the reordering has a significant effect on the power dissipation of the gate which drives the reordered gate. This is because the input capacitance depends on the signal values of other inputs. This property, however, has not been utilized for power reduction. Previous approaches focus on the reduction of the power dissipated by internal capacitances of the reordered gate. We propose a heuristic algorithm considering the total power consumed in the driving gate and the reordered gate. Experimental results using 30 benchmark circuits show that our method reduces the power dissipation in all the circuits by 5.9% on average. There is a possibility that power dissipation is reduced by 22.5% maximum. In the case of delay and power optimization, our method reduces delay by 6.7% and power dissipation by 5.3% on average.

Simplification orderings, like the recursive path ordering and the improved recursive decomposition ordering, are widely used for proving the termination property of term rewriting systems. The improved recursive decomposition ordering is known as the most powerful simplification ordering. Recently Jouannaud and Rubio extended the recursive path ordering to higher-order rewrite systems by introducing an ordering on type structure. In this paper we extend the improved recursive decomposition ordering for proving termination of higher-order rewrite systems. The key idea of our ordering is a new concept of pseudo-terminal occurrences.

This paper presents some fundamental properties of multiple-valued logic functions monotonic in a partial-ordering relation which is introduced in the set of truth values and does not necessarily have the greatest or least element. Two kinds of necessary and sufficient conditions for monotonic p-valued functions are given with the proofs. Their logic formulas using unary operators defined in the partial-ordering relation and a simplification method for those logic formulas are also given. These results include as their special cases our former results for p-valued functions monotonic in the ambiguity relation which is a partial-ordering relation with the greatest element.

In this paper, we propose a clustering based linear ordering algorithm which consists of global ordering and local ordering. In the global ordering, the algorithm forms clusters from n given vertices and orders the clusters. In the local ordering, the elements in each cluster are linearly ordered. The linear order, thus produced, is used to obtain optimal κ-way partitioning based on scaled cost objective function. When the number of cluster is one, the proposed algorithm is exactly the same as MELO [2]. But the proposed algorithm has more global partitioning information than MELO by clustering. Experiment with 11 benchmark circuits for κ-way (2 κ 10) partitioning shows that the proposed algorithm yields an average of 10.6% improvement over MELO [2] for the κ-way scaled cost partitioning.

The order of faults which are targeted for test-pattern generation affects both of the processing time for test generation and the number of generated test-patterns. This order is referred to as a test generation schedule. In this paper, we consider the effect of scheduling in test generation. We formulate the test generation scheduling problem which minimizes the cost of testing. We propose schedulings based on test-pattern generation time, dominating probability and dominated probability, and analyze the effect of these schedulings. In the analysis, we show that the total test-pattern generation time and the total number of test-patterns can be reduced by the scheduling according to the descending order of dominating probability prior to the ascending order of test-pattern generation. This is confirmed by the experiments using ISCAS'85 benchmark circuits. Further, in the experiments, we consider eight schedulings, and show that the scheduling according to the ascending order of dominated probability is the most effective of them.

An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can represent efficiently many practical Boolean functions and have other desirable properties. However, there is very little theoretical research on the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and related OBDD problems.

Ordered binary decision diagrams (OBDDs) have been widely used in many CAD applications as efficient data structures for representing and manipulating Boolean functions. For the efficient use of the OBDD, it is essential to find a good variable order, because the size of the OBDD heavily depends on its variable order. Dynamic variable reordering is a promising solution to the variable ordering problem of the OBDD. Dynamic variable reordering with the sifting algorithm is especially effective in minimizing the size of the OBDD and reduces the need to find a good initial variable order. However, it is very time-consuming for practical use. In this paper, we propose two new implementation techniques for fast dynamic variable reordering. One of the proposed techniques reduces the number of variable swaps by using the lower bound of the OBDD size, and the other accelerates the variable swap itself by recording the node states before the swap and the pivot nodes of the swap. By using these new techniques, we have achieved the speed-up ranging from 2.5 to 9.8 for benchmark circuits. These techniques have reduced the disadvantage of dynamic variable reordering and have made it more attractive for users.

Almost stoichiometric YBa2Cu3O7-δ(110) or (103) and SrTiOx(110) films, and multilayer films consisting of them have successfully been grown epitaxially on hot SrTiO3 substrates by 90off-axis rf magnetron sputtering with facing targets. Their whole composition, compositional distribution in depth, crystallinity and surface morphology were examined by inductively coupled plasma spectroscopy, Auger electron spectroscopy, reflection high-energy electron diffraction, and scanning tunneling microscopy or atomic force microscope, respectively. When any YBa2Cu3O7-δ film was exposed to air after deposition, a Ba-rich layer was formed in a near surface region of the film. However, such a compositional distribution in depth of the film was improved by in situ deposition of a SrTiOx film on it. Moreover, the surface roughness of the YBa2Cu3O7-δ film was improved by predeposition of a SrTiOx film under it. On the basis of these results, both YBa2Cu3O7-δ/SrTiOx/YBa2Cu3O7-δ/SrTiO3(sub.) and YBa2Cu3O7-δ/SrTiOx/YBa2Cu3O7-δ/SrTiOx/SrTiO3(sub.) multilayer films with average surface roughness of 3 nm were grown reproducibly, which had uniform compositional distribution throughout the depth of the film except a near surface region of the top YBa2Cu3O7-δ layer. A new 222 structure described by Sr8Ti8O20 (Sr2Ti2O5) with a long range ordered arrangement of oxygen vacancies was formed in the SrTiOx films deposited epitaxially on YBa2Cu3O7-δ films.

The self-organizing feature map is one of the most widely used neural network paradigm based on unsupervised competitive learning. However, the learning algorithm introduced by Kohonen is very slow when the size of the map is large. The slowness is caused by the search for large map in each training steps of the learning. In this paper, a fast learning algorithm based on incremental ordering is proposed. The new learning starts with only a few units evenly distributed on a large topological feature map, and gradually increases the number of units until it covers the entire map. In middle phases of the learning, some units are well-ordered and others are not, while all units are weekly-ordered in Kohonen learning. The ordered units, during the learning, help to accelerate the search speed of the algorithm and accelerate the movements of the remaining unordered units to their topological locations. It is shown by theoretical analysis as well as experimental analysis that the proposed learning algorithm reduces the training time from O(M2) to O(log M) for M by M map without any additional working space, while preserving the ordering properties of the Kohonen learning algorithm.