Rellenado de una matriz con unos a partir de sus distribuciones
Publicado por Aitor (49 intervenciones) el 02/01/2017 12:32:02
Buenas tardes,
Primero de todo, ¡que tengáis todos un feliz año 2017!
Ayer estrené el año enfrentado a un par de problemillas de un trabajo que tengo. Seguramente os acabe preguntando por ambos, pero hoy me gustaría hacerlo sólo por el primero. Creo que es algo sencillo, pero por alguna razón se me atasca.
Voy a intentar explicarme.
Tenemos que rellenar una matriz con unos y ceros. Los datos que tenemos son sus dimensiones y la distribución de los unos tanto por filas como por columnas (en forma de vector, ya que ésta puede ser distinta para cada caso). Es decir, tenemos dos vectores, v y h, cuyos elementos se definen como:
v_i = elemento i-ésimo del vector v que indica la fracción de columnas de peso i (fracción de columnas sobre el total que contienen i unos)
h_i = elemento i-ésimo del vector h que indica la fracción de filas de peso i (fracción de filas sobre el total que contienen i unos).
El procedimiento que se lleva a cabo se conoce como algoritmo de MacKay Neal. Consiste en ir rellenando la matriz por columnas, de izquierda a derecha. Se va eligiendo el peso de cada columna a añadir para obtener una distribución de unos válida. La localización de los unos en cada fila se hace de forma aleatoria entre aquellas que no están todavía llenas.
A continuación os adjunto mi código. También podéis encontrar en este enlace (http://sigpromu.org/sarah/SJohnsonLDPCintro.pdf) el documento que estoy consultando para llevar a cabo esta parte de mi trabajo. Todo lo que os he comentado aparece mencionado en las páginas 10 y 11. El algoritmo en cuestión aparece implementado mediante pseudocódigo en la página 14.
NOTA: 'a' y 'b' se refieren respectivamente a las variables 'alpha' y 'beta' que se utilizan en el pseudocódigo del texto que os he adjuntado. Su valor, tal y como se ha definido, indica el número de unos por cada columna y por cada fila respectivamente.
En mi caso todo ha ido bien hasta el momento de realizar la resta "a = a - c" en la línea 20. Me he pasado toda la tarde ayer hecho un auténtico lío. Según tal y como aparece, me he planteado dos preguntas:
- ¿Por qué la resta es "a = a - c" y no "b = b - [una unidad en cada posición de c]"? Para mí tendría más sentido con respecto a lo que aparece en la explicación anterior.
- ¿Qué sucedería si al escoger un subconjunto de b para realizar la asignación posterior se cogieran dos elementos iguales? Es una situación completamente plausible, y en este caso no se añadirían a_i números sino menos.
Si alguien también puede arrojar alguna luz sobre el misterio de cómo resolver la última parte, la que hace alusión en pseudocódigo a la 'eliminación de ciclos de longitud 4' (simplemente se refiere a que en dos columnas no puede haber dos pares de bits ocupando exactamente las mismas posiciones), se lo agradecería por favor.
¿Alguno me puede ayudar por favor? Tengo la sensación de que el resultado es bastante sencillo, sin embargo, cada vez tengo más dudas. Ni siquiera sé si lo que llevo hasta aquí está bien...
Muchas gracias de antemano, y un abrazo.
Primero de todo, ¡que tengáis todos un feliz año 2017!
Ayer estrené el año enfrentado a un par de problemillas de un trabajo que tengo. Seguramente os acabe preguntando por ambos, pero hoy me gustaría hacerlo sólo por el primero. Creo que es algo sencillo, pero por alguna razón se me atasca.
Voy a intentar explicarme.
Tenemos que rellenar una matriz con unos y ceros. Los datos que tenemos son sus dimensiones y la distribución de los unos tanto por filas como por columnas (en forma de vector, ya que ésta puede ser distinta para cada caso). Es decir, tenemos dos vectores, v y h, cuyos elementos se definen como:
v_i = elemento i-ésimo del vector v que indica la fracción de columnas de peso i (fracción de columnas sobre el total que contienen i unos)
h_i = elemento i-ésimo del vector h que indica la fracción de filas de peso i (fracción de filas sobre el total que contienen i unos).
El procedimiento que se lleva a cabo se conoce como algoritmo de MacKay Neal. Consiste en ir rellenando la matriz por columnas, de izquierda a derecha. Se va eligiendo el peso de cada columna a añadir para obtener una distribución de unos válida. La localización de los unos en cada fila se hace de forma aleatoria entre aquellas que no están todavía llenas.
A continuación os adjunto mi código. También podéis encontrar en este enlace (http://sigpromu.org/sarah/SJohnsonLDPCintro.pdf) el documento que estoy consultando para llevar a cabo esta parte de mi trabajo. Todo lo que os he comentado aparece mencionado en las páginas 10 y 11. El algoritmo en cuestión aparece implementado mediante pseudocódigo en la página 14.
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
function H = MacKayNeal(N,r,v,h)
H = zeros(N*(1-r),N);
a = [];
for i=1:length(v)
for j=1:(v(i)*N)
a = [a,i];
end
end
b = [];
for i=1:length(h)
for j=1:(h(i)*(N*(1-r)))
b = [b,i];
end
end
for i=1:N
c = datasample(b,length(a(i)),'Replace',false);
for j=1:a(i)
H(c(j),i)=1;
end
a = a - c;
end
% while 1 % cycles removed
% for i=1:(N-1)
% for j=(i+1):N
% if 1 %
% end
% end
% end
% end
end
NOTA: 'a' y 'b' se refieren respectivamente a las variables 'alpha' y 'beta' que se utilizan en el pseudocódigo del texto que os he adjuntado. Su valor, tal y como se ha definido, indica el número de unos por cada columna y por cada fila respectivamente.
En mi caso todo ha ido bien hasta el momento de realizar la resta "a = a - c" en la línea 20. Me he pasado toda la tarde ayer hecho un auténtico lío. Según tal y como aparece, me he planteado dos preguntas:
- ¿Por qué la resta es "a = a - c" y no "b = b - [una unidad en cada posición de c]"? Para mí tendría más sentido con respecto a lo que aparece en la explicación anterior.
- ¿Qué sucedería si al escoger un subconjunto de b para realizar la asignación posterior se cogieran dos elementos iguales? Es una situación completamente plausible, y en este caso no se añadirían a_i números sino menos.
Si alguien también puede arrojar alguna luz sobre el misterio de cómo resolver la última parte, la que hace alusión en pseudocódigo a la 'eliminación de ciclos de longitud 4' (simplemente se refiere a que en dos columnas no puede haber dos pares de bits ocupando exactamente las mismas posiciones), se lo agradecería por favor.
¿Alguno me puede ayudar por favor? Tengo la sensación de que el resultado es bastante sencillo, sin embargo, cada vez tengo más dudas. Ni siquiera sé si lo que llevo hasta aquí está bien...
Muchas gracias de antemano, y un abrazo.
Valora esta pregunta
1
