Precise reagent mixing in user-defined ratios is a fundamental requirement in many microfluidic applications, including diagnostics, chemical synthesis, and biological assays. However, existing solutions for ratio-specific mixing often rely on complex active components, such as multiple pressure sources, flow controllers, or on-chip valves, making them costly, bulky, and unsuitable for portable or low-resource settings. In this work, we present a mixer design and a synthesis method for generating 3D-printable microfluidic devices that achieve ratiospecific mixing using only a single constant pressure source. Our method decomposes the desired mixing ratio into additive subcomponents, each represented by a dedicated inlet channel with a tailored length to enforce the correct hydraulic resistance. The method outputs a complete microfluidic layout, ready for direct fabrication via 3D printers. We validate our approach through numerical simulations and physical prototyping across eight diverse mixing scenarios. Results show that the achieved mixing ratios closely resemble the target, demonstrating the method’s accuracy and robustness. This work enables low-cost, portable, and accessible microfluidic devices for ratio-specific solution delivery, broadening the scope of microfluidics in settings where simplicity, reproducibility, and affordability are critical.

Sample preparation, where a certain number of reagents must be mixed in a specific volumetric ratio, is an integral step for various bio-assays. A programmable microfluidic device (PMD) is an advanced flow-based microfluidic biochip (FMB) platform, that considered to be very effective for sample preparation. However, the impact of mixer placement, reagents' distribution, and mixing time on the automation of sample preparation has not yet been investigated. We consider a mixing efficiency model controlled by the number of alternations “μ” of reagents along the mixing circulation path and propose a loading-aware placement strategy that maximizes the mixing efficiency. We use satisfiability modulo theories (SMT) and propose a one-pass strategy for placing the mixers and the reagents, that successfully enhance the loading and mixing efficiencies.

Variational quantum algorithm (VQA) is a promising near-term quantum algorithm to efficiently generate quantum states for various applications from shallow parametrized quantum circuits (PQCs). To fully utilize VQA, it is essential to have measurement methods that efficiently extract desired information from the quantum states. Classical shadow is such method that measures each qubit onto one of three Pauli bases uniformly at random. It has been attracting active research for characterizing the quantum states of PQCs due to its requiring only polynomial number of measurements, in the number of qubits, in contrast to the exponential-measurement quantum state tomography. There are several variants of classical shadow to improve the accuracy of measurement. A highly accurate classical shadow whose choices of Pauli bases are based on a decision diagram (DD) has been recently proposed in designing PQCs. Here, we further extend the DD-based classical shadow by novel modification and application of conventional techniques to optimize DD. We develop a method to optimize the size of DD that can lead to even fewer number of measurements for optimization instances in quantum chemistry as confirmed by numerical experiments. Our results show another facet of the usefulness of DD in the design of PQCs.

Wavelength-routed optical networks-on-chip (WRONoCs) are well-known for providing high-speed and collision-free communication in multi-core processors. Previous work was unable to simultaneously reduce the design complexity and total optical power consumption of WRONoC. Besides, in current designs, each microring resonator (MRR), which is the key component of WRONoC, is configured to demultiplex to one specific wavelength. This significantly increases the MRR usage and the insertion loss. In this work, we adapt different types of ONoC routers into the mesh-based template. To reduce MRR usage, we take advantage of an important feature of MRR, multi-resonance, so that a single MRR can demultiplex signals on multiple wavelengths. To this end, we propose an efficient design method that synthesizes mesh-based WRONoCs using multi-resonance MRRs and existing optical routers to reduce total power consumption. The experimental results show that our method outperforms state-of-the-art design methods in significantly reducing MRR usage and optical power.

It is natural to assume that we can perform quantum operations between only two adjacent physical qubits (quantum bits) to realize a quantum computer for both the current and possible future technologies. This restriction is called the Nearest Neighbor Architecture (NNA) restriction. This paper proposes an SMT-solver-based synthesis of quantum circuits consisting of CNOT, H, and T gates to satisfy the NNA restriction. Although the existing SMT-solver-based synthesis cannot treat H and T gates directly, our method treats the functionality of quantum-specific T and H gates carefully so that we can utilize an SMT-solver to minimize the number of CNOT gates; unlike the existing SMT-solver-based methods, our method considers "Don't Care" conditions in intermediate points of a quantum circuit by exploiting the property of T gates to reduce CNOT gates. Experimental results show that our approach can reduce the number of CNOT gates by 58.11% on average compared to the naive application of the existing method which does not consider the "Don't Care" condition.

There has been a lot of attention to digital microfluidic biochips (DMFBs) in biochemical and medical industries. A major error source in operations on a DMFB is due to an unbalanced splitting error at a mixing operation. There has been a lot of existing research to tackle this problem; essentially two strategies have been studied so far. One strategy is a retry-based roll-back strategy; if an unacceptable error is detected, we roll back to a checkpoint to redo some part of the experiment again. The other strategy is to duplicate some concentration values, and mix droplets with the same concentration values to mitigate the impact of unbalanced splitting errors. Obviously, both techniques increase the number of mixing operations. This paper proposes a totally new technique compared to the above-mentioned existing two strategies. More precisely, our proposed method only selects the destinations of the output droplets from an intermediate node that has more than two outputs to be used later; our method does not need any additional overhead unlike the existing strategies. Although such a selection has not been studied in the community, this paper reveals that we can mitigate the impact of unbalanced splitting errors by an appropriate selection. To find the best selection, we introduce a measure called RRE (Ratio of Residual Error) which can tell how much each error affects the final target concentration very efficiently. We also show some simulation results by which we can confirm that our method can indeed reduce the impact of unbalanced splitting errors without any overhead.

LUT-based synthesis methods have recently been proposed as a way to synthesize quantum Boolean circuits in a qubit constrained environment. Other results have also shown that allowing a relative phase when implementing quantum Boolean circuits yields an advantage in T-count without additional ancilla qubits, which is advantageous in the fault-tolerant quantum computing paradigm. We propose a method that utilizes both LUT-based synthesis and relative phase quantum Boolean circuits which minimize the T-count while minimizing the ancilla required to implement them. We leverage recent results regarding relative phase versions of Boolean functions and Shannon's decomposition to propose a novel method to synthesize arbitrary Boolean functions up to a relative phase. We then utilize this method to synthesize Boolean logic inside each LUT as a relative phase quantum Boolean circuit and show that the resulting quantum circuit has a clear advantage in T-count over more naive methods.

Sample preparation is an essential step in almost all bioprotocols, which can be efficiently achieved via a sequence of mixing steps called mixing graph. In the literature, several techniques have been reported to determine a mixing graph with the minimal number of mixing steps, the minimal usage of reagent fluids, the minimal wastage, or sometimes a combination of them. The retention time of a flow-based microfluidic biochip (FMB) is defined as the maximum duration for which a fluid can be stored within a microchannel without any fluid leakage. However, the retention time has not yet been considered as a scheduling constraint during the automation of the sample preparation using an FMB in order to obtain the scheduled mixing graphs. In this article, we propose a retention time-aware scheduling method called time-aware list scheduling (TALS), which can be used with the state-of-the-art methods, and a new satisfiability-based mixing algorithm called time-aware sample preparation (TASP) to obtain the scheduled mixing graph for a target ratio satisfying the retention time constraint and the number of available on-chip mixers in an FMB. Simulation results suggest that on an average TALS always outperforms a baseline scheduling method while scheduling any mixing graph, whereas TASP can determine the optimal and scheduled mixing graphs compared to the existing mixing methods combined with TALS.

We usually use Mixed-Polarity Multiple-Control Toffoli (MPMCT) gates to realize large control logic functions for quantum computation. A logic circuit consisting of MPMCT gates needs to be mapped to a quantum computing device that has some physical limitation; (1) we need to decompose MPMCT gates into one or two-qubit gates, and then (2) we need to insert SWAP gates such that all the gates can be performed on Nearest Neighbor Architectures (NNAs). Up to date, the above two processes have been independently studied intensively. This paper points out that we can decrease the total number of the gates in a circuit if the above two processes are considered dynamically as a single step; we propose a method to inserts SWAP gates while decomposing MPMCT gates unlike most of the existing methods. Our additional idea is to consider the effect on the latter part of a circuit carefully by considering the qubit layout when composing an MPMCT gate. We show some experimental results to confirm the effectiveness of our method.

Microfluidic lab-on-a-chip has emerged as a new technology for implementing biochemical protocols on small-sized portable devices targeting low-cost medical diagnostics. Among various efforts of fabrication of such chips, programmable microfluidic device (PMD) is a relatively new technology for implementation of flow-based lab-on-a-chips. A PMD chip is suitable for automation due to its symmetric nature. In order to implement a bioprotocol on such a reconfigurable device, it is crucial to automate sample preparation on a chip as well. Sample preparation, which is a front-end process to produce the desired target concentrations of the input reagent fluid, plays a pivotal role in every bioassay or bioprotocol. In this paper, first, a method referred as dilution algorithm in two steps (DATS) is proposed, which needs only two diluting operations for any target concentration to achieve. Then, we present another method called as dilution algorithm on a small dilution area (DASDA), which needs less area compared to that by DATS. Finally, we propose the heuristic for efficient dilution of biochemical fluids using a PMD chip referred as dilution algorithm in a restricted dilution area (DARDA) that produces more accurate (with less error) target concentration value on a restricted area of the PMD chip in a shorter mixing time. Simulation results reveal that DARDA outperforms a start-of-the-art dilution algorithm applicable for PMD chips in terms of three performance parameters namely mixing time, mixing area and error in target concentration.

Recently, Programmable Microfluidic Device (PMD) has got an attention of the design automation communities as a new type of microfluidic biochips. For the design of PMD chips, one of the important tasks is to minimize the number of flows for loading the reactant fluids into specific cells (by creating some flows of the fluids) before the bio-protocol is executed. Nevertheless of the importance of the problem, there has been almost no work to study this problem. Thus, in this paper, we intensively study this fluid loading problem in PMD chips. First, we successfully formulate the problem as a constraint satisfaction problem (CSP) to solve the problem optimally for the first time. Then, we also propose an efficient heuristic called Determining Flows from the Last (DFL) method for larger problem instances. DFL is based on a novel idea that it is better to determine the flows from the last flow unlike the state-of-the-art method Fluid Loading Algorithm for PMD (FLAP) [Gupta et al., TODAES, 2019]. Simulation results confirm that the exact method can find the optimal solutions for practical test cases, whereas our heuristic can find near-optimal solutions, which are better than those obtained by FLAP.

Microfluidic fully programmable valve array (FPVA) biochips have emerged as general-purpose flow-based microfluidic lab-on-chips (LoCs). An FPVA supports highly re-configurable on-chip components (modules) in the two-dimensional grid-like structure controlled by some software programs, unlike application-specific flow-based LoCs. Fluids can be loaded into or washed from a cell with the help of flows from the inlet to outlet of an FPVA, whereas cell-to-cell transportation of discrete fluid segment(s) is not precisely possible. The simplest mixing module to realize on an FPVA-based LoC is a four-way mixer consisting of a 2 × 2 array of cells working as a ring-like mixer having four valves. In this paper, we propose a design automation method for sample preparation that finds suitable placements of mixing operations of a mixing tree using four-way mixers without requiring any transportation of fluid(s) between modules. We also propose a heuristic that modifies the mixing tree to reduce the sample preparation time. We have performed an extensive simulation and examined several parameters to determine the performance of the proposed solution.

In this paper, we propose an exact method of directly synthesizing a nearest neighbor compliant (NNC) quantum circuit with the smallest depth in 2-D architecture, given a reversible function. Our method maps the synthesis problem to a Boolean satisfiability (SAT) problem and uses a satisfiability modulo theories (SMT) solver to find an assignment of a network of allowed quantum gates. Since an SMT solver performs an exhaustive search, it can be ensured that on a specific qubit placement, the NNC quantum circuit synthesized by our method has the smallest number of quantum gates. However, the exhaustive search also makes our exact method not scale well. For that reason, we propose another method of applying our exact method in the local synthesis of large-scale circuits, to in parallel synthesize sub-NNC quantum circuits. From the experimental results, the quantum costs of the NNC quantum circuits synthesized by our methods are reduced by an average of 23.89%, when compared to an optimal heuristic method which determines the smallest number of SWAP gates in 2-D architecture.

We propose an efficient approach to optimize the number of necessary SWAP gates when we perform a quantum circuit on IBM Q system. Our idea is to change the order of quantum gates (if possible) so that each sub-circuit has only gates performing on adjacent qubits. For each sub-circuit, we utilize a SAT solver to find the best qubit placement such that the subcircuit has only gates on adjacent qubits. Each sub-circuit may have a different qubit placement such that we do not need SWAP gates for the sub-circuit. Thus, we insert SWAP gates between two sub-circuits to change the qubit placement which is desirable for the following sub-circuit. To reduce the number of such SWAP gates between two sub-circuits, we utilize A* algorithm.

The identification of threshold function (TF), which determines whether a Boolean function can be represented by an linear threshold logic gate (LTG) or not, is a fundamental but important task in the theories of threshold logic. In this paper, we propose a more efficient and effective algorithm of TF identification by constructing the system of irredundant inequalities and adjusting the weight assignment comprehensively. This is the first non-ILP-based approach that is able to identify all the eight-input TFs. The experimental results demonstrated that the proposed approach is more effective than all the existing non-ILP-based approaches and the LTGs obtained by the proposed approach are optimal for near 100% cases. For TFs with 9–15 inputs, the proposed approach can identify 100 000 randomly generated TFs as well in a reasonable CPU time.

Microfluidic lab-on-a-chip has emerged as a new technology for implementing biochemical protocols on small-sized portable devices targeting low-cost medical diagnostics. Among various efforts of fabrication of such chips, a relatively new technology is a programmable microfluidic device (PMD) for implementation of flow-based lab-on-a-chip. A PMD chip is suitable for automation due to its symmetric nature. In order to implement a bioprotocol on such a reconfigurable device, it is crucial to automate a sample preparation on-chip as well. In this article, we propose a dilution PMD algorithm (namely DPMD ) and its architectural mapping scheme (namely generalized architectural mapping algorithm ( GAMA )) for addressing fluidic cells of such a device to perform dilution of a reagent fluid on-chip. We used an optimization function that first minimizes the number of mixing steps and then reduces the waste generation and further reagent requirement. Simulation results show that the proposed DPMD scheme is comparative to the existing state-of-the-art dilution algorithm. The proposed design automation using the architectural mapping scheme reduces the required chip area and, hence, minimizes the valve switching that, in turn, increases the life span of the PMD-chip.

In order to generate an initial reversible/quantum circuit to realize a given Boolean function, one of the major approaches is to find a small Exclusive-or Sum-Of-Products (ESOP) expression for the function; each product term in the ESOP expression naturally corresponds to a single Mixed Polarity Multiple-Control Toffoli (MPMCT) gate. In this paper, we propose a technique to perform pre-optimization before generating an ESOP expression. Our approach is unique in a sense that instead of finding a small ESOP expression for a given function, we try to change it by adding MPMCT gates so that the modified function has a smaller ESOP expression. We expect that our approach can generate a better initial circuit compared to using ESOP minimization techniques only. Indeed our preliminary experiments for small functions confirm this expectation. Thus, we expect that our approach would be a good pre-optimization technique that can be used with most existing reversible circuit synthesis techniques.

As in the case of VLSI circuits, digital microfluidic biochips must be adequately tested after manufacturing to guarantee the correctness of the biomedical experiments. In this work, we propose an efficient test method for digital microfluidic biochips. In contrast to related prior work, the proposed test method is not only able to cover all chip defects but also applicable to arbitrary chip layouts. Experiments demonstrate that using the proposed test method, the test-application time can be reduced significantly compared to related prior work.

Digital microfluidics is viewed as one of the most promising technologies for biomedical experiments. Digital microfluidic biochips are often used today for applications such as point-of-care health assessment, drug discovery, and air-quality monitoring. Therefore, such devices must be adequately tested after manufacturing to guarantee the correctness of the biomedical experiments. Previous test methods for digital microfluidic biochips are either unable to cover all chip defects or inapplicable for application-specific biochips with arbitrary layouts. Furthermore, previous methods also ignore the fluidic constraints required for droplet routing, which makes the test droplet routing problem much more challenging in realistic test-application scenarios. In this paper, we propose the first test method for digital microfluidic biochips that is not only able to cover all chip defects, but is also applicable for arbitrary chip layouts. Moreover, we propose an optimization technique to route test droplets with minimum test-application time. A polynomial-time scheduling algorithm is also presented to solve the optimization problem in an efficient manner. Experiments demonstrate that the proposed test method requires significantly less test-application time compared to related previous work.

Digital microfluidic biochips have become one of the most promising technologies for biomedical experiments. In modern microfluidic technology, reducing the number of independent control pins that reflects most of the fabrication cost, power consumption, and reliability of a microfluidic system, is a key challenge for every digital microfluidic biochip design. However, all the previous chip designs sacrifice the optimality of the problem, and only limited reduction on the number of control pins is observed. Moreover, most existing designs cannot satisfy high-throughput demand for bioassays, and thus inapplicable in practical contexts. In this paper, we propose the first optimal pin-count design scheme for digital microfluidic biochips. By integrating a very simple combinational logic circuit into the original chip, the proposed scheme can provide high-throughput for bioassays with an information-theoretic minimum number of control pins. Furthermore, to cope with the rapid growth of the chip's scale, we also propose a scalable and efficient heuristics to reduce the number of control pins. A logic optimization technique, which can be used to reduce the complexity of the integrated combinational logic circuit, is also presented in this paper. Experiments demonstrate that the proposed scheme can obtain much fewer number of control pins compared with the previous state-of-the-art works.

Sample preparation, which is a front-end process to produce droplets of the desired target concentrations from input reagents, plays a pivotal role in every assay, laboratory, and application in biomedical engineering and life science. The consumption of sample/buffer/waste is usually used to evaluate the effectiveness of a sample preparation process. In this paper, for the first time, we present an optimal sample preparation algorithm based on a minimum-cost maximum-flow model. By using the proposed model, we can obtain both the optimal cost of sample and buffer usage and the waste amount even for multiple-target concentrations. Experiments demonstrate that we can consistently achieve much better results not only in the consumption of sample and buffer but also the waste amount when compared with all the state-of-the-art of the previous approaches.

Digital microfluidic biochips have become one of the most promising technologies for biomedical experiments. In modern microfluidic technology, reducing the number of independent control pins that reflects most of the fabrication cost, power consumption and reliability of a microfluidic system, is a key challenge for every digital microfluidic biochip design. However, all the previous chip designs sacrifice the optimality of the problem, and only limited reduction on the number of control pins is observed. Moreover, most existing designs cannot satisfy high-throughput demand for bioassays, and thus inapplicable in practical contexts. In this paper, we propose the first optimal pin-count design scheme for digital microfluidic biochips. By integrating a very simple combinational logic circuit into the original chip, the proposed scheme can provide high-throughput for bioassays with an information-theoretic minimum number of control pins. Furthermore, to cope with the rapid growth of the chip's scale, we also propose a scalable and efficient heuristics. Experiments demonstrate that the proposed scheme can obtain much fewer number of control pins compared with the previous state-of-the-art works.

Microfluidic biochips have been recently proposed to integrate all the necessary functions for biochemical analysis. There are several types of microfluidic biochips; among them there has been a great interest in flow-based microfluidic biochips, in which the flow of liquid is manipulated using integrated microvalves. By combining several microvalves, more complex resource units such as micropumps, switches and mixers can be built. For efficient execution, the flow of liquid routes in microfluidic biochips needs to be scheduled under some resource constraints or routing constraints. The execution time of the biochemical operations depends on the binding and scheduling results. The most previously developed binding and scheduling algorithms are based on heuristics, and there has been no method to obtain optimal results. Considering the above, this paper proposes an optimal method by casting the problem to a clique problem.

With continuous decrease of device geometries in the nanoscale era of digital design, increasing importance is given to the reliability aspect of basic building blocks. In this context, this brief discusses the inherent fault tolerance capability of conventional logic gates before proceeding with the analysis of error immune property of a subset of combinational standard cells present in commercial digital libraries. The analysis has led to the following inferences: (i) Compared to complex-gate implementation, discrete-gate based realization of compound logic functions enables a mean improvement in the error resiliency metric by 68.2%, and (ii) the associated increase in area overhead for discrete-gate realizations as a trade-off for enhanced fault tolerance over complex gate implementations is found to be 51.6% on average.

The growing size, density and complexity of modern VLSI chips are contributing to an increase in hardware faults and design errors in the silicon, decreasing manufacturing yield and increasing the design cycle. The use of Partially Programmable Circuits (PPCs) has been recently proposed for yield enhancement with very small overhead. This new circuit structure is obtained from conventional logic by replacing some subcircuits with programmable LUTs. The present paper lays the theoretical groundwork for evaluating PPCs with Quantified Boolean Formula (QBF) satisfiability. First, QBF models are constructed to calculate the fault tolerance and design error tolerance of a PPC, namely the percentages of faults and design errors that can be masked using LUT reconfigurations. Next, zero-cost Engineering Change Order (ECO) in PPCs is investigated. QBF formulations are given for performing ECOs, and for quantifying the ECO coverage of a PPC architecture. Experimental results are presented evaluating PPCs from [1], demonstrating the applicability and accuracy of the proposed formulations.

This paper formulates the logic level circuit optimization problem for topological quantum computation. Observing the properties of brading operations in topological quantum computation, we formulate our problem as to find a good gate order and a good initial qubit order. For the problem, we propose an efficient method by utilizing an algorithm for clique finding. Our experimental result shows the effectiveness of our proposed method.

Recently, the miniaturization process has brought an increase in transistor variations and in the failure rate at transistors. We propose a small variety of new standard cells. The proposed cells can correct and detect transistor faults. A functional unit with the proposed cells shows better fault tolerance. The area of this unit is approximately 1.4 times that of traditional cells.

In this paper we propose a practical framework to utilize quantum computers in the future. To the best of our knowledge, this is the first paper to show a concrete usage of quantum computation in general programming. In our framework, we can utilize a quantum computer as a coprocessor to speed-up some parts of a program that runs on a classical computer. To do so, we propose several new ideas and techniques, such as a practical method to design a large quantum circuits for search problems and an efficient quantum comparator.

In this paper, we propose a new framework to synthesize rapid single flux quantum (RSFQ) logic circuits. In our framework, we construct a virtual cell, which we call "2-AND/XOR," from the RSFQ logic primitives. By using 2-AND/XOR cells, we can successfully adopt the conventional logic design techniques into our framework, and thus we can successfully generate RSFQ circuits in reasonable time even for large benchmark circuits that have not been reported in the existing researches

An (n,1,p)-quantum random access (QRA) coding, introduced by Ambainis, Nayak, Ta-shma and Vazirani in ACM Symp. on Theory of Computing 1999, is the following communication system: The sender which has n-bit information encodes his/her information into one qubit, which is sent to the receiver. The receiver can recover any one bit of the original n bits correctly with probability at least p, through a certain decoding process based on positive operator-valued measures. Actually, Ambainis et al. shows the existence of a (2,1,0.85)-QRA coding and also proves the impossibility of its classical counterpart. Chuang immediately extends it to a (3,1,0.79)-QRA coding and whether or not a (4,1,p)-QRA coding such that p > 1/2 exists has been open since then. This paper gives a negative answer to this open question

Recently, reconfigurable computing has come under the spotlight as the new computing paradigm. A machine employing this paradigm combines the flexibility of a general purpose processor with the performance of a dedicated system. In this paper, we propose Event-Oriented Computing, a new application area for reconfigurable computing. We also show the architecture model suited to Event-Oriented Computing. Using Artificial Life as an example, we report the evaluation of our architecture model.

This presentation gives a new SPFD-based method to make a target wire redundant with higher possibility than the previous rewiring methods. After placement and routing, we obtain or estimate how much the existing and candidate wires interferes such physical design, and thus, we find out the most critical one of the existing wires. In order to remove it, the previous methods add new input wires to only one LUT. Actually, in the context of gate/cell-based logic optimization, it is well-known that input wire addition to many gates/cells is likely to make the critical one redundant. However, in an FPGA circuit, since an LUT can realize an arbitrary function for a specified number of inputs, such wire addition has never been considered to be useful. In this presentation, we provides with an SPFD-based condition for such wire addition to improve the FPGA circuit performance. We also present several experimental results to show the effectiveness of the proposed condition.

This paper proposes an innovative method for SPFD-based rewiring in Look-Up-Table-based (LUT-based) FPGA circuits. The new method adds new input wires to two or more LUT's in order to remove or to replace a target wire. There have been a few rewiring methods for FPGA circuits so far, such as the original SPFD-based optimization sometimes called Local Rewiring (LR), SPFD-based Global Rewiring (GR) and SPFD-based Enhanced Rewiring (ER). However, all of them replace one wire with other new input wire to one LUT but not with those to two or more LUT's. Moreover, the LR removes or replaces input wires with new one to the same LUT only, and the GR and ER topologically limit the LUT's where new input wires are added. Our new method, called One-to-Many Rewiring (OMR), loosens such topological constraints for more flexible FPGA circuit transformation so that it is easier to import constraints on physical design to the logic optimization. The experimental results show our OMR can transform FPGA circuits more flexibly than the LR, GR and ER, by introducing the new manipulation, wire addition. The OMR can rewire 1.2 times as many wires as the existing methods, especially, the ER. The computation time is as short as the existing methods.

This paper gives a simple but nontrivial set of local transformation rules for Control-NOT(CNOT)-based combinatorial circuits. It is shown that this rule set is complete, namely, for any two equivalent circuits, S1 and S2, there is a sequence of transformations, each of them in the rule set, which changes S1 to S2. Our motivation is to use this rule set for developing a design theory for quantum circuits whose Boolean logic parts should be implemented by CNOT based circuits. As a preliminary example, we give a design procedure based on our transformation rules which reduces the cost of CNOT-based circuits.

Abstract — We present an efficient framework for synthesizing look-up table (LUT) networks. Some of the existing LUT network synthesis methods are based on functional (boolean) decompositions. Our method also uses functional decompositions, but we try to use various decomposition methods, which include algebraic decompositions. Therefore, this method can be thought of as a general framework for synthesizing LUT networks by integrating various decomposition methods. We use a cost database file which is a unique characteristic in our method. We also present comparisons between our method and some well-known LUT network synthesis methods, and evaluate the final results after placement and routing. Although our method is rather heuristic in nature, the experimental results are encouraging. I.

In this paper, we propose a unique way to express functional flexibility by using sets of pairs of functions called "Sets of Pairs of Functions to be Distinguished" (SPFDs) rather than traditional incompletely specified functions. This method was very naturally derived from a unique concept for distinguishing two logic functions, which we explain in detail in this paper. The flexibility represented by an SPFD assumes that the internal logic of a node in a circuit can be freely changed, SPFDs make good use of this assumption, and they can express larger flexibility than incompletely specified functions in some cases. Although the main subject of this paper is to explain the concept of SPFDs, we also present an efficient method for calculating the functional flexibilities by SPFDs because the concept becomes useful only if there is an efficient calculation method for it. Moreover, we present a method to use SPFDs for circuit transformation along with a proof of the correctness of the method, We further make a comparison between SPFDs and compatible sets of permissible functions (CSPFs), which express functional flexibility by incompletely specified functions. As an application of SPFDs, we show a method to optimize LUT (look-up table) networks and experimental results.

This paper presents a method for synthesizing lookup table (LUT) networks. The strategy employed by our method is very different from the strategies of previous methods; many decomposition methods that are not only algebraic but also functional are integrated. Our method can be thought of as a general framework for LUT network synthesis integrating various decomposition methods. The experimental results are very encouraging.

This paper presents new efficient methods to find "optimal bi-decomposition" forms of logic functions. An "optimal bi-decomposition" form of f(X) is f=/spl alpha/(g/sub 1/(X/sup 1/),g/sub 2/(X/sup 2/)) where the total number of variables in X/sup 1/ and X/sup 2/ is the smallest among all bi-decomposition forms of f. We consider two methods; one's decomposition form is (g/sub 1//spl middot/g/sub 2/) and the other's is (g/sub 1//spl oplus/g/sub 2/). The proposed methods can find one of the existing "optimal" decomposition forms efficiently based on the Branch-and-Bound algorithm. These methods can decompose incompletely specified functions. Preliminary experimental results show that the proposed methods can construct networks with fewer levels than conventional methods.

Simple disjunctive decomposition is a special case of logic function decomposition, where variables are divided into two disjoint sets and there is only one newly introduced variable. This paper presents that many simple disjunctive decompositions can be found easily by detecting symmetric variables or checking variable cofactors. We also propose an algorithm that constructs a new logic representation for a simple disjunctive decomposition by assigning constant values to variables in the original representation. The algorithm enables us to apply the decomposition with keeping good structures of the original representation. We have performed experiments to restructure fanout free cones of multi-level logic circuits, and obtained better results than when not restructuring them.

This paper presents an efficient method for a simple disjunctive decomposition, where candidates for the bound set are restricted to sets of symmetric variables to reduce the computation cost. Symmetric variables are detected by depth-first traversals of an ordered binary decision diagram (OBDD) and decompositions are carried out by changing the variable order of the OBDD. We do not change the variable order until the change is really needed. Experimental results show that even if the decomposition form was restricted, many practical functions could be decomposed. The execution time for decomposition was very small even for functions with many variables. Combined with an exhaustive search, the method successfully decomposed some functions that could not be decomposed by exhaustive search alone in a practical amount of time.

This paper presents a new method to express functional permissibilities for look-up table (LUT) based field programmable gate arrays (FPGAs). The method represents functional permissibilities by using sets of pairs of functions, not by incompletely specified functions. It makes good use of the properties of LUTs such that their internal logics can be freely changed. The permissibilities expressed by the proposed method have the desired property that at many points of a network they can be simultaneously treated. Applications of the proposed method are also presented; a method to optimize networks and a method to remove connections that are obstacles at the routing step. Preliminary experimental results are given to show the effectiveness of our proposed method.

No abstract available.