Combinational logic and Arithmetics
2022-2025
We often use electrical signal to transport and store information.
Those quantities are Analog, i.e. continuous range of amplitudes and continuous during time.
We use electricity to transmit, process or store information because we can measure and generate electrical signals. We can control and current, voltage, frequencies… which made it possible to build circuits to transmit, process and store information.
Other physical phenomenon can be used, as light for transmission over optical fibers, but designing operators to process optical signals are hard/impossible to design.
The information is discrete, i.e. we can store it and transport with a finite number of distinct values during time (Niyquist-Shannon theory). Thus, we can limit the signal to:
Those specific amplitudes can be represented as numbers (or digits) and processed without loosing information.
Logical values correspond to a range of voltages. This allows to be resilient to a certain amount of noise.
For multilevel digital signals, we will use several binary signals.
Modern solid-state electronics.
Imagine we can build a controlled switch with the following behaviour:
| V_{in} | state |
|---|---|
| <V_t | open |
| >V_t | closed |
With a resistor and that controlled switch, we can design an inverter.
The issue with this is that when the switch is closed, we have a path from the power supply to the ground and thus a continuous current. This leads to a continuous power consumption for one of the logical states.
MOS stands for Metal-Oxide-Semiconductor. MOS transistors will be presented with a little more details in another lesson.
nMOS
N-channel MOS Transistors.
pMOS
P-channel MOS Transistors.
Complementary transistors are used together to unsure that no current path exists between the power supply and the ground when the output is in a stable logical state.
Complementary transistors to avoid continuous path from V_{dd} to V_{ss} for all logic states.
| i | V_i | nMOS | pMOS | V_o | o |
|---|---|---|---|---|---|
| 0 | 0V | open | closed | V_{dd} | 1 |
| 1 | V_{dd} | closed | open | 0V | 0 |
There is no direct conductivity path between the power supply and the ground for stable logical states. Thus, no static continuous power consumption.
A path may exist during the transition from one logical state to the other which may lead to a dynamic power consumption. Also, MOS transistors are not perfect switches and some leakage current my exist.
nAND
nOR
We can build more complex gates by constructing two complementary networks.
To have a valid logical gate, the two networks must be complementary, and can neither be both close (we will have a shortcut) nor open (we will have a floating node).
Note also that CMOS gates are inverting gates. Non inverting gates are often more complex to design. For example, a buffer will be composed of two chained inverters.
As an example, propose a structure for a XOR gate.
Even thought CMOS is the most common technology used to build logical gates, it is not the sole. Other technologies have been used or are still in used in specific fields to achieve this purpose.
In what follows, we will describe more abstract logical operators that will be used to construct complex operators. Still, you have to remember that what ever abstraction level we are using, at bottom, there is always a physical device that will implement the function.
| i | o |
|---|---|
| 0 | 1 |
| 1 | 0 |
o = \overline{i}
The simplest CMOS logic gate.
| i | o |
|---|---|
| 0 | 0 |
| 1 | 1 |
o = i
The output of a buffer is an electrically regenerated version of the input. A simple wire would not regenerate the signal.
| a | b | o |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
o = a \cdot b
| a | b | o |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
o = a + b
| a | b | o |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
o = \overline{a \cdot b}
| a | b | o |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
o = \overline{a + b}
| a | b | o |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
\begin{split} o & = a \oplus b \\ o & = a \cdot \overline{b} + \overline{a} \cdot b \end{split}
The XOR boolean function can also be interpreted as:
| a | b | o |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
\begin{split} o & = \overline{a \oplus b} \\ o & = \overline{a} \cdot \overline{b} + a \cdot b \end{split}
The XNOR boolean function can also be interpreted as:
For more complex combinational functions?
The output value o depends on a selection input
s:
s is high, the value of o is the value
of ao is the value of b| s | a | b | o |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
The sum of products canonical form can be obtained by summing the minterms for witch the output is true (high).
o = \overline{s} \cdot \overline{a} \cdot {b} + \overline{s} \cdot {a} \cdot {b} + {s} \cdot {a} \cdot \overline{b} + {s} \cdot {a} \cdot {b}
This equation can be simplified to:
o = \overline{s} \cdot b + s \cdot a
Writing the truth table of a Combinational Function is only feasible if the number of inputs is limited. Otherwise, analytic equations and the rules of Boolean Algebra can be used.
We will also see that with Hardware Description Languages (HDL) it is easier to express complex function by describing their behaviour using computer aided tools.
Example : The 2\rightarrow 4 decoder
2-bit intput I = (i_1,i_0)
4-bit output O = (o_3,o_2,o_1,o_0)
For each input value, only one bit of the output is high.
| i_1 | i_0 | o_3 | o_2 | o_1 | o_0 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 |
\begin{split} o_0 = \overline{i_1} \cdot \overline{i_0} \\ o_1 = \overline{i_1} \cdot {i_0} \\ o_2 = {i_1} \cdot \overline{i_0} \\ o_3 = {i_1} \cdot {i_0} \end{split}
The outputs of a decoder are individual miterms. Decoders can be used as building blocks for other combinational functions.
Let’s go back to nubmers.
Natural representation on integer numbers.
Base 10 representation.
A = 1234 = 1\times1000 + 2 \times 100 + 3 \times 10 + 1 \times 1
A = \sum_{i=0}^{n-1} d_i \cdot 10^i
Base 2 representation.
A = 1010 = 1 \times 8 + 0 \times 4 + 1 \times 2 + 0 \times 1
For a fixed n-bit representation:
\begin{split} A & = (b_{n-1},\dots,b_0)_2\\ A & = \sum_{i=0}^{n-1} b_i \cdot 2^i\\ A & \in [0,2^n -1] \end{split}
Base 16 representation.
A = 12AF = 1 \times 4096 + 2 \times 256 + 10 \times 16 + 15 \times 1
A = \sum_{i=0}^{n-1} d_i \cdot 16^i
Hexadecimal representation is used as a compact representation of binary numbers.
(b_3 b_2 b_1 b_0)_2 = b_3\cdot 8 + b_2\cdot 4 + b_1 \cdot 2 + b_0 \cdot 1 \in [0:15]
| binary | hex |
|---|---|
| 0000 | 0 |
| 0001 | 1 |
| 0010 | 2 |
| 0011 | 3 |
| 0100 | 4 |
| 0101 | 5 |
| 0110 | 6 |
| 0111 | 7 |
| 1000 | 8 |
| 1001 | 9 |
| 1010 | a |
| 1011 | b |
| 1100 | c |
| 1101 | d |
| 1110 | e |
| 1111 | f |
\begin{split} A & = (b_{n-1},\dots,b_0)_2\\ A & = -2^{n-1}\cdot b_{n-1} + \sum_{i=0}^{n-2} b_i \cdot 2^i\\ A & \in [-2^{n-1},2^{n-1} -1] \end{split}
| binary | unsigned | Two’s Complement |
|---|---|---|
| 0000 | 0 | 0 |
| 0001 | 1 | 1 |
| 0010 | 2 | 2 |
| 0011 | 3 | 3 |
| 0100 | 4 | 4 |
| 0101 | 5 | 5 |
| 0110 | 6 | 6 |
| 0111 | 7 | 7 |
| 1000 | 8 | -8 |
| 1001 | 9 | -7 |
| 1010 | 10 | -6 |
| 1011 | 11 | -5 |
| 1100 | 12 | -4 |
| 1101 | 13 | -3 |
| 1110 | 14 | -2 |
| 1111 | 15 | -1 |
-1 \equiv 15 [16]
signed -1 + 1 = 0
unsigned (15 + 1)[16] = 0
From Logic to arithmetic.
The addition algorithm?
How do you compute:
999
+ 1
-----
=How do you compute:
1110 (14)
+ 10 (2)
-----
=2 \times c_o + s = c_i + a + b
| c_o | s | c_i | a | b |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
\begin{split} s & = a \oplus b \oplus c_i\\ c_o & = a \cdot b + a \cdot c_i + b \cdot c_i \end{split}
For a n-bit addition we can chain n Full-adders.
The result of the addition between two n-bit numbers is a (n+1)-bit number (sum plus carry).
\begin{split} 0 \le A & < 2^n\\ 0 \le B & < 2^n\\ 0 \le A+B & < 2^{n+1} \end{split}
The same for signed representation.
\begin{split} -2^{n-1} \le A < 2^{n-1}\\ -2^{n-1} \le B < 2^{n-1}\\ -2^n \le A+B < 2^{n} \end{split}
When building hardware operators it is important to know the valid ranges of all intermediary results along the data path.
Use the methodology used to design the unsigned addition operator to design a subtraction operator.
It is possible to use the representation of n-bit signed numbers to build a subtraction operator using a standard addition operator.
\begin{split} D & = A - B\\ D & = A + (-B) \end{split}
Can we build a controlled operator that can compute either the sum or the difference depending on the value of a binary control signal?
Check that “1 \oplus x = \overline{x}” for a 1-bit signal x then propose an optimisation of this controlled operator.
Can we use the same methodology to design a Combinational Multiplication Operator?
bin dec
A | 0101 | 5
B | 1010 | 10
-----------------
AxB |Solution
A | 0101 (5)
B | 1010 (10)
-----------------
0000 b0xA
+ 0101. b1xA<<1
+ 0000.. b2xA<<2
+ 0101... b3xA<<3
-----------------
00110010 (50)| a_i | b_i | a_i \times b_i |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
It is an AND gate!
a_i \times b_i = a_i \cdot b_i
\begin{split} A & = \sum_{i=0}^{3} a_i \cdot 2^i\\ B & = \sum_{i=0}^{3} b_i \cdot 2^i\\ \end{split}
Thus:
A \times B = \sum_{i=0}^{3}(\sum_{j=0}^{3} a_i \cdot b_i \cdot 2^{i+j})
Or, if reorganized by powers of 2:
\begin{split} A \times B & = (a_3 \cdot b_3) \cdot 2^6 \\ &+ (a_2 \cdot b_3 + a_3 \cdot b_2 ) \cdot 2^5 \\ &+ (a_1 \cdot b_3 + a_2 \cdot b_2 + a_3 \cdot b_1) \cdot 2^4 \\ &+ (a_0 \cdot b_3 + a_1 \cdot b_2 + a_2 \cdot b_1 + a_3 \cdot b_0 ) \cdot 2^3 \\ &+ (a_0 \cdot b_2 + a_1 \cdot b_1 + a_2 \cdot b_0) \cdot 2^2 \\ &+ (a_0 \cdot b_1 + a_1 \cdot b_0 ) \cdot 2^1\\ &+ (a_0 \cdot b_0) \cdot 2^0\\ \end{split}
We need to:
| © Copyright 2022-2025, Tarik Graba, Télécom Paris. | |
|
Le contenu de cette page est mis à disposition selon les termes de la licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International. |
| The content of this page is licensed under a Creative Commons Attribution-ShareAlike 4.0 International Licence. | |