Устройство цифровой фильтрации

 

Изобретение относится к вычислительной технике, в частности к устройствам цифровой фильтрации, ос-тЖ нованным на методе свертки с использованием теоретико-числовых преобразований . Целью изобретения является повьшение быстродействия за счет параллельной обработки данных. Устройство содержит блоки прямого 1 и обратного 2 преобразований, сумматор 3, блок 4 управления, блок 5 памяти коэффициентов , умн ожитель 6, первый 9 и второй 10 блоки памяти, коммутатор 8, сумматор 7 по модулю q, буферную память 15, узел 12 циклического сдвига, сумматор 11 по модулю q, буферную память 21, узел 18 циклического сдвига, сумматор 17 по модулю q. 3 з.п. ф-лы, 2 ил., 1 табл. ел о MTfiHT „ ttn)i г Ф «м./

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

° СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (19) (11) 2 А1 (5g 4 G 06 F 15/353, 15/332

Ц.. .1 Яай1П

%,:-„Л:,6;- ЯСИН

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

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

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

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

ПРИ ГННТ СССР (21) 4247372/24-24 (22) 19,05,87 (46) 23. 12.88. Бюл. В 47 (72) Б.П.Курганов и В.В.Парфентьев (53) 681:32 (088.8) (56) Авторское свидетельство СССР

М 1161954, кл. G 06 F 15/332, 1983.

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

В 1297073, кл. G 06 F 15/332, 1985.

Заявка Франции В 2308144, кл. G 06 F 15/332, опублик. 1976. (54) УСТРОЙСТВО. ЦИФРОВОЙ ФИЛЬТРАЦИИ (57) Изобретение относится к вычислительной технике, в частности к устройствам цифровой фильтрации, основанным на методе свертки с использованием теоретико-числовых преобразований. Целью изобретения является повышение быстродействия за счет параллельной обработки данных. Устройство содержит блоки прямого 1 и обратного 2 преобразований, сумматор 3, блок 4 управления, блок 5 памяти коэффициентов, умножитель 6, первый 9 и второй 10 блоки памяти, коммутатор 8, сумматор 7 по модулю q, 6yферную память 15, узел 12 цикличес кого сдвига, сумматор 11 по модулю

q буферную память 21, узел 18 циклического сдвига, сумматор 17 по модулю q. 3 з.п. ф-лы, 2 ил., 1 табл.

1446627

Изобретение относится к вычислительной технике, в частности к устройствам цифровой фильтрации, основанном на методе свертки с использованием теоретико-числовых преобразований (ТЧП).

Цель изобретения — повышение быстродействия за счет параллельной обработки данных. 10

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

Устройство цифровой фильтрации 15 содержит блок 1 прямого теоретикочислового преобразования, блок 2 обратного теоретико-числового преобразования, сумматор 3, блок 4 управления, блок 5 памяти коэффициен- 20 тов, умножитель 6, сумматор по модулю q 7, коммутатор 8, блоки 9 и 10 памяти.

Блок 1 прямого теоретико-числового преобразования содержит сум- 2 матор 11 по модулю q, узел 12 циклического сдвига, содержащий И циклических сдвиговых регистров 13, -13„ и N ключей 14<-14< буферную память

15, содержащую N регистров 16, -16 . 30

Блок 2 обратного теоретико-числового преобразования содержит. сумматор 17 по модулю q, узел 18 циклического сдвига, содержащий R циклических сдвиговых регистров 19< -19< и R ключей 20, -20, .буферную па35 мять 21, содержащую R регистров

22,-22 .

Блок 4 управления содержит тактовый генератор 23, счетчик 24 адресов памяти, элемент НЕ 25, память 26, счетные триггеры 27-29, счетчик 30 адресов.

Функционирование устройства циф"ровой фильтрации, основано на свертке дискретных сигналов XÄ (m = О, 1... °,с>) с взвешивающими коэффициентами Ь (р = О, 1,..., Р-1) посредством теоретико-числовых преобразований (ТЧП) по методу суммиро50 вания с перекрытием.

Прямое ТЧП последовательности

Х» (n = О, 1, ..., N-1) имеет вид: 55 & -1

=-((,Г x„<" ")) (1)

».о где S - длина ТЧП, k - (0,1, ..., $-1).

Двойные скобки означают, что сумма должна быть вычислена по модулю q (mod q) .

Обратнре преобразование определяется следующим образом:

5-1 -4 х, = (($ x„ ") ), (2) ко где е = (О, 1, ..., $-1), S должно иметь обратное S по мо,-1 дулю q и удовлетворять S x S

1NodsСвойство цикличности свертки поз= воляет непосредственное вычисление

S-точечной свертки заменить вычислением двух прямых ТЧП последовательностей Х„ и Ь

Х„=-((Т Х.)), (За) Н ((Т Ь S )) (Зб)

S-покомпонентных произведений в области преобразования: к =- ((Хм®Нк)) (4) одного обратного ТЧП:

Уе =((Т Ук)) (5)

-/1

Матрицы Т и Т в выражениях (За, Зб) составлены из коэффициентов Ы."" и 6-ек взятых по шоач.

Э

Целые числа вида q = 2 -1, m— простое, есть числа Мерсенна. Существуют ш-. точечные ТЧП с корнем Ы =

= 2 и 2m — точечные ТЧП с корнем о =

= -2, не требующие операций умножения. В обоих случаях умножение числа на » или о е в выражениях (За, Зб) и (5) сводится к сдвигу числа соответственно на n-k и е-1с разрядов, влево или вправо.

В данном устройстве цифровой фильтрации для свертки последовательностей

Х (m=O. 1, ...,oo) иЬр (p =U, Р"1) применен метод суммирования с перекрытием, вследствие чего последовательность Х„„ условно разделяется на секции Х, j (n =

Оу 1 ° е ° у Ni p,1 Ор 1 p ° ° ° у ) каждая секция сворачивается с после— довательностью Ь посредством ТЧП по модулю чисел Мерсенна, а перекрывающиеся отсчеты свертки Уе с двумя соседними свертками Y, и

Е, 1Y „ складываются.

То обстоятельство, что свертка методом суммирования с перекрытием требует выполнения циклических (N+

+Р-1) — точечных сверток, учитыва1446627 ется при выборе S u q в выражениях (1) и (3), где S должно удовлетворять равенству:

S=(N+P-1)=M, при « = 2

S= (N+P-1) =2М, при еС, -2 J (6) При вычислении свертки посредством ТЧП по модулю чисел Иерсенна все вычисления производятся над последовательностями целых чисел и результаты свертки получаются по шо<1<1 без ошибок округления. Однако значение q должно гарантировать, что результаты Y свертки последовательностей Х„и Ь (и = О, 1, ..., М-1, р = О, 1, ..., P-1), вычисленной по

mod q, и результаты свертки Y этих же последовательностей будут равны.

В кольце целых чисел с операциями по

mod q (q = 2 -1) обычные целые числа могут быть представлены однозначно, если их абсолютное значение меньше q/2 и масштаб чисел последовательностей X„ H h > выбирается таким образом, чтобы (У ) никогда не превышало q/2.

Арифметика по модулю q = 2 -1 известна как арифметика в обратных кодах. Отсчеты Х и h перед выполнением теоретико-числовых преобразований представляются в обратных кодах.

В дальнейшем, при выполнении прямого преобразования, умножения, обратного преобразования все операции над числами выполняются без учета знака, вследствие чего результаты свертки посредством ТЧП по модулю чисел Иерсенна будут всегда целыми и условно положительными.

Соответствие результатов обычной свертки последовательностей Х„ и h и свертки посредством ТЧП по модулю

m чисел Мерсенна (q = 2 -1) обеспечивается следующим образом:

q-1 если Оа7 а, то Y, =-Y

z Y cà q, To Ym» Y<,-q, q-1 что достаточно просто реализуется в обратных кодах. Для определения действительного знака и результатов свертки, из результатов свертки, вычисленных посредством ТЧП по модулю чисел Мерсенна, достаточно к двоич-. ному коду Y добавить знаковый разряп, и записать в него состояние старшего (M-1)-ro разряда.

1О

Работа устройства цифровой фильтрации, использующего ТЧП по модулю чисел Мерсенна, осуществляется следующим образом. Входные отсчеты Х (ш = О, 1, ..., oo ) условно разделенные на секции Х„ (m = О, 1,..., N-1, j О, t, ... оо) послед. довательно поступают на вход блока 1 прямого преобразования и стробирующими импульсами с первого выхода 31 блока 4 управления на входы синхронизации регистров 15 буферной памяти, одновременно сдвигающими двоичное число с выхода каждого i-ro регистра в {(i+1)-й регистр (i = 1, 2,..., И)), записывается в первый регистр 16< буферной памяти 15. После записи (N-1)-ro отсчета j-й секции

Х „ сигналом с второго выхода 32 н.1 блока 4 управления на управляющие входы ключей 14, -14„ узла 12 циклического сдвига состояние выходов каждого i-го регистра 15 буферной памяти записывается в соответствующий i-й регистр циклического сдвига (i = t, 2, ..., N) узла 12 циклического сдвига.

Каждый i-й регистр циклического сдвига узла 12 циклического сдвига блока 1 прямого преобразования циклически сдвигает двоичное число эа один такт на (N-i) разрядов влево.

Вычисление компонентов вектора

Х согласно выражению (За) осущестК вляется следующим образом. Компонент

Х получается в результате суммироо вания входных данных Х„с выходов регистров 13< — 13<,, циклического сдвига узла 12 циклического сдвига на сумматоре 11 по mod q. Вычисление каждого из следующих компонентов вектора Хк (X,, Xgp ..., Х(„,1) осуществляется путем однократного, многоразрядного сдвига данных в узле 12 циклического сдвига и суммирования результатов сдвига на сумматоре 11

no mod q. Одновременный сдвиг данных осуществляется подачей стробирующего сигнала с третьего выхода 33 блока 4 управления на входы синхронизации регистров 13, -13 циклического сдвига узла 12 циклического сдвига.

Обнуление регистров циклического сдвига узла 12 циклического сдвига производится сигналом с четвертого выхода 34 блока управления 4.

Каждый вычисленный компонент вектора X к с выхода блока 1 прямого

1446627

55, 5 преобразования и соответствующий ему компонент вектора Н„, считанный из блока 5 памяти коэффициентов стробом выборки с седьмого выхода 35, по адресу с шестого выхода 36 блока 4 подаются на. соответствующие входные шины умножителя 6 и тактирующим импульсом с пятого выхода 37 блока 4, записываются во входные регистры умножителя 6. Результаты умножения

Y, приведенные по модулю q на сумматоре ? no mod q стробирующими импульсами с восьмого выхода 38 блока

4 на входы синхронизации регистров

21 буферной памяти одновременно сдвигающими двоичное число с выхода каждого К-го регистра в (К+ 1)-й регистр (K = 1, 2, ..., R), записываются в буферную память 21.

После записи (S-1)-ro отсчета j-й секции Y (К = О, 1, ..., S-1;

= О, 1,...,оо) сигналов с девятого

39,выхода блока 4 на управляющие входы узла 18 циклического сдвига состояние выхода каждого К-ro регистра 21 буферной памяти записывается в соответствующий К-й регистр циклического сдвига (К = 1, 2, . ° ., R) узла 18 циклического сдвига. Каждый

К-й регистр циклического сдвига узла

18 циклического сдвига блока 2 обратного преобразования циклически сдвигает двоичное число за один такт на (К-К) разрядов вправо. Обнуление регистров циклического сдвига узла

21 циклического сдвига производится сигналом с одиннадцатого выхода 40 блока 4.

После записи компонентов i-й секции Y â устройстве 21 циклического сдвйга, буферная память принимает следующую секцию компонентов У„

Вычисление компонентов в векторе

Y согласно выражению (5)„ осуществляется следующим образом. Компонент

Y получается в результате суммироо вания компонентов вектора Y с вык ходов регистров циклического сдвига

19, — 19к узла 18 циклического сдвига на блоке 17 сумматоров по mod q ° Вычисление каждого иэ следующих компонентов вектора Уе (Y Y, ..., Y,) осуществляется путем однотактного, многоразрядного сдвига данных Ук в регистрах циклического сдвига и суммирования результатов сдвига на блоке 17 сумматоров na mod q, 5

6

Одновременно сдвиг данных осуществляется стробирующим сигналом с десятого выхода 41 блока 4 на входы синхронизации регистров циклического сдвига .узла 18 циклического сдвига.

Каждый вычисленный компонент вектора У записывается в блок 9

Е,1 памяти стробом выборки с четырнадцатого выхода 42 по .команде "Запись" с тринадцатого выхода 43, по адресу с двенадцатого выхода 44 блока 4 управления.

Компоненты следующего (j+1)-го вектора Y е, записываются в блок

1 J

10 памяти стробом выборки с семнадцатого выхода 45 по команде "Запись" с шестнадцатого выхода 46 и по адресу с пятнадцатого выхода 47 блока 4 управления.

Для организации суммирования перекрывающихся компонентов (отсчехоа) векторов Уе, по методу cymm1 рования с перекрытием, перекрывающиеся компоненты двух соседних векторов У q и Уе считываемых из блоков 9 и 10 памяти складываются на сумматоре 3. Подключение старших (М-1)-х разрядов выходов первого 9 и второго 10 блоков памяти результатов преобразований к М-му разряду входных шин сумматора 3 позволяет выполнять сложения в обратных кодах.

На фиг.2 представлена функциональная схема блока 4 управления, выполненного как микропрограммное устройство и построенного на основе памяти 26 для случая работы устройства цифровой фильтрации по модулю q=12? с корнем о4 =2.

Генератор 23 вырабатывает тактовые импульсы. Счетчик адресов 24 вырабатывает адреса для памяти 26.

Счетчик адресов 30 вырабатывает адреса для памяти коэффициентов блока

5. Счетные Т-триггеры 27-29 предназначены для формирования управляющих импульсов необходимой длительности. Последовательность микрокоманд, необходимых для управления устройством цифровой фильтрации, записана в памяти 26 и приведена в таблице (отсутствие данных в таблице означает наличие логического "0" в памяти 26), Блок 4 управления работает следующим образом. Тактовые импульсы, поступающие от генератора 23 тактовых импульсов на счетчик 24 адреса

1 памяти и элемент НЕ 25, вызывают последовательную смену адресов на адресных шинах 26 памяти и считывание хранимой по этим адресам информации (микрокоманд), так как число управляющих микрокоманд составляет 64, то установка счетчика 24 адресов памяти в исходное состояние пррисходит автоматически с периодом 2 .

Память 26 и память коэффициентов блока 5 (фиг. 1) могут быть выполнены яа ИИС типа 573 РР 2.

Все остальные компоненты устройства цифровой фильтрации могут быть выполнены на HMC сер. 564.

Целесообразна реализация устройства цифровой фильтрации на основе

БИС-технологии (в частности на базовых матричных. кристаллах (БИК) типа

1515XM2), так как, например, комцлекс из блока 1 прямого преобразования, блока 2 обратного преобразования и умножителя 6 имеет всего две входные, одну выходную шину и девять управляющих выводов.

446627

3 ра является выходом устройства, о тл и ч а ю щ е е с я тем, что, с целью увеличения быстродействия за

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

q„ выход которого соединен с информационным входом блока обратного теоретико-числового преобразования, выход которого соединен с информационным входом коммутатора, управляющий вход которого соединен с входом

20 записи-считывания первого блока памяти и двенадцатым выходом блока управления, адресный вход и вход выборки первого блока памяти соединены соответственно с тринадцатым и че25 тырнадцатым выходами блока управления, информационный вход первого блоформула изобретения

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

2. Устройство по п. 1, о т л и— ч а ю щ е е с я тем, что, с целью сокращения оборудования, блок прямого теоретико-числового преобразования содержит сумматор по модулю узел циклического сдвига, сос-, тоящий из N ключей и N регистров циклического сдвига, буферную память, содержащую N регистров, причем выход сумматора по модулю q является выходом блока, i — и вход сумматора по модулю q, где i = 1, 2,..., N, N-разрядность q, соединен с выходом i-ro регистра циклического сдвига, информационный вход которого соединен с выходом i-го ключа, информационный вход которого соединен с выходом i-го регистра и информационным входом (i+1)-го регистра, входы записи всех регистров соедине14466 и 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 6 17 18 19 20

0 1

1 0 0 0

1 0 0

1 0 0 0

1 1

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

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

q, где i = 1, 2, ..., R, R-разрядность q, соединен с выходом i-ro регистра циклического сдвига, информационный вход которого соединен с выходом -го ключа, информационный вход которого соединен с выходом 25

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

4. Устройство п. 1, о т л и ч а35 ю щ е е с я тем, что блок управления содержит тактовый генератор, счетчик адресов памяти, элемент НЕ, память, первый, второй и третий счетные триггеры и счетчик адресов, причем выход тактового .генератора соединен со счетным входом счетчика ад"

27

l0 ресов памяти и входом элемента НЕ, выход которого соединен с входом выборки памяти, адресный вход которой соединен с выходом счетчика адресов памяти, первый выход памяти соеди-. нен с первым выходом блока, второй выход памяти соединен с четвертым выходом блока, третий выход памяти соединен с вторым выходом блока и входом обнуления счетчика адресов, выход которого соединен с шестым выходом блока, счетный вход счетчика адресов соединен с третьим выходом блока и четвертым выходом блока памяти, пятый выход которого соединен с информационным входом третьего счетного триггера, выход которого соединен .с седьмьпи выходом блока, с шестого по восьмой выходы памяти соединены соответственно с пятым, восьмым и одиннадцатым выходами блока, девятый выход памяти соединен с девятым выходом блока и тактовыми входами всех счетных триггеров, десятый и четырнадцатый выходы блока соединены соответственно с десятым и одиннадцатым выходами памяти, двенадцатый выход которой соединен с информационным входом второго счетного триггера, выход которого соединен с тринадцатым выходом блока, с тринадцатого по пятнадцатый выходы памяти .являются двенадцатым выходом блока, семнадцатый выход которого соединен с шестнадцатым выходом памяти, семнадцатый выход которой соединен с информационным входом первого счетного триггера, выход которого соединен с шестнадцатым выходом блока, с восемнадцатого по двадцатьй выходы блока памяти являются пятнадцатым выходом блока.

2

Продолжение таблицы

1446627

1 0 0

12

1 О 1 0!

1 0 0 1

1 0 1

1 1

1 0 1 1

18

20

1 1 О О

1 0 1 0

1 1 0

23

1 1

1 1 0 1

25

27

1 1 1 0

29

1 0 1 1

32

34

1 0 0 0

37

1 0 0 0

1 0. 0

1 1

1 0 0 1

41

43

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

1446627

Продолжение таблицы

1 0 1 0

1 0 0 1

1 1

1 0 1

47 1

1 0 1 1

49

51

1 1 0 0

54

1 0 1 0

1 1 0

55 1

1 1

1 1 0 1

58

60

1 1 1 0

62

1 0 1 1

63 1

Э 1 2 3 4 5 6 7 8 9 10 i i i2 i3 14 15 16 it 16 19 20

144б627

Составитель К.Воробьев

Редактор С.Патрушева Техред М.Дидык Корректор В.Бутяга

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

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4