Journal articles: 'Algebraic Circuits'

1

Limaye, Nutan, Srikanth Srinivasan, and Sébastien Tavenas. "Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits." Communications of the ACM 67, no. 2 (January 25, 2024): 101–8. http://dx.doi.org/10.1145/3611094.

Full text

Abstract:

An Algebraic Circuit for a multivariate polynomial P is a computational model for constructing the polynomial P using only additions and multiplications. It is a syntactic model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be easier to prove than lower bounds for Boolean circuits. Despite this, we do not have superpolynomial lower bounds against general algebraic circuits of depth 3 (except over constant-sized finite fields) and depth 4 (over any field other than F 2 ), while constant-depth Boolean circuit lower bounds have been known since the early 1980s. In this paper, we prove the first superpolynomial lower bounds against algebraic circuits of all constant depths over all fields of characteristic 0. We also observe that our super-polynomial lower bound for constant-depth circuits implies the first deterministic sub-exponential time algorithm for solving the Polynomial Identity Testing (PIT) problem for all small-depth circuits using the known connection between algebraic hardness and randomness.

APA, Harvard, Vancouver, ISO, and other styles

2

Sopena, Alejandro, Max Hunter Gordon, Diego García-Martín, Germán Sierra, and Esperanza López. "Algebraic Bethe Circuits." Quantum 6 (September 8, 2022): 796. http://dx.doi.org/10.22331/q-2022-09-08-796.

Full text

Abstract:

The Algebraic Bethe Ansatz (ABA) is a highly successful analytical method used to exactly solve several physical models in both statistical mechanics and condensed-matter physics. Here we bring the ABA into unitary form, for its direct implementation on a quantum computer. This is achieved by distilling the non-unitary R matrices that make up the ABA into unitaries using the QR decomposition. Our algorithm is deterministic and works for both real and complex roots of the Bethe equations. We illustrate our method on the spin-12 XX and XXZ models. We show that using this approach one can efficiently prepare eigenstates of the XX model on a quantum computer with quantum resources that match previous state-of-the-art approaches. We run small-scale error-mitigated implementations on the IBM quantum computers, including the preparation of the ground state for the XX and XXZ models on 4 sites. Finally, we derive a new form of the Yang-Baxter equation using unitary matrices, and also verify it on a quantum computer.

APA, Harvard, Vancouver, ISO, and other styles

3

Sarangapani, P., T. Thiessen, and W. Mathis. "Differential Algebraic Equations of MOS Circuits and Jump Behavior." Advances in Radio Science 10 (October 2, 2012): 327–32. http://dx.doi.org/10.5194/ars-10-327-2012.

Full text

Abstract:

Abstract. Many nonlinear electronic circuits showing fast switching behavior exhibit jump effects which occurs when the state space of the electronic system contains a fold. This leads to difficulties during the simulation of these systems with standard circuit simulators. A method to overcome these problems is by regularization, where parasitic inductors and capacitors are added at the suitable locations. However, the transient solution will not be reliable if this regularization is not done in accordance with Tikhonov's Theorem. A geometric approach is taken to overcome these problems by explicitly computing the state space and jump points of the circuit. Until now, work has been done in analyzing example circuits exhibiting this behavior for BJT transistors. In this work we apply these methods to MOS circuits (Schmitt trigger, flip flop and multivibrator) and present the numerical results. To analyze the circuits we use the EKV drain current model as equivalent circuit model for the MOS transistors.

APA, Harvard, Vancouver, ISO, and other styles

4

DUMITRIU, LUCIA, and MIHAI IORDACHE. "NUMERICAL STEADY-STATE ANALYSIS OF NONLINEAR ANALOG CIRCUITS DRIVEN BY MULTITONE SIGNALS." International Journal of Bifurcation and Chaos 17, no. 10 (October 2007): 3595–601. http://dx.doi.org/10.1142/s0218127407019421.

Full text

Abstract:

Widely-separated time scales appear in many electronic circuits, making traditional analysis difficult, even impossible, if the circuits are highly nonlinear. This paper presents a new version of the modified nodal method in two time variables for the analysis of the circuit with widely separated time scales. By applying this approach the differential algebraic equations (DAE) describing the nonlinear analog circuits driven by multitone signals are transformed into multitime partial differential equations (MPDEs). In order to solve MPDEs, associated resistive discrete equivalent circuits (companion circuits) for the dynamic circuit elements are used. The boundary conditions are detailed and simulation results are presented.

APA, Harvard, Vancouver, ISO, and other styles

5

Saima Yasin. "Analysis of Reachable and Positive Electrical Circuits Modelled by differential Algebraic System." Mathematical Sciences and Applications 3, no. 1 (June 30, 2024): 1–17. http://dx.doi.org/10.52700/msa.v3i1.23.

Full text

Abstract:

This research paper undertakes an exploration of novel concepts within the domain of electrical circuits modeled by matrices. The study is centered around circuits encompassing elements such as resistances, coils, and voltage sources, with a specific focus on elucidating aspects of positivity and reachability. A distinctive approach is employed through the introduction of additional inductors, aimed at enhancing the circuit’s functionality. Employing mathematical analysis, this research endeavor advances an extensive comprehension of these circuits, shedding light on their behavior even when subject to specific constraints. As a consequence, this inquiry contributes to the revelation of noteworthy insights about the operational dynamics of circuits.

APA, Harvard, Vancouver, ISO, and other styles

6

Agrawal, Manindra, Sumanta Ghosh, and Nitin Saxena. "Bootstrapping variables in algebraic circuits." Proceedings of the National Academy of Sciences 116, no. 17 (April 11, 2019): 8107–18. http://dx.doi.org/10.1073/pnas.1901272116.

Full text

Abstract:

We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One needs only to consider size-s degree-s circuits that depend on the firstlog○c svariables (where c is a constant and composes a logarithm with itself c times). Thus, the hitting-set generator (hsg) manifests a bootstrapping behavior—a partial hsg against very few variables can be efficiently grown to a complete hsg. A Boolean analog, or a pseudorandom generator property of this type, is unheard of. Our idea is to use the partial hsg and its annihilator polynomial to efficiently bootstrap the hsg exponentially w.r.t. variables. This is repeated c times in an efficient way. Pushing the envelope further we show that (i) a quadratic-time blackbox PIT for 6,913-variate degree-s size-s polynomials will lead to a “near”-complete derandomization of PIT and (ii) a blackbox PIT for n-variate degree-s size-s circuits insnδtime, forδ<1/2, will lead to a near-complete derandomization of PIT (in contrast,sntime is trivial). Our second idea is to study depth-4 circuits that depend on constantly many variables. We show that a polynomial-time computable,O(s1.49)-degree hsg for trivariate depth-4 circuits bootstraps to a quasipolynomial time hsg for general polydegree circuits and implies a lower bound that is a bit stronger than that of Kabanets and Impagliazzo [Kabanets V, Impagliazzo R (2003)Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing STOC ’03].

APA, Harvard, Vancouver, ISO, and other styles

7

Ozawa, Kazuhiro, Kaoru Hirota, LászlóT Kóczy, and Ken Ōmori. "Algebraic fuzzy flip-flop circuits." Fuzzy Sets and Systems 39, no. 2 (January 1991): 215–26. http://dx.doi.org/10.1016/0165-0114(91)90214-b.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Tykhovod, Sergii, and Ihor Orlovskyi. "Development and Research of Method in the Calculation of Transients in Electrical Circuits Based on Polynomials." Energies 15, no. 22 (November 15, 2022): 8550. http://dx.doi.org/10.3390/en15228550.

Full text

Abstract:

Long electromagnetic transients occur in electrical systems because of switching and impulse actions As a result, the simulation time of such processes can be long, which is undesirable. Simulation time is significantly increased if the circuit in the study is complex, and also if this circuit is described by a rigid system of state equations. Modern requests of design engineers require an increase in the speed of calculations for realizing a real-time simulation. This work is devoted to the development of a unified spectral method for calculating electromagnetic transients in electrical circuits based on the representation of solution functions by series in algebraic and orthogonal polynomials. The purpose of the work is to offer electrical engineers a method that can significantly reduce the time for modeling transients in electrical circuits. Research methods. Approximation of functions by orthogonal polynomials, numerical methods for integrating differential equations, matrix methods, programming and theory of electrical circuits. Obtained results. Methods for calculating transients in electrical circuits based on the approximation of solution functions by series in algebraic polynomials as well as in the Chebyshev, Hermite and Legendre polynomials, have been developed and investigated. The proposed method made it possible to convert integro-differential equations of state into linear algebraic equations for images of time-dependent functions. The developed circuit model simplifies the calculation method. The images of true current functions are interpreted as direct currents in the proposed equivalent circuit. A computer program for simulating the transient process in an electrical circuit was developed on the basis of the described methods. The performed comparison of methods made it possible to choose the best method and a way to use it. The advantages of the presented method over other known methods are to reduce the simulation time of electromagnetic transients (for the considered examples by more than 6 times) while ensuring the required accuracy. The calculation of the process in the circuit over a long time interval showed a decrease and stabilization of errors, which indicates the prospects for using research methods for calculating complex electrical circuits.

APA, Harvard, Vancouver, ISO, and other styles

9

Siegal-Gaskins, Dan, Elisa Franco, Tiffany Zhou, and Richard M. Murray. "An analytical approach to bistable biological circuit discrimination using real algebraic geometry." Journal of The Royal Society Interface 12, no. 108 (July 2015): 20150288. http://dx.doi.org/10.1098/rsif.2015.0288.

Full text

Abstract:

Biomolecular circuits with two distinct and stable steady states have been identified as essential components in a wide range of biological networks, with a variety of mechanisms and topologies giving rise to their important bistable property. Understanding the differences between circuit implementations is an important question, particularly for the synthetic biologist faced with determining which bistable circuit design out of many is best for their specific application. In this work we explore the applicability of Sturm's theorem—a tool from nineteenth-century real algebraic geometry—to comparing ‘functionally equivalent’ bistable circuits without the need for numerical simulation. We first consider two genetic toggle variants and two different positive feedback circuits, and show how specific topological properties present in each type of circuit can serve to increase the size of the regions of parameter space in which they function as switches. We then demonstrate that a single competitive monomeric activator added to a purely monomeric (and otherwise monostable) mutual repressor circuit is sufficient for bistability. Finally, we compare our approach with the Routh–Hurwitz method and derive consistent, yet more powerful, parametric conditions. The predictive power and ease of use of Sturm's theorem demonstrated in this work suggest that algebraic geometric techniques may be underused in biomolecular circuit analysis.

APA, Harvard, Vancouver, ISO, and other styles

10

Erata, Ferhat, Chuanqi Xu, Ruzica Piskac, and Jakub Szefer. "Quantum Circuit Reconstruction from Power Side-Channel Attacks on Quantum Computer Controllers." IACR Transactions on Cryptographic Hardware and Embedded Systems 2024, no. 2 (March 12, 2024): 735–68. http://dx.doi.org/10.46586/tches.v2024.i2.735-768.

Full text

Abstract:

The interest in quantum computing has grown rapidly in recent years, and with it grows the importance of securing quantum circuits. A novel type of threat to quantum circuits that dedicated attackers could launch are power trace attacks. To address this threat, this paper presents first formalization and demonstration of using power traces to unlock and steal quantum circuit secrets. With access to power traces, attackers can recover information about the control pulses sent to quantum computers. From the control pulses, the gate level description of the circuits, and eventually the secret algorithms can be reverse engineered. This work demonstrates how and what information could be recovered. This work uses algebraic reconstruction from power traces to realize two new types of single trace attacks: per-channel and total power attacks. The former attack relies on per-channel measurements to perform a brute-force attack to reconstruct the quantum circuits. The latter attack performs a single-trace attack using Mixed-Integer Linear Programming optimization. Through the use of algebraic reconstruction, this work demonstrates that quantum circuit secrets can be stolen with high accuracy. Evaluation on 32 real benchmark quantum circuits shows that our technique is highly effective at reconstructing quantum circuits. The findings not only show the veracity of the potential attacks, but also the need to develop new means to protect quantum circuits from power trace attacks. Throughout this work real control pulse information from real quantum computers is used to demonstrate potential attacks based on simulation of collection of power traces.

APA, Harvard, Vancouver, ISO, and other styles

11

Hutsell, Steven R., and Garrison W. Greenwood. "Efficient algebraic representation of quantum circuits." Journal of Discrete Mathematical Sciences and Cryptography 12, no. 4 (August 2009): 429–49. http://dx.doi.org/10.1080/09720529.2009.10698246.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Reif, John H. "Logarithmic Depth Circuits for Algebraic Functions." SIAM Journal on Computing 15, no. 1 (February 1986): 231–42. http://dx.doi.org/10.1137/0215017.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Rao, V. V. Bapeswara. "Reactive Power Measurement in Three-Phase Unbalanced Circuits Using Two Wattmeters." International Journal of Electrical Engineering & Education 47, no. 2 (April 2010): 227–28. http://dx.doi.org/10.7227/ijeee.47.2.12.

Full text

Abstract:

A procedure to measure reactive power in three-phase unbalanced circuits using two wattmeters is presented. The total reactive power is obtained as an algebraic sum of two wattmeter readings. The voltage coil circuit of each wattmeter is suitably modified.

APA, Harvard, Vancouver, ISO, and other styles

14

Jahandideh, Vahid, Bart Mennink, and Lejla Batina. "An Algebraic Approach for Evaluating Random Probing Security With Application to AES." IACR Transactions on Cryptographic Hardware and Embedded Systems 2024, no. 4 (September 5, 2024): 657–89. http://dx.doi.org/10.46586/tches.v2024.i4.657-689.

Full text

Abstract:

We employ an algebraic approach to estimate the success rate of a sidechannel adversary attacking secrets of a masked circuit within the Random Probing Model (RPM), where intermediate variables of the implementation leak with a probability p. Our method efficiently handles masked linear circuits, enabling security bound estimation for practically large masking orders. For non-linear circuits, we employ a linearization technique. To reason about the security of complex structures like an S-box, we introduce a composition theorem, reducing the RPM security of a circuit to that of its constituent gadgets. Moreover, we lower the complexity of the multiplication gadget of CHES 2016 from O(n2 log(n)) to O(n2) while demonstrating its conjectured RPM security. Collectively, these novel methods enable the development of a practical masking scheme with O(n2) complexity for AES, maintaining security for a considerably high leakage rate p ≤ 0.02 ≈ 2−5.6.

APA, Harvard, Vancouver, ISO, and other styles

15

Ashok, P., and B. Bala Tripura Sundari. "Accuracy Analysis on Design of Stochastic Computing in Arithmetic Components and Combinational Circuit." Computation 11, no. 12 (December 1, 2023): 237. http://dx.doi.org/10.3390/computation11120237.

Full text

Abstract:

Stochastic circuits are used in applications that require low area and power consumption. The computing performed using these circuits is referred to as Stochastic computing (SC). The arithmetic operations in this computing can be realized using minimum logic circuits. The SC system allows a tradeoff of computational accuracy and area; thereby, the challenge in SC is improving the accuracy. The accuracy depends on the SC system’s stochastic number generator (SNG) part. SNGs provide the appropriate stochastic input required for stochastic computation. Hence we explore the accuracy in SC for various arithmetic operations performed using stochastic computing with the help of logic circuits. The contributions in this paper are; first, we have performed stochastic computing for arithmetic components using two different SNGs. The SNGs considered are Linear Feed-back Shift Register (LFSR) -based traditional stochastic number generators and S-box-based stochastic number generators. Second, the arithmetic components are implemented in a combinational circuit for algebraic expression in the stochastic domain using two different SNGs. Third, computational analysis for stochastic arithmetic components and the stochastic algebraic equation has been conducted. Finally, accuracy analysis and measurement are performed between LFSR-based computation and S-box-based computation. The novel aspect of this work is the use of S-box-based SNG in the development of stochastic computing in arithmetic components. Also, the implementation of stochastic computing in the combinational circuit using the developed basic arithmetic components, and exploration of accuracy with respect to stochastic number generators used is presented.

APA, Harvard, Vancouver, ISO, and other styles

16

Hà, Huy Tài, and Susan Morey. "Algebraic Algorithms for Even Circuits in Graphs." Mathematics 7, no. 9 (September 17, 2019): 859. http://dx.doi.org/10.3390/math7090859.

Full text

Abstract:

We present an algebraic algorithm to detect the existence of and to list all indecomposable even circuits in a given graph. We also discuss an application of our work to the study of directed cycles in digraphs.

APA, Harvard, Vancouver, ISO, and other styles

17

Lafont, Yves. "Towards an algebraic theory of Boolean circuits." Journal of Pure and Applied Algebra 184, no. 2-3 (November 2003): 257–310. http://dx.doi.org/10.1016/s0022-4049(03)00069-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Ben-Asher, Yosi, and Gadi Haber. "Efficient parallel solutions of linear algebraic circuits." Journal of Parallel and Distributed Computing 64, no. 1 (January 2004): 163–72. http://dx.doi.org/10.1016/j.jpdc.2003.11.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Berthet, C., and E. Cerny. "An algebraic model for asynchronous circuits verification." IEEE Transactions on Computers 37, no. 7 (July 1988): 835–47. http://dx.doi.org/10.1109/12.2229.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

García de la Vega, Ignacio, and Ricardo Riaza. "Saddle-Node Bifurcations in Classical and Memristive Circuits." International Journal of Bifurcation and Chaos 26, no. 04 (April 2016): 1650064. http://dx.doi.org/10.1142/s0218127416500644.

Full text

Abstract:

This paper addresses a systematic characterization of saddle-node bifurcations in nonlinear electrical and electronic circuits. Our approach is a circuit-theoretic one, meaning that the bifurcation is analyzed in terms of the devices’ characteristics and the graph-theoretic properties of the digraph underlying the circuit. The analysis is based on a reformulation of independent interest of the saddle-node theorem of Sotomayor for semiexplicit index one differential-algebraic equations (DAEs), which define the natural context to set up nonlinear circuit models. The bifurcation is addressed not only for classical circuits, but also for circuits with memristors. The presence of this device systematically leads to nonisolated equilibria, and in this context the saddle-node bifurcation is shown to yield a bifurcation of manifolds of equilibria; in cases with a single memristor, this phenomenon describes the splitting of a line of equilibria into two, with different stability properties.

APA, Harvard, Vancouver, ISO, and other styles

21

KHEIRANDISH, F., and H. PAHLAVANI. "DRIVEN MESOSCOPIC ELECTRIC CIRCUITS." Modern Physics Letters B 22, no. 01 (January 10, 2008): 51–60. http://dx.doi.org/10.1142/s0217984908014511.

Full text

Abstract:

The quantum theory for a mesoscopic electric circuit with charge discreteness is investigated. The persistent current on a quantum ring using an algebraic approach have been obtained. The energy spectrum and the persistent current of a quantum LC-design mesoscopic circuit, with a time-dependent external source, have been found.

APA, Harvard, Vancouver, ISO, and other styles

22

Banik, Subhadeep, and Francesco Regazzoni. "Compact Circuits for Efficient Möbius Transform." IACR Transactions on Cryptographic Hardware and Embedded Systems 2024, no. 2 (March 12, 2024): 481–521. http://dx.doi.org/10.46586/tches.v2024.i2.481-521.

Full text

Abstract:

The Möbius transform is a linear circuit used to compute the evaluations of a Boolean function over all points on its input domain. The operation is very useful in finding the solution of a system of polynomial equations over GF(2) for obvious reasons. However the operation, although linear, needs exponential number of logic operations (around n · 2n−1 bit xors) for an n-variable Boolean function. As such, the only known hardware circuit to efficiently compute the Möbius Transform requires silicon area that is exponential in n. For Boolean functions whose algebraic degree is bound by some parameter d, recursive definitions of the Möbius Transform exist that requires only O(nd+1) space in software. However converting the mathematical definition of this space-efficient algorithm into a hardware architecture is a non-trivial task, primarily because the recursion calls notionally lead to a depth-first search in a transition graph that requires context switches at each recursion call for which straightforward mapping to hardware is difficult. In this paper we look to overcome these very challenges in an engineering sense. We propose a space efficient sequential hardware circuit for the Möbius Transform that requires only polynomial circuit area (i.e. O(nd+1)) provided the algebraic degree of the Boolean function is limited to d. We show how this circuit can be used as a component to efficiently solve polynomial equations of degree at most d by using fast exhaustive search. We propose three different circuit architectures for this, each of which uses the Möbius Transform circuit as a core component. We show that asymptotically, all the solutions of a system of m polynomials in n unknowns and algebraic degree d over GF(2) can be found using a circuit of silicon area proportional to m · nd+1 and circuit depth proportional to 2 · log2(n − d).In the second part of the paper we introduce a fourth hardware solver that additionally aims to achieve energy efficiency. The main idea is to reduce the solution space to a small enough value by parallel application of Möbius Transform circuits over the first few equations of the system. This is done so that one can check individually whether the vectors of this reduced solution space satisfy each of the remaining equations of the system using lower power consumption. The new circuit has area also bound by m · nd+1 and has circuit depth proportional to d · log2 n. We also show that further optimizations with respect to energy consumption may be obtained by using depth-bound Möbius circuits that exponentially decrease run time at the cost of additional logic area and depth.

APA, Harvard, Vancouver, ISO, and other styles

23

KURGANOV, Sergey A., and Vladimir V. FILARETOV. "Circuit-algebraic calculation of steady-state modes of electric networks." Elektrichestvo 4, no. 4 (2021): 65–72. http://dx.doi.org/10.24160/0013-5380-2021-4-65-72.

Full text

Abstract:

In iterative algorithms for calculating the steady-state modes of AC electrical networks, it is proposed to use compact symbolic-numerical functions of nodal voltages formed by the method of circuit determinants once. These functions, due to algebraic convolution, have many times less complexity than the expanded expressions obtained by the tree method. Such functions are found by circuit-algebraic formulas in the form of a ratio of circuit determinants by allocating parameters. First of all, the conductivities (resistances) composed of a larger number of parallel (sequential) branches and incident nodes with a minimum (maximum) degree are distinguished. The original and derived schemes are recursively divided into parts that are similar in complexity. It is shown that the known computer systems for analytical calculations do not take into account the features of electrical circuits, without providing compact convolution.

APA, Harvard, Vancouver, ISO, and other styles

24

STRAUBING, HOWARD. "CONSTANT-DEPTH PERIODIC CIRCUITS." International Journal of Algebra and Computation 01, no. 01 (March 1991): 49–87. http://dx.doi.org/10.1142/s0218196791000043.

Full text

Abstract:

This paper is devoted to the languages accepted by constant-depth, polynomial-size families of circuits in which every circuit element computes the sum of its input bits modulo a fixed period q. It has been conjectured that such a circuit family cannot compute the AND function of n inputs. Here it is shown that such circuit families are equivalent in power to polynomial-length programs over finite solvable groups; in particular, the conjecture implies that Barrington's result on the computational power of branching programs over nonsolvable groups cannot be extended to solvable groups. It is also shown that polynomial-length programs over dihedral groups cannot compute the AND function. Furthermore, it is shown that the conjecture is equivalent to a characterization, in terms of finite semigroups and formal logic, of the regular languages accepted by such circuit families. There is, moreover, considerable independent evidence for this characterization. This last result is established using new theorems, of independent interest, concerning the algebraic structure of finite categories.

APA, Harvard, Vancouver, ISO, and other styles

25

Sauer, P. W., B. C. Lesieutre, and M. A. Pai. "Transient algebraic circuits for power system dynamic modelling." International Journal of Electrical Power & Energy Systems 15, no. 5 (January 1993): 315–21. http://dx.doi.org/10.1016/0142-0615(93)90053-p.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

FILIPKOVSKA, MARIA S. "Lagrange Stability of Semilinear Differential-Algebraic Equations and Application to Nonlinear Electrical Circuits." Zurnal matematiceskoj fiziki, analiza, geometrii 14, no. 2 (June 25, 2018): 169–96. http://dx.doi.org/10.15407/mag14.02.169.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Al-Rabadi, Anas. "Three-dimensional lattice logic circuits, Part II: Formal methods." Facta universitatis - series: Electronics and Energetics 18, no. 1 (2005): 15–28. http://dx.doi.org/10.2298/fuee0501015a.

Full text

Abstract:

This paper introduces formal algebraic methods for the design of three-dimensional (3D) lattice circuits that were discussed in the first part of my article. New regular 3D logic circuits are introduced, where the application of ternary decompositions into regular three-dimensional lattice circuits is shown. Lattice circuits represent an important class of regular logic circuits that allow for local interconnections, predictable timing fast fault localization, and self-repair. The introduced design methods can be used for the automatic design of logic circuits in 3D for applications and future technologies that require such topologies.

APA, Harvard, Vancouver, ISO, and other styles

28

Jozsa, Richard, Barbara Kraus, Akimasa Miyake, and John Watrous. "Matchgate and space-bounded quantum computations are equivalent." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 466, no. 2115 (November 11, 2009): 809–30. http://dx.doi.org/10.1098/rspa.2009.0433.

Full text

Abstract:

Matchgates are an especially multiflorous class of two-qubit nearest-neighbour quantum gates, defined by a set of algebraic constraints. They occur for example in the theory of perfect matchings of graphs, non-interacting fermions and one-dimensional spin chains. We show that the computational power of circuits of matchgates is equivalent to that of space-bounded quantum computation with unitary gates, with space restricted to being logarithmic in the width of the matchgate circuit. In particular, for the conventional setting of polynomial-sized (logarithmic-space generated) families of matchgate circuits, known to be classically simulatable, we characterize their power as coinciding with polynomial-time and logarithmic-space-bounded universal unitary quantum computation.

APA, Harvard, Vancouver, ISO, and other styles

29

BRUNK, MARKUS, and ANSGAR JÜNGEL. "SIMULATION OF THERMAL EFFECTS IN OPTOELECTRONIC DEVICES USING COUPLED ENERGY-TRANSPORT AND CIRCUIT MODELS." Mathematical Models and Methods in Applied Sciences 18, no. 12 (December 2008): 2125–50. http://dx.doi.org/10.1142/s0218202508003315.

Full text

Abstract:

A coupled model with optoelectronic semiconductor devices in electric circuits is proposed. The circuit is modeled by differential-algebraic equations derived from modified nodal analysis. The transport of charge carriers in the semiconductor devices (laser diode and photo diode) is described by the energy-transport equations for the electron density and temperature, the drift-diffusion equations for the hole density, and the Poisson equation for the electric potential. The generation of photons in the laser diode is modeled by spontaneous and stimulated recombination terms appearing in the transport equations. The devices are coupled to the circuit by the semiconductor current entering the circuit and by the applied voltage at the device contacts, coming from the circuit. The resulting time-dependent model is a system of nonlinear partial differential-algebraic equations. The one-dimensional transient transport equations are numerically discretized in time by the backward Euler method and in space by a hybridized mixed finite-element method. Numerical results for a circuit consisting of a single-mode heterostructure laser diode, a silicon photo diode, and a high-pass filter are presented.

APA, Harvard, Vancouver, ISO, and other styles

30

Bibilo, P. N., and V. I. Romanov. "Experimental Study of Algorithms for Minimization of Binary Decision Diagrams using Algebraic Representations of Cofactors." Programmnaya Ingeneria 13, no. 2 (February 17, 2022): 51–67. http://dx.doi.org/10.17587/prin.13.51-67.

Full text

Abstract:

BDD (Binary Decision Diagram) is used for technology-independent optimization, performed as the first stage in the synthesis of logic circuits in the design of ASIC (application-specific integrated circuit). BDD is an acyclic graph defining a Boolean function or a system of Boolean functions. Each vertex of this graph is associated with the complete or reduced Shannon expansion formula. Binary decision diagrams with mutually inverse subfunctions (cofac-tors) are considered. We have developed algorithms for finding algebraic representations of cofactors of the same BDD level in the form of a disjunction or conjunction of other inverse or non-inverse cofactors of the same BDD level. The algorithms make it possible to reduce the number of literals by replacing the Shannon expansion formulas with simpler logical formulas and to reduce the number of literals in the description of a system of Boolean functions. We propose to use the developed algorithms for an additional logical optimization of the constructed BDD representations of systems of Boolean functions. Experimental results of the application of the corresponding programs in the synthesis of logic circuits in the design library of custom VLSI CMOS circuits are presented.

APA, Harvard, Vancouver, ISO, and other styles

31

Upadhyaya, Devanshi, Maël Gay, and Ilia Polian. "Locking-Enabled Security Analysis of Cryptographic Circuits." Cryptography 8, no. 1 (January 5, 2024): 2. http://dx.doi.org/10.3390/cryptography8010002.

Full text

Abstract:

Hardware implementations of cryptographic primitives require protection against physical attacks and supply chain threats. This raises the question of secure composability of different attack countermeasures, i.e., whether protecting a circuit against one threat can make it more vulnerable against a different threat. In this article, we study the consequences of applying logic locking, a popular design-for-trust solution against intellectual property piracy and overproduction, to cryptographic circuits. We show that the ability to unlock the circuit incorrectly gives the adversary new powerful attack options. We introduce LEDFA (locking-enabled differential fault analysis) and demonstrate for several ciphers and families of locking schemes that fault attacks become possible (or consistently easier) for incorrectly unlocked circuits. In several cases, logic locking has made circuit implementations prone to classical algebraic attacks with no fault injection needed altogether. We refer to this “zero-fault” version of LEDFA by the term LEDA, investigate its success factors in-depth and propose a countermeasure to protect the logic-locked implementations against LEDA. We also perform test vector leakage assessment (TVLA) of incorrectly unlocked AES implementations to show the effects of logic locking regarding side-channel leakage. Our results indicate that logic locking is not safe to use in cryptographic circuits, making them less rather than more secure.

APA, Harvard, Vancouver, ISO, and other styles

32

Essert, Mario, and Darko Žubrinić. "Šare’s algebraic systems." Acta mathematica Spalatensia 2 (December 1, 2022): 1–28. http://dx.doi.org/10.32817/ams.2.1.

Full text

Abstract:

We study algebraic systems MΓ of free semigroup structure, where Γ is a well ordered finite alphabet, discovered in 1970s within the Theory of Electric Circuits by Miro Šare, and and finding recent recent applications in Multivalued Logic, as well as in Computational Linguistics. We provide three simple axioms (reversion axiom (5) and two compression axioms (6) and (7)), which generate the corresponding equivalence relation between words. We also introduce a class of incompressible words, as well as the quotient Šare system MΓ~. The main result is contained in Theorem 16, announced by Šare without proof, which characterizes the equivalence of two words by means of Šare sums. The proof is constructive. We describe an algorithm for compression of words, study homomorphisms between quotient Šare systems for various alphabets Γ (Theorem 38), and introduce two natural Šare categories ŠŠa(M) and ŠŠa(M~). Šare systems are not inverse semigroups.

APA, Harvard, Vancouver, ISO, and other styles

33

Rakai, L., A. Farshidi, L. Behjat, and D. Westwick. "A New Length-Based Algebraic Multigrid Clustering Algorithm." VLSI Design 2012 (May 23, 2012): 1–14. http://dx.doi.org/10.1155/2012/395260.

Full text

Abstract:

Clustering algorithms have been used to improve the speed and quality of placement. Traditionally, clustering focuses on the local connections between cells. In this paper, a new clustering algorithm that is based on the estimated lengths of circuit interconnects and the connectivity is proposed. In the proposed algorithm, first an a priori length estimation technique is used to estimate the lengths of nets. Then, the estimated lengths are used in a clustering framework to modify a clustering technique based on algebraic multigrid (AMG), that finds the cells with the highest connectivity. Finally, based on the results from the AMG-based process, clusters are made. In addition, a new physical unclustering technique is proposed. The results show a significant improvement, reductions of up to 40%, in wire length can be achieved when using the proposed technique with three academic placers on industry-based circuits. Moreover, the runtime is not significantly degraded and can even be improved.

APA, Harvard, Vancouver, ISO, and other styles

34

NAKATA, YOSHIFUMI, and MIO MURAO. "DIAGONAL-UNITARY 2-DESIGN AND THEIR IMPLEMENTATIONS BY QUANTUM CIRCUITS." International Journal of Quantum Information 11, no. 07 (October 2013): 1350062. http://dx.doi.org/10.1142/s0219749913500627.

Full text

Abstract:

We study efficient generations of random diagonal-unitary matrices, an ensemble of unitary matrices diagonal in a given basis with randomly distributed phases for their eigenvalues. Despite the simple algebraic structure, they cannot be achieved by quantum circuits composed of a few-qubit diagonal gates. We introduce diagonal-unitaryt-designs and present two quantum circuits that implement diagonal-unitary 2-design with the computational basis in N-qubit systems. One is composed of single-qubit diagonal gates and controlled-phase gates with randomized phases, which achieves an exact diagonal-unitary 2-design after applying the gates on all pairs of qubits. The number of required gates is N(N - 1)/2. If the controlled-Z gates are used instead of the controlled-phase gates, the circuit cannot achieve an exact 2-design, but achieves an ϵ-approximate 2-design by applying gates on randomly selected pairs of qubits. Due to the random choice of pairs, the circuit obtains extra randomness and the required number of gates is at most O(N2(N + log 1/∊)). We also provide an application of the circuits, a protocol of generating an exact 2-design of random states by combining the circuits with a simple classical procedure requiring O(N) random classical bits.

APA, Harvard, Vancouver, ISO, and other styles

35

Hemaspaandra, Lane A. "SIGACT News Complexity Theory Column 113." ACM SIGACT News 53, no. 2 (June 10, 2022): 39. http://dx.doi.org/10.1145/3544979.3544988.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Glaßer, Christian, Christian Reitwießner, Stephen Travers, and Matthias Waldherr. "Satisfiability of algebraic circuits over sets of natural numbers." Discrete Applied Mathematics 158, no. 13 (July 2010): 1394–403. http://dx.doi.org/10.1016/j.dam.2010.04.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Dewilde, Patrick. "New algebraic methods for modelling large-scale integrated circuits." International Journal of Circuit Theory and Applications 16, no. 4 (October 1988): 473–503. http://dx.doi.org/10.1002/cta.4490160410.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

RIAZA, RICARDO. "GRAPH-THEORETIC CHARACTERIZATION OF BIFURCATION PHENOMENA IN ELECTRICAL CIRCUIT DYNAMICS." International Journal of Bifurcation and Chaos 20, no. 02 (February 2010): 451–65. http://dx.doi.org/10.1142/s0218127410025533.

Full text

Abstract:

This paper addresses bifurcation properties of equilibria in lumped electrical circuits. The goal is to tackle these properties in circuit-theoretic terms, characterizing the bifurcation conditions in terms of the underlying network digraph and the electrical features of the circuit devices. The attention is mainly focused on so-called singular bifurcations, resulting from the semistate (differential-algebraic) nature of circuit models, but the scope of our approach seems to extend to other types of bifurcations. The bifurcation analysis combines different tools coming from graph theory (such as proper trees in circuit digraphs, Maxwell's determinantal expansions or the colored branch theorem) with several results from linear algebra (matrix pencils, the Cauchy–Binet formula, Schur complements). Several examples illustrate the results.

APA, Harvard, Vancouver, ISO, and other styles

39

Tykhovod, S. M., T. YE Dyvchuk, T. P. Solodovnikova, and O. V. Sytik. "Spectral method of electrical circuits accelerated simulation with thyristors." Electrical Engineering and Power Engineering, no. 2 (September 15, 2023): 27–31. http://dx.doi.org/10.15588/1607-6761-2023-02-03.

Full text

Abstract:

Purpose. The development of transient processes calculation method in electric circuits with thyristors based on the use of functions approximation by orthogonal polynomials. Methodology. Functions approximation by orthogonal polynomials, numerical methods of differential equations integration, matrix methods, programming, theory of electric circuits. Obtained results. The method of solution function polynomial approximation of integro-differential equations of state, which describes the transient processes of an electric circuit with thyristors, is used in this paper. The used method showed the advantages over other known methods in increasing the accuracy and reducing the simulation time of transient electrical processes by more than 6 times. Findings. The solution is approximated by a series of Chebyshev polynomials. The integro-differential equations of state are transformed into linear algebraic equations for special depiction of the solution functions. The depiction of functions of true currents in the equivalent circuit is interpreted as direct currents. Such a schematic model creates visibility for a researcher performing simulation of transient electrical processes. Practical value. The proposed methods discover the possibility of using the apparatus of direct current electric circuits’ theory for transient processes in complex schemes modeling with thyristors.

APA, Harvard, Vancouver, ISO, and other styles

40

Elliott, Conal. "Timely Computation." Proceedings of the ACM on Programming Languages 7, ICFP (August 30, 2023): 895–919. http://dx.doi.org/10.1145/3607861.

Full text

Abstract:

This paper addresses the question “what is a digital circuit?” in relation to the fundamentally analog nature of actual (physical) circuits. A simple informal definition is given and then formalized in the proof assistant Agda. At the heart of this definition is the timely embedding of discrete information in temporally continuous signals. Once this embedding is defined (in constructive logic, i.e., type theory), it is extended in a generic fashion from one signal to many and from simple boolean operations (logic gates) to arbitrarily sophisticated sequential and parallel compositions, i.e., to computational circuits. Rather than constructing circuits and then trying to prove their correctness, a compositionally correct methodology maintains specification, implementation, timing, and correctness proofs at every step. Compositionality of each aspect and of their combination is supported by a single, shared algebraic vocabulary and related by homomorphisms. After formally defining and proving these notions, a few key transformations are applied to reveal the linearity of circuit timing (over a suitable semiring), thus enabling practical, modular, and fully verified timing analysis as linear maps over higher-dimensional time intervals. An emphasis throughout the paper is simplicity and generality of specification, minimizing circuit-specific definitions and proofs while highlighting a broadly applicable methodology of scalable, compositionally correct engineering through simple denotations and homomorphisms.

APA, Harvard, Vancouver, ISO, and other styles

41

Pandey, Anurag, Nitin Saxena, and Amit Sinhababu. "Algebraic independence over positive characteristic: New criterion and applications to locally low-algebraic-rank circuits." computational complexity 27, no. 4 (May 14, 2018): 617–70. http://dx.doi.org/10.1007/s00037-018-0167-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

GUGLIELMI, NICOLA. "INEXACT NEWTON METHODS FOR THE STEADY STATE ANALYSIS OF NONLINEAR CIRCUITS." Mathematical Models and Methods in Applied Sciences 06, no. 01 (February 1996): 43–57. http://dx.doi.org/10.1142/s0218202596000043.

Full text

Abstract:

In this paper numerical problems arising from steady state analysis of nonlinear circuits with quasiperiodic excitation are discussed. The approach we consider is based on the piecewise harmonic balance techniques8,9 (HB), a methodology which has its theoretical foundations in Galerkin's procedure (see the paper by Urabe12). The original problem, which can be expressed in the form of a system of integro-differential equations in the time domain, is changed into a nonlinear algebraic system through a natural projection technique. Thus, one of the main issues we have investigated consists in the numerical solution of the specific nonlinear algebraic problem.

APA, Harvard, Vancouver, ISO, and other styles

43

Matveenko, Valerii, Maksim Iurlov, Dmitrii Oshmarin, Nataliya Sevodina, and Nataliia Iurlova. "Modelling of vibrational processes in systems with piezoelements and external electric circuits on the basis of their electrical analogue." Journal of Intelligent Material Systems and Structures 29, no. 16 (June 11, 2018): 3254–65. http://dx.doi.org/10.1177/1045389x18781025.

Full text

Abstract:

The dissipative properties of electromechanical systems based on structure with elements made of piezomaterial can be controlled by attaching external electric circuits to the piezoelements. One can change electric circuit parameters in such a way as to ensure the greatest possible energy dissipation on an external electric circuit and, thereby, the best damping of the system’s specified oscillation frequency. Since the external electric circuits are a collection of elements with lumped parameters attached to a system with distributed parameters, the solution for such a system of electro-viscoelasticity problems in the complete formulation by the finite element method leads to a large solving system of algebraic equations. The solution of this system requires considerable time and computational resources. There are known approaches in mechanics that make it possible to represent mechanical systems with distributed parameters in the form of discrete systems with lumped parameters, such as a spring–mass–damper. In this article, it is proposed to model electromechanical systems with external electric circuits based on their electrical analogue in the form of equivalent electric substitution circuits, which are discrete electrical systems with lumped parameters. These discrete systems are analogues of the initial electromechanical systems in terms of frequency characteristics and the electrical processes that take place in them. The equivalent substitution circuit is based on the Van Dyke model and allows one to obtain the required number of complex eigenfrequencies of the electromechanical system under consideration.

APA, Harvard, Vancouver, ISO, and other styles

44

PULCH, ROLAND, MICHAEL GÜNTHER, and STEPHANIE KNORR. "Multirate partial differential algebraic equations for simulating radio frequency signals." European Journal of Applied Mathematics 18, no. 6 (December 2007): 709–43. http://dx.doi.org/10.1017/s0956792507007188.

Full text

Abstract:

In radio frequency (RF) applications, electric circuits produce signals exhibiting fast oscillations, whereas the amplitude and frequency may change slowly in time. Thus, solving a system of differential algebraic equations (DAEs), which describes the circuit's transient behaviour, becomes inefficient, since the fast rate restricts the step sizes in time. A multivariate model is able to decouple the widely separated time scales of RF signals and provides an alternative approach. Consequently, a system of DAEs changes into a system of multirate partial differential algebraic equations (MPDAEs). The determination of multivariate solutions allows for the exact reconstruction of corresponding time-dependent signals. Hence, an efficient numerical simulation is obtained by exploiting the periodicities in fast time scales. We outline the theory of this multivariate approach with respect to the simulation of amplitude as well as frequency modulated signals. Furthermore, a survey of numerical methods for solving the arising problems of MPDAEs is given.

APA, Harvard, Vancouver, ISO, and other styles

45

Ghosal, Purnata, and B. V. Raghavendra Rao. "On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models." Fundamenta Informaticae 177, no. 1 (December 18, 2020): 69–93. http://dx.doi.org/10.3233/fi-2020-1980.

Full text

Abstract:

We consider the problem of obtaining parameterized lower bounds for the size of arithmetic circuits computing polynomials with the degree of the polynomial as the parameter. We consider the following special classes of multilinear algebraic branching programs: 1) Read Once Oblivious Branching Programs (ROABPs), 2) Strict interval branching programs, 3) Sum of read once formulas with restricted ordering. We obtain parameterized lower bounds (i.e., nΩ(t(k)) lower bound for some function t of k) on the size of the above models computing a multilinear polynomial that can be computed by a depth four circuit of size g(k)nO(1) for some computable function g. Further, we obtain a parameterized separation between ROABPs and read-2 ABPs. This is obtained by constructing a degree k polynomial that can be computed by a read-2 ABP of small size such that the rank of the partial derivative matrix under any partition of the variables is large.

APA, Harvard, Vancouver, ISO, and other styles

46

Romaniuk, Roman. "The implementation of the method of reduced matrix D-trees in the Udf MAOPCs environment." Computational Problems of Electrical Engineering 13, no. 2 (December 15, 2023): 33–36. http://dx.doi.org/10.23939/jcpee2023.02.033.

Full text

Abstract:

The article explores the content of the MatrixDtrees function, which extends the functionality of the UDF MAOPCs and is designed to generate symbolic transfer functions of linear parametric circuits. This function represents a software implementation of the Transformed Matrix D-trees method. This method is an extension of the symbolic d-trees method, developed for constant parameters circuits, to parametric circuits. The extension involves the transition from algebraic operations with numbers and symbols in the d-trees method to matrix algebraic operations, taking into account the non-commutativity of matrix multiplication. The Transformed Matrix D-trees method significantly reduces computational time for modeling parametric circuits by factoring out similarities in complex symbolic expressions generated during the analysis process. The MatrixDtrees function allows for the steady-state analysis in highly complex parametric circuits. By such circuits, we mean circuits that contain dozens or hundreds of nodes and elements (including parametric ones). The article includes the results of analyzing a parametric long line model, which is represented by a combination of lumped parameters and consists of many cascaded elementary sections. Each of these sections is a combination of parametric inductance and constant capacitance. The paper presents the results of an experiment to determine the output voltage of a long line model containing 1025 nodes, 1024 constant capacitances, and 1024 parametric inductances. The results are comparable to calculations of the same long line model using the MicroCap program. The relative deviation between the calculation results for both programs was less than 1%. The calculation time for the Transformed Matrix D-trees method using the MatrixDtrees function was 18 minutes, whereas for the MicroCap program, it was 36 hours.

APA, Harvard, Vancouver, ISO, and other styles

47

Cannas, B., A. Fanni, and A. Montisci. "Algebraic Approach to Ambiguity-Group Determination in Nonlinear Analog Circuits." IEEE Transactions on Circuits and Systems I: Regular Papers 57, no. 2 (February 2010): 438–47. http://dx.doi.org/10.1109/tcsi.2009.2023834.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Grigoriev, Dima, and Marek Karpinski. "Computing the Additive Complexity of Algebraic Circuits with Root Extracting." SIAM Journal on Computing 27, no. 3 (June 1998): 694–701. http://dx.doi.org/10.1137/s0097539793258313.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Avcı, İbrahim. "Spectral collocation with generalized Laguerre operational matrix for numerical solutions of fractional electrical circuit models." Mathematical Modelling and Numerical Simulation with Applications 4, no. 1 (March 31, 2024): 110–32. http://dx.doi.org/10.53391/mmnsa.1428035.

Full text

Abstract:

In this paper, we introduce a pioneering numerical technique that combines generalized Laguerre polynomials with an operational matrix of fractional integration to address fractional models in electrical circuits. Specifically focusing on Resistor-Inductor ($RL$), Resistor-Capacitor ($RC$), Resonant (Inductor-Capacitor) ($LC$), and Resistor-Inductor-Capacitor ($RLC$) circuits within the framework of the Caputo derivative, our approach aims to enhance the accuracy of numerical solutions. We meticulously construct an operational matrix of fractional integration tailored to the generalized Laguerre basis vector, facilitating a transformation of the original fractional differential equations into a system of linear algebraic equations. By solving this system, we obtain a highly accurate approximate solution for the electrical circuit model under consideration. To validate the precision of our proposed method, we conduct a thorough comparative analysis, benchmarking our results against alternative numerical techniques reported in the literature and exact solutions where available. The numerical examples presented in our study substantiate the superior accuracy and reliability of our generalized Laguerre-enhanced operational matrix collocation method in effectively solving fractional electrical circuit models.

APA, Harvard, Vancouver, ISO, and other styles

50

Kaufmann, Daniela, Armin Biere, and Manuel Kauers. "Incremental column-wise verification of arithmetic circuits using computer algebra." Formal Methods in System Design 56, no. 1-3 (February 26, 2019): 22–54. http://dx.doi.org/10.1007/s10703-018-00329-2.

Full text

Abstract:

AbstractVerifying arithmetic circuits and most prominently multiplier circuits is an important problem which in practice still requires substantial manual effort. The currently most effective approach uses polynomial reasoning over pseudo boolean polynomials. In this approach a word-level specification is reduced by a Gröbner basis which is implied by the gate-level representation of the circuit. This reduction returns zero if and only if the circuit is correct. We give a rigorous formalization of this approach including soundness and completeness arguments. Furthermore we present a novel incremental column-wise technique to verify gate-level multipliers. This approach is further improved by extracting full- and half-adder constraints in the circuit which allows to rewrite and reduce the Gröbner basis. We also present a new technical theorem which allows to rewrite local parts of the Gröbner basis. Optimizing the Gröbner basis reduces computation time substantially. In addition we extend these algebraic techniques to verify the equivalence of bit-level multipliers without using a word-level specification. Our experiments show that regular multipliers can be verified efficiently by using off-the-shelf computer algebra tools, while more complex and optimized multipliers require more sophisticated techniques. We discuss in detail our complete verification approach including all optimizations.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Algebraic Circuits'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles