Difference between revisions of "Digital Electronics"

From ACSL Category Descriptions
Jump to navigation Jump to search
 
(44 intermediate revisions by 4 users not shown)
Line 1: Line 1:
This topic is an extension of the topic of [[Boolean Algebra]] which includes a more thorough description of the category in terms of determining whether a circuit results in a TRUE or FALSE value using truth tables or how to simplify a circuit to as few gates as possible.  Electrical engineers use the following symbols to design electrical circuits that are used inside the computer’s hardware.  The following table illustrates the equivalent Boolean algebra expression and truth table for each gate.
A digital circuit is constructed from logic gates. Each logic gate performs a function of boolean logic based on its inputs, such as AND or OR.
Each circuit can be represented as a Boolean Algebra expression;
this topic is an extension of the topic of [[Boolean Algebra]], which includes  
a thorough description of truth tables and simplifying expressions.  


= Definitions =
= Definitions =


::{| class="wikitable" style="text-align: left"
The following table illustrates all logic gates. For each logic gate, the
table shows the equivalent Boolean algebra expression and truth table.
 
{| class="wikitable" style="text-align: left"
|-
|-
!'''NAME'''
!'''NAME'''
Line 11: Line 17:
|-
|-
!'''BUFFER'''
!'''BUFFER'''
| Symbol
| [[File:Buffer-gate-en.svg|128px]]
| X = A
| X = A
|
|
{| class="wikiTable"
{| class="wikitable" style="text-align: center"
|-
|-
! X || A
|style="background-color: #cceeff; font-size: x-small" "|INPUT
|style="background-color: #cceeff; font-size: x-small" "|OUTPUT
|-
|-
| 0 || 0
| 0 || 0
Line 24: Line 31:
|-
|-
!'''NOT'''
!'''NOT'''
| Symbol
| [[File:Not-gate-en.svg|128px]]
| X = <math>\overline{A}</math>  
| X = <math>\overline{A}</math> or  <math>\neg A</math>
|
|
{| class="wikiTable"
{| class="wikitable" style="text-align: center"
|-
|style="background-color: #cceeff; font-size: x-small" "|INPUT
|style="background-color: #cceeff; font-size: x-small" "|OUTPUT
|-
|-
! X || A
! A || X
|-
|-
| 0 || 1
| 0 || 1
Line 37: Line 47:
|-
|-
!'''AND'''
!'''AND'''
| Symbol
| |[[File:And-gate.png|128px]]
| X = <math>AB</math> or <math>A*B</math>  
| X = <math>AB</math> or <math>A \cdot B</math>  
|
|
{| class="wikiTable"
{| class="wikitable" style="text-align: center"
|-
|colspan="2" style="background-color: #cceeff; font-size: x-small" "|INPUT
|colspan="1" style="background-color: #cceeff; font-size: x-small" "|OUTPUT
|-
|-
! A || B || X
! A || B || X
|-
|-
| 0 || 0 || 0
| 0 || 0 || 0
Line 54: Line 67:
|-
|-
!'''NAND'''
!'''NAND'''
| Symbol
| [[File:Nand-gate-en.svg|128px]]
| X = <math>\overline{AB}</math> or <math>\overline{A*B}</math>
| X = <math>\overline{AB}</math> or <math>\overline{A\cdot B}</math>
|
|
{| class="wikiTable"
{| class="wikitable" style="text-align: center"
|-
|colspan="2" style="background-color: #cceeff; font-size: x-small" "|INPUT
|style="background-color: #cceeff; font-size: x-small" "|OUTPUT
|-
|-
! A || B || X
! A || B || X
Line 71: Line 87:
|-
|-
!'''OR'''
!'''OR'''
| Symbol
| [[File:Or-gate-en.svg|128px]]
| X = <math>A+B</math>  
| X = <math>A+B</math>  
|
|
{| class="wikiTable"
{| class="wikitable" style="text-align: center"
|-
|colspan="2" style="background-color: #cceeff; font-size: x-small" "|INPUT
|style="background-color: #cceeff; font-size: x-small" "|OUTPUT
|-
|-
! A || B || X
! A || B || X
Line 88: Line 107:
|-
|-
!'''NOR'''
!'''NOR'''
| Symbol
| [[File:Nor-gate-en.svg|128px]]
| X = <math>\overline{A+B}</math>
| X = <math>\overline{A+B}</math>
|
|
{| class="wikiTable"
{| class="wikitable" style="text-align: center"
|-
|colspan="2" style="background-color: #cceeff; font-size: x-small" "|INPUT
|style="background-color: #cceeff; font-size: x-small" "|OUTPUT
|-
|-
! A || B || X
! A || B || X
Line 105: Line 127:
|-
|-
!'''XOR'''
!'''XOR'''
| Symbol
|[[File:Xor-gate-en.svg|128px]]
| X = <math>A \oplus B</math>
| X = <math>A \oplus B</math>
|
|
{| class="wikiTable"
{| class="wikitable" style="text-align: center"
|-
|colspan="2" style="background-color: #cceeff; font-size: x-small" "|INPUT
|style="background-color: #cceeff; font-size: x-small" "|OUTPUT
|-
|-
! A || B || X
! A || B || X
Line 122: Line 147:
|-
|-
!'''XNOR'''
!'''XNOR'''
| Symbol
| [[File:Xnor-gate-en.svg|128px]]
| X = <math>\overline{A \oplus B}</math>
| X = <math>\overline{A \oplus B} \text{ or } A \odot B</math>
|
|
{| class="wikiTable"
{| class="wikitable" style="text-align: center"
|-
|colspan="2" style="background-color: #cceeff; font-size: x-small" "|INPUT
|style="background-color: #cceeff; font-size: x-small" "|OUTPUT
|-
|-
! A || B || X
! A || B || X
Line 137: Line 165:
| 1 || 1 || 1
| 1 || 1 || 1
|}
|}
|}
Note that there is some ambiguity in the conversion from a diagram to a circuit. For example, is <math>\overline{A+B}</math> an OR gate followed by a NOT gate, or smply
a NOT gate.
=Online Tools=
The [http://www.cburch.com/logisim/index.html Logisim] application is a wonderful tool
for exploring this topic.
Logisim is free to download and use; among its many features is support to automatically draw
a circuit from a Boolean Algebra expression; to simulate the circuit with arbitrary inputs;
and to complete a truth table for the circuit. From the application, you can import the circuit corresponding to the [[#Sample_Problem_1|Sample Problem 1]]
from the file located at [http://www.acsl.org/misc/wiki-digital-electronics-sample1.circ http://www.acsl.org/misc/wiki-digital-electronics-sample1.circ].
There are many YouTube videos that show how to use the Logisim application; including a very nice [https://www.youtube.com/watch?v=cMz7wyY_PxE 4 minute tutorial].


|}
Logisim contains many
additional advanced features that are beyond
the scope of ACSL problems.


= Sample Problems =
=Sample Problems =


== Sample Problem 1 ==
== Sample Problem 1 ==


Find all ordered 4-tuples (A, B, C, D), which make the following circuit FALSE:
Find all ordered triplets (A, B, C) which make the following circuit FALSE:
 
::[[File:NotABorC.svg|200px]]
 
'''Solution:'''
 
One approach to solving this problem is to reason about that inputs and outputs are necessary at each gate. For the circuit to be FALSE, both inputs to the file OR gate must be false. Thus, input C must be FALSE, and the output of the NAND gate must also be false. The NAND gate is false only when both of its inputs are TRUE; thus, inputs A and B must both be TRUE. The final answer is (TRUE, TRUE, FALSE), or (1, 1, 0).
 
Another approach to solving this problem is to translate the circuit into a Boolean Algebra expression and simplify
the expression using the laws of Boolean Algebra. This circuit translates to the Boolean expression <math>\overline{AB}+C</math>. 
To find when this is FALSE we can equivalently find when the <math>\overline{\overline{AB}+C}</math> is TRUE. 
The expression becomes <math>\overline{\overline{AB}}\cdot \overline{C}</math> after applying DeMorgan’s Law.  The double NOT over the AB expression
cancels out, to become <math>AB\overline{C}</math>.  The AND of 3 terms is TRUE when each term is TRUE, or A=1, B=1 and C=0.
 
== Sample Problem 2 ==
 
How many ordered 4-tuples (A, B, C, D) make the following circuit TRUE?
 
::[[File:circuit-sample2.svg |400px]]
 
'''Solution:'''


[["f:\ACSl Category Descriptions\Pictures\de s1.png]]
We'll use a truth table to solve this problem. The rows in the truth table will correspond to all possible inputs - 16 in this case, since there are 4 inputs. The output columns will be the output of each gate, other than the NOT gates. The diagram below labels each of the gates; it's useful to keep the column straight when working the truth table.


Solution: This circuit diagram translates to: <math>(\overline{C+D}+B) \oplus (\overline{A}B) \oplus (\overline{C+D})</math>.
::[[File:circuit-sample2-labels.svg |300px]]
The table has the following headings: 1=<math>\overline{C+D}</math>, 2=<math>1+\overline{B}</math>, 3=<math>\overline{A}B</math>, 4=<math>A \oplus B</math>, and 5=<math>4 \oplus 1</math>.  Thus, the  4-tuples (0,0,0,0), (1,0,0,0), (1,1,0,0), (1,1,0,1), (1,1,1,0), and (1,1,1,1) all make the circuit FALSE.


{| class="wikitable" style="text-align: center"
{| class="wikitable" style="text-align: center"
|-
|-
!<math>A</math>
|colspan="4" style="background-color: #cceeff; font-size: x-small" "|INPUT
!<math>B</math>
|colspan="5" style="background-color: #cceeff; font-size: x-small" "|OUTPUT
!<math>C</math>
|-
!<math>D</math>
!rowspan="2" | A
!<math>1</math>
!rowspan="2" | B
!<math>2</math>
!rowspan="2" | C
!<math>3</math>
!rowspan="2" | D
!<math>4</math>
!  p
!<math>5</math>
!  q
!  r
!  s
!  t
|-
!<math>\overline{C+D}</math>
!<math>p+\overline{B}</math>
!<math>\overline{A}B</math>
!<math>r \oplus q</math>
!<math>s \oplus p</math>
|-
|-
|0
|0 || 0 || 0 || 0 || 1 || 1 || 0 || 1 || 0
|0
|0
|0
|1
|1
|0
|1
|0
|-
|-
|0
|0 || 0 || 0 || 1 || 0 || 1 || 0 || 1 || 1
|0
|0
|1
|0
|1
|0
|1
|1
|-
|-
|0
|0 || 0 || 1 || 0 || 0 || 1 || 0 || 1 || 1
|0
|1
|0
|0
|1
|0
|1
|1
|-
|-
|0
|0 || 0 || 1 || 1 || 0 || 1 || 0 || 1 || 1
|0
|1
|1
|0
|1
|0
|1
|1
|-
|-
|0
|0 || 1 || 0 || 0 || 1 || 1 || 1 || 0 || 1
|1
|0
|0
|1
|1
|1
|0
|1
|-
|-
|0
|0 || 1 || 0 || 1 || 0 || 0 || 1 || 1 || 1
|1
|0
|1
|0
|0
|1
|1
|1
|-
|-
|0
|0 || 1 || 1 || 0 || 0 || 1 || 1 || 1 || 1
|1
|1
|0
|0
|1
|1
|1
|1
|-
|-
|0
|0 || 1 || 1 || 1 || 0 || 0 || 1 || 1 || 1
|1
|1
|1
|0
|0
|1
|1
|1
|-
|-
|1
|1 || 0 || 0 || 0 || 1 || 1 || 0 || 1 || 0
|0
|0
|0
|1
|1
|0
|1
|0
|-
|-
|1
|1 || 0 || 0 || 1 || 0 || 1 || 0 || 1 || 1
|0
|0
|1
|0
|1
|0
|1
|1
|-
|-
|1
|1 || 0 || 1 || 0 || 0 || 1 || 0 || 1 || 1
|0
|1
|0
|0
|1
|0
|1
|1
|-
|-
|1
|1 || 0 || 1 || 1 || 0 || 1 || 0 || 1 || 1
|0
|1
|1
|0
|1
|0
|1
|1
|-
|-
|1
|1 || 1 || 0 || 0 || 1 || 1 || 0 || 1 || 0
|1
|0
|0
|1
|1
|0
|1
|0
|-
|-
|1
|1 || 1 || 0 || 1 || 0 || 0 || 0 || 0 || 0
|1
|0
|1
|0
|0
|0
|0
|0
|-
|-
|1
|1 || 1 || 1 || 0 || 0 || 0 || 0 || 0 || 0
|1
|1
|0
|0
|0
|0
|0
|0
|-
|-
|1
|1 || 1 || 1 || 1 || 0 || 0 || 0 || 0 || 0
|1
|1
|1
|0
|0
|0
|0
|0
|}
|}


== Sample Problem 2 ==
From the truth table, there are 10 rows where the final output is TRUE.
 
== Sample Problem 3 ==


Find all ordered triplets (A, B, C) which make the following circuit FALSE:
Simplify the Boolean expression that this circuit represents.


Solution: The circuit translates to the Boolean expression <math>\overline{AB}+C</math>.  To find when this is FALSE we can equivalently find when the <math>\overline{\overline{AB}+C}</math> is TRUE.  We can simplify this by applying DeMorgan’s Law and cancelling the double ''not'' over ''AB'' to yield <math>AB\overline{C}</math> .  This is TRUE when for (1,1,0) only.
::[[File:Circuit-PB.png|200px]]


== Sample Problem 3 ==
'''Solution:'''


Simplify the following digital circuit as a Boolean algebra expression using the fewest gates possible:
The circuit translates as follows:


Solution:  This translates to:  <math>\overline{A*B+\overline{C}*D}</math> .  Simplify:
<math>(\overline{A}(A+B))\overline{B+C}</math>
<math>\overline{(A*B+\overline{C})*D}=\overline{AB+\overline{C}}+\overline{D}</math>
<math>=(\overline{A}A+\overline{A}B)\overline{B}\overline{C}</math>
<math>=\overline{AB}*\overline{\overline{C}}+\overline{D}=(\overline{A}+B)C+\overline{D}</math>
<math>=(0+\overline{A}B)\overline{B}\overline{C}</math>
This has 5 gates and <math>\overline{A}C+BC+\overline{D}</math> has 6 so the above expression is best.
<math>=\overline{A}B\overline{B}\overline{C}</math>
<math>=0</math>


= Video Resources =
= Video Resources =
==ACSL Advisors==


The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.  
The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.  


<!--
<!--
Line 355: Line 301:
|}
|}
-->
-->
{|
|-
| <youtube width="300" height="180">https://youtu.be/gxil9VyGTtE</youtube>
| [https://youtu.be/gxil9VyGTtE ''Digital Electronics -1'' ('''Ravi Yeluru (hemsra)''')]
Introduces the AND, OR, and NOT gates, and works through a couple of simple circuits.
|-
| <youtube width="300" height="180">https://youtu.be/m7-wa5ca_G8</youtube>
| [https://youtu.be/m7-wa5ca_G8 Digital Electronics -2'' ('''Ravi Yeluru (hemsra)''')]
Solves a 3-gate circuit (the AND of an OR and a NOR) given by the Boolean expression <math>(\overline{A}+B)(\overline{B+C})</math>.
|-
| <youtube width="300" height="180">https://youtu.be/Eckd5UlJmB4</youtube>
| [https://youtu.be/Eckd5UlJmB4 ''Digital Electronics Boolean Algebra'' ('''Tangerine Code''')]
Solves a 3-gate circuit (the AND of an OR and a NOR) given by the Boolean expression
<math>\overline{(A+B)}(B+C)</math>.
|-
| <youtube width="300" height="180">https://youtu.be/JJL6DsVCpHo</youtube>
| [https://youtu.be/JJL6DsVCpHo ''ACSL Digital Electronics Worksheet Sample'' ('''misterminich''')]
Solves a handful of ACSL problems.
|}
==Other Videos==
The topic of Digital Electronics is fundamental in Computer Science and there are many videos on YouTube that teach this subject. We found the following videos to be
nice introductions to digital logic gates. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.
{|
|-
| <youtube width="300" height="180">https://youtu.be/s2MI_NgKD98</youtube>
| [https://youtu.be/s2MI_NgKD98 ''Digital Electronics Basics'' ('''Beginning Electronics''')]
|-
| <youtube width="300" height="180">https://youtu.be/z9s8A8oBe7g</youtube>
| [https://youtu.be/z9s8A8oBe7g ''Logic Gate Expressions'' ('''Kevin Drumm''')]
|-
| <youtube width="300" height="180">https://youtu.be/eroqZpbKrhc</youtube>
| [https://youtu.be/eroqZpbKrhc ''Determining the truth table and logic statement'' ('''Anna does some physics''')]
Uses a truth table to find the inputs that make the circuit <math>\not(A+B)+(AB)</math> true using a truth table.
|}

Latest revision as of 12:14, 18 December 2021

A digital circuit is constructed from logic gates. Each logic gate performs a function of boolean logic based on its inputs, such as AND or OR. Each circuit can be represented as a Boolean Algebra expression; this topic is an extension of the topic of Boolean Algebra, which includes a thorough description of truth tables and simplifying expressions.

Definitions

The following table illustrates all logic gates. For each logic gate, the table shows the equivalent Boolean algebra expression and truth table.

NAME GRAPHICAL SYMBOL ALGEBRAIC EXPRESSION TRUTH TABLE
BUFFER Buffer-gate-en.svg X = A
INPUT OUTPUT
0 0
1 1
NOT Not-gate-en.svg X = [math]\overline{A}[/math] or [math]\neg A[/math]
INPUT OUTPUT
A X
0 1
1 0
AND And-gate.png X = [math]AB[/math] or [math]A \cdot B[/math]
INPUT OUTPUT
A B X
0 0 0
0 1 0
1 0 0
1 1 1
NAND Nand-gate-en.svg X = [math]\overline{AB}[/math] or [math]\overline{A\cdot B}[/math]
INPUT OUTPUT
A B X
0 0 1
0 1 1
1 0 1
1 1 0
OR Or-gate-en.svg X = [math]A+B[/math]
INPUT OUTPUT
A B X
0 0 0
0 1 1
1 0 1
1 1 1
NOR Nor-gate-en.svg X = [math]\overline{A+B}[/math]
INPUT OUTPUT
A B X
0 0 1
0 1 0
1 0 0
1 1 0
XOR Xor-gate-en.svg X = [math]A \oplus B[/math]
INPUT OUTPUT
A B X
0 0 0
0 1 1
1 0 1
1 1 0
XNOR Xnor-gate-en.svg X = [math]\overline{A \oplus B} \text{ or } A \odot B[/math]
INPUT OUTPUT
A B X
0 0 1
0 1 0
1 0 0
1 1 1

Note that there is some ambiguity in the conversion from a diagram to a circuit. For example, is [math]\overline{A+B}[/math] an OR gate followed by a NOT gate, or smply a NOT gate.

Online Tools

The Logisim application is a wonderful tool for exploring this topic. Logisim is free to download and use; among its many features is support to automatically draw a circuit from a Boolean Algebra expression; to simulate the circuit with arbitrary inputs; and to complete a truth table for the circuit. From the application, you can import the circuit corresponding to the Sample Problem 1 from the file located at http://www.acsl.org/misc/wiki-digital-electronics-sample1.circ. There are many YouTube videos that show how to use the Logisim application; including a very nice 4 minute tutorial.

Logisim contains many additional advanced features that are beyond the scope of ACSL problems.

Sample Problems

Sample Problem 1

Find all ordered triplets (A, B, C) which make the following circuit FALSE:

NotABorC.svg

Solution:

One approach to solving this problem is to reason about that inputs and outputs are necessary at each gate. For the circuit to be FALSE, both inputs to the file OR gate must be false. Thus, input C must be FALSE, and the output of the NAND gate must also be false. The NAND gate is false only when both of its inputs are TRUE; thus, inputs A and B must both be TRUE. The final answer is (TRUE, TRUE, FALSE), or (1, 1, 0).

Another approach to solving this problem is to translate the circuit into a Boolean Algebra expression and simplify the expression using the laws of Boolean Algebra. This circuit translates to the Boolean expression [math]\overline{AB}+C[/math]. To find when this is FALSE we can equivalently find when the [math]\overline{\overline{AB}+C}[/math] is TRUE. The expression becomes [math]\overline{\overline{AB}}\cdot \overline{C}[/math] after applying DeMorgan’s Law. The double NOT over the AB expression cancels out, to become [math]AB\overline{C}[/math]. The AND of 3 terms is TRUE when each term is TRUE, or A=1, B=1 and C=0.

Sample Problem 2

How many ordered 4-tuples (A, B, C, D) make the following circuit TRUE?

Circuit-sample2.svg

Solution:

We'll use a truth table to solve this problem. The rows in the truth table will correspond to all possible inputs - 16 in this case, since there are 4 inputs. The output columns will be the output of each gate, other than the NOT gates. The diagram below labels each of the gates; it's useful to keep the column straight when working the truth table.

Circuit-sample2-labels.svg
INPUT OUTPUT
A B C D p q r s t
[math]\overline{C+D}[/math] [math]p+\overline{B}[/math] [math]\overline{A}B[/math] [math]r \oplus q[/math] [math]s \oplus p[/math]
0 0 0 0 1 1 0 1 0
0 0 0 1 0 1 0 1 1
0 0 1 0 0 1 0 1 1
0 0 1 1 0 1 0 1 1
0 1 0 0 1 1 1 0 1
0 1 0 1 0 0 1 1 1
0 1 1 0 0 1 1 1 1
0 1 1 1 0 0 1 1 1
1 0 0 0 1 1 0 1 0
1 0 0 1 0 1 0 1 1
1 0 1 0 0 1 0 1 1
1 0 1 1 0 1 0 1 1
1 1 0 0 1 1 0 1 0
1 1 0 1 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0

From the truth table, there are 10 rows where the final output is TRUE.

Sample Problem 3

Simplify the Boolean expression that this circuit represents.

Circuit-PB.png

Solution:

The circuit translates as follows:

[math](\overline{A}(A+B))\overline{B+C}[/math] [math]=(\overline{A}A+\overline{A}B)\overline{B}\overline{C}[/math] [math]=(0+\overline{A}B)\overline{B}\overline{C}[/math] [math]=\overline{A}B\overline{B}\overline{C}[/math] [math]=0[/math]

Video Resources

ACSL Advisors

The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.


Digital Electronics -1 (Ravi Yeluru (hemsra))

Introduces the AND, OR, and NOT gates, and works through a couple of simple circuits.

Digital Electronics -2 (Ravi Yeluru (hemsra))

Solves a 3-gate circuit (the AND of an OR and a NOR) given by the Boolean expression [math](\overline{A}+B)(\overline{B+C})[/math].

Digital Electronics Boolean Algebra (Tangerine Code)

Solves a 3-gate circuit (the AND of an OR and a NOR) given by the Boolean expression [math]\overline{(A+B)}(B+C)[/math].

ACSL Digital Electronics Worksheet Sample (misterminich)

Solves a handful of ACSL problems.


Other Videos

The topic of Digital Electronics is fundamental in Computer Science and there are many videos on YouTube that teach this subject. We found the following videos to be nice introductions to digital logic gates. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.


Digital Electronics Basics (Beginning Electronics)
Logic Gate Expressions (Kevin Drumm)
Determining the truth table and logic statement (Anna does some physics)

Uses a truth table to find the inputs that make the circuit [math]\not(A+B)+(AB)[/math] true using a truth table.