Научный журнал

Международный журнал прикладных и фундаментальных исследований

ISSN 1996-3955

ИФ РИНЦ = 0,593

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Макарова А.В. 1 Саркисов А.Б. 1 Калмыков И.А. 1 Жолобов П.А. 1 Ефременков И.Д. 1

---

1 ФГАОУ ВО «Северо-Кавказский федеральный университет»

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

Статья в формате PDF

1833 KB

модулярные коды

коррекция ошибок

полиномиальная система классов вычетов

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]. В ПСКВ в качестве оснований системы используются неприводимые полиномы , где , любой полином A(x), удовлетворяющий

(1)

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

(2)

где

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

(3)

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

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

(4)

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

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

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

(5)

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

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

(6)

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

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

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

(7)

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

(8)

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

(9)

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

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

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

.

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

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

Тогда веса ортогональных базисов равны

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

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

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

,

.

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

,

,

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

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

.

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

.

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

,

,

.

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

.

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

,

,

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

.

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

.

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

.

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

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

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

.

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

,

.

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

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

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

.

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

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

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

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

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

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

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

Заключение

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

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