Scientific journal

International Journal of Applied and fundamental research

ISSN 1996-3955

ИФ РИНЦ = 0,593

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

В настоящее время в системах хранения и передачи данных применяют различные технологии информационного резервирования с применением специальных алгоритмов кодирования на базе корректирующих кодов, в частности, кодов Рида-Соломона [1], которые за счет использования избыточной информации делают возможным исправление искажений. Однако, алгоритмы кодирования и декодирования информации с применением кодов Рида-Соломона достаточно нетривиальны, и для эффективной программной или аппаратной реализации требуется достаточно глубокая математическая проработка с применением алгебры конечных полей Галуа [2]. В частности, алгоритм декодирования состоит из блока вычисления синдрома искажений, полинома локаторов искажений, самих локаторов искажений и значений искажений, и все блоки имеют дело с полиномами, заданными над конечным полем Галуа. Особое место занимает блок вычисления значений искажений на базе метода Форни, использующего усеченную свертку полиномов, заданных над полем Галуа, и здесь требуется особый подход для построения эффективного алгоритма вычисления значения усеченной свертки полиномов при заданном аргументе.

В рамках научных исследований автора в области надежности систем хранения, передачи и обработки данных [3-9], а также в области информационного резервирования [10] возникла научная задача разработки эффективного алгоритма вычисления усеченной свертки полиномов Ψ(х) и ξ(х), заданных над полем Галуа GF(p^m), при заданном аргументе x, и аппаратной реализации для поля Галуа GF(2^m).

Полином над полем Галуа. Пусть задано поле Галуа GF(p^m). Тогда полиномом, заданным над полем Галуа, будем называть функцию:

;

(1)

Над полиномами можно производить алгебраические операции, также на место переменной x можно подставлять конкретное значение, являющееся элементом поля Галуа GF(p^m), и вычислять значение функции. При пересчете коэффициентов полинома при выполнении операции или вычислении значении функции, строго соблюдаются правила арифметики для поля GF(p^m).

Сумма полиномов. Сложение полиномов выполняется путем сложения по правилам арифметики поля Галуа GF(p^m) соответствующих коэффициентов, стоящих перед переменной в одной степени. Отсутствующие в полиномах коэффициенты, считаются равными нулю.

Пусть заданы два полинома Ψ(х) и ξ(х). Тогда, сумма этих полиномов определяется следующим образом:

;

. (2)

Пример. Сложим полиномы Ψ(х) = 49x² + 50x + 51 и ξ(х) = 19x² + 93x + 1, заданные над полем GF(2⁸), заданного с помощью неприводимого многочлена p(х) = x⁸ + x⁴ + x³ + x³ + 1. Используя арифметику поля GF(2⁸) для сложения коэффициентов полиномов, имеем: (49 + 19)x² + (50 + 93)x + (51 + 1) = 34x² + 111x + 50.

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

Пусть заданы два полинома Ψ(х) и ξ(х). Тогда, произведение этих полиномов определяется следующим образом:

(3)

Пример. Умножим полиномы Ψ(х) = 49x² + 50x + 51 и ξ(х) = 19x² + 93x + 1, заданные над полем GF(2⁸), заданного с помощью неприводимого многочлена p(х) = x⁸ + x⁴ + x³ + x³ + 1. Используя арифметику поля GF(2⁸) для сложения и умножения коэффициентов полиномов, получаем: Ψ(х)∙ξ(х) = (49∙19)x⁴ + (49∙93 + 50∙19)x³ + (49∙1 + 50∙93 + 51∙19)x² + (50∙1 + 51∙93)x + 51∙1 = 100x⁴ + 218x³ + 31x² + 3x + 51.

Особо отметим, что если мы будем подразумевать, что любые «отсутствующие» коэффициенты в полиномах, в том числе коэффициенты с индексами больше степени полиномов, равны нулю: и , то мы внутреннее суммирование по двум индексам можем преобразовать суммирование по одному индексу. Для этого мы изменим верхние границы для обоих индексов: i ≤ q и j ≤ q, при этом мы ничего не теряем, поскольку i ≥ 0, j ≥ 0 и i + j = q. Случаи, когда i > q (при k – 1 > q), или j > q (при l – 1 > q), все равно никогда не пройдут условие i + j = q, так как i ≥ 0 и j ≥ 0. А при i > k – 1 (при q > k – 1) коэффициенты Ψ_i = 0, а при j > l – 1 (при q > l – 1) коэффициенты ξ_j = 0. Тогда в итоге мы получаем следующие три условия: i + j = q, 0 ≤ i ≤ q и 0 ≤ j ≤ q.

Заметим, что оба индекса неотрицательны и ограничены одним и тем же верхним пределом, причем сумма индексов также равна верхнему пределу. Тогда, очевидно, можно избавиться от одного из индексов, попросту выразив его через другой: j = q – i, и мы ничего не теряем, поскольку 0 ≤ q – i ≤ q, так как 0 ≤ i ≤ q.

В итоге мы получаем следующую «оптимизированную» формулу произведения:

;

. (4)

Усеченная свертка полиномов. Пусть заданы два полинома Ψ(х) и ξ(х). Тогда, усеченной линейной сверткой полиномов будем называть остаток от произведения этих полиномов по модулю полинома xr, иными словами .

По сути, усеченная линейная свертка – это произведение полиномов, в котором «отброшены» члены, степень переменной x в которых больше либо равна r:

. (5)

Пример. Найдем усеченную свертку полиномов Ψ(х) = 49x² + 50x + 51 и ξ(х) = 19x² + 93x + 1, заданных над полем GF(2⁸), по модулю полинома x². Получаем:

.

Вычисление значения усеченной свертки полиномов при заданном аргументе над полем Галуа GF(p^m). Выше мы определили, что усеченная свертка Ω(х) двух полиномов Ψ(х) и ξ(х), заданных над полем Галуа GF(p^m), и при заданном r, определяется как:

.

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

.

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

.

Тогда, в первом приближении имеем следующую итерационную схему вычисления значения полинома-свертки Ω(х) при заданном аргументе х*:

(6)

Заметим, что хотя и итерационная процедура вычисляет Ω(х*) за r итераций, но на каждой итерации, требуется вычисление суммы , количество слагаемых в которой с каждой итерацией s = 1…r только растет. Однако заметим, что количество слагаемых в сумме в точности совпадает с номером итерации, и можно не заново пересчитывать сумму на каждой итерации s, а лишь добавлять очередное слагаемое к сумме, вычисленной на предыдущей итерации s 1. Обозначив , имеем рекуррентное соотношение: , причем . Очевидно, можно совместить обе итерационные схемы, на каждой итерации вычисляя сначала очередную , используя , а затем и , используя и . Наконец, отметим, что для вычисления также необязательно на каждой итерации возводить аргумент х* в степень s, можно использовать соотношение , причем . Тогда, имеем «оптимизированную» итерационную схему вычисления значения полинома-свертки Ω(х) при заданном аргументе х*:

(7)

Пример. Вычислим значение свертки полиномов Ψ(х) = 49x² + 50x + 51 и ξ(х) = 19x² + 93x + 1, заданных над полем GF(2⁸), по модулю полинома x² (т.е. r = 2) при заданном аргументе x* = 64, используя итерационную схему.

Имеем следующие начальные значения: ; .

Далее, на итерации s = 1 выполняем следующие вычисления:

Наконец, на итерации s = 2 (последняя итерация) получаем:

Тогда, искомое значение свертки полиномов равно .

Для проверки полученного значения, подставим заданный аргумент x* = 64 в полином-свертку , полученный в рассмотренном выше примере для полиномов Ψ(х) = 49x² + 50x + 51 и ξ(х) = 19x² + 93x + 1. Имеем: 3∙64 + 51 = 243. Таким образом, очевидно, результат вычисления по рекуррентной схеме верен.

Аппаратная реализация для поля Галуа GF(2^m). Теперь рассмотрим аппаратную реализацию вычисления значения полинома-свертки Ω(х) при заданном аргументе х* над полем Галуа GF(2^m). Аппаратная реализацию можно построить при помощи трех m-битных регистров, а также двух сумматоров и четырех умножителей элементов поля Галуа GF(2^m). Аппаратная реализация быстрых сумматоров и умножителей элементов поля Галуа GF(2^m) хорошо освещены в литературе [1, 2].

Ниже на рисунке представлена предлагаемая автором функциональная схема вычислителя значения полинома-свертки Ω(х) при заданном аргументе х*.