Численный метод параллельного вычисления позиционной характеристики для коррекции ошибок в полиалфавитном полиномиальном модулярном коде

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

Однако широкое использование параллельных вычислительных систем способствовало появлению следующего противоречия. С одной стороны, посто- янный рост требований к скоростным характеристикам ВС приводит к необходимости организации параллельных вычислений, а с другой стороны, при этом увеличивается частота возникновения отказов и возрастает время простоя процессоров, вызванного трудностью отыскания и ликвидации неисправности. Для решения данного противоречия была разработана теория построения корректирующих ПКСОК [2, 5, 6]. В отличие от помехоустойчивых кодов избыточные ПКСОК способны обнаруживать и исправлять ошибки, которые возникают в процессе вычислений. Для этого применяются позиционные характеристики (ПХ). Так как ошибка, возникшая по одному основанию, не может оказать влияние на другие основания, то обнаружение и коррекция ошибки производится в конце всех вычислений.

Однако несмотря на то, что принципы построения данных кодов подобны, теория обнаружения и коррекции ошибок в ППМК на основе использования ПХ находится в стадии становления и еще далека от своего окончательного решения. Актуальность решения данной задачи определяется тем, что разработка численного метода вычисления ПХ в ППМК позволит осуществлять коррекцию результатов линейного и нелинейного биективного преобразований, реализуемых в блочных SPN-шифрах. Благодаря этому будут устранены последствия атак «на основе сбоя», проводимых в шифрах AES и Кузнечик. Поэтому разработка численного метода вычисления ПХ для коррекции ошибок в полиалфавитном полиномиальном модулярном коде является актуальной задачей.

1.    Арифметические принципы получения полиалфавитных модулярных кодов

Арифметические коды бывают позиционные и непозиционные. Среди последних особое место занимают ПМК, в которых базовые элементы кода генерируются на основе разных базисов (алфавитов) [7]. Началом развития теории построения ПМК считается работа чешского ученого Миро Валах [1], в которой для повышения скорости вычислений было предложено кодировать целые числа в кольце вычетов, которое было получено с помощью взаимно простых чисел. Базовые принципы модулярной арифметики были рассмотрены советскими учеными И.Я. Акушским и Д.И. Юдицким в [2]. Вопросы повышения скорости выполнения немодульных операций нашли отражение в работе В.М. Амербаева [3]. Повышение надежности вычислительных систем за счет применения модулярных кодов показано в работе В.А. Торгашова [6]. Современные исследователи [7– 10] решают задачи по применению ПМК в цифровой обработке сигналов, фильтрации, криптографии, нейронных сетях. Основная цель данных исследований – повысить скорость вычислений и отказоустойчивость ВС за счет применения ПМК.

Если в качестве базисов такого кода выбрать числа m1, m2,…, mk, для которых выполняются m1 < m2 < ... < mk, (mi . mj-) = 1,

то получается полиалфавитный код системы остаточных классов. В этом случае кодовая комбинация целого числа S будет иметь вид

S = ( S i , s 2 ,..., S k ),

где S º s i ,mod m i ; i = 1,…, k .

Для реализации вычислений в ПКСОК необходимо, чтобы операнды и результат вычисления не выходили за пределы рабочего диапазона

k

Р раб = П m i .                                  (4)

i =1

Пусть заданы два целых числа S и G , тогда в ПКСОК можно выполнить аддитивные и мультипликативные арифметические операции [8, 9]

S + G = (Si + g 1 mod mi,..., Sk + gk mod mk),(5)

S - G = (Si - gi mod mi,..., Sk - gk mod mk),(6)

S ■ G = (Si ■ gi mod mi,..., Sk ■ gk mod mk),(7)

где G º g i mod m i ; i = 1,…, k .

Если в качестве базисов полиалфавитного кода выбрать неприводимые полиномы p1(x), p2(x),…, pk(x), для которых справедливо deg Pi (x) ^ deg P2(x) ^... ^ deg Pk (x),             (8)

то получается полиалфавитный полиномиальный модулярный код (ППМК) [6, 7]. В этом случае кодовая комбинация двоичного числа S будет иметь вид

S ( х ) = ( S i ( х ), s 2 ( х ),..., S k ( х )), (9)

где S(x) – полиномиальная форма числа S ;

S ( x ) º s i ( x ) mod p i ( x ); i = 1,…, k .

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

k

Р раб ( х ) = П P i ( х ).                             (i0)

i =i

Пусть заданы два полинома S ( х ) и G ( х ), тогда в ППМК можно выполнить модульные операции

S ( х ) ° G ( х ) =

= s i⁽ х ) ° g i⁽ х )L _ы ,.., к ⁽ х ) ° g k ⁽ х )|„ _ы , ^{(i i)}

р ₁ ( х )                                р _k ( х )

где о - модульные операции сложения, вычитания и умножения; G ( x ) º g i ( x ) mod p i ( x ); i = 1,…, k .

Анализ равенств (5–7) и (11) показывает, что ППМК и ПСОК обладают одинаковыми достоинствами. Очевидно, что переход к вычислениям на основе полиалфавитных модулярных кодов позволяет увели- чить скорость выполнения модульных операций. Данный положительный результат связан с тем, что:

• -    арифметические операции выполняются параллельно по базисам кода;

• -    операнды si, gi имеют меньший размер по сравнению с числами S и G.

2.    Теоретические основы обнаружения и коррекции ошибок в ППМК

Поэтому полиалфавитные модулярные коды были применены в вычислительных системах реального времени, таких как спецпроцессоры цифровой обработки сигналов [8– 10], цифровые фильтры [11 – 15], системы аутентификации низкоорбитальных спутников [16, 17], системы шифрования [18 – 20]. Так, в работе [20] представлена архитектура СБИС для реализации криптосистемы с открытым ключом RSA с использованием системы остаточных классов. Проведенные исследования показали, что использование ПСОК позволило увеличить скорость выполнения на 35 % по сравнению с существующими реализациями RSA.

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

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

В настоящее время теория построения корректирующих кодов системы остаточных классов достаточно глубоко проработана [9, 23, 24]. В этих кодах обнаружения и исправления ошибок в код ПСОК вводится n дополнительных контрольных модулей mk+1, mk+2,…, mk+n, для которых mk < mk+i < ... < mk+n .                              (12)

В этом случае избыточная кодовая комбинация целого числа S будет иметь вид

S ^{( s} 1 , s 2 , ..., ^s k , ^s k +1 , ..., ^s k + n ) ,                           ⁽¹³⁾

где S º s i ,mod m i ; i = 1,…, k + n .

При введении n контрольных модулей происходит расширение количества возможных кодовых комбинаций, которое образует полный диапазон

Рпол = П Pi =Рраб П Pi =Рраб Ркон •(14)

i=1

Избыточная комбинация кода ПСОК (13) считается разрешенной, если число S принадлежит рабочему диапазону, то есть

S < Рраб .(15)

Поэтому в основу большинства методов обнару жения и исправления ошибок ( МОИО ) положены по зиционные характеристики ( ПХ ), которые однознач но показывают положение числа S относительно ра бочего диапазона без перевода в позиционный код .

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

Рассмотрим код ППМК с минимальной избыточ ностью . Данный результат можно достичь за счет введения дополнительного контрольного остатка

S(x) = (s1(x),..., Sk(x), Sk+1(x)), где S(x) º sk+1(x) mod pk+1(x).

То есть необходимо добавить контрольное основание pk+1(x), для которого выполняется условие deg P1(x), ^... ^ deg Pk(x) ^ deg Pk+1(x) •

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

Рпол (X) = П Pi (х) = Рраб (x)Pk+1 (x) .(18)

i =1

Для избыточного ППМК комбинация (16) считается разрешенной только при условии, что deg S (х) < deg РРаб (x).(19

Ошибка вычислений приводит к искажению остатка кодовой комбинации s * (х) = sj (x) + Asj (x),(20)

где + - суммирование по модулю два; A s j ( x ) - глубина ошибки;

A s j ( х ) = { 1, ..., x M ¹ + x M^{J 2} + ... + 1 } ; M j = deg P j ( x ).

Тогда ошибочная комбинация ППМК представляется

S * ( x ) = ( S ! ( x ),..., s J ( x ),..., S k _{+ 1}( x )).                 (22)

Теорема 1 . Если в избыточном полиалфавитном полиномиальном модулярном коде, основания которого удовлетворяют условию (18), для кодовой комбинации S * (x) не выполняется условие (19), то такая комбинация является запрещенной.

Доказательство.

Известно, что разрешенная комбинация S ( x ) = ( s i ( x ),^, s k ( x ), s k +i ( x )) удовлетворяет условию (20). Выполним обратный перевод из ППМК в позиционный код (ПК) с помощью Китайской теоремы об остатках в полиномах (КТОП)

S ( x ) = ( s 1 ( x ), В 1 ( х ) + ... + s_J ( x ) В ( х ) + ... + ⁺ s k +1 ( x ) В ( х ))mod Р _пол ( х ),

где B j (x) - ортогональный базис основания p j (x) ;

B j ^{( x} ) = m j ^{( x} ) P пол ^{( x} ) / p j ^{( x} ) = m j ^{( x} ) P j ^{( x} ); B j ^{( x} ) ° ^1mod p j ^{( x} );

mj(x ) = P 4 x )|j x )- вес ортогонального базиса.

Пусть в комбинации S ( x ), глубина которой равна A s j ( x ) / 0, произошла ошибка в j -м остатке. Тогда комбинация будет иметь вид (22). Выполним обратный перевод из ППМК в позиционный код

S * ( x ) =

k +1

^ s i ( x ), B i ( х ) + s ^j ( x ) В ( х )

i =1

Однако введение одного контрольного остатка (основания) позволяет только обнаруживать однократные ошибки в коде. Под такими ошибками в по-лиалфавитных кодах понимается искажение одного остатка в комбинации. Чтобы обеспечить коррекцию такой ошибки, необходимо увеличить избыточность кода. Для этого необходимо ввести второе контрольное основание pk+2(x), для которого справедливо deg P1(x), < ... < deg pg+1(х) < deg pg+2 (х) . (27)

Докажем теорему, определяющую требования к контрольным основаниям ППМК, способным корректировать однократную ошибку.

Теорема 2. Если в избыточном полиалфавитном полиномиальном модулярном коде, для которого справедливо соотношение (27), выполняется условие deg(рк—1 (x)pk (x)) < deg(pk+1 (x)pk+2 (x)), (28) то данный код может корректировать однократную ошибку.

Доказательство. Пусть задана разрешенная кодовая комбинация, которая удовлетворяет условию (19). Введем в данную комбинацию однократную ошибку. Допустим, что в данной комбинации исказился j -й и g -й остатки, где j * g . Тогда получаем

S j ( x ) = ( s 1 ( x ),..., s j ( x ),..., s k + ₂( x )), (29)

S g ( x ) = ( s 1 ( x ),..., s g ( x ),..., s k + ₂( x )), (30)

Р пол ^{( х} )

= § s , ( x ), B i ( х ) + ( s j ( x ) + A s J ( x )) В ( х )       = (24)

i =1

i * ^j                                                                    Р пол ( х )

= S ( x ) + A s j ( x )) В j ( х ).

где s j ( х ) = s_J ( x ) + A s_J ( x ); s g ( х ) = s_g ( x ) + A s_g ( x ).

Разделим обе комбинации на рабочий диапазон. Полученные полиномиальные интервалы должны отличаться друг от друга как минимум в одном младшем разряде. Тогда согласно (26) имеем

Разделим комбинации S(x) и S * (x) на рабочий диапазон. Если комбинация ППМК является разрешенной и выполняется условие (19), то частное от деления будет равно нулю.

H ( x ) = _ S ( х )/ Р раб ( x ) ] = 0, (25)

где [_] - целая часть числа.

Для ошибочной комбинации S * (x) получаем

H ( x ) =

S * ( х )

Р раб ( x )

S ( х ) + A s j ( x ) B j ( x ) Р раб ( x )

A s j ( x ) B j ( x )

Р раб ( x )

* 0.

Теорема доказана.

В кодах ПСОК с помощью выражения (25) вычисляют ПХ, которая называется интервалом числа. Учитывая подобие между кодами ПСОК и ППМК, можно сделать вывод, что в качестве ПХ для последнего можно выбрать полиномиальный интервал (ПИ).

S * ( х ) . Р_раб ( x )

s g ( х ) . Р_раб ( x )

Согласно (26) имеем

A s j ( x ) B j ( x ) Р раб ( x )

> 1.

A s g ^{( x} ) B g ^{( x} ) Р раб ( x )

> 1.

Известно, что ортогональные базисы вычисляются

m j ( x ) Р пол ( x ) = m j ( x ) Р раб ( x ) Р к _О н ( х ) p j^{( x} )                p j^{( x} )

_R x m g ( x ) Р пол ( x ) _ m_s ( x ) Р раб ( x ) Р к _О н ( х )

Bg(x)          r \                      \ pg(x)              pg(x)

где P кон ( x ) = p k +1 ( x ) p k +2 ( x ).

Подставим (33) и (34) в выражение (32) и сократим на Р раб (х).

A s j ( x ) m j ( x ) Р _К о _Н ( x ) + A s g ( x ) m g ( x ) Р _К о _Н ( x ) . pj^{( x} ) _ _ pg ^{( x} ) .

> 1.(35)

Известно, что число полиномиальных интервалов будет равно N_ПИ =2^d es P «»( x ) . Это позволяет перейти к вычислениям по модулю Р кон (х). Получаем

Р кон ( х )

A s j ( x ) m j ( x ) A s g ( x ) m g ( x ) P j ⁽.^x )            P g ^{( x} )

Рассмотрим второй сомножитель (36)

^A s j ^{( x} ) m j ^{( x} ) P g ^{( x} ) + ^A s g ^{( x} ) m g ^{( x} ) P j ^{( x} )

P j ^{( x} ) P g ^{( x} )

> 1.

> 1.(37)

^Р кон ^{( х} )

Так как P j ( x ), P g ( x ) - неприводимые полиномы, а |^A s j ⁽ x ) m j ⁽ x )| _Pj( x ) = s j ⁽ x ) ,

|^{A s} g ^{( x} ) m g ^{( x} )l ₍ = s g ^{( x} ), I                               I ^P g ^{( x} )

где deg s j ( x ) <  deg P j ( x ), deg S g ( x ) <  deg P g ( x ), то

I ^A s j ⁽ x ) m j ⁽ x ) P g ⁽ x ) + ^A s g ⁽ x ) m g ⁽ x ) P₃ ⁽ x )|       * 0 . ⁽³⁸⁾

^{1                                                                                              1} Ркон ^{( х} )

Положим, что j = k -1, g = k . В этом случае получаем

Р кон ^{( Х} У ( Pk -1⁽ x ) Pk ^{( x} ) ) > 1.                          ⁽³⁹⁾

Тогда справедливо, deg(рк-1(x)Pk (x)) < deg(Pk+1(x)Pk+2(x)) .

Теорема доказана.

3. Разработка численного метода вычисления позиционной характеристики полиномиального интервала в ППМК

В избыточных кодах ПСОК во многих МОИО используется ПХ - интервал [8]. Выбор данной позиционной характеристики определяется тем, что данная она имеет простое описание

H = _ S/ Р б ] .                                  (40)

Если выполняется условие (15), то комбинация S =( s 1 , s ₂,.., s_k + ₂) не содержит ошибки и Н = 0. Значит, она будет находиться внутри рабочего диапазона, то есть значение Н = 0. При возникновении ошибки позиция комбинации S * = ( s i ,. s ₂,.., s_{k +2}) изменится и она будет находиться вне Р_ра6 . В результате интервал Н # 0.

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

S ( x ) =

k + n

Е s i ^{( x} ), ^B i ^{( х} )

i =1

^Р пол ^{( х} )

где B j (x) - ортогональный базис модуля P j (x) ; i =1,2,..., k + n .

Воспользуемся подобием кодов ПСОК и ППМК и вычислим полиномиальный интервал, используя выражение (41). Получаем

H ( x ) =    S ⁽ x )

_ Р р _а6 ( x )

k + n

Е s i ^{( x} ) B i ^{( x} )

Р пол ( Х )

Р раб ( x )

Разделим ортогональные базисы на Р р _аб( x ) до получения частного Q i (x) и остатка R i (x) . Тогда

B i ( x ) = Q i ( x ) Р раб ( x ) + R i ( x ),                     (43)

где

I B i ( x ), i = 1,...., k

R i ⁽ x ) — |

[ 0, i — k + 1,..., k + n

; Bi ( x ) -

ортогональный базис кода с информационными основаниями.

Так как число полиномиальных интервалов равно N пи =2^{deg P 1} x ) , то выражение (42) можно свести к вычислениям по модулю Р_кон(х) . Тогда

^{Н ( х} ) =

где

W ( x ) =

k + n

Е s i ^{( x} ) Q i ^{( x} ) ⁺ W ^{( x} )

i =1

£«( x ) B i ( x )

i =1 _________________________

Р раб ( х )

Р кон ( x )

ранг полинома при использовании информационных оснований.

Основным недостатком выражения (44) является вычисление по составному модулю Р кон (х) . Воспользуемся изоморфизмом КТОП и преобразим выражение (44) к виду

^L k +1 ^{( х} ) =

Lk + n ( х ) =

k + n

E s i ^{( x} ) Q i ^{( x} ) ⁺ U ^{( x} ) i =1

P k + 1 ⁽ x )

k + n

E s i ( x ) Q i ( x ) + U ( x )

i =1

Pt + n ⁽ x )

Анализ выражения (45) показывает, что предложенный численный метод вычисления ПХ не является оптимальным с точки зрения количества выпол-

ненных арифметических операций. Чтобы вычислить полиномиальный интервал кода ППМК, необходимо выполнить ( k + n ) операций умножений остатков s i ( x ) на константы Q i ( x ), где i = 1,…, k , и одно сложение. Чтобы уменьшить вычислительную сложность численного метода вычисления ПХ, рассмотрим код ППМК, состоящий из k информационных оснований и одного контрольного основания p k +1 ( x ). Для данного набора остатков необходимо вычислить ортогональные базисы B 1k +1 ( x ),..., B k +1 ( x ), B k ++11 ( x ). Верхний индекс показывает, какое контрольное используется в данном избыточном коде. Полученные ортогональные базисы делятся на рабочий диапазон до получения частного Q i ( x ) и остатка R i ( x ) согласно (43). При поступлении на вход декодера избыточной комбинации ППМК с одним контрольным основанием производится вычисление полиномиального интервала по модулю p k +1 ( x ).

L k +i⁽ х) =

k

= £ s i (x ) Q i (x ) + s k +i⁽ x ) ^Q k +i⁽ x ) + U ⁽ x ) i =1

Оставим в коде ППМК k информационных основания и заменим только контрольное основание p k +1 ( x ) на p k +2 ( x ). Для данного набора остатков необходимо вычислить ортогональные базисы B k ^{+ 2} ( x ),..., B k ^{+ 2} ( x ), B k +k(x ). Полученные ортогональные базисы делятся на рабочий диапазон до получения остатка согласно (43). Тогда выражение (46) примет вид

L k +2 ⁽ х) =

k

£ S i ( x ) Q i ( x ) + S k +2 ( x ) Q k +2 ( x ) + U ( x ) i =1

P k + 2 ⁽ x )

Реализуем данную процедуру для всех остальных контрольных оснований. Тогда численный метод вычисления ПХ кода ППМК можно представить, как

k

L k +i⁽ х ) = £ s i ⁽ x ) ^{Q (} x ) + s k +i⁽ x ^{) Q} k +i⁽ x ) + U ⁽ x )

i =1

,

P k + 1 ⁽ x )

^L k + n ⁽ х ) =

k

£ s i ^{( x ) Q ( x} ) + s k + n ^{( x ) Q} k + n ^{( x} ) + U ^{( x} ) i =1

P k + n ⁽ x )

Анализ выражения (48) показывает, что в разработанном численном методе вычисления ПХ было сокращено количество операций умножения, что позволяет уменьшить временные затраты на коррекцию ошибочной комбинации кода ППМК. Так, при вычислении данной ПХ требуется выполнить ( k+n ) операций умножения по модулю

Р кон ( х ) = П P i (х ).

i = k +1

А при использовании разработанного численного метода для вычисления ПХ интервальный полином требуется выполнить ( k+ 1) операцию умножения по модулю контрольного основания.

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

Рассмотрим пример использования разработанного численного метода вычисления позиционной характеристики полиномиальный интервал ППМК. Пусть информационными основаниями будут p 1 ( x ) = x ⁵ + x ³ + x ²+ x + 1, p 2 ( x ) = x ⁵+ x ⁴+ x ²+ x + 1. Тогда рабочий диапазон будет равен P раб ( x ) = x ¹⁰+ x ⁹+ x ⁸+ x ⁷+ x ⁶+ x ⁴+ x ³ + x ²+ 1. В качестве контрольных оснований в данном коде используются два пятиразрядных неприводимых полинома. Рассмотрим первый кортеж кода ППМК с минимальной избыточностью. Пусть первым контрольным основанием будет полином p 3 ( x ) = x ⁵+ x ⁴+ x ³+ x +1. Для компактной записи используем шестнадцатеричную систему счисления. Тогда p 3 ( x ) = x ⁵+ x ⁴+ x ³+ x + 1 = 111011 2 = 3 B 16 . Полный диапазон данного кода ППМК равен

P™ ( x ) = x ¹⁵ + x ¹⁴ + х ¹² + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ⁴ + x ³ +

+ x ² + x + 1 = 1101000011111111 = B 0 FF .

Воспользуемся методом вычисления ортогонального базиса [5]. Для получения первого ортогонального базиса необходимо выполнить:

• 1.    Вычислить константу

  C 1¹²³ ( x ) = П p j ( x ) = 100 01110001 = 471.

• 2.    Найти остаток константы по модулю p 1 ( x )

• 3.    Найти вес ортогонального базиса m ₁ ¹²³ ( x ), для которого справедливо

• 4.    Вычислить ортогональный базис

  B 1¹²³ ( x ) = m 1²³ ( x ) C 1¹²³ ( x ) =

  = 110 000011101001 = 60 E 9.

j =1 j *1

d 1¹²³ ( x ) = C 1¹²³ ( x ) mod p 1 ( x ) = 01011 = х ³ + х + 1.

d 123 ( x ) m 1²³ ( x ) = 1 mod p 1 ( x ).                       (49)

Получили m 1¹²³ ( x ) = х ⁴ + х ³ + 1 = 11001.

Аналогичным образом получаем два оставшихся ортогональных базиса

B 2²³ ( x ) = 101000101011 = A 2 B ,

B 3²³ ( x ) = 110101011000011 = 6 AC 3 .

Для выполнения разработанного численного метода вычисления позиционной характеристики в ППМК представим ортогональные базисы в виде (43)

B 1²³ ( x ) = R 1¹²³ ( x ) P _pa6 ( x ) + B * ( x ) =

= ( x ⁴ + x ² ) Р раб ( x ) + ( x ⁹ + x ⁶ + x ³ + x ² + 1).

B 2²³ ( x ) = R 1²³ ( x ) Р раб ( x ) + B * ( x ) =

= ( x + 1) Р_раб ( x ) + ( x ⁹ + x ⁶ + x ³ + x 2 ).

B 323 ( x ) = R 123 ( x ) Р раб ( x ) = ( x ⁴ + x ² + x + 1) Р раб ( x ).

Тогда имеем

Q ¹²³ ( x ) = x ⁴ + x ² = 10100.

Q 2²³ ( x ) = x + 1 = 00011.

Q 1¹²³ ( x ) = x ⁴ + x ² + x + 1 = 10111.

Данные значения будут использоваться при вычислении значения полиномиального интервала по модулю p 3 ( x ) = x ⁵ + x ⁴+ x ³ + x + 1.

Рассмотрим второй кортеж кода ППМК. В качестве второго контрольного основания выбираем p 4 ( x ) = x ⁵ + x ² + 1. Тогда код ППМК имеет p 1 ( x ) = x ⁵+ x ³ + x ²+ x + 1, p 2 ( x ) = x ⁵+ x ⁴+ x ²+ x + 1, а информационные основания и контрольное основание p 4 ( x ) = x ⁵ + x ² + 1. Тогда полный диапазон равен

P 3 ( x ) = x ¹⁵ + x ¹⁴ + х ¹³ + x ⁹ + x ⁸ + x ³ + 1 =

= 1110001100001001 = E 309.

Произведем вычисление первого ортогонального базиса для данного кортежа оснований. Для получения первого ортогонального базиса необходимо выполнить:

• 1.    Вычислить константу

  С 1¹²⁴ ( x ) = р 2 ( х ) р 4 ( х ) = 110 00001011 = 70 D .

• 2.    Найти остаток константы по модулю p 1 ( x )

• 3.    Найти вес ортогонального базиса m 1¹²⁴ ( x ), для которого справедливо

  d 1¹²⁴ ( x ) m J⁴³ ( x ) = 1mod p 1 ( x ).

• 4.    Вычислить ортогональный базис

  В ³²⁴ ( x ) = m l²⁴ ( x ) C 1¹²⁴ ( x ) = 100111011001111 = 4 ECF .

d 1²⁴ ( x ) = C 1²⁴ ( x )mod p 1 ( x ) = 10010 = х ⁴ + х .

Получили т™( x ) = х ⁴ + х ³ + х ² + 1 = 11101.

Аналогичным образом получаем другие ортогональные базисы

В 2²⁴ ( x ) = 10 0100 00001101 = 240 D ,

В 3²⁴ ( x ) = 110101011000011 = 6 AC 3.

Воспользуемся выражением (43) и представим ортогональные базисы в виде

B 1²⁴ ( x ) = R ¹²⁴ ( x ) Р раб ( x ) + B * ( x ) =

= ( x ⁴ + x ³ + x ) Р_раб ( x ) + ( x ⁹ + x ⁶ + x ³ + x ² + 1).

B 2²⁴ ( x ) = R 2²⁴ ( x ) Р раб ( x ) + B * ( x ) =

= ( x ³ + x ² + 1) Р_раб ( x ) + ( x ⁹ + x ⁶ + x ³ + x ² ).

B 2²⁴ ( x ) = R 3¹²⁴ ( x ) Р раб ( x ) = ( x ⁴ + x ² + x + 1) Р раб ( x ).

Тогда имеем

Q 1¹²⁴ ( x ) = x ⁴ + x ² + х = 10110.

Q 2²⁴ ( x ) = x ³ + х ² + 1 = 01101.

Q 3²⁴ ( x ) = x ⁴ + x ² + x + 1 = 101 1 1.

Выберем в качестве полинома S(x) = x ⁷, который удовлетворяет условию (19). Представим полином в коде ППМК с двумя контрольными основаниями

S ( x ) = ( x ⁴ + x + 1, x ² + 1, х ⁴ + х ³ + х , x ⁴ + x ² ).

Для обнаружения и коррекции ошибки в ППМК сначала используем первый кортеж, состоящий из p1(x) = x5+ x3+ x2+ x + 1,        p2(x) = x5 + x4+ x2+ x + 1, p3(x) = x5 + x4+ x3 + x + 1 оснований. Тогда имеем комбинацию

S ( x ) = ( x ⁴ + x + 1, x ² + 1, x ⁴ + x ³ + x ) =

= (10011,00101,11010).

Вычислим ранг полинома при использовании информационных оснований. Получаем

W ( x ) =

( х ⁴ + х + 1) В * + ( x ² + 1) В 2*

x ¹⁰ + x ⁹ + х ⁸ + x ⁷ + x ⁶ + х ⁴ + x ³ + x ² + 1

= x ³ + x ² + x + 1.

Вычислим значение полиномиального интервала, представленного по первому контрольному основанию, используя выражение (46). Представим аргументы выражения (46) в виде элементов поля Галуа GF(2⁵), порожденных p 3 ( x ) = x ⁵ + x ⁴ + x ³ + x + 1.

51 (х) = 10011 = p29, s 2( х) = 00101 = P13, s 3( х) = 11010 = P7, W (х) = 01111 = p8,

Q 1¹²³ ( x ) = x ⁴ + x ² = 10100 = P ⁹ ,

Q 2²³ ( x ) = x ² + 1 = 00101 = в ⁸ ,

Q 1¹²³ ( x ) = x ⁴ + x ² + x + 1 = 10111 = P ²⁶ .

Тогда

L ( х ) =

^ S i ( x ) Q i ( x ) + s 3 ( x ) Q 3 ( x ) + U ( x ) i =1

p ₃ ( х )

= |p²⁹ -P ²⁸ +P ²⁶ -P ¹³ +P ⁷ -P ¹⁹ +P ⁸|          = 0.

I                                                        i x + x + x +1

Представим заданный полином в коде ППМК, используя второй кортеж, состоящий из оснований p 1 ( x ) = x ⁵+ x ³+ x ²+ x + 1, p 2 ( x ) = x ⁵ + x ⁴+ x ²+ x + 1, p 3 ( x ) = x ⁵ + x² + 1. Тогда имеем комбинацию

S ( x ) = ( x ⁴ + x + 1, x ² + 1, x ⁴ + x ² ) =

= (10011,00101,10100).

Вычислим значение полиномиального интервала, представленного по второму контрольному основанию, используя выражение (46). Представим аргу- менты выражения (46) в виде элементов поля Галуа GF(25), порожденных p3(x) = x5 + x2 + 1.

5 1 ( х ) = 10011 = в ¹⁷ , s 2 ( х ) = 00101 = Р 5 , s ₃( х ) = 10100 = в ⁷ , W ( х ) = 01111 = в ²³ , Q 1²⁴ ( x ) = x ⁴ + x ² + х = 10110 = в ⁹ , Q 2²⁴ ( x ) = x ³ + х ² + 1 = 01101 = в ⁸ Q 3²⁴ ( x ) = x ⁴ + x ² + x + 1 = 10111 = в ²⁶ .

Тогда

L 4 ( х ) =

£ s, ( x ) Q ( x ) + s 4 ( x ) Q 4 ( x ) + U ( x ) i =1

p ₄ ( х )

^ 'в ⁹ +в ⁵ 'в ⁸ +₽ ’ 'в ²⁶ +в ²³ | x 4 + x 2 +1 = 0.

Так как значение полиномиального интервала равно L 3 ( x ) = L 4 ( x ) = 0, то комбинация

S ( x ) = ( x ⁴ + x + 1, x ² + 1, х ⁴ + х ³ + х , x ⁴ + x ² )

не содержит ошибки.

Пусть ошибка возникла в первом остатке, а ее глубина равна Л s 1 ( x ) = 1. Тогда искаженный остаток

s * ( x ) = s 1 ( x ) + Л s 1 (x) = x ⁴ + x .

В результате этого ошибочная комбинация кода ППМК примет вид

S ( x ) = ( x ⁴ + x , x ² + 1, х ⁴ + х ³ + х , x ⁴ + x ² )

Воспользуемся разработанным численным методом вычисления ПХ. Для обнаружения и коррекции ошибки в ППМК сначала используем первый кортеж, состоящий из        p1(x) = x5 + x3 + x2 + x + 1, p2(x) = x5+ x4+ x2+ x + 1, p3(x) = x5+ x4+ x3+ x + 1 оснований. Тогда имеем комбинацию

S * ( x ) = ( x ⁴ + x , x ² + 1, x ⁴ + x ³ + x ) = (10010,00101,11010).

Вычислим ранг полинома при использовании информационных оснований. Получаем

W ( x ) =

( х ⁴ + х + 1) В * + ( x ² + 1) В 2*

x ¹⁰ + x ⁹ + х ⁸ + x ⁷ + x ⁶ + х ⁴ + x ³ + x ² + 1

= x ³ + x ² + x + 1.

Представим аргументы выражения (46) в виде элементов поля Галуа GF(2⁵), порожденных p 3 ( x ) = x ⁵+ x ⁴+ x ³ + x + 1.

s1 (х) = 10010 = в24, s 2( х) = 00101 = в13, s 3 (х) = 11010 = в7, W (х) = 01111 = в8.

Тогда

L 3 ( х ) =

£ s i ( x ) Q .( x ) + s 3 ( x ) Q 3 ( x ) + U ( x ) i =1

p ₃ ( х )

= в ²⁴ 'в ²⁸ + в ²⁶ 'в ¹³ +в ⁷ 'в ¹⁹ + в 8|₄ з = 01110. I                                                        I x ⁴ + x 3 + x +1

Представим аргументы выражения (46) в виде элементов поля Галуа GF(2⁵), порожденных p 3 ( x ) = x ⁵ + x ² + 1.

s (х) = 10010 = в30, s 2( х) = 00101 = в5, s 3( х) = 10100 = в7, W (х) = 01111 = в23.

Тогда

L 4 ( х ) =

£ s i ( x ) Q i ( x ) + s 4 ( x ) Q 4 ( x ) + U ( x ) i =1

p ₄ ( х )

= |в ³⁰ 'в ⁹ +в ⁵ 'в ⁸ +в ⁷ 'в ²⁶ + в ²³| x _{4 +} x 2 _{+ 1} = 11010.

В результате получили, что позиционная характеристика отлична от нуля, что свидетельствует о том, что комбинация ППМК содержит ошибку. Значению ПХ L3(x) = 11010, L4(x) = 11010 соответствует вектор ошибки e = (00001,00000,00000,00000,00000).

Чтобы исправить ошибку, необходимо к искаженной комбинации прибавить вектор ошибки.

S ( x ) = S * ( x ) + e = ( x ⁴ + x , x ² + 1, x ⁴ + x ³ + x ) +

+ (00001,00000,00000,00000,00000) =

= (10011,00101,11010).

Используя разработанный численный метод вычисления ПХ полиномиальный, ошибка в коде ППМК была обнаружена и исправлена.

Заключение

В статье рассмотрены основные принципы построения полиалфавитных полиномиальных модулярных кодов. Показано, что благодаря распараллеливанию таких арифметических операций, как сложение, вычитание и умножение, применение кодов ППМК позволяет повысить производительность вычислительных систем. При этом коды ППМК обладают потенциальными возможностями по обнаружению и коррекции ошибок, возникающих в процессе вычислений. Это обусловлено равноправностью и независимостью оснований ППМК. В статье представлены теоретические основы построения избыточных ППМК, способных обнаруживать и корректировать ошибки вычислений. На основе доказанных теорем был разработан численный метод вычисления позиционной характеристики полиномиальный интервал в ППМК, который требует меньших временных затрат. Так, при вычислении данной ПХ на основе Китайской теоремы об остатках в полиномах требовалось выполнить ( k+n ) операций умножения по модулю

P (х) =П Pi( х), i=k+1

а при использовании разработанного численного метода для вычисления ПХ требуется выполнить ( k+ 1)

операцию умножения по модулю контрольного основания. Представленный в статье пример подтвердил выводы.

Работа выполнена при поддержке Министерства науки и высшего образования в рамках работ Российского научного фонда (проект №23-21-00036, .