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, 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 $
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]

Stefano Galatolo. Orbit complexity and data compression. Discrete & Continuous Dynamical Systems - A, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477

[2]

Alexander Barg, Oleg R. Musin. Codes in spherical caps. Advances in Mathematics of Communications, 2007, 1 (1) : 131-149. doi: 10.3934/amc.2007.1.131

[3]

Benedetto Piccoli, Francesco Rossi. Measure dynamics with Probability Vector Fields and sources. Discrete & Continuous Dynamical Systems - A, 2019, 39 (11) : 6207-6230. doi: 10.3934/dcds.2019270

[4]

Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039

[5]

Markku Lehtinen, Baylie Damtie, Petteri Piiroinen, Mikko Orispää. Perfect and almost perfect pulse compression codes for range spread radar targets. Inverse Problems & Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465

[6]

Cem Güneri, Ferruh Özbudak, Funda ÖzdemIr. On complementary dual additive cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 353-357. doi: 10.3934/amc.2017028

[7]

Gabriele Nebe, Wolfgang Willems. On self-dual MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 633-642. doi: 10.3934/amc.2016031

[8]

Sergio R. López-Permouth, Benigno R. Parra-Avila, Steve Szabo. Dual generalizations of the concept of cyclicity of codes. Advances in Mathematics of Communications, 2009, 3 (3) : 227-234. doi: 10.3934/amc.2009.3.227

[9]

Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems & Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030

[10]

Matti Lassas, Teemu Saksala, Hanming Zhou. Reconstruction of a compact manifold from the scattering data of internal sources. Inverse Problems & Imaging, 2018, 12 (4) : 993-1031. doi: 10.3934/ipi.2018042

[11]

S. J. Li, Z. M. Fang. On the stability of a dual weak vector variational inequality problem. Journal of Industrial & Management Optimization, 2008, 4 (1) : 155-165. doi: 10.3934/jimo.2008.4.155

[12]

Masaaki Harada, Akihiro Munemasa. Classification of self-dual codes of length 36. Advances in Mathematics of Communications, 2012, 6 (2) : 229-235. doi: 10.3934/amc.2012.6.229

[13]

Stefka Bouyuklieva, Anton Malevich, Wolfgang Willems. On the performance of binary extremal self-dual codes. Advances in Mathematics of Communications, 2011, 5 (2) : 267-274. doi: 10.3934/amc.2011.5.267

[14]

Nikolay Yankov, Damyan Anev, Müberra Gürel. Self-dual codes with an automorphism of order 13. Advances in Mathematics of Communications, 2017, 11 (3) : 635-645. doi: 10.3934/amc.2017047

[15]

Carlos Munuera, Morgan Barbier. Wet paper codes and the dual distance in steganography. Advances in Mathematics of Communications, 2012, 6 (3) : 273-285. doi: 10.3934/amc.2012.6.273

[16]

Alexander Schaub, Olivier Rioul, Jean-Luc Danger, Sylvain Guilley, Joseph Boutros. Challenge codes for physically unclonable functions with Gaussian delays: A maximum entropy problem. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020060

[17]

Steven T. Dougherty, Cristina Fernández-Córdoba, Roger Ten-Valls, Bahattin Yildiz. Quaternary group ring codes: Ranks, kernels and self-dual codes. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020023

[18]

Masaaki Harada, Akihiro Munemasa. On the covering radii of extremal doubly even self-dual codes. Advances in Mathematics of Communications, 2007, 1 (2) : 251-256. doi: 10.3934/amc.2007.1.251

[19]

Stefka Bouyuklieva, Iliya Bouyukliev. Classification of the extremal formally self-dual even codes of length 30. Advances in Mathematics of Communications, 2010, 4 (3) : 433-439. doi: 10.3934/amc.2010.4.433

[20]

Joaquim Borges, Josep Rifà, Victor A. Zinoviev. On $q$-ary linear completely regular codes with $\rho=2$ and antipodal dual. Advances in Mathematics of Communications, 2010, 4 (4) : 567-578. doi: 10.3934/amc.2010.4.567

2018 Impact Factor: 0.879

Article outline

Figures and Tables

[Back to Top]