Xor delta coding

This post is a (bit modified) translation of my older post in Russian.

Delta coding is widely used as a component of different algorithms e. g. data compression or digital signal processing. Delta encoding is done through computation of differences between adjacent elements of a sequence and hence is the result of applying the first-order finite difference operator, which is a discrete analogue of a continuous differential operator. Delta decoding is done through computation of partial sums and is a discrete analogue of a continuous integration operator.

Delta encoding has the following important feature: a sequence of repeating values produces a sequence of zeroes. That made me ponder what if difference be replaced with something else conserving the mentioned property of converting sequences of repeating values into zeroes. The obvious candidate (for the case when values have fixed-size binary representation) is the bitwise exclusive or operation (xor; do other viable candidates exist?). This operation is commutative and associative. It also has the following properties (for any a):

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

A corollary of this is (a xor b) xor ba for any a and any b. (This is the base of the well-known trick of swapping values of two variables without explicitly using temporary storage.)

Thus for a set of functions defined as { xora | aZ, xora(x) ≡ a xor x } we have an identity element xor0. Any element of this abelian group (with function composition operation) is an inverse to itself.

These properties made xor popular in cryptographic algorithms (is there any well-known cipher or hash that doesn’t use it?).

The following code replaces addition and subtraction in «classic» delta coding algorithm with bitwise xor.

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;
}

Simple testing code is available here.

This code has an amusing property: repeated xor-delta encoding leads to coincidence of prefixes of the resulting sequence and the original sequence. It can be shown on paper (due to properties of xor) that after 2n repeats we have coincidence of prefix of length 2n (or coincidence of the entire sequences if the original sequence is no longer than 2n). Therefore after 2N repeats of encoding, where N = ceil(log2(sequence length)), we have the original sequence recovered. Repeating of the inverse operation (decoding) has the same property and enumerates the same intermediate sequences but in inverse order.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: