НЕЙРОННАЯ СЕТЬ УСКОРЕННОГО МАСШТАБИРОВАНИЯ МОДУЛЯРНЫХ ЧИСЕЛ
NEURON NETWORK OF ACCELERATED RANGING OF MODULAR NUMBERS

Изобретение относится к вычислительной технике, и в частности к модулярным нейрокомпьютерным средствам, и предназначено для выполнения операции масштабирования модулярных чисел, т.е. чисел, представленных в системе остаточных классов (СОК).
Известно устройство для округления чисел в системе остаточных классов (АС СССР №398949, кл. G06F 7/52, 1973 г.), содержащее входной регистр, блоки хранения констант, сумматоры констант по основаниям рабочего и дополнительного диапазонов, блоки вычисления неточных рангов и блок коррекции округления.
Недостатком данного устройства является большой объем оборудования, низкая скорость округления и ограниченная функциональная возможность.
Наиболее близким к данному изобретению техническим решением является нейронная сеть для округления и масштабирования чисел, представленных в системе остаточных классов, содержащая входной слой нейронов, нейронную сеть конечного кольца определения ранга числа, нейронную сеть конечного кольца вычисления остатка по основанию n-l, нейронную сеть конечного кольца вычисления разности чисел между входными остатками и остатками по основанию n+1, n-нейронных сетей конечного кольца вычисления масштабированного числа.
Недостатком устройства является большой объем оборудования, ограниченная функциональная возможность, которая заключается в том, что масштабирование модулярных чисел реализуется только для случая, если коэффициент масштабирования модулярных чисел равен одному из модулей системы остаточных классов. Однако на практике требуется чтобы коэффициент масштабирования был равен произведению модулей.
В данном изобретении предлагается использовать коэффициент масштаба, равный произведению нескольких множителей.
Целью изобретения является уменьшение объема оборудования, повышение скорости масштабирования чисел и расширение функциональных возможностей.
i
j
Поставленная цель достигается тем, что нейронная сеть ускоренного масштабирования модулярных чисел содержит входной слой 2 с нейронами 3, нейронные сети конечного кольца (НСКК) по модулям СОК 4 и НСКК 5 по модулю разности чисел ΔС(A)=р-p. Структура НСКК зависит от внешних параметров, которые определяются модулями СОК. Функционирование нейронной сети ускоренного масштабирования модулярных чисел определяется структурой НСКК по модулям СОК, весовыми коэффициентами и выходным значением НСКК по модулю разности чисел. НСКК обучается путем установки весовых коэффициентов, которые являются константами и определяется выбранными модулями СОК, поэтому режим классического обучения сети не используется.
Известен ряд алгоритмов для масштабирования чисел СОК. Ранние попытки масштабирования разбиваются на две категории: масштабирование одним модулем, подразумевающее, что число СОК подвергается делению на один из модулей или масштабирование на произведение модулей, при этом процесс масштабирования происходит итерационно. Тем не менее, эти методы являются медленными и требуют обработки чисел с большей длиной слова вне СОК.
i
Метод ускоренного приблизительного масштабирования чисел на произведение модулей СОК с модулями р и динамическим диапазоном  основан на применении в качестве масштабного коэффициента подмножества .
1
2
n
Если задан ряд положительных целых чисел р, р, …, р, называемых в дальнейшем основанием системы, то под системой счисления в остаточных классах будем понимать такую систему, в которой целое положительное число представляется в виде набора остатков (вычетов) по выбранным основаниям
причем образование цифр осуществляется следующим процессом
i
i
то есть цифра i-го разряда α числа А есть наименьший неотрицательный остаток от деления А на р.
Объем диапазона представимых чисел определяется
Для обратного перевода используется метод, основанный на применении ортогональных базисов, при этом число А представляются в виде
i
где B ортогональные базисы СОК и могут быть представлены в виде
i
где k целое положительное число, которое называется весом ортогонального базиса.
i
Причем k должно выбираться таким образом, чтобы имело место следующее сравнение
i
Для вычисления k необходимо найти .
i
i
i
i
i
i
i
Так как Р составлено из Р множителей взаимно простых чисел с р, то Р не будет нацело делиться на р, в результате деления получим некоторый остаток, который обозначим через δ. Тогда в соответствии с (6) k определяется как решение сравнения
i
i
i
Ввиду сравнительной малости величин оснований для набора модулей р составлены таблицы решений сравнений (7), в которых по величине δ находится соответствующее k.
Рассмотрим метод масштабирования чисел СОК, основанный на центральной функции. Метод состоит из выведения центра внутри СОК, при этом все вычисления сокращаются до результатов внутри модулей СОК.
Масштабирование числа СОК на основе китайской теоремы об остатках
Введено понятие центральной функции, которая определяется для целого А как
i
i
i
где А обозначает А по модулю р, а m обозначает i-ый вес (значение).
n
Полагая А=Р в (8), получим
Разделив левую и правую части на Р, получим
i
Для получения небольших значений С(P) необходимо, чтобы некоторые значения m были отрицательными. Подставляя (10) в (8), получим
i
j
Значения m можно определить выражением (10), если взять обе стороны по модулю р
i
j
где  для всех p за исключением p. Из (12) определим
j
j
j
При выбранных значениях С(Р) некоторые m могут быть отрицательными, что обеспечивает С(Р)<<Р. Заметим, что если С(Р) является составной р, то соответствующее значение m=0. Область центральной функции G(P) определяется как
Теперь Китайская теорема об остатках для преобразования чисел СОК обратно в позиционные (то есть десятичные или двоичные) может быть выражена как
i
где R(n) известна как функция ранга, а B, обозначает i-ый базис СОК, тогда
Подстановка (15) в (11) дает
Упрощение и реконструкция (17) дает
i
Устанавливая A=В в (11), получаем
Откуда
которое известно как Китайская теорема об остатках центральной функции. Тем не менее, вследствие невыполнимости вычисления R(n) независимо, предпочтительная форма теоремы об остатках центральной функции выглядит как
i
i
i
Пример. Рассмотрим СОК с набором модулей p={2,3,5,7,11,13}, тогда Р=30,030, а Р={1,2,1,6,6,3}. Далее выберем С(Р)=3·5·11=165. Затем из (13) вычислим значения m:
i
i
Для минимизации центральной функции необходимо выбрать значения m с небольшими размерами. В этом примере выберем набор значений m={-1,0,0,3,0,1}, а его правомерность можно проверить выражением (9)
С(Р)=-1×15015+3×4290+1×2310=165.
i
Альтернативная установка значений m={1,0,0,-4,0,1} также возможна, правомерность которой определяется как
С(Р)=1×15015+-4×4290+1×2310=165
Метод приблизительного масштабирования модулярных чисел
Метод приблизительного масштабирования определяется в пределах представления СОК, не выходя в другие формы представления (позиционные или обобщенные позиционные системы счисления).
Из равенства (11) видно, что С(A) можно вычислить внутри СОК, что и определяет приблизительную масштабную версию А
j
k
j
k
j
k
j
k
Это достигается разделением набора модулей на два подмножества наборов, которые определяют Р и Р так, что PP=P и Pj|Pk≈1. Затем можно выполнить масштабирование с помощью Р или Р (другими словами, извлечение С(А) из С(Р)=Р или С(Р)=Р).
Сначала установим . Затем из (22) находим
j
j
j
j
для набора модулей р, который создал Р. Но Р это составляющая С(Р), так что
k
k
J
Тем не менее, для набора модулей р, который образует Р, не делит P, поэтому подобное упрощение невозможно
j
Таким образом, равенство (23) можно вычислить внутри набора модулей р, но (24) нет. Подобно, если
k
J
k
k
j
j
K
K
k
который можно вычислить внутри набора модулей р. Отсюда  можно вычислить внутри набора модулей р, но не набора модулей p, к тому же  можно вычислить внутри модуля набора модулей р, но не подстановки р. Тем не менее, если использовать разницу между центрами ΔС(A)=С(А)-С(A), то можно вычислить С(А) набора модулей р, расширяя внутри
J
k
J
K
C(А) наборы модулей р. Другими словами, добавляя ΔС(A) (или вычитая) к значениям одного набора модулей масштабных остатков, доступно С(А) или С(А} по всем остаткам, а масштабное значение А можно получить внутри СОК. Простое выражение для ΔС(A) можно получить из(20) как
которое можно упростить для практического использования
где
, а .
Из-за сложности определения значения R(A) из остатков лучше использовать выражение (28) в виде
Это выражение очень удобное для оценки ΔС(A), так как оно имеет малый модуль ΔС(Р).
Численный пример и нейросетевая реализация ускоренного масштабирования модулярных чисел
1
2
3
4
5
6
j
1
4
6
k
2
3
5
Провести масштабирование числа А=1859107, представленного в системе остаточных классов (СОК) по модулям р=7, р=11, p=13, p=17, p=19, p=23 А=(5,8,3,4,14,17) на число Р=p·p·p=7·17·23=2737 или Р=р·р·р=11·13·19=2717, которые представляют подмножество модуля .
1
2
3
4
5
6
j
k
При этом общий диапазон представления числа в СОК определится как P=p·p·p·p·p·p=7·11·13·17·19·23=7436429, а разность между выбранными подмножествами ΔP(Р)=Р-Р=2737-2717=20.
i
Для нахождения ортогональных базисов B (i=1,2,…,n) определим
и ,
i
i
i
*
*-1
тогда значение P =(1062347, 676039, 572033, 437437, 391391, 323323), Р =(6,1,2,12,2,2), а B=(6374282, 676039, 1144066, 5259244, 782782, 646646).
i
j
j
k
k
Используя вычислительную модель (13), определим весовые коэффициенты m для С(Р)=Р и С(Р)=Р.
i
k
i
Для , отсюда m=(0,-2,1,0,2,0), и для С(Р)=2717, m=(-1,0,0,-2,-6).
j
k
i
Теперь выразим С, С и ΔР(B) через ортогональные базисы СОК, тогда на основе  получим
j
i
C(B)=(2346, 249, 421, 1932, 288, 238),
k
i
i
С(B)=(2329, 247, 418, 1918, 286, 236), ΔP(B)=(17, 2, 3, 14, 2, 2).
i
j
k
Выполним масштабирование числа А=(5, 8, 3, 4, 14, 17) с помощью  и  на основе китайской теоремы об остатках, результат которой необходимо взять по модулю р (i=1,2,…,n), поэтому предварительно представим Р и Р по модулям выбранной СОК:
j1
i
С(B)mod7=(1,4,1,0,1,0);
j2
i
C(B)mod17=(0,11,13,11,16,0);
j3
i
C(B)mod23=(0,19,7,0,12,8);
k
i
C(B)mod11=(8,5,0,4,0,5);
k
i
C(B)mod13=(2,0,2,7,0,2);
k
i
C(B)mod19=(11,0,0,18,1,8),
тогда:
j
C(A)mod7=(5·1+8·4+3·1+4·0+14·1+17·0)mod7=5
j
C(A)mod17=(5·0+8·11+3·13+4·11+14·16+17·0)mod17=4
j
C(A)mod23=(5·0+8·19+3·7+4·0+14·12+17·8)mod23=l7
k
C(A)mod11=(5·8+8·5+3·0+4·4+14·0+17·5)mod11=5
k
C(A)mod13=(5·2+8·0+3·2+4·7+14·0+17·2)mod13=0
k
C(A)mod19=(5·11+8·0+3·0+4·18+14·1+17·8)mod19=11
Параллельно вычислим :
ΔP(A)mod20=(5·17+8·2+3·3+4·14+14·2+17·2)mod20=8.
k
Наконец, проведем сложение ΔР(A) с С(А), тогда
j
k
C(A)mod11=C(A)+ΔP(A)mod11=5+8=13=2mod11
j
k
C(A)mod13=C(A)+ΔP(A)mod13=0+8=8mod13
j
k
C(A)mod19=C(A)+ΔP(A)mod19=11+8mod19=0.
j
Итак, значение модулярного числа А=1859107 (или (5,2,8,4,0,17) в СОК формате) после приблизительного масштабирования на число 2717 равно С(A)=(5,2,8,4,0,17). Проверим путем обратного преобразования в десятичное, используя китайскую теорему об остатках
Действительно, при приблизительном масштабировании числа А=1859107 на число 2717 получим число .
На чертеже представлена нейронная сеть для ускоренного масштабирования модулярных чисел для шести модулей, используемых в числовом примере. Принцип работы данного изобретения изложен ниже.
i
j
k
Нейронная сеть для ускоренного масштабирования модулярных чисел представляет собой набор n-НСКК 4 по модулям p, где i=1,2,…,n, и НСКК 5 по модулю разности чисел ΔС(A)=Р-P.
1
2
3
4
5
6
i
i
i
j
i
k
i
m
Информация в виде остатков масштабируемого числа А=(α,α,α,α,α,α) 1 поступает на входы НСКК 4 по модулям р и НСКК 5 по модулю ΔС(A). Выходы НСКК 4 по модулям р представляют результат масштабирования чисел А 6, выходы 7. Разряды (остатки) чисел в реальной схеме представлены в двоичном коде. Для упрощения схемы остатки будем рассматривать в десятичном коде. Весовые коэффициенты ΔС(B) 9, С(В) 10, C(B) 11 (синаптические веса) НСКК 4, 5 определяются константами выбранной системы остаточных классов и поступают на первые входы умножителей 12, которые представляют собой просмотровые таблицы, выполненные в виде табличных ROM (постоянные запоминающие устройства). Там, где весовые коэффициенты равны 0, входные шины для НСКК 4 не показаны.
Нейронный слой 2 нейроны 3 обеспечивают прием разрядов масштабируемого числа А 1, которые затем поступают на первые (информационные) входы умножителей 12, а на вторые (синаптические) входы умножителей 12 поступают значения весовых коэффициентов 9, 10, 11.
i
i
i
i
k
i
i
i
i
i
i
Информационные входы являются адресными входами табличных умножителей, содержимое которых предварительно вычислено и сохранено в просмотровых таблицах соответственно AC(B), AC(B) и АΔC(B). Организация просмотровых таблиц определяется двоичным представлением значений модулей p и ΔС(Р) соответственно l и l' и выражается формулами l=[log p] и l′=[log ΔC(P)]. Выходные значения умножителей суммируются в HCKKmod7-HCKKmod23 и НСКК ΔР(В), где реализуются вычислительные модели (24-26).
Организация и функционирование НСКК приведены в патенте №2279132, опубликованные 10.07.2005, Бюл.19. Финальным шагом является суммирование выходного значения НСКК ΔC(P), в нашем примере НСКК mod20, выход 7, с содержимым НСКК mod11, НСКК mod13 и HCKK mod19. На выходах HCKKmod7-HCKKmod23 формируются значения разрядов масштабированного числа , 6.
i
Время суммирования определяется 0[logn]+1 циклами синхронизации. Заметим, что два соответствующих коэффициента в HCKK mod7 - HCKK mod23 С(B)=0, поэтому используется n-2 входов HCKK mod7 - HCKK mod23.
Время масштабирования модулярного числа на произведение модулей в предложенной схеме определяется временем масштабирования на один модуль в известных схемах. Время масштабирования чисел на произведение модулей в известных схемах определяется итерационным методом и линейно зависит от числа модулей, на произведение которых осуществляется масштабирование.
Выше было сказано, что масштабирование модулярных чисел на произведение модулей может быть выполнено в рамках представления чисел в СОК без использования итераций. Этим обеспечивается высокая скорость масштабирования модулярных чисел. Масштабированное число 6 появляется на выходах НСКК mod7 - HCKK mod23, выходы 7.Операция масштабирования на коэффициент масштабирования, равного произведению модулей, выполняется за 3 цикла синхронизации.
В известном изобретении масштабирование осуществляется только на один из модулей, и если их использовать для масштабирования на коэффициент масштаба, равный произведению модулей, то процесс будет итерационным и время масштабирования определяется числом модулей СОК, входящих в масштабный коэффициент. Количество итераций линейно зависит от числа модулей, входящих в масштабный коэффициент, что и отличает это изобретение от известного. Изобретение предназначено для ускоренного масштабирования модулярных чисел в модулярных нейрокомпьютерах.