УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДИСКРЕТНЫХ ПОЛИНОМИАЛЬНЫХ ПРЕОБРАЗОВАНИЙ

Заявляемая полезная модель относится к области цифровой обработки сигналов (ЦОС) различного назначения и может быть использован при обработке видео и аудиосигналов в реальном масштабе времени. Для решения задач ЦОС различного назначения применимы определенные подклассы дискретных полиномиальных преобразований (ДПП). Например, дискретных ортогональных (унитарных) преобразований - дискретного преобразования Фурье (ДПФ) и Хартли (ДПХ), как прямого, так и обратного [1, стр.21], а также цифровых фильтров с импульсной характеристикой конечной длительности (КИХ-фильтров) [2, стр.357].
ki
k
Существенной проблемой при проектировании устройств для выполнения ДПП является выбор такой его структуры, при которой обеспечивается как высокое быстродействие, так и универсальность данного устройства применительно к реализации заданного подкласса ДПП. Одним из способов повышения быстродействия указанного устройства является реализация конвейерной обработки данных с сохранением промежуточных результатов. Для устройств вычислительной техники (ВТ), реализованных указанным способом, максимальное быстродействие определено как сумма максимального времени задержки функционирования одной из ступеней конвейера и максимального времени задержки одного из регистров, сохранявших промежуточные результаты. Универсальность устройства для вычисления ДПП достигается за счет возможности варьирования элементов системы функций φ(x), ,  на конечном интервале длины  вида [1, стр.21]
k
k
k
k
k
k
c
Согласно [2, стр.357], КИХ-фильтр (нерекурсивный цифровой фильтр) реализуем на основе (1) для системы функций φ(х)=a·x на конечном интервале длины N, N=2, где х - значение сигнала в k-й момент времени, , c - целые положительные значения. Согласно [3, стр.157], данная система функций (1) в совокупности с определенным коэффициентами a, , образует «фильтрующий» полином.
(11)
(13)
Известна реализация быстрого преобразования Хартли и Фурье при использовании конвейеризации процесса вычисления базовой операции («бабочки») алгоритма быстрого ДПФ и ДПХ [RU 2190874 С2 G06F 17/14, 20.07.1999]. Недостатком данной реализации является ограничение по количеству выполняемых дискретных преобразований.
c
(11)
(13)
Известна реализация ДПФ на конечном интервале N=2 при использовании процессоров, для которой обеспечивается максимальное быстродействие за счет оптимизации процесса извлечения коэффициентов ДПФ из памяти [RU 2290687 C1 G06F 17/14 (2006.01), 31.05.2005]. Недостатком данной реализаций является ограничение по количеству выполняемых дискретных преобразований.
(11)
(13)
Известна реализация универсального цифрового фильтра с программируемой структурой, которая, помимо КИХ-фильтра, позволяет реализовать и авторегрессионный фильтр [RU 2399152 С2 Н03Н 17/04, Н03Н 17/06, Н03Н 21/00 (2006.01), 12.03.2008]. Недостатки данной реализации - ограничение по количеству выполняемых дискретных преобразований и низкое быстродействие.
2
(11)
(13)
Наиболее близким по технической сущности к заявляемой полезной модели является устройство для формирования остатка по заданному модулю, содержащее Т блоков формирования частичных остатков с сохранением вычисленных результатов, два параллельных регистра, мультиплексор, компаратор и блок вычитания, причем t-й блок формирования частичных остатков, , содержит комбинационный сумматор с (n-p) (p+1)-разрядными входами и (p+q)-разрядным выходом, где n - разрядность чисел, (p+1) - разрядность заданного модуля, q=]log(n-p)[[RU 2421781 C1 G06F 7/72, Н03М 7/18 (2006.01), 19.10.2009]. Данное устройство позволяет производить конвейерное вычисление значений остатков от деления по заданному модулю с сохранением промежуточных результатов (частичных остатков), следствием чего является существенное увеличение быстродействие данного устройства при обработке потока чисел. Недостаток данного устройства - ограничение по количеству выполняемых дискретных преобразований.
К причинам, препятствующим достижению технического результата при использовании известного устройства является ограничение по количеству выполняемых ими дискретных преобразований, что существенно ограничивает область его применения.
ki
k
k
Технический результат заключается в расширении функциональных возможностей устройства для вычисления ДПП, структура которого может быть настроена для выполнения различных подклассов ДПП (например, Фурье, Уолша, Хаара, Хартли, косинусного), а также для реализации КИХ-фильтров. Настройка производится путем задания системы функций на конечном интервале длины N и заключается в занесении всевозможных значений функций (φ(x) при заданных значениях x, , , в параллельные регистры значений разрядов функций каждого из блоков вычисления системы функций ДПП, а также в изменении количества блоков вычисления системы функций ДПП и блоков комбинационных сумматоров для N f-разрядных двоичных чисел. Количество каждого из указанных блоков определено как Т - количество элементов образа заданного подкласса ДПП. В устройстве реализовано параллельное вычисление каждого из Т элементов указанных подклассов ДПП, причем в каждом из блоков вычисления системы функций ДПП и в каждом из комбинаиионных сумматоров для N f-разрядных двоичных чисел производится конвейерное вычисление с сохранением промежуточных результатов.
2
2
2
2
n
n
n
n
n
n
n
n
u-2-j
d
d+1
d+1
N/2
N/2
Технический результат достигается тем, что в устройство для вычисления дискретных полиномиальных преобразований, содержащем t-й комбинационный сумматор для N f-разрядных двоичных чисел с одним выходом на (f-1+logN) разрядов каждый, , введены система из n N-разрядных регистров сдвига с входом на n двоичных разрядов, с синхровходом и с N n-разрядными двоичными выходами, а также Т блоков вычисления системы функций ДПП с N n-разрядными двоичными входами, с Т входами значений разрядов функций ДПП на N·f·2 двоичных разрядов каждый, с синхровходом, с входом инициализации и с N выходами на f двоичных разрядов каждый, причем вход системы из n N-разрядных регистров сдвига является входом устройства на n двоичных разрядов, каждый из N выходов системы из n N-разрядных регистров сдвига соединен с N n-разрядными двоичными входами каждого из Т блоков вычисления системы функций ДПП, при этом N f-разрядных выходов каждого из Т блоков вычисления системы функций ДПП соединены с N входами соответствующего ему комбинационного сумматора для N f-разрядных двоичных чисел, (f-1+logN) - разрядные выходы каждого из комбинационных сумматоров для N f-разрядных двоичных чисел являются выходами устройства для вычисления ДПП, синхровход системы из n N-разрядных регистров сдвига, синхровход каждого из Т блоков вычисления системы функций ДПП и синхровход каждого из Т комбинационных сумматоров для N f-разрядных двоичных чисел является синхровходом устройства для вычисления ДПП, каждый вход значений разрядов функций ДПП t-го блока вычисления системы функций ДПП соединен с t-м входом значений разрядов функций ДПП на N·f·2 двоичных разрядов устройства для вычисления ДПП, , а вход инициализации каждого из Т блоков вычисления системы функций ДПП является входом инициализации устройства, система из n N-разрядных-регистров сдвига содержит n N-разрядных регистров сдвига с последовательным входом, синхровходом и N двоичными выходами каждый, причем последовательный вход каждого N-разрядного регистра сдвига соединен с соответствующим двоичным разрядом n-разрядного входа устройства для вычисления ДПП, синхровход каждого из n N-разрядных регистров сдвига соединен с синхровходом устройства для вычисления ДПП, а i-е разряды N-разрядных регистров сдвига являются i-м выходом системы из n N-разрядных регистров сдвига на n двоичных разрядов каждый, , t-й блок вычисления системы функций ДПП, , содержит N·f параллельных регистров значений разрядов функций разрядности 2 каждый с синхровходом, N·f мультиплексоров «2 в 1», N параллельных f-разрядных регистров с синхровходом, причем синхровход каждого из параллельных регистров значений разрядов функций соединен с входом инициализации устройства для вычисления ДПП, вход данных каждого из N·f параллельных регистров значений разрядов функций соединен с соответствующими входами значений разрядов функций ДПП на N·f·2 двоичных разрядов устройства для вычисления ДПП, а выходы данных каждого из N·f параллельных регистров значений разрядов функций соединены с входами данных соответствующих им мультиплексоров «2 в 1», управляющие входы каждого из f элементов i-й группы мультиплексоров «2 в 1» соединены с i-м входом n-разрядных двоичных чисел t-го блока вычисления системы функций ДПП, выходы данных i-й группы мультиплексоров «2 в 1» соединены с входом данных i-го параллельного f-разрядного регистра, синхровход каждого из которых соединен с синхровходом устройства для вычисления ДПП, а выход данных каждого из которых является i-м выходом f-разрядных двоичных чисел t-го блока вычисления системы функций ДПП, , , t-й комбинационный сумматор для N f-разрядных двоичных чисел, , содержит (N-1) двухвходовых сумматора, из которых 2 имеют разрядность (f+j+1), , u=1+logN, N входов на f двоичных разрядов каждый, причем каждый из N входов на f двоичных разрядов N/2 двухвходовых сумматоров соединен с N входами t-го блока вычисления системы функций ДПП разрядности f, , выходы двухвходовых сумматоров соединены с входами (f+1)-разрядных параллельных регистров, выходы которых, в свою очередь, соединены с входами N/4 двухвходовых сумматоров, выходы которых соединены с входами N/4 (f+2)-разрядных параллельных регистров, выходы N/2 (f+d)-разрядных параллельных регистров соединены с входами N/2 двухвходовых сумматоров, выходы которых соединены с входами N/2 (f+а+1)-разрядных параллельных регистров, , выходы двух (f-1+logN)-разрядных параллельных регистров соединены с входами двухвходового сумматора, выход которого соединен с входом параллельного регистра разрядности (f+log N), выход которого является выходом t-го комбинационного сумматора для N f-разрядных двоичных чисел, , синхровходы каждого из (N-1)-го параллельного регистра соединены с синхрозходом устройства для вычисления ДПП.
k
k
k
Каждый из Т блоков вычисления системы функций ДПП может быть настроем для реализации произвольной системы функций φ(x) от заданных значений x, , , соответствующей указанному подклассу ДПП (см. выше). При этом для комплексной и для вещественной составляющей каждого элемента образа заданного подкласса ДПП применимы отдельные пары блоков вычисления системы функций ДПП и комбинационных сумматоров для N f-разрядных двоичных чисел. Например, для реализации ДПФ на конечном интервале N требуется Т=2N указанных блоков, для реализации ДПХ - Т=N пар указанных блоков, а для реализации КИХ-фильтра порядка N достаточно одной пары данных блоков, соответственно. Кроме того, внутри каждого из Т комбинационных сумматоров для N f-разрядных двоичных чисел предусмотрена возможность сохранения промежуточных результатов, частичных сумм, в параллельных регистрах с синхровходом.
Схема устройства для вычисления дискретных полиномиальных преобразований представлена на фиг.1, а схемы системы из n N-разрядных регистров сдвига, t-го блока вычисления системы функций ДПП и f-го комбинационного сумматора для N f-разрядных двоичных чисел,  приведены на фиг.2, фиг.3 и фиг.4, соответственно.
1,
T
t
2
k
t
t
t
t
t
t
t
t
2
t
c
n
Устройство для вычисления ДПП, содержит Т комбинационных сумматоров 1…,1 для N f-разрядных двоичных чисел, систему 2 из n N-разрядных регистров сдвига, блоки 3 вычисления системы функций ДПП, , причем каждая из данных функций представлена f-разрядными двоичными числами, где Т - количество элементов образа заданного подкласса ДПП, представленных (f-1+logN) - разрядными двоичными числами, N=2 - длина интервала последовательности, над которой выполняется ДПП, f=n+r, r - максимальное количество двоичных разрядов постоянных коэффициентов для заданного подкласса ДПП, n - количество двоичных разрядов входа устройства, причем вход системы 2 из n N-разрядных регистров сдвига, представленный n-разрядным двоичных значением x, является входом 4 устройства для вычисления ДПП, синхровход системы 2 из n N-разрядных регистров сдвига, а также каждого из блоков 3 вычисления системы функций ДПП и каждого из комбинационных сумматоров 1 для N f-разрядных двоичных чисел, , является синхровходом устройства для вычисления ДПП (на фиг.1 не показаны), вход инициализации каждого из блоков 3 вычисления системы функций ДПП, , является входом инициализации устройства для вычисления ДПП (на фиг.1 не показаны), вход значений разрядов функции ДПП соответствующего блока 3 вычисления системы функций ДПП на N·f·2 двоичных разрядов является t-м входом значений разрядов функции ДПП устройства для вычисления ДПП,  (на фиг.1 не показаны), выход системы 2 из n N-разрядных регистров сдвига, представленный n·N - разрядным двоичным числом, соединен с входами каждого из блоков 3 вычисления системы функций ДПП, , выход каждого из блоков 3 вычисления системы функций ДПП, представленный f-разрядным двоичным значением, соединен с входом соответствующего комбинационного сумматора 1 для N f-разрядных двоичных чисел, , а выход каждого комбинационного сумматора 1 для N f-разрядных двоичных чисел, определенный как (f-1+logN) - разрядное двоичное число, является выходом 5 устройства для вычисления ДПП, .
b
b
b
b
b.i
b
На фиг.2 представлена система 2 из n N-разрядных регистров сдвига, которая включает n N-разрядных регистров сдвига 6, , причем последовательные входы каждого из регистров сдвига 6, , соединены с соответствующим двоичным разрядом входа устройства 4 для вычисления ДПП - 4, , синхровходы каждого из N-разрядных регистров сдвига 6, , соединены с синхровходом устройства для вычисления ДПП (на фиг.2 не показаны), а выходы 7, каждого из N-разрядных регистров сдвига 6, , образуют i-й выход системы 2 из n N-разрядных регистров сдвига на n двоичных разрядов каждый, .
t
k(t-1)
k
t.(k+1).p
k(t-1)
k
t.(k+1).p
t.(k+1)
t.(k+1).p
t.(k+1).p
k(t-1)
k
t.(k+1).p
t.(k+1).p
t.(k+1).p
t.(k+1).1
t.(k+1).f
t.(k+1)
k
1.(k+1)
n.(k+1)
t.(k+1).1
t.(k+1).f
t.(k+1)
t.(k+1)
t.(k+1)
t
n
n
n
n
n
n
На фиг.3 представлен один из блоков 3 вычисления системы функций ДПП вида φ(x), , , который включает N·f параллельных регистров 8, , значений p-го разряда функции φ(x) разрядности 2 каждый, N·f мультиплексоров 9 «2 в 1» и N параллельных f-разрядных регистров 10, причем синхровход каждого из параллельных регистров 8 значений разрядов функций, , , соединен с входом инициализации 11 устройства для вычисления ДПП, каждый вход данных параллельного регистра 8 значений разрядов функций ДПП φ(x), , соединен с соответствующим входом 12 значений p-го разряда указанных функции на N·f·2 двоичных разрядов, , , выход каждого из параллельных регистров 8, соединен с соответствующими входами данных мультиплексора 9, «2 в 1», тогда как управляющие входы каждого мультиплексора «2 в 1» из группы 9…9, , соединены с n-разрядным входом 13 значений x, разряды каждого из которых соединены с двоичными выходами 7…7 системы 2 из n N-разрядных регистров сдвига (см. фиг.2), выходы мультиплексоров 9…9 «2 в 1» соединены с входами параллельных f-разрядных регистров 10, , синхровход каждого из которых соединен с синхровходом устройства для вычисления ДПП (на фиг.3 не указаны), а выходы параллельных f-разрядных регистров 10, являются f-разрядными выходами 14 блока 3 вычисления системы функций ДПП, , , соответственно.
t
t.1
t.(N-1)
t.1
t.(N-1)
t.1
t.(N/2)
t.
t.1
t.(N/2)
t.1
t.(N/2)
1
2
t.(N-3)…
t.(N-2)
t.(N-1)
t.(N-1)
2
t
t.1…
t.(N-1)
u-2-j
u-2-j
d
i
d÷1
d+1
На фиг.4 изображен комбинационный сумматор 1 для N f-разрядных двоичных чисел, , который включает в себя (N-1) двух-входовых сумматора 15…15, из которых 2 имеют разрядность (f+j), , u=1+logN, а также (N-1) параллельных регистра 16…16, с синхровходом, , из которых 2 имеют разрядность (f+j+1), , u=1+logN, N входов на f двоичных разрядов каждый, причем каждый из N входов на f двоичных разрядов N/2 двухвходовых сумматоров 15…15 соединен с N входами блока 3 вычисления системы функций ДПП разрядности f, , выходы N/2 двухвходовых сумматоров 15…15 соединены с входами N/2 (f+1)-разрядных параллельных регистров 16…16, выходы которых, в свою очередь, соединены с входами N/4 двухвходозых сумматоров , D=N/2, выходы которых соединены с входами N/4 (f+2)-разрядных параллельных регистров , выходы N/2 (f+d)-разрядных параллельных регистров ,  N/2, соединены с входами N/2 двухвходовых сумматоров , выходы которых соединены с входами N/2 (f+d+1) -разрядных параллельных регистров , , выходы двух (f-1+logN)-разрядных параллельных регистров 1616 соединены с входами двухвходового сумматора 15, выход которого соединен с входом параллельного регистра 16 разрядности (f-1+logN), выход которого является выходом 5 t-то комбинационного сумматора для N f-разрядных двоичных чисел, , синхровходы каждого из (N-1)-го параллельного регистра 1616 соединены с синхровходом устройства для вычисления ДПП (на фиг.4 не указаны).
Рассмотрим устройство для вычисления дискретных полиномиальных преобразований в работе.
t.(k+1).p
k(t-1)
k
t.(k+1).p
k(t-1)
t.(k+1).p
n
В предлагаемом устройстве на этапе инициализации в параллельные регистры 8 значений разрядов функции разрядности 2 по сигналу 11 инициализации параллельно заносятся соответствующие значения р-х двоичных разрядов значения функций φ(x) системы (1), , , . При этом значение в d-м разряде каждого из регистров 8, соответствует p-му разряду значения функции, φ(d), . Через период времени от момента прихода сигнала инициализации 11 устройства для вычисления ДПП до момента занесения информации в регистры 8, , , , устройство для вычисления ДПП готово к работе.
УТПП
k
На этапе функционирования на каждом такте работы устройства для вычисления ДПП на вход 4 по синхросигналам, генерируемым через период времени Т, поступают n-разрядные двоичные числа x, .
1
N
t.(k+1).p
t.1
t.N
t.1
t.(N-1)
k
b
УТПП
1
N
k
t.(k+1)
t
ki
k
t.(k+1)
t
t.(k+1).p
t.(k+1).p
k(t-1)
t.(k+1).p
n
n
На основании последовательности указанных чисел конечной длины N производится определенный подкласс дискретных полиномиальных преобразований. Генератор синхросигналов и синхровходы регистров 6,…6, 8, , , , 10,…10, 16…16 на фиг.2, фиг.3 и фиг.4 не указаны. По синхросигналу b-й разряд каждого из значений x, , , сохраняется поразрядно в N-разрядном регистре сдвига 6, , (см. фиг.2). В результате, через период времени N·Т, когда в регистрах сдвига 6…6 будет находиться последовательность {x},  длины N, элементы указанной последовательности параллельно поступают на входы 13 на блоков 3, вычисления системы функций ДПП, φ(x), , , (см. фиг.3). В случае, если на вход 13 блока 3, вычисления системы функций ДПП, , являющийся также управляющим входом мультиплексора 9 «2 в 1», поступает значение d, представленное n-разрядным двоичным числом, то на выход мультиплексора 9 «2 в 1» поступает p-й разряд значения функции φ(d), который был сохранен в d-м разряде параллельного регистра 8 значений разрядов функции на этапе инициализации, , , , .
УТПП
t.(k+1).p
t.(k+1)
t.(k+1)
t.(k+1)
t
t.1
t.(N/2)
n
Во время поступления следующего, (N·Т+1)-го, синхросигнала значения с выходов каждого из мультиплексоров 9 «2 в 1» сохраняются в параллельных f-разрядных регистрах 10, , , которые затем поступают на выходы 14 каждого из блоков 3, вычисления системы функций ДПП,  (см. фиг.3). Значения на выходах 14 являются также входами комбинационных сумматоров 1 для N f-разрядных двоичных чисел, , и поступают на сумматоры 15,…,15 (см. фиг.4).
УТПП
t.1
t.(N/2)
t.1
t.(N/2)
Во время поступления синхросигнала под номером (N·Т+2) значения частичных сумм, снимаемых с выходов сумматоров 15,…,15, сохраняются в параллельных регистрах 16,…,16 разрядности (f+1), соответственно,  (см. фиг.4)
УТПП
t.(N-1)
t.(N-1)
2
t
Во время поступления синхросигнала под номером (N·Т +logN) значение, снимаемое с выхода сумматора 15, сохраняется в параллельном регистре 16 разрядности (f-1+logN) и поступает на выход 5, который является одним из t выходов устройства для вычисления ДПП, .
УТПП
В результате, за (N·Т +logN) тактов работы устройства для вычисления ДПП возможно вычисление значений Т элементов образов тля заданного подкласса дискретных полиномиальных преобразований. При этом минимальный интервал времени между поступлениями синхросигналов рассчитывается согласно формуле вида
,
R
t.(k+1).p
t.(k+1)
1
N
t.(k+1).p
t.(k+1)
t.(k+1)
УТПП
n
где  и T - оценки максимального времени задержки мультиплексоров 9 «2 в 1», двухвходового сумматора 15 для (f-1+logN) - разрядных двоичных чисел , , , а также максимального времени задержки функционирования регистров: N-разрядных регистров сдвига 6,…,6 параллельных регистров 8, значений разрядов функций, параллельных f-разрядных регистров 10, и параллельных регистров 16, , , , соответственно. Величина Т позволяет определить верхнюю оценку частоты работы устройства для вычисления ДПП -.
2
1
T
УТПП
При этом значения n-разрядных двоичных элементов обрабатываемых последовательностей, а также значения элементов образов заданного подкласса дискретных полиномиальных преобразований, поступают на n-разрядный вход 4 и снимаются с (f-1+logN)-разрядных выходов 5,…,5 устройства для вычисления ДПП, соответственно, по синхросигналам, поступающим через период времени не менее, чем Т.
Таким образом, предлагаемое устройство для вычисления ДПП по сравнению с прототипом позволяет производить вычисление широкого класса дискретных полиномиальных преобразований, задаваемых системой полиномиальных функций вида (1), при использовании конвейерной обработки данных с сохранением промежуточных результатов, что позволяет обеспечивать высокое быстродействие предлагаемого устройства.
Источники информации
1. Крот A.M. Дискретные модели динамических систем на основе полиномиальной алгебры. Минск: Навука i тэхника, 1990. 311 с.
2. Калабеков Б.А. Микропроцессоры и их применение в системах передачи и обработки сигналов: учебн. пособие для вузов. М.: Радио и связь, 1988. 312 с.
3. Блейхуд Р. Теория и практика кодов, контролирующих ошибки. Пер. с англ. под ред. Зигангирова К.Ш. М.: Мир, 1986. 576 с.
(11)
(13)
4. RU2190874 С2 G06F 17/14, 20.07.1999.
(11)
(13)
5. RU2290687 C1 G06F 17/14 (2006.01), 31.05.2005.
(11)
(13)
6. Ru 2399152 С2 Н03Н 17/04, Н03Н 17/06, Н03Н 21/00 (2006.01), 12.03.2008.
(11)
(13)
7. RU 2421781 C1 G06F 7/72, Н03М 7/18 (2006.01), 19.10.2009.