Dispositivo para generar funciones multivariables afines a tramos con computación on-line del árbol de búsqueda.

Dispositivo para generar funciones multivariables afines a tramos,

en donde se realice la computación on-line del árbol de búsqueda para la localización del valor de entrada en los politopos de la partición, y la posterior generación de la correspondiente función afín. El dispositivo es configurable y programable para generar funciones multivariables afines a tramos y está compuesto por una arquitectura con cuatro bloques funcionales siendo éstos: un bloque unidad de control (1), un bloque de memoria del árbol, un bloque de memoria de parámetros y un bloque de unidad aritmética; y presenta al menos tres modos de operación seleccionables mediante distintos valores de un bus (config): escritura de la memoria del árbol, escritura de la memoria de parámetros y evaluación de la función afín. Puede incluir un cuarto modo de operación, que es el modo de test.

DISPOSITIVO PARA GENERAR FUNCIONES MULTIVARIABLES AFINES A TRAMOS CON COMPUTACiÓN ÓN-LlNE DEL ÁRBOL DE BÚSQUEDA

La presente invención se refiere a un dispositivo que permite la generación de funciones multivariables afines a tramos con computación on-line del árbol de búsqueda. Se enmarca en el ámbito de la automática y el control permitiendo implementar procesamiento de señal no lineal y/o controladores para cualquier planta cuya superficie de control sea definible mediante funciones afines a tramos.

ESTADO DE LA TÉCNICA ANTERIOR

La necesidad de implementar funciones afines a tramos surge de forma natural en muchos problemas de ingeniería como son el control adaptativo, el control difuso, la identificación de sistemas no lineales dinámicos o las redes de sensores. La realización de las funciones lineales a tramos mediante circuitos VLSI tiene muchas aplicaciones prácticas, principalmente en el ámbito de sistemas de control empotrados en tiempo real o siempre que no es viable o conveniente recurrir a procesadores, microcontroladores o dispositivos de propósito general, como por ejemplo las placas que incorporan elementos DSP (Digital Signal Processing) .

Una función afín a tramos (PWA) , fpwA: O R, definida sobre un dominio compacto De Rn , verifica que:

=

fpWA (x) fl x+ g¡ , X Eq, i=1, . .., Np donde f¡ E R n, gi E R Y ni son Np regiones poliédricas, denominadas politopos, que no se solapan y cuya unión da lugar a D, es decir, inducen una partición poliédrica en el dominio D; donde cada politopo es una región cerrada delimitada por hiperplanos (hIj x

+ kj 0, donde hj E R n, kj E R) ; Y donde en todo el dominio se podrán distinguir NE

=

hiperplanos que delimitan los politopos, en donde cada hiperplano divide el dominio en dos partes, y la función fPWA es afín sobre cada politopo, ni; de tal forma que el problema de localización del punto tiene como objetivo encontrar el índice i tal que x E ni para así proporcionar la función afín en ese punto.

Del estado de la técnica se conocen diversos trabajos sobre la implementación electrónica de funciones afines a tramos dependientes de múltiples entradas. Entre los circuitos conocidos, las implementaciones analógicas no son lo suficientemente robustas por lo que en los últimos tiempos se han propuesto implementaciones digitales, orientadas a realizaciones sobre hardware reconfigurable como las FPGAs (Field Programmable Gate Arrays) , especialmente interesantes para la realización de prototipos, u orientadas a realizaciones de circuitos integrados (ICs) dedicados, también conocidos como ASICs (Application Specific Integrated Circuits) . Por lo general, aunque las implementaciones sobre FPGAs son factibles, las soluciones ASIC sobre tecnologías VLSI (Ver y Large Scale Integration) proporcionan mejor rendimiento y son más adecuadas para el diseño de sistemas empotrados.

La implementación electrónica de funciones PWA así como otras funciones no lineales para controladores difusos ya se conoce del estado de la técnica. El problema de realizar funciones multivariables PWA se resuelve en el estado de la técnica [1 y 2] empleando un dispositivo DSP comercial. Otros documentos del estado de la técnica analizan cómo incluir controladores difusos no lineales (en particular PWA) en aplicaciones empotradas. A este respecto el documento [3] describe cómo implementar el controlador difuso como un módulo a medida IP que acelera las tareas de inferencia de un procesador de propósito general. La publicación en [4] describe una metodología de diseño basada en herramientas de CAD que permiten el rápido diseño de controladores difusos complejos que son implementados en un DSP de punto fijo. Los dos ASICs digitales descritos en [5] implementan funciones no lineales típicas del control difuso. Por último, la solución FPGA descrita en [6] también está orientada a la implementación de un controlador difuso.

Asimismo se han estudiado distintas formas canónicas para la implementación de funciones PWA multivariables. Las representaciones canónicas realizan una descripción de una función PWA utilizando el menor número de parámetros posibles. La elección de una determinada forma canónica es fundamental, sobre todo en aplicaciones donde se trabaja con funciones definidas sobre un dominio de muchas dimensiones o definidas sobre un dominio de pocas dimensiones pero muy particionado.

La forma canónica denominada PieceWise-Affine Simplicial (PWAS) realiza una partición del dominio de entrada en regiones denominadas 'simplices'. En el estado de la técnica se propone también una arquitectura para la realización de circuitos 20 integrados de señal mixta de funciones PWAS. Se conoce un ASIC digital que implementa controladores PWAS, y se conoce un diseño de un circuito integrado mixto que implementa funciones PWAS de tres entradas en una tecnología CM OS 0.5 IJm. Más recientemente, varias arquitecturas han sido presentadas para la realización de circuitos digitales PWAS. Entre ellas cabe destacar, la arquitectura propuesta en [7] de 25 la que se describen dos versiones (una paralela y otra serie) implementadas sobre FPGAs. Las implementaciones PWAS presentan dos importantes limitaciones. La primera de ellas es la denominada "maldición de la dimensionalidad", que consiste en que el número de parámetros necesarios para definirlas crece exponencialmente con el número de dimensiones del dominio. La segunda limitación de la forma canónica PWAS es que no es capaz de generar cualquier tipo de función PWA sino sólo un subconjunto de ellas. Las realizaciones microelectrónicas reportadas reducen aún más este subconjunto porque emplean un número máximo de particiones por dimensión que no es muy elevado.

Otra forma canónica es la basada en la representación 'Iattice' descrita en [8], que ha sido implementada sobre FPGAs utilizando un flujo de diseño basado en las herramientas ISE y System Generator de Xilinx. Una limitación de esta forma canónica es que tan solo permite la realización de funciones afines continuas.

Otra solución consiste en realizar la implementación de una arquitectura jerárquica, donde la función PWA multivariable se descompone en módulos, que implementan funciones PWA uni-dimensionales, conectados en cascada. Esta arquitectura ha sido explorada para distintos casos de estudio, implementándose sobre FPGAs en [9]. Como ocurre con la forma canónica PWAS, esta solución no es capaz de generar cualquier tipo de función PWA sino sólo un subconjunto de ellas.

La única representación canónica que permite implementar cualquier función PWA es la denominada PWA genérica (PWAG) . Solo existen dos circuitos digitales propuestos en la literatura que implementan funciones PWAG [10, 11]. Ambos circuitos emplean

arquitecturas destinadas a explorar un árbol de búsqueda binario para resolver el problema de localización del punto. El árbol se construye para minimizar su profundidad (máxima distancia entre la raíz y las hojas del árbol) y para obtener la mayor simetría posible, mediante el procedimiento descrito en [12]. En [10] no se propone una arquitectura específica para implementar funciones PWAG, sino que se realiza una síntesis hardware directa a partir de una descripción en alto nivel (lenguaje C) de la función PWAG que emplea el algoritmo basado en el árbol de búsqueda binario. La síntesis hardware emplea la herramienta PICQ-NPA. Cualquier modificación de la función PWA que implique un cambio en el árbol de búsqueda binario, requiere repetir todo el procedimiento de síntesis para obtener un circuito digital nuevo. En [11], se recorre el árbol de búsqueda binario utilizando una máquina de estados finitos. Del mismo modo que ocurre en [10], una modificación del árbol implica una nueva descripción HDL (Hardware Description Language) que debe programarse nuevamente en la FPGA. Esto significa que la FPGA debe extraerse de su contexto de operación para ser de nuevo configurada o que su entorno de operación debe complicarse considerablemente para poder ser reconfigurada 'in situ'.

Referencias:

[1] R. Rovatti, A. Ferrari, M. Borgatti, "Automatic implementation of piecewise-linear fuzzy systems addressing memor y -performance tradeoff, " in Fuzzy hardware: architectures and applications, A. Kandel and G. Langholz, Eds. Norwell, MA, USA: Kluwer Academic Publishers, 1998, pp. 159-179.

[2] R. Rovatti, C. Fantuzzi, S. Simani, "High-speed DSP-based implementation of piecewise-affine and piecewise-quadratic fuzzy systems, " Signal Processing, Vol. 80, pp. 951-963, 2000.

[3] S. Sánchez-Solano, A. Cabrera, \. Baturone, F. J. Moreno-Velo, M. Brox, "FPGA implementation of embedded fuzzy controllers for robotic...

1. Dispositivo para generar funciones multivariables afines a tramos, compuesto por una arquitectura con cuatro bloques funcionales siendo éstos:

-un bloque unidad de control (1)

-un bloque de memoria del árbol (2)

-un bloque de memoria de parámetros (3) y

-un bloque de unidad aritmética (4)

que presenta al menos tres modos de operación seleccionables mediante distintos valores de un bus (config) : escritura de la memoria del árbol (2) , escritura de la memoria de parámetros (3) y evaluación de la función afín;

realizándose en el dispositivo la computación on-line del árbol de búsqueda para la localización del valor de entrada en los politopos de la partición, y la posterior generación de la correspondiente función afín; y donde una función afín a tramos (PWA) , fpwA: O -R, definida sobre un dominio compacto De Rn , verifica que:

!PWA (x) =!lx+ g¡ , X EQ, i=1, ..., Np donde f; E Rn, gi E R Y Oi son Np regiones poliédricas, denominadas politopos, que no se solapan y cuya unión da lugar a D, es decir, inducen una partición poliédrica en el dominio D; donde cada politopo es una región cerrada delimitada por hiperplanos (hTj x

+ kj 0, donde hj E Rn, E R) ; Y donde en todo el dominio se podrán distinguir NE

=

hiperplanos que delimitan los politopos, en donde cada hiperplano divide el dominio en dos partes, y la función fPWA es afín sobre cada politopo, 0i; de tal forma que el problema de localización del punto tiene como objetivo encontrar el índice i tal que x E Oi para así proporcionar la función afín en ese punto; y donde la resolución de este problema parte de la construcción de un árbol de búsqueda y posteriormente su exploración, estando dicho árbol de búsqueda constituido por una única raíz, que es un primer estado (8[1]) que se bifurca en dos estados, que son un segundo estado (8[2]) y un tercer estado (8[3]) que a su vez y sucesivamente se van bifurcando en dos estados, tal que para una profundidad del árbol d, el número de estados e.

2. 1, siendo lo.

2. 1 estados del nivel más profundo las hojas del árbol; y donde el problema de localización del valor de entrada en los politopos equivale a la evaluación iterativa de funciones afines cuyos parámetros (hj, kj) son valores reales; y donde es posible localizar el politopo que contiene el vector de entrada realizando sucesivamente las comparaciones (h x + kj < O) ; Y donde la exploración del árbol de búsqueda on-line se realiza de tal forma que dado un vector x, se comienza desde el primer estado (8[1]) chequeando si hT1 x + k1 < O: si es cierto, se selecciona la rama que conduce al segundo estado (8[2]) , si no es cierto, se selecciona la que conduce al tercer estado (8[3]) , repitiéndose el proceso hasta que se alcanza un estado asociado a una hoja del árbol,

estando dicho dispositivo caracterizado porque

-el bloque unidad de control (1) conduce la operación del sistema en todos los modos de operación, controlando la adquisición de la entrada de datos al circuito, generando las señales de habilitación de los demás bloques, esto es, la escritura o lectura en las memorias, a través de señales w/rMA y w/rMP, el bus de datos x a la unidad aritmética

(4) y la señal de validación de salida correcta (vafid_out) ; -el bloque de memoria del árbol (2) almacena el árbol de búsqueda binario y los valores que configuran el número de entradas y la profundidad del árbol; -el bloque de memoria de parámetros (3) almacena los parámetros f, g, h Y k necesarios para computar las funciones afines asociadas a los hiperplanos de la partición y a los politopos, en donde todos los parámetros que se necesitan para la computación de una función afín o de un hiperplano se deben almacenar en la misma dirección de memoria, pudiéndose conseguir toda la información con un único acceso; y donde el bloque de memoria de parámetros (3) tiene tantas palabras como número máximo Nmax de politopos (Np) más hiperplanos (NE) describen la función PWA; y -el bloque unidad aritmética (4) realiza la computación de la función afín.

2. Dispositivo según la reivindicación 1 en donde la longitud de cada palabra del bloque de memoria de parámetros (3) es la suma de las longitudes de los parámetros necesarios para computar la expresión afín, tal que en un caso n-dimensional con parámetros de mi bits la longitud de palabra es m1 + m2 + .. . + mn +mn+1 bits.

3. Dispositivo según una cualquiera de las reivindicaciones 1 a 2 donde el bloque memoria del árbol emplea una memoria RAM, el usuario puede rediseñar el árbol reprogramando la memoria, permitiendo la computación de la función PWA on-line y donde dicho bloque de memoria contiene 2dmax palabras, en el caso de un árbol de profundidad máxima d, donde el número de posibles estados es 2dmax_1. De dichas max2dmax palabras, 2dmax_1 son las direcciones de la memoria de parámetros (3) y la longitud de cada palabra es log2 (N) , siendo Nel número máximo de politopos e maxmax hiperplanos que conforman la partición, y la palabra restante almacena los valores que configuran el número de entradas y la profundidad del árbol.

4. Dispositivo según una cualquiera de las reivindicaciones 1 a 3 en el que, al configurar el modo de operación de escritura de la memoria del árbol (2) , el circuito de control del dispositivo activa las señales específicas de la escritura de datos en la memoria del árbol (2) habilitando la escritura de los estados en dicha memoria del árbol (2) , dependiendo el mecanismo de escritura de las ser"lales de entrada de la memoria y dependiendo la temporización de dicha escritura del tipo de memoria empleada.

5. Dispositivo según una cualquiera de las reivindicaciones 1 a 4 en el que, al configurar el modo de escritura de la memoria de parámetros (3) , el circuito de control del dispositivo activa las señales específicas de la escritura de datos en la memoria de parámetros (3) habilitando la escritura de los parámetros f, g, h Y k correspondientes a la partición y distintas funciones afines de cada politopo, dependiendo el mecanismo de escritura de las señales de entrada de la memoria de parámetros (3) y dependiendo la temporización de dicha escritura del tipo de memoria empleada.

6. Dispositivo según una cualquiera de las reivindicaciones 1 a 5 en el que el dispositivo permite un cuarto modo de operación, que es el modo test; de forma que al configurar el modo de operación de test, el circuito de control activa las señales necesarias para almacenar en un registro de desplazamiento las direcciones y contenidos de las memorias, extrayéndose mediante un protocolo adecuado y permite la verificación del correcto funcionamiento del circuito o en caso de fallo permite detectar qué bloque o bloques son los causantes del fallo.

7. Dispositivo según una cualquiera de las reivindicaciones 1 a 6 en el que al configurar el modo de operación de evaluación de la función afín, el circuito de control activa las señales específicas de la lectura de datos en el bloque de memoria del árbol

(2) Y en el bloque de memoria de parámetros (3) , realizándose la exploración del árbol para la localización del valor de la entrada dependiendo el mecanismo de lectura de las señales de entrada y de la memoria de parámetros (3) y dependiendo la temporización de dicha lectura del tipo de memoria empleada; el circuito de control determina a partir del estado actual la posición correspondiente en el bloque de memoria del árbol (2) , que contiene la dirección de la memoria de parámetros (3) que almacena los valores (h, k) correspondientes a la evaluación de ese hiperplano; la unidad aritmética (4) realiza la operación conducente a evaluar si hT x + k < 0, tal que si la evaluación es cierta, la señal (decisión) se hace 1 y la unidad de control (1) selecciona la rama (u hoja) del árbol binario que esté a su izquierda en el nivel inmediatamente inferior, si la evaluación no es cierta, (decisión) se hace O y se selecciona la rama del árbol binario que esté a su derecha en el nivel inmediatamente inferior; la información sobre el estado próximo que se alcanza se comunica al bloque de unidad de control (1) a través de esta señal (decisión) ; al ser conocida y programable por el usuario la profundidad del árbol, el bloque de unidad de control (1) reconoce cuándo se ha alcanzado una hoja.