Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Binary Gray code conversion
function reverse(array) {
var copy = array.slice();
copy.reverse();
return copy;
}
function gray(nbits) {
if (nbits <= 0) return ['']; // zero bit code contains 2^0 values == 1
var gray0 = gray(nbits - 1);
var lower = gray0.map(function(b) { return '0' + b; });
var upper = reverse(gray0).map(function(b) {
return '1' + b;
});
return lower.concat(upper);
}
function not(bits) {
return bits.split('').
map(function(c) { return c == '0' ? '1' : '0'; }).
join('')
}
function shiftR(bits) {
return '0' + bits.substring(0, bits.length-1);
}
function xor(a, b) {
var sum = [];
for (var i = 0; i < a.length; i++) {
sum[i] = ((a[i] == '1') ^ (b[i] == '1')) ? '1' : '0';
}
return sum.join('');
}
function gray2bin(g) {
if (g === '') return ''; // zero bit code
var firstBit = g.charAt(0);
if (firstBit == '0') {
return '0' + gray2bin(g.substring(1))
}
else {
return '1' + not(gray2bin(g.substring(1)))
}
}
function bin2gray(b) {
if (b === '') return ''; // zero bit code
var firstBit = b.charAt(0);
if (firstBit == '0') {
return '0' + bin2gray(b.substring(1));
}
else {
return '1' + bin2gray(not(b.substring(1)));
}
}
function bin2grayFast(b) {
return xor(b, shiftR(b));
}
function toBinary(n) {
return n.toString(2)
}
function padLeftSlow(s, padding, totalLength) {
// not efficient
while (s.length < totalLength) {
s = padding + s;
}
return s;
}
function printGray(grayCode) {
var columnWidth = 15;
var nbits = grayCode[0].length;
function col(s) { return padLeftSlow(s, ' ', columnWidth); }
console.log(col('INDEX') + '|' +
col('GRAY') + '|' +
col('BIN2GRAY') + '|' +
col('BIN2GRAY FAST'));
for (var i = 0; i < grayCode.length; i++) {
var indexStr = padLeftSlow(toBinary(i), '0', nbits);
var grayStr = grayCode[i];
var gray2Str = bin2gray(indexStr);
var gray3Str = bin2grayFast(indexStr);
console.log(col(indexStr) + '|' +
col(grayStr) + '|' +
col(gray2Str) + '|' +
col(gray3Str));
}
}
printGray(gray(3));
printGray(gray(4));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment