Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

INCREASE CORRECTING CAPABILITY MODULAR POLYNOMIAL CODE

Strizhkov N.S. 1 Kalmykov M.I. 1
1 North-caucasian federal university
Parallel computing have been widely applied in the fields of digital signal processing (DSP ) . However, it reduces the probability of failure of a computing device. To improve the reliability of special processor DSP is proposed to use the redundant modular polynomial codes. In this paper, we propose an algorithm that allows to increase the ability of these corrective code designs polynomial system of residue classes ( PSKV). Thanks to this modular polynomial algorithm code having two control base, capable of correcting all errors twofold. This property is achieved by addressing collisions that occur when the detection and correction of errors
residues
polynomial system of residue classes
the coefficients of the generalized polyadic notations
detection and correction of errors

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

Постановка задачи исследований

В настоящее время модулярные арифметические модулярные системы нашли широкое применение в различных сферах, связанных с информационными технологиями. В работах [1-4] доказана целесообразность использования модулярных кодов при реализации методов цифровой обработки сигналов. Широкое применение модулярные алгебраические системы нашли в сфере обеспечения защиты информации от несанкционированного доступа (НСД). Так в работах [5, 6] показана возможность применения модулярной арифметики в криптографических системах, использующих полиномиальную систему классов вычетов. В работе [7] рассмотрены вопросы использования модулярной псевдослучайной функции повышенной эффективности в электронных коммерческих системах. Использование модулярных алгебраических структур позволяет обеспечить требуемый уровень защиты информации от НСД.

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

В полиномиальной системе классов вычетов в качестве оснований системы используются неприводимые полиномы striz1.wmf, где striz2.wmf. В этом случае любой полином striz3.wmf, удовлетворяющий условию

striz4.wmf (1)

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

striz7.wmf (2)

где striz8.wmf

Для реализации процесса обнаружения и исправления ошибок в модулярном коде полинома striz9.wmf вводят избыточность. С этой целью выбирается одно контрольное основание striz10.wmf, удовлетворяющее условию

striz11.wmf (3)

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

striz12.wmf (4)

striz13.wmf (5)

где striz14.wmf – полиномиальная форма i-го порядкового номера, striz15.wmf– суммирование по модулю два, можно однозначно исправить однократную ошибку.

Под однократной ошибкой понимается искажение одного разряда в кодовой комбинации, представленной равенством (2).

При работе данное устройство обрабатывает n информационных остатка striz16.wmf и два контрольных остатка striz17.wmf и striz18.wmf.

Для обнаружения ошибки в переданной кодовой комбинации вычисляются значения

striz19.wmf (6)

striz20.wmf (7)

Полученные значения striz21.wmfи striz22.wmf используются для вычисления синдрома ошибки согласно

striz23.wmf (8)

striz24.wmf (9)

где striz25.wmf – суммирование по модулю два.

Если синдром ошибки striz26.wmf и striz27.wmf, то данная комбинация не содержит ошибки. В противном случае, когда striz28.wmf и striz29.wmf, принятая комбинация является запрещенной, т.е. ошибочной. По величине striz30.wmf и striz31.wmf можно провести коррекцию однократной ошибки.

В табл. 1 приведены значения синдромов striz32.wmf и striz33.wmf, а также соответствующие им константы ошибки для рабочих оснований striz34.wmf striz35.wmfstriz36.wmf и контрольного основания striz37.wmf

Таблица 1

Синдромы ошибки в коде ПСКВ

striz38.wmf

striz39.wmf

константа ошибки ∆конст

0

0

(0, 0, 0, 0, 0)

1

1

(1, 0, 0, 0, 0)

1

z

(0, 1, 0, 0, 0)

z

z2

(0, z, 0, 0, 0)

1

z+1

(0, 0, 1, 0, 0)

z

striz42.wmf

(0, 0, z, 0, 0)

z2

striz44.wmf

(0, 0, z2, 0, 0)

z3

striz46.wmf

(0, 0, z3, 0, 0)

Однако, используя два контрольных остатка striz48.wmf и striz49.wmf, можно исправить и двукратные ошибки, т.е. ошибки, произошедшие в двух разрядах комбинации striz50.wmf одновременно.

В табл. 2 приведены значения синдромов ошибки striz51.wmf и striz52.wmf при всех возможных двукратных ошибках по рабочим основаниям striz53.wmf striz54.wmf striz55.wmf, в которых произошла коллизия, т.е. совпадение.

Таблица 2

Коллизии при двукратных ошибках в коде ПСКВ

п/п

Отказавший разряд 1-го основания

Отказавший разряд 2-го основания

δ1

δ2

∆ кор

1

striz56.wmf

striz57.wmf

striz58.wmf

striz59.wmf

коллизия

2

striz60.wmf

striz61.wmf

0

z

коллизия

3

striz62.wmf

striz63.wmf

striz64.wmf

striz65.wmf

коллизия

4

striz66.wmf

striz67.wmf

striz68.wmf

striz69.wmf

коллизия

5

striz70.wmf

striz71.wmf

0

z

коллизия

6

striz72.wmf

striz73.wmf

striz74.wmf

striz75.wmf

коллизия

Проведенный анализ табл. 2 показывает, что совпадение пар значений striz76.wmf и striz77.wmf не произошло, за исключением совпадения строк 1 и 4, 2 и 5, 3 и 6. Это означает, что устройство способно корректировать двукратные ошибки за исключением отмеченных совпадающих строк.

Чтобы обеспечить процедуру коррекции результата в условиях коллизии (совпадение синдрома striz78.wmf и striz79.wmf) в устройство введены блок управления, второй блок памяти, блок устранения коллизии.

Функциональная схема устройства представлена на рис. 1. Она включает: регистр 1, вход 2, блок устранения коллизии 3, модуль вычисления синдрома ошибки 4, содержащий первый блок вычисления ошибки 5, второй блок вычисления синдрома ошибки 6, блок управления 7, первый блок памяти 8, второй блок памяти 9, сумматор 10, выход устройства 11.

str1.wmf

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

Устройство работает следующим образом: на вход 2 устройства поступает модулярный код полинома striz80.wmf. Контролируемая комбинация записывается в регистр 1. На первый вход блока 3 устранения коллизии с первого выхода регистра 1 поступает значение striz81.wmf Если коллизия не обнаружена блоком управления 7, то на второй вход блока 3 поступает управляющая комбинация y=0. Одновременно с выхода второго блока 9 памяти на третий вход блока 3 устранения коллизии поступает четырехразрядная комбинация striz82.wmfБлагодаря этому входная комбинация не изменяется и с выхода блока 3 устранения коллизии подается на первый вход первого блока 5 и второго блока 6 вычисления синдрома ошибки, входящих в состав модуля 4 вычисления синдрома ошибки, а также на первый вход сумматора 10.

На второй вход первого блока 5 вычисления синдрома ошибки подается с второго выхода регистра 1 значение первого контрольного остатка striz83.wmf. Блок 5 реализует выражение (8).

На второй вход второго блока 6 вычисления синдрома ошибки подается с третьего выхода регистра 1 значение второго контрольного остатка striz84.wmf. Данный блок 6 реализует выражение (9).

Величины striz85.wmf и striz86.wmf в двоичном коде поступают на соответствующие входы первого 8 и второго 9 блоков памяти и блок управления 7.

Если коллизия отсутствует, а это соответствует условию, когда контролируемая комбинация

striz87.wmf

не содержит ошибки или имеет однократную ошибку или двухкратную, за исключением когда ошибка одновременно произошла в комбинациях striz88.wmf и striz89.wmf striz90.wmf и striz91.wmf striz92.wmf и striz93.wmfstriz94.wmf и striz95.wmf striz96.wmf и striz97.wmfstriz98.wmf и striz99.wmf, где striz100.wmf – j-й разряд i-го канала, то с выхода блока управления 7 поступает управляющий сигнал striz101.wmf на второй вход блока 3 устранения коллизии.

Если однократная ошибка произошла в нулевом разряде первого основания, в striz102.wmf т. е. когда значение синдрома ошибки striz103.wmf и striz104.wmf, то с выхода второго блока 9 памяти снимается комбинация x=1000 которая подается на третий вход блока 3 устранения коллизии.

Если однократная ошибка произошла в первом разряде второго основания striz105.wmf, т. е. когда значение синдрома ошибки striz106.wmf и striz107.wmf то с выхода второго блока 9 памяти подается на третий вход блока 3 устранения коллизии комбинация x=0100.

Если однократная ошибка произошла в нулевом разряде третьего основания striz108.wmf, то есть когда значение синдрома ошибки striz109.wmf и striz110.wmf то с выхода второго блока 9 памяти подается на третий вход блока 3 устранения коллизии комбинация striz111.wmf

Если однократная ошибка произошла в первом разряде третьего основания striz112.wmf, т. е. когда значение синдрома ошибки striz113.wmf и striz114.wmf то с выхода второго блока 9 памяти подается на третий вход блока 3 устранения коллизии комбинация striz115.wmf

В зависимости от величины striz116.wmf и striz117.wmf с выхода первого блока 8 памяти выдается соответствующая константа ошибки ∆конс. Это значение поступает в сумматор 10, где суммируется со значением комбинации striz118.wmf, которая подается в параллельном коде на первый, третий и четвертый входы сумматора 10. Исправленное значение A(z) с выхода сумматора 10 подается на выход 11 устройства.

При возникновении коллизии, это соответствует ситуации, когда с выходов блоков 5 и 6 вычисления синдрома ошибки подаются значения striz119.wmf и striz120.wmf striz121.wmf и striz122.wmf striz123.wmf и striz124.wmf то с выхода блока управления 7 на второй вход блока 3 поступает управляющий сигнал striz125.wmf

В результате контролируемая комбинация модулярного кода striz126.wmfбудет содержать только однократную ошибку. Эта ошибка будет обнаружена в модуле 4 вычисления синдрома по значениям striz127.wmf и striz128.wmf. Эти значения подаются на входы первого блока 8 памяти, с выхода которого выдается ∆кор, что позволяет исправить вторую ошибку в контролируемой комбинации.

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

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