Устройство для вычисления свертки в базисе Жегалкина Советский патент 1983 года по МПК H03H17/06 G06F17/17 

2. Устройство по п. 1, отличающееся тем, что блок ореГобразования базиса содержит п сдвиговых регистров, причем разрядность t-rp сдвигового регистра равна О, п), п элементов И и п сумматоров по модулю два, выход 1-го сдвигового регистра подключен к первому входу 1-го элемента И, выход которого соединен с первым входом t-ro сумматора по модулю два, выход Irro (, n-t) сумматора по модулю два

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

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

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

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

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

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

сложно.

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

Поставленная цель достигается тем что в устройство для вычисления сверки , содержащее первый и второй блоки 10 преобразования базиса, причем информационный вход первого блока преобразования базиса является информационным вхЬдом устройства, а выход второго блОка преобразования базиса является информационным выходом устройства, содержит сдвиговый регистр, элемент И и счетчик, 1-й (1«1, п) выход которого соединен с }-м ул; равляющим входом первого и второго 20; блоков преобразования базиса, выход первого блока преобразования базиса подключен к первому входу элемента .И, выход которого соединен с информа.ционным входом второго блока преоб25 : разования базиса, выход сдвигового регистра подключен к его входу и. второму входу элемента И, а тактовый i вход счетчика является синхронизиру,ющим входом устройства. 30 При этом блок преобразования базиса содержит п сдвиговых регистров,

причем разрядность t-ro сдвигового регистра равна (,n), п элементов И и п сумматоров по. модулю два,

35 выход «1-го сдвигового регистра подключен к первому входу {-го элемента И, выход которого соединен с первым входом i-ro сумматора по модулю два, выход 1-го 0«1, п-1) сумма3; 10Ut26 , . 4

iTopa no модулю два соединен с вхо- Рассмотрим алгоритм фильтрации дом 1+1-го сдвигового регистра и втр- двоичных последовательностей длины рым входом i+1-го сумматора по модулю два, выход п-го сумматора по моду лю два является выходом блока преобразования базиса, второй вход первого сумматора по модулю два и вход первого сдвигового регистра объединены и являются информационным входом блока преобразования, второй вход 1-го , п) элемента И является 1-м управляющим входом блока преобразования базиса. На фиг. 1 приведена функциональная схема устройства для вычисления свертки; на фиг. 2 - структура блока преобразования. Устройство для вымислениясвертки содержит блоки преобразования базиса 1 и 2, фильтр 3« состоящий из элемента И 4 и 2 -разрядного сдви гового регистра 5 используемого хранения коэффициентов передаточной функции, выход которого соединен с его входом а также п-разрядный счет чик 6. Информационном входом устройства служит вход 7 блока преобрааювания 1, а выходом является выхОдг 8 блока преобразования 2. Вход 9 счет чика 6 представляет собой вход синхронизации устройства. Блок преобразования 1 (или 2) содержит п сдвиговых регистров 10 --10, п логических элементоб И 1Ц-П|, и п сумма оров по модулю два 12 121, Вторые входы хюгических элементов Я 111,-11 служат управляющими входзми , блока преобразования. Раз рядность регистра 10 равна единице, а количество разрядов ка)«(дого последующего регистра увеличивается вдвое обозначена сумма по могде через i дулю два., . 5 Вектор UP, и,,..,и J, состоящий из нулей и единиц (сложение выпол няется по модулю два), называется

,, 2 , реализуемый данным устройством, (добавлением соответствующего чис ла нулей длину последовательности всегда можно сделать равной степени двойки).. Преобразователь 1 умножает 2 компонентный вектор входной последовательности, состоящей иэ нулей и еди ниц, на п-ю кронекерову степень матб Г1 1 41 iJ являющейся 1-й кронекеровой степенью. При этом сложение выполняется по но- дулю два. Вторая кронекерова стецень мат- - имеет вид рицы G размера rs, K«J; где О,, - матрица (2X2) из одних иул кренекерова степень G у. размера 2x2 определяется через (n-l)-) кронекерову степень G ) слеауюшим образом П-1 п-1 где 0 - матрица размера одних нулей, . При входная последовательность ; определяемая З-компонентшм вектором Uo, и, U2, и,, и Uy, и. u-,1 где и ,1}, умножается посредством преобразователя 1 на матрицу спектром последовательности ,.. базисе Жегалкина, а выражение (1) представляет собой матриду. hepfeхода в область и1эображения - матрицу прямого преобразования. фильтр 3 непосредственно осуществляет фильтрацию - покомпонентное умножение спектра fU, U,..., двримной последовательности Ги«, вектор передаточной s функции Но,К,... хранимый Отличны от нуля и равны единице только те компоненты вектора И LUjjV -i-J Л оторых как Tait и . Блок преобразования 2, осуществляет обратный переход от базиса Жегалкина к базису, состоящему из 2 единичных векторов, только одна компоне та которых отлична от нуля и равна единице. Этот переход из области изобоэаженмя в область оригинала реализуВектор Зд, X,,..., :у редставляет собой последовательность на выходе § устройства для вычисления свертки. Преобразование входной последовательности UQ, U,,,. выходв сдвиговом регистре 5 и состоящий только из нулей и единиц. Для функционирование фильтра 3 описывается следующим матричным соотношением етсч посредством умножения вектора HpUo, .,,... H2nL.i.U2.n..,3,a натри-. ЦУ (1)V которая являе -ся матрицей обратного преобразования. Базис Кегалкина образует векторы, являющиеся столбцами матрицы обратно го преобразования - матрицы (1). При переход из области изображения а область оригинала можно записать в следующей матричной форме ную t, З ,... j.iu. задаваемой при посредством соотношений (2), (З) и С), можно представить с помощью следующего матричного равен laaТаким образом, сверткой(v , у ,. ...у п . базисе Жегалкина является ре зультат умножения вектора fU,U ,., Ц)1-}3 входной последовательности на нижетреугольную матрицу, элементы которой однозначно определяются ком понентами вектора передаточной фуннк ции HO, Рассмотрим функционирование преобразователя 1 для случая. . На вход 7 в течение восьмк тактов поступает последовательность о 2, и. и , и, и, и. В первом такте на управляющие входы , блска. преобразования 1 подается комбинация 000 с разрядных выходов двоичного счетчика 6i Поэтому сигналы с выходом сдвиговых регистров , не проходят через логические элементы И Ц и на выходе блока преобразования 1 имеем величину, тождественную элементу и входной последовательности, В мо мёнт окончания первого такта UQ за писывается в сдвиговые регистры ,о в течение второго такта на управ ляющем входе 13 присутствует логическая единица, вследствие чего величина на выходе блока преобразования 1 является суммой по модулю два элемента U последовательности на входе 7 и элемента Up, хранимого в одноразрядном регистре сдвига 10. В сдвиговые регистры 10.-10, засылаются соответственно величины -U.. третьем такте единичный потенциал поступает на управляющий вход 13 блока преобразования 1. Вследств этого к символу и на. входе 7 прибавляется по модулю два элемент: U два такта хранившийся в двухразрядном регистре сдвига lOj. На выходе имеем и(+)и.Величина U со входа 7 записывается в сдвиговый регистр j , а величины U- и U-0U, с выхо-дов сумматоров по модулю два 12 и IZ, соответственно, поступают в сдвиговые регистры 10„ и 10,. В течение четвертого такта на управляющих входах 13 и 132 Рисутствуют логические единицы, обеспечивающие прибавление к элементу U-. на входе 7 величин 2 и (l , поступающих с выходов сдвиговых регистров 10 и Ю. На выходе бтюка преобразования 1 имеем суммуОд 5)и(5| , По окончании такта в сдбиговые регистры IO.j10-j записываются . вели чины Uj, и„®и и , соответственно. Пятый такт характеризуется появлением единицы только на входе 13. Поэтому, к символу и, присутствующему на входе 7, прибавляется по модулю два величина UQ, четыре такта . хранившаяся в четырехразрядном регистре сдвига 10. Следовательно, на выходе блока преобразования 1 имеем ,.Величина U засылается во все регистры . В шестом такте в формировании суммы участвуют величины 1) иОрфи с выходов регистров сдвига 10 и Ш, а также элемент U5 со входа 7. На блока преобразования 1 получаем UQ® tL® я@ По окончании такта в сдвиговые регистры запи