|
RDM General Implementation Discussion General Discussion and questions relating to implementing RDM in a product. |
|
Thread Tools | Search this Thread | Display Modes |
September 20th, 2006 | #1 |
Junior Member
Join Date: Jun 2006
Posts: 14
|
Discovery Checksum Problem Analysis
Hello
David our resident guru , has analysed the probability of getting one good discovery response when in fact 2 devices are replying at the same time (below) The problem seems to appear a lot more often than I have won the lotto ! Maybe there should be some kind of implementation guide that could recommend having a small backoff timer of some sort to reduce the probability of having this problem. (like ethernet PHYs) Considering most lighting rigs are composed of at least multiple devices of a same manuafcturer that were probably purchased at the same time, I't very possible for an end user to have sequential device IDs. Nic www.enttec.com 1. Discovery Collision Analysis 1.1 Uncorrupted msg MID1 | 0xAA MID1 | 0x55 MID0 | 0xAA MID0 | 0x55 DID3 | 0xAA DID3 | 0x55 DID2 | 0xAA DID2 | 0x55 DID1 | 0xAA DID1 | 0x55 DID0 | 0xAA DID0 | 0x55 ------------- CSUM1 | 0xAA CSUM1 | 0x55 CSUM0 | 0xAA CSUM0 | 0x55 CSUM = (MID1|0xAA + MID0|0xAA + DID3|0xAA + DID2|0xAA + DID1|0xAA + DID0|0xAA) + (MID1|0x55 + MID0|0x55 + DID3|0x55 + DID2|0x55 + DID1|0x55 + DID0|0x55) = (MID1 + MID0 + DID3 + DID2 + DID1 + DID0) + 6*0xFF = (MID1 + MID0 + DID3 + DID2 + DID1 + DID0) + 0x5FA 1.2 Single Bit Corruption Suppose there are 2 responders A and B with UIDs which differ only in DIDx. Collided msg would differ from original msgs A and B in the DIDx bytes and the checksum bytes, as follows. CSUMB - CSUMA = (DIDBx|0xAA + DIDBx|0x55) - (DIDAx|0xAA + DIDAx|0x55) COLLISION(DIDAx|0xAA, DIDBx|0xAA) = (DIDAx | 0xAA) & (DIDBx | 0xAA) = (DIDAx & DIDBx) | 0xAA COLLISION(DIDAx|0x55, DIDBx|0x55) = (DIDAx | 0x55) & (DIDBx | 0x55) = (DIDAx & DIDBx) | 0x55 COLLISION(CSUMA1|0xAA, CSUMB1|0xAA) = (CSUMA1 | 0xAA) & (CSUMB1 | 0xAA) = (CSUMA1 & CSUMB1) | 0xAA COLLISION(CSUMA1|0x55, CSUMB1|0x55) = (CSUMA1 | 0x55) & (CSUMB1 | 0x55) = (CSUMA1 & CSUMB1) | 0x55 COLLISION(CSUMA0|0xAA, CSUMB0|0xAA) = (CSUMA0 | 0xAA) & (CSUMB0 | 0xAA) = (CSUMA0 & CSUMB0) | 0xAA COLLISION(CSUMA0|0x55, CSUMB0|0x55) = (CSUMA0 | 0x55) & (CSUMB0 | 0x55) = (CSUMA0 & CSUMB0) | 0x55 Taking checksum over collided msg gives CSUM(over EUID part of collided msg) - CSUMA = [(DIDAx & DIDBx) | 0xAA] + [(DIDAx & DIDBx) | 0x55] - - [DIDAx | 0xAA] - [DIDAx | 0x55] = (DIDAx & DIDBx) - DIDAx CSUM1(recovered from CSUM part of collided msg) = (CSUMA1 & CSUMB1) CSUM0(recovered from CSUM part of collided msg) = (CSUMA0 & CSUMB0) => CSUM(recovered from CSUM part of collided msg) = CSUMA & CSUMB = CSUMA & [CSUMA + (DIDBx|0xAA) + (DIDBx|0x55) - (DIDAx|0xAA) - (DIDAx|0x55)] = CSUMA & [CSUMA + DIDBx - DIDAx] For collided msg to have good checksum: CSUMA + (DIDAx & DIDBx) - DIDAx = CSUMA & (CSUMA + DIDBx - DIDAx) For the Special Case where DIDBx is obtained from DIDAx by changing a single bit from 0 to 1: bit k of DIDAx = 0 and DIDBx = DIDAx + (1 << k), where 0 <= k <= 7. DIDAx & DIDBx = DIDAx CSUMA = CSUMA & (CSUMA + (1<<k)), which is true whenever bit k of CSUMA is 0. CONCLUSION: For the special case of a single bit difference in the device IDs, there is a 50% chance of the discovery collision having a good checksum when ideally the discovery collision checksum should be bad. Last edited by nic123; September 20th, 2006 at 11:54 PM. |
September 22nd, 2006 | #2 |
Task Group Member
Join Date: Sep 2006
Posts: 26
|
A fundamental assumption made above is that the transmission medium acts as a wire-and, such that the receiver sees a one if both transmitters transmit a one, and sees a zero otherwise. DMX uses a differential transmission medium, and so a one is transmitted as
Code:
D+ = V+ D- = V- Code:
D+ = V- D- = V+ Code:
D+ = V- of B D- = V- of A Code:
|D+ - D-| < 0.2 V Cheers, Shaun Jackman Pathway Connectivity |
September 24th, 2006 | #3 |
Junior Member
Join Date: Jun 2006
Location: London
Posts: 13
|
You are forgetting two things:
The SN75176 is a very old device, and more modern transceivers usually guarantee that a 0V input will give a high output. The MAX485 datasheet says: "The receiver input has a fail-safe feature that guarantees a logic-high output if the input is open circuit." Also, the controller's terminating network is required to put a slight bias on the line. Either of these things would ensure that a collision by drivers of exactly equal strength would result in a one being received. |
September 24th, 2006 | #4 |
Junior Member
Join Date: Sep 2006
Posts: 1
|
Thanks for the corrections.
Repeating the analysis (below) assuming the contending bits are random still gives a 25% probability of good checksum on collided message. Is this to be expected? David Nemes 1. Discovery Collision Analysis 1.1 Uncollided msg MID1 | 0xAA MID1 | 0x55 MID0 | 0xAA MID0 | 0x55 DID3 | 0xAA DID3 | 0x55 DID2 | 0xAA DID2 | 0x55 DID1 | 0xAA DID1 | 0x55 DID0 | 0xAA DID0 | 0x55 ------------- CSUM1 | 0xAA CSUM1 | 0x55 CSUM0 | 0xAA CSUM0 | 0x55 CSUM = (MID1|0xAA + MID0|0xAA + DID3|0xAA + DID2|0xAA + DID1|0xAA + DID0|0xAA) + (MID1|0x55 + MID0|0x55 + DID3|0x55 + DID2|0x55 + DID1|0x55 + DID0|0x55) = (MID1 + MID0 + DID3 + DID2 + DID1 + DID0) + 6*0xFF = (MID1 + MID0 + DID3 + DID2 + DID1 + DID0) + 0x5FA 1.2 Collided Msg Suppose there are 2 responders A and B with UIDs which differ only in DIDx. CSUMB - CSUMA = (DIDBx|0xAA + DIDBx|0x55) - (DIDAx|0xAA + DIDAx|0x55) = DIDBx - DIDAx In general it is assumed that the collision between 2 bytes would preserve the noncontending bit positions which have the same value in both bytes, and create random bit values in the contending bit positions which have different values in both bytes. COLLISION(X, Y) = (X & Y) | [(X ^ Y) & R], where 0 <= R <= 255 is a uniformly distributed random number. For the special case where DIDBx is obtained from DIDAx by changing a single bit from 0 to 1, and also where bit k of CSUMA is 0 (which would happen 50% of the time): bit k of DIDAx = 0, bit k of CSUMA = 0, DIDBx = DIDAx + (1 << k), where 0 <= k <= 7. DIDAx & DIDBx = DIDAx CSUMB - CSUMA = (1 << k) CSUMA & CSUMB = CSUMA Collided msg would differ from original msgs A and B in the DIDx bytes and the checksum bytes, as follows. COLLISION(DIDAx|0xAA, DIDBx|0xAA) = [(DIDAx | 0xAA) & (DIDBx | 0xAA)] | [((DIDAx | 0xAA) ^ (DIDBx | 0xAA)) & R1] = [(DIDAx & DIDBx) | 0xAA] | [(DIDAx ^ DIDBx) & 0x55 & R1] = [DIDAx | 0xAA] | [(1 << k) & 0x55 & R1] COLLISION(DIDAx|0x55, DIDBx|0x55) = [(DIDAx | 0x55) & (DIDBx | 0x55)] | [((DIDAx | 0x55) ^ (DIDBx | 0x55)) & R2] = [(DIDAx & DIDBx) | 0x55] | [(DIDAx ^ DIDBx) & 0xAA & R2] = [DIDAx | 0x55] | [(1 << k) & 0xAA & R2] COLLISION(CSUMA1|0xAA, CSUMB1|0xAA) = [(CSUMA1 & CSUMB1) | 0xAA] | [(CSUMA1 ^ CSUMB1) & 0x55 & R3] = [CSUMA1 | 0xAA] COLLISION(CSUMA1|0x55, CSUMB1|0x55) = [(CSUMA1 & CSUMB1) | 0x55] | [(CSUMA1 ^ CSUMB1) & 0xAA & R4] = [CSUMA1 | 0x55] COLLISION(CSUMA0|0xAA, CSUMB0|0xAA) = [(CSUMA0 & CSUMB0) | 0xAA] | [(CSUMA0 ^ CSUMB0) & 0x55 & R5] = [CSUMA0 | 0xAA] | [(1 << k) & 0x55 & R5] COLLISION(CSUMA0|0x55, CSUMB0|0x55) = [(CSUMA0 & CSUMB0) | 0x55] | [(CSUMA0 ^ CSUMB0) & 0xAA & R6] = [CSUMA0 | 0x55] | [(1 << k) & 0xAA & R6] Taking checksum over collided msg gives CSUM(over EUID part of collided msg) - CSUMA = ([DIDAx | 0xAA] | [(1 << k) & 0x55 & R1]) + ([DIDAx | 0x55] | [(1 << k) & 0xAA & R2]) - [DIDAx | 0xAA] - [DIDAx | 0x55] when k is even: CSUM(over EUID part of collided msg) - CSUMA = ([DIDAx | 0xAA] | [(1 << k) & 0x55 & R1]) + ([DIDAx | 0x55]) - [DIDAx | 0xAA] - [DIDAx | 0x55] = [(1 << k) & R1] when k is odd: CSUM(over EUID part of collided msg) - CSUMA = ([DIDAx | 0xAA]) + ([DIDAx | 0x55] | [(1 << k) & 0xAA & R2]) - [DIDAx | 0xAA] - [DIDAx | 0x55] = [(1 << k) & R2] CSUM1(recovered from CSUM part of collided msg) = [CSUMA1 | 0xAA] & [CSUMA1 | 0x55] = CSUMA1 CSUM0(recovered from CSUM part of collided msg) = ([CSUMA0 | 0xAA] | [(1 << k) & 0x55 & R5]) & ([CSUMA0 | 0x55] | [(1 << k) & 0xAA & R6]) = CSUMA0 | [(1 << k) & 0xAA & R6] | [(1 << k) & 0x55 & R5] => CSUM(recovered from CSUM part of collided msg) = CSUMA | [(1 << k) & 0xAA & R6] | [(1 << k) & 0x55 & R5] when k is even: CSUM(recovered from CSUM part of collided msg) = CSUMA | [(1 << k) & R5] when k is odd: CSUM(recovered from CSUM part of collided msg) = CSUMA | [(1 << k) & R6] For collided msg to have good checksum, when k is even: CSUMA + [(1 << k) & R1] = CSUMA | [(1 << k) & R5], which is true whenever bit k of R1 = bit k of R5 (50% chance given that bit k of CSUMA = 0, or 25% chance when bit k of CSUMA has any value). For collided msg to have good checksum, when k is odd: CSUMA + [(1 << k) & R2] = CSUMA | [(1 << k) & R6], which is true whenever bit k of R2 = bit k of R6 (50% chance given that bit k of CSUMA = 0, or 25% chance when bit k of CSUMA has any value). CONCLUSION: For a single bit difference in the device IDs, there is at least a 25% chance of the discovery collision having a good checksum when ideally the discovery collision checksum should be bad. |
Bookmarks |
Thread Tools | Search this Thread |
Display Modes | |
|
|
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Incremental Discovery | prwatE120 | RDM General Implementation Discussion | 1 | September 29th, 2021 04:18 PM |
Discovery Response Preamble | prwatE120 | RDM General Implementation Discussion | 0 | January 20th, 2007 01:22 AM |
Table 6-6 Checksum Example Error | prwatE120 | RDM Interpretation Questions | 1 | January 19th, 2007 07:49 PM |
Checksum curiosa | sjackman | RDM General Implementation Discussion | 3 | October 3rd, 2006 07:24 AM |