American Institute of Mathematical Sciences

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  August 2020 Early access  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. Berger, F. 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. [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. [3] A. E. Gamal, L. Hemachandra, I. 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. [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. [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. [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. [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. [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). [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. [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. [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. [12] C. Torezzan, S. 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. [13] R. Zamir, Lattice Coding for Signals and Networks, 1$^{st}$ edition, Cambridge University Press, Cambridge, 2014.

show all references

References:
 [1] T. Berger, F. 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. [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. [3] A. E. Gamal, L. Hemachandra, I. 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. [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. [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. [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. [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. [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). [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. [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. [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. [12] C. Torezzan, S. 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. [13] R. Zamir, Lattice Coding for Signals and Networks, 1$^{st}$ edition, Cambridge University Press, Cambridge, 2014.
Illustration of the quantization process in $\mathbb{R}^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]
Example of a spherical code $C(3,100)_+\subset \mathbb{R}^{3}$ that represents 100 flat tori in $S^{5} \subset \mathbb{R}^{6}$
Illustration of the construction of a torus layer spherical code $C_T(4, M)$
Illustration of the quantization process of a vector x
SNR as a function of the number of tori, for rate $R = 3$ and dimensions 4, 6 and 8
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 and Continuous Dynamical Systems, 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 and Continuous Dynamical Systems, 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 and Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465 [6] Richard Archibald, Hoang Tran. A dictionary learning algorithm for compression and reconstruction of streaming data in preset order. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 655-668. doi: 10.3934/dcdss.2021102 [7] 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 [8] Gabriele Nebe, Wolfgang Willems. On self-dual MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 633-642. doi: 10.3934/amc.2016031 [9] 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 [10] Matti Lassas, Teemu Saksala, Hanming Zhou. Reconstruction of a compact manifold from the scattering data of internal sources. Inverse Problems and 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 and Management Optimization, 2008, 4 (1) : 155-165. doi: 10.3934/jimo.2008.4.155 [12] Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems and Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030 [13] Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $A_n$-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118 [14] 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 [15] 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 [16] 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 [17] 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 [18] 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, 2020, 14 (2) : 319-332. doi: 10.3934/amc.2020023 [19] Keita Ishizuka, Ken Saito. Construction for both self-dual codes and LCD codes. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2021070 [20] 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, 2020, 14 (3) : 491-505. doi: 10.3934/amc.2020060

2020 Impact Factor: 0.935