Two-dimensional RC/SW constrained codes: bounded weight and almost balanced weight

In this work, we study two types of constraints on two-dimensional binary arrays. Given p\in [0,1],\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 -balanced constraint: a binary vector of size n is said to be -balanced if its weight is within big [(1/2-)n, (1/2+)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 -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 =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. Furthermore, for certain values of p and we show that, for sufficiently large array size, there exists linear-time encoding/decoding algorithm that incurs at most one redundant bit.Ministry of Education (MOE)The work of Tuan Thanh Nguyen and Kui Cai was supported by the Singapore Ministry of Education Academic Research Funds Tier 2 under Grant MOE2019-T2-2-123 and Grant T2EP50221-0036. The work of Han Mao Kiah was supported by the Ministry of Education, Singapore, under its MOE AcRF Tier 2 Award under Grant MOE-T2EP20121-0007