I'm working on reverse engineering the bit stream format of an FPGA, in particular regarding the address translation of the BRAM (block RAM), but the algorithm could in general be used for any permutation of an address space. The algorithm is as follows:

Assign an index to each bit in the input space. For every bit in the space, set the bit to 1 if bit 0 of the index is 1, otherwise set the bit to 0, and look at the output space. This allows you to list all bits in the output which have bit 0 of the input index set. Repeat the process for each bit in the input index. This allows you to reconstruct the complete input index for each bit in the output space by performing the permutation log2(n) times.

Obviously, I didn't invent this algorithm, and the idea is essentially identical to that of a Hamming code, although the application is different. Does this algorithm have a name?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.