Logic Design, Part 2

?

?# 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: 'Logic Design'

⏫

0:07Set the stage for the day continuing on logic design

🗩

0:07Set the stage for the day continuing on logic design

🗩

0:07Set the stage for the day continuing on logic design

🗩

0:25Review the notion of boolean logic expressions, and turning a truth table into a sum of products representation

📖

0:25Review the notion of boolean logic expressions, and turning a truth table into a sum of products representation

📖

📖

2:06Review our ability to tabulate functions to their truth table

📖

2:06Review our ability to tabulate functions to their truth table

📖

2:06Review our ability to tabulate functions to their truth table

📖

3:23Demo function_to_sum_of_products() on an OR function

3:23Demo function_to_sum_of_products() on an OR function

3:23Demo function_to_sum_of_products() on an OR function

4:00Run it to see our non-minimal representation of OR, noting that the problem of producing the minimal representation in the general case is NP-complete^{1}^{,2}^{,3}

🏃

4:00Run it to see our non-minimal representation of OR, noting that the problem of producing the minimal representation in the general case is NP-complete^{1}^{,2}^{,3}

🏃

🏃

7:10Review off-stream change to using a bit vector for the input

📖

7:10Review off-stream change to using a bit vector for the input

📖

7:10Review off-stream change to using a bit vector for the input

📖

7:46Review muxes and Shannon expansion

📖

7:46Review muxes and Shannon expansion

📖

7:46Review muxes and Shannon expansion

📖

8:35Consult the graph for our Example3 parity function, highlighting the shareable nodes and bit vector notation, and noting the usefulness of binary decision diagrams

🏃

8:35Consult the graph for our Example3 parity function, highlighting the shareable nodes and bit vector notation, and noting the usefulness of binary decision diagrams

🏃

🏃

12:33Note the efficiency of muxes for XOR implementations

🏃

12:33Note the efficiency of muxes for XOR implementations

🏃

12:33Note the efficiency of muxes for XOR implementations

🏃

13:04Understanding XOR as a conditional inverter

🗩

13:04Understanding XOR as a conditional inverter

🗩

13:04Understanding XOR as a conditional inverter

🗩

14:45Define Example4 as a 5-bit XOR reduction circuit

14:45Define Example4 as a 5-bit XOR reduction circuit

14:45Define Example4 as a 5-bit XOR reduction circuit

15:33Check out our 5-bit XOR reduced graph, noting its linear depth

🏃

15:33Check out our 5-bit XOR reduced graph, noting its linear depth

🏃

15:33Check out our 5-bit XOR reduced graph, noting its linear depth

🏃

16:03Introduce reduce() to illustrate linear reduction

16:03Introduce reduce() to illustrate linear reduction

16:03Introduce reduce() to illustrate linear reduction

18:13Run it to see that the graph is the same as before

🏃

18:13Run it to see that the graph is the same as before

🏃

18:13Run it to see that the graph is the same as before

🏃

18:42Rename reduce() to linear_reduce() and introduce logarithmic_reduce() as a divide and conquer reduction

18:42Rename reduce() to linear_reduce() and introduce logarithmic_reduce() as a divide and conquer reduction

22:16Run it to see that it works but is slightly unbalanced for a non-power of two

🏃

22:16Run it to see that it works but is slightly unbalanced for a non-power of two

🏃

22:16Run it to see that it works but is slightly unbalanced for a non-power of two

🏃

22:36Run it on an 8-bit input, to see that our graph is fully balanced

🏃

22:36Run it on an 8-bit input, to see that our graph is fully balanced

🏃

22:36Run it on an 8-bit input, to see that our graph is fully balanced

🏃

25:21A few words on divide and conquer and the fork–join model^{4}

🗩

25:21A few words on divide and conquer and the fork–join model^{4}

🗩

25:21A few words on divide and conquer and the fork–join model^{4}

🗩

26:13Determine to cover standard circuit elements and write a simulator

🗩

26:13Determine to cover standard circuit elements and write a simulator

🗩

26:13Determine to cover standard circuit elements and write a simulator

🗩

27:07Define Example5 as an 8-bit comparison function, applying reduction

27:07Define Example5 as an 8-bit comparison function, applying reduction

27:07Define Example5 as an 8-bit comparison function, applying reduction

30:38Check out the graph of our 8-bit comparison function

🏃

30:38Check out the graph of our 8-bit comparison function

🏃

30:38Check out the graph of our 8-bit comparison function

🏃

32:19Q&A

🗩

32:19Q&A

🗩

32:19Q&A

🗩

33:06Define Example6 as an 8-bit comparison function in which one of the values is constant

33:06Define Example6 as an 8-bit comparison function in which one of the values is constant

33:06Define Example6 as an 8-bit comparison function in which one of the values is constant

34:38Check out our graphed comparison against a constant

🏃

34:38Check out our graphed comparison against a constant

🏃

34:38Check out our graphed comparison against a constant

🏃

35:23Introduce equals_constant() as a bespoke constant comparer

35:23Introduce equals_constant() as a bespoke constant comparer

35:23Introduce equals_constant() as a bespoke constant comparer

37:51Check out our more optimal constant comparison graph

🏃

37:51Check out our more optimal constant comparison graph

🏃

37:51Check out our more optimal constant comparison graph

🏃

39:23Ripple-carry adder

🗩

39:23Ripple-carry adder

🗩

39:23Ripple-carry adder

🗩

43:33Sketch out add3()

🗩

43:33Sketch out add3()

🗩

43:33Sketch out add3()

🗩

46:17Introduce add() as bit-vector adder using our sketched out add3()

46:17Introduce add() as bit-vector adder using our sketched out add3()

46:17Introduce add() as bit-vector adder using our sketched out add3()

48:15Define Example7 as a 4-bit ripple-carry adder

48:15Define Example7 as a 4-bit ripple-carry adder

48:15Define Example7 as a 4-bit ripple-carry adder

49:21Run it to see that the graph is already too much

🏃

49:21Run it to see that the graph is already too much

🏃

49:21Run it to see that the graph is already too much

🏃

49:29Change Example7 from a 4- to 2-bit ripple-carry adder

49:29Change Example7 from a 4- to 2-bit ripple-carry adder

49:29Change Example7 from a 4- to 2-bit ripple-carry adder

49:56Run it to see our 2-bit ripple-carry adder

🏃

49:56Run it to see our 2-bit ripple-carry adder

🏃

49:56Run it to see our 2-bit ripple-carry adder

🏃

50:56Create Add3 module

50:56Create Add3 module

50:56Create Add3 module

52:47Check out our 2-bit ripple-carry adder to see more clearly the chain structure of the Add3 modules

🏃

52:47Check out our 2-bit ripple-carry adder to see more clearly the chain structure of the Add3 modules

🏃

🏃

53:12Check out our 4-bit ripple-carry adder, noting that we likely wouldn't make an adder manually for our FPGA, letting our logic synthesis tools pick which adder to instantiate

🏃

53:12Check out our 4-bit ripple-carry adder, noting that we likely wouldn't make an adder manually for our FPGA, letting our logic synthesis tools pick which adder to instantiate

🏃

🏃

56:11Prevent add() from taking the carry

56:11Prevent add() from taking the carry

56:11Prevent add() from taking the carry

56:52Check out our ripple-carry adder with only internal carries

🏃

56:52Check out our ripple-carry adder with only internal carries

🏃

56:52Check out our ripple-carry adder with only internal carries

🏃

57:15Consider simplifications to Add3 when the carry is 0, to make a half-adder

🗩

57:15Consider simplifications to Add3 when the carry is 0, to make a half-adder

🗩

57:15Consider simplifications to Add3 when the carry is 0, to make a half-adder

🗩

1:01:12Split out the intermediate propagating and generated carry bits in Add3

1:01:12Split out the intermediate propagating and generated carry bits in Add3

1:01:12Split out the intermediate propagating and generated carry bits in Add3

1:02:38Check out the graph of our Add3 half-adder module

🏃

1:02:38Check out the graph of our Add3 half-adder module

🏃

1:02:38Check out the graph of our Add3 half-adder module

🏃

1:04:25Subtraction in two's complement

🗩

1:04:25Subtraction in two's complement

🗩

1:04:25Subtraction in two's complement

🗩

1:06:31Introduce sub() using add(), also having changed add() back to take a carry

1:06:31Introduce sub() using add(), also having changed add() back to take a carry

1:06:31Introduce sub() using add(), also having changed add() back to take a carry

1:07:30Check out our subtraction graph

🏃

1:07:30Check out our subtraction graph

🏃

1:07:30Check out our subtraction graph

🏃

1:07:44Define Example9 as a simple ALU that does addition or subtraction depending on the state of an operation bit

1:07:44Define Example9 as a simple ALU that does addition or subtraction depending on the state of an operation bit

1:10:17Check out our addition / subtraction ALU

🏃

1:10:17Check out our addition / subtraction ALU

🏃

1:10:17Check out our addition / subtraction ALU

🏃

1:14:21Equality comparison

🗩

1:14:21Equality comparison

🗩

1:14:21Equality comparison

🗩

1:15:18Lexicographical equality comparison

🗩

1:15:18Lexicographical equality comparison

🗩

1:15:18Lexicographical equality comparison

🗩

1:18:25Subtraction and < 0 equality comparison in an ALU

🗩

1:18:25Subtraction and < 0 equality comparison in an ALU

🗩

1:18:25Subtraction and < 0 equality comparison in an ALU

🗩

1:19:53Change add() to output the carry

1:19:53Change add() to output the carry

1:19:53Change add() to output the carry

1:21:06Create Example10 module as a subtraction and < 0 comparator

1:21:06Create Example10 module as a subtraction and < 0 comparator

1:21:06Create Example10 module as a subtraction and < 0 comparator

1:21:58Check out our comparison graph

🏃

1:21:58Check out our comparison graph

🏃

1:21:58Check out our comparison graph

🏃

1:22:46Explicit zero-extension in lieu of the output carry

🗩

1:22:46Explicit zero-extension in lieu of the output carry

🗩

1:22:46Explicit zero-extension in lieu of the output carry

🗩

1:24:59Check our workings with Fabian

🗩

1:24:59Check our workings with Fabian

🗩

1:24:59Check our workings with Fabian

🗩

1:26:17Create Example11 module as a signed comparator

1:26:17Create Example11 module as a signed comparator

1:26:17Create Example11 module as a signed comparator

1:26:41Check out our signed comparator graph

🏃

1:26:41Check out our signed comparator graph

🏃

1:26:41Check out our signed comparator graph

🏃

1:28:01Reflect on our comparator modules, noting that you cannot overflow when extending by one bit

🗩

1:28:01Reflect on our comparator modules, noting that you cannot overflow when extending by one bit

🗩

🗩

1:31:00That's a good stopping point

🗩

1:31:00That's a good stopping point

🗩

1:31:00That's a good stopping point

🗩

⏬

Next: 'Logic Design, Part 3'

⏬