miércoles, 31 de octubre de 2012

Steganography







Download

martes, 30 de octubre de 2012

Programa 1: Análisis de respuesta y estabilidad de

Para esta semana la tarea de la materia de Automatización consiste en realizar un análisis en donde podemos ver cómo es la respuesta y estabilidad del sistema que hemos estado desarrollando durante el transcurso del semestre, por lo que voy a hacer un análisis en tiempo y frecuencia del circuito RLC en función de sus parámetros físicos utilizando el paquete de control de Octave.

Primero que nada, expongo el circuito RLC que hice en el modelo matemático.



En donde, sacamos una función de transferencia en la cual obtuvimos el siguiente resultado.


En donde como definimos, la L es la inductancia, R la resistencia y la C la capacitancia, por lo que podemos decir que esta función de transferencia está dada por sus parámetros físicos, pero para poder realizar el análisis en necesario tener las multiplicaciones de entrada y salida en función de s por lo que he multiplicado y agrupado para entender mejor el sistema.


 Para tener como resultado una nueva función de transferencia equivalente a la anterior.


Esta sería la función de transferencia desde la entrada a voltaje de salida, por lo que podemos decir que en base a el libro de Ogata [1] de control moderno, para observar el comportamiento de nuestro circuito es necesario tener nuestro sistema en una frecuencia de 1 rad/s, por lo que podemos utilizar la inductancia y la capacitancia en un valor de uno y la variar resistencia del voltaje para saber como cámbia el sistema.

Entonces, para poder analizar la frecuencia de respuesta del circuito vamos a desarrollar una grafica Bode, herramienta que nos sirve de apoyo para investigar si el flujo de voltaje con características RLC esta generando una frecuencia estáble, por lo que primero tenemos que definir la función de transferencia e igualar los valores R, L, C en su valor minimo (En este caso puse un 1), para luego generar un diagrama bode en donde  luego de estar variando la R, genero una pequeña animación para observar el comportamiento.

Podemos decir que respuesta en frecuencia es la respuesta del sistema que estamos observando en base a una entrada seno, por tanto, en el diagrama de bode podemos ver dos gráficas en donde en la parte superior vemos la representación en decibelios en contra una frecuencia logarítmica y en la parte inferior vemos los grados en contra una frecuencia logarítmica


Los valores R del 1 al 14
 Podemos ver que hace cambios en frecuencia más drásticamente.



Los valores R del 15 al 100
Ahora, hace cambios de frecuencia menores en cada cambio de R.

Como definimos, tenemos un circuito RLC en donde tiene una ganancia máxima a frecuencia de 1 rad / s, en la parte media del de la representación de decibelios, pero vemos que la atenuación a nivel R = 2 ohms en frecuencia de 10 rad/s es de -60dB, luego en R = 14 ohms en frecuencia 10 rad/s es de -70dB, mientras que en R = 100 ohms tenemos una atenuación de -100dB, por lo que podemos decir que una R = 100 ohms podemos tener una ateniación más estrecha an base a la frecuencia de destino de 1 rad /s.

En base a [2], podemos decir que el punto crítico para medir la estabilidad de un sistema de control es el tener en un paso en la gráfica en -180 grados en la parte inferior y en la parte superior el paso de la linea en 0dB de manera que caigan de manera semejante, por lo que según mi punto de vista, este sistema no tiene una estabilidad ya que en la parte superior de magnitud nunca tenemos 0dB ni aunque la R = 1 menos en R = 100.

Ahora voy a realizar el análisis del tiempo de respuesta del circuito, en donde como podemos ver que en donde tenemos un mayor cambio de atenuación en el circuito es en R=15, vamos a sacar el análisis de tiempo en base a la función lsim() de octave la cual, calcula como evoluciona las salidas del sistema en conjunto con los estados de las entradas,  es como si fuera una versión especial de step() en donde vemos los cambios, pero en cambio en lsim, estamos simulando el tiempo de respuesta producido de un sistema dinamico de control.



Las ondas nunca son atenuadas después o antes de 1 rad / seg, por lo que podemos decir que hemos tenido una respuesta no satisfactoria en base a el tiempo de respuesta, ya que si tuvieramos un sistema estable, veriamos una variación después de cierto tiempo, podemos ver que se generan gráficas de la misma magnitud.

Ahora les dejo el programa que hice para hacer estas gráficas y el análisis.




Por lo que podemos ver que en ninguno de los dos análisis que realizamos, obtuvimos resultados no satisfactorios, podemos concluir que mi sistema no es estable, considero, ahora que he estado leyendo sobre estabilidad y sobre lo que debería de hacer mi sistema, es que mi función de trasferencia está dada por factores físicos y por el sistema armónico, como lo describí en el modelado matemático, tal vez se necesite una forma de que el sistema armónico lo tengamos que poner en base a los factores físicos del RLC y tener así un sistema con una respuesta estable satisfactoria, ya que el sistema está siendo afectado directamente por las funciones trigonométricas que tengo de manera de salida.


Bibliografia.
[1] Chapter 3: Mathematical Modeling of Electrical Systems, Modern Control Engineering, Fifth Edition, Katsuhiko Ogata.
[2] Stability margins, models estim control, link
[3] Analyzing RLC Circuit, R2012b, link

Tarea 9: Grafo de programa

Para esta entrada de verificación voy a hacer un sistema en donde podamos modelar en base al reciclaje del papel, por lo que podemos decir que  el sistema consta de los siguientes procesos.
  • Recolectar papel y Clasificar el papel(Recolección)
  • Se moja y se bate para crear pasta (Creación_pasta)
  • Se limpia la pasta de pegamento, tintes, etc. (Limpieza)
  • Se moldea en superficia plana. (Molde_pasta)
  • Secado y enrollado de hoja. (Generar_papel)
Entonces, podemos tener un sistema en donde por ejemplo, ya tenmos papel previamente limpiado, o ya tenemos la pasta, y se pueden automatizar los procesos ya que según el estado en el que tengamos el papel, vamos a utilizar las herramientas que tengamos, por lo que considero que estos serian los procesos fundamentales en donde los procesos tienen solamente dos estados llamados 0 y 1.

Ahora, en base a estos procedimiento, voy a crear el sistema en base al estado del papel en donde según el estado, vamos a crear las transiciones del sistema dado el siguiente diagrama.


En donde el sistema global inicial es 0000, pero para poder iniciar el ciclo necesitamos por lo menos tener papel, por lo que pongo como estado global el tener papel recolectado 1000.

Bibliografia.
Principles of Model Cheking, Baier & Katoen,

miércoles, 24 de octubre de 2012

Stream Cipher: E0

Hi! for this week we need to choose a stream cipher to investigate and also put an example, so, I chose E0 which is the algorithm that is used to protect the confidentiality of communication protocol in wireless Bluetooth, developed by Bluetooth Special Interest Group (SIG) [1] including 1500 companies.

The pseudo-random generator consists with four LFSRs (Linear feedback shift register) combined by a function having 4 bits of internal memory which is updated by a nonlinear function. Bluetooth work on the principle of a protocol for master-slave type.

Vulnerability: E0 is vulnerable with the fast correlation attack that can recover the encrypthon key in 2^38 operations if we know the first 24 bits.

If we need to implement a security using E0 must have the following parameters.
  • Key length: 128 bits, the key is always extended to a word of 128 bits by adding bits redundancy even when the actual number of bits is less key.
  • Initialization 64 bits vector, corresponding to the logical address of the master (48 bits) and the data of the clock (22 bits).

Under the bluetooth protocol, data is transmitted in the form of frames more than 2745 bits, so, each frame is encrypted by modulo 2 bit by bit with the first output bit of the pseudo-random generatos, initialized with a secret key which is the same during the session and an initial value which is modified at each frame change.

Description

E0 diagram[6]


E0 uses a combination of four LFSRs[5], and having a 4 bits in memory, this is used at two different levels, it is applied once furing initialization to generate an initial state of 128 bits from the secret key and the first vector and the same mechanism is then used to produce the keystream from this initial state[4].

The four registers LFSRs are binary with this lengths L1 = 25, L2= 31, L3=33, L4 = 39, total = 128 bits.


If we denote xit the output at time t with i-th LFSR, then we need to calculate the 3-bit integer (0 to 4) corresponding to the sum of the outputs of the four LFSRs.


We need a combiner function F, that is a 4-bit finite state machine, if we have ct =(qt , pt , qt-1, pt-1) it's the registers of F and l(t) = x1t+ x2t+ x3t+ x4t is integer addition.

The output of the combiner function is pt, so, pt = F(xt, ct)
The state change by the following instruction:


where

St+1is the binary representation of the right number, 1 most significant bit and 0 least significant bit.

The output of the algorithm is:

So, we can say that the E0 algorithm made for each packet transmissions generates a new encryption that combine the four registers (complex RAND, device address, master clock, secret key), which has a 25, 31, 33, 39 bits, 128 in total, the secret key is used as an input to E0 to produce a bit stream pt that is added with modulo 2 to be encrypted.

Example
So, this is my example, I use for made the calculation, python in console mode.

We need 4 variables, with determinate bits:
RAND = 1101101000001010110100111  (25 bits)
Device Address = 1101111001010011010001010100011  (31 bits)
Master Clock =  111000001001110111101000111001001 (33 bits)
Secret Key =110010111000000010100110010100110001101 (39 bits)

I just use random numbers generates with the function getrandbits in python, then, we need to do LFRS, so this is one iteration, we need to select the position base on the polynomials and made the sum.
P1(x) = 1 + 0 + 0 + 1 + 1
P1(x) = 11

P2(x) = 1 + 0 + 0 + 0 + 1
P2(x) = 10

P3(x) = 1 + 0 + 0 + 1 + 1
P3(x) = 11

P4(x) =  1 + 1 + 1 + 0 + 1
P4(x) = 100

Then, we need to have  lt
lt = 11 + 10 + 11 + 100
lt = 1100

Then we need to calcule  F(xt, ct) if we have ct =(qt , pt , qt-1, pt-1) as memory of previous iterations, base in [1] we have 2 states 2-bit that:

Suppose that we have this combination and a t = 35 seg:
qt = 00
p= 01
qt-1 = 11
pt-1= 10

St+1= floor(pi(100011)+2*(00)+01/2)
St+1 = 11110

pt = F(xt, ct)
p= 11110

Then we can calculate Z:
Z = (l(t) % 2) + Pt
Z = (1100 % 2) + 11110
Z = 11110

So, Z contains one bit stream encrypted, this change in the time and in the state.

Vulnerability
The generator by combining registers used in the algorithm e0 is vulnerable to several attacks, I can mention for example linear attack, algebraic and fast algebraic attacks and fast correlation attacks. Most of these attacks requires the knowledge of a large number of successive bits of the key, which is not possible in the practical context of the Bluetooth protocol since the initial state of the generator is changed every number of bits.

By cons, sophisticated correlation attacks, presented by Yi Lu, Wili Meier [2], take into the session the re-synchronization occurs after encrypting each frame, and also there are one most effective[3] that allows to recover the encryption key from the knowledge of the first 24 bits of 2223.8 frames in 238 operations, as a result, the algorithm used in Bluetooth e0 is clearly offers insufficient security.

Biography.
[1] Bluetooth special interest group link
[2] Cryptanalysis of Bluetooth Keystream Generator Two-Level E0, Yi Lu, link
[3] A Practical Arrak on Bluetooth Encryption, Vili Meier, link
[4] Criptografía Moderana, cifra de flujo, P. Caballero link
[5] Communication Systems Security, Appendix B.L. Chen, link
[6] Algebraic Attacks and Stream Ciphers, Mikko Kiviharju, link

lunes, 22 de octubre de 2012

Red Petri

La red petri son los tipos de modelos que se utilizaron en sistemas distribuidos, utilizan tokens que van viajando dentro de los estados, sirve para investigar las combinaciones de tokens permitidas en posiciones en las cuales no son permitidas.

Para esta tarea hice una red petri sencilla en donde modele un sistema de reconocimiento de huellas, como el que se utilizan en las empresas, para abrir o cerrar una puerta.

El aparato siempre esta en la espera de que entre un dedo, al momento de que ponga el dedo empieza a capturar su huella digital, después el sistema empieza a reconocerlo y decide si se abre o no la puerta, por lo que podemos decir que tenemos entonces los siguientes estados.
  • Esperando.
  • Capturando.
  • Reconociendo.
  • Abierto
  • Cerrado.
Incluyendo 5 transiciones diferentes y el token sería el dedo o la huella.

Utilizando python realizamos un modelo.


Teniendo como resultado el siguiente diagrama.
Esta sería me entrada de validación, para más información sobre las redes petri, pueden ver información en el wiki aquí.

miércoles, 17 de octubre de 2012

Block Ciphers: RC5


Hi!, for this week we need to choose a block cipher to investigate and also put an example, so, I chose RC5, is a block cipher quick and easy, designed by Ronald Rivest in 1995 in the MIT's Laboratory of Computer Science, this encryption algorithm, works for hardware and software, use as a parameters the length of the word, the number of iterations and the length of the private key.

RC5 has the following characteristics:

  • Is a symmetric cipher, both the encryption and decryption uses the same private key.
  • It works in both, hardware and software because RC5 uses only elementary operations.
  • Is adaptable to processors with different word lengths, for example, if we have a 64-bit processor, RC5 can use the entire length of the word.
  • Has an iterative structure with a variable number of iterations.
  • Has a cryptographic key variable length, this allows that the user can choose the desired level of security for your application and solves problems related to the export of cryptographic algorithms that use more than 40 bits keys.
  • It is easy to implement.
  • A request has limited memory, so it can be easily implement on devices with small memory.
  • Provides a high safety
  • Using data-dependent rotations, in which words are rotated cyclically.

One of the fundamental characteristics of RC5 is that uses three parameters, W, R, B, if two users exchange messages using RC5 for encryption must agree with that parameters.

  • W: is the word length in bits. RC5 uses basically values such as 16, 32 and 64 in W, We need to know that RC5 cipher blocks of 2 words use the plaintext and the ciphertext uses 2W bits. so if we have a W = 32, the blocks of plaintext and ciphetext are of 64 bits.
  • R: represents the number of iterations of the algorithm and varies from 0 to 255. the security level of the cipher depends from this parameter: the larger choose R, the better the security.
  • B: is the length of the private key K. Allowed values of b are 0, 1, …, 255.

For convenience, we can use RC5-W/R/B to denote those parameters, for example, the algorithm RC5-32/16/10 uses 32-bits words, leaving 16 iterations of the algorithm and has a key of 80 bits (10 bytes). Not necessarily all the parameters must be specified. We can omitted the last parameter or can be omitted the last two. For example, with RC5-32, is indicated the RC5 algorithm that uses 32-bits words, without any reference to the number of iterations and the length of the key.

RC5 uses only the following three operations and their inverses:

  • Sum of words module W/8, this operation is denoted by +, the inverse operation, subtraction, is denoted by -.
  • Bitwise exclusive-OR, denoted XOR (The reverse is itself).
  • Rotation to the left of words. The cyclical rotation of the word x of y bits to the left is denoted with 2^w y is considered the modulo w, so when w is a power of two, are need only x << y low order bits of y to determine the number of position to rotate. the reverse operation is to the right.

These operations are supported efficiently by many processors, the main feature of RC5 is the use of data-dependent rotations, rotations dependent on the plaintext and the key, also, the rotations are the only nonlinear operator in RC5.

The RC5 cipher contains the three following procedures:
  • Key expansion algorithm
  • Encryption algorithm
  • Decryption algorithm
The plaintext input to RC5 consists of two w-bit words, contained in the registers A and B, also uses a "expanded key table" containing t = 2(r+1), obtained from the user's private key K.

The key expansion algorithm, use the secret key K, fills the key table S with t = 2(r+1) binary words, use also two "magic constants" P and Q. which are defined as a W for arbitrary.

Pw = ODD((e-2)2^w)
Qw = ODD((phi-1)2^w)

where e = 2.7182... , phi = 1.618... and ODD(x) is the odd integer closest to x.

For w = 16, 32, 64, have the following values in hexadecimal.

  • Pw 16-bit = B7 E1
  • Pw 32-bit = B7 E1 51 63
  • Pw 64-bit = B7 E1 51 62 8A ED 2A 6B
  • Qw 16-bit = 9E 37
  • Qw 32-bit = 9E 37 79 B9
  • Qw 64-bit = 9E 37 79 B9 7F 4A 7C 15


The key expansion algorithm is divided into two steps:

Conversion of the secret key from bytes to words. The B-byte secret key K [0 .. B-1] is copied into an array L [0 … c-1] of c words. each w-bit, so in this way, in L[0] is stored the first byte of the key and L[c-1] contains, if  necessary, of the null bits, added to make the key size equal to a certain number of words, namely 8*b must be a multiple of W. 

So, the size of the array L[] is c = [8*b/w]

Creation of the expanded key table, the array S is initialized by using an arithmetic progression modulo w/8 determined by magic constants, 

S[0] = Pw 
for i = 1 to 2r+1 do  
        S[i] = S[i-1]+Qw

Then the algorithm performs the actual expansion of the key processing arrays S and L in the following way:

X ,  Y = 0
i, j = 0
do 3*max(x, 2r+1) times:
X = S[i] = (S[i]+X+Y) << 3
Y = L[j] = (L[j]+X+Y) << (X+Y)
i = (i+1) mod (2r+1)
j = (j+1) mod c

So in S[0, …, 2*r + 1] contains the key will be scheduled. The expansion function key can be considered one way. It is not easy to determine K from S.

The encryption algorithm takes as input the plaintext stored in two registers A and B, each of w bits, the number r of iterations to be performed and the key, stored in S[0, …., 2*r + 1], returns the cipher text in the registers A and B, the algorithm in pseudocode:

A = A + S[0]
B = B + S[1]
for i = 1 to r do:
A = ((A XOR B) << B) + S[2i]
B = ((B XOR A) << A) + S[2i+1] 

The output is contained in the registers A and B.

We observe that RC5, at each iteration, updates both registers A and B. During each iteration of the DES, however, only half word is actually transformed, while the other half remains unchanged, Therefore an iteration on RC5 "is equivalent" in two iterations of the DES.

The decryption routine is easily derived from the encryption routine: just do the reverse in reverse order:

for i = r downto 1 do:
B = ((B-2[2*i+1] >> A) XOR A
A = ((A - S[2i]) >> B) XOR B
      B = B - S[1]
      A = A - S[0]

The output is stored in the registers A and B containing the plaintext.

The RC5 algorithm is extremely simple. Its cryptographic strength depends heavily on the use of data-dependent rotations. Sice they depend on the input data, do not allow to collect statistics and avoid attacks of differential cryptanalysis and linear cryptanalysis.

I tried to understand the vulnerabilities of the RC5, I saw that if we have two similar plaintext blocks can give us results very similar, so I put the example about that:

This is first iteration and we already have the table expansion.

A = A XOR B 
A = A << B 
A = A + S[i] 
B = B XOR A 
B = B << A 
B = B + S[i+1]

A = 11111101100001001101111001100011
B = 10110001100110011010111100110001
   

Now, we can made the first 3 steps.

A = A XOR B

A =
      11111101100001001101111001100011 XOR
      10110001100110011010111100110001
      ---------------------------------------------------------
      11001100000111010111000101010010


A = 11001100000111010111000101010010

A = 11111101100001001101111001100011 << 10110001100110011010111100110001

A = 11100010101001011001100000111010

A = A + S[i]

A = 
   11100010101001011001100000111010 
+ 01110001100111101110010011011001
    --------------------------------------------------------
    01110001000001011011001101100001

A = 1110001000001011011001101100001

Then, imagine that we have a A and B just only one letter different.

A = 11111101100001001101111001100011
B =  00110001100110011010111100110001

Now, we can made the next 3 steps.

A = A XOR B

A = 11111101100001001101111001100011  XOR
       00110001100110011010111100110001
    -----------------------------------------------------------
       11001100000111010111000101010010

A = A << B

A = 11001100000111010111000101010010 << 00110001100110011010111100110001

A = 11100010101001011001100000111010

A = A + S[i]

A = 11100010101001011001100000111010
     + 01110001100111101110010011011001
     ----------------------------------------------------------
       001110001000001101011001101100001

A = 1110001000001101011001101100001


Now, compare A.

A_1 = 1110001000001011011001101100001
A_2 = 1110001000001101011001101100001

You can see that we have two plaintext blocks very similar, if we have the ciphertext very similar, we have a problem because an attacker can see that ciphertext blocks and check similarities to have things for the plain text.

So it is important to know that we have issues that involves vulnerabilities but we can improve put, as I explain in the algorithm,  put a lager R that represents the number of iterations of the algorithm and varies from 0 to 255. the security level of the cipher depends from this parameter: the larger choose R, the better the security.

Bibliography.
* The RC5 Encryption Algorithm MIT, Ronald Rivest link

Lab 4: Factor de amortiguamiento relativo del sistema

La siguiente figura que se muestra a continuación es un diagrama de bloques del sistema de control de altitud de un vehículo espacial.


Suponiendo que la constante de tiempo T del controlador es de 3 seg y que la razón K/J es de 2/9 rad2/seg2, encuentre el factor de amortiguamiento relativo del sistema.

Capturemos los datos:









Después, según la álgebra de bloques, vamos a sacar la función de tranferencia del sistema de control de altitud del vehículo espacial.

Multiplicamos las constantes.

Ponemos de fórmula de modo que tengamos constantes de K/J para poder sustituir.

Sustituimos con los valores dados en el problema.


Como necesitamos el  factor de amortiguamiento relativo del sistema, y sabemos que podemos con lo anterior relacionar la frecuencia natural no amortiguada Wn y el símbolo del factor de amortiguamiento, algo importante es dejar las J del mismo valor para poder sustituir, tenemos que:

Podemos sacar el factor de amortiguamiento relativo del sistema con la siguiente fórmula.
Sustituyendo:
Este sería nuestro resultado.

domingo, 14 de octubre de 2012

La lógica predicativa en las bases de datos.

Como pudimos ver en clase de verificación de software, la lógica predicativa tiene una alta gama de significaciones que la lógica booleana que hemos visto anteriormente, por lo que este tipo de lógica predicativa tiene aplicaciones más diversas, para esta entrada voy a explicar como podemos utilizar la lógica predicativa en las bases de datos.

Primero que nada vamos a definir base de datos, la cual podemos decir que es una colección finita de datos relacionados, por ejemplo un diccionario inglés-español, un directorio de teléfonos, etc...

En una base de datos podemos encontrar los siguientes elementos los cuales podemos representarlos de manera lógica [1]:

  • Un átomo = numero, letra, etc...
    • Representado en lógica como un elemento en el universo.
  • Un registro = una tupla de elementos atómicos.
    • Representado en lógica como un hecho.
  • Una tabla = una colección de registros compatibles.
    • Representado en lógica como una relación.
  • Una base de datos relacionada = una colección de tablas
    • Representado en lógica como una colección de relaciones
  • Una base de datos deductiva = base de datos relacionada incluyendo mecanismos deductivos.
    • Representado en lógica como una base de datos extensional y bases de datos intencionales (esto quiere decir que se incluyen ciertas reglas)
  • Un query = es una herramienta linguistica para seleccionar información.
    • Representado en lógica como una fórmula.

Entonces podemos decir que el modelo de bases de datos deductivo es una restricción de primer orden de la lógica de predicativa en un modelo de datos relacional, este modelo deductivo se hacen relaciones bien definidos extensionalmente a través de hechos o intencionalmente a través de reglas, en donde las reglas pueden ser definidas, como podemos ver en la arquitectura de una base de datos deductiva.

Arquitectura de una base de datos deductiva
Podemos decir que las bases de datos extensionales, las restrucciones de integridad y las queries están presentes en los sistemas tradicionales de bases de datos, lo que se diferencia la base de datos deductivas es que ofrece almacenar reglas deductivas en bases de datos intensionales y proporcionar un mecanismo de deducción.

Se han desarrollado varios lenguajes formales para este tipo de modelo de datos deductiva, por ejemplo existe un lenguaje llamado Datalog [2], un sublenguaje en donde se le llena una base de datos y se ingresan algún query que cumple con lógica predicativa de primer ornen, también lenguajes como Prolog [3], extienden las estructuras de bases de datos complejas utilizando componentes en donde se combinan el lenguaje lógico declarativo con el almacenamiento de datos en base a sus datos y las reglas.

Los hechos en datalog son representados en forma de relaciones NOMBRE(argumento-1, ..... argument-n), donde NOMBRE es el nombre de la relación y argumento son las constantes.
Por ejemplo, DIRECCION(Roberto, 'Calle 13')

Los queries atómicas son representados de la siguiente forma: NOMBRE(argumento-1.... argumento-n), donde los argumentos son constantes o variables que incluyen la variable ''-" negación.

Las reglas en datalog son expresadas de la siguiente forma.
En donde las Z son vectores de variables o constantes en donde cualquier variable que aparece en la parte de la izquierda de ":-" aparece también del lado derecho.

La semántica en datalog es la forma:

En donde todas las variables que aparecen tanto de lado izquierdo como de lado derecho de la regla (llamados cabeza y cuerpo) son universalmente cuantificados, mientras que los que solamente aparecen de lado izquierdo (en el cuerpo) están existencialmente cuantificados.

Entonces en base a los conceptos anteriores voy a desarrollar un ejemplo en donde vamos a utilizar lo anterior, supongamos que necesitamos realizar una base de datos que contenga información acerca de autores de libros, vamos a guardar en una relación, llamada AUTOR y otra relación llamada TITULO de la siguiente manera:
  • AUTOR(Nombre_autor, Id) 
    • Esto significa que el autor cuyo nombre tiene una identificación ID
  • TITULO(Id, Nombre_libro)
    • Esto significa que el autor cuyo numero de ID es autor o coautor de un libro titulado Nombre_libro.
Ahora por ejemplo vamos a definir una nueva relación COAUTOR(Nombre_1, Nombre_2), el cual significa que dichos nombres fueron coautores del libro:

COAUTOR(Nombre_1, Nombre_2) :- AUTOR(Nombre_1, ID_1), TITULO(ID_1, Nombre_libro), AUTOR(Nombre_2, ID_2), TITULO(ID_2, Nombre_libro), Nombre_1 =/= Nombre_2.

Podemos ver que la regla que hemos realizado diciendo que tenemos un número de ID único en donde a esta variable le podemos decir que es una restricción de integridad que cumple con la siguiente semántica:

Entonces este sería una forma de modelar una base de datos por medio del lenguaje Datalog, se puede implementar este tipo de bases en nuestros programas incluyendo la lógica en base a algunas extensiones por ejemplo en python existe pyDatalog [4] en donde de manera sencilla podemos modelar una base de datos deductiva.

Esta sería mi tarea de verificación si tienen alguna duda espero me lo hagan saber.

Bibliografía.
[1] Lectura de la clase lógica de la Universidad de Linkoping liga.
[2] Lenguaje Datalog liga
[3] GNU Prolog website. liga
[4] pyDatalog liga

lunes, 8 de octubre de 2012

Reporte de Redes Neuronales: Medio Curso.

Como reporte de medio curso de la materia de Redes Neuronales Artificiales de la Dra. Elisa Schaeffer en el semestre Ago-Dic 2012, voy a exponer en lo que he colaborado en el equipo de Speaker Recognition System, en donde básicamente lo que estamos implementando es una red neuronal que pueda clasificar entre si es una persona, o no en base a su voz, validando mediante una serie de pasos y entrenando la red neuronal para poder saber si esta persona es la que está utilizando el sistema, para posteriormente realizar algún otro tipo de acción, en este caso estamos solamente trabajando de lado de la validación.

Este es el Repositorio de nuestro proyecto.

En las primeras semanas de la materia, estuvimos viendo teoría básica para poder empezar a programar una red neuronal, por lo que en la primera parte del proyecto pude contribuir en crear una primera versión de una neurona binaria simple, la cual documento en este post. Link, en donde utilizo el modulo numpy para multiplicar y generar los vectores para multiplicarlos y simplemente nos da la salida 0-1, en base a este programa pequeño script que hice en python pudimos empezar a programar nuestro primer programa agregando una funcionalidad de orientado a objetos, en colaboración con todo el equipo.


Después estuve desarrollando la interfaz, que obtendrá el usuario al momento de saber si es o no la persona que está hablando, es muy sencilla y simplemente estamos desplegando dicha información.





Esta sería la interfaz de salida que tendría el usuario con unos script sencillos, que están listos para integrarse al prototipo final en donde utilicé TK con python y desplegamos si la persona es identificada o no.


Después, trabajé en base a lo que estuvimos haciendo en equipo, desarrollando la neurona y moldelandola para recibiera como entrada valores no únicamente binarios, trabajando con el programa que realicé en la clase para generar los valores se necesitan y empecé a programar utilizando el módulo de tk de python, la interfaz gráfica de respuesta al usuario, al igual que la animación del comportamiento de la red neuronal, por lo que en la mayor parte del proyecto estuve trabajando en dichas interfaces de observación de la neurona y las del usuario de salida.


Para crear la interfaz para la observación del comportamiento de la neurona, utilicé la libreria tk de python en donde primero generé una ventana de 1000 pixeles x 1000 pixeles, programé un script en el cual pudiéramos obtener valores de -1:1 y tenerlos en sus planos correspondientes, por lo que dividí la ventana de manera que tuviéramos un plano de cuatro partes, en donde en la parte superior derecha tengamos los valores positivos de estos números, luego en la parte superior izquierda los valores negativos respecto al eje x y los valores positivos respecto al eje y, la parte inferior derecha los valores prositivos respecto al eje x y los valores negativos respecto al eje y, y en la parte inferior izquierda los valores negativos respecto a ambos ejes, por lo que por medio de la fórmula (1-x)*500, donde x es el número de entrada a neurona dado -1:1 y el menos uno para controlar la posición de pixeles, por lo que de esta manera podemos posicionar los elementos de manera correcta.


En la versión entregable, nuestros valores de entrada que tomamos de parámetros para nuestra primera versión, utilizamos valores de 0:1 por lo que ahora, tomé los valores directamente y los he multiplicado por el numero de pixeles para poderlos posicionar, en lo cual me he basado para poder unir mi script con el script de la neurona, en donde tenemos la siguiente simbología en la imagen de la derecha.


Como podemos ver en el siguiente video que he subido a youtube, ésta es la interfaz de observación del comportamiento de la neurona en base a como va corriendo nuestro script.





Obteniendo como resultado:



Este sería mi reporte de la materia de redes neuronales para el medio curso, si tienen alguna duda acerca de lo que se está haciendo con el proyecto, pueden dejar un comentario en el blog, esperamos que para final de semestre tengamos todo esto en conjunto y funcional.


Por último muestro las diapostivas grupales, en donde exponemos el avance en equipo:

Gracias

jueves, 4 de octubre de 2012

Reporte 2: Diagrama de bloques

Como hemos visto en la clase de automatización, nosotros por medio de un modelo matemático estamos intentando controlar el audio a través del ruido ambiental, esta la podemos llamar planta, todo generando cierta salida, nosotros lo que debemos es diseñar en el sistema es comparar una referencia con la salida que generamos, a esto se le llama control.

Lo que pretendemos es calcular el error de lo que deseamos en términos de cuanto diferencia hay, si el error es pequeño, es importante agregar una amplificación para poder fácilmente detectar el error que estamos teniendo, lo que quiere es que ese error desaparezca y la salida se apegue a la referencia que tenemos, la señal de control entra a un actuador que va a aumentar el volumen, cambiando según el ruido detectado por el sensor.

Como en mi tarea anterior del modelado matemático del sistema, vamos a sacar un diagrama de bloques para ver de una manera más simple y entender a profundidad el mismo que estamos desarrollando.

Entonces, vamos a expresar estas funciones del reporte anterior en un diagrama de bloques, o sea que es lo que va a pasar internamente del sistema de control, cual va a ser la señal de salida y que va a producir la señal de entrada lo definimos como los componentes del circuito y del micrófono, la señal de salida armónico simple generado del micrófono, al sobrepasar un cierto umbral éste va a cambiar su volumen y generar un audio más estable.

Tenemos el siguiente diagrama de bloques
Como podemos ver, esto no nos muestra mucha información a nuestro sistema, lo que necesitamos es expresar el sistema en bloques más pequeños, para eso voy a maximizar este diagrama, en base a la álgebra de bloques, vista en el libro de control moderno de Ogata.






 En donde vemos que, las cajas son las funciones generadas por medio de la función de transferencia y las flechas son el flujo de la señales de una función a otra, generando un diagrama de bloques lineal en donde siempre sumamos o restamos dichas funciones.

Es importante remarcar, que las señales no se reparten si no que se replican, lo que entra es la variable de la función para producir las salidas entrando R(s) y C(s), combinando bloques en serie, paralelos, retroalimentado.

Referencias.
Ogata, control moderno liga.
Modelado matemático, blog. liga.