Comparators priority encoders and code circuits

Start with the information contract

A bit vector can be a number, a set of requests or an error-detection code. The same gates serve different purposes depending on that interpretation. For each circuit, define the input ordering, output meaning and behavior on every permitted input before simplifying equations.

Prerequisites: Boolean gates, XOR/XNOR, minterms and combinational implementation. All signals are ideal active-high bits unless explicitly stated, and outputs are observed after settling. This lesson designs an unsigned comparator, a priority encoder, binary/Gray converters and an even-parity circuit. It does not specify electrical pinouts, asynchronous synchronization or error-correcting codes.

Unsigned comparison from the most significant difference

For one bit, X>Y when XY′=1; X<Y when X′Y=1; equality is X XNOR Y. For multi-bit unsigned words, the highest differing position determines the comparison because its weight exceeds the sum of all lower weights. Equality requires every corresponding pair to match, not merely equal parity.

For two-bit X=x_1x_0 and Y=y_1y_0, let e_1=x_1 XNOR y_1 and e_0=x_0 XNOR y_0. Then

EQ=e_1e_0; GT=x_1y_1′+e_1x_0y_0′; LT=x_1′y_1+e_1x_0′y_0.

The low-bit comparison matters only if the high bits match. Worked example 1: X=10,Y=01. The high pair is 1 versus 0, so GT=1 despite low bits 0 versus 1. At X=10,Y=11 the high pair matches; the low pair makes LT=1. Exactly one of EQ,GT,LT is 1 for every input pair.

For longer words, repeat the same structure: a lower-position greater term is enabled only if every more-significant pair matches. Do not apply this unsigned equation blindly to two's-complement ordering. For example 1000 is greater than 0111 as unsigned 8>7, but less as signed −8<7. When signed operands have different signs, the sign interpretation must be handled separately.

Ordinary encoder versus priority encoder

An ordinary one-hot encoder expects exactly one asserted input, or a separately defined zero-input case. For inputs d_3…d_0, a one-hot 4-to-2 encoder reports the index of the asserted input. Simple equations y_1=d_3+d_2, y_0=d_3+d_1 work for that restricted contract. With d_2=d_1=1 they give 11, falsely naming index 3: multiple requests violate the one-hot assumption.

A priority encoder explicitly accepts simultaneous requests. Define d_3 highest priority, then d_2,d_1,d_0. Let v report whether any request exists; if none exists, require output code 00 and v=0.

d_3 d_2 d_1 d_0	v	y_1 y_0
1 X X X	1	11
0 1 X X	1	10
0 0 1 X	1	01
0 0 0 1	1	00
0 0 0 0	0	00

X here means the lower-priority input is irrelevant for that row's output; each such row stands for several concrete Boolean assignments. From the table,

v=d_3+d_2+d_1+d_0; y_1=d_3+d_2; y_0=d_3+d_2′d_1.

Worked example 2: d_3d_2d_1d_0=0111 selects d_2 and gives code 10,v=1. The term d_2′d_1 suppresses the lower request while d_2 is asserted. Code 00 alone is ambiguous between no request and d_0 winning, so v is necessary under this contract.

Commercial encoders can use active-low inputs, outputs or enable controls. The TI SN74HC148 is a different eight-input component with its own polarity and cascade conventions; do not copy this educational table to its pins without checking its data sheet.

Binary to reflected Gray code

Reflected binary Gray code arranges consecutive count values so adjacent codewords differ in exactly one bit. It is not an unsigned positional numeral to add directly. For binary b_3b_2b_1b_0, define

g_3=b_3; g_2=b_3⊕b_2; g_1=b_2⊕b_1; g_0=b_1⊕b_0.

Worked example 3: binary 1011 gives g_3=1,g_2=1,g_1=1,g_0=0, so Gray code 1110. Reverse conversion uses cumulative XOR: b_3=g_3, b_2=b_3⊕g_2, b_1=b_2⊕g_1, b_0=b_1⊕g_0. Applying it to 1110 recovers 1011.

For a two-bit count the binary sequence 00,01,10,11 maps to Gray 00,01,11,10. This explains the ordering used on Karnaugh-map axes. The one-bit adjacency property concerns consecutive encoded counts, not arbitrary pairs of Gray words. It does not alone guarantee safe clock-domain crossing or the absence of physical transition problems.

Even parity generation and checking

An even-parity bit p is chosen so the data bits plus p contain an even number of ones. For data x_0…x_(n−1), choose p=x_0⊕…⊕x_(n−1). Then XOR of the complete codeword is zero because p⊕p=0.

Worked example 4: data 1011 has three ones, so p=1; appending it gives 10111 with four ones. A receiver XORs all received data and parity bits. Result 1 indicates odd parity, inconsistent with the expected even-parity contract. Result 0 means parity is consistent, not that every bit is necessarily correct.

Flipping a bit toggles total XOR. Therefore any odd number of bit flips is detected; an even number can leave parity unchanged. In a single parity-check code, every even number of flips in distinct bit positions leaves parity unchanged. The parity result does not locate the erroneous bit, so it does not by itself correct even a single-bit error.

A word-comparison circuit cannot be replaced by one parity comparison: 00 and 11 have the same parity but are different words. Likewise a priority code is not a parity code merely because both use a few output bits.

A complete small-circuit check

Enumerate all 16 input pairs for the two-bit comparator, all 16 request vectors for the priority encoder and all 16 binary inputs for the four-bit code converter. Check binary→Gray→binary round trips and consecutive-word Hamming distance. For parity, test no error, one flipped data bit, one flipped parity bit and two distinct flips. These finite exhaustive checks are practical and reveal input-contract mistakes that a handful of typical examples can miss.

Original practice

These six single-correct MCQs are original learning questions, not previous-year questions. Choose exactly one option.

C01. For unsigned two-bit X=10 and Y=01, which comparison is true?

A. X<Y B. X=Y C. X>Y D. Cannot compare because both words contain one 1

Answer: C

A is incorrect: the high bit has greater weight than the low bit.

B is incorrect: the corresponding bits differ.

C is correct: unsigned 2 is greater than 1.

D is incorrect: equal parity does not prevent numerical comparison.

C02. An active-high priority encoder uses d_3 highest, then d_2,d_1,d_0. For requests 0111, what are (v,code)?

A. 1,10 B. 1,11 C. 1,01 D. 0,00

Answer: A

A is correct: d_2 is the highest asserted request, and a request exists.

B is incorrect: d_3 is not asserted.

C is incorrect: d_1 loses to d_2.

D is incorrect: three requests exist, so v cannot be zero.

C03. Why is a valid bit needed when priority code 00 is returned for both no requests and d_0 alone?

A. To double the numeric index B. To turn OR into XOR C. To make every output one-hot D. To distinguish those two input situations

Answer: D

A is incorrect: validity does not scale the index.

B is incorrect: validity is a separate information signal.

C is incorrect: the output remains binary encoded.

D is correct: code alone carries no distinction between absent input and index zero.

C04. What is the four-bit reflected Gray code of binary 1101?

A. 1101 B. 1011 C. 1001 D. 0111

Answer: B

A is incorrect: it copies binary without the conversion.

B is correct: keep the high 1, then compute 1⊕1=0,1⊕0=1,0⊕1=1.

C is incorrect: the third output bit should be 1.

D is incorrect: the high Gray bit equals the high binary bit, which is 1.

C05. Which parity bit must be appended to data 1011 to obtain even parity?

A. 0 B. Either value C. 1 D. No parity bit can work

Answer: C

A is incorrect: three ones would remain odd.

B is incorrect: only one of the two choices makes the total even.

C is correct: three data ones plus parity 1 give four ones.

D is incorrect: adding 1 supplies a valid even-parity codeword.

C06. A single even-parity check receives a codeword with exactly two distinct bits flipped. What does the parity check report?

A. Parity remains even, so this error is not detected. B. Odd parity, always detecting the error. C. The exact locations of both flips. D. Automatic correction of both flips.

Answer: A

A is correct: two XOR toggles cancel, preserving parity.

B is incorrect: an even number of flips preserves the original parity.

C is incorrect: one parity bit does not locate errors.

D is incorrect: a parity check alone does not provide correction.

Scope and sources

This is one bounded Digital Logic lesson, not complete GATE CS coverage. The official syllabus establishes relevance only; the derivations, examples and practice are original. Technical references were used to check representation and circuit conventions, not to reproduce their exercises.

• Official GATE 2027 CS syllabus Section 2
• NPTEL Digital Systems combinational functions and codes
• TI SN74HC148 official priority encoder data sheet

Sources checked 14 October 2026.