Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,916

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

Заворотинский Д.И. 1 Солодкин И.Г. 1 Гапочкин А.В. 1 Калмыков М.И. 1
1 ФГАОУ ВПО «Северо-Кавказский федеральный университет»
Современные избыточные коды используются для проведения операции поиска и коррекции ошибок, которые могут возникать в результате воздействия помехи на кодовую комбинацию или при отказе элементов кодера-декодера. Особое место среди таких кодов занимают модулярные коды, которые относят к непозиционным кодам. Так как модулярные коды являются арифметическими, то их применяют для коррекции ошибок, которые возникают в процессе функционирования вычислительных систем. В основу алгоритмов определения ошибки в модулярных кодах используют позиционные характеристики. Одной из таких характеристик является интервальный номер числа. В работе представлен усовершенствованный алгоритм вычисления данной характеристики.
модулярные коды
избыточные коды
система остаточных классов
обнаружение и коррекция ошибок
позиционные характеристики
интервальный номер числа
след числа
1. Бережной В.В., Калмыков И.А., Червяков Н.И., Щелкунова Ю.О., Шилов А.А., Нейросетевая реализация в полиномиальной системе классов вычетов операций ЦОС повышенной разрядности // Нейрокомпьютеры: разработка и применение. – 2004. – № 5-6. – С. 94.
2. Калмыков И.А., Калмыков М.И. Структурная организация параллельного спецпроцессора цифровой обработки сигналов, использующего модулярные код // Теория и техника радиосвязи. – 2014. – № 2. – С. 60–66.
3. Калмыков И.А., Стрекалов Ю.А., Щелкунова Ю.О., Кихтенко О.А., Барильская А.В. Технология нелинейного шифрования данных в высокоскоростных сетях связи // Инфокоммуникационные технологии. – 2010. – Т. 8, № 2. – С. 14–22
4. Калмыков И.А., Воронкин Р.А., Резеньков Д.Н., Емарлукова Я.В., Фалько А.А. Генетические алгоритмы в системах цифровой обработки сигналов // Нейрокомпьютеры: разработка и применение. – 2011. – № 5. – С. 20–27.
5. Калмыков И.А., Саркисов А.Б., Макарова А.В. Технология цифровой обработки сигналов с использованием модулярного полиномиального кода // Известия Южного федерального университета. Технические науки. – 2013. – № 12 (149). – С. 234–241.
6. Чипига А.Ф., Калмыков И.А. Структура нейронной сети для реализации цифровой обработки сигналов повышенной разрядности // Наука. Инновации. Технологии. – 2004. – Т. 38. – С. 46.
7. Калмыков И.А., Резеньков Д.Н., Горденко Д.В., Саркисов А.Б. Методы и алгоритмы реконфигурации непозиционных вычислительных структур для обеспечения отказоустойчивости спецпроцессоров. – Ставрополь, 2014.
8. Калмыков И.А., Калмыков М.И. Новая технология, повышающая корректирующие способности модулярных кодов // Теория и техника радиосвязи. – 2014. – № 3. – С. 5–12.
9. Калмыков И.А., Зиновьев А.В., Емарлукова Я.В. Высокоскоростные систолические отказоустойчивые процессоры цифровой обработки сигналов для инфотелекоммуникационных систем // Инфокоммуникационные технологии. – 2009. – Т. 7, №2. – С. 31–47.
10. Калмыков И.А., Саркисов А.Б., Яковлева Е.М., Калмыков М.И. Модулярный систолический процессор цифровой обработки сигналов с реконфигурируемой структурой // Вестник Северо-Кавказского федерального университета. – 2013. – № 2 (35). – С. 30–35.

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

Постановка и решение задачи исследования. Использование параллельных алгоритмов вычислений в современных информационных технологиях обусловлено высокими требованиями, предъявляемыми к скорости обработки информации. Чтобы обеспечить данное требование в ряде работ предлагается использовать модулярные коды [1–6]. Модулярные коды относятся к арифметическим кодам, которые применяются для выполнения алгоритмов, в которых используются модулярные операции – сложение, вычитание и умножение по модулю.

Так в системе остаточных классов (СОК) числа, которые принадлежат рабочему диапазону можно однозначно представить в виде набора остатков

zav01.wmf, (1)

где zav02.wmf. – рабочий диапазон; А < Pраб; zav03.wmf; i = 1,2,…,k.

Тогда для суммы, разности и произведения двух чисел А и В, имеющих соответственно модулярные коды (a1,a2,…,ak) и (b1, b2,…, bk) справедливы соотношения при i = 1,…,k

zav06.wmf, (2)

где ● – операции сложения, вычитания и умножения по модулю.

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

zav07.wmf, (3)

где zav08.wmf – остаток по модулю отсчета входной последовательности zav09.wmf; zav10.wmf – остаток по модулю спектрального отсчета сигнала zav11.wmf; β – поворачивающий коэффициент дискретного преобразования Фурье.

При этом обратное ортогональное преобразование сигнала определяется

zav12.wmf, (4)

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

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

Для построения избыточных модулярных кодов необходимо в данный набор оснований ввести дополнительные модули. В работе [7] показано, что для обнаружения и коррекции однократной ошибки необходимо ввести два контрольных основания, которые будут удовлетворять требованию

zav13.wmf. (5)

В этом случае происходит расширение диапазона системы остаточных классов.

zav14.wmf. (6)

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

zav15.wmf, (7)

то она считается разрешенной.

При этом при возникновении ошибки такая комбинация переносится в область запрещенных комбинаций. Это связано с тем, что однократная ошибка переводит разрешенную комбинацию А = (a1,a2,…,ak+2) в комбинацию zav16.wmf, где zav17.wmf – искаженный остаток, ∆ai – глубина ошибки. В результате воздействия ошибки искаженное число выходит за пределы рабочего диапазона и переносится в диапазон полный. Значит если определить местоположение искаженной комбинации zav18.wmf, то можно однозначно выявить модуль, по которому произошла ошибка, а также определить ее величину ∆ai.

Чтобы провести эту процедуру в непозиционных модулярных кодах применяют различные позиционные характеристики [7–10]. Среди множества позиционных характеристик особое место занимает интервальный номер. Эта позиционная характеристика имеет достаточно простой физический смысл, так как задается следующим выражением

zav19.wmf. (8)

Как показывает анализ равенства (8), для вычисления позиционной характеристики необходимо выполнить операцию деления, которая не является модульной операцией. Следовательно, чтобы реализовать данную немодульную операцию необходимо выполнить совокупность модульных операций в непозиционном коде. Так в работе [5] показан алгоритм, с помощью которого можно осуществить обнаружение и исправление ошибки в коде классов вычетов, используя данную позиционную характеристику.

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

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

Если в упорядоченной системе СОК, содержащей k информационных и два избыточных оснований, в результате нулевизации модулярного кода числа A получен позиционная характеристика след

zav20.wmf, (9)

то интервал, в который будет перенесена ошибочная комбинация СОК числа A*, будет вычисляться

zav21.wmf, (10)

где zav22.wmf; Bj – ортогональный базис по j-му основанию СОК;

zav23.wmf – ранг в безизбыточной системы; zav24.wmf.

Чтобы доказать правильность усовершенствованного алгоритма вычисления интервального номера числа покажем, в начале, что если хотя бы один след числа zav25.wmf, где j =k+1, k+2, то код СОК числа A является запрещенным. Другими словами, код СОК содержит ошибку. Для этого проведем замену произведения двух контрольных оснований СОК одним составным основанием zav27.wmf.

Тогда исходный код СОК числа A, который задается в виде (k + 2) – мерного вектора, (a1,a2,…,ak+1, ak+2), примет вид

zav28.wmf, (11)

где zav29.wmf.

Известно, что если в коде СОК числа A, принадлежащего рабочему диапазону СОК, произошла ошибка, то результатом операции параллельной нулевизации кода числа A* с использованием псевдоортогональных базисов Aik будет отличный от нуля след числа

zav30.wmf, (12)

где zav31.wmf zav32.wmf;

zav33.wmf – ортогональный базис безизбыточной системы оснований СОК.

С другой стороны, согласно китайской теореме об остатках (КТО)

zav34.wmf, (13)

где zav35.wmf; Мj – ортогональный базис системы модулярного кода с контрольными основаниями pk+1 и pk+r.

Очевидно, что если след отличен от нуля zav36.wmf, то хотя бы один из остатков zav37.wmf должен отличаться от нуля.

Таким образом, если в результате параллельной нулевизации кода СОК числа A* и с помощью псевдоортогональных базисов будет получен след zav38.wmf, то данный полином содержит ошибку.

Покажем теперь, что величина интервального номера l кода СОК числа A будет определяться согласно алгоритма (10).

Пусть в результате процедуры нулевизации кода СОК искаженного числа A* получим след zav39.wmf отличный от нуля. Известно

zav40.wmf, (14)

где zav41.wmf; ∆ai – глубина ошибки по i-ому основанию.

При этом zav42.wmf = γ = (0,0,0,...,0,γk + 1, γk + 2).

Тогда на основании выражения (14) имеем

zav43.wmf. (15)

Согласно КТО и с учетом ai = 0, i = 1,2,…,k, имеем

zav44.wmf. (16)

Подставляем (16) в равенство (15) получаем

zav45.wmf. (17)

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

zav46.wmf, (18)

где zav47.wmf.

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

Выводы

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


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

Заворотинский Д.И., Солодкин И.Г., Гапочкин А.В., Калмыков М.И. УСОВЕРШЕНСТВОВАНИЕ АЛГОРИТМА ВЫЧИСЛЕНИЯ ИНТЕРВАЛЬНОГО НОМЕРА, ИСПОЛЬЗУЕМОГО ДЛЯ КОРРЕКЦИИ ОШИБОК В МОДУЛЯРНОМ КОДЕ // Современные наукоемкие технологии. – 2014. – № 11. – С. 12-15;
URL: http://top-technologies.ru/ru/article/view?id=34763 (дата обращения: 01.04.2020).

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

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