Welcome to the CSC Q&A.
Get help and give help!
Write great code!
It is our choices... that show what we truly are, far more than our abilities.

Categories

+19 votes

Could someone try and explain how the 4-bit hamming code works? I'm just struggling with how to relate the parity bits to the correct positions and how to determine if a parity bit is supposed to be a 1 or a 0

asked in CSC335_Spring2019 by (3.4k points)

3 Answers

+12 votes

I think this video will help you.
Link: https://www.youtube.com/watch?v=373FUw-2U2k

answered by (4.8k points)
+12 votes

The way that I was interpreting this problem is that for the examples we are given a 12-bit message that includes data bits as well as the bits included in the hamming code.

Parity bits are in positions of powers of two (and including 1). So for a 12-bit message we have 4 parity bits.

P# = parity bits
D# = data bits

So we now have this format for our message. (Remember that we count from 0 to 11 for a 12-bit message)

| P1 | P2 | D3 | P4 | D5 | D6 | D7 | P8 | D9 | D10 | D11 | D12 |

All parity bits must ensure an even number of 1s among all of the bits it is responsibly for.

P1 has one bit between each that it is responsible for which alternates among the other bits.P1, D3, D5, D7, D9, D11.

P2 has two bits between each that it is responsible for and will alternate every two bits. P2, D3, D6, D7, D10, D11.

P4 has four bits between each that it is responsible for and will alternate every four bits. P4, D5, D6, D7, and D12.

P8 has eight bits between each that it is responsible for and will alternate every eight bits. This includes the final 5 bits since this is only a 12-bit message.

If we had a message that was 16-bits or longer we would also include more bits that P8 is responsible for as well as a P16 parity bit.

Now we need to go through and check to see that there are an even amount of 1s for each of the parity bits. If a parity bit check fails, make note of the parity bit number (i.e. P1 would be 1 and P8 would be 8). Let's say that The parity bit check fails for P2 and P8, we then add up the values of the parity bits (i.e. 8 + 2 which is 10) this shows where our problematic bit is which is in position 10 which translates to D11 since we start counting at zero in CS. To ~fix~ this bit we use the bitwise XOR or simply just flip the bit from its value (i.e. 0 to 1, or 1 to 0). Now to ensure that this is fixed you can check the two parity bit checks that failed and they should now pass and have an even amount of 1s.

Please let me know if this makes sense or if it is wrong! I can maybe explain this further in class on a whiteboard to ensure that it makes sense for how I learned it.

answered by (5.7k points)
edited by
+9 votes

The first parity bit is for all the data bits, so add up all the 1's in the data bits and the first parity bit and make sure the 1's add up to an even number.

The second parity bit is for the 4,5,6, and 7 data bits, so add them up with the second parity bit and make sure it adds up to an even number.

Repeat for the last two parity bits. If you find an error in one or more of the bits then determine what data bits are correct and which are wrong by comparing which data bits correspond to which parity bits.

answered by (1.3k points)
...