F3 Fundamentals of Digital Logic Circuits

Don't use night mode to read this chapter

In night mode, the image display will be difficult to recognize, it is recommended to use day mode for reading.

Processor chips are fundamentally digital circuits. Digital circuits are circuits that process digital signals, and digital signals, simply put, are discrete signals represented by 0 and 1. Here, 0 and 1 are not natural numbers in the mathematical sense; instead, they represent two different states of a signal. For simplicity, we refer to these two states as 0 and 1. To distinguish them from the mathematical numbers 0 and 1, they are sometimes called logic 0 and logic 1.

In contrast to digital signals, analog signals are generally continuous. Current and voltage, for example, are analog signals. Circuits that process analog signals are called analog circuits, but they are rarely our focus in processor design.

Therefore, a processor chip is essentially a chip that processes the two signals 0 and 1. Knowledge of digital circuits is fundamental to learning processor chip design. Learning digital circuits means understanding how information is represented, processed, and stored in digital circuits. Specifically, you will learn:

• How to represent information: the physical meanings of the digital signals 0 and 1 in digital circuits
• How to process information: the operating principles of logic gates and combinational logic circuits
• How to store information: the operating principles of sequential logic circuits

Implementing 0 and 1 with Transistors

0 and 1 are abstract concepts. In digital circuits, their physical representations are closely related to transistors.

The most commonly used transistor is the metal–oxide–semiconductor field-effect transistor (MOSFET), commonly referred to as a MOS transistor. Based on their operating principles, MOS transistors are divided into two types: nMOS (N-type MOS, where N stands for Negative) and pMOS (P-type MOS, where P stands for Positive). Both types have three terminals: the gate, source, and drain. Their side views are shown in the figure below.

Transistors are commonly used as circuit components and are connected into circuits like switches. In everyday life, switches are generally controlled manually, such as a light switch. When the switch is turned on, the circuits connected to its two terminals become connected. Unlike manually operated switches, however, a transistor is a special switch controlled by voltages in the circuit. By controlling the voltage at the gate of a MOS transistor, we can determine whether its source and drain are connected.

Taking an nMOS transistor as an example, its behavior can be summarized from its electrical characteristics as follows:

• When the voltage difference between the gate and source, , is sufficiently large, the source and drain conduct, which is equivalent to closing a switch.
• When the voltage difference between the gate and source, , is small, the source and drain are cut off, which is equivalent to opening a switch.

A pMOS transistor behaves similarly to an nMOS transistor. It conducts when is sufficiently large and is cut off when is small.

How Does a Transistor Act as a Voltage-Controlled Switch?

Understanding this question requires some knowledge of high-school physics and chemistry. However, this topic is beyond the scope of processor design and is not something that must be mastered during the "One Student One Chip" learning process. If you are interested, we can provide a brief explanation.

Silicon is the primary material used to manufacture semiconductors. Two silicon atoms, each with four valence electrons, can readily form stable covalent bonds. Therefore, pure silicon does not conduct electricity.

Taking nMOS fabrication as an example, a small amount of a group-III element, such as boron, is doped into silicon to form a p-type substrate, labeled p-substrate in the figure above. An impurity atom in the p-type substrate forms stable covalent bonds with four neighboring silicon atoms but lacks one electron. It can therefore readily attract an electron from another covalent bond. Once an electron leaves its original position, that position can attract another electron to form a covalent bond again. As this process repeats, the p-type substrate behaves as though it contains freely moving positive charges.

After the p-type substrate is formed, two n-type regions, labeled n-channel in the figure above, are created above the substrate, and a small amount of a group-V element, such as phosphorus, is doped into the silicon. An impurity atom in an n-type region forms stable covalent bonds with four neighboring silicon atoms and has one extra electron. This electron can move freely within the n-type region.

To connect the transistor to a power source, two metal electrodes are brought out from the two n-type regions and used as the source and drain. A layer of silicon dioxide is then placed over the surface of the substrate as an insulating dielectric layer, labeled dielectric in the figure above. Another metal electrode is placed above the dielectric layer to serve as the gate.

During operation, the source and drain are connected to the power supply and the circuit. By default, free electrons in the n-type source region cannot cross the p-type substrate to reach the n-type drain region. Therefore, the source and drain do not conduct, and the nMOS transistor is in the cutoff state.

When a sufficiently high voltage is applied to the gate, an electric field forms beneath the dielectric layer. Under the influence of this electric field, the freely moving electrons in the p-type substrate move toward the dielectric layer. Because the electrons cannot pass through the dielectric, they accumulate beneath it and form a conductive channel. This channel connects the source and drain, placing the nMOS transistor in the conducting state.

A pMOS transistor operates on a principle similar to that of an nMOS transistor, although the two are not exactly the same. Interested students may search for additional information.

Because nMOS and pMOS transistors have complementary characteristics, they are commonly used together in digital circuits. This is known as complementary metal–oxide–semiconductor (CMOS) technology. The following is one of the simplest CMOS circuits:

This CMOS circuit operates as follows:

• When a high voltage is applied at point A, the lower nMOS transistor conducts while the upper pMOS transistor is cut off. This is equivalent to connecting point Y to ground, as shown in the middle figure, so the voltage at point Y is low.
• When a low voltage is applied at point A, the lower nMOS transistor is cut off while the upper pMOS transistor conducts. This is equivalent to connecting point Y to the power supply, as shown in the right figure, so the voltage at point Y is high.

As we can see, the CMOS circuit converts the switching characteristics of the nMOS and pMOS transistors into high and low output voltages. By defining a physically high voltage, such as 5 V, as logic 1 (high level), and a low voltage, such as 0 V, as logic 0 (low level), we obtain the two basic signal states used in digital circuits.

Building Logic Gates with Transistors

Merely representing 0 and 1 is not enough. We also need to use CMOS circuits to perform various meaningful transformations on 0 and 1. This process is called performing operations on digital signals.

NOT Gate (Inverter)

Consider the CMOS circuit above. When the input at point A is 1, the output at point Y is 0; when the input at point A is 0, the output at point Y is 1. This is exactly the logical NOT operation. This gate circuit is called a NOT gate, or an inverter.

NAND Gate

Now consider another gate circuit below.

Its function is not easy to understand by inspecting the circuit structure directly, so we need to analyze its behavior. Specifically, because P1 and P2 are connected in parallel, Y is 1 whenever either of them conducts. In addition, because N1 and N2 are connected in series, Y is 0 only when both of them conduct. Therefore, we can summarize its behavior in the following table:

A	B	P1	P2	N1	N2	Y
0	0	conductivity	conductivity	cut-off	cut-off	1
0	1	conductivity	cut-off	cut-off	conductivity	1
1	0	cut-off	conductivity	conductivity	cut-off	1
1	1	cut-off	cut-off	conductivity	conductivity	0

According to the table above, the circuit outputs 0 when both inputs are 1; otherwise, it outputs 1. This is exactly the logical NAND operation, so this gate circuit is a NAND gate.

AND Gate

Connecting the output of a NAND gate to the input of a NOT gate produces an AND gate. Compared with the symbol for a NAND gate, the symbol for an AND gate does not have an inversion bubble at its output. In logic gate symbols, this bubble indicates inversion.

Analyze the Gate Circuit

Try to analyze the behavior and function of the following gate circuit.

Transistor Structure of an OR Gate

The following is the logic symbol for an OR gate. Try to draw its transistor-level circuit.

Three-Input NAND Gate

The gate circuits introduced above all have two inputs. Sometimes, however, we need to perform operations on multiple input signals. One example is a three-input NAND gate. Its behavior can be expressed by the Boolean expression Y = ~(A & B & C), where & represents the AND operation. Based on this expression, we can build a three-input NAND gate using a two-input AND gate and a two-input NAND gate, as shown in the left figure. Alternatively, we can build a three-input NAND gate directly with transistors, as shown in the right figure.

Comparison of the number of transistors required for the two implementations

It is not difficult to analyze that the above transistor structure also realize the function of a three-input NAND gate.Try to compare the number of transistors required in the two implementations.

Hint: For designs built with gate circuits, The number of transistors can be considered as the sum of the number of transistors used in all gate circuits in the design.

Full-Custom Circuits: Designing Circuits at the Transistor Level

A circuit designed directly at the transistor level is called a full-custom circuit. From the three-input NAND gate example, we can see that a full-custom circuit requires fewer transistors and therefore occupies a smaller area. In actual production, full-custom circuits can also achieve higher clock frequencies and lower power consumption.

However, full-custom circuits are difficult to design and require long development cycles. Modern processor chips often contain hundreds of millions of transistors, so developing the entire chip using full-custom design is impractical. For very-large-scale integrated circuits, semi-custom design methods are more commonly used.

Semi-custom circuit design can be further divided into standard-cell-based design and gate-array-based design. In standard-cell-based design, commonly used logic elements, such as AND gates, OR gates, and flip-flops, are first designed using full-custom methods. These logic elements are called standard cells, and large-scale circuits are then constructed from them. Returning to the three-input NAND gate example above, if the two-input AND gate and the two-input NAND gate are treated as standard cells, building the three-input NAND gate from them can be regarded as a semi-custom design. A common example of gate-array-based design is the FPGA. However, we will not use an FPGA in the following sections. Interested students may search for additional information.

In modern processor design, standard-cell-based semi-custom design is used in most cases. Full-custom design is applied only to certain critical modules when extreme performance is required, such as when commercial products compete for market share through higher performance.

XOR Gate

An XOR gate performs the exclusive OR (XOR) operation. Its logic symbol is shown in the figure below.

Exclusive OR is a special operation commonly used when processing logical data. Its truth table is shown below:

A	B	Y
0	0	0
0	1	1
1	0	1
1	1	0

The XOR operation can be understood in two ways:

1. The word “exclusive” indicates “difference.” Therefore, the result is 1 when inputs A and B are different; otherwise, the result is 0.
2. An OR operation produces 1 when at least one of its two inputs is 1. Unlike OR, XOR excludes the case in which both inputs are 1. Therefore, it is called “exclusive OR,” where “exclusive” corresponds to the word exclusive. In contrast, the OR operation is also called “inclusive OR,” indicating that the case in which both inputs are 1 is included.

From the truth table, we can derive the corresponding Boolean expression as follows:

1. Construct a product term for each input combination. For each row in the truth table, consider every input signal. If an input is 1, use the input signal itself; if an input is 0, use its complement. Apply the AND operation to these signals to obtain the description of that product term. For example, the row in which A = 1 and B = 0 is described as A & ~B.
2. Combine the product terms whose output is 1 using the OR operation to obtain the final Boolean expression. In the XOR truth table, there are two cases in which the output is 1: A = 1, B = 0, described as A & ~B; and A = 0, B = 1, described as ~A & B. Applying the OR operation to these two descriptions gives the Boolean expression for XOR: Y = A ^ B = (A & ~B) | (~A & B).

The steps above allow us to convert a truth table into a Boolean expression composed of AND and OR operations. Based on this Boolean expression, we can easily construct the corresponding circuit using AND gates and OR gates.

Karnaugh Map Simplification

You may have heard of this technique in some digital circuit textbooks. If you have not, that may actually be a good thing. You may need to learn it for an exam, but you will hardly ever use it in a hands-on project such as "One Student One Chip."

The point is that this technique scales very poorly. In real projects, you may need to deal with five or more variables, or even dozens of them, making Karnaugh maps highly inefficient for simplifying such expressions. In fact, modern tools usually simplify Boolean expressions using algorithms such as the Quine–McCluskey (QMC) algorithm or the Espresso algorithm. Therefore, you will rarely need to simplify Boolean expressions manually. The method introduced above is sufficient to help you derive a correct Boolean expression, while modern tools can handle the simplification. Interested students may search for additional information about these algorithms.

Build an XOR Gate Using Other Logic Gates

In Logisim, try to build an XOR gate using the logic gates mentioned above. After completing the circuit, verify your design through simulation.

Once your implementation works correctly, calculate how many transistors it uses.

Find a Better Implementation

Without considering a full-custom circuit, try to find an implementation of the XOR gate that uses the fewest transistors, and test your design in Logisim.

Hint: One implementation requires only 14 transistors, so an optimal implementation should use no more than 14 transistors.

A Full-Custom Circuit for the XOR Gate

The figure below shows one full-custom implementation of an XOR gate. Try to analyze its behavior.

Design an XNOR Gate

Another operation is the exclusive NOR (XNOR) operation. When inputs A and B are the same, the result is 1; otherwise, the result is 0. The XNOR operation can be regarded as the inverse of the XOR operation.

In Logisim, try to build an XNOR gate using the logic gates introduced above. After completing the circuit, verify your design through simulation.

A Full-Custom Circuit for the XNOR Gate

Try to build an XNOR gate using the fewest possible transistors.

Hint: One implementation requires only 6 transistors, so an optimal implementation should use no more than 6 transistors.

Machine representation of integers

We already know that CMOS circuits can represent and process 0 and 1. However, the physical world in which we live contains far more than just 0 and 1. We therefore need to consider how various kinds of information in the physical world can be represented using 0 and 1. This representation process is called encoding. Since the physical world contains many kinds of information, we will first consider how to represent natural numbers.

Binary Numeral System

We have had a basic understanding of the concept of numbers since primary school or even kindergarten. In everyday life, we use the decimal numeral system. The value of a decimal numeral—the actual numerical value it represents—can be obtained through a weighted-sum expansion. For example, the decimal numeral 734 can be expanded as follows:

In general, for an -digit base- numeral , its value can be obtained through the following weighted-sum expansion:

Here, is called the base, and is called the weight of digit .

Setting and restricting each to either 0 or 1 gives us the binary numeral system. Because the decimal system also uses the digits 0 and 1, prefixes or subscripts are generally added in writing to indicate that a numeral is binary. Some programming languages use the prefix 0b to denote a binary numeral, such as 0b00101110; some textbooks use the subscript , such as . In these handouts, we primarily use the prefix 0b. For example, the value of the binary numeral 0b00101110 is

To convert a binary numeral to a decimal numeral, use the following weighted-sum expansion:

To convert a decimal number to binary, we need to determine each binary digit in the weighted-sum expansion. To do so, we can rewrite the expansion above as follows:

From this rewriting, we can see that if a decimal number is repeatedly divided by 2, the remainders obtained in sequence correspond to . We can use the repeated division-by-2 method to list this calculation process. For example, for the decimal number 46:

2 | 46   -> 0          ^  lower-bit
  +----                |
 2 | 23   -> 1         |
   +----               |
  2 | 11   -> 1        |
    +----              |
   2 | 5    -> 1       |
     +----             |
    2 | 2    -> 0      |
      +----            |
     2 | 1    -> 1     |  higher-bit
       +----
         0 (Business is zero, end.)

Finally, arranging all the remainders from the most significant bit to the least significant bit gives 0b101110, which is the binary representation of 46. This is consistent with 0b00101110 from the previous example after omitting the leading 0s.

Hexadecimal Numeral System

Although binary numbers can be processed directly by digital circuits, they are difficult for humans to read and remember. For example, it is difficult to determine the number of digits in the binary number 0b1011111011101111 at a glance. In addition, converting between binary and decimal requires a certain amount of arithmetic, which is generally difficult for humans to perform quickly.

To address these problems, the hexadecimal numeral system is commonly used in computer-related fields. In hexadecimal, each digit has 16 possible values. In addition to 0–9, the letters a, b, c, d, e, and f (uppercase letters may also be used) represent the values 10, 11, 12, 13, 14, and 15, respectively. Some programming languages use the prefix 0x to denote a hexadecimal number, such as 0xbeef; some textbooks use the subscript , such as . In these handouts, we primarily use the prefix 0x. Similarly, conversions between decimal and hexadecimal can be performed using weighted-sum expansion and repeated division. For example, the weighted-sum expansion of the hexadecimal number 0xbeef is

Although digital circuits cannot process hexadecimal numbers directly, , so one hexadecimal digit can be converted directly to four binary digits, and vice versa. This greatly improves the efficiency of conversion between hexadecimal and binary. For example, for the binary number 0b1011111011101111, we can divide its digits into groups of four from right to left, padding the most significant group with leading 0s if it contains fewer than four digits, and then write the corresponding hexadecimal digit for each group:

1011 1110 1110 1111
  |    |    |    |
  b    e    e    f

Therefore, the corresponding hexadecimal number is 0xbeef. Compared with its binary representation 0b1011111011101111, the hexadecimal representation 0xbeef is much more concise and compact.

Octal Numeral System

The octal numeral system is also used in some computing scenarios. Its principles are similar to those of hexadecimal. Interested students may derive the conversion methods between octal and decimal, as well as between octal and binary.

Building Basic Combinational Logic Circuits with Logic Gates

With logic gates, we can combine multiple gate circuits to build modules commonly used in digital circuits.

Decoder

A decoder is a circuit that converts a -bit input into at most distinct outputs. A common type of decoder is the one-of-n decoder, which has input bits and output bits. It interprets the input as a binary number , sets output to 1, and sets all other outputs to 0. Since exactly one output bit is 1, this output format is also known as one-hot encoding. For example, a 2-to-4 decoder has two input bits, , and four output bits, . Its truth table and circuit diagram are shown below:

0	0		0	0	0	1
0	1		0	0	1	0
1	0		0	1	0	0
1	1		1	0	0	0

Build a 2-to-4 Decoder

In Logisim, try to build a 2-to-4 decoder using logic gates. It has a 2-bit input and a 4-bit output. After completing the circuit, verify your design through simulation.

Logisim also provides ready-made components such as decoders. However, you are still required to build them using logic gates so that you can better understand the fundamental principles of digital circuits.

In computers, one-of-n decoders are commonly used to implement part of the addressing process. In this case, the input to the decoder is an address, while its outputs are selection signals. The selection signal corresponding to the address is set to 1.

Configuring the Number and Polarity of Logic-Gate Inputs

In Logisim, you can configure the number and polarity of the inputs to a logic gate. The polarity property determines whether a signal is inverted before entering the logic gate. If inversion is enabled, a circle appears at the corresponding input terminal to indicate inversion. For detailed configuration instructions, refer to the section on logic gates in the official documentation.

Addresses and Addressing

“Address” is a technical term in computing, but it can also be understood through examples from everyday life. You may have used Excel to view a table. Each row in the table stores an item, and multiple items are usually stored consecutively in increasing row-number order. Excel displays row numbers on the left, allowing you to quickly identify the row you are currently viewing. To find the item in row 176, you do not need to examine every row starting from row 1. Instead, you can drag the window's scroll bar and quickly move to row 176. This is possible because the row numbers are consecutive, allowing you to skip the preceding rows efficiently.

In fact, much of the data in a computer is also stored consecutively, much like a table. For example, memory can be regarded as a huge table in which each row is a storage unit capable of storing one byte of data. For a 4 GB memory module, this table contains rows. Because these storage units are arranged consecutively, the computer does not need to examine them one by one from the first unit when accessing a particular storage unit. Instead, it can use a “row number” to locate the corresponding storage unit directly. This “row number” is called an address in computing, and the process of locating a storage unit according to its address is called addressing.

A computer can quickly locate the corresponding storage unit using an address because a one-of-n decoder can rapidly convert the address into a group of selection signals, which are then used to select the target data.

Subcircuits in Logisim

Decoders will be used frequently in subsequent digital circuit designs. To avoid repeatedly designing the same circuit, Logisim provides a subcircuit feature: a circuit only needs to be designed once and can then be instantiated repeatedly. For detailed instructions, read the Subcircuits section of the official manual.

After learning how to use subcircuits in Logisim, try to encapsulate the decoder you designed as a subcircuit.

Extending the Decoder

A 3-to-8 decoder has a 3-bit input and an 8-bit output. Try to instantiate several 2-to-4 decoders—the exact number is left for you to determine—and add a small number of logic gates to implement a 3-to-8 decoder. After completing the circuit, verify your design through simulation.

In Logisim, a module's input and output signals are usually connected to input or output components, whose states indicate the current values of those signals. To inspect the current value of an intermediate signal, use the Probe component provided in the component library. You can find it under the Wiring category in the Logisim component library. RTFM for detailed usage instructions.

Configuring the Data Bit Width of Components

In Logisim, you can configure the data bit width of a component. For example, when the data bit width of an AND gate is set to 4, each terminal can connect to a 4-bit signal. Functionally, this is equivalent to using four 1-bit AND gates to process the corresponding bits of four-bit signals independently. Data bit widths make it convenient to design circuits that perform the same operation on multiple bits. For detailed configuration instructions, refer to the section on logic gates in the official documentation.

You may also need to extract several bits from a group of signals or combine several individual signals into a single group for connection. For this purpose, use the Splitter component, which can be found under the Wiring category in the Logisim component library. RTFM for detailed usage instructions.

Another common type of decoder is the code translator, which converts an input in one encoding into an output in another encoding according to specified rules. Unlike a one-of-n decoder, a code translator does not require its output to contain at most one 1.

A common application of a code translator is the 7-segment decoder. A 7-segment display is an output component composed of seven light-emitting diodes arranged in the shape of the digit 8, as shown in the figure below. The letters a through g identify the positions of the seven segments. When a corresponding control signal is asserted, that segment lights up. The figure also includes a decimal point labeled h, which is used in applications that need to display decimal fractions.

   a
  ---
f| g |b
  ---
e|   |c
  ---    .h
   d

A 7-segment decoder interprets a 4-bit input as a binary integer and produces a group of control signals that turn the segments of a 7-segment display on or off, allowing the display to show the digit corresponding to the input. For example:

input    output
         abcdefgh
0100     01100110

The example above shows how to display the digit 4 on a 7-segment display. Specifically, displaying 4 requires segments b, c, f, and g to be turned on, so their corresponding control signals must be asserted. Here, we assume that the signals are active-high; in practice, you should verify the input polarity of the 7-segment display component. The control signals for the remaining segments should be deasserted. If the outputs are arranged from a to h from left to right, the output control signals should be 01100110. Since the binary representation of 4 is 0b0100, the 7-segment decoder should output 01100110 when its input is 0100. In the same way, you can derive the input and output patterns for the digits 0 through 9.

Build a 7-Segment Decoder

In Logisim, try to build a 7-segment decoder using logic gates. It has a 4-bit input and an 8-bit output, connected to a DIP switch and a 7-segment display, respectively. The decoder should support displaying decimal digits: when the input represents a digit from 0 to 9, the 7-segment display should show the corresponding digit; for all other inputs, it should display only the decimal point. After completing the circuit, verify your implementation through simulation.

Hint:

• The 7-segment display component can be found in the component library. After instantiating it, hover the mouse pointer over a port to view a description of that port's function.
• You can first use a one-of-n decoder to generate a one-hot code, and then use a layer of OR gates to determine under which input values each segment should be turned on.

Build a 7-Segment Decoder (2)

In Logisim, try to build a 7-segment decoder that supports hexadecimal digits using logic gates. In addition to the decimal digits described above, when the input represents a value from 10 to 15, the 7-segment display should show A, b, C, d, E, and F, respectively. After completing the circuit, verify your implementation through simulation.

Encoder

An encoder performs the inverse function of a one-of-n decoder: it converts a one-hot code into the corresponding binary value. Specifically, an encoder has input bits and output bits. If the input is a valid one-hot code and bit is 1, the output is the binary representation of . If the input is not a valid one-hot code, the output is undefined.

For example, a 4-to-2 encoder has four input bits, , and two output bits, . Its truth table is shown below. When the input is not a valid one-hot code, the output is represented by x, indicating that it is undefined and may take any value.

0	0	0	1		0	0
0	0	1	0		0	1
0	1	0	0		1	0
1	0	0	0		1	1
oth	er	cond	ition		X	X

Understanding Undefined Outputs

Some operations or modules produce meaningful outputs only when certain preconditions are satisfied. Division in mathematics is one example. You have probably heard statements such as “division by zero is not allowed.” However, “is not allowed” is an expression in natural language rather than mathematical language. More precisely, a nonzero divisor is a precondition for division. When the divisor is 0, this precondition is no longer satisfied, so no correct and meaningful result can be defined. The result is therefore said to be undefined.

The encoder example above is similar. A valid one-hot input is a precondition for the encoder to operate correctly. When the input is not one-hot, this precondition is not satisfied, so no correct and meaningful output can be defined.

This implies a usage contract: if users expect the encoder to produce correct results, they must ensure that the precondition of providing a valid one-hot input is satisfied. Conversely, if this precondition is not satisfied, the user has violated the contract. The encoder's output is then undefined, and the user is responsible for any consequences caused by subsequent circuits processing that undefined output.

At the digital circuit level, each encoder output signal must be either 0 or 1. However, when the output is undefined, neither value has any practical meaning. Therefore, the encoder designer may assign either value to the output signals in these undefined cases. According to the usage contract above, users of the encoder should not allow subsequent circuits to process these undefined output signals.

Therefore, when designing the encoder, we do not need to consider its outputs under other input conditions. We only need to ensure that it produces the correct output when the input is one-hot:

Build an Encoder

In Logisim, try to build a 16-to-4 encoder using logic gates. It has a 16-bit input and a 4-bit output, connected to a DIP switch and a 7-segment decoder, respectively, so that the encoder's output is displayed as a hexadecimal digit on the 7-segment display. After completing the circuit, verify your implementation through simulation.

In computers, encoders are commonly used to generate the corresponding address from selection signals represented by one-hot codes. Another way to understand their function is that they locate the position of the 1 in a one-hot code.

The encoder introduced above requires users to ensure that the input is one-hot. To produce valid information even when the input is not one-hot, another type of encoder is needed: the priority encoder. A priority encoder has input bits and output bits. Unlike the encoder introduced above, a priority encoder allows multiple input bits to be 1. In this case, the highest-order 1 is encoded. Therefore, if the input is not all zeros, the output indicates the position of the highest-order 1; if the input is all zeros, the output is undefined.

For example, a 4-to-2 priority encoder has four input bits, , and two output bits, . Its truth table is shown below.

0	0	0	1		0	0
0	0	1	X		0	1
0	1	X	X		1	0
1	X	X	X		1	1
0	0	0	0		X	X

Build a 4-to-2 Priority Encoder

Based on the truth table above, try to derive the Boolean expression for each output bit. Then build a 4-to-2 priority encoder using logic gates in Logisim. After completing the circuit, verify your design through simulation.

After completing the implementation, compare the numbers of logic gates required by the 4-to-2 encoder and the 4-to-2 priority encoder.

Extend the Priority Encoder

A 16-to-4 priority encoder has 16 input bits and 4 output bits. Try to instantiate several 4-to-2 priority encoders and add a small number of logic gates to implement a 16-to-4 priority encoder. Then connect the 16-to-4 priority encoder to a DIP switch and a 7-segment decoder so that its output is displayed as a hexadecimal digit on the 7-segment display. After completing the circuit, verify your implementation through simulation.

Counting Leading and Trailing Zeros and Ones

Computers sometimes need to count the number of leading zeros in a data word—that is, the number of consecutive 0s starting from the most significant bit of its binary representation. Suppose the data width is 16 bits. For the value 16392, whose binary representation is 0b0100000000001000, the number of leading zeros is therefore 1.

Similarly, we can define trailing zeros as the number of consecutive 0s starting from the least significant bit of a data word. Using 16392 as an example again, the number of trailing zeros is 3. Leading ones and trailing ones can be defined in the same way.

Think about how these values can be calculated efficiently using a priority encoder.

Multiplexer

A multiplexer selects one of several data inputs according to its select input and forwards the selected data to the output. A multiplexer is also called a MUX, or simply a selector. The simplest multiplexer is a 1-bit 2-to-1 multiplexer, which selects one of two 1-bit data inputs according to the select input. Its logic symbol, circuit structure, and truth table are shown below.

0
1

As we can see, a multiplexer contains a one-of-n decoder. If the multiplexer’s select signal is regarded as an address, the decoder generates the corresponding selection signals. These signals allow the selected data input to pass through an AND gate, while the unselected data inputs are forced to 0 after passing through their AND gates. Finally, an OR gate forwards the selected data to the output.

Build a 1-Bit 2-to-1 Multiplexer

In Logisim, try to build a 1-bit 2-to-1 multiplexer using logic gates. After completing the circuit, verify your design through simulation.

Multiplexers are used frequently in computers because computers are fundamentally designed to process data, and data can come from many sources and be processed in many different ways. Therefore, a large number of multiplexers are needed to select among data sources and processing results.

Build a 3-Bit-Wide 4-to-1 Multiplexer

Try to draw the circuit structure of a 3-bit-wide 4-to-1 multiplexer, and then build it using logic gates in Logisim. After completing the circuit, verify your design through simulation.

Hint:

• If you do not understand what a “3-bit-wide 4-to-1 multiplexer” means, carefully review the description of the “1-bit 2-to-1 multiplexer” above.
• For each bit of the data inputs, the selection signals generated by a one-of-n decoder can be used to select the corresponding input.

Build a 7-Segment Display with a Switchable Numeral System

Use five DIP switches and one 7-segment display to implement the following function: four DIP switches serve as the data input, while the remaining DIP switch selects the numeral system. When the select signal is 0, the 7-segment display shows the input in decimal; when the select signal is 1, it shows the input in hexadecimal. The two display modes differ when the input value is between 10 and 15.

Comparator

A comparator checks whether every corresponding bit of two inputs is identical. Since XOR gates and XNOR gates can compare two 1-bit values, a multi-bit comparator can be constructed using XOR gates or XNOR gates. The figure below shows the circuit structure of a 4-bit comparator.

Build a Comparator

In Logisim, try to build a 4-bit comparator using logic gates. Then use two groups of DIP switches to determine whether two groups of data are equal. If they are equal, turn on an LED. After completing the circuit, verify your design through simulation.

Adder

Addition is the foundation of arithmetic operations, so we need to consider how to implement it using logic gates. First, consider a 1-bit adder. The inputs to an addition operation are two addends, and the output is the sum . Since addition may produce a carry, a carry output is also required to preserve this information. Based on the rules of addition, we can easily derive the truth table of a 1-bit adder.

A	B		S	C
0	0		0	0
0	1		1	0
1	0		1	0
1	1		0	1

Specifically, the sum is 1 if and only if the two addends are different, while the carry is 1 if and only if both addends are 1. From the truth table, we obtain the Boolean expressions for and : S = A ^ B, C = A & B.

For a multi-bit adder, the carry generated by a lower bit must participate in the addition at the next higher bit. Therefore, we need to design a new adder that accepts the carry from the lower bit as an input. Specifically, this adder has three inputs, A, B, and Cin, where Cin represents the carry-in from the lower bit; it has two outputs, S and Cout, where Cout represents the carry-out generated by the addition. To distinguish it from the adder described above, an adder with a carry-in is called a full adder (FA), while the adder described above, which has no carry-in, is called a half adder (HA).

Build a 1-Bit Full Adder

Try to derive the truth table of a 1-bit full adder, and then build a 1-bit full adder using logic gates in Logisim. After completing the circuit, verify your design through simulation.

Build a 1-Bit Full Adder (2)

Try to instantiate several half adders and add a small number of logic gates to implement a 1-bit full adder. After completing the circuit, verify your design through simulation.

With a full adder, we can build a multi-bit adder. For example, the figure below shows the circuit structure of a 4-bit adder. As we can see, a multi-bit adder operates much like the multi-digit addition learned in primary school: the calculation proceeds bit by bit from the least significant bit to the most significant bit. The difference is that primary-school arithmetic uses decimal addition, whereas the circuit here performs binary addition. This type of multi-bit adder is called a ripple-carry adder (RCA), because the carry generated during the calculation propagates from the lower bits to the higher bits like a ripple.

Build a 4-Bit Adder

In Logisim, try to build a 4-bit adder using logic gates. Use 7-segment displays to show the adder's two inputs and result in hexadecimal, and use an LED to indicate whether the addition produces a carry-out. After completing the circuit, verify your design through simulation.

Machine-Level Representation of Integers

Recall the example from the binary representation introduced above:

In this representation, each binary digit contributes to the magnitude of the value. This representation is called an unsigned binary integer, or simply an unsigned integer. For an -bit unsigned integer, the minimum value is 0 and the maximum value is . The adder you implemented above is, in fact, an unsigned integer adder.

How, then, should a computer represent negative integers? In mathematics, we represent a negative number by placing a minus sign - before its absolute value, such as -5. Since computers can process only binary data, we need to consider how integers, including negative integers, can be encoded in binary. A straightforward approach is to use one binary bit to encode the sign of an integer and use the remaining bits to encode its absolute value. This representation is called a signed binary integer, or simply a signed integer.

Sign-and-Magnitude Representation

Sign-and-magnitude is an intuitive encoding scheme. The most significant bit is the sign bit: 0 represents a positive number, while 1 represents a negative number. The remaining bits represent the absolute value of the corresponding value. For example:

0b00000111 = 7
0b10000111 = -7
0b00100010 = 34
0b10100010 = -34

Consider performing sign-and-magnitude addition using an 8-bit RCA:

  0b00000111 (7)      0b10000111 (-7)      0b10000111 (-7)      0b00000111 (7)
 +0b00100010 (34)    +0b10100010 (-34)    +0b00100010 (34)     +0b10000111 (-7)
  ------------        ------------          ------------          ------------
  0b00101001 (41)     0b00101001 (41)       0b10101001 (-41)      0b10001110 (-14)

From the observations above, we can draw the following conclusions:

• When both operands are positive, the result obtained by adding them with an RCA, interpreted as a sign-and-magnitude number, is consistent with the mathematical sum of the values represented by the two operands. Therefore, sign-and-magnitude addition can be performed directly with an RCA in this case.
• When both operands are negative, the result produced by the RCA does not match the mathematical result, with the difference occurring in the sign bit. Therefore, the circuit needs to handle the sign bit specially in this case.
• When only one operand is negative, the result produced by the RCA does not match the mathematical result. Both the sign bit and the magnitude may be incorrect. Therefore, an RCA cannot be used directly for sign-and-magnitude addition in this case.

In fact, when computing the third case mathematically, the operand with the smaller magnitude should be subtracted from the operand with the larger magnitude, and the sign of the result should be taken from the operand with the larger magnitude. This means that a sign-and-magnitude adder also requires a subtractor. It must then select the correct result according to the signs and magnitudes of the two operands.

Build a 4-Bit Subtractor

Following the design approach used for the 4-bit adder, try to build a 4-bit subtractor using logic gates in Logisim. Use 7-segment displays to show the subtractor's two inputs and result in hexadecimal, and use an LED to indicate whether the subtraction produces a borrow. After completing the circuit, verify your design through simulation.

Build a 4-Bit Sign-and-Magnitude Adder

After understanding how a sign-and-magnitude adder works, use components such as adders, subtractors, and multiplexers to build a 4-bit sign-and-magnitude adder in Logisim. To display the sign bit, you may instantiate an additional 7-segment display: show a minus sign - when the result is negative, and leave it blank otherwise. After completing the circuit, verify your design through simulation.

One's Complement

One's complement is another encoding scheme that attempts to address the problems involving negative numbers in sign-and-magnitude addition. Specifically, positive numbers and 0 are represented in the same way as in sign-and-magnitude representation. A negative number is represented by taking the sign-and-magnitude representation of its positive counterpart and inverting every bit. For example:

0b00000111 = 7
0b11111000 = -7
0b00100010 = 34
0b11011101 = -34

Consider performing one's complement addition using an 8-bit RCA:

  0b00000111 (7)      0b11111000 (-7)      0b11111000 (-7)      0b00000111 (7)
 +0b00100010 (34)    +0b11011101 (-34)    +0b00100010 (34)     +0b11111000 (-7)
  ------------        ------------          ------------          ------------
  0b00101001 (41)     0b11010101 (-42)      0b00011010 (26)       0b11111111 (-0)

From the observations above, we can draw the following conclusions:

• When both operands are positive, the result produced by the RCA, interpreted as a one's complement number, is consistent with the mathematical sum of the values represented by the two operands. Therefore, one's complement addition can be performed directly with an RCA in this case.
• When one operand is negative, the result produced by the RCA does not match the mathematical result. Although the sign bit is correct, the magnitude is incorrect.
• In particular, when two numbers that are additive inverses of each other are added, the result is always 0b11111111 according to the definition of one's complement. Interpreted as a one's complement number, its value is -0. If -0 is regarded as the mathematical value 0, the RCA result is correct.

However, using -0 as an input to the RCA again produces incorrect results:

  0b00000111 (7)      0b11111000 (-7)
 +0b11111111 (-0)    +0b11111111 (-0)
  ------------        ------------
  0b00000110 (6)      0b11110111 (-8)

The examples above show that an RCA cannot be used directly to perform one's complement addition. One way to implement one's complement addition is to first convert each one's complement operand into an equivalent sign-and-magnitude representation, use a sign-and-magnitude adder to compute the result, and then convert the result back into an equivalent one's complement representation.

Build a 4-Bit One's Complement Adder

Following the approach described above, try to build a 4-bit one's complement adder in Logisim. After completing the circuit, verify your design through simulation.

Build a 4-Bit One's Complement Adder (2)

In fact, only a small adjustment to the result produced by the RCA is needed to obtain the correct result for one's complement addition. Examine several 3-bit one's complement additions, identify the pattern behind the discrepancy in the results, and then add the corresponding circuit to the RCA to build a 4-bit one's complement adder in a simpler way. After completing the circuit, verify your design through simulation.

Two's Complement

Two's complement is the integer encoding most commonly used in modern computers. It further eliminates the one-off discrepancy that occurs in one's complement arithmetic. Specifically, positive numbers and 0 are represented in the same way as in sign-and-magnitude representation. A negative number is represented by inverting every bit of the sign-and-magnitude representation of its positive counterpart and then adding 1. For example:

0b00000111 = 7
0b11111001 = -7
0b00100010 = 34
0b11011110 = -34

For an -bit two's complement number, the maximum value is represented by 0b011...11, whose value is , while the minimum value is represented by 0b100...00, whose value is . The minimum value is special in two's complement because it cannot be obtained by applying “invert all bits and add 1” to a corresponding positive value. For example, in 8-bit two's complement, the maximum value is 0b01111111 = 127; applying “invert all bits and add 1” gives 0b10000001 = -127. The minimum value, however, is 0b10000000 = -128; applying “invert all bits and add 1” gives 0b01111111 + 1 = 0b10000000 = -128, which is the original value itself. This is because 128 is outside the range representable by an 8-bit two's complement number.

Suppose the two's complement representation of a positive integer is , and the two's complement representation of its additive inverse is . By the definition of two's complement,

where denotes the bitwise complement of . Expanding the binary representations on both sides as weighted sums gives

Moreover, since is either 0 or 1, is correspondingly 1 or 0. Therefore, .

Now consider the numerical value represented by :

Therefore, the sign bit of a two's complement number can be assigned the weight when expanding the representation to obtain its numerical value. For example, expanding 0b11111001 in this way gives

which is consistent with the value represented by the encoding.

Consider performing two's complement addition using an 8-bit RCA:

  0b00000111 (7)      0b11111001 (-7)      0b11111001 (-7)      0b00000111 (7)
 +0b00100010 (34)    +0b11011110 (-34)    +0b00100010 (34)     +0b11111001 (-7)
  ------------        ------------         ------------         ------------
  0b00101001 (41)     0b11010111 (-41)     0b00011011 (27)      0b00000000 (0)

From these observations, we can see that when an RCA performs two's complement addition, the result remains mathematically correct even when the inputs include negative numbers. This means that an RCA can also be used to perform two's complement subtraction. Mathematically, . Since we have shown that the result produced by the RCA is mathematically correct regardless of the values of and , we have

A + (-B) computed by an RCA = A + (-B) in mathematics = A - B in mathematics

It is precisely because both two's complement addition and subtraction can be performed using an adder that modern computers commonly use two's complement to represent integers.

Why does using an RCA to perform two's complement addition produce the correct result? Consider 4-bit binary numbers as an example. We arrange all the binary patterns clockwise to form a clock-face model:

              0000 (0)
      (-1) 1111  0001 (1)
   (-2) 1110   ^    0010 (2)
 (-3) 1101     |      0011 (3)
(-4) 1100      +       0100 (4)
 (-5) 1011            0101 (5)
   (-6) 1010        0110 (6)
      (-7) 1001  0111 (7)
              1000 (-8)

An RCA performs addition at the binary level. Adding a positive integer is equivalent to moving the pointer clockwise by positions, while adding a negative integer is equivalent to moving it counterclockwise by positions. For addition under a particular encoding to agree with its mathematical meaning, the numerical values represented by that encoding must also increase in the clockwise direction. The values in parentheses in the figure above illustrate the case for two's complement. As we can see, as long as the boundary between 7 and -8 is not crossed, the result of two's complement addition performed by an RCA always agrees with the mathematical result. We will discuss what happens when this boundary is crossed later.

       Sign-and-Magnitude                     One's Complement
              0000 (0)                             0000 (0)
      (-7) 1111  0001 (1)                  (-0) 1111  0001 (1)
   (-6) 1110   ^    0010 (2)            (-1) 1110   ^    0010 (2)
 (-5) 1101     |      0011 (3)        (-2) 1101     |      0011 (3)
(-4) 1100      +       0100 (4)      (-3) 1100      +       0100 (4)
 (-3) 1011            0101 (5)        (-4) 1011            0101 (5)
   (-2) 1010        0110 (6)            (-5) 1010        0110 (6)
      (-1) 1001  0111 (7)                  (-6) 1001  0111 (7)
              1000 (-0)                            1000 (-7)

Sign-and-magnitude and one's complement do not satisfy the property described above. Specifically, sign-and-magnitude representation has two problems:

1. There is a discontinuity between 0b0000 and 0b1111. Although the binary encodings on the two sides of this boundary are consecutive, the values they represent are not. As a result, the computed result does not agree with its mathematical meaning. For example, computing 0 + (-1) using sign-and-magnitude representation is equivalent to moving the pointer counterclockwise by one position from 0, producing -7, which does not agree with the mathematical result.
2. The encoding of negative numbers makes their represented values decrease in the clockwise direction, violating the requirement that values increase clockwise. As a result, the computed result does not agree with its mathematical meaning. For example, computing (-4) + 1 using sign-and-magnitude representation is equivalent to moving the pointer clockwise by one position from -4, producing -5, which does not agree with the mathematical result.

By inverting the bits, one's complement makes the values represented by negative encodings increase in the clockwise direction, thereby fixing the second problem of sign-and-magnitude representation. However, the first problem remains. For example, computing 0 + (-1) using one's complement is equivalent to moving the pointer counterclockwise by one position from 0, producing -0, which does not agree with the mathematical result.

Based on one's complement, two's complement applies an additional +1 to the encoding, rotating the values represented by the negative encodings clockwise by one position and thereby fixing the first problem as well.

Why Are They Called One's Complement and Two's Complement?

In fact, a complement is a concept in numeral systems. To subtract a number, we can instead add its complement.

In an n-digit base-b numeral system, a number has two kinds of complements. One is the radix complement, called the b's complement in this case, and is defined as . The other is the diminished radix complement, called the 's complement in this case, and is defined as . Both complements can be used with corresponding calculation methods to perform subtraction. In particular, when , these two complements are the two's complement and one's complement, respectively.

For more information, refer to the relevant Wikipedia page.

Overflow Detection

Recall the analysis above. Even in two's complement, there is still a boundary at which the encodings are consecutive but the represented values are not: the boundary between 0b0111...111 and 0b1000...000, which represent the maximum and minimum values, respectively. If an addition crosses this boundary, the computed result will not agree with its mathematical meaning. This boundary exists because, for any fixed number of binary bits, the representable range is finite. Some values must therefore lie outside that range, preventing the represented values from remaining continuous indefinitely. A computation whose result exceeds the range representable by the encoding is said to overflow. Clearly, when overflow occurs, the computed result does not agree with its mathematical meaning. Therefore, an addition operation usually needs to detect whether its result has overflowed.

From the perspective of the clock-face model, crossing the discontinuity boundary can occur in two ways:

1. Moving the pointer clockwise from the positive-number region and crossing into the negative-number region
2. Moving the pointer counterclockwise from the negative-number region and crossing into the positive-number region

From a mathematical perspective, these two cases correspond to:

1. Adding two positive numbers and obtaining a negative result
2. Adding two negative numbers and obtaining a positive result

From this perspective, we only need to consider the addition of the sign bits to determine whether overflow occurs. Since sign-bit addition is also performed by a full adder, we can examine the truth table of the full adder.

						overflow
0	0	0		0	0	NO
0	0	1		0	1	YES
...	...	...		...	...	...

Only the first two rows of the truth table are shown here. Given the two inputs and and the carry-in , the full-adder logic produces the carry-out and the sum bit . To determine whether overflow occurs from the sign bits of the two operands and the result, we only need to examine , , and . For example, the first case corresponds to adding two positive numbers and obtaining a positive result, so no overflow occurs. The second case corresponds to adding two positive numbers and obtaining a negative result, so overflow occurs.

Detect Overflow in Two's Complement Addition

Complete the truth table above and derive a Boolean expression for the overflow condition. Then add overflow detection logic to the 4-bit adder in Logisim. After completing the circuit, verify your design through simulation.

Sequential Logic Circuits

The modules introduced in the previous section share a common property: their outputs are determined entirely by their current inputs. However, the modules described above are not sufficient to implement every circuit. For example, a digital watch needs to perform the operation new seconds = previous seconds + 1, so its current output also depends on its previous value.

Therefore, we need to implement a new type of circuit with the following two properties: (1) it can read the previous state of the circuit, and (2) it can update the state of the circuit. A circuit with these properties is called a sequential logic circuit. It can store state, and its output is determined jointly by the current input and the previous state. In contrast, the circuits introduced in the previous section are called combinational logic circuits, which have no concept of previous or current state.

Cross-Coupled Inverters

To begin, let us consider how to store and read the state of a circuit. The simplest circuit capable of storing state is a pair of cross-coupled inverters. Its circuit structure is shown below:

Suppose the total propagation delay for to travel through the wire to and then through the inverter to is . The total propagation delay for to travel through the wire to and then through the inverter to is also . The behavior of the circuit can be analyzed in the following four cases:

1. Suppose initially and , that is, and . After time , becomes the inverse of , which is 1, while becomes the inverse of , which is 0. Therefore, after time , we still have and , which is the same as before time $T`, so the state of the circuit remains unchanged.
2. Suppose initially and , that is, and . A similar analysis shows that after time , we still have and , which is the same as before time , so the state of the circuit remains unchanged.
3. Suppose initially and , that is, and . After time , becomes the inverse of , which is 1, while becomes the inverse of , which is also 1. Therefore, after time , we have and $\overline{Q}=1`, so the state of the circuit changes.
4. Suppose initially and , that is, and . A similar analysis shows that after time , we have and , so the state of the circuit changes.

From the analysis above, when or , the circuit remains in a stable state. We consider the circuit capable of reliably storing 1 bit of information in these cases: when and , the circuit stores 0; when and , the circuit stores 1. The stored state can be read from the output.

When or , however, the circuit repeatedly oscillates between these two states. The output alternates between 0 and 1 and cannot represent stable information. This condition is called a metastable state. It may corrupt other information in the circuit and cause the circuit output to behave unexpectedly, so it must be avoided during circuit design.

The following table summarizes the behavior of the cross-coupled inverters:

			newQ		instruction
0	0		1	1	metastability
0	1		0	1	store 0
1	0		1	0	store 1
1	1		0	0	metastability

However, even when the cross-coupled inverters are in a stable state, we cannot update that state. Since the circuit has no external inputs, we have no way to control it, making it difficult to use in practice. To solve this problem, we need a more practical storage element.

Cross-Coupled Inverters Cannot Be Simulated in Logisim

Because cross-coupled inverters have no inputs, Logisim cannot determine their initial state and therefore cannot simulate them properly. You only need to understand how cross-coupled inverters work; you do not need to complete any related experiments.

SR Latch

An SR latch replaces the inverters in a pair of cross-coupled inverters with NOR gates, thereby providing external control inputs. Here, S stands for set, and the corresponding control input sets the latch to 1; R stands for reset, and the corresponding control input resets the latch to 0. The logic symbol and circuit structure of an SR latch are shown below.

Depending on the inputs, the behavior of an SR latch can be analyzed in four cases:

1. When S=1, R=0, the upper NOR gate behaves like an inverter, while the output of the lower NOR gate is forced to 0. In this case, , so the value stored in the SR latch is updated to 1.
2. When S=0, R=1, the output of the upper NOR gate is forced to 0, while the lower NOR gate behaves like an inverter. In this case, , so the value stored in the SR latch is updated to 0.
3. When S=0, R=0, both NOR gates behave like inverters. The SR latch therefore behaves in the same way as the cross-coupled inverters and retains its previously stored value.
4. When S=1, R=1, the outputs of both NOR gates are forced to 0, so the circuit cannot represent valid information. Furthermore, changing the inputs from S=1, R=1 to S=0, R=0 is equivalent to placing the cross-coupled inverters in the state . As discussed above, this may cause the SR latch to enter a metastable state and must therefore be avoided.

The following table summarizes the behavior of an SR latch:

S	R		Q
0	0		Keep
0	1		0
1	0		1
1	1		Invalid

Build an SR Latch

In Logisim, try to build an SR latch using logic gates. After completing the circuit, verify your design through simulation.

When operating the circuit manually, it is impossible to change two DIP switches directly from 11 to 00 with a single click. To trigger a metastable state, you can add several AND gates before the SR latch and use another DIP switch to control one input of each AND gate simultaneously. This allows both inputs of the SR latch to become 0 at the same time using a single DIP switch. If you successfully trigger a metastable state, Logisim will display the message Oscillation apparent at the bottom of the window. The simulation will then be unable to continue, and you will need to reset it through the Logisim menu.

An SR Latch Built with NAND Gates

The SR latch introduced above is built with NOR gates. In fact, the NOR gates can be replaced with NAND gates, producing a latch known as an latch. Try to derive the truth table of the latch and analyze its behavior.

D Latch

To prevent metastability at its source, we can add several logic gates before the SR latch to restrict its four input combinations to three valid combinations. This is the basic idea behind the D latch. Its logic symbol and circuit structure are shown below, where D is the data input and WE is the write enable.

Analyze the Behavior of the D Latch

Try to derive the truth table from the circuit structure and analyze the behavior of the D latch.

Build a D Latch

In Logisim, try to build a D latch using logic gates. After completing the circuit, verify your design through simulation.

Build a D Latch with Reset

Try to add a reset input and reset functionality to the D latch. When the reset signal is asserted, the value stored in the D latch should become 0.

Implement Bit Toggling with a D Latch

Instantiate a D latch with reset functionality, invert its output, and feed the inverted signal back into its input. We might expect the output of the D latch to alternate between 0 and 1, but the simulation should display the message Oscillation apparent. Analyze why this happens.

Synchronous Circuits

A complex system contains multiple modules, so coordinating their operation is an important issue to consider. For example, suppose a system contains three modules: a data-reading module, an addition module, and a result-writing module. We expect the following events to occur in sequence:

1. The data-reading module operates first.
2. After the data has been read, the addition module begins its computation.
3. After the addition module finishes computing the result, the result is written to the target storage element.

Therefore, we need to establish a synchronization relationship in which event A occurs after event B. This requires an additional mechanism, and there are generally two approaches:

• Synchronous circuit: Synchronization is achieved using a global periodic clock signal. A clock signal is a pulse signal, as shown below, that alternates between high and low levels. One high-level interval together with one low-level interval is called a clock cycle. In a synchronous circuit, a storage element writes data only when the clock signal reaches a positive edge (rising edge, a transition from low to high) or a negative edge (falling edge, a transition from high to low), and the stored data can be read reliably during subsequent clock cycles. With this property, events that need to be synchronized can be assigned to different clock cycles, allowing the clock signal to control their order of execution.

Example clock signal

             +--- positive edge              +--- negative edge
             V                               V
     +----+   +----+   +----+   +----+   +----+   +----+   +----+   +----+
     |    |   |    |   |    |   |    |   |    |   |    |   |    |   |    |
+----+    +---+    +---+    +---+    +---+    +---+    +---+    +---+    +

• Asynchronous circuit: Synchronization is achieved through local communication signals between modules.

Compared with asynchronous circuits, synchronous circuits are easier to design and analyze. Although introducing a periodically toggling clock signal results in higher power consumption than in asynchronous circuits, synchronous circuits are still widely used in industry. Our subsequent study will also be based on synchronous circuits.

However, a D latch cannot satisfy the requirements of a synchronous circuit as a storage element. Even if the clock signal is connected to the write-enable input of the D latch, the requirements above are still not met. As shown in the figure below, we expect data to be written to the storage element when the rising edge of the clock arrives and to be read reliably from the storage element during subsequent clock cycles. The red-circled region in the figure, however, violates this property.

This is because a latch is a level-triggered storage element. As long as its input changes while it is enabled, the latch detects the change immediately and propagates it to the output. In contrast, we need an edge-triggered storage element that propagates its input to the output only when a signal edge arrives.

D Flip-Flop

A D flip-flop is an edge-triggered storage element. It is constructed from latches, but it can prevent input changes from propagating while the clock signal remains at a constant level. The logic symbol of a D flip-flop is shown below. The > symbol at the lower-left corner indicates that this port should be connected to the clock signal. D flip-flops can be implemented in several ways. Here, we first introduce the master–slave D flip-flop, whose structure is shown below.

A master–slave D flip-flop consists of two D latches. The latch on the left is called the master latch, while the one on the right is called the slave latch. The write-enable inputs of the two D latches are connected to the clock signal and its inverse, respectively. The operation of a master–slave D flip-flop can be divided into the following phases:

1. Data preparation phase: At this time, the clock signal clk is at a low level, so the write-enable input of the master latch is asserted, allowing the data signal D to enter the master latch from outside. However, because the write-enable input of the slave latch is deasserted, the data signal cannot propagate to the slave latch, so the output Q of the entire D flip-flop remains unchanged.
2. Sampling phase: When the rising edge of clk arrives, the write-enable input of the master latch is deasserted, so the data signal D can no longer enter the master latch from outside. Subsequent changes in D can no longer affect the master latch, thereby “locking” the external value of D present at the rising edge inside the master latch. At the same time, the write-enable input of the slave latch becomes asserted, allowing the data “locked” in the master latch to propagate to the slave latch and become the output of the entire D flip-flop.
3. Holding phase: At this time, the clock signal clk is at a high level, so the write-enable input of the master latch is deasserted and is therefore unaffected by changes in the data signal D. Although the write-enable input of the slave latch is asserted, the master latch remains unchanged, so the slave latch also remains unchanged and the output Q of the entire D flip-flop stays stable.

Overall, when the rising edge of the clock arrives, the data is written into the D flip-flop and can then be read reliably during subsequent clock cycles, satisfying the requirements for storage elements in synchronous circuits. Therefore, the D flip-flop is a fundamental storage element in synchronous circuit design.

Build a D Flip-Flop

Try to build a D flip-flop using logic gates in Logisim. After completing the circuit, connect its clock port to a button. Pressing and releasing the button produce high and low levels, respectively, so clicking the button once generates a pulse that can serve as the clock signal. Try pressing and holding the button to observe how the master–slave D flip-flop operates.

Build a D Flip-Flop with Reset

Try to add a reset input and reset functionality to the D flip-flop. When the reset signal is asserted, the value stored in the D flip-flop should become 0.

Implement Bit Toggling with a D Flip-Flop

Instantiate a D flip-flop with reset functionality, invert its output, and feed the inverted signal back into its input. We expect the output of the D flip-flop to alternate between 0 and 1. Compare the result with that of the D latch described above.

Build a Falling-Edge-Triggered D Flip-Flop

The master–slave D flip-flop described above is rising-edge-triggered. Try to build a falling-edge-triggered D flip-flop. After completing the circuit, verify your design through simulation.

Another Implementation of the D Flip-Flop

The figure below shows another implementation of a D flip-flop, known as a hold-block D flip-flop. Compared with a master–slave D flip-flop, it imposes fewer restrictions on its input. Interested students may consult relevant materials to understand and analyze the behavior of the hold-block D flip-flop.

Sometimes, we do not want a D flip-flop to update unconditionally. Therefore, we need to add an enable input to the D flip-flop, forming a D flip-flop with enable. Its logic symbol is shown below.

Build a D flip-flop with an enabling pin

Try to build a D flip-flop with an enable pin in Logisim using D flip-flops and several circuits. After building it, checking if your solution is correct through simulation.

Register

The D flip-flop described above can store only 1 bit of data, but sometimes we need to store and process multiple bits as a single unit. A register is a storage element composed of multiple D flip-flops. Its circuit structure is shown below. These D flip-flops share the same clock and enable signals, allowing multiple bits to be stored as a single unit.

Build a 4-Bit Register

In Logisim, try to build a 4-bit register using D flip-flops and add reset functionality. After completing the circuit, try writing 4-bit data from a DIP switch into the register and connect the register's output to a 7-segment display.

Build a 4-Bit Counter

Use the 4-bit register described above and the adder built earlier to implement a 4-bit counter. On each clock edge, increment the value in the register by 1. After reaching the maximum value, the counter should wrap around to 0. In Logisim, you can instantiate a constant using the Constant component under the Wiring category in the component library. RTFM for detailed usage instructions.

Design a Sequence Summation Circuit

Try to use registers and adders to compute the result of 1+2+...+10. You may consider implementing 8-bit registers and adders to accommodate the result.

Implement a Digital Clock

Use registers and 7-segment displays to implement a digital clock that displays minutes and seconds.

Hint: The Clock component can automatically generate a clock signal without requiring manual clicks as with a button. You can find it under the Wiring category in the Logisim component library. RTFM for detailed usage instructions.