From One-Dimensional Codes to Two-Dimensional Codes: A Universal Framework for the Bounded-Weight Constraint This work was supported by the SUTD Kickstarter Initiative (SKI) Grant 2021_04_05 and the Singapore Ministry of Education Academic Research Fund Tier 2 T2EP50221-0036.

Viet Hai Le 1 , Thanh Phong Pham 2 , Tuan Thanh Nguyen 1 , Kui Cai 1 , and Kees A. Schouhamer Immink 3 · 2025

Read From One-Dimensional Codes to Two-Dimensional Codes: A Universal Framework for the Bounded-Weight Constraint This work was supported by the SUTD Kickstarter Initiative (SKI) Grant 2021_04_05 and the Singapore Ministry of Education Academic Research Fund Tier 2 T2EP50221-0036. by Viet Hai Le 1 , Thanh Phong Pham 2 , Tuan Thanh Nguyen 1 , Kui Cai 1 , and Kees A. Schouhamer Immink 3 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-01240.txt.

Introduction

New memory technology stores data in two-dimensional arrays, so codes must obey limits in every row and column, not just along a line. Viet Hai Le, with four co-authors, tackles bounded-weight codes, where each line may hold only a capped number of ones. Building good two-dimensional versions from known one-dimensional codes had been a challenge.

The team offers a universal framework that lifts a one-dimensional design into two dimensions while keeping the weight limit in all rows and columns of a given length. The bound they guarantee follows a stated function of that length. Le and the co-authors present the method as an efficient general solution, aimed at raising reliability in dense resistive memory systems where stray heavy lines cause errors.

Catalog record

CREATORViet Hai Le 1 , Thanh Phong Pham 2 , Tuan Thanh Nguyen 1 , Kui Cai 1 , and Kees A. Schouhamer Immink 3
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-01240

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

From One-Dimensional Codes to Two-Dimensional Codes: A Universal Framework for the Bounded-Weight Constraint This work was supported by the SUTD Kickstarter Initiative (SKI) Grant 2021_04_05 and the Singapore Ministry of Education Academic Research Fund Tier 2 T2EP50221-0036. Viet Hai Le 1 , Thanh Phong Pham 2 , Tuan Thanh Nguyen 1 , Kui Cai 1 , and Kees A. Schouhamer Immink 3 Abstract Recent developments in storage- especially in the area of resistive random access memory (ReRAM)- are attempting to scale the storage density by regarding the information data as two-dimensional (2D), instead of one-dimensional (1D). Correspondingly, new types of 2D constraints are introduced into the input information data to improve the system reliability. While 1D constraints have been extensively investigated in the literature, the study for 2D constraints is much less profound. Particularly, given a constraint ℱ \mathcal{F} and a design of 1D codes whose codewords satisfy ℱ \mathcal{F} , the problem of constructing efficient 2D codes, such that every row and every column in every codeword satisfy ℱ \mathcal{F} , has been a challenge. This work provides an efficient solution to the challenging coding problem above for the binary bounded-weight constrained codes that restrict the maximum number of 1 1 ’s (called weight ). Formally, we propose a universal framework to design 2D codes that guarantee the weight of every row and every column of length n n to be at most f ⁡ ( n ) f(n) for any given function f ⁡ ( n ) f(n) . We show that if there exists a design of capacity-approaching 1D codes, then our method also provides capacity-approaching 2D codes for all f = ω ⁡ ( log ⁡ n ) f=\omega(\log n) . I Introduction Binary weight-constrained codes are useful in various applications in the fields of computer science, information security, communications, and data storage systems. For example, the constant-weight (CW) codes, whose codewords share the same Hamming weight , have been used in several applications including frequency hopping in GSM networks [ 1 , 2 ] , optical and magnetic recording [ 3 , 4 ] . Particularly, the balanced codes , in which every codeword has an equal number of 0 ’s and 1 ’s, have many applications in both classical and modern communications and data storage systems such as digital optical disks [ 4 , 5 ] , data synchronization [ 6 , 7 ] , and the emerging DNA-based data storage [ 8 , 9 , 10 , 11 ] . In this work, we study the bounded-weight constrained codes, which restrict the maximum number of 1 ’s in every codeword and have been used widely to tackle several challenging communications and storage systems issues, especially in the area of resistive random access memory (ReRAM). We first describe briefly certain applications of the bounded-weight constraint, including 1D codes and 2D codes. For instance, such 1D codes have been used to prevent energy outage at a receiver having finite energy storage capability in simultaneous energy and information transfer [ 12 , 13 , 14 ] , or to prevent high temperatures in electronic devices [ 15 , 16 , 17 ] . On the other hand, the 2D bounded-weight codes, which restrict the maximum number of 1 ’s in every row and every column of an array codeword, have been suggested as an effective solution to reduce the sneak path interference , a fundamental and challenging problem in ReRAM [ 22 , 21 , 20 , 23 , 18 , 19 ] . While 1D constraints have been extensively investigated, the study for 2D constraints is much less profound. For instance, for the 1D bounded-weight constraint, there are several efficient prior-art coding methods for designing 1D codes with optimal redundancy or almost optimal (up to a constant number of redundant bits away from the optimal redundancy), particularly including the enumeration coding technique [ 4 ] , Knuth’s balancing technique [ 24 , 12 , 3 ] , the classic polarity bit code [ 4 , 12 ] , and the sequence replacement technique [ 12 , 25 , 26 ] . Among them, the enumeration coding technique has been considered an efficient solution providing optimal redundancy, despite its disadvantages of high complexity and high error propagation [ 4 , 27 , 9 , 28 ] . Nevertheless, using such a technique to handle 2D constraints has remained a challenge. In this work, we are interested in the following coding problem: Given a constraint \mathcal{F} (or generally, a finite set of constraints \mathcal{F} ) and an efficient construction of 1D codes whose codewords satisfy \mathcal{F} , how to extend the construction to 2D codes, i.e. every row and every column in every 2D codeword satisfy \mathcal{F} ? Our main contribution is to provide an efficient solution to the challenging problem above when \mathcal{F} is a bounded-weight constraint. Formally, we propose a universal framework to design 2D codes that guarantee the weight of every row and every column of length n to be at most f(n) for any given function f(n) , through efficient encoding and decoding algorithms. We show that if a design of capacity-approaching 1D codes exists, then our encoder provides capacity-approaching 2D codes for all f=\omega(\log n) . Our results extend the study of literature works that specifically require f(n)=n/2 as proposed by Ordentlich and Roth [ 22 ] , or f(n)=pn for a constant p\in(0,1) as proposed by Nguyen et al. [ 23 ] . II Preliminary Given two sequences {\mathbfsl{x}}=x_{1}\ldots x_{n_{1}} and {\mathbfsl y}=y_{1}\ldots y_{n_{2}} , the concatenation of the two sequences is defined by {\mathbfsl{x}}{\mathbfsl y}\triangleq x_{1}\ldots x_{n_{1}}y_{1}\ldots y_{n_{2}} . For a binary sequence {\mathbfsl{x}} , we use \operatorname{wt}({\mathbfsl{x}}) to denote the weight of {\mathbfsl{x}} , i.e. the number of ones in {\mathbfsl{x}} . In addition, we use \bar{{\mathbfsl{x}}} to denote the complement of {\mathbfsl{x}} . For example, if {\mathbfsl{x}}=110011 , then \operatorname{wt}({\mathbfsl{x}})=4 and \overline{{\mathbfsl{x}}}=001100 . Definition 1 . Given {\mathbfsl y}=y_{1}y_{2}\ldots y_{n},{\mathbfsl{z}}=z_{1}z_{2}\ldots z_{n} . For 1\leqslant t\leqslant n , we use {\rm Swap}_{t}({\mathbfsl y},{\mathbfsl{z}}) , {\rm Swap}_{t}({\mathbfsl{z}},{\mathbfsl y}) to denote the sequences obtained by swapping the first t bits of {\mathbfsl y} and {\mathbfsl{z}} , i.e. \displaystyle{\rm Swap}_{t}({\mathbfsl y},{\mathbfsl{z}}) \displaystyle=z_{1}z_{2}\ldots z_{t}y_{t+1}y_{t+2}\ldots y_{n},\text{ and } \displaystyle{\rm Swap}_{t}({\mathbfsl{z}},{\mathbfsl y}) \displaystyle=y_{1}y_{2}\ldots y_{t}z_{t+1}z_{t+2}\ldots z_{n}. Big-O, little-o, big-omega and little-omega functions . Given two real functions f and g , we say that f is big-O of g and write f=O(g) , if there exists a positive real number M and a real number x_{0} such that |f(x)|\leqslant Mg(x) for all x\geqslant x_{0} . We say that f is little-o of g and write f=o(g) if \lim_{x\to\infty}f(x)/g(x)=0 . On the other hand, f is big-omega of g , denoted by \Omega(g) , if there exists a positive real number M and a real number x_{0} such that f(x)\geqslant M|g(x)| for all x\geqslant x_{0} . We say f is little-omega of g , denoted by f=\omega(g) , if \lim_{x\to\infty}f(x)/g(x)=\infty , or equivalently, \lim_{x\to\infty}g(x)/f(x)=0 . Definition 2 . Given a function f , a sequence {\mathbfsl{x}}\in\{0,1\}^{n} is called f -bounded if its weight satisfies that \operatorname{wt}({\mathbfsl{x}})\leqslant f(n) . Let {\mathbfsl A}_{n} denote the set of all n\times n binary arrays. For an array A\in{\mathbfsl A}_{n} , the

Read the complete text