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

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 .