Устройство быстрого преобразования сигналов по Уолшу с упорядочением по Адамару Советский патент 1992 года по МПК G06F15/332 

1 регистров содержит группу регистров и их связи, Каждый вычислительный блок содержит первый, второй, третий и четвертый регистры входных отсчетов, первый и второй коммутаторы, сумматор-вычитатель, пер- вый-,и второй регистры коэффициентов Ада- мара и соответствующие связи. Блок 3 управления содержит счетчик тактовых импульсов; ICK-триггер, группу элементов И,

элемент ИЛИ, группу входов выходной шины и соответствующие связи. Новым в устройстве является введение блока регистров, дополнительного вычислительного блока, двух регистров выходных отсчетов коэффициентов Уолша-Адамара, второго коммутатора, группы элементов И, триггера и элементов ИЛИ и обусловленных ими связей. 6 ил.

Изобретение относится к области автоматики и вычислительной техники и может быть использовано для спектрального и корреляционного анализа случайных процессов, для цифровой фильтрации, сжатия информации, в технике связи. Цель изобретения - повышение производительности устройства за счет использования алгоритма быстрого преобразования, имеющего регулярную структуру, и параллельной итерационной обработки входных отсчетов. Устройство содержит блок 1 регистров, группу 2.1 ... 2(N/2) вычислительных блоков, блок 3 управления, вход 4 обрабатываемого сигнала, вход 5 синхронизации, группу 6.1 ... 6.N выходов блока 1 регистров, группу первых 7.1 ... 7.N и вторых 8.1 ... 8.N информационных выходов вычислительных блоков 2.1 ... 2.(М/2), выход 9 блока 3 управления и соответствующие связи. Блок fe 4 00 Јь О О О (Duaf

t SSF.

a. ttfИзобретение относится к области автоматики и вычислительной техники и может быть использовано для спектрального и корреляционного анализа случайных процессов, для цифровой фильтрации, сжатия информации, в технике связи.

Цель изобретения - повышение производительности.

На фиг. 1 представлена структура устройства быстрого преобразова нШ сиТналое по Уолшу с упорядочением по Адамару; на фиг. 2 - функциональная схема блока регистров; на фиг. 3 - функциональная схема вычислительного блока; на фиг. 4 - функциональная схема блока управления; на фиг. 5 - временные диаграммы функционирования устройства; на фиг. 6 представлена схема алгоритма быстрого преобразования Уолша с упорядочением по Адамару.

Устройство быстрого преобразования сигналов по Уолшу с упорядочением по Адамару содержит блок 1 регистров, группу 2.1 ... 2.N/2 (N 8) вычислительных блоков, блок 3 управления, вход 4 обрабатываемого сигнала, выход 5 синхронизации, группу 6.1 ... 6.N выходов блока 1 регистров, группу первых 7.1 ... 7.N и вторых 8.1 ... 8.N информационных выходов вычислительных блоков 2.1 ... 2.N/2, выход 9 блока 3 управления, причем вход 4 процессора соединен с информационным входом блока 1 регистров, вход 5 синхронизации соединен с синхров- ходами блока 1 регистров и блока 3 управления, первый 6,1 и второй 6 2 выходы блока 1 регистров соединены соответственно с первым и третьим информационными входами первого 2.1 вычислительного блока, третий 6,3 и четвертый 6.4 выходы блока 1 регистров соединены соответственно с первым и вторым информационными входами второго 2,2 вычислительного блока, пятый 6.5 и шестой 6 б выходы блока 1 регистров соединены соответственно с первым и вторым информационными входами третьего 2.3 вычислительного блока, седьмой 6 7 и восьмой 6 8 выходов блока 1 регистров соединены соответственно с первым и вторым информационными входами четвертого 6,4 вычислительного блока, первый 7.1 и второй 7.2 выходы первого 2.1 вычислительного

блока соединены со вторыми информационными входами соответственно первого 2.1 и третьего 2.3 вычислительных блоков, первый 7.3 и второй 7.4 выходы второго 2.2 вычислительного блока соединены с четвертыми информационными входами соответственно первого 2.1 и третьего 2,3 вычислительных блоков, первый 7.5 и 7.6 выходы третьего 2.3 вычислительного блока соединены со вторыми информационными

входами соответственно второго 2.2 и четвертого 2.4 вычислительных блоков, первый 7.7 и второй 7.8 выходы четвертого 2.4 вычислительного блока соединены с четвертыми входами соответственно второго 2.2 и

четвертого 2,4 вычислительных блоков группа 8.1 ... 8.8 третьих и четвертых выходов вычислительных 2.1 ... 2.4 блоков являются группой выходов устройства, выход 9 блока управления соединен с управляющими входами группы 2.1-2.4 вычислительных блоков.

Блок 1 регистров (фиг. 2) содержит группу 10.1 ... 10,N регистров, причем вход 5

соединен с синхронизирующими входами всех 10.1 ... 10.N регистров, информационный вход 4 соединен с информационным входом регистра 10.8, выходы регистров 10.1 ... (I 2, 8), соединены с информационными

входами регистров 10.1+1 и соответствующими 6.1 выходами блока 1 регистров, выход регистра 10.1 соединен с первым 6.1 выходом блока 1 регистров.

Каждый вычислительный блок (фиг. 3)

(для примера раскрыт первый 2.1 из них) содержит первый 11.1, второй 12,1, третий 13,1 и четвертый 14.1 регистры входных отсчетов, первый 15.1 и второй 16.1 коммутаторы, сумматор-вычитатель 17.1, первый

Блок 3 управления (фиг. 4) содержит счетчик 20 тактовых импульсов, 1СК-триггер 21, группу 22, 23. 24, 25, 26, 27, 28, 29 элементов И, элемент ИЛ И 30, группу 31,32,33, 34, 35 входов выходной шины, причем вход 5 соединен со счетным входом счетчика 20 и первыми входами элементов И 22 и 23, выход первого разряда счетчика соединен со вторым входом элемента И 22, первыми инверсными входами элементов 24, 25, 26, 27 И и первым прямым входом элемента И 28, второй выход счетчика соединен с третьим входом элемента И 22, вторыми прямыми входами элементов 25, 27, 28 И и вторыми инверсными входами элементов 24, 26 И, третий выход счетчика соединен с четвертым входом элемента И 22, третьими инвер- сными входами элементов 24, 25 И, третьими прямыми входами элементов 26, 27 И и вторым инверсным входом элемента 1/1 29, выход элемента И 22 соединен с I- и С-входами триггера 21, выход которого соединен со вторым входом элемента И 23, выход элемента И 23 соединен со входом 31 выходной шины, выход элемента И 24 соединен со входом 32 выходной шины, выходы элементов И 25 и И 26 соединены соответственно с первым и вторым входами элемента ИЛИ 30, выход которого соединен со входом 33 выходной шины, выход элемента VI28 соединен с первым инверсным входом элемента И 29, выход которого соединен со входом 35 выходной шины, выходная шина соединена с выходом 9 блока управления.

На ,фиг. 5 использованы обозначения, принятые на фиг. 1-4. На фиг. 6 символами xi, X2, ... хв обозначены входные отсчеты, символами yi, у2,... ув - выходные отсчеты - коэффициенты Адамара.

Рассмотрим назначение основных элементов устройства. Блок 1 регистров предназначен для формирования параллельного потока входных отсчетов. Рассмотрим порядок функционирования блока регистров. Входные отсчеты xi... XN поступают с частотой, в два раза превышающей тактовую частоту устройства, которая определяется быстродействием сумматора-вычислителя последовательно на вход регистра 10.8. По тактовым импульсам они последовательно перезаписываются из регистра в регистр. Таким образом, к концу восьмого такта в регистре 10.1 окажется записан отсчет xin, в регистре 10,2 - отсчет хап. ... в регистре 10.8 - отсчет хв (где п - номер группы отсчетов). Еще через восемь тактов в регистрах в той же последовательности будут записаны отсчеты ... хзп+1 очередной группы п + 1.

Вычислительный блок служит для выполнения в каждой итерации базовой операции над соответствующими отсчетами Xi

(I-1TB, п-1,2, ...).

Базовая операция алгоритма заключается в вычислении по формулам

AN + BN - CN AN -BN -DN ,

где AN и BN - входные отсчеты для 1-итера- ции (I 1, 2, 3), при I 1А0 и Вы являются выходными отсчетами из группы xin, при 1 1 они поступают на первый и третий, а при I 2, 3 - на второй и четвертый информационные входы вычислительного блока соответственно, См и DIM - результаты базовой операции в 1-й итерации принимаемые как исходные данные AN и В +1 для базовых операций следующей итерации соответствующими вычислительными блока- ми согласно графу алгоритма фиг. 6. Таким образом.

Bil+1 C2

В2М - C41, B3 +1 D2 B4I+1 D41

С/ A2I+1 - Сз АзМ D3 .

где 1 1,2- номер итерации, нижний индекс - номер вычислительного блока. После выполнения последней итерации I 3 на выходи вычислительных блоков поступят результаты - коэффициенты Уолша, упорядоченные по Адамару, причем

35

Yin Ci3n. Y2n - С23п, Y3n - Сз3п, Y4n - C43n, Y5 - Di3n, Y6n - D23n, Y7n . Y8n - D43n,

где n - 1, 2, 3 ... номер группы входных

отсчетов.

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

вычислительного блока на примере блока 2.1. В исходном состоянии все регистры блока обнулены. (Цепи установки элементов устройства в исходное состояние условно не приведены).

По первому импульсу, прошедшему на вход 31 при разрешающем сигнале на входе 33 в регистры 11.1 и 13.1 занесутся отсчеты Ai1 и Bi1 соответственно. По единичному сигналу на входе 35 они поступят соответственно на первый и второй входы сумматора- вычислителя 17.1, где будет произведена базовая операция:

Ai + Bi1 Ai1-Bi1C11Di1

Результаты этой операции поступят соответственно на первый и второй выходы сумматора-вычислителя. По очередному тактовому импульсу через промежуток времени2т,- где т т- , f0 - частота поступлеTO

ния отсчетов при разрешающем сигнале на входе 32 в регистры 12.1 и 14.1 занесутся отсчеты А / и В По нулевому сигналу на входе 35 через коммутаторы 15.1 и 16.1 эти отсчеты поступят соответственно на первый и второй выходы сумматора-вычитателя. Еще через промежуток 2т после аналогичных преобразований результаты базовой операции,

Ai2+Bi2 Ai -Bi2

C1 Di2

поступят на первый и второй выходы сумматора-вычитателя 17.1.

Третья итерация производится аналогично. Результаты третьей итерации С i Yi и Di3 Ys через промежуток по тактовому импульсу при разрешающем сигнале на входе 34 будут занесены в регистры 18.1 и 19.1 соответственно, и с их выходов поступят на третий 8.1 и четвертый 8.2 выходы вычислительного блока 2.1,

Таким образом, при итерации СдЯя N 8} вычислительный блок реализует за промежуток времени равный 6т, а время накопления группы входных отсчетов в блоке 1 регистров составляет 8 t, следовательно два такта вычислительный блок находится в режиме ожидания. Вынужденный простой можно использовать, например, для проведения тестирования вычислительного блока. По очередному тактовому импульсу через промежуток времени 8 после начала обработки n-й группы отсчетов при разрешающем сигнале на входе 33 в регистры 11.1 и 13 1 будут занесены входные отсчеты очередной п + 1-й группы и процесс функционирования блока повторится. Временная диаграмма функционирования вычислительного блока приведена на фиг. 5.

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

Рассмотрим порядок функционирования блока управления. В исходном состоянии счетчик 20 и триггер 21 обнулены. (Цепи установки в исходное состояние условно не показаны). Седьмой импульс переведет счетчик 20 в состояние, при котором на всех его выходах появятся единичные сигналы, что разрешит прохождение через элемент И 22 восьмого импульса, который переводит

триггер 21 в единичное состояние, тем самым разрешил поступление тактовых импульсов, начиная с девятого; через элемент И 23 на вход 31 выходной шины. Временные

диаграммы сигналов, формируемых на входах 32, 33, 34, 35. представлены на фиг. 5.

Рассмотрим порядок функционирования устройства быстроте преобразования сигналов по Уолшу с упорядочением по Адамару в целом. Входные отсчеты xin ... хап накапливаются в блоке 1 регистров, откуда считываются в соответствующие регистры вычислительных блоков. Затем над ними в вычислительных блоках выполняются базовые операции, результаты которых распределяются между вычислительными блоками согласно алгоритму (фиг. 6). После выполнения третьей итерации на третьих и четвертых выходах всех вычислительных блоков

появляется значение коэффициентов Уол- ша-Адамара. Далее по соответствующим управляющим сигналам порядок работы устройства повторяется Таким образом, устройство производит обработку потока

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

Формула изобретения Устройство для быстрого преобразования сигналов по Уолшу с упорядочением по Адамару, содержащее n-разрядный счетчик, п вычислительных блоков {n logaW), каждый из которых, кроме первого, содержит первый и второй коммутаторы, суммз- тор-вычитатель и 2м разрядный регистр сдвига каскада (I « Сп - номер каскада

преобразования первый вычислительный блок содержит первый коммутатор, сумма- тор-вычитатель. регистр, причем счетный вход сметчика является тактовым входом устройства, выход 1-го разряда счетчика (| 2, п)

соединен с управляющими входами первого и второго коммутаторов |-го вычислительного блока, выход первого разряда счетчика соединен с управляющим входом первого коммутатора первого разряда, выход регистра сдвига в каждом вычислительном блоке соединен с вторым информационным входом сумматора-вычитателя этого блока, выход регистра сдвига j-ro вычислительного блока, кроме того, соединен с вторым ин-(

формзционным входом первого коммутатора j-ro вычислительного блока, выход первого коммутатора (j - 1)-го вычислительного блока соединен с первым информационным входом второго коммутатора и

первым входом сумматора-вычитателя J-ro

вычислительного блока, выход первого коммутатора п-го каскада является выходом устройства, первый и второй выходы сумматора-вычитатёля J-ro вычислительного блока соединены соответственно с первым информационным входом первого и вторым информационным входом второго коммутаторов этого блока, первый и второй выходы еумматора-вычитателя первого вычислительного блока соединены соответственно с первым и вторым информационными входами первого коммутатора этого блока, выход второго коммутатора J-ro вычислительного блока соединен с информационным входом регистра сдвига, отличающееся тем, что, с целью повышения производительности,

оно дополнительно содержитС-д- - ю02М)вычислительных блоков, блок регистров, первый вычислительный блок дополнительно содержит первый и второй регистры выходных отсчетов - коэффициентов Уолша-Ада- мара, блок управления содержит восемь элементов И, элемент ИЛИ, ICK-триггер и счетчик, причем вход синхронизации уст- ройства соединен со счетным входом счет- : чика, первыми входами первого и второго элементов И и синхровчодами регистров, информационный вход устройства соединен с информационным входом N-rb региет- ра блока регистров, выход t-ro (t - 2, N) регистра блока регистров соединен с информационным входом (t + 1)-го регистра и соответствующим t-м выходом блока регистров, в,ыход первого регистра блока реги- строе соединён с первым выходом блока регистров, (2т - 1)-й и 2т-й выходы блока регистров соединены соответственно с информационными входами первого и третьего регистров выходных отсчетов -т-го вычислительнбго блока(т 1, N/2), выход (1од2К/8 + 1) (К 8, N) разряда счетчика соединен с вторым входом первого, первы- ми инверсными входами третьего, четвертого, пятого, шестого и первым прямым входом

седьмого элементов И соответственно выход I/

( 092 Ј + 2) разряда счетчика соединен с

третьим входом первого, вторыми прямыми входами четвертого, шестого, седьмого и вторыми инверсными входами третьего и

к

пятого элементов И, выход (Iog2 т + 3)

разряда счетчика соединен с четвертым входом

.- - -:

первого, третьими инверсными входами третьего, четвертого, третьими прямыми входами пятого, шестого и вторым инверсным входом восьмого элемента И, выход первого элементам соединён с )- и С-входа- ми триггера, выход которого соединен с вторым входом второго элемента И, выходы четвертого и пятого элементов И соединены соответственно с первым и вторым выходами элемента ИЛИ, выход седьмого элемента И соединен с первым инверсным входом восьмого элемента И, выход второго элемента И соединен с синхровходами первого, второго, третьего, четвертого регистров выходных отсчетов и первого и второго регистров выходных коэффициентов 0 + 1)-го вычислительного блока, выход третьего элемента И соединен с управляющими входами второго и четвертого регистров выходных отсчетов всех вычислительных блоков, выход элемента ИЛИ соединен с управляющими входами первого и второго регистров входных отсчетов всех вычислительных блоков, выход шестого элемента И соединен с первыми прямыми и вторыми инверсными входами первого и второго коммутаторов, вУход восьмого элемента И соединен с управляющими входами первого и второго регистров выходных коэффициентов, выходы первого, второго и третьего, четвертого регистра входных отсчетов всех вычислительных блоков соединены с первыми и вторыми информационными входами соответственно первого и второго коммутаторов, выходы которых соединены с Первым и вторым входами сумматора-вычитателя, первые и вторые выходы суммато- ров-вычитателей (2С - 1)-х (С - 1, N/4) вычислительных блоков соединение информационными входами вторых регистров входных отсчетов соответственно Ох и (С + N/4) вычислительных блоков, первые и вторые выходы сумматоров-вычитателей 2С-х вычислительных блоков соединены с информационными входами четвертых регистров входных отсчетов соответственно С-х и (С + N/4) вычислительных блоков, первый и второй выходы сумматора-вычи- тателя каждого вычислительного блока соединены с информационными входам соответственно первого и второго регистров выходных коэффициентов, выходы которых являются информационными выходами устройства.

Јгпф

AS S5

и19Ј9 AS S5 59 L9 89

frrfprfFdfc

I сфЈЦ, г(йьвд o JLsda Lsn

I LlЈh LEh Г pл I Ьп Г РП Lljri LlЈh Lk

IL..

1Ш - M-6{Д sr

Щ

966t78il

5

Ьппппппппппппппппшпиппппппп

з/f

п

п