This paper studies two families of constraints for two-dimensional and multidimensional arrays. The first family requires that a multidimensional array will not contain a cube of zeros of some fixed size and the second constraint imposes that there will not be two identical cubes of a given size in the array. These constraints are natural extensions of their one-dimensional counterpart that have been rigorously studied recently. For both of these constraint we present conditions of the size of the cube for which the asymptotic rate of the set of valid arrays approaches 1 as well as conditions for the redundancy to be at most a single symbol. For the first family we present an efficient encoding algorithm that uses a single symbol to encode arbitrary information into a valid array and for the second family we present a similar encoder for the two-dimensional case. The results in the paper are also extended to similar constraints where the sub-array is not necessarily a cube, but a box of arbitrary dimensions and only its volume is bounded.
翻译:本文对二维和多维阵列的两种限制进行了研究。 第一种是要求多维阵列不包含某种固定大小的零的立方体, 而第二种是要求在阵列中不存在两个相同大小的立方体。 这些制约是其一维对应方的自然延伸, 最近对此进行了严格研究。 对于这两种制约, 我们对立方体的大小提出了条件, 即有效阵列的无药性速度为 1, 以及使冗余最多是一个单一符号的条件。 对于第一个家庭, 我们提出了一个有效的编码算法, 使用一个单一符号将任意信息编码成一个有效的阵列, 对于第二个家庭, 我们为二维的立体提供了类似的编码器。 文件中的结果也扩大到类似的制约, 即子阵列不一定是一个立方体, 而是一个任意尺寸的框, 并且只有体积被捆绑在一起 。