4.3. Основа для вывода алгоритма
Основой для вывода желаемого алгоритма является установление связи между общим видом приведенных выше матриц С и S и степенями W, являющимися первообразными корнями степени N из единицы, а также использование представления чисел, которое допускает дальнейшее обобщение.
Представление числа. Каждое десятичное число 
выражается в двоичном виде
где 
или 1, 
. Таким же образом каждое десятичное число 
, записывается как
где 
0 или 1, 
. Обозначая двоичное представление 
как 
, получаем
(4.3.1)
Выражение (4.3.1) приводит к важному соотношению
(4.3.2)
Покажем справедливость выражения (4.3.2) для случая 
. Для этого правую часть выражения (4.3.2) запишем как
(4.3.3)
Из выражения (4.3.3) следует, что аргументы 
соответствуют двоичному представлению десятичных чисел 
, записанному в естественном порядке следования, как показано в табл. 4.3.1. Таким образом, выражение (4.3.3) принимает вид
что соответствует выражению (4.3.2) при 
.
Таблица 4.3.1
