Раздел "Обработка сигналов и изображений\Communications Toolbox"

Список функций CommunicationsToolbox: Вычисления в конечных полях (полях Галуа)

  В оглавление \ К следующему разделу \ К предыдущему разделу

Внимание! Приведенное ниже описание относится к версии 2.0 пакета Communications, (MATLAB 6.1). В версии 2.1 (MATLAB 6.5) деление объектов полиномов двоичных конечных полей (в том числе расширенных) производится с помощью функции deconv, а данная функция применяется только к полям GF(p^m), где p — простое число, большее двух.

Синтаксис:

[quot,remd] = gfdeconv(b,a);
[quot,remd] = gfdeconv(b,a,p);
[quot,remd] = gfdeconv(b,a,field);

Описание:

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

• [quot,remd] = gfdeconv(b,a)

Выполняет деление полинома b на полином a над полем GF(2), возвращая частное в выходном параметре quot и остаток от деления в выходном параметре remd. Входные параметры и результаты работы представляют собой векторы-строки, содержащие коэффициенты соответствующих полиномов в порядке возрастания степеней. Каждый коэффициент может быть равен 0 или 1, поскольку вычисления производятся в поле GF(2).

• [quot,remd] = gfdeconv(b,a,p)

Выполняет деление полинома b на полином a над полем GF(p), возвращая частное в выходном параметре quot и остаток от деления в выходном параметре remd. Третий входной параметр p — простое число. Параметры b, a, quot и remd представляют собой векторы-строки, содержащие коэффициенты соответствующих полиномов в порядке возрастания степеней. Возможные значения коэффициентов лежат в диапазоне от 0 до p – 1.

• [quot,remd] = gfdeconv(b,a,field)

Выполняет деление полинома b на полином a над полем GF(p^m), возвращая частное в выходном параметре quot и остаток от деления в выходном параметре remd. Здесь p — простое число, а m — положительное целое число. Входные и выходные параметры представляют собой векторы-строки коэффициентов (в порядке возрастания степеней) соответствующих полиномов, представленные в экспоненциальном формате по отношению к некоторому примитивному элементу поля GF(p^m). Третий входной параметр field представляет собой матрицу, в которой перечислены все элементы поля GF(p^m), упорядоченные по степеням того же самого примитивного элемента. Получить такую матрицу можно с помощью функции gftuple.

Пример:

Приведенный ниже код показывает, что в простом двоичном поле GF(2) выполняется равенство с остатком 1. Код также проверяет корректность деления.

p = 2;
b = [0 1 0 1 1];
a = [1 1];
[quot, remd] = gfdeconv(b,a,p)
% Проверка результата
bnew = gfadd(gfconv(quot,a,p),remd,p);
if isequal(bnew,b)
   disp('Правильно.')
end;

Результат работы примера приведен ниже:

quot =
     1      0      0      1
remd =
     1

Правильно.

Приведенный ниже код выводит список тех полиномов вида (для k от 2 до 8), которые нацело делятся на полином в поле GF(3).

p = 3; m = 2;
a = [1 0 1]; % делитель равен 1+x^2
for ii = 2:p^m-1
     b = gfrepcov(ii); % вычислили x^ii
     b(1) = p-1; % вычислили -1+x^ii
     [quot, remd] = gfdeconv(b,a,p);
     % выводим полином -1+x^ii, если он делитсЯ на a без остатка      if remd==0
          gfpretty(b)
     end
end

Результат работы примера приведен ниже:

      4
      2 + X
      8
      2 + X

Как видите, на делятся без остатка полиномы и . Это, в частности, означает, что неприводимый в поле GF(3) полином не является примитивным для поля GF(9) (см. раздел “Алгоритм” на странице с описанием функции gfprimck).

Алгоритм:

Функция gfdeconv использует тот же алгоритм, что и функция deconv базовой библиотеки MATLAB, вычисляя частное как импульсную характеристику дискретного фильтра с функцией передачи, описываемой полиномами b и a. Вычисления производятся с помощью функции gffilter. Для расширенных конечных полей в текущей версии пакета не поддерживается операция дискретной фильтрации, поэтому нахождение частного в данном случае сводится к вычитанию в цикле.

Сопутствующие функции: gfconv, gfadd, gfsub, gfdiv, gftuple

  В оглавление \ К следующему разделу \ К предыдущему разделу