Skew-tolerant gray codes

• US 6,885,321 B1
• Filed: 12/12/2003
• Issued: 04/26/2005
• Est. Priority Date: 12/12/2003
• Status: Expired due to Fees

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Hitachi Global Storage Technologies Netherlands BV (Western Digital Corporation)
• Inventors: Blaum, Mario, Wilson, Bruce Alexander
• Primary Examiner(s): Tokar, Michael
• Assistant Examiner(s): Nguyen, John B
• Application Number:
  US10/734,943
• Time in Patent Office: 501 Days
• Field of Search: 341/98, 341/97, 341/106, 360/48, 360/75, 360/77.08, 360/49, 360/40, 711217-219, 377/34
• US Class Current: 341/98
• CPC Class Codes: H03M 7/16 Conversion to or from unit-distance codes, e.g. Gray code, reflected binary code

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.

Claims

1. A method executable by a programmed processor for generating a binary Gray code, comprising:

providing an n-bit binary Gray code Cⁿ;

using Cⁿ, generating an n+2 bit binary Gray code Cⁿ⁺² having 4M code words c₀ⁿ through c<sub>N−

1</sub>ⁿ, where N is less than or equal to 2ⁿ, by;

changing the leftmost bit between the code words c₀ⁿ and c₁ⁿ;

finding the largest value M such that the rightmost bit changes between code words c<sub>M−

2</sub>ⁿ and c<sub>M−

1</sub>ⁿ; and

forming 4M code words of Cⁿ⁺² by extending the first M code words of Cⁿ by a single bit at each end, with reversals in the order of the code words of Cⁿ as required to yield an extended code X, wherein;

$x_k^{n+2}=\{\begin{array}{cccc}[0,& c_k^n,& 0],& 0<<br><br>k\le <br><br>M\\ [0,& c_{M-k+1}^n,& 1],& M<<br><br>k\le <br><br>2<br><br>M\\ [1,& c_k^n,& 1],& 2<br><br>M<<br><br>k\le <br><br>3<br><br>M\\ [1,& c_{M-k+1}^n,& 0],& 3<br><br>M<<br><br>k\le <br><br>4<br><br>M.\end{array}$

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ⁿ;

using Cⁿ, generating an n+2 bit binary Gray code Cⁿ⁺² having 4M code words c₀ⁿ through c<sub>N−

1</sub>ⁿ, where N is less than or equal to 2ⁿ, by;

changing the leftmost bit between the code words c₀ⁿ and c₁ⁿ;

finding the largest value M such that the rightmost bit changes between code words c<sub>M−

2</sub>ⁿ and c<sub>M−

1</sub>ⁿ; and

forming 4M code words of Cⁿ⁺² by extending the first M code words of Cⁿ by a single bit at each end, with reversals in the order of the code words of Cⁿ as required to yield an extended code X, wherein;

$x_k^{n+2}=\{\begin{array}{cccc}[0,& c_k^n,& 0],& 0<<br><br>k\le <br><br>M\\ [0,& c_{M-k+1}^n,& 1],& M<<br><br>k\le <br><br>2<br><br>M\\ [1,& c_k^n,& 1],& 2<br><br>M<<br><br>k\le <br><br>3<br><br>M\\ [1,& c_{M-k+1}^n,& 0],& 3<br><br>M<<br><br>k\le <br><br>4<br><br>M.\end{array}$

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}.