Skew-tolerant gray codes
View Patent ↗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. A method executable by a programmed processor for generating a binary Gray code, comprising:
providing an n-bit binary Gray code C n ;
using C n , generating an n+2 bit binary Gray code C n+2 having 4M code words c 0 n through c N−1 n , where N is less than or equal to 2 n , by:
changing the leftmost bit between the code words c 0 n and c 1 n ;
finding the largest value M such that the rightmost bit changes between code words c M−2 n and c M−1 n ; 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
.
2. The method of claim 1 , wherein the n-bit binary code is a single bit binary code.
3. The method of claim 1 , wherein the n-bit binary code is a two-bit binary code.
4. The method of claim 3 , wherein the two bit binary code is given by a code table having four code words in the order {01}, {11}, {10}, {00}.
5. The method of claim 1 , wherein the n-bit binary code is a three-bit binary code.
6. The method of claim 5 , 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}.
7. A method executable by a programmed processor for generating a skew-tolerant Gray code having code words with co-ordinate positions, comprising:
receiving a number n representing the length of the code words;
if n is equal to or less than 3, selecting a predetermined code table containing 2, 4, or 8 code words, in which the predetermined tables having 4 or eight code words are characterized by at least two properties:
a first property that consecutive code words differ in only one coordinate position;
and a second property that, in each consecutive group of three consecutive code words, the first and third code words differ in only two adjacent coordinate positions;
otherwise, if n is even, selecting the predetermined code table containing 4 code words as a first code table, or if n is odd, selecting the predetermined code table with 8 code words as the first code table; and then performing the following recursion;
setting a parameter L to a value equal to the number of code words in the first code table;
forming a second code table from the first (3L/4+2) code words in the first code table;
forming a third code table by adding a zero at the beginning and end of each code word in the second code table;
forming a fourth code table by adding a one at the beginning and end of each code word in the second code table;
forming a fifth code table by reversing the order of code words in the second code table;
forming a sixth code table by adding a zero at the beginning and a one at the end of each code word in the fifth code table;
forming a seventh code table by adding a one at the beginning and a zero at the end of each code word in the fifth code table;
forming an eighth code table by concatenating corresponding code words of the third, fourth, sixth, and seventh code tables;
if the length of the code words in the eighth code table is less than n, continuing the recursion using the eighth code table as the first code table; otherwise,
ending the recursion.
8. The method of claim 7 , wherein the predetermined code table having four code words is given by the four code words in the order {01}, {11}, {10}, {00}.
9. The method of claim 7 , wherein the predetermined code table having eight code words is given by the eight code words in the order {110}, {010}, {000}, {001}, {011}, {111}, {101}, {100}.
10. A program medium having computer-readable code means for performing a method to generate a binary Gray code, the method comprising:
providing an n-bit binary Gray code C n ;
using C n , generating an n+2 bit binary Gray code C n+2 having 4M code words c 0 n through c N−1 n , where N is less than or equal to 2 n , by:
changing the leftmost bit between the code words c 0 n and c 1 n ;
finding the largest value M such that the rightmost bit changes between code words c M−2 n and c M−1 n ; 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
.
11. The program medium of claim 10 , wherein the n-bit binary code is a single bit binary code.
12. The program medium of claim 10 , wherein the n-bit binary code is a two-bit binary code.
13. The program medium 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 program medium of claim 10 , wherein the n-bit binary code is a three-bit binary code.
15. The program medium 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 program medium having computer-readable code means for performing a method to generate a skew-tolerant Gray code having code words with co-ordinate positions, comprising:
receiving a number n representing the length of the code words;
if n is equal to or less than 3, selecting a predetermined code table containing 2, 4, or 8 code words, in which the predetermined tables having 4 or eight code words are characterized by at least two properties:
a first property that consecutive code words differ in only one co-ordinate position;
and a second property that, in each consecutive group of three consecutive code words, the first and third code words differ in only two adjacent coordinate positions;
otherwise, if n is even, selecting the predetermined code table containing 4 code words as a first code table, or if n is odd, selecting the predetermined code table with 8 code words as the first code table; and then performing the following recursion;
setting a parameter L to a value equal to the number of code words in the first code table;
forming a second code table from the first (3L/4+2) code words in the first code table;
forming a third code table by adding a zero at the beginning and end of each code word in the second code table;
forming a fourth code table by adding a one at the beginning and end of each code word in the second code table;
forming a fifth code table by reversing the order of code words in the second code table;
forming a sixth code table by adding a zero at the beginning and a one at the end of each code word in the fifth code table;
forming a seventh code table by adding a one at the beginning and a zero at the end of each code word in the fifth code table;
forming an eighth code table by concatenating, in order, the rows of the third, sixth, fourth, and seventh code tables;
if the length of the code words in the eighth code table is less than n, continuing the recursion using the eighth code table as the first code table; otherwise,
ending the recursion.
17. The program medium of claim 16 , wherein the predetermined code table having four code words is given by the four code words in the order {01}, {11}, {10}, {00}.
18. The program medium of claim 16 , wherein the predetermined code table having eight code words is given by the eight code words in the order {110}, {010}, {000}, {001}, {011}, {111}, {101}, {100}.