# GRAY_CODE_DISPLAY Display Hamming Distances for Binary and Gray Codes

GRAY_CODE_DISPLAY, a MATLAB program which computes the Hamming distance tables for both the binary and Gray codes, and displays 3D plots that illustrate how the Gray code does a better job of providing nearby representations for nearby numbers.

Consider the numbers 0 through N. We can represent them using the binary code or the Gray code. Both codes can be thought of as vectors of M binary digits.

The Hamming distance between two vectors counts the number of digits that are different.

In the binary code, the Hamming distance between two M vectors that represent consecutive integers can be any value from 1 to M. However, if we use the Gray code, this Hamming distance is always 1.

Moreover, this fact implies that the Hamming distance between Gray codes for integers that are 2 places apart is 2, 3 places apart is 3 or less, and in general for integers K places apart, the Hamming distance between the Gray codes will be no more than K.

The property that nearby integers have nearby Gray codes can be a very useful fact, for example, when using genetic algorithms, where small differences in the object should be accomplishable by small changes in the "genes".

This program computes and compares the Hamming distance matrices for the binary and Gray codes. Note that for the Gray code, there is an obvious smooth valley running along the diagonal.

The plots of the distance matrices are created by code that was extracted from the program quad_mesh_order1_display().

### Languages:

GRAY_CODE_DISPLAY is available in a MATLAB version.

### Related Data and Programs:

COMBO, a MATLAB library which includes routines for ranking, unranking, enumerating and randomly selecting balanced sequences, cycles, graphs, Gray codes, subsets, partitions, permutations, restricted growth functions, Pruefer codes and trees.

gray_code_display, a MATLAB program which computes the Hamming distance tables for both the binary and Gray codes, and displays 3D plots that illustrate how the Gray code does a better job of providing nearby representations for nearby numbers.

IMAGE_MATCH_GENETIC, a MATLAB program which tries to match a 256x256 JPEG image by blending 32 colored rectangles, using ideas from genetic algorithms, based on an example by Nick Berry.

QUAD_MESH_ORDER1_DISPLAY, a MATLAB program which plots piecewise constant data associated with a mesh of quadrilaterals;

SUBSET, a MATLAB library which enumerates, generates, ranks and unranks combinatorial objects including combinations, Gray codes, index sets, partitions, permutations, subsets, and trees.

### Reference:

1. Albert Nijenhuis, Herbert Wilf,
Combinatorial Algorithms for Computers and Calculators,
Second Edition,
ISBN: 0-12-519260-6,
LC: QA164.N54.

### Source Code:

• gray_code_display.m, a program which displays the Hamming distance matrix for both the binary codes and Gray codes of the numbers 0 through N.
• timestamp.m, prints the YMDHMS date as a timestamp.

### Examples and Tests:

• gray_code_display.txt, the output from the command gray_code_display(17).
• b17.png, a plot of the Hamming distance matrix for the binary codes for the numbers 0 through 17.
• g17.png, a plot of the Hamming distance matrix for the Gray codes for the numbers 0 through 17.

Last revised on 24 January 2019.