Digital Electronics

From ACSL Category Descriptions
Revision as of 10:38, 21 August 2018 by Marc Brown (talk | contribs)
Jump to navigation Jump to search

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.

Definitions

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]
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

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 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?

De s1.png

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.

INPUT OUTPUT
A B C D NOR OR AND XOR XOR
[math]p=\overline{C+D}[/math] [math]q=p+\overline{B}[/math] [math]r=\overline{A}B[/math] [math]s=q \oplus r[/math] [math]p \oplus s[/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.

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.



https://youtu.be/Eckd5UlJmB4 [math]\overbar(A+B)}(B+C)[/math] Digital Electronics Boolean Algebra Tangerine Code

https://youtu.be/JJL6DsVCpHo ACSL Digital Electronics Worksheet Sample misterminich

https://youtu.be/gxil9VyGTtE Digital Electronics -1 Ravu Yeluru (hemsra)

https://youtu.be/m7-wa5ca_G8 Digital Electronics -2 Ravu Yeluru (hemsra)


https://youtu.be/s2MI_NgKD98 Digital Electronics Basics Beginning Electronics

https://youtu.be/z9s8A8oBe7g Logic Gate Expressions Kevin Drumm

https://youtu.be/TLl4E3IV6Z0 Logic Gate Combinations Kevin Drumm