Устройство для вычисления сумм парных произведений
Владельцы патента RU 2711731:
Федеральное государственное автономное образовательное учреждение высшего образования "Северо-Кавказский федеральный университет" (RU)
Изобретение относится к вычислительной технике. Технический результат заключается в повышении корректирующих способностей устройства для вычисления сумм парных произведений. Устройство содержит преобразователь кода СОК в позиционный код, счетчик тактов, блок коррекции ошибки, модульный сумматор, два блока вычисления сумм парных произведений по произвольному модулю и один блок вычисления сумм парных произведений по контрольному модулю, каждый из которых содержит регистр, блок памяти, матричный умножитель, три группы буферных регистров и матричный сумматор, блок коррекции ошибки содержит четыре регистра, коммутатор, два блока памяти, матричный умножитель, модульный сумматор, счетчик количества переходов за рабочий диапазон, введен дополнительный блок вычисления сумм парных произведений по контрольному модулю, состоящий из регистра, блока памяти, матричного умножителя, матричного сумматора и трех групп буферных регистров, кроме того, в блок коррекции ошибки введены пятый информационный вход, пятый регистр. 2 ил., 1 табл.
Заявленное изобретение относится к вычислительной технике и может быть использовано в процессорах обработки сигналов и цифровых фильтрах.
Известно устройство для вычисления сумм парных произведений ([1] Калмыков И.А. Устройство вычисления сумм парных произведений//Патент РФ № 2012041, G06F 7/72), содержащее два блока вычисления парных произведений по произвольному модулю и один по контрольному модулю, каждый из которых содержит регистр, память, матричный сумматор, матричный умножитель и три группы буферных регистров, преобразователь кода СОК в позиционный код, блок коррекции ошибки, модулярный сумматор, счетчик тактов и выход результата устройства.
Недостатком устройства являются малые корректирующие способности кода, так как исправляются ошибки, возникающие только в рабочих основаниях.
Основной задачей является повышение корректирующих способностей устройства для вычисления сумм парных произведений, за счет исправления однократных ошибок, возникающих как в рабочих, так и в проверочных основаниях.
Техническим результатом, достигнутым при осуществлении заявленного изобретения, является повышение корректирующих способностей устройства для вычисления сумм парных произведений.
Цель изобретения – повышение корректирующей способности устройства, которая достигается введением дополнительного блока вычисления сумм парных произведений по контрольному модулю, содержащему регистр, блок памяти, матричный сумматор, матричный умножитель и три группы буферных регистров.
Указанный технический результат достигается тем, что в устройство для вычисления сумм парных произведений, содержащее преобразователь кода СОК в позиционный код; счетчик тактов; блок коррекции ошибки; модульный сумматор; два блока вычисления сумм парных произведений по произвольному модулю и один блок вычисления сумм парных произведений по контрольному модулю, каждый из которых содержит регистр, блок памяти, матричный умножитель, три группы буферных регистров и матричный сумматор, причем выход счетчика тактов соединён с адресными выходами блоков памяти первого, второго блоков вычисления сумм парных произведений по произвольному модулю и блока вычисления сумм парных произведений по контрольному модулю, входом разрешения работы преобразователя кода СОК в позиционный код, и входом разрешения работы блока коррекции ошибки, а в первом и втором блоках вычисления сумм парных произведений по произвольному модулю и в блоке вычисления сумм парных произведений по контрольному модулю выход регистра соединен с первым входом матричного умножителя, второй вход которого соединен с выходом блока памяти, а его выходы – с входами буферного регистра первой группы, выходы которого соединен с входами первого слагаемого матричного сумматора, выходы которого соединены с входами буферного регистра второй группы, выходы которого соединены с входом буферного регистра третьей группы, выходы которого соединены с входами второго слагаемого матричного сумматора, выходы буферных регистров третьей блоков вычисления сумм парных произведений по произвольному модулю соединены соответственно с первым и вторым информационными входами преобразователя кода СОК в позиционный код, первый выход которого соединен с входом второго слагаемого модульного сумматора, а второй выход с пятым информационным входом блока коррекции ошибки, выход которого подключен к входу первого слагаемого модульного сумматора, выход которого является выходом устройства, выходы буферных регистров третьей группы первого и второго блоков вычисления сумм парных произведений по произвольному модулю и блока вычисления сумм парных произведений по контрольному модулю подключены соответственно к первому, второму и третьему информационным входам блока коррекции ошибки, блок коррекции ошибки содержит четыре регистра, коммутатор, два блока памяти, матричный умножитель, модульный сумматор, счетчик количества переходов за рабочий диапазон причем, первые три информационных входа подключены к входам первых трех регистров, а четвертый информационный вход подключен ко входу счетчика количества переходов за рабочий диапазон, выходы первых двух регистров подключены к соответствующим входам коммутатора, выход которого подключен к первому входу матричного умножителя, второй вход которого подключен к выходу первого блока памяти, выход матричного умножителя подключен к первому входу модульного сумматора, а второй вход которого подключен к первому выходу четвертого регистра, выход модульного сумматора подключен к входу четвертого регистра, второй выход которого подключен к входу второго блока памяти, выход которого является выходом блока коррекции ошибки, вход разрешения работы блока коррекции ошибки подключен к управляющему входу коммутатора и входу первого блока памяти, введен дополнительный блок вычисления сумм парных произведений по контрольному модулю, состоящий из регистра, блока памяти, матричного умножителя, матричного сумматора и трех групп буферных регистров, причем выход счетчика тактов соединен с адресным входом блока памяти дополнительного блока вычисления сумм парных произведений по контрольному модулю, выход регистра дополнительного блока вычисления сумм парных произведений по контрольному модулю соединен с первым входом матричного умножителя, второй вход которого соединен с выходом блока памяти, а выход – с входом буферного регистра первой группы, выход которого соединены с входом первого слагаемого матричного сумматора, выход которого соединен с входом буферного регистра второй группы, выход которого соединен с входом буферного регистра третьей группы, выход которого соединен с входом второго слагаемого матричного сумматора, также выходы буферных регистров третьей группы блока вычисления сумм парных произведений по контрольному модулю и дополнительного блока вычисления сумм парных произведений по контрольному модулю соединены соответственно с третьим и четвертым информационными входами преобразователя кода СОК в позиционный код, выход буферного регистра третьей группы дополнительного блока вычисления сумм парных произведений по контрольному модулю также соединен с четвертым информационным входом блока коррекции ошибки, кроме того в блок коррекции ошибки введены пятый информационный вход, пятый регистр, вход которого подключен к пятому информационному входу, а выход к четвертому входу коммутатора, к третьему входу коммутатора подключен выход третьего регистра, к пятому входу коммутатора подключен выход счетчика количества переходов за рабочий диапазон.
Сущность изобретения заключается в следующем. Основным достоинством системы остаточных классов (СОК) является независимость образования разрядов числа, в силу чего каждый разряд несет информацию обо всем исходном числе. Отсюда вытекает возможность их параллельной обработки. Это позволяет привлечь новые методы арифметического контроля. При введении дополнительного контрольного основания остаток, взятый по этому основанию, несет избыточную информацию об исходном числе, что позволяет обнаружить и справить ошибки в цифрах как по рабочим, так и по контрольным основаниям.
Любое число N, представленное в СОК как, может быть выражено как:
, (1)
где – ортогональные базисы,
– ранг числа,
– полный диапазон,
, (2)
где – основания СОК,
,
– число рабочих оснований,
и
– контрольные основания.
В то же время:
, (3)
где – рабочий диапазон.
Число считается правильным, если
. Другими словами:
, (4)
где – номер интервала, в котором находится число
.
Подставим в равенство (4) равенство (1), тогда:
. (5)
Представим ортогональные базисы избыточного кода СОК через рабочий диапазон Р. Тогда получаем, что , где
,
– остаток от деления ортогонального базиса избыточного кода на рабочий диапазон.
Но данный остаток представляет собой ортогональный базис с основанием
. Так как значение номера интервала S изменяется от 0 до pn+1 pn+2 – 1, то можно выражение (5) можно представить
Полученные равенства подставляем в формулу (5), тогда:
, (6)
где – ранг числа в системе по рабочим основаниям
., который показывает количество переходов за рабочий диапазон.
Так как выбранная система является упорядоченной, и
, то по величине
можно однозначно определить величину
коррекции результата.
На фиг. 1 представлена функциональная схема устройства для вычисления сумм парных произведений; на фиг. 2 функциональная схема блока коррекции ошибки.
Устройство для вычисления сумм парных произведений (фиг.1) содержит блоки вычисления сумм парных произведений по произвольному модулю 1,2 и по контрольному модулю 3, 4, каждый из которых содержит регистр 5, блок памяти 6, матричный сумматор 7, матричный умножитель 8, три группы буферных регистров 9, 10, 11, преобразователь 12 кода СОК в позиционный код, блок 13 коррекции ошибки, модульный сумматор 14, счетчик 15 тактов и выход 16 устройства.
Структура блоков вычисления сумм парных произведений 1-4 идентичная. Выход регистра 5 подключен к первому входу матричного умножителя 8, ко второму входу которого подключен выход блок памяти 6. Выход матричного умножителя 8 соединен с буферным регистром первой группы 9, выход которого соединен с входом первого слагаемого матричного сумматора 7. Выход матричного сумматора 7 соединен с входом буферного регистра второй группы 10, выход которого подключен к входу буферного регистра третьей группы 11. Выход буферного регистра третьей группы 11 подсоединен к входу второго слагаемого матричного сумматора 7. Выходы буферных регистров третьей группы 11 всех блоков вычисления сумм парного произведений 1-4 подключены к соответствующим входам преобразователя 12 кода СОК в позиционный код, первый выход которого подключен к входу второго слагаемого модульного сумматора 14, а второй выход - к пятому информационному входу блока 13 коррекции ошибки. Выход блока 13 коррекции ошибки подсоединен ко входу первого слагаемого модульного сумматора 14, выход которого является выходом 16 устройства. Выход счетчика 15 тактов соединен с адресными входами блоков памяти 6 четырех блоков вычисления сумм парных произведений, входом разрешения работы преобразователя 12 кода СОК в позиционный код, а также входом разрешения работы блока 13 коррекции ошибки.
Блок 13 коррекции ошибки (фиг. 2) содержит 5 регистров 17-20, 24, коммутатор 21, матричный умножитель 22, модульный сумматор 23, счетчик 25 количества переходов за рабочий диапазон, первый и второй блоки памяти 26, 27, информационные входы 28, 29, 30, 31, 32, вход 33 разрешения работы блока, выход 34 блока коррекции ошибки 13. При этом первый, второй, третий и пятый информационные входы 28-31 подключены к входам первого, второго, третьего и пятого регистров 17, 18, 19, 20 соответственно, выходы которые подключены к соответствующим входам коммутатора 21.Четвертый информационный вход 32 подключен к входу счетчика 25 количества переходов за рабочий диапазон, выход которого подключен к пятому входу коммутатора 21. Выход коммутатора 21 подключен к первому входу матричного умножителя 22, второй вход которого подключен к выходу первого блока памяти 26. Вход 33 разрешения работы блока подключен к управляющему входу коммутатора 21 и входу первого блока памяти 26. Выход матричного умножителя 22 подключен к первому входу модульного сумматора 23, второй вход которого соединен с первым выходом четвертого регистра 24. Выход модульного сумматора 23 подсоединен к входу четвертого регистра 24, второй выход которого подключен к входу второго блока памяти 27, выход которого подсоединен к выходу 34 блока коррекции ошибки 13.
Блоки памяти, матричный умножитель, матричные сумматор в устройстве выполнены в виде постоянных запоминающих устройств (ПЗУ).
Устройство работает следующим образом.
В регистры 5 блоков вычисления сумм парных произведений по произвольному модулю 1, 2 и контрольному модулю 3, 4 до начала работы записаны целые числа в коде СОК. Так как система работает по четырем основаниям, то число в коде СОК представляется в виде четырех остатков соответственно α1, α2, α3, α4. Счетчик тактов 15 формирует адреса для считывания коэффициентов, которые хранятся в блоках вычисления сумм парных произведений 1, 2, 3, 4 в блоках памяти 6 в коде СОК. Содержимое регистров 5 в каждом из блоков 1, 2, 3, 4 перемножается с коэффициентами с помощью матричных умножителей 8. Результаты умножений записываются в буферные регистры первой группы 9, содержимое которых складывается с содержимым буферных регистров 11 третьей группы (в первом цикле происходит сложение с нулем). Сложение осуществляют матричные сумматоры 7 в каждом из блоков 1, 2, 3, 4. Суммы сначала записываются в буферные регистры 10 второй группы, а затем в буферные регистры 11 третьей группы. С выходов буферных регистров третьей группы 11 блоков вычисления сумм парных произведений по произвольному модулю 1 и 2 результат подается на первый и второй информационные входы преобразователя 12 кода СОК в позиционный код и на первый и второй информационные входы блока 13 коррекции ошибки, на третий и четвертый информационные входы которого подается также информация с выходов буферных регистров третьей группы 11 блоков вычисления сумм парных произведений по контрольному модулю 3 и 4. Счетчик тактов 15 по окончании суммирования парных произведений выдает разрешающий сигнал на вход разрешения работы преобразователя кода СОК в позиционный код 12 и на вход разрешения работы блока 13 коррекции ошибки. На пятый вход блока 13 коррекции ошибки поступает сигнал о переходе через Р, который подается со второго выхода преобразователя кода СОК в позиционный код 12. Структура преобразователя кода СОК в позиционный код 12 аналогична прототипу. Результаты с первого выхода преобразователя 12 кода СОК в позиционный код и выхода блока 13 коррекции ошибки подаются на входы модульного сумматора 14, где и происходит сложение. Выход модульного сумматора 14 является выходом 16 устройства. Слагаемые кода СОК в регистры 5 блоков вычисления сумм парных произведений 1, 2, 3, 4 могут быть записаны из аналогово-цифрового преобразователя.
Блок 13 коррекции ошибки работает следующим образом.
Значения ,
,
и
записываются в соответствующие первый, второй, третий, пятый регистры 17,18,19 и 20. Значения
,
,
и
последовательно через коммутатор 21 подаются на матричный умножитель 22, на второй вход которого поступают величины
,
,
и
с выхода первого блока памяти 26, где производится умножение
,
,
и
. Данные значения подаются на первый вход модульного сумматора 23, где складываются. Полученный результат заносится в четвертый регистр 24, а затем снова подается на второй вход модульного сумматора 23 для сложения со значением
, которое подается с выхода счетчика 25 количества переходов за рабочий диапазон. Конечный результат поступает на вход второго блока памяти 27, на выходе которой появляется значение коррекции, которое подается на выход 34 блока коррекции ошибки 13.
Например, пусть имеем систему оснований ,
,
,
(контрольные основания
и
).
Тогда ;
Рабочий диапазон для данного набора оснований равен
.
Вычислим ортогональные базисы:
,
,
,
.
Вычислим коэффициенты:
;
;
;
.
Получаем:
,
,
,
,
,
.
Возьмем число . В СОК оно имеет вид
.
Вычислим значение:
.
Ошибки нет.
Допустим, что произошла ошибка и получено число .
Тогда
.
Произошла ошибка.
Рассмотрим работу блока 13 коррекции ошибки. Значения ,
,
и
записываются в соответствующие регистры 17,18,19 и 20. Сначала значение
из первого регистра 17 через коммутатор 21 подается на матричный умножитель 22, на второй вход которого поступает величина
с выхода первого блока памяти 26. С выхода матричного умножителя 22 результат умножения
подается на вход модульного сумматора 23, где складывается с нулем, который перед работой блока 13 коррекции ошибки был записан в четвертом регистре 24. Полученный результат заносится в четвертый регистр 24. Затем значение
из второго регистра 18 через коммутатор 21 подается на матричный умножитель 22, на второй вход которого поступает величина
с выхода первого блока памяти 26. С выхода матричного умножителя 22 результат умножения
подается на вход модульного сумматора 23, где складывается с первым промежуточным результатом 50, который был записан в четвертом регистре 24. Полученный результат 65 заносится в четвертый регистр 24.
Затем значение из третьего регистра 19 через коммутатор 21 подается на матричный умножитель 22, на второй вход которого поступает величина
с выхода первого блока памяти 26. С выхода матричного умножителя 22 результат умножения
подается на вход модульного сумматора 23, где складывается с промежуточным результатом, который был в четвертом регистре 24. Полученный результат (110+65) mod 77 = 21 заносится в четвертый регистр 24.
Затем значение из пятого регистра 20 через коммутатор 21 подается на матричный умножитель 22, на второй вход которого поступает величина
с выхода первого блока памяти 26. С выхода матричного умножителя 22 результат умножения
подается на вход модульного сумматора 23, где складывается с промежуточным результатом 28, который был в четвертом регистре 24. Полученный результат (70+21) mod 77 = 14 заносится в четвертый регистр 24.
Одновременно с этими вычислениями со второго выхода преобразователя 12 кода СОК в позиционный код подается сигнал равный на четвертый информационный вход 32, в результате на выходе счетчика 25 количества переходов за рабочий диапазон появляется единичный сигнал, который через коммутатор 21 подается на вход матричного умножителя 22, где умножается на единицу. Полученный результат подается на модульный сумматор 23, где складывается с промежуточным результатом 14, который подается из четвертого регистра 24. Полученный результат S = 15 поступает на вход четвертого регистра 24, а затем с его второго выхода на вход второго блока памяти 27. С выхода второго блока памяти 27 снимается значение
, которое поступает на вход первого слагаемого модульного сумматора 14, а на вход второго слагаемого с первого выхода преобразователя 12 кода СОК в позиционный код подается ошибочное число, представленное в позиционном коде
.
С выхода модульного сумматора 14 будет снято исправленное число
.
Исправленное число подается на выход 16 устройства.
Корректирующие значения определяются из таблицы 1.
Устройство для вычисления сумм парных произведений, содержащее преобразователь кода СОК в позиционный код; счетчик тактов; блок коррекции ошибки; модульный сумматор; два блока вычисления сумм парных произведений по произвольному модулю и один блок вычисления сумм парных произведений по контрольному модулю, каждый из которых содержит регистр, блок памяти, матричный умножитель, три группы буферных регистров и матричный сумматор, причем выход счетчика тактов соединён с адресными выходами блоков памяти первого, второго блоков вычисления сумм парных произведений по произвольному модулю и блока вычисления сумм парных произведений по контрольному модулю, входом разрешения работы преобразователя кода СОК в позиционный код и входом разрешения работы блока коррекции ошибки, а в первом и втором блоках вычисления сумм парных произведений по произвольному модулю и в блоке вычисления сумм парных произведений по контрольному модулю выход регистра соединен с первым входом матричного умножителя, второй вход которого соединен с выходом блока памяти, а его выходы – с входами буферного регистра первой группы, выходы которого соединены с входами первого слагаемого матричного сумматора, выходы которого соединены с входами буферного регистра второй группы, выходы которого соединены с входом буферного регистра третьей группы, выходы которого соединены с входами второго слагаемого матричного сумматора, выходы буферных регистров третьей группы блоков вычисления сумм парных произведений по произвольному модулю соединены соответственно с первым и вторым информационными входами преобразователя кода СОК в позиционный код, первый выход которого соединен с входом второго слагаемого модульного сумматора, а второй выход с пятым информационным входом блока коррекции ошибки, выход которого подключен к входу первого слагаемого модульного сумматора, выход которого является выходом устройства, выходы буферных регистров третьей группы первого и второго блоков вычисления сумм парных произведений по произвольному модулю и блока вычисления сумм парных произведений по контрольному модулю подключены соответственно к первому, второму и третьему информационным входам блока коррекции ошибки, блок коррекции ошибки содержит четыре регистра, коммутатор, два блока памяти, матричный умножитель, модульный сумматор, счетчик количества переходов за рабочий диапазон, причем первые три информационных входа подключены к входам первых трех регистров, а четвертый информационный вход подключен к входу счетчика количества переходов за рабочий диапазон, выходы первых двух регистров подключены к соответствующим входам коммутатора, выход которого подключен к первому входу матричного умножителя, второй вход которого подключен к выходу первого блока памяти, выход матричного умножителя подключен к первому входу модульного сумматора, а второй вход которого подключен к первому выходу четвертого регистра, выход модульного сумматора подключен к входу четвертого регистра, второй выход которого подключен к входу второго блока памяти, выход которого является выходом блока коррекции ошибки, вход разрешения работы блока коррекции ошибки подключен к управляющему входу коммутатора и входу первого блока памяти, отличающееся тем, что в него введен дополнительный блок вычисления сумм парных произведений по контрольному модулю, состоящий из регистра, блока памяти, матричного умножителя, матричного сумматора и трех групп буферных регистров, причем выход счетчика тактов соединен с адресным входом блока памяти дополнительного блока вычисления сумм парных произведений по контрольному модулю, выход регистра дополнительного блока вычисления сумм парных произведений по контрольному модулю соединен с первым входом матричного умножителя, второй вход которого соединен с выходом блока памяти, а выход – с входом буферного регистра первой группы, выход которого соединен с входом первого слагаемого матричного сумматора, выход которого соединен с входом буферного регистра второй группы, выход которого соединен с входом буферного регистра третьей группы, выход которого соединен с входом второго слагаемого матричного сумматора, также выходы буферных регистров третьей группы блока вычисления сумм парных произведений по контрольному модулю и дополнительного блока вычисления сумм парных произведений по контрольному модулю соединены соответственно с третьим и четвертым информационными входами преобразователя кода СОК в позиционный код, выход буферного регистра третьей группы дополнительного блока вычисления сумм парных произведений по контрольному модулю также соединен с четвертым информационным входом блока коррекции ошибки, кроме того, в блок коррекции ошибки введены пятый информационный вход, пятый регистр, вход которого подключен к пятому информационному входу, а выход к четвертому входу коммутатора, к третьему входу коммутатора подключен выход третьего регистра, к пятому входу коммутатора подключен выход счетчика количества переходов за рабочий диапазон.