A practical application for Gray codes
Suppose you have two devices both of which get their digital clock via a LEMO connector on the front panel. Device A sends signals to device B via a cable. Whether or not device B can read the signals sent by device A correctly depends on whether the signals have been stable for long enough at the time when the signals are read (typcially the rising edge of the digital clock). Varying the delays of the clock signal into either device should show a range of delays where the signals can be read correctly and a range where the communication does not work.
For obvious reasons one does not need to go beyond the duration of one clock cycle. In my case, the clock frequency was about 40 MHz (corresponding to a clock cycle length of 25ns). I decided that steps of 2ns would be sufficient for the test I had to do. I used set of cables ‘lengths’ corresponding to delays of powers of two: 2ns, 4ns, 8ns and 16ns.
Now cycle is as follows: insert the delay x into the clock cable for device A, run a test, replace the delay on the clock cable to device A by another combination of the test cables, rerun the test etc. How do you optimize the number of times one has to connect/disconnect cables ? Certainly, stepping from 2ns to 30ns (or to 26 ns) by increasing the delay by 2ns at each step is not optimal…
Gray codes provide a solution to this answer. For example, a 4 bit Gray code traverses all binary numbers from 0000 to 1111 but in a way where for each step only one bit changes. Applying this to the delay scanning problem, this means that cable delays are tested in the following order:
| Gray code | Corresponding set of cables |
total delay | action for next step |
|---|---|---|---|
| 0000 | none | 0ns | add 2ns cable |
| 0001 | 2ns | 2ns | add 4ns cable |
| 0011 | 4ns + 2ns | 6ns | remove 2ns cable |
| 0010 | 4ns | 4ns | add 8ns cable |
| 0110 | 8ns + 4ns | 12ns | add 2ns cable |
| 0111 | 8ns + 4ns + 2ns | 14ns | remove 4ns cable |
| 0101 | 8ns + 2ns | 10ns | remove 2ns cable |
| 0100 | 8ns | 8ns | add 16ns cable |
| 1100 | 16ns + 8ns | 24ns | add 2ns cable |
| 1101 | 16ns + 8ns + 2ns | 26ns | add 4ns cable |
| 1111 | 16ns + 8ns + 4ns + 2ns | 30ns | remove 2ns cable |
| 1110 | 16ns + 8ns + 4ns | 28ns | remove 8ns cable |
| 1010 | 16ns + 4ns | 20ns | add 2ns cable |
| 1011 | 16ns + 4ns + 2ns | 22ns | remove 4ns cable |
| 1001 | 16ns + 2ns | 18ns | remove 2ns cable |
| 1000 | 16ns | 16ns | remove 16ns cable |
Andre Holzner's Blog 