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

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

Макарова А.В. 1 Саркисов А.Б. 1 Калмыков И.А. 1 Жолобов П.А. 1 Ефременков И.Д. 1
1 ФГАОУ ВО «Северо-Кавказский федеральный университет»
Стремление обеспечить цифровую обработку сигналов с максимальной производительности способствовали применению параллельных методов вычислений. Для обеспечения максимальной производительности ортогональных преобразований сигналов используют параллельную обработку на самых различных уровнях. В настоящее время внимание уделяется вопросам обеспечения параллельных вычислений на уровне операций. Для решения данной проблемы предлагается использовать непозиционные модулярные коды. Однако эти коды позволяют не только повышать производительность спецпроцессоров, но способны обнаруживать и корректировать ошибки, возникающие из-за отказов и сбоев оборудования. Разработка эффективного метода поиска местоположения и глубины ошибки на основе использования модулярных кодах является актуальной задачей. В работе рассмотрены вопросы применения полиномиальной системы классов вычетов для коррекции ошибок с использованием процедуры расширения системы оснований.
модулярные коды
коррекция ошибок
полиномиальная система классов вычетов
1. Калмыков И.А., Тимошенко Л.И., Лободин М.В., Сагдеев А.К. Реализация ортогональных преобразований сигналов в расширенных полях Галуа // Современные наукоемкие технологии. 2006. № 4. С. 54-57.
2. Калмыков И.А., Саркисов А.Б., Макарова А.В. Технология цифровой обработки сигналов с использованием модулярного полиномиального кода // Известия ЮФУ. Технические науки. 2013. № 12 (149). С. 234-241.
3. Калмыков И.А., Саркисов А.Б., Яковлева Е.М., Калмыков М.И. Модулярный систолический процессор цифровой обработки сигналов с реконфигурируемой структурой // Вестник Северо-Кавказского федерального университета. – Ставрополь. – 2013. – № 2. – С. 30-35.
4. Саркисов А.Б., Калмыков М.И., Яковлева Е.М. Параллельные технологии цифровой обработки сигналов на основе непозиционных модулярных кодов // XIII Всероссийская научная конференция «Высокопроизводительные параллельные вычисления на кластерных системах» – Нижний Новгород. – 2013. – С. 236-241.
5. Червяков Н.И., Калмыков И.А., Щелкунова Ю.О., Шилов А.А., Бережной В.В Нейросетевая реализация в ПСКВ операций ЦОС повышенной разрядности // Нейрокомпьютеры: разработка, применение. 2004. № 5-6. С. 94-100.
6. Чипига А.Ф., Калмыков И.А Структура нейронной сети для реализации цифровой обработки сигналов повышенной разрядности // Наука. Инновации. Технологии. 2004. Т. 38. С. 46.
7. Kalmykov I.A., Katkov K.A., Timoshenko L.I., Dunin A.V., Gish T.A. Application of modular technologies in the large-scale analysis of signals // Journal of Theoretical and Applied Information Technology. 2015. Т. 80. № 3. С. 391-400.
8. Mohan P.V. Residue Number Systems. Algorithms and Architectures. Springer. 2002.

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

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

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

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

Особенность ПСКВ заключается в том, что независимость обработки информации по основаниям ПСКВ позволяет не только повысить скорость и точность обработки, но также и обеспечить обнаружение и коррекцию ошибок в процессе функционирования вычислительного устройства [1-3]. В ПСКВ в качестве оснований системы используются неприводимые полиномы mak01.wmf, где mak02.wmf, любой полином A(x), удовлетворяющий

mak03.wmf (1)

где mak04.wmf – рабочий диапазон системы, mak05.wmf – степень полинома, можно однозначно представить в виде набора остатков

mak06.wmf (2)

где mak07.wmf

Для обнаружения и исправления однократных ошибок в модулярном коде полинома mak08.wmf вводят два контрольных основания mak09.wmf и mak10.wmf, которые удовлетворяют условию

mak11.wmf (3)

Наличие двух контрольных основания позволяет определить местоположение ошибки и ее глубину в коде ПСКВ [4, 5, 8].

Возникновение ошибки в непозиционной кодовой конструкции A(z) переводит ее из подмножества разрешенных комбинаций в подмножество запрещенных. Согласно китайской теореме об остатках (КТО) значение ошибочного полинома A*(z) равно

mak12.wmf (4)

где mak13.wmf – полный диапазон кода ПСКВ; mak14.wmf – глубина ошибки по j-ому основанию кода ПСКВ; Bj(z) – ортогональный базис j-го основания ПСКВ; j = 1, 2, …, n + 2.

Анализ выражения (4) показывает, что местоположение ошибочного полинома A*(z) относительно рабочего диапазона Pраб(z) определяется величиной второго слагаемого.

Рассмотрим алгоритм перевода из безизбыточного полиномиального модулярного кода в позиционный код согласно КТО, имеем

mak15.wmf (5)

где mak16.wmf – ортогональный базис; mi(z) – вес ортогонального базиса; mak17.wmf; rA(z) – ранг кода ПСКВ.

Воспользуемся определением ортогональных базисов, тогда выражение (5) можно представить в виде

mak18.wmf (6)

Умножение остатка на вес ортогонального базиса выполняется по модулю pi(z), что позволяют отказаться от вычисления ранга rA(z) при использовании китайской теоремы об остатках при переводе к позиционному коду.

Чтобы осуществить поиск и коррекцию ошибки в коде ПСКВ на основе расширения системы оснований необходимо, используя остатки по рабочим основаниям (α1(z),…, αn(z)), вычислитель остатки по контрольным основаниям pn + 1(z) и pn + 2(z).

Тогда для вычисления первого контрольного остатка mak19.wmf по основанию mak20.wmf используем следующее выражение

mak21.wmf (7)

Второй контрольный остаток mak22.wmf по основанию mak23.wmf определяется

mak24.wmf (8)

После этого вычисленные остатки mak25.wmf и mak26.wmf складываются по модулю два с остатками mak27.wmf и mak28.wmf, которые входят в состав комбинации кода ПСКВ mak29.wmf. В результате получается синдром ошибки, который определит местоположение и глубину ошибки в коде

mak30.wmf (9)

Если полученный синдром будет равен нулю, то это означает, что код ПСКВ не содержит ошибки. Если синдром будет отличен от нуля, то это будет означать, что код ПСКВ содержит ошибку.

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

Пусть задано поле Галуа mak31.wmf, в котором определены информационные основания mak32.wmf, mak33.wmf, mak34.wmf, расширяем систему оснований за счет введения двух контрольных оснований mak35.wmf и mak36.wmf. В этом случае

mak37.wmf.

При этом полный диапазон составляет mak38.wmf Тогда контрольный полином

mak39.wmf

Определим значения рабочих оснований mak40.wmf и mak41.wmf:

mak42.wmf

Тогда веса ортогональных базисов равны mak43.wmf mak44.wmf mak45.wmf

Следовательно, ортогональные базисы mak46.wmf соответственно равны

mak47.wmf

mak48.wmf

mak49.wmf

Воспользуемся полином mak50.wmf, который представляется как mak51.wmf.

Расширяем систему оснований за счет mak52.wmf и mak53.wmf. Первое основания расширения системы mak54.wmf. Вычислим значения mak55.wmf. Тогда имеем

mak56.wmf

mak57.wmf,

mak58.wmf.

Определим произведения

mak59.wmf,

mak60.wmf,

mak61.wmf

Подставляем полученные значения в выражение (7) и получаем

mak62.wmf

Результат расширения по основанию mak63.wmf получили остаток mak64.wmf. Проведем проверку и определим остаток исходного полинома

mak65.wmf.

Второе основание расширения

mak66.wmf.

Вычислим значения mak67.wmf. Тогда имеем

mak68.wmf,

mak69.wmf,

mak70.wmf.

Определим произведение

mak71.wmf.

Они соответственно равны

mak72.wmf,

mak73.wmf,

mak74.wmf

Подставляем полученные значения в выражение (8)

mak75.wmf.

Результат расширения по основанию mak76.wmf – остаток mak77.wmf. Проведем проверку и определим остаток исходного полинома

mak78.wmf.

Таким образом, расширенная комбинация избыточного кода ПСКВ будет иметь вид

mak79.wmf.

Если на вход устройства и обнаружения ошибки, использующего разработанный алгоритм расширения системы оснований, поступит mak80.wmf, то синдром ошибки будет равен

mak81.wmf

Так как синдром ошибки равен нулю, то код ПСКВ не содержит ошибки.

Рассмотрим ситуацию, когда проверяемая комбинация ПСКВ содержит ошибку по первому основанию и ее глубина равна mak82.wmf. Тогда значение первого остатка равно mak83.wmf. Ошибочная комбинация модулярного кода ПСКВ имеет вид

mak84.wmf.

Определим mak85.wmf, для данной ошибочной комбинации кода ПСКВ. Получаем

mak86.wmf,

mak87.wmf

mak88.wmf.

Вычислим первый контрольный остаток, подставив значения в выражение (7)

mak89.wmf

Результатом расширения по модулю mak90.wmf является mak91.wmf.

Вычислим второй контрольный остаток, подставив значения в выражение (8)

mak92.wmf.

Результатом расширения по модулю mak93.wmf является остаток mak94.wmf.

Выполним проверку комбинации путем вычисления синдрома ошибки, имеем

mak95.wmf

Проверяемая комбинация содержит ошибки, так как синдром ошибки отличен от нуля. В таблице приведены значения глубины и местоположения ошибки в коде ПСКВ по рабочим основаниям и соответствующего им синдрома ошибки S1(z) и S2(z). Данные в таблице приведены в шестнадцатеричной системе счисления. По значению синдрома ошибки определяем, что ошибка произошла по первому основанию p1(z) = z + 1, а ее глубина равна mak96.wmf. Значит, вектор ошибки будет равен mak97.wmf.

Для коррекции ошибки необходимо данный вектор ошибки сложить с ошибочной комбинацией кода ПСКВ. Имеем

mak98.wmf

Глубина и местоположение ошибки в коде ПСКВ по S1(z) и S2(z)

Основание

Глубина

S1(z)

S2(z)

p1(z) = z + 1

1

B

2

p2(z) = z2 + z + 1

1

7

9

2

A

7

3

D

E

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

1

E

D

2

1

F

3

F

2

4

6

B

5

8

6

6

7

4

7

9

9

8

C

5

9

2

8

A

D

A

B

3

7

C

A

E

D

4

3

E

B

1

F

5

C

Если ошибка произойдет по первому контрольному основанию p4(z) = z4 + z3 + 1, то значение первой составной синдрома S1(z) будет показывать глубину ошибки, а значение S2(z) будет равняться нулю.

Если ошибка произойдет по второму контрольному основанию p5(z) = z4 + z + 1, то значение второй составной синдрома S2(z) будет показывать глубину ошибки, а значение первой составляющей синдрома S1(z) будет равняться нулю.

Заключение

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


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

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

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

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