Исключение Гаусса-Жордана над GF(2)

Мне нужно преобразовать матрицу проверки четности H (которая состоит только из единиц и нулей) из нестандартной формы в стандартную, то есть выразить ее как:

                                    Hsys = [A | I]

H и Hsys имеют одно и то же измерение: (n-k,n). I выше соответствует единичной матрице размерности (n-k).

Исключение Гаусса-Жордана пригодится для решения этой проблемы. Для этой цели в Matlab есть специальная команда rref, однако она больше не действует при работе с GF(2), как в нашем случае. Просматривая Интернет я нашел на Github потенциально подходящее решение для преодоления этого недостатка. Однако это не всегда получается.

Я также пытался сделать HH = mod(rref(H),2), что вообще не сработало, так как многие элементы вывода не были двоичными.

Здесь ниже вы можете найти три образца нестандартных матриц проверки на четность, в которых может быть применено исключение Гаусса-Жордана (по GF(2)). Поскольку всегда должен быть способ систематизировать любую матрицу, мне нужен метод, работающий с матрицами любой размерности.

Этот первый образец взят из сообщение sid в Stackoverflow, еще не ответил:

H=[1 0 1 1 0; 
   0 0 1 0 1; 
   1 0 0 1 0; 
   1 0 1 1 1];

H=[1 1 0 1 1 0 0 1 0 0;
   0 1 1 0 1 1 1 0 0 0;
   0 0 0 1 0 0 0 1 1 1;
   1 1 0 0 0 1 1 0 1 0;
   0 0 1 0 0 1 0 1 0 1];

Последняя представляет собой матрицу размерности (50x100), ее можно найти по по этой ссылке на мой Dropbox< /а>.

Редактировать 21.06.2017

Решение, предложенное @Jonas, сработало в некоторых случаях, но не в большинстве из них, поскольку матрица H кажется сингулярной. Любой другой подобный способ сделать это?

Заранее спасибо и с наилучшими пожеланиями.


matlab matrix math information-theory galois-field
person ailoher    schedule 10.06.2017    source источник
comment
Я не вижу здесь вопроса.   -  person President James K. Polk    schedule 10.06.2017
comment
Я выделил запрос, чтобы сделать его достаточно ясным, я надеюсь, что все в порядке!   -  person ailoher    schedule 10.06.2017
comment
У кого-нибудь есть ключ? Я все еще застрял здесь...   -  person ailoher    schedule 21.06.2017

Ответы (2)


arrow_upward
1
arrow_downward

Вот как я это сделаю (используя исключение Гаусса-Джордана):

H=[1 1 0 1 1 0 0 1 0 0;
   0 1 1 0 1 1 1 0 0 0;
   0 0 0 1 0 0 0 1 1 1;
   1 1 0 0 0 1 1 0 1 0;
   0 0 1 0 0 1 0 1 0 1];


rows = size(H, 1);
cols = size(H, 2);

r = 1;
for c = cols - rows + 1:cols
    if H(r,c) == 0
        % Swap needed
        for r2 = r + 1:rows
            if H(r2,c) ~= 0
                tmp = H(r, :);
                H(r, :) = H(r2, :);
                H(r2, :) = tmp;
            end
        end

        % Ups...
        if H(r,c) == 0
            error('H is singular');
        end
    end

    % Forward substitute
    for r2 = r + 1:rows
        if H(r2, c) == 1
            H(r2, :) = xor(H(r2, :), H(r, :));
        end
    end

    % Back Substitution
    for r2 = 1:r - 1
        if H(r2, c) == 1
            H(r2, :) = xor(H(r2, :), H(r, :));
        end
    end

    % Next row
    r = r + 1;
end

Дайте мне знать, если это не решит вашу проблему.

person Jonas    schedule 10.06.2017
comment
Привет @Jonas, Ваш метод кажется хорошим, но в большинстве случаев на выходе получается единственная матрица, и поэтому я не могу продолжать. Разве нельзя было бы проверить, является ли матрица единственной, и повторить процесс в этом случае? Вы не можете вычислить определитель, так как в большинстве случаев это не квадратная матрица, и хотя я видел людей, рекомендующих использовать «rcond (A)» и «cond (A)», результаты почти одинаковы. когда матрица сингулярна или когда она не сингулярна... - person ailoher; 17.06.2017
comment
И чем длиннее матрица, тем меньше шансов, что этот метод сработает... - person ailoher; 23.06.2017
comment
@MisterTellini, это упрощенная версия, добавление такой вещи, как замена столбцов, может сделать ее еще более мощной. Но все зависит от желаемой структуры кода и исходной структуры кода. В конце концов, может быть лучше с самого начала разработать код с желаемой структурой. - person Jonas; 23.06.2017
comment
Однако есть еще кое-что, чего я не понимаю @Jonas. Исходя из прямоугольной матрицы, «gfrank» которой равен количеству строк, ваш метод все еще не может работать, так как он говорит, что матрица является единственной... - person ailoher; 05.07.2017

arrow_upward
0
arrow_downward

Я столкнулся с той же проблемой, и код @jonas также выдавал в основном единичную матричную ошибку. вы можете попробовать следующий код, который мне показался полезным при поиске систематической формы H. Он также включает вычисление G.

% Gauss-Jordan elimination 
swaps=zeros(m,2);
swaps_count=1;

n=size(H, 2);
m=size(H, 1);

j=1;
index=1;
while index<=m
    i=index;
    while (HH(i,j)==0)&(i<m)
        i=i+1;
    end
    if HH(i,j)==1
        temp=HH(i,:);
        HH(i,:)=HH(index,:);
        HH(index,:)=temp;
        for i=1:m
            if (index~=i)&(HH(i,j)==1)
                HH(i,:)=mod(HH(i,:)+HH(index,:),2);
            end
        end
        swaps(swaps_count,:)=[index j];
        swaps_count=swaps_count+1;
        index=index+1;
        j=index;
    else
        j=j+1;
    end
end

for i=1:swaps_count-1
    temp=HH(:,swaps(i,1));
    HH(:,swaps(i,1))=HH(:,swaps(i,2));
    HH(:,swaps(i,2))=temp;
end

G=[(HH(:,m+1:n))' eye(n-m)];

for i=swaps_count-1:-1:1
    temp=G(:,swaps(i,1));
    G(:,swaps(i,1))=G(:,swaps(i,2));
    G(:,swaps(i,2))=temp;
end

disp(sum(sum((mod(H*G',2)))));
person DaniDaone    schedule 28.07.2020