Устройство для вычисления спектрафункций уолша

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советскик

С оциалистйчессиик

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. сеид-ву (22) 3»»«о 18.10,79 (21) 2831264/18-24 (51)М. КЛ

G 06 F 15/332 с присоединением заявки ¹ .— (23) Приоритет

Государственный комитет

СССР по делам изобретений и открытий

Опубликовано 23.0781 Бюллетень Н9 27

Дата опубликования описания 2 0781 (53) УДК 681.14 (088.8) (72) Автор изобретения

В.П.Шмерко (71) Заявитель

Минский радиотехнический институт (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СПЕКТРА

ФУНКЦИЙ УОЛША

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

Известнф устройство для спектрального анализа, содержащее три блока памяти, коммутатор, блок задания тригонометрических функций, операционный блок, выполненный в виде сумматоров и умножителей, блок инверсной перестановки и соответствующие связи. Устройство реализует наиболее эффективный метод вычислений— быстрое преобразование Фурье (1). .Наиболее близким по технической сущности к изобретению является устройство, содержащее блок опреде- ления корреляционной функции, три переключателя, два блока памяти, 2 блок умножения, регистр, цифроаналоговый преобразователь, интегратор, блок задания констант и блок адресации, в совокупности адекватные по функциональному назначению блоку определения весового коэффициента, шифратор, блок сравнения, три счетчика, элемент И, ключевой элемент, адекватный по функциональному назначению триггеру, делитель, сумматор, дешифратор, преобразователь кода, блок управления и соответствующие связи. Устройство позволяет вычис.лить спектры сигналов н процессов, 15 в том числе и функций Уолша (2).

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

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

Поставленная цель достигается тем, что в устройство, содержащее

30 счетчик, блок адресации, блок зада849224 ния констант, блок умножения, сумматор, переключатель, блок сравнения, триггер, формирователь номера цикла, элемент И и блок управления, первый выход которого подключен к первому входу триггера, первый выход которого подключен к первому входу элемента И, выход которого подключен к первому входу блока управления, а второй вход элемента И соединен с первым выходом формирователя номера цикла, вход которого подключен к выходу сумматора, а второй выход формирователя номера цикла является первым выходом устройства и соединен с первыми входами переключателя и блока сравнения, выход которого подключен к второму входу триггера, второй выход которого подключен к второму входу переключателя, выход которого подключен к первому входу блока адресации, выход которого под- 20 ключен к входу блока задания констант, выход которого подключен к первому входу блока умножения, выход которого является вторым выходом устройства, вход счетчика является первым входом устройства, входрегистра является вторым входом устройства, выход регистра соединен с вторым входом блока сравнения, введены группа элемЕнтов И, генератор кода Грея, регистр сдвига, циклический регистр сдвига и блок формирования знака, выход которого подключен к второму входу блока умножения, а вход блока формирования знака соединен с первым входом регистра сдвига и первым выходом генератора кода Грея, второй и третий выходы которого подключены соответственно к первому и второму входам сумматора, а вход генератора кода Грея соединен с выходом счет- 40 чика, второй вход блока адресации объединен с вторым входом блока управления и подключен к выходам группы элементов И, входы которых подключены к первому выходу регистра 45 сдвига, второй выход которого подключен к третьему входу блока адресации, четвертый вход которого соединен с выходом циклического регистра сдвига, первый вход которого подключен к ® второму входу регистра сдвига и второму выходу блока управления, а второй вход циклического регистра сдвига соединен с третьим выходом блока управления.

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

На фиг.1 представлена структурная схема устройства; на фиг.2 — структурная схема блока управления °

Устройство содержит счетчик 1, группу 2 элементов И, блок 3 адресации, блок 4 задания констант, генератор 5 кода Грея, регистр б сдвига, блок 7 умножения, сумматор

8, циклический регистр.9 сдвига, переключатель 10, логический блок

11, регистр 12, блок 13 сравнения, триггер 14, преобразователь 15 кода элемент 16 И и блок 17 управления.

Счетчик 1 предназначен для приема с первого входа устройства начального номера гб(1,2,...,N-1 функции Уолша, спектр которой необходимо вычислить, и наращивания этого номера в естественном порядке (вычисление спектра для тривиального случая wal(0,х) в устройстве не предусмотрено).

Группа 2 элементов H предназначена для анализа на нуль состояния регистра б сдвига и формирования тем самым признака функции синуса, косинуса .(логический уровень единицы) или функции отсчетов (sin x)/х (логический уровень нуля).

Блок 3 адресации предназначен для формирования адреса (в общем случаепризнака) требуемой в процессе вычислений константы (значения функции). На первый его вход подается код kE$1 2,...,N-1) номера спектральной компоненты, адекватного номеру цикла работы. устройства. На второй вход подается одноразрядный признак функции синуса, косинуса (логический уровень единицы) или функции отсчетов (логический уровень нуля). На третий вход подается одноразрядный признак функции синуса (логический уровень единицы) или косинуса (логический уровень нуля). На четвертый вход подается код признака сомножителя Й: /2" аргумента функций, где

i6 $1,2,..., m=log

0... 01-й /2, 0... 010- /4, 0... 0100

46/8 и т.д.

Блок 4 задания констант предназначен для хранения или .формирования (в зависимости от конструкции) значений функций sin (Ю/2" ), cos (Ю/2 ), (я1п / =(sin klan/2 ) /(М/2 ) =Sa(kit/2" ), i© 1,2,...т), m=log>N.

849224

60 б5

Генератор 5 кода Грея предназначен для формирования на первом выходе кода Грея G(r) от числа r; на втором выходе-кода Грея G(2s) от числа 2; на третьем выходе — G(2s-l), S=r/2 для r-четных, S=(r/2)+1 — для

r — нечетных чисел.

На вход генератора 5 кода Грея подается двоичный код rе jl,2,...,N-1 номера функции Уолша. Конструктивно генератор может быть выполнен по лю" бому из известных методов преобразования двоичного кода в код .Грея.

Блок 7 умножения предназначен для выполнения последовательного перемножения операндов, поступающих на первый вход. Знак полученного произведения корректируется (присваивается) в соответствии ° с сигналом на втором входе. Результат на выходе может сопровождаться одноразрядным признаком действительной или мнимой величины.

Сумматор 8 предназначен для выполнения операции сложения по модулю два операндов, поступающих на первый и второй входы, т.е. G(2S)+G(2S-1), и управления работой преобразователя 15 кода.

Циклический регистр 9 сдвига предназначен для задания сомножителя

iC/2" аргумента функций в соответствии с тактом работы устройства путем циклического сдвига единицы. На первый вход регистра подается сигнал сдвига в сторону старших разрядов.

По второму входу организована начальная установка кода 0...01, а с выхода снимается параллельный код состояния.

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

Блок ll предназначен для формирования знака и признака действительной или мнимой величины (в общем . случае двухразрядный код на выходе) путем анализа количества функций Ра-. демахера, образующих данную функцию

Уолша. Логическая функция, выполняемая блоком, зависит от интервала представления функции Уолша,.

Регистр 12 предназначен для приема с второго входа устройства номера

km 1,2,...,N-1) вычисляемой спектральной компоненты соответствующей функции Уолша.

Блок 13 сравнения предназначен для формирования сигнала совпадения (логический уровень единицы) или несовпадения (логический уровень нуля) кодов, поступающих на первый и второй его входы.

Триггер 14 предназначен для формирования управляющих сигналов для переключателя 10 и элемента 16 И, соответственно на втором и первом выходах. По первому входу триггер

14 устанавливается в исходное нулевое состояние (высокий логический уровень напряжения на первом выходе), а второй вход является установочным.

Формирователь 15 предназначен для формирования кода номера цикла k6(l, 2,...,N — lj работы устройства и имеет особенности функционирования и конструктивных решений.

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

Блок 17 управления предназначен для синхронизации во времени структурных элементов устройства. По.входу, являющемуся управляющим, задается признак конца вычислений (высокий логический уровень напряжения),т.е ° прерывание работы устройства на данном цикле и переход на следующий цикл. Первый, второй и третий выходы являются импульсными, по которым организуется передача одиночных или групп импульсов в соответствии с законами функционирования структурных элементов .Устройства. Одиночные импульсные сигналы с первого и третьего выходов предшествуют началу каждого цикла работы устройства, обеспечивая установку исходных состояний триггера 14 и циклического регистра

9 сдвига. На второй выход блока 17 управления выдаются тактирующие импульсные сигналы, соответствующие тактам работы устройства с номерами в естественном порядке.

Блок 17 управления содержит (фиг.2) первый 18, второй 19, третий

20 и четвертый 21 элементы И, делитель 22 частоты, генератор 23 импульсов, регистр 24 сдвига и одновибратор 25.

Первые входы второго 19, третьего

20 и четвертого 21 элементов И соединены между собой и подключены к выходу генератора 23 и второму входу регистра 24,первый выход которого подключен к внешнему входу блока 17 управления и входу одновибратора

25, выход которого подключен к входу генератора 23, первый и второй входы блока 17 подключены соответственно к первому и второму входам первого элемента 18 И, выход которого подключен к второму входу второго элемента 19 И, выход которого подключен к входу делителя 22, выход которого подключен к второму выходу блока 17.

Первый выход блока 17 подключен к выходу второго элемента 19 И, второй вход которого подключен к первому

849224 выходу регистра 24, второй выход которого подключен к второму входу третьего элемента 20 И, выход которого подключен к третьему входу блока 17 °

Первый элемент 18 И предназначен для формирования сигнала прерывания работы блока 17 управления путем осуществления операции конъюнкции над сигналами прерывания вычислений и конца цикла. Второй элемент 19 И предназначен для управления передачей импульсных сигналов на второй выход блока 17. Третий 20 и четвертый 21 элементы И предназначены для формирования одиночных сигналов на первом и третьем выходах блока 17.

Делитель 22 частоты предназначен для формирования последовательности импульсов с периодом, равным времени выполнения операций блоками устройства в течение одного такта.

Генератор 23 импульсов обеспечивайт формирование последовательности импульсных сигналов.

Регистр 24 сдвига предназначен для управления работой третьего 20 и четвертого 21 элементов И ° По первому входу осуществляется запись единицы в младший разряд, а по второму входу — сдвиг информации в регистре.

Одновибратор 25 предназначен для задержки внешнего пускового сигнала при запуске генератора 23 импульсов.

Блок управления работает следующим образом. . По внешнему пусковому сигналу в момент времени „ (фиг.3) в младший разряд регистра 24 сдвига записывается единица и через время At одновибратор 25 запускает генератор 23 импульсов. Первый импульс с выхода генератора 23 передается на первый выход блока 17 управления (t ), так как на первом выходе регистра 24 присутствует логический уровень единицы, а на втором выходе — логический .уровень нуля. Этот же импульсный сигнал сдвигает единицу на один разряд в регистре 24 ° Следующий импульс, формируемый генератором 23, передается на третий выход блока 17 (Q ) и освобождает регистр 24 от информации.

При наличии разрешающих уровней напряжения на первом и втором входах блока 17 тракт передачи сигналов с выхода генератора 23 на второй выход блока 17 открыт, а делитель 22 частоты обеспечивает требуемую частоту формирования. на втором выходе сиг4 5)

Блокировка передачи сигналов на второй выход может быть осуществлена по любому из низких уровней напряжения на первом или втором входах блока.17 (Q,te). Очередной цикл работы блока 17 выйолняется аналогично (t, 9 ) Преобразователь 15 кода содержит

m (m=log2 N) схем преобразования, каждая из которых обеспечивает формирование последовательности кодов на выходе в соответствии с формулой

5 у =2 (2 f-l), 1,2,... N/2

j в(2,3,... m+1), (1) где j - номер разряда входного двоичного кода, адекватный номеру схемы в преобразователе, в котором записана единица.

Выбор схемы преобразования осуществляется m-разрядным управляющим кодом на входе.

После формирования всей последовательности на первый выход выдается сигнал конца последовательности (высокий логический уровень) .

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

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

wal(r,õ) =,и (R; (х) )

3() где R„ (х) =cos Ь, — функция Радемахера;

g„ -i-ый разряд кода Грея от номера r функции Уолша.

Спектр S-й функции Радемахера ра35 вен Яе (1, 2,...

)ik Tk 5" k

F (R (x)3 = -j sin — S — П cos—

5 .1 25 25 2 (2) 40 где k=1 2,...,N-1;

S - символ функции отсчетов (sin Х ) /2.

Выражение (2) имеет особый случай

4 при Я=1, для которого знак произведения изменяется на противоположный.

Спектр r-й функции Уолша определяется как свертка спектров соответствующий функций Радемахера на основа5Q нии (2) знак и призна действительно или мнимой ве личины юмб(г, )} =

sin —" 5 — ":х

2 2в (3) kl/$п -(ilg

П Gos —,) П г ) ;, где Я вЂ” максимальный номер функции

Радемахера в структуре ланной функции Уолша;

60 S — разность Z-S множества.

Ze(1,2,...,m) и номеров S функций

Радемахера из структуры r-й Функции

Уолша.

Знак и признак действительной

65 или мнимой величины в (3) онредсля849224

10 ется из условия интервала представления функций Уолша и Радемахера и для интервала -1/2 «(9» 1/2 справедливо соотношение

r знак и призна действительно

l или мнимой ве личины

=, 1) (-3) (4) К . а(где Π— количество функций Радемахера в представлении r-й функции Уолша;

g e (0,1) — значение первого

1 (младшего) разряда кода

Грея от номера r.

Работа устройства начинается,С формирования на первом выходе блока

17 управления сигнала, по которому триггер 14 устанавливается в нулевое состояние (на первом выходе уровень нуля, а на втором †. уровень единицы).

В следующий момент времени на втором выходе блока 17 вырабатывается сигнал установки в исходное состояние

0...01 регистра 9.

Процедура задания исходных данных заключается в записи с первого входа устройства в счетчик 1 номера функции

Уолша, спектр которой необходимо вычислить, и с второго входа устройства в регистр 12 номера спектральной компоненты. На этом подготовительный этап заканчивается.

Генератор 5 формирует на первом выходе код Грея С(г) от заданного номера г функции Уолша, который записывается в регистр 6 сдвига, а на втором и третьем выходах — соответственно коды. Грея G(2s) и G(2s-1), над которыми сумматором 8 выполняется операция сложения по модулю два °

В силу известных свойств кода Грея в сумме G(2s) + G(2s-1) присутствует только одна единица в одном из разрядов, а в остальных записаны нули.

Код этой суммы является управляющим для преобразователя 15 в соответствии с уравнением (1). Сформированный на втором его выходе код подается на первый вход блока 13 сравнения,на втором входе которого присутствует код состояния регистра 12. Если коды совпадают, на выходе блока 13 формируется уровень логической единицы, по которому триггер 14 переходит в единичное состояние, снимая тем самым блокировку тракта второй выход преобразователя 15 - первый вход переключателя 10 — первый вход блока 3.

В противном случае преобразователь 15 генерирует очередной код, т.е. работает до тех пор, пока не происходит совпадение кодов на входах блока 13 сравнения. Если совпадения не происходит, после генерации всей последовательности на первом выходе преобразователя 15 формируется логический уровень единицы (признак конца последовательности), который подается на второй вход элемента 16 И, на первом входе которого присутствует высокий логический уровень (нулевое состояние триггера 14).

Поэтому на выходе элемента 16 И формируется сигнал конца цикла, т;е. данная спектральная компонента равна нулю.

В общем случае первый такт работы устройства характеризуется формированием адреса на выходе блока 3 адресации, считыванием (вычислением) константы из блока 4 задания констант и передачей ее в локальную память блока 7. Это происходит следующим образом. Адрес (признак) константы на выходе блока 3 организуется в соответствии с набором сигналов на входах: на первом входе — код номера спектральной компоненты, адекgQ ватный номеру цикла; на втором входе — логический уровень единицы или нуля, т.е. признак функции синуса, косинуса либо функции отсчетов, соответственно; на третьем входе д логический уровень единицы или нуля (младший разряд кода Грея G(r), записанный в регистре 6, т.е. признак функции синуса либо косинуса, соот.— ветственно; на четвертом. входе — код

3() признака сомножителя Tc/2 аргумента функций, т.е. код 0..01, соответствующий сомножителю )с /2 . Этот набор сигналов обеспечивает формирование адреса блоком, 3 любой из констант вида sin (k ь/2 ), cos (k ь/2 ) и S (kVC/2 ) с последующим считыванием из блока 4 и передачей в локальную память блока 7. Таким образом, на первом такте работы состояния узлов и информационных магистралей

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

45 синуса либо косинуса, так как состояние регистра 6 не нулевое; б) передача информации на выход устройства из блока 7 блокирована, если на выходе элемента 16 И нет сиг5Q нала конца цикла; в противном случае на второй выход устройства передается нулевое значение и устройство переводится на первый такт второго цикла работы.

Второй такт вычисления заданной компоненты спектра r-й функции Уолша начинается с управляющего сигнала на втором выходе блока 17 управления, .по которому содержимое регистров,6

ЬО и 9 сдвигается на один разряд, и функционирование устройства по логическому содержанию повторяет. первый такт °

Количество тактов на первом цикле

65 определяется состоянием регистра 6:

849224

12 его нулевое состояние обеспечивает формирование группой 2 элементов И низкого логического уровня напряжения, который является признаком задания функции отсчетов от аргумента предыдущего такта и признаком последнего такта работы устройства на данном цикле. Значение функции отсчетов передается в блок 7, где выполняется последняя операция умножения и присваивается. знак с признаком действительной или мнимой величины в соответствии с логической Функцией блока 11. По сигналу ат блока 17 результат из блока 7 передается на второй выход устройства. Полученная величина является значением компо- 15 ненты спектра с номером, определяемым кодом на первом выходе устройства.

Второй цикл работы начинается с установки в исходное состояние 0...01 20 регистра 9 и триггера 14.По второму входу устройства задается номер очередной спектральной компоненты. Логическое содержание функционирования. устройства на втором и последующих циклах не отличается от первого цикла. Количество циклов определяется количеством вычисляемых спектральных компонент.

Таким образом, устройство на каждом цикле вычисляет в соответствии с уравнением (3) спектральные компоненты kе (1,2,...,N-1 функции Уолша.

Спектр следующей за номером ь функции Уолша находится аналогично,при этом состояние счетчика 1 увеличивается на единицу по сигналу от блока

17 управления.

Технико-экономическая эффективность предлагаемого устройства определяется повышением быстродействия, 40 расширением функциональных возможностей, повышением точности вычислений, что позволяет полностью исключить искажения и повысить разрешающую способность устройства, т.е. 45 обеспечивается возможность анализировать функции более высоких частот, при этом ограничения характеризуются не быстродействием элементной базы, а разрядностью конструкции. 50

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

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

ro подключен к первому входу элемента И, выход которого подключен к первому входу блока управления, а второй вход элемента И соединен с первым выходом формирователя номера цикла, вход которого поцключен к выходу сумматора, а второй выход Формирователя номера цикла является первым выходом устройства и соединен с первыми входами переключателя и блока сравнения, выход которого подключен к второму входу триггера, второй выход которого подключен к второму входу переключателя, выход которого подключен к первому входу блока адресации,выход которого подключен к входу блока задания константы, выход которого подключен к первому входу блока умножения, выход которого является вторым выходом устройства, вход счетчика является первым входом устройства, вход регистра является вторым входом устройства, выход регистра соединен с вторым входом блока сравнения, о т л и ч а ю щ е е с тем, что, с целью повышения быстродействия и расширения функциональных возможностей, в него введены группа элементов И, генератор кода Грея, регистр сдвига, циклический регистр сдвига и блок формирования знака, выход которого подключен к второму входу блока умножения, .а вход блока формирования знака соединен с первым входом регистра сдвига и первым вы.<одом генератора кода Грея, второй и третий выходы которого подключены ссответственно к первому и второму входам сумматора, а вход генератора кода Грея соединен с выходом счетчика, второй вход блока адресации объединен с вторым входом блока управления и подключен к выходам элементов И группы, входы которы подключены к первому выходу регистра сдвига, второй выход которого подключен к третьему входу блока адресации, четвертый вход которого соединен с выходом циклического регистра сдвига, первый вход которого подключен к второму входу регистра сдвига и второму выходу блока управления, а второй вход циклического регистра сдвига соединен с третьим выходом блока управления.

2. Устройство по п.1, о т л и ч а ю щ- е е с я тем, что блок управления содержит четыре элемента И, делитель частоты, генератор импульсов, регистр сдвига и одновибратор, выход которого соединен с входом генератора импульсов, выходы которого соединены с первыми входами трех элементов И и тактовым входом регистра сдвига, первый и второй выходы которого соединены с вторыми входами соответственно первого и второго.элементов И, выходы которых являются соответственно первым и третим выходами блока управления, первый и второй входы четвертого элемента И являются соответственно первым и вторым входами блока управления, а выход четвертого элемента И соединен

849224

14 фиг.1

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

Р 509872, кл. G 06 F 15/34., 1976 °

2. Авторское свидетельство СССР

Р 532863, кл. 6 06 Г 15/34, 1976 (прототип) .

849224 цикл 2 цикл Я бмхИ

Виход

Вход 1

Заказ 6095/64 Тираж 745 Подписное

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

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

Филиал ППП Патент, г.ужгород, ул.Проектная, 4

Составитель А.Баранов

Редактор Г.Кацалап Техред М.Голинка Корректор д.иван