Устройство быстрого преобразования сигналов по уолшу с упорядочением по адамару

 

Изобретение относится к области автоматики и вычислительной техники и может быть использовано для спектрального и корреляционного анализа случайных процессов , для цифровой фильтрации, сжатия информации, в технике связи. Цель изобретения - повышение производительности устройства за счет использования алгоритма быстрого преобразования, имеющего регулярную структуру, и параллельной итерационной обработки входных отсчетов. Устройство содержит блок 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

Ы „1784996 Al

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

{я)5 G 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ и ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 2 (21) 4887409/24 .. быть использовано для-спектрального и кор{22) 29.10.90 реляционного анализа случайных процес(46)30.12.92. Бюл. N 48 -.сов, для цифровой фильтрации, сжатия (71) Конструкторское бюро электроприбора- информации, в технике связи. Цель изобрестроения .... тения — повышение производительности ус(72) H.Ê,Áaéäà, А.С.Резник, К.Ю.Воробьев, тройстэа за счет использования алгоритма

Г.H,Тимонькин, В.С,Харченко и С.Н.Ткаченко быстрого преобразованйя, имеющего регу(56) Авторское свидетельство СССР лярную структуру, и параллельной итераци№ 951320, кл. G 06 F 15/332, 1982.. - онной обработки входных отсчетов, . Авторскоесвидетельство СССР Устройство содержит блок 1 регистров, № 1265795, кл. 8 06 F 15/33?, 1984, группу 2,1 ... 2(N/2) вычислительных блоков, Авторское свидетельство СССР - - блок 3 управления, вход 4 обрабатываемого

¹ 1571610, кл. G 06 F 15/332, 1988, сигнала,. вход 5 синхронйзации, группу 6.1 (54) УСТРОЙСТВО БЫСТРОГО ПРЕОБРА- ... 6.M выходов блока 1 регистров, группу

ЗОВАНИЯ СИГНАЛОВ ПО УОЛШУ С УПО- первых 7.1 ... 7,N и вторых 8.1 ... 8.N инфорРЯДОЧЕНИЕМ ПО АДАМАРУ - мационных выходов вычислительных бло(57) Изобретение относится к области авто-, ков 2.1 ... 2.(N/2), выход 9 блока 3 З матики и вычислительной техники и может управления и соответствующие связи, Блок

1784996

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

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

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

Уолша-с упорядочением по Адамару.

Устройства быстрого преобразования сигналов но Уолшу с упорядочением по Адамару содержит блок 1 регистров, группу 2Л ... 2.М/2 (N = 8) вычислительных блоков, блок

3 управления, вход 4 обрабатываемого сигнала; выход 5 синхронизации, группу 6.1 ...

6.К выходов блока 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,6 выходы блока 1 регистров соединены соответственно с первым и вторым информационными входами третьего

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

7.2 выходы первого 2.1 вычислительного

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

1.5 входами соответственно второго 2.2 и четвертого 2;4 вычислительных блоков, первый

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

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

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

30 соединен с синхронизирующими входами всех 10Л ..; 10.Й регистров, информационный вход 4 соединен с информационным входом регистра 10.8, выходы регистров 10Л ...(! = 2, 8), соединены с информационными

35 входами регистров 10.!+1 и соответствующими G.i выходами блока 1 регистров, выход регистра 10Ë соединен с первым 6.1 выходом блока 1 регистров.

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

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

45 18.1 и второй 19,1 регистры коэффициентов

Адамара.

1784996

Блок 3 управления (фиг. 4) содержит счетчик 20 тактовых импульсов, !СК-триггер

21, группу 22, 23, 24, 25, 26, 27, 28, 29 элементов И, элемент ИЛ И 30, группу 31, 32, 33, 34, 35 входов выходной шины, причем вход 5

5 соединен со счетным входом счетчика 20 и первыми входами элементов И 22 и 23, выход первого разряда счетчика соединен со вторым входом элемента И 22, первыми инверсными входами элементов 24, 25, 26, 10

27 И и первым прямым входом элемента И

28, второй выход счетчика соединен с третьим входом элемента И 22, вторыми прямыми входами элементов 25, 27, 28 И и вторыми инверсными входами элементов 24, 26 И, 15 третий выход счетчика соединен с четвертым входом элемента И 22, третьими инверсными входами элементов 24, 25 И, третьими прямыми входами элементов 26, 27 И и вторым инверсным входом элемента 20

И 29, выход элемента И 22 соединен с !- и

С-входами триггера 21, выход которого соединен со вторым входом элемента И 23, выход элемента И 23 соединен со входом 31 выходной шины, выход элемента И 24 сое- 25 динен со входом 32 выходной шины, выходы элементов И 25 и И 26 соединены соответственно с первым и вторым входами элемента ИЛИ. 30, выход которого соединен со. входом 33 выходной шины, выход элемента 30

И 28 соединен с первь1м инверсным входом элемента И 29, выход которого соединен со входом 35 выходной шины, выходная шина соединена с выходом 9 блока управления.

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

Рассмотрим назначение осноьнйх эле- 40 ментов устройства; Блок 1 регистров предназначен для формирования параллельного потока входных отсчетов. Рассмотрим порядок функционирования блока регистров.

Входные отсчеты х1 ... xN поступают с часто- 45 той, в два раза превышающей тактовую частоту устройства, которая определяется быстродействием сумматора-вычислителя последовательно на вход регистра 10.8. По тактовым импульсам они последовательно 50 перезаписываются иэ регистра е регистр.

Таким образом, к концу восьмого такта в регистре 10.1 окажется записан. отсчет x1", в регистре 10,2 — отсчет x2", .„ в регистре

10.8 — отсчет х8 (где n - номер группы отсче- 55 тов), Еще через восемь тактов в регистрах в . той же последовательности будут записаны отсчеты x1 ... хз" очередной группы и+ 1.

Вычислительный блок служит для выполнения в каждой. итерации базовой one- рации над соответствующими отсчетами х1" . (i = 1, 3, и = 1, 2, ...).

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

А! + Вк!! = CN

AN -BN =DN, А2 =Сэ

АЗ -D1

I+1

А4 =03, I+1 1

Вэ =02

В4 =D4 где! = 1, 2 — номер итерации, нижний индекс — номер вычислительного блока.

После выполнения последней итерации ! -= 3 на выход вычислительных блоков поступят результаты — коэффициенты Уолша, упорядоченные по Адамару, причем т1 =С1 т2 = 2 тз = Сэ (4" = C4 " Yrп =* 01 " У8" = 0 т7 =03, т8 04 где n — 1, 2, 3 ... номер группы входных отсчетов, Каждый вычислительный блок выполняет базовую операцию над входными отсчетами во .всех итерациях одинаково.

Рассмотрим порядок функционирования вычислительного блока на примере блока

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

По первому импульсу, прошедшему на вход 31 при разрешающем сигнале на входе

33 в регистры 11,1 и 13.1 занесутся отсчеты

А1 и В1. соответственно, По единичному

1 сигналу на входе 35 они поступят соответственно на первый и второй входы сумматоравычислителя 17.1, где будет произведена базовая операция:

А1+В 1 С1.

A1 - В1 - Dl

1 1 где AN u BN — входные отсчеты для i-итера1 I ции (! = 1, 2, 3), при = 1АО и BN являются

I I выходными отсчетами из группы х!", при ! = 1 они поступают на первый и третий, а при = 2, 3 — на второй и четвертый информационные входы вычислительного блока соответственно, CN u DN — результаты ба1 1 зовой операции в i-й итерации принимае- ° мые как исхоДные Данные AN + и В.!41+1 для базовых операций следующей итерации соответствующими вычислительными блоками согласно графу алгоритма фиг. 6.

Таким образом, 1784996

Результаты этой операции поступят соответственно на первый и второй выходы сумматора-вычислителя. По очередному тактовому импульсу через промежуток времени т;где г = -, 4- частота поступле5 .. о ния отсчетов при разрешающем сигнале на входе 32 в регистры.12.1 и 14.1 занесутся отсчеты А t . и В g .. Ao нулевому сигналу на

2. t. входе 35 через коммутаторы 15.1 и 16,1 эти 10 отсчеты поступят соответственно на первый и второй выходы сумматора-вычитателя.

Еще через промежуток Зт после аналогичных преобразований результаты базовой операции; - - " ., 15

А,2+ 812 = С12

В 12 поступят на первый и второй выходы сумма- 20 тора-вычитателя 17,1.

Третья итерация производится аналогично. Результаты третьей итерации С1 = Vj и 01 - Y5 через промежуток(по тактовому з импульсу при разрешающем сигнале на вхо- 25 де 34 будут занесены в регистры 18.1 и 19.1 соответственно, и с их выходов йоступят на третий 8.1 и четвертый 8.2 выходы вйчислительного блока 2.1, Таким образом, при итерации (для N - 8) 30 вычислительный блок реализует за промежуток времени равный 6 г, а время накопления группы входных отсчетов в блоке f регистров составляет 8 .i, следовательно два так а вычислительный блок находится 35 в режиме "ожидания". Выйужденный простой можно использовать, например, для проведения тестирования вичислительного блока. По очередному тактовому импульсу через промежуток времени 8 после начала 40 обработки и-й группы отсчетов.при разрешающем сигнале на входе 33 в регистры

11.1 и 13,1 будут занесены входные отсчеты очередной и+ 1-й группы и процесс функционирования блока повторится. Временйая 45 диаграмма функционировайия вычислительного блока приведена на. фиг, 5;

Блок 3 управления служит для форми рования сигналов, управляющих работой вычислительных блоков.: 50 . Рассмотрим порядок функционирования блока управления. В иСходном состоянии счетчик 20 и трлггер 21 обнулены. (Цепи установки в исходное состояние условно не показаны). Седьмой импульс переведет 55 счетчик 20 в состояние, при котором на всех

его выходах появятся единичные сигналы, что разрешит прохождение через элемент И

22 восьмого импульса, который переводит триггер 21 в единичное состояние, тем самым разрешил поступление тактовых импульсов, начиная с девятого, через элемент

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

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

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

Устройство для быстрого преобразования сигналов по Уалшу с упорядочением по

Адамару. содеpжащеe п-разрядный. счетчик, п вычислительных блоков (n =!адгй), каждый из каторйх, кроме первого, содержит первый и второй коммутаторы,. сумматор-вычитатель и 2 -разрядный регистр сдвига каскада (I . f. n — номер каскада преобразования первый вычислительный блок содержит первый коммутатор, сумматор-вычитатель, регистр, причем счетный вход счетчйка является тактовым входомдстройства, выход J-го разряда счетчика O - 2, n) соединен с управляющими входами первого и второго коммутаторов j-ro вычислительного блока, выход первого разряда счетчика соединен с управляющим входом первого. коммутатора первого разряда, выход реги-:стра сдвига в каждом вычислительном блоке . соединен с вторым информационным входом сумматора-вычитателя этого блока, выход регистра сдвига j-ro вычислительного блока, кроме того, соединен с вторым информационным входам первого коммутатора j-го вычислительного блока, выход первого коммутатора (j - 1)-ro вычислительного блока соединен с первым информационным входом второго коммутатора и первым входам сумматора-вычитателя j-го

1784996 вычислительного блока, выход первого ком- первого. третьими инверсными входами мутатора и-го каскада является выходом ус- третьего, четвертого, третьими прямыми тройства, первый и второй выходы входами пятого, шестого и вторым инверссумматора-вычитателя J-говйчислительного - ным входом восьмого:элемента И; выход блока соединены. соответственно с первым 5 йервогозлемента Исоедйнекс)-и С-входаинформационным входом первого и вторым ми триггера, выход которого соедйнен с втоинформационным входом второго коммута- рым входом второго элемента И, выходы торов этого Ьлока, первый и второй выхода четвертого и пятого элементов И, соедйнены сумматора-вйчитателя первого вычйсли- соответственно с первым и.вторым-выходательного блока соединены соответственно с 10 ми элемента ИЛИ. выход седьмого элемента первымивторйминформационными-входа- И соединен с первым инверсным входом . ми первого коммутатора этого блока, выход, восьмого элемента И, выход второго эле второго коммутатора j-го вычислительного. мента И соединен с синхровходами первоблока соединен с информационным входом го, второго, третьего, четвертого регистров регистра сдвига, о т л и ч а ю щ е е с я тем, 16 выходных отсчетов и первого и второго речто, с целью повышения производительности.: гистров выходйых коэффйциентов Ц + 1)-rO оно дополнительно содержит(— — 1офгд) вы- : вычислительного блока, аиходтРюьего элеN

2 . - . -:; . мента Й соединен с упрааляющими входами числительных блоков, блок регистров, пер-. второго и четвертого регистров выходных вый вычислительный блок дополнительно 20 отсчетов, всех аычйслительных блоков, высодержит первый и второй регистры выМод- ход элемента ИЛИ соединен с управляющиных отсчетов — коэффициентов Уолша-Ада- ми входами первого и второго регистров мара, блок управления содержит восемь входныхотсчетов всехвычислительныхблоэлементов И., элемент ИЛИ. !СК-триггер и . " ков, выход шестого злемвйта И соедийен с счетчик, причем вход .синхронйэации уст-. 26 первыми прямыми и вторыми инверсными чика, первыми входами первого и второго . выход восьмого эиййента И соединен с упзлементов И и синхровходами ретистров. равляющими входами первого.и второго информационнйй вход устройства с6еди- . регистров выходных коэффициентов„еы- - нен с информационнйм входом N-га регист-:ЗО. ходы первого, второго и третьего, четверра. блоке регйстров, выход t-го (t -.2, И) того регистра входных отсчетов всех регистра блока регйстров соединен с ин-:: вычислительнйх блоков соединены с пер-формационным входом (i+ 1 -го регистра и .:. - выми и вторыми ийформационными входастров; вйход первого регистра блуа реги- 36 коммутаторов; выходы коМрыхсоединены с стров соединен с первым выходом блока первыми вторймвходамисумматора-вычирегистров, (2m - 1)-й и 2m-й выходы:блока .. тателя, первые и вторые выходы сумматорегистров соединены соответственно с ин-- : p08-âû÷èòàòeëåé (2С - 1)-х(С - 1.,й/4) .. формациойными,входами первого и третье-:- вычислительййх блоков соединень с инфорго регистров выходных отСчетов .в- го 40 мационнймй входами вторых-регистров вычислительного блока (а = 1, N/2). выход:: входных отсчетов соответственно С-х и (С+ (toggK/8 + 1) (К 8„N) разряда счетчика . —, N/4) аычислйтельнйх.блоков, {тервые и втосоединен с вторым входом первого, первы-. : рые выходы сумматоров-вычитателей 2С-х ми инверсными входами третьего, четверто- ::. вычислительных блоков соединены с инго, пятою, шестогои первым прямым входом 45 формйционными входами четвертых региседьмого элемейтов И соответственно а{ход строе входных отсчетов соответственно (Ь + 2) азряда счетчика соединен с С-х и (С + И/4) вычислительных блоков, 8 . .::.: : первый и второй выходы сумматора-вычитретьим входом nepsoro, âòoðûìè прямыми татвля каждого вычиСлйтельного блока со: входами четвертого, шестого. седьмого и 60 единены с информационными входами вторыми инверсными входами третьего и соответственно A6p80l0 и второго регистпятого элементов И, выход (!оцг " + g) . ров выходных коэффициентов, выходы ко8 торых являются информационными разрядасчетчикасоединен с четвертым входом Ыходами устройства.

1784996

1784996

1784996

"2 л 8 Фиг 6

Составитель Ю,Ланцов

Техред M.Моргентал Корректор. С,Лисина

Редактор B.Êîëÿäà

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 4366 Тираж Подписное

ВНИИПИ;Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5