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

Авторы патента:

G06F17/17 - вычисление функций приближенными методами, например интерполяцией или экстраполяцией, сглаживанием, методом наименьших квадратов (интерполяция для числового управления G05B 19/18)

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

QWIC7

РЕСПУБЛИК

„SU,, 101412

ЗЮ Н 0 H 1 /06 G 06 F 1 !.

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

ГЮ ДЕЛАЮ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

;,0ОПИСАНИЕ ИЗОБРЕТЕН Я ..

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

° \

МЬ

° Ю (21) 3367440/18-24 (22) 21. 12.81 (46) 23.04.83. Бюл..М 15 (72) В.А.йащенко (71) Днепропетровский ордена Трудового Красного Знамени государственный университет им, 300-летия воссоединения Украины с Россией (53) 681.32 (088.8) (56) 1. Рабинф Л., Гоулд Р. Теория и применение цифровой обработки сигналов. M., "Мир", 1978.

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

11 800995, m. G 06 F 15/33, 1981 (прототип), (54) (57) l. УСТРОЬ:ТВ0 ДЛЯ ВЦЧИСЛЕНИЯ СВЕРТКИ В БАЗИСЕ ЖЕГАЛКИНА, содержащее первый и второй блоки преобразования базиса, причем информационный вход первого блока преобразования базиса является информационным входом устройства, а выход второго блока преобразования базиса являет-. ся информационным выходом устройства, . о т л и ч а ю щ е е с я . тем, что, с целью повывения быстродействия и упрощения устройства, оно содержит сдвиговый регистр, элемент И H счетчик, i-й (1 1, п) выход которого сое" динен с i-м управляющим входом первого и второго блоков преобразования базиса, выход первого блока преобразования базиса, подключен к первому входу элемента И, выхбд которого соединен с информационным входом второго блока преобразования базиса, выход сдвигового регистра подклю- 3 чен к его входу и второму входу элемента И, а тактовый вход счетчика является синхронизирующим входом устройства.

101412б

2. Устройство по и. 1, о т л и - соединен с входом (1+1)-.-о сдвиговоч а ю щ е е с я тем, что блок яре- ro регистра и вторым входом (1+1)-ro ..образования базиса содержит и сдви- ; сумматора по модупю .два, выход и-го говых регистров, причем разрядность сумматора по модулю два является выхо1-го сдвигового регистра равна 21 " : дом блока преобразования базиса, вто(1рдГ, л), и элементов И и и суммато" рой вход первого сумматора по модулю ров по модулю два, выход 1 ãî сдви- два и вход первого сдвигового регистrosoro регистра подключен к первому ра объединены и являются информационвходу i-го элемента И, выход которо-,ным входом блока преобразования, втого соединен с первым входом 1-ro сум- рой вход 1-го (IT, n) элемента И явматора по модулю два, выход I.. го ляется 1-м управляющим входом блока ((1, и-Д сумматора по модулю даа праобрааоаамма брамса.

1$. 30.И, выход которого соединен с информа,.ционным входом второго блока преоб2$ разования базиса, выход сдвигового регистра подключен к его входу и

30 При этом блок преобразования ба" зиса содержит и сдвиговых регистров, 1

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

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

Однако данное устройство не предназначено для вычисления свертки в базисе Жегалкинааа

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

Однако и это устройство не может использоваться при вычислении сверт2 ки в базисе Жегалкина и достаточно сложно.

Цель изобретения состоит в упрощении устройства за счет фильтрации двоичных последовательностей в базисе. Жегалкина.

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

: вход счетчика является синхронизиру-

;ющим ьходом устройства. причем разрядность i-го сдвигового регистра равна 2 "(i l ï), и элементав И и и сумматоров по. модулю два, выход ч -го сдвигового регистра подключен к первому входу I-ro элемента И, выход которого соединен с первым входом i-ro сумматора по модулю два, выход i-го (i l, n-1) сумма14126 . 4

Рассмотрим алгоритм фильтрации

"двоичных последовательностей длины

2, реализуемый данным устройствомр (добавлением соответствующего чис-

5 ла нулей длину последовательности всегда можно сделать равной степени двойки).

Преобразователь 1 умножает 2 компонентный вектор входной последо- е вательности, состоящей из нулей и еди- . ниц, íà и-ю кронекерову степень матрицы

GÄ= х 4

15 являющейся l.-й кронекеровой степенью.

При этом сложение выполняется по модулю два.

I J

Вторая кронекерова степень мат

2o ðèöû 6„ размера 2 х21 имеет вид

4 6

1 а

1 1

° 1 4

1 0

j e

О 0 О

О 6 6

1 0 0

1 .1 О

9 0

0 О I

+ 0,1

1 1 1

0 ©О ®.2

U Оо О+ А Э ОЭ

uOuÄ®v,O+u

Q©Q+U Q+U+O+U ц Оо Оu

3 Ф 5 Ь t

МеЦ

" тд

С О О

0 О О

9 0 О б О О

0 9 О

0 О

0 1 0 1 1 I

ОЭ

U(, О. где через (+) обозначена сумма по мо- спектром последовательности ВО,О „. дулю два. 55 О.,н )в базисе Жегалкина а выражена

Вектор fu+ о ...,,0 „3, оостоя-., Л) йредставляет собой матрену. Лара» щий из нулей и единиц (сложение. выпол- хода в область иэображения " матриняется по модулю два), называется : цу прямого преобразования.

3 10

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

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

Устройство для вычисления сверт" ки содержит блоки преобразования базиса 1 и 2, фильтр 3, состоящий иэ элемента Й 4 и 2 -разрядного сдви.гового регистра 5, используемого для

;хранения коэффициентов передаточной функции,:выход которого соединен с . его входом, а также п.-разрядный счет. чик 6. Информационным входом устройства служит вход 7 блока преобразования 1, а выходом является выход 8 блока преобразования 2. Вход 9 счет. чика 6 .представляет собой вход синхронизации устройства.

Блок-преобразования 1 {или 2) содержит и сдвиговых регистров 10 -10,, вр n логических элементов И 11 -llew и и сумма1оров по: модулю два 12.-12,.

Вторые входы логических элемейтов и 11.-11п служат управляющими входами 13. -13, блока преобразования. Разрядность регистра 10„ равна единице, а количество разрядов каждого после- дующего регистра увеличивается вдвое„ в

ci„o

25 где 0„- матрица (2X2) из одних нулей и-я кренекерова степень 6 размера

2 «2 олределяется черве Ь-11-р кронекерову степень G 1:2 к2 ) слеауюшим образом

6„„0

0 Gh1 Gh1 где 0„ „- матрица размера 2 из одних нулей.

При п3 входная последовательность|; определяемая 8-компонентным вектором (Оор О, р О р Озр О, О,р 0, О-.Д, е

40 где О.е10,1), умножается-посредством . преобразователя 1 на матрицу

1014126 4

Фильтр 3 непосредственно осуще- в сдвиговом регистре 5 и состоящий ствляет фильтрацию - покомпонентное только иэ нулей и единиц.

° ° °

/ воичной последовательности Г0, Для и 3 функциониро ункционирование фильтра

,...,0 п„„ на вектор передаточной ф 3 описывается следующим матричным функции (Но,Н.,... Н2я 13, хранимый соотношением о î î о

О О О О

0 0 О О

О 0 О О и О 0 0

О И

0 О ИЬО

О О 0 й1 к

Отличны от нуля и равны единице только те компоненты вектора (н {У

0r, J„„: .-°-, U2n „„3 „для которых как

Ж, та и Н 1. е

Блок преобразования 2 осуществляет обратный переход от базиса Мегалкина к базису, состоящему иэ 2" единичных векторов, только одна компонен--, та которых отлична от нуля и равна единице. Этот переход из области иэоб33 глажения в область оригинала реализуется посредством умножения вектора (НоОо, И„О, ° ..,Н п. 0 и на матРи-. цу (.1); которая являешься матрицей обратного преобразования, Базис Жегалкина образует векторы, являющиеся столбцами матрицы обратно. го преобразования - матрицы (1).

При и 3 переход иэ области иэображения в область оригинала можно записать в следующей матричной форме

О О О О О О О

О О 0 О. О О

О 1 О О 0.0 О

1 1 1 О 0 О О

ОООа000 1 0,0 1 1.0 0

1 О 1 О е 0 W 9

1 -1 1 1 1 1 1

Н 0

Н Ц

"з "з

4 4

Ю. %

Ь Ь

Н О

Вектор рк, eÄ,..., к фредставпкет собой последовательность на выходе 8 устройства для вычисления свертки.

Преобразование входной последо- вательности Р U,...ô 3Ь выходОр 1р ° ° ° нуа (М, у.1,...,М„ ), задаваемое при и 3 посредством соотношений (2)

Р (3) и (4), можно представить с помощью следующего матричного равен" à но Uî

"1 "1

Н2 02

Э 3 н о, H U

Н, 0

H1 V

М, 2

М . М

Но О 0 а

О H„O 0

О О Н 0

0 О О Н

О О О О, О О 0 О

0 0 0 0

О 0 0 0 о

О.

О о

Ь о

1014126 о - о о о о о

"О

Ц1

2.и2 о о о

tl0 н ®н н,®н, Мр + Й, () н Он н ОМ,О

Н O++l, Н О О ОН о

0 о о о о

Я2 н®н, н P. 9

И о и (+)й о н ®н, о н, H®H o

НрC H О+

H OH 9 Н ®н,9 ill@Í ß

Н,О+И, 20 Этого к символу U2 на. входе 7 прибавляется по модулю два элемент 0

О два такта хранившийся в двухразрядном регистре сдвига 102. На выходе имеем О ®О Яеличина 0 со входа

2 .

257 записывается в сд ви говый регистр

01 ° а величины 0 и 0 +) U с Выходов сумматоров по модулю дв 12 и

122, соответственно, поступают в сдвиговые Регистры 102 и 10З, З0 В течение четвертого такта на управляющих входах 13 и 13 присут1 2 ствуют логические единицы, обеспечивающие прибавление к элементу

О на входе 7 величин U2 и ООО+О

3S поступающих с выходов сдвиговых oiгистров 10„и 10, На выходе блока преобразования 1 имеем сумму0 (+)О Q+

:ОО ДО ; По окончании такта в сдвиговые регистры 10 -10> записываются 4

40 величины 0, U Я+О и О О+ . Q+ U Î+U в

Э - З а 1 2З соответственн

Пятый такт характеризуется появ" лением единицы только на входе 13

Поэтому, к символу 0, присутству3

45 ющему на входе 7, прибавляется по мо. дулю два величина U четыре такта хранившаяся в четырехразрядном регистре сдвига 10З. Следовательно, на выходе блока преобразования 1 имеем

0 QU,Величина U,1 засылается во все 0 регистры 10 -10 !

Таким образом, сверткой(ч

О ° 1 ° ° ° ...у „.Ú базисе Жегалкина является ре 2 -ч зультат умножения вектора (0,U (О 1

$n „) входной последовательности на нижетреугольную матрицу, элементы которой однозначно определяются компонентами вектора передаточной функции fH, Н1,...,Н2п» ), Рассмотрим функционирование преобразователя 1 для случая. @=3.

На вход 7 в течение восьми тактов поступает последовательность

00» U„° U2> Ug> 01 ° 0 > 1(В первом такте на управляющие входы 13„-13 бликса преобразования

1 подается комбинация 000 с разрядных выходов двоичного счетчика 6.

Поэтому сигналы с выходом сдвиговых регистров 10„-10> не проходят через логические элемейты И 11 -ll и на

1 выходе блока преобразования 1 имеем величину, тождественную элементу

U0 входной последовательности, В момент окончания первого такта U записывается в сдвиговые регистры I 01-10 .

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

В сдвиговые регистры 10 -10 засй1 лаются соответственно величины

В третьем .такте единичный потенциал поступает на управляющий вход l3 блока преобразования 1. Вследствие н ®н g н,®н, н,Ен, ъ, В шестом танте в формировании суммы участвуют величины О, иО (+)О с выходов регистров сдвига 101 и 10З, а также элемент U5 со входа 7, На выходе блока преобразования 1 полу(/оО+ 0.,0+ 20+ з " """ """ "" та в сдвйговые регистры 10„-10> запиИПИ Заказ 3037/66 аж 934 Подписное

9 10141 сываются величины U>, U+Q+ (35 0+0+0 соответственно, В течение седьмого такта на входах 13 -131; имеем комбинацию (110), и поэтому информация считывается с выходов регистров сдвига 10 и 10 на которых присутствуют велйчины 3+, 0 ® С умма на выходе ра в на О Q+ 0 Q+ о

+U Q+U,Âåëè÷èíû U U U ®ОЬзапи

4 6. сываются в сдвиговые регистры 10„-10 .

Восьмой такт отличается тем, что ,в формировании суммы по модулю два участвуют величины с выходов всех регистров сдвига 10 -10 . Таковыми м я вляют ая О, 0 0 5 ОО О+ 11® 2 80 . На,, выходе имеем;0 +О Я}02Q+U ЯО Я "

; О 1 2

S Q+>6®0; В сдвиговые регистры 20

10„-10З засылается величины,0,0 Q+0

К(+ 0 Q+U (+}О соответственно. ,+.. Ь Т, Следовательно, в восьми следующих друг за другом тактах на выходе блока преобразования 1 имеем последо,. вательность, вид которой для п=3 . задается вектором в правой части соотношения (2), Эта последовательность поступает на первый вход элемента И 4, входящего в состав фильтра 3, Некоторый элемент двоичной последовательности

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

Функционирование блока преобразования 2 аналогично работе блока преобразования 1.

Таким образом, на входе 8 устройства имеем последовательность, представляющую собой свертку в базисе

Жегалкина.

Заметим, что поскольку матрица в соотношении (5) является нижнетре-„ угольной, то элемент у . появляется на выходе 8 в том же такте, в котором на вход подается элемент 0 (J=0,1...,,2. -1). Другими словами, 3 свертка в данном устройстве вычисляется без задержки, что также является преимуществом предлагаемого устройства.

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