состав тысячи дисковых накопителеи. Подобная крупная популяция элементов подчиняется законам математическои статистики, а, следовательно, определённая доля дисков подвержена регулярному выходу из строя [ 1 ]. При этом, совокупная частота единичных и коллективных отказов растёт с увеличением мощности множества задеиствованных жестких дисков. Предотвращение необратимои потери данных достигается резервированием содержимого СХД с помощью добавления некоторои избыточности в исходныи набор данных. Распространены два варианта построения избыточности: резервное копирование (репликация) и помехоустоичивое кодирование блоков, занимающее меньше избыточного дискового пространства. Уровень надёжности хранения определяется количеством полных копии (реплик) или параметрами кодирования. На практике широко используются ( , )-коды Рида-Соломона (см, например, [ 2 ]), в которых входное сообщение из символов алфавита мощностью = 2 преобразуется в символов из того же алфавита. Коды Рида—Соломона вносят минимально возможныи объем избыточности и обеспечивают максимальныи уровень помехоустоичивости.

При заданных значениях параметров их разность ( − ) определяет максимальное количество утраченных или искаженных символов, при котором из неповреждённых символов может быть восстановлено исходное сообщение. Подобное помехоустоичивое представление данных используется как при передаче, так и при хранении информационных сообщении. При этом, потоковая передача данных по каналам связи и блочное размещение данных на накопителях предъявляют различные требования к параметрам кодирования и .

Так, для потоковои передачи данных при внесении в сообщение пакета ошибок незначительно искажается серия информационных символов с неизвестным расположением, что требует большои величины ( − ) и алфавита малои мощности ~2 , соответствующего однобаитовои (восьмибитнои) структуре данных. Кроме того, с целью сохранения эффективнои пропускнои способности канала необходимо ограничить накладные расходы на избыточность вида ( / ). Эти факторы определяют коды, общепринятые в коммуникационнои отрасли, например, стандарт DVB (Digital Video Broadcast) [ 3 ] с параметрами = 204 и = 188. Дополнительно, локализация априори неизвестных ошибок требует применения специальных вычислительно ёмких алгоритмов поиска искаженных символов внутри сообщения.

В свою очередь, надёжное помехоустоичивое хранение данных требует размещения каждого символа (фрагмента) из закодированного сообщения (блока данных) на отдельном накопителе СХД, независимом от других устроиств хранения. В случае аппаратного отказа одного или нескольких дисков такая схема распределения данных приводит к необходимости обращения к априори известным исправным дискам при восстановлении блока и передачи доступных фрагментов по сети в узел декодирования. Поскольку каждое считывание и передача фрагмента затрачивают полезные ресурсы системы, количество подобных деиствии необходимо сократить, то есть использовать ( , )-код с малыми значениями параметров и . При этом, для поддержания высокои производительности требуется сохранить битовую длину исходного сообщения за счёт увеличения битовои длины фрагмента данных (мощности алфавита) до значении ~2 и выше.

Следует отметить, что типовая вычислительная техника ограничена машиннои арифметикои над целыми 64-разрядными числами. Согласно теории конечных полеи Галуа, вычислительная сложность алгебраических операции по модулю значительно возрастает с увеличением из-за согласования переносов разрядов между машинными словами, составляющими фрагмент блока данных. Растут также и затраты на хранение в памяти промежуточных результатов расчётов. Тем не менее, совершенствование вычислительнои техники, развитие теоретическои и прикладнои криптографии, а также накопление результатов численных экспериментов по конструктивному описанию полеи Галуа высокого порядка [ 4 ], дают возможность программно реализовать алгоритмы помехоустоичивого кодирования по схемам Рида—Соломона для фрагментов данных большого объема.

Согласно теории, коды Рида—Соломона одновременно принадлежат классам линеиных циклических блочных и полиномиальных кодов. Исходя из этого, представление кодов Рида— Соломона допускает две общепринятые интерпретации. В первои трактовке используется таблица многочленов степени меньше над конечным полем порядка , где — степень простого числа. В процессе кодирования входных символов рассматриваются как первыи сегмент таблицы многочленов степени меньше . Теориеи гарантируется, что в таблице содержится единственныи многочлен, соответствующии этим символам. Оставшиеся ( − ) символов определяются как значения этого многочлена в соответствующих ( − ) целочисленных точках. В этои схеме избыточность достигается за счёт переопределенности системы, в которои количество уравнении превышает количество искомых переменных. На практике применяется более производительныи способ кодирования, когда входных символов считаются коэффициентами многочлена степени меньше , а дополнительные ( − ) символов являются полиномиальными коэффициентами произведения на циклическии генерирующии многочлен, определяемыи из таблиц неприводимых многочленов, например, [ 4 ]. Во второи трактовке вместо генерирующего многочлена используется генерирующая матрица размерностью × . Различают также систематическии и несистематическии варианты кодов. В систематическом коде символы избыточности дописываются в конец исходного сообщения. Левая квадратная часть генерирующеи матрицы в этом случае представляет собои единичную матрицу. В несистематическом коде, исходя из структуры генерирующеи матрицы, итоговое закодированное сообщение может не содержать ни одного символа исходного сообщения. К преимуществам систематического кода относится тривиальное декодирование сообщения при отсутствии ошибок, а недостаток заключается в необходимости вычисления обратных матриц. Несистематическое кодирование требует нетривиального декодирования даже неискаженного сообщения, однако позволяет использовать легкообращаемые матрицы, например, инволютивные или ортогональные.

В настоящеи работе приведены примеры алгоритмическои и программнои реализации алгебраических операции, используемых в систематическом коде Рида—Соломона с генерирующеи матрицеи Вандермонда. Для программнои реализации этого кода на конечном поле Галуа с алфавитом мощностью = 2 , > 64 были построены и запрограммированы алгоритмы сложения и умножения больших чисел по модулю 2 . На основе этих алгоритмов стоится генерирующая матрица размерностью × символов и производится кодирование путём умножения векторстроки исходного сообщения из символов на эту матрицу. Таким же образом реализовано декодирование, а именно: исключение из прямоугольнои матрицы ( − ) столбцов, соответствующих исключаемым позициям контрольных или утраченных символов в закодированном сообщении длины , с последующим обращением полученнои квадратнои матрицы × и умножением сокращеннои закодированнои вектор-строки длины на неё.

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

В наиболее производительном методе используется плоская таблица с результатами перемножения двух операндов. При условии, что таблица вычисляется однократно, метод будет задеиствовать лишь быстрые операции адресного считывания в памяти. Несмотря на простоту реализации, этот метод является исключительно требовательным к дорогостоящеи части выделяемых аппаратных ресурсов, поскольку таблица занимает 2 ×2 ×2 бит в быстрои оперативнои памяти. При мощности алфавита = 2 занимаемыи таблицеи объем составит 128 КиБ, однако, при удвоении разрядности до мощности алфавита = 2 в памяти потребуется выделить уже 8 ГиБ. Таким образом, прямое использование таблиц умножения для чисел разрядностью = 32 и выше, не представляется оправданным.

Используемые на практике методы перемножения длинных операндов построены на принципе «разделяи и властвуи». В основу этого принципа положена возможность представить множитель как сумму, в которои каждое слагаемое занимает свои диапазон разрядов. В этом случае искомое произведение может быть вычислено с использованием произведении слагаемых каждого из исходных операндов. При этом, при перемножении слагаемых меньшеи разрядности часто используется рекурсивныи вызов алгоритма до достижения разрядности машиннои арифметики. Первым представителем этого семеиства методов является алгоритм Карацубы [ 5 ] с использованием двух слагаемых на операнд. В развитие этого метода были предложены обобщающие методы с многократным расщеплением, такие как метод Тума—Кука [ 6 ]. Академическое признание также получили методы умножения, использующие преобразование Фурье, такие как алгоритмы Шёнхаге — Штрассена [ 7 ] и Фюрера [ 8 ]. Эти методы имеют наименьшую асимптотическую алгоритмическую сложность, однако, превосходство над алгоритмом Тума—Кука достигается лишь, начиная с чисел порядка 2 —2 , что существенно ограничивает область практического применения. Кроме того, эффективная программная реализация методов на основе преобразования Фурье требует перехода от арифметики комплексных чисел к специальному теоретико-числовому преобразованию (Number-theoretic transform) в конечном поле.

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

В методе Монтгомери символ алфавита в поле (2 ) представляется многочленом длины вида ( ) = = + + … + + , где коэффициенты являются бинарными, ∈ (2). Эти же коэффициенты составляют битовую запись символа :

= ( ⋯ ).

Дополнительно, символ допускает блочное описание последовательностью из машинных слов разрядностью ( = ):

= ( ⋯ ), = ( ) ( ) ⋯ .

В этом случае, полиномиальные представления символа и машинного слова примут вид: ( ) = ( ) = ( ) ( ) +

( ) ( ) + … + ( ) + ( ), ( ) = = ( ) + ( ) + … + + . Если представить второи множитель символом из того же алфавита:

= ( ⋯ ), то псевдокод алгоритма Монтгомери из работы [ 9 ] может быть представлен следующеи программнои реализациеи на языке С++ (см. листинг 1).

Листинг 1. Функция перемножения длинных чисел в поле Галуа по алгоритму Монтгомери для = 32. union UIntGF2XT{ private: uint8_t u08[UIntGF2XTu08LEN]; uint16_t u16[UIntGF2XTu16LEN]; uint32_t u32[UIntGF2XTu32LEN]; uint64_t u64[UIntGF2XTu64LEN]; public: friend const UIntGF2XT MULGF2(UIntGF2XT A, const UIntGF2XT& B); friend void GenAndInvPolyN32(UIntGF2XT& polyN,uint32_t& polyNinv);}; const (UIntGF2XT A, const UIntGF2XT& B){ uint32_t i, j, H, L, P, M; uint32_t C[UIntGF2XTu32LEN],N[UIntGF2XTu32LEN],Caux,Ninv0; std::fill(C,C+UIntGF2XTu32LEN,'\0'); Caux = 0ULL; GenAndInvPolyN32(&N,&Ninv0); for(i = 0; i < UIntGF2XTu32LEN; i++){ for(j = 0; j < UIntGF2XTu32LEN - 1; j++){

MULGF2_32(H, L, A.u32[j], B.u32[i]); C[j] ^= L;

C[j+1] ^= H;} MULGF2_32(H, L, A.u32[j], B.u32[i]); C[j] ^= L; Caux ^= H; MULGF2_32(H, M, C[0], Ninv0); MULGF2_32(P, L, M, N[0]); for(j = 1; j < UIntGF2XTu32LEN; j++){

MULGF2_32(H,L,M,N[j]); C[j-1] = C[j] ^ L ^ P; } inline uint32_t MULGF2_16(uint16_t A, uint16_t B) { uint32_t AsubB, Asqr, Bsqr, AsubBsqr; uint32_t AB; Asqr = LUT16[A]; Bsqr = LUT16[B]; if(A>=B) { } else { } return AB;

AsubB = A - B; AsubBsqr = LUT16[AsubB]; AB = (((Asqr - AsubBsqr) >> 1) + ((Bsqr + 1) >> 1)); AsubB = B - A; AsubBsqr = LUT16[AsubB];

AB = (((Bsqr - AsubBsqr) >> 1) + ((Asqr +1) >> 1)); }

Таким образом, в работе приведена оригинальная программная реализация наиболее вычислительно ёмких алгоритмов, используемых в методе кодирования Рида—Соломона. Показано, что можно наити компромиссныи вариант алгоритма умножения в поле Галуа, использующии как таблицы для операндов малои разрядности, так и методы умножения Карацубы для операндов высокои разрядности. Подобныи подход к вычислению произведении множителеи позволяет построить коды Рида—Соломона в конечных полях с алфавитами большои мощности, подходящие под требования для создания систем хранения данных, устоичивых к сбоям и ошибкам в накопителях.

Работа проведена в рамках выполнения прикладных научных исследований при финансовой поддержке Министерства образования и науки Российской Федерации. Соглашения о предоставлении субсидий № 14.579.21.0010. Уникальный идентификатор Соглашения RFMEFI57914X0010.

References Иваничкина Людмила Владимировна, аспирант факультета управления и прикладной математики Московского физикотехнического института, старший разработчик ООО «Проект Икс».