# Addition modulo 26 in Digital Logic

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?

• Why would you want to do this? Is this homework? Apr 11, 2013 at 19:49
• Could the result of computing S-26 be used somehow to determine whether S is greater than 25? Also, since S-26 is the same as S+(32-26)-32, might it be conceptually easier to think in terms of computing (S+6) and dropping the high bit? Apr 11, 2013 at 20:21
• Is this your question in a nutshell... How do I convert a 6 bit number to mod 26? Apr 11, 2013 at 20:32
• @Andy, yes. That is what I need. Apr 11, 2013 at 20:36
• There's not many 'tricks' you can do for modulo in digital logic (assuming you're not doing mod power of two). It's essentially a messy division operation or looping and subtracting. I would expect any solution to this to feel a bit 'clunky'.
– Tim
Apr 11, 2013 at 20:39

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.

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