Download implementación de funciones lineales a tramos mediante

IMPLEMENTACIÓN DE FUNCIONES LINEALES A TRAMOS MEDIANTE
OPERADORES DE LUKASIEWICZ
N.M. Hussein Hassan, A. Barriga, S. Sánchez-Solano
Instituto de Microelectrónica de Sevilla (CNM-CSIC)
Avda. Reina Mercedes s/n. Edif. CICA. 41012-Sevilla, España
[email protected]
ABSTRACT
2. LÓGICA DE LUKASIEWICZ
Se presenta en esta comunicación una realización
hardware de los operadores de Lukasiewicz. Dichos
operadores los hemos aplicado en la aproximación de
funciones lineales a tramos. Con objeto de analizar las
características de los diseños se comparan las
implementaciones sobre dispositivos FPGA de estrategias
basadas en redes neuronales y basadas en lógica
combinacional.
Un álgebra multivaluada de Lukasiewicz es una
estructura A = ( A,⊕ ,⊗, ¬,0,1) que satisface las siguientes
propiedades:
1. INTRODUCCIÓN
El desarrollo de los conceptos teóricos de las lógicas
multivaluadas se inició en la década de los años 20 por J.
Lukasiewicz, quién estableció la generalización de la
lógica clásica a la lógica multivaluada. Posteriormente, a
finales de los años 50 C.C. Chang formalizó el álgebra
multivaluada basada en la lógica de Lukasiewicz.
Nuestro interés se centra en la aplicación del teorema
de McNaughton que permite representar las formulas de n
variables de Lukasiewicz mediante funciones lineales a
tramos con coeficientes enteros [3]. Estas expresiones
reciben el nombre de funciones McNaughton.
En esta comunicación vamos a mostrar diversas
realizaciones hardware de estos sistemas y los
aplicaremos a la interpolación de funciones. Analizaremos
distintos estilos de realización. Para ello vamos a explorar
realizaciones basadas en el diseño de los operadores de
Lukasiewicz mediante lógica combinacional o bien
mediante redes neuronales.
En el apartado siguiente vamos a realizar una breve
introducción a los conceptos teóricos de la lógica de
Lukasiewicz. A continuación consideraremos la
implementación de los operadores básicos sobre
dispositivos FPGA y la aplicación a un ejemplo de
aproximación de funciones.
•
x ⊕ ( y ⊕ z ) = ( x ⊕ y) ⊕ z
•
x⊕ y = y⊕ x
•
•
•
x⊕0= x
x ⊕1 = 1
¬0 = 1 y ¬1 = 0
•
¬(¬x ⊕ ¬y ) = x ⊗ y
•
x ⊕ (¬x ⊗ y ) = y ⊕ (¬y ⊗ x )
El álgebra multivaluada coincide con el álgebra
booleana si se verifica la idempotencia ( x ⊕ x = x ).
Los operadores vienen definidos de la siguiente forma:
•
x ⊕ y = min(1, x + y )
(1)
•
x ⊗ y = max(0, x + y − 1)
(2)
•
¬x = 1 − x
(3)
Por otro lado, las siguientes conectivas son de utilidad:
•
x ∨ y = max( x , y ) = ( x ⊗ ¬y ) ⊕ y
(4)
•
x ∧ y = min( x , y ) = ( x ⊕ ¬y ) ⊗ y
(5)
Una función continua lineal a tramos, en la que cada
tramo tiene coeficientes enteros, está asociada a una
fórmula de Lukasiewicz [4].
Una función f : [0,1]n → [0,1] es una función de
McNaughton de n variables si se cumplen las siguientes
condiciones:
• f es continua
• f es lineal a tramos, esto es, existen polinomios p1, ...,
pk tal que p i ( x ) = a i • x + bi para todo x ∈ [0,1]n e
índice i ∈ {1,..., k} de manera que f(x)=pj(x).
• Para cada i ∈ {1,..., k} los coeficientes ai, bi son
enteros.
La clase de funciones determinadas por fórmulas de la
lógica de Lukasiewicz coinciden con la clase de funciones
de McNaughton [3]. Una definición importante por su
utilidad es la de función racional de McNaughton. Una
función racional de McNaughton se define como una
función lineal a tramos en la que cada tramo tiene
coeficientes racionales. La importancia de esta definición
radica en que cualquier formula racional de Lukasiewicz
puede implementarse como una función racional de
McNaughton. Por lo tanto estas funciones constituyen
aproximadores universales.
3. OPERADORES BÁSICOS
X
-1
Ψ
-1
+
1
Y
Min(x,y)
1
Ψ
1
(a)
X
1
Ψ
1
+
-1
Y
Max(x,y)
1
Ψ
1
(b)
Figura 1. Operadores min(x,y) y max(x,y) realizados
mediante redes neuronales.
En este apartado vamos a mostrar la realización de los
operadores básicos. Los operadores que vamos a
considerar corresponden a los definidos en las ecuaciones
(1-5). Estos operadores constituyen los elementos básicos
para el diseño de circuitos que permitan aproximar
funciones lineales a tramos como veremos en apartados
posteriores.
La realización de los circuitos operadores básicos se
realizará en función de dos estrategias de diseño: diseño
basado en redes neuronales y diseño basado en lógica
combinacional.
3.1. Diseño basado en redes neuronales
En una primera estrategia de implementación de los
operadores min y max vamos a realizar el diseño mediante
redes neuronales. Para ello nos basaremos en [5] donde se
demuestra que dada una función de activación
ψ ( x ) = 1 ∧ ( x ∨ 0) es posible representar la red neuronal
correspondiente como una combinación de proposiciones
del cálculo de Lukasiewicz.
De acuerdo con lo anterior en [4] se propone las
realizaciones de los operadores min(x,y) y max(x,y) tal y
como se ilustra en la figura 1. Se trata de una red de una
sola capa cuya salida suministra el comportamiento que se
muestra en la figura 2 y que corresponde a las superficies
de dichos operadores.
El diseño de la neurona se describe en la figura 3. En
este ejemplo se han codificado las entradas y salidas de
datos con 8 bits. La figura 3a muestra la descripción del
comportamiento de la neurona. El circuito generado por la
herramienta de síntesis XST de Xilinx se muestra en la
figura 3b.
(a)
(b)
Figura 2. Superficies correspondientes a los operadores
(a) min(x,y) y (b) max(x,y).
function f=net(x,y,wx,wy)
suma=wx*x+wy*y;
if suma >= 0
if suma >=1
f=1;
else
f=suma;
end;
else
f=0;
end;
La tabla 1 muestra los resultados de las distintas
implementaciones sobre FPGAs de Xilinx.
(a)
(a)
(b)
(b)
Figura 3. (a) Descripción funcional y (b) circuito de una
neurona.
(c)
Figura 4. (a) operador min, (b) operador producto
acotado, (c) operador suma acotada.
La realización de los operadores producto y suma
acotados se basa en las expresiones siguientes:
x ⊕ y = min(1, x + y ) = 1 ∧ ( x + y )
x ⊗ y = max(0, x + y − 1) = 0 ∨ ( x + y − 1)
Al considerar la realización de estos operadores como
una red neuronal se puede simplificar el diseño ya que tan
sólo se requiere una neurona. Por lo tanto el coste de las
realizaciones viene determinado por las características del
circuito de la figura 3b.
3.2. Diseño basado en lógica combinacional
La figura 4 muestra el diseño de los operadores min, max
y los operadores de Lukasiewicz mediante componentes
lógicos. Una diferencia entre el estilo de realización de los
operadores mediante redes neuronales y la estrategia
basada en lógica combinacional consiste en que este
último caso se basa en descripciones que contienen
componentes de circuito tales como comparadores,
sumadores, restadores, multiplexores, etc, sin que se
establezca una estructura regular. Esto supone que las
descripciones pueden optimizarse mejor y se reducen las
redundancias en el hardware.
Red neuronal
Lógica combinacional
slices retrasos slices
retraso
min
8
17.63
8
16.58
max
8
17.85
8
16.77
⊕
15
14.84
8
16,89
⊗
13
19.64
13
19.64
Tabla 1. Resultados comparativos de las realizaciones
de los operadores. (Nota: el retraso en nsec)
Las realizaciones de la tabla 1 son diseños puramente
combinacionales ya que hemos primado reducir el tiempo
de procesado. El coste de los circuitos en términos de área
ocupada se expresa mediante slices. Por su parte el
restraso corresponde al caso de retraso máximo de
caminos entre pads de entradas y salidas.
4. APROXIMACIÓN DE FUNCIONES
De acuerdo con la definición de función racional de
McNaughton resulta claro que el uso de los operadores de
Lukasiewicz nos permiten realizar la aproximación de
funciones lineales a tramos. En este apartado nos interesa
analizar cómo puede aplicarse el álgebra de Lukasiewicz
en la aproximación de funciones lineales a tramos. En este
sentido, una primera aproximación a dicho problema se
establece en [6] donde se especifica que una función lineal
a tramos puede describirse mediante la siguiente
expresión:
f ( x) = ∨
∧ gi ( x)
∀x
j∈ J i ∈ S j
donde
la
familia
{S j }j∈J son
(6)
subconjuntos
incomparables (respecto a ⊆ ) de {1, ..., n}.
Con objeto de ilustrar la aproximación de funciones
mediante los operadores de Lukasiewicz vamos a
considerar dos ejemplos. El primero corresponde a una
función de una variable y, a continuación, se tratará el
caso de una función de dos variables:
4.1. Caso de función de una variable.
Sea la función lineal a tramos que se muestra en la figura
5. Dicha función viene descrita por la expresión siguiente:
 g1 = 0
g = x − 3
 2
1
1

f1 ( x ) =  g 3 = 3 x + 3

3
 g 4 = − x + 15
2

 g5 = 0
x<3
3< x < 5
5< x <8
(7)
8 < x < 10
x > 10
Una realización directa de esta función a partir de la
expresión (7) da lugar a la técnica de aproximación basada
en splines. En este caso cada tramo viene determinado por
la recta g i = m i x + ni .
g i = (1 + ni ) ⊗ m i x , por lo que la función anterior viene
dada por la siguiente expresión:
x<3
 g1 = 0
 g = −2 ⊗ x
3< x < 5
 2
g = 4 ⊗ 1 x
5< x <8
f1 ( x ) =  3 3 3

3
 g 4 = 16 ⊗ − x 8 < x < 10
2

x > 10
 g5 = 0
(8)
Por otro lado, haciendo uso de la expresión (6) la
función f1(x) puede expresarse de la siguiente forma:
f1 ( x ) = ( g 2 ∧ g3 ∧ g 4 ) ∨ 0
(9)
donde los términos g2, g3 y g4 vienen dadas por las
funciones descritas en la expresión (8).
La tabla 2 muestra los resultados de la realización de la
función f1(x) sobre FPGA de Xilinx. En este caso se ha
considerado una precisión de 4 bits para la entrada. Dicha
entrada corresponde a un número entero. La salida se
codifica con 8 bits de los que los cuatro más significativos
corresponden a la parte entera y los menos significativos a
la decimal. El coste de área se expresa en términos de
slices ocupados en el FPGA. La realización basada en una
red neuronal consiste en una red multicapa cuyo esquema
se muestra en la figura 6a. El caso de la realización que
emplea los operadores de Lukasiewicz se basa en la
implementación de la expresión (9) y corresponde al
circuito de la figura 6b.
slices
Retraso máx.
162
54.9 ns
25
21.4 ns
Tabla 2. Realizaciones hardware de la función f1(x).
Red neuronal
Oper. Lukasiewicz
3
4.2. Caso de función de dos variables.
2
Vamos a considerar una función con dos variables
descrita en [4] que tiene la expresión siguiente:
f 2 ( x ) = (3 x ∧ 1) ∧ (( x + y ) ∧ 1)
3
5
8
(10)
10
Figura 5. Ejemplo de función lineal a tramos.
Otro tipo de realización puede inferirse al aplicar el
álgebra de Lukasiewicz. En este caso es posible obtener
una expresión de la función haciendo uso de los
operadores de Lukasiewicz. En efecto puede comprobarse
que una función g i = m i x + ni puede expresarse como
Haciendo uso de las expresiones (3) y (4) podemos
rescribir la función f2(x) mediante los operadores de
Lukasiewicz:
F2 ( x ) = [( x ⊕ y ) ⊕ {(¬3 x ⊗ 1) ⊕ 0}] ⊗ [(3 x ⊕ 0) ⊗ 1] (11)
1
1
18
Ψ
x
-5/2
1/3
Ψ
-1
x
1
-3/2
1/3
Ψ
1
15
Ψ
1
-1
1/3
Ψ
f1
1
1/3
(a)
Figura 7. Superficie correspondiente a la función f2(x).
1
y
x
1
1
Ψ
-1
-1
-1
1
Ψ
+
-3
Ψ
1
1
-1
-1
Ψ
f2
-1
1
Figura 8. Realización de f2(x) como una red neuronal.
slices Retraso máx.
36
25.64 ns
32
29.18 ns
Tabla 3. Realizaciones de la función f2(x).
Red neuronal
Oper. Lukasiewicz
(b)
Figura 6. Realizaciones de la función f1(x) basada en
(a) red neuronal, (b) operadores de Lukasiewicz.
La superficie correspondiente a esta función se muestra
en la figura 7.
De nuevo hemos realizado el diseño de dicha función
mediante circuitos sobre FPGA empleando las dos
aproximaciones (red neuronal y operadores de
Lukasiewicz).
La figura 8 muestra el esquema correspondiente a la
red neuronal. Se trata de una red de dos capas con cuatro
neuronas.
La tabla 3 muestra los datos de las implementaciones.
De la observación de las tablas 2 y 3 podemos observar
que las realizaciones basadas en redes neuronales
requieren más recursos hardware que la aplicación de los
operadores de Lukasiewicz como bloques lógicos
combinacionales. Ello se debe a que en el caso de las
redes neuronales se requiere más multiplicadores (sobre
todo en el ejemplo de la tabla 2).
5. APLICACIÓN DE LA INTERPOLACIÓN DE
FUNCIONES A LA COMPRESIÓN DE IMÁGENES
En este apartado vamos a considerar una aplicación a la
interpolación en la que trataremos el suavizado de
imágenes y el problema de la compresión. El objetivo de
esta aplicación es mostrar un ejemplo práctico de
utilización del álgebra de Lukasiewicz. Puesto que se trata
de un estudio preliminar vamos a considerar realizaciones
algorítmicas previas a una implementación hardware. Para
ello mostraremos los resultados del análisis realizado con
Matlab.
La descripción del algoritmo de compresión de
imágenes en Matlab se muestra en la figura 9 para una
imagen 2D en color RGB. La información se almacena en
una matriz de tres dimensiones (img) La función Lprod
corresponde al producto acotado de Lukasiewicz. La
variable d corresponde al índice de compresión de la
imagen. El algoritmo se basa en una interpolación lineal a
tramos.
for k=1:3
for i=1:length(x)
for j=1:(length(y)/d)-1
if (y(d*j+1)-y(d*j-1))==0
A=0;
else
A=(img(i,d*j+1,k)-img(i,d*j-1,k))/(y(d*j+1)-y(d*j-1));
end
B=img(i,d*j-1,k)-A*y(d*j-1);
img_out(i,j,k)=Lprod(B+1,A*y(d*j));
end
end
end
aproximar funciones lineales a tramos. Ello permite
aplicar técnicas de interpolación que tienen aplicaciones
en campos como el control o el tratamiento de imágenes.
Nosotros hemos mostrado un ejemplo de aplicación a la
compresión de imágenes.
Figura 9. Algoritmo de compresión de imágenes.
El ejemplo que se ilustra en la figura 9 realiza la
compresión de columnas. La estrategia de compresión que
hemos usado es muy simple y se muestra en la figura 10a.
Se basa en considerar cada fila (columna) como una
función lineal a tramos en la que cada píxel almacena un
valor entero entre 0 y 255 (codificación con 8 bits). Para
el caso de un índice de compresión de 2 (d=2)
seleccionamos uno de cada 2 pixels aproximando su valor
por la recta que une los pixels vecinos.
(a)
(b)
(c)
255
Figura 10. Ejemplo de compresión y descompresión: (a)
imágen original, (b) imágen comprimida, (c) imagen
descomprimida.
255
10. REFERENCIAS
0
i-1
i
i+1 i+2 i+3
0
i-1
i1
i2
i
(a)
(b)
Figura 10. (a) Algoritmos de compresión (d=2). (b)
Algoritmo de descompresión (d=3),
[1] H.T. Nguyen, V. Kreinovich, A. Di Nola, “Which truth
values in fuzzy logics are definable?,” Int. J. Intelligent Systems,
Wiley Interscience, vol. 18, no. 3, pp. 1057-1064, Oct. 2003.
[2] A. Di Nola, A. Lettieri, “Formulas of Lukasiewicz’s logic
represented by hyperplanes,” 10th International Fuzzy Systems
Association World Congress (IFSA), Istanbul, Turkey, pp. 189194, 2003.
Por otro lado el algoritmo de descompresión también
aplica el criterio de la aproximación lineal a tramos
(figura 10b). En este caso se insertan nuevos pixels entre
cada dos mediante aproximación lineal. La figura 11
muestra el resultado obtenido. Se puede observar los
efectos de la aproximación tanto en la imagen comprimida
(figura 11b) como en la descomprimida (figura 11c).
Puesto que el mecanismo de interpolación se basa en una
aproximación lineal a tramos se observa en la figura 11c
que se trata de una técnica de compresión con pérdidas.
[3] A. Di Nola, A. Lettieri, “On normal forms in Lukasiewicz
logic,” Archive for Mathematical Logic, Springer-Verlag
Heidelberg, vol 43, no. 6, pp. 795-823, Aug. 2004.
9. CONCLUSIONES
[5] J.L. Castro, E. Trillas: “The logic of neural networks”,
Mathware and Soft Computing, vol 5, pp. 23-27, 1998.
Se han presentado diversas realizaciones hardware de
operadores de Lukasiewicz. Ello nos ha permitido
comparar las diferentes estrategias de realización. El
interés de poder implementar sistemas basados en el
álgebra de Lukasiewicz viene dado por la posibilidad de
[4] P. Amato, A. Di Nola, B. Gerla, “Neural Networks and
Rational Lukasiewicz Logic”, Journal of multiple-valued logic
and soft computing, to appear.
[6] S. Ovchinnikov: “Max-min representation of piecewise
linear functions”, Contributions to Algebra and Geometry, vol
43, pp. 297-302, 2002.