Сборник трудов III международной научно практической конференции

381 
 
 
4.
 
Червяков  Н.И.  Методы  и  принципы  построения  модулярных 
нейрокомпьютеров  //  50  лет  модулярной  арифметике,  сборник  трудов 
Юбилейной  Международной  научно-технической  конференции.  Москва, 
ОАО «Ангстрем», МИЭТ. – 2006. – С. 239-249. 
5.
 
Червяков  Н.И.  Реализация  высокоэффективной  модулярной 
цифровой  обработки  сигналов  на  основе  программируемых  логических 
интегральных схем // Нейрокомпьютеры: разработка, применение. – 2006. 
– № 10. – С. 24-36. 
6.
 
Червяков  Н.И.,  Бабенко  М.Г.  Системы  защиты  данных  на 
эллиптической  кривой.  Модулярная  арифметика.  Методы  и  алгоритмы 
моделирования  вычислительных  структур  на  эллиптических  кривых  с 
параллелизмом машинных операций. М.: Saarbücken, 2011.  - 121 с. 
7.
 
Червяков  Н.И.,  Бабенко  М.Г.,  Кучеров  Н.Н.  Применение 
корректирующих  кодов  СОК  для  диагностики  работы  модулярных 
процессоров// Наука. Инновации. Технологии. 2014. № 3. С. 24-39. 
 
Червяков Н.И., Шалалыгин Д.Г. 
АНАЛИЗ МЕТОДОВ КОРРЕКЦИИ ОШИБОК В СИСТЕМЕ 
ОСТАТОЧНЫХ КЛАССОВ 
 Северо-Кавказкий федеральный университет, г.Ставрополь, Россия 
 
Аннотация. В статье рассматриваются теоретические обоснования и 
анализ выполнения коррекции ошибок в системе остаточных классов (СОК). 
Также анализируется модификации алгоритма вычисления интервального 
номера. 
Введение 
Современные  средства  цифровой  обработки  сигналов  должны 
обеспечивать  первичную  обработку  сигнала  в  реальном  масштабе  времени. 
Распараллеливание на уровне арифметических операций позволяет обеспечить 

382 
 
 
данное  требование.  При  этом  использование  алгебраических  кодов, 
обладающих 
свойством 
кольца, 
позволяет 
проводить 
с 
высокой 
эффективностью  операции  по  обнаружения  и  коррекцию  ошибок.  Так  как 
данные коды относятся к кодам классов вычетов, то для организации коррекции 
результата должны быть использованы позиционные характеристики.  
 
Основная часть
 
При  цифровой  обработке  сигналов  (ЦОС)  в  реальном  масштабе 
применяют  параллельно-конвейерные  вычисления.  Одним  из  наиболее 
перспективных  направлений  обеспечения  высокой  скорости  обработки 
сигналов является использование модулярных непозиционных кодов. В данных 
системах  позиционные  отсчеты  сигналов  представляются  в  виде  наборов 
остатков,  величины  которых  определяются  значениями  оснований  кодов 
классов  вычетов  [1-4].  Наряду  с  высоким  быстродействием  непозиционные 
модулярные  коды  позволяют  проводить  операции  по  поиску  и  коррекции 
ошибок,  которые  возникают  в  процессе  вычислительных  устройств  из-за 
отказов  оборудования.  Правильный  выбор  соответствующего  алгоритма, 
позволяющий  определить  ошибочный  остаток,  а  также  глубину  ошибки, 
выполняет поиск и коррекцию ошибок при минимальных схемных и временных 
затратах. 
Известно,  что  введение  двух  контрольных  оснований  в  упорядоченное 
множество оснований СОК, удовлетворяющих условию 
2
1
1




k
k
k
k
p
p
p
p
, 
 
 
 
 
(1) 
где 
k
-  количество  рабочих  оснований,  позволяет  осуществлять  коррекцию 
однократных ошибок, возникающих в кодах СОК. Использование контрольных 
оснований расширяет рабочий диапазон, определяемый согласно 



k
i
i
раб
p
P
1
   
 
 
 
 
(2) 
до значения полного диапазона 

383 
 
 









2
1
2
1
k
k
i
i
раб
k
i
i
полн
p
P
p
P
   
 
 
(3) 
Комбинация  СОК  считается  разрешенной,  если  она  принадлежит 
рабочему  диапазону.  Известно,  что  ошибка  преобразует  правильную 
комбинацию 
)
,
,
,
(
2
2
1


k
A




  в  комбинацию 
)
,
,
,
,
(
2
*
*
1
*


k
i
A





,  где 
i
i






*
  –  искаженный  остаток, 
i


  –  глубина  ошибки.  В  этом  случае 
производится  перевод  искаженного  числа  из  рабочего  диапазона,  в  диапазон 
полный.  Следовательно,  зная  местоположение  искаженной  комбинации  
)
,
,
,
,
(
2
*
*
1
*


k
i
A





,  можно  однозначно  определить  основание,  по  которому 
произошла ошибка, а также ее глубину. 
Данное  свойство  непозиционных  модулярных  кодов  и  предопределило 
повышенный  интерес  разработчиков  к  позиционным  характеристикам,  с 
помощью  которых  можно  однозначно  определить  ошибочное  основание  и 
глубину  ошибки.  В  качестве  позиционных  характеристик  могут  выступать 
коэффициенты  обобщенной  полиадической  системы  счисления  (ОПСС), 
приведенные  в  работах  [5,  6].  В  работах  [7,  8]  рассматриваются  алгоритмы 
расширения  системы  оснований  модулярного  кода  с  последующим 
вычислением  невязки  кода.  Особое  место  среди  позиционных  характеристик 
занимает  интервальный  номер  [9].  Это  обусловлено  тем,  что  данная 
позиционная  характеристика  имеет  простой  физический  смысл.  Определение 
данной характеристики осуществляется согласно 
 









раб
инт
P
A
l
  
 
 
 
 
(4) 
Очевидно, что операция деления (4) относится к немодульным, ее сводят 
к  совокупности  модульных  операций.  В  работе  [9]  представлен  алгоритм, 
который  позволяет  осуществлять  поиск  и  коррекцию  ошибки  в  коде  классов 
вычетов, используя интервальный номер числа. 

384 
 
 
В основу данного алгоритма положено свойство подобия ортогональных 
базисов полных и безизбыточных систем класса, согласно которому 
)
(mod
*
раб
i
i
P
B
B

,    
 
 
 
(5) 
где 
*
B
и
B
– ортогональные базисы безизбыточной и полной системы. 
Тогда, используя (5), получаем: 
*
*
j
раб
i
i
раб
раб
i
i
B
P
K
B
P
P
B
B












.  
         (6) 
Подставив последнее равенство в выражение (4) получаем 














2
1
*
)
(
k
i
раб
полн
i
раб
i
i
P
RP
B
P
K
l

,   
 
 
(7) 
где
R
– ранг полной системы оснований СОК. 
Проведя упрощения, имеем: 
конт
r
k
i
раб
полн
k
j
раб
j
j
i
i
P
P
RP
P
B
K
l
mod
1
1
*


























, 
 (8) 
где 





2
1
k
k
i
i
конт
p
P
. 
Так как множество значений интервального номера 1 представляет собой 
кольцо по модулю 
конт
P
, то выражение (8) можно преобразовать к виду 






полн
P
k
i
i
i
R
K
l
2
1
*

,  
 
 
 
 
(9) 
где 











k
j
раб
j
j
P
B
R
1
*
*

 – ранг в безизбыточной системы. 
Если  число,  представленное  в  модулярном  коде,  принадлежит  рабочему 
диапазону,  то  значение  интервального  номера  равно  нулю,  т.е. 
0

l
.  При 
возникновении ошибки число
A
 не будет принадлежать рабочему диапазону, а 
будет размещаться вне его. Следовательно, если номер числа будет отличен от 
нуля,  то  это  свидетельствует  о  том,  что  исходная  комбинация  модулярного 
числа содержит ошибку. 
Проведенный  анализ  необходимых  схемных  затрат  на  реализацию 
данного  алгоритма  вычисления  позиционной  характеристики  показал,  что 

385 
 
 
применение  составного  модуля 
конт
P
,  по  которому  определяется  значение 
интегрального  номера  1,  с  точки  зрения  аппаратурных  затрат,  является  не 
самым  оптимальным.  Это  обусловлено  тем,  что  одномерные  исчисления  над 
кольцом,  определяемым  значением 





2
1
k
k
i
i
конт
p
P
,  требует  обработки 


конт
P
2
log
 
разрядных операндов. 
С  целью  сокращения  аппаратурных  затрат  в  работе[9]  предлагается 
усовершенствовать  данный  алгоритм.  В  основу  усовершенствования 
целесообразно  положить  изоморфизм,  порожденный  китайской  теоремой  об 
остатках  (КТО).  Использование  этого  изоморфизма  позволяет  перейти  от 
одномерной  обработки  к  многомерной.  Приравнивая  соответствующие 
значения 
конт
P
 и основания 
2
1
,


k
k
p
p
 получаем 2 преобразования, которые можно 
реализовать параллельно  























r
k
k
P
r
k
i
i
i
r
k
P
r
k
i
i
i
k
R
K
l
R
K
l
1
*
1
*
1
1


 
 
 
 
 
(10) 
Несмотря  та  то,  что  выражения  (9)  и  (10)  позволяют  получить 
одинаковый  результат,  тем  не  менее,  использование  изоморфизма  КТО 
позволяет  сократить  схемные  затраты,  которые  необходимы  на  реализацию 
алгоритма  вычисления  интервала.  Проведенный  анализ  [9]  показал,  что 
реализация вычисления интервала согласно (10) потребовала на 14,3% меньше 
схемных  затрат  по  сравнению  с  алгоритмом  (9).  При  этом  при  увеличении 
размерности  контрольных  оснований  выигрыш  в  схемных  затратах 
увеличивается. 
 
Заключение 
Использование  избыточных  модулярных  кодов  позволяет  осуществлять 
поиск  и  коррекцию  ошибок,  которые  могут  возникать  в  процессе 

386 
 
 
функционирования 
непозиционного 
спецпроцессора. 
Проанализирован 
алгоритм, позволяющий определить местоположение ошибки и ее глубину с ис-
пользованием  позиционной  характеристики  интервала.  Был  рассмотрен 
алгоритм,  в  основу  которого  был  положен  изоморфизм  КТО.  Переход  к 
параллельному  алгоритму  позволил  сократить  схемные  затраты,  необходимые 
для  вычисления  позиционной  характеристики  при  обработке  16-разрядных 
данных  на  14,3%  по  сравнению  с  классическим  методом  вычисления 
интервала  числа.  При  этом  при  увеличении  размерности  контрольных 
оснований возрастает выигрыш от использования разработанного алгоритма. 
 
Литература 
1. 
Бережной  В.В.,  Калмыков  И.А.,  Червяков  Н.И.,  Щелкунова  Ю.О.,  
Шилов  А.А.  Нейросетевая  реализация  в  полиномиальной  системе  классов 
вычетов  операции  ЦОС  повышенной  разрядности  //  Нейрокомпьютеры: 
разработка и применение. 2004. - № 5-6. - С. 94. 
3.Калмыков И.А., Оленев А.А., Бережной В.В. Систолический процессор 
дискретного  преобразования  Фурье  с  коррекцией  ошибки  //  Патент  на 
изобретениеRUS 2018950 
4.Калмыков  И.А.,  Червяков  Н.И.,  Щелкунова  Ю.О.,  Шилов  А.А., 
Бережной  В.В.  Архитектура  отказоустойчнвой  нейронной  сети  для  цифровой 
обработки  сигналов  //  Нейрокомпьютеры:  разработка  и  применение.  2004.  - 
№12. -С. 51-57. 
5.
Калмыков  И.А.,  Ханватов  А.Б.,  Сагдеев  А.К.  Разработка  методов 
обнаружения  и  коррекции  ошибок  в  коде  полиномиалыюй  системы  классов 
вычетов, базирующихся на вычислении синдрома ошибки // Фундаментальные 
исследования. - 2006. - №2. - С. 13.
 
 
Червяков Н.И., Шалалыгин Д.Г., Шалалыгина И.В. 

387 
 
 
КРАТКАЯ ХАРАКТЕРИСТИКА СИСТЕМЫ ОСТАТОЧНЫХ 
КЛАССОВ 
Северо-Кавказкий федеральный университет, г.Ставрополь, Россия 
 
Ключевые  слова:  Система  остаточных  классов  (СОК),  класс  вычетов, 
китайская теорема об остатках (КТО), модульные операции.
 
Аннотация 
Основные назначения этой статьи – провести теоретическое обоснование и 
анализ выполнения арифметических операций над числами, представленными в 
СОК.  Будут  рассмотрены  наиболее  важные  теоретико-числовые  алгоритмы, 
являющиеся основой арифметики в остаточных классах.  
Введение 
Основной теоретико-числовой базой системы остаточных классов является 
теория  сравнений.  Полной  системой  вычетов  по  модулю 
p
  называется 
совокупность 
p
 целых чисел, содержащая точно по одному представителю из 
каждого  класса  вычетов  по  модулю 
p
.  Каждый  класс  вычетов  по  модулю 
p
 
содержит в точности одно из чисел совокупности всех возможных остатков от 
деления  на 
p
: 


1
,
...
,
1
,
0

p
.  Множество 


1
,
...
,
1
,
0

p
  также  называется  полной 
системой наименьших неотрицательных вычетов по модулю 
p
. 
Основная часть 
Один  из  методов  выполнения  арифметических  операций  над  длинными 
целыми числами основан на простых положениях теории чисел. Представление 
чисел в СОК позволяет заменить операции с большими числами на операции с 
малыми  числами,  которые  представлены  в  виде  остатков  от  деления  больших 
чисел на заранее выбранные взаимно-простые модули 
n
p
p
p
,
...
,
,
2
1
. Пусть 


1
1
mod p
A


, 


2
2
mod p
A


, … , 


n
n
p
A
mod


.   
 
(1) 
Тогда  целому  числу 
A
  можно  поставить  в  соответствие  кортеж 


n



,
...
,
,
2
1
 
наименьших  неотрицательных  вычетов  по  одному  из 

388 
 
 
соответствующих  классов.  Данное  соответствие  будет  взаимно  однозначным, 
пока 
n
p
p
p
A
...
2
1

,  в  силу  Китайской  Теоремы  об  Остатках  (КТО).  Кортеж 


n



,
...
,
,
2
1
  можно рассматривать  как  один  из  способов представления  целого 
числа 
A
 в ЭВМ – модулярное представление или представление в СОК. 
Основным  преимуществом  такого  представления  является  тот  факт,  что 
выполнение  операций  сложения,  вычитания  и  умножения  реализуется  очень 
просто, по формулам: 

 





n
n
B
A






,
...
,
,
...
,
,
2
1
2
1
 








n
n
n
p
p
p
mod
,
...
,
mod
,
mod
2
2
2
1
1
1










; 
 
(2) 

 





n
n
B
A






,
...
,
,
...
,
,
2
1
2
1
 








n
n
n
p
p
p
mod
,
...
,
mod
,
mod
2
2
2
1
1
1










.   
(3) 
Эти  операции  носят  название  модульных,  так  как  для  их  выполнения  в 
СОК  достаточно  одного  такта  обработки  численных  значений,  причем  эта 
обработка  происходит  параллельно и  значения  информации  в  каждом разряде 
не зависит от других разрядов. 
Основной недостаток модулярного представления чисел состоит в том, что 
трудно  упорядочить  множество  всех  целочисленных  кортежей  длины 
n
  так, 
чтобы этот порядок соответствовал естественному порядку на множестве целых 
чисел.  Как  следствие  этого  факта,  трудно  установить,  является  ли  кортеж 


n



,
...
,
,
2
1
  большим  (меньшим),  чем 


n



,
...
,
2
1
.  Трудно  также  проверить, 
возникло  ли  переполнение  допустимого  диапазона  чисел 
n
p
p
p
P
...
2
1

  в 
результате  выполнения  операций  сложения  или  умножения,  но  еще  труднее 
выполнить  операцию  деления.  Эти,  и  некоторые  другие  операции,  носят 
название немодульных, так как для их выполнения требуется знание о величине 
числа в целом, которое называется позиционной характеристикой числа. 
Модель целочисленной модулярной арифметики можно задать следующей 
сигнатурой 
НО
МО
P
i
p
,
,
,


,  где: 
P
  -  полная  система    вычетов  по  модулю 

389 
 
 
полного  динамического  диапазона, 


i
p
  -  вычет  чисел  по  модулю 
i
p
,  МО  – 
множество  модульных  операций,  к  которым  относятся  арифметические 
операции  сложения,  вычитания,  умножения  и  деления  нацело  или  умножение 
на  обратный  элемент,  НО  –  множество  немодульных  операций,  к  которым 
относятся расширения база СОК, деления, масштабирования и другие.  
Немодульные  операции  обусловлены  знанием  числового  значения 
модулярной  величины,  которая  определенным  образом  связана  со  значениями 
компонент  модулярного  представления.  Эти  операции  являются  медленными, 
что снижает эффективность применения модулярной алгебры. Для реализации 
немодульных  операций  используются  специальные  функционалы,  которые 
определяют  количественные  характеристики  отношения  порядка  над 
множеством  модулярных  векторов.  Одно  из  устоявшихся  названий 
функционалов  – позиционная характеристика (ПХ) модулярной величины или 
числовой  величины  в  модулярном  коде.  В  основе  алгоритмов  выполнения 
немодульных  операций  лежат  методы  вычисления  ПХ,  сложность  которых 
непосредственно  влияет  на  скорость  выполнения  немодульных  операций  в 
модулярной  алгебре.  Поиск  эффективных  и  универсальных  ПХ  важен  для 
теоретических основ модулярных вычислительных структур и вычислительных 
средств на их основе. 

жүктеу/скачать 7,09 Mb.

Достарыңызбен бөлісу: