Arrays composed from the extended rational cycle

Previous Article
Reversible DNA codes over $F_{16}+uF_{16}+vF_{16}+uvF_{16}$
AMC Home
This Issue
Next Article
On the covering radius of some binary cyclic codes

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.
[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.
[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.
[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.
[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.
[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.
[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.
[8]	J. K. Holmes, Coherent spread spectrum systems, New York Wiley-Interscience, 1 (1982), p. 636.
[9]	S. Katzenbeisser and F. Petitcolas, Information Hiding Techniques for Steganography and Digital Watermarking, Artech house, 2000.
[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.
[11]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, Elsevier, 1977.
[12]	J. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, 15 (1969), 122-127.
[13]	O. Moreno and S. Maric, A New Family of Frequency-Hop Codes, IEEE Trans. Commun., 48 (2000), 1241-1244.
[14]	O. Moreno and A. Z. Tirkel, Multi-dimensional arrays for watermarking, in Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2011,2691-2695.
[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.
[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.
[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.
[18]	H. Qi, Stream Ciphers and Linear Complexity, Ph. D thesis, National Univ. Singapore, 2008.
[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.
[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.
[21]	W. M. Schmidt, Linear recurrence sequences, in Diophantine Approximation, Springer, 2003, 171-247. doi: 10.1007/3-540-44979-5_4.
[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.
[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.
[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.
[25]	A. Z. Tirkel, R. G. van Schyndel and C. F. Osborne, A two-dimensional digital watermark, DICTA, 95 (1995), 5-8.
[26]	L.-J. Weng, Decomposition of M-sequences and its applications, IEEE Trans. Inf. Theory, 17 (1971), 457-463.

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.
[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.
[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.
[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.
[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.
[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.
[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.
[8]	J. K. Holmes, Coherent spread spectrum systems, New York Wiley-Interscience, 1 (1982), p. 636.
[9]	S. Katzenbeisser and F. Petitcolas, Information Hiding Techniques for Steganography and Digital Watermarking, Artech house, 2000.
[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.
[11]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, Elsevier, 1977.
[12]	J. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, 15 (1969), 122-127.
[13]	O. Moreno and S. Maric, A New Family of Frequency-Hop Codes, IEEE Trans. Commun., 48 (2000), 1241-1244.
[14]	O. Moreno and A. Z. Tirkel, Multi-dimensional arrays for watermarking, in Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2011,2691-2695.
[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.
[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.
[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.
[18]	H. Qi, Stream Ciphers and Linear Complexity, Ph. D thesis, National Univ. Singapore, 2008.
[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.
[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.
[21]	W. M. Schmidt, Linear recurrence sequences, in Diophantine Approximation, Springer, 2003, 171-247. doi: 10.1007/3-540-44979-5_4.
[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.
[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.
[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.
[25]	A. Z. Tirkel, R. G. van Schyndel and C. F. Osborne, A two-dimensional digital watermark, DICTA, 95 (1995), 5-8.
[26]	L.-J. Weng, Decomposition of M-sequences and its applications, IEEE Trans. Inf. Theory, 17 (1971), 457-463.

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$	2	1
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$	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$

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 2ⁿ-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 2ⁿ-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

Tools

Article outline

Figures and Tables

2018 Impact Factor: 0.879

Tools

Figures and Tables

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences