2014, 8(1): 83-101. doi: 10.3934/amc.2014.8.83

Sets of zero-difference balanced functions and their applications

1. 

Institute of Algebra and Geometry, Otto-von-Guericke University Magdeburg, 39106 Magdeburg, Germany

2. 

Department of Mathematics and System Sciences, National University of Defense Technology, Changsha, Hunan 410073, China

Received  March 2013 Revised  September 2013 Published  January 2014

Zero-difference balanced (ZDB) functions can be employed in many applications, e.g., optimal constant composition codes, optimal and perfect difference systems of sets, optimal frequency hopping sequences, etc. In this paper, two results are summarized to characterize ZDB functions, among which a lower bound is used to achieve optimality in applications and determine the size of preimage sets of ZDB functions. As the main contribution, a generic construction of ZDB functions is presented, and many new classes of ZDB functions can be generated. This construction is then extended to construct a set of ZDB functions, in which any two ZDB functions are related uniformly. Furthermore, some applications of such sets of ZDB functions are also introduced.
Citation: Qi Wang, Yue Zhou. Sets of zero-difference balanced functions and their applications. Advances in Mathematics of Communications, 2014, 8 (1) : 83-101. doi: 10.3934/amc.2014.8.83
References:
[1]

M. Antweiler and L. Bömer, Complex sequences over GF$(p^M)$ with a two-level autocorrelation function and a large linear span,, IEEE Trans. Inform. Theory, (1992), 120. doi: 10.1109/18.108256.

[2]

C. Carlet, C. Ding and J. Yuan, Linear codes from perfect nonlinear mappings and their secret sharing schemes,, IEEE Trans. Inform. Theory, (2005), 2089. doi: 10.1109/TIT.2005.847722.

[3]

L. Carlitz and C. Wells, The number of solutions of a special system of equations in a finite field,, Acta Arith., 12 (): 77.

[4]

P. Dembowski and T. G. Ostrom, Planes of order $n$ with collineation groups of order $n^2$,, Math. Z., 103 (1968), 239. doi: 10.1007/BF01111042.

[5]

C. Ding, Optimal constant composition codes from zero-difference balanced functions,, IEEE Trans. Inform. Theory, 54 (2008), 5766. doi: 10.1109/TIT.2008.2006420.

[6]

C. Ding, Optimal and perfect difference systems of sets,, J. Combin. Theory Ser. A, 116 (2009), 109. doi: 10.1016/j.jcta.2008.05.007.

[7]

C. Ding, M. J. Moisio and J. Yuan, Algebraic constructions of optimal frequency-hopping sequences,, IEEE Trans. Inform. Theory, 53 (2007), 2606. doi: 10.1109/TIT.2007.899545.

[8]

C. Ding and Y. Tan, Zero-difference balanced functions with applications,, J. Stat. Theory Practice, 6 (2012), 3. doi: 10.1080/15598608.2012.647479.

[9]

C. Ding and J. Yin, Algebraic constructions of constant composition codes,, IEEE Trans. Inform. Theory, 51 (2005), 1585. doi: 10.1109/TIT.2005.844087.

[10]

C. Ding and J. Yin, Combinatorial constructions of optimal constant-composition codes,, IEEE Trans. Inform. Theory, 51 (2005), 3671. doi: 10.1109/TIT.2005.855612.

[11]

C. Ding and J. Yin, Sets of optimal frequency-hopping sequences,, IEEE Trans. Inform. Theory, 54 (2008), 3741. doi: 10.1109/TIT.2008.926410.

[12]

F.-W. Fu, A. J. H. Vinck and S.-Y. Shen, On the constructions of constant-weight codes,, IEEE Trans. Inform. Theory, 44 (1998), 328. doi: 10.1109/18.651060.

[13]

R. Fuji-Hara, Y. Miao and M. Mishima, Optimal frequency hopping sequences: a combinatorial approach,, IEEE Trans. Inform. Theory, 50 (2004), 2408. doi: 10.1109/TIT.2004.834783.

[14]

G. Ge, R. Fuji-Hara and Y. Miao, Further combinatorial constructions for optimal frequency-hopping sequences,, J. Combin. Theory Ser. A, 113 (2006), 1699. doi: 10.1016/j.jcta.2006.03.019.

[15]

G. Ge, Y. Miao and Z. Yao, Optimal frequency hopping sequences: auto- and cross-correlation properties,, IEEE Trans. Inform. Theory, 55 (2009), 867. doi: 10.1109/TIT.2008.2009856.

[16]

S. W. Golomb and G. Gong, Signal Design for Good Correlation, for Wireless Communication, Cryptography, and Radar,, Cambridge University Press, (2005). doi: 10.1017/CBO9780511546907.

[17]

P. V. Kumar, Frequency-hopping code sequence designs having large linear span,, IEEE Trans. Inform. Theory, 34 (1988), 146. doi: 10.1109/18.2616.

[18]

A. Lempel and H. Greenberger, Families of sequences with optimal Hamming correlation properties,, IEEE Trans. Inform. Theory, 20 (1974), 90.

[19]

V. I. Levenšteĭn, A certain method of constructing quasilinear codes that guarantee synchronization in the presence of errors,, Problemy Peredači Informacii, 7 (1971), 30.

[20]

V. I. Levenšteĭn, Combinatorial problems motivated by comma-free codes,, J. Combin. Des., 12 (2004), 184. doi: 10.1002/jcd.10071.

[21]

R. Lidl and H. Niederreiter, Finite Fields, Second edition,, Cambridge University Press, (1997).

[22]

Y. Luo, F.-W. Fu, A. J. H. Vinck and W. Chen, On constant-composition codes over $Z_q$,, IEEE Trans. Inform. Theory, 49 (2003), 3010. doi: 10.1109/TIT.2003.819339.

[23]

H. Niederreiter and A. Winterhof, Cyclotomic $\mathfrakR $-orthomorphisms of finite fields,, Discrete Math., 295 (2005), 161. doi: 10.1016/j.disc.2004.12.011.

[24]

K. Nyberg, Perfect nonlinear S-boxes,, in Advances in Cryptology-EUROCRYPT '91, (1991), 378. doi: 10.1007/3-540-46416-6_32.

[25]

D. Peng and P. Fan, Lower bounds on the Hamming auto- and cross correlations of frequency-hopping sequences,, IEEE Trans. Inform. Theory, 50 (2004), 2149. doi: 10.1109/TIT.2004.833362.

[26]

D. V. Sarwate, Comments on "Lower bounds on the Hamming auto- and cross correlations of frequency-hopping sequences'' by D. Peng and P. Fan,, IEEE Trans. Inform. Theory, 51 (2005). doi: 10.1109/TIT.2005.844055.

[27]

M. K. Simon, J. K. Omura, R. A. Scholtz and B. K. Levitt, Spread Spectrum Communications Handbook, revised edition,, McGraw-Hill Inc., (2002).

[28]

H. Wang, A new bound for difference systems of sets,, J. Combin. Math. Combin. Comput., 58 (2006), 161.

[29]

Q. Wang, Optimal sets of frequency hopping sequences with large linear spans,, IEEE Trans. Inform. Theory, 56 (2010), 1729. doi: 10.1109/TIT.2010.2040874.

[30]

Z. Zhou, X. Tang, D. Wu and Y. Yang, Some new classes of zero-difference balanced functions,, IEEE Trans. Inform. Theory, 58 (2012), 139. doi: 10.1109/TIT.2011.2171418.

show all references

References:
[1]

M. Antweiler and L. Bömer, Complex sequences over GF$(p^M)$ with a two-level autocorrelation function and a large linear span,, IEEE Trans. Inform. Theory, (1992), 120. doi: 10.1109/18.108256.

[2]

C. Carlet, C. Ding and J. Yuan, Linear codes from perfect nonlinear mappings and their secret sharing schemes,, IEEE Trans. Inform. Theory, (2005), 2089. doi: 10.1109/TIT.2005.847722.

[3]

L. Carlitz and C. Wells, The number of solutions of a special system of equations in a finite field,, Acta Arith., 12 (): 77.

[4]

P. Dembowski and T. G. Ostrom, Planes of order $n$ with collineation groups of order $n^2$,, Math. Z., 103 (1968), 239. doi: 10.1007/BF01111042.

[5]

C. Ding, Optimal constant composition codes from zero-difference balanced functions,, IEEE Trans. Inform. Theory, 54 (2008), 5766. doi: 10.1109/TIT.2008.2006420.

[6]

C. Ding, Optimal and perfect difference systems of sets,, J. Combin. Theory Ser. A, 116 (2009), 109. doi: 10.1016/j.jcta.2008.05.007.

[7]

C. Ding, M. J. Moisio and J. Yuan, Algebraic constructions of optimal frequency-hopping sequences,, IEEE Trans. Inform. Theory, 53 (2007), 2606. doi: 10.1109/TIT.2007.899545.

[8]

C. Ding and Y. Tan, Zero-difference balanced functions with applications,, J. Stat. Theory Practice, 6 (2012), 3. doi: 10.1080/15598608.2012.647479.

[9]

C. Ding and J. Yin, Algebraic constructions of constant composition codes,, IEEE Trans. Inform. Theory, 51 (2005), 1585. doi: 10.1109/TIT.2005.844087.

[10]

C. Ding and J. Yin, Combinatorial constructions of optimal constant-composition codes,, IEEE Trans. Inform. Theory, 51 (2005), 3671. doi: 10.1109/TIT.2005.855612.

[11]

C. Ding and J. Yin, Sets of optimal frequency-hopping sequences,, IEEE Trans. Inform. Theory, 54 (2008), 3741. doi: 10.1109/TIT.2008.926410.

[12]

F.-W. Fu, A. J. H. Vinck and S.-Y. Shen, On the constructions of constant-weight codes,, IEEE Trans. Inform. Theory, 44 (1998), 328. doi: 10.1109/18.651060.

[13]

R. Fuji-Hara, Y. Miao and M. Mishima, Optimal frequency hopping sequences: a combinatorial approach,, IEEE Trans. Inform. Theory, 50 (2004), 2408. doi: 10.1109/TIT.2004.834783.

[14]

G. Ge, R. Fuji-Hara and Y. Miao, Further combinatorial constructions for optimal frequency-hopping sequences,, J. Combin. Theory Ser. A, 113 (2006), 1699. doi: 10.1016/j.jcta.2006.03.019.

[15]

G. Ge, Y. Miao and Z. Yao, Optimal frequency hopping sequences: auto- and cross-correlation properties,, IEEE Trans. Inform. Theory, 55 (2009), 867. doi: 10.1109/TIT.2008.2009856.

[16]

S. W. Golomb and G. Gong, Signal Design for Good Correlation, for Wireless Communication, Cryptography, and Radar,, Cambridge University Press, (2005). doi: 10.1017/CBO9780511546907.

[17]

P. V. Kumar, Frequency-hopping code sequence designs having large linear span,, IEEE Trans. Inform. Theory, 34 (1988), 146. doi: 10.1109/18.2616.

[18]

A. Lempel and H. Greenberger, Families of sequences with optimal Hamming correlation properties,, IEEE Trans. Inform. Theory, 20 (1974), 90.

[19]

V. I. Levenšteĭn, A certain method of constructing quasilinear codes that guarantee synchronization in the presence of errors,, Problemy Peredači Informacii, 7 (1971), 30.

[20]

V. I. Levenšteĭn, Combinatorial problems motivated by comma-free codes,, J. Combin. Des., 12 (2004), 184. doi: 10.1002/jcd.10071.

[21]

R. Lidl and H. Niederreiter, Finite Fields, Second edition,, Cambridge University Press, (1997).

[22]

Y. Luo, F.-W. Fu, A. J. H. Vinck and W. Chen, On constant-composition codes over $Z_q$,, IEEE Trans. Inform. Theory, 49 (2003), 3010. doi: 10.1109/TIT.2003.819339.

[23]

H. Niederreiter and A. Winterhof, Cyclotomic $\mathfrakR $-orthomorphisms of finite fields,, Discrete Math., 295 (2005), 161. doi: 10.1016/j.disc.2004.12.011.

[24]

K. Nyberg, Perfect nonlinear S-boxes,, in Advances in Cryptology-EUROCRYPT '91, (1991), 378. doi: 10.1007/3-540-46416-6_32.

[25]

D. Peng and P. Fan, Lower bounds on the Hamming auto- and cross correlations of frequency-hopping sequences,, IEEE Trans. Inform. Theory, 50 (2004), 2149. doi: 10.1109/TIT.2004.833362.

[26]

D. V. Sarwate, Comments on "Lower bounds on the Hamming auto- and cross correlations of frequency-hopping sequences'' by D. Peng and P. Fan,, IEEE Trans. Inform. Theory, 51 (2005). doi: 10.1109/TIT.2005.844055.

[27]

M. K. Simon, J. K. Omura, R. A. Scholtz and B. K. Levitt, Spread Spectrum Communications Handbook, revised edition,, McGraw-Hill Inc., (2002).

[28]

H. Wang, A new bound for difference systems of sets,, J. Combin. Math. Combin. Comput., 58 (2006), 161.

[29]

Q. Wang, Optimal sets of frequency hopping sequences with large linear spans,, IEEE Trans. Inform. Theory, 56 (2010), 1729. doi: 10.1109/TIT.2010.2040874.

[30]

Z. Zhou, X. Tang, D. Wu and Y. Yang, Some new classes of zero-difference balanced functions,, IEEE Trans. Inform. Theory, 58 (2012), 139. doi: 10.1109/TIT.2011.2171418.

[1]

Shanding Xu, Xiwang Cao, Jiafu Mi, Chunming Tang. More cyclotomic constructions of optimal frequency-hopping sequences. Advances in Mathematics of Communications, 2019, 13 (3) : 373-391. doi: 10.3934/amc.2019024

[2]

Lenny Fukshansky, Ahmad A. Shaar. A new family of one-coincidence sets of sequences with dispersed elements for frequency hopping cdma systems. Advances in Mathematics of Communications, 2018, 12 (1) : 181-188. doi: 10.3934/amc.2018012

[3]

Aixian Zhang, Zhengchun Zhou, Keqin Feng. A lower bound on the average Hamming correlation of frequency-hopping sequence sets. Advances in Mathematics of Communications, 2015, 9 (1) : 55-62. doi: 10.3934/amc.2015.9.55

[4]

Fang Liu, Daiyuan Peng, Zhengchun Zhou, Xiaohu Tang. New constructions of optimal frequency hopping sequences with new parameters. Advances in Mathematics of Communications, 2013, 7 (1) : 91-101. doi: 10.3934/amc.2013.7.91

[5]

Xianhua Niu, Daiyuan Peng, Zhengchun Zhou. New classes of optimal frequency hopping sequences with low hit zone. Advances in Mathematics of Communications, 2013, 7 (3) : 293-310. doi: 10.3934/amc.2013.7.293

[6]

Xing Liu, Daiyuan Peng. Frequency hopping sequences with optimal aperiodic Hamming correlation by interleaving techniques. Advances in Mathematics of Communications, 2017, 11 (1) : 151-159. doi: 10.3934/amc.2017009

[7]

Xing Liu, Daiyuan Peng. Sets of frequency hopping sequences under aperiodic Hamming correlation: Upper bound and optimal constructions. Advances in Mathematics of Communications, 2014, 8 (3) : 359-373. doi: 10.3934/amc.2014.8.359

[8]

Yuri Kifer. Ergodic theorems for nonconventional arrays and an extension of the Szemerédi theorem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (6) : 2687-2716. doi: 10.3934/dcds.2018113

[9]

Denis S. Krotov, Patric R. J.  Östergård, Olli Pottonen. Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code. Advances in Mathematics of Communications, 2016, 10 (2) : 393-399. doi: 10.3934/amc.2016013

[10]

Feng Qi, Bai-Ni Guo. Completely monotonic functions involving divided differences of the di- and tri-gamma functions and some applications. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1975-1989. doi: 10.3934/cpaa.2009.8.1975

[11]

Jingjun Bao. New families of strictly optimal frequency hopping sequence sets. Advances in Mathematics of Communications, 2018, 12 (2) : 387-413. doi: 10.3934/amc.2018024

[12]

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

[13]

Andries E. Brouwer, Tuvi Etzion. Some new distance-4 constant weight codes. Advances in Mathematics of Communications, 2011, 5 (3) : 417-424. doi: 10.3934/amc.2011.5.417

[14]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032

[15]

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

[16]

Yang Yang, Xiaohu Tang, Guang Gong. New almost perfect, odd perfect, and perfect sequences from difference balanced functions with d-form property. Advances in Mathematics of Communications, 2017, 11 (1) : 67-76. doi: 10.3934/amc.2017002

[17]

Anass Belcaid, Mohammed Douimi, Abdelkader Fassi Fihri. Recursive reconstruction of piecewise constant signals by minimization of an energy function. Inverse Problems & Imaging, 2018, 12 (4) : 903-920. doi: 10.3934/ipi.2018038

[18]

Tibor Krisztin. The unstable set of zero and the global attractor for delayed monotone positive feedback. Conference Publications, 2001, 2001 (Special) : 229-240. doi: 10.3934/proc.2001.2001.229

[19]

Sanyi Tang, Wenhong Pang. On the continuity of the function describing the times of meeting impulsive set and its application. Mathematical Biosciences & Engineering, 2017, 14 (5&6) : 1399-1406. doi: 10.3934/mbe.2017072

[20]

Jonas Eriksson. A weight-based characterization of the set of correctable error patterns under list-of-2 decoding. Advances in Mathematics of Communications, 2007, 1 (3) : 331-356. doi: 10.3934/amc.2007.1.331

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (12)

Other articles
by authors

[Back to Top]