Unit 5 - Practice Quiz

A Half Adder is a circuit designed to add two single binary digits. It produces a sum and a carry output.

A half adder adds two bits (A and B) and generates a Sum bit (S) and a Carry bit (C).

A Full Adder adds three bits: two input bits (A, B) and a carry-in bit () from a previous stage.

A half subtractor calculates the difference between two single bits (A and B) and produces a Difference output (D) and a Borrow output ().

A full subtractor performs subtraction between two input bits (A, B) and also considers a borrow-in bit () from a lower significant stage.

A magnitude comparator is a combinational circuit that compares two binary numbers (A and B) to determine if A > B, A = B, or A < B.

A 1-bit comparator typically has three outputs to indicate the relationship between the two input bits: A is greater than B (A > B), A is equal to B (A = B), and A is less than B (A < B).

A multiplexer is called a Data Selector because it selects one of its many input lines and directs it to a single output line based on the value of the select lines.

The relationship between the number of select lines (n) and the number of input lines (m) in a multiplexer is . For n=3, the number of inputs is .

A de-multiplexer performs the reverse operation of a multiplexer. It takes a single input line and distributes it to one of several output lines, as determined by the select lines. It is also called a data distributor.

For a de-multiplexer, the number of output lines (m) is related to the number of select lines (n) by . For m=4, we need , which means n=2 select lines are required.

A decoder takes 'n' binary inputs and activates one of its outputs corresponding to the binary code on the input lines.

A BCD-to-7-segment decoder takes a 4-bit Binary-Coded Decimal (BCD) input and generates the appropriate outputs to light up segments on a 7-segment display to show a decimal digit (0-9).

The name "3-to-8 decoder" directly specifies its structure: 3 input lines and 8 output lines. This follows the -to- rule where n=3.

An encoder is a combinational circuit that performs the inverse operation of a decoder. It typically has input lines and 'n' output lines.

An octal-to-binary encoder converts one of 8 active input lines into a 3-bit binary code. It has 8 inputs and 3 outputs.

A simple encoder functions correctly only when one input is active. A priority encoder includes a priority function, so if two or more inputs are active, the output corresponds to the input with the highest designated priority.

Parity circuits are used for detecting single-bit errors in data transmission. A parity bit is added to a block of data to make the total number of 1s either even (even parity) or odd (odd parity).

In an even parity system, the parity bit is set to make the total number of 1s even. The data 1010 already has two 1s (an even number), so the parity bit is 0. The transmitted data would be 10100.

An XOR (Exclusive OR) gate's output is 1 if an odd number of its inputs are 1. This property makes it ideal for generating both even and odd parity bits. For odd parity, the output of cascaded XOR gates is the parity bit.

The sum is calculated as . So, . The carry-out is calculated as . So, . Essentially, in decimal, which is in binary, giving a sum of 1 and a carry of 1.

The propagate signal is 1 when exactly one of the inputs or is 1. In this case, if there is a carry-in (), it will be propagated to the next stage as a carry-out (), because or results in a carry-out only if is 1.

An N-bit parallel adder adds two N-bit numbers. The least significant bit (LSB) position requires only a half adder as there is no carry-in. The remaining N-1 positions each require a full adder to accommodate the carry-in from the previous stage. For a 5-bit adder, this means 1 HA for the LSB and 4 FAs for the remaining bits.

Subtraction using 2's complement is performed as . The 2's complement of B is found by inverting all its bits (1's complement) and adding 1. The inverters find the 1's complement of B, and adding 1 is achieved by setting the initial carry-in () of the parallel adder to 1.

The equations for a full subtractor are and . For A=0, B=1, =1: . And . The operation is effectively , which results in a difference of 0 with a borrow of 1 from the next higher bit.

For A = = 10 and B = = 11. The comparison starts from the most significant bit (MSB). Here, and , so they are equal. We then check the next bit, and . Since , the overall result is A < B. Therefore, the output is HIGH (1), and the other two outputs (, ) are LOW (0).

When cascading comparators, the result of comparing the lower-order bits is used to decide the final outcome only if the higher-order bits are equal. Therefore, the outputs of the less significant comparator are connected to the cascading inputs of the more significant comparator.

The output should be HIGH (1) only when A is 1 and B is 0. This condition is described by the Boolean AND operation between A and the complement of B, which is (or ).

For an 8x1 MUX with A, B, C as select lines ( where A is MSB), the input corresponding to the selected binary number appears at the output. To implement the function , we need the output to be HIGH for minterms 1 (001), 3 (011), 5 (101), and 6 (110). Thus, we connect the corresponding data inputs () to logic HIGH (1) and all other data inputs to LOW (0).

A 4x1 MUX has 4 data inputs and 2 select lines (). You can use two 2x1 MUXes for the first stage, with as their common select line. One MUX takes inputs and the other takes . The outputs of these two MUXes then become the inputs to a third 2x1 MUX, which uses the other select line, , to make the final selection. Total MUXes = 2 + 1 = 3.

A demultiplexer routes a single data input to one of several output lines based on the value of the select lines. The binary value of the select lines corresponds to the decimal number 6. Therefore, the data input will be routed to the output line . Since the data input is HIGH, will be HIGH and all other outputs will be LOW.

A multiplexer (MUX) has multiple data input lines and a single output line. By sequentially changing the select line inputs, it can select each parallel data input one by one and pass it to the single output line. This process effectively converts parallel data into a serial stream of data.

The Carry-out of a full adder is HIGH for the input combinations (A, B, ) of 011, 101, 110, and 111. These correspond to minterms . A 3-to-8 decoder with inputs A, B, will activate the output lines corresponding to these minterms. Therefore, connecting decoder outputs to an OR gate will implement the Carry-out function.

The input to this type of decoder is a 4-bit Binary Coded Decimal (BCD) number, which represents decimal digits 0-9. The output drives a 7-segment display, which requires 7 distinct signals (one for each segment: a, b, c, d, e, f, g). Therefore, the decoder has 4 input lines and 7 output lines.

A decoder takes an N-bit binary input and activates exactly one of its outputs. This is ideal for memory address decoding, where the address from the CPU is used as the decoder's input to select a specific memory chip or location by activating a single chip-select line.

A priority encoder outputs the binary code corresponding to the highest-priority input that is currently active. In this scenario, both and are active. Since has a higher priority than , the encoder will ignore the input and produce the output corresponding to , which is binary 10 (decimal 2).

In a standard encoder, if more than one input is active at the same time, the output can be incorrect or ambiguous because the circuit is typically designed assuming only one input is active. A priority encoder resolves this by establishing a priority hierarchy, ensuring a valid output that corresponds to the highest-priority active input.

In an even parity system, the parity bit is set to make the total number of '1's in the transmitted word (data + parity bit) an even number. The data word 1011001 has four '1's, which is already an even number. To keep the total count of '1's even, the parity bit must be set to 0.

An even parity checker verifies if the total number of '1's in the received message is even. The message 10101 contains three '1's, which is an odd number. Since the count of '1's is not even as expected, the checker circuit will signal that an error has been detected.

A parity bit generator determines if the number of 1s in a data word is odd or even. This is the exact function of cascading XOR gates. The output of a multi-input XOR gate is 1 if an odd number of inputs are 1, and 0 if an even number of inputs are 1. This output can be used directly as an odd parity bit or inverted for an even parity bit.

The total delay is the sum of delays along the critical path for .

1. Generate for all 16 bits: .
2. Generate group propagate/generate signals for each of the four 4-bit blocks (2 gate levels): . Total elapsed: .
3. The lookahead carry generator computes carries into each block, e.g., (2 gate levels): . Total elapsed: .
4. The final 4-bit block computes the internal carry using (2 gate levels): . Total elapsed: .
5. The final sum bit is computed using a 3-input XOR, which takes .
6. Total delay = (Delay to get ) + (Delay for final sum) = .

For n-bit 2's complement addition (which is used to perform subtraction), an arithmetic overflow occurs if and only if the carry-in to the most significant bit column () is different from the carry-out from the most significant bit column (). For an 8-bit operation (bits 0 to 7), this condition is , or .

An implementation table is created with MUX inputs () corresponding to select line values ABC=000..111. For each input , we check the pair of minterms determined by and . For , we check m(0) and m(1). Since only m(1) is in the function, must be . For , we check m(4) and m(5). Since only m(4) is in the function, must be . Following this method for all inputs yields the sequence .

To create a larger decoder, the higher-order input bits are used to select which smaller decoder is active, while the lower-order bits are fed in parallel to all smaller decoders. Here, the low-order bits are connected to the address inputs of all four 3-to-8 decoders. The high-order bits are used as inputs to the 2-to-4 decoder. Each of the four outputs of the 2-to-4 decoder is then used to assert the enable pin of one of the 3-to-8 decoders, activating the correct block of 8 outputs.

The overall 'A < B' condition is true if at the current bit position , we have and (which is ), OR if the current bits are equal, (which is ), AND the less significant bits have already established that A < B (i.e., ). Therefore, the expression is . Comparing this to the given form , we find that and (the equality condition).

A priority encoder outputs the binary code corresponding to the highest-priority input that is currently active. Among the asserted inputs and , the input with the highest priority is . The binary code for the index 6 is . Therefore, the output will be . The active lower-priority inputs ( and ) are ignored.

The Exclusive-OR (XOR) gate's output is 1 if an odd number of its inputs are 1. By cascading XOR gates, we can determine if the total number of 1s in a binary word is odd or even. For an even parity generator, the output of the XOR chain is the required parity bit. For a parity checker, the XOR of the data bits and the parity bit will be 0 if the parity is correct.

The sum bit of a full adder is . With A and B as select lines for a 4:1 MUX, the output is determined by the data inputs for each combination of A and B.

• When AB=00 ( selected), . So, .
• When AB=01 ( selected), . So, .
• When AB=10 ( selected), . So, .
• When AB=11 ( selected), . So, .
  The required inputs are therefore .

A standard 1-to-4 DEMUX with select lines S1, S0 has outputs corresponding to the four minterms: . The required outputs () are not minterms of A and B. For example, if A=1 and B=1, both and would need to be active, but a demultiplexer can only activate one output line at a time. The outputs are not mutually exclusive based on A and B, so a single DEMUX is insufficient.

A simple ripple-cascade of six 4-bit comparators would work but would be slow. For a faster two-level lookahead architecture, the first level consists of six 4-bit comparators, each handling a 4-bit chunk of the 24-bit inputs. The second level requires logic to combine the six sets of outputs () based on priority. A single additional comparator IC can be configured to act as this priority logic for the outputs of the first level, making a total of 7 ICs (6 in level 1, 1 in level 2).

The truth table for a full subtractor yields the sum-of-products expressions for the outputs in terms of minterms of inputs A, B, and Bin. The Difference is and the Borrow-out is . A 3-to-8 decoder generates all 8 minterms. To create the final functions, the corresponding active-high decoder outputs must be combined using OR gates. Thus, a 4-input OR gate is needed for D, and another 4-input OR gate is needed for Bout.

An overflow in subtraction occurs when the result exceeds the representable range [-128, 127]. We evaluate as .

• In option A, . This is outside the valid range. Computationally, this is the addition of two positive numbers ( and ) which yields a negative result (), a clear sign of overflow.
• The other options result in values within the range: B) -120, C) +50, D) -128. All are valid 8-bit 2's complement numbers.

To create a 32:1 MUX, we need 32 data inputs and 5 select lines ( to ). The first stage can use four 8:1 MUXs to handle all 32 inputs (8 inputs each). The three lower-order select lines () are connected in parallel to these four MUXs. This stage produces four outputs. The second stage uses the 4:1 MUX to select one of these four outputs, using the two higher-order select lines () as its select inputs.

For cascading, the higher-priority encoder (U2) is checked first. If any of U2's inputs (I8-I15) are active, its GS output goes high. This GS signal serves two purposes: 1) It becomes the Most Significant Bit (MSB) of the final 4-bit output, indicating the active input is in the upper range. 2) It is used to disable the lower-priority encoder U1 by connecting to its active-low Enable In (EI). If no inputs are active in U2, its GS is low, which enables U1 to process inputs I0-I7.

A tree structure is the most efficient way to compute the XOR of many inputs. For N inputs, the number of levels in a binary tree of 2-input gates is . For N=16, this is levels of logic.

• Level 1: 8 gates, Delay = 5 ns.
• Level 2: 4 gates, Total Delay = 10 ns.
• Level 3: 2 gates, Total Delay = 15 ns.
• Level 4: 1 gate, Total Delay = 20 ns.
  The total delay is the number of levels multiplied by the delay per gate: .

By analyzing the truth table for a full adder with inputs A, B, Cin, we can write the sum-of-products expressions for the outputs. The Sum bit S is 1 for minterms 1 (001), 2 (010), 4 (100), and 7 (111). The Carry-out bit Cout is 1 for minterms 3 (011), 5 (101), 6 (110), and 7 (111). A decoder generates these minterms at its outputs, which are then ORed together to form the final functions.

The condition for A > B can be expressed logically. It is true if the most significant bit of A is greater than B's (, which means , or ), OR if the most significant bits are equal (, which is ) AND the next bit of A is greater than B's (, which means ). Combining these conditions gives the expression .

The output of a 2:1 MUX is . We want to implement . By connecting A to the select line S, the MUX equation becomes . To make this equal to the XNOR function, we match the terms. The term requires . The term requires . Therefore, the inputs must be and .

The required function is . The decoder provides active-low outputs, so for input '2', output is LOW, while others are HIGH. We want if the input is 2 OR 3 OR 5 OR 7. This means we want if is LOW, OR is LOW, etc. The expression is . By De Morgan's theorem, this is equivalent to . This function is directly implemented by a 4-input NAND gate whose inputs are connected to the decoder's prime number outputs.

A full subtractor's logic is and .

• Implementing the three-input XOR for D requires two levels of 2-input XORs. Each 2-input XOR can be made with one 2:1 MUX. Total for D: 2 MUXs.
• For Bout, we can express it as . This can be implemented with a 2:1 MUX with select line A, and inputs and .
• Implementing the OR gate () requires one MUX. Implementing the AND gate () requires another MUX.
• Total for Bout: 1 (final stage) + 1 (OR) + 1 (AND) = 3 MUXs.
• Grand total for the full subtractor = 2 MUXs (for D) + 3 MUXs (for Bout) = 5 MUXs.