TY - GEN

T1 - Enumerative Constrained Coding in Two and Three Dimensions

AU - Baksheev, Ivan

N1 - Conference code: 19

PY - 2025/12/23

Y1 - 2025/12/23

N2 - We generalize enumerative constrained coding from one dimension to two and three dimensions by computing completion counts with a frontier-state dynamic program that grows arrays in raster order for two dimensions and in slabs for three dimensions. A stripe reduction treats each vertical stack as a composite symbol, and the state retains only the local pattern context and any additive global statistics needed to validate constraints, yielding a modular construction that combines multiple local and global rules and is agnostic to the underlying alphabet. The same dynamic program provides the counts required for exact ranking and unranking, giving a bijective encoder over all allowed arrays; as block size increases, the finite-length coding rate approaches capacity. We provide the cost of computing a single completion count. We also describe possible optimizations: state lumping to merge provably indistinguishable states, early pruning for additive global constraints via forward-feasibility bounds, and fast methods to replace linear number of dynamic-programming steps with a logarithmic number of operations.

AB - We generalize enumerative constrained coding from one dimension to two and three dimensions by computing completion counts with a frontier-state dynamic program that grows arrays in raster order for two dimensions and in slabs for three dimensions. A stripe reduction treats each vertical stack as a composite symbol, and the state retains only the local pattern context and any additive global statistics needed to validate constraints, yielding a modular construction that combines multiple local and global rules and is agnostic to the underlying alphabet. The same dynamic program provides the counts required for exact ranking and unranking, giving a bijective encoder over all allowed arrays; as block size increases, the finite-length coding rate approaches capacity. We provide the cost of computing a single completion count. We also describe possible optimizations: state lumping to merge provably indistinguishable states, early pruning for additive global constraints via forward-feasibility bounds, and fast methods to replace linear number of dynamic-programming steps with a logarithmic number of operations.

KW - кодирование с ограничениями

KW - перечислительное кодирование

KW - многомерное кодирование

KW - динамическое программирование

KW - изоляция битов

KW - ограничение «жёсткий квадрат»

KW - отсутствие соседних единиц

KW - Constrained code

KW - enumerative coding

KW - multidimensional coding

KW - dynamic programming

KW - bit isolation

KW - hardsquare constraint

KW - no-adjacent-ones

UR - https://www.scopus.com/pages/publications/105032075852

U2 - 10.1109/Redundancy68069.2025.11301501

DO - 10.1109/Redundancy68069.2025.11301501

M3 - Conference contribution

SN - 979-8-3315-4993-0

SP - 1

EP - 4

BT - 2025 XIХ International Symposium on Problems of Redundancy in Information and Control Systems (Redundancy)

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2025 XIX International Symposium on Problems of Redundancy in Information and Control Systems

Y2 - 5 November 2025 through 7 November 2025

ER -