Digital Logic Design: A Rigorous Approach

Preface......Page 3
I Preliminaries......Page 27
Sets......Page 29
Relations and Functions......Page 36
Boolean Functions......Page 40
Truth Tables......Page 41
Commutative and Associative Binary Operations......Page 42
Induction and Recursion......Page 47
Induction......Page 48
Recursion......Page 51
Application: One-to-one and Onto Functions......Page 53
Sequences......Page 59
Series......Page 61
Directed Graphs......Page 69
Definitions......Page 70
Topological Ordering......Page 73
Longest path in a DAG......Page 75
Rooted Trees......Page 79
Division and Modulo......Page 85
Bits and Strings......Page 86
Bit Ordering......Page 87
Binary Representation......Page 88
Computing a Binary Representation......Page 91
More on Unique Binary Representation......Page 99
Boolean Formulas......Page 103
Truth Assignments......Page 109
Satisfiability and Logical Equivalence......Page 112
Interpreting a Boolean Formula as a Function......Page 113
Substitution......Page 117
Complete Sets of Connectives......Page 120
Important Tautologies......Page 124
De Morgan's Laws......Page 126
Negation Normal Form......Page 127
Order of Growth Rates......Page 133
Recurrence Equations......Page 137
Computer Stories: Big Endian vs. Little Endian......Page 145
II Combinational Circuits......Page 147
Representation by Formulas......Page 149
Sum of Products......Page 150
Product of Sums......Page 154
The Finite Field GF(2)......Page 157
Polynomials over GF(2)......Page 160
Relation to P vs. NP......Page 161
Minimization Heuristics......Page 162
Basic Terminology and Properties......Page 163
The Implicants' Graph......Page 164
Essential Prime Implicants......Page 165
Optimality Conditions......Page 166
The Quine-McCluskey Heuristic......Page 168
Karnaugh Maps......Page 171
The Digital Abstraction......Page 177
Transistors......Page 178
A CMOS inverter......Page 180
From analog signals to digital signals......Page 181
Transfer functions of gates......Page 183
The bounded-noise model......Page 185
Redefining the digital interpretation of analog signals......Page 186
Stable signals......Page 188
Summary......Page 189
Foundations of combinational circuits......Page 191
Combinational gates - an analog approach......Page 192
Back to the digital world......Page 194
Example......Page 195
Combinational gates......Page 196
Wires and Nets......Page 197
Combinational circuits......Page 199
Properties of Combinational Circuits......Page 202
Simulation and Delay Analysis......Page 204
Completeness......Page 208
Cost and propagation delay......Page 212
Semantics and Syntax......Page 213
Summary......Page 214
Trees......Page 217
Associative Boolean functions......Page 218
Trees of associative Boolean gates......Page 219
Cost analysis......Page 220
Delay analysis......Page 221
Definitions......Page 226
Lower bound on cost......Page 228
Lower bound on delay......Page 230
Summary......Page 232
Decoders and Encoders......Page 235
Buses......Page 236
Division in Binary Representation......Page 238
Definition of Decoder......Page 239
An optimal decoder design......Page 240
Correctness......Page 241
Cost and delay analysis......Page 242
Asymptotic Optimality......Page 244
Concatenation of Strings......Page 245
Brute Force Implementation......Page 246
Implementation and Correctness......Page 247
Reducing the Cost......Page 249
Cost and delay analysis......Page 250
Summary......Page 251
Selectors and Shifters......Page 255
Multiplexers......Page 256
Implementation......Page 257
Cyclic Shifters......Page 260
Correctness and analysis of cost and delay......Page 261
Logical Shifters......Page 264
Implementation......Page 265
Arithmetic shifter......Page 267
Summary......Page 269
Addition......Page 271
Definition of a binary adder......Page 272
Ripple Carry Adder......Page 273
Correctness proof......Page 274
Cone of adder outputs......Page 275
Lower bounds......Page 276
Implementation......Page 277
Delay and cost analysis......Page 278
Implementation......Page 279
Correctness......Page 280
Delay and cost analysis......Page 281
Redundant and non-redundant representation......Page 282
Summary......Page 283
Signed Addition......Page 287
Representation of negative integers......Page 288
Computing a two's complement representation......Page 289
Negation in two's complement representation......Page 290
Properties of two's complement representation......Page 292
Reduction: two's complement addition to binary addition......Page 294
Detecting overflow......Page 296
Determining the sign of the sum......Page 297
A two's-complement adder......Page 298
A two's complement adder/subtractor......Page 299
Summary......Page 301
III Synchronous Circuits......Page 305
Flip-Flops......Page 307
The clock......Page 308
Edge-triggered Flip-Flop......Page 309
Arbitration......Page 311
Arbiters - an impossibility result......Page 312
Necessity of critical segments......Page 315
A Timing Example......Page 316
Bounding Instability......Page 317
D-Latch......Page 321
Clock enabled flip-flops......Page 322
Summary......Page 323
Memory Modules......Page 327
The Zero Delay Model......Page 328
Parallel Load Register......Page 329
Random Access Memory (RAM)......Page 330
Read-Only Memory (ROM)......Page 333
Summary......Page 335
Foundations of Synchronous Circuits......Page 337
Definition......Page 338
Timing Analysis: the canonic form......Page 340
An Easy Example......Page 341
Input/Output Timing Constraints......Page 344
Sufficient Conditions......Page 345
Initialization......Page 346
Functionality: the canonic form......Page 348
Finite State Machines......Page 349
Timing analysis: the general case......Page 350
Timing Constraints......Page 351
Algorithms: feasibility and minimum clock period......Page 352
Algorithms: correctness......Page 353
Simulation of Synchronous Circuits......Page 355
Analysis......Page 356
Summary......Page 357
Problems......Page 358
Synchronous Modules: Analysis and Synthesis......Page 363
Example: a two-state FSM......Page 364
Sequential Adder......Page 365
Implementation......Page 366
Analysis......Page 367
Initialization and the Corresponding FSM......Page 368
Analysis......Page 369
Revisiting Shift Registers......Page 370
Analysis......Page 371
Synthesis and Analysis......Page 373
IV A Simplified DLX......Page 377
The ISA of a Simplified DLX......Page 379
Why use abstractions?......Page 380
Architectural Registers and Memory......Page 381
Instruction Set......Page 383
Encoding of the Instruction Set......Page 389
Examples of Program Segments......Page 391
Summary......Page 392
A Simplified DLX: Implementation......Page 395
The Outside World: The Memory Controller......Page 396
Registers......Page 397
ALU Environment......Page 398
The IR Environment......Page 400
The GPR Environment......Page 401
Control......Page 402
The Control FSM......Page 403
RTL Instructions......Page 405
Examples of Instruction Execution......Page 406
Summary......Page 409
Bibliography......Page 410
Index......Page 419