American Institute of Mathematical Sciences

Advanced
May  2017, 11(2): 313-327. doi: 10.3934/amc.2017024

Arrays composed from the extended rational cycle

Domingo Gomez-Perez 1,, , Ana-Isabel Gomez 2, and  Andrew Tirkel 3,

1. 

Universidad de Cantabria, Avd. Los Castros, s/n. Facultad de Ciencias, Santander, Spain
2. 

Universidad de Cantabria, Avd. Los Castros, s/n. EIIT, Santander, Spain
3. 

Scientific Technology, 8 Cecil St., East Brighton, Vic, 3187, Australia

* Corresponding author

Received  February 2016 Revised  March 2016 Published  May 2017

Fund Project: 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.

Keywords: Watermark, multidimensional array, Groebner basis, recursion polynomial, linear complexity, Chinese Remainder Theorem.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.
Citation: Domingo Gomez-Perez, Ana-Isabel Gomez, Andrew Tirkel. Arrays composed from the extended rational cycle. Advances in Mathematics of Communications, 2017, 11 (2) : 313-327. doi: 10.3934/amc.2017024
References:
[1]

E. Berlekamp and O. Moreno, Extended double-error-correcting binary Goppa codes are cyclic (Corresp.), IEEE Trans. Inf. Theory, 19 (1973), 817-818. Google Scholar

[2]

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. Google Scholar

[3]

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. Google Scholar

[4]

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. Google Scholar

[5]

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. Google Scholar

[6]

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. Google Scholar

[7]

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.Google Scholar

[8]

J. K. Holmes, Coherent spread spectrum systems, New York Wiley-Interscience, 1 (1982), p. 636.Google Scholar

[9] S. Katzenbeisser and F. Petitcolas, Information Hiding Techniques for Steganography and Digital Watermarking, Artech house, 2000. Google Scholar
[10]

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. Google Scholar

[11] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, Elsevier, 1977. Google Scholar
[12]

J. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, 15 (1969), 122-127. Google Scholar

[13]

O. Moreno and S. Maric, A New Family of Frequency-Hop Codes, IEEE Trans. Commun., 48 (2000), 1241-1244. Google Scholar

[14]

O. Moreno and A. Z. Tirkel, Multi-dimensional arrays for watermarking, in Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2011,2691-2695.Google Scholar

[15]

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. Google Scholar

[16]

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. Google Scholar

[17]

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. Google Scholar

[18]

H. Qi, Stream Ciphers and Linear Complexity, Ph. D thesis, National Univ. Singapore, 2008.Google Scholar

[19]

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.Google Scholar

[20]

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. Google Scholar

[21]

W. M. Schmidt, Linear recurrence sequences, in Diophantine Approximation, Springer, 2003, 171-247. doi: 10.1007/3-540-44979-5_4. Google Scholar

[22]

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. Google Scholar

[23]

A. Z. Tirkel, T. E. Hall and C. F. Osborne, Steganography applications of coding theory, in IEEE Information Theory Workshop, Svalbard, 1997, 57-59.Google Scholar

[24]

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.Google Scholar

[25]

A. Z. Tirkel, R. G. van Schyndel and C. F. Osborne, A two-dimensional digital watermark, DICTA, 95 (1995), 5-8. Google Scholar

[26]

L.-J. Weng, Decomposition of M-sequences and its applications, IEEE Trans. Inf. Theory, 17 (1971), 457-463. Google Scholar

show all references

References:
[1]

E. Berlekamp and O. Moreno, Extended double-error-correcting binary Goppa codes are cyclic (Corresp.), IEEE Trans. Inf. Theory, 19 (1973), 817-818. Google Scholar

[2]

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. Google Scholar

[3]

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. Google Scholar

[4]

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. Google Scholar

[5]

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. Google Scholar

[6]

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. Google Scholar

[7]

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.Google Scholar

[8]

J. K. Holmes, Coherent spread spectrum systems, New York Wiley-Interscience, 1 (1982), p. 636.Google Scholar

[9] S. Katzenbeisser and F. Petitcolas, Information Hiding Techniques for Steganography and Digital Watermarking, Artech house, 2000. Google Scholar
[10]

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. Google Scholar

[11] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, Elsevier, 1977. Google Scholar
[12]

J. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, 15 (1969), 122-127. Google Scholar

[13]

O. Moreno and S. Maric, A New Family of Frequency-Hop Codes, IEEE Trans. Commun., 48 (2000), 1241-1244. Google Scholar

[14]

O. Moreno and A. Z. Tirkel, Multi-dimensional arrays for watermarking, in Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2011,2691-2695.Google Scholar

[15]

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. Google Scholar

[16]

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. Google Scholar

[17]

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. Google Scholar

[18]

H. Qi, Stream Ciphers and Linear Complexity, Ph. D thesis, National Univ. Singapore, 2008.Google Scholar

[19]

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.Google Scholar

[20]

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. Google Scholar

[21]

W. M. Schmidt, Linear recurrence sequences, in Diophantine Approximation, Springer, 2003, 171-247. doi: 10.1007/3-540-44979-5_4. Google Scholar

[22]

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. Google Scholar

[23]

A. Z. Tirkel, T. E. Hall and C. F. Osborne, Steganography applications of coding theory, in IEEE Information Theory Workshop, Svalbard, 1997, 57-59.Google Scholar

[24]

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.Google Scholar

[25]

A. Z. Tirkel, R. G. van Schyndel and C. F. Osborne, A two-dimensional digital watermark, DICTA, 95 (1995), 5-8. Google Scholar

[26]

L.-J. Weng, Decomposition of M-sequences and its applications, IEEE Trans. Inf. Theory, 17 (1971), 457-463. Google Scholar

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 Options

Download full-size image

Download as PowerPoint slide

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 Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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.
Figure Options

Download full-size image

Download as PowerPoint slide

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$21
8$(2,2)$$2\alpha+2$$3$-1
Table Options

Download as excel

$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$21
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$
Table Options

Download as excel

$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$
[1]

Sohana Jahan, Hou-Duo Qi. Regularized multidimensional scaling with radial basis functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 543-563. doi: 10.3934/jimo.2016.12.543
[2]

Gui-Qiang Chen, Bo Su. A viscous approximation for a multidimensional unsteady Euler flow: Existence theorem for potential flow. Discrete & Continuous Dynamical Systems - A, 2003, 9 (6) : 1587-1606. doi: 10.3934/dcds.2003.9.1587
[3]

Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369
[4]

Eugenia N. Petropoulou, Panayiotis D. Siafarikas. Polynomial solutions of linear partial differential equations. Communications on Pure & Applied Analysis, 2009, 8 (3) : 1053-1065. doi: 10.3934/cpaa.2009.8.1053
[5]

Thomas Y. Hou, Pengfei Liu. Optimal local multi-scale basis functions for linear elliptic equations with rough coefficients. Discrete & Continuous Dynamical Systems - A, 2016, 36 (8) : 4451-4476. doi: 10.3934/dcds.2016.36.4451
[6]

Guo Lin, Wan-Tong Li. Traveling wave solutions of a competitive recursion. Discrete & Continuous Dynamical Systems - B, 2012, 17 (1) : 173-189. doi: 10.3934/dcdsb.2012.17.173
[7]

Roberta Fabbri, Carmen Núñez, Ana M. Sanz. A perturbation theorem for linear Hamiltonian systems with bounded orbits. Discrete & Continuous Dynamical Systems - A, 2005, 13 (3) : 623-635. doi: 10.3934/dcds.2005.13.623
[8]

Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297
[9]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016
[10]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[11]

Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047
[12]

Fernando Hernando, Diego Ruano. New linear codes from matrix-product codes with polynomial units. Advances in Mathematics of Communications, 2010, 4 (3) : 363-367. doi: 10.3934/amc.2010.4.363
[13]

Jaume Llibre, Yilei Tang. Limit cycles of discontinuous piecewise quadratic and cubic polynomial perturbations of a linear center. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1769-1784. doi: 10.3934/dcdsb.2018236
[14]

Elimhan N. Mahmudov. Optimal control of evolution differential inclusions with polynomial linear differential operators. Evolution Equations & Control Theory, 2019, 8 (3) : 603-619. doi: 10.3934/eect.2019028
[15]

David Gómez-Ullate, Niky Kamran, Robert Milson. Structure theorems for linear and non-linear differential operators admitting invariant polynomial subspaces. Discrete & Continuous Dynamical Systems - A, 2007, 18 (1) : 85-106. doi: 10.3934/dcds.2007.18.85
[16]

C. D. Ahlbrandt, A. C. Peterson. A general reduction of order theorem for discrete linear symplectic systems. Conference Publications, 1998, 1998 (Special) : 7-18. doi: 10.3934/proc.1998.1998.7
[17]

Roberta Fabbri, Russell Johnson, Carmen Núñez. On the Yakubovich frequency theorem for linear non-autonomous control processes. Discrete & Continuous Dynamical Systems - A, 2003, 9 (3) : 677-704. doi: 10.3934/dcds.2003.9.677
[18]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036
[19]

Angelo Alvino, Roberta Volpicelli, Bruno Volzone. A remark on Hardy type inequalities with remainder terms. Discrete & Continuous Dynamical Systems - S, 2011, 4 (4) : 801-807. doi: 10.3934/dcdss.2011.4.801
[20]

M. Euler, N. Euler, M. C. Nucci. On nonlocal symmetries generated by recursion operators: Second-order evolution equations. Discrete & Continuous Dynamical Systems - A, 2017, 37 (8) : 4239-4247. doi: 10.3934/dcds.2017181

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (10)
  • HTML views (5)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences