Tag Archives: дельта-кодирование

Xor-Δ-кодирование

Дельта-кодирование является распространённым составным элементом различных алгоритмов сжатия данных и обработки дискретных сигналов. Дельта-кодирование выполняется путём вычисления разностей между соседними элементами последовательности (и напоминает дифференцирование). Дельта-декодирование выполняется путём накапливания частичных сумм (и напоминает, соответственно, интегрирование).

Одним из характерных свойств дельта-кодирования является то, что последовательность повторяющихся значений кодируется последовательностью нулей. В связи с этим, мне стало интересно, что получится, если заменить и вычитание и сложение одной операцией — вычислением поразрядного исключающего или (xor). Данная операция коммутативна и ассоциативна. Кроме того, она обладает следующими двумя свойствами (для любого числа a):

  • a xor 0 ≡ a;
  • a xor a ≡ 0.

Откуда легко выводится тождество (a xor b) xor b ≡ a.

Таким образом, если мы определим множество функций { xora | a ∈ Z, xora(x) ≡ a xor x }, то единица этого множества — тождественное преобразование xor0, и каждый элемент этого множества является обратным к самому себе относительно операции композиции функций (в частности, множество таких функций является абелевой группой относительно операции композиции).

Благодаря своим свойствам, операция xor очень популярна в области криптографических алгоритмов.

Итак, я написал следующий C++-код, заменяющий операции вычитания и сложения в дельта-кодировании/декодировании на операцию поразрядного исключающего или.

void xor_delta_encode(char *begin, size_t n)
{
  char prev = begin[0], t;
  for (size_t i = 1; i < n; ++i)
  {
    t = begin[i];
    begin[i] ^= prev;
    prev = t;
  }
}

void xor_delta_decode(char *begin, size_t n)
{
  char prev = begin[0];
  for (size_t i = 1; i < n; ++i)
    prev = begin[i] ^= prev;
}

Тестировочный код целиком: Bitbucket.

Если запустить этот код, то можно увидеть довольно забавное свойство (которое и сподвигло меня написать этот пост).

Повторное xor-дельта-кодирование приводит к повторению префиксов исходной последовательности. А именно (это можно показать «на бумажке», сокращая элементы благодаря свойствам операции xor): после 2n повторений имеем совпадение с исходной последовательностью префикса длины до 2n. Через 2N повторений операции кодирования, где N = ceil(log2(длина последовательности)), имеем восстановление исходной последовательности, «круг замкнулся». Повторение обратной операции (xor-дельта-декодирования) перебирает те же 2N возможных последовательностей, но уже в обратном порядке.

Реклама