Addition modulo 26 in Digital Logic

Question

I have two 5-bit signals, each guaranteed to be carrying a value between 0 and 25. I would like to add them together and get another 5-bit value between 0 and 25, simply taking the sum % 26.

The best solution I have so far involves adding them together to get 6-bit sum S, then also calculating S-26 and selecting between the two based on the output of a comparator to check if S > 25. This requires quite a few parts to create (4 4bit adders, 2 4-bit comparators, 5 bit mux) and feels kinda clunky.

I know I could do it with a simple rom or micro pretty easy, but I am a bit of a masochist for designs built from 74xx and similar chips only. Is there a more elegant solution to this problem I am missing?

Answer 1

You should be able to do it with three 4-bit adders, a 4-bit, 2-input mux and an OR gate:

Use two of the adders to form the 6-bit sum of the original two numbers. If the MSB (bit 5) of this sum is set, you know you need to subtract 26 from the result.

Here's the trick: Doing a %26 operation on a number is not going to affect the LSB (bit 0), so the LSB of the sum formed above is already the LSB of the final result.

Use the third adder to add the constant 0011 (the decimal value 6, with the LSB dropped, too) to bits 4:1 of the first sum. If the carry out from this adder is set, then the original sum was 26 or greater, and you need to subtract 26 from it — which is what the output of this adder is!

OR together the carry bits from the two adders and use its output to control the mux. The mux is going to select bits 4:1 of the first sum if the OR gate is low, or bits 3:0 of the second sum if the OR gate is high, to become bits 4:1 of the final result.

I hope that is clear; if you need a diagram, let me know.

Answer 2

Here is a method that uses less resources than does the first answer.

Let [x4..x0] and [y4..y0] be the inputs, [z4..z0] =([x4..x0]+[y4..y0])%26 the desired output. For simplicity, I assimilate the bit vector [x4..x0] and the integer it represents, in binary, MSbit first.

Build z0 = x0^y0.

Build u0 = x0&y0. We have [z4..z1] = ([x4..x1]+[y4..y1]+u0)%13.

Build [v4..v0] = [x4..x1]+[y4..y1]+u0 , using one 4-bit adder with carry input and output. We have [v4..v0]<26, and [z4..z1] = [v4..v0]%13.

Build w0 = v4|(v3&v2&(v1|v0)). It is 0 iff [v4..v0]<13, 1 otherwise. Let w1 = w0 (no cost), now [w1..w0] is 0 iff [v4..v0]<13, 3 otherwise. We thus have [z4..z1] = ([v4..v1]+[w1..w0])%16 !!

Build [z4..z1] = ([v4..v1]+[w1..w0])%16 , using one 4-bit adder. Carry input and the two high-order bits of one input are grounded, the two low-order bits are tied together to be v4|(v3&v2&(v1|v0)).

---

Circuitry used: the 74HC83 pictured below; 3 AND, 2 OR, 1 XOR. That's three other common 14-pin ICs, leaving 6 unused 2-input gates.

---

74HC83 (4-Bit Binary Full Adder with Fast Carry) logic diagram