Adders, shifters, ALUs, parity and CRC
- Trace half and full adders
- Distinguish common carry structures
- Analyze subtraction and width
- Explain shifters, an ALU, parity, and CRC
- Identify loops, incomplete behavior, and delay trade-offs
opcode
Explanation
Half and full adders
A half adder adds two single bits:
sum = A XOR B
carry = A AND B
A full adder also accepts carry_in:
sum = A XOR B XOR carry_in
carry_out = (A AND B) OR (carry_in AND (A XOR B))
Connecting full adders creates a multi-bit adder. An N-bit plus N-bit unsigned sum may need N+1 bits. Signed addition may also overflow even when the physical carry-out is zero.
Carry architectures
In a ripple-carry adder, each bit waits for the preceding carry. It is compact and easy to understand, but delay grows with width.
A carry-lookahead adder forms generate and propagate signals to calculate carries in parallel groups. It reduces delay with more logic and wiring.
A carry-select adder computes possible results for both carry-in values, then selects the correct result when the earlier carry arrives. It trades duplicate hardware for speed.
Architecture choice depends on timing, area, power, available cells, and synthesis results. “Faster” is meaningful only under stated constraints and technology.
Subtraction
Two's-complement subtraction reuses addition:
A - B = A + (!B) + 1
Unsigned subtraction needs a defined underflow or borrow policy. Signed subtraction needs signed overflow detection. Comparing only the final bit pattern can miss both conditions.
Shifters
| Operation | Vacated positions | Typical use |
|---|---|---|
| Logical left | zeros on right | unsigned multiply by powers of two, bit placement |
| Logical right | zeros on left | unsigned divide by powers of two |
| Arithmetic right | copies sign bit | signed scaling toward negative infinity in typical hardware |
| Rotate | wraps shifted bits | permutations, checksums, cryptographic datapaths |
A barrel shifter selects among shifts by powers of two and completes a variable shift combinationally. A serial shifter uses fewer resources but takes multiple cycles.
Left shifting can discard significant bits. Arithmetic right shift is not the same as signed division rounded toward zero for negative odd values, so numerical requirements must define rounding.
ALU structure
An arithmetic logic unit computes operations such as add, subtract, AND, OR, XOR, compare, and shift. The opcode selects the result through a mux. Common flags include:
- zero: result equals zero;
- negative: signed result has its sign bit set;
- carry or borrow: unsigned arithmetic condition;
- signed overflow: signed result is outside range.
Each flag needs an operation-specific definition. A carry flag from subtraction varies across architectures, so do not assume its polarity.
Parity
XOR reduction creates parity. For even parity, choose a parity bit that makes the total number of ones even. At the receiver, XOR all protected data and parity bits. A nonzero result indicates an odd number of bit errors.
Parity detects, but does not correct, errors. Two flipped bits can escape detection.
CRC concept
A cyclic redundancy check treats a bit sequence as polynomial coefficients over modulo-2 arithmetic. Addition and subtraction are both XOR, so there is no carry. The transmitter divides the augmented message polynomial by a generator polynomial and appends the remainder. The receiver performs the agreed calculation and checks the syndrome.
A CRC's strength depends on its generator, message length, initialization, reflection, bit order, and final XOR. Saying only “CRC-16” is incomplete because several incompatible parameter sets exist.
A linear feedback shift register can update the CRC one or several input bits per clock. Verification should compare the hardware result with trusted test vectors and include reset, empty message, all-zero, all-one, and single-bit-error cases.
Combinational correctness
Avoid these defects:
- an output left unassigned on a branch;
- a combinational feedback path;
- a result bus too narrow for the required range;
- signed operands silently treated as unsigned;
- a variable shift beyond the operand width with undefined policy;
- a CRC with undocumented parameters or bit order.
Worked example
Design a 4-bit ALU operation A + B with result, carry, zero, negative, and overflow flags. Use A=4'b0111 and B=4'b0011.
unsigned values: 7 + 3 = 10
5-bit addition: 0_0111 + 0_0011 = 0_1010
result: 1010
carry: 0
zero: 0
negative: 1, because result[3]=1
signed overflow: 1, because two positive operands produced a negative 4-bit result
The same result is correct for unsigned arithmetic and overflowed for signed arithmetic. Flags preserve information that the four result bits alone cannot express.
For A=4'b1111 and B=4'b0001, the 5-bit sum is 1_0000: result is zero, carry is one, and signed overflow is zero because -1 + 1 = 0.
Check yourself
Why is carry-out not the same as signed overflow? What CRC parameters must two communicating blocks agree on?