C Program to Convert Binary to Gray Code using Recursion

In this blog post, we will see how to write C Program to Convert Binary to Gray Code using Recursion with detailed explanation.

Before we start let’s understand few basic.

What is Binary Code?

Binary code is a system of representing information using only two digits: 0 and 1. It’s the fundamental language computers use to store and process data. Each digit in a binary code is called a “bit,” and a sequence of bits represents information.

Example: Representing Numbers in Binary

Let’s take the decimal number 13 and represent it in binary.

Decimal to Binary Conversion:

• Start with the number 13.
• Repeatedly divide the number by 2 and note the remainder each time.
• Keep dividing until the quotient is 0.

   13 ÷ 2 = 6 with a remainder of 1
    6 ÷ 2 = 3 with a remainder of 0
    3 ÷ 2 = 1 with a remainder of 1
    1 ÷ 2 = 0 with a remainder of 1

• Now, read the remainders in reverse order: 1101.

Binary Representation:

• The binary representation of the decimal number 13 is 1101.

So, in binary code, 13 is represented as 1101. Each digit in the binary sequence corresponds to a power of 2, where the rightmost bit is 2^0, the next is 2^1, and so on. In this example:

• 1 * 2^3 = 1 * 8 = 8
• 1 * 2^2 = 1 * 4 = 4
• 0 * 2^1 = 0 * 2 = 0
• 1 * 2^0 = 1 * 1 = 1

Adding these together: 8 + 4 + 0 + 1 = 13, which matches the original decimal number.

What is Gray Code?

Gray code also known as reflected binary code, named after Frank Gray, is a binary numeral system where two consecutive numbers differ in only one bit. This is in contrast to traditional binary code, where changing one digit may alter multiple bits. Gray code is often used in applications such as rotary encoders and error correction.

Example of Gray Code:

Let’s consider a 3-bit Gray code sequence:

Binary to Gray Conversion:

• Start with a regular binary sequence from 0 to 7:

000 (Decimal 0)
001 (Decimal 1)
010 (Decimal 2)
011 (Decimal 3)
100 (Decimal 4)
101 (Decimal 5)
110 (Decimal 6)
111 (Decimal 7)

• The Gray code is obtained by exclusive OR (XOR) of each bit with its adjacent bit.
• The resulting sequence is the Gray code for 3-bit numbers.

000
001  (XOR with previous: 000)
011  (XOR with previous: 001)
010  (XOR with previous: 011)
110  (XOR with previous: 010)
111  (XOR with previous: 110)
101  (XOR with previous: 111)
100  (XOR with previous: 101)

The decimal equivalents of the Gray code are as follows:

000 (Decimal 0)
001 (Decimal 1)
011 (Decimal 2)
010 (Decimal 3)
110 (Decimal 4)
111 (Decimal 5)
101 (Decimal 6)
100 (Decimal 7)

Decimal Representation:

• In decimal, the Gray code sequence corresponds to: 0, 1, 3, 2, 6, 7, 5, 4.

Observations:

• Notice that in the Gray code sequence, consecutive numbers differ by only one bit change.
• This property helps in reducing errors during transitions in digital systems.

Decimal to Gray Conversion:

• Converting from decimal to Gray code involves XORing consecutive decimal values.

   Decimal:  0   1   2   3   4   5   6   7
   Gray:    0   1   3   2   6   7   5   4

In this example, Gray code provides a smooth transition between consecutive numbers, making it advantageous in applications where minimizing errors during transitions is crucial.

Convert Binary to Gray Code

Let’s see how to convert Binary to Gray Code.

Algorithm to Convert Binary to Gray Code:

1. Initialization: Start with the given binary number.
2. MSB (Most Significant Bit): The leftmost bit (MSB) of the Gray code remains the same as the MSB of the binary code.
3. Bitwise XOR Operation:Perform a bitwise XOR operation between each pair of adjacent bits in the binary code.The result becomes the corresponding bit in the Gray code.
4. Repeat for All Bits:Continue the XOR operation for each pair of adjacent bits in the binary code, moving from left to right.
5. Final Gray Code:The resulting sequence of XORed bits forms the Gray code representation.

Example:
Let’s convert the binary number 1101 to Gray code:

1. Initialization: Binary: 1101
2. MSB: The leftmost bit (MSB) remains the same: 1
3. Bitwise XOR Operation: XOR operation on adjacent bits: 1 ⊕ 1 = 0, 1 ⊕ 0 = 1, 0 ⊕ 1 = 1.
4. Repeat for All Bits: Continue the XOR operation for each pair of adjacent bits: 1101 → 1011
5. Final Gray Code:The Gray code representation of the binary number 1101 is 1011.

So, the algorithm involves starting with the MSB, performing a bitwise XOR operation between each pair of adjacent bits, and obtaining the Gray code representation. This process ensures that consecutive numbers in Gray code differ by only one bit.

To write a C Program to Convert Binary to Gray Code using Recursion you can follow this algorithm and corresponding pseudo code.

Algorithm:

1. Input:
   • Take a binary number as input. A binary number is a sequence of 0s and 1s.
2. Initialize:
   • Start with the leftmost bit (most significant bit) of the binary number.
3. Base Case:
   • If there is only one bit remaining, set the corresponding bit in the Gray code to the same value as the remaining bit.
4. Recursive Case:
   • For each pair of adjacent bits in the binary number, perform the following steps:
     • Recursively convert the remaining bits (excluding the current bit).
     • Perform XOR (exclusive OR) operation between the current bit and the next bit, and set the result as the corresponding bit in the Gray code.
5. Repeat:
   • Continue the process for each pair of adjacent bits until the last bit is reached.
6. Output:
   • The resulting sequence of bits after the recursive process represents the Gray code.

C Program to Convert Binary to Gray Code using Recursion

#include <stdio.h>

// Function to perform XOR operation
int xorOperation(int bit1, int bit2) {
    return (bit1 ^ bit2);
}

// Function to convert binary to Gray code using recursion
void binaryToGray(int binary[], int n, int gray[], int i) {
    // Base case: if only one bit is left
    if (i == n - 1) {
        gray[i] = binary[i];
        return;
    }

    // Recursive case: convert the rest of the bits
    binaryToGray(binary, n, gray, i + 1);

    // Corrected XOR operation between consecutive bits
    gray[i] = xorOperation(binary[i], gray[i + 1]);
}

// Function to display an array
void displayArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
    }
}

int main() {
    // Example binary number: 1101
    int binary[] = {1, 1, 0, 1};
    int n = sizeof(binary) / sizeof(binary[0]);

    // Initialize an array to store the Gray code
    int gray[n];

    // Convert binary to Gray code using recursion
    binaryToGray(binary, n, gray, 0);

    // Display the binary and Gray code
    printf("Binary: ");
    displayArray(binary, n);

    printf("\nGray Code: ");
    displayArray(gray, n);

    return 0;
}

Output

In the above program,

This program defines a function binaryToGray that uses recursion to convert a binary array to Gray code. The xorOperation function is a helper function to perform the XOR operation between two bits. The displayArray function is used to display the binary and Gray code arrays. In the main function, an example binary number 1101 is converted to Gray code and displayed.

The execution flow for the input value as 1101 would unfold as follows:

Binary Number: 1101

Initialization: Start with the leftmost bit (1).

Base Case: There is more than one bit remaining, so proceed to the recursive case.

Recursive Case:

1. First Pair (Leftmost):
   • Recursively convert the remaining bits: 1011.
   • Perform XOR: 1 ⊕ 1 = 0.
   • Set the result (0) as the corresponding bit in the Gray code.
2. Second Pair:
   • Recursively convert the remaining bits: 011.
   • Perform XOR: 1 ⊕ 0 = 1.
   • Set the result (1) as the corresponding bit in the Gray code.
3. Third Pair:
   • Recursively convert the remaining bits: 11.
   • Perform XOR: 0 ⊕ 1 = 1.
   • Set the result (1) as the corresponding bit in the Gray code.

• The resulting Gray code is 1011.

If you liked this post you can checkout other C Programs.

FAQ

How is binary code used in computers?

Computers use binary code to represent data and perform calculations. All digital information, such as text, images, and program instructions, is stored and processed in binary form.

Why is Gray code used in certain applications?

Gray code is useful in applications like rotary encoders and error detection circuits. Its property of minimal bit changes between consecutive numbers helps reduce errors during transitions, making it advantageous in specific electronic systems.