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

ES 2 458 215 B1 19 OFICINA ESPAÑOLA DE PATENTES Y MARCAS ESPAÑA 11 21 Número de publicación: 2 458 215 Número de solicitud: 201200608 51 Int. CI.: G06F 17/10 (2006.01) 12 PATENTE DE INVENCIÓN B1 54 Título: Dispositivo para generar funciones multivariables afines a tramos con computación on-line del árbol de búsqueda 73 Titular/es: UNIVERSIDAD DE SEVILLA (50.0%) OTRI-Pabellón de Brasil, Paseo de las Delicias s/n 41013 Sevilla (Sevilla) ES y CONSEJO SUPERIOR DE INVESTIGACIONES CIENTÍFICAS (50.0%) 72 Inventor/es: ACOSTA JIMÉNEZ, Antonio José; BATURONE CASTILLO, María Iluminada; CASTRO RAMÍREZ, Javier; JIMÉNEZ FERNÁNDEZ, Carlos Jesús; BROX JIMÉNEZ, Piedad y MARTÍNEZ RODRÍGUEZ, Macarena Cristina 74 Agente/Representante: GONZÁLEZ CARVAJAL, Ramón 22 Fecha de presentación: 04.06.2012 43 Fecha de publicación de la solicitud: 30.04.2014 Fecha de la concesión: 05.02.2015 45 Fecha de publicación de la concesión: 12.02.2015 56 Se remite a la solicitud internacional: PCT/ES2013/000134 57 Resumen: 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. Se puede realizar consulta prevista por el art. 37.3.8 LP. Aviso: DISPOSITIVO PARA GENERAR FUNCIONES MULTIVARIABLES AFINES A TRAMOS CON COMPUTACION ON-LINE DEL ARBOL DE BOSQUEDA La presente invenciOn se refiere a un dispositivo que permite la generacion de 5 funciones multivariables afines a tramos con computaci6n on-line del arbol de busqueda. Se enmarca en el ambito de la automatica y el control permitiendo implementar procesamiento de serial no lineal y/o controladores para cualquier planta cuya superficie de control sea definible mediante funciones afines a tramos. 10 ESTADO DE LA TECNICA ANTERIOR La necesidad de implementar funciones afines a tramos surge de forma natural en muchos problemas de ingenieria como son el control adaptativo, el control difuso, la identificaciOn de sistemas no lineales dinamicos o las redes de sensores. La 15 realizaciOn de las funciones lineales a tramos mediante circuitos VLSI tiene muchas aplicaciones practicas, principalmente en el ambito de sistemas de control empotrados en tiempo real o siempre que no es viable o conveniente recurrir a procesadores, microcontroladores o dispositivos de proposito general, como por ejennplo las placas que incorporan elementos DSP (Digital Signal Processing). 20 Una funcion afin a tramos (PWA), f p w A : D definida sobre un dominio compacto D c R n , verifica que: f P w A N = x + , X C O , , 1 = 1 , .. . , N p donde f i E R n , g , c R y fli son N p regiones poliedricas, denominadas politopos, que no se solapan y cuya union da lugar a D, es decir, inducen una partici& poliedrica en el 25 dominio D; donde cada politopo es una region cerrada delimitada por hiperplanos (hri x + k i = 0, donde h, E R n , k e R ) ; y donde en todo el dominio se podran distinguir N E hiperplanos que delimitan los politopos, en donde cada hiperplano divide el dominio en dos partes, y la funci6n fp w A es afin sobre cada politopo, cl,; de tal forma que el problema de localizacion del punto tiene como objetivo encontrar el indice i tal que x E 30 Q, para asi proporcionar la funciOn afin en ese punto. Del estado de la tecnica se conocen diversos trabajos sobre la implementaciOn electrOnica de funciones afines a tramos dependientes de multiples entradas. Entre los circuitos conocidos, las implementaciones analogicas no son lo suficientennente 35 robustas por lo que en los ultimos tiempos se han propuesto implementaciones digitales, orientadas a realizaciones sobre hardware reconfigurable como las FPGAs (Field Programmable Gate Arrays), especialmente interesantes para la realizaciOn de prototipos, u orientadas a realizaciones de circuitos integrados (ICs) dedicados, tambien conocidos como ASICs (Application Specific Integrated Circuits). Por lo 40 general, aunque las implementaciones sobre FPGAs son factibles, las soluciones ASIC sobre tecnologias VLSI (Very Large Scale Integration) proporcionan mejor rendimiento y son mas adecuadas para el diserio de sistemas empotrados. La implementacion electrOnica de funciones PWA asi como otras funciones no lineales para controladores difusos ya se conoce del estado de la tecnica. El problema de 45 realizar funciones multivariables PWA se resuelve en el estado de la tecnica [1 y 2] empleando un dispositivo DSP comercial. Otros documentos del estado de la tecnica ES 2 458 215 A1  2 ES 2 458 215 B1 DESCRIPCIÓN analizan cOmo incluir controladores difusos no lineales (en particular PWA) en aplicaciones empotradas. A este respecto el documento [3] describe come implementar el controlador difuso como un modulo a medida IP que acelera las tareas de inferencia de un procesador de proposito general. La publicaciOn en [4] describe 5 una metodologia de disefio basada en herramientas de CAD que permiten el rapid° diseno de controladores difusos complejos que son implementados en un DSP de punto fijo. Los dos ASICs digitales descritos en [5] implementan funciones no lineales tipicas del control difuso. Por ültimo, la solucion FPGA descrita en [6] tambien esta orientada a la implementacion de un controlador difuso. 10 Asimismo se han estudiado distintas formas can6nicas para la implementaciOn de funciones PWA multivariables. Las representaciones canonicas realizan una descripciOn de una funci6n PWA utilizando el nnenor numero de parametros posibles. La elecciOn de una determinada forma canOnica es fundamental, sobre todo en aplicaciones donde se trabaja con funciones definidas sobre un dominio de muchas 15 dimensiones o definidas sobre un dominio de pocas dimensiones pero muy particionado. La forma canonica denominada PieceWise-Affine Simplicial (PWAS) realiza una partici& del dominio de entrada en regiones denominadas `sinnplices'. En el estado de la tecnica se propone tambien una arquitectura para la realizacion de circuitos 20 integrados de sena' mixta de funciones PWAS. Se conoce un ASIC digital que implementa controladores PWAS, y se conoce un diseiio de un circuito integrado mixto que implementa funciones PWAS de tres entradas en una tecnologia CMOS 0.5 pm. Mas recientemente, varias arquitecturas han sido presentadas para la realizacion 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 prinnera de ellas es la denominada "maldiciOn de la dimensionalidad", que consiste en que el numero de parametros necesarios para definirlas crece exponencialmente con el nOmere de dimensiones del dominio. La segunda limitaciOn de la forma canOnica 30 PWAS es que no es capaz de generar cualquier tipo de funci6n PWA sino solo un subconjunto de ellas. Las realizaciones microelectronicas reportadas reducen aCin mas este subconjunto porque emplean un nOmero maxim° de particiones por dimensi6n que no es muy elevado. Otra forma canonica es la basada en la representacion 'lattice' descrita en [8], que ha 35 sido implementada sobre FPGAs utilizando un flujo de diseno basado en las herramientas ISE y System Generator de Xilinx. Una limitacion de esta forma canonica es que tan solo permite la realizacion de funciones afines continuas. Otra soluciOn consiste en realizar la implementacion de una arquitectura jerarquica, donde la funcion PWA multivariable se descompone en modules, que implementan 40 funciones PWA uni-dimensionales, conectados en cascada. Esta arquitectura ha sido explorada para distintos casos de estudio, implementandose sobre FPGAs en [9]. Como ocurre con la forma canonica PWAS, esta solucion no es capaz de generar cualquier tipo de fund& PWA sino sOlo un subconjunto de ellas. La Unica representacion canOnica que permite implementar cualquier funci6n PWA es 45 la denominada PWA generica (PWAG). Solo existen dos circuitos digitales propuestos en la literatura que implementan funciones PWAG [10, 11]. Ambos circuitos emplean ES 2 458 215 A1  3 ES 2 458 215 B1 arquitecturas destinadas a explorar un arbol de bCisqueda binario para resolver el problema de localizaciOn del punto. El arbol se construye para minimizar su profundidad (maxima distancia entre la raiz y las hojas del arbol) y para obtener la mayor simetria posible, mediante el procedimiento descrito en [12]. En [10] no se 5 propone una arquitectura especifica para implementar funciones PWAG, sino que se realiza una sintesis hardware directa a partir de una descripciOn en alto nivel (lenguaje C) de la funciOn PWAG que emplea el algoritmo basado en el arbol de bCisqueda binario. La sintesis hardware emplea la herramienta PICO-NPA. Cualquier modificaci6n de la funcion PWA que implique un cambio en el arbol de bCisqueda 10 binario, requiere repetir todo el procedimiento de sintesis para obtener un circuito digital nuevo. En [11], se recorre el arbol de bOsqueda binario utilizando una nriaquina de estados finitos. Del mismo modo que ocurre en [10], una modificaci6n del arbol implica una nueva descripcion HDL (Hardware Description Language) que debe programarse nuevamente en la FPGA. Esto significa que la FPGA debe extraerse de 15 su contexto de operaci6n para ser de nuevo configurada o que su entorno de operacion debe complicarse considerablemente para poder ser reconfigurada 'in situ'. Referencias: 20 [1] R. Rovatti, A. Ferrari, M. Borgatti, "Automatic implementation of piecewise-linear fuzzy systems addressing memory-performance tradeoff," in Fuzzy hardware: architectures and applications, A. Kandel and G. Langholz, Eds. Norwell, MA, USA: Kluwer Academic Publishers, 1998, pp. 159-179. 25 [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. Sanchez-Solano, A. Cabrera, I. Baturone, F. J. Moreno-Velo, M. Brox, "FPGA 30 implementation of embedded fuzzy controllers for robotic applications", IEEE Trans. on Industrial Electronics, Vol. 54 (4), pp. 1937-1945, Aug. 20077 [4] I. Baturone, F. J. Moreno-Velo, V. Blanco, J. Ferruz, "Design of embedded DSP- based fuzzy controllers for autonomous robots", IEEE Trans. on Industrial Electronics, 35 Vol. 55, pp. 928-936, Feb. 2008, 40 [5] I. Baturone, A. Barriga, S. Sanchez Solano, C.J. Jimenez Fernandez, D.R. Lopez, "Microelectronic design of fuzzy logic-based systems", CRC Press, March 2000, ISBN: 0849300916. [6] P. Echevarria, M. Martinez, J. Echanobe, I. del Campo, J. Tare la, "Digital hardware implementation of high dimensional fuzzy systems," in Applications of Fuzzy Sets Theory, ser. Lecture Notes in Computer Science. Berlin: Springer, 2007, pp. 245-252. 45 [7] M. Storace, T. Poggi, "Digital architectures realizing piecewise-linear multi-variate functions: two FPGA implementations", Int. Journal of Circuit Theory and Applications, Vol. 39(1), pp. 1-15,2011. ES 2 458 215 A1  4 ES 2 458 215 B1 [8] M. C. Martinez-Rodriguez, I. Baturone, P. Brox, "Design Methodology for FPGA Implementation of Lattice Piecewise-Affine Functions", in Proc. 2011 Int. Conf. on Field-Programmable Technology (FPT), New Delhi (India), 12-14 Dec., 2011, pp. 1-4. 5 M. C. Martinez-Rodriguez, I. Baturone, P. Brox, "Circuit Implementation of Piecewise- Affine Functions Based on Lattice Representation", in Proceedings of the 2011 European Conference on Circuit Theory and Design (ECCTD), Link6ping, Sweden, 29- 31 August, 2011, pp. 644-647. 10 [9] I. Baturone, M. C. Martinez-Rodriguez, P. Brox, A. Gersnoviez, S. Sanchez-Solano "Digital implementation of hierarchical piecewise-affine controllers", in Proc. of the 21th IEEE International Symposium on Industrial Electronics (ISIE), Gdansk, Poland, 27-30 June, 2011, pp. 1497-1502. 15 [10] T. Johansen, W. Jackson, R. Schreiber, and P. Tondel, "Hardware synthesis of explicit model predictive controllers," IEEE Trans. on Control Systems Technology, Vol. 15 (1), pp. 191-197, Jan. 2007. [11] A. Oliveri, T. Poggi, M. Storace, "Circuit implementation of piecewise-affine 20 functions based on a binary search tree", in Proc. European Conference on Circuit Theory and Design (ECCTD), Antalya (Turkey), 23-27 Aug., 2009, pp.145-148. [12] P. Tondel, T. Johansen, and A. Bemporad, "Evaluation of piecewise affine control via binary search tree," Automatica, Vol. 39 (5), pp. 945-950, May 2003. 25 EXPLICACION DE LA INVENCION La presente invenciOn propone un dispositivo para generar funciones multivariables afines a tramos, en donde se realiza la computaciOn on-line del arbol de busqueda 30 para la localizaciOn del valor de entrada en los politopos de la particion, y la posterior generaci6n de la correspondiente funci6n afin. El dispositivo para generar funciones multivariables afines a trannos de la presente invencion comprende una arquitectura para circuitos digitales que innplementa funciones PWA en su forma generica (PWAG). La arquitectura permite implementar 35 cualquier funciOn PWA, incluidas aquellas que no pueden ser implementadas por las soluciones dirigidas a formas PWAS, "lattice" o jerarquicas. La arquitectura de la presente invenciOn permite configurabilidad y programabilidad 'in situ', siendo posible modificar el arbol de busqueda y la funci6n PWA sin necesidad de generar un nuevo circuito. Este procedimiento permite que con un Onico circuito digital puedan 40 implennentarse distintas funciones PWA. Por lo tanto, se pueden abarcar distintas aplicaciones industriales configurando y programando adecuadamente el circuito. La invencion hace referencia a la implementaciOn electronica VLSI de funciones afines a tramos (PWA) en su solucion generica (PWAG). Estos circuitos son de innnediata 45 aplicaciOn en aplicaciones de control que puedan resolverse nnediante control predictivo basado en modelo (MPC, Model Predictive Control). En las soluciones existentes en el estado de la tecnica del tipo PWAG, el problema de localizacion del ES 2 458 215 A1  5 ES 2 458 215 B1 punto dentro del politopo, se resuelve mediante la construcci6n del arbol de busqueda binario de forma externa al circuito (off-line). En la presente invencion, la construcci6n del arbol de bUsqueda binario se realiza internamente, es decir on-line. Para ello se emplea un esquenna basado en dos memorias digitales. La primera memoria (memoria 5 del arbol) almacena los posibles estados del arbol, mientras que la segunda memoria (memoria de parametros) almacena los parametros que sirven para computar la funci6n mediante una unidad aritmetica. La memoria de parametros contiene los coeficientes y los offsets que emplea la unidad 10 aritmetica para computar las funciones afines asociadas a los politopos y a los hiperplanos de la particiOn poliedrica. La memoria del arbol almacena las direcciones de la memoria de parametros. Las principales ventajas de la presente invenciOn son la programabilidad, ya que el usuario puede programar distintas particiones con distintas funciones afines, y la 15 configurabilidad, ya que puede emplearse el mismo circuito para resolver problemas que requieran diferentes nOrneros de entradas o arboles de bUsqueda con distinta profundidad y estructura. Al ser directannente integrable en un Circuito Integrado de Aplicaciones Especificas (ASIC) sus requisitos de area, prestaciones temporales y de consumo nnejoran en al nnenos un orden de magnitud las soluciones programables off- 20 line. En tal sentido se puede considerar un generador universal PWA de altas prestaciones. BREVE DESCRIPCION DE LOS DIBUJOS 25 FIG. 1 muestra el arbol de busqueda que tiene una profundidad d . FIG. 2 muestra el esquema de recorrido del arbol binario con el dispositivo, mostrando la arquitectura del dispositivo. 30 FIG. 3 muestra el diagrama de bloques de la arquitectura de la invenciOn. FIG. 4 muestra el esquema a nivel de bloques del ASIC que se ha diseriado como prueba del dispositivo. 35 EXPOSICION DETALLADA DE MODOS DE REALIZACION La presente invenciOn describe un dispositivo para generar funciones multivariables afines a tramos, compuesto par una arquitectura con cuatro bloques funcionales 40 siendo estos: - un bloque unidad de control (1) - un bloque de memoria del arbol (2) - un bloque de memoria de parametros (3) y - un bloque de unidad aritmetica (4) ES 2 458 215 A1  6 ES 2 458 215 B1 que presenta at menos tres modos de operacion seleccionables mediante distintos valores de un bus ( c on f i g ) : escritura de la memoria del arbol (2), escritura de la memoria de parametros (3) y evaluacion de la funcion afin. 5 En el dispositivo se realiza la computacion on-line del arbol de busqueda para la localizacion del valor de entrada en los politopos de la particion, y la posterior generacion de la correspondiente funci6n afin; y donde una funci6n afin a tramos (PWA), fpwA: D — + R , definida sobre un dominio compacto D c R n , verifica que: f p w A ( x ) = x + g i , X E Q , , i = 1 , . . . , N p (1) 10 donde f , E E R y Qi son N p regiones poliedricas, denominadas politopos, que no se solapan y cuya union da lugar at dominio D, es decir, inducen una partici& poliedrica en el dominio D; donde cada politopo es una region cerrada delimitada por hiperplanos ( h T i x + k = 0, donde k e R " , k c R ) ; y donde en todo el donninio se podran distinguir N E hiperplanos que delimitan los politopos, en donde cada 15 hiperplano divide el dominio en dos partes, y la funci6n f p w A es afin sobre cada politopo, 0,; de tal forma que el problema de localizaciOn del punto tiene como objetivo encontrar el indice i tal que x E 0, para asi proporcionar la fund& afin en ese punto; y donde la resoluciOn de este problema parte de la construed& de un arbol de busqueda y posteriormente su exploracion. El procedimiento que se implementa en el 20 dispositivo objeto de la invencion se caracteriza porque el arbol de bUsqueda binario lo constituyen una Unica raiz, que es un primer estado S[1] que se bifurca en dos estados, que son un segundo estado S[2] y un tercer estado S[3] que a su vez y sucesivamente se van bifurcando en dos estados, tat que para una profundidad del arbol d , el nt:imero de estados es 2d-1, siendo los 2d-1 estados del nivel mas profundo 25 las hojas del arbol; y donde el problema de localizacion del valor de entrada en los politopos equivale a la evaluaciOn iterativa de funciones afines cuyos parametros ( h i , k i) son valores reales; y donde es posible localizar el politopo que contiene el vector de entrada realizando sucesivamente las comparaciones ( h T i x + k < 0 ) ; y donde la exploracion del arbol de bCisqueda on-line se realiza de tal forma que dado un vector x, 30 se comienza desde el primer estado S[1] chequeando si hT1 x + k l < 0 : si es cierto, se selecciona la rama que conduce at segundo estado S[2], si no es cierto, se selecciona la que conduce al tercer estado S[3], repitiendose el proceso hasta que se alcanza una hoja. En la figura 1 se observa el arbol binario. En la figura 2 esta representada la exploracion del arbol de busqueda on-line mediante el dispositivo de la invencion 35 (ilustrando la exploraciOn por el estado S[2d-2]). Esta exploraciOn se realiza desde la raiz a las hojas. En la figura 3 se aprecia el diagrama de bloques de la arquitectura del dispositivo, los cuales ejecutan las siguientes operaciones: 40 - el bloque unidad de control (1) conduce la operacion del sistema en todos los modos de operacion, controlando la adquisicion de la entrada de datos al circuito, generando las sefiales de habilitacion de los dernas bloques (escritura o lectura en las memorias, a traves de senates wirMA y wirMP), el bus de datos x a la unidad aritnnetica (4) y la serial de validacion de salida correcta ( v a li d ou t ) . 45 ES 2 458 215 A1  7 ES 2 458 215 B1 - el bloque de memoria del arbol (2) almacena el arbol de busqueda binario y los valores que configuran el numero de entradas y la profundidad del arbol. En una realizacion de la invencion el bloque memoria de arbol emplea una memoria RAM. El usuario puede redisefiar el arbol reprogramando la memoria, permitiendo la 5 computacion de la funcion PWA on-line. Este bloque de memoria del arbol (2) contiene 2dmax palabras, por lo que permite programar arboles de profundidad maxima dm, donde el n0rnero de posibles estados es 2dmax-1. De las 2dmax palabras, 2dmax-1 son las direcciones de la memoria de parametros (3) y la longitud de cada palabra es log2(Nmax), siendo Nmax el nOmero maxim° de politopos e hiperplanos que pueden 10 programarse para conformar una particion. La palabra restante de la memoria que no almacena direcciones de la memoria de parametrosi se usa para almacenar los bits que configuran el nOmero de entradas y la profundidad del arbol de la aplicaciOn concreta en la que se vaya a emplear el dispositivo de la invenciOn. - el bloque de memoria de parametros (3) almacena los parametros f , g , h y k 15 necesarios para computar las funciones afines asociadas a los hiperplanos de la partici& y a los politopos. Todos los parametros que se necesitan para la computaci6n de una funcion afin o de un hiperplano se deben almacenar en la misma direccion de memoria, pudiendose conseguir toda la informacion con un &flop acceso. Este bloque tiene tantas palabras como nOrnero maxim° Nmax de politopos (Np) mas hiperplanos 20 (NE) describen la funciOn PWA. La longitud de cada palabra del bloque de memoria de parametros (3) es la suma de las longitudes de los parametros necesarios para computar la expresiOn afin, tal que en un caso n-dimensional con parametros de m , bits la longitud de palabra es m l + m 2 + , . . + m n + m n . 1 bits. - el bloque unidad aritmetica (4) realiza la computaci6n de la funcion afin como la que 25 aparece en la ecuaciOn (1), a traves de un conjunto de multiplicadores y sumadores. Este bloque puede operar con una arquitectura en serie o en paralelo. El dispositivo objeto de la presente invencion posee una arquitectura de doble memoria y es de inmediata realizaciOn en un circuito integrado de aplicaciones 30 especificas, de forma que sobrepasa en al menos un orden de magnitud las prestaciones temporales y de potencia de las soluciones existentes basadas en lOgica programable. Es de aplicacion en el ambito de la Autornatica y el Control, ya que es capaz de implementar procesanniento de serial no lineal y/o controladores para cualquier planta cuya superficie de control sea definible mediante funciones afines a 35 tramos. Su configurabilidad y programabilidad permite adecuar la funciOn PWA al problema sin necesidad de redisefiar el circuito. El dispositivo propuesto presenta al menos tres modos de operacion diferentes, siendo estos: el modo de escritura de memoria del arbol (2), el modo de escritura de memoria 40 de parametros (3) y el modo de evaluacion de la funcion afin. En una realizacion preferente incorpora un cuarto modo de operacion, que es el nnodo test. En el modo de escritura de la memoria del arbol (2) el circuito de control del dispositivo activa las sefiales especificas de la escritura de datos en la memoria del arbol (2) 45 habilitando la escritura de los estados en dicha memoria del arbol (2), dependiendo el mecanismo de escritura de las sefiales de entrada de la mennoria y dependiendo la temporizaciOn de dicha escritura del tipo de memoria empleada. ES 2 458 215 A1  8 ES 2 458 215 B1 En el modo de escritura de memoria de parametros (3) el circuito de control active las seriales especificas de la escritura de datos en la memoria de parametros (3) habilitando la escritura de los parametros f , g , h y k correspondientes a la partici& y distintas funciones afines de cada politopo, dependiendo el mecanismo de escritura de 5 las setiales de entrada de la memoria de parametros (3) y dependiendo la temporizacion de dicha escritura del tipo de memoria empleada. En el modo de operaci6n de evaluacion de la funci6n affn el circuito de control del dispositivo active las seriales especificas de la lecture de datos en el bloque de 10 mennoria del arbol (2) y en el bloque de memoria de parametros (3). Se realize la explored& del arbol para la localized& del valor de la entrada dependiendo el mecanismo de lecture de las seriales de entrada de la memoria de parametros (3) y dependiendo la temporizaci6n de dicha lecture del tipo de memoria empleada. El circuito de control determina a partir del estado actual, (por ejemplo S[2d-2], como se 15 aprecia en el ejemplo de la figura 2, la posici6n correspondiente en el bloque de memoria del arbol (2), que contiene la direccion de la memoria de parametros (3) que almacena los valores ( h , k ) correspondientes a la evaluaciOn de ese hiperplano. A su vez, la unidad aritmetica (4) realize la operacion conducente a evaluar si h T x + k < 0 , tal que la serial ( d ec i s i on ) se hace 1 y la unidad de control (1) selecciona una de las 20 ramas del arbol binario (la hoja S[2d-1], en la figura 2). Si la evaluaciOn no es cierta, ( d e c i s i on ) se hace 0 y se selecciona la otra rama del arbol binario (la hoja S[2d-1+1] en el ejemplo de la figura 2); la informaci6n sobre el estado pr6ximo que se alcanza se comunica al bloque de unidad de control (1) a traves de esta serial ( d e c i s i on ) ; al ser conocida y programable por el usuario la profundidad del arbol, el bloque de unidad de 25 control (1) reconoce cuando se ha alcanzado una hoja. En una realized& preferente se trabaja con numeros con signo, de forma que el bit de signo se puede utilizer directamente como la serial ( d ec i s i On ) que controla por cual de las ramas del arbol hay que seguir la busqueda. 30 En una realized& preferente de la invenciOn, el dispositivo permite un modo de operacion de test. En este caso el bloque unidad de control (1) del dispositivo active las setiales necesarias para almacenar en un registro de desplazanniento las direcciones y contenidos de las memorias, extrayendose mediante un protocolo 35 adecuado y permitiendose la verificaciOn del correct° funcionamiento del dispositivo o en caso de fallo permitiendose detectar que bloque o bloques son los causantes del fallo. El dispositivo de la invencion es a la vez programable y configurable. La 40 configurabilidad permite cambiar la profundidad del arbol de busqueda y el nirmero de entradas, siendo capaz de trabajar con diferentes numeros de dimensiones y tannatios de memoria que determinan la complejidad y tamatio del arbol de bUsqueda binario-y nCimeros de parametros. El paralelismo o la serialidad de las soluciones dependen de la forma en que se implemente la unidad de control (1) y la unidad aritmetica (4), 45 siendo posible cualquier grado de paralelismo sin modificar la arquitectura. La programabilidad permite, una vez seleccionada la configuraciOn deseada, trabajar con diferentes funciones PWA, reprogramando los contenidos de las memories. Por tanto, ES 2 458 215 A1  9 ES 2 458 215 B1  ES 2 458 215 B1 16  ES 2 458 215 B1 17  ES 2 458 215 B1 18