On the Equivalence Classes of Recoverable Patterns in DR Code: A Group-Theoretic Analysis with Applications to Storage Optimization

Source abstract

The DR Code (Data Restorable Code), originally proposed by Sriphum (2013), is a two-dimensional barcode that achieves a 33% data-recovery rate against six distinct cases of strip-shaped data loss using simple XOR-based parity. The original work presented a single 3×3 arrangement of nine logical blocks (A0, A1, A2, B0, B1, B2, C0, C1, C2) in which each row and each column contains exactly one element from each of the three data classes (A, B, C). This paper systematically enumerates every 3×3 arrangement that satisfies this recoverability property and proves, by exhaustive search released as an open-source program (DR15.py), that exactly 2,592 such arrangements exist. We then introduce five structural theorems—mirror reflection, vertical flipping, Tetris-style rotation, cyclic column rotation, and cyclic row rotation—and prove that each preserves recoverability. We show that these five generators, viewed as a group action, produce a finite group of order 72 isomorphic to D₄ × C₃ × C₃, which partitions the 2,592 patterns into exactly 36 absolute equivalence classes. We further explore the partial-quotient structure under D₄ alone (yielding 324 classes, the case the practitioner is most likely to encounter) and under cyclic-only quotient (yielding 288 classes). As practical contributions, we propose (i) a compact equivalence-class encoding that reduces the storage cost of one DR Code template from a naïve 36 bits to 12 bits, and (ii) a canonical-form deduplication scheme suitable for cloud and embedded storage systems. Additionally, we propose two further contributions: a fast pattern-validity oracle based on canonical lookup, and a randomization-friendly DR Code variant for security-aware barcode applications. Empirical results confirm all theorems on the full enumeration of 2,592 patterns.