Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

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

Калмыков И.А. 1 Катков К.А. 1 Степанова Е.П. 1 Калмыков М.И. 1 Топоркова Е.В. 1
1 ФГАОУ ВПО «Северо-Кавказский федеральный университет»
Целью исследований является повышение отказоустойчивости высокоскоростных информационных систем, в частности систем цифровой обработки сигналов (ЦОС). Достижение данной цели возможно за счет распараллеливания вычислений. В работе показано, что для обеспечения обработки сигналов в реальном масштабе времени необходимо использовать алгебраические структуры, обладающие свойством кольца и поля, в частности систему остаточных классов (СОК) и полиномиальную систему классов вычетов (ПСКВ). Применение новых модулярных технологий в задачах ЦОС позволяет за счет распараллеливания на уровне операций независимой обработки малоразрядных данных не только увеличить скорость вычислений, но и обеспечить получение корректного результата в условиях воздействия помех при передаче и отказа оборудования. В работе представлен новый алгоритм коррекции ошибок на основе вычисления усеченной свертки. Применение данного алгоритма позволяет разрабатывать СП ЦОС, способных сохранять работоспособное состояние при возникновении отказов за счет реконфигурации структуры.
отказоустойчивые информационные системы
цифровая обработка сигналов
система остаточных классов
полиномиальная система классов вычетов
коррекция ошибки
позиционные характеристики
1. Гапочкин А.В, Калмыков М.И., Васильев П.С. Обнаружение и коррекция ошибки на основе вычисления интервального номера кода классов вычетов // Современные наукоёмкие технологии. – 2014. – № 6. – С. 9–14.
2. Калмыков И.А., Зиновьев А.В., Емарлукова Я.В. Высокоскоростные систолические отказоустойчивые процессоры цифровой обработки сигналов для инфокоммуникационных систем // Инфокоммуникационные технологии. – 2009. – Т. 7, № 2, – С. 31–37.
3. Калмыков И.А., Саркисов А.Б., Яковлева Е.М. Модулярный систолический процессор цифровой обработки сигналов с реконфигурируемой с6труктурой // Вестник Северо-Кавказского федерального университета. – 2013. – Вып. 2. – С. 30–34.
4. Калмыков И.А., Калмыков М.И. Новая технология, повышающая корректирующие способности модулярных кодов // Теория и техника радиосвязи. Воронеж. ОАО «Концерн «Созвездие» – 2014. – № 3. – С. 5–13.
5. Стрижков Н.С., Калмыков М.И. Алгоритм преобразования из модулярного кода в полиадическую систему основания для систем обнаружения и коррекции ошибок // Международный журнал экспериментального образования. РАЕ – 2014. – № 3. – С. 127–131.
6. Червяков Н.И., Калмыков И.А., Галкина В.А., Щелкунова Ю.О., Шилов А.А Элементы компьютерной математики и нейроноинфроматики / под ред. Н.И. Червякова. – М.: Физматлит, 2003. – 216 с.
7. Katkov K.A., Kalmykov I.A. Application of Parallel Technologies in Navigation Management under the Conditions of Artificial Ionospheric Disturbances. World Applied Sciences Journal. – 2013. – № 26 (1). – Р. 108–113.
8. Rohde & Schwarz. R&S FSQ-K96 OFDM Vector Signal Analysis with the R&S FSQ Signal Analyzer. Product Brochure, Vol. 1.00, March 2008.
9. Shahana T., Jose B., James R., Jacob K., Sasi S. RRNS-convolutional encoded concatenated code for ofdm based wireless communication. – In Networks, 2008. – 16th IEEE International Conference on, dec. 2008. – Р. 1–6.
10. Yong Soo Cho, Jaekwon Kim, Won, Young, Chung G., 2010. Kang MIMO-OFDM Wireless Communications with MATLAB. WILEY.2010.

Современные инфокоммуникационные системы широко используют системы на кристалле (СнК), которые на основе применения математической модели ортогонального частотного мультиплексирования (OFDM) позволяют обеспечить высокую помехоустойчивость, передачу информации в реальном масштабе времени, устойчивость к многолучевому распространению радиоволн и ряд других преимуществ. Однако использование математической модели цифровой обработки сигналов (ЦОС) на основе быстрых преобразований Фурье (БПФ) в позиционной системе счисления не позволяет в полной мере использовать весь потенциал сигнального процессора. Обеспечить предельную производительность спецпроцессора ЦОС можно за счет использования параллельных методов вычислений. Но усиливающаяся тенденция к использованию параллельных вычислений, с другой стороны, приводит к снижению надежности работы вычислительной системы. Решить данное противоречие можно за счет использования алгебраических структур корректирующих непозиционных модулярных кодов. Параллельная и независимая обработка малоразрядных остатков, их функциональная равнозначность позволяют не только повысить скорость вычислений, но и обеспечить СП свойство устойчивости к отказам.

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

Основная часть. Цель исследования

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

В последние годы наблюдается повышенный интерес к применению перспективных видов сигнально-кодовых конструкций OFDM (Orthogonal Frequency Division Multiplexing). При этом в основе метода OFDM положено быстрое преобразование Фурье (БПФ). Использование математической модели цифровой обработки сигналов на основе БПФ позволяет эффективно бороться с многолучевостью, которая является характерной чертой радиосвязи. В качестве достоинств OFDM можно выделить достаточно высокий коэффициент использования выделенного частотного спектра и отсутствие межсимвольной интерференции [8–10].

Однако наряду с достоинствами системы передачи и обработки с OFDM, использующие математическую модель ортогонального частотного мультиплексирования на основе БПФ, имеют ряд проблемных сторон. К ним можно отнести:

– недостаточно высокая скорость ортогонального преобразования сигнала;

– увеличение сложности модема OFDM, что приводит к снижению его надежности.

Устранить данные недостатки можно за счет обеспечения свойства устойчивости к отказам во время функционирования СП ЦОС.

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

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

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

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

В системе остаточных классов целое число A представляется в виде совокупности остатков, A = (a1, a2, ..., an), где A ≡ ai modpi; i = 1, 2, …, n, полученных путем его деления на попарно взаимно простые модули pi [6–7]. Основным достоинством СОК является высокая скорость выполнения модульных операций, к которым относятся сложение, вычитание и умножение. Тогда, используя СОК, можно реализовать дискретное преобразование Фурье

Kalmykov01.wmf (1)

В ПСКВ полиномиальная форма числа представляется в виде остатков от деления, только в качестве оснований здесь применяются неприводимые полиномы. В работах [1–3] показано, что применение системы ПСКВ, в которой в качестве оснований используются минимальные многочлены p1(z), p2(z), ..., pn(z), позволяет осуществлять ДПФ в виде

Kalmykov02.wmf (2)

где xi(j) ≡ x(j) mod pi(z); Kalmykov03.wmfXi(l) ≡ X(l) mod pi(z); b – первообразный корень; x(j) – входная последовательность сигнала; X(l) – спектральные составляющие входного сигнала; d = 2v – 1 – размерность входного вектора.

Анализ выражений (1)–(2) показывает, что использование модулярных кодов позволяет операции сложения, вычитания и умножения свести к операциям над остатками. При этом эти операции проходят параллельно и независимо в каждом вычислительном тракте.

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

Для коррекции ошибок с помощью модулярных кодов вводят r избыточных оснований pn+1(z), ..., pn+r(z), для которых справедливо

deg p1(z) ≤...≤ deg pn–1(z) ≤ deg pn(z) ≤ deg pn+1(z) ≤...≤ deg pn+r(z), (3)

где deg pi(z) – степень неприводимого полинома pi(z); n – количество рабочих оснований.

Код ПСКВ считается разрешенным, если он принадлежит рабочему диапазону

Kalmykov04.wmf (4)

Введение избыточных модулей приводит к появлению полного диапазона кода

Kalmykov05.wmf (5)

Ошибка, преобразуя правильную комбинацию A = (α1(z), α2(z), ..., αn+r(z)) в комбинацию Kalmykov06.wmf, осуществляет перевод кода за пределы рабочего диапазона, где αi ≡ A mod pi; Kalmykov07.wmf – искаженный остаток СОК; Δαi – глубина ошибки.

Так как модулярные коды относятся к непозиционным кодам, то для коррекции ошибки в этих кодах используются позиционные характеристики (ПХ). Они показывают расположение ошибочной кодовой комбинации модулярного кода относительно рабочего диапазона системы. В работе [1] приведен алгоритм и схемная реализация вычисления интервального номера, физический смысл которой определяется как Kalmykov08.wmf. Если код ПСКВ не содержит ошибки, т.е. deg A(z) < deg Pраб(z), то значение интервального номера равно нулю, т.е. l(z) = 0. При возникновении ошибки в коде ПСКВ – l(z) ≠ 0. В работе [5] в качестве ПХ используются старшие коэффициенты обобщенной полиадической системы. В работе [4] предлагается для коррекции ошибок применять алгоритм расширения оснований ПСКВ. Однако, отмеченные выше алгоритмы требуют значительных схемных и временных затрат. Уменьшить их можно за счет использования ПХ – усеченной свертки.

Для перевода из ПСКВ в позиционную систему счисления (ПСС) используют

Kalmykov09.wmf (6)

где Bi(z) – ортогональный базис; Pi(z) = P(z)/pi(z); mi(z) – вес базиса; Bi(z) ≡ 1 mod pi(z).

Пусть ошибка произошла по j-му основанию ПСКВ, а ее глубина равна Δαj(z). Произведем перевод ошибочного кода ПСКВ в ПСС

Kalmykov10.wmf (7)

Анализ (7) показывает, что выход за пределы рабочего диапазона Pраб(z) определяется вторым слагаемым. Для выполнения коррекции необходимо вычислить для каждого основания ПСКВ величину Pi(z). Затем вычислим степень рабочего диапазона

Kalmykov11.wmf (8)

В полиномах Pi(z) отбрасываем разряды, степень которых будет меньше значения

L – deg pi(z) = Li. (9)

Тогда остаются полиномы

Kalmykov12.wmf (10)

где aj = {0, 1} элементы поля Галуа GF(2).

Если код A(z) = (α1(z), α2(z), ..., αn+1(z)) не содержит ошибки, то его степень deg A(z) < deg Pраб(z) = L. В этом случае свертка произведений остатков αi(z), веса базиса mi(z) и констант Mi(z) должна быть равна нулю

Kalmykov13.wmf (11)

Если код Kalmykov14.wmf содержит ошибку, то свертка равна

Kalmykov15.wmf (12)

Используя равенство (11), получаем

Kalmykov16.wmf (13)

По величине S можно однозначно определить местоположение ошибки и ее глубину.

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

Пусть рабочими основаниями выбраны многочлены p1(z) = z+ 1; p2(z) = z3 + z+ 1, а контрольным – p3(z) = z3 + z2+ 1. Тогда рабочий диапазон

Kalmykov17.wmf

Значит, L = deg Pраб(z) = 4. Вычислим константы

P1(z) = z6 + z5 + z4 + z3 + z2 + z + 1;

P2(z) = z4 + z2 + z + 1; P3(z) = z4 + z3 + z2 + 1.

Вычислим значения весов первого ортогонального базиса. Для этого определяем

Kalmykov18.wmf

Значит, m1(z) = 1, так как δ1(z)m1(z) ≡ 1 mod pi(z). Вычислим вес базиса B2(z). Получаем

Kalmykov19.wmf

Так как δ2(z) = 1, тогда m2(z) = 1. Для базиса B3(z) получаем

Kalmykov20.wmf

Так как значение δ3(z) ≠ 1, то вес B3(z) равен m3(z) = z2 + 1. Это определяется из условия

Kalmykov21.wmf (14)

Воспользуемся выражением (10) и вычислим константы Mi(z). Так как deg p1(z) = 1, то имеем

M1(z) = z6 + z5 + z4.

Так как deg p2(z) = 3, то имеем

M2(z) = z4 + z2.

Так как deg p3(z) = 3, то имеем

M3(z) = z4 + z3 + z3.

Пусть на вход блока коррекции подается код ПСКВ

A(z) = z3 + z3 + z + 1 = (0, z2, z).

Так как deg A(z) < deg Pраб(z) = 4, то ПСКВ не содержит ошибки. Произведем вычисление свертки. Определим произведения αi(z) и mi(z). Получаем

Kalmykov22.wmf Kalmykov23.wmf

Kalmykov24.wmf

Определим значения δi(z)Mi(z). Получаем

δ1(z)M1(z) = 0(z6 + z5 + z4) = 0;

δ2(z)M2(z) = z2(z4 + z2) = z6 + z4;

δ3(z)M3(z) = (z2 + z + 1)(z4 + z3 + z2) = z6 + z4 + z2.

Оставляем только степени, которые не меньше L = 4. Получаем усеченные значения K1 = 0; K2 = z6 + z4; K3 = z6 + z4. Складываем по модулю два усеченных значения

S = K1 + K2 + K3 = 0+ (z6 + z4) + (z6 + z4) = 0.

Так как свертка S = 0, то код ПСКВ не содержит ошибки.

Пусть ошибка произошла по первому основанию, а ее глубина равна Δα1(z) = 1. Тогда

Kalmykov25.wmf

Значит код ПСКВ равен

A*(z) = (1, z2, z) = z6 + z5 + z4.

Тогда имеем

Kalmykov26.wmf

Kalmykov27.wmf

Kalmykov28.wmf

Определяем произведение δi(z)Mi(z). Получаем

δ1(z)M1(z) = z6 + z5 + z4;

δ2(z)M2(z) = z2(z4 + z2) = z6 + z4;

δ3(z)M3(z) = z6 + z4 + z2.

Тогда усеченные значения

K1(δ1(z)M1(z)) = z6 + z5 + z4;

K2(δ2(z)M2(z)) = z6 + z4;

K3(δ3(z)M3(z)) = z6 + z4.

Тогда свертка равна

S = K1 + K2 + K3 = (z6 + z5 + z4) + (z6 + z4) +  (z6 + z4) = z6 + z5 + z4.

Так как S ≠ 0, то код ПСКВ содержит ошибку.

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

После преобразования из кода ПСКВ в код ПСС проведем исправление ошибки

A(z) = A*(z) + Δ(z) = (z6 + z5 + z4) +  (z6 + z5 + z4 + z3 + z2 + z + 1) = z3 + z2 + z + 1.

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

Значения усеченных сверток S

Основания

Ошибка Δαi(z)

Свертка S

Корректирующее значение Δ

p1(z) = z + 1

1

z6 + z5 + z4

z6 + z5 + z4 + z3 + z2 + z + 1

p2(z) = z3 + z + 1

1

z

z2

z4

z5

z6 + z4

z4 + z2 + z + 1

z5 + z3 + z2 + z

z6 + z4 + z3 + z2

Заключение

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


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

Калмыков И.А., Катков К.А., Степанова Е.П., Калмыков М.И., Топоркова Е.В. ПРИМЕНЕНИЕ МОДУЛЯРНЫХ КОДОВ ДЛЯ ПОСТРОЕНИЯ ОТКАЗОУСТОЙЧИВЫХ ИНФОРМАЦИОННЫХ СИСТЕМ // Фундаментальные исследования. – 2016. – № 10-1. – С. 42-47;
URL: http://www.fundamental-research.ru/ru/article/view?id=40806 (дата обращения: 21.10.2019).

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

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