устройство для вычисления дискретных полиномиальных преобразований

Классы МПК:G06F17/14 преобразования Фурье, Уолша или аналогичные преобразования
Автор(ы):,
Патентообладатель(и):Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Казанский национальный исследовательский технический университет им. А.Н. Туполева - КАИ" (КНИТУ-КАИ) (RU)
Приоритеты:
подача заявки:
2012-11-16
публикация патента:

Изобретение относится к области цифровой обработки сигналов и может быть использовано при обработке видео- и аудиосигналов в реальном масштабе времени. Техническим результатом является обеспечение выполнения различных подклассов дискретных полиномиальных преобразований (ДПП) и для реализации КИХ-фильтров с использованием заданной системы функций на конечном интервале длины N=2 c. Устройство содержит систему из n N-разрядных регистров сдвига, Т блоков вычисления системы функций ДПП и Т блоков комбинационных сумматоров для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел, где Т - количество элементов образа заданного подкласса ДПП, представленных (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -1+log2N)-разрядными двоичными числами, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 =n+r, n - количество двоичных разрядов входа устройства, r - максимальное количество двоичных разрядов постоянных коэффициентов для заданного подкласса ДПП. 4 ил. устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694

устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694

Формула изобретения

Устройство для вычисления дискретных полиномиальных преобразований, содержащее T комбинационных сумматоров для N f-разрядных двоичных чисел с одним выходом на (f+log2N) разрядов каждый, где T - количество элементов образа заданного подкласса дискретных полиномиальных преобразований (далее - ДПП), представленных (f+log2N)-разрядными двоичными числами, N=2c - длина интервала последовательности, над которой выполняется ДПП, c - целое положительное число, f=n+r, r - максимальное количество двоичных разрядов постоянных коэффициентов для заданного подкласса ДПП, n - количество двоичных разрядов входа устройства, отличающееся тем, что в него введены: система из n N-разрядных регистров сдвига с входом на n двоичных разрядов, с синхровходом и с N n-разрядными двоичными выходами, а также T блоков вычисления системы функций ДПП с N n-разрядными двоичными входами, с T входами значений разрядов функций ДПП на N·f·2n двоичных разрядов каждый, с синхровходом, с входом инициализации и с N выходами на f двоичных разрядов каждый, причем вход системы из n N-разрядных регистров сдвига является входом устройства на n двоичных разрядов, каждый из N выходов системы из n N-разрядных регистров сдвига соединен с N n-разрядными двоичными входами каждого из T блоков вычисления системы функций ДПП, при этом N f-разрядных выходов каждого из T блоков вычисления системы функций ДПП соединены с N входами соответствующего ему комбинационного сумматора для N f-разрядных двоичных чисел, (f+log2 N)-разрядные выходы каждого из комбинационных сумматоров для N f-разрядных двоичных чисел являются выходами устройства для вычисления ДПП, синхровход системы из n N-разрядных регистров сдвига, синхровход каждого из T блоков вычисления системы функций ДПП и синхровход каждого из T комбинационных сумматоров для N f-разрядных двоичных чисел является синхровходом устройства для вычисления ДПП, каждый вход значений разрядов функций ДПП t-то блока вычисления системы функций ДПП соединен с t-м входом значений разрядов функций ДПП на N·f·2n двоичных разрядов устройства для вычисления ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , а вход инициализации каждого из Т блоков вычисления системы функций ДПП является входом инициализации устройства, система из n N-разрядных регистров сдвига содержит n N-разрядных регистров сдвига с последовательным входом, синхровходом и N двоичными выходами каждый, причем последовательный вход каждого N-разрядного регистра сдвига соединен с соответствующим двоичным разрядом n-разрядного входа устройства для вычисления ДПП, синхровход каждого из n N-разрядных регистров сдвига соединен с синхровходом устройства для вычисления ДПП, а i-e разряды N-разрядных регистров сдвига являются i-м выходом системы из n N-разрядных регистров сдвига на n двоичных разрядов каждый, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , t-й блок вычисления системы функций ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , содержит N·f параллельных регистров значений разрядов функций разрядности 2n каждый с синхровходом, N·f мультиплексоров «2n в 1», N параллельных f-разрядных регистров с синхровходом, причем синхровход каждого из параллельных регистров значений разрядов функций соединен с входом инициализации устройства для вычисления ДПП, вход данных каждого из N·f параллельных регистров значений разрядов функций соединен с соответствующими входами значений разрядов функций ДПП на N·f·2n двоичных разрядов устройства для вычисления ДПП, а выходы данных каждого из N·f параллельных регистров значений разрядов функций соединены с входами данных соответствующих им мультиплексоров «2 n в 1», управляющие входы каждого из f элементов i-й группы мультиплексоров «2n в 1» соединены с i-м входом n-разрядных двоичных чисел t-го блока вычисления системы функций ДПП, выходы данных i-й группы мультиплексоров «2n в 1» соединены с входом данных i-го параллельного f-разрядного регистра, синхровход каждого из которых соединен с синхровходом устройства для вычисления ДПП, а выход данных каждого из которых является i-м выходом f-разрядных двоичных чисел t-го блока вычисления системы функций ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , t-й комбинационный сумматор для N f-разрядных двоичных чисел, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , содержит (N-1) двухвходовых сумматора, из которых 2 u-2-j имеют разрядность (f+j), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , u=1+logN, а также (N-1) параллельных регистра с синхровходом, из которых 2u-2-j имеют разрядность (f+j+1), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , u=1+logN, N входов на f двоичных разрядов каждый, причем каждый из N входов на f двоичных разрядов N/2 двухвходовых сумматоров соединен с N выходами t-го блока вычисления системы функций ДПП разрядности f, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , выходы N/2 двухвходовых сумматоров соединены с входами N/2 (f+1)-разрядных параллельных регистров, выходы которых, в свою очередь, соединены с входами N/4 двухвходовых сумматоров, выходы которых соединены с входами N/4 (f+2)-разрядных параллельных регистров, выходы N/2d (f+d)-разрядных параллельных регистров соединены с входами N/2d+1 двухвходовых сумматоров, выходы которых соединены с входами N/2 d+1 (f+d+1)-разрядных параллельных регистров, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , выходы двух (f-1+log2N)-разрядных параллельных регистров соединен с входами двухвходового сумматора, выход которого соединен с входом параллельного регистра разрядности (f +log2N), выход которого является выходом t-го комбинационного сумматора для N f-разрядных двоичных чисел, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , синхровходы каждого из (N-1)-го параллельного регистра соединены с синхровходом устройства для вычисления ДПП.

Описание изобретения к патенту

Заявляемое изобретение относится к области цифровой обработки сигналов (ЦОС) различного назначения и может быть использовано при обработке видео- и аудиосигналов в реальном масштабе времени. Для решения задач ЦОС различного назначения применимы определенные подклассы дискретных полиномиальных преобразований (ДПП). Например, дискретных ортогональных (унитарных) преобразований - дискретного преобразования Фурье (ДПФ) и Хартли (ДПХ), как прямого, так и обратного [1, стр.21], а также цифровых фильтров с импульсной характеристикой конечной длительности (КИХ-фильтров) [2, стр.357].

Существенной проблемой при проектировании устройств для выполнения ДПП является выбор такой его структуры, при которой обеспечивается как высокое быстродействие, так и универсальность данного устройства применительно к реализации заданного подкласса ДПП. Одним из способов повышения быстродействия указанного устройства является реализация конвейерной обработки данных с сохранением промежуточных результатов. Для устройств вычислительной техники (ВТ), реализованных указанным способом, максимальное быстродействие определено как сумма максимального времени задержки функционирования одной из ступеней конвейера и максимального времени задержки одного из регистров, сохраняющих промежуточные результаты. Универсальность устройства для вычисления ДПП достигается за счет возможности варьирования элементов системы функций устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 ki(xk), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 на конечном интервале длины N, N=2c вида [1, стр.21]

устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694

Согласно [2, стр.357], КИХ-фильтр (нерекурсивный цифровой фильтр) реализуем на основе (1) для системы функций устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 k(xk)=ak·х k на конечном интервале длины N, N=2c, где x k - значение сигнала в k-й момент времени, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , с - целые положительные значения. Согласно [3, стр.157], данная система функций (1) в совокупности с определенным коэффициентами ak, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , образует «фильтрующий» полином.

Известна реализация быстрого преобразования Хартли и Фурье при использовании конвейеризации процесса вычисления базовой операции («бабочки») алгоритма быстрого ДПФ и ДПХ [RU(11) 2190874(13) , C2 G06F 17/14, 20.07.1999]. Недостатком данной реализации является ограничение по количеству выполняемых дискретных преобразований.

Известна реализация ДПФ на конечном интервале N=2c при использовании процессоров, для которой обеспечивается максимальное быстродействие за счет оптимизации процесса извлечения коэффициентов ДПФ из памяти [RU (11) 2290687(13), C1 G06F 17/14 (2006.01), 31.05.2005]. Недостатком данной реализации является ограничение по количеству выполняемых дискретных преобразований.

Известна реализация универсального цифрового фильтра с программируемой структурой, которая, помимо КИХ-фильтра, позволяет реализовать и авторегрессионный фильтр [RU(11) 2399152(13), C2 H03H 17/04, H03H 17/06, H03H 21/00 (2006.01), 12.03.2008]. Недостатки данной реализации - ограничение по количеству выполняемых дискретных преобразований и низкое быстродействие.

Наиболее близким по технической сущности к заявляемому изобретению является устройство для формирования остатка по заданному модулю, содержащее Т блоков формирования частичных остатков с сохранением вычисленных результатов, два параллельных регистра, мультиплексор, компаратор и блок вычитания, причем t-й блок формирования частичных остатков, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , содержит комбинационный сумматор с (n-p) (p+1)-разрядными входами и (p+q)-разрядным выходом, где n-разрядность чисел, (p+1)-разрядность заданного модуля, q=]log2(n-p)[ [RU(11) 2421781(13), C1 G06F 7/72, H03M 7/18 (2006.01), 19.10.2009]. Данное устройство позволяет производить конвейерное вычисление значений остатков от деления по заданному модулю с сохранением промежуточных результатов (частичных остатков), следствием чего является существенное увеличение быстродействия данного устройства при обработке потока чисел. Недостаток данного устройства - ограничение по количеству выполняемых дискретных преобразований.

К причинам, препятствующим достижению технического результата при использовании известного устройства, относится ограничение по количеству выполняемых ими дискретных преобразований, что существенно ограничивает область его применения.

Технический результат заключается в расширении функциональных возможностей устройства для вычисления ДПП, структура которого может быть настроена для выполнения различных подклассов ДПП (например, Фурье, Уолша, Хаара, Хартли, косинусного и т.п.), а также для реализации КИХ-фильтров. Настройка производится путем задания системы функций на конечном интервале длины N и заключается в занесении всевозможных значений функций устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 ki(xk) при заданных значениях x k, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , в параллельные регистры значений разрядов функций каждого из блоков вычисления системы функций ДПП, а также в изменении количества блоков вычисления системы функций ДПП и блоков комбинационных сумматоров для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел. Количество каждого из указанных блоков определено как Т - количество элементов образа заданного подкласса ДПП. В устройстве реализовано параллельное вычисление каждого из Т элементов указанных подклассов ДПП, причем в каждом из блоков вычисления системы функций ДПП и в каждом из комбинационных сумматоров для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел производится конвейерное вычисление с сохранением промежуточных результатов.

Технический результат достигается тем, что в устройство для вычисления дискретных полиномиальных преобразований, содержащее t-й комбинационный сумматор для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел с одним выходом на (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +log2N) разрядов каждый, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , введены система из n N-разрядных регистров сдвига с входом на n двоичных разрядов, с синхровходом и с N n-разрядными двоичными выходами, а также Т блоков вычисления системы функций ДПП с N n-разрядными двоичными входами, с Т входами значений разрядов функций ДПП на N·устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 ·2n двоичных разрядов каждый, с синхровходом, с входом инициализации и с N выходами на устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 двоичных разрядов каждый, причем вход системы из n N-разрядных регистров сдвига является входом устройства на n двоичных разрядов, каждый из N выходов системы из n N-разрядных регистров сдвига соединен с N n-разрядными двоичными входами каждого из Т блоков вычисления системы функций ДПП, при этом N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных выходов каждого из Т блоков вычисления системы функций ДПП соединены с N входами соответствующего ему комбинационного сумматора для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел, (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +log2N)-разрядные выходы каждого из комбинационных сумматоров для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел являются выходами устройства для вычисления ДПП, синхровход системы из n N-разрядных регистров сдвига, синхровход каждого из Т блоков вычисления системы функций ДПП и синхровход каждого из Т комбинационных сумматоров для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел является синхровходом устройства для вычисления ДПП, каждый вход значений разрядов функций ДПП t-го блока вычисления системы функций ДПП соединен с t-м входом значений разрядов функций ДПП на N·устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 ·2n двоичных разрядов устройства для вычисления ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , а вход инициализации каждого из Т блоков вычисления системы функций ДПП является входом инициализации устройства, система из n N-разрядных регистров сдвига содержит n N-разрядных регистров сдвига с последовательным входом, синхровходом и N двоичными выходами каждый, причем последовательный вход каждого N-разрядного регистра сдвига соединен с соответствующим двоичным разрядом n-разрядного входа устройства для вычисления ДПП, синхровход каждого из n N-разрядных регистров сдвига соединен с синхровходом устройства для вычисления ДПП, а i-е разряды N-разрядных регистров сдвига являются i-м выходом системы из n N-разрядных регистров сдвига на n двоичных разрядов каждый, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , t-й блок вычисления системы функций ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , содержит N·устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 параллельных регистров значений разрядов функций разрядности 2n каждый с синхровходом, N·устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 мультиплексоров «2n в 1», N параллельных устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных регистров с синхровходом, причем синхровход каждого из параллельных регистров значений разрядов функций соединен с входом инициализации устройства для вычисления ДПП, вход данных каждого из N·устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 параллельных регистров значений разрядов функций соединен с соответствующими входами значений разрядов функций ДПП на N·устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 ·2n двоичных разрядов устройства для вычисления ДПП, а выходы данных каждого из N·устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 параллельных регистров значений разрядов функций соединены с входами данных соответствующих им мультиплексоров «2 n в 1», управляющие входы каждого из устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 элементов i-й группы мультиплексоров «2n в 1» соединены с i-м входом n-разрядных двоичных чисел t-го блока вычисления системы функций ДПП, выходы данных i-й группы мультиплексоров «2n в 1» соединены с входом данных i-го параллельного устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядного регистра, синхровход каждого из которых соединен с синхровходом устройства для вычисления ДПП, а выход данных каждого из которых является i-м выходом устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел t-го блока вычисления системы функций ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , t-й комбинационный сумматор для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , содержит (N-1) двухвходовых сумматора, из которых 2 u-2-j имеют разрядность (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +j); устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , u=1+logN, а также (N-1) параллельных регистра с синхровходом, из которых 2u-2-j имеют разрядность (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +j+1), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , u=1+logN, N входов на устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 двоичных разрядов каждый, причем каждый из N входов на устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 двоичных разрядов N/2 двухвходовых сумматоров соединен с N входами t-го блока вычисления системы функций ДПП разрядности устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , выходы N/2 двухвходовых сумматоров соединены с входами N/2 (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +1)-разрядных параллельных регистров, выходы которых, в свою очередь, соединены с входами N/4 двухвходовых сумматоров, выходы которых соединены с входами N/4 (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +2)-разрядных параллельных регистров, выходы N/2d (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +d)-разрядных параллельных регистров соединены c входами N/2d+1 двухвходовых сумматоров, выходы которых соединены с входами N/2d-1 (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +d+1)-разрядных параллельных регистров, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , выходы двух (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -1+log2N)-разрядных параллельных регистров соединены с входами двухвходового сумматора, выход которого соединен с входом параллельного регистра разрядности (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +log2N), выход которого является выходом t-го комбинационного сумматора для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , синхровходы каждого из (N-1)-го параллельного регистра соединены с синхровходом устройства для вычисления ДПП.

Каждый из Т блоков вычисления системы функций ДПП может быть настроен для реализации произвольной системы функций устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 ki(xk) от заданных значений x k, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , соответствующей указанному подклассу ДПП (см. выше). При этом для комплексной и для вещественной составляющей каждого элемента образа заданного подкласса ДПП применимы отдельные пары блоков вычисления системы функций ДПП и комбинационных сумматоров для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел. Например, для реализации ДПФ на конечном интервале N требуется T=2N указанных блоков, для реализации ДПХ-Т=N пар указанных блоков, а для реализации КИХ-фильтра порядка N достаточно одной пары данных блоков, соответственно. Кроме того, внутри каждого из Т комбинационных сумматоров для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел предусмотрена возможность сохранения промежуточных результатов, частичных сумм, в параллельных регистрах с синхровходом.

Схема устройства для вычисления дискретных полиномиальных преобразований представлена на фиг.1, а схемы системы из n N-разрядных регистров сдвига, t-го блока вычисления системы функций ДПП и t-го комбинационного сумматора для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , приведены на фиг.2, фиг.3 и фиг.4, соответственно.

Устройство для вычисления ДПП, содержит Т комбинационных сумматоров 11, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , 1T для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел, систему 2 из n N-разрядных регистров сдвига, блоки 3t вычисления системы функций ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , причем каждая из данных функций представлена устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядными двоичными числами, где Т - количество элементов образа заданного подкласса ДПП, представленных (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +log2N)-разрядными двоичными числами, N=2 c - длина интервала последовательности, над которой выполняется ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 =n+r, r - максимальное количество двоичных разрядов постоянных коэффициентов для заданного подкласса ДПП, n - количество двоичных разрядов входа устройства, причем вход системы 2 из n N-разрядных регистров сдвига, представленный n-разрядным двоичных значением xk, является входом 4 устройства для вычисления ДПП, синхровход системы 2 из n N-разрядных регистров сдвига, а также каждого из блоков 3t вычисления системы функций ДПП и каждого из комбинационных сумматоров 1t для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , является синхровходом устройства для вычисления ДПП (на фиг.1 не показаны), вход инициализации каждого из блоков 3 t вычисления системы функций ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , является входом инициализации устройства для вычисления ДПП (на фиг.1 не показаны), вход значений разрядов функции ДПП соответствующего блока 3t вычисления системы функций ДПП на N·устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 ·2n двоичных разрядов является t-м входом значений разрядов функции ДПП устройства для вычисления ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 (на фиг.1 не показаны), выход системы 2 из n N-разрядных регистров сдвига, представленный n·N-разрядным двоичным числом, соединен с входами каждого из блоков 3t вычисления системы функций ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , выход каждого из блоков 3t вычисления системы функций ДПП, представленный устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядным двоичным значением, соединен с входом соответствующего комбинационного сумматора 1t для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , а выход каждого комбинационного сумматора 1t для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел, определенный как (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +log2N)-разрядное двоичное число, является выходом 5t устройства для вычисления ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 .

На фиг.2 представлена система 2 из n N-разрядных регистров сдвига, которая включает n N-разрядных регистров сдвига 6b, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , причем последовательные входы каждого из регистров сдвига 6b, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , соединены с соответствующим двоичным разрядом входа устройства 4 для вычисления ДПП - 4b, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , синхровходы каждого из N-разрядных регистров сдвига 6 b, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , соединены с синхровходом устройства для вычисления ДПП (на фиг.2 не показаны), а выходы 7b,i, каждого из N-разрядных регистров сдвига 6b, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , образуют i-й выход системы 2 из n N-разрядных регистров сдвига на n двоичных разрядов каждый, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 .

На фиг.3 представлен один из блоков 3 t вычисления системы функций ДПП вида устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 k(t-1)(xk), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , который включает N·устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 параллельных регистров 8t.(k+1)p, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , значений p-го разряда функции устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 k(t-1)(xk) разрядности 2n каждый, N·устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 мультиплексоров 9t.(k+1).p «2n в 1» и N параллельных устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных регистров 10t.(k+1), причем синхровход каждого из параллельных регистров 8t.(k+1).p значений разрядов функций, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , соединен с входом инициализации 11 устройства для вычисления ДПП, каждый вход данных параллельного регистра 8t(k+1)p значений разрядов функций ДПП устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 k(t-1)(xk), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , соединен с соответствующим входом 12t.(k+1).p значений p-го разряда указанных функции на N·устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 ·2n двоичных разрядов, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , выход каждого из параллельных регистров 8t(k+1).p соединен с соответствующими входами данных мультиплексора 9 t.(k+1)p «2n в 1», тогда как управляющие входы каждого мультиплексора «2n в 1» из группы 9t.(k+1).1 устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 9t.(k+1).устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , соединены с n-разрядным входом 13t.(k+1) значений xk, разряды каждого из которых соединены с двоичными выходами 71.(k+1)устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 7n.(k+1) системы 2 из n N-разрядных регистров сдвига (см. фиг.2), выходы мультиплексоров 9t.(k+1).1 устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 9t.(k+1).устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 «2n в 1» соединены с входами параллельных устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных регистров 10t.(k+1), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , синхровход каждого из которых соединен с синхровходом устройства для вычисления ДПП (на фиг.3 не указаны), а выходы параллельных устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных регистров 10t.(k+1) являются устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядными выходами 14t.(k+1) блока 3t вычисления системы функций ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , соответственно.

На фиг.4 изображен комбинационный сумматор 1t, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , который содержит (N-1) двухвходовых сумматора 15 t.1устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 15t.(N-1), из которых 2u-2-j имеют разрядность (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +j), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , u=1+logN, а также (N-1) параллельных регистра 16 t.1устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 16t.(N-1) с синхровходом, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , из которых 2u-2-j имеют разрядность (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +j+1), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , u=1+logN, N входов на устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 двоичных разрядов каждый, причем каждый из N входов на устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 двоичных разрядов N/2 двухвходовых сумматоров 15t.1 устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 15t.(N/2) соединен с N входами блока 3t. вычисления системы функций ДПП разрядности устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , выходы N/2 двухвходовых сумматоров 15t.1устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 15t.(N/2) соединены с входами N/2 (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +1)-разрядных параллельных регистров 16t.1устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 16t.(N/2), выходы которых, в свою очередь, соединены с входами N/4 двухвходовых сумматоров устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , D1=N/2, выходы которых соединены с входами N/4 (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +2)-разрядных параллельных регистров устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , выходы N/2d (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +d)- разрядных параллельных регистров устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , соединены с входами N/2d+1 двухвходовых сумматоров устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , выходы которых соединены с входами N/2d+1 (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +d+1)-разрядных параллельных регистров устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , выходы двух (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -1+log2N)-разрядных параллельных регистров 16 t(N-3) 16t(N-2) соединены с входами двухвходового сумматора 15t.(N-1), выход которого соединен с входом параллельного регистра 16t.(N-1) разрядности (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +log2N), выход которого является выходом 5 t t-го комбинационного сумматора для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , синхровходы каждого из (N-1)-го параллельного регистра 16t.1устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 16t.(N-1) соединены с синхровходом устройства для вычисления ДПП (на фиг.4 не указаны).

Рассмотрим устройство для вычисления дискретных полиномиальных преобразований в работе.

В предлагаемом устройстве на этапе инициализации в параллельные регистры 8t.(k+1).p значений разрядов функции разрядности 2n по сигналу 11 инициализации параллельно заносятся соответствующие значения p-x двоичных разрядов значения функций устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 k(t-1)(xk) системы (1), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 . При этом значение в d-м разряде каждого из регистров 8t.(k+1).p соответствует p-му разряду значения функции устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 k(t-1)(d), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 . Через период времени от момента прихода сигнала инициализации 11 устройства для вычисления ДПП до момента занесения информации в регистры 8t.(k+1).p, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления ДПП готово к работе.

На этапе функционирования на каждом такте работы устройства для вычисления ДПП на вход 4 по синхросигналам, генерируемым через период времени ТУТПП, поступают n-разрядные двоичные числа xk, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 . На основании последовательности указанных чисел конечной длины N производится определенный подкласс дискретных полиномиальных преобразований. Генератор синхросигналов и синхровходы регистров 61, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 6N, 8t.(k+1).p, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , 10t.1, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 10t.N, 16t.1, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 16t.(N-1) на фиг.2, фиг.3 и фиг.4 не указаны. По синхросигналу b-й разряд каждого из значений xk , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , сохраняется поразрядно в N-разрядном регистре сдвига 6b, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 (см. фиг.2). В результате, через период времени N·Т УТПП, когда в регистрах сдвига 61устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 6N будет находиться последовательность {x k}, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 длины N, элементы указанной последовательности параллельно поступают на входы 13t.(k+1) блоков 3t вычисления системы функций ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 ki(xk), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , (см. фиг.3). В случае, если на вход 13t.(k+1) блока 3t вычисления системы функций ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , являющийся также управляющим входом мультиплексора 9 t.(k+1).p «2n в 1», поступает значение d, представленное n-разрядным двоичным числом, то на выход мультиплексора 9t.(k+1).p «2n в 1» поступает p-й разряд значения функции устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 k(t-1)(d), который был сохранен в d-м разряде параллельного регистра 8t.(k+1).p значений разрядов функции на этапе инициализации, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 .

Во время поступления следующего, (N·Т УТПП+1)-го, синхросигнала значения с выходов каждого из мультиплексоров 9t.(k+1).p «2n в 1» сохраняются в параллельных устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных регистрах 10t.(k+1), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , которые затем поступают на выходы 14t.(k+1) каждого из блоков 3t вычисления системы функций ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 (см. фиг.3). Значения на выходах 14t.(k+1) являются также входами комбинационных сумматоров 1t для N устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных двоичных чисел, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , и поступают на сумматоры 15t.1, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , 15t.N/2 (см. фиг.4).

Во время поступления синхросигнала под номером (N·ТУТПП +2) значения частичных сумм, снимаемых с выходов сумматоров 15 t.1, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , 15t.N/2, сохраняются в параллельных регистрах 16t.1, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , 16t.N/2 разрядности (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +1), соответственно, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , (см. фиг.4) и т.д.

Во время поступления синхросигнала под номером (N·ТУТПП+d+2) значения частичных сумм, снимаемых с выходов сумматоров устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , сохраняются в параллельных регистрах устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 разрядности (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +d+1), соответственно, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 .

Во время поступления синхросигнала под номером (N·ТУТПП+2+logN) значение, снимаемое с выхода сумматора 15t.(N-1), сохраняется в параллельном регистре 16t.(N-1) разрядности (устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +log2N) и поступает на выход 5t, который является одним из t выходов устройства для вычисления ДПП, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 .

В результате, за (N·ТУТПП +2+logN) тактов работы устройства для вычисления ДПП возможно вычисление значений Т элементов образов для заданного подкласса дискретных полиномиальных преобразований. При этом минимальный интервал времени между поступлениями синхросигналов рассчитывается согласно формуле вида

ТУТПП=max(T MX, T(устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 ))+TR,

где TMX, T(устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 ) и TR - оценки максимального времени задержки мультиплексоров 9t.(k+1).p «2n в 1», двухвходового сумматора 15t.(k+1) для устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , а также максимального времени задержки функционирования регистров: N-разрядных регистров сдвига 61, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , 6N, параллельных регистров 8t(k+1).p значений разрядов функций, параллельных устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 -разрядных регистров 10t.(k+1) и параллельных регистров 16t.(k+1), устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , соответственно. Величина ТУТПП позволяет определить верхнюю оценку частоты работы устройства для вычисления ДПП - устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 .

При этом значения n-разрядных двоичных элементов обрабатываемых последовательностей, а также значения элементов образов заданного подкласса дискретных полиномиальных преобразований поступают на n-разрядный вход 4 и снимаются с Т(устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 +log2N)-разрядных выходов 51, устройство для вычисления дискретных полиномиальных преобразований, патент № 2517694 , 5T устройства для вычисления ДПП, соответственно, по синхросигналам, поступающим через период времени не менее чем ТУТПП.

Таким образом, предлагаемое устройство для вычисления ДПП по сравнению с прототипом позволяет производить вычисление широкого класса дискретных полиномиальных преобразований, задаваемых системой полиномиальных функций вида (1), при использовании конвейерной обработки данных с сохранением промежуточных результатов, что позволяет обеспечивать высокое быстродействие предлагаемого устройства.

Источники информации

1. Крот A.M. Дискретные модели динамических систем на основе полиномиальной алгебры. Минск: Навука i тэхника, 1990. 311 с.

2. Калабеков Б.А. Микропроцессоры и их применение в системах передачи и обработки сигналов: учебн. пособие для вузов. М.: Радио и связь, 1988. 312 с.

3. Блейхуд Р. Теория и практика кодов, контролирующих ошибки. Пер. с англ. под ред. Зигангирова К.Ш. М.: Мир, 1986. 576 с.

4. RU(11) 2190874(13), C2 G06F 17/14, 20.07.1999.

5. RU(11) 2290687 (13), C1 G06F 17/14 (2006.01), 31.05.2005.

6. RU(11) 2399152(13), C2 H03H 17/04, H03H 17/06, H03H 21/00 (2006.01), 12.03.2008.

7. RU (11) 2421781(13), C1 G06F 7/72, H03M 7/18 (2006.01), 19.10.2009.

Класс G06F17/14 преобразования Фурье, Уолша или аналогичные преобразования

способ измерения времени прихода сигнала и устройство для его реализации -  патент 2524843 (10.08.2014)
бортовой спецвычислитель -  патент 2522852 (20.07.2014)
звуковое кодирующее устройство и декодер для кодирования декодирования фреймов квантованного звукового сигнала -  патент 2507572 (20.02.2014)
эффективные аппроксимации с фиксированной запятой прямого и обратного дискретных косинусных преобразований -  патент 2496139 (20.10.2013)
способ построения спектра n-мерных неразделимых цифровых сигналов -  патент 2484523 (10.06.2013)
устройство для приема дискретных сигналов -  патент 2480839 (27.04.2013)
способ анализа электроэнцефалограмм -  патент 2467384 (20.11.2012)
способ цифровой рекурсивной полосовой фильтрации и цифровой фильтр для реализации этого способа -  патент 2460130 (27.08.2012)
структура преобразования с масштабированными и немасштабированными интерфейсами -  патент 2460129 (27.08.2012)
эффективный способ проектирования набора фильтров для mdct/imdct в приложениях для кодирования речи и аудиосигналов -  патент 2451998 (27.05.2012)
Наверх