Reversing a Bit Vector
Bit reversal shows up in FFT addressing. In hardware it costs no logic at all: it is only wiring, with bit 0 connected to bit 63 and so on.
The solution module receives a 64-bit input vector and must output the exact bit-reversed sequence on the following clock cycle. Bit 63 of the input becomes bit 0 of the output, bit 62 becomes bit 1, and so forth. The reversal must be evaluated entirely through wiring connections before being registered into the output flip-flops.
- Clock edge:
posedge clk - Reset type: Asynchronous
- Reset polarity: Active-low (
rst_n) - Output values on reset:
data_outgoes to64'b0 - Latency: Exactly 1 clock cycle (registered output)
Worked Trace:
- Cycle 1:
rst_n=0 →data_out=64'h0000000000000000 - Cycle 2:
rst_n=1,data_in=64'h8000000000000000 →data_out=64'h0000000000000000 (holding reset value) - Cycle 3:
rst_n=1,data_in=64'hF000000000000000 →data_out=64'h0000000000000001 (reversed from Cycle 2) - Cycle 4:
rst_n=1,data_in=64'hAAAA000000000000 →data_out=64'h000000000000000F (reversed from Cycle 3) - Cycle 5:
rst_n=1,data_in=64'h0000000000000000 →data_out=64'h0000000000005555 (reversed from Cycle 4) - Cycle 6:
rst_n=1,data_in=64'h0000000000000000 →data_out=64'h0000000000000000 (reversed from Cycle 5)
| Signal | Direction | Width | Description |
|---|---|---|---|
clk |
input | 1 | Positive-edge triggered clock |
rst_n |
input | 1 | Asynchronous active-low reset; sets data_out to 0 when asserted |
data_in |
input | 64 | The 64-bit vector to be reversed |
data_out |
output | 64 | The bit-reversed vector, updated on the clock edge |
Constraints
- The module must complete the reversal and register the result in exactly one clock cycle.
- The design must not infer any combinational logic gates (e.g., AND, OR, XOR, MUX). It must consist exclusively of wires and D flip-flops.
- Output must be strictly registered; do not expose combinational signals directly to the output ports.
Topics
Solve this problem
Write the module in Verilog, SystemVerilog or VHDL. Your submission is compiled and simulated against the problem's testbench. You get the waveform back, not a stored answer.
This problem is part of Codiode Pro. The statement above is free to read.
The circuit builder and code editor need a desktop screen. On a phone, read the problem here and open it on a laptop to solve.
Part of Interview Circuit
Problem 9 of 10 in the Interview Circuit track.
Related problems
Browse all problems · Verilog practice problems · Learning tracks