Bitwise»Episode Guide
Logic Design, Part 5
?
?

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:06Recap and set the stage for the day continuing with the simulator
🗩
0:06Recap and set the stage for the day continuing with the simulator
🗩
0:06Recap and set the stage for the day continuing with the simulator
🗩
2:30Check out the graph of Example7, our adder
🏃
2:30Check out the graph of Example7, our adder
🏃
2:30Check out the graph of Example7, our adder
🏃
3:32Simulate our adder
3:32Simulate our adder
3:32Simulate our adder
5:16Verify our adder simulation using python's own addition functionality
5:16Verify our adder simulation using python's own addition functionality
5:16Verify our adder simulation using python's own addition functionality
6:41Run it and fail to hit our verification assertion, with a few words on this brute-force verification
🏃
6:41Run it and fail to hit our verification assertion, with a few words on this brute-force verification
🏃
6:41Run it and fail to hit our verification assertion, with a few words on this brute-force verification
🏃
8:33Simulate our subtraction circuit
🏃
8:33Simulate our subtraction circuit
🏃
8:33Simulate our subtraction circuit
🏃
9:14Run it to find that our subtraction works too
🏃
9:14Run it to find that our subtraction works too
🏃
9:14Run it to find that our subtraction works too
🏃
9:36Simulate our less-than comparison circuit
🏃
9:36Simulate our less-than comparison circuit
🏃
9:36Simulate our less-than comparison circuit
🏃
10:37Run it to find that our less-than comparison does not work
🏃
10:37Run it to find that our less-than comparison does not work
🏃
10:37Run it to find that our less-than comparison does not work
🏃
15:06rygorous carry = below, (i.e. unsigned less than). Definitely not <=. Argh, no, I'm thinking x86. x86 CMP is a SUB which sets the carry flag to "borrow", which is !carry, i.e. you need to invert. Your carry is unsigned >=, as in, regular (non-inverted) carry is
🗪
15:06rygorous carry = below, (i.e. unsigned less than). Definitely not <=. Argh, no, I'm thinking x86. x86 CMP is a SUB which sets the carry flag to "borrow", which is !carry, i.e. you need to invert. Your carry is unsigned >=, as in, regular (non-inverted) carry is
🗪
15:06rygorous carry = below, (i.e. unsigned less than). Definitely not <=. Argh, no, I'm thinking x86. x86 CMP is a SUB which sets the carry flag to "borrow", which is !carry, i.e. you need to invert. Your carry is unsigned >=, as in, regular (non-inverted) carry is
🗪
15:10Negate the result of the less-than comparison in Example10
15:10Negate the result of the less-than comparison in Example10
15:10Negate the result of the less-than comparison in Example10
15:58Run it to find that our inverted less-than comparison succeeds
🏃
15:58Run it to find that our inverted less-than comparison succeeds
🏃
15:58Run it to find that our inverted less-than comparison succeeds
🏃
16:19Respecify Example10 as greater-than-or-equal-to, and simulate its signed comparison
16:19Respecify Example10 as greater-than-or-equal-to, and simulate its signed comparison
16:19Respecify Example10 as greater-than-or-equal-to, and simulate its signed comparison
18:29Run it to find that our signed greater-than-or-equal-to comparison fails
🏃
18:29Run it to find that our signed greater-than-or-equal-to comparison fails
🏃
18:29Run it to find that our signed greater-than-or-equal-to comparison fails
🏃
20:29Enable join() to interpret NOT as an unsigned operation
20:29Enable join() to interpret NOT as an unsigned operation
20:29Enable join() to interpret NOT as an unsigned operation
21:35Change our geus simulation test to assert that x < y (i.e. less-than), and find that it passes
🏃
21:35Change our geus simulation test to assert that x < y (i.e. less-than), and find that it passes
🏃
21:35Change our geus simulation test to assert that x < y (i.e. less-than), and find that it passes
🏃
21:53Understanding the lts comparison and bitwise negation before sign-extension of the second operand
🗩
21:53Understanding the lts comparison and bitwise negation before sign-extension of the second operand
🗩
21:53Understanding the lts comparison and bitwise negation before sign-extension of the second operand
🗩
24:08Set up to cover fast adders
🗩
24:08Set up to cover fast adders
🗩
24:08Set up to cover fast adders
🗩
25:31Understanding ripple-carry adder performance, with a mention of FO4
🗩
25:31Understanding ripple-carry adder performance, with a mention of FO4
🗩
25:31Understanding ripple-carry adder performance, with a mention of FO4
🗩
28:40Speculative execution, and carry-select addition
🗩
28:40Speculative execution, and carry-select addition
🗩
28:40Speculative execution, and carry-select addition
🗩
31:15Set up to easily instantiate different sized adders
31:15Set up to easily instantiate different sized adders
31:15Set up to easily instantiate different sized adders
33:34Define Example11 as a divide-and-conquer ripple-carry adder
33:34Define Example11 as a divide-and-conquer ripple-carry adder
33:34Define Example11 as a divide-and-conquer ripple-carry adder
37:08Simulate Example11 to see that it works
🏃
37:08Simulate Example11 to see that it works
🏃
37:08Simulate Example11 to see that it works
🏃
37:31Define Example12 using speculative execution on Example11 to form a carry-select adder
37:31Define Example12 using speculative execution on Example11 to form a carry-select adder
37:31Define Example12 using speculative execution on Example11 to form a carry-select adder
38:48Simulate Example12 to see that it works
🏃
38:48Simulate Example12 to see that it works
🏃
38:48Simulate Example12 to see that it works
🏃
39:21Understanding why the carry-select adder is faster than ripple-carry
🗩
39:21Understanding why the carry-select adder is faster than ripple-carry
🗩
39:21Understanding why the carry-select adder is faster than ripple-carry
🗩
42:16Introduce conditional_sum_adder()
42:16Introduce conditional_sum_adder()
42:16Introduce conditional_sum_adder()
42:45cubercaleb data.medicare.gov.json?
🗪
42:45cubercaleb data.medicare.gov.json?
🗪
42:45cubercaleb data.medicare.gov.json?
🗪
42:52Implement conditional_sum_adder()
42:52Implement conditional_sum_adder()
42:52Implement conditional_sum_adder()
45:41Check out the graph of Example12, the carry-select adder
🏃
45:41Check out the graph of Example12, the carry-select adder
🏃
45:41Check out the graph of Example12, the carry-select adder
🏃
46:26Define Example13 as a conditional-sum adder
46:26Define Example13 as a conditional-sum adder
46:26Define Example13 as a conditional-sum adder
48:25Check out the graph of Example13, the conditional-sum adder
🏃
48:25Check out the graph of Example13, the conditional-sum adder
🏃
48:25Check out the graph of Example13, the conditional-sum adder
🏃
49:02Instantiate a 16-bit conditional-sum adder, and check out its graph
🏃
49:02Instantiate a 16-bit conditional-sum adder, and check out its graph
🏃
49:02Instantiate a 16-bit conditional-sum adder, and check out its graph
🏃
50:28Simulate our conditional-sum adder
50:28Simulate our conditional-sum adder
50:28Simulate our conditional-sum adder
51:46Run it to find that the conditional-sum adder does not work
🏃
51:46Run it to find that the conditional-sum adder does not work
🏃
51:46Run it to find that the conditional-sum adder does not work
🏃
54:14Investigate the possibility that the simulator is not correctly masking
54:14Investigate the possibility that the simulator is not correctly masking
54:14Investigate the possibility that the simulator is not correctly masking
1:04:45Step through compile() to see how it treats our operands, and find that the operands don't have the same length
🏃
1:04:45Step through compile() to see how it treats our operands, and find that the operands don't have the same length
🏃
1:04:45Step through compile() to see how it treats our operands, and find that the operands don't have the same length
🏃
1:09:14Consult the graph of the conditional-sum adder to see a node erroneously containing bit[5]
🏃
1:09:14Consult the graph of the conditional-sum adder to see a node erroneously containing bit[5]
🏃
1:09:14Consult the graph of the conditional-sum adder to see a node erroneously containing bit[5]
🏃
1:09:39Make Example13, the conditional-sum adder, only output the lower bits
1:09:39Make Example13, the conditional-sum adder, only output the lower bits
1:09:39Make Example13, the conditional-sum adder, only output the lower bits
1:10:47Run it to see that we pass the test
🏃
1:10:47Run it to see that we pass the test
🏃
1:10:47Run it to see that we pass the test
🏃
1:11:06Set up to cover carry lookahead adders
🗩
1:11:06Set up to cover carry lookahead adders
🗩
1:11:06Set up to cover carry lookahead adders
🗩
1:11:33Speculative execution in carry lookahead adders
🗩
1:11:33Speculative execution in carry lookahead adders
🗩
1:11:33Speculative execution in carry lookahead adders
🗩
1:13:45Restructuring a ripple-carry adder with indexable bits, towards a carry lookahead adder
🗩
1:13:45Restructuring a ripple-carry adder with indexable bits, towards a carry lookahead adder
🗩
1:13:45Restructuring a ripple-carry adder with indexable bits, towards a carry lookahead adder
🗩
1:19:38Parallelising the carry circuit
🗩
1:19:38Parallelising the carry circuit
🗩
1:19:38Parallelising the carry circuit
🗩
1:29:37Introduce carry_lookahead_adder() and linear_scan()
1:29:37Introduce carry_lookahead_adder() and linear_scan()
1:29:37Introduce carry_lookahead_adder() and linear_scan()
1:33:49Define Example14 as a linear_scan() of XOR
1:33:49Define Example14 as a linear_scan() of XOR
1:33:49Define Example14 as a linear_scan() of XOR
1:34:56Check out the graph of the XOR linear_scan
🏃
1:34:56Check out the graph of the XOR linear_scan
🏃
1:34:56Check out the graph of the XOR linear_scan
🏃
1:35:51Define Example15 as a carry lookahead adder
1:35:51Define Example15 as a carry lookahead adder
1:35:51Define Example15 as a carry lookahead adder
1:36:28Check out the graph of the carry lookahead adder
🏃
1:36:28Check out the graph of the carry lookahead adder
🏃
1:36:28Check out the graph of the carry lookahead adder
🏃
1:36:51Simulate the carry lookahead adder
1:36:51Simulate the carry lookahead adder
1:36:51Simulate the carry lookahead adder
1:37:29Run the carry lookahead adder simulation to find that it doesn't work
🏃
1:37:29Run the carry lookahead adder simulation to find that it doesn't work
🏃
1:37:29Run the carry lookahead adder simulation to find that it doesn't work
🏃
1:38:59Fix pg_compose() to return the operands in the correct order
1:38:59Fix pg_compose() to return the operands in the correct order
1:38:59Fix pg_compose() to return the operands in the correct order
1:40:36Consult the carry lookahead adder graph to determine that it is off-by-one
🏃
1:40:36Consult the carry lookahead adder graph to determine that it is off-by-one
🏃
1:40:36Consult the carry lookahead adder graph to determine that it is off-by-one
🏃
1:41:56Make carry_lookahead_adder() shift the carry right one bit
1:41:56Make carry_lookahead_adder() shift the carry right one bit
1:41:56Make carry_lookahead_adder() shift the carry right one bit
1:44:29rygorous I think you meant c[1:] @ 0
🗪
1:44:29rygorous I think you meant c[1:] @ 0
🗪
1:44:29rygorous I think you meant c[1:] @ 0
🗪
1:44:35Fix carry_lookahead_adder() to slice the carry the correct way
1:44:35Fix carry_lookahead_adder() to slice the carry the correct way
1:44:35Fix carry_lookahead_adder() to slice the carry the correct way
1:44:42Run the carry lookahead adder simulation to find that it passes
🏃
1:44:42Run the carry lookahead adder simulation to find that it passes
🏃
1:44:42Run the carry lookahead adder simulation to find that it passes
🏃
1:45:24Check out the graph of the correct carry lookahead adder
🏃
1:45:24Check out the graph of the correct carry lookahead adder
🏃
1:45:24Check out the graph of the correct carry lookahead adder
🏃
1:46:15Introduce bruteforce_logarithmic_scan()
1:46:15Introduce bruteforce_logarithmic_scan()
1:46:15Introduce bruteforce_logarithmic_scan()
1:47:49Test our bruteforce_logarithmic_scan() and check out the graph
🏃
1:47:49Test our bruteforce_logarithmic_scan() and check out the graph
🏃
1:47:49Test our bruteforce_logarithmic_scan() and check out the graph
🏃
1:48:06Wrap the pg_compose into a PG module
1:48:06Wrap the pg_compose into a PG module
1:48:06Wrap the pg_compose into a PG module
1:49:38Check out the graph of our carry lookahead adder with bruteforce logarithmic scan and PG module
🏃
1:49:38Check out the graph of our carry lookahead adder with bruteforce logarithmic scan and PG module
🏃
1:49:38Check out the graph of our carry lookahead adder with bruteforce logarithmic scan and PG module
🏃
1:50:08Instantiate an 8-bit carry lookahead adder and check out its graph
🏃
1:50:08Instantiate an 8-bit carry lookahead adder and check out its graph
🏃
1:50:08Instantiate an 8-bit carry lookahead adder and check out its graph
🏃
1:51:22Introduce sklansky_scan()
1:51:22Introduce sklansky_scan()
1:51:22Introduce sklansky_scan()
1:54:42Instantiate a 4-bit carry lookahead adder with sklansky_scan and check out its graph
🏃
1:54:42Instantiate a 4-bit carry lookahead adder with sklansky_scan and check out its graph
🏃
1:54:42Instantiate a 4-bit carry lookahead adder with sklansky_scan and check out its graph
🏃
1:55:33Compare bruteforce and Sklansky scan 8-bit carry lookahead adder graphs
🏃
1:55:33Compare bruteforce and Sklansky scan 8-bit carry lookahead adder graphs
🏃
1:55:33Compare bruteforce and Sklansky scan 8-bit carry lookahead adder graphs
🏃
1:56:37spriithy What does the @ operator do?
🗪
1:56:37spriithy What does the @ operator do?
🗪
1:56:37spriithy What does the @ operator do?
🗪
1:57:09Introduce brent_kung_scan() and rename unzip() to interleave()
1:57:09Introduce brent_kung_scan() and rename unzip() to interleave()
1:57:09Introduce brent_kung_scan() and rename unzip() to interleave()
2:04:50Instantiate a 4-bit carry lookahead adder with Brent Kung scan, and check out its graph
🏃
2:04:50Instantiate a 4-bit carry lookahead adder with Brent Kung scan, and check out its graph
🏃
2:04:50Instantiate a 4-bit carry lookahead adder with Brent Kung scan, and check out its graph
🏃
2:08:41That's it for fast adders
🗩
2:08:41That's it for fast adders
🗩
2:08:41That's it for fast adders
🗩
2:10:16Recommend Guy Even's 'On teaching fast adder designs: revisiting Ladner & Fischer'1
📖
2:10:16Recommend Guy Even's 'On teaching fast adder designs: revisiting Ladner & Fischer'1
📖
2:10:16Recommend Guy Even's 'On teaching fast adder designs: revisiting Ladner & Fischer'1
📖
2:11:16That's it for today
🗩
2:11:16That's it for today
🗩
2:11:16That's it for today
🗩