Logic Design, Part 5

?

?

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)

X, ShiftSpace Toggle category and focus previous

v Invert topics / media as per focus

# Keyboard Navigation

## Global Keys

[, < / ], > Jump to previous / next episodeW, 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

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 nextX, 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)⏫

Previous: 'Logic Design, Part 4'

⏫

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

🏃

🏃

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: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: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: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: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: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: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: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

🗩

⏬

Next: 'Logic Design, Part 6'

⏬