February  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, 38 (1992), 120-130. 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, 51 (2005), 2089-2102. 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-258. doi: 10.1007/BF01111042.

[5]

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

[6]

C. Ding, Optimal and perfect difference systems of sets, J. Combin. Theory Ser. A, 116 (2009), 109-119. 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-2610. 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-19. 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-1589. 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-3674. 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-3745. 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-333. 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-2420. 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-1718. 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-879. 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, Cambridge, 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-151. 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-94.

[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-40.

[20]

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

[21]

R. Lidl and H. Niederreiter, Finite Fields, Second edition, Cambridge University Press, Cambridge, 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-3016. doi: 10.1109/TIT.2003.819339.

[23]

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

[24]

K. Nyberg, Perfect nonlinear S-boxes, in Advances in Cryptology-EUROCRYPT '91, Springer, Berlin, 1991, 378-386. 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-2154. 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), 1615. 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., New York, 2002.

[28]

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

[29]

Q. Wang, Optimal sets of frequency hopping sequences with large linear spans, IEEE Trans. Inform. Theory, 56 (2010), 1729-1736. 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-145. 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, 38 (1992), 120-130. 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, 51 (2005), 2089-2102. 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-258. doi: 10.1007/BF01111042.

[5]

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

[6]

C. Ding, Optimal and perfect difference systems of sets, J. Combin. Theory Ser. A, 116 (2009), 109-119. 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-2610. 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-19. 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-1589. 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-3674. 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-3745. 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-333. 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-2420. 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-1718. 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-879. 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, Cambridge, 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-151. 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-94.

[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-40.

[20]

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

[21]

R. Lidl and H. Niederreiter, Finite Fields, Second edition, Cambridge University Press, Cambridge, 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-3016. doi: 10.1109/TIT.2003.819339.

[23]

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

[24]

K. Nyberg, Perfect nonlinear S-boxes, in Advances in Cryptology-EUROCRYPT '91, Springer, Berlin, 1991, 378-386. 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-2154. 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), 1615. 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., New York, 2002.

[28]

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

[29]

Q. Wang, Optimal sets of frequency hopping sequences with large linear spans, IEEE Trans. Inform. Theory, 56 (2010), 1729-1736. 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-145. 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]

Xianhong Xie, Yi Ouyang, Honggang Hu, Ming Mao. Construction of three classes of strictly optimal frequency-hopping sequence sets. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022024

[5]

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

[6]

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

[7]

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

[8]

Wenli Ren, Feng Wang. A new class of optimal wide-gap one-coincidence frequency-hopping sequence sets. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020131

[9]

Wenjuan Yin, Can Xiang, Fang-Wei Fu. Two constructions of low-hit-zone frequency-hopping sequence sets. Advances in Mathematics of Communications, 2022, 16 (2) : 249-267. doi: 10.3934/amc.2020110

[10]

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

[11]

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

[12]

Xiujie Zhang, Xianhua Niu, Xin Tan. Constructions of optimal low hit zone frequency hopping sequence sets with large family size. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2021071

[13]

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

[14]

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

[15]

Shanding Xu, Longjiang Qu, Xiwang Cao. Three classes of partitioned difference families and their optimal constant composition codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020120

[16]

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

[17]

Hongyu Han, Sheng Zhang. New classes of strictly optimal low hit zone frequency hopping sequence sets. Advances in Mathematics of Communications, 2020, 14 (4) : 579-589. doi: 10.3934/amc.2020031

[18]

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

[19]

Ferruh Özbudak, Eda Tekin. Correlation distribution of a sequence family generalizing some sequences of Trachtenberg. Advances in Mathematics of Communications, 2021, 15 (4) : 647-662. doi: 10.3934/amc.2020087

[20]

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

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (133)
  • HTML views (0)
  • Cited by (20)

Other articles
by authors

[Back to Top]