El FIR transversal

Un filtro FIR es una suma con pesos fijos de la entrada actual y de las anteriores. El FIR transversal es esa suma dibujada en hardware: una fila de registros por donde la entrada avanza una muestra por tic, una derivación a la salida de cada registro con su multiplicador, y un sumador que junta todo. Es la estructura del slide 17 de la filmina de convolución y la «Transversal Filter» de la filmina de estructuras. No tiene nada que diseñar: la ecuación ya es el circuito.

01 · La definición

Un FIR causal de $N$ coeficientes calcula, en cada instante,

y [n] = \sum_{k = 0}^{N - 1} h [k] x [n - k]

Es la suma de convolución con $h$ finita y causal: la segunda forma de la filmina, la que se lee «la salida actual es una combinación ponderada de la entrada actual y las $N - 1$ anteriores, con pesos $h [k]$ ». La estructura que la implementa tiene tres piezas:

La línea de retardos: $N - 1$ bloques $z^{- 1}$ en fila. Cada uno es un registro que en cada tic entrega lo que recibió en el tic anterior. Juntos son un registro de desplazamiento.
Las derivaciones (taps): una a la entrada de la línea y una a la salida de cada registro, cada una multiplicada por su $h [k]$ . De ahí la jerga: «un FIR de 64 taps» es $N = 64$ , y el nombre en inglés de la estructura es tapped delay line (TDL).
El sumador, que junta los $N$ productos en $y [n]$ .

02 · La ecuación, leída en el dibujo

Cada término de la suma es una columna del diagrama. Se ve en tres pasos, siguiendo una muestra.

Paso 1: cada registro atrasa una muestra. Un $z^{- 1}$ que recibe $x [n]$ entrega $x [n - 1]$ . Después de $k$ registros la línea tiene $x [n - k]$ . Así que en todo instante la línea guarda, en orden, las últimas $N$ entradas: $x [n], x [n - 1], \dots, x [n - N + 1]$ . La más vieja se cae por el final.

Paso 2: cada derivación pesa su muestra. El multiplicador de la columna $k$ recibe $x [n - k]$ y entrega $h [k] x [n - k]$ : el término $k$ de la sumatoria.

Paso 3: el sumador cierra la sumatoria. Suma los $N$ productos y da $y [n]$ . En el tic siguiente la línea avanza, cada muestra pasa a la columna de al lado, y la misma cuenta da $y [n + 1]$ . Los coeficientes no se mueven: se mueve la señal por debajo de ellos. Es el «dar vuelta y deslizar» de la convolución a mano, con la diferencia de que acá lo que se desliza es $x$ .

El mismo dibujo se lee en $z$ . Un bloque $z^{- 1}$ multiplica por $z^{- 1}$ , así que la columna $k$ aporta $h [k] z^{- k}$ y el diagrama entero es el polinomio

H (z) = \sum_{k = 0}^{N - 1} h [k] z^{- k}

No hay ningún camino que vuelva hacia atrás, y por eso no hay denominador: sus raíces son los ceros del filtro, que es tema de polos y ceros.

Con un impulso, la estructura escupe su propio $h$ . Si entra $δ [n]$ , en cada instante hay un solo 1 en la línea. En el instante $n$ está en la columna $n$ , y la salida es el coeficiente de esa columna: $y [n] = h [n]$ . A las $N$ muestras el 1 se cae por el final y la salida queda en cero para siempre. Es la respuesta finita, leída en el circuito.

03 · Lo que cuesta por muestra

El dibujo cuenta sus recursos. Por cada muestra de salida:

$N$ multiplicaciones, una por coeficiente.
$N - 1$ sumas: juntar $N$ números de a dos pide $N - 1$ sumas, se ordenen como se ordenen.
$N - 1$ registros: la muestra actual no se guarda, llega por el cable.

El costo crece lineal con $N$ y no depende de nada más. Un FIR de 101 taps son 101 multiplicaciones por muestra; el IIR de un polo de Ejemplo_filtros.m hace dos. Esa es la cuenta que pesa en la comparación con los IIR.

Los registros arrancan en cero. Antes de la primera muestra la línea está vacía, y eso es suponer $x [n] = 0$ para $n < 0$ : la condición inicial de filter. Cuando la entrada se termina, la línea todavía tiene $N - 1$ muestras adentro. Para vaciarla hay que meter $N - 1$ ceros, y mientras tanto sigue saliendo algo: son las $L_{x} + N - 1$ muestras de conv, contra las $L_{x}$ de filter, que corta en cuanto se acaba la entrada. Es la diferencia de largos que muestra waystofilt.m.

La simulación usa el FIR de 7 taps de la filmina de fase, $h = [0,1, 0,2, 0,3, 0,4, 0,3, 0,2, 0,1]$ , y la entrada de waystofilt.m, $x = [1, 2, 3, 4, 5, 6, - 5, - 4]$ . Son 8 muestras y 7 taps, así que la salida completa tiene $8 + 7 - 1 = 14$ .

En la forma directa los registros guardan entradas enteras, y en cada pulsación se corren un lugar a la derecha. La columna $k$ tiene siempre la muestra que entró hace $k$ tics: a los siete tics el 1 del principio ya se cayó. La salida azul cae una por una sobre los círculos de la convolución, y sigue saliendo después de la última muestra de $x$ , mientras la línea se vacía con ceros. En $n = 9$ la salida es cero exacto por casualidad de los números:

0,3 \cdot (- 4) + 0,4 \cdot (- 5) + 0,3 \cdot 6 + 0,2 \cdot 5 + 0,1 \cdot 4 = 0

Con el impulso, la salida dibuja el propio $h$ y en $n = 7$ se apaga.

04 · La forma transpuesta

La misma $H (z)$ se puede calcular con otro circuito. Sale de reagrupar el polinomio.

Paso 1: sacar $z^{- 1}$ de factor común, una y otra vez. Es la regla de Horner aplicada a $Y (z) = H (z) X (z)$ :

Y = h [0] X + z^{- 1} (h [1] X + z^{- 1} (h [2] X + \dots + z^{- 1} h [N - 1] X))

Paso 2: cada paréntesis es un registro. Se lee de adentro hacia afuera. El paréntesis más interno es $h [N - 1] X$ , que se guarda en un registro. El siguiente es $h [N - 2] X$ más lo que sale de ese registro, y se guarda en otro. Y así hasta afuera. Con $s_{k}$ el contenido del registro $k$ , en el tiempo:

\begin{array}{l} y [n] = h [0] x [n] + s_{1} [n - 1] \\ s_{k} [n] = h [k] x [n] + s_{k + 1} [n - 1], k = 1, \dots, N - 2 \\ s_{N - 1} [n] = h [N - 1] x [n] \end{array}

Paso 3: dibujarlo. La entrada $x [n]$ va a los $N$ multiplicadores a la vez. Abajo, la cadena corre al revés, de derecha a izquierda: cada eslabón es un sumador seguido de un registro, y la salida sale por la izquierda. Es el diagrama directo con las flechas invertidas, los nodos de derivación cambiados por sumadores y la entrada cambiada por la salida: el teorema de transposición de grafos, que garantiza la misma transferencia. Contado, cuesta exactamente lo mismo: $N$ multiplicaciones, $N - 1$ sumas y $N - 1$ registros.

Los registros ya no guardan entradas. Guardan sumas parciales de salidas futuras: $s_{1}$ es todo $y [n + 1]$ menos el término de la muestra que todavía no llegó. En la simulación, elegí «Transpuesta» y llevala a $n = 4$ : los seis registros valen 2,80 · 3,20 · 3,00 · 2,00 · 1,10 · 0,40, y la salida es $0,1 \cdot 5 + 2,80 = 3,30$ , la misma de la forma directa. Son los que da en MATLAB el lazo fir_transpuesta de la sección 08, cortado en ese instante. Cambiá de estructura en cualquier instante: la salida no se mueve, los registros sí.

Por qué conviene en hardware: el camino crítico. En un circuito sincrónico, el período de reloj tiene que alcanzar para que una señal atraviese el tramo combinacional más largo entre dos registros. En la forma directa, con el sumador armado como la cadena del dibujo, ese tramo va de la entrada, pasa por un multiplicador y atraviesa todos los sumadores:

T_{directa} = T_{\times} + (N - 1) T_{+} T_{transpuesta} = T_{\times} + T_{+}

En la transpuesta, entre la entrada y cualquier registro hay un multiplicador y un sumador, y nada más, tenga el filtro 7 taps o 101. La frecuencia de reloj máxima deja de depender de $N$ . Con un árbol de sumadores la directa baja a $T_{\times} + ⌈ \log_{2} N ⌉ T_{+}$ , que para 101 taps son 7 sumadores en serie, pero sigue creciendo con $N$ . La directa también se puede segmentar metiendo registros entre sumadores; eso agrega latencia y registros que la transpuesta no necesita, porque ya viene segmentada.

Tiene dos precios. La entrada alimenta a $N$ multiplicadores a la vez, un cable con mucho abanico de salida. Y los registros guardan sumas, que ocupan más bits que una muestra de entrada, así que en punto fijo la memoria crece. En MATLAB, filter dice implementar la forma directa II transpuesta, que para un FIR es esta.

05 · El FIR plegado

Un FIR de fase lineal tiene coeficientes simétricos, $h [k] = h [N - 1 - k]$ . En la forma directa eso es desperdicio: el mismo número se multiplica dos veces por muestra, contra dos entradas distintas. La nota verde de la filmina de fase lo dice así: este tipo de filtros reduce el almacenamiento de coeficientes y la cantidad de operaciones.

Paso 1: juntar los términos que comparten coeficiente. El término $k$ y el término $N - 1 - k$ llevan el mismo $h [k]$ :

h [k] x [n - k] + h [k] x [n - (N - 1 - k)] = h [k] (x [n - k] + x [n - N + 1 + k])

Es factor común. Una multiplicación menos por cada par, a cambio de una suma previa.

Paso 2: doblar la línea. Para tener las dos muestras de cada par una enfrente de la otra, la línea se dobla por la mitad como una hoja: la primera mitad va hacia la derecha, da la vuelta y vuelve por abajo. La columna $k$ tiene arriba $x [n - k]$ y abajo $x [n - N + 1 + k]$ , un presumador las junta y recién ahí se multiplica. Con $N$ impar sobra la muestra del centro, $x [n - (N - 1) / 2]$ , que no tiene pareja y se multiplica sola:

y [n] = \sum_{k = 0}^{⌊ N / 2 ⌋ - 1} h [k] (x [n - k] + x [n - N + 1 + k]) [+ h [\frac{N - 1}{2}] x [n - \frac{N - 1}{2}] si N es impar]

Paso 3: contar. Hay $⌊ N / 2 ⌋$ pares, más el centro si $N$ es impar: $⌈ N / 2 ⌉$ multiplicaciones. Las sumas no bajan: las $⌊ N / 2 ⌋$ previas más las que juntan los $⌈ N / 2 ⌉$ productos dan $N - 1$ otra vez. Los registros tampoco: la línea es la misma, sólo que doblada. Contado con un contador dentro de los lazos de MATLAB:

N	directa y transpuesta	plegada
7	7 × · 6 +	4 × · 6 +
8	8 × · 7 +	4 × · 7 +
100	100 × · 99 +	50 × · 99 +
101	101 × · 100 +	51 × · 100 +

Multiplicaciones (×) y sumas (+) por muestra de salida. Los 51 de 101 son la respuesta del autochequeo del apunte de fase. En software lo que se ahorra depende del procesador. En una FPGA, donde los multiplicadores son el recurso escaso, es la mitad del filtro. Y la simetría paga dos veces: la misma condición que da la fase lineal deja guardar la mitad de los coeficientes.

En la simulación, «Plegada» muestra el FIR de 7 taps con 4 multiplicadores. Un detalle: la línea doblada tiene los registros de abajo corriendo hacia la izquierda, así que la muestra que entra arriba a la izquierda sale, seis tics después, abajo a la izquierda, al lado de donde entró. Por eso las dos mitades de cada par quedan en la misma columna.

06 · Por qué «transversal»

El nombre viene de cuando la línea era analógica: un cable o un dispositivo por donde la señal viaja y tarda. La señal recorre la línea a lo largo, y las derivaciones la cortan de través, en ángulo recto con el recorrido. Lo que se suma en cada instante es un corte transversal de la historia de la señal: las últimas $N$ muestras, tomadas todas a la vez. La filmina de estructuras usa los dos nombres juntos, Transversal Filter y Tapped Delay Line. Son la misma cosa vista de dos lados: una por cómo se leen las muestras, la otra por lo que es el hardware.

El filtro de media móvil es un transversal con todos los coeficientes iguales a $1 / M$ . Justamente por eso admite otra estructura, recursiva, que el transversal general no tiene.

07 · El mismo esquema, más adelante

La línea de retardos con derivaciones vuelve al final del curso, en la ecualización adaptiva de la Unidad 6. El ecualizador lineal es un transversal cuyos coeficientes no son fijos: un algoritmo los corrige muestra a muestra. La línea, los multiplicadores y el sumador son los de esta nota. Lo único nuevo es quién elige los $h [k]$ .

08 · El análisis en MATLAB

Las tres estructuras escritas a mano, con un vector de estado y un lazo muestra a muestra, comparadas contra filter y conv. Lo que figura como comentario es la salida real de correrlo en R2026a.

%% 1. El FIR de la filmina y una entrada corta
h = [0.1 0.2 0.3 0.4 0.3 0.2 0.1];     % N = 7, simétrico
x = [1 2 3 4 5 6 -5 -4];               % la entrada de waystofilt.m
N = numel(h);
xz = [x, zeros(1, N-1)];               % ceros al final: que salga la cola

y_conv = conv(h, x);
y_dir  = fir_directa(h, xz);
y_tr   = fir_transpuesta(h, xz);
y_pl   = fir_plegada(h, xz);
fprintf('y = '); fprintf('%.2f ', y_dir); fprintf('\n')
% y = 0.10 0.40 1.00 2.00 3.30 4.80 5.20 4.40 2.70 -0.00 -1.40 -1.60 -1.30 -0.40

%% 2. Las tres estructuras contra conv y filter, con un FIR largo
rng(1)
hl = fir1(100, 0.3);                    % N = 101, simétrico
xl = randn(1, 5000);
yf = filter(hl, 1, xl);
yc = conv(hl, xl);  yc = yc(1:numel(xl));
yd = fir_directa(hl, xl);
yt = fir_transpuesta(hl, xl);
yp = fir_plegada(hl, xl);
fprintf('max|directa    - filter| = %.1e\n', max(abs(yd - yf)))
fprintf('max|transpuesta- filter| = %.1e\n', max(abs(yt - yf)))
fprintf('max|plegada    - filter| = %.1e\n', max(abs(yp - yf)))
fprintf('max|directa    - conv  | = %.1e\n', max(abs(yd - yc)))
fprintf('max|filter     - conv  | = %.1e\n', max(abs(yf - yc)))
fprintf('max|conv(h,x) chica - directa| = %.1e\n', max(abs(y_conv - y_dir)))
fprintf('max|transpuesta - directa| chica = %.1e\n', max(abs(y_tr - y_dir)))
fprintf('max|plegada - directa| chica = %.1e\n', max(abs(y_pl - y_dir)))
% max|directa    - filter| = 2.2e-15
% max|transpuesta- filter| = 8.9e-16
% max|plegada    - filter| = 1.3e-15
% max|directa    - conv  | = 2.2e-15
% max|filter     - conv  | = 1.1e-16
% max|conv(h,x) chica - directa| = 0.0e+00
% max|transpuesta - directa| chica = 8.9e-16
% max|plegada - directa| chica = 8.9e-16

%% 3. Contar operaciones por muestra
for Nn = [7 8 100 101]
    [~, c1] = fir_directa(ones(1, Nn), 1);
    [~, c2] = fir_transpuesta(ones(1, Nn), 1);
    [~, c3] = fir_plegada(ones(1, Nn), 1);
    fprintf('N = %3d  directa %3d mult, %3d sumas  transpuesta %3d mult, %3d sumas  plegada %3d mult, %3d sumas\n', ...
        Nn, c1(1), c1(2), c2(1), c2(2), c3(1), c3(2))
end
% N =   7  directa   7 mult,   6 sumas  transpuesta   7 mult,   6 sumas  plegada   4 mult,   6 sumas
% N =   8  directa   8 mult,   7 sumas  transpuesta   8 mult,   7 sumas  plegada   4 mult,   7 sumas
% N = 100  directa 100 mult,  99 sumas  transpuesta 100 mult,  99 sumas  plegada  50 mult,  99 sumas
% N = 101  directa 101 mult, 100 sumas  transpuesta 101 mult, 100 sumas  plegada  51 mult, 100 sumas

%% Las tres estructuras, muestra a muestra
function [y, ops] = fir_directa(h, x)
    % Registros: r(k) = x[n-k], k = 1..N-1. Guardan entradas viejas.
    N = numel(h);  r = zeros(1, N-1);  y = zeros(size(x));  ops = [0 0];
    for n = 1:numel(x)
        acc = h(1) * x(n);             ops(1) = ops(1) + 1;
        for k = 1:N-1
            acc = acc + h(k+1) * r(k); ops = ops + 1;
        end
        y(n) = acc;
        r = [x(n), r(1:end-1)];        % la línea avanza un lugar
    end
    ops = ops / numel(x);
end

function [y, ops] = fir_transpuesta(h, x)
    % Registros: s(k) guardan sumas parciales, no entradas.
    N = numel(h);  s = zeros(1, N-1);  y = zeros(size(x));  ops = [0 0];
    for n = 1:numel(x)
        y(n) = h(1) * x(n) + s(1);     ops = ops + 1;
        for k = 1:N-2
            s(k) = h(k+1) * x(n) + s(k+1);  ops = ops + 1;
        end
        s(N-1) = h(N) * x(n);          ops(1) = ops(1) + 1;
    end
    ops = ops / numel(x);
end

function [y, ops] = fir_plegada(h, x)
    % Supone h simétrico: h(k) = h(N+1-k). Suma los pares antes de multiplicar.
    N = numel(h);  M = floor(N/2);  r = zeros(1, N-1);  y = zeros(size(x));  ops = [0 0];
    for n = 1:numel(x)
        v = [x(n), r];                 % v(k+1) = x[n-k]
        acc = 0;
        for k = 1:M
            par = v(k) + v(N+1-k);     ops(2) = ops(2) + 1;   % suma previa
            if k == 1, acc = h(k) * par; ops(1) = ops(1) + 1;
            else, acc = acc + h(k) * par; ops = ops + 1; end
        end
        if mod(N, 2) == 1              % tap central, sin pareja
            acc = acc + h(M+1) * v(M+1);  ops = ops + 1;
        end
        y(n) = acc;
        r = [x(n), r(1:end-1)];
    end
    ops = ops / numel(x);
end

Las catorce salidas del bloque 1 son las de la simulación. En el FIR largo, las tres estructuras dan lo mismo que filter y que conv hasta unos pocos eps: la peor diferencia es 2,2×10⁻¹⁵ sobre 5000 muestras. No es cero porque cada estructura suma en otro orden, y la suma en punto flotante no es asociativa. Ni siquiera la transpuesta coincide al bit con filter, aunque sea la estructura que filter dice usar: difieren en 8,9×10⁻¹⁶. Las dos cuentas no son la misma aritmética, y justamente por eso la comparación dice algo.

Los detalles que muerden:

Índices desde 1. El $h [k]$ de la teoría es h(k+1), y el registro que guarda $x [n - k]$ es r(k). En la plegada, el par de h(k) es v(k) + v(N+1-k).
La cola. Para que el lazo dé las $L_{x} + N - 1$ muestras de conv hay que meterle los $N - 1$ ceros a mano, como hace xz. Sin eso da las $L_{x}$ de filter, y hay que recortar conv para comparar, como en el bloque 2.
El cero que no es cero. La salida en $n = 9$ vale 0 exacto en papel y MATLAB la imprime -0.00: es un residuo de redondeo del orden de eps, con signo.
La plegada supone la simetría y no la comprueba. Con un $h$ no simétrico da otra cosa, sin error. fir1 lo da simétrico; conviene mirar max(abs(h - fliplr(h))) antes de plegar.
Es didáctico, no rápido. filter está compilado y el lazo no. El ahorro de la plegada y el camino corto de la transpuesta son de hardware; en MATLAB el lazo es para ver la estructura, no para ganarle a filter.

Para tener a mano

El FIR transversal es $y [n] = \sum_{k = 0}^{N - 1} h [k] x [n - k]$ hecho hardware: línea de retardos, un multiplicador por tap y un sumador. Cada columna es un término.
La línea es un registro de desplazamiento: guarda las últimas $N$ entradas. Arranca en cero, como filter. Con un impulso, escupe $h$ .
Por muestra: $N$ multiplicaciones, $N - 1$ sumas, $N - 1$ registros.
La transpuesta sale de Horner: mismo costo, registros con sumas parciales, camino crítico $T_{\times} + T_{+}$ sin importar $N$ . Paga con abanico en la entrada y registros más anchos.
La plegada usa la simetría de fase lineal: $⌈ N / 2 ⌉$ multiplicaciones, las mismas $N - 1$ sumas y registros. 101 taps, 51 productos.
Las tres estructuras dan la misma salida; en punto flotante difieren en unos pocos eps porque suman en otro orden.
El ecualizador adaptivo de la Unidad 6 es este mismo transversal con coeficientes que se mueven.