Skip to main content
2 of 3
Fixed last expression
Simon F
  • 4.3k
  • 13
  • 30

There's actually a reasonably good mathematical reason for doing bit replication:

First note that the n-bit string, $N$, actually represents the value $\frac{N}{2^n-1}$ and we want to produce the m-bit string, $M$, where $n<m$ and $$\frac{N}{2^n-1}\approx\frac{M}{2^m-1}$$

We first scale numerator and denominator with $$\frac{N.(2^n+1)}{(2^n-1)(2^n+1)}\approx \frac{M}{2^m-1}$$ and this simplifies to $$\frac{N.(2^n+1)}{2^{2n}-1}\approx \frac{M}{2^m-1}$$

In your case, $n$ and $m$ are 5 and 8 respectively and we can "stop" here (but the process can be repeated, ad nauseum, if m >> n).

We next make the approximation: $$\frac{N.(2^n+1)}{2^{2n}}\approx \frac{M}{2^m}$$ which simplifies to $$\frac{N.(2^n+1)}{2^{2n-m}}\approx M $$

Note that $N.(2^n+1)$ is equivalent to repeating the n-bit string, to create a 2n-bit string, and the division, shifts off the $2n-m$ LBS to leave an M bit result.

QED

Of course, the 'correct' calculation is $M=\lfloor(\frac{(2^m-1) N}{2^n-1}+\frac{1}{2}\rfloor$ but this approximation, in general, works most of the time. Of course there are times when it's inaccurate, but IIRC only by one bit and relatively infrequently.

Simon F
  • 4.3k
  • 13
  • 30