Arrays over roots of unity with perfect autocorrelation and good ZCZ cross-correlation

Samuel T. Blake; Thomas E. Hall; Andrew Z. Tirkel

doi:10.3934/amc.2013.7.231

Article Contents

2013, Volume 7, Issue 3: 231-242. Doi: 10.3934/amc.2013.7.231

This issue Previous Article Next Article Improved bounds for the implicit factorization problem

Arrays over roots of unity with perfect autocorrelation and good ZCZ cross-correlation

1.
School of Mathematical Sciences, Building 20, Clayton Campus, Monash University, Victoria, 3800

Received: December 31, 2010

Revised: February 28, 2013

Published: July 2013

Abstract Related Papers Cited by

Abstract

We present a new construction for two-dimensional, perfect autocorrelation arrays over roots of unity. These perfect arrays are constructed from a block of perfect column sequences. Other blocks are constructed from the first block, to generate a block-circulant structure. The columns are then multiplied by a perfect sequence over roots of unity, which, when folded into an array commensurate with our block width has the array orthogonality property. The size of the arrays is commensurate with the length of the underlying perfect sequences. For a given size we can construct an exponential number of inequivalent perfect arrays. For each perfect array we construct a family of arrays whose pairwise cross-correlation values are almost all zero (large zero correlation zones (ZCZ)). We present experimental evidence that this construction for perfect arrays can be generalized to higher dimensions.

Keywords:

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

Citation:

Related Papers

Cited by

References

[1]	K. T. Arasu and W. de Launey, Two-dimensional perfect quaternary arrays, IEEE Trans. Inform. Theory, 47 (2001), 1482-1493.doi: 10.1109/18.923729.
[2]	L. Bömer and M. Antweiler, Perfect n-phase sequences and arrays, IEEE J. Selected Areas Commun., 10 (1992), 782-789.
[3]	D. Calabro and J. K. Wolf, On the synthesis of two-dimensional arrays with desirable correlation properties, Inform. Control, 11 (1968), 537-560.doi: 10.1016/S0019-9958(67)90755-3.
[4]	G. Caronni, Ermitteln unauthorisierter Verteiler von maschinenlesbaren Daten, ETH, Zurich, Switzerland, Tech. Rep., 1993.
[5]	W. Chi and N. George, Phase-coded aperture for optical imaging, Optics Commun., 282 (2009), 2110-2117.
[6]	D. C. Chu, Polyphase codes with good periodic correlation properties, IEEE trans. Inform. Theory, 18 (1972), 531-532.doi: 10.1109/TIT.1972.1054840.
[7]	T. Cox and P. D'Antonio, "Acoustic Absorbers and Diffusers,'' $2^{nd}$ edition, Taylor and Francis, 2009.
[8]	P. Z. Fan and M.Darnell, The synthesis of perfect sequences, Lecture Notes Comp. Sci. Crypt. Coding, 1025 (1995), 63-73.doi: 10.1007/3-540-60693-9_9.
[9]	E. E. Fenimore and T. M. Cannon, Coded aperture imaging with uniformly redundant arrays, Applied Optics, 17 (1978), 337-347.doi: 10.1364/AO.17.000337.
[10]	R. L. Frank, S. A. Zadoff and R. Heimiller, Phase shift pulse codes with good periodic correlation properties, IRE Trans. Inform. Theory, 8 (1962), 381-382.doi: 10.1109/TIT.1962.1057786.
[11]	F. Hartung and M. Kutter, Multimedia watermarking techniques, Proc. IEEE, 87 (1999), 1079-1107.doi: 10.1109/5.771066.
[12]	R. C. Heimiller, Phase shift pulse codes with good periodic correlation properties, IRE Trans. Inform. Theory, 7 (1961), 254-257.doi: 10.1109/TIT.1961.1057655.
[13]	V. P. Ipatov, Contribution to the theory of sequence with perfect periodic autocorrelation properties, Radio Engin. Electr. Phys., 25 (1980), 31-34.
[14]	J. Jedwab and C. Mitchell, Constructing new perfect binary arrays, Electronic Letters, 24 (1988), 650-652.doi: 10.1049/el:19880440.
[15]	L. E. Kopilovich, On perfect binary arrays, Electronics Letters, 24 (1988), 566-567.doi: 10.1049/el:19880385.
[16]	A. Koz, G. A. Triantafyllidis and A. Aydin, 3D watermarking: techniques and directions, in "Three-Dimensional Television: Capture, Transmission, and Display'' (eds. H.M. Ozaktas and L. Onural), Springer-Verlag, (2007), 427-470.doi: 10.1007/978-3-540-72532-9_12.
[17]	H-D. Lüke, Sequences and arrays with perfect periodic correlation, IEEE Trans. Aerospace Electr. Sys., 24 (1988), 287-294.
[18]	S. L. Ma and W. S. Ng, On non-existence of perfect and nearly perfect sequences, Int. J. Inform. Coding Theory, 1 (2009), 15-38.doi: 10.1504/IJICOT.2009.024045.
[19]	F. J. MacWilliams and N. J. A. Sloane, Pseudo-random sequences and arrays, Proc. IEEE, 64 (1976), 1715-1729.doi: 10.1109/PROC.1976.10411.
[20]	A. Milewski, Periodic sequences with optimal properties for channel estimation and fast start-up equalization, IBM J. Res. Development, 27 (1983), 426-431.doi: 10.1147/rd.275.0426.
[21]	B. G. Mobasseri, Direct sequence watermarking of digital video using m-frames, in "ICIP,'' (1998), 399-403.doi: 10.1109/ICIP.1998.723399.
[22]	W. H. Mow, "A Study of Correlation of Sequences,'' Ph.D thesis, The Chinese University of Hong Kong, 1993.
[23]	J. Salvi, J. Pages and J. Batlle, Pattern codification strategies in structured light systems, Pattern Recognition, 37 (2004), 827-849.doi: 10.1016/j.patcog.2003.10.002.
[24]	M. R Schroeder, "Number Theory in Science and Communications, with Applications to Physics, Digital Information, Computing and Self-Similarity,'' Springer, 2006.
[25]	K. Tanaka, Y. Nakamura and K. Matsui, Embedding secret information into a dithered multilevel image, in "Proc. IEEE Military Commun. Conf.,'' (1990), 216-220.
[26]	A. Z. Tirkel, C. F. Osborne and T. E. Hall, Image and watermark registration, Signal Processing J., 66 (1998), 373-383.doi: 10.1016/S0165-1684(98)00016-4.
[27]	A. Z. Tirkel, G. A. Rankin, R. M. Van Schyndel, W. J. Ho, N. R. A. Mee and C. F. Osborne, Electronic watermark, in "Digital Image Comp. Tech. Appl. (DICTA’93),'' (1993), 666-673.
[28]	P. Wild, Infinite families of perfect binary arrays, Electronics letters. doi: 10.1049/el:19880575.
[29]	R. B. Wolfgang and E. J. Delp, A watermark for digital images, in "Proc. International Conference on Image Processing,'' Lausanne, Switzerland, (1996), 219-222.doi: 10.1109/ICIP.1996.560423.
[30]	R. B. Wolfgang and E. J. Delp, A watermarking technique for digital imagery: Further studies, in "Proc. International Conference on Imaging Sciences, Systems and Technology,'' Las Vegas, (1997), 279-287.
[31]	R. B. Wolfgang and E. J. Delp, "Authentication of Signals Using Watermarks,'' U.S. Patent 6,625,295, September 2003.
[32]	J. Zhao and E. Koch, A generic digital watermarking model, Comp. Graphics, 22 (1998), 397-403.