The algorithm below, BlockEncode, is an algorithm for compressing fixed density binary strings of length n with k ones. We will assume for simplicity that n/k is a power of two, so that n/k is an integer, and log(n/k) is also an integer.
BlockEncode ( bitstring s of length n with k ones )
1. Break s into k blocks each of size n/k.
2. For each block B in s