Добавление серых кодов
Есть ли какой-нибудь известный способ вычислить сложение (и, возможно, вычитание) двух кодов Грея без необходимости преобразования двух кодов Грея в обычный двоичный код, выполнить двоичное сложение и затем преобразовать результат обратно в код Грея? Мне удалось написать функции увеличения и уменьшения, но сложение и вычитание кажутся еще менее документированными и сложными для написания.
Решение
В этот документ под # 6 есть алгоритм для последовательного добавления кода Грея (скопировано напрямую; обратите внимание, что ⊕ является 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;
При этом добавляются кодовые слова Грея A и B для формирования кодового слова Грея S. Четности операндов — PA и PB, суммарная четность — PS. Это распространяет два внутренних бита переноса, E и F, и создает два внешних бита переноса CE и CF
К сожалению, в нем ничего не говорится о вычитании, но я предполагаю, что когда вы можете кодировать отрицательные числа, вы можете использовать сложение для этого.
Другие решения
Я принял ответ @Sebastian Dressler, потому что предложенный алгоритм действительно работает. Для полноты картины я предлагаю здесь соответствующую реализацию алгоритма на C99 (совместимую с 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;
}
Замечания: __builtin_parity является встроенной функцией компилятора (GCC и Clang), которая возвращает четность числа установленных бит в целом числе (если встроенная функция не существует, существуют другие методы вычислить это вручную). Серый код — это даже когда он имеет четное количество установленных битов. Алгоритм все еще может быть улучшен, но эта реализация довольно верна исходному алгоритму. Если вам нужны подробности об оптимизированной реализации, вы можете взглянуть на этот вопрос& на проверку кода.
Недавно я разработал новый алгоритм добавления двух кодов Грея. К сожалению, он все еще медленнее, чем простое решение с двойным преобразованием, а также медленнее, чем алгоритм Гарольда Лукала (тот, что в принятом ответе). Но любое новое решение проблемы приветствуется, верно?
// 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);
}
Алгоритм использует следующие служебные функции для правильной работы:
// 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);
}
Я должен признать, что это просто стена кода для чего-то столь же «простого», как дополнение. Это главным образом основано на наблюдениях о битовых комбинациях в кодах Грея; то есть я ничего не доказал формально, но мне еще предстоит найти случаи, когда алгоритм не работает (если я не принимаю во внимание переполнение, он не обрабатывает переполнение). Вот основные наблюдения, использованные для построения алгоритма, предположим, что все является кодом Грея:
- 2 * n = (n << 1) ⊕ четность (n)
- Если a — степень 2 и a> b, то a ⊕ b = a + b
- Следовательно, i a является степенью 2 и a < b, то a ⊕ b = a — b. Это будет работать только если б < 2 * хотя.
- Если a и b имеют одинаковый гиперэтаж, но не равны, то a + b = (hyperfloor (a) << 1) ⊕ ((hyperfloor (a) ⊕ a) + (hyperfloor (b) ⊕ b)).
По сути, это означает, что мы знаем, как умножить на 2, как добавить степень 2 в меньший код Грея и как вычесть степень 2 из кода Грея, который больше, чем степень 2, но меньше, чем следующий. Степень 2. Все остальное — уловки, чтобы мы могли рассуждать в терминах равных значений или степеней 2.
Если вы хотите больше деталей / информации, вы также можете проверить этот вопрос& в Code Review, который предлагает современную реализацию алгоритма на C ++, а также некоторые оптимизации (в качестве бонуса, есть несколько хороших уравнений MathJax, которых у нас здесь нет: D).