Logic Design, Part 2 | Bitwise Episode Guide

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

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¹^,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¹^,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¹^,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

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

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

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⁴

🗩

25:21A few words on divide and conquer and the fork–join model⁴

🗩

25:21A few words on divide and conquer and the fork–join model⁴

🗩

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

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

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

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()

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

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

🗩

Bitwise

Keyboard Navigation

Global Keys

Menu toggling

In-Menu Movement

Quotes and References Menus

Quotes, References and Credits Menus

Filter Menu

Filter and Link Menus

Credits Menu