Добавление серых кодов

Существует ли какой-либо известный способ вычисления сложения (и, возможно, вычитания) двух кодов Grey без необходимости преобразовывать два кода Grey в обычный двоичный файл, выполнить двоичное добавление, а затем преобразовать результат обратно в код Grey? Мне удалось написать функции увеличения и уменьшения, но сложение и вычитание выглядят еще менее документированными и сложнее писать.

Ответы

Ответ 1

В этот документ под №6, есть алгоритм для добавления серийного кода Grey (скопировано напрямую, обратите внимание, что is 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, чтобы сформировать кодовое слово Gray. Параметр операндов - PA и PB, суммарная четность - PS. Это распространяет два несущих бита внутри, E и F и создает два внешних бита переноса CE и CF

К сожалению, он ничего не говорит о вычитании, но я предполагаю, что когда вы можете кодировать отрицательные числа, вы можете использовать для этого дополнение.

Ответ 2

Я принял ответ @Sebastian Dressler, потому что предложенный алгоритм действительно работает. Для полноты я предлагаю здесь соответствующую реализацию C99 алгоритма (совместимо с С++):

// 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), который возвращает четность числа битов набора в целое число (если внутреннее имя не существует, другие методы, чтобы вычислить его вручную). Серый код даже тогда, когда он имеет четное количество заданных бит. Алгоритм все еще может быть улучшен, но эта реализация скорее верна исходному алгоритму. Если вы хотите получить подробную информацию о оптимизированной реализации, вы можете посмотреть этот Q & A в обзоре кода.

Ответ 3

Недавно я разработал новый алгоритм для добавления двух кодов Grey. К сожалению, он все еще медленнее, чем наивное решение с двойным преобразованием, а также медленнее алгоритма Гарольда Лукаля (тот, который принят в принятом ответе). Но любое новое решение проблемы приветствуется, верно?

// 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 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
  • Следовательно, я a является степенью 2 и a < b, то a ⊕ b = a - b. Это будет работать, только если b < 2 * a хотя.
  • Если a и b имеют один и тот же гиперпокрытие, но не равны, то a + b = (гиперпокрытие (a) < 1) ⊕ ((гиперпокрытие (a) ⊕ a) + (гиперпокрытие (b) ⊕ b )).

В основном это означает, что мы знаем, как умножить на 2, как добавить мощность от 2 до меньшего кода Grey и как вычесть мощность 2 из кода Grey, которая больше, чем мощность 2, но меньше чем следующая сила 2. Все остальное - это трюки, чтобы мы могли рассуждать в терминах равных значений или степеней 2.

Если вам нужна дополнительная информация/информация, вы также можете проверить этот Q & A в обзоре кода, в котором предлагается современная реализация алгоритма С++, а также некоторые оптимизации (в качестве бонуса есть несколько хороших уравнений MathJax, которых мы не можем здесь: D).