How to create hamming distance using xor and adders?

Question

My goal is to create n bit hamming distance circuit but using only xors and adders. I do understand that xor is required to compare two bits, but once I have all comparison results, how I can add them using adders to get the total count.

If the result of XOR is ABCD (four bits) then one approach can be:

A ADD B = S_0,C_0
C_0(S_0 ADD C)= S_1,C_1
C_1(S_1 ADD D)= S_2,C_2

However, if we set all A,B,C,D to 1 then this gives 1000 which is not equal to 4. Can you please let me know which part I am missing in the solution? Thanks

Answer 1

A ADD B = S_0,C_0
C_0(S_0 ADD C)= S_1,C_1
C_1(S_1 ADD D)= S_2,C_2

If I understand things, you should be using S to be the sum and C to be the carry. I may not be understanding that correctly, though. But if so, then try the following:

$$\begin{align*} \left(A + B\right) \rightarrow \left[S_0,C_0\right] \\\\ \left(C+D\right) \rightarrow \left[S_1,C_1\right] \\\\ \left(S_0+S_1\right) \rightarrow \left[S_2,C_2\right] \\\\ \left(C_0+C_1\right) \rightarrow \left[S_3,C_3\right] \\\\ \left(C_2+C_3\right) \rightarrow \left[S_4,C_4\right] \end{align*}$$

Your answer will be the the binary value: \$S_4 S_3 S_2\$.

This is effectively the following schematic:

^{simulate this circuit – Schematic created using CircuitLab}

So, using \$ABCD=1111\$:

$$\begin{align*} \left(1_A + 1_B\right) \rightarrow \left[0_{S_0},1_{C_0}\right] \\\\ \left(1_C + 1_D\right) \rightarrow \left[0_{S_1},1_{C_1}\right] \\\\ \left(0_{S_0} + 0_{S_1}\right) \rightarrow \left[0_{S_2},0_{C_2}\right] \\\\ \left(1_{C_0} + 1_{C_1}\right) \rightarrow \left[0_{S_3},1_{C_3}\right] \\\\ \left(0_{C_2} + 1_{C_3}\right) \rightarrow \left[1_{S_4},0_{C_4}\right] \end{align*}$$

Your answer is: \$1_{S_4} 0_{S_3} 0_{S_2}\$.

---

You could use a full adder to reduce this a bit.

^{simulate this circuit}

---

Here's a generalized half adder approach:

^{simulate this circuit}

You may notice how wasteful it can be. But it is easy to visualize the extension. And that seems to be your goal. Try extending it to one more bit, adding in \$X_4\$ and note that you can do some pruning of the tree, then.

This approach handles both odd and even numbers of bits in the Hamming symbol string.

If you want to handle only an even number, you could create two of these "trees," one for the even-numbered input bits and one for the odd-numbered input bits and then sum the results at the end of the two trees with a standard adder arrangement.