Устройство цифровой фильтрации Советский патент 1988 года по МПК G06F17/17 H03H17/00 G06F17/14 

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

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

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

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

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

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

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

Функционирование устройства циф- ровой фильтрации, основано на свертке дискретных сигналов Х (т О, 1, ... ,0°) с взвешивающими коэффициентами hp (р О, 1i..., Р-1) посредством теоретико-числовых преобразований (ТЧП) по методу суммирования с перекрытием.

Прямое ТЧП последовательности Хи (п О, 1, ..., N-1) имеет вид:

s-r

XK(( ЦХп об - ))

П сО

где S - длина ТЧП,

k (0,1, ..., S-1).

(1)

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

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

где

е е

(2)

X« ((.fti )),

KtO

(О, 1, ..., S-1), S должно иметь обратное S по мо-.,-1

-i

дулю q и удовлетворять Sх S 51,

mod (

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

X,.s((T-X)),

H,,H((T-h.

S- ))

(За) (36)

i| .4i- lips-покомпонентных произведений в области преобразования:

.Y, ((X..®HJ) (4)

К

одного обратного ТЧП:

E((T

-)

Y,)).

(5)

0

5

5

0

5

0

Матрицы Т и Т в вьфажениях (За, Зб) составлены из коэффициентов ei и , взятых по modq.

Целые числа вида q , m - простое, есть числа Мерсенна. Существуют т-точечные ТЧП с корнем й6 2 и 2т - точечные ТЧП с корнем об -2, не требующие операций умножения. В обоих случаях умножение числа на et или uf. в выражениях (За, 36) и (5) сводится к сдвигу числа соответственно на n-k и e-k разрядов, влево или вправо.

В данном устройстве цифровой фильтрации для свертки последовательностей Х (т О, 1, ...,00 ) и hp (р О, 1, ..., Р-1) применен метод суммирования с перекрытием, вследствие чего последовательность Х условно разделяется на секции Х., j (п О, 1, ..., N-n -j О, 1, ...,оо) каждая секция сворачивается с после - довательностью hp посредством ТЧП по модулю чисел Мерсенна, а перекрывающиеся отсчеты свертки с двумя соседними свертками Yg ,, и , складьшаются.

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

S(N+P-1)M, при et 2 1 S(N+P-1)2M, при о6 -2J

При вьиислении свертки посредст- вом ТЧП по модулю чисел Мерсенна все вычисления производятся над последовательностями целых чисел и результаты свертки получаются по mod q без ошибок округления. Однако значение q должно гарантировать, что результаты Yg свертки последовательностей (п 0, 1,..., N-1, р О, 1, ..., Р-1), вьиисленной по modq, и результаты свертки Y этих же последовательностей будут равны. В кольце целых чисел с операциями по modq (q ) обычные целые числа могут быть представлены однозначно, если их абсолютное значение меньше q/2 и масштаб чисел последовательобностей Х и hn выбирается таким С

разом, чтобы (Y) никогда не превышало q/2.

Арифметика по модулю q 2 -1 известна как арифметика в обратных кодах. Отсчеты hp перед выполнением теоретико-числовых преобразований представляются в обратных кодах. В дальнейшем, при выполнении прямого преобразования, умножения, обратного преобразования все операции над числами выполняются без учета знака, вследствие чего результаты свертки посредством ТЧП по модулю чисел Мерсенна будут всегда целыми и условно положительными.

Соответствие результатов обычной свертки последовательностей Х и h и свертки посредством ТЧП по модулю чисел Мерсенна (q 2 -1) обеспечивается следующим образом:

если О Y.

q-1

то Y н Y,

е

если

q-1

Yg q, то ,

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

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

Работа устройства цифровой фильтрации, использующего ТЧП по модулю чисел Мерсенна, осуществляется следующим образом. Входные отсчеты Х (т О, 1, ...,00 ) условно разделенные на секции Х„ (т О, 1,..., ..., N-1; j 0, 1, ...,оо), последовательно поступают на вход блока 1

10 прямого преобразования и стробирую- 1Щ1МИ импульсами с первого выхода 31 блока 4 управления на входы синхронизации регистров 15 буферной памяти, одновременно сдвигающими двоичное

15 число с выхода каждого i-го регистра в ((1+1)-й регистр (i 1, 2,..., ..., N)), записывается в первьй регистр 16 буферной памяти 15. После записи (N-l)-ro отсчета j-й секции

20 X „ сигналом с второго выхода 32 блока 4 управления на управляющие входы ключей узла 12 циклического сдвига состояние выходов каждого i-ro регистра 15 буферной

25 памяти записывается в соответствующий i-й регистр циклического сдвига (i 1, 2, ..., N) узла 12 циклического сдвига.

Каждый i-й регистр циклического

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

Х согласно вьфажению (За) осуществляется следуюпщм образом. Компонент Хд получается в результате суммирования входных данных X с выходов регистров 13,-13ц циклического сдвига узла 12 циклического сдвига на сумматоре 11 по mod q. Вычисление каждого из следующих компонентов вектора X(X,, Х, ..., X(-,)) осуществляется путем однократного, многоразрядного сдвига данных в узле 12 циклического сдвига и суммирования результатов сдвига на сумматоре 11 по fflodq. Одновременный сдвиг данных осуществляется подачей стробирующе- го сигнала с третьего выхода 33 блока 4 управления на входы синхронизации регистров циклического сдвига узла 12 циклического сдвига. Обнуление регистров циклического сдвига узла 12 циклического сдвига производится сигналом с четвертого выхода 34 блока управления 4.

Каждый вычисленный компонент век

тора X

ко

с выхода блока 1 прямого

преобразования и соответствующий ему компонент вектора Н, считанный из блока 5 памяти коэффициентов стробом выборки с седьмого выхода 35, по адресу с шестого выхода 36 блока 4 подаются на соответствующие входные шины умножителя 6 и тактирующим импульсом с пятого выхода 37 блока 4, записываются во входные регистры умножителя 6. Результаты умножения Y , приведенные по модулю q на сумматоре 7 по mod q стробирующими импульсами с восьмого выхода 38 блока 4 на входы синхронизации регистров 21 буферной памяти одновременно сдвигающими двоичное число с выхода каждого К-го регистра в (К+1)-й регистр (К 1, 2, ... R), записываются в буферную память 21.

После записи (S-l)-ro отсчета j-й секции YH (К О, 1, ..., S-1; j 0, 1,,..,оо) сигналов с девятого 39 .выхода блока 4 на управляющие входы узла 18 циклического сдвига сое- тояние выхода каждого К-гр регистра 21 буферной памяти записывается в соответствующий К-й регистр циклического сдвига (К 1, 2, ..., R) узла 18 циклического сдвига. Каждый К-й регистр циклического сдвига узла 18 циклического сдвига блока 2 обратного преобразования циклически сдвигает двоичное число за один так на (R-K) разрядов вправо. Обнуление регистров циклического сдвига узла 21 циклического сдвига производится сигналом с одиннадцатого выхода 40 блока 4.

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

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

ходов регистров циклического сдвига 19,-19, узла 18 циклического сдвига на блоке 17 сумматоров по modq. Вычисление каждого из следующих компонентов вектора YJ (YJ , Y, ..., Yg, осуществляется путем однотактното, многоразрядного сдвига данных Y в регистрах циклического сдвига и суммирования результатов сдвига на блоке 17 сумматоров по mod-q.

5

0

g

g g

5

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

Каждый вычислеиньй компонент вектора Yg записывается в блок 9 памяти стробом выборки с четырнадцатого выхода 42 по команде Запись с тринадцатого выхода 43, по адресу с двенадцатого выхода 44 блока 4 управления.

Компоненты следующего (j+1)-ro вектора Yg записываются в блок 10 памяти стробом выборки с семнадцатого выхода 45 по команде Запись с шестнадцатого выхода 46 и по адресу с пятнадцатого выхода 47 блока 4 управления.

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

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

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

Блок 4 управления работает следующим образом. Тактовые импульсы, поступающие от генератора 23 тактовых импульсов на счетчик 24 адреса

7

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

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

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

Целесообразна реализация устройства цифровой фильтрации на основе БИС-технологии (в частности на базовых матричных кристаллах (БМК) типа 1515ХМ2), так как, например, комцлек из блока 1 прямого преобразования, блока 2 обратного преобразования и умножителя 6 имеет всего две входные, одну выходную шину и девять управляющих выводов.

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

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

10

15

20

25

46627

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

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

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

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

10

IS

20

U6627

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

25

35

40

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

(fji rajs 4 Гз ej вТэ ю Гц jT2ji3Ti4 isjie i7Ti8 | i9 20

1ДИ i

1

6

7 8

9 10

1

1

1

1

1 1

1 1

I

Мб 19 120

12

13 14

15 16

17

1001

1

1 О 1

1 1 О

1010 1001 10 1 1

1

1100 1010 1101

1110

1011

1000

000

1 0.0

о о 1

13

1

1

.

1

1

11

1

1 1

11

1

1 1

11

1

1 1

11

1

1 1

1

1А46627

.14

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

010 001

1

011

1 01

1

1100 10 1 о 1101

1 1 о

1110

1011

Г

Фиг.1