Arrays composed from the extended rational cycle

Domingo Gomez-Perez; Ana-Isabel Gomez; Andrew Tirkel

doi:10.3934/amc.2017024

Article Contents

2017, Volume 11, Issue 2: 313-327. Doi: 10.3934/amc.2017024

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

Arrays composed from the extended rational cycle

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
* Corresponding author

Received: February 2016

Revised: March 2016

Published: September 2017

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

Abstract / Introduction Full Text(HTML) Figure(4) / Table(2) Related Papers Cited by

Abstract

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:

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

Citation:

Full Text(HTML)

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

Download: Full-size image 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

Download: Full-size image PowerPoint slide

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

Download: Full-size image 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.

Download: Full-size image 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

| Show Table

DownLoad: CSV

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$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	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.