# Hamming Code Circuit

Given the following Hamming Code, I was tasked to implement the following circuits using gates.

• Transmiter Circuit (Parity Bit Generator).
• Error Detector Circuit of the receptor (Parity Check).
• Data Bit Corrector.

I did the first two circuits, but I can't seem to figure out the corrector circuit.

Parity Bit Generator Circuit:

Parity Check Circuit:

I was hoping for a little push to help me finish the rest of the circuit.

• You've already got the generators: $P_N$. Apply them to their three inputs from the received data and compare their outputs with the received parity bits. (XOR?) These comparisons have eight possibilities. If all three are 0, no error. Otherwise, you have 7 possible error conditions. But if only one of the comparison outputs is 1 (the other are 0) then it's the parity bit that went wrong. So no data change. This leaves only ... hmm... shocking? ... Four remaining possibilities!! Can you work out what that means? – jonk Jun 9 '18 at 6:36
• Yes, the remaining possibilities are 011 (I1), 110 (I2), 111 (I3) and 101 (I4). Now with this information I can make a truth table with 3 imputs (S1, S2, S3) and 4 outputs, each output will be applied in a XOR gate along with each data bit. When the inputs are 000, 001, 010, 100 I will want no changes in my data bits, the rest of the inputs will have an specific output that will fix any erroneous data bit. For example, if the inputs are 110 (I2), then the desired outputs will be i1=0, i2=1, i3=0, i4=0 (0100), this secures that the bit I2 will be the one corrected. I understand it now, thanks. – Leonel Jun 9 '18 at 8:25

Here's your diagram, given your table. This diagram makes things really easy to understand, I think:

This is just another way of writing your table, except more visual and quicker to navigate without holding things in your head while you read a row.

The original generators, $P_1$, $P_2$, and $P_3$, will have produced their values as a result of generating parity for the values within their circle. Doesn't really matter if this is odd or even parity generation, so long as the receiver of the message shares the method. This generates 7 total bits out of 4 data bits.

Upon receipt, a receiver performs the same function using generators $P_1$, $P_2$, and $P_3$ to replicate the work, applying them to the received 4 data bits. This produces another set of three generated parity values, which can now be compared with the parity bits included in the 7-bit message. (Using an XOR or XNOR.)

There are eight possible combinations of these three comparison bits. But if the generated parities match up with the transmitted parities, then there is no single-bit error (this doesn't entirely exclude multi-bit errors.) So that accounts for one of the combinations, leaving seven to consider.

It's possible that one of the parity bits is itself the error and that the data bits are just fine. But if that's so, then only one of the comparisons will produce an error. If only one, then it is a parity bit error. There are exactly three possible cases where only one comparison generates an error. So this accounts for three more combinations, leaving only four remaining to consider.

(You can choose to correct the parity bit, but I think that's pointless. If you want to correct the parity bits you can do that merely by accepting your own generated parities.)

There are three combination where two of the comparisons generate an error. These will account for those data bits which affect two parity bits. And there is only one combination which affects all three parity bits. From the diagram above, it should be very easy to see which are which. Those are the data bits that might have singly been corrupted and they should be appropriately inverted to get back the original value.