File GrayCode.txt W. Kahan version dated 3 Mar. 2009 ~~~~~~~~~~~~ supersedes 13 July 2007 version This ASCII text-file documents package GrayPack of MATLAB functions grays.m gray2int.m int2gray.m btr2int.m graynext.m grayndcs.m gray2btr.m btr2gray.m int2btr.m graystep.m programmed to manipulate the Gray Cyclic Binary Codes. Included also are conversions between their codewords' two MATLAB representations. What are the Gray Cyclic Binary Codes? ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ For any integer n > 0 these can be construed as a sequence of 2^n distinct n-bit integers g each of which differs from its precursor in just one bit-position. Column G = grays(n) exhibits all 2^n of these integers g at once; 2^n invocations g = graynext(d, g, n) step through all 2^n consecutive codewords in the forward direction if d > 0 or else backward; but these integers g need 0 < n < 54 . Gray Codes can be construed also as a sequence of 2^n distinct Bit- Rows B = [b1, b2, ..., bn] in which each bj is either 0 or 1 . Now 2^n invocations of B = graystep(d, B) step through all 2^n codewords in turn in the forward direction if d > 0 or else backward. Henceforth we abbreviate "codeword" to "code" unless it is confusing. Conversion between a bit-row B = (B(:)' ~= 0) and an integer g >= 0 representing the same Gray code in GrayPack enforces the relation B = [b1, b2, ..., bn] <--> g = b1 + b2*2 + b3*4 + ... + bn*2^(n-1) . At n = 4 all 2^n Gray Codes G = grays(n) and bit-rows B are ... Index Gray Code Bit-row B Change-Index k g = G(1+k) b1 b2 b3 b4 m = M(1+k) --- ---------- --- --- --- --- ------------ 0 0 0 0 0 0 +1 1 1 1 0 0 0 +2 2 3 1 1 0 0 -1 3 2 0 1 0 0 +3 4 6 0 1 1 0 +1 5 7 1 1 1 0 -2 6 5 1 0 1 0 -1 7 4 0 0 1 0 +4 8 12 0 0 1 1 +1 9 13 1 0 1 1 +2 10 15 1 1 1 1 -1 11 14 0 1 1 1 -3 12 10 0 1 0 1 +1 13 11 1 1 0 1 -2 14 9 1 0 0 1 -1 15 8 0 0 0 1 -4 ( 16 - - - 0 0 0 0 ) The last column M = grayndcs(n) of Change-Indices tells which bit, namely b|m| , will change and which way, namely by sign(m) . GrayPack's sequence of Gray codes exhibited here is the most common since its G(1+k) and index k determine each other though no more be known about n than that 2^n > k . Other sequences can be obtained by permuting and/or complementing columns under the bj's , or by cyclically reodering the indices under k ; every such sequence of Gray codes is a periodic function of index k with period 2^n , so we redefine G(1+k) = G(1 + mod(k, 2^n)) when k < 0 or k >= 2^n . GrayPack lets Gray codewords be represented in two ways. MATLAB's usual way is a single 8-byte floating-point number like those in the first two columns tabulated above. The second way is a Bit-Row like B = [b1, b2, ..., bn] in which each bj is an 8-byte floating-point number either 0.0 or 1.0 . Bit-rows waste memory but may save time in some applications. GrayPack's Gray code programs let their user choose to manipulate either or both representations. However, there are limits: MATLAB's consecutive integers all have magnitudes running from 0 to 2^53 = bitmax + 1 . MATLAB's bigger 8-byte floating-point integers are no longer consecutive; they are all even (or infinite); GrayPack rejects them though it accepts bit-rows B with dimension n > 53 . MATLAB 7 and later versions support the computer's native unsigned integer uint** data-types; rewriting GrayPack's programs to use one would shrink memory occupancy and increase speed noticeably, and simplify checking of input arguments. But then GrayPack would not work under the last version, MATLAB 5.2, that runs on my favorite old computer, a 1992 33 MHz. 68040-based Apple Macintosh Quadra 950. Conversions ~~~~~~~~~~~ Two functions convert bit-rows <--> integers. If column K of m integers relates to m-by-n logical array Br of ones and zeros via either Br = int2btr(K, n) or K = btr2int(Br) then K = Br*[1; 2; 4; ...; 2^(n-1)] in the simplest case, namely if 0 < n < 54 and 0 <= K < 2^n . Otherwise int2btr(K, n) treats K as if it were mod(K, 2^n) . Both functions require 0 < n < 54 . Two functions map integer bit-rows Br <--> Gray code bit-rows Gr . If Br and Gr are m-by-n logical arrays whose every element is a one or a zero (i.e. Br = (Br ~= 0) , Gr = (Gr ~= 0) ) related via either Br = gray2btr(Gr) or Gr = btr2gray(Br) , then btr2int(Gr(i,:)) = G(1 + btr2int(Br(i,:))) for G = grays(n) and for 0 < i <= m , except that dimension n can exceed 53 now. Moreover, for arbitrary same-sized logical arrays X and Y both of these function satisfy the same commutative identity ... btr2gray(xor(X, Y)) == xor(btr2gray(X), btr2gray(Y)) and gray2btr(xor(X, Y)) == xor(gray2btr(X), gray2btr(Y)) . Two function map integer indices k <--> Gray code integers g . If MATLAB arrays k and g of nonnegative integers are related via either g = int2gray(k, n) or k = gray2int(g) then every g(i,j) = G(1 + mod(k(i,j), 2^n)) wherein G = grays(n) without computing all 2^n elements of G , provided 0 < n < 54 . Though 0 <= k = gray2int(g) < 2^n if 0 <= g < 2^n , int2gray(k, n) accepts a wider range of input integer indices k . Both functions run only in MATLAB 5 and later versions. Moreover, if X and Y are same-sized arrays of nonnegative integers less than 2^n , both functions satisfy the same commutative identity ... gray2int(bitxor(X, Y)) == bitxor(gray2int(X), gray2int(Y)) and int2gray(bitxor(X, Y), n) == bitxor(int2gray(X, n), int2gray(Y, n)) . Single Steps through the Gray Codes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Two functions graystep and graynext go from a given Gray code to one of its two immediate neighbors represented in the same way. Given a Gray code's bit-row Br = (Br(:)' ~= 0) , a neighbor's is Hr = graystep(d, Br) , forward if d > 0 , else backward, and computed rather faster than Hr = int2btr(int2gray( 2*(d>0)-1 + gray2int(btr2int(Br)) )) . (The current version of graystep runs faster again than before.) Which bit of Hr differs from the corresponding bit of Br ? It is the sole nonzero element of bit-row Dr = Hr - Br . This element Dr(m) has index m = abs(sum(cumsum(fliplr(Dr)))) ; and sign(Dr(m)) tells which way the bit changed. The change-index is m*sign(Dr(m)) . The bit-rows' common length n is limited only by available memory. Given n and an array g of n-bit Gray codes' representations as nonnegative integers, their neighbors' respective representations in MATLAB 5 and later versions constitute the nonnegative integer array h = graynext(d, g, n) , forward where d > 0 , else backward, wherein d is either a scalar or an array the same size as g . CONSTRAINT: 0 <= g < 2^n <= 2^53 . Which single bit of h(i,j) differs from the corresponding bit of g(i,j) ? Counting from 1 for the least significant (rightmost) bit, the changed bit is number m(i,j) where m = 1 + log2(abs(h - g)) ; and sign(h - g) tell which way the corresponding bits changed. Change-Indices, like m... above, tell which bit of a Gray code will change after a step forward to the next codeword, and are also made to tell the change's direction. M = grayndcs(n) is a column of 2^n change-indices corresponding to the column G = grays(n) of Gray codes. Counting up from 1 for the least-significant (rightmost) bit of G(1+k) , the advance to G(1 + k+1) changes bit number |M(1+k)| by sign(M(k+1)) . The last change-index M(2^n) is for the change from G(2^n) back to G(1) . Only memory capacity and your patience impose a limit upon n in grayndcs(n) . Application of Gray Codes to the Digital Goniometer ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This device encodes the angle, through which a circular disk has been turned, as a n-bit binary integer with a resolution of 1/2^n of a revolution. Inscribed in the disk are n circular tracks concentric with it, and 2^(n-1) uniformly spaced straight lines through the disk's center. The lines partition each track into 2^n equal cells half of which are filled with metal; the others are insulating. There are n wire brushes mounted along a fixed ray running over a radius of the disk and aligned so that each brush touches a different track. The brushes serve as electrical switches; each one closes when its brush touches a metal-filled cell. Cells along the Kth radius of the disk are metal-filled or insulating according as the elements of the Kth bit-row Br above are 1 or 0 . Consequently the electrical outputs from all n switches, regarded as an n-bit binary integer g , step through consecutive Gray Codes in array grays(n) as the disk turns. Gray Codes can be used in a similar way to encode the linear travel of a pneumatically or hydraulically driven piston, or of an iron rod in a solenoid activated electrically. And the switches can be photocells sensing black or reflective cells, instead of brushes touching metal. Before the Gray Code g put out by the switches can be interpreted as a linear position it must be converted to an integer k = gray2int(g) . This computation can be done electronically instead by n layers of EXCLUSIVE OR gates, but all that is a story for another day. Why use Gray Codes instead of filling cells so that the switches' outputs would step through consecutive binary integers? Using Gray Codes renders the Goniometer tolerant of tiny variations among the positions and lengths of cells and of brushes. So long as each brush touches just its own track, the switches' electrical outputs cannot be wrong by more than one step through the Gray Codes. Consequently the Goniometer's accuracy matches its resolution. Were the cells filled to produce electrical outputs intended to step through consecutive binary integers, an error in one switch's bit-position could throw the Goniometer off by as much as half a revolution. (An error as bad as this can be caused also by the utter failure -- stuck closed or open -- of a single switch no matter whether codes are binary or Gray.) The designers of Hitachi hard disk drives in San Jose, CA, patented "Skew-tolerant Gray Codes" ordered differently than the ones tabulated above. Besides adjacent codewords that differ in just one bit-position as do all Gray codes, these are so constrained that each triple of consecutive codewords vary in just the same two adjacent bit-positions. For n > 2 the number of these skew-tolerant n-bit codewords is if n is odd then 4*3^((n-1)/2) - 4 else 16*3^((n-4)/2) - 4 . Here is an example for n = 4 with 12 codewords: change- k b1 b2 b3 b4 index --- ---- ---- ---- ---- ~~~~~ 0 0 0 1 1 +1 1 1 0 1 1 +2 2 1 1 1 1 -3 3 1 1 0 1 -4 4 1 1 0 0 +3 5 1 1 1 0 -2 6 1 0 1 0 -1 7 0 0 1 0 +2 8 0 1 1 0 -3 9 0 1 0 0 +4 10 0 1 0 1 +3 11 0 1 1 1 -2 ( 12 0 0 1 1 +1 ) These skew-tolerant codes combine with other means to achieve a finer resolution than ordinary Gray codes could achieve in the face of some tiny misalignments that degrade the performance of hard disk drives. For details see U.S. Patents #6885321 and #7119975 (2006), but beware their many presumably unintentional typos. Further enhancements appear in "Construction of Distance-Separated Gray Codes" by M. Blaum, K. Lakovic and B. Wilson, Proc. IEEE GLOBECOM 2006, #1-4244-0357-X06. Application of Gray Codes to Hamiltonian Circuits in Hypercubes. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Regard logical bit-row B as the coordinates of a point in n-space. The set of all 2^n such points constitutes a (hyper)cube's vertices. Its edges are line segments parallel to coordinate axes, segments that join pairs of neighboring vertices which differ in only one coordinate. The array G = grays(n) , or the sequence of rows B = graystep(1, B) starting at B = zeros(1,n) and running 2^n - 1 steps, enumerates a sequence of vertices on a closed path that traverses only 2^n of the n*2^(n-1) edges and touches every one of the 2^n vertices just once. Such a path is called a "Hamiltonian Circuit". A Hypercube Architecture for massively parallel computation connects each of 2^n processors tightly to just n "neighbors" as if they were positioned at the vertices of an n-dimensional hypercube. All of them are connected also to one more central computer as if it were the conductor of the orchestra; and each processor has its own memory. To multiply two matrices of enormous dimensions, each is broken into 2^n submatrices distributed over the hypercube's processors with the aid of Gray codes, and then the multiplication is carried out with nearly minimal time wasted waiting for communications among memories. For the details see J.W. Demmel's lecture notes posted on the world-wide web: . Application of Gray Codes to Exhaustive Searches and Optimizations ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Suppose a function F depends upon, among other things, an array of parameters each of which can take only a few discrete values. Little generality is lost by assuming also that each of the n parameters can take only the values 0 and 1 . Then the function in question can be written either as F(g) where g is an n-bit integer, or as F(Br) where bit-row [b1, b2, b3, ..., bn] = Br = (Br(:)' ~= 0) . Suppose further that F costs very much more to compute than does the change in F when one of its n binary parameters bj changes. A situation like this motivated the construction of the MATLAB programs that manipulate Gray Codes to help locate the maximum of F . Other searches, such as for parameters where F falls between preassigned thresholds, can be assisted the same way. A costly computation of, say, F(0) was followed by (2^n - 1) cheap incremental computations of F(g) as g was stepped through the Gray Codes. This brute-force approach would have taken intolerably long had n been too big. When n is not too big, stepping through the column M = grayndcs(n) of change-indices may obviate the need for anything else in GrayPack to help conduct an exhaustive search. Because |M| <= n , all change- indices are small integers that fit into a column of 2^n short words. Example of Incremental Exhaustive Exploration ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This example arose from a problem posed by Prof. Michael Slawinski of Memorial Univ., Newfoundland. Given are two real symmetric L-by-L matrices X and Y . Each of them has n = L*(L+1)/2 elements on and above the diagonal. There are 2^n symmetric matrices W whose every element W(i,j) can be chosen to be either X(i,j) + Y(i,j) or else X(i,j) - Y(i,j)) independently of the other n-1 choices. For every such chosen W its ordered eigenvalues form a column w regarded as a point's coordinates in L-space. The distribution of these points may have physical significance, so all 2^n of them must be computed. This task's first step is the construction of a mapping from indices m of bm in the bit-row Br = [b1, b2, b3, ..., bn] to the n pairs (I(m), J(m)) of indices that locate matrix elements W(I(m), J(m)) and W(J(m), I(m)) . The simplest way constructs two n-columns thus: m = 0 ; I = zeros(n,1) ; J = I ; %... preallocates memory for i = 1:L, for j = i:L m = m+1 ; I(m) = i ; J(m) = j ; end, end Then, for k = 1:2^n , a desired eigenvector-column w(:,k) consists of the sorted eigenvalues of a k-th matrix W whose L^2 elements are computed (for m = 1:n ) from a k-th bit-row Br via a formula W(J(m),I(m)) = W(I(m),J(m)) = X(I(m),J(m)) + (2*Br(m) - 1)*Y(I(m),J(m)) after which Br is advanced to the next of the 2^n Gray codewords. The advantage of Gray codes Br over integers Br = int2btr(k-1,n) is substantial only if L is big, n huge and 2^n gargantuan, in which case two economies will reduce computation time. The first uses just one change-index m to alter one or two elements of W instead of recomputing all L^2 of them from the previous paragraph's formula. Whether m = M(k) from M = grayndcs(n) , or |m| is computed from the difference between graystep(1,Br) and Br as explained above under "Single Steps through the Gray Codes", doesn't matter. Just update W(I(|m|),J(|m|)) and, unless I(|m|) = J(|m|) , also update W(J(|m|),I(|m|)) to W(I(|m|),J(|m|)) + 2*sign(m)*Y(I(|m|),J(|m|)) , assuming the initial W = X - Y as required by the initial Br = 0 . The second computational economy exploits the low rank, 1 or 2 , of the matrix added to W to update it. (Every L-by-L symmetric matrix of rank 2 decomposes into a sum of two symmetric matrices of rank 1 each of the form s*v*v' whose s is a scalar and v an L-vector.) Given all the eigenvalues and eigenvectors of W , the eigenvalues and eigenvectors of a rank-1 update W + s*v*v' are computable relatively quickly by procedures discussed in the book "Matrix Computations" 3rd ed. (1996) by G.H. Golub and C.F. Van Loan, section "Eigensystems of Diagonal Plus Rank-1 Matrices", and elaborated in papers cited at the section's end. Moreover these procedures lend themselves well to parallel computation unless the computers perform divisions extremely slowly without pipelining them. Thus may Gray codes speed things up. Test Program graytest.m ~~~~~~~~~~~~~~~~~~~~~~~~ A function graytest(n) tests whether GrayPack's other ten functions grays gray2int int2gray btr2int graynext grayndcs gray2btr btr2gray int2btr graystep function correctly. The test passed when run under MATLAB 5.2 on my Mac Quadra 950 and on an iMac, and when run under MATLAB 6.5 on a Wintel PC, for n = 1:12 . See the text of graytest.m to ascertain whether the test is valid and thorough enough. As usual, this test is a bit more complicated than any of the programs tested and consequently more prone to error. Graytest runs on MATLAB 5 and later versions. Other Programs ~~~~~~~~~~~~~~ A program gc2dec.m submitted to MATLAB Central in mid 2005 by Arjun Srinivasan Rangamani does rather slower, especially when length(Br) is big, what either gray2int( btr2int(fliplr(Br)) ) or btr2int( gray2btr(fliplr(Br)) ) does. Adrian at ubicom.tudelft.nl has submitted two programs: his gray2bi is like but slower than our gray2btr; his bi2gray is like but slower than our btr2gray . The PASCAL programs in Robert W. Dornan's "The Gray Code" (Mar. 2007) posted at gain elegance from recursion at the cost of a little speed. GrayPack has no Recursive (reentrant) programs; some use a Recurrence (loop). Prof. W. Kahan, ======================================================================= Information for MATLAB Central: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Title: Manipulation of Binary Gray Codewords ~~~~~~ Description: A package "GrayPack" of MATLAB programs to manipulate ~~~~~~~~~~~~ Cyclic n-bit Binary Gray Codes and convert between two ways to represent them, one as n-bit integers for 0 < n < 54 , the other as logical bit-rows each of unbounded length n . GrayPack also includes one program to test all ten others, plus a lengthy text-file that describes the package and notes a few applications like tolerant conversions of mechanical positions to digital signals, Hamiltonian circuits of hypercubes, and exhaustive incremental explorations. Supersedes an earlier version dated 13 July 2009, File ID #15570 MATLAB Release: 5.2 (R 10) ~~~~~~~~~~~~~~~ GrayPack's Contents: Twelve files, namely ~~~~~~~~~~~~~~~~~~~~ grays.m grayndcs.m graystep.m graynext.m gray2int.m int2gray.m gray2btr.m btr2gray.m GrayCode.txt graytest.m btr2int.m int2btr.m Tags: Gray codes, goniometer, tolerant analog-to-digital conversion, ~~~~~ hypercube, Hamiltonian circuit, exhaustive incremental search.