原理

有時間再補充。

注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