gray_code_display


gray_code_display, a MATLAB code 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 MIT license

Languages:

gray_code_display is available in a MATLAB version.

Related Data and Programs:

combo, a MATLAB code 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

quad_mesh_order1_display, a MATLAB code which plots piecewise constant data associated with a mesh of quadrilaterals;

subset, a MATLAB code 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.