August  2020, 14(3): 467-476. doi: 10.3934/amc.2020064

A shape-gain approach for vector quantization based on flat tori

1. 

State University of Goias, Anapolis, GO 75132-903, Brazil

2. 

School of Applied Sciences, University of Campinas, Limeira, SP 13484-350, Brazil

 

Received  December 2018 Revised  September 2019 Published  January 2020

Fund Project: This research is supported by the Sao Paulo Research Foundation, FAPESP, grant 13/25977-7

In this paper we present a vector quantization framework for Gaussian sources which combines a spherical code on layers of flat tori and the shape and gain technique. The basic concepts of spherical codes in tori layers are reviewed and two constructions are presented for the shape by exploiting the $ k/2 $-dimensional lattices $ D_{k/2} $ and $ A^{*}_{k/2} $ as its pre-image. A scalar quantizer is optimized for the gain by using the Lloyd-Max algorithm for a given rate. The computational complexity of the quantization process is dominated by the lattice decoding process, which is linear for the $ D_{k/2} $ lattice and quadratic for the $ A^{*}_{k/2} $ lattice. The proposed quantizer is described in details and some numerical results are presented in terms of the SNR as a function of the quantization rate, in bits per dimension. The results show that the quantizer designed from the $ D_4 $ lattice outperform previous records when the rate is equal to 1 bit per dimension. These quantizer also outperform the quantizers designed from the dual lattice $ A^{*} $ for all rates tested. In general the two proposed frameworks perform within 2 dB of the rate distortion function, which may be a good trade-off considering their low computational complexity.

Citation: Fabiano Boaventura de Miranda, Cristiano Torezzan. A shape-gain approach for vector quantization based on flat tori. Advances in Mathematics of Communications, 2020, 14 (3) : 467-476. doi: 10.3934/amc.2020064
References:
[1]

T. BergerF. Jelinek and J. K. Wolf, Permutation codes for sources, IEEE Transaction on Infomation Theory, IT-18 (1972), 160-169.  doi: 10.1109/tit.1972.1054729.  Google Scholar

[2]

J. H. Conway and N. J. A. Sloane, Sphere-Packings, Lattices, and Groups, Third edition, Grundlehren der Mathematischen Wissenschaften, 290. Springer-Verlag, New York, 1999. doi: 10.1007/978-1-4757-6568-7.  Google Scholar

[3]

A. E. GamalL. HemachandraI. Shperling and V. Wei, Using simulated annealing to design good codes, IEEE Transactions on Information Theory, 33 (1987), 116-123.  doi: 10.1109/TIT.1987.1057277.  Google Scholar

[4]

A. Gersho and R. M.Gray, Vector Quantization and Signal Compression, 8$^{th}$ edition, Kluwer Academic Publishers, New York, 2001. doi: 10.1007/978-1-4615-3626-0.  Google Scholar

[5]

J. Hamkins and K. Zeger, Asymptotically dense spherical codes. Ⅰ. Wrapped spherical codes, IEEE Transactions on Information Theory, 43 (1997), 1774-1785.  doi: 10.1109/18.641544.  Google Scholar

[6]

J. Hamkins and K. Zeger, Asymptotically dense spherical codes. Ⅱ. Laminated spherical codes, IEEE Transactions on Information Theory, 43 (1997), 1786-1798.  doi: 10.1109/18.641545.  Google Scholar

[7]

J. Hamkins and K. Zeger, Gaussian source coding with spherical codes, IEEE Transactions on Information Theory, 48 (2002), 2980-2989.  doi: 10.1109/TIT.2002.804056.  Google Scholar

[8]

F. B. Miranda and C. Torezzan, A shape-gain approach for vector quantization based on flat tori and dual lattices $A^{*}_{n}$, Latin American Week on Coding and Information, (2018). Google Scholar

[9]

F. B. Miranda and C. Torezzan, Quantização vetorial utilizando códigos esféricos em camadas de toros, XXXV Simpósio Brasileiro de Telecomunicaçoes e Processamento de Sinais, (2017), 230–234. Google Scholar

[10]

C. E. Shannon, Probability of error for optimal codes in a Gaussian channel, The Bell System Technical Journal, 38 (1959), 611-656.  doi: 10.1002/j.1538-7305.1959.tb03905.x.  Google Scholar

[11]

J. E. Strapasson and C. Torezzan, A heuristic approach for designing cyclic group codes, International Transactions in Operational Research, 23 (2016), 883-896.  doi: 10.1111/itor.12238.  Google Scholar

[12]

C. TorezzanS. I. R. Costa and V. A. Vaishampayan, Constructive spherical codes on layers of flat tori, IEEE Trans. Inform. Theory, 59 (2013), 6655-6663.  doi: 10.1109/TIT.2013.2272931.  Google Scholar

[13] R. Zamir, Lattice Coding for Signals and Networks, 1$^{st}$ edition, Cambridge University Press, Cambridge, 2014.   Google Scholar

show all references

References:
[1]

T. BergerF. Jelinek and J. K. Wolf, Permutation codes for sources, IEEE Transaction on Infomation Theory, IT-18 (1972), 160-169.  doi: 10.1109/tit.1972.1054729.  Google Scholar

[2]

J. H. Conway and N. J. A. Sloane, Sphere-Packings, Lattices, and Groups, Third edition, Grundlehren der Mathematischen Wissenschaften, 290. Springer-Verlag, New York, 1999. doi: 10.1007/978-1-4757-6568-7.  Google Scholar

[3]

A. E. GamalL. HemachandraI. Shperling and V. Wei, Using simulated annealing to design good codes, IEEE Transactions on Information Theory, 33 (1987), 116-123.  doi: 10.1109/TIT.1987.1057277.  Google Scholar

[4]

A. Gersho and R. M.Gray, Vector Quantization and Signal Compression, 8$^{th}$ edition, Kluwer Academic Publishers, New York, 2001. doi: 10.1007/978-1-4615-3626-0.  Google Scholar

[5]

J. Hamkins and K. Zeger, Asymptotically dense spherical codes. Ⅰ. Wrapped spherical codes, IEEE Transactions on Information Theory, 43 (1997), 1774-1785.  doi: 10.1109/18.641544.  Google Scholar

[6]

J. Hamkins and K. Zeger, Asymptotically dense spherical codes. Ⅱ. Laminated spherical codes, IEEE Transactions on Information Theory, 43 (1997), 1786-1798.  doi: 10.1109/18.641545.  Google Scholar

[7]

J. Hamkins and K. Zeger, Gaussian source coding with spherical codes, IEEE Transactions on Information Theory, 48 (2002), 2980-2989.  doi: 10.1109/TIT.2002.804056.  Google Scholar

[8]

F. B. Miranda and C. Torezzan, A shape-gain approach for vector quantization based on flat tori and dual lattices $A^{*}_{n}$, Latin American Week on Coding and Information, (2018). Google Scholar

[9]

F. B. Miranda and C. Torezzan, Quantização vetorial utilizando códigos esféricos em camadas de toros, XXXV Simpósio Brasileiro de Telecomunicaçoes e Processamento de Sinais, (2017), 230–234. Google Scholar

[10]

C. E. Shannon, Probability of error for optimal codes in a Gaussian channel, The Bell System Technical Journal, 38 (1959), 611-656.  doi: 10.1002/j.1538-7305.1959.tb03905.x.  Google Scholar

[11]

J. E. Strapasson and C. Torezzan, A heuristic approach for designing cyclic group codes, International Transactions in Operational Research, 23 (2016), 883-896.  doi: 10.1111/itor.12238.  Google Scholar

[12]

C. TorezzanS. I. R. Costa and V. A. Vaishampayan, Constructive spherical codes on layers of flat tori, IEEE Trans. Inform. Theory, 59 (2013), 6655-6663.  doi: 10.1109/TIT.2013.2272931.  Google Scholar

[13] R. Zamir, Lattice Coding for Signals and Networks, 1$^{st}$ edition, Cambridge University Press, Cambridge, 2014.   Google Scholar
Figure 1.  Illustration of the quantization process in $ \mathbb{R}^2 $
13]">Figure 2.  Equivalent radiuses of a rectangular cell. The figure shows $ r_{cov} $, $ r_{pack} $ and $ r_{eff} $ as well as $ r_{\sigma^2} $ (the radius of a ball with the same second moment). We clearly have $ r_{pack} < r_{eff} < r_{\sigma^2} < r_{cov} $ [13]
Figure 3.  Example of a spherical code $ C(3,100)_+\subset \mathbb{R}^{3} $ that represents 100 flat tori in $ S^{5} \subset \mathbb{R}^{6} $
Figure 4.  Illustration of the construction of a torus layer spherical code $ C_T(4, M) $
Figure 5.  Illustration of the quantization process of a vector x
Figure 6.  SNR as a function of the number of tori, for rate $ R = 3 $ and dimensions 4, 6 and 8
Table 1.  Comparison of the vector quantizer performance for $ C_T(k, M) $ with previous results presented in [7]
rate (bits/dimension)
Quantizer 1 2 3 4 5 6
Rate-distortion bound (7) 6.02 12.04 18.06 24.08 30.10 36.12
VQ using $ W_{\Lambda_{24}} $ 2.44 11.02 17.36 23.33 29.29 35.27
VQ using $ C_T(k, M) $ and $ D_4 $ 4.62 10.35 16.30 22.26 28.21 34.03
VQ using $ C_T(k, M) $ and $ A_{n}^{*} $ $ 4.45_\textbf{4} $ $ 10.05_\textbf{8} $ $ 16.16_\textbf{8} $ $ 22.05_\textbf{8} $ $ 27.93_\textbf{8} $ $ 33.34_\textbf{6} $
Lloyd-Max EQ 4.40 9.30 14.62 20.22 26.02 31.89
Uniform EQ 4.40 9.25 14.27 19.38 24.57 29.83
rate (bits/dimension)
Quantizer 1 2 3 4 5 6
Rate-distortion bound (7) 6.02 12.04 18.06 24.08 30.10 36.12
VQ using $ W_{\Lambda_{24}} $ 2.44 11.02 17.36 23.33 29.29 35.27
VQ using $ C_T(k, M) $ and $ D_4 $ 4.62 10.35 16.30 22.26 28.21 34.03
VQ using $ C_T(k, M) $ and $ A_{n}^{*} $ $ 4.45_\textbf{4} $ $ 10.05_\textbf{8} $ $ 16.16_\textbf{8} $ $ 22.05_\textbf{8} $ $ 27.93_\textbf{8} $ $ 33.34_\textbf{6} $
Lloyd-Max EQ 4.40 9.30 14.62 20.22 26.02 31.89
Uniform EQ 4.40 9.25 14.27 19.38 24.57 29.83
[1]

Joe Gildea, Adrian Korban, Abidin Kaya, Bahattin Yildiz. Constructing self-dual codes from group rings and reverse circulant matrices. Advances in Mathematics of Communications, 2021, 15 (3) : 471-485. doi: 10.3934/amc.2020077

[2]

Muhammad Ajmal, Xiande Zhang. New optimal error-correcting codes for crosstalk avoidance in on-chip data buses. Advances in Mathematics of Communications, 2021, 15 (3) : 487-506. doi: 10.3934/amc.2020078

[3]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261

[4]

Yves Dumont, Frederic Chiroleu. Vector control for the Chikungunya disease. Mathematical Biosciences & Engineering, 2010, 7 (2) : 313-345. doi: 10.3934/mbe.2010.7.313

[5]

Davi Obata. Symmetries of vector fields: The diffeomorphism centralizer. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021063

[6]

Antonio Cossidente, Sascha Kurz, Giuseppe Marino, Francesco Pavese. Combining subspace codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021007

[7]

Antonio De Rosa, Domenico Angelo La Manna. A non local approximation of the Gaussian perimeter: Gamma convergence and Isoperimetric properties. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021059

[8]

Yuta Tanoue. Improved Hoeffding inequality for dependent bounded or sub-Gaussian random variables. Probability, Uncertainty and Quantitative Risk, 2021, 6 (1) : 53-60. doi: 10.3934/puqr.2021003

[9]

Zhang Chen, Xiliang Li, Bixiang Wang. Invariant measures of stochastic delay lattice systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3235-3269. doi: 10.3934/dcdsb.2020226

[10]

Fatemeh Abtahi, Zeinab Kamali, Maryam Toutounchi. The BSE concepts for vector-valued Lipschitz algebras. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1171-1186. doi: 10.3934/cpaa.2021011

[11]

Jinsen Guo, Yongwu Zhou, Baixun Li. The optimal pricing and service strategies of a dual-channel retailer under free riding. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021056

[12]

Paul E. Anderson, Timothy P. Chartier, Amy N. Langville, Kathryn E. Pedings-Behling. The rankability of weighted data from pairwise comparisons. Foundations of Data Science, 2021, 3 (1) : 1-26. doi: 10.3934/fods.2021002

[13]

Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087

[14]

Christoforidou Amalia, Christian-Oliver Ewald. A lattice method for option evaluation with regime-switching asset correlation structure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1729-1752. doi: 10.3934/jimo.2020042

[15]

A. K. Misra, Anupama Sharma, Jia Li. A mathematical model for control of vector borne diseases through media campaigns. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1909-1927. doi: 10.3934/dcdsb.2013.18.1909

[16]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046

[17]

Wei Xi Li, Chao Jiang Xu. Subellipticity of some complex vector fields related to the Witten Laplacian. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021047

[18]

Habib Ammari, Josselin Garnier, Vincent Jugnon. Detection, reconstruction, and characterization algorithms from noisy data in multistatic wave imaging. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 389-417. doi: 10.3934/dcdss.2015.8.389

[19]

Cheng-Kai Hu, Fung-Bao Liu, Hong-Ming Chen, Cheng-Feng Hu. Network data envelopment analysis with fuzzy non-discretionary factors. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1795-1807. doi: 10.3934/jimo.2020046

[20]

Woocheol Choi, Youngwoo Koh. On the splitting method for the nonlinear Schrödinger equation with initial data in $ H^1 $. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3837-3867. doi: 10.3934/dcds.2021019

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (170)
  • HTML views (381)
  • Cited by (0)

[Back to Top]