##
Constructing an *n*-bit Gray code[edit]

The binary-reflected Gray code list for

*n*bits can be generated recursively from the list for*n−1*bits by reflecting the list (i.e. listing the entries in reverse order), concatenating the original list with the reversed list, prefixing the entries in the original list with a binary 0, and then prefixing the entries in the reflected list with a binary 1.^{[6]}For example, generating the*n*= 3 list from the*n*= 2 list:2-bit list: | 00, 01, 11, 10 | |

Reflected: | 10, 11, 01, 00 | |

Prefix old entries with 0: | 000, 001, 011, 010, | |

Prefix new entries with 1: | 110, 111, 101, 100 | |

Concatenated: | 000, 001, 011, 010, | 110, 111, 101, 100 |

The one-bit Gray code is

*G*_{1}= (0, 1). This can be thought of as built recursively as above from a zero-bit Gray code*G*_{0}= { Λ } consisting of a single entry of zero length. This iterative process of generating*G*_{n+1}from*G*_{n}makes the following properties of the standard reflecting code clear:*G*_{n}is a permutation of the numbers 0, ..., 2^{n}−1. (Each number appears exactly once in the list.)*G*_{n}is embedded as the first half of*G*_{n+1}.- Therefore the coding is
*stable*, in the sense that once a binary number appears in*G*_{n}it appears in the same position in all longer lists; so it makes sense to talk about*the*reflective Gray code value of a number:*G*(*m*) = the*m*-th reflecting Gray code, counting from 0. - Each entry in
*G*_{n}differs by only one bit from the previous entry. (The Hamming distance is 1.) - The last entry in
*G*_{n}differs by only one bit from the first entry. (The code is cyclic.)

## No comments:

## Post a Comment