нейронная сеть для деления чисел, представленных в системе остаточных классов
Классы МПК: | G06F7/52 для умножения; для деления G06N3/02 использующие модели нейронных сетей |
Автор(ы): | Червяков Николай Иванович (RU), Лавриненко Ирина Николаевна (RU), Кондрашов Александр Владимирович (RU), Гуйда Михаил Владимирович (RU), Щегольков Алексей Викторович (RU) |
Патентообладатель(и): | Червяков Николай Иванович (RU), Лавриненко Ирина Николаевна (RU), Кондрашов Александр Владимирович (RU), Гуйда Михаил Владимирович (RU), Щегольков Алексей Викторович (RU) |
Приоритеты: |
подача заявки:
2005-05-11 публикация патента:
27.08.2007 |
Изобретение относится к вычислительной технике и может быть использовано в модулярных нейрокомпьютерах для быстрого деления чисел, представленных в системе остаточных классов. Техническим результатом является повышение скорости выполнения операции деления, а также сокращение оборудования. Указанный результат достигается за счет того, что нейронная сеть содержит входной слой, нейронные сети конечного кольца для определения остатка делителя и нейронные сети конечного кольца для вычисления частного от деления двух чисел. 1 табл., 1 ил.
Формула изобретения
Нейронная сеть для деления чисел, представленных в системе остаточных классов, содержащая входной слой нейронов, выходы которых разветвлены на входы нейронных сетей конечного кольца, входящих в состав выходной нейронной сети частного и на входы нейронных сетей конечного кольца по модулям р 1,р2,...рn,р n+1, входящих в состав нейронной сети для вычисления остатка делителя, которая реализует вычислительную модель n+1=|A|D, где А - исходное число, представленное в системе остаточных классов, D - делитель, D=рn+1, отличающаяся тем, что в нейронную сеть для вычисления остатка делителя введены нейронная сеть конечного кольца для вычисления суммы произведений , где i - остатки исходного числа А по модулю рi, - ортогональные базисы, представленные в обобщенной позиционной системе счисления, i,j=1,2,...n, и нейронная сеть конечного кольца с весовым коэффициентом, равным обратной мультипликативной величине для выполнения финального шага при вычислении остатка от делителя, вход которой соединен с инверсным выходом нейронной сети конечного кольца для вычисления суммы произведений по модулю делителя D, на вход которой подаются значения с выходов нейронных сетей конечного кольца по модулям р1,р2,...р n,рn+1, выход нейронной сети конечного кольца для выполнения финального шага при вычислении остатка от делителя соединен с первыми входами нейронных сетей конечного кольца, входящих в состав выходной нейронной сети частного, на вторые входы которых поступают остатки исходного числа по модулям р1,р2,...р n, которая реализует вычислительную модель , где , причем di являются константами операции, вычисляемыми заранее по заданному делителю D и не зависящими от исходного числа А, на выходной нейронной сети частного получают результат от деления исходного числа на заданный делитель.
Описание изобретения к патенту
Изобретение относится к вычислительным модулярным нейрокомпьютерным системам и предназначено для выполнения операции деления над числами, представленными в системе остаточных классов (СОК).
Известно устройство для деления чисел в системе остаточных классов (Овчаренко Л.А., Лопатин Д.С. Деление числа в модулярном коде на основание системы счисления // Телекоммуникации. - 2002. - №6. - С.7-10), содержащее табличные вычислители, когерентный преобразователь модулярного кода, устройство отображения и сумматор по модулю.
Недостатком данного устройства является большой объем оборудования и низкая скорость деления чисел.
Наиболее близким к данному изобретению техническим решением является устройство, представленное в виде "Нейронной сети для округления и масштабирования чисел, представленных в системе остаточных классов" (Решение о выдаче патента по заявке №2003115586/09(016529) от 26.05.2003), содержащее входной слой нейронов, нейронную сеть конечного кольца (НСКК) определения ранга числа, нейронную сеть конечного кольца вычисления остатка по основанию n+1, n - нейронных сетей конечного кольца вычисления масштабированного числа.
Недостатком устройства является большой объем оборудования и низкая скорость округления.
Однако такие нейронные сети предназначены для округления и масштабирования чисел, представленных в системе остаточных классов.
Целью данного изобретения является расширение возможностей известной нейронной сети для выполнения операции деления чисел, повышения скорости деления и уменьшения объема оборудования.
Поставленная цель достигается тем, что в нейронную сеть введена нейронная сеть конечного кольца для определения остатка делителя. Таким образом, нейронная сеть для деления чисел, представленных в системе остаточных классов, будет состоять из входного слоя 2 с нейронами 3, нейронной сети для вычисления остатка делителя 4, состоящей из нейронных сетей конечного кольца 5 по модулям СОК р1, р 2,...,pn делимого и нейронных сетей конечного кольца 6 по модулю делителя, нейронных сетей конечного кольца 14 для вычисления произведений , нейронной сети конечного кольца 11 для выполнения финального шага при выполнении делителя остатка и выходной нейронной сети частного 7, состоящей из НСКК 8.
Структура нейронной сети зависит от внешних параметров, которые определяются модулями делимого, делителя и частного. Функционирование нейронной сети определяется весовыми коэффициентами, которые являются константами СОК и определяются заранее. Обучение сети не требуется.
Число А представляется в СОК набором наименьших неотрицательных остатков 1, 2,..., n от деления А на попарно простые числа р1,p2,...,р n, называемые модулями (основаниями). При этом число А записывается в СОК в следующей форме
где .
Число А лежит в пределах - Р А<Р, где Р=р1·р 2·...·рn.
При выполнении этого условия представление (1) взаимно однозначно с обычным представлением А в позиционной системе счисления, т.е. по ( 1, 2,..., n) можно определить А.
Деление числа в СОК сводится к отбрасыванию от делимого соответствующим образом подобранного остатка, определяющегося делителем. Ниже выводится алгоритм деления числа А на число D с отбрасыванием остатка в предположении, что D либо целое положительное число, попарно простое с p1,р2 ,...,рn, либо целое положительное число, представляющее собой произведение чисел, попарно простых с p 1,р2,...,рn . Алгоритм деления получается, исходя из следующих рассуждений.
Если А делится на D без остатка, то операция деления является модульной операцией и сравнительно просто реализуется на НСКК. Поэтому алгоритм деления в качестве вспомогательной операции включает операцию нахождения числа , которое делится на D без остатка. Операция нахождения заменяет операцию отбрасывания остатка от деления. При нахождении используется алгоритм определения остатка делителя путем расширения системы оснований, где в качестве расширяемого основания используется делитель. Пусть
Тогда
где .
Из выражения (3) видно, что делится без остатка на D.
Рассмотрим алгоритм определения остатка делителя.
Пусть СОК состоит из оснований р 1, р2, ..., рn . Диапазон чисел этой системы будет . Добавим к числу оснований СОК делитель D=р n+1. Диапазон этой системы равен . Тогда любое число А из диапазона [0, P n+1) в обобщенной позиционной системе счисления (ОПСС) представим как , где аi - коэффициенты обобщенной позиционной системы счисления.
Если число А будет лежать в первоначальном диапазоне [0, Рn), то в обобщенной позиционной системе цифра an+1 =0. Этот факт и используется для получения остатка делителя от деления числа А на новое основание СОК рn+1 , которое отождествляется с делителем.
Пусть число А имеет представление ( 1, 2,..., n) по основаниям p 1,p2,...,рn . Добавим новое основание pn+1=D, тогда число в системе оснований р1,р 2,...,рn, D=pn+1 , где - остаток от деления числа А на рn+1 , т.е. искомая цифра по новому основанию, равному делителю D.
Для определения этой цифры используется метод перевода числа из СОК в ОПСС, включая неизвестную цифру в проводимые операции. При этом мы параллельно получаем цифры в ОПСС a1,a2 ,...,аn и выражение для цифры a n+1=0. Из полученных соотношений и определяем остаток числа по модулю делителя .
Расширим число А в системе оснований р 1,р2,...,рn , рn+1, тогда
где - диапазон расширенной системы оснований,
- ортогональные базисы расширенной системы оснований.
Представим ортогональные базисы в обобщенной позиционной системе счисления, тогда
где - коэффициенты ОПСС; i,j=1,2,...,n.
На основании (5) запишем выражение (4) в виде
Из выражения (6) можно определить коэффициенты обобщенной позиционной системы счисления аi числа А, тогда
где i - вычеты числа А по р i;
- ортогональные базисы, представленные в ОПСС.
Цифра аi в представлении ОПСС получается суммированием по модулю pi всех произведений и переносом, генерируемым при формировании a i-1. Перенос генерируется как число раз, когда сумма цифр в ОПСС переполняется по модулю pi. Этот перенос используется для формирования цифр ai+1 . Последний перенос, генерируемый при получении последней цифры числа в ОПСС, отбрасывается. Рассмотренный метод выполняется в параллельном режиме. Цифры i, принимают от 0 до pi-1, причем являются константами, поэтому произведение можно поместить в ПЗУ или в весовые коэффициенты связей между нейронами. Адресами произведений являются вычеты i числа А по модулю p i.
Для иллюстрации определения констант приведем пример 1.
Пример 1. Пусть p1=2, p 2=3, p3=5, D=7, Р n+1=2·3·5·7=210, B1 =105, B2=70, В3=126, B4=120.
Далее на основании (5) определим :
Пример 2. Пусть задана система модулей р 1=2, р2=3, р3 =5, тогда Рn=2·3·5=30. И пусть задано число X=23=(1, 2, 3). Расширим систему оснований, где в качестве рn+1 возьмем делитель D=7. Необходимо определить остаток по основанию, равному делителю.
Пусть X=23=(1, 2, 3, |A|7) в системе оснований р1=2, р2=3, р 3=5, р4=D=7.
Воспользуемся константами , приведенными в (8), которые заданы матрицей
Процесс решения задачи приведем в таблице 1.
Таблица 1 | ||||
Вычеты числа Х по модулю pi | Модули | |||
p1 =2 | p2=3 | p3=5 | p 4=7 | |
1 | 1 | 1 | 2 | 3 |
2 | 0 | 4 | 2 | 4 |
3 | 0 | 0 | 3 | 12 |
|A|7 | 0 | 0 | 0 | 4|A|7 |
Коэффициенты ОПСС числа A | 1 | 2 | 3 | 6+4|A|7 |
Так как , но по условию a4=0, т.е. 4|A| 7=-6 или . Мультипликативная обратная величина , и так как число 6 отрицательное, возьмем его дополнение по модулю 7.
Итак, вычет числа А по модулю p 4=D=7 определяется выражением |A|7 =2·(7-6)=2.
Так как результат образования цифры в СОК по новому основанию pn+1=D зависит только от первых цифр, то операцию определения вычетов можно проводить сразу по нескольким делителям, попарно простым с основаниями СОК.
Преимущество предложенного метода определения вычетов исходного числа по нескольким делителям состоит в том, что:
- все вычисления выполняются в параллельных каналах по отдельным модулям;
- не требуется вычисления большого количества дополнительных величин, необходимо только наличие констант и мультипликативных величин по расширенным основаниям;
- возможно получение расширенного представления вычетов числа сразу по нескольким дополнительным основаниям, что не влияет на быстродействие всей операции расширения.
На основании проведенных расширений алгоритм деления числа А на число D с отбрасыванием остатка можно представить как последовательность следующих операций:
определение n+1 на основе вычислительной модели (7);
вычисление на основе вычислительной модели (3);
нахождение частного от деления на D
Эта операция представляет собой совокупность модульных операций, реализующих выражение
В случае, если pi - простые числа
Величины d1,d 2,...,dn не зависят от А и они вычисляются заранее по заданному D, т.е. числа d1,d 2,...,dn являются константами операции. Алгоритм деления числа А на число D, являющееся произведением чисел, попарно простых с р1,р 2,...,рn, может быть представлен как последовательность алгоритмов деления числа на числа, попарно простые с p1,p2,...,p n.
Пример 3. Пусть задана система оснований, как в примере 1. Требуется число А=(1, 2, 3) разделить на D=7.
В примере 2 вычислен остаток по модулю D и он равен 4=2.
После этого вычисляются по формуле (3)
Далее вычисляем по формуле (11) d 1=|70|2=1, d2=|71| 3=1 и d3=|73 |5=3.
Наконец, по формуле (10) вычисляем частное F=(|1·1|2, |1·0| 3, |1·3|5)=(1, 0, 3).
Нетрудно проверить, что F=23:7 3 (1, 0, 3).
Предложенный алгоритм деления отличается от известного тем, что его реализация полностью состоит из модульных операций по модулю pi и его можно легко реализовать нейронными сетями конечного кольца.
На чертеже представлена схема нейронной сети для деления чисел, представленных в СОК.
Принцип работы данного изобретения излагается ниже.
Нейронная сеть, приведенная на чертеже, позволяет выполнять операции деления исходного числа ( 1, 2,..., n) 1 на число D, соответствующее расширяемому модулю pn+1.
Остатки делимого ( 1, 2,..., n) 1 по системе оснований р 1,р2,...,рn поступают на вход нейронов 3 входного слоя 2, остаток делителя с учетом переносов 10 формируется нейронной сетью 4, состоящей из НСКК 5, 6, 14, финальный шаг которого вычисляется НСКК 11, а результат (частное) в остатках появляется на выходе нейронной сети частного 7, выходы 9.
С выходов нейронов 3 входного слоя 2 остатки делимого ( 1, 2,..., n) по модулям р1 ,р2,...,рn поступают на вход нейронной сети 4, состоящей из НСКК 5, 6, по соответствующим модулям. Весовые коэффициенты 12 нейронов НСКК 5, 6, выполняющие роль распределенной памяти, определяются значениями . НСКК 5, 6 вычисляют значение с учетом переносов 10. Выходные значения НСКК 5, 6 с весовыми коэффициентами 13, равными 1, подаются на вход НСКК 14 для выполнения суммирования значений .
Результаты суммирования с выхода НСКК 14 по модулю D (делителя), соответствующему остатку делителя, в дополнительном коде подаются на вход нейронной сети НСКК 11 для выполнения финального шага, весовой коэффициент которого 15 определяется мультипликативной величиной . На выходе НСКК 11 формируется остаток делителя, равный , который поступает на первые входы нейронной сети 7 НСКК 8. На вторые входы НСКК 8 с входного слоя поступают остатки делимого 1, 2,..., n. Весовые коэффициенты 16 НСКК 8 определяются выражением , где i=1,2,...,n. Используя распределительный закон алгебры, выходные НСКК 8 реализуют вычислительную модель , на выходах которой формируется частное 9.
Время деления числа определяется двумя циклами синхронизации: один цикл для формирования остатка делителя и один цикл для формирования частного.
Работа выполнена по гранту А 04-2.8-755.
Класс G06F7/52 для умножения; для деления
Класс G06N3/02 использующие модели нейронных сетей