Article Contents
Article Contents

# Arrays composed from the extended rational cycle

• * Corresponding author

The first author is partially supported by project MTM2014-55421-P from the Ministerio de Economia y Competitividad

• We present a 3D array construction with application to video watermarking. This new construction uses two main ingredients: an extended rational cycle (ERC) as a shift sequence and a Legendre array as a base. This produces a family of 3D arrays with good auto and cross-correlation. We calculate exactly the values of the auto correlation and the cross-correlation function and their frequency. We present a unified method of obtaining multivariate recursion polynomials and their footprints for all finite multidimensional arrays. Also, we describe new results for arbitrary arrays and enunciate a result for arrays constructed using the method of composition. We also show that the size of the footprint is invariant under dimensional transformations based on the Chinese Remainder Theorem.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

 Citation:

• Figure 1.  Legendre array defined for $\alpha\in\mathbb{F}_9$, where $\alpha$ is the root of the polynomial $x^2+x+2$. The graphical representation uses the calculation in Table 1. The color of the cube in the row $n_1$ and column $n_2$ is: red if $n_1=n_2=0$, pink if $L(n_1,n_2) =-1$ and black in the other case

Figure 2.  Graphic representation of a 3D array with the shift sequence given in Table 2. For reasons of space, we have flatten the cubes. The first 2D array starting from the left is just a copy of the Legendre array (reference array) without shifts. In the third array, the rows of the initial array have been shifted once and the columns twice. The shifts are above each plane, except for the last one which coincides with $\infty$. In that case, we added a constant array

Figure 3.  One dimensional linear feedback shift register implementation of a two dimensional array

Figure 4.  Two frames corresponding to a unmarked and a marked version of the same media file. The left one shows a unmarked frame whereas the right one corresponds to a marked frame. The differences in colour balance are a result of pushing the contrast to make the mark and video compression artifacts visible.

Table 1.  2D array given by the logarithm map together with the Legendre array for $\mathbb{F}_9$. The second column shows the digits of number $n$ in base $3$, which coincides with the coefficients of $\xi_n$ using the basis $\{1,\alpha\}$, where $\alpha$ is the root of the polynomial $x^2+x+2$. The corresponding element is in the third column. The logarithm in base $\alpha$ and the value of the Legendre array are in the fourth and fifth column

 $n$ $(n_1,n_2)$ $\xi_n$ $\log_{\alpha}(\xi_n)$ $L(n_1,n_2)$ 0 $(0,0)$ 0 $-$ 0 1 $(1,0)$ $1$ $0$ 1 2 $(2,0)$ 2 $4$ 1 3 $(0,1)$ $\alpha$ $1$ -1 4 $(1,1)$ $\alpha+1$ $7$ -1 5 $(2,1)$ $\alpha+2$ $6$ 1 6 $(0,2)$ $2\alpha$ $5$ -1 7 $(1,2)$ $2\alpha+1$ 2 1 8 $(2,2)$ $2\alpha+2$ $3$ -1

Table 2.  Extended rational cycle defined by $u_{n}=\alpha/(u_{n-1}+1)$, where $\alpha$ is the root of the polynomial $x^2+x+2$. The rational cycle has always length equal to $q+1$, in this case 10

 $u_0$ $u_1$ $u_2$ $u_3$ $u_4$ $u_5$ $u_6$ $u_7$ $u_8$ $u_9$ 0 $\alpha$ $2\alpha+1$ $\alpha+2$ $1$ $2\alpha$ $\alpha+1$ $2\alpha+2$ 2 $\infty$ (0, 0) (0, 1) (1, 2) (2, 1) (1, 0) (0, 2) (1, 1) (2, 2) (2, 0) $\infty$
•  E. Berlekamp  and  O. Moreno , Extended double-error-correcting binary Goppa codes are cyclic (Corresp.), IEEE Trans. Inf. Theory, 19 (1973) , 817-818. S. T. Blake, O. Moreno and A. Z. Tirkel, Families of 3d arrays for video watermarking, in Sequences and Their Applications, 2014,134-145. doi: 10.1007/978-3-319-12325-7_12. S. T. Blake and A. Z. Tirkel, A construction for perfect periodic autocorrelation sequences, in Int. Conf. Seq. Their Appl. -SETA 2014, Springer, 2014, 104-108. doi: 10.1007/978-3-319-12325-7_9. L. Bömer  and  M. Antweiler , Construction of a new class of higher-dimensional Legendre-and pseudonoise-arrays, IEEE Symposium on IT, 90 (1990) , p.76. I. J. Cox , J. Kilian , F. T. Leighton  and  T. Shamoon , Secure spread spectrum watermarking for multimedia, IEEE Trans. Image Proc., 6 (1997) , 1673-1687. J.-C. Faugere , P. Gianni , D. Lazard  and  T. Mora , Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symb. Comput., 16 (1993) , 329-344.  doi: 10.1006/jsco.1993.1051. D. Gomez-Perez, T. Høholdt, O. Moreno and I. Rubio, Linear complexity for multidimensional arrays-a numerical invariant, in Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2015,2697-2701. J. K. Holmes, Coherent spread spectrum systems, New York Wiley-Interscience, 1 (1982), p. 636. S. Katzenbeisser and  F. Petitcolas,  Information Hiding Techniques for Steganography and Digital Watermarking, Artech house, 2000. E. I. Krengel, A. Z. Tirkel and T. E. Hall, New sets of binary and ternary sequences with low correlation, in Int. Conf. Seq. Their Appl., Springer, 2004,220-235. doi: 10.1109/TIT.2003.818399. F. J. MacWilliams and  N. J. A. Sloane,  The Theory of Error Correcting Codes, Elsevier, 1977. J. Massey , Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, 15 (1969) , 122-127. O. Moreno  and  S. Maric , A New Family of Frequency-Hop Codes, IEEE Trans. Commun., 48 (2000) , 1241-1244. O. Moreno and A. Z. Tirkel, Multi-dimensional arrays for watermarking, in Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2011,2691-2695. O. Moreno and A. Z. Tirkel, New optimal low correlation sequences for wireless communications, in International Conference on Sequences and Their Applications, Springer, 2012, 212-223. doi: 10.1007/978-3-642-30615-0_20. H. Niederreiter  and  J. Rivat , On the correlation of pseudorandom numbers generated by inversive methods, Monatsh. Math., 153 (2008) , 251-264.  doi: 10.1007/s00605-007-0503-3. H. Niederreiter and I. E. Shparlinski, Recent advances in the theory of nonlinear pseudorandom number generators, in Monte Carlo and Quasi-Monte Carlo Methods 2000, Springer, 2002, 86-102. H. Qi, Stream Ciphers and Linear Complexity, Ph. D thesis, National Univ. Singapore, 2008. I. M. Rubio, M. Sweedler and C. Heegard, Finding a Gröbner basis for the ideal of recurrence relations on m-dimensional periodic arrays, in Contemporary Developments in Finite Fields and Applications, World Scientific, 2016,296-320. S. Sakata , Extension of the Berlekamp-Massey algorithm to N dimensions, Inf. Comput., 84 (1990) , 207-239.  doi: 10.1016/0890-5401(90)90039-K. W. M. Schmidt, Linear recurrence sequences, in Diophantine Approximation, Springer, 2003, 171-247. doi: 10.1007/3-540-44979-5_4. A. Z. Tirkel  and  T. Hall , New matrices with good auto and cross-correlation, IEICE Trans. Fundam. Electr. Commun. Comp. Sci., 89 (2006) , 2315-2321. A. Z. Tirkel, T. E. Hall and C. F. Osborne, Steganography applications of coding theory, in IEEE Information Theory Workshop, Svalbard, 1997, 57-59. A. Z. Tirkel, T. E. Hall, C. F. Osborne, N. Meinhold and O. Moreno, Collusion resistant fingerprinting of digital audio, in Proc. 4th Int. Conf. Sec. Inf. Networks, 2011, 5-12. A. Z. Tirkel , R. G. van Schyndel  and  C. F. Osborne , A two-dimensional digital watermark, DICTA, 95 (1995) , 5-8. L.-J. Weng , Decomposition of M-sequences and its applications, IEEE Trans. Inf. Theory, 17 (1971) , 457-463.

Figures(4)

Tables(2)