Изобретение относится к области автоматики и вычислительной техники и может быть использовано для спектрального и корреляционного анализа случайных процессов, для цифровой фильтрации, сжатия информации в технике, связи.
Технический результат заключается в повышении производительности процессора быстрого преобразования сигналов по Уолшу с упорядочением по Адамару за счет распараллеливания входного потока данных путем построения схемы процессора как вычислительной системы, полученной на основе регулярной гомоморфной свертки с коэффициентом граф-схемы реализуемого алгоритма.
Суть гомоморфной свертки заключается в объединении вершин граф-схемы алгоритма. При этом сохраняются дуги графа, инциндентные хотя бы одной объединяемой вершине, кратные дуги объединяются в одну, дуги инциндентные обеим объединяемым вершинам опускаются. Коэффициент свертки определяет число вершин графа в каждом ярусе ярусно-параллельной формы, в которой представлена граф-схема алгоритма. Регулярная свертка характеризуется тем, что закон, по которому она производится, постоянен и не зависит от номера яруса параллельной формы. При таком объединении вычислительный блок, соответствующий объединенным вершинам, выполняет все операции, им соответствующие.
На фиг. 1 приведена структура процессора, на фиг. 2 функциональная схема блока регистров, на фиг. 3 функциональная схема блока управления, на фиг. 4 функциональная схема модуля запуска, на фиг. 5 функциональная схема процессорного элемента первого типа, на фиг. 6, 7 функциональные схемы процессорных элементов второго типа, на фиг. 8 функциональная схема процессорного элемента третьего типа, на фиг. 9, 10, 11, 12 временные диаграммы, иллюстрирующие работу процессора, на фиг. 13 граф-схема реализуемого алгоритма.
Процессор (фиг. 1) содержит блок 1 регистров, блок 2 управления, группу первых 3.i (i 1,2, ) вторых 4.i.j и третьих 5.k.j n log2N, где N длина выборки отсчетов cигналов) процессорных элементов, информационный 6 вход, тактовый 7 вход, управляющий 8 вход, группу 9.m (m=1.8) выходов блока 1 регистров, первый 10.1, второй 10.2, третий 13.1, четвертый 14.1, шестой 12.2, седьмой 13.3, восьмой 12.3, девятый 14.1, десятый 11.1, одиннадцатый 11.2, двенадцатый 14.2.(n+8)-ой 14.(n-3), (n+9)-й 15.1.(2n+10) 15. (n-4) выходы блока управления, группу первых 16.i.j и вторых 17.i.j выходов j-тых процессорных элементов i-тых каскадов, первый и второй каскады составляют процессорные элементы первого типа, третий и четвертый каскады состоят из процессорных элементов второго типа, каскады с пятого по n-тый из третьих процессорных элементов.
Блок 1 регистров (фиг. 2) содержит группу из восьми регистров 18.1.18.8.
Блок управления (фиг. 3) содержит счетчик 19, первый 20 и второй 21 элементы И, JCK триггер 22, группу 23.i.1.23.i.3 модулей запуска, группу 24.1.24.3 триггеров, первую 25.1.25.3 и вторую 26.1.26.3 группы элементов И, группу 27.k(k+1) разрядных счетчиков.
Каждый модуль 23 запуска (фиг. 4) содержит первый 32, второй 33, третий 34, элементы И, первый 35 и второй 36 триггеры.
Каждый процессорный элемент первого типа (фиг. 5) содержит первый 37, второй 38, третий 39 и четвертый 40 регистры, первый 41 и второй 42 коммутаторы, сумматор-вычитатель 43.
Каждый процессорный элемент второго типа (на фиг. 6 приведен пример элемента для третьего, на фиг. 7 элемент четвертого каскада) содержит группу 44.1, 44.2 регистров, регистр 45, сумматор-вычитатель 46.
Каждый процессорный элемент третьего типа (фиг. 8) содержит первый 47, второй 48, третий 49 и четвертый элементы И, первый 51 и второй 52 элементы ИЛИ, первую 53.(2k+1+1), вторую 54.2k+1 группу регистров, регистр 55, третью 56.2k+1 группу регистров, сумматор-вычитатель 57.
Блок 1 регистров предназначен для приема восьми отсчетов входного сигнала и формирования из них входного массива для последующей обработки на процессорных элементах первого каскада. В исходном состоянии все регистры обнулены (цепи установки исходного состояния условно не показаны). Поступающий на вход 6 процессора отсчет входного сигнала по заднему фронту импульса со входа 7 заносится в первый 18.1 регистр блока. По тактовому импульсу этот отсчет перезаписывается во второй 18.2 регистр, а в первый заносится следующий отсчет. Таким образом, каждые восемь тактов в блоке регистров накапливается массив из восьми отсчетов обрабатываемого сигнала.
Блок 2 управления служит для формирования последовательностей сигналов, управляющих работой процессорных элементов. Модуль 23.i. служит для формирования сигналов разрешающих (запрещающих) работу i-го cегмента блока управления. Модуль функционирует следующим образом. В исходном состоянии первый 35 триггер находится в единичном состоянии, а второй 36 триггер в нулевом. На четвертом входе модуля присутствует единичный сигнал. После того, как на этом входе сигнал поменяет значение, деблокируется элемент И33. Первый импульс, поступивший на третий вход модуля, переведет по переднему фронту первый триггер 35 в нулевое состояние, а по заднему фронту триггер 36 в единичное. Единичный сигнал с прямого выхода триггера 36 деблокирует элемент И34 и на его выход поступит последовательность импульсов со второго входа модуля.
Появление на четвертом входе модуля единичного сигнала свидетельствует о начале режима блокировки. Этот сигнал деблокирует элемент И32. Первый импульс, поступивший с первого входа модуля, и прошедший через элемент И32 переведет в исходное единичное состояние первый 35 триггер. Единичный сигнал на прямом выходе первого 35 триггера переведет второй 36 триггер в нулевое состояние. Далее работа модуля при смене значения сигнала на его четвертом входе повторяется, как описано выше.
Временные диаграммы, иллюстрирующие работу блока управления в целом, приведены на фиг. 9, 10. В исходном состоянии на входе 8 процессора присутствует единичный сигнал, счетчик 19, триггер 22, группа триггеров 24.1.24.3. группа 27.1.27.(n-4) счетчиков находятся в нулевом состоянии. (Цепи установки исходного состояния условно не показаны). Блок управления представляет собой конвейерную систему, содержащую n сегментов и может функционировать в четырех режимах: режиме ожидания, режиме запуска, основном режиме, режиме останова (возвращения в исходное состояние режим ожидания). В режим запуска блок управления переходит после появления на входе 8 нулевого сигнала. При этом на выходе 28 элемента И21 появляется нулевой сигнал, который по инверсному входу разрешает работу счетчика 19 в режиме счета и деблокирует элемент И20. На выходе 31 элемента И20 появляется последовательность импульсов. Каждый импульс этой последовательности формируется в тот момент времени, когда счетчик 19 находится в исходном нулевом состоянии. В исходное состояние счетчик 19 будет переходить по заднему фронту каждого восьмого импульса, поступившего на его счетный вход. Первый импульс с выхода 31 элемента И20 переводит модуль 23.1 запуска в рабочее состояние. На его втором выходе появляется нулевой сигнал. Последовательность импульсов со второго входа модуля поступает на его вход 29.1. По заднему фронту каждого импульса этой последовательности триггер 24.1 переходит в состояние, противоположное тому, в котором он находился. На выходах элементов И25.1 и 26.1 в соответствии с состоянием триггера 24.1 формируются последовательности импульсов. Первый импульс с выхода элемента И25.1 переводит в рабочее состояние модуль 23.2 запуска второго сегмента конвейера. Первый импульс с выхода элемента И 25.2 второго сегмента конвейера переводит в рабочее состояние модуль 23.3 запуска третьего сегмента. Второй и третий сегменты конвейера функционируют аналогично первому. Первый импульс с выхода элемента И25.3 переводит модуль 23.4 запуска четвертой ступени конвейера в рабочее состояние и на его первом 29.4 выходе появляется последовательность импульсов. Перевод модуля 23. i запуска в рабочее состояние осуществляется по первому импульсу последовательности с выхода 29.(i-1) соответствующего модуля 23 (i-1) запуска. Таким образом, режим запуска длится (n-1) такт. На n-том такте функционируют все сегменты конвейера.
Сегменты блока управления с пятого по n-тый функционируют одинаково. Счетчик i-го сегмента работает в режиме деления на 2i-3. Импульс на выходе (2i-3-1) состояния появляется на тот момент, когда счетчик находится в этом состоянии. Блок управления функционирует в основном режиме до тех пор, пока на его управляющем входе 8 не появится нулевой сигнал. С этого момента начинается режим возвращения в исходное состояние.
По заднему фронту импульса с выхода 31 элемента И20 триггер 22 переводится в единичное состояние и сигналом со своего прямого выхода разрешает блокировку модуля 23.1 запуска по импульсу с выхода элемента И26.1. Единичный сигнал с выхода 30.i модуля 23.i запуска блокирует по соответствующему импульсу модуль 23.2 запуска. Далее процесс происходит аналогично, пока не будет заблокирован последний модуль 23.n запуска. При этом на выходе 28 элемента И21 появится единичный сигнал, который запрещает работу счетчика 19 и переводит его в исходное состояние, блокирует элемент И20 и обнуляет триггер 22. В режиме ожидания блок управления будет находиться до тех пор, пока на его управляющем входе 8 не изменится значение сигнала. После этого блок будет функционировать по вышеописанному алгоритму.
Процессорные элементы первого, второго, третьего типов служат для выполнения базовых операций реализуемого алгоритма быстрого преобразования сигналов по Уолшу с упорядочением по Адамару над соответствующими парами отсчетов.
Все процессорные элементы первого типа функционируют одинаково. По заднему фронту импульса в первый 37 и третий 39 регистры заносятся отсчеты сигнала соответственно с первого и третьего информационного входов. По заднему фронту импульса со второго управляющего входа отсчеты со второго и четвертого информационных входов заносятся соответственно во второй 38 и четвертый 40 регистры. Сигналы с третьего управляющего входа позволяют осуществлять выбор отсчетов, поступающих на входы сумматора-вычитателя 43 посредством первого 41 и второго 42 коммутаторов. По нулевому управляющему сигналу на первый и второй входы сумматора-вычитателя поступают отсчеты, записанные соответственно в первом 37 и втором 38, по единичному в третьем 39 и четвертом 40 регистрах. Сумматор-вычитатель 43 реализует по своему первому и второму выходам соответствующие операции:
C A + B, D A B,
где А отсчет, поступивший на его первый вход; В отсчет со второго входа; С и D результаты базовой операции, сформированные на первом и втором выходах сумматора-вычитателя.
Процессорные элементы второго типа функционируют одинаково. По заднему фронту импульса с управляющего входа в регистры 44.1 и 45 заносятся отсчеты сигнала соответственно с первого и второго информационных входов, а отсчет, находившийся в регистре 44.1, перезаписывается в регистр 44.2. По заднему фронту очередного импульса процессорный элемент продолжит функционировать по описанному алгоритму.
Процессорные элементы третьего типа функционируют одинаково. Первые 2n-3 отсчетов сигнала с первого и второго информационного входов при разрешающем нулевом сигнале на первом управляющем входе процессорного элемента, по задним фронтам тактовых импульсов со второго управляющего входа заносятся соответственно в 2n-3 первых 53.i и вторых 54.i регистров. Очередные 2n-3 тактов отсчеты со второго информационного входа по единичному управляющему сигналу с первого управляющего входа заносятся в регистры 56.i третьей группы. Отсчеты сигнала с первого входа последовательно заносятся в регистр 55. Отсчет из регистра 53.i записывается в регистр 53.i+1, отсчет из регистра 54.i заносится в регистр 54.i+1. Отсчет из регистра 54.2n-3 заносится в регистр 53.1, при этом регистры 54.i обнуляются. Таким образом, в каждом i-том такте этого цикла на первом входе сумматора-вычитателя 57 формируются отсчеты, находившиеся к началу цикла в регистре 53.(2n-3-i+1), а на втором входе отсчеты, заносимые в регистр 55. К концу цикла отсчеты из регистров 54.i второй группы оказываются перезаписанными в соответствующих регистрах 53. i первой группы, а вторая группа регистров обнуляется. Очередные 2n-3 такта с первого и второго информационных входов заполняют соответственно первую 53. i и вторую 54.i группы регистров, отсчет из регистра 56.i заносится в регистр 56.i+1, отсчет из регистра 56.2n-3 заносится в регистр 55, при этом регистр 56.i обнуляется. Таким образом, в i-том такте этого цикла на первом входе сумматора-вычитателя 57 формируется отсчет, находившийся к началу цикла в регистре 53.(2n-3 i+1) третьей группы. К концу цикла регистры первой и второй групп оказываются заполненными отсчетами, поступившими соответственно на первые и вторые входы процессорного элемента, а третья группа регистров будет обнулена. Далее процессорный элемент будет функционировать по описанному выше алгоритму.
Временные диаграммы, иллюстрирующие процесс функционирования процессора на примере реализации 32- точечного преобразования, приведены на фиг. 11, 12. Процессор имеет четыре режима работы: ожидания, втягивания, основной, выхода (возвращения в режим ожидания). В исходном состоянии (режим ожидания) на управляющем входе 8 процессора присутствует единичный сигнал, на выходах 10.1 и 10.2 блока управления присутствуют единичные сигналы, на информационный вход 6 процессора последовательность входных отсчетов не поступает. В таком режиме процессор будет находиться до тех пор, пока на управляющем входе 8 значение сигнала не изменится на противоположное. После этого процессор переходит в режим втягивания.
При появлении на входе 8 нулевого сигнала на информационный вход 6 процессора начинает поступать последовательность отсчетов преобразуемого сигнала. В течении первого такта работы в блоке регистров накапливается группа из восьми отсчетов. По заднему фронту первого тактового импульса с выхода 12.1 блока управления отсчеты сформированной группы считываются в регистры первого 3.1.1 и второго 3.1.2 процессорных элементов первого каскада. Далее эти процессорные элементы реализуют операции 1.1 и 1.3 cоответственно, а в блоке регистров формируется очередная группа из восьми отсчетов. По очередному тактовому импульсу с выхода 13.1 блока управления сформированная группа отсчетов заносится регистры процессорных элементов 3.1.3 и 3.1.4. По импульсу с выхода 12.2 блокам управления в первые и третьи регистры процессорных элементов 3.3.1 и 3.2.2 заносятся результаты выполнения базовых операций 1.1 и 1.3. В очередном такте процессорные элементы 3.1.1, 3.1.2, 3.1.3, 3.1.4 реализуют следующие базовые операции: 1.2, 1.4, 1.5, 1.7 cоответственно. В блоке регистров формируется очередная группа отсчетов. По импульсу с выхода 13.2 во вторые и четвертые регистры процессорных элементов 3.2.1 и 3.2.2 второго каскада заносятся результаты выполнения базовых операций соответствующих 3.1.1 и 3.1.2 процессорных элементов первого яруса. По импульсу с выхода 13.2 блока управления в первые и третьи регистры процессорных элементов 3.2.3 и 3.2.4 заносятся результаты выполнения базовых операций, соответствующих 3.1.3 и 3.1.4 процессорных элементов первого каскада. Таким образом, к концу этого такта работы оказываются сформированными условия для функционирования первого 3.2.1 и второго 3.2.2 процессорных элементов второго каскада. В очередном такте функционируют процессорные элементы 3.1.1, 3.1.2, 3.1.3, 3.1.4, 3.2.1, 3.2.2, которые реализуют следующие базовые операции: 1.9, 1.11, 1.6, 1.8, 2.1, 2.3 соответственно.
Результаты выполнения базовых операций в процессорных элементах 3.2.1, 3.2.2 по импульсу с выхода 12.3 заносятся в первые и вторые регистры процессорных элементов 4.1.1 и 4.1.2 третьего каскада, а во вторые и четвертые регистры процессорных элементов 3.2. 3.2.4 по импульсу с выхода 12.2 блока 2 управления заносятся результаты базовых операций, реализованных процессорными элементами 3.1.3, 3.1.4 cоответственно. В очередном такте в работу втягиваются процессорные элементы 4.1.1 и 4.1.2 третьего каскада. В этом также функционируют следующие процессорные элементы: 3.1.1, 3.1.2, 3.1.3, 3.1.4, 3.2.1, 3.2.2, 3.2.3, 3.2.4, 4.1.1, 4.1.2, которые реализуют следующие базовые операции: 1.10, 1.12, 1.13, 1.15, 2.2, 2.4, 2.5, 2.7, 3.1, 3.3 соответственно. Результаты выполнения базовых операций 3.1 и 3.3 заносятся по импульсу с выхода 14 блока управления в первые регистры групп регистров процессорных элементов 4.2.1, 4.2.3, 4.2.2, 4.2.4 соответственно. В очередном такте работы процессора в работу втягиваются процессорные элементы 4.1.3 и 4.1.4 третьего каскада. В конце этого такта по импульсу в выхода 14.1 в первые регистры групп регистров процессорных элементов четвертого каскада заносятся значения результатов выполнения базовых операций 3.2 и 3.4, а во вторые регистры 45.1, j (j 1,4) этих процессорных элементов заносятся результаты выполнения базовых операций 3.5 и 3.7. Информация, которая хранилась в первых 44.2.1.j регистрах групп регистров процессорных элементов 4.2.j перепишется в регистры 44.2.2.j. Таким образом, в следующем такте появляется возможность для функционирования этих процессорных элементов четвертого каскада. В течение этого такта процессорные элементы 3.1.1 и 3.1.2 реализуют базовые операции 1.1 и 1.2 соответственно очередной 32- точечной выборки. В очередном такте функционируют процессорные элементы первого, второго, третьего и четвертого каскадов. Результаты выполнения базовых операций 4.1 и 4.3, 4.5, 4.7 заносятся по импульсу с входа 14.2 в первые регистры 53.1 и 54.1 первой и второй групп соответствующих процессорных элементов пятого каскада. Результаты базовых операций 4.2, 4.4, 4.6, 4.8, реализуемых в очередном такте, регистрируются аналогичным образом, а результаты базовых операций предыдущего такта перезаписываются во вторые регистры групп 53.2 и 54.2. Результаты базовых операций 4.9, 4.11, 4.13, 4.15 очередного такта заносятся в первые 6.1 регистры третьей группы регистров и регистры 55 соответствующих процессорных элементов пятого каскада. В регистрах первой и второй групп происходит сдвижка информации; таким образом, в регистрах 53.3 первых групп и регистрах 5 всех процессорных элементов пятого каскада оказываются записаны преобразуемые отсчеты, следовательно, в следующем также процессорные элементы пятого каскада могут приступить к работе. В очередных тактах группы первых и вторых регистров этих элементов функционируют в режиме стека, а в регистр 55 отсчеты записываются из группы третьих регистров. Далее процессорные элементы пятого каскада функционируют, как описано выше. После того, как начинают функционировать процессорные элементы (n-го) каскада, процессор работает в основном режиме. Возвращение процессора в исходное состояние осуществляется по мере прекращения формирования управляющих сигналов на соответствующих выходах блока управления по вышеописанному алгоритму.
название | год | авторы | номер документа |
---|---|---|---|
ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ СИГНАЛОВ ПО УОЛШУ С УПОРЯДОЧЕНИЕМ ПО АДАМАРУ | 1991 |
|
RU2025772C1 |
УСТРОЙСТВО ТАКТОВОЙ СИНХРОНИЗАЦИИ | 1990 |
|
RU2011303C1 |
ТРЕХКАНАЛЬНАЯ АСИНХРОННАЯ СИСТЕМА | 1991 |
|
RU2029365C1 |
Процессор цифровой обработки сигналов | 1990 |
|
SU1789991A1 |
Процессор цифровой обработки сигналов | 1990 |
|
SU1837320A1 |
МАЖОРИТАРНО-РЕЗЕРВИРОВАННЫЙ АНАЛОГО-ЦИФРОВОЙ ПРЕОБРАЗОВАТЕЛЬ | 1991 |
|
RU2015617C1 |
МИКРОПРОГРАММНОЕ УСТРОЙСТВО УПРАВЛЕНИЯ | 1993 |
|
RU2079876C1 |
Устройство быстрого преобразования сигналов по Уолшу с упорядочением по Адамару | 1990 |
|
SU1784996A1 |
ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО С ДИНАМИЧЕСКИМ РЕЗЕРВИРОВАНИЕМ | 1990 |
|
RU2028677C1 |
УСТРОЙСТВО ДЛЯ КОРРЕКЦИИ ФАЗЫ | 1992 |
|
RU2028727C1 |
Изобретение относится к области автоматики и вычислительной техники и может быть использовано для спектрального и корреляционного анализа случайных процессов, для цифровой фильтрации, сжатия информации в технике связи. Задачей, решаемой изобретением, является повышение производительности процессора быстрого преобразования сигналов по Уолшу с упорядочением по Адамару за счет распараллеливания входного потока данных путем построения схемы процессора как вычислительной системы на основе регулярной гомоморфной свертки граф-схемы реализуемого алгоритма с коэффициентом Новым в процессоре быстрого преобразования сигналов по Уолшу с упорядочением по Адамару является введение блока регистров и групп процессорных элементов первого, второго и третьего типов. 2 з.п. ф-лы, 13 ил.
Устройство ортогонального преобразования цифровых сигналов по Уолшу-Адамару | 1980 |
|
SU951320A1 |
Приспособление для точного наложения листов бумаги при снятии оттисков | 1922 |
|
SU6A1 |
Устройство быстрого преобразования сигналов по Уолшу с упорядочением по Адамару | 1984 |
|
SU1265795A1 |
Приспособление для точного наложения листов бумаги при снятии оттисков | 1922 |
|
SU6A1 |
Авторы
Даты
1997-01-27—Публикация
1992-05-18—Подача