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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 178499 51)5 6 Об Р 15/3 ГОСУДАРСТПО ИЗОБРЕТПРИ ГКНТ С ННЫЙ КОМИТЕТНИЯМ И ОТКРЫТИЯМ ЗОБ РЕТ РСАНИ ИЯ КОМУ ВТО У 2(21) 4887409/24быть использовано для спектрального и кор- (22) 29.10.90 реляционного анализа случайных процес- (46)30.12.92. Бюл. Ь 48сов, для цифровой фильтрации, сжатия (71) Конструкторское бюро электроприбора- информации, в технике связи, Цель изобре- строениятения - повышение производительности ус- (72) Н.К,Байда, А.С.Резник, К.Ю.Воробьев, тройстэа за счет использования алгоритма Г.Н,Тимонькин, В.С,Харченко и С.Н.Ткаченко быстрого преобразованйя, имеющего регу- (56) Авторское свидетельство СССР лярную структуру; и параллельной итерациМ 951320, кл. О 06 Р 15/332, 1982, .онной обработки входных отсчетов,, Авторскоесвидетельство СССР Устройство содержит блок 1 регистров, М 1265795, кл. 8 06 Р 15/332, 1984, группу 2,12(М 2) вычислительных блоков,Авторское свидетельство СССР блок 3 управления, вход 4 обрабатываемого Ь 1571610, кл. 6 06 Р 15/332, 1988 сигнала,. вход 5 синхронизации, группу 6.1 (54) УСТРОЙСТВО БЫСТРОГО ПРЕОБРА-б.й выходов блока 1 регистров, группу ЗОВАНИЯ СИГНАЛОВ ПО УОЛШУ С УПО-первых 7.1.7,й и вторых 8.18.й инфор- РЯДОЧЕНИЕМ ПО АДАМАРУ мационных выходов вычислительных бло- (57) Изобретениеотносится кобласти авто-, ков 2.12.(К/2), выход 9 блока 3 матики и вычислительной техники и мОжет управления и соответствующие связи, Блок1784996 1 регистров содержит группу регистров и их связи, Каждый вычислительный блок содержит первый, второй, третий и четвертый регистры входных отсчетов, первый и второй коммутаторы, сумматор-вычитатель, первыи второй регистры коэффициентов Адамара и соответствующие связи. Блок 3 управления содержит счетчик тактовых импульсов; СК-триггер, группу элементов И,ФФ:ф"фИзобретение относится к области автоматики и вычислительной техники и можетбыть использовано для спектрального икорреляционного анализа случаййых процессов, для цифровой фильтрации, сжатияинформации, в технике связи,Цель изобретения- повыаейие произ-водительности.На Фиг, 1 представлена структура устройства быстрого преобразования"сйгналовпо Уолшу с упорядбчением по Адамару; нафиг, 2 - функциональная схема блока регистров; на фиг, 3 - функциональная схема .вычислительного блока; на фиг, 4 - функци-ональная схема блока управления; на Фиг, 5временные диаграммы Функционирования устройства; на фиг. 6 представлена схема алгоритма быстрого преобразовайияУолша с упорядочением по Адамару.Устройство быстрого преобразованиясигналов но Уолшу с упорядочением по Адамару содержит блок 1 регистров, группу 2 Л. 2. М/2 (К =8) вычислитель н ых блоков, блок3 управления, вход 4 обрабатываемого сигнала; выход 5 синхронизации, группу 6,16.К выходов блока 1 регистров, группу первых 7 Л7.й и вторых 8.18 З информационных выходов вычислительных блоков2.1 .;. 2,И/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 вычислительного блока соединены с четвер тыми информационными входами соответственно первого 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.12.4 блоков являются группой выходов устройства, выход 9 блока управления соединен с управляющими вхо дами группы 2.1-2.4 вычислительных блокОв. Блок 1 регистров (фиг. 2) содержит группу 10,1 . 10,й регистров, причем вход 5 30 соединен с синхронизирующими входамивсех 10 Л ; 10.Й регистров, информационный вход 4 соединен с информационным входом оегистра 10,8, выходы регистров 10,= 2, 8), соединены с информационными 35 входами регистров 10.+1 и соответствующими 6. выходамиблока 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 регистры коэффициентовАдамара.Блок 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 сое динен со входом 32 выходной шины, выходы элементов И 25 и И 26 соединены соответственно с первым и вторым входами элемента ИЛИ. 30, выход которого соединен со.входом 33 выходной шины, выход элемента 30 И 28 соединен с первьм инверсным входом элемента И 29, выход которого соединен со входом 35 выходной шины, выходная шина соединена с выходом 9 блока управления.На,фиг. 5 использованы обозначения, 35 принятые,на фиг. 1-4. На фиг. 6 символами х 1, хг,х 8 обозначены входные отсчеты, символами у 1, уг,у 8 - выходные отсчеты - коэффициенты Адамара.Рассмотрим назначение основнйх эле ментов устройства; Блок 1 регистров предназначен для формирования параллельного потока входных отсчетов. Рассмотрим порядок функционирования блока регистров.Входные отсчеты х 1хи поступают с часто той, в два раза превышающей тактовую частоту устройства, которая определяется быстродействием сумматора-вычислителя последовательно на вход регистра 10.8. По тактовым импульсам они последовательно 50 перезаписываются иэ регистра в регистр. Таким образом, к концу восьмого такта в регистре 10.1 окажется записан. отсчет х 1", в регистре 10,2 - отсчет хгп, ". в регистре 10.8 - отсчет х 8 где и - номер группы отсче тов), Еще через восемь тактов в регистрах в . той же последовательности будут записаны отсчеты х 1хзп очередной группы и+ 1.Вычислительный блок служит для выполнения в каждой. итерации базовой опе рации над соответствующими отсчетами х" ( = 1, 3, и = 1, 2, ),Базовая операция алгоритма заключается в вычислении по формулам А+ Вц = Сч Ам - Ви= Оч,Аг -Сз Аз -01+1 А 4 =03,Вз =Ог В 4 =04 где = 1, 2 - номер итерации, нижний индекс - номер вычислительного блока.После выполнения последней итерации= 3 на выходи вычислительных блоков поступят результаты - коэффициенты Уолша, упорядоченные по Адамару, причем т 1 =С 1,Уг =.Сг, тз =Сэ У 4 п С 4 зп Упп = О 1 зп У 8 п 0 Эп У 7 =ОЗ, т 8 04 где п - 1, 2, 3 .номер группы входных отсчетов,Каждый вычислительный блок выполняет базовую операцию над входными отсчетами во всех итерациях одинаково. Рассмотрим порядок функционирования вычислительного блока на примере блока 2.1, В исходном состоянии все регистры блока обнулены. (Цепи установки элементов устройства в исходное состояние условно не приведены).По первому импульсу, прошедшему на вход 31 при разрешающем сигнале на входе 33 в регистры 11,1 и 13,1 занесутся отсчеты А 1 и В 1. соответственно, По единичному сигналу на входе 35 они поступят соответственно на первый и второй входы сумматора- вычислителя 17.1, где будет произведена базовая операция: А 11+ В 11= С 11А 1 -В -01 где Аи и Вы - входные отсчеты для -итерации= 1, 2, 3), при= 1 Ао и Вв являютсявыходными отсчетами из группы х", при= 1 они поступают на первый и третий, апри= 2, 3 - на второй и четвертый информационные входы вычислительного блокасоответственно, Си и Оч - результаты ба 1 1зовой операции в -й итерации 1 принимае- .мые как исходныеданные Аи+ и В 1+ длябазовых операций следующей итерации соответствующими вычислительными блоками согласно графу алгоритма фиг. б,Таким образом,Результаты этой операции поступят соответственно на первый и второй выходы сумматора-вычислителя. По очередному тактовому импульсу через промежуток вре- мениск, где г =-, 1, - частотапоступле 5Тония отсчетов при разрешающем сигнале на входе 32 в регистры 12.1 и 14.1 занесутся отсчеты А . и ВПо нулевому сигналу на входе 35 через коммутаторы 15.1 и 16,1 эти 10 отсчеты поступят соответственно на первый и второй выходы сумматора-вычитателя. Еще через промежуток 3 т послеаналогичных преобразований результаты базовой операции;" .,15А 12+ 81 = С 1 поступят на первый и второй выходы сумма торэ-вычитателя 17,1.Третья итерация производится эналО- гично. Результаты третьей итерации С =У 1 и 01 "У 5 через промежутокГпо тактовому3импульсу при разрешающем сигнале на вхо де 34 будут занесены в регистры 18,1 и 19.1 соответственно, и с их выходов йоступят на третий 8 Л и четвертый 8.2 выходы вычислительного блока 2.1.Таким образом, при итерации(для й -8) 30 вычислительный блок реализует за промежуток времени равный б г, а времй накопления группы входных отсчетов в блоке 1 регистров составляет 8 г, следовательно двэ така вычислительный блок находится 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). После выполнения третьей итерации на третьих и четвертых выходах всех вычислительных. блоков появляется значение коэфФициейтов Уолша-Адамара. Далее по соответствующим управляющим сигналам порядок работы устройства повторяется Таким образом, устройство производит обработку потока входных отсчетов; имеющего частоту в двое большую тактовой частоты работы устройства, котораяопределяется быстродействием сумматора-вычитателя, что приаодйт к значительному повышению производительности.Формула изобретения Устройство для быстрого преобразования сигналов по Уолшу с упорядочением по Адамару. содержащее п-разрядный.счетчик, и вычислительных блоков (и = од 2 й), каждый из которых, кроме первого, содер- жит первый и второй коммутаторы,. сумматор-вычитатель и 2"-разрядный регистр сдвига каскада ( Г и - номер каскада преобразования первый вычислительный блок содержит первый коммутатор, сумматор-вычитатель, регистр, причем счетный вход счетчйка является тактовым входомдстройства, выход 1-го разряда счетчика-2, и) соединен с управляющими входами первого и второго коммутаторов)-го вычислительного блока, выход первого разрядасчетчика соединен с управляющим входом первого. коммутатора первого разряда, выход реги-: стра сдвига в каждом вычислительном блоке . соединен с вторым инФормационйым входом суммэтора-вычитателя этого блока, выход регистра сдвига )-го вычислительного блока, кроме того, соединен с вторым информационным входом первого коммутатора )-го вычислительного блока, выход первого коммутатора Ц - 1)-го вычислительного блока соединен с первым информационным входом второго коммутатора и первым входом сумматора-вычитателя )-говычислительного блока, выход первого ком- первого, третьими инверсными входами мутатора и-го каскада является выходом ус- третьего, четвертого, третьими прямыми тройства, первый и второй выходывходами пятого, шестого й вторым инверссумматора-вычитателя-говйцислительного - ным входом восьмого:элемента И; вцход блока соединены.соответственнос первым 5 йервогозлементаИсоедйнекс)-иС-входа- информационным входом первого и вторым ми триггера, выход которогосоедйнен с вто- .информациойным входом второго коммута- рым входом второго элемента .И, выходы торов этого блока, первый и второй выходы четвертого ипятого элементов И, соедйнены сумматора-вйчитателя первого вычисли- соответственн 6 с первым и вторым выхода- тельного блока соединены соответственно с 10 ми элемента ИЛИ. выход седьмого элементапервымивторйминформационными:входа- И соединен с первыминверсным входом .ми первого коммутаторазтогоблока, выход , восьмого элемента И,выход второго эле второго коммутатора -го вычислительного. мента И соединен с синхровходами перво- блока соединен с информационным входом: го, второго, третьего,четвертого регистров регистра сдвига, о т л и ч а ю щ е е с я тем, 15 выходных отсчетов и первогои второго речто, с целью повышения производительности.гистров вцходйых козффициентоаО + 1)-го оно дополнительно содержит( -- ору) вы :, вычислительного. блока, щаход третьего элеМ2 .:.мента Й соединен с управляющими входамичислительных блоков, блок регистров, пер-. второго и четвертого регистров:выходных вый вычислительный блок дополнительно 20 отсчетов, всех аычйслительных блоков, высодержит первый и второй регистрывыМод-ход элемента ИЛИ соедийен с управляющиных отсчетов - коэффициентов Уолша-Ада-ми входами первого и второго регистров мара, блок управления содержит восемьвходныхотсчетоввсехвычислительныхблоэлементов И, элемент ИЛИ,СК-триггер иков, выход шестого элемента И соедийен с счетчик, причем вход. синхронизации уст первыми прямыми й вторыми инверсными ройства соединенсо счетным входом счет-. -входами первого ивторого коммутаторов, чика, первыми входами первогои второго . выход восьмого эиййентаИ соединен с упзлементов И и синхровходамиретистров.равляющими входами первого и второго информационййй вход устройства с 6 еди-. регистров выходных коэффйциентовеы- - нен с информационнйм входом Й-го регист- ЗО. ходы первого, второй и третьего, четверра.блоке регйстров, выход 1-го (1 -.2,И) того регистра входных отсчетов всех регистра блока регйстров соединен сий-.: вычислительнйх блоков соединены с перформационным входом (т 4 Я-го регистра й- выми и вторыми ийформационными входасоотнетствующимт-м выходом блока регими "соответственно йераого и второго стров; вйход первого регистра блуа реги коммутаторов; выходы коМрыхсоединены с стров соединен с первым выходом блокапервыми вторймвходамисумматора-вычирегистров, фа - 1)-й и 2 а-й выходы:блока . тателя, первые и вторые выходы сумматорегистров соединены соответственно с ин;- " ров-вычитателей 2 С - 1)-х С 1 Л 4)формациойными,входами первого и тютьЬ-вычислительййх блоковсоединеньс инфорго регистров выходных отсчетов .е-го 40 мационными входами вторых-регистров вычислительн 6 го блока а = 1, Ы/2), выход: входных отсчетов соответственно С-х и (С+ 1 о 92 К/8 + 1) (К 8, М) разряда счетчика . - , й/4) аычислйтельнйх блоков, первыеи втосоединен с вторым входом первого,первы-.рые выходы сумматоров-вычитателей 2 С-х ми инверсными входами третьего, четверто- , вычислительных блоков соединены с инго, пятого, шестогои первым прямым входом 45 формйционными входами четвертых реги- седьмого элемейтов И соответственновйход строе входйых отсчетов с 6 ответственно 0 о 92 - + 2) разряда счетчика соединен с. С" и (С + И/4) вычислительныхблоков,8 .. : первый и второй выходы сумматора-вычитретьим входом первого,вторыми прямыми тателя каждого вычиСлйтельного блока со входами четвертого, шестого, седьмого и 60 единены с информационными входамивторыми инверсными входами третьего и соответственнб первого и второго регист. пятого элементов И, выход (одг К + ч) Ров выходных коэффициентов, выходы ко 8 торых являются информационнымиразряда счетчика соединен с четвертым входом выходами устройства.1784996 32 Составитель Ю,ЛанцоРедактор В.Коляда Техред М.Моргентал орректор. С одственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 каз 4366 Тираж Подписное ВНИИПИосударственногокомитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-З 5, Раущская наб., 4/5