Puedes resolver esta pregunta con un método de cambio y eliminación.
Digamos que tienes N bits de entrada y N es 16.
Paso 1)
Cargue un registro de desplazamiento ancho de N bits con su entrada en paralelo. Agregue un bit cero a LSB.
0111 1010 0111 0011|0
restablece tu contador de resultados a 0
Paso 2)
Realice una operación de 'cambio' que expanda los ceros existentes al bit del vecino izquierdo.
0111 1010 0111 0011|0
0111 0000 0110 0010|0
Incrementa el contador de resultados.
Paso 3)
Compruebe si el registro es cero.
falso - > repita los pasos 2 y 3
verdadero - > el contador de resultados contiene la secuencia más larga.
Ejemplo:
0111 1010 0111 0011|0 cnt=0 / input
0111 0000 0110 0010|0 cnt=1
0110 0000 0100 0000|0 cnt=2
0100 0000 0000 0000|0 cnt=3
0000 0000 0000 0000|0 cnt=4 / done
El tiempo mínimo de ejecución es 1 carga y 1 comparación - > Se puede resolver en 1 ciclo.
El tiempo máximo de ejecución es 1 carga y N turnos - > 17 ciclos en el ejemplo.
El tiempo de ejecución real es 1 carga y n cambia si n es la longitud de la secuencia más larga - > 5 ciclos en el ejemplo.
¿Cómo calcular los bits mientras se desplaza?
Vamos a nombrar el registro de desplazamiento a
.
a(0) := 0
for i in 1..N-1
a(i) := a(i) and a(i-1)
next
¿Cuántos hardware se utilizan?
- N se registra para un
- N LUTs para carga y cambio antes de cada registro
- un contador de bits ld (N + 1)
- un comparador de cero bits N
En el hardware Xilinx:
Los FPGA de Xilinx tienen LUT de 6 entradas que se pueden utilizar como 2 LUT de 5 entradas, además, hay 2 FF por LUT. La síntesis puede asignar un registro de desplazamiento de 16 bits en solo 2 segmentos y el comperador en un tercer segmento.
Según lo solicitado: un contador de 5 bits
reg [4:0] counter;
always @(posedge Clock)
begin
if(Reset)
counter <= 5'b0;
else if(counter_en)
counter <= counter + 1;
end