Kompresja motyla

Kompresja motyla

Kompresja motyla to technika stosowana w algorytmie COMP128, której nazwa wywodzi się z angielskiego terminu butterfly compression. Proces ten polega na przetwarzaniu danych w celu zmniejszenia ich objętości.

Opis procesu

Na wejściu algorytmu znajduje się 512 elementów, z których każdy ma 8 bitów. Po przeprowadzeniu kompresji uzyskuje się 32 elementy, z których każdy składa się z 4 bitów. Dzięki temu następuje znacząca redukcja danych.

Algorytm

Poniżej przedstawiono uproszczony pseudo-kod ilustrujący sposób działania kompresji motyla:

for j = 0 to 4
{
    for k = 0 to (2 ^ j) - 1
    {
        for l = 0 to 2 ^ (4 - j) - 1
        {
            m = 1 + k * 2 ^ (5 - j)
            n = m + 2 ^ (4 - j)
            y = (x[m] + 2 * x[n]) mod 2 ^ (9 - j)
            z = (2 * x[m] + x[n]) mod 2 ^ (9 - j)
            x[m] = T[j][y]
            x[n] = T[j][z]
        }
    }
}

Podsumowanie

Kompresja motyla jest istotnym elementem algorytmów używanych w telekomunikacji, umożliwiającym efektywną redukcję wielkości danych. Dzięki zastosowaniu tej techniki, możliwe jest optymalizowanie przesyłania informacji.