При разработке вычислительных средств, функционирующих в системе остаточных классов (СОК) возникает важная задача обеспечения достоверности всего потока информации. Обеспечение достоверности всего потока информации прямо и непосредственно связано с увеличением производительности вычислительных машин. Для каждого специального кода, обладающего способностью к обнаружению и коррекции ошибки, характерно наличие двух групп цифр – информационной и контрольной. В информационную группу входят цифры, составляющие числовое значение закодированной величины, а в контрольную – цифры, дополнительно вводимые для целей обнаружения и коррекции возможных искажений.

В настоящее время СОК привлекает все более пристальное внимание из – за ее способности поддерживать высокоскоростную арифметику при параллельной обработки данных.

Система остаточных классов представляет собой такую систему, в которой целое положительное число представляется в виде набора остатков по выбранным основаниям [1]

А = (a₁, a₂,…, a_n), a_n
º
А (mod p_n), n = 1, 2,…, k,            (1)

где p_n – основания системы остаточных классов.

Корректирующие свойства кодов в остатках, как и любого другого кода, проявляется при введении избыточности. Пусть число А представлено остатками a₁, a₂,…, a_n по основаниям p₁, p₂,…, p_n. Диапазон представления чисел по выбранным основаниям равен произведению этих оснований, его обозначим как

R = , (2)

где R – рабочий диапазон системы.

Введем основание p_n+1, и будем представлять числа в системе из n+1 оснований. Это означает, что будем передавать числа и производить операции над числами, лежащими не в диапазоне [0, R), а в более широком диапазоне [0, P).

P = R× p_n+1,

где P– полный диапазон системы с одним контрольным основанием. Если в результате, какой – либо операции или при передаче числа оказалось, что получено число А>R, то значит, при проведении операции была допущена ошибка.

Таким образом, для того чтобы обнаружить наличие или отсутствие ошибки в числе А, надо сопоставить его с диапазоном R. При этом если оказалось А
³
R, значит, имела место ошибка, по крайней мере, в одной цифре. Если же А < R, то либо ошибки нет, либо она носит более сложный характер. Будем в дальнейшем числа, меньшие R, называть правильными, а большие R – неправильными.

Пусть основания p₁, p₂,…, p_n, p_n+1 системы остаточных классов удовлетворяют условию

p_i< p_n+1

где i = 1, 2, …, n, и пусть А = (a₁, a₂,…, a_i ,…, a_n, a_n+1) – правильное число. Тогда величина A не изменится, если будем представлять его в системе оснований, из которой изъято основание p_i (т.е. если в представлении A зачеркнуть цифру a_i).

Назовем число А_i, полученное из А зачеркиванием цифры a_i, проекцией числа А по основанию p_i.

Если в упорядоченной системе оснований

p₁< p₂< …< p_n< p_n+1

задано правильное число A, то проекции этого числа по всем основаниям совпадают, т.е.

A₁ = A₂ =…= A_i =…= A_n+1 <.

По величинам проекций можно сделать выводы о правильности отдельных цифр. Так, например, если в упорядоченной системе оснований проекция А_i числа А = (a₁, a₂,…, a_i ,…, a_n, a_n+1) по основанию p_i удовлетворяет условию

A_i >, (3)

то цифра a_i правильная, если возможна ошибка по одному какому – либо основанию. Если же (3) имеет место для всех i = 1, 2, …, n, то ошибочна цифра a_n+1.

Введение только одного контрольного основания не позволяет в общем случае локализовать ошибочный разряд. Коды с двумя контрольными основаниями обладают большими обнаруживающими и корректирующими возможностями. Таким образом, дополнении к рассмотренной выше системе оснований добавляем основание p_n+2
> p_n+1

p₁, p₂,…, p_n, p_n+1, p_n+2

и будем представлять числа, лежащие в рабочем диапазоне [0, R), в системе имеющей диапазон [0, P), где

P= R×
p_n+1× p_n+2.

Если в системе p₁, p₂,…, p_n, p_n+1, p_n+2 с двумя контрольными основаниями задано неправильное число = (), то необходимым и достаточным условием ошибочности цифры в является правильность его проекции _i по основанию p_i. Из этого вытекает следующий алгоритм определения ошибочной цифры. Вычисляются проекции числа по всем основаниям

₁, ₂,…, _i,…, _n+2.

Среди этих проекций есть одна _i < . Тогда ошибочной является цифра .

Заметим, что данный алгоритм, может быть, применим для нахождения и исправления не только одиночной ошибки, но и при некоторых условиях также двойных и тройных ошибок.

Обработка информации, основанная на параллелизме и модульности СОК, служит идеальной основой для разработки довольно значительного набора методов повышения отказоустойчивости вычислительных средств. С повышением интереса к машинной арифметики в СОК возникла возможность построения кодов обнаруживающих и исправляющих ошибки с применением нейронной сети (НС).

Нейронная сеть является совокупностью элементов (нейронов), соединенных некоторым образом так, чтобы между ними обеспечивалось взаимодействие и представляет собой высокопараллельную динамическую систему [2]. Проблема исследования надежности нейронных сетей находится еще в самом начале своего развития. Ее решение окажет значительное воздействие на реализацию нейрокомпьютеров (НК) построенных по новым технологиям. Структура нейронных ЭВМ представляет собой массив процессоров. Это предъявляет особые требования к процедуре диагностики по крайней мере той части нейронных ЭВМ, которая представляет сеть нейронов.

В статье представлен алгоритм локализации ошибок методом проекции числа в СОК по каждому из оснований на основе НС. Такая сеть будет представлять собой НС конечного кольца (НСКК) и пороговую функцию активации (рис. 1).

Рисунок 1 – Нейронная сеть, обеспечивающая метод проекций в СОК

НСКК состоит из сборного и вычислительного слоев [3]. Сборный слой используется для сбора входов, принадлежащих одному двоичному разряду входных источников. Вычислительный слой реализует вычислительную модель

На этапе настройки сети устанавливаются следующие значения весов
W_i=B_i, где B_i – ортогональные базисы СОК. Функция активации представляет собой порог (рис. 2).

Рисунок 2 – Пороговая функция активации

Если применяется пороговая функция активации, то выходное значение нейронного элемента [4]

y =

Таким образом, НС локализует ошибку в данных, представленных в СОК с основаниями p₁, p₂,…, p_n, p_n+1, p_n+2, по значению проекций числа A. Если на выходе нейронной сети «1» – ошибка по данному основанию, «0» – ошибки нет.

Из сказанного выше хорошо видно, что существующие разработки по теории СОК обеспечивают реальную возможность повышения информационной надежности вычислительной системы. Это обусловлено специфическими способностями представления и обработки непозиционных кодовых структур в СОК [5]. Следовательно, внедрение чисел в модулярном коде, является одним из наиболее перспективных путей повышения отказоустойчивости и быстродействия вычислительных средств.

Для иллюстрации рассмотренного метода проекции числа в СОК по каждому из оснований приведем пример.

Выберем систему p₁=2, p₂=3, p₃=5, p₄=7, для которой диапазон правильных величин (рабочий диапазон) R=2×3×5×7=210. Введем контрольные основания p₅=11, p₆=13. Тогда полный диапазон определяется как: P=210×11×13=30030.

Вычислим ортогональные базисы этой системы:

В₁=15015, В₂=20020, В₃=6006, В₄=25740, В₅=16380 В₆=6930.

Пример. Передано число А= (1, 2, 2, 3, 6, 4) = 17. Принято вместо него число = (1, 2, 2, 3, 1, 4). Вычисляем величину :

= 1×15015+2×20020+2×6006+3×25740+1×16380+4×6930 – r×30030==8207.

Неравенство 8207 > 210 устанавливает, что неправильное.

Вычислим проекции числа по каждому из оснований.

По основанию p₁=2.

Для системы с основаниями: p₂=3, p₃=5, p₄=7, p₅=11, p₆=13 вычислим ортогональные базисы В⁽¹⁾₂=5005, В⁽¹⁾₃=6006, В⁽¹⁾₄=10725, В⁽¹⁾₅=1365, В⁽¹⁾₆=6930.

Тогда

₁= (2, 2, 3, 1, 4)= 2×5005+2×6006+3×10725+1×1365+4×6930 – r₁×15015= =8207>210.

По основанию p₂=3.

Для системы с основаниями: p₁=2, p₃=5, p₄=7, p₅=11, p₆=13 вычислим ортогональные базисы В⁽²⁾₁=5005, В⁽²⁾₃=6006, В⁽²⁾₄=5720, В⁽²⁾₅=6370, В⁽²⁾₆=6930.

Тогда

₂= (1, 2, 3, 1, 4)= 1×5005+2×6006+3×5720+1×6370+4×6930 – r₂×10010= =8207>210.

По основанию p₃=5.

Для системы с основаниями: p₁=2, p₂=3, p₄=7, p₅=11, p₆=13 вычислим ортогональные базисы В⁽³⁾₁=3003, В⁽³⁾₂=2002, В⁽³⁾₄=1716, В⁽³⁾₅=4368, В⁽³⁾₆=924.

Тогда

₃= (1, 2, 3, 1, 4)= 1×3003+2×2002+3×1716+1×4368+4×924 – r₃×6006= =2201>210.

По основанию p₄=7.

Для системы с основаниями: p₁=2, p₂=3, p₃=5, p₅=11, p₆=13 вычислим ортогональные базисы В⁽⁴⁾₁=2145, В⁽⁴⁾₂=2860, В⁽⁴⁾₃=1716, В⁽⁴⁾₅=3510, В⁽⁴⁾₆=2640.

Тогда

₄= (1, 2, 2, 1, 4)= 1×2145+2×2860+2×1716+1×3510+4×2640 – r₄×4290= =3917>210.

По основанию p₅=11.

Для системы с основаниями: p₁=2, p₂=3, p₃=5, p₄=7, p₆=13 вычислим ортогональные базисы В⁽⁵⁾₁=1365, В⁽⁵⁾₂=910, В⁽⁵⁾₃=546, В⁽⁵⁾₄=1170, В⁽⁵⁾₆=1470.

Тогда

₅= (1, 2, 2, 3, 4)= 1×1365+2×910+2×546+3×1170+4×1470 – r₅×2730= 17<210.

По основанию p₆=13.

Для системы с основаниями: p₁=2, p₂=3, p₃=5, p₄=7, p₅=11 вычислим ортогональные базисы В⁽⁶⁾₁=1155, В⁽⁶⁾₂=1540, В⁽⁶⁾₃=1386, В⁽⁶⁾₄=330, В⁽⁶⁾₅=210.

Тогда

₆= (1, 2, 2, 3, 1)= 1×1155+2×1540+2×1386+3×330+1×210 – r₆×2310= =1277>210.

Итак, все проекции числа , кроме ₅ неправильны. Следовательно, ошибочна цифра a₅=1 по основанию p₅=11.

Представленный алгоритм локализации ошибок методом проекции числа в СОК по каждому из оснований на основе НС может быть, применим для локализации не только одиночной ошибки, но и при некоторых условиях также двойных и тройных ошибок, обеспечивает реальную возможность повышения информационной надежности НК. Это обусловлено специфическими способностями представления и обработки непозиционных кодовых структур в СОК.

1. Червяков Н. И., Горденко Д. В. Нейронная сеть для округления и масштабирования чисел, представленных в системе остаточных классов // Патент на изобретение rus 2271570 26.05.2003.
2. Червяков Н. И., Сивоплясов Д. В., Горденко Д. В. Нейронная сеть для преобразования полиадического кода в код системы остаточных классов // Нейрокомпьютеры: разработка, применение. 2003. № 10-11. с. 10.
3. Горденко Д. В., Горденко Н. В. Локализация ошибок в устройствах цифровой обработки сигналов на основе алгебры полиномов // Вестник Сев-Кав ГТИ. 2009. № 9. с. 56-61.
4. Горденко Д. В., Резеньков Д. Н., Яйлаханов С. В. Высоконадежные комплексы и средства связи на нейросетевых элементах. Москва, 2010.
5. Горденко Д. В., Горденко Н. В., Павленко Н. А., Павлюк Д. Н., Ткачук Р. В. Коррекция ошибок в системе остаточных классов с минимальной временной сложностью на основе метода расширения оснований // Известия высших учебных заведений. Северо-Кавказский регион. Серия: технические науки. 2007. № 4. с. 12-14.

Все статьи автора «Горденко Дмитрий Владимирович»