American Institute of Mathematical Sciences

Advanced
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

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

[2]

L. Bömer and M. Antweiler, Perfect n-phase sequences and arrays, IEEE J. Selected Areas Commun., 10 (1992), 782-789. Google Scholar

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

[4]

G. Caronni, Ermitteln unauthorisierter Verteiler von maschinenlesbaren Daten, ETH, Zurich, Switzerland, Tech. Rep., 1993. Google Scholar

[5]

W. Chi and N. George, Phase-coded aperture for optical imaging, Optics Commun., 282 (2009), 2110-2117. Google Scholar

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

[7]

T. Cox and P. D'Antonio, "Acoustic Absorbers and Diffusers,'' $2^{nd}$ edition, Taylor and Francis, 2009. Google Scholar

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

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

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

[11]

F. Hartung and M. Kutter, Multimedia watermarking techniques, Proc. IEEE, 87 (1999), 1079-1107. doi: 10.1109/5.771066.  Google Scholar

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

[13]

V. P. Ipatov, Contribution to the theory of sequence with perfect periodic autocorrelation properties, Radio Engin. Electr. Phys., 25 (1980), 31-34.  Google Scholar

[14]

J. Jedwab and C. Mitchell, Constructing new perfect binary arrays, Electronic Letters, 24 (1988), 650-652. doi: 10.1049/el:19880440.  Google Scholar

[15]

L. E. Kopilovich, On perfect binary arrays, Electronics Letters, 24 (1988), 566-567. doi: 10.1049/el:19880385.  Google Scholar

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

[17]

H-D. Lüke, Sequences and arrays with perfect periodic correlation, IEEE Trans. Aerospace Electr. Sys., 24 (1988), 287-294. Google Scholar

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

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

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

[21]

B. G. Mobasseri, Direct sequence watermarking of digital video using m-frames, in "ICIP,'' (1998), 399-403. doi: 10.1109/ICIP.1998.723399.  Google Scholar

[22]

W. H. Mow, "A Study of Correlation of Sequences,'' Ph.D thesis, The Chinese University of Hong Kong, 1993. Google Scholar

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

[24]

M. R Schroeder, "Number Theory in Science and Communications, with Applications to Physics, Digital Information, Computing and Self-Similarity,'' Springer, 2006.  Google Scholar

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

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

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

[28]

P. Wild, Infinite families of perfect binary arrays,, Electronics letters., ().  doi: 10.1049/el:19880575.  Google Scholar

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

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

[31]

R. B. Wolfgang and E. J. Delp, "Authentication of Signals Using Watermarks,'' U.S. Patent 6,625,295, September 2003. Google Scholar

[32]

J. Zhao and E. Koch, A generic digital watermarking model, Comp. Graphics, 22 (1998), 397-403. Google Scholar

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

[2]

L. Bömer and M. Antweiler, Perfect n-phase sequences and arrays, IEEE J. Selected Areas Commun., 10 (1992), 782-789. Google Scholar

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

[4]

G. Caronni, Ermitteln unauthorisierter Verteiler von maschinenlesbaren Daten, ETH, Zurich, Switzerland, Tech. Rep., 1993. Google Scholar

[5]

W. Chi and N. George, Phase-coded aperture for optical imaging, Optics Commun., 282 (2009), 2110-2117. Google Scholar

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

[7]

T. Cox and P. D'Antonio, "Acoustic Absorbers and Diffusers,'' $2^{nd}$ edition, Taylor and Francis, 2009. Google Scholar

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

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

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

[11]

F. Hartung and M. Kutter, Multimedia watermarking techniques, Proc. IEEE, 87 (1999), 1079-1107. doi: 10.1109/5.771066.  Google Scholar

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

[13]

V. P. Ipatov, Contribution to the theory of sequence with perfect periodic autocorrelation properties, Radio Engin. Electr. Phys., 25 (1980), 31-34.  Google Scholar

[14]

J. Jedwab and C. Mitchell, Constructing new perfect binary arrays, Electronic Letters, 24 (1988), 650-652. doi: 10.1049/el:19880440.  Google Scholar

[15]

L. E. Kopilovich, On perfect binary arrays, Electronics Letters, 24 (1988), 566-567. doi: 10.1049/el:19880385.  Google Scholar

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

[17]

H-D. Lüke, Sequences and arrays with perfect periodic correlation, IEEE Trans. Aerospace Electr. Sys., 24 (1988), 287-294. Google Scholar

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

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

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

[21]

B. G. Mobasseri, Direct sequence watermarking of digital video using m-frames, in "ICIP,'' (1998), 399-403. doi: 10.1109/ICIP.1998.723399.  Google Scholar

[22]

W. H. Mow, "A Study of Correlation of Sequences,'' Ph.D thesis, The Chinese University of Hong Kong, 1993. Google Scholar

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

[24]

M. R Schroeder, "Number Theory in Science and Communications, with Applications to Physics, Digital Information, Computing and Self-Similarity,'' Springer, 2006.  Google Scholar

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

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

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

[28]

P. Wild, Infinite families of perfect binary arrays,, Electronics letters., ().  doi: 10.1049/el:19880575.  Google Scholar

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

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

[31]

R. B. Wolfgang and E. J. Delp, "Authentication of Signals Using Watermarks,'' U.S. Patent 6,625,295, September 2003. Google Scholar

[32]

J. Zhao and E. Koch, A generic digital watermarking model, Comp. Graphics, 22 (1998), 397-403. Google Scholar

[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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2007, 3 (4) : 701-713. doi: 10.3934/jimo.2007.3.701

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (71)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy