An efficient encoding/decoding method for block compression for RRR, provides an area-saving method that operates at high speed even with a dense bit string. A block encoding device generates blocks having a first block length by dividing an input bit string into a plurality of blocks, determines a first weight of each block from the number of 1 values included in the bit string, divides each block into small blocks having a second block length, determines a first order of the blocks in a set in which predetermined bit strings having the first block length and the first weight are arranged in a predetermined order on the basis of the weight and value of each of the small blocks, and generates block encoding data by converting the bit string of each block into the values of the determined first weight and first order.