The 2-D architecture of fully programmable valve arrays (FPVAs) is designed as a crossbar consisting of reaction chambers and microvalves, functioning as a versatile, flow-based microfluidic lab-on-chip for implementing biochemical protocols. While an FPVA enables efficient execution of various fluidic operations—such as mixing, loading, and storage, transporting fluids between chambers remains a challenging task. Furthermore, mapping a general mixing tree (representing a sequence of mixing steps) onto an FPVA is complex. It requires careful placement of reagents into specific chambers and the scheduling of subsequent mixing operations. Most sample preparation algorithms aim to generate a minimum-depth mixing tree to achieve the target mixing ratio. However, due to constraints on fluid transportation and scheduling, such a tree may not be the most practical for FPVA implementation. In this article, we harness the power of a satisfiability solver to derive a skewed mixing tree/graph that can be efficiently mapped onto an FPVA using a single mixer. This approach localizes most fluidic operations to a small region of the crossbar. Simulation results show that, for most mixing ratios, a skewed mixing tree can be found which not only reduces fluid-transportation distance and scheduling complexities but also the number of loading cycles, reagent volumes, and waste production in sample preparation, when compared to the approach based on the minimum-depth mixing tree.

With the emergence of all-inclusive AI/ML applications, hardware solutions, commonly known as AI-Accelerators (AIA), are now being widely adopted to emulate deep neural networks (DNN) to facilitate faster and large-scale data analytics. An AIA-chip comprises a 2D systolic array of identical processing units (PEs), registers, and glue logic. These arrays may be implemented with traditional digital logic or with analog primitives such as memristors. As the packing density of AIA-chips increases, they become vulnerable to various manufacturing defects thereby compromising yield and the accuracy of prediction. In this review article, we summarize various methods that have been recently proposed for expediting Automatic Test-Pattern Generation (ATPG) for stuck-at and transition faults in AIA-arrays. Other relevant issues such as fault-criticality, self-test, fault-recovery, and the asymmetry of fault behavior, are also discussed.

Memristors have recently shown significant promise in designing memory and logic subsystems. A 2D-crossbar architecture built with memristor arrays provides a convenient platform for storing multivalued memory states by utilizing the analog variation of current-induced resistance through these cells. The integration of CMOS components with non-CMOS memristor cells further enhances the scope of their applications to various complex system designs. However, present-day memristors by virtue of their inherent structure are prone to various manufacturing defects and sensitive to operational modalities. Existing techniques for testing memristor arrays are either ad hoc in nature or suited for application-specific designs with little concern for optimizing test time. In this work, we envisage a 2-D memristor crossbar as a network and identify certain paths that are suitable for fault sensitization. For full-size square and rectangular memristive crossbars, the proposed method optimizes test time using a path-based technique guided by maximum matching in bipartite graphs. An integer linear programming (ILP) formulation is then used to solve the problem for a general crossbar, either full or incomplete. Simulation results with LTspice demonstrate the effectiveness and superiority of the method to the prior art in terms of test time and fault coverage.

Microfluidic platforms have recently emerged as an invaluable component for studying synthetic biology as they are capable of emulating complex molecular networks of biological pathways (biocircuits) on a chip. A special type of biochemical assays, known as biocircuit-regulatory scanning (BRS) assays, is employed to regulate gene expression, enabling comprehensive exploration of related biocircuit parameters. Prior work has provided high-level design methodologies for implementing BRS; however, most of these methods are abstract and cannot be used in practice as they overlook the dynamics of interactions between the samples and the biochip. In this article, we address this limitation by providing a comprehensive framework that implements BRS assays. The proposed framework, named BioScan, includes: 1) a statistical method that selects suitable volumetric ratios of biochemicals used to execute a BRS assay; 2) a high-level synthesis method that generates the specifications of the target BRS assay; 3) a translation technique enabling implementation of BRS on a microelectrode-dot array (MEDA) biochip; and 4) a Dirichlet-regressor that constructs the parameter space of the associated biocircuit. Simulation results show that the proposed framework can efficiently perform parameter-space exploration (PSE) while significantly reducing completion time and reagent cost.

Microfluidic biochips have recently emerged with significant promise and versatility in automating a variety of biochemical protocols on a tiny chip. Sample preparation, which involves the mixing of fluids with a specified target ratio in the minuscule scale, is an essential component of these protocols. Algorithms that optimize on-chip sample-preparation cost and time are closely intertwined with the underlying mixing model, mixing sequence, and fluidic architecture. Although numerous mixing models have been studied in the literature, their impact on the dynamics of mixing steps is hitherto not fully understood. In this article, we show that various mixing models can be envisaged in the light of prime factorization of integers thus establishing a connection among mixing algorithms, chip architectures, and performance. This insight has led to the development of the proposed factorization-based dilution algorithm (FacDA) considering a generalized mixing model suitable for micro-electrode-dot-array (MEDA) biochips. It further leads to target volume oriented dilution algorithm (TVODA) to cater to user’s demand for an output with a given volume. We formulate the optimization problem on the fabric of the satisfiability modulo theory (SMT) while determining mixing sequences. Simulation results on a large number of test-cases reveal thatFacDAandTVODAoutperform the state-of-the-art dilution algorithms for MEDA biochips with respect to reactant cost, mixing time, and waste production.

Microfluidic lab-on-chips offer promising technology for the automation of various biochemical laboratory protocols on a minuscule chip. Sample preparation (SP) is an essential part of any biochemical experiments, which aims to produce dilution of a sample or a mixture of multiple reagents in a certain ratio. One major objective in this area is to prepare dilutions of a given fluid with different concentration factors, each with certain volume, which is referred to as the demand-driven multiple-target (DDMT) generation problem. SP with microfluidic biochips requires proper sequencing of mix-split steps on fluid volumes and needs storage units to save intermediate fluids while producing the desired target ratio. The performance of SP depends on the underlying mixing algorithm and the availability of on-chip storage, and the latter is often limited by the constraints imposed during physical design. Since DDMT involves several target ratios, solving it under storage constraints becomes even harder. Furthermore, reduction of mix-split steps is desirable from the viewpoint of accuracy of SP, as every such step is a potential source of volumetric split error. In this article, we propose a storage-aware DDMT algorithm that reduces the number of mix-split operations on a digital microfluidic lab-on-chip. We also present the layout of the biochip with -storage cells and their allocation technique for . Simulation results reveal the superiority of the proposed method compared to the state-of-the-art multi-target SP algorithms.

Digital microfluidic biochips have fueled a paradigm shift in implementing bench-top laboratory experiments on a single tiny chip, thus replacing costly and bulky equipment. However, because of imprecise fluidic functions, several volumetric split errors may occur during the execution of bioassays. Earlier approaches to error-correcting sample preparation addressed this problem by using a cyberphysical system yielding several drawbacks such as increased sample preparation cost and time, and uncertainty in assay completion time. In addition, error correction for only a single-target sample has been considered so far, although many assays require the production of multi-target samples. In this work, we present an error-free dilution technique that guarantees the correctness of the resulting concentration factor of a sample without performing any additional roll-back or roll-forward action. To the best of our knowledge, we are the first to present a solution strategy for tackling dispensing errors during sample preparation. We use micro-electrode-dot-array biochips that offer the advantages of manipulating fractional volumes of droplets (aliquots) for navigation, as well as mix-split operations. Instead of performing traditional mix-and-split steps with integral-volume droplets, we execute only an aliquoting-and-mix sequence using differential-size aliquots. Thus, all split operations, which are the main source of errors in conventional digital microfluidic biochips, are completely eliminated, and hence neither sensing nor any correcting action is needed, and further, no management of intermediate waste droplets is needed. Additionally, the procedure can be fully parallelized for accurately producing multiple dilutions of a sample. Experimental results corroborate the superiority of the proposed method in terms of error management, as well as sample preparation cost and time.

Block ciphers are widely regarded as concrete realizations of pseudorandom permutations with established security features. However, their applicability outside the domain of encryption has not been explored so far. In this paper, we open up, for the first time, an entirely novel application of them to logic hiding. We show that a combinational circuit can always be embedded within a block cipher having a bit-permutation based diffusion layer, preserving the cipher structure and security properties. The functionality of the embedded circuit becomes transparent only on the application of a secret key, whereas a wrong key will cause behaviour that is uncorrelated to that of the circuit. As an immediate application, we propose a combinational logic-locking scheme. The proposed locking scheme is also found to be robust against the state-of-the-art (SAT-assisted and other) attacks on logic locks.

Microfluidic biochips enable low-cost automation of biochemical protocols with numerous applications to medical diagnostics, forensics, molecular biology, and drug design. An important component of protocol design is sample preparation, which involves dilution or mixing of two or more fluids in a desired ratio of concentration factors (CF). Existing continuous-flow microfluidic biochips deploy either free-flowing networks where only a single layer of flow-channels is used devoid of any control valves, or valve-based technology where the flow-layer is augmented with a control layer of valves. While the former is easy to fabricate, reliable, and less expensive, they are typically hardwired for specific applications only. The latter class, although programmable, is expensive and prone to various manufacturing and operational defects. In this paper, we present the physical design of a microfluidic network that is free-flowing as well as programmable. The proposed valve-free network resembles a complete binary tree with serpentine obstacles embedded within its channels, and can be used to achieve a desired dilution of a sample just by proper selection of fluid concentrations to be fed as inputs under constant pressure. Simulation with COMSOL Multiphysics Software shows that the proposed network provides a powerful and versatile architecture for solution preparation with minimal control, outperforming prior approaches in terms of the accuracy of CFs and time for convergence.

Lab-on-chip (LoC) technology has emerged as one of the major driving forces behind the recent surge in biochemical protocol automation. Dilution and mixture preparation with fluids in a desired ratio, constitute basic steps in sample preparation for which several LoC-based architectures and algorithms are known. The optimization of cost and time for such protocols requires proper sequencing of fluidic mix-and-split steps, and storage-units for holding intermediate-fluids to be reused in the later steps. However, practical design constraints often limit the amount of on-chip storage in microfluidic LoC architectures and thus can badly affect the performance of the algorithms. Consequently, results generated by previous work may not be useful (in the case they require more storage-units than available) or more expensive than necessary (in the case when storage-units are available but not used, e.g., to further reduce the number of mix/split operations or reactant-cost). In this paper, we propose new algorithms for dilution and mixing with continuous-flow-based LoCs that explicitly take care of storage constraints while optimizing reactant-cost and time of sample preparation. We present a symbolic formulation of the problem that captures the degree of freedom in algorithmic steps satisfying the specified storage constraints. Solvers based on Boolean satisfiability are used to achieve the optimization goals. The experimental results show the efficiency and effectiveness of the solution as well as a variety of applications where the proposed methods would prove beneficial.

Flow-based microfluidic biochips have become a promising platform for complex biochemical assays. As the integration of such chips is increasing, a flexible general reconfigurable platform, fully programmable valve array (FPVA), has emerged. Such a 2-D array comprises regularly arranged valves using which flow-networks with different geometry, size, and connectivity can be constructed dynamically. However, the test generation for such arrays becomes challenging due to the large number of potential flow-networks and transportation paths that can be configured on-chip. In this article, we propose a strategy to generate efficient test patterns for FPVAs based on the concepts of test paths and cuts. These patterns together can cover multiple faults in both flow and control layers. We also introduce the concept of test trees and multiple cuts for a test pattern to deal with faults in FPVAs with multiple ports. Moreover, the proposed method can be applied to generate test patterns for traditional flow-based biochips with predefined architectures. The simulation results demonstrate that defects in FPVAs can be detected reliably by a limited number of test patterns generated by the proposed method. For traditional biochips with predefined architectures, these patterns also exhibit an improved test efficiency.

Microfluidic technologies enable replacement of time-consuming and complex steps of biochemical laboratory protocols with a tiny chip. Sample preparation (i.e., dilution or mixing of fluids) is one of the primary tasks of any bioprotocol. In real-life applications where several assays need to be executed for different diagnostic purposes, the same sample fluid is often required with different target concentration factors ( CF s). Although several multi-target dilution algorithms have been developed for digital microfluidic biochips, they are not efficient for implementation with continuous-flow-based microfluidic chips, which are preferred in the laboratories. In this article, we present a multi-target dilution algorithm ( MTDA ) for continuous-flow-based microfluidic biochips, which to the best of our knowledge is the first of its kind. We design a flow-based rotary mixer with a suitable number of segments depending on the target- CF profile, error tolerance, and optimization criteria. To schedule several intermediate fluid-mixing tasks, we develop a multi-target scheduling algorithm ( MTSA ) aiming to minimize the usage of storage units while producing dilutions with multiple CF s. Furthermore, we propose a storage architecture for efficiently loading (storing) of intermediate fluids from (to) the storage units.

In this article, we consider the problem of droplet routing for Microelectrode-Dot-Array (MEDA) biochips. MEDA biochips today provide a host of useful features for droplet movement by making it possible to manoeuvre droplets at a much finer granularity and with significantly increased flexibility. More precisely, MEDA biochips support more degrees of freedom in navigation and volumetric manipulation such as diagonal movement, droplet reshaping, and fractional-level split-and-merge. This helps improve routing of droplets on microfluidic grids—in particular, when the space available on the grid is limited or blocked by obstacles. In this work, we discuss how these improved capabilities can be utilized in the realization of the desired routes on those biochips. To this end, we introduce a routing method that utilizes satisfiability solvers and guarantees the generation of optimal solutions, considering the set of MEDA operations we model. This significantly improves the state of the art, since previously proposed solutions either (1) relied on heuristics and, hence, were not able to guarantee the optimum or (2) only considered a subset of the MEDA features. The solution proposed in this work includes a formulation of all MEDA features, which, as illustrated by examples, allows for the determination of routing solutions with smaller completion times. Experimental evaluations confirm these findings.

Sample preparation, an essential preprocessing step for biochemical protocols, is concerned with the generation of fluids satisfying specific target ratios and error-tolerance. Recent micro-electrode-dot-array (MEDA)-based DMF biochips provide the advantage of supporting both discrete and dynamic mixing models, the power of which has not yet been fully harnessed for implementing on-chip dilution and mixing of fluids. In this paper, we propose a novel factorization-based algorithm called FacDA for efficient and accurate dilution of sample fluid on a MEDA chip. Simulation results reveal that over a large number of test-cases with the mixing volume constraint in the range of 4--10 units, FacDA requires around 38% fewer mixing steps, 52% less sample units, and generates approximately 23% less wastage, all on average, compared to two prior dilution algorithms used for MEDA chips.

Most of the Automatic Test Pattern Generation (ATPG) algorithms for digital circuits rely heavily on netlist description that comprises both network interconnect structure among logic gates and the functionality of each gate. The performance of an ATPG tool on a circuit-under-test (CUT) C is determined by the size of the test set T and its fault coverage (FC). Despite extensive research in the field of testing, the following question remains unanswered: Is the structure or the functionality of C dominant in determining FC of a test-set T for C? In this paper, we present empirical evidence in favour of the dominance of structure on FC by randomly selecting a logic gate from a synthesized netlist for C, and replacing it by a different type of gate. Our experiments provide an un-intuitive result that F C of a test-set T for C under the single stuck-at fault model remains nearly the same on other sibling circuits that have identical structure as of C but with different gate functionality, provided these have similar extent of fault redundancy. This observation supports the view that feeding structural information alone may suffice to train machine-learning models that are currently being used to expedite different problems of digital circuit testing and diagnosis.

Recent advances in microfluidic technology offer efficient platforms to emulate complex molecular networks of biological pathways (biocircuits) on a lab-on-chip. The behavior of biocircuits is governed by a number of gene-regulatory parameters. A fundamental challenge in synthesizing and verifying biocircuits is the lack of design tools that implement biocircuit-regulatory scanning (BRS) assays to explore the large parameter-space efficiently, while optimizing synthesis time and reagent cost. In this paper, we introduce an optimization flow named BioScan for systematic exploration of the parameter-space of a biocircuit. BioScan includes: (1) a statistical approach to determine a subset of mixing ratios of reagents that span the entire parameter space as densely as possible under cost constraints; (2) an ILP-based synthesis method that implements a BRS-assay on a micro-electrode dot-array biochip. Simulation results show that BioScan reduces reagent cost and enhances space-filling properties.

Digital microfluidic biochips (DMFBs) are now being extensively used to automate several biochemical laboratory protocols such as clinical analysis, point-of-care diagnostics, or DNA sequencing. In many biological assays, e.g., bacterial susceptibility tests and cellular response analysis, samples, or reagents are required in multiple concentration (or dilution) factors, satisfying certain gradient patterns such as linear, exponential, or parabolic. Dilution gradients are traditionally prepared using continuous-flow microfluidic devices. Unfortunately, most of them suffer from inflexibility and nonprogrammability, and they require large volumes of costly stock-solutions. DMFBs, on the other hand, are shown to produce, more efficiently, samples with multiple dilution factors. However, none of the existing DMFB-based algorithms utilize the properties of the gradient-profile while optimizing reactant-cost and sample-preparation time. In this paper, we explore the underlying combinatorial attributes of different gradients and harnessed them for efficient production of the desired concentration profile. For linear gradients, we present theoretical results concerning the number of mix-split operations and waste production, and prove an upper bound on on-chip storage requirement. A cost-effective method for generating a wide class of exponential gradients is also proposed. Finally, in order to handle a complex-shaped gradient, we posit a digital-geometric technique to approximate it with a sequence of linear gradients. Experimental results on various gradient-profiles are presented in support of the proposed method.

Sample preparation is a fundamental preprocessing step needed in almost all biochemical assays and is conveniently automated on a microfluidic lab-on-chip. In digital microfluidics, it is accomplished by a sequence of droplet-mix-split steps on a biochip. Many real-life applications require a sample with multiple concentration factors (CFs). Existing algorithms, while producing multi-CF targets, attempt to share the mix-split steps in order to reduce reactant-cost and sample-preparation time. However, all prior approaches have two limitations: 1) sharing of intermediate droplets can be best effected only when all required target CFs are known a priori and 2) the processing time may vary depending on the allowable error-tolerance in target-CFs. In this paper, we present a cost-effective solution to multi-CF-dilution on-demand, by using only one (or two) mix-split step(s). In order to service dynamically arriving requests of multiple CFs quickly, we prepare dilutions of the sample with a few CFs in advance (called source-CFs), and fill on-chip reservoirs with these fluids. For minimizing the number of such preprocessed CFs, we present an integer linear programming-based method, an approximation algorithm, and a heuristic algorithm. The proposed methods also allow the users to tradeoff the number of on-chip reservoirs against service time for various applications. Simulation results for several target sets demonstrate the superiority of the proposed techniques over prior art in terms of the number of mix-split steps, waste droplets, and reactant usage when the on-chip reservoirs are preloaded with source-CFs using a customized droplet-streaming engine.

Microfluidic chips are now being increasingly used for fast and cost-effective implementation of biochemical protocols. Sample preparation involves dilution and mixing of fluids in certain ratios, which are needed for most of the protocols. On a digital microfluidic biochip (DMFB), these tasks are usually automated as a sequence of droplet mix-split steps. In the most widely used (1:1) mix-split operation for DMFBs, two equal-volume droplets are mixed followed by a split operation, which, ideally, should produce two daughter-droplets of equal volume (balanced splitting). However, because of uncertain variabilities in fluidic operations, the outcome of droplet-split operations often becomes erroneous, i.e., they may cause unbalanced splitting. As a result, the concentration factor (CF) of each constituent fluid in the mixture may become erroneous during sample preparation. All traditional approaches aimed to recover from such errors deploy on-chip sensors to detect possible volumetric imbalance, and adopt either checkpointing-based rollback or roll-forward techniques. Most of them suffer from significant overhead in terms of assay-completion time, reactant-cost, and uncertainties in termination due to randomly occurring split-errors. In this paper, we propose a new approach to accurate dilution preparation on a DMFB that is oblivious to volumetric split-errors. It does not need any sensor and can handle multiple split-errors, deterministically. The proposed method is customized for each target-CF based on the criticality of split-errors in each mix-split step. Simulation experiments on various test-cases demonstrate the effectiveness of the proposed method.

Digital circuits are often prone to suffer from uncertain timing, inadequate sensor feedback, limited controllability of past states or inability of initializing memory-banks, and erroneous behavior of analog-to-digital converters, which may produce an unknown (${X}$) logic value at various circuit nodes. Additionally, many design bugs that are identified during the post-silicon validation phase manifest themselves as${X}$-values. The presence of such${X}$-sources on certain primary or secondary inputs of a logic circuit may cause loss of fault-coverage of a test set, which, in turn, may impact its reliability and robustness. In this paper, we provide a mechanism for predicting the sensitivity of${X}$-sources in terms of loss of fault-coverage, on the basis of learning only a few structural features of the circuit that are easy to extract from the netlist. We show that the${X}$-sources can be graded satisfactorily according to their sensitivity using support vector regression, thereby obviating the need for costly explicit simulation. Experimental results on several benchmark circuits demonstrate the efficacy, speed, and accuracy of prediction.

High--performance multiprocessor SoCs used in practice require a complex network-on-chip (NoC) as communication architecture, and the channels therein often suffer from various manufacturing defects. Such physical defects cause a multitude of system-level failures and subsequent degradation of reliability, yield, and performance of the computing platform. Most of the existing test approaches consider mesh-based NoC channels only and do not perform well for other regular topologies such as octagons or spidergons, with regard to test time and overhead issues. This article proposes a topology-agnostic test mechanism that is capable of diagnosing on-line, coexistent channel-short, and stuck-at faults in these special NoCs as well as in traditional mesh architectures. We introduce a new test model called Damaru to decompose the network and present an efficient scheduling scheme to reduce test time without compromising resource utilization during testing. Additionally, the proposed scheduling scheme scales well with network size, channel width, and topological diversity. Simulation results show that the method achieves nearly 92% fault coverage and improves area overhead by almost 60% and test time by 98% compared to earlier approaches. As a sequel, packet latency and energy consumption are also improved by 67.05% and 54.69%, respectively, and they are further improved with increasing network size.

Active-Matrix (AM) technology is currently being used to implement a superior class of EWOD-based biochips, which consist of a dense 2D-array of microelectrodes. These chips offer many advantages over conventional biochips such as the capability of handling variable-size droplets, more flexibility in droplet movement, precise control over droplet navigation, and as a sequel, ease of implementing complex bioprotocols on-chip. However, the new technology poses a number of challenges concerning droplet routing. In order to enhance routability, we propose, in this paper, a multi-level hierarchical approach that takes appropriate decisions on droplet splitting and reshaping. Compared to the most recent routing methods used for EWOD, the proposed multi-level router reduces maximum latest-arrivaltime by an average 18% and achieves 7% less average latest-arrival-time.

Recent advances in microfluidics have been the major driving force behind the ubiquity of Labs-on-Chip (LoC) in biochemical protocol automation. The preparation of dilutions and mixtures of fluids is a basic step in sample preparation for which several algorithms and chip-architectures are well known. Dilution and mixing are implemented on biochips through a sequence of basic fluid-mixing and splitting operations performed in certain ratios. These steps are abstracted using a mixing graph. During this process, on-chip storage-units are needed to store intermediate fluids to be used later in the sequence. This allows to optimize the reactant-costs, to reduce the sample-preparation time, and/or to achieve the desired ratio. However, the number of storage-units is usually limited in given LoC architectures. Since this restriction is not considered by existing methods for sample preparation, the results that are obtained are often found to be useless (in the case when more storage-units are required than available) or more expensive than necessary (in the case when storage-units are available but not used, e.g., to further reduce the number of mixing operations or reactant-cost). In this paper, we present a storage-aware algorithm for sample preparation with flow-based LoCs which addresses these issues. We present a SAT-based approach to construct a mixing graph that enables the best usage of available storage-units while optimizing sample-preparation cost and/or time. Experimental results on several test cases reveal the scope, effectiveness, and the flexibility of the proposed method.

Microfluidic technology offers vast promise for implementing biochemistry-on-chip with diverse applications to clinical diagnosis, genome analysis, drug design, and point-of-care testing. Among various types of fluid-chips, droplet-based digital microfluidic biochips (DMFBs), which consist of a patterned array of controllable electrodes, provide the advantage of programmability, ease of fluidic operations, and versatile droplet mobility. However, because of manufacturing or field defects, electrode degradation, or dielectric breakdown, these chips may suffer from incorrect fluidic behavior. Reliability of fluidic operations is of utmost concern in DMFBs that are used to perform safety-critical bio-protocols. Various methods are deployed to test these devices, either offline or being overlapped with bioassay operations (termed as concurrent or in-field testing). The main challenge of in-field testing lies in the fact that the test must run concurrently with the execution of the normal assay without hampering the correctness of the latter. In prior work, optimal testing for droplet mobility over all electrodes was formulated in terms of finding either a Hamiltonian path or a Eulerian path in an undirected graph that represents the electrode-adjacency structure. Although these models have been studied for offline testing, no such effort was made in the area of concurrent testing. In this work, we propose, for in-field application, an SAT-based modeling and solution approach to find an optimal test plan that can be used to check droplet movement across the boundary between every pair of adjacent electrodes, which is visited by the droplets of the ongoing assay. The proposed method is robust and determines a test solution successfully regardless of the cover assay that is being executed concurrently. Experiments on several real-life assays and other test cases demonstrate the effectiveness of the method with respect to test completion time.

In the area of biomedical engineering, digital-microfluidic biochips (DMFBs) have received considerable attention because of their capability of providing an efficient and reliable platform for conducting point-of-care clinical diagnostics. System reliability, in turn, mandates error-recoverability while implementing biochemical assays on-chip for medical applications. Unfortunately, the technology of DMFBs is not yet fully equipped to handle error-recovery from various microfluidic operations involving droplet motion and reaction. Recently, a number of cyber-physical systems have been proposed to provide real-time checking and error-recovery in assays based on the feedback received from a few on-chip checkpoints. However, to synthesize robust feedback systems for different types of DMFBs, certain practical issues need to be considered such as co-optimization of checkpoint placement, error-recoverability, and layout of droplet-routing pathways. For application-specific DMFBs, we propose here an algorithm that minimizes the number of checkpoints and determines their locations to cover every path in a given droplet-routing solution. Next, for general-purpose DMFBs, where the checkpoints are pre-deployed in specific locations, we present a checkpoint-aware routing algorithm such that every droplet-routing path passes through at least one checkpoint to enable error-recovery and to ensure physical routability of all droplets. Furthermore, we also propose strategies for executing the algorithms in reliable mode to enhance error-recoverability. The proposed methods thus provide reliability-hardening mechanisms for a wide class of cyber-physical DMFBs.

Sample preparation plays a crucial role in almost all biochemical applications, since a predominant portion of biochemical analysis time is associated with sample collection, transportation, and preparation. Many sample-preparation algorithms are proposed in the literature that are suitable for execution on programmable digital microfluidic (DMF) platforms. In most of the existing DMF-based sample-preparation algorithms, a fixed target ratio is provided as input, and the corresponding mixing tree is generated as output. However, in many biochemical applications, target mixtures with exact component proportions may not be needed. From a biochemical perspective, it may be sufficient to prepare a mixture in which the input reagents may lie within a range of concentration factors. The choice of a particular valid ratio, however, strongly impacts solution-preparation cost and time. To address this problem, we propose a concentration-resilient ratio-selection method from the input ratio space so that the reactant cost is minimized. We propose an integer linear programming--based method that terminates very fast while producing the optimum solution, considering both uniform and weighted cost of reagents. Experimental results reveal that the proposed method can be used conveniently in tandem with several existing sample-preparation algorithms for improving their performance.

The active matrix (AM)-based architecture offers many advantages over conventional digital electrowetting-on-dielectric (EWOD) microfluidic biochips, such as the capability of handling variable-size droplets, more flexible droplet movement, and precise control over droplet navigation. However, a major challenge in choosing the routing paths is to decide when the droplets are to be reshaped depending on the congestion of the intended path, or split- and route sub droplets,and merging them at their respective destinations. As the number of microelectrodes in AM-EWOD chips is large, the path selection problem becomes further complicated. In this article, we propose a negotiation-guided flow based on routing of subdroplets that obviates the explicit need for deciding when the droplets are to be manipulated, yet fully utilizing the power of droplet reshaping, splitting, and merging them to facilitate their journey. The proposed algorithm reduces routing cost and provides more freedom in deadlock avoidance in the presence of multiple routing tasks by assigning certain congestion penalty for sibling subdroplets and fluidic penalty for heterogeneous droplets. Compared to existing techniques, it reduces latest arrival time by an average of 29% for several benchmark and random test suites. Furthermore, our method is observed to provide 100% routability of nets for all test cases, whereas existing and baseline routers fail to produce feasible solutions in many instances. We also propose a reliable mode droplet routing strategy where the number of unreliable splitting operations can be reduced by paying a small penalty on latest arrival time.

Recent studies in algorithmic microfluidics have led to the development of several techniques for automated solution preparation using droplet-based digital microfluidic (DMF) biochips. A major challenge in this direction is to produce a mixture of several reactants with a desired ratio while optimizing reactant cost and preparation time. The sequence of mix-split operations that are to be performed on the droplets is usually represented as a mixing tree (or graph). In this article, we present an efficient mixing algorithm, namely, Mixing Tree with Common Subtrees ( MTCS ), for preparing single-target mixtures. MTCS attempts to best utilize intermediate droplets, which were otherwise wasted, and uses morphing based on permutation of leaf nodes to further reduce the graph size. The technique can be generalized to produce multitarget ratios, and we present another algorithm, namely, Multiple Target Ratios ( MTR ). Additionally, in order to enhance the output load, we also propose an algorithm for droplet streaming called Multitarget Multidemand ( MTMD ). Simulation results on a large set of target ratios show that MTCS can reduce the mean values of the total number of mix-split steps ( T ms ) and waste droplets ( W ) by 16% and 29% over Min-Mix (Thies et al. 2008) and by 22% and 34% over RMA (Roy et al. 2015), respectively. Experimental results also suggest that MTR can reduce the average values of T ms and W by 23% and 44% over the repeated version of Min-Mix , by 30% and 49% over the repeated version of RMA , and by 9% and 22% over the repeated-version of MTCS , respectively. It is observed that MTMD can reduce the mean values of T ms and W by 64% and 85%, respectively, over MTR . Thus, the proposed multitarget techniques MTR and MTMD provide efficient solutions to multidemand, multitarget mixture preparationon a DMF platform.

In recent years, digital microfluidic biochips are being dominantly used for implementing a wide range of biochemical laboratory protocols (bioprotocols) on hand-held devices. Accurate preparation of fluid-samples is a fundamental preprocessing step that is needed in many bioprotocols. Oftentimes, the number of reservoirs built on-chip may be far less than that of the reactant fluids to be mixed. Hence, during the execution of an assay, several fluids are to be unloaded from the reservoirs to make room for loading new fluids stored off-line. Such unload-wash-load steps (switching) may be required several times, and these steps, being manual, significantly impact assay-completion time. In this paper, we propose a new scheduling scheme namely Reservoir and Mixer constrained Scheduling (RMS) that can schedule a mixing tree obtained by a mixing algorithm, while minimizing the number of switching such that the total completion time can be minimized. Simulation results over a large number of target ratios show that given the mixing trees obtained by standard mixing algorithms such as MinMix/RMA/CoDOS, RMS reduces switching steps (on average by 40.3%/41.9%/33%) at the cost of increasing mixing time (by only 3.5%/6.2%/4.8%), compared to an existing scheduling scheme invoked with reservoir constraints.

In the area of biomedical engineering, digital-microfluidic biochips (DMFBs) have received considerable attention, because of their capability of providing an efficient and reliable platform for conducting point-of-care clinical diagnostics. System reliability, in turn, mandates error-recoverability while implementing biochemical assays on-chip for medical applications. Unfortunately, the technology of DMFBs is not yet fully equipped to handle error-recovery from various microfluidic operations involving droplet motion and reaction. Recently, a number of cyber-physical systems have been proposed to provide real-time checking and error-recovery in assays based on the feedback received from a few on-chip checkpoints. However, in order to synthesize robust feedback systems for different types of DMFBs, certain practical issues need to be considered such as co-optimization of checkpoint placement and layout of droplet-routing pathways. For application-specific DMFBs, we propose here an algorithm that minimizes the number of checkpoints and determines their locations to cover every path in a given droplet-routing solution. Next, for general-purpose DMFBs, where the checkpoints are pre-deployed in specific locations, we present a checkpoint-aware routing algorithm such that every droplet-routing path passes through at least one checkpoint to enable error-recovery and to ensure physical routability of all droplets. Our experiments on assay benchmarks show encouraging results in terms of latest-arrival-time and routability of droplets. The proposed methods thus provide convenient reliability-hardening mechanisms for a wide class of cyber-physical DMFBs.

Fully Programmable Valve Array (FPVA) has emerged as a new architecture for the next-generation flow-based microfluidic biochips. This 2D-array consists of regularly-arranged valves, which can be dynamically configured by users to realize microfluidic devices of different shapes and sizes as well as interconnections. Additionally, the regularity of the underlying structure renders FPVAs easier to integrate on a tiny chip. However, these arrays may suffer from various manufacturing defects such as blockage and leakage in control and flow channels. Unfortunately, no efficient method is yet known for testing such a general-purpose architecture. In this paper, we present a novel formulation using the concept of flow paths and cut-sets, and describe an ILP-based hierarchical strategy for generating compact test sets that can detect multiple faults in FPVAs. Simulation results demonstrate the efficacy of the proposed method in detecting manufacturing faults with only a small number of test vectors.

Advances in digital microfluidic (DMF) technologies offer a promising platform for a variety of biochemical applications, ranging from massively parallel DNA analysis and computational drug discovery to toxicity monitoring and medical diagnosis. In this paper, we address the migration problem that arises when the technology undergoes a change in the context of DMFs. Given a biochemical reaction synthesized for actuation on a given DMF architecture, we discuss how the same biochemical reaction can be ported seamlessly to an enhanced architecture, with possible modifications to the architectural parameters (e.g., clock frequency, mixer size, and mixing time) or geometric changes (e.g., change in reservoir locations or mixer positions, inclusion of new sensors or other physical resources). Complete resynthesis of the protocol for the new architecture may often become either inefficient or even infeasible due to scalability, proprietary, security, or cost issues. We propose an adaptation method for handling such technology-changes by modifying the existing actuation sequence through an incremental procedure. The foundation of our method lies in symbolic encoding and satisfiability-solvers, enriched with pertinent graph-theoretic and geometric techniques. This enables us to generate functionally correct solutions for the new target architecture without necessitating a complete resynthesis step, thereby enabling the utilization of these chips by users in biology who are not familiar with the on-chip synthesis tool-flow. We highlight the benefits of the proposed approach through extensive simulations on assay benchmarks.

Albeit sample preparation is well-studied for digital microfluidic biochips, very few prior work addressed this problem in the context of continuous-flow microfluidics from an algorithmic perspective. In the latter class of chips, microvalves and micropumps are used to manipulate on-chip fluid flow through microchannels in order to execute a biochemical protocol. Dilution of a sample fluid is a special case of sample preparation, where only two input reagents (commonly known as sample and buffer) are mixed in a desired volumetric ratio. In this paper, we propose a satisfiability-based dilution algorithm assuming the generalized mixing models supported by an N-segment, continuous-flow, rotary mixer. Given a target concentration and an error limit, the proposed algorithm first minimizes the number of mixing operations, and subsequently, reduces reagent-usage. Simulation results demonstrate that the proposed method outperforms existing dilution algorithms in terms of mixing steps (assay time) and waste production, and compares favorably with respect to reagent-usage (cost) when 4- and 8-segment rotary mixers are used. Next, we propose two variants of an algorithm for handling the open problem of k-reagent mixture-preparation (k ≥ 3) with an N-segment continuous-flow rotary mixer, and report experimental results to evaluate their performance. A software tool called flow-based sample preparation algorithm has also been developed that can be readily used for running the proposed algorithms.

Although the modern automatic test pattern generation (ATPG) tools can efficiently produce near-optimal test sets with high fault-coverage for a circuit-under-test, a diagnostic test set (DTS), which is needed for fault localization, is much more challenging to construct. The DTS is used to analyze the responses of failing chips during manufacturing test for the purpose of identifying the root cause of observed errors. In this paper, a novel technique for selecting a powerful DTS for stuck-at faults from a pool of ATPG detection vectors is proposed. Unlike existing methods, this technique does not use any diagnostic test generation, circuit modification, or miter-based approach. It constructs a combinatorial cover of the pool to determine a test set with high diagnostic coverage (DC). Two variants of the covering algorithm are proposed based on this technique. The experimental results on several combinational and scan-based benchmark circuits demonstrate the effectiveness of our method in terms of the size of the DTS, DC, and CPU time.

In many biochemical protocols, a mixture of several fluids in a certain ratio is repeatedly required, and hence a sufficient quantity of the mixture must be supplied for on-chip bioassay completion. For example, in polymerase chain reaction (PCR) a premixed and ready-to-use solution, called PCR master mix containing different fluids at optimal concentrations, is used for efficient amplification of DNA templates by PCR. Existing scheduling scheme, namely SRS (storage reduced scheduling), finds a trade-off between time of completion and storage unit requirement depending on the demand while designing a mixing engine using the (1 : 1) mixing model on a digital microfluidic (DMF) biochip. In this paper, we present a scheduling scheme, namely KMS, for optimizing time and storage requirements in multiple-demand mixture preparation using a DMF rotary mixer. The scheduling scheme has been combined with all existing mixing algorithms, namely MinMix, RMA, MTCS and CoDOS to analyze its performance. Simulation results show significant reduction in latency (75%) and storage (48%) requirements by KMS compared with SRS for multiple-demand mixture preparation.

In an on-chip network (NoC), the channels often experience several open faults because of certain manufacturing or in-field defects. Such faults may cause enormous loss of packets degrading the reliability and performance of the system. A reliability-aware NoC should include a module that has the capability of detecting and locating an open fault in the channels so as to enable alternative routing paths and to prevent excessive packet loss. This paper proposes an on-line test scheme that detects open faults and locates the faulty channel-wires in an NoC. The proposed scheme makes use of diagonal-driven test strategy and scales well when the size of the NoC increases. We evaluate the performance of an NoC under large-traffic scenario and our simulation results establish the effectiveness of the proposed scheme in terms of several network-metrics.

The presence of open-faults in NoC channels drastically drops packets while routing them causing severe degradation of network performance. Nevertheless, it can still be compensated by utilizing a fault-repairing scheme. This paper shows how the performance of a NoC architecture can be improved through self-repairing of open channels using short-defects. Simulation results reveal that the performance degrades to nearly 30% when the channels suffer from manufacturing open-faults, and to 10% when they are self-repaired with the help of co-existent short-defects. Thus, the overall performance can be improved beyond 65%.

With the ever-shrinking global geometries on a die and the concomitant rise in the complexity of interconnections in an on-chip network (NoC), the links used therein often suffer from various manufacturing defects such as shorts. These defects not only cause logical or functional errors but also give rise to various other system level failures such as duplication, misrouting, or dropping of a packet, thereby impacting the performance of the network significantly. This paper proposes an on-line test method that detects the presence of pairwise-shorts, if any, and identifies the faulty links. Several performance metrics are evaluated to demonstrate the impact of these faults, and simulation results demonstrate 100% coverage. The proposed method scales well to large-size NoCs irrespective of the topology and link-width.

This paper presents a distributed on-line test mechanism that detects stuck-at faults (SAFs) in the channels as well as identifies the faulty channel-wires in an on-chip network (NoC). The proposed test mechanism improves yield and reliability of NoCs at the cost of few test clocks and small performance degradation. Additionally, the mechanism is scalable to large-scale NoCs. We study the impact of channel stuck-at faults on various performance metrics and simulation results establish 100% coverage metrics and the effectiveness of the proposed test mechanism.

While 3D chips open up versatile potentialities in compact system design, they pose the challenge of testing the composite system, which consists of multiple cores, logic, and memory, interconnected across different layers of the chip. The test strategy for such chips must also take into account the issues of inherent power and thermal constraints, design of test-access mechanism (TAM), and the decision concerning pre-bond and post-bond test choices. Additionally, for post-bond testing, the constraints imposed by the limited use of TSVs, worsen the controllability and observability of the cores that are accessed through the inter-layer scan-paths. Thus, while designing the TAM architecture, the optimization of overall test time under the constraints of power and TSV-count, is needed. This paper presents a new technique for test-time reduction in post-bond core-based 3D-SOCs, considering certain constraints on test power and TAM width (i.e., bounds on TSVs). The proposed algorithm runs much faster compared to prior art, and our results on several ITC02 benchmarks reveal significant reduction in test-time for most of the cases.

In this article, we introduce a novel method of synthesizing symmetric Boolean functions with reversible logic gates. In contrast to earlier approaches, the proposed technique deploys a simple, regular, and cascaded structure consisting of an array of Peres and CNOT gates, which results in significant reduction with respect to the quantum cost. However, the number of circuit inputs may increase slightly when such cascades are used. In order to reduce their number, we next propose a postsynthesis optimization phase that allows judicious reuse of circuit lines. In addition to offering a cost-effective synthesis methodology, the proposed reversible logic structure supports elegant testability properties. With respect to all single or partial missing gate faults (SMGFs and PMGFs), or repeated gate faults (RGFs) in such an n -input circuit module, we show that it admits a universal test set of constant cardinality (=3) for any value of n . Thus, considering both the cost and testability issues, this approach provides a superior option for synthesizing symmetric functions compared to existing designs.

Advances in flow-based microfluidics now allow an efficient implementation of biochemistry on-a-chip for DNA sequencing, drug discovery, and point-of-care disease diagnosis. However, the adoption of flow-based biochips is hampered by defects that frequently occur in chips fabricated using soft lithography techniques. Recently published work has shown how we can automate the testing of flow-based biochips; diagnosis methods are now needed to identify the flaws in the fabrication process and to facilitate the use of partially defective chips. Since disposable biochips are being targeted for a highly competitive and low-cost market segment, such diagnosis methods need to be inexpensive, quick, and effective. In this paper, we present the first approach for the automated diagnosis of leakage and blockage defects in flow-based microfluidic biochips. The proposed method targets the identification of fault types and their locations based on test outcomes. It reduces the number of possible fault sites significantly while identifying their exact locations. We use a graph representation of flow paths and a formulation based on hitting sets for the analysis of observed error syndromes. The diagnosis technique is evaluated on three fabricated biochips, and the localization of faults and their classification are achieved correctly in all cases.

At-speed testing of deep-submicrometer or nano-scale integrated circuits (ICs) consumes excessive power and creates hotspots and temperature gradient in the chip-under-test. The problem worsens for 3-D ICs, where heat dissipation across layers is more unbalanced. These hotspots in a circuit often cause severe degradation of performance and reliability, as a rise in temperature can introduce an extra delay along paths. As a result, the delay of an otherwise fault-free path may exceed the functional clock period. Such thermal emergencies can thus lead to over-detection and undue yield loss during testing. Their effects will be more severe for small-delay defects (SDDs), which target to sensitize the long paths in a circuit. In this paper, we quantify, for the first time, the impact of thermal emergencies on SDDs and provide a solution to mitigate them. The proposed method is based on: 1) a new thermal-aware (TA) path-selection method, 2) a TA test-ordering method, and 3) an effective scan architecture and a test-application scheme. Experimental results on benchmarks demonstrate that the new method can significantly reduce the number of over-detections of SDDs.

Digital (droplet-based) microfluidic technology offers an attractive platform for implementing a wide variety of biochemical laboratory protocols, such as point-of-care diagnosis, DNA analysis, target detection, and drug discovery. A digital microfluidic biochip consists of a patterned array of electrodes on which tiny fluid droplets are manipulated by electrical actuation sequences to perform various fluidic operations, for example, dispense, transport, mix, or split. However, because of the inherent uncertainty of fluidic operations, the outcome of biochemical experiments performed on-chip can be erroneous even if the chip is tested a priori and deemed to be defect-free. In this article, we address an important error recoverability problem in the context of sample preparation. We assume a cyberphysical environment, in which the physical errors, when detected online at selected checkpoints with integrated sensors, can be corrected through recovery techniques. However, almost all prior work on error recoverability used checkpointing-based rollback approach, that is, re-execution of certain portions of the protocol starting from the previous checkpoint. Unfortunately, such techniques are expensive both in terms of assay completion time and reagent cost, and can never ensure full error-recovery in deterministic sense. We consider imprecise droplet mix-split operations and present a novel roll-forward approach where the erroneous droplets, thus produced, are used in the error-recovery process, instead of being discarded or remixed. All erroneous droplets participate in the dilution process and they mutually cancel or reduce the concentration-error when the target droplet is reached. We also present a rigorous analysis that reveals the role of volumetric-error on the concentration of a sample to be prepared, and we describe the layout of a lab-on-chip that can execute the proposed cyberphysical dilution algorithm. Our analysis reveals that fluidic errors caused by unbalanced droplet splitting can be classified as being either critical or non-critical , and only those of the former type require correction to achieve error-free sample dilution. Simulation experiments on various sample preparation test cases demonstrate the effectiveness of the proposed method.

The emerging technology of reversible circuits offers a potential solution to the synthesis of ultra low-power quantum computing systems. A reversible circuit can be envisaged as a cascade of reversible gates only, such as Toffoli gate, which has two components: k control bits and a target bit (k-CNOT), k ⩾ 1. While analyzing testability issues in a reversible circuit, the missing-gate fault model is often used for modeling physical defects in quantum k-CNOT gates. In this paper, we propose a new design-for-testability (DFT) technique for quantum reversible circuits that deploys bit-swapping using Fredkin gates. It is shown that in an (n x n) circuit implemented with k-CNOT gates, addition of only two extra inputs along with a few Fredkin gates yields easy testability in the circuit. The modified design admits a universal test set of size (n + k + 2) that detects all detectable missing gate faults in the original circuit, where k is the maximum number of controls used among all k-CNOT gates. The DFT overhead in terms of quantum cost is also much less compared to previous approaches.

Advances in flow-based microfluidics allow biochemistry-on-a-chip for DNA sequencing, drug discovery, and point-of-care disease diagnosis. However, the adoption of flow-based biochips is hampered by defects that frequently occur in chips fabricated using soft lithography techniques. Fault diagnosis methods are now needed to improve fabrication processes and facilitate the (partial) use of chips that have defects. We present the first approach for the automated diagnosis of flow-based microfluidic biochips. The proposed method facilitates the identification of defects through syndrome analysis and a hitting-set problem formulation. The proposed technique is evaluated using three fabricated biochips, and exact defect localization and identification of the defect type is achieved in all cases.

Granular object segmentation is an important area of image processing, which has several practical applications in agriculture, food industry, geology, and forensics. In this paper, we present a simple algorithm for the analysis of granulometric images that consist of touching or overlapping convex objects such as coffee bean, food grain, nuts, blood cell, or cookies. The algorithm is based on certain underlying digital-geometric features embedded in their binary snapshots. The concept of an outer isothetic cover and the property of geometric convexity are used to extract the joining points (or concavity points) from the ensemble of objects. Next, a combinatorial technique is employed to determine the separator of two overlapping or neighboring objects. This technique is fully automated and it needs only integer-domain computation. The termination time of the algorithm can be traded-off with the quality of segmentation by changing the resolution parameter. Experimental results for a variety of objects chosen from different application domains such as cell image, coffee-bean image and others demonstrate the efficiency and robustness of the proposed method compared to earlier watershed-based algorithms.

The amount of DNA strands available in a biological sample is a major limitation for many genomic bioanalyses. To amplify the traces of DNA strands, polymerase chain reaction (PCR) is widely used for conducting subsequent experiments. Compared to conventional instruments and analyzers, the execution of PCR on a digital microfluidic biochip (DMFB) can achieve short time-to-results, low reagent consumption, rapid heating/cooling rates, and high integration of multiple processing modules. However, the PCR biochip design methods in the literature are oblivious to the inherent randomness and complexity of bioanalyses, and they do not consider the interference among the neighboring devices and the cost of droplet transportation. We present an integrated design solution to optimize the complete PCR procedure, including: 1) DNA amplification and termination control; 2) resource placement that satisfies proximity constraints; and 3) droplet transportation. Based on the sensor feedback data, a statistical model is developed to optimize and control the DNA amplification sequence in real-time on a cyberphysical biochip. Next, we present a geometric algorithm for avoiding device interference and for reducing droplet routing cost. A novel optical sensing system is deployed based on the physical visibility of droplets. Simulation results for three laboratory protocols demonstrate that the proposed design method results in a compact layout and produces an execution sequence for efficient control of PCR operations on a cyberphysical DMFB.

The recent proliferation of digital microfluidic (DMF) biochips has enabled rapid on-chip implementation of many biochemical laboratory assays or protocols. Sample preprocessing, which includes dilution and mixing of reagents, plays an important role in the preparation of assays. The automation of sample preparation on a digital microfluidic platform often mandates the execution of a mixing algorithm, which determines a sequence of droplet mix-split steps (usually represented as a mixing graph). However, the overall cost and performance of on-chip mixture preparation not only depends on the mixing graph but also on the resource allocation and scheduling strategy, for instance, the placement of boundary reservoirs or dispensers, mixer modules, storage units, and physical design of droplet-routing pathways. In this article, we first present a new mixing algorithm based on a number-partitioning technique that determines a layout-aware mixing tree corresponding to a given target ratio of a number of fluids. The mixing graph produced by the proposed method can be implemented on a chip with a fewer number of crossovers among droplet-routing paths as well as with a reduced reservoir-to-mixer transportation distance. Second, we propose a routing-aware resource-allocation scheme that can be used to improve the performance of a given mixing algorithm on a chip layout. The design methodology is evaluated on various test cases to demonstrate its effectiveness in mixture preparation with the help of two representative mixing algorithms. Simulation results show that on average, the proposed scheme can reduce the number of crossovers among droplet-routing paths by 89.7% when used in conjunction with the new mixing algorithm, and by 75.4% when an earlier algorithm [Thies et al. 2008] is used.

A digital microfluidic biochip (DMB) is often deployed for multiplexing several assays in space and in time. The residue left by one assay may contaminate the droplets used for subsequent assays. Biochemical assays involving cell culture and those based on particle microfluidics also require sweeping of residual media from an active droplet on-chip. Thus, fluidic operations such as washing or residue removal need to be performed routinely either to clean contamination from the droplet pathways or to rinse off certain droplets on the chip. In this work, several graph-based techniques are presented for offline washing of biochips that may have either a regular geometry (e.g., a 2D array of electrodes), or an irregular geometry (e.g., an application-specific layout). The schemes can be used for total washing, that is, for cleaning the entire biochip or for selective washing of sites or pathways located sparsely on the chip. The problem of reducing the path length and washing time of the droplets is investigated with or without capacity constraints. The proposed algorithms for offline washing make use of several techniques such as graph traversal, integer linear programming (ILP) modeling, and customized heuristics based on the nature of the geometric distribution of the contamination profile. The contaminated pathways are assumed to be Manhattan or curved, and hence the techniques are applicable to the conventional field-actuated DMBs as well as to the emerging classes of light-actuated and active-matrix DMBs. These techniques will be useful in enhancing the reliability of a wide class of emerging digital microfluidic healthcare devices

In many biochemical protocols, such as polymerase chain reaction, a mixture of fluids in a certain ratio is repeatedly required, and hence a sufficient quantity of the mixture must be supplied for assay completion. Existing sample-preparation algorithms based on digital microfluidics (DMF) emit two target droplets in one pass, and costly multiple passes are required to sustain the emission of the mixture droplet. To alleviate this problem, we design a streaming engine on a DMF biochip, which optimizes droplet emission depending on the demand and available storage. Simulation results show significant reduction in latency and reactant usage for mixture preparation.

Microfluidic biochips are recently being advocated for on-chip implementation of several biochemical laboratory assays or protocols [1]. Such labs-on-a-chip (LoC) have brought a complete paradigm shift in DNA analysis, toxicity grading, in molecular biology, and in drug design and delivery. This technology offers a viable and low-cost platform for reducing healthcare cost of cardiovascular diseases, cancer, diabetes, for providing point-of-care (P-o-C) health services [2, 3], and for the management of bio-terrorism threats [4]. These chips are also immensely useful for rapid and accurate diagnosis of various diseases including malaria, human immunodeficiency virus infection (HIV), acquired immunodeficiency syndrome (AIDS), and for mitigating neglected tropical diseases (NTD) prevalent in the developing countries [5].

Digital microfluidic (DMF) biochips are recently being advocated for fast on-chip implementation of biochemical laboratory assays or protocols, and several algorithms for diluting and mixing of reagents have been reported. However, all methods for such automatic sample preparation suffer from a drawback that they assume the availability of input fluids in pure form, that is, each with an extreme concentration factor ( CF ) of 100%. In many real-life scenarios, the stock solutions consist of samples/reagents with multiple CF s. No algorithm is yet known for preparing a target mixture of fluids with a given ratio when its constituents are supplied with random concentrations. An intriguing question is whether or not a given target ratio is feasible to produce from such a general input condition. In this article, we first study the feasibility properties for the generalized mixing problem under the (1:1) mix-split model with an allowable error in the target CF s not exceeding 1 2d, where the integer d is user specified and denotes the desired accuracy level of CF . Next, an algorithm is proposed which produces the desired target ratio of N reagents in ONd mix-split steps, where N ( ≥ 3) denotes the number of constituent fluids in the mixture. The feasibility analysis also leads to the characterization of the total space of input stock solutions from which a given target mixture can be derived, and conversely, the space of all target ratios, which are derivable from a given set of input reagents with arbitrary CF s. Finally, we present a generalized algorithm for diluting a sample S in minimum (1:1) mix-split steps when two or more arbitrary concentrations of S (diluted with the same buffer) are supplied as inputs. These results settle several open questions in droplet-based algorithmic microfluidics and offer efficient solutions for a wider class of on-chip sample preparation problems.

In many biochemical protocols, sample preparation is an extremely important step for mixing multiple reagents in a given ratio. Dilution of a biochemical sample/reagent is the special case of mixing or solution preparation where only two fluids (sample and buffer) are mixed at a certain ratio corresponding to the desired concentration factor. Many bioassays often require multiple concentration values of the same sample/reagent, and implementing them efficiently on a digital microfluidic biochip is a challenge. In this paper, we present an algorithmic solution for the problem of producing a set of different target droplets in a minimum number of mix-split steps, and satisfying a given upper bound in concentration error. Unlike prior methods, this approach does not require any intermediate storage. We represent the underlying search space using a binary de Brujin graph and show that a shortest mix-split sequence can be obtained by solving an asymmetric traveling salesman problem therein. Simulation results over a large data set reveal that the proposed technique outperforms existing methods in terms of the number of mix-split steps, waste droplets, and reactant usage. The method is applicable in general scenarios of either one mixer or more mixers on the chip. A digital microfluidic platform can be easily designed to implement such a technique for rapid on-chip sample preparation.

Digital microfluidic biochips are recently being developed for on-chip implementation of biochemical laboratory assays. Existing mixing algorithms determine the mixing tree or mixing graph from a given target ratio of several biochemical fluids for on-chip mixture preparation. We present an algorithm to determine a reduced mixing tree by sharing the common subtrees within itself. We observe two transformations that preserve the semantics of the tree: (a) permutation of leaf nodes (input fluids/reagents) within the same level of a mixing tree, and (b) level-shifting of a leaf node to the next lower level by duplicating its appearance. The proposed algorithm utilizes both the intermediate droplets obtained after a split operation when a pair of identical subtrees are identified under permutation of leaf nodes at the same level. Simulation results for a large set of target ratios show that our algorithm reduces the mean values of the total number of mix-split steps, waste droplets and the number of mixer modules required for earliest completion by 16%, 29% and 12% over Min-Mix and by 22%, 34% and 20% over RMA, respectively. Moreover, it reduces the number of checkpoint insertions required for dynamic error recovery against incorrect mix-split steps during mixture preparation.

In this paper, we introduce a new method to realize symmetric Boolean functions with reversible logic based on unate decomposition. In contrast to earlier synthesis methods, our solution uses a simpler circuit structure of reversible gates, which enables a significant reduction with respect to quantum cost. The resulting design offers an improved solution to reversible synthesis of symmetric Boolean functions.

The amount of DNA strands available in a biological sample is a major limitation for many genomic bioanalyses. To amplify the traces of DNA strands, polymerase chain reaction (PCR) is widely used for conducting subsequent experiments. Compared to conventional instruments and analyzers, the execution of PCR on a digital microfluidic biochip (DMFB) can achieve short time-to-results, low reagent consumption, rapid heating/cooling rates, and high integration of multiple processing modules. However, the PCR biochip design methods in the literature are oblivious to the inherent randomness and complexity of bioanalyses, and they do not consider the interference among on-chip devices and the cost of droplet transportation. We present, for the first time, an integrated design method to optimize the complete PCR procedure, including (i) DNA amplification and termination control, (ii) resource placement that satisfies physical constraints needed to avoid interference, and (iii) droplet transportation needed for mixing and detection. We propose a statistical model for sensor feedback-driven (cyberphysical) on-line decision making in order to optimize and control the execution sequence for DNA amplification. Next, we present a geometric algorithm for layout design to avoid device interference and reduce the cost of droplet routing. Simulation results on three laboratory protocols demonstrate that the proposed design method results in a compact layout and produces an execution sequence for efficient control of PCR operations on a cyberphysical DMFB.

Digital microfluidic technology is being increasingly used for implementing a lab-on-a-chip with many life-critical applications. Testing of these biochips is thus indispensable not only after manufacture, but also during in-field operation. To keep the product cost (including both design and test) low for disposable biochips, efficient on-line test techniques are desirable. All previous on-line test mechanisms interleave testing and the target bioassay protocol, but they involve overhead such as use of separate test droplet(s) and increased completion time. In this paper, we propose a simple on-line error-detection methodology that can be performed concurrently with the normal operation of the system with no or little extra effort. The proposed procedure does not require any test droplet. In the case of incorrect operation, the error is detected on or before the completion of the bioassay. The main objective of the proposed strategy is to ensure the correctness of the executed assay on-chip and not to guarantee the absence of a defect in the chip. The given assay protocol is assumed to be executed correctly if the on-line procedure finishes with success. The assay is aborted as soon as an error is detected, thereby saving costly sample/reagents. Moreover, the scheme can be easily adopted to enhance diagnosis.

Digital Micro fluidic biochips have been developed as a promising platform for Lab-on-chip systems that manipulate individual droplet of chemicals on a 2D planar array of electrodes. Due to the significance of the correctness of the results -- fault tolerance and dependability becomes a major issue for operation of these devices. Therefore, such devices are required to be tested frequently both off-line (e.g., post manufacturing) and concurrently ahead of each assay execution. Under both scenarios, testing is accomplished by routing one or more test droplets across the chip simultaneously and recording their arrival at the destination. In this paper we attempted to solve the problem of customized testing for a given Bioassay layout. We have applied a look ahead strategy for parallel testing using multiple droplets for any given test bench with an objective of minimization of test completion time and optimized utilization of test resources. The test simulations are carried out on test benches of Benchmark suite III and results obtained are found to be encouraging.

Potential applications of digital microfluidic (DMF) biochips now include several areas of real-life applications like environmental monitoring, water and air pollutant detection, and food processing to name a few. In order to achieve sufficiently high throughput for these applications, several instances of the same bioassay may be required to be executed concurrently on different samples. As a straightforward implementation, several identical biochips can be integrated on a single substrate as a multichip to execute the assay for various samples concurrently. Controlling individual electrodes of such a chip by independent pins may not be acceptable since it increases the cost of fabrication. Thus, in order to keep the overall pin-count within an acceptable bound, all the respective electrodes of these individual pieces are connected internally underneath the chip so that they can be controlled with a single external control pin. In this article, we present an orientation strategy for layout of a multichip that reduces routing congestion and consequently facilitates wire routing for the electrode array. The electrode structure of the individual pieces of the multichip may be either direct-addressable or pin-constrained. The method also supports a hierarchical approach to wire routing that ensures scalability. In this scheme, the size of the biochip in terms of the total number of electrodes may be increased by a factor of four by increasing the number of routing layers by only one. In general, for a multichip with 4 n identical blocks, ( n + 1) layers are sufficient for wire routing.

We present a combined hardware-software based approach to scan-chain diagnosis, when the outcome of a test may be affected by system faults occurring in the logic out-side of the scan chain. For the hardware component we adopt the double-tree scan (DTS) chain architecture, which has previously been shown to be effective in reducing power, volume, and application time of tests for stuck-at and delay faults. We develop a version of flush test which can resolve a multiple fault in a DTS chain to a small number of suspect candidates. Further resolution to a unique multiple fault is enabled by the software component comprising of fault simulation and analysis of the response of the circuit to test patterns produced by ATPG. Experimental results on benchmark circuits show that near-perfect scan-chain diagnosis for multiple faults is possible even when a large number of random system faults are injected in the circuit.

A key challenge in design automation of digital microfluidic biochips is to carry out on-chip dilution/mixing of biochemical samples/reagents for achieving a desired concentration factor (CF). In a bioassay, reducing the waste is crucial because the waste droplet handling is cumbersome and the number of waste reservoirs on-chip needs to be minimized to use limited volume of sample and expensive reagents and hence to reduce the cost of a biochip. The existing dilution algorithms attempt to reduce the number of mix/split steps required in the process but focus little on minimization of sample requirement or waste droplets. In this work, we characterize the underlying combinatorial properties of waste generation and identify the inherent limitations of two earlier mixing algorithms (BS algorithm by Thies et al., Natural Computing 2008; DMRW algorithm by Roy et al., IEEE TCAD 2010) in addressing this issue. Based on these properties, we design an improved dilution/mixing algorithm (IDMA) that optimizes the usage of intermediate droplets generated during the dilution process, which in turn, reduces the demand of sample/reagent and production of waste. The algorithm terminates in O(n) steps for producing a target CF with a precision of 1/2n. Based on simulation results for all CF values ranging from 1/1024 to 1023/1024 using a sample (100% concentration) and a buffer solution (0% concentration), we present an integrated scheme of choosing the best waste-aware dilution algorithm among BS, DMRW, and IDMA for any given value of CF. Finally, an architectural layout of a DMF biochip that supports the proposed scheme is designed.

Multiplexing several assays in time on the same digital microfluidic biochip is often needed in several biochemical applications. Contamination may lead to undesirable mixing of the residue left by one assay with the droplets of the subsequent assay. Hence, cleaning the droplet pathways of such a biochip by wash droplets between successive assays is required. Since a wash droplet may have a finite capability of residue removal, one has to design an efficient route planning for wash droplet(s) that minimizes the washing time and/or electrode actuation. In this paper, we formulate the problem in terms of graph Eulerization and Capacitated Chinese Postman Problem. We also propose efficient solutions and report some simulation results.

The Illinois Scan Architecture (ILS) consists of several scan path segments and is useful in reducing test application time and test data volume for high density chips. In this paper, we propose a scheme of layout-aware as well as coverage-driven ILS design. The partitioning of the flip-flops into ILS segments is determined by their geometric locations, whereas the set of the flip-flops to be placed in parallel is determined by the minimum incompatibility relations among the corresponding bits of a test set, to enhance fault coverage in broadcast mode. As a result, the number of serial test patterns also reduces.

Logic synthesis of reversible circuits has received considerable attention in the light of advances recently made in quantum computation. Implementation of a reversible circuit is envisaged by deploying several special types of quantum gates, such as k-CNOT. Although the classical stuck-at fault model is widely used for testing conventional CMOS circuits, new fault models, namely single missing-gate fault (SMGF), repeated-gate fault (RGF), partial missing-gate fault (PMGF), and multiple missing-gate fault (MMGF), have been found to be more suitable for modeling defects in quantum k-CNOT gates. This article presents an efficient algorithm to derive an optimal test set (OTS) for detection of multiple missing-gate faults in a reversible circuit implemented with k-CNOT gates. It is shown that the OTS is sufficient to detect all single missing-gate faults (SMGFs) and all detectable repeated gate faults (RGFs). Experimental results on some benchmark circuits are also reported.

Digital micro fluidic technology is now being extensively used for implementing a lab-on-a-chip. Micro fluidic biochips are often used for safety-critical applications, clinical diagnosis, and for genome analysis. Thus, devising effective and faster testing methodologies to warrant correct operations of these devices after manufacture and during bioassay operations, is very much needed. In this paper, we propose a technique to obtain the route plan of a test droplet for the purpose of structural testing of biochips. The technique is applicable to fully reconfigurable arrays and application specific biochips. We propose an improved eulerization technique to implement the test plan based on a graph model of the chip. The optimal eulerization can be abstracted in terms of the classical Chinese postman problem. The Euler tour can then be identified using a cycle decomposition method, which is easy to implement. This can also be used in phase-based test planning leading to significant savings in testing time. The method provides a unified approach towards unidirectional structural testing and can be easily adapted to design an improved droplet routing procedure for bidirectional functional testing of digital micro fluidic biochips.

A novel algorithm to recognize hand-drawn graphs is proposed. The algorithm uses properties of digital-geometric straightness combined with a new idea of Farey sequence, followed by geometric refinement, in order to speed up the recognition of graph edges. In the next phase, the nodes of the graph - which, being hand-drawn, are very grossly circular - are recognized using the annular regions containing the vertices of their corresponding isothetic covers. Results of the two phases are finally compiled using interval search to output the adjacency list of the graph. The problems of jaggedness, waviness, and similar unforeseen aberrations usually present in a hand-drawn graph are well-tackled by the adopted techniques, as verified by our experimentation on various hand-drawn graphs. Some results have been given in this paper to show the usability and efficiency of the proposed algorithm.

A novel approach towards word segmentation and baseline detection in a handwritten document is proposed. It is based on certain structural properties of isothetic covers tightly enclosing the words in a handwritten document. For an appropriate grid size, the isothetic covers successfully segregates the words so that each cover corresponds to a particular word. By analyzing the horizontal chords of these covers, the corresponding baselines are extracted. The method is fast, robust, and efficient by dint of its traversal strategy along the word boundaries in a combinatorial manner and usage of limited operations strictly in the integer domain. Some results on several Bengali and English handwritings have been given to demonstrate its strength and elegance.

In this paper, we deal with the problem of partitioning a set of coplanar points of more than one colors into monochromatic cells using minimum number of axis-parallel straight lines. It is first shown that the problem is NP-hard. A fast heuristic is then presented to solve this problem. Experimental results on randomly generated instances indicate that the proposed method is much faster than the existing techniques, with minor degradation in the cost of the partition.

The recent emergence of lab-on-a-chip (LoC) technology has led to a paradigm shift in many healthcare-related application areas, e.g., point-of-care clinical diagnostics, high-throughput sequencing, and proteomics. A promising category of LoCs is digital microfluidic (DMF)-based biochips, in which nanoliter-volume fluid droplets are manipulated on a 2-D electrode array. A key challenge in designing such chips and mapping lab-bench protocols to a LoC is to carry out the dilution process of biochemical samples efficiently. As an optimization and automation technique, we present a dilution/mixing algorithm that significantly reduces the production of waste droplets. This algorithm takesO(n) time to compute at mostnsequential mix/split operations required to achieve any given target concentration with an error in concentration factor less than [1/(2n)]. To implement the algorithm, we design an architectural layout of a DMF-based LoC consisting of twoO(n)-size rotary mixers andO(n) storage electrodes. Simulation results show that the proposed technique always yields nonnegative savings in the number of waste droplets and also in the total number of input droplets compared to earlier methods.

There are several algorithms for digitization of a real disc (circle) to derive a digital disc, and also for finding the real disc corresponding to a digital disc. However, the correspondence of a digital disc with a regular polygon in the real plane is not well studied. This paper presents some theories and related experiments on setting the correspondence from a digital disc to its polygonal cover in the real plane. For an ideal regular polygon covering a digital disc, all the grid points of the digital disc should lie on and inside the polygon, and vice versa. That an ideal regular polygon corresponding to a digital disc is possible for some of the digital discs, especially for the ones having smaller radii, is shown. Further, for a disc whose ideal regular polygon is not possible, an approximate polygon, tending to the ideal one, is possible, in which the error of approximation can be controlled by the number of vertices of the approximate polygon. These (ideal or approximate) polygonal covers of digital discs have several applications in many problems of point set pattern matching. We have reported the conditions under which an ideal regular polygon always exists corresponding to a digital disc, and the conditions under which the existence of an ideal regular polygon becomes uncertain. Experimental results have been given to demonstrate the possibilities of approximation and the trade-off in terms of error versus the number of vertices in the approximate polygon.

Matching and analysis of patterns or shapes in the digital plane are of utmost importance in various problems of computer vision and pattern recognition. A digital point set is such a pattern that corresponds to an object in the digital plane. Although there exist several data structures that can be employed for Approximate Point Set Pattern Matching (APSPM) in the real domain, they require substantial modification to support algorithms in the digital domain. To bridge this gap, a novel data structure called "angular tree" is proposed, targeting an efficient and error-controllable circular range query in the digital plane. The farthest pair of points may be used as the starting correspondence between the pattern set and the background set. Several classical discrete structures and methodologies of computational geometry, as well as some topological features of circles/discs in digital geometry, have been used in tandem, for successful realization of the proposed APSPM algorithm in the digital plane. The APSPM algorithm based on the angular tree has been implemented and tested on various point sets and the reported results demonstrate the efficiency and versatility of the new data structure for supporting APSPM algorithms.

Structural testing of digital microfluidic biochips targets the detection of physical defects, but it does not guarantee robust execution of target bioassays or the integrity of assay outcomes. Functional testing is needed to detect fluidic malfunctions. Such tests ensure whether or not, the elementary fluidic operations, such as droplet transportation, mixing, incubation, and splitting are reliably executed on the microfluidic array. Routing test and mixing/splitting test are two important steps in functional testing. We present two procedures for optimal bidirectional routing test and accelerated mixing/splitting test. Compared to previous methods, these procedures need significantly fewer droplet manipulation steps and reduced execution time. The proposed method of functional testing in an N x N microfluidic array requires only a constant number of mixing/splitting steps. Further, the test outcome is free from boundary errors related to droplet size that may arise during mixing/splitting test.

Testing of bridging faults in a reversible circuit is investigated in this paper. The intra-level single bridging fault model is considered here, i.e. any single pair of lines, both lying at the same level of the circuit, may be assumed to have been logically shorted in order to model a defect. For an (n · n) reversible circuit with d levels realized with simple Toffoli gates, the time complexity of the test generation procedure is O(nd2 log2n). A test set of cardinality O(d log2n) is found to be sufficient for testing all such detectable faults. A minimal test set can also be easily derived by using the concept of test equivalence.

Several existing DSS (digital straight line segment) recognition algorithms can be used to determine the digital straightness of a given one-pixel-thick digital curve. Because of the inherent geometric constraints of digital straightness, these algorithms often produce a large number of segments to cover a given digital curve representing a real-life object=image. Thus, a curve segment, which is not exactly digitally straight, but appears to be visually straight, is fragmented into multiple DSS when these algorithms are run. In this paper, a new concept of approximate straightness is introduced by relaxing certain conditions of DSS, and an algorithm is described to extract those segments from a digital curve. The number of such segments required to cover the curve is found to be significantly fewer than that of the exact DSS-cover. As a result, the data set required for representing a curve also reduces to a large extent. The extracted set of segments can further be combined to determine a compact polygonal approximation of a digital curve based on certain approximation criteria and a specified error tolerance. The proposed algorithm involves only primitive integer operations and thus runs very fast compared to those based on exact DSS. The overall time complexity becomes linear in the number of points present in the representative set. Experimental results on several digital curves demonstrate the speed, elegance and efficacy of the proposed method.

A new combinatorial feature called Stacked Euler Vector (SERVE) is introduced to characterize a gray-tone image. SERVE comprises a four-tuple, where each element is an integer representing the Euler number of the partial binary image formed by certain pixel overlap relations among the four most significant bit planes of the gray-tone image. Computation of SERVE is simple, fast, and does not involve any floating point operation. SERVE can be used to augment other features to improve the performance of image retrieval significantly. Experimental results on the COIL database are reported to demonstrate its performance.

Tree-based scan path architectures have recently been suggested for reducing test application time or test data volume in today's high-density very large scale integrated circuits. However, these techniques strongly rely on the existence of a large number of compatible sets of flip-flops under the given test set and therefore may not be suitable for a highly compact test set generated by an efficient automatic test pattern generator tool. Tree-based architectures also suffer from loss of fault coverage while achieving a significant reduction ratio for test time or data. In this paper, to circumvent this problem, a new two-pass hybrid method is proposed to design an efficient scan tree architecture based on approximate compatibility. The method is particularly suitable for a highly compact test set having fewer don't cares and low compatibility. Finally, to reduce the volume of scan-out data, test responses shifted out from the leaf nodes of the scan tree are compacted by a space compactor, which is designed specially for the proposed scan tree architecture. The compactor uses an XOR tree, and its overhead is low. The design thus offers a solution to both test data and response compaction. Experimental results on various benchmark circuits demonstrate that the proposed algorithm outperforms the earlier methods in reducing test application time significantly without degrading fault coverage.

This article addresses the problem of recursively bipartitioning a given floorplan F using monotone staircases. At each level of the hierarchy, a monotone staircase from one corner of F to its opposite corner is identified, such that (i) the two parts of the bipartition are nearly equal in area (or in the number of blocks), and (ii) the number of nets crossing the staircase is minimal. The problem of area-balanced bipartitioning is shown to be NP-hard, and a maxflow-based heuristic is proposed. Such a hierarchy may be useful to repeater placement in deep-submicron physical design, and also to global routing.

Wire routing in a VLSI chip often requires minimization of ire-length as well as the number of intersections among multiple nets. Such an optimization problem is computationally hard for which no efficient algorithm or good heuristic is known to exist. Additionally, in a biobjective setting, the major challenge to solve a problem is to obtain representative diverse solutions across the (near-) Pareto-front.In this work, we consider the problem of constructing spanning trees of two geometric graphs corresponding to two nets, each with multiple terminals, with a goal to minimize the total edge cost and the number of intersections among the edges of the two trees. We first design simple heuristics to obtain the extreme points in the solution space, which however, could not produce diverse solutions. Search algorithms based on evolutionary multiobjective optimization (EMO) are then proposed to obtain diverse solutions in the feasible solution space. Each element of this solution set is a tuple of two spanning trees corresponding to the given geometric graphs. Empirical evidence shows that the proposed evolutionary algorithms cover a larger range and are much superior to the heuristics.

The Binary Decision Diagram (BDD) is a powerful vehicle for large-scale functional specification and circuit design. In this paper, we consider the open problem of generating in polynomial time, the exact minimum set (T) of test vectors for detecting all single stuck-at faults in such a BDD-based circuit synthesized with multiplexors. It is shown that for a single-output circuit, T = 2k, where k is the minimum number of paths that cover all the arcs of the BDD graph. The value of k, and consequently the test set T, can be readily determined by running the max-flow algorithm on a network derived from the BDD, followed by a simple graph traversal. This procedure not only generates the optimal test set in polynomial time, but also obviates the need of employing an ATPG (Automatic Test Pattern Generator) and a fault simulator. For multi-output circuits, the procedure requires slight enhancement.

Scan based testing is a powerful and popular test technique. However the scan chain can be used by an attacker to decipher the cryptogram. The present paper shows such a side-channel attack on LFSR-based stream ciphers using scan chains. The paper subsequently discusses a strategy to build the scan chains in a tree based pattern with a selfchecking compactor. It has been shown that such a structure prevents such scan based attacks but does not compromise on fault coverage.

Compact set of 3-valued test vectors for random pattern resistant faults are covered in multiple test passes. During a pass, its associated test cube specifies certain bits in the scan chain to be held fixed and others to change pseudo -randomly. We propose an algorithm to find a small number of cubes to cover all the test vectors, thus minimizing total test length. The test-cube finding algorithm repeatedly evaluates small perturbations of the current solution so as to maximize the expected test coverage of the cube. Experimental results show that our algorithm covers the test vectors by test cubes that are one to two orders of magnitude smaller in number with a much smaller increase in the percentage of specified bits. It outperforms comparable schemes reported in the literature

Efficient and successful joining of torn pieces of papers to reconstruct the original documents is an important and challenging issue in many disciplines, especially in forensics and investigation sciences. Automation of the process by means of appropriate techniques can speed up the problem solving substantially. In this paper, we propose a fast, efficient, and useful technique for the reconstruction of hand-torn pages of documents from their images, using contour descriptors for shape-based matching. Chain code of the closed digital arc representing a contour, and its Minkowski sum, have been exploited in our reconstruction work. Experimental results demonstrate the strength and robustness of the method.

A new combinatorial characterization of a gray-tone image called Euler Vector is proposed. The Euler number of a binary image is a well-known topological feature, which remains invariant under translation, rotation, scaling, and rubber-sheet transformation of the image. The Euler vector comprises a 4-tuple, where each element is an integer representing the Euler number of the partial binary image formed by the gray-code representation of the four most significant bit planes of the gray-tone image. Computation of Euler vector requires only integer and Boolean operations. The Euler vector is experimentally observed to be robust against noise and compression. For efficient image indexing, storage and retrieval from an image database using this vector, a bucket searching technique based on a simple modification of Kd-tree, is employed successfully. The Euler vector can also be used to perform an efficient four-dimensional range query. The set of retrieved images are finally ranked on the basis of Mahalanobis distance measure. Experiments are performed on the COIL database and results are reported. The retrieval success can be improved significantly by augmentiong the Euler vector by a few additional simple shape features. Since Euler vector can be computed very fast, the proposed technique is likely to find many applications to content-based image retrieval.

New techniques are presented for routing straight channels, L-channels, switchboxes, and staircase channels in a two-layer Manhattan-diagonal (MD) model with tracks in horizontal, vertical, and ± 45° directions. First, an O ( l.d ) time algorithm is presented for routing a straight channel of length l and density d with no cyclic vertical constraints . It is shown that the number of tracks h used by the algorithm for routing multiterminal nets satisfies d ≤ h ≤ ( d + 1). Second, an output-sensitive algorithm is reported that can route a channel with cyclic vertical constraints in O ( l.h ) time using h tracks, allowing overlapping of wire segments in two layers. Next, the routing problem for a multiterminal L-channel of length l and height h is solved by an O ( l.h ) time algorithm. If no cyclic vertical constraints exist, its time complexity reduces to O ( l.d ) where d is the density of the L-channel. Finally, the switchbox routing problem in the MD model is solved elegantly. These techniques, easily extendible to the routing of staircase channels, yield efficient solutions to detailed routing in general floorplans. Experimental results on benchmarks show significantly low via count and reduced wire length, thus establishing the superiority of MD routing to classical strategies. The proposed algorithms are also potentially useful for general non-Manhattan area routing and multichip modules (MCMs).

A technique for implementing totally symmetric Boolean functions using hierarchical modules is presented. First, a simple cellular module is designed for synthesizing unate symmetric functions. The structure is universal, admits a recursive design and uses only 2-input AND-OR gates. General symmetric functions are then realized following a unate decomposition method. The synthesis procedure guarantees complete and robust path-delay fault testability in the circuit. Experimental results on several symmetric functions reveal that the hardware cost of the proposed design is low, and the number of paths in the circuit is reduced significantly compared to those in earlier designs. Results on circuit area and delay for a few benchmark examples are also reported.

In a scan-based system with a large number of flip-flops, a major component of power is consumed during scan-shift and clocking operation in test mode. In this paper, a novel scan-path architecture called double-tree scan (DTS) is proposed that drastically reduces the scan-shift and clock activity during testing. The inherent combinatorial properties of double-tree structure are employed to design the scan architecture, clock gating logic, and a simple shift controller. The design is independent of the structure of the circuit-under-test (CUT) or its test set. It provides a significant reduction both in instantaneous and average power needed for clocking and scan-shifting. The architecture fits well to built-in self-test (BIST) scheme under random testing, as well as to deterministic test environment.

A structure-independent method for space compaction in combinational circuits based on a new generic scheme is presented. It is shown that a single-output compactor can always be designed for compressing test responses of a circuit-under-test (CUT) with guaranteed zero-aliasing. Test responses from multiple outputs are compacted to a single periodic data stream. The compactor is independent of the fault model and can be designed only from the knowledge of the given test set and the corresponding fault-free responses. An additional response logic and a special code checker are used to design the compactor. The same test set given for the CUT also detects all multiple stuck-at faults in the response logic and almost all faults in the rest of the compactor. Further, time compaction is also easily achieved. Since the design can be accomplished without any information about the structure and functionality of the CUT, it would be useful for testing embedded cores as their internal structures may not be transparent to the users.

A combinatorial characterization of a gray-tone image called Euler vector is discussed. The Euler vector comprises a 4-tuple, where each element is an integer representing the Euler number of the partial binary image formed by the four most significant bit planes of the gray-tone image. The vector is topologically invariant and can be used for image indexing and retrieval. The Euler vector for all the images in the database can be arranged using any multidimensional data structure. For retrieval, a query range is to be defined around the query image vector. We use a simple statistical technique to specify the query range. Next, we propose a modification in the Kd-Tree construction to build a simple hybrid tree that supports efficient adaptive clustering and indexing. The same data structure is used for clustering and indexing.

This paper addresses the problem of space compaction of test responses of combinational and scan-based sequential circuits. In a general circuit, compaction of output space to a single output with zero-aliasing cannot always be achieved by earlier known approaches. In this work, it is shown that given a precomputed test set T, the test responses at the functional outputs of any arbitrary circuit-under-test (CUT) can be compacted to a single periodic output, with guaranteed zero aliasing. All the errors that are produced by T at the outputs of the CUT will also appear at the output of the compactor. The method is independent of the fault model and the structure of the CUT and uses only the knowledge of the test set T and the corresponding fault-free responses. A new concept of distinguishing outputs and a characteristic function is used to design the compactor. The test vectors in T are appropriately ordered to optimize the compactor logic, which to achieve zero-aliasing uses a test pattern counter to designate the sequence of test application and a special code checker. A design procedure is described to synthesize the compactor using logic synthesis tools, and relevant experimental results on hardware overhead for several benchmark circuits are presented. It is further shown that the overhead can be significantly reduced if the constraint of exact zero aliasing is slightly relaxed.

A new problem called monotone bipartitioning of a planar point set is identified which is found to be useful in VLSI layout design. Let F denote a rectangular floor containing a set A of n points. The portion of a straight line formed by two points from the set A is called a line segment. A monotone increasing path ( MP ) in F is a connected and ordered sequence of line segments from the bottom-left corner of F to its top-right corner, such that the slope of each line segment is nonnegative, and each pair of consecutive line segments share a common point of A . An MP is said to be maximal ( MMP ) if no other point in A can be included in it preserving monotonicity. Let A L denote the subset of A corresponding to the end points of the line segments in an MMP , L . The path L partitions the set of points A \ A L into two subsets lying on its two sides. The objective of monotone bipartitioning is to find an MMP L , such that the difference in the number of points in these two subsets is minimum. This problem can be formulated as finding a path between two designated vertices of an edge-weighted digraph (the weight of an edge being an integer lying in the range [- n, n ]), for which the absolute value of the algebraic sum of weights is minimized. An O ( n × e ) time algorithm is proposed for this problem, where e denotes the number of edges of the graph determined from the geometry of the point set. The monotone bipartitioning problem has various applications to image processing, facility location, and plant layout problems. A related problem arises while partitioning a VLSI floorplan. Given a floorplan with n rectangular blocks, the goal is to find a monotone staircase channel from one corner of the floor to its diagonally opposite corner such that the difference in the numbers of blocks lying on its two sides is minimum. The problem is referred to as the staircase bipartitioning problem. The proposed algorithm for a point set can be directly used to solve this problem in O ( n 2 ) time. However, an improved O ( n ) time algorithm is reported for this special case. This leads to an O ( n log n ) time algorithm for hierarchical decomposition of a floorplan with a sequence of staircase channels. Staircase bipartitioning has many applications to channel and global routing.

This paper addresses the problem of space compaction of test responses of combinational and scan-based sequential circuits. It is shown that given a precomputed test set T , the test responses at the functional outputs of the given circuit-under-test (CUT) can be compacted to a single periodic output, with guaranteed zero-aliasing. The method is independent of the fault model and the structure of the CUT, and uses only the knowledge of the test set T and the corresponding fault-free responses---it is particularly suitable for intellectual property (IP) cores. A new concept of distinguishing outputs and characteristic response function is utilized for synthesizing the compactor. Relevant experimental results on hardware overhead for several ISCAS circuits are presented. 1 Introduction Space compaction, which refers to the problem of reducing a wide data stream to a narrow signature stream, is commonly used for test response compression. Atypical space compaction scheme for a general c...

The Euler number is a fundamental topological feature of an image, which remains invariant under translation, rotation, scaling, and rubber-sheet transformation of the image. A novel algorithm for computing the Euler number of a binary image is proposed which is based on the properties of runs of 0's and 1's present in the pixel matrix. The algorithm outperforms significantly the existing techniques in terms of both the number of pixel accesses and CPU time. It can be easily parallelized, and a simple on-chip implementation is reported here. Results on a database consisting of 1039 logo images reveal that the Euler number has a strong discriminatory power, and hence can be used for efficient database searching or matching of binary images. The proposed algorithm is very fast and easy to implement, and has potential of wide applicability in image processing.

We present an efficient space compaction method which propagates all realistic errors that can appear at the outputs of a circuit under test in response to a precomputed test set. Since the proposed method does not rely on structural information of the circuit under test, it can be readily applied to intellectual property (IP) cores. Space compaction of test responses for IP cores provides parallel access to their functional outputs and reduces testing time. A /spl delta/-bounded-weight error model is combined with a /spl delta/-response graph model to generate the logic specification for the compactor via graph coloring. Moreover, a carefully-chosen subset of inputs of the circuit under test allows error propagation to be achieved using an arbitrarily small number of compactor outputs. The error-bound variable /spl delta/ parametrizes the space compactor, and the synthesis approach can be used to design several space compactors for the same circuit under test by simply varying /spl delta/. We illustrate the proposed method by presenting experimental results on compactor synthesis for several large ISCAS benchmark circuits.

Best-first and depth-first heuristic search algorithms often assume underlying search graphs with only nonnegative edge costs and attempt to optimize simple objective functions. Applicability of these algorithms to graphs with both positive and negative edge costs is not completely studied. In the paper, two new problems are identified: one in computational geometry and the other in the layout design of very large scale integrated (VLSI) circuits. The former problem relates to a weight-balanced bipartitioning of a given set of points in a plane. The goal of the second problem is to find an area-balanced staircase path in a VLSI floorplan. Formulations of these problems lead to an interesting directed acyclic search graph with positive, zero and negative edge costs and an objective function of general nature. These problems are NP-hard. To solve such general problems optimally, search schemes are proposed. Experimental results reveal the efficacy and versatility of the proposed schemes, the depth-first scheme being the better choice. It is shown that the classical number-partitioning problem can also be formulated in this framework.

Design of irredundant and fully testable nonscan sequential circuits is a major concern of logic synthesis, as the presence of undetectable faults may render an ATPG intractable. This paper outlines some intriguing properties of isomorph faults, which are sequentially undetectable as well as redundant. An isomorph fault in a sequential circuit makes the state diagram of the faulty machine identical to that of the fault-free machine under certain renaming of states. Examples of reduced sequential machines whose circuit realization is combinationally irredundant, but isomorph-redundant, are hard to construct and very little is known about them. In this paper, many curious examples of such sequential circuits are presented wherein a single stuck-at fault causes isomorphic faulty machines. An infinite family of such circuits may, in fact, be constructed. It is shown that even two-level irredundant circuits obtained by synthesis tools may admit isomorph-redundancy under multiple stuck-at faults. Various classifications and related properties of isomorph faults are also reported. These results reveal new insight and understanding of redundancy in sequential circuits.

A new technique of synthesizing totally symmetric Boolean functions is presented that achieves complete robust path-delay fault testability. We show that every consecutive symmetric function can be expressed as a logical composition (e.g., AND, NOR) of two unate symmetric functions, and the resulting composite circuit can be made robustly path-delay fault testable, if the constituent unate functions are synthesized as two-level irredundant circuits. Nonconsecutive symmetric functions can also be synthesized by decomposing them into a set of consecutive symmetric functions. The circuit cost of the proposed design can further be reduced by a novel algebraic factorization technique based on some combinatorial clues. The overall synthesis guarantees complete robust path-delay fault testability, and can be completed in linear time. The results shows that the proposed method ensures a significant reduction in hardware, as well as in the number of paths, which in turn, reduces testing time, as compared to those of the best-known earlier methods.

Design of an adaptive built-in-self-test (BIST) scheme for detecting multiple stuck-open faults in a CMOS complex cell is proposed. The test pattern generator (TPG) adaptively generates a subset of single-input-change (SIC) test pairs based on the past responses of the circuit under test (CUT). The design is universal, i.e., independent of the structure and functionality of the CUT. The average length of the test sequence (TS) in an n-input CUT is (n+1).2/sup n/ [(n+1).2/sup n-1/] in a fault-free [faulty] condition. The response analyzer (RA) is also simple to design. All robustly testable multiple stuck-open faults (occurring simultaneously both in n- and p-parts) can be detected using the proposed BIST scheme.

A new concept of interchangeability of boolean functions under stuck-at faults in logic circuits is introduced in this paper. Two boolean functions F/sub 1/ and F/sub 2/ are said to be interchangeable if there exist two irredundant combinational networks N/sub 1/ and N/sub 2/ realizing F/sub 1/ and F/sub 2/ respectively, such that under some single/multiple stuck-at fault f/sub 1/(f/sub 2/) in N/sub 1/(N/sub 2/), the faulty network realizes F/sub 2/(F/sub 1/). It has been shown that an infinite family of such interchangeable pairs of functions exist, and they play an important role in determining several new types of redundancy in combinational and sequential circuits.

The set of input-output permutations that are routable through a multistage interconnection network without any conflict (known as the admissible set), plays an important role in determining the capability of the network. Recent works on the permutation admissibility problem of shuffle-exchange networks (SEN) of size N/spl times/N, deal with (n+k) stages, where n=log/sub 2/N, and k denotes the number of extra stages. For k=0 or 1, O(Nn) algorithms exist to check if any permutation is admissible, but for k/spl ges/2, a polynomial time solution is not yet known. The more general problem of finding the minimum number (m) of shuffle-exchange stages required to realize an arbitrary permutation, 1/spl les/m/spl les/2n-1, is also an open problem. In this paper, we present an O(Nn) algorithm that checks whether a given permutation P is admissible in an m stage SEN, 1/spl les/m/spl les/n, and determines in O(Nnlogn) time the minimum number of stages m of shuffle-exchange, required to realize P. Thus, a single-stage shuffle-exchange network will be able to realize such a permutation with m passes, by recirculating all the paths m times through a single-stage, i.e., with minimum transmission delay, which, otherwise cannot be achieved with a fixed-stage SEN. Furthermore, we present a necessary condition for permutation admissibility in an m stage SEN, where n

Existing algorithms for floorplan topology generation by rectangular dualization usually do not consider sizing issues. In this paper, given a rectangularly dualizable adjacency graph and a set of aspect ratios of the modules, a topology which is likely to yield an optimally sized floorplan, is produced first in a top-down fashion by an AI-based search technique with novel heuristic estimates based on size parameters. It is shown that for any rectangular graph, there exists a feasible topology using only either straight or Z-cutlines recursively within a bounding rectangle. The significance of this result is four-fold: (1) considerable acceleration of the heuristic search, (2) topology generation with minimal number of nonslice cores, (3) guaranteed safe routing order without addition of pseudo modules, and (4) design of an efficient bottom-up heuristic for optimal sizing. Experimental results show that this integrated method elegantly solves floorplan optimization problem for general including inherently nonslicible adjacency graphs.

An isomorph fault in a sequential circuit makes the state diagram of the faulty machine identical to that of the fault-free machine, under the renaming of states. However, no example of a reduced sequential machine whose circuit realization is combinationally irredundant but isomorph-redundant, is yet known. This paper shows that an infinite family of such circuits can be constructed with isomorph-redundancy. Isomorph faults are then classified into various types. Their properties reveal new insight and understanding of redundancy in sequential circuits.

Design of irredundant and fully testable non-scan synchronous sequential circuits is a major concern of logic synthesis. The presence of sequentially redundant faults (SRFs) makes test generation complicated, and hence their removal is highly desirable to enhance testability. In this paper, we propose a novel technique for testable design which is significantly different from scan designs, or testability-targeted synthesis approaches. We show that addition of some extra logic and a control input to an arbitrary sequential circuit can eliminate all equivalent and isomorph SRFs, even under the multiple stuck-at-fault model. Every pair of states can easily be distinguished in the modified machine, thus making it easily testable. The augmented logic is also universal, i.e., independent of the state diagram or the circuit structure of the given machine. Analysis of benchmark circuits reveals that its hardware overhead is much less compared to that of full scan design.

In this paper, it is shown that for any rectangularly dualizable graph, a feasible topology can be obtained by using only either straight or Z-cutlines recursively within a bounding rectangle. Given an adjacency graph, a potential topology, which may be nonslicible and is likely to yield an optimally sized floorplan, is produced first in a top-dozen fashion using heuristic search in AND-OR graphs. The advantage of this technique is four-fold: (i) accelerates top-down search phase, (ii) generates a floorplan with minimal number of nonslice cores, (iii) ensures safe routing order without addition of pseudo-modules, and (iv) solves the bottom-up algorithm efficiently for optimal sizing of general floorplans in the second phase.

This paper explores a new hierarchy among different permutation classes, that has many applications in multistage interconnection networks. The well-known LC (linear-complement) class is shown to be merely a subset of the closure set of the BP (bit-permute) class, known as the BPCL (bit-permute-closure) class; the closure is obtained by applying certain group-transformation rules on the BP-permutations. It indicates that for every permutation P of the LC class, there exists a permutation PI in the BP class, such that the conflict graphs of P and P* are isomorphic, for n-stage MIN's. This obviates the practice of treating the LC class as a special case; the existing algorithm for optimal routing of BPC class in an n-stage MIN can take care of optimal routing of the LC class as well. Finally, the relationships of BPCL with other classes of permutations, e.g., LIE (linear-input-equivalence), BPIE (bit-permute-input-equivalence), BPOE (bit-permute-output-equivalence) are also exposed. Apart from lending better understanding and an integral view of the universe of permutations, these results are found to be useful in accelerating routability in n-stage MIN's as well as in (2n-1)-stage Benes and shuffle-exchange networks.>

A study on the isomorphism of conflict graphs in multistage interconnection networks (MINs) and its applications is outlined. A concept called group-transformation is introduced for the baseline network, which induces an equivalence partition on the set of all permutations. All members belonging to the same equivalence class have isomorphic conflict graphs. Thus, determination of conflict resolution of one permutation results in determination of conflict resolution of all other equivalent members. The BPCL (bit-permute-closure) class of permutations is defined, for which the conflict resolution problem can be settled in linear time by an earlier algorithm developed only for the BPC (bit-permute-complement) permutations. It is proved that for an N*N MIN, mod BPCL mod >or=n 2N-1, in contrast to mod BPC mod n 2n, (nlog/sup 2/ N). Conflict graphs for BPCL permutations are also characterized. An O(N) time algorithm to check membership of a given permutation to the BPCL class is described. All of these results are generalized to extend their applicability to other unique-path full-access MINs.>

Channel graphs for nonsliceable floorplans are studied for determination of feasible channel routing order. The minimum feedback vertex set (MFVS) formulation is revisited and a polynomial time heuristic is presented. It is shown that feasible routing orders with reserved channels, L-channels, and monotone channels can be obtained from a given MFVS for any floorplan. This approach provides a powerful tool to unify all three previous approaches and produces a solution with comparable efficiency and quality.>

This paper presents a new testable design scheme appli- cable to any arbitrary 1-dimensional bilateral systolic array. The hardware overhead is a global control he and a small amount of additional logic per cell . The proposed design ensures that all cells in the array can simultaneously be set to any state in constant steps after initialization, regardless of the size of the array. The design also supports propaga- tion of test outcomes to observable exiremitles so that the where IVI is the number of states per cell and N is the number

The parity testability of a single output is related to its partition in terms of maximal supergates, and a scheme is proposed for making an untestable circuit parity testable by augmenting its maximal supergates. Only a small amount of extra logic and a single external test-mode pin are required to complete the design. The test procedure is simple, and the hardware overhead is low.>

A unified approach is developed for solving the general problem of minimizing the number of via holes in a two-layer very large-scale integration (VLSI) channel and switch-box routing environment with movable terminals. All horizontal segments of the nets are assumed to be in one layer, and the vertical segments in the other layer. Each net can have multiple terminals. Three different models are considered: (i) two-row channel routing, (ii) three-sided switch-box routing, and (iii) four-sided switch-box routing. The concept of a maximum parallel set of edges in a bipartite graph is introduced to solve the minimization problem. This leads to a unified graph-theoretic approach for solving the via minimization problem for all three models considered. The complexity of the proposed algorithm is O(N log N), in all three cases, where N is the number of pairs of terminals to be connected.>

The performance of a fast fault simulation algorithm for combinational circuits, such as the critical-path-tracing method, is determined primarily by the efficiency with which it can deduce the detectability of stem faults (stem analysis). A graph-based approach to perform stem analysis is proposed. A dynamic data structure, called the criticality constraint graph, is used during the backward pass to carry information related to self-masking and multiple-path sensitization of stem faults. The structure is updated in such a way that when stems are reached, their criticality can be found by looking at the criticality constraints on their fanout branches. Compared to the critical-path-tracing method, the algorithm is exact and does not require forward propagation of individual stem faults. Several examples which illustrate the power of the algorithm are given. Preliminary data on an implementation are also provided.>

The important problem of recognizing a priori the class of Boolean functions which are never obtainable from a given combinational network under short circuit faults is almost unexplored, primarily due to lack of understanding of the functional and structural factors that influence the fault behavior in the network. In view of this, a new concept of impossible class of faulty functions (ICFF) is introduced in this correspondence. Several intriguing properties of ICFF are uncovered, namely, the undetectability of input bridging faults, the impossibility of the transformation of a fault free function Fo to a subset or superset of Fo, and to other functions belonging to the same P-and N-equivalence classes of Fo, etc. The closure amongst the fan-out-free and unate functions under bridging faults is investigated. The impact of ICFF on the testability of the network is also discussed.

In this correspondence we develop a parallel algorithm to compute the all-pairs shortest paths and the diameter of a given graph. Next, this algorithm is mapped into a suitable VLSI systolic architecture and the performance of this proposed VLSI implementation is evaluated.

The problem of estimating the number of all possible multiple short circuit faults in a network with a given number of lines is settled in this correspondence. A new combinatorial number, namely an associated Bell number B'(r), which enumerates the number of possible partitions of a set {1, 2,···, r} with certain constraints, is introduced. This concept immediately resolves the counting problem of short-circuit or bridging faults in an electrical network. A related combinatorial problem is also discussed which shows that under some realistic model of circuit failure, the number of possible ways the network can malfunction is closely connected to the Fibonacci sequence.