11 bit × ten multiply

The second multiplication that occurs in the spigot algorithm is that of an eleven bit number (g) by the decimal value ten (i.e. 1010, hex A).

A pragmatic place to start is with the previously described 10 bit × 6 bit multiplier; the six bits of the multiplier being set to 001010, with an eleventh bit added to the multiplicand.

The fact that we are multiplying by a constant (1010) leads to some considerable simplifications; in the first place, all the AND gates can go. The game continues with removing all the circuitry that doesn't do anything. This quickly reduced the thing to just 4 off 74283 4-bit full adder chips.

(One 'trick' that proved useful is to hook up the 11-bit input to an 11-bit counter circuit (3 off 74163 binary counters), and see which lines remain at logic zero (or one), as the counter clocks, and then remove the same.)

In fact, it proves possible to reduce the chip count to just three 74283 chips: after some thought it's apparent that the lower 74283 chip (see circuit below) can do two things: (1) generate bits 12 - 14 of the product, and (2) generate bit P₃ of the product and the carry bit that is needed by what is now the uppermost 74283. We can get away with this because inputs A3 and B3 to the lower 74283 are always zero; whatever happens in the lower part of this adder (i.e. inputs A1, A2, B1, B2) cannot affect the A4, B4 part of the adder (i.e. adder outputs S4 and C4). Cool huh?!

Here's the final 11 bit × ten multiply circuit:

Pressing the space bar activates the circuit in Digital:

Here the input (multiplicand, B) is 7FF or 2047 decimal; the output is 4FF6 or 20470 decimal, the correct answer! The three LEDs, which are the carry outputs from the adders, are included for diagnostics.

Some further examples:

317 × A = 1EE6

754 × A = 4948

001 × A = 000A

007 × A = 0046

In the final circuit, the lowest significant bit of the product (P₀) is connected to ground - it's always zero. The next two bits of the product are also straightforward, given by P₁= B₀ and P₂= B₁. 

This makes sense: since multiplying a number by ten is the same as multiplying the number by 2 and then by 5, it is evident that the lowest significant bit of the product will always be zero; multiplication by 2 being a left shift. The fact that next two bits, P₁ and P₂, are given by B₁ and B₂ is clear from the following example. The right-most three digits of the second row, formed by a shift of the multiplicand (11111111111), have nothing added to them - the row above is zero and the row below is zero; the right-most three digits of the fourth row are also (always) zero, hence the boxed digits appear in the product.

Chip count:

3 × 74283 (4-bit full adder)