Digital Logic, one concept at a time
Curriculum
Master the fundamentals one concept at a time.
14 topics, 2,512 interactive questions and 56 practice exams. Everything here is free. The first 3 topics need no sign-up, and a free account opens the rest.
- 01
Number Systems
No sign-upBinary, hexadecimal and octal, converting between bases, binary addition and subtraction, unsigned ranges, two's complement, sign extension and overflow.
185 steps · 100 lesson questions · about 74 min · 4 practice exams · 186 questions in total
Start this topic →Not startedWhat's covered (37) ↓Hide what's covered ↑
- Number system
- Where place value comes from: bundling
- Place value
- Writing weights as powers
- Radix (base)
- The same rule in every base
- Bit
- Powers of 2 worth knowing
- MSB and LSB
- Adding a 0 on the right doubles
- Decimal → binary
- Odd or even? Look at the LSB
- Unsigned
- How much fits in n bits?
- Byte and nibble
- Hexadecimal
- The 16 nibbles
- Octal
- Binary addition
- Binary subtraction
- Real hardware has a fixed number of bits
- What about negative numbers?
- Sign bit
- Sign-magnitude's problems
- Two's complement
- The number wheel
- Spotting the sign at a glance
- One pattern, three meanings
- Negate: invert, then add 1
- Where this shows up
- Two's complement range
- Sign extension
- Where sign extension shows up
- Carry out and overflow are different things
- Overflow
- Overflow on the number wheel
- Where this shows up: status flags
- 02
Boolean Algebra
No sign-upBoolean variables and operators, truth tables, the laws of Boolean algebra, De Morgan's laws and step-by-step simplification.
178 steps · 97 lesson questions · about 71 min · 4 practice exams · 179 questions in total
Start this topic →Not startedWhat's covered (43) ↓Hide what's covered ↑
- Algebra with only two values
- Boolean variable
- AND
- OR
- + is not addition
- NOT
- Bars on screen, primes when you type
- Same ideas, different symbols
- Literal
- Operator precedence
- A product picks out one input
- Truth table
- Naming the rows
- Proving and disproving
- The laws
- Identity law
- Null law
- Idempotent law
- Complement law
- Involution law
- Duality principle
- Commutative law
- Associative law
- Distributive law
- XOR and XNOR
- The strange one: OR over AND
- A letter can stand for a whole expression
- Absorption law
- Dropping a barred letter
- Combining terms
- De Morgan's laws
- Angle 1: everyday words
- Angle 2: the truth table
- The OR version, checked
- Dual or complement?
- Where this shows up
- Sum of products (SOP)
- Product of sums (POS)
- Measuring simplicity
- A simplification strategy
- Reading the clues
- How do you know you're done?
- Consensus theorem
- 03
Logic Gates
No sign-upAND, OR, NOT, NAND, NOR, XOR and XNOR: symbols, truth tables and expressions, universal gates, and reading multi-gate circuits and waveforms.
175 steps · 98 lesson questions · about 70 min · 4 practice exams · 184 questions in total
Start this topic →Not startedWhat's covered (35) ↓Hide what's covered ↑
- What a gate does
- Optional: what 0 and 1 are physically
- Optional: transistors are switches
- From here on: gates are black boxes
- Three ways to describe a gate
- Reading a gate symbol
- Gate notation
- NOT gate
- Truth tables for more inputs
- AND gate
- OR gate
- Bubble
- NAND gate
- NOR gate
- De Morgan's law
- Optional: why NAND and NOR come first in CMOS
- XOR gate
- An AND term picks out one row
- Where XOR is used: adding bits
- XNOR gate
- Timing diagram
- Gates on a timing diagram
- The method: one column at a time
- Gates with more inputs
- Odd parity (multi-input XOR)
- Reading a circuit
- Typing an expression
- One input, several gates
- Working backwards
- Universal gate
- Tying inputs together
- NOR works the same way
- Bubble pushing
- The four bubble-pushing pairs
- Sum of products
- 04
Combinational Logic
Free accountDesign circuits from word specifications, and use multiplexers, decoders, encoders and comparators.
157 steps · 99 lesson questions · about 63 min · 4 practice exams · 180 questions in total
What's covered (30) ↓Hide what's covered ↑
- Circuits without memory
- Combinational circuit
- Spotting memory
- The design recipe
- Step 1 in detail: the signal legend
- Turning words into logic
- Minterm
- Sum of products (Σm notation)
- The complement: the missing rows
- Always check your simplification
- Multiplexer (MUX)
- The 2:1 MUX
- Feeding signals into a MUX
- The 4:1 MUX
- Bigger MUXes from smaller ones
- Intuition: a MUX is a lookup table
- A MUX can implement any function
- Saving a select line: the recipe
- Decoder
- The 2-to-4 decoder
- Enable, and the DEMUX
- Demultiplexer (DEMUX)
- Building bigger decoders
- Intuition: a decoder hands you every minterm
- The complement trick
- Encoder and priority encoder
- Inside a plain 4-to-2 encoder
- Comparator
- Multi-bit equality
- Choosing a building block
- 05
Boolean Simplification
Free accountCanonical SOP and POS forms, minterms and maxterms, converting between them, systematic algebraic simplification, prime implicants, don't-cares and two-level NAND/NOR circuits.
150 steps · 90 lesson questions · about 60 min · 4 practice exams · 170 questions in total
What's covered (30) ↓Hide what's covered ↑
- One function, many expressions
- Where this shows up
- Conventions used here
- Minterm (recap)
- Sum of minterms (recap)
- Maxterm
- The minterm and maxterm polarity rule in one line
- Product of maxterms (ΠM notation)
- Switching between Σm and ΠM
- The complement in both forms
- From any SOP to Σm
- Shortcut: patterns with dashes
- From any POS to ΠM
- Measuring cost
- Gate-input count
- Adjacent minterms
- Compare bits, not numbers
- Reusing a minterm
- Dropping redundant terms
- Simplifying a POS
- Picture it: patches over the 1s
- Implicant
- Prime implicant
- Which prime implicants to keep
- Don't-care condition
- Where don't care rows come from
- Two-level logic
- Reading a NAND-NAND circuit back
- SOP or POS?
- Mixed practice
- 06
Karnaugh Maps
Free accountSimplify Boolean functions visually: Gray-code layouts, grouping rules, prime implicants and don't-cares.
148 steps · 99 lesson questions · about 59 min · 4 practice exams · 180 questions in total
What's covered (30) ↓Hide what's covered ↑
- Where this shows up
- Karnaugh map
- Two variables
- Gray code ordering
- Three variables
- Four variables
- Common slip: counting cells
- Professors draw K-maps differently
- The layout this course uses
- Group (implicant)
- Grouping rules
- Mistake: groups that aren't a power of two
- Mistake: diagonal groups
- Is it adjacent?
- Common reading slips
- Bigger is better
- Mistake: groups that are too small
- Wrap-around adjacency
- Mistake: missing wrap-around and corners
- An isolated 1
- Check your cover
- Prime implicant
- Essential prime implicant
- Listing prime implicants
- Don't-care condition
- Using don't-cares well
- The minimal SOP recipe
- Mixed practice
- Product of sums (POS) from a K-map
- Reading a sum term directly
- 07
Adders and ALUs
Free accountBuild binary arithmetic from gates: half and full adders, ripple-carry and carry-lookahead adders, subtraction, overflow, and a simple ALU with status flags.
153 steps · 100 lesson questions · about 61 min · 4 practice exams · 180 questions in total
What's covered (27) ↓Hide what's covered ↑
- Arithmetic from gates
- Where this shows up
- Half adder
- Reading off the gates
- Full adder
- The sum is odd parity
- The carry is the majority
- The two-level full adder
- Ripple-carry adder
- Carry numbering
- A 2-bit ripple-carry adder
- The carry has to ripple
- Gate delay model
- Counting conventions
- When does the worst case happen?
- Subtracting with an adder
- Controlled inverter
- Adder/subtractor
- Two kinds of "too big"
- Carry-out when subtracting
- Comparing by subtracting
- Beating the ripple
- Generate and propagate
- Speed and cost
- Arithmetic logic unit (ALU)
- How the blocks fit together in an n-bit ALU
- Status flags
- 08
Latches and Flip-Flops
Free accountHow circuits remember: SR and D latches, edge-triggered D, JK and T flip-flops, and reading timing diagrams.
151 steps · 100 lesson questions · about 60 min · 4 practice exams · 185 questions in total
What's covered (27) ↓Hide what's covered ↑
- Circuits that remember
- Sequential circuit
- A quick test
- SR latch
- Leaving S = R = 1
- NAND SR latch
- Gated D latch
- Edge-triggered
- Finding edges on a waveform
- D flip-flop
- Window or camera?
- Checking your own trace
- Setup and hold time
- Characteristic table
- The D latch's equation
- JK flip-flop
- The JK characteristic equation
- Common JK mistakes
- T flip-flop
- Shortcut: count the toggles
- Frequency and period
- Excitation table
- Asynchronous preset and clear
- Active-low preset and clear
- Synchronous vs asynchronous reset
- Reading timing diagrams: the checklist
- Identifying a device from its waveform
- 09
Registers
Free accountStoring words: parallel-load registers with load enable and clear, shift registers, shifting and rotating, register files and register transfer notation.
148 steps · 97 lesson questions · about 59 min · 4 practice exams · 177 questions in total
What's covered (28) ↓Hide what's covered ↑
- From one bit to a word
- Register
- Notation used in this topic
- The one rule for everything in this topic
- The problem: loading on every edge
- Load enable
- Tempting but wrong: gate the clock
- Getting to a known value
- Asynchronous clear
- Synchronous clear
- Shift register
- Which way is right?
- SISO, SIPO, PISO, PIPO
- Where this shows up
- Moving data between registers serially
- Universal shift register
- Shift left = multiply by 2
- Logical shift right
- Arithmetic shift right
- Rounding: always downwards
- Rotate
- Shift registers that count
- Ring counter
- Johnson counter
- Register file
- The read path: one MUX per output bit
- Register transfer notation
- Where this is going: registers in a CPU
- 10
Counters
Free accountRipple and synchronous binary counters, up/down, mod-N and BCD counters, ring and Johnson counters, and counters as frequency dividers.
153 steps · 100 lesson questions · about 61 min · 4 practice exams · 187 questions in total
What's covered (25) ↓Hide what's covered ↑
- Circuits that count
- Where counters show up
- Binary up counter
- Modulus
- The toggle rule
- Asynchronous (ripple) counter
- Which signal clocks the next stage?
- Every stage divides by 2
- Ripple delay
- Cleaning up a glitchy output
- Synchronous counter
- The next-state table
- How fast can a synchronous counter run?
- Down counter
- Up/down counter
- Count enable
- Parallel load
- Terminal count (carry out)
- Mod-N counter
- Clearing asynchronously
- Mod-N checklist
- BCD (decade) counter
- Ring counter
- Johnson counter
- Counters as frequency dividers
- 11
Finite State Machines
Free accountStates, state diagrams and tables, Moore vs Mealy machines, and designing sequence detectors.
144 steps · 93 lesson questions · about 58 min · 4 practice exams · 175 questions in total
What's covered (22) ↓Hide what's covered ↑
- Memory with a purpose
- Where this shows up
- State
- Finite state machine
- State diagram
- Reading a diagram
- One arrow per input
- Tracing without slipping
- Moore machine
- Mealy machine
- State table
- Which output do I write down?
- Designing, not just reading: the recipe
- Sequence detector
- Non-overlapping version
- Where does a mismatch go? The suffix rule
- Choosing a good test sequence
- Non-overlapping in a Mealy machine
- State encoding
- Unused codes
- Equivalent states
- The design recipe, start to finish
- 12
Memory
Free accountMemory as an array of words: address bits and capacity, RAM and ROM, SRAM and DRAM, ROMs as lookup tables, read/write control and building big memories from small chips.
146 steps · 97 lesson questions · about 58 min · 4 practice exams · 177 questions in total
What's covered (25) ↓Hide what's covered ↑
- From one register to thousands
- Memory, word and address
- Address bits
- Powers of 2 worth knowing by heart
- Capacity and the 2ᵏ × n notation
- Convention: K, M and G
- Addresses in hex
- RAM
- ROM
- Volatile and non-volatile
- SRAM
- DRAM
- Kinds of ROM
- Inside a memory: the address decoder
- Big memories: rows and columns
- Memory control signals
- Reading active-low controls
- Tri-state outputs and the data bus
- A ROM is a truth table in hardware
- Building big from small: wider or deeper?
- Wider words: chips side by side
- More words: decode the top address bits
- The recipe: any memory from any chips
- How to read off a chip select from a range
- Byte addressing
- 13
Timing and Sequential Logic
Free accountPropagation and contamination delay, critical paths, glitches and hazards, setup and hold checks, maximum clock frequency, clock skew, synchronizers and pipelining.
150 steps · 92 lesson questions · about 60 min · 4 practice exams · 172 questions in total
What's covered (24) ↓Hide what's covered ↑
- Real gates are not instant
- Propagation delay
- Contamination delay
- Delays add along a path
- Critical path
- Speeding up a circuit
- Glitch
- Hazard
- Static-0 and dynamic hazards
- Clock
- Where this shows up
- Flip-flop timing parameters
- The register-to-register path
- Setup constraint
- Setup slack
- Many paths, one clock
- Hold constraint
- Clock skew
- Synchronous design rules
- Metastability
- Metastability, intuitively
- Two-flip-flop synchronizer
- Pipelining
- Balancing the stages
- 14
Basic CPU / Computer Architecture
Free accountHow registers, an ALU, memory and a control FSM combine into a working CPU: instruction formats, the fetch–decode–execute cycle, control signals, adding your own instruction, tracing programs, and CPI.
163 steps · 100 lesson questions · about 65 min · 4 practice exams · 180 questions in total
What's covered (35) ↓Hide what's covered ↑
- Putting the pieces together
- Stored-program computer
- Datapath and control unit
- A picture to keep in your head
- Meet Tiny8
- Program counter (PC)
- Instruction register (IR)
- MAR and MDR
- Accumulator and Z flag
- Instruction format
- The Tiny8 instruction set
- How many bits?
- The Tiny8 datapath
- Load enable
- Tiny8's ALU
- Buses
- Register transfer notation
- The instruction cycle
- Execute steps for every instruction
- Control signals
- The 0s matter, and some signals don't
- How to read a clock trace
- What to notice in that trace
- The same JZ, not taken
- Hardwired control
- Decoding with logic
- Adding an instruction yourself: the recipe
- Another way to build it
- Microprogrammed control
- Tracing without slipping
- Clock period and frequency
- Units without tears
- CPI
- CPU execution time
- Single-cycle vs multi-cycle