Need help understanding a parity check with XOR
-
Hi!
My first post here, please be gentle!
I'm building a MQTT ethernet gateway with 433 MHz receiver and transmitter. I have some cheap wall switches and also a couple of temperature/humidity sensors (UPM/ESIC).
Right now I'm trying to shape the messages which will be relayed from my Arduino.
The protocol for the temperature/humidity sensor is very well explained here:
http://wiki.nethome.nu/doku.php/upmprotocolBut I don't understand the part about the parity bits:
"C = Checksum. bit 1 is XOR of odd bits, bit 0 XOR of even bits in message" (bit 0 and 1 refers to the two LSB of part 4)Some example data:
Can someone please help me understand the error check algorithm? Also, tips of code which verifies the data parity/integrity are much appreciated!
Regards, Niklas.
-
Hi Niklas, welcome to MySensors!
Just a note: It looks like your example data is missing 4 bits in byte 0. Byte 0 only has 4 bits in your example data, but it should have 8, like this:
XOR is actually really simple. Imagine a clicker counter, like this:
Every time you press the lever, the counter will increment by 1. When you reach 9999 it will roll over to 0.Now imagine a clicker counter with only one wheel/digit. The wheel will count 0...9 and the roll over to 0.
Now imagine that the wheel only has two numbers: 0 and 1. It will count 0, 1 and then roll over to 0 again. That's XOR.
The description of the upmp protocol says that bit 1 of the checksum is XOR of odd bits. Get your XOR clicker ready. Look at the first number in the first row (bit 7 in byte 0). It is a 1, so we press the clicker which goes from 0 to 1. We skip the second number (since 2 is even) and look at the third bit. The third bit is a 0 so we don't press the lever. The clicker stays at 1. We move on to bit 3, 1... until we reach the end of byte 3. Look at the number on the clicker. That's your first C number.
Reset the XOR clicker to 0. Start over with the first row but now only look at the even positions. Click away until you reach the end of the third byte. Look at the number on the clicker. That's the second C number.
When you check the integrity of the message, you do as described above. You then compare the two C bits you got from your XOR clicker to the two C bits that was in the message. If they don't match, you know there was an error in the transmission.
-
Thank you @mfalkvidd for the very educational description. I thought that the check could have been as you described but I felt that it was too crude and simple. This doesn't seem to be the most typical use of "exclusive or" but I guess it does the job.
Is it common to only include part of the transmission packet in the parity check? I would have assumed that the nib (Nib4) should be part of the bit check and that the parity bits would then be set or not set so that the complete packet is confirmed.
Anyways I have found description of the protocol with conflicting interpretations so I guess that I anyway will have to do some confirmations regarding the packet content and structure.
Your observation regarding the incomplete first byte led me to find an error in the code I've stolen. I was 4 bits short, thank you!
-
@NickBuilder said:
Thank you @mfalkvidd for the very educational description. I thought that the check could have been as you described but I felt that it was too crude and simple. This doesn't seem to be the most typical use of "exclusive or" but I guess it does the job.
There are more advanced ways. This scheme will not detect two bit errors in the same group (even or odd) and it can only detect errors, not correct them. But without knowing the reasoning behind the design it is impossible to say if it was a bad choice or not.
Is it common to only include part of the transmission packet in the parity check? I would have assumed that the nib (Nib4) should be part of the bit check and that the parity bits would then be set or not set so that the complete packet is confirmed.
Yes, it is common to exclude things. What things depends on the use case.
From what I understand, the exact same message is always sent three times. If the z-bits were included in the checksum, a new checksum would have to be calculated for each time the message is sent. That would probably have a negative effect on the communication speed and would add complexity to the solution without adding any real benefit.
If the checksum bits themselves (C) were included in the checksum calculation they would affect the checksum so the checksum would change so the checksum would have to be calculated again which would cause the checksum to change so the checksum would have to be calculated again and so on.
