On the Minimum Distance and Erasure Correction of Codes with Block Circulant Topology

Codes with locality without any global paritycheck constraints apart from those generated by local codes' constraints have recently found a unique application in decentralized systems. In response to this, we proposed in previous work, a new class of block circulant (BC) codes possessing certain structure in the arrangement of parity-check constraints referred to as a block circulant topology. The BC topology T_{[μ, λ, ω]} (ρ) and BC codes C_BC[μ, λ, ω, ρ] are parameterized by integers λ ≥ 2, ω ≥ 2, ρ ≥ 2 and μ a multiple of λ. In this work, we show that the rate and the minimum distance of the BC code scale with corresponding metrics of its local codes in a manner that can not be realized by well-known linear array and product topologies, thus widening the possible regime of operation. We also provide an efficient erasure-correcting decoder for C_BC[μ, λ=3, ω, ρ], while such a decoder was earlier known only for λ=2. The decoding algorithm uses a novel mechanism that iteratively corrects erasures from either a single or a triplet of local codes. We show that the minimum distance of C_BC[μ, λ=3, ω, ρ] is 3 ρ+1, whereas the same result was earlier available under a constraint that μ=2^a · 3 for some integer a.