Skip to section
Foundationsfor rotation-free search
Section 40 of 5277% of course
Contents
Chapter 7 Section 7.2 70 min

Part V · Hardware foundations

Signals, bits, and widths

Read a hardware value as wires with an explicit finite width.

In hardware, values take up physical space

When you're writing Python, an integer just grows in memory if it gets too big. Hardware doesn't have that luxury. A hardware signal is a literal bundle of wires. A one-bit signal is one wire (0 or 1). An unsigned W-bit signal is a bundle of W wires, representing values from 0 all the way up to 2ᵂ−1.

bit 7
1bit 6
0bit 5
1bit 4
1bit 3
0bit 2
0bit 1
1bit 0
0

If we look at the pattern 10110010 and treat it as an unsigned integer, it's 178. But keep in mind, those exact same wires could represent a completely different number if we were treating them as signed or fixed-point values. The wires themselves are just voltages; they rely on us to enforce a "type contract" so they mean something useful.

Worked example

Reading 178 from the wires

Let's break it down. We have a 1 at bit positions 7, 5, 4, and 1. Their place values are 2⁷, 2⁵, 2⁴, and 2¹. If you add 128 + 32 + 16 + 2, you get 178. Just like we used indices to keep track of polynomial coefficients earlier, we use indices to keep track of bit significance here.

Multiplying means making wider pipes

The biggest number you can fit in W bits is close to 2ᵂ. If you multiply two of those numbers together, the result can approach 2²ᵂ. That means if you don't want to lose data, your output signal needs twice as many wires as your inputs.

W-bit × W-bit → 2W-bit full product

Worked example

The 8-bit overflow trap

Take two 8-bit numbers: 255 × 255 = 65,025. An 8-bit wire bundle maxes out at 255, but a 16-bit bundle goes up to 65,535. If you try to shove that product back into 8 bits, you'll silently chop off the most important parts of your number—unless, of course, you're doing it on purpose to apply a reduction.

Wait, if the product is 56 bits, why does our modular reduction output go back to 28 bits?

Because we're taking a remainder! The full product has to expand to 56 bits so we don't lose any information during the math. But once we calculate the remainder modulo our 28-bit prime, the resulting value is guaranteed to be between 0 and q−1. That fits perfectly back into 28 bits. The wide 56-bit signal and the narrow 28-bit signal are fulfilling two different mathematical contracts.

Check your understanding

How many bits do you need to hold the full unsigned product of two 28-bit values?

Section summary

  • Signals are literal wires; they have an explicit, fixed width.
  • A bit pattern is just ones and zeros until you define what it represents.
  • A full multiplication requires double the bits (if the operands are the same width) to avoid truncation.

Repository layer · second pass

Why is bit width part of a value’s type?

A hardware signal has a fixed number of wires and a signedness interpretation. Values outside the representable range wrap or truncate unless logic explicitly extends them. A full unsigned W-by-W multiplication needs 2W result bits; addition may need one extra bit.

Width errors often pass small tests. Use maximum operands, negative signed values, and intermediate bounds. Document whether reductions occur before or after truncation and make casts visible in RTL.

Reasoning chain

  1. 1

    Declare numeric range.

  2. 2

    Choose signed or unsigned interpretation.

  3. 3

    Derive each intermediate width.

  4. 4

    Extend operands before arithmetic.

  5. 5

    Reduce or saturate deliberately.

  6. 6

    Assert high bits when truncation is expected safe.

Worked trace

The missing upper half

  1. Two 8-bit unsigned inputs can each be 255.
  2. Their product is 65025.
  3. Eight bits retain only 1.
  4. Sixteen bits retain the full product.

Result. The multiplier output width must be derived, not copied from its inputs.

Executable lens · Python

Make the hidden state visible

def mask(value, width): return value & ((1<<width)-1)
full = 255*255
assert full == 65025
assert mask(full,8) == 1
assert mask(full,16) == full

Retype this example, predict each intermediate value, and then change one input that touches a boundary.

Misconception clinic

Tempting mistakes

  • Treating a bit vector as an unbounded Python integer.
  • Mixing signed and unsigned operands implicitly.

Retrieval and transfer

Close the book first

  1. Derive width of three accumulated 28×28 products.
  2. Decode 8-bit 0xF6 as signed and unsigned.
  3. Write boundary vectors for a modular multiplier.