Научный журнал
Международный журнал прикладных и фундаментальных исследований
ISSN 1996-3955
ИФ РИНЦ = 0,564

РАЗРАБОТКА МЕТОДА КОРРЕКЦИИ ОШИБКИ НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ МНОГОВЕРСИОННОЙ ИЗБЫТОЧНОСТИ МОДУЛЯРНЫХ КОДОВ

Белов С.П. 1 Саркисов А.Б. 2 Абакумова А.М. 2 Калмыков И.А. 2 Ряднов С.А. 3
1 ФГАОУ ВО «Белгородский государственный национальный исследовательский университет»
2 ФГАОУ ВО «Северо-Кавказский федеральный университет»
3 Филиал Московского государственного университета приборостроения и информатики в городе Ставрополе
Стремление обеспечить обработку сигналов с максимальной производительности способствовали применению параллельных методов вычислений. Такое распараллеливание может происходить на различных уровнях. Особое внимание в настоящее время уделяется вопросам обеспечения параллельных вычислений на уровне операций. Для решения данной проблемы предлагается использовать непозиционные модулярные коды. Однако такие коды позволяют не только повышать производительность спецпроцессоров, но способны обнаруживать и корректировать ошибки, возникающие из-за отказов и сбоев оборудования. Разработка эффективного метода поиска местоположения и глубины ошибки на основе использования многоверсионной избыточности в модулярных кодах является актуальной задачей. В работе рассмотрены вопросы применения обобщенной полиадической системы для коррекции ошибок.
модулярные коды
параллельные вычисления
коррекция ошибок
полиномиальная система классов вычетов
позиционные характеристики
обобщенная полиадическая система
1. Барсагаев А.А., Калмыков М.И. Алгоритмы обнаружения и коррекции ошибок в модулярных полиномиальных кодах // Международный журнал экспериментального образования. – 2014. – № 3 (часть 1). – С. 103–107.
2. Калмыков И.А., Саркисов А.Б., Калмыков М.И. Модулярный систолический процессор цифровой обработки сигналов с реконфигурируемой структурой // Вестник Северо-Кавказского федерального университета. – 2013. – № 2 (35). – С. 30–35.
3. Калмыков И.А., Зиновьев А.В., Гахов В.Р. Применение систолических ортогональных преобразований в полиномиальной системе классов вычетов для повышения эффективности цифровой обработки сигналов // Инфокоммуникационные технологии. – 2010. – Т. 8. № 3. – С. 4–11.
4. Калмыков И.А. Математические модели нейросетевых отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе классов вычетов. – М.: ФИЗМАТЛИТ, – 2005. – 276 с.
5. Мартиросян А.Г., Калмыков М.И. Основные методы обеспечения отказоустойчивости специализированных вычислительных устройств цифровой обработки сигналов // Современные наукоемкие технологии. – 2014. – № 3. – С. 62–68.
6. Саркисов А. Б., Калмыков И. А., Степанова Е.П., Топоркова Е.В. Устройство для коррекции ошибок в полиномиальной системе классов вычетов // Патент России № 2560823. 2015. Бюл. № 25.
7. Червяков Н.И., Калмыков И.А., Щелкунова Ю.О. Математическая модель нейронной сети для коррекции ошибок в непозиционном коде расширенного поля Галуа // Нейрокомпьютеры: разработка, применение. – 2003. – № 8-9. – С. 10–16.
8. Червяков Н.И. Нейрокомпьютеры в остаточных классах/ Н.И. Червяков, А.В. Шапошников, П.А. Сахнюк, А.Н. Макоха // – М.: Радиотехника, 2003. – 272 с.
9. Kalmykov I.A., Katkov K.A., Naumenko D.O., Sarkisov A.B., Makarova A.V. Parallel modular technologies in digital signal processing // Life Science Journal – 2014. 11 (11s) – Р. 435 – 438. http://www.lifesciencesite.com.
10. Mohan P.V. Residue Number Systems. Algorithms and Architectures. Springer. 2002.

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

Цель исследования

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

Поэтому целью работы является разработка метода коррекции ошибок, который на основе многоверсионной избыточности, позволил бы повысить отказоустойчивость спецпроцессоров ЦОС при меньших схемных затратах чем метод маскирования отказов «2 из 3».

Материалы и методы исследования

В коде ПСКВ в качестве оснований непозиционной системы используются неприводимые полиномы pi(z) – неприводимые полиномы поля GF(2); i = 1,…, k. Данный код относится к непозиционным кодам классов вычетов. В кодах ПСКВ берется сначала позиционный двоичный код А = 1101…12. Затем он представляется в полиномиальной форме в виде

bel01.wmf, (1)

где bel02.wmf – элемент поля GF(2).

Используя полученную полиномиальную форму, определяются соответствующие остатки, полученные при делении полинома A(z) на основания ПСКВ. В результате получается набор остатков

bel03.wmf, (2)

где bel04.wmf.

Произведение оснований кода ПСКВ позволяет определить рабочий диапазон

bel05.wmf. (3)

Проведенный анализ работ [2, 7, 9] показал, что наиболее эффективно выполняются в кодах ПСКВ модульные операции. К этим операциям относятся – сложение, вычитание и умножение по модулю. Пусть даны два полинома bel06.wmf и bel07.wmf. Так как сравнения по одному и тому же модулю можно почленно складывать, то для модульных операций имеем

bel08.wmf, (4)

bel09.wmf, (5)

bel10.wmf. (6)

где + – операция суммирования по модулю р; bel11.wmf – операция вычитания по модулю р.

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

bel12.wmf. (7)

В результате применения контрольных оснований ПСКВ происходит расширение рабочего диапазона до полного диапазона

bel13.wmf. (8)

Так как ошибка переводит правильный bel14.wmf в ошибочный полином bel15.wmf, лежащий вне рабочего диапазона, то, зная местоположение искаженного полинома A*(z), можно однозначно определить модуль pi(z), по которому произошла ошибка, а также ее глубину.

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

Так коды ПСКВ являются непозиционными, то для обнаружения местоположения и глубины ошибки используют позиционные характеристики (ПХ). Все множество методов коррекции ошибок можно разделить на две группы, в зависимости от используемой многоверсионной избыточности кодов ПСКВ. К первой относятся методы и алгоритмы контроля и коррекции ошибок непозиционного кода ПСКВ, базирующиеся на вычисление позиционных характеристик во временной области [1, 4, 5]. Что касается процедур второй группы, то они реализуются в частотной области [4]. Рассмотрим методы обнаружения и коррекции ошибок, работающие во временной области. В настоящее время широкое применение нашли такие методы вычисления ПХ как, интервальный номер, нормированный след, параллельная нулевизация, вычисление старших коэффициентов обобщенной полиадической системы. Наличие такой многоверсионной избыточности модулярных кодов позволяет разработчикам обоснованно выбирать соответствующий метод коррекции ошибок, исходя из заданных требований к вычислительным системам [8, 10].

Анализ известных методов контроля и коррекции ошибки в модульных избыточных кодах показал, что довольно часто поиск и исправление ошибок производится с помощью перевода чисел из модулярного кода в обобщенную полиадическую систему (ОПС) [4, 6]. Данные алгоритмы, основаны на вычисление коэффициентов промежуточной полиадической системы, в котором А(z) изображается в виде

bel16a.wmf

bel16b.wmf (9)

Если bel17.wmf, служат одновременно основаниями модульной системы и ОПС, тогда интервалы изменения цифр разрядов с одинаковыми номерами совпадут. Следовательно, если обеспечить соответствие между основаниями ОПС и основаниями системы классов вычетов, то справедливо

bel18.wmf. (10)

Исходя из условия, что bel19.wmf, выражение (9) имеет вид

bel20.wmf (11)

Тогда на основании (11) можно сделать вывод о возможности применения коэффициентов ОПС для процедур поиска и локализации ошибки. Данный вывод основывается на том, что, начиная с k + 1-го коэффициента ОПС, в слагаемых равенства (11) в качестве сомножителя используется Рраб(z). Таким образом, если полином А(z) принадлежит рабочему диапазону Рраб(z), то старшие коэффициенты ОПС должны bel21.wmf bel22.wmf bel23.wmf. В противном случае полином А(z) содержит ошибку и находится вне Рраб(z) кода ПСКВ.

Особенностью разработанного методы состоит в том, что наиболее трудоемкий этап перевода остаток – коэффициенты ОПС осуществляется путем параллельно-конвейерного вычисления коэффициентов с использованием китайской теоремы об остатках [6]. Тогда

bel24a.wmf

bel24b.wmf, (13)

где Bi(z) – ортогональный базис i-го основания.

Представив ортогональные базисы в виде коэффициентов ОПС, получаем

bel25.wmf, (14)

где bel26.wmf – коэффициенты ОПС j-го ортогонального базиса.

Тогда, проведя умножение вычетов αi на соответствующие коэффициенты ОПС помодульно и поразрядно, при этом, учитывая превышение модуля pi как перенос единицы при суммировании результата, коэффициенты ОПС могут быть найдены выражения

bel27.wmf, (15)

где ηi–1 – переполнение, полученное при суммировании по модулю pi–1.

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

bel28.wmf, (16)

где i = 1, 2, .., n – количество оснований кода ПСКВ.

Результаты исследования и их обсуждение

Рассмотрим реализацию разработанного метода при минимальной избыточности кода ПСКВ. В системе ПСКВ с рабочими основаниями bel29.wmf, bel30.wmf и контрольным основанием – bel31.wmf вычислим значение рабочего диапазона

bel32.wmf.

Определим значение ортогональных базисов и представим их в ОПС.

bel33.wmf;

bel34.wmf;

bel35.wmf.

Переведем в ОПС код ПСКВ bel36.wmf. Умножим остатки на ортогональные базисы, представленные в ОПС помодульно, учитывая количество превышения модуля. Результаты показаны в табл. 1.

Таблица 1

Вычисление коэффициентов ОПС

Модули

p1(z) = z4 + z + 1

p2(z) = z4 + z3 + 1

p3(z) = z4 + z3 + z2 + z+1

Код ПСКВ

Произведение

Произведение

Превышение р2(х)

Результат

a1(z) = 0

0

0

0

0

a2(z) = z2 + 1

0

z3 + z2

z + 1

1 + (z + 1) = z

a3(z) = z3 + z2 + 1

0

0

0

z

ОПС

v1(z) = 0

v2(z) = z3 + z2

v3(z) = 0

Так как старший коэффициент v3 = 0, то код ПСКВ не содержит ошибку.

Пусть произошла ошибка по первому основанию. Тогда код ПСКВ bel37.wmf. Вычислим коэффициенты ОПС. Результаты вычисления коэффициентов ОПС показаны в табл. 2.

Таблица 2

Вычисление коэффициентов ОПС при наличии ошибки

Модули

p1(z) = z4 + z + 1

p2(z) = z4 + z3 + 1

p3(z) = z4 + z3 + z2 + z + 1

Код ПСКВ

Произведение

Произведение

Превышение р2(х)

Результат

a1(z) = 0

1

0

0

0

a2(z) = z2 + 1

0

z3 + z2

z + 1

1 + (z + 1) = z

a3(z) = z3 + z2 + 1

0

0

0

z

ОПС

v1(z) = 1

v2(z) = z2 + z + 1

v3(z) = 1

Таблица 3

Зависимость коэффициентов ОПС от ошибки для поля GF(24)

Величина ошибки

Коэффициенты ОПС

a4(z)

a5(z)

Δα1 = 1

z3

z3 + z2 + z

Δα2 = 1

z3 + z + 1

z3 + z2

Δα2 = z

z3 + z2 + z

z3 + z

Δα3 = 1

z2 + 1

z3 + z2 + z

Δα3 = z

z3 + z

z3 + z2 + z + 1

Δα3 = z2

z3 + z2

z3 + z2

Δα3 = z3

1

z3 + z

Δα4 = 1

z2 + z

z3 + z2 + z

Δα4 = z

z3 + z2

z3 + z2 + z + 1

Δα4 = z2

1

z3 + z2

Δα4 = z3

z

z3 + z + 1

Δα5 = 1

0

z

Δα5 = z

0

z2

Δα5 = z2

0

z3

Δα5 = z3

0

z + 1

Так как старший коэффициент v3 = 1, то код ПСКВ содержит ошибку.

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

– рабочие основания bel38.wmf, bel39.wmf; bel40.wmf;

– контрольные основания

bel41.wmf и bel42.wmf.

При этом значение bel44.wmf заранее учитывает количество превышение модуля pi(z) как перенос единицы при суммировании результата.

Для исследования процессов поиска и локализации ошибки в непозиционном коде полиномиальной системы классов вычетов полей GF(23), GF(24), GF(25) с использованием коэффициентов ОПС были разработаны математические модели. Проведенные исследования показали, что использование многоверсионной избыточности в методы вычисления коэффициентов ОПС для коррекции ошибок, позволяет сократить схемные затраты в 1,19 раз при обработке 16-разрядных данных по сравнению с методов маскирования отказов «2 из 3». При чем, с увеличением разрядности увеличивается эффективность схемной реализации.

Заключение

В статье проведена разработка нового метода использования многоверсионной избыточности модулярных кодов для коррекции ошибок на основе вычисления старших коэффициентов ОПС. Представлены результаты применения данного метода в кодах ПСКВ с одним и двумя контрольными основаниями. Показано, что использование минимальной избыточности позволяет обнаруживать факт ошибки. Проведенные исследования показали, что при использовании двух контрольных оснований код ПСКВ исправляет 100 % однократных ошибок, требуя при этом при обработке 16-разрядных данных в 1,19 раз меньше схемных затрата чем метод маскирования отказов «2 из 3».

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 16-37-50032.


Библиографическая ссылка

Белов С.П., Саркисов А.Б., Абакумова А.М., Калмыков И.А., Ряднов С.А. РАЗРАБОТКА МЕТОДА КОРРЕКЦИИ ОШИБКИ НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ МНОГОВЕРСИОННОЙ ИЗБЫТОЧНОСТИ МОДУЛЯРНЫХ КОДОВ // Международный журнал прикладных и фундаментальных исследований. – 2016. – № 11-2. – С. 198-202;
URL: https://applied-research.ru/ru/article/view?id=10464 (дата обращения: 29.09.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074