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().

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

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_test

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,
    Academic Press, 1978,
    ISBN: 0-12-519260-6,
    LC: QA164.N54.

Source Code:


Last revised on 24 January 2019.