Как найти минимальный многочлен бинарной матрицы

Я работаю с минимальным полиномом бинарной матрицы (1 или 0). Я знаю какой-то алгоритм для нахождения минимального многочлена матрицы, такой как Берлекэмп Мэсси. Не могли бы вы предложить мне какой-нибудь код Matlab для реализации Berlekamp Massey в Galios Field 2. Я пытался использовать linbox lib, но это заняло много времени и не применялось для двоичной матрицы. это моя матрица

 A=[1     0     0    0; 
    0     1     0    1;
    1     1     1    1;
    1     1     1    0];

И это мой код Matlab (но я думаю, что он не подходит для моей задачи в GF(2))

function f=minPoly_Berlemap(A,b)
A=[1     0     0    0; 
    0     1     0    1;
    1     1     1    1;
    1     1     1    0];
b=[1;1;0;0];
[m n]=size(A);
A_u=[];
I=eye(n);
%% Step1
for i=1:(2*n)
    A_u(:,i)= mod(A^(i-1)*b,2);   
end
%% Step2
k=0;
g=[1];
gk=[1];
d=0;
%% Step3
while (d<n&k<n)
    %% Step4
    u_k=I(:,k+1);
    s=mod(u_k'*A_u,2);
    %% Step 5
    d = length(g)-1;
    mul_gs =mod( conv(g(end:-1:1),s),2); %multiply two polynomial
    s_g = mul_gs(d+1:end-d);  
    %% Step 6
    f=Berlekamp_Massey2(s_g);
    %% Step 7
    gk=mod(conv(f,g),2);    
    if d<n
        k=k+1;
        g=gk;
    else 
        break;
    end
end
    f=g
end

matlab matrix polynomials linear-algebra
person John    schedule 29.12.2014    source источник
comment
Я думаю, вы рассматривали функцию minpol для вычислений GF, nl.mathworks.com/ help/comm/ref/minpol.html   -  person Kostya    schedule 29.12.2014
comment
Я думаю, ваш код должен быть pl = minpol(gf(M,1))   -  person Kostya    schedule 29.12.2014
comment
Нет, ошибка Ошибка при использовании gf/minpol (строка 20) X должен быть скаляром или вектор-столбцом   -  person John    schedule 29.12.2014
comment
@ user8264: Есть новости по этому поводу?   -  person knedlsepp    schedule 07.01.2015
comment
@knedlsepp: Чтобы найти минимальный полином матрицы, мы можем использовать Берлекэмпа-Месси. Однако оригинальный Berlekamp-Massey применяется только для последовательности. Чтобы справиться с проблемой, я прочитал алгоритм 2 этой статьи csd.uwo.ca/~moreno/CS424/Ressources/WIEDEMANN-IEEE-1986.pdf . На самом деле реализовать его непросто. Я путаю шаги 5 и 6 этого метода. Вы можете прочитать эту статью и дайте мне знать, если вы понимаете шаг 5. Спасибо.   -  person John    schedule 07.01.2015
comment
Вы недостаточно хорошо читали газету. Они не применяют алгоритм Берлекампа-Месси для нахождения минимального полинома матрицы.   -  person knedlsepp    schedule 07.01.2015
comment
@knedlsepp: Да, он подает заявку на последовательность, и эта последовательность может быть получена из матрицы. Наконец, мы можем найти минимальный многочлен матрицы с помощью последовательностей   -  person John    schedule 07.01.2015
comment
@ user8264: Может быть, вы можете рассказать нам некоторую справочную информацию, для чего вы хотите это использовать. Возможно, то, что вам нужно для вашего решения, на самом деле не минимальный полином матрицы как линейной карты, а что-то еще. Может быть, минимальный многочлен сдвиговых регистров, определяемый строками.   -  person knedlsepp    schedule 07.01.2015
comment
@ user8264: Как вы сказали, он применяет его для последовательности, созданной матрицей, которая не совпадает с матрицей. Вы бы не сказали, что владеете автомобильным заводом, если на самом деле у вас есть только машина.   -  person knedlsepp    schedule 07.01.2015
comment
Да, может быть, я использую неправильное слово. Для фона я понимаю, что его цель - найти минимальный многочлен матрицы. Традиционный метод Берлекампа-Месси применяется только для последовательности. Итак, чтобы использовать его для матрицы, он попытается построить последовательность, созданную внутренним производством между единичным вектором u и пространством Крылова (шаг 4). После этого на шаге 5 он применил полином к той последовательности, которая была получена на шаге 4. Результатом шага 5 является последовательность, и мы можем использовать Берлекэмпа-Месси, чтобы найти минимальный полином.   -  person John    schedule 07.01.2015
comment
Хорошо, немного прочитав статью, я согласен с тем, что они используют BM-алгоритм как важную часть для вычисления минимального многочлена матрицы над конечным полем. В этой статье описано, что вам нужно. Вам следует ознакомиться с ним и приступить к реализации алгоритма 2.   -  person knedlsepp    schedule 07.01.2015
comment
@knedlsepp: Вы понимаете шаг 5 этой статьи? Я обновлю свою реализацию для ясного объяснения   -  person John    schedule 08.01.2015

Ответы (1)


arrow_upward
1
arrow_downward

Проблемы с вашим кодом:

Шаг 1. Вместо (A^i)*b следует вычислить A*(A*(...(A*b)..)), так как это менее сложно. Заменять:

%% Step1 - old
for i=1:(2*n)
    A_u(:,i)= mod(A^(i-1)*b,2);   
end

С этим:

%% Step1 - new
A_u(:,1) = b;
for i = 2:2*n
    A_u(:,i) = mod(A*A_u(:,i-1), 2);   
end

Оригинальный подход

Не слишком углубляясь в проблему, я бы предложил вам простой выход:

Просто взглянув на: M, M^2, M^3, ... мы видим, что

M^3 == eye(4)  [mod 2].

Таким образом, вы знаете, что степень вашего многочлена не больше трех. (Поскольку вы можете заменить M^4 на M и M^5 на M^2 и так далее).

Таким образом, ваш минимальный полином должен быть одним из следующих:

a_0*eye(4) + a_1*M + a_2*M^2 + a_3*M^3, с a_i в {0,1}.

Вы можете просто попробовать все 2^4-1 = 15 возможностей (мы не включаем ту, где все a_i равны нулю), и вы увидите, что M^3 - eye(4) — это ваш минимальный многочлен.

person knedlsepp    schedule 29.12.2014
comment
Я считаю, что метод Берлекэмпа Мэсси может найти коэффициент многочлена. Вы знаете, как применить это для моей проблемы - person John; 30.12.2014
comment
Вы уверены, что это можно сделать с помощью метода Берлекампа-Месси? Из чтения страницы в Википедии мне кажется, что он может найти минимальный многочлен линейно рекуррентной последовательности, что я не уверен, что это то же самое, что и минимальный многочлен линейной карты. Для чего вам это нужно? - person knedlsepp; 30.12.2014