Преобразование с использованием разложения на подпоследовательности

Рассмотрим последовательность данных

которая представляется в виде суммы двух слагаемых. Две короткие последовательности при их точном «прослаивании» по аналогии с идеальным «тасованием» воспроизводят исходную последовательность

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

На основании теоремы о растяжении для ДПХ (см. гл. 4) непосредственно можем утверждать:

Однако применительно к последнему выражению следует отметить, что нам требуется ДПХ последовательности . С целью получения преобразования этой последовательности применим теорему о сдвиге. При сдвиге на один элемент вправо эта теорема формулируется следующим образом:

Если последовательность имеет то имеет ДПХ вида

Используя обозначение можем утверждать, что последовательность приобретает вид

Следовательно, при условии что последовательность

имеет . Для последовательности равно

Наконец, применяя теорему сложения, получим

Если в это равенство для входят коэффициенты 0, 1 или — 1, то оно упрощается:

На этом завершается доказательство того, что -элементное преобразование может быть сформировано из двух четырехэлементных преобразований