miércoles, 21 de noviembre de 2012

Lab 7: Matriz de ganancia K

Ejercicio 11.3: Determinar la matriz de ganacia K de manera que los polos en lazo cerrado del sistema



sean s1 = -1 y s2 = -2.

Utilizar la retroalimentación de estados u = -Kx

Podemos decir que, dado el sistema de una o varias entradas y un vector p deseados en ubicaciones auto-conjugadas para polos en lazo cerrado, se utiliza la función place en octave la cual calcula una matriz de ganancia K tal que la retroalimentación de estado u = -Kx colocando los polos en lazo cerrado en p ubicaciones.

octave:1> A = [0, 1; -1, 2]
A =

   0   1
  -1   2

octave:2> B = [1;1]
B =

   1
   1

octave:3> C = [1;-1]
C =

   1
  -1

octave:4> polos = [-1, -2]
polos =

  -1  -2

Esto quiere decir que los valores propos de A - BK coinciden con las entradas de p.

K = place(A, B, p) pone el lazo cerrado según los polos p calculado una matriz de ganancia de retroalimentación, todas las entradas de la planta asumen que  son entradas de control y la longitud del vector p debe concidir con el tamaño menor de la fila de las matrices, funciona en sistemas de múltiples entradas y se basa en un algoritmo que usa los grados de libertad adicionales para encontrar una solución que minimice la sensibilidad de los polos en lazo cerrado en las perturbaciones A o B.

octave:5> [K, prec] = place(A, B, polos)
K =

   1   1

prec =

  scalar structure containing the fields:

    nfp = 0
    nap =  1
    nup =  1
    z =

       0.70711  -0.70711
       0.70711   0.70711

Como resultado [K, prec] = place(A, B, p)devuelve en prec una estimación de la precisión con los valores propios de A-BK especificadas en p, midiendo el número de dígitos decimales exactos en el actual ciclo cerrado y la matriz de ganancia K.

octave:6> plot(place(A,B,polos))


Vemos la gráfica no cambia ya que la matriz de ganancia K generada tiene como valores 1, por lo que tenemos una ganancia de retroalimentación nula.

martes, 20 de noviembre de 2012

Reporte final automatización.

Para la materia de automatización y control de sistemas dinámicos del semestre Agosto-Diciembre 2012, estuvimos trabajando en el proyecto de ajuste de volumen de sistemas en donde controlamos el volumen del sonido en una bocina o altavoz, que depende directamente del ruido que se encuentra en el entorno.

Por lo tanto, para nuestro proyecto podemos decir que si por ejemplo estamos reproduciendo una canción en una habitación y en determinado momento entra gente a platicar o hay algún ruido externo inesperado, el volumen del dispositivo que está emitiendo el sonido de la canción va aumentando paulatinamente para que se continue escuchando la canción.

Podemos decir que la importancia de nuestro proyecto es por ejemplo en sistemas en automóviles, en donde el volumen de la música dentro del auto aumenta cuando el motor emite mucho ruido, en cambio cuando este está detenido, el volumen baja, cuando las personas en alguna empresa tienen audifonos en donde se les transmiten comandos a realizar, pero el sonido de la planta es muy fuerte, se controla el volumen de lo que se emite.

Diagrama de bloques.

En donde tenemos como entrada y salida:

  • Salidas: 
    • El audio de la canción o video reproduciendo actualmente a un volumen ajustado automáticamente por el programa.
  • Entradas:
    •  El ruido del ambiente y en base a esto se hace un cambio en el volumen.

En donde generamos la función de tranferencia:


Usamos Python como lenguaje de programación, haciendo uso de las siguientes librerias.

  • Alsaaudio:
    •  Sirve para controlar el nivel del volumen.
  • Audioop:
    •  Regresa el valor máximo absoluto de un tramo de datos captado como sonido.
  • Time: 
    • Usamos esta librería para controlar el tiempo de ejecución en la recepción del ruido.

En el siguiente diagrama vemos la arquitectura de sistema lógico en donde podemos ver la secuencia que realiza el sistema y cómo va cambiando el volumen.


Diapositivas.

Código.
Demo

Reporte Speaker Recognition

Como reporte final 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.

Para esta mitad después de medio curso estuve contribuyendo con el proyecto haciendo una integración de la interfaz que habiamos desarollado anteriormente con la que utilizamos en nuestro prototipo final, ahora las ventanas van en cadena y están relacionadas según los datos que obtenemos en la red neuronal  y así detectar si es o no una persona.

Estas serían las capturas actualizadas del prototipo final.




Esta sería la interfaz de salida que tendría el usuario con unos script integrados con la grabadora, que 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, decidimos hacer un análisis de compomtentes principales (PCA), por lo que yo estuve a cargo de desarrollarla y hacer pruebas para saber si esta forma de obtener los datos nos pudiera servir para tener un mejor resultado, basicamente lo que hice fue seguir los pasos del análisis y luego hice un archivo de prueba en donde utilizo el array de las frecuencia de MEL obtenidas anteriormente.

Este análisis es un proceso matemático que calcula los datos más significativos por medio de una descomposición de valores en la matriz de covarianza.

Estos son los resultados que obtuvimos de este análisis.



Como pueden ver entre Ramón y yo no tenemos mucha diferencia, cuando con Cecilia tenemos un valores completamente diferentes, de hecho también hice el análisis gráfico y vemos que el vector de coeficientes y el vector de puntuación se posiciona de manera contraria.

CECILIA

RAMON

ROBERTO

Después de algunas pruebas, utilizando el PCA, determinamos que los valores que obtuvimos eran muy parecidos entre Ramon y Roberto, por lo que decidimos utilizar los valores obtenidos del análisis de audio.

Los códigos del análisis y un código de prueba lo pueden ver en el repositorio, este sería mi reporte de la materia de redes neuronales, si tienen alguna duda acerca del proyecto, pueden dejar un comentario en el blog.

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

miércoles, 14 de noviembre de 2012

Lab 6: Observable y Controlable

B.12.1   Sea el sistema definido por



donde


Transforme la ecuación del sistema en

  • (a) la matiz controlable.
  • (b) la matriz observable.

Después concluir sobre su resultado.

Por lo tanto, como sabemos Octave tiene las funciones en donde podemos obtener dichos resultados, primero que nada vamos a hacer la forma canónica controlable, en donde vamos a utilizar la función ctrb(A, B) del paquete de control, obtenemos lo siguiente:

octave:1> A = [-1,0,1;1,-2,0;0,0,-3] 
A =
  -1   0   1     
   1  -2   0    
   0   0  -3

octave:2> B = [0;0;1] 
B =
   0    
   0    
   1

octave:3> pkg load control

octave:4> Pc = ctrb(A, B) 
Pc =
   0   1  -4    
   0   0   1    
   1  -3   9

Ahora, en esta matriz de controlabilidad tenemos un sistema que es lineal completamente controlable si y sólo si la matriz Pc = [B AB A^2*B ... A^N*B] tiene un rango completo, donde tenemos la A como una matriz de n x n para sistemas lienales de una entrada, el sistema es controlable si y solo si el determinante de la matriz de controlabilidad Pc es distinto a cero, por lo que vamos a verificarlo.

octave:5> det(Pc) 
ans =  1

Por lo tanto concluimos que el sistema es completamente controlable.

Después se nos pide sacar la matriz de observabilidad, lo vamos a sacar con la función obsv(A, C), y analizamos su resultado.

octave:6> A = [-1,0,1;1,-2,0;0,0,-3] 
A =
  -1   0   1    
   1  -2   0    
   0   0  -3

octave:7> C = [1,1,0] 
C =
   1   1   0

octave:8> Po = obsv(A, C) 
Po =
   1   1   0    
   0  -2   1  
  -2   4  -3

octave:9> det(Po)ans = 0

Ahora se nos dice en la teoria matriz de observabilidad vemos que el sistema lienal es completamente observable si y solo si la matriz de observabilidad Po tiene un rango completo, Para sistemas lineales con una unica entrada y una unica salida, el sistema es observable si y solo si el determiante de la matriz de observabilidad Po es distinto a 0, en nuestro caso podemos decir que nuestro sistema no es completamente observable ya que el determinante de dicha matriz nos da como resultado exactamente 0.

Fin de la actividad.

martes, 13 de noviembre de 2012

Reporte grupal

Proyecto de Automatización: Control de volumen automático
Equipo:



LaTeX

Aplicación de red neuronal


Para esta entrada voy a hablar acerca de alguna aplicación en la industria usando redes neuronales, por lo que busque algun texto en el cual estuviera estrechamente ligado a mi proyecto que hemos estado desarrollando duerante este semestre, por lo que voy a hablar hacerca de Speaker Recognition Using Neral Networks and Conventional Classifiers Liga, escrito por Kevin R. Farrell, Richard Mammone.

En este documento se hace una evaluación de diferentes clasificadores de renocimiento del hablante y proponen un clasificador llamado modified neural tree network (MNTN), el cual es un clasificador que combina las propiedades de un árbol de desición y la retroalimentación de las redes neuronales, existe ya un estandar NTN, esta versión modificada fue hecha especificamente para el reconocimiento del hablante, haciendo una verificación y una identificación usando datos de 38 personas que hablan el mismo idioma y en la misma región.

Como sabemos en la identificación del hablante es determinar quien está hablando en donde un sistema común y a grandes rasgos tiene como entrada la voz, en donde se hace un cierto preprocesamiento para extraer características importantes para ahora clasificarlo en si la persona es o no la identificada, la versión en la que ellos se enfocan es un sistema en donde depende de cierto texto para saber si esa persona es la que está hablando.

Basicamente lo que hace este MNTN es comparar con el metodo de clasificación del vecino más próximo, cuyo objetivo es estimar el valor de la función de densidad de probabilidad y tener por otra parte un arbol estructurado según su vector de cuantificación, una red multicapa y arboles de decisión para evaluar la comparación.

Nos hablan de la importancia de poder extraer las características del habla para poder identificar a la persona, en donde ellos proponen una seleccion de una herramienta la cual consideran clave para la clasificación de la voz en cuestión de la persona este se llama coeficiente Cepstral, estos se generan sacando la transformada inversa de Fourier del logaritmo del espectro de señal, son utilizandos para aplicaciones de este tipo, estos los podemos calcular con una pequeña porcion de audio, se saca del estracto la transformada de Fourier, después se hace un mapeo de la energía del espectro, se calcula el logaritmo de esa energia para obtener nuestro resultado a clasificar.

La clasificación se hace referencia a varios formas que se han hecho a lo largo del tiempo, como la distancia Euclidean, la clasificación Mahalanobis, usando el discriminante Bayesiano, pero la alternativa que ellos proponen es utilizar una red neuronal multicapa basada en entrenamento no supervisado, proponen utilizar el modelo discreto de Markov, la cual saca las probabilidades de cada transición entre estados, o la sumatoria de mezclas gausianas, la cual uiliza información temporal para ir mejorando cada iteración.

Después el MNTN como clasificador hace una medición en cada nodo del arbol junto con una etiqueta de la clase a la que pertenece, según la secuencia del vector de pesos, como speaker y como antispeaker, después se calcula el ratio acumulado de los hablantes con dicha etiqueta y se calcula una sumatoria de los ratios de los que tienen etiqueta speaker, ese mismo procedimiento se hace con los de etiqueta antispeaker para despues hacer una comparación de esa sumatoria y determinar si o no es el hablante.

Ellos realizar experimentos usando esta técnica y determinaron que de 20 personas a las cuales se les realizó el experimento para la validación del hablante, se obtuvo un 4% de error, proponen usar esta técnica ya que computacionalmente tiene ventaja al tener un arbol estructurado reducir una busqueda completa de si es o no el hablante, porque ya tenemos dicha información de cierto modo acomodado para su facilidad de uso.

Referencias.
Speaker Recognition Using Neral Networks and Conventional Classifiers Liga.

lunes, 12 de noviembre de 2012

T12: Linear Temporal Logic

Como vimos en los ejemplos de maquina vending en clase, podemos formular la operación de recarga que se hace infinitas veces, debemos de satisfacer algunas propiedades, por lo que en base a esto realizamos desarrollamos el ejercicio.

Podemos ver que tenemos los siguientes operadores temporales y los conectivos:

Obtenida de LTS capítulo 14

Se nos pide formalizar la siguiente oración acerca de la maquina vending en LTL.

3) The recharge transaction occurs infinitely often.

Podemos expresar como T la operación de recarga, entonces, para decir que esta operación ocurre infinitamente utilizaremos los operadores temporales:

□   =    siempre

◇   =     eventualmente

Por lo tanto expresamos con T la operación de recarga,  para concluir que.

□◇T

Bibliografía
Capítulo 14 LTL Link

martes, 6 de noviembre de 2012

Aplicaciones de Automatización y Control

Para esta semana nos toca investigar acerca de una aplicación que utiliza los conceptos aprendidos en clase, por lo que realizamos una búsqueda en google scholar en donde encontramos algún paper y explicarlo en esta entrada, por lo que yo estuve buscando algo relacionado con mi proyecto y exponer un breve resumen de lo leído  este es un paper llamado Active Noise Control System from Headphone Applications [1], escrito por Sen. M. Kuo, Sohini Mitra y Woon-Seng Gan.

En el paper que estuve leyendo vemos un diseño y una implementación de un sistema adaptativo en el cual podemos capturar el sonido exterior para crear un ambiente de menos sonido dentro de la capucha del audífono en donde se busca primero que nada el no utilizar mucho los recursos del micrófono que captura el ruido exterior y que también pueda predecir ese parámetro para crear una segunda fase en la cual se tiende que la señal del error tienda a 0.

Actualmente existen sistemas que utilizan una versión del Active Noise Control[2] en donde constantemente se captura el ruido y va comprando esa salida con lo que se genera de entrada para apegarse a que no exista más ruido exterior al que se tiene dentro de los audífonos  ellos consideran que este modelo no es lo suficientemente eficiente y por eso escriben ese paper para demostrar que sería mejor hacer ciertas modificaciones por el ejemplo el colocar de manera estratégica el micrófono para que solamente cada cierto tiempo de manera de entrada se capture ese dato y por medio de un procesamiento pueda ir adaptando de una mejor manera la señal de exaltación interior de la capucha, que en este caso utilizan música, aunque pudiera ser alguna otra cosa como audífonos especiales para ingeniería en donde se reciben comandos hablados[3] pero en el lugar donde se posicionan existe mucho ruido, llámese una planta o en alguna máquina, se necesita que el trabajador pueda escuchar estos comandos a pesar del ruido exterior.

Lo que hacen es tener una señal de referencia z que se captura de la fuente de ruido, para luego de esta entra a un procesado en donde procuran que la señal de control que altera el speaker interior de la capucha para producir un llamado antinoise que hace el aumento o disminución del audio producido, el micrófono por su parte mide el ruido residual y lo miniza por medio del procesamiento que genera al ANC al tratar de imitar o sintetizar la señal de referencia en lugar de utilizar el micrófono en si, si no que se tiene de una manera artificial ahorrando recursos y haciendo incluso el diseño de un ANC normal de manera más compacta, ya que los que se utilizan ellos nos dicen que tienen múltiples micrófonos, convirtiendo la señal digital a analógico de cada uno de ellos.

Por lo tanto, podemos decir que ellos en base a conceptos algoritmos adaptativos , ellos utilizan uno llamado FXLMS[4] que es el filtrado de la media cuadrada y poniendola como en una segunda forma de función de transferencia modelada para tomar los datos sintetizados del micrófono y generar la salida, también en base a la materia de control, ellos explican como diseñaron su sistema, al igual que uso de electrónica vista en materias de computo integrado.

Considero que este diseño que exponen es interesante, pero aunque se necesiten más recursos para estar captando y actualizando el ruido exterior resulte más costoso que de esta forma, creo que podemos tener un mejor audio interno actualizando a lo que está pasando en el exterior y no de una manera artificial, aunque ellos demuestren lo contrario.

Referencias.
[1] Active Noise Control System for Headphone Applications - Sen M. Kuo, Sohini Mitra -Liga
[2] Active Noise Control - Liga
[3] Electronic Hearing NoiseBuster - (Empresa que hace este tipo de audifonos) - Liga
[4] Algoritmo FXLMS - Liga

Tarea 10: expresión ω-regular & NBA

Para esta tarea tenemos que inventar una expresión regular ω y hacer el diagrama del automata no determinista de Büchi.

Una expresión ω-regular G en ∑ tiene la forma:
G = E1F1 ω + ... + En Fn ω 

Donde E1, ... , En y F1, ... , Fn son expresiones regulares de ∑ y Λ∉L(Fi) para todas i.

Un lenguaje de G es:
L(G) = L(E1)L(F1)ω U ... U L(En)L(Fn)ω


Por lo tanto, pongo la siguiente expresión.

(A+B)+(AB)ω

 




 Este sería mi NBA.

 Bibliografía.
  • Concurrency - Slides - Link
  • Principles of Model Checking - Christel Baier - Link
  • Automata - Berndt Farwe - Link

jueves, 1 de noviembre de 2012

Lab 5: Factores cuadráticos

B.8.6 Dado
 Demuestre que:


Para poder demostrar estuve investigando como podemos decir que eso es correcto, por lo que primero que nada debemos de entender que la salida en estado estacionario de una función de transferencia de un sistema lo podemos obtener mediante la función de transferencia sinusoidal, esto quiere decir, que vamos a sustituir lo que es jωn en cada s que tenemos en nuestra función de transferencia, en donde la ω es la frecuencia , y la ωn es la frecuencia esquina para el factor cuadrático, ahora vamos a proceder con las formulas dadas.


Sustituimos
 Lo ponemos de modo que tengamos los factores cuadráticos en base a los 4 factores básicos que nos proponen en el libro, tenemos:


Por lo tanto, como sabemos, tenemos números complejos y partiendo de que cerca de la frecuencia ω = ω_n, hay un pico de resonancia, el factor de amortiguamiento relativo determina la magnitud de este pico, por lo tanto consideramos que son 1 y el numero complejo al cuadrado es -1, decimos que:

Por lo que hemos demostrado que:

Bibliografía.
[1] Chapter 8: Frecuency analysis, Modern Control Engineering, Fifth Edition, Katsuhiko Ogata.

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