c++ - Adición de códigos grises

gray-code

Question

¿Existe alguna forma conocida de calcular la suma (y tal vez la resta) de dos códigos de Gray sin tener que convertir los dos códigos de Gray a binarios regulares, realizar una suma binaria y luego convertir el resultado a un código de Gray? Logré escribir funciones de incremento y decremento, pero la suma y la resta parecen ser incluso menos documentadas y más difíciles de escribir.

Answer 1

Acepté la respuesta de @Sebastian Dressler porque el algoritmo sugerido funciona. En aras de la exhaustividad, propongo aquí una implementación C99 correspondiente del algoritmo (compatible con C ++):

// lhs and rhs are encoded as Gray codes
unsigned add_gray(unsigned lhs, unsigned rhs)
{
// e and f, initialized with the parity of lhs and rhs
// (0 means even, 1 means odd)
bool e = __builtin_parity(lhs);
bool f = __builtin_parity(rhs);
unsigned res = 0u;
for (unsigned i = 0u ; i < CHAR_BIT * sizeof(unsigned) ; ++i)
{
// Get the ith bit of rhs and lhs
bool lhs_i = (lhs >> i) & 1u;
bool rhs_i = (rhs >> i) & 1u;
// Copy e and f (see {in parallel} in the original paper)
bool e_cpy = e;
bool f_cpy = f;
// Set the ith bit of res
unsigned res_i = (e_cpy & f_cpy) ^ lhs_i ^ rhs_i;
res |= (res_i << i);
// Update e and f
e = (e_cpy & (!f_cpy)) ^ lhs_i;
f = ((!e_cpy) & f_cpy) ^ rhs_i;
}
return res;
}

Nota: __builtin_parity es un compilador intrínseco (GCC y Clang) que devuelve la paridad del número de bits establecidos en un entero (si el intrínseco no existe, existen otros métodos para calcularlo a mano). Un código gris es parejo cuando tiene un número par de bits establecidos. El algoritmo aún puede mejorarse, pero esta implementación es bastante fiel al algoritmo original. Si desea detalles sobre una implementación optimizada, puede consultar estas Preguntas y respuestas sobre Revisión de código.

Answer 2

Recientemente ideé un nuevo algoritmo para agregar dos códigos de Gray. Desafortunadamente, sigue siendo más lento que la ingenua solución de doble conversión y también es más lento que el algoritmo de Harold Lucal (el que está en la respuesta aceptada). Pero cualquier nueva solución a un problema es bienvenida, ¿verdad?

// lhs and rhs are encoded as Gray codes
unsigned add_gray(unsigned lhs, unsigned rhs)
{
// Highest power of 2 in lhs and rhs
unsigned lhs_base = hyperfloor(lhs);
unsigned rhs_base = hyperfloor(rhs);
if (lhs_base == rhs_base)
{
// If lhs and rhs are equal, return lhs * 2
if (lhs == rhs)
{
return (lhs << 1u) ^ __builtin_parity(lhs);
}
// Else return base*2 + (lhs - base) + (rhs - base)
return (lhs_base << 1u) ^ add_gray(lhs_base ^ lhs, lhs_base ^ rhs);
}
// It''s easier to operate from the greatest value
if (lhs_base < rhs_base)
{
swap(&lhs, &rhs);
swap(&lhs_base, &rhs_base);
}
// Compute lhs + rhs
if (lhs == lhs_base)
{
return lhs ^ rhs;
}
// Compute (lhs - base) + rhs
unsigned tmp = add_gray(lhs ^ lhs_base, rhs);
if (hyperfloor(tmp) < lhs_base)
{
// Compute base + (lhs - base) + rhs
return lhs_base ^ tmp;
}
// Here, hyperfloor(lhs) == hyperfloor(tmp)
// Compute hyperfloor(lhs) * 2 + ((lhs - hyperfloor(lhs)) + rhs) - hyperfloor(lhs)
return (lhs_base << 1u) ^ (lhs_base ^ tmp);
}

El algoritmo utiliza las siguientes funciones de utilidad para que funcione correctamente:

// Swap two values
void swap(unsigned* a, unsigned* b)
{
unsigned temp = *a;
*a = *b;
*b = temp;
}
// Isolate the most significant bit
unsigned isomsb(unsigned x)
{
for (unsigned i = 1u ; i <= CHAR_BIT * sizeof(unsigned) / 2u ; i <<= 1u)
{
x |= x >> i;
}
return x & ~(x >> 1u);
}
// Return the greatest power of 2 not higher than
// x where x and the power of 2 are encoded in Gray
// code
unsigned hyperfloor(unsigned x)
{
unsigned msb = isomsb(x);
return msb | (msb >> 1u);
}

¿Entonces, cómo funciona?

Tengo que admitir que es un muro de código para algo tan "simple" como una adición. Se basa principalmente en observaciones sobre patrones de bits en códigos de Gray; es decir, no probé nada de manera formal, pero aún tengo que encontrar casos en los que el algoritmo no funciona (si no tengo en cuenta el desbordamiento, no se maneja el desbordamiento). Aquí están las principales observaciones utilizadas para construir el algoritmo, asumiendo que todo es un código Gris:

• 2 * n = (n << 1) ⊕ paridad (n)
• Si a es una potencia de 2 y a> b, entonces a ⊕ b = a + b
• En consecuencia, ia es una potencia de 2 y a <b, luego a ⊕ b = a - b. Esto solo funcionará si b <2 * a sin embargo.
• Si a y b tienen el mismo piso pero no son iguales, entonces a + b = (campo) (a) << 1) ⊕ ((campo) (a) ⊕ a) + (piso) (b) ⊕ b).

Básicamente, significa que sabemos cómo multiplicar por 2, cómo agregar una potencia de 2 a un código de Gray más pequeño y cómo restar una potencia de 2 de un código de Gray que es más grande que esa potencia de 2 pero más pequeño que el siguiente poder de 2. Todo lo demás son trucos para que podamos razonar en términos de valores iguales o poderes de 2.

Si desea más detalles / información, también puede consultar esta Preguntas y Respuestas sobre Revisión de Código, que propone una implementación moderna del algoritmo en C ++, así como algunas optimizaciones (como beneficio adicional, hay algunas bonitas ecuaciones de MathJax que no podemos tener aquí). RE).

Answer 3

En este documento bajo # 6, hay un algoritmo para la adición del código Gray en serie (copiado directamente; tenga en cuenta que ⊕ es xor ):

procedure add (n: integer; A,B:word; PA,PB:bit;
var S:word; var PS:bit; var CE, CF:bit);
var i: integer; E, F, T: bit;
begin
E := PA; F := PB;
for i:= 0 to n-1 do begin {in parallel, using previous inputs}
S[i] := (E and F) ⊕ A[i] ⊕ B[i];
E := (E and (not F)) ⊕ A[i];
F := ((not E) and F) ⊕ B[i];
end;
CE := E; CF := F;
end;

Esto agrega las palabras A y B del código Gray para formar la palabra S del código Gray. Las paridades de los operandos son PA y PB, la paridad de la suma es PS. Esto propaga dos bits de acarreo internamente, E y F, y produce dos bits de acarreo externos CE y CF

Desafortunadamente, no dice nada sobre la resta, pero supongo que cuando puedes codificar números negativos, puedes usar la suma para eso.