Фантазии о Вселенной и мой личный сайт
"Дискретное Косинус-Преобразование"

"Дискретное Косинус-Преобразование"

Эту тему, о которой я собираюсь писать, я практически не знаю. Дискретное косинус-преобразование Фурье - это важнейшая тема из "гармонического анализа", потому что на ее основе базируются технологии цифрового спектрального преобразования изображении (jpeg) и звука (mp3), видео (avi), короче говоря, вся мультимедия. В рамках постоянного мультимедийного прогресса ДКП-Ф (Дискр.Косинус-преобр. Фурье) не столько важно, сколько "жизненно" необходимо.

Как обычно, мне лень куда-то глядеть, изучать, лишний раз напрягаться, но, с другой стороны, мне очень хотелось узнать, в чем же секрет этого ДКП-Ф. Как может целый ряд сложиться в прерывистую функцию, если ряд непрерывен? Потому, долго ломая голову, я, наконец, немного понял, но только немного, потому что способ, по которому я разлагал ряд в непрерывность, очень непродуктивен, однако ПОНЯТЬ схему этого ДКП-Ф оказалось просто.

Дана функция

F(x) = a0 + a1*cosx + a2*cos2x + a3*cos3x + ... + an*cosnx

Нужно ухитриться так подобрать все значения [a], чтобы функция F(x) при x = [0..1] равнялась A0, при x = (1,2] была A1, и т.д. Это сделать, конечно, возможно... а может, нет?

Я подумал, а если взять не бесконечный ряд косинусов, а только два? И пусть тогда при x = 0 функция будет равна 1, и при x = 1 функция будет равна 8. При этом опустим a0 - все равно будет константа, и значения это число не играет в данном случае. Тогда будет:
a1*cos(1*x) + a2*cos(2*x) = 1, если x = 0, то
a1*cos(1*0) + a2*cos(2*0) = 1

a1*cos(1*x) + a2*cos(2*x) = 8, если x = 1, то
a1*cos(1*1) + a2*cos(2*1) = 8
Полученный результат можно представить в виде системы уравнений:
a1*cos(0) + a2*cos(0) = 1
a1*cos(1) + a2*cos(2) = 8
пусть a1 = x, a2 = y, в таком случае:
1*x + 1*y = 1; (1)
0,5403*x - 0,4161*y = 8; (2)
Здесь нетрудно найти x и y:
  • x = 1 - y, подстановка в (2) получается:
  • 0,5403 - 0,5403*y - 0,4161*y = 8
  • -0,9564*y = 7,4597
  • y = - 7,4597 : 0,9564 = -7,799
  • x = 8,799
Проверим теперь: 8,799*cos(x) - 7,799*cos(2*x) = F(X)
x = 0, то 8,799*cos(0) - 7,799*cos(0) = 1
x = 1, то 8,799*cos(1) - 7,799*cos(2) = 0,5403*9,0524 + 8,0523*0,4161 = 4,89101172 + 3,2451639 = 8,136
Чуть-чуть "промахнулся", конечно, в результате сильной погрешности, но это принципиально неважно, ведь глаз с трудом сможет отличить разность в 1% при более точном вычислении этого можно получить правильный результат.

Конечно, все эти разглагольствования и приведение примеров очень мало значат с тем, что из себя представляет вся последовательность косинусов. Подход с помощью систем уравнении не то что неправилен, нет, он может быть, но он непродуктивен, потому что решить систему уравнении с N, стремящимися к бесконечности, неизвестных, невозможно. Даже при N = 256 это уже затруднительно.

Система уравнении:
a1*cos(1*x) + a2*cos(2*x) + ... + a8*cos(8*x) = A1, где x = 0
a1*cos(1*x) + a2*cos(2*x) + ... + a8*cos(8*x) = A2, где x = 1
.... ... ...
a1*cos(1*x) + a2*cos(2*x) + ... + a8*cos(8*x) = A7, где x = 6
a1*cos(1*x) + a2*cos(2*x) + ... + a8*cos(8*x) = A8, где x = 7
Может быть представлена в виде матрицы:
   a1   a2    a3    a4    a5    a6    a7    a8
| cos0 cos0  cos0  cos0  cos0  cos0  cos0  cos0  | A1
| cos1 cos2  cos3  cos4  cos5  cos6  cos7  cos8  | A2
| cos2 cos4  cos6  cos8  cos10 cos12 cos14 cos16 | A3
| cos3 cos6  cos9  cos12 cos15 cos18 cos21 cos24 | A4
| cos4 cos8  cos12 cos16 cos20 cos24 cos28 cos32 | A5
| cos5 cos10 cos15 cos20 cos25 cos30 cos35 cos40 | A6
| cos6 cos12 cos18 cos24 cos30 cos36 cos42 cos48 | A7
| cos7 cos14 cos21 cos28 cos35 cos42 cos49 cos56 | A8
Как видно, нужно найти a1-a8, строки матрицы - это система коэффициентов. Здесь матрица - это всего лишь упрощенный вид системы уравнении, не больше. Самое интересное именно в этой матрице, что здесь нет ни одного значения, равное 0, ведь нет ни одного числа, который был бы кратен "пи наполовину" :) Данная матрица, правда, в некоторой весьма видоизмененной форме, называется "матрицей ДКП", и строится по формуле:

m(i,j) = K1*cos(K2*i*j),

где i - строка, j - столбец, а K1, K2 - некоторые фиксированные значения-константы. Я не помню, чему они равны, но если они равны нужным значением, поиск a1-a8 упрощается в несколько раз.
Решить ее можно методом Гаусса. Этот метод я приводить не буду, потому что решение этим методом займет огромное количество места в статье, просто скажу, что нужно привести всю матрицу к виду, где под/над главной диагональю будут 0. Любую строку можно умножить на любое число, отличное от 0, любую строку можно сложить с любой другой строкой без потерь. Таковы основные приемы метода Гаусса, хотя, честно говоря, все это проистекает из очень простых правил:
  1. [A = B] потому и [K*A = K*B]
  2. [A1 + B1] = C1
    -K*[A2 + B2] = -K*C2
    
    [A1 + B1] - C1 = 0;
    -K*[A2 + B2] + K*C2 = 0;
    
    [A1 + B1] - C1 = K*[A2 + B2] + K*C2;
    [A1 + B1] + K*[A2 + B2] = C1 + K*C2
  3. Отсюда видно, что строки "прибавились" между собой, учитывая и коэффициент K. Хотя чего объяснять, детский сад :) Еще в школе это проходили, хотя... повторить иногда нужно.
Если же [x] распределить на сегменте от 0 до 1 c шагом 1/8, можно получить более точные дискретные значения. Система уравнений будет иметь решение все равно. Теперь, если [x] распределить на сегменте, взяв при этом шаг 1/n, где n стремится к бесконечности, то система уравнений будет все большей и большей, неизвестных будет n, и их число будет стремиться к бесконечности, но, однако, решение все равно будет.

Если же [x] распределить на всей числовой оси, т.е. x=(-W,+W), где W стремится к бесконечности, а шаг будет стремится к нулю, т.е. шаг = 1/W2, то количество неизвестных при решении ДКП-матрицы будет возрастать квадратично n = W2, но, все равно, будет иметь решения. Отсюда очень интересный вывод: с помощью ДКП-Ф можно разложить абсолютно любую дискретную функцию на всей числовой оси. Хотя сейчас данный вывод плохо соотносится с компьютерной тематикой, и является, по сути, просто чистой математикой. Обычно разложения ведутся на отрезке x = [-W,W] с шагом 1, где W=128,256,512... или любые другие конечные значения, и это я назвал бы "сэмплированием". Что-то я вроде объяснил, только не назвал самого главного - как на практике производить простое ДКП-Ф или быстрое ДКП-Ф. Для этого я бы лучше пока порекомендовал бы статью из Википедии [Дискретное преобразование Фурье]