109
votes
Accepted
Why is addition as fast as bit-wise operations in modern processors?
Addition is fast because CPU designers have put in the circuitry needed to make it fast. It does take significantly more gates than bitwise operations, but it is frequent enough that CPU designers ...
D.W.♦
- 156k
43
votes
Why is addition as fast as bit-wise operations in modern processors?
There are several aspects.
The relative cost of a bitwise operation and an addition. A naive adder will have a gate-depth which depend linearly of the width of the word. There are alternative ...
- 3,024
26
votes
Why is addition as fast as bit-wise operations in modern processors?
CPUs operate in cycles. At each cycle, something happens. Usually, an instruction takes more cycles to execute, but multiple instructions are executed at the same time, in different states.
For ...
- 528
13
votes
Accepted
Connection between NAND gates and Turing completeness
There is indeed little connection. For a thorough understanding, let me explain the connection between programs and circuits.
A program (or algorithm, or machine) is a mechanism for computing a ...
- 275k
13
votes
Why is addition as fast as bit-wise operations in modern processors?
Processors are clocked, so even if some instructions can clearly be done faster than others, they may well take the same number of cycles.
You'll probably find that the circuitry required to ...
- 296
12
votes
Why is addition as fast as bit-wise operations in modern processors?
Addition is important enough to not have it wait for a carry bit to ripple through a 64-bit accumulator: the term for that is a carry-lookahead adder and they are basically part of 8-bit CPUs (and ...
- 121
10
votes
Why is addition as fast as bit-wise operations in modern processors?
I think you'd be hard pressed to find a processor that had addition taking more cycles than a bitwise operation. Partly because most processors must carry out at least one addition per instruction ...
- 411
9
votes
Why is addition as fast as bit-wise operations in modern processors?
At the gate level, you are correct that it takes more work to do addition, and thus takes longer. However, that cost is sufficiently trivial that doesn't matter.
Modern processors are clocked. You ...
- 3,241
8
votes
Full Adder vs. Half Adder
The C's are not the same, but your statement about the AND gate is right.
Unfortunately, the people who drew your full-adder decided to save space instead of maximizing readability. This image does a ...
- 3,241
8
votes
Why is addition as fast as bit-wise operations in modern processors?
Modern processors are clocked: Every operation takes some integral number of clock cycles. The designers of the processor determine the length of a clock cycle. There are two considerations there: One,...
- 28.4k
6
votes
Connection between NAND gates and Turing completeness
You are in fact correct. A combinational logic circuit is equivalent to a finite automaton. NAND gates do not make them more powerful; they are used because it is simply cheaper to build a digital ...
- 203
6
votes
Why is addition as fast as bit-wise operations in modern processors?
Let me correct a few things that were not mentioned that explicitely in your existing answers:
I know that bitwise operations are so fast on modern processors, because they can operate on 32 or 64 ...
- 1,273
5
votes
Accepted
Ripple Carry Adder
You're misinterpreting the action of a ripple-carry adder. Each of the two boxed circuits takes in two 1-bit numbers (the top two inputs) and a carry bit (the left input) and returns a sum bit (the ...
- 14.8k
4
votes
Accepted
Why is c) a combinational circuit, but d) not?
A combinatorial circuit corresponds to a "straight-line program" that computes the outputs of the circuit given its inputs. (It has to satisfy some constraints that will exclude circuit (f) ...
- 275k
4
votes
Accepted
Algorithm for simplifying ANF or polynomials?
The algebraic normal form (ANF) is unique. You can't "simplify" the ANF; each formula has a single, unique ANF, and there's only one. Once you've found it, that's it; there's no other, "simpler" ANF ...
D.W.♦
- 156k
4
votes
Accepted
Algorithms for logical synthesis of multiple output bits?
as you realize, while universal, Quine-Mcclusky is only a "bitwise" construction method (single bit output) that does not recognize/ exploit common subpatterns for multibit outputs. multibit function ...
- 11k
4
votes
Is it possible to determine if C=A+B faster than adding A+B in logical circuits
Consider computing $\overline{a_{n-1}\ldots a_0}+\overline{b_{n-1}\ldots b_0}=\overline{c_{n-1}\ldots c_0}$. If the last $(k+1)$-bits are correctly computed, then $c_{k+1}$ is correct if and only if
$$...
- 1,173
4
votes
Trick/insight to I implement given boolean function with minimum numbers of given gate
There is no trick. There is no efficient method. The circuit minimization problem is NP-hard (in fact $\Sigma_2^P$-hard), and I suspect that finding the smallest circuit with only NAND gates is NP-...
D.W.♦
- 156k
4
votes
Accepted
Proof of universality in the circuit model
I'm sure you are aware of the following problem: Turing-Machines can't compute any Boolean function. E.g. there is no such TM that prints $0$ if the input TM does not halt and $1$ if it halts (halting ...
- 1,589
3
votes
Accepted
Using analog values with Algebraic Normal Form?
Perhaps the most appropriate way of thinking of algebraic normal form is as the following statement:
Every function from $\mathbb{Z}_2^n$ to $\mathbb{Z}_2$ can be represented uniquely as a ...
- 275k
3
votes
Accepted
Physical significance of Don't cares in Digital Logic design
Yes they do have physical significance.Input combinations for which value of a function ( or a device) is not specified are called don't care conditions.
They are met when the number of inputs are ...
- 838
3
votes
Accepted
Determining whether a digital circuit is optimal
Use one of the standard techniques for circuit minimization. As far as I know, verifying that a candidate circuit is minimal is as hard as finding the minimal circuit in the first place (I know of no ...
D.W.♦
- 156k
3
votes
Accepted
Adder circuit with sign bit (not twos complement)
This is called "sign-magnitide" or "signed-magnitude" representation. A Google search for "sign-magnitude adder" gives lots of useful results. I know this doesn't answer your question directly (I don'...
- 106
3
votes
Is there a canonical form that uses AND and XOR?
Yes. You want algebraic normal form. Every formula in algebraic normal form has the form of an xor of products.
Because xor is the same as addition when working modulo 2 (i.e., when working in the ...
D.W.♦
- 156k
3
votes
Accepted
Is there a canonical form that uses AND and XOR?
You're looking for Reed-Müller forms. The introduction to this paper summarizes some families of these forms:
An arbitrary n-variable function $f(x_1,x_2,...,x_n)$ can be represented using the ...
- 150
3
votes
Accepted
How does a register remember value?
Registers can be thought of as collections of flip-flops. These have inputs which, when activated, change the stored value. When not activated, the stored value stays the same. Look at the truth ...
- 275k
3
votes
Do Karnaugh maps yield the simplest solution possible?
Karnaugh maps do not always give the simplest expression possible, but they do always give the simplest "Sum of Products" expression possible (https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/...
- 1,328
3
votes
What is Control ROM and Decision ROM?
This terminology is some 30 or more years old coming from the times when Read-only memory (ROM) was a way to implement functions as a cheaper alternative than a general purpose processor. In 1980s ...
- 1,409
2
votes
D - Latch or D Flip Flop?
This feels like a homework question, but I'll at least try to point you in the right direction.
The difference between a latch and a flip-flop is that a flip-flop is clocked. At first glance, I ...
- 121
Only top scored, non community-wiki answers of a minimum length are eligible