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

Previous Article
Improved bounds for the implicit factorization problem
AMC Home
This Issue
Next Article

August 2013, 7(3): 231-242. doi: 10.3934/amc.2013.7.231

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

Samuel T. Blake ^1, , Thomas E. Hall ^1, and Andrew Z. Tirkel ^1,

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

Received January 2011 Revised March 2013 Published July 2013

Abstract
Related Papers

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: zero correlation zone., Perfect arrays, block circulant, array orthogonality property, autocorrelation, cross-correlation.

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

Citation: Samuel T. Blake, Thomas E. Hall, Andrew Z. Tirkel. Arrays over roots of unity with perfect autocorrelation and good ZCZ cross-correlation. Advances in Mathematics of Communications, 2013, 7 (3) : 231-242. doi: 10.3934/amc.2013.7.231

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.

show all references

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.

[1]	Samuel T. Blake, Andrew Z. Tirkel. A multi-dimensional block-circulant perfect array construction. Advances in Mathematics of Communications, 2017, 11 (2) : 367-371. doi: 10.3934/amc.2017030
[2]	Wei-Wen Hu. Integer-valued Alexis sequences with large zero correlation zone. Advances in Mathematics of Communications, 2017, 11 (3) : 445-452. doi: 10.3934/amc.2017037
[3]	Xiaohui Liu, Jinhua Wang, Dianhua Wu. Two new classes of binary sequence pairs with three-level cross-correlation. Advances in Mathematics of Communications, 2015, 9 (1) : 117-128. doi: 10.3934/amc.2015.9.117
[4]	Zhenyu Zhang, Lijia Ge, Fanxin Zeng, Guixin Xuan. Zero correlation zone sequence set with inter-group orthogonal and inter-subgroup complementary properties. Advances in Mathematics of Communications, 2015, 9 (1) : 9-21. doi: 10.3934/amc.2015.9.9
[5]	Chunlei Xie, Yujuan Sun. Construction and assignment of orthogonal sequences and zero correlation zone sequences for applications in CDMA systems. Advances in Mathematics of Communications, 2020, 14 (1) : 1-9. doi: 10.3934/amc.2020001
[6]	Yuhua Sun, Zilong Wang, Hui Li, Tongjiang Yan. The cross-correlation distribution of a $p$-ary $m$-sequence of period $p^{2k}-1$ and its decimated sequence by $\frac{(p^{k}+1)^{2}}{2(p^{e}+1)}$. Advances in Mathematics of Communications, 2013, 7 (4) : 409-424. doi: 10.3934/amc.2013.7.409
[7]	Hua Liang, Jinquan Luo, Yuansheng Tang. On cross-correlation of a binary $m$-sequence of period $2^{2k}-1$ and its decimated sequences by $(2^{lk}+1)/(2^l+1)$. Advances in Mathematics of Communications, 2017, 11 (4) : 693-703. doi: 10.3934/amc.2017050
[8]	Tinghua Hu, Yang Yang, Zhengchun Zhou. Golay complementary sets with large zero odd-periodic correlation zones. Advances in Mathematics of Communications, 2021, 15 (1) : 23-33. doi: 10.3934/amc.2020040
[9]	Lassi Roininen, Markku S. Lehtinen, Sari Lasanen, Mikko Orispää, Markku Markkanen. Correlation priors. Inverse Problems and Imaging, 2011, 5 (1) : 167-184. doi: 10.3934/ipi.2011.5.167
[10]	Limengnan Zhou, Daiyuan Peng, Hongyu Han, Hongbin Liang, Zheng Ma. Construction of optimal low-hit-zone frequency hopping sequence sets under periodic partial Hamming correlation. Advances in Mathematics of Communications, 2018, 12 (1) : 67-79. doi: 10.3934/amc.2018004
[11]	Wenbing Chen, Jinquan Luo, Yuansheng Tang, Quanquan Liu. Some new results on cross correlation of $p$-ary $m$-sequence and its decimated sequence. Advances in Mathematics of Communications, 2015, 9 (3) : 375-390. doi: 10.3934/amc.2015.9.375
[12]	Liqun Yao, Wenli Ren, Yong Wang, Chunming Tang. Z-complementary pairs with flexible lengths and large zero odd-periodic correlation zones. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021037
[13]	Vladimír Špitalský. Local correlation entropy. Discrete and Continuous Dynamical Systems, 2018, 38 (11) : 5711-5733. doi: 10.3934/dcds.2018249
[14]	Ming Su, Arne Winterhof. Hamming correlation of higher order. Advances in Mathematics of Communications, 2018, 12 (3) : 505-513. doi: 10.3934/amc.2018029
[15]	Nian Li, Xiaohu Tang, Tor Helleseth. A class of quaternary sequences with low correlation. Advances in Mathematics of Communications, 2015, 9 (2) : 199-210. doi: 10.3934/amc.2015.9.199
[16]	Xin-Guo Liu, Kun Wang. A multigrid method for the maximal correlation problem. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 785-796. doi: 10.3934/naco.2012.2.785
[17]	Kaitlyn (Voccola) Muller. SAR correlation imaging and anisotropic scattering. Inverse Problems and Imaging, 2018, 12 (3) : 697-731. doi: 10.3934/ipi.2018030
[18]	Oǧuz Yayla. Nearly perfect sequences with arbitrary out-of-phase autocorrelation. Advances in Mathematics of Communications, 2016, 10 (2) : 401-411. doi: 10.3934/amc.2016014
[19]	Yu Zheng, Li Peng, Teturo Kamae. Characterization of noncorrelated pattern sequences and correlation dimensions. Discrete and Continuous Dynamical Systems, 2018, 38 (10) : 5085-5103. doi: 10.3934/dcds.2018223
[20]	Houduo Qi, ZHonghang Xia, Guangming Xing. An application of the nearest correlation matrix on web document classification. Journal of Industrial and Management Optimization, 2007, 3 (4) : 701-713. doi: 10.3934/jimo.2007.3.701

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Samuel T. Blake Thomas E. Hall Andrew Z. Tirkel
on Google Scholar
Samuel T. Blake Thomas E. Hall Andrew Z. Tirkel

[Back to Top]