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

a
w
s
d
h j k l


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)
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
📖
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-complete1,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-complete1,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-complete1,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
🏃
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
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 model4
🗩
25:21A few words on divide and conquer and the fork–join model4
🗩
25:21A few words on divide and conquer and the fork–join model4
🗩
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
🗩
32:38rygorous Good thing CPUs don't have silly shit like, say, a "parity" flag bit that is set to match the parity of the last 64-bit result you computed
🗪
32:38rygorous Good thing CPUs don't have silly shit like, say, a "parity" flag bit that is set to match the parity of the last 64-bit result you computed
🗪
32:38rygorous Good thing CPUs don't have silly shit like, say, a "parity" flag bit that is set to match the parity of the last 64-bit result you computed
🗪
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
🏃
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
🏃
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
🏃
54:43barely_polar Does this add work with negatives?
🗪
54:43barely_polar Does this add work with negatives?
🗪
54:43barely_polar Does this add work with negatives?
🗪
54:49rygorous In two's complement, yes
🗪
54:49rygorous In two's complement, yes
🗪
54:49rygorous In two's complement, yes
🗪
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: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:11:48barely_polar Can you talk about the intuition for why flipping the bits and adding 1 is equivalent to subtraction? I can see it's true but don't understand why
🗪
1:11:48barely_polar Can you talk about the intuition for why flipping the bits and adding 1 is equivalent to subtraction? I can see it's true but don't understand why
🗪
1:11:48barely_polar Can you talk about the intuition for why flipping the bits and adding 1 is equivalent to subtraction? I can see it's true but don't understand why
🗪
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:25:30rygorous pervognsen Not actually sure
🗪
1:25:30rygorous pervognsen Not actually sure
🗪
1:25:30rygorous pervognsen Not actually sure
🗪
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:26:47rygorous pervognsen I just know the normal form which uses N and V bits
🗪
1:26:47rygorous pervognsen I just know the normal form which uses N and V bits
🗪
1:26:47rygorous pervognsen I just know the normal form which uses N and V bits
🗪
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: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
🗩