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

Современные наукоемкие технологии

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

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

Черномазов С.А. 1 Мартиросян А.Г. 1 Гапочкин А.В. 1 Калмыков М.И. 1

---

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

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

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

880 KB

коды классов вычетов

система остаточных классов

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

обнаружение и коррекция ошибок

расширение системы оснований

1. Чипига А.Ф., Калмыков И.А. Структура нейронной сети для реализации цифровой обработки сигналов повышенной разрядности // Наука. Инновации. Технологии. – 2004. – Т. 38. – С. 46.

2. Калмыков И.А., Резеньков Д.Н., Горденко Д.В., Саркисов А.Б. Методы и алгоритмы реконфигурации непозиционных вычислительных структур для обеспечения отказоустойчивости спецпроцессоров. – Ставрополь, 2014.

3. Калмыков И.А., Калмыков М.И. Структурная организация параллельного спецпроцессора цифровой обработки сигналов, использующего модулярные код // Теория и техника радиосвязи. – 2014. – № 2. – С. 60–66.

4. Калмыков И.А., Воронкин Р.А., Резеньков Д.Н., Емарлукова Я.В., Фалько А.А. Генетические алгоритмы в системах цифровой обработки сигналов // Нейрокомпьютеры: разработка и применение. – 2011. – № 5. – С. 20–27.

5. Калмыков И.А., Саркисов А.Б., Макарова А.В. Технология цифровой обработки сигналов с использованием модулярного полиномиального кода // Известия Южного федерального университета. Технические науки. – 2013. – № 12 (149). – С. 234–241.

6. Мартиросян А.Г., Калмыков М.И. Основные методы обеспечения отказоустойчивости специализированных вычислительных устройств цифровой обработки сигналов Современные наукоемкие технологии. – 2014. – № 3. – С. 62–67.

7. Калмыков И.А., Зиновьев А.В., Емарлукова Я.В. Высокоскоростные систолические отказоустойчивые процессоры цифровой обработки сигналов для инфотелекоммуникационных систем // Инфокоммуникационные технологии. – 2009. – Т. 7, № 2. – С. 31–47.

8. Калмыков И.А., Саркисов А.Б., Яковлева Е.М., Калмыков М.И. Модулярный систолический процессор цифровой обработки сигналов с реконфигурируемой структурой // Вестник Северо-Кавказского федерального университета. – 2013. – № 2 (35). – С. 30–35.

9. Барсагаев А.А., Калмыков М.И. Алгоритм обнаружения и коррекции ошибок в модулярных полиномиальных кодах // Международный журнал экспериментального образования. – 2014. – № 3-1. – С. 103–106.

10. Стрижков Н.С., Калмыков М.И. Алгоритм преобразования из модулярного кода в полиадическую систему оснований для систем обнаружения и коррекции ошибок // Международный журнал экспериментального образования. – 2014. – № 3-1. – С. 127–131.

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

Основная часть

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

, (1)

где – остаток, полученный при делении числа А на основание pi; i = 1,…,n; HOД(pi, pj), .

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

, (2)

где k – количество информационных рабочих оснований СОК; k < n.

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

, (3)

В работах [4–8], показано, что, если при переводе из модулярного кода в позиционный код, полученная величина числа (полинома) не превышает значение рабочего диапазона, то модулярный код не содержит ошибки.

В противном случае – модулярный код является запрещенным и содержит ошибку, как минимум в одном остатке.

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

В данном алгоритме берется исходное число A = (a1,…,ak, ak + 1, ak + 2), которое имеет два контрольных основания, удовлетворяющих условию

, (4)

затем используя k информационных остатков a1, a2,…,ak, вычисляют остатки по контрольным основаниям . После этого необходимо определить величину синдрома ошибки по этим двум контрольным основаниям

(5)

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

Если кодовая комбинация СОК является запрещенной, то вычисленные значения остатков по контрольным основаниям не совпадет с исходными величинами остатков избыточных оснований ak + 1 и ak + 2. При этом по величине синдрома ошибки можно однозначно определить ошибочное основание, а также величину ошибки.

Рассмотрим пример использования алгоритма расширения оснований. В данном алгоритме синдром ошибки будет определяться выражением

, (6)

где ; Ra – ранг числа A в безизбыточной СОК; ; j = k + 1, k + 2.

Как отмечалось ранее, если в системе остаточных классов с рабочими p1, p2,…, pk и контрольными основаниями pk+1, pk+2, удовлетворяющих условию (4), модулярная кодовая конструкция A = (a1, a2,…, ak + 2) не содержит ошибок, если выполняется условие

, (7)

Пусть задана система остаточных классов с рабочими основаниями р1 = 2, р2 = 3, р3 = 5. Тогда рабочий диапазон данной системы СОК будет равен Pраб = 30. В качестве контрольных оснований выберем основания р4 = 7 и р5 = 11. В этом случае полный диапазон такой системы Pполн = 2310.

Вычислим ортогональные базисы полной СОК. В данной полной системе основания ортогональные базисы равны

Представим ортогональные базисы, чтобы реализовать алгоритм (6)

Проведем расчет по модулю р4 = 7

; ; ;

Определим величину

.

Проведем расчет по модулю р5 = 11

; ; ;

Определим величину

.

Пусть имеем число А = (0, 2, 2, 2, 2) = 2. Вычислим значение остатков по контрольным основаниям для данного числа, используя разработанный алгоритм.

Вычислим значение ранг в безизбыточной системы, определяемые основаниями р1=2, р2 = 3, р3 = 5.

Тогда вычисленное значение первого остатка по контрольному основанию р4 = 7 для данной комбинации

Вычисленное значение первого остатка по контрольному основанию р5 = 11 для данной комбинации

Теперь определим величину синдрома ошибки согласно (7)

В результате синдром ошибки равен нулю, то это соответствует тому, что комбинация СОК А = (0, 2, 2, 2, 2) не содержит ошибки.

Пусть ошибка произошла по первому основанию и ее глубина равна ∆a1 = 1. Тогда модулярный код имеет вид А* = (1, 2, 2, 2, 2) = 2. Вычислим значение синдрома ошибки для данного числа, используя разработанный алгоритм.

Вычислим значение ранг в безизбыточной системы, определяемые основаниями р1 = 2, р2 = 3, р3 = 5.

Тогда вычисленное значение первого остатка по контрольному основанию р4 = 7 для данной комбинации

Вычисленное значение первого остатка по контрольному основанию р5 = 11 для данной комбинации

Теперь определим величину синдрома ошибки согласно (7)

В результате синдром ошибки отличен от нуля, то это соответствует тому, что комбинация СОК А* = (1, 2, 2, 2, 2) содержит ошибку.

Так как ошибочное число определяется из условия

, (8)

то для получения нулевого синдрома ошибки необходимо из полученного синдрома вычесть значения , где i = 1, 2, …, k; j = k + 1, k + 2.

Так значение безизбытоного ортогонального базиса , то значения коррекции будут равны

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

В таблице приведены значения ошибок по основаниям модулярного кода и соответствующие им номера интервалов.

Распределение однократных ошибок кода СОК

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

Структура устройства обнаружения и коррекции ошибки на основе расширения системы оснований

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

. (9)

Данный вектор записывается в регистр 1. На вход первого 3 блока вычисления синдрома с выходов регистра 1 подается

(10)

c образованием на его выходе сигнала

δ₁=(α _k+1-α* _k+1))mod рk+1. (11)

При этом

α* _k+1=λ⁽¹⁾₁α₁+ λ ⁽¹⁾₂α₂+…+ λ⁽¹⁾_kα_k , (12)

где λ(1)i – константы системы СОК.

На входы блока 4 вычисления синдрома с выходов регистра 2 подается

. (13)

С образованием на выходе сигнала

δ2=(α k+2+ α *k+2)mod pk+2. (14)

При этом

α*k+2= λ(2)1α1+ λ(2)2α2+…+ λ(2)kαk , (15)

где λ(2)i – константы системы.

Величины δ1 и δ2 в двоичном виде поступают на входы блока 5 памяти и выбирают оттуда соответствующую константу ошибки. Эта константа ошибки поступает в сумматор 6, где суммируется с искаженным A*, представленном в непозиционном виде поданным из регистра 1. Исправленное представление A с выхода сумматора 6 подается на выход 7 устройства.

Выводы

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

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