Logic Design

?

?# Keyboard Navigation

## Global Keys

[, < / ], > Jump to previous / next episode

W, K, P / S, J, N Jump to previous / next marker

t / T Toggle theatre / SUPERtheatre mode

V Revert filter to original state Y Select link (requires manual Ctrl-c)## Menu toggling

q Quotes
r References
f Filter
y Link
c Credits
## In-Menu Movement

## Quotes and References Menus

Enter Jump to timecode

## Quotes, References and Credits Menus

o Open URL (in new tab)
## Filter Menu

x, Space Toggle category and focus next

X, ShiftSpace Toggle category and focus previous

v Invert topics / media as per focus## Filter and Link Menus

z Toggle filter / linking mode
## Credits Menu

Enter Open URL (in new tab)

W, K, P / S, J, N Jump to previous / next marker

t / T Toggle theatre / SUPERtheatre mode

V Revert filter to original state Y Select link (requires manual Ctrl-c)

a

w

s

s

d

h
j
k
l

←

↑

↓

↓

→

X, ShiftSpace Toggle category and focus previous

v Invert topics / media as per focus

⏫

Previous: 'Hardware Design Overview'

⏫

0:00Recap and set the stage for the day on logic design

🗩

0:00Recap and set the stage for the day on logic design

🗩

0:00Recap and set the stage for the day on logic design

🗩

2:10Introducing logic design, gates and operation cost

🗩

2:10Introducing logic design, gates and operation cost

🗩

2:10Introducing logic design, gates and operation cost

🗩

7:39Set up to design and visualise a simple circuit fragment

🗩

7:39Set up to design and visualise a simple circuit fragment

🗩

7:39Set up to design and visualise a simple circuit fragment

🗩

8:42Define Example1 module as a simple NOT circuit

8:42Define Example1 module as a simple NOT circuit

8:42Define Example1 module as a simple NOT circuit

10:40Run our Graphviz generator and checkout the graph for Example1

🏃

10:40Run our Graphviz generator and checkout the graph for Example1

🏃

10:40Run our Graphviz generator and checkout the graph for Example1

🏃

11:16Add another NOT node to Example1

11:16Add another NOT node to Example1

11:16Add another NOT node to Example1

11:37Run it to see our additional NOT node

🏃

11:37Run it to see our additional NOT node

🏃

11:37Run it to see our additional NOT node

🏃

11:42Building up circuits of primitives

🗩

11:42Building up circuits of primitives

🗩

11:42Building up circuits of primitives

🗩

12:43Define Not module to show the possibility to replace builtin primitives

12:43Define Not module to show the possibility to replace builtin primitives

12:43Define Not module to show the possibility to replace builtin primitives

15:20Run it to see our graphed handwritten Not node

🏃

15:20Run it to see our graphed handwritten Not node

🏃

15:20Run it to see our graphed handwritten Not node

🏃

17:45Change Example1 to contain two input nodes

17:45Change Example1 to contain two input nodes

17:45Change Example1 to contain two input nodes

18:53Run it to see our circuit with two inputs

🏃

18:53Run it to see our circuit with two inputs

🏃

18:53Run it to see our circuit with two inputs

🏃

18:58Add two custom Not nodes to Example1

18:58Add two custom Not nodes to Example1

18:58Add two custom Not nodes to Example1

19:31Run it to see our custom Not nodes

🏃

19:31Run it to see our custom Not nodes

🏃

19:31Run it to see our custom Not nodes

🏃

19:48Typical module hierarchy

🗩

19:48Typical module hierarchy

🗩

19:48Typical module hierarchy

🗩

20:21Define Xor module for Not to use

20:21Define Xor module for Not to use

20:21Define Xor module for Not to use

22:02Run the Graphviz generator on all levels of our module hierarchy

🏃

22:02Run the Graphviz generator on all levels of our module hierarchy

🏃

22:02Run the Graphviz generator on all levels of our module hierarchy

🏃

23:04Set up to demonstrate universality through generation of the circuit corresponding to a Python boolean function / table

🗩

23:04Set up to demonstrate universality through generation of the circuit corresponding to a Python boolean function / table

🗩

🗩

25:03Produce the formula for XOR from its truth table using the sum of products representation

🗩

25:03Produce the formula for XOR from its truth table using the sum of products representation

🗩

25:03Produce the formula for XOR from its truth table using the sum of products representation

🗩

29:29Set up to create a general truth table-to-circuit converter

🗩

29:29Set up to create a general truth table-to-circuit converter

🗩

29:29Set up to create a general truth table-to-circuit converter

🗩

31:56Introduce table_to_circuit(), reduce_or() and reduce_and()

31:56Introduce table_to_circuit(), reduce_or() and reduce_and()

31:56Introduce table_to_circuit(), reduce_or() and reduce_and()

38:23Test reduce_or()

38:23Test reduce_or()

38:23Test reduce_or()

38:50Run it to see that it does what you hope it does

🏃

38:50Run it to see that it does what you hope it does

🏃

38:50Run it to see that it does what you hope it does

🏃

39:00Add a third input to our reduce_or() call in Example2

39:00Add a third input to our reduce_or() call in Example2

39:00Add a third input to our reduce_or() call in Example2

39:09Run it to see that it's incorrect

🏃

39:09Run it to see that it's incorrect

🏃

39:09Run it to see that it's incorrect

🏃

39:29Fix typo in our reduce_or() call

39:29Fix typo in our reduce_or() call

39:29Fix typo in our reduce_or() call

39:39Run it to see our cascaded reduction of inputs

🏃

39:39Run it to see our cascaded reduction of inputs

🏃

39:39Run it to see our cascaded reduction of inputs

🏃

40:21Test table_to_circuit()

40:21Test table_to_circuit()

40:21Test table_to_circuit()

41:02Run it to see our Xor circuit

🏃

41:02Run it to see our Xor circuit

🏃

41:02Run it to see our Xor circuit

🏃

41:26Sum of products

🗩

41:26Sum of products

🗩

41:26Sum of products

🗩

42:05Introduce tabulate() to turn a boolean function into its corresponding truth table

42:05Introduce tabulate() to turn a boolean function into its corresponding truth table

42:05Introduce tabulate() to turn a boolean function into its corresponding truth table

48:26Introduce function_to_circuit()

48:26Introduce function_to_circuit()

48:26Introduce function_to_circuit()

50:30Test function_to_circuit()

50:30Test function_to_circuit()

50:30Test function_to_circuit()

51:04Run it to see that it produces the minimal representation for an AND gate, but not an OR gate

🏃

51:04Run it to see that it produces the minimal representation for an AND gate, but not an OR gate

🏃

51:04Run it to see that it produces the minimal representation for an AND gate, but not an OR gate

🏃

51:57Illustrate the wasteful (yet correct) nature of this OR circuit

🗩

51:57Illustrate the wasteful (yet correct) nature of this OR circuit

🗩

51:57Illustrate the wasteful (yet correct) nature of this OR circuit

🗩

54:05Set up to illustrate the inability of sum of products to scale

🗩

54:05Set up to illustrate the inability of sum of products to scale

🗩

54:05Set up to illustrate the inability of sum of products to scale

🗩

55:41Produce a three-input XOR circuit

55:41Produce a three-input XOR circuit

55:41Produce a three-input XOR circuit

56:45Run it to see our greater number of terms

🏃

56:45Run it to see our greater number of terms

🏃

56:45Run it to see our greater number of terms

🏃

57:02Add a fourth input to our XOR circuit

57:02Add a fourth input to our XOR circuit

57:02Add a fourth input to our XOR circuit

57:18Run it to see our exponentially growing graph, noting that this is bound to happen with a two-level circuit

🏃

57:18Run it to see our exponentially growing graph, noting that this is bound to happen with a two-level circuit

🏃

🏃

58:52Summarise our establishment of universality

🗩

58:52Summarise our establishment of universality

🗩

58:52Summarise our establishment of universality

🗩

59:50Q&A

🗩

59:50Q&A

🗩

59:50Q&A

🗩

1:00:30Note the assumption that viewers are comfortable with programming

🗩

1:00:30Note the assumption that viewers are comfortable with programming

🗩

1:00:30Note the assumption that viewers are comfortable with programming

🗩

1:02:02Set up to cover multiplexers and Shannon expansion

🗩

1:02:02Set up to cover multiplexers and Shannon expansion

🗩

1:02:02Set up to cover multiplexers and Shannon expansion

🗩

1:02:55Define Example3 as a multiplexer using the "when" node

1:02:55Define Example3 as a multiplexer using the "when" node

1:02:55Define Example3 as a multiplexer using the "when" node

1:05:24Run it to see our "when" node

🏃

1:05:24Run it to see our "when" node

🏃

1:05:24Run it to see our "when" node

🏃

1:06:33Define a custom When node

1:06:33Define a custom When node

1:06:33Define a custom When node

1:08:07Run it to see our custom sum-of-products When node

🏃

1:08:07Run it to see our custom sum-of-products When node

🏃

1:08:07Run it to see our custom sum-of-products When node

🏃

1:08:31Hand write a more efficient When node

1:08:31Hand write a more efficient When node

1:08:31Hand write a more efficient When node

1:09:06Run it to see this more efficient representation

🏃

1:09:06Run it to see this more efficient representation

🏃

1:09:06Run it to see this more efficient representation

🏃

1:10:54Shannon expansion^{1}

🗩

1:10:54Shannon expansion^{1}

🗩

1:10:54Shannon expansion^{1}

🗩

1:16:19Introduce function_to_muxes() and expand()

1:16:19Introduce function_to_muxes() and expand()

1:16:19Introduce function_to_muxes() and expand()

1:21:04Test function_to_muxes()

1:21:04Test function_to_muxes()

1:21:04Test function_to_muxes()

1:22:33Run it to see our Shannon expanded AND circuit

🏃

1:22:33Run it to see our Shannon expanded AND circuit

🏃

1:22:33Run it to see our Shannon expanded AND circuit

🏃

1:25:02Test function_to_muxes() on a multi-input XOR

1:25:02Test function_to_muxes() on a multi-input XOR

1:25:02Test function_to_muxes() on a multi-input XOR

1:26:29Run it to see our neat XOR circuit thanks to the implicit BDDs (binary decision diagrams) in our memoization

🏃

1:26:29Run it to see our neat XOR circuit thanks to the implicit BDDs (binary decision diagrams) in our memoization

🏃

🏃

1:27:17Temporarily disable memoization

1:27:17Temporarily disable memoization

1:27:17Temporarily disable memoization

1:27:39Run it to see our full exponential circuit, and consider its potential for memoization

🏃

1:27:39Run it to see our full exponential circuit, and consider its potential for memoization

🏃

1:27:39Run it to see our full exponential circuit, and consider its potential for memoization

🏃

1:29:04Run it with our re-enabled memoization and consider the ready compaction of multiplexers thanks to binary decision diagrams^{2}

🏃

1:29:04Run it with our re-enabled memoization and consider the ready compaction of multiplexers thanks to binary decision diagrams^{2}

🏃

🏃

1:30:28Add a fifth input to our function_to_muxes() test

1:30:28Add a fifth input to our function_to_muxes() test

1:30:28Add a fifth input to our function_to_muxes() test

1:30:47Run it to see our compact circuit, and consider our ability to formally compare reduced BDDs of functions

🏃

1:30:47Run it to see our compact circuit, and consider our ability to formally compare reduced BDDs of functions

🏃

🏃

1:33:00Summarise the stream

🗩

1:33:00Summarise the stream

🗩

1:33:00Summarise the stream

🗩

1:34:55Q&A

🗩

1:34:55Q&A

🗩

1:34:55Q&A

🗩

1:39:31That's it

🗩

1:39:31That's it

🗩

1:39:31That's it

🗩

⏬

Next: 'Logic Design, Part 2'

⏬