Two-Dimensional Half-Rate Codes Using Two-Dimensional Finite-Field Filter Banks

This correspondence introduces two-dimensional (2-D) filter bank codes (TDFBCs). The synthesis bank of a two-channel two-dimensional filter bank over a finite field is used to design the 2-D code, and the corresponding analysis bank is used to generate the syndrome of the code. First, we study the encoder of half-rate TDFBCs and show that these linear codes are lattice-cyclic. It is proven that any 2-D lattice-cyclic code can also be generated by a 2-D filter bank. Second, we introduce a methodology to design TDFBCs over binary erasure channels. These codes have a simple and efficient maximum-likelihood (ML) decoding algorithm for burst erasures. We show that half-rate TDFBCs of dimensions N₁ X N₂/ can recover burst erasures of size up to N₁ X N₂ /2 and N₁ /2 X N₂ using the proposed decoding technique. Finally, we present examples of TDFBCs that satisfy the Reiger bound with equality, i.e., they are capable of correcting any burst of size N₁ X N₂ /2 .

I. Introduction

There are many data transmission and storage systems with two-dimensional (2-D) data structures that suffer from 2-D bursts of error and erasure. Research in error correcting codes has shown that 2-D codes are very effective in combating such errors and erasures. The performance of a 2-D code depends on its burst-correcting efficiency. The burst-correcting efficiency, denoted by , of a 2-D code that can correct burst errors of area up to is given by . It is clear that for erasure correcting two-dimensional codes, is modified as . According to the Reiger bound [1], . Hence, the design of 2-D codes whose efficiencies are close to 1 is an important goal. In [2], Elspas has shown that the product of two cyclic codes is capable of correcting 2-D burst errors. One of the drawbacks of product codes is that it introduces unnecessary redundancies. However, it is worth noting that the capability of these codes is not limited to correcting burst errors. Imai [3] has studied 2-D fire codes, which are cyclic and are capable of correcting bursts of size (for some and ). Although 2-D fire codes have less redundancy compared to product codes, their burst-correcting efficiency is still less than 0.4. In [4]–[6], different 2-D codes were suggested to correct a single rectangular burst of errors of size . The 2-D codes introduced in [6] have the highest efficiency that is equal to 2/3.