I 1111111111111111 1111111111 lllll lllll 111111111111111 11111 1111111111 11111111
`US010693700Bl
`
`c12) United States Patent
`Barsoum et al.
`
`(10) Patent No.: US 10,693,700 Bl
`Jun.23,2020
`(45) Date of Patent:
`
`(54) RECEIVERS INCORPORATING
`NON-UNIFORM MULTIDIMENSIONAL
`CONSTELLATIONS AND CODE RATE PAIRS
`
`(71) Applicant: Constellation Designs, LLC, Anaheim,
`CA (US)
`
`(72)
`
`Inventors: Maged F. Barsoum, San Jose, CA
`(US); Christopher R. Jones, Pacific
`Palisades, CA (US)
`
`(73) Assignee: Constellation Designs, LLC, Anaheim,
`CA (US)
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,289,501 A
`5,862,179 A
`
`2/ 1994 Seshadri et al.
`1/1999 Goldstein et al.
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`
`9/2005
`1578021 Al
`1971098 Al
`9/2008
`(Continued)
`
`OTHER PUBLICATIONS
`
`( *) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by O days.
`
`European Supplementary Search Report for Application No. EP
`08795885, International Filing Date Jun. 5, 2008, Search Completed
`Apr. 1, 2014, 8 pgs.
`
`(Continued)
`
`(21) Appl. No.: 16/726,037
`
`(22) Filed:
`
`Dec. 23, 2019
`
`Related U.S. Application Data
`
`(63)
`
`Continuation of application No. 16/206,991, filed on
`Nov. 30, 2018, now Pat. No. 10,567,980, which is a
`(Continued)
`
`(51)
`
`Int. Cl.
`H04L 27106
`H04L 27134
`
`(2006.01)
`(2006.01)
`(Continued)
`
`(52)
`
`(58)
`
`U.S. Cl.
`CPC ...... H04L 2713405 (2013.01); H03M 131255
`(2013.01); H03M 13/6325 (2013.01); H04B
`171336 (2015.01); H04L 2713809 (2013.01)
`Field of Classification Search
`CPC ............ H04L 27/3405; H04L 27/3809; H04B
`17/336; H03M 13/255; H03M 13/6325
`(Continued)
`
`Primary Examiner - Tesfaldet Bocure
`(74) Attorney, Agent, or Firm - KPPB LLP
`
`ABSTRACT
`(57)
`Communication systems are described that use unequally
`spaced constellations that have increased capacity compared
`to conventional constellations operating within a similar
`SNR band. One embodiment is a digital communications
`system including a transmitter transmitting signals via a
`communication channel, the transmitter including a coder
`capable of receiving user bits and outputting encoded bits at
`a rate, a mapper capable of mapping encoded bits to symbols
`in a constellation, and a modulator capable of generating a
`modulated signal for transmission via the communication
`channel using symbols generated by the mapper, wherein the
`constellation is unequally spaced and characterizable by
`assignment of locations and labels of constellation points to
`maximize parallel decode capacity of the constellation at a
`given signal-to-noise ratio so that the constellation provides
`a given capacity at a reduced signal-to-noise ratio compared
`to a uniform constellation that maximizes the minimum
`distance between constellation points of the uniform con(cid:173)
`stellation.
`
`30 Claims, 43 Drawing Sheets
`
`Parallel Decoding Capacity
`r---------------- ---- ----- -------,
`1 B ~ - - -~ X ~ - - -~ Y _ _ _ _ ~ :
`!
`!
`1
`:
`
`Mapper
`
`AWGN
`Channel
`
`Demapper
`
`1
`l
`' - - - - - -~ !
`!
`
`User
`Bits
`
`Coder
`
`40
`
`···································'
`
`•----------------------------------- ~
`~
`
`Received
`Bits
`
`Decoder
`
`LGE 1001
`
`1
`
`

`

`US 10,693,700 Bl
`Page 2
`
`Related U.S. Application Data
`
`continuation of application No. 15/682,475, filed on
`Aug. 21, 2017, now Pat. No. 10,149,179, which is a
`continuation of application No. 15/200,800, filed on
`Jul. 1, 2016, now Pat. No. 9,743,292, which is a
`continuation of application No. 14/491,731, filed on
`Sep. 19, 2014, now Pat. No. 9,385,832, which is a
`continuation of application No. 13/618,630, filed on
`Sep. 14, 2012, now Pat. No. 8,842,761, which is a
`continuation of application No. 13/118,921, filed on
`May 31, 2011, now Pat. No. 8,270,511, which is a
`continuation of application No. 12/156,989, filed on
`Jun. 5, 2008, now Pat. No. 7,978,777.
`
`(60) Provisional application No. 60/933,319, filed on Jun.
`5, 2007.
`
`(51)
`
`Int. Cl.
`H04L 27138
`(2006.01)
`H04B 171336
`(2015.01)
`H03M 13/00
`(2006.01)
`H03M 13125
`(2006.01)
`( 58) Field of Classification Search
`USPC ....... 375/261, 269, 279, 295, 308, 316, 340,
`375/341, 329, 332; 329/103, 304, 305;
`332/104
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`6,084,915 A
`6,115,415 A
`6,157,678 A
`6,603,801 Bl
`6,606,355 Bl
`6,611,554 Bl
`6,665,831 Bl
`7,212,582 B2
`7,215,713 B2 *
`
`7/2000 Williams et al.
`9/2000 Goldstein et al.
`12/2000 Wei
`8/2003 Andren et al.
`8/2003 Wei
`8/2003 Chouly et al.
`12/2003 Yoshida et al.
`5/2007 Zhang et al.
`5/2007 Walker .
`
`H04B 7/18513
`267/246
`
`7,245,666 Bl
`7,376,203 B2
`7,620,067 B2
`7,660,368 B2 *
`
`7,978,777 B2
`8,265,175 B2
`8,270,511 B2
`8,675,754 Bl*
`
`8,842,761 B2
`9,191,148 B2
`9,385,832 B2
`9,743,290 B2
`9,743,292 B2
`9,887,870 B2
`9,967,127 Bl
`10,149,179 B2
`10,524,139 B2
`10,530,629 B2
`2002/0044597 Al
`2002/0106010 Al
`2003/0231715 Al
`2004/0022179 Al
`2004/0066738 Al
`2004/0161050 Al
`2004/0258177 Al
`2005/0089068 Al
`2005/0111581 Al*
`
`2005/0180531 Al
`
`7/2007 Gardner et al.
`5/2008 Brunel et al.
`11/2009 Niu et al.
`2/2010 Ling ..................... H04L 1/0045
`341/143
`
`7/2011 Barsoum et al.
`9/2012 Barsoum et al.
`9/2012 Barsoum et al.
`3/2014 Yonge, III ................ H04L 5/12
`375/261
`
`9/2014 Barsoum et al.
`11/2015 Barsoum
`7/2016 Barsoum et al.
`8/2017 Barsoum et al.
`8/2017 Barsoum et al.
`2/2018 Barsoum et al.
`5/2018 Sun et al.
`12/2018 Barsoum et al.
`12/2019 Barsoum et al.
`1/2020 Barsoum et al.
`4/2002 Shively
`8/2002 Jones
`12/2003 Shoemake
`2/2004 Giannakis et al.
`4/2004 Stopler
`8/2004 Larsson et al.
`12/2004 Shen et al.
`4/2005 Sun et al.
`5/2005 Walker .................. H04L 27/183
`375/308
`
`8/2005 Wellig et al.
`
`2005/0207507 Al
`2005/0268206 Al
`2005/0276343 Al
`2005/0286409 Al
`2006/0045169 Al
`2006/0085720 Al
`2006/0144843 Al
`2006/0155843 Al
`2006/0165190 Al
`2007 /0022179 Al
`2007/0025283 Al
`2007/0054614 Al
`2007/0104293 Al
`2007/0116161 Al
`2007/0147530 Al
`2007/0195868 Al
`2007/0211822 Al
`2007/0280147 Al
`2008/0200114 Al
`2009/0097582 Al
`2009/0161786 Al
`2010/0195743 Al
`2010/0303174 Al
`2011/0090948 Al
`2011/0228869 Al
`2011/0305300 Al
`2012/0147983 Al
`2013/0083862 Al
`2013/0170571 Al
`2014/0314177 Al
`2015/0236812 Al
`2016/0204967 Al
`2016/0309342 Al
`2016/0316382 Al
`2017/0374564 Al
`2017/0374565 Al
`2018/0102933 Al
`2018/0191548 Al
`2019/0116509 Al
`2019/0342772 Al
`
`9/2005 Mitsutani
`12/2005 Tran et al.
`12/2005 Jones
`12/2005 Yoon et al.
`3/2006 Kim
`4/2006 Tran et al.
`7/2006 Vandal et al.
`7/2006 Glass et al.
`7/2006 Tamaki et al.
`1/2007 Kim et al.
`2/2007 Koslov et al.
`3/2007 Walker et al.
`5/2007 Hiatt, Jr. et al.
`5/2007 Tokoro et al.
`6/2007 Li
`8/2007 Walker et al.
`9/2007 Olesen et al.
`12/2007 Catreux-erceg et al.
`8/2008 Eberlein et al.
`4/2009 Barsoum et al.
`6/2009 Nakagawa et al.
`8/2010 Barsoum et al.
`12/2010 Oh et al.
`4/2011 Zhou et al.
`9/2011 Barsoum et al.
`12/2011 Ko
`6/2012 Barsoum et al.
`4/2013 Barsoum et al.
`7/2013 Barsoum et al.
`10/2014 Choi et al.
`8/2015 Barsoum et al.
`7/2016 Choi et al.
`10/2016 Barsoum et al.
`10/2016 Barsoum et al.
`12/2017 Barsoum et al.
`12/2017 Barsoum et al.
`4/2018 Schneider et al.
`7/2018 Barsoum et al.
`4/2019 Barsoum et al.
`11/2019 Barsoum et al.
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`JP
`JP
`JP
`JP
`JP
`TR
`WO
`WO
`WO
`WO
`
`2153561 Bl
`3518485 Al
`09130438 A
`2003229835
`2005269258 A
`2010538502 A
`5513377 B2
`201905158 T4
`9832257
`2007074524 Al
`2008151308 Al
`2010078472 Al
`
`1/2019
`7/2019
`5/1997
`8/2003
`9/2005
`12/2010
`6/2014
`5/2019
`7 /1998
`7/2007
`12/2008
`7/2010
`
`OTHER PUBLICATIONS
`
`Extended European Search Report for European Application No.
`18212572.4, Search completed May 27, 2019, dated Jun. 6, 2019,
`13 Pgs.
`International Preliminary Report on Patentability for International
`Application No. PCT/US/2008/065994, Report Completed Jun. 18,
`2009, Report dated Jun. 30, 2009, 4 pgs.
`International Preliminary Report on Patentability for International
`Application No. PCT/US2009/069881, Report dated Jan. 7, 2011,
`Report dated Jan. 14, 2011, 11 pgs.
`International Search Report for International Application No. PCT/
`US 09/69881, date completed Apr. 12, 2010, dated May 3, 2010, 2
`pgs.
`International Search Report for International Application No. PCT/
`US2008/065994, Report completed Oct. 3, 2008, dated Oct. 22,
`2008, 2 pgs.
`Written Opinion for International Application No. PCT/US2008/
`065994, completed Oct. 3, 2008, dated Oct. 22, 2008, 5 pgs.
`
`2
`
`

`

`US 10,693,700 Bl
`Page 3
`
`(56)
`
`References Cited
`
`OTHER PUBLICATIONS
`
`Written Opinion of the International Searching Authority for Inter(cid:173)
`national Application No. PCT/US 09/69881, date completed Apr.
`13, 2010, dated May 3, 2010, 10 pgs.
`"ETSI EN 302 307 Vl.1.1, European Standard (Telecommunica(cid:173)
`tions series), Digital Video Braodcasting (DVB); Second generation
`framing structure,", channel coding and modulation systems for
`Broadcasting, Interactive Services, News Gathering and other broad(cid:173)
`band satellite applications, Mar. 2005, Retrieved from: http://www.
`etsi.org/deliver/etsi_en/302300_302399/302307/01.01.01_60/en_
`302307v01010 lp.pdf.
`U.S. Appl. No. 13/618,630, "Notice of Allowance Received", May
`15, 2014, 10 pgs.
`Agrell et al., "Gray Coding for Multilevel Constellations in Gauss(cid:173)
`ian Noise", To appear in IEEE Transactions on Information Theory,
`vol. 53, Issue 1, Jan. 2007, Published Dec. 26, 2006, 14 pgs.
`Agrell et al., "On optimal constellations for BICM at low SNR",
`Information Theory Workshop, 2009. ITW 2009. IEEE, Confer(cid:173)
`ence: Oct. 11-16, 2009, 6 pgs.
`Agrell et al., "On the BICM Capacity", ArXiv.org, Dec. 8, 2010, 53
`pgs.
`Agrell et al., "On the Optimality of the Binary Reflected Gray
`Code", IEEE Transactions on Information Theory, Dec. 2004, vol.
`50, No. 12, pp. 3170-3182.
`Agrell et al., "Optimal Signal Sets and Binary Labelings for BICM
`at low SNR", To Appear in IEEE Transactions on Information
`Theory, vol. 57, Issue 10, Oct. 2011, Published Oct. 6, 2011, 24 pgs.
`Alvarado et al., "On the BICM Capacity-Part I: Binary Labelings,
`Arbitrary Input Distributions, and First-Order Asymptotics", Arxiv.
`org, Jan. 25, 2010, 45 pgs.
`Alvarado et al., "On the capacity ofBICM with QAM constellations
`(Invited Paper)", Retrieved from: http://publications.lib.chalmers.
`se/records/fulltext/local_92655.pdf, IWCMC'09, Jun. 21-24, 2009,
`Leipzig, Germany, 8 pgs.
`Arafa et al., "Non-Uniform Signal Constellation for Iteratively
`Decoded Bit Interleaved Coded Modulation (BICM-ID) with Con(cid:173)
`volution and LDPC Codes", 2011 International Conference on
`Innovations in Information Technology, Conference: Apr. 25-27,
`2011, pp. 23-28.
`Barsoum, "On Constellation Design and Iterative Codes", Univer(cid:173)
`sity of California, Los Angeles, Dissertation, 2008, 119 pgs.
`Barsoum et al., "Constellation Design via Capacity maximization",
`IEEE International Symposium on Information Theory, Jun. 24,
`2007, pp. 1821-1825.
`Batshon et al., "Iterative Polar Quantization-Based Modulation to
`Achieve Channel Capacity in Ultrahigh-Speed Optical Communi(cid:173)
`cation Systems", IEEE Photonics Journal, vol. 2, No. 4, pp. 593-599
`Aug. 2010.
`Betts et al., "Performance of Nonuniform Constellations on the
`Gaussian Channel", IEEE Transactions on Information Theory, Sep.
`1994, vol. 40, No. 5, pp. 1633-1638.
`Chen et al., "Increasing achievable information rates via geometric
`shaping", arXiv.org, e-Print Archive, Physics, arXiv: 1804.08850vl,
`Apr. 24, 2018.
`Choi et al., "Channel Capacity Enhancement Scheme for Satellite
`Communication System", 2007 6th International Conference on
`Information, Communications & Signal Processing, Conference:
`Dec. 10-13, 2007, 4 pgs.
`Choi et al., "Satellite-DMB applied to the 8PSK hierarchical
`modulation", Digest of Technical Papers. International Conference
`on Consumer Electronics, 2007. ICCE 2007, Conference: Jan.
`10-14, 2007, 2 pgs.
`Conway et al., "A Fast Encoding Method for Lattice Codes and
`Quantizers", IEEE Transactions on Information Theory, Nov. 1983,
`vol. IT-29, No. 6, pp. 820-824.
`De Gaudenzi et al., "Performance Analysis of Turbo-Coded APSK
`Modultions Over Nonlinear Satellite Channels", IEEE Transactions
`of Wireless Communications, Sep. 2006, vol. 5, No. 5, pp. 2396-
`2407.
`
`De Gaudenzi et al., "APSK Coded Modulation Schemes for Non(cid:173)
`linear Satellite Channels with High Power and Spectral Efficiency",
`American Institute of Aeronautics and Astronautics Paper AIAA,
`2002-1861, 2002, Retrieved from: http://www.dtic.upf.edu/-aguillen/
`home _upf/Publications_files/aiaa200 l .pdf.
`De Gaudenzi et al., "Performance Analysis of Turbo-Coded APSK
`Modulations over Nonlinear Satellite Channels", IEEE Transactions
`on Wireless Communications, vol. 5, No. 9, Sep. 6, 2006, 1536-
`1276, 12 pgs.
`De Gaudenzi et al., "Turbo-Coded APSK Modulations Design for
`Satellite Broadband Communications", International Journal of
`Satellite Communications and Networking, vol. 24, No. 4, Jul. 1,
`2006, pp. 261-281.
`Fabregas et al., "Bit-Interleaved Coded Modulation", Foundations
`and Trends® in Communications and Information Theory: vol. 5:
`No. 1-2, pp. 1-153. http://dx.doi.org/10.1561/0100000019 , Pub(cid:173)
`lished: Nov. 30, 2008.
`Fabregas et al., "Bit-Interleaved Coded Modulation with Shaping",
`IEEE Information Theory Workshop (ITW), 2010, Conference:
`Aug. 30-Sep. 3, 2010, 6 pgs.
`Fabregas et al., "Error Probability of Bit-Interleaved Coded Modu(cid:173)
`lation using the Gaussian Approximation", 2004 Conference on
`Information Sciences and Systems, Princeton University, Mar. 17-19,
`2004, 7 pgs.
`Fabregas et al., "Impact of Signal Constellation Expansion on the
`Achievable Diversity of Pragmatic Bit-interleaved Space-Time Codes",
`IEEE Transactions on Wireless Communications, vol. 5, Issue 8,
`Aug. 2006, 15 pgs.
`Farid, et al., "Design of Non-Uniform Capacity-Approaching Sig(cid:173)
`naling for Optical Wireless Intensity Channels", IEEE International
`Symposium on Information Theory, 2008, Conference: Jul. 6-11,
`2008, pp. 2327-2331.
`Farid et al., "Channel Capacity and Non-Uniform Signalling for
`Free-Space Optical Intensity Channels", IEEE Journal on Selected
`Areas in Communications, vol. 27, No. 9, Dec. 2009, 12 pgs.
`Forney, et al., "Multidimensional Constellations-Part II: Voronoi
`Constellations", IEEE Journal on Selected Areas in Communica(cid:173)
`tions, Aug. 1989, vol. 7, No. 6, pp. 941-958.
`Forney, Jr. et al., "Efficient Modulation for Band-Limited Chan(cid:173)
`nels", IEEE Journal on Selected Areas in Communications, Sep.
`1984, vol. SAC-2, No. 5, pp. 632-647.
`Forney, Jr. et al., "Multidimensional Constellations-Part I: Intro(cid:173)
`duction, Figures of Merit, and Generalized Cross Constellations",
`IEEE Journal on Selected Areas in Communication, Aug. 1989, vol.
`7, No. 6, pp. 877-892.
`Foschini et al., "Optimization of Two-Dimensional Signal Constel(cid:173)
`lations in the Presence of Gaussian Noise", IEEE Transactions on
`Communications, Jan. 1974, vol. Com-22, No. 1, pp. 28-38.
`Fragouli et al., "Serially Concatenated Coding for Broadcasting
`S-UMTS Applications", IEEE 7th Int. Symp. on Spread-Spectrum
`Tech. & Appl., Prague, Czech Republic, Sep. 2-5, 2002, pp.
`697-701.
`Wang et al, "Shaping Gain for AWGN Channel by Non-Uniform
`Constellation in LDPC-Coded System", 11th IEEE Singapore Inter(cid:173)
`national Conference on Communication Systems, 2008, ICCS 2008,
`Conference: Nov. 19-21, 2008, pp. 1302-1306.
`Wu et al., "Non-uniform and Large Distance Constellation Design
`for Hierarchical Modulation", 2010 IEEE International Conference
`on Communications (ICC), Conference: May 23-27, 2010, 5 pgs.
`Xie et al., "Bit-Interleaved LDPC-Coded Modulation with Iterative
`Demapping and Decoding", IEEE 69th Vehicular Technology Con(cid:173)
`ference, Barcelona, Spain, Date of Conference Apr. 26-29, 2009, 5
`pgs.
`Xie et al., "On the Channel Capacity and Iterative Demapping of
`Generalized 4PAM over AWGN Channel", 11th IEEE Singapore
`International Conference on Communication Systems, 2008. ICCS
`2008. Dec. 2008, pp. 860-863.
`Yang et al., "A Novel BICM-ID System Approaching Shannon(cid:173)
`Limit at High Spectrum Efficiency", IEICE Trans. Commun., vol.
`E94-B, No. 3, Mar. 2011, pp. 793-795.
`Yuan et al., "Robust Hierarchical Broadcasting for AWGN and Flat
`Rayleigh Fading Channels using Multilevel Codes", Proceedings of
`
`3
`
`

`

`US 10,693,700 Bl
`Page 4
`
`(56)
`
`References Cited
`
`OTHER PUBLICATIONS
`
`IEEE Fifth International Symposium on Communication Theory &
`Applications, ISCTA'99, Ambleside, UK, 1999, S. 3 pgs.
`Zesong et al., "Shaping Gain by Non-Uniform QAM Constellation
`with Binary Turbo Coded Modulation", Personal, Indoor and Mobile
`Radio Communications, IEEE, vol. 2. pp. 1863-1867, Sep. 7, 2003.
`Zhang et al., "A New Constellation Shaping Method and Its
`Performance Evaluation in BICM-ID", IEEE 70th Vehicular Tech(cid:173)
`nology Conference Fall (VTC 2009-Fall). Conference: Sep. 20-23,
`2009, 5 pgs.
`Zheng et al., "Shaping Gain of LDPC Coded-QAM Transmitting
`Systems with Non-Uniform Constellation", IEEE, pp. 6-9, 2007.
`Fragouli et al., "Turbo Codes with Non-Uniform Constellations",
`IEEE Int. Conf. Commun., Jun. 2001, pp. 70-73.
`Kschischang et al., "Optimal Nonuniform Signaling for Gaussian
`Channels", IEEE, pp. 913-929, 1993.
`Goff et al., "Channel capacity of bit-interleaved coded modulation
`schemes using 8-ary signal constellations", Electronics Letters, vol.
`38, Issue 4, Feb. 14, 2002, pp. 187-188.
`Goff et al., "Signal Constellations for Bit-Interleaved Coded Modu(cid:173)
`lation", IEEE Transactions on Information Theory, vol. 49, Issue 1,
`Jan. 2003, pp. 307-313.
`Hamkins et al., "Asymptotically Dense Spherical Codes-Part I:
`Wrapped Spherical Codes", IEEE Transactions on Information
`Theory, Nov. 1997, vol. 43, No. 6, pp. 1774-1785.
`Hamkins et al., "Asymptotically Dense Spherical Codes-Part II:
`Laminated Spherical Codes", IEEE Transactions on Information
`Theory, Nov. 1997, vol. 43, No. 6, pp. 1786-1798.
`Hossain et al., "BICM Transmission using Non-Uniform QAM
`Constellations: Performance Analysis and Design", IEEE Interna(cid:173)
`tional Conference on Communications (ICC), 2010, Conference:
`May 23-27, 2010, 7 pgs.
`Hossain et al., "Constellation and Interleaver Design for BICM",
`Global Telecommunications Conference (GLOBECOM 2011 ), 2011
`IEEE, Conference: Dec. 5-9, 2011, 7 pgs.
`Hossain et al., "Towards Fully Optimized BICM Transceivers",
`Arxiv.org, Dec. 8, 2010, 31 pgs.
`Isaka et al., "Error performance analysis of multilevel coded asym(cid:173)
`metric 8-PSK modulation with multistage decoding and unequal
`error protection", 1998 IEEE International Symposium on Cam(cid:173)
`bridge, MA, USA Aug. 16-21, Aug. 16, 1998 p. 210.
`Jo et al., "An Advanced Hierarchical Modulation with Rotated
`Constellation", The 12th International Conference on Advanced
`Communication Technology (ICACT), 2010, Conference: Feb. 7-10,
`2010, pp. 515-518.
`Kayhan et al., "Joint Signal-Labeling Optimization for Pragmatic
`Capacity under Peak-Power Constraint", Global Telecommunica(cid:173)
`tions Conference (GLOBECOM 2010), 2010 IEEE, Conference
`Dec. 6-10, 2010, Miami, FL, USA, 6 pgs.
`Khandani et al., "Application of Shaping Technique to Multi-level
`Turbo-coded Modulation", 2002, 5 pgs.
`Khandani et al., "Application of Shaping Technique to Multi-level
`Turbo-coded Modulation", University of Waterloo, Department of
`Electrical and Computer Engineering, Waterloo, Ontario, Canada,
`Technical Report UW-E&CE#02-07, May 30, 2002, 24 pgs.
`Khoo et al., "Bit Interleaved Coded Modulation with Iterative
`Decoding Using Constellation Shaping", IEEE Transactions on
`Communications, Oct. 2006, 5 pgs.
`Lee et al., "Hierarchical Constellation Based Adaptive Relay Scheme
`in Multi-Hop Networks", IEEE Communication Letters, vol. 11,
`No. 3, Mar. 2007, pp. 225-227.
`Liolis et al., "Amplitude Phase Shift Keying Constellation Design
`and its Applications to Satellite Digital Video Broadcasting", Retrieved
`from: http://www.dtic.upf.edu/-aguillen/home _upf/Publications_
`files/apsk_chapter.pdf, Jun. 1, 2009, 28 pgs.
`Liu et al., "APSK Constellation with Gray Mapping", IEEE Com(cid:173)
`munications Letters, vol. 15, Issue 12, Dec. 2011, pp. 127-1273,
`Date of Publication Oct. 31, 2011.
`
`Loghin et al., "Non-Uniform Constellations for ATSC 3.0", IEEE
`Transactions on Broadcasting, vol. 62, No. 1, Mar. 2016, pp.
`197-203.
`Long Duan et al., "Approaching the AWGN Channel Capacity
`without Active Shaping", Proceedings of the International Sympo(cid:173)
`sium on Information Theory, pp. 374, 1997.
`Ma et al., "Coded Modulation Using Superimposed Binary Codes",
`IEEE Transactions of Information Theory, vol. 50, No. 12, Dec.
`2004, pp. 3331-3343.
`Makowski, "On the Optimality of Uniform Pulse Amplitude Modu(cid:173)
`lation", IEEE Transactions on information Theory, Dec. 2006, vol.
`52, No. 12, pp. 5546-5549.
`Martinez et al., "Bit-Interleaved Coded Modulation in the Wideband
`Regime", Retrieved from: https://arxiv.org/pdf/0710 .4046 .pdf, Draft,
`Oct. 22, 2007, 23 pgs.
`Martinez et al., "Coding and Modulation for the Additive Expo(cid:173)
`nential Noise Channel", IEEE International Symposium on Infor(cid:173)
`mation Theory, 2008. ISIT 2008, Conference: Jul. 6-11, 2008, 5 pgs.
`Meric et al., "Generic Approach for Hierarchical Modulation Per(cid:173)
`formance Analysis: Application to DVB-SH and DVB-S2'', Retrieved
`from: https://arxiv.org/abs/1103 .1742, Submitted Mar. 9, 2011, Draft
`Mar. 10, 2011, 17 pgs.
`Mheich et al., "Constellation Shaping for Broadcast Channels in
`Practical Situations", 19th European Signal Processing Conference
`(EUSIPCO 2011), Barcelona, Spain, Aug. 29-Sep. 2, 2011, pp.
`96-100.
`Milovanovic et al., "Simple Optimization Method of One(cid:173)
`Dimensional M-PAM Constellations for the AWGN Channels", 4th
`International Conference on Telecommunications in Modern Satel(cid:173)
`lite, Cable and Broadcasting Services, Oct. 13-15, 1999, 4 pgs.
`Moore et al., "Pairwise optimization of modulation constellations
`for non-uniform sources Modulation", Can. J. Elect. Computer Eng.
`vol. 34, pp. 167-177, 2009.
`Muhammad, Nabil Sven, "Coding and Modulation for Spectral
`Efficient Transmission", University of Stuttgart. Aug. 25, 2010
`(http://dx.doi.org/ 10 .18419/opus-267 6).
`Muhammad et al., "Joint Optimization of Signal Constellation and
`Bit Labeling for Bit-Interleaved Coded Modulation with Iterative
`Decoding", IEEE Communications Letters, Sep. 2005, vol. 9, No.
`9, pp. 775-777.
`Ngo et al., "A New Iterative Decoder for Turbo Codes on the
`Nonlinear Channel with Non-uniform 16QAM Modulation", Turbo
`Coding 2006, Apr. 3-7, 2006, Munich, 7 pgs.
`Ngo et al., "Performance of non-uniform 16QAM modulation over
`linear and nonlinear channels", Electronics Letters, vol. 42, Issue 9,
`Apr. 27, 2006, 2 pgs.
`Otnes et al., "Adaptive Data Rate using ARQ and Nonuniform
`Constellations", Vehicular Technology Conference pp. 1211-1215,
`2001.
`Raphaeli et al., "An Improved Pragmatic Turbo Encoding Scheme
`for High Spectral Efficiency Using Constellation Shaping", IEEE
`International Conference on Communications, ICC 2003, Confer(cid:173)
`ence May 11-15, 2003, Anchorage, AK, USA, 6 pgs.
`Raphaeli et al., "Constellation Shaping for Pragmatic Turbo-Coded
`Modulation with High Spectral Efficiency", IEEE Transactions on
`Communications, Mar. 2004, vol. 52, No. 3, pp. 341-345.
`Ruotsalainen et al., "On the construction of the higher dimensional
`constellations", ISIT 2000, Lausanne, Switzerland, Jun. 30-Jul. 5,
`2002, p. 490.
`Sawaya, "Performance optimization for capacity-approaching chan(cid:173)
`nel coding schemes", XP055604929 Ph.D. report, ENST Paris,
`France Mar. 31, 2002.
`Sawaya et al., "Multilevel coded modulations based on asymmetric
`constellations", Proceedings of the 2001 IEEE International Sym(cid:173)
`posium on Information Theory New York, NY: IEEE, US, Jun. 24,
`2001 pp. 281-281.
`Schreckenach et al., "Signal Shaping Using Non-Unique Symbol
`Mappings", Proceedings of the 43rdAnnual Allerton Conference on
`Communication, Control and Computing, Sep. 2005, 10 pgs.
`Shannon et al., "A Mathematical Theory of Communication", The
`Bell System Technical Journal, vol. 27, Jul. Oct. 1948, 379-423,
`623-656.
`
`4
`
`

`

`US 10,693,700 Bl
`Page 5
`
`(56)
`
`References Cited
`
`OTHER PUBLICATIONS
`
`Shen et al., "On the Design of Modern Multilevel Coded Modula(cid:173)
`tion for Unequal Error Protection", IEEE International Conference
`on Communications, 2008. ICC '08., Conference: May 19-23, 2008,
`6 pgs.
`Sommer et al., "Signal Shaping by Non-Uniform QAM for AWGN
`Channels and Applications Using Turbo Coding", ITG Conference
`on Source and Channel Coding, Jan. 2000, pp. 81-86.
`Souto et al., "Iterative Detection and Channel Estimation for
`WCDMA Systems Employing Non-Uniform QAM Constellations",
`IST Mobile and Wireless Communications Summit, Jun. 2006, 6
`pgs.
`Souto et al., "Iterative Turbo Multipath Interference Cancellation
`for WCDMA System with Non-Uniform Modulation", IEEE, 2005,
`5 pgs.
`Souto et al., "Non-Uniform Constellations for Broadcasting and
`Multicasting Services in WCDMA Systems", Retrieved from: http://
`www.eurasip.org/Proceedings/Ext/IST05/papers/424.pdf, Jun. 19-23,
`2005, 5 pgs.
`Stierstorfer et al., "Asymptotically Optimal Mappings for BICM
`with M-PAM and M ~ ~2QAM", Retrieved from: http://www.lit.int.
`de/papers/elet_set_part_cst_2009.pdf, Draft, Jul. 13, 2009, 6 pgs.
`Stierstorfer et al., "Optimizing BICM with convolutional codes for
`transmission over the AWGN channel", Int. Zurich Seminar on
`Communications (IZS), Mar. 3-5, 2010, 5 pgs.
`Sun et al., "Approaching Capacity by Equiprobable Signaling on the
`Gaussian Channel", IEEE Transactions on Information Theory, Sep.
`1993, vol. 39, No. 5, pp. 1714-1716.
`
`Theodorakopoulos et al., "Comparison of Uniform and Non(cid:173)
`uniform M-QAM Schemes for Mobile Video Applications", Pro(cid:173)
`ceedings of the 2005 Systems Communications, 2005, Conference:
`Aug. 14-17, 2005, 6 pgs.
`Tran et al., "Signal Mappings of 8-Ary Constellations for BI CM-ID
`Systems Over a Rayleigh Fading Channel", Canadian Conference
`on Electrical and Computer Engineering, 2004, pp. 1809-1813.
`Ungerboeck et al., "Channel Coding with Multilevel/Phase Sig(cid:173)
`nals", IEEE Transactions on Information Theory, Jan. 1982, vol.
`IT-28, No. 1, pp. 55-67.
`Valles et al., "Constellation Design for Improved Iterative LDPC
`Decoding", Aerospace Conference, 2008 IEEE, Conference: Mar.
`1-8, 2008, Big Sky, MT, USA, DOI: 10.1109/AERO.2008.4526371,
`7 pgs.
`Vitthaladevuni et al., "A Recursive Algorithm for the Exact BER
`Computation of Generalized Hierarchical QAM Constellations",
`IEEE Transactions on Information Theory, vol. 49, No. 1, Jan. 14,
`2003, pp. 297-307.
`Von Deetzen et al., "On Code Design for Unequal Error Protection
`Multilevel Coding", 7th International ITG Conference on Source
`and Channel Coding (SCC), 2008, Conference: Jan. 14-16, 2008, 4
`pgs.
`De Gaudenzi et al., "A New Coded Digital Modulation Scheme for
`Nonlinear Satellite Channels, with High Power-and Spectral(cid:173)
`Efficiency", European Space Agency, STR-242, July 2001, 60 pgs.
`De Gaudenzi et al., "Analysis and Design of an All-Digital Demodu(cid:173)
`lator for Trellis Coded 16-QAM Transmittion over a Nonlinear
`Satellite Channel", IEEE Transactions on Communications, vol. 43,
`Nos. 2, 3, 4, Feb., Mar., Apr. 1995, pp. 659-668.
`
`* cited by examiner
`
`5
`
`

`

`16
`
`FIG. 1
`
`15
`
`10
`
`14
`
`0
`N
`0
`N
`
`18
`
`Receiver
`
`Channel
`
`Transmitter
`
`Sink
`
`Source
`
`12
`
`e •
`
`•
`00
`
`6
`
`

`

`~
`.i;...
`
`0 ....
`N
`.....
`rJJ =- ('D
`
`('D
`
`0
`N
`0
`N
`
`bits
`Received
`
`16
`
`14
`
`Decoder
`
`Demapper
`
`Demodulator
`
`Channel
`
`34
`
`FIG. 3
`
`32
`
`24
`
`FIG. 2
`
`22
`
`30
`
`20
`
`~
`N
`
`~ = ?
`
`~
`
`Channel
`
`Modulator
`
`Mapper
`
`Coder
`
`bits
`User
`
`e •
`
`•
`00
`
`7
`
`

`

`0
`N
`0
`N
`
`e •
`
`•
`00
`
`Hits
`
`,.......---......., Received
`
`!
`j
`
`Decoder
`
`:
`
`!
`1 B
`1
`r-----------··----.. ---. -----·--.· .. ---·.,
`
`!
`
`~ Demapper
`•
`Y ,..............---...,
`
`th~:n~I I
`,
`------~ X ~----
`
`,
`
`Mapper
`
`r-----
`
`Parallel Decoding Capacity
`
`11'-----R~e~c~e_i_v_e~r~~--~-:➔C:::O~:
`
`L------------------------~
`
`I
`
`/ 42
`
`1Y
`
`syU:~_~_ls __ ~ .. _-___ -_c ____ -~----~-~'.- ____ -___ ~_ ! ~1---"""'--____ c_-~_:_:_i_·~_:_----..,..,1!
`
`iB ----~ X
`I---------·-----·-· -----· ----·-1
`
`Joint Decoding Capacity
`
`40
`
`L-----------------------------------~
`
`FIG. 4a
`
`1. .. --~~,.,.J
`
`....................................
`
`............. ______
`
`!
`j
`
`:
`
`~ Coder
`User
`
`I
`
`8
`
`

`

`U.S. Patent
`
`Jun.23,2020
`
`Sheet 4 of 43
`
`US 10,693,700 Bl
`
`Input M; TJ
`
`/50
`
`Invalid
`Parameters
`
`51
`
`55
`
`Optimize M~Ary
`Constellation for
`SNRin
`
`FIG~ 5
`
`Yes
`
`_____________ 59
`
`Output Constellation
`
`9
`
`

`

`FIG. 6b
`
`'· )
`(h.
`
`40
`-$
`o.____. _ _...._ .......... _ _.__ ......... _.._ ___ .____._ _ __.
`
`SNR. in dB
`15 20
`
`1(}
`
`5
`
`C)
`
`35
`
`30
`
`25
`
`FIG. 6a
`
`40
`
`35
`
`25 so
`
`-s
`Qt---..J----~---'----------..,__--.____. _ __,
`
`)
`.,
`(a"
`SNRindB
`
`15 20
`
`10
`
`S
`
`0
`
`0
`N
`0
`N
`
`e •
`
`•
`00
`
`. .✓
`
`64
`
`---PAM.32
`-PAM 16
`· · · • · --PAM S
`PAM4
`--PAM2
`
`-
`
`-
`
`1
`
`5
`
`6
`
`/
`
`66
`
`62
`
`--PAM32
`-PAfvl 16
`· · ., .. PAfvl 8
`-~ PAM 4
`· ·---
`--PAfv12
`
`-
`
`-
`
`1
`
`2
`
`5
`
`60
`
`10
`
`

`

`Capadty
`
`FIG. 7
`
`0
`N
`0
`N
`
`e •
`
`•
`00
`
`-h -Joint Capacity
`
`,,,,,,,,,,,,,,,,,,,,,,,,,,,_ ParaHel Decoding Capacity
`
`C)
`ro
`
`er z
`0 -0..
`
`(f)
`
`5
`0 ....... """"'-_._ _ ___... __ .,___ _ _.._ ____ .,__ _ _,_ _ _. __ ...._ _ __,
`
`4,5
`
`4
`
`3,5
`
`3
`
`2.5
`
`2
`
`1.5
`
`1
`
`0.5
`
`0
`
`11
`
`

`

`FIG. 8a
`
`,,,,, optin1ized consteHations
`
`·+·
`
`---classic consteHatlons
`
`0
`N
`0
`N
`
`e •
`
`•
`00
`
`5
`
`4.5
`
`4
`
`3.5
`
`3
`
`2.5
`
`in bits
`
`Ca
`2
`
`1.5
`
`1
`
`.,, 'I'"~- '
`
`,,I'//•
`
`., •• ,,_
`
`/
`
`/.
`
`'
`' J
`
`/
`
`0.5
`
`1
`
`2
`
`12
`
`

`

`FIG. 8b
`
`,,,,, optimized constellations
`
`·+,,
`
`,,,,,,,,,,,,,,,,,,,,,,,,,, classic constellations
`
`0
`N
`0
`N
`
`e •
`
`•
`00
`
`5
`
`4,5
`
`4
`
`3,5
`
`3
`
`2.5
`
`2
`
`1.5
`
`1
`
`Capacity in bits
`
`I
`
`0
`
`0
`
`(f) 0.5
`0:: z
`0)
`ro
`0...
`
`1
`
`1.5
`
`13
`
`

`

`20
`~---------------_.....,
`
`19,5
`
`19
`
`SMR (dB)
`18
`18.5
`
`17.5
`
`17
`
`16.5
`
`10-5
`
`FIG. 9
`
`90
`
`0
`N
`0
`N
`
`---------{;--------, PAtv132, k= 16384
`---------(>--------PID Opt PAM32, k=16384
`---------El--------P AM32, k=4096
`······<)········· PlD Opt PAM32, k=4096
`..... n ..... P Ati/t32 vii/ iter. k=4096
`.... fJ ..... PID Opt PAM32 \NI lter, k:=4096
`
`l !~~:~
`
`-
`
`•. I
`
`-~. -
`
`•;
`
`... ~ . ..
`
`-4
`
`10
`
`LI-
`LU
`r.c
`
`14
`
`

`

`0
`N
`0
`N
`
`e •
`
`•
`00
`
`FIG. 1 Oa
`
`Hi
`
`'l.-4
`
`12
`
`0.6
`
`0.2
`
`0
`
`-1.,,-; ____ __._ ___________________ ,__ ___ __. ____ _.... ____ _,_ ________ _
`
`··-~~--~•-•=••·· ···-~·-·~·-~, ...
`
`<
`
`.
`
`'
`
`.
`
`'
`
`.
`
`,. ., .. ~ ~ ~ ' , . " ' .. ~ .,. ,, ~ ~ .,. ~ ... ~-· .. '
`
`.
`
`.
`
`.,,_ ., .. ,,
`
`'
`
`' ••
`
`• • • •• ~ ••• ~ ••• -
`
`• • • •
`
`~ •••••• -
`
`• .......... -·• • • ... • • .
`
`... } · ... = •• ~ • • • •
`
`i
`
`1,5,-----------,,...----.....,.....----...------,------,-----------,------.-----
`
`PAM4 optimlz<?.d for joint i:ap.adty
`
`15
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun.23,2020
`Jun. 23, 2020
`
`Sheet 11 of 43
`Sheet 11 of 43
`
`US 10,693,700 Bl
`US 10,693,700 B1
`
`I..O
`0 ,....,
`
`2‘
`
`‘
`
`‘+
`
`4
`
`‘,
`
`4
`
`5
`
`?
`
`‘
`
`’
`
`8
`
`4
`
`‘
`
`‘2’4
`
`‘
`
`‘s
`
`4>
`
`+
`
`aieees
`
`-.?" ·t
`
`Cl.I
`~
`i:'ey
`l.>
`~
`oOrhe
`:[
`,.....
`J?,
`'\;I
`
`304pezuundepy%
`
`a., :~ g-
`
`'"f
`os;;
`;~
`td
`0.,,
`
`· , . •.• ,, " , " "
`
`-
`
`· • , , . " , . " " , . , ,. , ·!f , ,, "
`
`, " " " .. ,• "
`
`, ,. ,, "
`
`, , " , , , "
`
`. · , ,. "
`
`ip
`—_
`t.s'.)
`
`we
`~ ...... ~
`
`ey
`lt)
`m
`ci
`
`0
`
`'i ci
`I
`
`7
`
`16
`
`
`
`
`
`RRRRARERNAIRRRRARETEERANMERRIERREMENmRMMIREEEEMeRENMMNETHMRNReHEN
`
`, 'I\'-; Cl
`
`_c
`0
`'T""'"
`•
`
`GO“SD
`(!) -LL
`
`to
`'O
`,5
`tt': z
`
`(.t)
`
`u,")
`......
`
`0 .,..
`OL
`
`eee
`4~~
`
`
`
`
`
`
`
`Sr,
`-~
`aest:
`. l
`,._,,,,.,.
`
`16
`
`
`
`
`
`
`

`

`0
`N
`0
`N
`
`e •
`
`•
`r:J).
`
`•
`
`,; ~.
`
`j> _.
`
`'>
`
`,; A
`
`'> _.
`
`,>.
`
`• A
`
`,
`
`,
`
`•
`
`.
`
`•
`
`,,_ ~. t
`
`FIG. 10c
`
`1.4
`I
`
`1.:2
`I
`
`i.16
`r
`
`0.2
`
`',. -,
`
`.,.,
`
`; ~ '> ~ ,; ,-
`
`•
`
`.
`
`• • •
`
`0
`
`15......--------.-----......... -----........ --------,.-----....... ------,-------,....------,------,.,......-----
`
`PAM4 oplkr1ized for prnalleI deco<lirg r,ap.1crty
`
`17
`
`

`

`0
`N
`0
`N
`
`e •
`
`•
`00
`
`U.S. Patent
`
`Jun. 23, 2020
`
`Sheet 13 of 43
`
`US 10,693,700 B1
`
`FIG. 1 Od
`
`15
`
`10
`
`5
`
`0
`
`POL“Ola
`
`aLOya3 SB
`
`&=c
`
`as
`
`ay
`
`CeAreRMeeweeetaweanWeeAeReeaneeeeetereeeeeng’‘.”‘‘®*+‘+*,‘*‘4,*44‘+.¥‘‘¥44‘’y>«4‘+<
`
`»©x++‘a-“‘4.¥*‘‘¥«¥®
`
`NeeewPRNeReRemANR