Logic circuits and software
Toshiyuki Masui
2018/7/11
Reasons why we should study logic circuits
Simply interesting
Understanding boolean logic (switching algebra)
Making Ubicomp hardware
Understanding state transition machines
Steve Wozniak
https://www.persol-group.co.jp/special/iconicworkers/sw/limitedmovie.html http://gyazo.com/3ce0db0aa51550090903b0beb42c178c.png
Apple cofounder
Logic circuit wizard
Designed sophisticated systems with elegant design
AppleII Schematic
http://gyazo.com/f71101fc6114bea09bc0aefb37a9ed7f.png
Masui's article (1978)
https://gyazo.com/a85e9bf20a1f317c95270c06798d2f46 http://gyazz.masuilab.org/upload/5693e31f2b37c1fd5b5043c2696855b6.pdf
A computer is ...
A very complex state transition machine
State changes based on current state and external conditions
clock signal (= time)
interrupt signals
sensor values
Made up of digital logic circuits
State diagram of a toggle switch
http://gyazo.com/f8b9cf57199c5ed2501770dce007805c.png
State transition of puzzle pieces
http://gyazo.com/e91195d80701b5541bc71d9c147f3f05.png
Detecting C-style comments
Recognize /* .... */
http://gyazo.com/c0d7354659a4eaa51af15edfa5c542b7.png
Typical structure of a hardware state transition machine
A memory device for holding current status
Combinational circuits for calculating next state
External input
http://gyazo.com/065c1aa34bbcbdc782db9e8b0a1d67bf.png
Example: digital clock
Input = pulses from AC outlet
50Hz pulse
Changing the value every $ 1/50 second
Users can set values
https://ksr-video.imgix.net/projects/2867676/video-773889-h264_high.mp4
Digital circuits
Combinations of on/off switches
Can be constructed using relays and other hardware
Combinational logic and Sequential logic
Combinational logic
No memory
Like a pure function
AND, OR
Adder
$ f = sin(x)
Example: AND function
code:and.c
function and(x,y){
if(x == 1 && y == 1) return 1;
else return 0;
}
MIL symbol of an AND gate
http://gyazo.com/5c100de39bb86aa4386c9be5430dad64.png
AND logic example
Implementation with relays (electromagnet + switch)
http://gyazo.com/4ce62e78e5630e8d322e3be6cd6279e0.png
MIL symbol of an OR gate
http://gyazo.com/e5951801853cc917aa9a26157a35b2ee.png
OR logic example
http://gyazo.com/1b33fea6e14c0e8b833faf361ef753cf.png
MIL symbol of a NOT gate
http://gyazo.com/a289f7cfab8020db720b69bb857be2c7.png
MIL symbol of an AND gate
NAND = AND + NOT
http://gyazo.com/5280c481a947c9d7f58c467fc7d0acf7.png
A TTL NAND gate
http://gyazo.com/a71168f3c3db69fde9928249b8e6c265.png
SN7400N
TTL from Texas Instruments
https://gyazo.com/063de13d9982f91135c0540d09a9a00d
SN7400N
https://gyazo.com/536a9b4ebc4eaab1d90a86279b4fec80
CMOS NAND gate
http://gyazo.com/a38c7a4ecdfbbf3be5515a884b35ec28.png
Exclusive OR
http://gyazo.com/eef789540c8e9050a196bc5dbbd57d75.png
EOR gate from NAND gates
http://gyazo.com/3f271340279254daa20bb5c2fb2496b7.png
Truth table of an NAND gate
http://gyazo.com/722605b98b9e5e7750036de7945f5fdb.png
Karnaugh map
http://gyazo.com/44bdb71d5d14288a8ddb66acbfb19b59.png
Karnaugh map of an OR gate
http://gyazo.com/9eb9b97b8c5a4e365f719f586508f38b.png
Adder
https://gyazo.com/b781bd240d3e3480341190e69b50553a
Half adder
https://gyazo.com/416229ac2cf2e0c15d9600c6b1a1e0ad
Full adder
https://gyazo.com/848a691cbebfe90c45ecaf6c9a85ba16 https://gyazo.com/848a691cbebfe90c45ecaf6c9a85ba16
Full adder
https://gyazo.com/b600fbbbc9c41d62720059b095810d41
Comparator
https://gyazo.com/0240ddf66a8655925c4bc2877dc7bf7c
Karnaugh map of a compare function
AB > CD ?
http://gyazo.com/067a855e7d7a34efd063ac8d788bf36e.png
Optimizing the circuit using a Karnaugh map
Find large rectangles which fits the pattern
http://gyazo.com/37983b9b5665d5202e595cea4a611ad7.png
Corresponding if-statement
Listing all the conditions
if(A == 1 && C == 0 ||
C == 0 && D == 0 && B == 1 ||
A == 1 && B == 1 && C == 1 && D == 0)
Difficult without a Karnaugh map
Disjunctive normal form (DNF)
http://gyazo.com/f96a78e115b2b12b00dd3790bc68aecf.png
PLA-based DNF Implementation
http://gyazo.com/bc66ccbcd327d19d95b94caf0af6f2ba.png
Sequential Logic
How can we hold current state?
Use Flip-Flops
Can have stable values
Combinational logic with feedback wiring
RS Flip-Flop
http://gyazo.com/5eac22576e16a9f00a11b283380e07b0.png
D Latch
http://gyazo.com/1a29cd3e9371107fff3a6156e7a4b0cd.png
D Flip-Flop
Can be used as a memory device
http://gyazo.com/42a1e52b03c45e4f146798cde8727261.png
CMOS Switch
http://gyazo.com/948d4c6dffefc07850cfca58aece1066.png
D Flip-Flop on CMOS
http://gyazo.com/2dbadd0b5ad1075ab6fb8f5ea07bb2e5.png
State transition machine
http://gyazo.com/065c1aa34bbcbdc782db9e8b0a1d67bf.png
Counter
https://gyazo.com/60bccad3e0beb6665e5d8d21389ecb95
Shift register
http://gyazo.com/24dd91aae749c42c3b2a1a89f9b15d3f.png
Fluctuation LED
http://gyazo.com/88f64657d2c32932a105102045fa3e86.png
Using a shift register
Generate pseudo-random values using M-series
http://www.youtube.com/watch?v=-LvrZUEb72E
Simulation of M-series
code:m.js
function setup(){
data = []
createCanvas(640,20)
for(i=0;i<32;i++) datai = 0 frameRate(20)
}
function draw(){
strokeWeight(0)
for(i=0;i<1;i++){
data.push((data3 + data10 + data29 + 1) % 2) // data.shift()
}
for(i=0;i<32;i++){
fill(datai == 0 ? 'black' : 'white') rect(i*20,0,20,20)
}
}
State transition programming
Using the current execution point
Using the program counter as the state variable
Using state variables
Using a state transition table
Flowchart
http://gyazo.com/ba6a0d78000d76428b935d3a1d63c4af.png
Recognizing C comments
/* ... */
http://gyazo.com/e3114c38659d39bd4598116103724ee6.png
Using the execution point as the state variable
code:comment1.c
main()
{
int c;
while(1){
c = get_c();
while(c == '/'){
c = get_c();
if(c == '*'){
printf("/*");
int done = 0;
while(! done){
c = get_c();
printf("%c",c);
while(c == '*'){
c = get_c();
printf("%c",c);
if(c == '/'){
done = 1;
c = get_c();
break;
}
}
}
}
}
}
}
Characteristics of this approach
Good for simple cases
Not good for very complicatd state transition
Difficult to understand in many cases
Using state variables
Combination of values indicate the state of the program
Using if's and switch's for state transition table
Good for simple state transition
Not ideal for really complicated state transition
comment2.c
code:comment2.c
typedef enum {
S1, S2, C1, C2
} State;
State state = S1;
trans(int c)
{
switch(state){
case S1:
if(c == '/') state = S2;
break;
case S2:
if(c == '/') state = S2;
else if(c == '*'){
printf("/*");
state = C1;
}
else state = S1;
break;
case C1:
printf("%c",c);
if(c == '*') state = C2;
break;
case C2:
printf("%c",c);
if(c == '*') state = C2;
else if(c == '/') state = S1;
else state = C1;
break;
}
}
main()
{
char *s;
while(fgets(buf,1000,stdin)){
for(s=buf;*s;s++){
trans(*s);
}
}
}
Using a state transition table
Assign a unique number to each state
Create a state transitino table
By hand
By special tools
State transition table
http://gyazo.com/adb22100f07d3c58e4d00192368589d9.png
comment3.c
code:comment3.c
enum {
S1, S2, C1, C2
};
int state = S1;
void init()
{
int i;
for(i=0;i<0x100;i++){
}
state = S1;
}
main()
{
unsigned char *s;
init();
while(fgets(buf,1000,stdin)){
for(s=buf;*s;s++){
int oldstate = state;
if(oldstate == S2 && state == C1) printf("/*");
if(oldstate == C1 || oldstate == C2) printf("%c",*s);
}
}
}
State transition programming ≈ state transition machine
http://gyazo.com/065c1aa34bbcbdc782db9e8b0a1d67bf.png
State transition programming and Karnaugh map
http://gyazo.com/adb22100f07d3c58e4d00192368589d9.png
http://gyazo.com/44bdb71d5d14288a8ddb66acbfb19b59.png
Conclusions
Logic circuits are not only important, but interesting
Circuits and software for state transition are important
Various techniques are common to hardware and software
AppleII Schematic
http://gyazo.com/f71101fc6114bea09bc0aefb37a9ed7f.png