Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

THE USE OF MODULAR CODES TO BUILD FAULT-TOLERANT INFORMATION SYSTEMS

Kalmykov I.A. 1 Katkov K.A. 1 Stepanova E.P. 1 Kalmykov M.I. 1 Toporkova E.V. 1
1 North Caucasus Federal University
The purpose of research is to increase the resiliency of high-information systems, particularly systems, digital signal processing (DSP). Achieving this goal is possible due to parallelization. It is shown that for signal processing in real time is necessary to use algebraic structures with rings and field properties, in particular the residue number system (RNS) and polynomial residue number system (PRNS). Application of new modular technology allows DSP tasks by parallelizing processing at the level of an independent low-bit data operations not only increase the speed of computing, but also to ensure receipt of the correct result under the effect of interference in the transmission and equipment failure. This paper presents a new algorithm for error correction on the basis of calculation of a truncated convolution. The use of this algorithm allows the joint venture to develop DSP, capable of maintaining a usable state when a failure due to the reconfiguration of the structure.
fault tolerance information systems
digital signal processing
residue number system
polynomial system of residue classes
error correction
positional characteristics
1. Gapochkin A.V, Kalmykov M.I., Vasilev P.S. Obnaruzhenie i korrekcija oshibki na osnove vychislenija intervalnogo nomera koda klassov vychetov // Sovremennye naukojom-kie tehnologii. 2014. no. 6. рр. 9–14.
2. Kalmykov I.A., Zinovev A.V., Emarlukova Ja.V. Vysokoskorostnye sistolicheskie otkazoustojchivye processory cifrovoj obrabotki signalov dlja infokommunikacionnyh sistem // Infokommunikacionnye tehnologii. 2009. T. 7, no. 2, рр. 31–37.
3. Kalmykov I.A., Sarkisov A.B., Jakovleva E.M. Moduljarnyj sistolicheskij processor cifrovoj obrabotki signalov s rekonfiguriruemoj s6trukturoj // Vestnik Severo-Kavkazskogo federalnogo universiteta. 2013. Vyp. 2. рр. 30–34.
4. Kalmykov I.A., Kalmykov M.I. Novaja tehnologija, povyshajushhaja korrektirujushhie sposobnosti moduljarnyh kodov // Teorija i tehnika radiosvjazi. Voronezh. OAO «Koncern «Sozvezdie» 2014. no. 3. рр. 5–13.
5. Strizhkov N.S., Kalmykov M.I. Algoritm preobrazovanija iz moduljarnogo koda v poliadicheskuju sistemu osnovanija dlja sistem obnaruzhenija i korrekcii oshibok // Mezh-dunarodnyj zhurnal jeksperimentalnogo obrazovanija. RAE 2014. no. 3. рр. 127–131.
6. Chervjakov N.I., Kalmykov I.A., Galkina V.A., Shhelkunova Ju.O., Shilov A.A Jele-menty kompjuternoj matematiki i nejronoinfromatiki / pod red. N.I. Chervjakova. M.: Fizmatlit, 2003. 216 р.
7. Katkov K.A., Kalmykov I.A. Application of Parallel Technologies in Navigation Man-agement under the Conditions of Artificial Ionospheric Disturbances. World Applied Sciences Journal. 2013. no. 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., and. Sasi S. RRNS-convolutional encoded concatenated code for OFDM based wireless communication. In Networks, 2008. 16th IEEE Inter-national 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

Заключение

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