Browse Prior Art Database

An optimal way to compare m LSB of two n bit grey coded numbers

IP.com Disclosure Number: IPCOM000014811D
Original Publication Date: 2002-Jul-01
Included in the Prior Art Database: 2003-Jun-20
Document File: 2 page(s) / 65K

Publishing Venue

IBM

Abstract

Sometimes we need to compare a part of 2 Gray code number, just to know if they are equal or not. It is impossible to compare them directly, and there is a need to convert them back to binary. The way to do it is expensive in logic: FIGURE 1. conversion of Gray code to binary The following method suggest a shorter way to do so. In order to compare m-least significant bits of 2 n-bit Gray code number, it is enough to transform only the first (n-m+1) most significant bits. Proof: The transformation from binary to Gray code is: gi=bi-1 Xor bi if i>0 , and g0=b0 . gi is the i bit of the Gray code representation of a number, and bi is the corresponding bit in the binary code representation. If the m least significant bits of two numbers are equal, then m-1 of the Gray code representation will be equal too. Only the most significant bit of the m bits should be converted by the Gray to binary transformation: bi=g0 Xor g1 Xor ... Xor gi , i=n-m+1 .

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

An optimal way to compare m LSB of two n bit grey coded numbers

Sometimes we need to compare a part of 2 Gray code number, just to know if they are equal or not. It is impossible to compare them directly, and there is a need to convert them back to binary. The way to do it is expensive in logic: FIGURE 1. conversion of Gray code to binary

    The following method suggest a shorter way to do so. In order to compare m-least significant bits of 2 n-bit Gray code number, it is enough to transform only the first (n-m+1) most significant bits.

Proof:The transformation from binary to Gray code is: gi=bi-1 Xor bi if i>0, and g0=b0

. gi is the i bit of the Gray code representation of a number, and bi is the corresponding bit in the binary code representation. If the m least significant bits of two numbers are equal, then m-1 of the Gray code representation will be equal too. Only the most significant bit of the m bits should be converted by the Gray to binary transformation: bi=g0 Xor g1 Xor ... Xor gi, i=n-m+1.

An example:

    lets compare two numbers which may be represented as 4-bit binary code: 3 and 15, and compare the 2 least significant bits. In our problem n=4, and m=2. 3 mod 4=3, and 15 mode 4=3 and therefore they are equal in their 2 least significant bits. In Binary code this is strait forward: 0011 vs. 1111. In gray code their representation is 0010 vs. 1000, and the comparison is not obvious. Lets now perform the transformation to binary, but instead of transforming the n bits (i.e. the 4 bits), which requires at least n-1 xor gates (i.e. 3 xor gates), we will perform the transformation on n-m+1 bits (i.e 4-2+1=3 bits), which requires m-n xor gates (i.e 2xor gates). for the 1st number - 0010 - the result of the transformation is 0 (0 xor 0) (0 xor 0 xor 1) 0 = 0010, for the 2nd number - 1000 - the result of the transformation is 1 (1 xor 0) (1 xor 0 xor 0) 0 = 1110. Now we can compare the 2 least significant bits, and see they match. In this simple example we saved the transformation of only 1 bit out of 4, but the general case in m bits of n we save the transformation of m-1 bits. As we will see in the following example, the benefit may be much greater. Application Example: Optimal Gray Code Read and Write Pointers of Different Clock Domain Compare.

    A way to synchronize data between different clock domain might be a fifo. One side write to...