Gray code to binary conversion
-
06-01-2021 - |
Question
Given a gray code for a number, find the binary code for the number.
Gray code is a binary numeral system where two successive values differ in only one bit.
For Example two bit gray code is: 0 - 00 1 - 01 2 - 11 3 - 10
Binary is:
0 - 00 1 - 01 2 - 10 3 - 11
Provide an algorithm to convert the gray code of the number to binary code.
For example, input is 11. Expected output is 10.
Solution
Converting the Gray code to binary is:
Retain the Most significant bit as it is and for the rest of the bits keep xoring the successive bits.
ie Gn Gn-1 Gn-2 ........ G1 is the gray code and Bn Bn-1 .......B1 is the binary code.
Bn= Gn and for all the other bits Bn-1 = Gn-1 XOR Gn
OTHER TIPS
If you want an easy way there is a good online gray code converter that you can use: http://www.convertforfree.com/gray-code-converter/
<?php
function gry_code($n) {
if($n == 0 || $n > 65 ) {
return "Invalid input please input between 1 to 65";
exit;
}
$arr = array();
array_push($arr,"0","1");
$i = 0;
$j = 0;
for ($i = 2; $i < (1<<$n); $i = $i<<1)
{
//duplicate the arr contents in reverse order
for ($j = $i-1 ; $j >= 0 ; $j--)
array_push($arr,$arr[$j]);
// append 0 to the first half
for ($j = 0 ; $j < $i ; $j++)
$arr[$j] = "0".$arr[$j];
// append 1 to the second half
for ($j = $i ; $j < 2*$i ; $j++)
$arr[$j] = "1".$arr[$j];
}
//return $arr;
$arr = array_slice($arr, -$n);
foreach($arr as $key => $arrx) {
echo $arrx."\n";
}
//return $arr;
}
print_r(gry_code(5));
?>