Skew-tolerant gray codes

Abstract

Skew-tolerant Gray codes have the property that consecutive code words differ in only one co-ordinate position, and the additional property that, in each consecutive group of three consecutive code words, the first and third code words differ in only two adjacent coordinate positions.

1. An apparatus for decoding a code word of a skew-tolerant Gray code sequence, comprising:
 a first selector responsive to a root code word in the code word for selecting an initial code sequence position p; 
 at least a second selector responsive to an extension of the root code word in the code word for selecting sign and offset values with which to adjust p; 
 at least one arithmetic unit for combining the sign value with p to produce a signed value of p; 
 at least one arithmetic unit for combining the signed value of p with the offset value to produce an interim value of p; and 
 at least one arithmetic unit for performing a modulo calculation of the interim value of p to produce an adjusted value of p. 
 
   
   
     2. The apparatus of  claim 1 , further including a lookup table associating root code words with respective values of p, wherein the first selector includes a multiplexer having a control input for receiving a root code word and a data input for receiving a value of p from the table which is associated with the root code word received by the control input. 
   
   
     3. The apparatus of  claim 2 , further including at least one lookup table associating extensions of the root code word with sign and offset values, wherein the at least a second selector includes a multiplexer having a control input for receiving an extension of the root code word and a data input for receiving sign and offset values from the at least one lookup table which are associated with the extension. 
   
   
     4. The apparatus of  claim 1 , wherein the skew-tolerant Gray code sequence is coded by a binary Gray code derived from an n-bit binary Gray code C n , in which:
 an n+2 bit binary Gray code C n+2  is generated using C n , the binary Gray code C n+2  having 4M code words c n   0  through c n   N−1 , where N is less than or equal to 2 n  and being generated by: 
 changing the leftmost bit between the code words c n   0  and c n   1 ; 
 finding the largest value M such that the rightmost bit changes between code words c n   M−2  and c n   M−1 ; and 
 forming 4M code words of C n+2  by extending the first M code words of C n  by a single bit at each end, with reversals in the order of the code words of C n  as required to yield an extended code X, wherein: 
         x   k     n   +   2       =     {             [           0   ,             c   k   n     ,         0         ]     ,           0   <   k   ≤   M                 [           0   ,             c     M   -   k   +   1     n     ,         1         ]     ,           M   <   k   ≤     2   ⁢   M                   [           1   ,             c   k   n     ,         1         ]     ,             2   ⁢   M     <   k   ≤     3   ⁢   M                   [           1   ,             c     M   -   k   +   1     n     ,         0         ]     ,             3   ⁢   M     <   k   ≤     4   ⁢   M                   
 
 
   
   
     5. The apparatus of  claim 4 , wherein the n-bit binary code is a single bit binary code. 
   
   
     6. The apparatus of  claim 4 , wherein the n-bit binary code is a two-bit binary code. 
   
   
     7. The apparatus of  claim 6 , wherein the two bit binary code is given by a code table having four code words in the order {01}, {11}, {10}, {00}. 
   
   
     8. The apparatus of  claim 7 , wherein the n-bit binary code is a three-bit binary code. 
   
   
     9. The apparatus of  claim 8 , wherein the three bit binary code is given by a code table having eight code words in the order {110}, {010}, {000}, {001}, {011}, {111}, {101}, {100}. 
   
   
     10. An apparatus for generating a skew-tolerant Gray code from an n-bit binary Gray code C n , comprising:
 means for using C n  to generate an n+2 bit binary Gray code C n+2  having 4M code words c n   0  through c n   N−1 , where N is less than or equal to 2 n , by: 
 means for changing the leftmost bit between the code words c n   0  and c n   1 ; 
 means for finding the largest value M such that the rightmost bit changes between code words c n   M−2  and c n   M−1 ; and 
 means for forming 4M code words of C n+2  by extending the first M code words of C n  by a single bit at each end, with reversals in the order of the code words of C n  as required to yield an extended code X, wherein: 
         x   k     n   +   2       =     {             [           0   ,             c   k   n     ,         0         ]     ,           0   <   k   ≤   M                 [           0   ,             c     M   -   k   +   1     n     ,         1         ]     ,           M   <   k   ≤     2   ⁢   M                   [           1   ,             c   k   n     ,         1         ]     ,             2   ⁢   M     <   k   ≤     3   ⁢   M                   [           1   ,             c     M   -   k   +   1     n     ,         0         ]     ,             3   ⁢   M     <   k   ≤     4   ⁢   M                   
 
 
   
   
     11. The apparatus of  claim 10 , wherein the n-bit binary code is a single bit binary code. 
   
   
     12. The apparatus of  claim 10 , wherein the n-bit binary code is a two-bit binary code. 
   
   
     13. The apparatus of  claim 12 , wherein the two bit binary code is given by a code table having four code words in the order {01}, {11}, {10}, {00}. 
   
   
     14. The apparatus of  claim 10 , wherein the n-bit binary code is a three-bit binary code. 
   
   
     15. The apparatus of  claim 14 , wherein the three bit binary code is given by a code table having eight code words in the order {110}, {010}, {000}, {001}, {011}, {111}, {101}, {100}. 
   
   
     16. A coding system, comprising:
 an encoder for generating a skew-tolerant Gray code from an n-bit binary Gray code C n , the encoder comprising:
 means for using C n  to generate an n+2 bit binary Gray code C n+2  having 4M code words c n   0  through c n   N−1 , where N is less than or equal to 2 n , by: 
 means for changing the leftmost bit between the code words c n   0  and c n   1 ; 
 means for finding the largest value M such that the rightmost bit changes between code words c n   M−2  and c n   M−1 ; and 
 
 means for forming 4M code words of C n+2  by extending the first M code words of C n  by a single bit at each end, with reversals in the order of the code words of C n  as required to yield an extended code X, wherein: 
         x   k     n   +   2       =     {             [     0   ,     c   k   n     ,   0     ]     ,           0   <   k   ≤   M                 [     0   ,     c     M   -   k   +   1     n     ,   1     ]     ,           M   <   k   ≤     2   ⁢   M                   [     1   ,     c   k   n     ,   1     ]     ,             2   ⁢   M     <   k   ≤     3   ⁢   M                   [     1   ,     c     M   -   k   +   1     n     ,   0     ]     ,             3   ⁢   M     <   k   ≤     4   ⁢   M                   
 
 a decoder for decoding code words of a skew-tolerant Gray code sequence, comprising:
 a first selector responsive to a root code word in the code word for selecting an initial code sequence position p; 
 at least a second selector responsive to an extension of the root code word in the code word for selecting sign and offset values with which to adjust p; 
 at least one arithmetic unit for combining the sign value with p to produce a signed value of p; 
 at least one arithmetic unit for combining the signed value of p with the offset value to produce an interim value of p; and 
 
 at least one arithmetic unit for performing a modulo calculation of the interim value of p to produce an adjusted value of p. 
 
   
   
     17. The program medium of  claim 16 , wherein the n-bit binary code is a single bit binary code. 
   
   
     18. The program medium of  claim 10 , wherein the n-bit binary code is a two-bit binary code.