Método de eliminación de Gauss-Jordan en matrices binarias
Publicado por Aitor (49 intervenciones) el 10/06/2017 10:21:53
¡Buenos días!
Necesito transformar una matriz de paridad binaria H (esto es, que sólo contiene unos y ceros) en otra patriz de paridad binaria sistemática Hsys de la siguiente forma:Hsys = [A | I]
Donde H y Hsys tienen la misma dimensión (n-k,n) e I es una matriz identidad de dimensión n-k.
Mi problema es que tras ejecutar el código que podéis encontrar debajo no consigo generar una matriz identidad de dimensión n-k. Os he adjuntado tres matrices con las que he trabajado a modo de ejemplo. Necesitaría que este código funcionase con matrices de cualquier dimensión (en la práctica necesito trabajar con dimensiones del orden de 51000 x 64000).
Aquí podéis encontrar la función que he encontrado en github. Es una versión modificada de la función 'rref' de Matlab adaptada para trabajar con matrices en GF(2). Si hubiera alguna forma más sencilla de hacer esto, ¡estaré encantado de conocerla!
Y aquí os pongo algunas de las matrices con las que he probado este código:
(La tercera matriz, de dimensión 50x100, podéis generarla con los archivos que os adjunto en el mensaje).
Un saludo a todos y muchas gracias de antemano por vuestra ayuda. ¡Que tengáis un buen fin de semana!
Necesito transformar una matriz de paridad binaria H (esto es, que sólo contiene unos y ceros) en otra patriz de paridad binaria sistemática Hsys de la siguiente forma:
Donde H y Hsys tienen la misma dimensión (n-k,n) e I es una matriz identidad de dimensión n-k.
Mi problema es que tras ejecutar el código que podéis encontrar debajo no consigo generar una matriz identidad de dimensión n-k. Os he adjuntado tres matrices con las que he trabajado a modo de ejemplo. Necesitaría que este código funcionase con matrices de cualquier dimensión (en la práctica necesito trabajar con dimensiones del orden de 51000 x 64000).
Aquí podéis encontrar la función que he encontrado en github. Es una versión modificada de la función 'rref' de Matlab adaptada para trabajar con matrices en GF(2). Si hubiera alguna forma más sencilla de hacer esto, ¡estaré encantado de conocerla!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
% This is a modified version of matlab's building rref which calculates
% row-reduced echelon form in gf(2). Useful for linear codes.
% Tolerance was removed because yolo, and because all values
% should only be 0 or 1. @benathon
function [A] = g2rref(A)
%G2RREF Reduced row echelon form in gf(2).
% R = RREF(A) produces the reduced row echelon form of A in gf(2).
%
% Class support for input A:
% float: with values 0 or 1
% Copyright 1984-2005 The MathWorks, Inc.
% $Revision: 5.9.4.3 $ $Date: 2006/01/18 21:58:54 $
[m,n] = size(A);
% Loop over the entire matrix.
i = 1;
j = 1;
while (i <= m) && (j <= n)
% Find value and index of largest element in the remainder of column j.
k = find(A(i:m,j),1) + i - 1;
% Swap i-th and k-th rows.
A([i k],j:n) = A([k i],j:n);
% Save the right hand side of the pivot row
aijn = A(i,j:n);
% Column we're looking at
col = A(1:m,j);
% Never Xor the pivot row against itself
col(i) = 0;
% This builds an matrix of bits to flip
flip = col*aijn;
% Xor the right hand side of the pivot row with all the other rows
A(1:m,j:n) = xor( A(1:m,j:n), flip );
i = i + 1;
j = j + 1;
end
Y aquí os pongo algunas de las matrices con las que he probado este código:
1
2
3
4
5
6
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]; % Funciona
H=[1 0 1 1 0; 0 0 1 0 1; 1 0 0 1 0; 1 0 1 1 1]; % No funciona
(La tercera matriz, de dimensión 50x100, podéis generarla con los archivos que os adjunto en el mensaje).
Un saludo a todos y muchas gracias de antemano por vuestra ayuda. ¡Que tengáis un buen fin de semana!
- ParityCheckMatrixGen.zip(1,0 KB)
Valora esta pregunta
0