Two-Dimensional RC/SW Constrained Codes: Bounded Weight and Almost Balanced Weight
Tuan Thanh Nguyen, Kui Cai, Han Mao Kiah, Kees A. Schouhamer Immink, Yeow Meng Chee · IEEE Transactions on Information Theory · 2023
In this work, we study two types of constraints on two-dimensional binary arrays. Given$p\in [{0,1}],\epsilon \in [{0,1/2}]$, we study 1) the$p$-bounded constraint: a binary vector of size$n$is said to be$p$-bounded if its weight is at most$pn$, and 2) the$\epsilon $-balanced constraint: a binary vector of size$n$is said to be$\epsilon $-balanced if its weight is within$\big [(1/2-\epsilon)n, (1/2+\epsilon)n\big]$. Such constraints are crucial in several data storage systems, those regard the information data as two-dimensional (2D) instead of one-dimensional (1D), such as the crossbar resistive memory arrays and the holographic data storage. In this work, efficient encoding/decoding algorithms are presented for binary arrays so that the weight constraint (either$p$-bounded constraint or$\epsilon $-balanced constraint) is enforced over every row and every column, regarded as 2D row-column (RC) constrained codes; or over every window (where each window refers to as a subarray consisting of consecutive rows and consecutive columns), regarded as 2D sliding-window (SW) constrained codes. While low-complexity designs have been proposed in the literature, mostly focusing on 2D RC constrained codes where$p=1/2$and$\epsilon =0$, this work provides efficient coding methods that work for both 2D RC constrained codes and 2D SW constrained codes, and more importantly, the methods are applicable for arbitrary values of$p$and$\epsilon $. Furthermore, for certain values of$p$and$\epsilon $, we show that, for sufficiently large array size, there exists linear-time encoding/decoding algorithm that incurs at most one redundant bit.