A Modern Digital Logic Curriculum

Fundamental Values

To implement Boolean logic, we need two values for a variable, the minimum to make a distinction or decision: this or that, left or right, but usually true or false, conventionally represented as 1 and 0. We refer to a variable with two possible values as "binary".

With two possible values for a variable, we have four possible variable contents: one value, the other value, neither value, or both values. We will see more about these last two case in XXX. For now, consider a Boolean variable as holding only 1 or 0.

Boolean Functions

The Niladic (whose number of arguments is Nil (none)) Boolean functions take no input variable and produce a constant output variable. Thus 1 and 0 are the Niladic Boolean functions.

The Monadic Boolean functions take one input variable and produce one output variable. Since we only have two possible input values, we have two possible Monadic Boolean Functions:

Wire: 1:1, and 0:0
Inverter: 1:0, and 0:1

The Dyadic Boolean Functions take two input variables and produce one output variable. There are 16 Dyadic Boolean Functions.

(list them here in a meaningful order for later representation as a mux)

From here, we can construct any arbitrary Boolean function with more inputs, such as Triadic (256 cases) and Tetradic (65536 cases) functions, but they are of little use or interest as objects of reasoning. However, Triadic functions will show up in XXX as useful optimizations in extreme cases.

From Binary Sets to Binary Integers (Place Value Notation)

Mapping Addition and Multiplication of Binary Integers

Substraction via Complement Addition (Decimal)

Substraction via Complement Addition (Binary)

Selection: Implementing a 2:1 Multiplexer

4:1 from 2:1

Ripple-Carry Addition from 4:1 Muxes

Carry-Select Addition

Carry Look-Ahead Addition

Constant Propagation as the Fundamental Logic Optimization

Example: From 4:1 Mux to Dyadic Boolean Function

Example: From Addition to Bit-Shift Right

Multiplication: Shifting and Conditional Addition


fpgacpu.ca