原理
有时间再补充。
注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:m
for j=i:n
if gcd(H_stair(i,j), q) == 1
break;
else
if j==n
error('Gaussian_Elimination_in_GFq: The H is not full rank in GF(%d).',q);
else
continue;
end
end
end
if j ~= i
H_stair(:, [i, j]) = H_stair(:, [j, i]);
Py(:, [i, j]) = Py(:, [j, i]);
end
end
for 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:m
if j~=i && H_stair(j,i)~=0
factor=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);
end
end
end
parity_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 find
for j=1:m
for i=j:m
if gcd(H_stair(i,j), q) == 1
break;
else
if i==m
%% row find
for k=j+1:n
if gcd(H_stair(j,k), q) == 1
break;
else
if k==n
error('Gaussian_Elimination_in_GFq: The H is not full rank in GF(%d).',q);
else
continue;
end
end
end
%% column exchange
H_stair(:,[j,k]) = H_stair(:,[k,j]);
Py(:,[j,k]) = Py(:,[k,j]);
i=j;
break;
else
continue;
end
end
end
%% row exchange
if i ~= j
H_stair([j, i],:) = H_stair([i, j],:);
Px([j, i],:) = Px([i, j],:);
end
end
for 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:m
if j~=i && H_stair(j,i)~=0
factor=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);
end
end
end
parity_matrix = mod((q-1).*H_stair(:,m+1:n),q);
G_fixed=[parity_matrix',eye(n-m)];
G=G_fixed*Py';
end