Skip to main content

Gray Codes and Paths on the n-cube

01 May 1958

New Image

A G r a y code is a m e a n s of quantizing an angle a n d representing it in a b i n a r y a l p h a b e t . T h e encoding is such t h a t angles in a d j a c e n t q u a n t u m intervals are encoded into n-tuples of b i n a r y digits which differ in j u s t one place. F o r example, t a k i n g n = 3, as t h e angle increases f r o m 0° to 360°, t h e b i n a r y code for t h e angle might go t h r o u g h t h e succession 000, 001, 011, 010, 110, 111, 101, 100 a n d back to 000. G r a y codes are used when t h e encoding is performed by a code wheel. At angles close to t h e b o u n d a r y between two q u a n t u m intervals, a n y of t h e digits which change at t h e b o u n d a r y are likely to be in error. In a G r a y code there is only one such questionable digit, a n d a mistake in this digit only gives to t h e angle the code for the a d j a c e n t q u a n t u m interval. Although the G r a y code example given for n = 3 is easily generalized to o b t a i n t h e well known G r a y (reflected binary) code for a n y n, there are, in general, a large n u m b e r of other codes which also change one digit at a time. O u r problem is to find these other codes. In special applications, some of the others m a y be preferable to t h e conventional G r a y code. F o r instance, it m a y be desirable to use other n u m b e r s of q u a n t u m intervals beside powers of 2; powers of 10 m i g h t be a n a t u r a l choice. If the q u a n t i t y being encoded is a length r a t h e r t h a n an angle, one can d r o p the r e q u i r e m e n t t h a t the first a n d last q u a n t u m interval h a v e codes differing in j u s t one position.