jueves, 9 de mayo de 2013

Hamming Code

Encoding and decoding with the Hamming Code

Hola a todos mis compañeros y gente que visita el blog, esta entrada trata sobre la detección de errores en la transmisión de datos, mediante Hamming Code.

En los protocolos de comunicación, como RS232, es muy común observar el uso de bits de paridad, los bits de paridad (0 o 1) nos sirven en un sistema para realizar detección de errores en una transmisión. Existen diversos motivos por los que puede haber un error en una transmisión, ya sea que se pierda el control de flujo de información, que la transmisión de datos sea intermitente, problemas de congestión, etc. Es por eso que un bloque de bits se transmite con una paridad específica, con la intención de encontrar errores en una transmisión.


Bien, en nuestro caso encontraremos estos errores mediante Hamming Code, a continuación explico el proceso a detalle.
Los pilares que considero en Hamming Code son: 

1 - Multiplicación de matrices. 

2 - Aritmética de módulo 2

Se dice aritmética de módulo 2 porque solamente se emplean 2 dígitos para representar este sistema numérico, básicamente es lenguaje binario; la aritmética es porque vamos a realizar operaciones de adición y multiplicación.

La adición de módulo 2 se realiza de la siguiente manera (noten que es un XOR):

0+0 = 0
0+1 = 1
1+0 = 0
1+1 = 1

Mientras que la multiplicación de módulo 2 se realiza de la siguiente manera (noten que es el operador lógico AND):

0+0 = 0
0+1 = 0
1+0 = 0
1+1 = 1

3 - Paridad

La ya mencionada paridad se presenta en 2 sabores; paridad par y paridad impar. Una cadena de bits tiene una paridad par si contiene un número par de 1 (la suma número 2 de los bits es 0), de lo contrario tiene paridad impar (la suma número 2 de los bits es 1).

Codificación

Los códigos de Hamming tradicionales son códigos (7, 4). Esto quiere decir que codifica 4 bits de datos en siete bloques de bits, como podrán imaginarse, los bits "extra" del bloque, son bits de paridad (todos los bits de paridad son paridad par).

Supongamos que tenemos los bits de datos: d1, d2, d3 y d4.
Podemos obtener nuestros bits de paridad de la siguiente manera:

p1 = d2+d3+d4
p2 = d1+d3+d4
p3 = d1+d2+d4

La operación para obtener los bits de paridad es un XOR, como lo vimos anteriormente, por ejemplo si tenemos un bloque de bits de datos = 0110, el procedimiento para obtener p1 es:

p1 = d2 + d3 + d4 = p1 = 1+1+0 = p1 = 0

Luego p2 es: 0+1+0 = 1
Luego p3 es: 0+1+0 = 1

De manera que nuestro bloque de bits, más nuestros 3 bits de paridad quedan así:  "0110011"

Lo siguiente que vamos a hacer es generar una matriz "G" de 4x7.  Esto lo hacemos con la intención de transformar nuestra cadena de bits (4 bits) en un código Hamming de 7 bits (en una palabra: codificar).
Seguido a esto, vamos a definir los 4 vectores de bits de datos, vamos a llamarlos d1,d2,d3 y d4

d1 = [1 0 0 0]
d2 = [0 1 0 0]
d3 = [0 0 1 0]
d4 = [0 0 0 1]

Ya que los definí, ahora vamos a obtener nuestros vectores pero ahora de bits de paridad, para obtenerlos solo tenemos que recurrir a las ecuaciones antes mencionadas:

p1 = d2+d3+d4
p2 = d1+d3+d4
p3 = d1+d2+d4

Quedando de la siguiente manera nuestros vectores de bits de paridad:


p1 = [0 1 1 1]
p2 = [1 0 1 1]
p3 = [1 1 0 1]

Ahora que contamos con los vectores de bits de datos y los vectores de bits de paridad, voy a formar la matriz generadora "G". Para formar la matriz G es muy sencillo, solo se tienen que acomodar los vectores anteriores en el siguiente orden [p1, p2, p3, d1, d2, d3, d4]; es decir, primero los vectores de bits de paridad, luego los vectores de bits de datos.
Me queda una matriz como la siguiente:


     p1  p2  p3  d1  d2  d3  d4
     ---------------------------
    |                          |
    |0   1   1   1   0   0   0 |  
G = |1   0   1   0   1   0   0 |
    |1   1   0   0   0   1   0 |
    |1   1   1   0   0   0   1 |
    |                          |

Bien, ya tenemos lo necesario para codificar, tomemos de ejemplo la cadena de bits "1010", vamos a codificarla con nuestro generador, lo que tenemos que hacer es multiplicar nuestro vector [1010] por el generador[G] que acabamos de hacer (por eso mencioné anteriormente que uno de los pilares para la codificación Hamming es la multiplicación de matrices).


            |                          |
            |0   1   1   1   0   0   0 |  
|1 0 1 0| X |1   0   1   0   1   0   0 | = | 1 0 1 1 0 1 0 |
            |1   1   0   0   0   1   0 |
            |1   1   1   0   0   0   1 |
            |                          |

Así pués, tenemos el código Hamming: "1011010" de la cadena "1010", con esto podemos concluir que la codificación dependerá de la matriz generadora que hagamos.

Implementé en python el proceso de "encoding", el código es el siguiente:


Decodificación

El primer paso para la decodificación es comprobar los bits de paridad para ver si existe algún error. Si suponemos que en vez de la cadena "1011010" que recibimos anteriormente con la matriz generadora, hubieramos recibido esta otra "1011011". Los bits de paridad podríamos obtenerlos de forma aritmética con las ecuaciones ya antes mencionadas:
p1 = d2 + d3 + d4 = 0 + 1 + 1 = 0
p2 = d1 + d3 + d4 = 1 + 1 + 1 = 1
p3 = d1 + d2 + d4 = 1 + 0 + 1 = 0


Y si sabemos que los bits de paridad de nuestra cadena son los primeros 3, tenemos que "101" y "010" son todo lo contrario, osea cada bit de paridad resultante es erróneo.

A continuación vamos a construir una matriz de verificación de paridad (de 3x7), precisamente para verificar los posibles errores en la transmisión. La matriz H está dada por:


            |                          |
            |1   0   0   0   1   1   1 |  
       H =  |0   1   0   1   0   1   1 | 
            |0   0   1   1   1   0   1 |
            |                          |

Existe una matriz llamada "síndrome" que es la que nos da el resultado si existen o no errores en la codificación. Existen 2 propiedades de la matriz "síndrome", si los valores de la matriz "síndrome" son todos ceros significa que los datos codificados están libre de errores.

Para obtener nuestra matriz "síndrome", tan solo tenemos que la matriz H por nuestro código obtendido en el proceso anteriormente abordado.

No alcancé a implementar la parte de decodificación, pero intentaré terminar la entrada porque la actividad me pareció interesante.
Por mi parte es todo.

Liga a mi git: https://github.com/eddypre/M-todosCodificaci-n

Bibliografía

http://en.wikipedia.org/wiki/Parity-check_matrix
http://michael.dipperstein.com/hamming/#example2
http://elisa.dyndns-web.com/~elisa/teaching/comp/info/correct.pdf

Cualquier duda o aclaración pueden dejarla en la caja de comentarios. 

Saludos a todos!

jueves, 25 de abril de 2013

Métodos adaptativos

Métodos adaptativos de compresión

Hola, esta entrada trata sobre los métodos adaptativos de compresión de datos, para esta actividad se nos encargó inventar, implementar y evaluar nuestro propio método adaptativo de compresión.

Como ya lo había comentado en mi post anterior (no está de más); la compresión de información es el proceso de codificar de una manera efectiva con el objetivo de reducir el número de bits necesarios para representar cierta información.

En la tarea pasada vimos un algoritmo que cumple con las tareas antes mencionadas, pero esta vez se nos pidió desarrollar un método de compresión dinámico o adaptativo.

Esto quiere decir que no hay un cálculo de frecuencia de los símbolos usados (como la pasada tarea en codificación de Huffman), estos métodos adaptativos son principalmente usados en el streaming de información ya que se adaptan a los cambios que se localizan en las características de los datos.

Debo mencionar que a mi no se me ocurrió ningún algoritmo donde pudiera implementar este tipo de método, sin embargo; en previas lecturas cuando realicé la tarea anterior (Huffman) conocí algunos tipos de compresión adaptativos, por ejemplo el LZW (Lempel-Ziv-Welsh) que es un sistema adaptativo del LZ (de Lempel y Jacob Ziv).

Con el sistema LZW es posible crear "al vuelo" y en una sola pasada un diccionario de cadenas que se encuentren dentro del texto a comprimir mientras al mismo tiempo se procede a su codificación.

Para explicar de una manera práctica este método podemos comenzar con un diccionario de 3 caracteres, cada uno con una codificación del 1 al 3.


Tomemos de entrada la siguiente cadena: ABABBABCABABBA
 El algoritmo de compresión LZW hace lo siguiente:

Toma el primer caracter de entrada (s), luego toma el que le sigue(c), la salida (output), que será el código que representará a la cadena original, será el equivalente al valor del código que tiene el caracter s en nuestro diccionario, luego el código para nuestro nuevo string va aumentando una unidad y el nuevo string se guarda en nuestro diccionario (junto con su valor de código) para poder contar con patrones que luego se puedan repetir. El método hace lo mismo hasta que el contenido de nuestro mensaje sea nulo.

Para la descompresión podemos pintar una tabla similar, porque prácticamente se sigue el mismo proceso:


Noten que ahora la columna de output es la cadena original que introducimos.
Bien, yo codifiqué en python este método:

En algunas de las notas que leí, mencionan que la relación de compresión de este método es de aproximadamente de un tercio del archivo; también mencionan que se utiliza en formatos universales como el GIF o el TIFF.

Yo realicé unas sencillas pruebas midiendo la proporción de compresión:

Prueba 1


Prueba 2





Prueba 3




Prueba 4



Conclusiones

Bueno, como lo mencioné antes, en algunas notas mencionan que la relación de compresión es de aproximádamente un tercio del archivo. En mis pruebas lo máximo que obtuve fue comprimir a más de la mitad y seguía conforme iba aumentando el largo del mensaje original.

Una de las desventajas es que hay que agregar al diccionario los caracteres que vas a usar, y haciendo un diagnóstico más detallado nos podemos dar cuenta que muchos de los caracteres que agregamos ni siquiera se usan, ocupando demasiada memoria de una manera inecesaria en el diccionario.
 

Cualquier duda o aclaración pueden ponerla en los comentarios. 

Saludos a todos!


jueves, 11 de abril de 2013

Algoritmo de Huffman

Algoritmo de Huffman 

Hola en esta entrada hablaré sobre el algoritmo de Huffman, este algoritmo se usa precisamente para construir códigos de Huffman, lo que hace es tomar un alfabeto de n símbolos, también toma las frecuencias para cada símbolo, luego produce un código de Huffman con estos elementos.

El objetivo de construir códigos de Huffman es el de la compresión de datos, es decir, expresar de una manera distinta (más corta, obviamente) la misma información.


A continuación explicaré a detalle el funcionamiento del algoritmo.

Vamos a obtener el código de Huffman de la palabra: "ingeniero".
Lo primero a realizar es obtener las frecuencias de cada elemento de la sentencia, es decir, las veces que aparece cada caracter en nuestra palabra u oración, dependiendo el caso.

En nuestro caso quedaría de la siguiente manera.

Lo siguiente es ordenar estos caracteres en función a las frecuencias obtenidas, de menor a mayor y dejándo solo el caracter con su correspondiente frecuencia, quedaría de la siguiente manera.



Lo siguiente es la construcción de un árbol binario mediante la unión de nodos que contienen el caracter y su respectiva frecuencia, los nodos que tenemos hasta ahorita son los siguientes.


Ahora lo que toca hacer es ir uniendo los nodos consecutivos en pares, sumaremos las frecuencias de esos dos nodos y luego con ellos crearemos un nuevo nodo. El nuevo nodo contendrá un caracter "null", seguido de la frecuencia obtenida al sumar las 2 frecuencias de los nodos con que se formó. Para entender mejor el concepto realizaremos este paso con los primeros 2 nodos de nuestro conjunto. El resultado es el siguiente.




Noten que ahora el inicio es de nuestra lista es otro, ahora está al inicio el tercer nodo que teníamos en nuestra lista anterior, los nodos que retiramos ahora se encuentran dentro del nuevo nodo que formamos con la suma de sus respectivas frecuencias. El nuevo nodo es colocado al final de la lista.

Ahora, si seguimos el mismo procedimiento podemos concluir que obtendremos un árbol binario, donde las hojas del mismo serán los caracteres de nuestra palabra. Al seguir realizando el mismo procedimiento obtendremos lo siguiente.


Luego.




Hacemos el mismo procedimiento con los nodos nuevos, se crea un nodo nuevo con la suma de las frecuencias, y le antecede un null.



Al final queda un árbol binario de la siguiente manera.



Lo siguiente es asignar ceros y unos a las ramas del árbol, las de la izquierda serán ceros, mientras que las de la derecha serán unos.



Mediante esta asignación de números podemos determinar el camino para llegar al caracter deseado, por ejemplo si queremos llegar a n, el recorrido es 00, mientras que para e, el recorrido es 01. Podemos hacer lo mismo para obtener el código de las demás letras de nuestra palabra, a continuación muestro una tabla con los caracteres, su frecuencia y su código de Huffman correspondiente a esta palabra.





Yo implementé el algoritmo de Huffman en python, el siguiente es el código fuente:


'''
    Algoritmo de Huffman
    Compresion de datos
'''
def huff():
 text = raw_input("Put your text: ")
 let = dict()
 large1 = len(text)
 for i in range (large1):
     if text[i] in let:
  let[text[i]] += 1
     else:
  let[text[i]] = 1
 k = let.items()

 large2 = len(k)
 for i in range(large2):
     men = k[i][1] #menor
     for j in range(len(k)):
  if k[j][1] > men:
      men,let2 = k[j][1],k[j][0]
      a,b = k[i][1],k[i][0]
      k[j] = (b,a)
      k[i] = (let2,men)         
 num = [] 
 lett = []             
 comb = [] 

 for i in range(len(k)):
     num.append(k[i][1])
     lett.append(k[i][0])
     comb.append((k[i][0],0,0))
 tam = 0 

 #Finish - tree
 size = len(num)

 while (len(num) > 1):
     m = num[0] # 
     z = 0
     a = lett[0]
     for i in range(len(num)):
  if num[i] < m:
      m = num[i]
      a = lett[i]
      z = i        
     lett.pop(z)        
     num.pop(z)
     mini = num[0] 
     j = 0
     b = lett[0]
     for i in range(len(num)):
  if num[i] < mini:
      mini = num[i]
      b = lett[i]
      j = i
     add = m + mini
     lett[j] = tam
     num[j] = add
     comb.append((tam,0,0))
     if m >= mini:
  counter = 1 
  con = 0
     else:
  counter = 0
  con = 1
     for q in range(len(comb)):
  if comb[q][0] == a:
      comb[q] = (a,counter,tam)
  if comb[q][0] == b:    
      comb[q] = (b,con,tam)
     tam += 1

 #Finish1

 num = [] #
 leng = len(comb)
 last = comb[leng-1][0]
 k = 0
 for i in range(size):
     num.append([])
     a,b,c = comb[i]
     num[i].append(str(b))
     q = i
     cont = 0
     while(q <= leng-2): 
  if(comb[q][0] == c):
      c = comb[q][2]
      num[i].append(str(comb[q][1]))
      cont = c
      if cont == last:
          break
  q += 1
     num[i] =num[i][::-1]
 #Finish2-
 code = [] 
 for i in range(len(text)):
     last = 0
     while (last <= size):
  if comb[last][0] == text[i]:
      break
  last += 1
     cads = "".join(num[last])
     code.append((cads))

 #print "Code: ",code
 new = []

 for i in range(len(code)):
     new.append(str(code[i]))
 new = "".join(new)
 cal = []
 j, k, i, l = 0,0,0,0 #another
 temp = []
 while(i < len(new)):
     l = 1
     j = 0
     while(j < len(num) ):
  k = 0
  if new[i] == num[j][k]:
      k += 1
      if len(num[j]) == k:
          l = k
          temp.append(comb[j][0])
      while (k < len(num[j])):
          if new[i+k] == num[j][k]:
              k += 1
              if k == len(num[j]):
                  temp.append(comb[j][0])
                  l = k
          else:
              k = len(num[j])        
  j += 1
     i += l
 lenew = len(new)
 trans = "".join(temp)
 print "Binary: ",new
 #print "Code: ",code
 print "Translate: ",trans

 print "\nLength of text: ", large1
 print "In bytes: ", large1

 bytecomp = float(lenew/8.0)
 print "Bytes affter compression: ", bytecomp 
 print "Relation: ", float(large1/bytecomp)

if __name__ == '__main__':
 huff()



Y este es el resultado de la ejecución del script.

Para "hello huffman":


Para "arsenal fc"




Para "Facultad de Ingenieria Mecanica y Electrica"






Para medir la efectividad de compresión de datos por el algoritmo de Huffman partimos de la idea de la equivalencia de un caracter y un byte, es decir el largo de caracteres de la cadena introducida será el valor de bytes de la misma, seguido de eso podemos obtener el valor de bytes después de la compresión, dividiendo la cadena binaria obtenida entre 8.
Por último imprimí también la relación entre la entrada y salida, quedando los resultados de la siguiente manera:


El resultado es una compresión de cerca del doble.
Veamos ahora con cadenas más largas.


Podemos observar nuevamente que la relación es cercana al doble, tomando en cuenta que existe un mayor número de caracteres.
Es todo por esta entrada. Cualquier duda o aclaración pueden dejarla en comentarios. 

Bibliografía:


http://www.alegsa.com.ar/Diccionario/C/1048.php
https://www.youtube.com/watch?v=8Gf8wutvS1w


Liga hacia mi git: https://github.com/eddypre/M-todosCodificaci-n

Saludos!


miércoles, 20 de febrero de 2013

Tarea 2

Tarea 2 - String matching

Hola, esta actividad consiste en realizar un programa en python sobre el tema de string matching. String matching son las coincidencias u ocurrencias de palabras (no necesariamente palabras) en una cadena de texto (no necesariamente de texto XD).

El escenario es el siguiente:

Dada una cadena de texto (T), y una cadena patrón (P), vamos a encontrar las ocurrencias presentadas. Por ejemplo:

T = (issttstsisitstsisitstttits)
P = (its)
Vamos a encontrar las veces que se hace un match, en el ejemplo anterior tendriamos 3 matches.

Los algoritmos que usaremos para la búsqueda de cadenas serán el de Boyer-Moore y el de Knuth-Morris-Pratt.
A continuación explicaré el funcionamiento del algoritmo Boyer-Moore

Boyer-Moore

El algoritmo Boyer-Moore es un algoritmo de búsqueda de cadenas desarrollado por Bob Boyer y J Strother Moore en 1977. Lo que este algoritmo hace es buscar la coincidencia del último elemento de la cadena patrón con un elemento cualquiera de una cadena de texto; por ejemplo si la cadena patrón es 'a,b,c' y la cadena de texto es 'ccbacababca', el algoritmo realiza una comparación entre c (último elemento de la cadena patrón) y la cadena de texto. En caso de que ocurra una coincidencia, ahora se comparará la penúltima posición de la cadena patrón con la ocurrencia en la cadena de texto-1. Luego si también hay concidencia se compara la antepenúltima posición de la cadena patrón con la posición de la cadena de texto-2 y así sucesivamente, lo que provoca un buen ahorro de tiempo en ejecución debido a que no tiene . En conclusión y resumidas cuentas, el algoritmo hace una verificación hacia atrás.


Yo realicé el código en python de manera sencilla, lo que hice fue iterar el recorrido de toda la cadena de texto, luego cuando enontraba match de una letra de la cadena con la última posición de la cadena patrón, tomaba una sub cadena de la cadena de texto, donde esa subcadena se compone de la letra match más las posiciones anteriores correspondientes a la cadena patrón, al final comparé la subcadena con la cadena patrón. Si la comparación arroja un "True" pues cuento un match. Y así hasta recorrer toda la cadena de texto.

A continuación el código:

import random 
from sys import argv
import string
import time

def boyer(largoM, largoN):

 #Para m = largo de texto, n = largo de patron
 archi=open('BM.dat','a') #Abro el archivo
 #largoM = int(argv[1]) 
 #largoN = int(argv[2])
 newporcent = 0.0
 M = []
 N = []
 com = []
 # Llenando listas ------------------------------------
 for i in range(largoM):
  let = random.choice(string.ascii_lowercase)
  M.append(let) #Rellenando la cadena de texto
  
 for j in range(largoN):
  let = random.choice(string.ascii_lowercase)
  N.append(let) #Rellenando el patron
 #print M
 #print N, "\n\n"

 # Algoritmo Boyer-Moore -------------------------------
 tiempoInicial = time.time()

 for x in range(largoM):
  if x >= largoN:
   if M[x] == N[-1]:
    miLargo = (x)-(largoN-1)
    com = M[miLargo:x+1]
    #print "i = ",x,  "  -  M[x] = ", M[x], " - com = ", com     
    print com
    if com == N:
     print "match: com = ", com, " - N = ", N 
     
    else:
     print "No exito :("

 tiempoFinal = time.time()
 d = tiempoFinal - tiempoInicial
 diferencia = round(d, 6) 
 
 newlargoM = str(largoM)
 newlargoN = str(largoN)   #Para poder meter los datos al dat
 newdiferencia = str(diferencia)
   
 if largoN != 10:  # Cuando el largo del patron es 9, saltamos 2 lineas en el dat
  archi.write(newlargoM) #Escribe largo de texto
  archi.write(' ')
  archi.write(newlargoN) # Escribiendo largo del patron 
  archi.write(' ')
  archi.write(newdiferencia) #Escribiendo los promedios de tiempo
  archi.write('\n')

 else:
  archi.write(newlargoM) #Lo mismo que arriba
  archi.write(' ')
  archi.write(newlargoN)
  archi.write(' ')  
  archi.write(newdiferencia)
  archi.write('\n\n')
 
 archi.close()   # Cerrando el archivo, se abre cada vez que se ejecuta esta subrutina

 
def main():
  for i in range(10): #Correr distintos tipos de largo de texto
   for j in range(10): #Correr distintos tipos de largo de patron  
    print "\nTransmitiendo con largo de texto = ", i+1, "y con patron = ", j+1      # Meramente informativo para el programador
    boyer(i+1, j+1) 
  

if __name__ == "__main__":
 main() 




Para poder graficar los tiempos hice que en un dat se fueran guardando los largos de cadena de texto y largos de cadena patrón, luego obtuve los tiempos para cada combinación. Al final realicé un plot con los datos obtenidos (como en la tarea anterior):

A continuación los datos obtenidos (en primera columna los largos de M ó largos de texto, en segunda columna los largos de N o patrón, y al final los tiempos obtenidos):



1 1 3e-06
1 2 3e-06
1 3 2e-06
1 4 3e-06
1 5 2e-06
1 6 2e-06
1 7 3e-06
1 8 2e-06
1 9 1e-06
1 10 2e-06

2 1 3e-06
2 2 2e-06
2 3 2e-06
2 4 2e-06
2 5 2e-06
2 6 2e-06
2 7 2e-06
2 8 2e-06
2 9 3e-06
2 10 2e-06

3 1 3e-06
3 2 2e-06
3 3 3e-06
3 4 2e-06
3 5 3e-06
3 6 2e-06
3 7 2e-06
3 8 3e-06
3 9 3e-06
3 10 2e-06

4 1 2e-06
4 2 2e-06
4 3 2e-06
4 4 2e-06
4 5 2e-06
4 6 3e-06
4 7 2e-06
4 8 2e-06
4 9 2e-06
4 10 2e-06

5 1 2e-06
5 2 3e-06
5 3 3e-06
5 4 2e-06
5 5 2e-06
5 6 2e-06
5 7 2e-06
5 8 2e-06
5 9 2e-06
5 10 2e-06

6 1 5.4e-05
6 2 4e-06
6 3 4.3e-05
6 4 2e-06
6 5 2e-06
6 6 2e-06
6 7 2e-06
6 8 2e-06
6 9 2e-06
6 10 2e-06

7 1 4.5e-05
7 2 2e-06
7 3 3e-06
7 4 2e-06
7 5 3e-06
7 6 2e-06
7 7 3e-06
7 8 2e-06
7 9 2e-06
7 10 1e-06

8 1 2e-06
8 2 1.8e-05
8 3 2e-06
8 4 1.8e-05
8 5 1.9e-05
8 6 1.8e-05
8 7 2e-06
8 8 1e-06
8 9 2e-06
8 10 2e-06

9 1 2e-06
9 2 2e-06
9 3 2e-06
9 4 1.9e-05
9 5 2e-06
9 6 2e-06
9 7 1e-06
9 8 2e-06
9 9 1e-06
9 10 2e-06

10 1 3e-06
10 2 2e-06
10 3 3e-06
10 4 2e-06
10 5 2e-06
10 6 2e-06
10 7 2e-06
10 8 2e-06
10 9 2e-06
10 10 2e-06


 
A continuación la gráfica obtenida:


Los resultados son tiempos bastante cortos y aceptables, donde es más tardado con largos 6 y 8 de texto y patrón respectivamente.

En la siguiente liga   se menciona más a detalle el funcionamiento de este algoritmo.

Quedo pendiente con el algoritmo Knuth-Morris-Pratt por falta de tiempo. 

Liga a mi git (se encuetra el archivo py, dat y el plot): https://github.com/eddypre/M-todosCodificaci-n

Bibliografía:

http://banyut.obolog.com/python-listas-115312
http://techerald.com/page/python-generacin-cadena-aleatoria-de-letras-maysculas-y-cifras.html

Cualquier duda o aclaración pueden dejarla en comentarios.

Saludos para todos!

jueves, 14 de febrero de 2013

Tarea 1

Tarea 1 - Transmisor de palabras

Hola, para esta primera tarea de la materia de métodos de transmisión se nos pidió realizar en python un programa generador y transmisor de palabras, la idea es que determináramos el porcentaje de éxito con el que se mandaban las palabras, es decir tiene que haber un match entre la palabra generada y la palabra transmitida. Y las palabras generadas y transmitidas se componen de cadenas binarias (0 y 1)
Para obtener los porcentajes de éxito debemos primero darle parámetros a nuestro transmisor, los parámetros con los que el generador/transmisor trabaja son:

- Largo de la palabra
- Frecuencia de ceros
- Porcentaje de ceros correctos
- Porcentaje de unos correctos  

El proceso que sigue mi transmisor es el siguiente:

El generador produce palabras de largo 2^0, 2^1, 2^2 ... 2^9, luego realiza el proceso de transmisión con frecuencias de cero de 0.1%, 0.2% ... 0.9% (obviando que las frecuencias de 1 es 1-frecuencia de ceros), los porcentajes de ceros y unos correctos se definen como parámetros al ejecutar el programa. Seguido de eso se empiezan a transmitir las palabras, luego se comparan las palabras generadas con las palabras transmitidas. Al final se obtienen porcentajes de éxito.

Todos estos valores antes mencionados se van grabando en un archivo .dat para luego ser graficados en un gnuplot y ser analizados más fácilmente.

A continuación les dejo con el código que realicé (generador y transmisor).

Parte del generador:

#Generador y transmisor de palabras
#Autor: Eduardo Triana
#FIME - ITS

import random 
from sys import argv

def generador(l, cer): #Generador y transmisor de palabras
 
 #freqzero = 0
 freqzero = (cer/10.0) + 0.1  
 
 #z = 1
 #for a in range(9):
 archi=open('canalTriana.dat','a') #Abro el archivo donde se almacenaran todas las probabilidades de exito, junto con los largos y frecuencias
 #length = int(argv[1])
 length = pow(2,l) #El largo del archivo lo elevamos a la "l", necesito l para generar el dat
 
 #freqzero = float(argv[1]) Esto ya va arriba, y ya no es con parametro
 zerocorrect = float(argv[1])
 onecorrect = float(argv[2]) # El orden de parametros por consola es: 1) Porcentaje de ceros correctos. 2) Porcentaje de unos correctos. 3) Repeticiones
 repet = int(argv[3])

 conteo0 = 0
 conteo1 = 0

 freqzeroProduct = freqzero*length
 listaG = []
  
 for i in range(length): #Todo esto es para generar cada una de las palabras
  bit = int(random.randint(0,1))
  if bit == 0:  
   if freqzeroProduct > conteo0: #Agregando los bits para formar las cadenas de palabras
    listaG.append(0)
    conteo0 = conteo0 + 1
   else:
    listaG.append(1)
  else:
   listaG.append(1)
 print "Generated:  " ,listaG  #Imprimiendo la palabra generada



Parte del transmisor:

#Transmision de palabras
 
 zerocorrect = zerocorrect*length  
 onecorrect = onecorrect*length    
 exitos = 0.0
 #print "zerocorrect:", zerocorrect
 #print "onecorrect: ", onecorrect, "\n"

 # Todo lo que sigue corresponde a la transmision de las palabras

 for j in range(repet):
  conteo0 = 0
  contCorr0 = 0
  contCorr1 = 0
  listaT = []
  for k in range(length):
   bitransmited = int(random.randint(0,1))
   if bitransmited == 0:  
    if freqzeroProduct > conteo0:
     if zerocorrect > contCorr0:
      listaT.append(0)  #Esto es para que la frecuencia de ceros corresponda a la que indicamos
      conteo0 = conteo0 + 1
      contCorr0 = contCorr0 + 1
     else:
      listaT.append(1)
      contCorr1 = contCorr1 + 1
    else:
      listaT.append(1)
   else:
    if onecorrect > contCorr1:
     listaT.append(1)
     contCorr1 = contCorr1 + 1  #Si ya rebasamos el limite de ceros creados, ahora ponemos unos
    else:
     listaT.append(0)
     contCorr0 = contCorr0 + 1
  if listaT == listaG:  #Comparamos el contenido de las listas de palabras transmitidas con las generadas
   exitos = exitos + 1 #Elevamos en 1 el exito obtenido
  print "Transmited: ", listaT
 porcent = (exitos/repet) #Creamos el porcentaje de exito, esto sera la columna 3 de nuestro archivo dat, es lo mero mero
 print "\n", repet
 print exitos 
 print porcent
 
 newl = str(l)    #
 newfreqzero = str(freqzero)  # Convirtiendo a string todos los datos para poder escribirlos en nuestro dat
 newporcent = str(porcent)  #
   
 if cer != 8:    # Cuando la frecuencia de ceros ya sea 0.9, saltamos 2 lineas en el dat
  archi.write(newl)
  archi.write(' ')
  archi.write(newfreqzero) # Escribiendo en el dat 
  archi.write(' ')
  archi.write(newporcent)
  archi.write('\n')

 else:
  archi.write(newl)
  archi.write(' ')
  archi.write(newfreqzero)
  archi.write(' ')  #Escribiendo en el dat
  archi.write(newporcent)
  archi.write('\n\n')
 
 archi.close()   # Cerrando el archivo, se abre cada vez que se ejecuta esta subrutina




Llamando a la función que genera/transmite con largo de palabras desde potencia 0,1,2 hasta 9, y con valores de frecuencias de 0 desde 0.1, 0.2 hasta 0.9:

def main():

 for i in range(10):  #Para poder correr el transmisor con potencias desde 0 hasta la 9
  for j in range(9): #Para poder correr el transmisor con frecuencias de zero desde 0.1 hasta 0.9  
   print "\nTransmitiendo con largo = ", i, "y con freqzero = ", j      # Meramente informativo para el programador
   generador(i, j) #Correr el generador/transmisor con largos y frecuencias distintas

 #i = 1
 #while i <= 512:
  #generador(i)
 # i = i*2

if __name__ == "__main__":
 main()



Ejecutando mi generador/transmisor con los parámetros 0.8 y 0.8 20, que corresponden a la porcentaje de ceros correctos, unos correctos y repeticiones(esto es las veces con las que se promedia el experimento, es decir, se transmite 20 veces las palabras y se obtiene un promedio de éxito, decidí que lo pusiera como parametro el usuario para tener escenarios más amplios):



Algo de lo que se ve cuando se está ejecutando el transmisor, son las palabras generadas y transmitidas, esto lo hace para cada iteración de largo de palabras (esto no es tan relevante).




Ahora les muestro el archivo dat obtenido:

Esto es el archivo dat resultante con valores 0.8, 0.8 y 20, que corresponde a porcentajes de cero correctos, unos correctos y repeticiones respectivamente. Va con largos de palabra desde potencia 0 hasta 9 (con base 2, primera columna) y frecuencias desde 0.1 hasta 0.9 (segunda columna), la tercera columna corresponde a los porcentajes de éxito.




0 0.1 0.55
0 0.2 0.45
0 0.3 0.45
0 0.4 0.6
0 0.5 0.5
0 0.6 0.7
0 0.7 0.5
0 0.8 0.35
0 0.9 0.55

1 0.1 0.55
1 0.2 0.15
1 0.3 0.35
1 0.4 0.5
1 0.5 0.4
1 0.6 0.2
1 0.7 0.05
1 0.8 0.35
1 0.9 0.25

2 0.1 0.1
2 0.2 0.3
2 0.3 0.35
2 0.4 0.0
2 0.5 0.0
2 0.6 0.05
2 0.7 0.1
2 0.8 0.1
2 0.9 0.05

3 0.1 0.45
3 0.2 0.0
3 0.3 0.0
3 0.4 0.0
3 0.5 0.0
3 0.6 0.0
3 0.7 0.0
3 0.8 0.0
3 0.9 0.0

4 0.1 0.25
4 0.2 0.0
4 0.3 0.0
4 0.4 0.0
4 0.5 0.0
4 0.6 0.0
4 0.7 0.0
4 0.8 0.0
4 0.9 0.0

5 0.1 0.0
5 0.2 0.0
5 0.3 0.0
5 0.4 0.0
5 0.5 0.0
5 0.6 0.0
5 0.7 0.0
5 0.8 0.0
5 0.9 0.0

6 0.1 0.0
6 0.2 0.0
6 0.3 0.0
6 0.4 0.0
6 0.5 0.0
6 0.6 0.0
6 0.7 0.0
6 0.8 0.0
6 0.9 0.0

7 0.1 0.0
7 0.2 0.0
7 0.3 0.0
7 0.4 0.0
7 0.5 0.0
7 0.6 0.0
7 0.7 0.0
7 0.8 0.0
7 0.9 0.0

8 0.1 0.0
8 0.2 0.0
8 0.3 0.0
8 0.4 0.0
8 0.5 0.0
8 0.6 0.0
8 0.7 0.0
8 0.8 0.0
8 0.9 0.0

9 0.1 0.0
9 0.2 0.0
9 0.3 0.0
9 0.4 0.0
9 0.5 0.0
9 0.6 0.0
9 0.7 0.0
9 0.8 0.0
9 0.9 0.0


Al final así es como se ve la gráfica generada en gnuplot:


Ahora hago el experimento con probabilidades menores de obtener ceros y unos correctos, con la misma cantidad de repeticiones:




El siguiente es el archivo dat obtenido tras correr el experimento con los parámetros mencionados:



0 0.1 0.5
0 0.2 0.6
0 0.3 0.6
0 0.4 0.65
0 0.5 0.5
0 0.6 0.5
0 0.7 0.6
0 0.8 0.6
0 0.9 0.5

1 0.1 0.7
1 0.2 0.45
1 0.3 0.55
1 0.4 0.0
1 0.5 0.6
1 0.6 0.0
1 0.7 0.0
1 0.8 0.0
1 0.9 0.0

2 0.1 0.15
2 0.2 0.25
2 0.3 0.0
2 0.4 0.0
2 0.5 0.5
2 0.6 0.3
2 0.7 0.1
2 0.8 0.0
2 0.9 0.0

3 0.1 0.45
3 0.2 0.0
3 0.3 0.0
3 0.4 0.15
3 0.5 0.0
3 0.6 0.0
3 0.7 0.0
3 0.8 0.0
3 0.9 0.0

4 0.1 0.0
4 0.2 0.0
4 0.3 0.0
4 0.4 0.0
4 0.5 0.0
4 0.6 0.0
4 0.7 0.0
4 0.8 0.0
4 0.9 0.0

5 0.1 0.0
5 0.2 0.0
5 0.3 0.0
5 0.4 0.0
5 0.5 0.0
5 0.6 0.0
5 0.7 0.0
5 0.8 0.0
5 0.9 0.0

6 0.1 0.0
6 0.2 0.0
6 0.3 0.0
6 0.4 0.0
6 0.5 0.0
6 0.6 0.0
6 0.7 0.0
6 0.8 0.0
6 0.9 0.0

7 0.1 0.0
7 0.2 0.0
7 0.3 0.0
7 0.4 0.0
7 0.5 0.0
7 0.6 0.0
7 0.7 0.0
7 0.8 0.0
7 0.9 0.0

8 0.1 0.0
8 0.2 0.0
8 0.3 0.0
8 0.4 0.0
8 0.5 0.0
8 0.6 0.0
8 0.7 0.0
8 0.8 0.0
8 0.9 0.0

9 0.1 0.0
9 0.2 0.0
9 0.3 0.0
9 0.4 0.0
9 0.5 0.0
9 0.6 0.0
9 0.7 0.0
9 0.8 0.0
9 0.9 0.0
Y la gráfica resultante con los datos obtenidos es la siguiente:



Ahora el código para realizar el plot en gnuplot:


set term postscript eps color 10
set view map
set pm3d map
set cbrange[0:100]
set xlabel 'Word length (power of 2)'
set ylabel 'Frequency of zeroes'
set title 'Avg. prob. of correct transmission'
set output "canalTriana.eps"
set palette color positive
set key off
set size square
set yrange [0.05:0.95]
set xrange [-0.75:9.75]
set xtics 0, 1
set ytics 0.1, 0.1
splot "canalTriana.dat" using ($1-0.5):($2+0.05):($3*100.0)


En la bibliografía agrego una liga que me sirvió a la hora de implementar archivos de texto en python (lectura, escritura).


Liga a mi git: https://github.com/eddypre/M-todosCodificaci-n

PD: Traduje del libro de Shannon de la página 41 a la página 45. 

Bibliografía:


Cualquier duda o aclaración pueden ponerla en comentarios. 

Saludos a todos!

lunes, 22 de octubre de 2012

Tarea 8

Sistemas concurrentes / Redes Petri

Hola a todos, el tema de esta actividad son los sistemas concurrentes y su modelación con una red Petri. Empecemos con comentar lo que es un sistema concurrente.

Un sistema o un programa concurrente es la simultaneidad en la ejecución de múltiples tareas interactivas. Las tareas estas de las que comento pueden ser un conjunto de procesos o hilos de ejecución creados por un único programa. Las tareas se pueden ejecutar en una sola unidad central de proceso , en varios procesadores o en una red de computadoras distribuidas. La programación concurrente está relacionada con la programación paralela, pero enfatiza más la interacción entre tareas. Así, la correcta secuencia de interacciones o comunicaciones entre los procesos y el acceso coordinado de recursos que se comparten por todos los procesos o tareas son las claves de esta disciplina.

Y la red Petri la defino de la siguiente manera: Una Red de Petri es una representación matemática o gráfica de un sistema es decir, en esta actividad, es una representación gráfica que cuenta con lugares, trancisiones y arcos dirigidos. Para una definición un tanto más "formal" y completa pueden visitar este enlace: http://es.wikipedia.org/wiki/Red_de_Petri

Bien, entendida la teoría vayamos a la actividad en concreto, lo encargado fue: Inventar un pequeño(esto me lo tomé muy enserio hehe) sistema concurrente y modelarlo con una red Petri.

Bueno el sistema concurrente que inventé fue uno que representara la solicitud de direcciones IP(por elementos de red: PC, dispositivos multimedia, refrigeradores, cámaras fotográficas, ipod, etc) a un router. Es en concreto un sistema de "address request", un protocolo DHCP.

Y el funcionamiento se basa en que un cliente solicita una dirección IP, y el router tiene una variable llamada "Contador", de manera que apartir de aquí se abren 2 trancisiones en las cuales si el contador es menor a 50(casi siempre son más, en telmex si creo que son 50), entrará a un estado de "IPEnviada". En caso contrario(cuando el contador es igual a 50), el sistema pasa a un estado llamado "SolicitudCancelada". Obviamente sabemos que el protocolo DHCP es más complejo y la cantidad límite de host que permite un router(wireless) es configurable(el límite es prácticamente la máscara de red), pero esto es solo una representación para ejemplificar los sistemas recurrentes

El diagrama, al igual que mis compañeros lo realicé en python con la ayuda de las librerías python-snakes (era requisito de la actividad).

El código para realizar el diagrama es el siguiente:





La imagen del diagrama es la siguiente:




Cualquier duda o aclaración pueden dejarla en comentarios.

Bibliografía


Saludos a todos!


domingo, 2 de septiembre de 2012

BDD

Diagramas Binarios de Decisión


Hola, la tarea para la siguiente semana consiste en:

1 - Inventar una expresión Booleana, usando por mínimo 3 variables y 4 conectivos básicos.
2 - Construir y dibujar su BDD.
3 - Reducir el BDD resultante a un ROBDD y dibujarlo.

Primeramente definiré el concepto de "Diagramas Binarios de Decisión".

Un diagrama de decisión binario es un concepto usado en el campo de las ciencias de la computación y es una estructura de datos utilizada para representar una función booleana.

Luego, mediante el diagrama binario de decisión se puede obtener la ecuación o expresión lógica de la proposición, y viceversa.

1- Para realizar la expresión booleana lo hice al azar, y la tabla de verdad obtenida con los conectores básicos que empleé salió así:


((A˅B)˄C)  ˅  (¬(B˅C))


2- Dibujar y construir BDD.





3 - Reducir el BDD resultante a un ROBDD y dibujarlo.


Removiendo terminales duplicadas...




Uniendo los nodos duplicados...




Removiendo nodos redundantes (final)...


Esto es todo para la tarea número 3. Gracias.
Cualquier duda o aclaración pueden dejarla en comentarios.

Saludos!