根据H在有限域GF(2^m)上求解生成矩阵G

原理

有时间再补充。

注1：使用高斯消去法。如果Py不为单位阵，则说明进行了列置换，此时G不是系统形式。

注2：校验矩阵H必须是行满秩才存在对应的生成矩阵G，且生成矩阵G通常不唯一。

matlab实现：只做列置换，不做行置换

function [G, Px, Py] = Gaussian_Elimination_in_GFq(H, q)% initial[m, n] = size(H);H_stair = mod(H,q);Px = eye(m); Py = eye(n);for i=1:mfor j=i:nif gcd(H_stair(i,j), q) == 1break;elseif j==nerror('Gaussian_Elimination_in_GFq: The H is not full rank in GF(%d).',q);elsecontinue;endendendif j ~= iH_stair(:, [i, j]) = H_stair(:, [j, i]);Py(:, [i, j]) = Py(:, [j, i]);endendfor i=1:m[~, x, ~] = gcd(H_stair(i,i), q);inv_i = mod(x, q);H_stair(i, :) = mod(inv_i * H_stair(i, :), q);Px(i, :) = mod(inv_i * Px(i, :), q);for j=1:mif j~=i && H_stair(j,i)~=0factor=H_stair(j, i);H_stair(j, :) = mod(H_stair(j, :) - factor * H_stair(i, :), q);Px(j, :) = mod(Px(j, :) - factor * Px(i, :), q);endendendparity_matrix = mod((q-1).*H_stair(:,m+1:n),q);G_fixed=[parity_matrix',eye(n-m)];G=G_fixed*Py';
end

matlab实现：先做行置换，若无逆元，再做列置换

function [G, Px, Py] = Gaussian_Elimination_in_GFq(H, q)[m, n] = size(H);H_stair = mod(H,q);Px = eye(m); Py = eye(n);%% column findfor j=1:mfor i=j:mif gcd(H_stair(i,j), q) == 1break;elseif i==m%% row findfor k=j+1:nif gcd(H_stair(j,k), q) == 1break;elseif k==nerror('Gaussian_Elimination_in_GFq: The H is not full rank in GF(%d).',q);elsecontinue;endendend%% column exchangeH_stair(:,[j,k]) = H_stair(:,[k,j]);Py(:,[j,k]) = Py(:,[k,j]);i=j;break;elsecontinue;endendend%% row exchangeif i ~= jH_stair([j, i],:) = H_stair([i, j],:);Px([j, i],:) = Px([i, j],:);endendfor i=1:m[~, x, ~] = gcd(H_stair(i,i), q);inv_i = mod(x, q);H_stair(i, :) = mod(inv_i * H_stair(i, :), q);Px(i, :) = mod(inv_i * Px(i, :), q);for j=1:mif j~=i && H_stair(j,i)~=0factor=H_stair(j, i);H_stair(j, :) = mod(H_stair(j, :) - factor * H_stair(i, :), q);Px(j, :) = mod(Px(j, :) - factor * Px(i, :), q);endendendparity_matrix = mod((q-1).*H_stair(:,m+1:n),q);G_fixed=[parity_matrix',eye(n-m)];G=G_fixed*Py';end