Science in Education https://doi.org/10.53656/math2023-6-1-mir Научно-методически статии

2023/6, стр. 559 - 578

MIRROR (LEFT-RECURSIVE) GRAY CODE

Dr. Valentin Bakoev, Assoc. Prof.

”St. Cyril and St. Methodius” University of Veliko Tarnovo (Bulgaria)

Abstract. Here we consider a version of the Binary Reflected Gray Code (BRGC, or Gray code for short), called the mirror Gray code – in parallel and in comparison to the Gray code. We discuss some sources where the two codes are not distinguished and the reasons why. We present our arguments for treating the two codes as distinct, starting with a definition of the mirror Gray code and showing its main properties. Among the most important of these is the relationship between the two codes – the codewords of the mirror Gray code are “left-right mirror images” of those in the Gray code and vice versa. Other arguments we show are the differences in the algorithms for generating the codewords. We also present another approach that involves representing the codewords by integers (their serial numbers), generating and examining the two codes by using their sequences of serial numbers. For this purpose, we use the bijections that relate the pairs of combinatorial objects: binary vectors in a certain order and the corresponding integer sequences and subsets. In this way, we get different algorithms, sequences, and functions for successor and predecessor, for ranking and unranking at the mirror Gray code. We believe that this article provides at least one more perspective, as well as expands and enriches the knowledge of the Gray code.

Keywords: Gray code; mirror Gray code; lexicographic order; binary vector; codeword; generation algorithm; integer sequence; predecessor; successor; rank; unrank function

1. Introduction

The ordering of all binary vectors (words, codewords) in a Gray code is a well-known concept that has many useful properties and applications. The most important property of the ordering in a Gray code is known as minimal change, which means that every two adjacent vectors in this sequence differ by exactly one coordinate. This property applies not only to the generation of binary vectors but also to other combinatorial objects – Frank Ruskey notes “The fastest known algorithms for generating certain objects are based on Gray codes...” (Ruskey 2003, p. 115). Other applications (and relations) of the Gray code are discussed in many sources. Almost all of them associate it with the -dimensional Boolean cube (hypercube) and Hamiltonian cycles in the graph corresponding to the cube. Examples of a hypercube network with 2 processors such that each processor is connected to other  processors are given in (Rosen 2012), (Koshy 2003), (Grimaldi 2004), (Anderson 2001), etc. In (Ruskey 2003), (Rosen 2012), (Knuth 2011), (Waren 2012) examples of a measuring device with a rotating pointer and 2 sectors of its scale are given. When they are labeled by a Gray code, as opposed to their lexicographic labeling, the possibility of errors is minimized. Some historical notes and references on the French telegraph engineer Émile Baudot and his code (patented in 1874), the Bell Labs researcher Franc Gray and his “reflected binary code” (patented in 1947), the French magistrate Louis Gros and his solution to the classic toy “Chinese ring puzzle”, as well as a solution of the “Towers of Hanoi problem” etc. are given in (Knuth 2011), (Ruskey 2003). Applications of Gray code in: (1) minimization of Boolean functions via Karnaugh maps are discussed in (Garnier & Taylor 2002), (Grimaldi 2004), (Ruskey 2003), (Manev 2012); (2) databases – in (Ruskey 2003); (3) addressing microprocessors, hashing algorithms, distributed systems, channel noise detection and correction – in (Bunder et al. 2008); (4) Algebraic coding theory – in (MacWilliams & Sloane 1978), (Suparta 2006), and others. So it is not surprising that dozens of different types of Gray codes have been invented and studied – see the surveys (Savage 1997) and especially the latter (Mütze 2022).

Here we consider another type of Gray code, which is closely related to the Binary Reflected Gray Code (BRGC), also called a standard Gray code, or Gray code for short. It is obtained by reflection of the internal order of the bits in the codewords of the Gray code. In (Knuth 2011), in Section 7.1.3. (Bit reversal, p. 144), Knuth writes “… let's change  = (6362 … 10)2 to its left-right mirror image,  = (01 … 6263)2” and that is why we call it mirror Gray code. We present our arguments regarding the distinction between the two codes and consider this code to be different from the Gray code. We use another approach that involves representing the codewords by integers (their serial numbers), generation and examining the two codes by using their sequences of serial numbers and performing simple operations on them. For this purpose, we use the bijections that relate the pairs of combinatorial objects: binary vectors in a certain ordering and their corresponding integer sequences and subsets.In this way, we get different algorithms, sequences, and functions for successor and predecessor, for ranking and unranking at the mirror Gray code. This article summarizes the main results of (Bakoev 2023a) and (Bakoev 2023b), which you can refer to for details.

2. Basic notions

The set of all -dimensional binary vectors (words) is known as an -dimensional Boolean cube (hypercube). It is defined as the Cartesian -th power of the set {0,1} which is {0,1} = {(1, 2, … , )| ∈ {0,1}, for  = 1, 2, … , }. Let  = (1, 2, … , ) and  = (1, 2, … , ) be arbitrary vectors of {0,1}. A serial number of the vector  is the non-negative integer which is the decimal representation of the binary number  ,  , … ,  formed by the coordinates of . A (Hamming) weight of  is the non-negative integer () equal to the number of non-zero coordinates of . Since the coordinates of  are zeros and ones, A Hamming distance between  and  is the non-negative integer where ⊕ is the Boolean function eXclusive OR (XOR). So (,  ) means the number of coordinates in which  and  differ. When (, ) = 1 we call  and  adjacent vectors, or more precisely adjacent in the th coordinate, if they differ only on it. When (, ) =  we call  and  opposite. We say that  lexicographically precedes  and write  ≤  if  =  or there exists an integer , 1 ≤  ≤ , such that  < , and  = , for all  < . The relation ≤ defined on {0,1} × {0,1} with (, ) ∈ ≤ if  ≤  is called a lexicographic precedence relation. It is reflexive, strongly antisymmetric and transitive and so ≤ is a total order relation on the vectors of the -dimensional Boolean cube. The ordering determined by ≤ is called lexicographic.

Let  be a positive integer,  = {1, 2, … , } be a given set, and  ⊆ . The vector  = (1, 2 , … , ) ∈{0,1} defined as:  = 0, when  ∉ X, or  = 1, when  ∈ X, for  = 1, 2, … , , is called the characteristic vector of the subset . A well-known theorem states that if  is an -element set, the function

:  → {0,1},

defined by the notion of a characteristic vector is a bijection.

Many authors denote by  the sequence of all binary vectors of {0,1} in a Gray code and define it recursively:

(1)

where 0−1 denotes all vectors of {0,1}−1 in a Gray code, prefixed by 0, and denotes all vectors of {0,1}−1 in a Gray code, taken in reversed order and prefixed by 1 (Ruskey 2003), (Kreher & Stinson 1999). Knuth uses a similar definition, starting from  = 0 and the empty word (Knuth 2011). The following inductive and constructive definition is more useful for us.

Definition 1. 1) The vectors (0) and (1) of {0,1}1 are ordered in a Gray code.

2) Let 0, 1, … , 2−1−1 be the sequence of all vectors of {0,1}−1, ordered in a Gray code.

3) To obtain the vectors of {0,1} in Gray code, we perform three steps. First, we prefix with 0 all vectors 0, 1, … , 2−1−1 of {0,1}−1 in a Gray code. Then, we take the same sequence 0, 1, … , 2−1−1 a second time and reverse the order of its vectors, i.e. we take its reflection 2−1−1, … , 1 , 0 and then we prefix each of its vectors with 1. Third, we concatenate the two sequences, and the result

(0, 0),(0, 1), … ,(0, 2−1−1), (1, 2−1−1), … , (1, 1), (1, 0 )

contains all vectors of {0,1} ordered in a Gray code.

Both definitions show why the Gray code is called reflected and cyclic – notice that the first and last vectors in these sequences are also adjacent.

Here we note that if we neglect the reflection in point 3) of Definition 1, we shall obtain the vectors of {0,1}in lexicographic order. It is well known that when the vectors of {0,1} are in lexicographic order, the sequence of their serial numbers is: 0, 1, 2, … , 2 − 1, and the function that relates them is a bijection.

Besides by this definition, the vectors of {0,1} can be generated in a Gray code by using the so-called transition sequence. In accordance with the position of the new-coordinate expansion in Definition 1, we number the coordinates of the vectors of {0,1} from right to left, i.e.  = (, −1, … , 2, 1).

Definition 2. Let 0, 1, … , 2−1 be the vectors of {0,1} ordered in a Gray code. The sequence of integers: () = 1, 2, … , 2−1, where  ∈ {1, 2, … , }, for  = 1, 2, … , 2 − 1, is defined as follows: the th term  denotes the number of the coordinate in the serial vector −1 that must be inverted to obtain the next vector , for  = 1, 2, … , 2 − 1. () is called a transition sequence.

From the last two definitions it follows that () is a symmetric sequence with respect to its middle term, for = 1, 2, 3, … We can define () with (1) = 1, and () = ( − 1), , ( − 1). Hence () is a palindrome of integers, exactly a palindrome of palindromes if we exclude the middle term. Another way to obtain () is given by the following theorem, which is little known.

Theorem 1. Let the vectors of {0,1} be in lexicographic order. Then the sequence of Hamming distances between the pairs of adjacent vectors, i.e.  (−1, ), for  = 1, 2, … , 2 − 1, coincides with the transition sequence () of the Gray code.

More details about the transition sequence and its varieties can be found in, (Knuth 2011), (Gulliver et al. 1999), (Bakoev 2023a).

Table 1 illustrates the statement of Theorem 1, and Table 2 shows how the vectors of {0,1} in a Gray code are obtained via the transitions sequence. The sequence denoted by # in Table 1 is A001477 in the OEIS1. The sequence denoted by # in Table 2 is A003188, and the transition sequence is A001511. The tables also illustrate the bijection between the (serial) numbers in the left columns of the two tables (sequences A001477 and A003188) and the vectors of {0,1} in the corresponding row. The aforementioned bijection between {0,1} and the subsets of an -element set (via the notion of a characteristic vector) defines an ordering of the subsets corresponding to the ordering of the vectors. So, we explore the combinatorial objects: integer sequences, binary vectors, and subsets in a certain order through these bijections that relate each pair of them.

As we have seen, the generation of the Gray code for {0,1} can be done by using formula (1), Definition 1, or by the transition sequence. This can be done through the predecessor and successor functions, through ranking and unranking functions (Ruskey 2003), (Kreher & Stinson 1999), (Knuth 2011), and others.

3. About mirror (left-recursive) Gray code

After an extensive search, we found 3 sources that refer to mirror (lefyrecursive) Gray code. In (Nijenhuis & Wilf 1978), the authors define Gray code recursively in relation to Hamiltonian walks in the Boolean cube and the generation of the subsets by minimal change. For a given set/subset , || = , the authors formulate and prove the rule of succession: “If  is even, then  = 1; if  is odd, then  is the index of the coordinate which follows the first “1” bit of ”. Actually, the authors define, comment and use only the mirror Gray code.

In (Lipski 1988) an inductive definition of the Gray code is given, where the expansion of the codewords with a new coordinate is done on the right-hand side of the vectors (as in Definition 1). Lipski proposes Algorithm 1.13 which generates all subsets of a set of  elements ordered in a Gray code. In fact, the algorithm uses the “rule of succession” and successively performs integer divisions of the integers 0, 1, … , 2 − 1 to compute the coordinate number that must be inverted to obtain the new codeword. This corresponds to numbering the codeword coordinates (bits) from right to left (i.e.  , −1, … , 1), but the algorithm inverts the values (0 or 1) of an array whose elements are numbered in reverse, with 1, 2, … ,  (Lipski 1988, p. 31, Fig. 1.6). So the algorithm generates the mirror Gray code. Lipski does not notice to this fact and does not distinguish between the two codes.

There are similar considerations in the third source (Ruskey 2003). Ruskey first defines recursively and considers binary reflected Gray code (BRGC) in relation to a Hamiltonian cycle on the Boolean cube and the Towers of Hanoi problem. Ruskey defines the transition sequence and considers the generation of this Gray code by it. The ranking and unranking functions for BRGC are also discussed. But in the next section “Recursive generation of BRGC”, by formula (5.3), Ruskey gives a recursive definition of the mirror Gray code. Two recursive algorithms built on this formula are proposed: Algorithm 5.2 (indirect) and Algorithm 5.3 (direct). However, Ruskey does not distinguish between the two codes, possibly because the results of running Algorithm 5.1 or Algorithm 5.2 are not shown.

In (Suparta 2006) some equivalences are considered over the set of “all cyclic minimal-change -ary Gray codes of length ”. Following this classification, Gray code and mirror Gray code are equivalent because one of them can be obtained from the other by permutation of its columns, i.e. by permutation of its coordinates.

After all, the main question follows: Should we distinguish between Gray code and Gray mirror code, and is it even worth considering Gray mirror code separately? Our opinion is “yes” and we argue this view, presenting more arguments in the remainder of this article.

4. Mirror (left-recursive) Gray code

The following definition is analogous to Definition 1, the difference being in the place of expansion with a new coordinate, and we start with the case  = 0.

Definition 3. 1) If  = 0, then {0,1}0 = {()}0, i.e. it contains only the empty vector – an analog of the empty word. If  = 1, the vectors (0) and (1) of {0,1}1 are ordered in a mirror (left-recurcive) Gray code, simply mirror Gray code.

2) Let 0, 1, … , 2−1−1 be the sequence of all vectors of { 0,1}−1, ordered in a mirror Gray code.

3) We perform three steps. First, we append 0 at the end of all vectors 0, 1, … , 2−1−1 of {0,1}−1 in mirror Gray code. Second, we take the reflection 2−1−1, … , 1, 0 ofthe same sequence and then append 1 at the end of each of its vectors. Third, we concatenate the two sequences, and the result

(0, 0), (1, 0), … ,(2 −1−1 , 0), (2−1−1, 1), … , (1, 1), (0, 1)

contains all vectors of {0,1} ordered in a mirror Gray code.

The following statements follow from definitions 1 and 3. They can be proven rigorously by induction on , following both definitions.

Theorem 2. The mirror Gray code is reflected and cyclic, as is the Gray code.

Theorem 3. (Relationship between Gray code and mirror Gray code) The mirror Gray code can be obtained from the Gray code and vice versa, by reflecting the internal order (i.e. the bits’ order) of the vectors in the corresponding code.

We can supplement and clarify the last statement by defining the function (or operation) to reflect (or reverse) the coordinates of a vector. We denote it by  and define  ∶ {0,1}n → {0,1}n, for an arbitrary vector  = (1, 2, … ,  ), () =  = (, … , 2, 1). Thus the coordinates of  are a mirror image of those of  and vice versa. Obviously () = (()) =  and so  is an involution.

Corollary 1. (Fixed points of transformation of Gray code to mirror Gray code) The vectors that occupy the same positions and match in Gray code and mirror Gray code are the palindromes. Hence their number is

Corollary 2. Let the coordinates of the vectors of the -dimensional Boolean cube be numbered 1, 2, … , , i.e. from left to right. Then the sequence () given by Definition 2 is a transition sequence for the mirror Gray code.

Theorem 4. Let the vectors of {0,1}n be obtained according to Definition 3. Then:

a) The sequence () of serial numbers of the vectors is defined recursively as:

(2)

Thus () is the result of concatenating two sequences: (1) the terms of ( − 1) multiplied by 2 and (2) 2. ( − 1)+ 1 which means that each term of the reversed sequence ( − 1) is multiplied by 2 and increased by 1.

b) The sequence () of vector weights is defined recursively as:

(3)

Similarly, () is the result of concatenating two sequences: ( − 1) and  ( − 1) + 1 – each of the terms of the reversed sequence is incremented by 1.

Proof. We will prove the statements of the theorem by induction on .

1) For  = 0 and  = 1 both statements are obvious.

2) We assume that for arbitrary positive integer  the formulas (2) and (3) are valid, respectively for the sequences () and ().

3) We consider the vectors of {0,1}k+1 in mirror Gray code obtained according to Definition 3.

a) The first half of {0,1}k+1 vectors are the vectors of {0,1}k expanded with a new coordinate 0 at the end of each of them. Thus, their serial numbers are obtained from the corresponding serial numbers of the vectors in () multiplied by 2. The second half of vectors of {0,1}k+1 are obtained by reflection the outer order of the vectors of {0,1}k and then 1 is added at the end of each of them. Thus, their serial numbers are obtained from those of the reflected sequence (), multiplied by 2 (due to the addition of a new coordinate at the end) and increased by one, since the new coordinate is 1. Therefore, formula (2) is also true for  + 1.

b) The assertion about weights is proved analogously. In the first half of {0,1}k+1the vectors remain the same as in () because all vectors of {0,1}k are expanded with a new coordinate 0. Analogously, the second half of the vectors of {0,1}+1 are obtained by incrementing the terms of the reflected sequence () by 1. Therefore, formula (3) is also true for  + 1.

Therefore, the statements of the theorem are true for all positive integers . □

Let us clarify formula (2). In fact 2.  ( − 1) + 1 means that the resulting sequence 2. ( − 1) of (1) is taken a second time, reversed and all its terms are incremented by 1. Hence 2. ( − 1) + 1 = (2. ( − 1)) + 1 and then () is a concatenation of 2. ( − 1), and (2. ( − 1)) + 1, when  > 0. So we do not need to multiply the terms of 2. ( − 1) by 2 twice. Thus, the first half of () contains even integers, and the second half contains odd integers.

These notes and the statement of Theorem 4 are illustrated in Figure 1 for  = 1, 2, 3. We note that the sequence () is the same for the Gray code and the mirror Gray code. The entry of () in the OEIS is A005811.

5. Generation of the mirror Gray code

There are several ways to generate mirror Gray code. We have already commented on the byte-wise (in an array) generation of the mirror Gray code by Algorithm 1.13 in (Lipski 1988) and Algorithms 5.1 and 5.2 in (Ruskey 2003). The same type of generation can be done according to Corollary 2 – by using the transition sequence (), in two ways. The first way is to generate the entire transition sequence in an array, following Definition 2 and the notes after it. The following simple function does this, assuming that the array t is suitably defined beforehand.

The second way is to compute the terms of () one after the other using Theorem 1 (see Table 1). This involves computing the weight of a binary vector (i.e. computer word) since (,  +1) = ( ⊕ +1). This can be done via the __popcnt, or via the __builtin_popcount function (for the GCC and Clang compilers), for example:

In the first way, the sequence () is generated with time complexity (2) – exponential concerning the size of the input but linear concerning the size of the output. Thus, one term of () is computed in constant time. The second way requires (log2) time, which is the running time of the popcnt function, and  is the size of the computer word that stores . The transition sequence can be used to generate both a Gray code and a mirror Gray code, both byte-wise and bitwise.

5.1. Generating the sequence of the serial numbers of the vectors in mirror Gray code

Here we consider two algorithms that generate the sequence of serial numbers () of the vectors in the mirror Gray code. The first algorithm, called Gen_MGC_Seq, is based on Theorem 4 and the remarks after it that determine its correctness. It sequentially generates the sequences (1), (2), … , () in the onedimensional array seq with 2 elements, predefined according to a suitable maximum value of , so that memory can store them. Here is its code.

When  ≤ 32 and there is enough memory (static or dynamic) to hold the array seq, then 32-bit (or 16-bit) computer words can be used to represent the elements of the sequence (). The complexity of the algorithm is easily calculated. The first nested loop performs a total of (2 + 4 + ⋯ + 2−1) = (2) operations. The second nested loop also performs(2) operations. The time complexity of the algorithm is therefore (2) and so is the space complexity since it uses an array of 2 integers. So the average cost of computing an arbitrary element of () is constant, i.e. Gen_MGC_Seq is a CAT-algorithm (CAT stands for Constant Amortized Time (Ruskey 2003)).

The second algorithm is called Mirror algorithm G and it is a modification of the well-known Algorithm G given in (Knuth 2011). Algorithm G is similar to Algorithm 1.13 (Lipski 1988) and also uses the “rule of succession”. But it maintains a parity check variable that reverses its value after each subsequent codeword is generated. In (Knuth 2011) the bits are numbered  − 1, … , 1, 0, the algorithm is described in words and it is suitable for byte-wise and bitwise implementations. In our bitwise version of Algorithm G, all codewords are sequentially received in the integer c_v, which stands for “current vector”, the binary representation of that integer. Briefly, the algorithm starts with the zero vector whose parity is 0. If at the current step, the parity is 0, the rightmost (the least significant) bit of c_v is flipped. Otherwise, the algorithm looks for the bit with the least significant 1 in c_v, i.e. the first bit with value 1 from right to left. If the number of this bit  is equal to  − 1, the algorithm terminates, otherwise it reverses the value of the ( + 1)th bit. Each time a new integer is received, the value of the parity variable is flipped.

We reverse these rules to obtain the Mirror algorithm G: (1) if the parity is 0, the ( − 1)th bit is flipped, or (2) we look for the most significant bit that is 1 to flip the value of the bit to its right if its number j is ≥ 0. In the following code we use the vector (1,0,0, … ,0), i.e. 1, followed with ( − 1) zeros (which is 2−1) as a mask – this is the variable m.

Lipski proves the correctness of Algorithm 1.13 and notes that the average number of operations to generate the next codeword is constant. Therefore, this applies to both Algorithm G and Mirror algorithm G – they are CAT-algorithms.

5.2. The sequence A362160 in the OEIS

The results of running the Gen_MGC_Seq algorithm were used to create the A362160 sequence in the OEIS (the Mirror algorithm G gives the same results). The first of its terms can be seen in Figure 1, but they are not enough. The terms of () are generated for  = 0, 1, … , 15 and available via the section LINKS in the description of A362160. The sequences (0), (1) , … , (5) form the rows of an irregular triangle denoted by (, ) – see section EXAMPLE of A362160. The first 5 rows of (, ) are shown in Table 3.

We note that A362160 does not contain only the terms of (), even for some sufficiently large . It is a concatenation of the rows of (, ) and so starts with:

0, 0, 1, 0, 2, 3, 1, 0, 4, 6, 2, 3, 7, 5, 1, 0, 8, 12, 4, 6, 14, 10, 2, 3, 11, 15, 7, 5, …

Representing the results by (, ) allows one to notice more properties about (). For example:

 The zero column is A000004 in the OEIS is named “The zero sequence”.

The last term of each row is 1, the sequence of the last terms is A000012 in the OEIS: “The simplest sequence of positive numbers: the all 1's sequence”.

 Row  is a permutation of the numbers 0, 1, … , 2 − 1 and so their sum is 2−1.(2– 1). The numbers of (, ) taken for  = 0, 1, 2, …, form A006516.

 The numbers in column 1 (as well as columns 3, 7, etc.) form the sequence of powers of 2, which is A000079, and so on.

Algorithm Gen_MGC_Seq and its analogousversion for the Gray code (Bakoev 2023a) are representatives of algorithms that generate the sequences of integers – the serial numbers of the vectors in a certain ordering. The applications, advantages and disadvantages of this approach are discussed in (Bakoev 2023b).

The relationships between the binary vectors of {0,1}3 in these two orderings, the corresponding serial numbers, and the subsets  ⊆  = {, , } are illustrated in Table 4 and Table 5.

5.3. The function to reflect the coordinates of a vector

Recall Theorem 3 about the relationship between Gray code and mirror Gray code by the operation (function)  to reflect (or reverse) the coordinates of a vector. We can use this relationship in several ways:

 It can be applied sequentially to each vector of one code to obtain the corresponding vector of the other code, and so any algorithm that generates one code can generate the other code.

 It can be incorporated into the algorithm itself so that it generates the codewords of the corresponding code (without the need to reverse each one), as we have shown through Algorithm G and Mirror algorithm G.

 The difference between the ways of numbering the array elements and the bits of the binary vectors, as in Algorithm 1.13 (Lipski 1988). Also, when the transition sequence () is applied to an array, the mirror Gray code is obtained, and when applied to binary vectors, the Gray code is obtained. But if we reverse the ( − )th coordinate or index, instead of the th (where  is the serial term of ()), this swaps the two resulting codes.

The implementation of the operation  depends on the representation of codewords. At the byte-wise one, reversing the first  elements in the array a is simple and needs Θ() operations. The corresponding bitwise approach, which reflects the least significant  bits in the binary representation of the number , looks like this:

This function also performs () operations. More efficient implementations (with () operations) of the bit reflect function can be seen in (Knuth 2011), (Warren 2013), (Arndt 2011), (Anderson S.2005), etc. But the reader should be careful with them, because they require more knowledge and experience.

6. The four basic functions for the mirror Gray code

Apart trough the algorithms under consideration, the mirror Gray code (as well as the Gray code) can be obtained by the functions for successor (next) and predecessor (previous), for ranking and unranking, etc., as we will see here. They

are related as it is shown in Figure 2.

The successor and predecessor functions are used to generate combinatorial objects sequentially, one after the other, in straight or reverse order. Ruskey notes that “Ranking (and unranking) is generally only possible for some of the elementary combinatorial objects.” (Ruskey 2003). These four functions for the Gray code are well-known, they can be found in most of the books on Combinatorial algorithms cited here. Using them, the function that reverses bits and the relations in Figure 2, we can easily create such functions for the mirror Gray code. When the sequence () is generated, the predecessor and successor functions are trivial. Therefore, we will not consider these ways of obtaining them. Instead, we will derive the four basic functions for the sequence () and its terms.

6.1. The successor and predecessor functions for mirror Gray code

We recall the “rule of succession” again, which is implemented in the main loop of Mirror algorithm G and so we only need to extract it. When an arbitrary term  of () is given, its parity is unknown and must first be computed. This can be done via the __builtin_parity function (for the GCC and Clang compilers), or via the __popcnt fuction to compute the weight of  and then check its rightmost bit. If  = 1, then it is the last member of ()and has no successor. So the following function returns −1 as such indicator, and its second parameter is .

As for the predecessor function, we simply look at the changes made to the successor function and reverse them. If  has an odd weight, then its last bit has been flipped and we flip it again to restore its previous value. Otherwise, the bit to the right of the most significant 1 is inverted. We invert this bit again and get the previous vector. Similarly, the zero vector (the number 0) is first in ()and has no predecessor – the function again returns −1 to indicate this. Here is its code.

Let us consider the time complexity of the last two algorithms. The __popcnt function runs in (log2 ) time (the same as __builtin_parity), where  ∈ {8, 16, 32, 64}is the size of the computer word that stores . The while loop runs in () time and hence the time complexity of these algorithms is (log2) + () = () for these values of  – it is best to be the smallest integer, such that 2 > .

Obviously, only minimal changes to the two algorithms are needed to obtain their respective algorithms for the Gray code. Also, their byte-wise realizations for both codes are simple and easy.

6.2. The rank and unrank functions for mirror Gray code

These functions for the Gray code can be found in many sources, in some of them they have been proved. For example, formulas (9) and(10) in (Knuth 2011, p. 284), Lemma 2.3 in (Kreher & Stinson 1999, p. 40), Lemma 5.1 and Algorithm 5.1 in (Ruskey 2003, p. 119), etc. They have very efficient implementations.It is important to note that ranking the codewords of a Gray code actually means converting that order of binary vectors to their lexicographic order, and vice versa for the unrank function. So we can use these functions for the Gray code, the bijective relation between the Gray code and mirror Gray code stated by Theorem 3, and the function  (implemented by the function reverse_bits). Instead, we apply another approach to derive these functions using the recursive formula (2) for the sequence (), explanations after it and Algorithm Gen_MGC_Seq.

Let  be any term of (), 0 ≤  ≤ 2 − 1. We want to compute its rank, i.e. which place (in order) it occupies in (). So, if the -bit binary representation of  is the vector , we want to compute its rank – the place that occupies  in the mirror Gray code. Let us denote this place by . So, if (, ) = , we seek , 0 ≤  ≤ 2  − 1, as a function of  and . We recall that the left half of the terms of () are even numbers, which are the doubled terms of ( − 1). The terms of the right half of() are odd numbers which are the reflected terms of the left half and each of them is increased by 1. Reflection also means central symmetry about an imaginary point in the middle of the sequence (). Thus the element with number , 0 ≤  ≤ 2 − 1, in one half corresponds to the element with number 2 − 1 −  in the other half. We reason like this:

 If  is an even number, it is the result of the “filling the left half”step in the code of Algorithm Gen_MGC_Seq. First, we check if  = 0 and if “yes”, its serial number is  = 0. Otherwise,  = 2 > 0 and element  has the same number  in the sequence ( − 1), i.e.  = (, ) = 2 = 2( − 1, ).

Therefore (, ) = ( − 1, /2).

 If  is an odd number,  is the result of the the “filling the right half” step in the code of Algorithm Gen_MGC_Seq. This means that  is obtained by reflecting the number  − 1 from the left half of () then and adding 1. Let  occupies the place with number  in the right half of (), i.e.  = (, ), where 2−1 ≤  ≤ 2 − 1. Since  is obtained by adding 1 to the number  − 1 whose serial number in () is 2 − 1 − , i.e.  = (, 2 − 1 −  ) + 1 = (, ), it follows that (, ) = 2 − 1 − (,  − 1 ).But now the number  − 1 is even, and for (,  − 1) we can apply the inference from the first case, which associates it with the sequence ( − 1). Thus we save one recursive step and finally get:

(, )= 2 − 1 − (,  − 1) = 2 − 1 − ( − 1, ( − 1)/2).

Therefore, the recursive definition of  by the parameters  and  is:

(4)

We propose the code of two functions – recursive and non-recursive, which implement formula (4). Replacing recursion with iteration is not so simple. When t is an odd number, the result is formed in the reverse step of the recursion. This is why the non-recursive function uses a stack represented by the st array. The while loop fills the stack with the required values and then the final value is computed by the for loop.

Formula (4) and the arguments in its derivation determine the correctness of these ranking algorithms. Their time complexity is of type () since the first function executes at most  + 1 recursive calls, the same applies to the while loop and the for loop executions in the second function.

The function unrank must compute the term that occupies the th consecutive position in (), for given integers  and , 0 ≤  ≤ 2 − 1. The derivation of the unrank function is analogous to that of the rank function.

1) If  < 2−1, then  is in the left half of (). First, we check if  = 0; if “yes”, then  is the zero term of (), i.e.  = 0. Otherwise,  = 2 > 0 and the element  occupies position with the number  in ( − 1), the same as  in (). Then  = (, ) and  = ( − 1, ) and therefore  = 2 = 2( − 1, ).

2) If  ≥ 2−1, then  is in the right half of (). Then  is obtained by reflecting the number  − 1 from the left half of () and adding 1. The number  − 1 occupies a position with the number 2 − 1 −  in the left half of () and therefore  = (, ) = (, 2 − 1 − ) + 1. Also, the number  − 1 is even, and then  − 1 = 2 = (, 2 − 1 − ). Then  − 1 and  the occupy the same position – with number 2 − 1 −  in the sequences () and ( − 1), respectively. Since  < 2−1 we save one recursive step using the first case, i.e.  = ( − 1, 2 − 1 − ). Then we have  − 1 = 2( − 1, 2  − 1 − ), whence  = 2( − 1, 2 − 1 − ) + 1.

Thus we get the recursive formula:

(5)

We propose the code of two functions – recursive and non-recursive, which implement formula (5). Their parameters and explanations are the same as for the rank function. The same is valid for their correctness and time complexity.

7. Conclusions

Here we considered the mirror Gray code, comparing it to the Gray code. We have examined and shown that the algorithms for their generation are different, and the serial number sequences of the corresponding codewords, the corresponding subsets generated by them, and their four basic functions are also different.

Finally, whether readers continue to think that both codes are the same or not, we hope that they have at least looked at it from a different perspective and gained a deeper knowledge of the Gray code.

Acknowledgments

This work was supported in part bythe Bulgarian National Science Fund under Contract No KP-06-H62/2-2022.

NOTES

1. The On-line Encyclopedia of Integer Sequences. https://oeis.org/

REFERENCES

ANDERSON, J., 2001. Discrete Mathematics with Combinatorics, New Jersey: Prentice-Hall.

ANDERSON, S., Bit Twiddling Hacks. [viewed 26 Nov. 2023]. Available from: https://graphics.stanford.edu/~seander/bithacks.html

ARNDT, J., 2011. Matters Computational: Ideas, Algorithms, Source Code, Springer.

BAKOEV, V., 2023a. Generating sets in lexicographic order and with minimal change, “St. Cyril and St. Methodius” University Publishing House, Veliko Tarnovo (In Bulgarian, БАКОЕВ, В., Генериране на множества в лексикографска наредба и чрез минимално изменение, Университетско издателство „Св. св. Кирил и Методий“, В. Търново, 2023).

BAKOEV, V., 2023b. Binary vectors: orderings, integer sequences, and generating of sets, “St. Cyril and St. Methodius” University Publishing House, Veliko Tarnovo (In Bulgarian, БАКОЕВ, В., Двоични вектори: наредби, числови редици и генериране на множества, Университетско издателство „Св. св. Кирил и Методий“, В. Търново, 2023).

GARNIER, R., TAYLOR, J., 2002. Discrete Mathematics for New Technology, 2nd ed. IOP Publishing Ltd.

GRIMALDI, R.,2004. Discrete and Combinatorial Mathematics. An Applied Introduction, 5th ed., Addison-Wesley.

GULLIVER, T.A., BHARGAVA, V.K., STEIN, J.M., 1999. Q-ary Gray codes and weight distributions, Applied Mathematics and Computation, no. 103, pp. 97 – 109.

KNUTH, D., 2011. The art of computer programming, Volume 4A: Combinatorial Algorithms, Part 1, Addison-Wesley.

KOSHY, T., 2003. Discrete Mathematics with Applications, Academic Press.

KREHER, D., STINSON, D., 1999. Combinatorial algorithms: generation, enumeration and search, CRC Press.

LIPSKI, W., Combinatorics for programmers, Mir, Moscow (In Russian, ЛИПСКИЙ, В., 1988. Комбинаторика для программистов, Мир, Москва).

MACWILLIAMS, F.J., SLOANE, N.J.A., 1978. The Theory of ErrorCorrecting Codes, Amsterdam: North-Holland.

MANEV, K., 2012. Introduction to discrete mathematics, 5th ed., KLMN, Sofia (МАНЕВ, К., 2012. Увод в дискретната математика, V изд., КЛМН, София)

MÜUTZE, T., 2022. Combinatorial Gray Codes – An Updated Survey, [viewed 26 Nov. 2023]. Available from: https://arxiv.org/abs/2202.01280

NIJENHUIS, A., WILF, H., 1978. Combinatorial Algorithms for Computers and Calculators, (1st ed., 1975), 2nd ed., Academic Press.

ROSEN, K., 2012. Discrete Mathematics and its Applications, 7th edition, McGraw-Hill.

RUSKEY, F., 2003. Combinatorial Generation. Working Version (1j-CSC 425/ 520), [viewed 26 Nov. 2023]. Available from:

http://page.math.tu-berlin.de/~felsner/SemWS17-18/Ruskey-Comb

Gen.pdf

SAVAGE, C., 1997. A Survey of Combinatorial Gray Codes, SIAM Review, vol. 39, no. 4, pp. 605 – 629.

SUPARTA, I.N., 2006. Counting sequences, Gray codes and Lexicodes, Dissertation at Delft University of Technology. [viewed 26 Nov. 2023]. Available from: https://theses.eurasip.org/theses/113/counting-sequencesgray-codes-and-lexicodes/download/

WARREN, H.S.Jr., 2013. Hacker’s Delight, 2nd Ed., Addison-Wesley.

 Dr. Valentin Bakoev, Assoc. Prof.

ORCID iD: 0000-0003-2503-5325
“St. Cyril and St. Methodius” University
Veliko Tarnovo, Bulgaria
E-mail: v.bakoev@ts.uni-vt.bg