Gray code sequences

Details Gray code sequences Gray code sequences

2001-09-14

2004-03-09

Tokar, Michael (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from constant distance codes

C341S098000, C341S159000, C341S160000, C377S034000, C711S217000, C711S218000

Reexamination Certificate

active

06703950

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to integrated circuits and logic devices. In particular, the present invention pertains to an apparatus and method for Gray encoding and decoding.
2. Description of Related Art
A Gray code sequence is characterized by the fact that there is only one bit difference between any two adjacent numbers of the sequence. In contrast, in a binary code sequence, adjacent numbers may differ by several bits. Therefore, the use of Gray code avoids the transition errors or glitches caused by simultaneous transitions of multiple bits in binary code. Table 1 shows a decimal number sequence and corresponding 4-bit binary and Gray code sequences.
TABLE 1
Decimal and 4-bit Binary and Gray Code
Decimal
Gray Code
Binary Code
Number
G(3)
G(2)
G(1)
G(0)
B(3)
B(2)
B(1)
B(0)
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
2
0
0
1
1
0
0
1
0
3
0
0
1
0
0
0
1
1
4
0
1
1
0
0
1
0
0
5
0
1
1
1
0
1
0
1
6
0
1
0
1
0
1
1
0
7
0
1
0
0
0
1
1
1
8
1
1
0
0
1
0
0
0
9
1
1
0
1
1
0
0
1
10
1
1
1
1
1
0
1
0
11
1
1
1
0
1
0
1
1
12
1
0
1
0
1
1
0
0
13
1
0
1
1
1
1
0
1
14
1
0
0
1
1
1
1
0
15
1
0
0
0
1
1
1
1
Note that in Table 1 the Gray code sequence is symmetric about the axis of reflection (between Gray codes 7 and 8) with the exception of the most-significant bit (G(3)).
There are many existing schemes for generating, encoding and decoding Gray code. See for example, U.S. Pat. No. 5,754,614 issued to Charles B. Guyt, for a Gray code counter; U.S. Pat. No. 5,448,606 issued to Andrew H. Snelgrove, for a Gray code counter; U.S. Pat. No. 4,618,849 issued to John H. Bruestle, also for a Gray code counter; U.S. Pat. No. 5,097,491 issued to Christopher M. Hall, for a modular Gray code counter; U.S. Pat. No. 5,164,968 issued to Kurt J. Otto, for a nine-bit Gray code generator; U.S. Pat. No. 5,426,756 issued to Jonathan Shyi and Kenny Shen, for a memory controller and method for determining the empty/full status of a FIFO memory using Gray code counters; and U.S. Pat. No. 5,084,841 issued to Williams et al. for a programmable Status flag generator FIFO using Gray code.
As used throughout this disclosure, L refers to the length of a binary code sequence being Gray encoded. Similarly, N is defined as the bit number of the binary code to be Gray encoded.
Gray encoders convert binary code (B) to corresponding Gray code (G). Let G(N−1) . . . G(0) denote a code word for an N-bit gray code number, and let B(N−1) . . . B(0) denote a code word for the corresponding binary number, where the indexes 0 and N−1 denote the least and most significant bits respectively. Then, the i
th
bit G(i) can be obtained from the corresponding binary bits as follows:
G
(
N
−1)=
B
(
N
−1)  (Eq. 1(a))
G
(
i
)=
B
(
i
)
XOR B
(
i
+1) 0
≦i≦N
−2  (Eq. 1(b))
Where the operation XOR is the Boolean operation of exclusive or for the operands between which it is positioned, defined as: 0 XOR 0=0, 1 XOR 1=0, 1 XOR 0=1, 0 XOR 1=1.
FIG. 1
shows an example of the prior art logic, called a Gray encoder, to implement the above encoding procedure.
Gray decoders convert Gray code numbers to corresponding binary code numbers. Again, let G(N−1) . . . G(0) denote a code word for an N-bit gray code number, and let B(N−1) . . . B(0) denote the code word for the corresponding binary number, where the indices 0 and N−1 denote the least and most significant bits, respectively. The i
th
bit B(i) can be obtained as follows:
B
(
N
−1)=
G
(
N
−1)  (Eq. 2(a))
B
(
i
)=
B
(
i
+1)
XOR G
(
i
) 0
≦i≦N
−2  (Eq. 2(b))
FIG. 2
shows an example of the logic, called a gray decoder, to implement the above decoding procedure.
The disadvantage of prior art Gray encoders/decoders is that they only operate on full-length binary code sequences. A full-length binary code sequence is defined as an N-digit binary code where the length (L) is equal to two to the power N:
L
=2
N
As an example of this full-length limitation, if the memory size needed for FIFO memory control logic is 18, the bit number N for the address bus has to be at least 5 (2
4
≦18≦2
5
). However, with N=5, the L=2
N
limitation for prior art Gray encoders/decoders requires that the memory size be 32, nearly twice the memory required by the memory control logic.
In view of the foregoing, it can be appreciated that a need exists for a Gray encoder/decoder that can encode/decode Gray code sequences that have lengths less than 2
N
.
SUMMARY OF THE INVENTION
The present invention includes a method of Gray encoding/decoding between Gray code sequences, that are of even length less than or equal to 2
N
that are symmetrical about an axis of reflection with the exception of the most significant bit, and binary code sequences.
The present invention further includes a method of Gray encoding/decoding between N-bit binary code sequences, that have any length less than or equal to 2
N
, and (N+1)-bit Gray code sequences that have a length of 2*L.
Because the above methods enable the Gray encoding/decoding of binary code sequences that are less than full length, the method of the present invention results in a geometrically reduced storage requirement over the prior art.
The present invention additionally comprises a method for generating Gray Code sequences of even length less than 2
N
where N is the bit number and which are symmetrical about an axis of reflection with the exception of the most-significant bit.


REFERENCES:
patent: 4055841 (1977-10-01), Crawford
patent: 4427972 (1984-01-01), Haville et al.
patent: 4618849 (1986-10-01), Bruestle
patent: 4780894 (1988-10-01), Watkins et al.
patent: 5001479 (1991-03-01), Becker et al.
patent: 5084841 (1992-01-01), Williams et al.
patent: 5097491 (1992-03-01), Hall
patent: 5164968 (1992-11-01), Otto
patent: 5426756 (1995-06-01), Shyi et al.
patent: 5448606 (1995-09-01), Snelgrove
patent: 5754614 (1998-05-01), Wingen
patent: 6041370 (2000-03-01), Guyt
patent: 6314154 (2001-11-01), Pontius
patent: 6337893 (2002-01-01), Pontius

Affiliated with

Also associated with

Rating

Gray code sequences does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Gray code sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Gray code sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3234489