Generalized Three-Layer Integrated Interleaved Codes

Integrated interleaved (II) codes allocate parities sharable by codewords, which are also called interleaves, and hence enable a good tradeoff on locality and correction capability. Better locality translates to shorter decoding latency, which is essential to many new applications, such as failure recovery in distributed storage. The shared parities can be allocated in multiple layers to improve the locality. However, existing work only generalized two-layer II codes to allow multiple interleaves with extra errors to be corrected. For three or more layers, the shared parities in a layer only provide extra protection over one of the interleaves or subgroups they cover in the next lower layer. This letter proposes a construction of generalized three-layer II codes. In our codes, the shared parities can be used to correct multiple interleaves in each subgroup and the allocation of their correction power among the interleaves is flexible. Our scheme corrects much more error patterns than the prior three-layer II codes, and achieves better locality than the two-layer GII codes.