E1.20 RDM (Remote Device Management) Protocol Forums  

Go Back   E1.20 RDM (Remote Device Management) Protocol Forums > RDM Developer Forums > RDM General Implementation Discussion

RDM General Implementation Discussion General Discussion and questions relating to implementing RDM in a product.

Reply
 
Thread Tools Search this Thread Display Modes
Old September 20th, 2006   #1
nic123
Junior Member
 
Join Date: Jun 2006
Posts: 14
Default 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 10:54 PM.
nic123 is offline   Reply With Quote
Old September 22nd, 2006   #2
sjackman
Task Group Member
 
Join Date: Sep 2006
Posts: 26
Default

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-
and a zero is transmitted as
Code:
D+ = V-
D- = V+
If we assume that the more negative voltage is seen by the receiver -- I'm not entirely positive this assumption is valid, but it seems reasonable -- and transmitter A is transmitting a one, and transmitter B is transmitting a zero, the receiver will see
Code:
D+ = V- of B
D- = V- of A
The datasheet for the SN75176 differential transceiver says that if the absolute differential voltage is less than 0.2 V
Code:
|D+ - D-| < 0.2 V
the output is indeterminate. In practice, if V- of B is more positive than V- of A, the receiever will see a one, otherwise the receiver will see a zero. The result being that in the case of a collision, the bit the receiver sees depends more on the characteristics of the transmitting transceivers than the bits being transmitted.

Cheers,
Shaun Jackman
Pathway Connectivity
sjackman is offline   Reply With Quote
Old September 24th, 2006   #3
Nigel Worsley
Junior Member
 
Join Date: Jun 2006
Location: London
Posts: 13
Default

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.
Nigel Worsley is offline   Reply With Quote
Old September 24th, 2006   #4
dcn123
Junior Member
 
Join Date: Sep 2006
Posts: 1
Default

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.
dcn123 is offline   Reply With Quote
Reply

Bookmarks

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Incremental Discovery prwatE120 RDM General Implementation Discussion 0 September 26th, 2008 12:49 AM
Discovery Response Preamble prwatE120 RDM General Implementation Discussion 0 January 20th, 2007 12:22 AM
Table 6-6 Checksum Example Error prwatE120 RDM Interpretation Questions 1 January 19th, 2007 06:49 PM
Checksum curiosa sjackman RDM General Implementation Discussion 3 October 3rd, 2006 06:24 AM


All times are GMT -6. The time now is 07:02 PM.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2019, vBulletin Solutions, Inc.