Distributed source coding - Revision history

GreenC bot: Move 1 url. Wayback Medic 2.5 per WP:URLREQ#ieee.org pass 2

2024-09-04T17:14:37Z

Move 1 url. Wayback Medic 2.5 per WP:URLREQ#ieee.org pass 2

← Previous revision		Revision as of 17:14, 4 September 2024
Line 66:		Line 66:
	The basic framework of syndrome based DSC is that, for each source, its input space is partitioned into several cosets according to the particular channel coding method used. Every input of each source gets an output indicating which coset the input belongs to, and the joint decoder can decode all inputs by received coset indices and dependence between sources. The design of channel codes should consider the correlation between input sources.		The basic framework of syndrome based DSC is that, for each source, its input space is partitioned into several cosets according to the particular channel coding method used. Every input of each source gets an output indicating which coset the input belongs to, and the joint decoder can decode all inputs by received coset indices and dependence between sources. The design of channel codes should consider the correlation between input sources.

	A group of codes can be used to generate coset partitions,<ref>[https://ieeexplore.ieee.org/Xplore/login.jsp?url=%2Fxpls%2Ffreeabs_all.jsp%3Farnumber%3D21245&authDecision=-203 "Coset codes. I. Introduction and geometrical classification" by G. D. Forney]</ref> such as trellis codes and lattice codes. Pradhan and Ramchandran designed rules for construction of sub-codes for each source, and presented result of trellis-based coset constructions in DSC, which is based on [[convolution code]] and set-partitioning rules as in [[Trellis modulation]], as well as lattice code based DSC.<ref name=discus/><ref name=discus2/> After this, embedded trellis code was proposed for asymmetric coding as an improvement over their results.<ref>[https://ieeexplore.ieee.org/~~xpls~~/~~freeabs_all~~.jsp?~~arnumber~~=~~917167~~ "Design of trellis codes for source coding with side information at the decoder" by X. Wang and M. Orchard]</ref>		A group of codes can be used to generate coset partitions,<ref>[https://ieeexplore.ieee.org/Xplore/login.jsp?url=%2Fxpls%2Ffreeabs_all.jsp%3Farnumber%3D21245&authDecision=-203 "Coset codes. I. Introduction and geometrical classification" by G. D. Forney]</ref> such as trellis codes and lattice codes. Pradhan and Ramchandran designed rules for construction of sub-codes for each source, and presented result of trellis-based coset constructions in DSC, which is based on [[convolution code]] and set-partitioning rules as in [[Trellis modulation]], as well as lattice code based DSC.<ref name=discus/><ref name=discus2/> After this, embedded trellis code was proposed for asymmetric coding as an improvement over their results.<ref>[https://ieeexplore.ieee.org/Xplore/login.jsp?url=%2Fxpls%2Ffreeabs_all.jsp%3Farnumber%3D917167&authDecision=-203 "Design of trellis codes for source coding with side information at the decoder" by X. Wang and M. Orchard]</ref>

	After DISCUS system was proposed, more sophisticated channel codes have been adapted to the DSC system, such as [[Turbo Code]], [[LDPC]] Code and Iterative Channel Code. The encoders of these codes are usually simple and easy to implement, while the decoders have much higher computational complexity and are able to get good performance by utilizing source statistics. With sophisticated channel codes which have performance approaching the capacity of the correlation channel, corresponding DSC system can approach the Slepian–Wolf bound.		After DISCUS system was proposed, more sophisticated channel codes have been adapted to the DSC system, such as [[Turbo Code]], [[LDPC]] Code and Iterative Channel Code. The encoders of these codes are usually simple and easy to implement, while the decoders have much higher computational complexity and are able to get good performance by utilizing source statistics. With sophisticated channel codes which have performance approaching the capacity of the correlation channel, corresponding DSC system can approach the Slepian–Wolf bound.

GreenC bot: Move 22 urls. Wayback Medic 2.5 per WP:URLREQ#ieee.org

2024-07-31T03:27:51Z

Move 22 urls. Wayback Medic 2.5 per WP:URLREQ#ieee.org

Show changes

InternetArchiveBot: Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5

2024-02-04T05:48:26Z

Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5

← Previous revision		Revision as of 05:48, 4 February 2024
Line 116:		Line 116:

	===Large scale distributed quantization===		===Large scale distributed quantization===
	Unfortunately, the above approaches do not scale (in design or operational complexity requirements) to sensor networks of large sizes, a scenario where distributed compression is most helpful. If there are N sources transmitting at R bits each (with some distributed coding scheme), the number of possible reconstructions scales <math> 2^{NR}</math>. Even for moderate values of N and R (say N=10, R = 2), prior design schemes become impractical. Recently, an approach,<ref>[http://www.scl.ece.ucsb.edu/pubs/pubs_D/d10_4.pdf "Towards large scale distributed source coding" by S. Ramaswamy, K. Viswanatha, A. Saxena and K. Rose]</ref> using ideas borrowed from Fusion Coding of Correlated Sources, has been proposed where design and operational complexity are traded against decoder performance. This has allowed distributed quantizer design for network sizes reaching 60 sources, with substantial gains over traditional approaches.		Unfortunately, the above approaches do not scale (in design or operational complexity requirements) to sensor networks of large sizes, a scenario where distributed compression is most helpful. If there are N sources transmitting at R bits each (with some distributed coding scheme), the number of possible reconstructions scales <math> 2^{NR}</math>. Even for moderate values of N and R (say N=10, R = 2), prior design schemes become impractical. Recently, an approach,<ref>{{Cite web \|url=http://www.scl.ece.ucsb.edu/pubs/pubs_D/d10_4.pdf \|title="Towards large scale distributed source coding" by S. Ramaswamy, K. Viswanatha, A. Saxena and K. Rose \|access-date=2011-01-19 \|archive-date=2011-04-01 \|archive-url=https://web.archive.org/web/20110401145514/http://www.scl.ece.ucsb.edu/pubs/pubs_D/d10_4.pdf \|url-status=dead }}</ref> using ideas borrowed from Fusion Coding of Correlated Sources, has been proposed where design and operational complexity are traded against decoder performance. This has allowed distributed quantizer design for network sizes reaching 60 sources, with substantial gains over traditional approaches.

	The central idea is the presence of a bit-subset selector which maintains a certain subset of the received (NR bits, in the above example) bits for each source. Let <math> \mathcal{B}</math> be the set of all subsets of the NR bits i.e.		The central idea is the presence of a bit-subset selector which maintains a certain subset of the received (NR bits, in the above example) bits for each source. Let <math> \mathcal{B}</math> be the set of all subsets of the NR bits i.e.

Cornmazes at 21:52, 24 August 2023

2023-08-24T21:52:17Z

← Previous revision		Revision as of 21:52, 24 August 2023
Line 1:		Line 1:
			{{Short description\|Problem in information theory and communication}}
	{{Information theory}}		{{Information theory}}
	'''Distributed source coding''' ('''DSC''') is an important problem in [[information theory]] and [[communication]]. DSC problems regard the compression of multiple correlated information sources that do not communicate with each other.<ref>[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1328091 "Distributed source coding for sensor networks" by Z. Xiong, A.D. Liveris, and S. Cheng]</ref> By modeling the correlation between multiple sources at the decoder side together with [[channel code]]s, DSC is able to shift the computational complexity from encoder side to decoder side, therefore provide appropriate frameworks for applications with complexity-constrained sender, such as [[sensor networks]] and video/multimedia compression (see [[distributed video coding]]<ref>[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=1657820&isnumber=34703 "Distributed video coding in wireless sensor networks" by Puri, R. Majumdar, A. Ishwar, P. Ramchandran, K. ]</ref>). One of the main properties of distributed source coding is that the computational burden in encoders is shifted to the joint decoder.		'''Distributed source coding''' ('''DSC''') is an important problem in [[information theory]] and [[communication]]. DSC problems regard the compression of multiple correlated information sources that do not communicate with each other.<ref>[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1328091 "Distributed source coding for sensor networks" by Z. Xiong, A.D. Liveris, and S. Cheng]</ref> By modeling the correlation between multiple sources at the decoder side together with [[channel code]]s, DSC is able to shift the computational complexity from encoder side to decoder side, therefore provide appropriate frameworks for applications with complexity-constrained sender, such as [[sensor networks]] and video/multimedia compression (see [[distributed video coding]]<ref>[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=1657820&isnumber=34703 "Distributed video coding in wireless sensor networks" by Puri, R. Majumdar, A. Ishwar, P. Ramchandran, K. ]</ref>). One of the main properties of distributed source coding is that the computational burden in encoders is shifted to the joint decoder.

Physchris at 16:25, 12 October 2020

2020-10-12T16:25:33Z

← Previous revision		Revision as of 16:25, 12 October 2020
Line 42:		Line 42:
	Shortly after Slepian–Wolf theorem on lossless distributed compression was published, the extension to lossy compression with decoder side information was proposed as Wyner–Ziv theorem.<ref name=wzbound/> Similarly to lossless case, two statistically dependent i.i.d. sources <math>X</math> and <math>Y</math> are given, where <math>Y</math> is available at the decoder side but not accessible at the encoder side. Instead of lossless compression in Slepian–Wolf theorem, Wyner–Ziv theorem looked into the lossy compression case.		Shortly after Slepian–Wolf theorem on lossless distributed compression was published, the extension to lossy compression with decoder side information was proposed as Wyner–Ziv theorem.<ref name=wzbound/> Similarly to lossless case, two statistically dependent i.i.d. sources <math>X</math> and <math>Y</math> are given, where <math>Y</math> is available at the decoder side but not accessible at the encoder side. Instead of lossless compression in Slepian–Wolf theorem, Wyner–Ziv theorem looked into the lossy compression case.

	Wyner–Ziv theorem presents the achievable lower bound for the bit rate of <math>X</math> at given distortion <math>D</math>. It was found that for Gaussian memoryless sources and mean-squared error distortion, the lower bound for the bit rate of <math>X</math> remain the same no matter whether side information is available at the encoder or not.		The Wyner–Ziv theorem presents the achievable lower bound for the bit rate of <math>X</math> at given distortion <math>D</math>. It was found that for Gaussian memoryless sources and mean-squared error distortion, the lower bound for the bit rate of <math>X</math> remain the same no matter whether side information is available at the encoder or not.

	==Virtual channel==		==Virtual channel==

Bender235: /* Non-asymmetric DSC for more than two sources */Replaced arXiv PDF link with more mobile-friendly abstract link, replaced: https://arxiv.org/pdf/ → https://arxiv.org/abs/

2020-05-29T21:03:09Z

Non-asymmetric DSC for more than two sources: Replaced arXiv PDF link with more mobile-friendly abstract link, replaced: https://arxiv.org/pdf/ → https://arxiv.org/abs/

← Previous revision		Revision as of 21:03, 29 May 2020
Line 141:		Line 141:
	The syndrome approach can still be used for more than two sources. Consider <math>a</math> binary sources of length-<math>n</math> <math> \mathbf{x}_1,\mathbf{x}_2,\cdots, \mathbf{x}_a \in \{0,1\}^n </math>. Let <math> \mathbf{H}_1, \mathbf{H}_2, \cdots, \mathbf{H}_s </math> be the corresponding coding matrices of sizes <math> m_1 \times n, m_2 \times n, \cdots, m_a \times n</math>. Then the input binary sources are compressed into <math> \mathbf{s}_1 = \mathbf{H}_1 \mathbf{x}_1, \mathbf{s}_2 = \mathbf{H}_2 \mathbf{x}_2, \cdots, \mathbf{s}_a = \mathbf{H}_a \mathbf{x}_a </math> of total <math> m= m_1 + m_2 + \cdots m_a </math> bits. Apparently, two source tuples cannot be recovered at the same time if they share the same syndrome. In other words, if all source tuples of interest have different syndromes, then one can recover them losslessly.		The syndrome approach can still be used for more than two sources. Consider <math>a</math> binary sources of length-<math>n</math> <math> \mathbf{x}_1,\mathbf{x}_2,\cdots, \mathbf{x}_a \in \{0,1\}^n </math>. Let <math> \mathbf{H}_1, \mathbf{H}_2, \cdots, \mathbf{H}_s </math> be the corresponding coding matrices of sizes <math> m_1 \times n, m_2 \times n, \cdots, m_a \times n</math>. Then the input binary sources are compressed into <math> \mathbf{s}_1 = \mathbf{H}_1 \mathbf{x}_1, \mathbf{s}_2 = \mathbf{H}_2 \mathbf{x}_2, \cdots, \mathbf{s}_a = \mathbf{H}_a \mathbf{x}_a </math> of total <math> m= m_1 + m_2 + \cdots m_a </math> bits. Apparently, two source tuples cannot be recovered at the same time if they share the same syndrome. In other words, if all source tuples of interest have different syndromes, then one can recover them losslessly.

	General theoretical result does not seem to exist. However, for a restricted kind of source so-called Hamming source <ref name="HCMS">[https://arxiv.org/~~pdf~~/1001.4072 "Hamming Codes for Multiple Sources" by R. Ma and S. Cheng]</ref> that only has at most one source different from the rest and at most one bit location not all identical, practical lossless DSC is shown to exist in some cases. For the case when there are more than two sources, the number of source tuple in a Hamming source is <math>2^n (a n + 1)</math>. Therefore, a packing bound that <math>2^m \ge 2^n (a n + 1)</math> obviously has to satisfy. When the packing bound is satisfied with equality, we may call such code to be perfect (an analogous of perfect code in error correcting code).<ref name="HCMS" />		General theoretical result does not seem to exist. However, for a restricted kind of source so-called Hamming source <ref name="HCMS">[https://arxiv.org/abs/1001.4072 "Hamming Codes for Multiple Sources" by R. Ma and S. Cheng]</ref> that only has at most one source different from the rest and at most one bit location not all identical, practical lossless DSC is shown to exist in some cases. For the case when there are more than two sources, the number of source tuple in a Hamming source is <math>2^n (a n + 1)</math>. Therefore, a packing bound that <math>2^m \ge 2^n (a n + 1)</math> obviously has to satisfy. When the packing bound is satisfied with equality, we may call such code to be perfect (an analogous of perfect code in error correcting code).<ref name="HCMS" />

	A simplest set of <math> a, n, m</math> to satisfy the packing bound with equality is <math> a=3, n=5, m=9 </math>. However, it turns out that such syndrome code does not exist.<ref>[http://tulsagrad.ou.edu/samuel_cheng/papers/dcc10.pdf "The Non-existence of Length-5 Slepian–Wolf Codes of Three Sources" by S. Cheng and R. Ma] {{webarchive \|url=https://web.archive.org/web/20120425092322/http://tulsagrad.ou.edu/samuel_cheng/papers/dcc10.pdf \|date=April 25, 2012 }}</ref> The simplest (perfect) syndrome code with more than two sources have <math> n = 21 </math> and <math> m = 27 </math>. Let		A simplest set of <math> a, n, m</math> to satisfy the packing bound with equality is <math> a=3, n=5, m=9 </math>. However, it turns out that such syndrome code does not exist.<ref>[http://tulsagrad.ou.edu/samuel_cheng/papers/dcc10.pdf "The Non-existence of Length-5 Slepian–Wolf Codes of Three Sources" by S. Cheng and R. Ma] {{webarchive \|url=https://web.archive.org/web/20120425092322/http://tulsagrad.ou.edu/samuel_cheng/papers/dcc10.pdf \|date=April 25, 2012 }}</ref> The simplest (perfect) syndrome code with more than two sources have <math> n = 21 </math> and <math> m = 27 </math>. Let

BD2412: /* Non-asymmetric DSC for more than two sources */Replace "let us consider" statements per MOS:NOTED and consensus at Wikipedia talk:Manual of Style#"Let us consider" statements, replaced: Let us consider → Consider

2019-05-06T21:40:37Z

Non-asymmetric DSC for more than two sources: Replace "let us consider" statements per MOS:NOTED and consensus at Wikipedia talk:Manual of Style#"Let us consider" statements, replaced: Let us consider → Consider

← Previous revision		Revision as of 21:40, 6 May 2019
Line 139:		Line 139:

	==Non-asymmetric DSC for more than two sources==		==Non-asymmetric DSC for more than two sources==
	The syndrome approach can still be used for more than two sources. ~~Let us consider~~ <math>a</math> binary sources of length-<math>n</math> <math> \mathbf{x}_1,\mathbf{x}_2,\cdots, \mathbf{x}_a \in \{0,1\}^n </math>. Let <math> \mathbf{H}_1, \mathbf{H}_2, \cdots, \mathbf{H}_s </math> be the corresponding coding matrices of sizes <math> m_1 \times n, m_2 \times n, \cdots, m_a \times n</math>. Then the input binary sources are compressed into <math> \mathbf{s}_1 = \mathbf{H}_1 \mathbf{x}_1, \mathbf{s}_2 = \mathbf{H}_2 \mathbf{x}_2, \cdots, \mathbf{s}_a = \mathbf{H}_a \mathbf{x}_a </math> of total <math> m= m_1 + m_2 + \cdots m_a </math> bits. Apparently, two source tuples cannot be recovered at the same time if they share the same syndrome. In other words, if all source tuples of interest have different syndromes, then one can recover them losslessly.		The syndrome approach can still be used for more than two sources. Consider <math>a</math> binary sources of length-<math>n</math> <math> \mathbf{x}_1,\mathbf{x}_2,\cdots, \mathbf{x}_a \in \{0,1\}^n </math>. Let <math> \mathbf{H}_1, \mathbf{H}_2, \cdots, \mathbf{H}_s </math> be the corresponding coding matrices of sizes <math> m_1 \times n, m_2 \times n, \cdots, m_a \times n</math>. Then the input binary sources are compressed into <math> \mathbf{s}_1 = \mathbf{H}_1 \mathbf{x}_1, \mathbf{s}_2 = \mathbf{H}_2 \mathbf{x}_2, \cdots, \mathbf{s}_a = \mathbf{H}_a \mathbf{x}_a </math> of total <math> m= m_1 + m_2 + \cdots m_a </math> bits. Apparently, two source tuples cannot be recovered at the same time if they share the same syndrome. In other words, if all source tuples of interest have different syndromes, then one can recover them losslessly.

	General theoretical result does not seem to exist. However, for a restricted kind of source so-called Hamming source <ref name="HCMS">[https://arxiv.org/pdf/1001.4072 "Hamming Codes for Multiple Sources" by R. Ma and S. Cheng]</ref> that only has at most one source different from the rest and at most one bit location not all identical, practical lossless DSC is shown to exist in some cases. For the case when there are more than two sources, the number of source tuple in a Hamming source is <math>2^n (a n + 1)</math>. Therefore, a packing bound that <math>2^m \ge 2^n (a n + 1)</math> obviously has to satisfy. When the packing bound is satisfied with equality, we may call such code to be perfect (an analogous of perfect code in error correcting code).<ref name="HCMS" />		General theoretical result does not seem to exist. However, for a restricted kind of source so-called Hamming source <ref name="HCMS">[https://arxiv.org/pdf/1001.4072 "Hamming Codes for Multiple Sources" by R. Ma and S. Cheng]</ref> that only has at most one source different from the rest and at most one bit location not all identical, practical lossless DSC is shown to exist in some cases. For the case when there are more than two sources, the number of source tuple in a Hamming source is <math>2^n (a n + 1)</math>. Therefore, a packing bound that <math>2^m \ge 2^n (a n + 1)</math> obviously has to satisfy. When the packing bound is satisfied with equality, we may call such code to be perfect (an analogous of perfect code in error correcting code).<ref name="HCMS" />

Fvultier: Information theory sidebar template.

2018-12-28T12:31:45Z

Information theory sidebar template.

← Previous revision		Revision as of 12:31, 28 December 2018
Line 1:		Line 1:
			{{Information theory}}
	'''Distributed source coding''' ('''DSC''') is an important problem in [[information theory]] and [[communication]]. DSC problems regard the compression of multiple correlated information sources that do not communicate with each other.<ref>[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1328091 "Distributed source coding for sensor networks" by Z. Xiong, A.D. Liveris, and S. Cheng]</ref> By modeling the correlation between multiple sources at the decoder side together with [[channel code]]s, DSC is able to shift the computational complexity from encoder side to decoder side, therefore provide appropriate frameworks for applications with complexity-constrained sender, such as [[sensor networks]] and video/multimedia compression (see [[distributed video coding]]<ref>[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=1657820&isnumber=34703 "Distributed video coding in wireless sensor networks" by Puri, R. Majumdar, A. Ishwar, P. Ramchandran, K. ]</ref>). One of the main properties of distributed source coding is that the computational burden in encoders is shifted to the joint decoder.		'''Distributed source coding''' ('''DSC''') is an important problem in [[information theory]] and [[communication]]. DSC problems regard the compression of multiple correlated information sources that do not communicate with each other.<ref>[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1328091 "Distributed source coding for sensor networks" by Z. Xiong, A.D. Liveris, and S. Cheng]</ref> By modeling the correlation between multiple sources at the decoder side together with [[channel code]]s, DSC is able to shift the computational complexity from encoder side to decoder side, therefore provide appropriate frameworks for applications with complexity-constrained sender, such as [[sensor networks]] and video/multimedia compression (see [[distributed video coding]]<ref>[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=1657820&isnumber=34703 "Distributed video coding in wireless sensor networks" by Puri, R. Majumdar, A. Ishwar, P. Ramchandran, K. ]</ref>). One of the main properties of distributed source coding is that the computational burden in encoders is shifted to the joint decoder.

KolbertBot: Bot: HTTP→HTTPS (v481)

2018-01-26T13:40:12Z

Bot: HTTP→HTTPS (v481)

← Previous revision		Revision as of 13:40, 26 January 2018
Line 140:		Line 140:
	The syndrome approach can still be used for more than two sources. Let us consider <math>a</math> binary sources of length-<math>n</math> <math> \mathbf{x}_1,\mathbf{x}_2,\cdots, \mathbf{x}_a \in \{0,1\}^n </math>. Let <math> \mathbf{H}_1, \mathbf{H}_2, \cdots, \mathbf{H}_s </math> be the corresponding coding matrices of sizes <math> m_1 \times n, m_2 \times n, \cdots, m_a \times n</math>. Then the input binary sources are compressed into <math> \mathbf{s}_1 = \mathbf{H}_1 \mathbf{x}_1, \mathbf{s}_2 = \mathbf{H}_2 \mathbf{x}_2, \cdots, \mathbf{s}_a = \mathbf{H}_a \mathbf{x}_a </math> of total <math> m= m_1 + m_2 + \cdots m_a </math> bits. Apparently, two source tuples cannot be recovered at the same time if they share the same syndrome. In other words, if all source tuples of interest have different syndromes, then one can recover them losslessly.		The syndrome approach can still be used for more than two sources. Let us consider <math>a</math> binary sources of length-<math>n</math> <math> \mathbf{x}_1,\mathbf{x}_2,\cdots, \mathbf{x}_a \in \{0,1\}^n </math>. Let <math> \mathbf{H}_1, \mathbf{H}_2, \cdots, \mathbf{H}_s </math> be the corresponding coding matrices of sizes <math> m_1 \times n, m_2 \times n, \cdots, m_a \times n</math>. Then the input binary sources are compressed into <math> \mathbf{s}_1 = \mathbf{H}_1 \mathbf{x}_1, \mathbf{s}_2 = \mathbf{H}_2 \mathbf{x}_2, \cdots, \mathbf{s}_a = \mathbf{H}_a \mathbf{x}_a </math> of total <math> m= m_1 + m_2 + \cdots m_a </math> bits. Apparently, two source tuples cannot be recovered at the same time if they share the same syndrome. In other words, if all source tuples of interest have different syndromes, then one can recover them losslessly.

	General theoretical result does not seem to exist. However, for a restricted kind of source so-called Hamming source <ref name="HCMS">[~~http~~://arxiv.org/pdf/1001.4072 "Hamming Codes for Multiple Sources" by R. Ma and S. Cheng]</ref> that only has at most one source different from the rest and at most one bit location not all identical, practical lossless DSC is shown to exist in some cases. For the case when there are more than two sources, the number of source tuple in a Hamming source is <math>2^n (a n + 1)</math>. Therefore, a packing bound that <math>2^m \ge 2^n (a n + 1)</math> obviously has to satisfy. When the packing bound is satisfied with equality, we may call such code to be perfect (an analogous of perfect code in error correcting code).<ref name="HCMS" />		General theoretical result does not seem to exist. However, for a restricted kind of source so-called Hamming source <ref name="HCMS">[https://arxiv.org/pdf/1001.4072 "Hamming Codes for Multiple Sources" by R. Ma and S. Cheng]</ref> that only has at most one source different from the rest and at most one bit location not all identical, practical lossless DSC is shown to exist in some cases. For the case when there are more than two sources, the number of source tuple in a Hamming source is <math>2^n (a n + 1)</math>. Therefore, a packing bound that <math>2^m \ge 2^n (a n + 1)</math> obviously has to satisfy. When the packing bound is satisfied with equality, we may call such code to be perfect (an analogous of perfect code in error correcting code).<ref name="HCMS" />

	A simplest set of <math> a, n, m</math> to satisfy the packing bound with equality is <math> a=3, n=5, m=9 </math>. However, it turns out that such syndrome code does not exist.<ref>[http://tulsagrad.ou.edu/samuel_cheng/papers/dcc10.pdf "The Non-existence of Length-5 Slepian–Wolf Codes of Three Sources" by S. Cheng and R. Ma] {{webarchive \|url=https://web.archive.org/web/20120425092322/http://tulsagrad.ou.edu/samuel_cheng/papers/dcc10.pdf \|date=April 25, 2012 }}</ref> The simplest (perfect) syndrome code with more than two sources have <math> n = 21 </math> and <math> m = 27 </math>. Let		A simplest set of <math> a, n, m</math> to satisfy the packing bound with equality is <math> a=3, n=5, m=9 </math>. However, it turns out that such syndrome code does not exist.<ref>[http://tulsagrad.ou.edu/samuel_cheng/papers/dcc10.pdf "The Non-existence of Length-5 Slepian–Wolf Codes of Three Sources" by S. Cheng and R. Ma] {{webarchive \|url=https://web.archive.org/web/20120425092322/http://tulsagrad.ou.edu/samuel_cheng/papers/dcc10.pdf \|date=April 25, 2012 }}</ref> The simplest (perfect) syndrome code with more than two sources have <math> n = 21 </math> and <math> m = 27 </math>. Let

81.105.146.16: Heading formatting for asymmetric case

2017-10-03T14:50:58Z

Heading formatting for asymmetric case

← Previous revision		Revision as of 14:50, 3 October 2017
Line 86:		Line 86:
	Take the same example as in the previous '''Asymmetric DSC vs. Symmetric DSC''' part, this part presents the corresponding DSC schemes with coset codes and syndromes including asymmetric case and symmetric case. The Slepian–Wolf bound for DSC design is shown in the previous part.		Take the same example as in the previous '''Asymmetric DSC vs. Symmetric DSC''' part, this part presents the corresponding DSC schemes with coset codes and syndromes including asymmetric case and symmetric case. The Slepian–Wolf bound for DSC design is shown in the previous part.

	=====Asymmetric case ~~(<math>R_X=3</math>, <math>R_Y=7</math>)~~=====		=====Asymmetric case =====
	In ~~this~~ case, the length of an input variable <math>\mathbf{y}</math> from source <math>Y</math> is 7 bits, therefore it can be sent lossless with 7 bits independent of any other bits. Based on the knowledge that <math>\mathbf{x}</math> and <math>\mathbf{y}</math> have Hamming distance at most one, for input <math>\mathbf{x}</math> from source <math>X</math>, since the receiver already has <math>\mathbf{y}</math>, the only possible <math>\mathbf{x}</math> are those with at most 1 distance from <math>\mathbf{y}</math>. If we model the correlation between two sources as a virtual channel, which has input <math>\mathbf{x}</math> and output <math>\mathbf{y}</math>, as long as we get <math>\mathbf{y}</math>, all we need to successfully "decode" <math>\mathbf{x}</math> is "parity bits" with particular error correction ability, taking the difference between <math>\mathbf{x}</math> and <math>\mathbf{y}</math> as channel error. We can also model the problem with cosets partition. That is, we want to find a channel code, which is able to partition the space of input <math>X</math> into several cosets, where each coset has a unique syndrome associated with it. With a given coset and <math>\mathbf{y}</math>, there is only one <math>\mathbf{x}</math> that is possible to be the input given the correlation between two sources.		In the case where <math>R_X=3</math> and <math>R_Y=7</math>, the length of an input variable <math>\mathbf{y}</math> from source <math>Y</math> is 7 bits, therefore it can be sent lossless with 7 bits independent of any other bits. Based on the knowledge that <math>\mathbf{x}</math> and <math>\mathbf{y}</math> have Hamming distance at most one, for input <math>\mathbf{x}</math> from source <math>X</math>, since the receiver already has <math>\mathbf{y}</math>, the only possible <math>\mathbf{x}</math> are those with at most 1 distance from <math>\mathbf{y}</math>. If we model the correlation between two sources as a virtual channel, which has input <math>\mathbf{x}</math> and output <math>\mathbf{y}</math>, as long as we get <math>\mathbf{y}</math>, all we need to successfully "decode" <math>\mathbf{x}</math> is "parity bits" with particular error correction ability, taking the difference between <math>\mathbf{x}</math> and <math>\mathbf{y}</math> as channel error. We can also model the problem with cosets partition. That is, we want to find a channel code, which is able to partition the space of input <math>X</math> into several cosets, where each coset has a unique syndrome associated with it. With a given coset and <math>\mathbf{y}</math>, there is only one <math>\mathbf{x}</math> that is possible to be the input given the correlation between two sources.

	In this example, we can use the <math>(7,4, 3)</math> binary [[Hamming Code]] <math>\mathbf{C}</math>, with parity check matrix <math>\mathbf{H}</math>. For an input <math>\mathbf{x}</math> from source <math>X</math>, only the syndrome given by <math>\mathbf{s}=\mathbf{H}\mathbf{x}</math> is transmitted, which is 3 bits. With received <math>\mathbf{y}</math> and <math>\mathbf{s}</math>, suppose there are two inputs <math>\mathbf{x_1}</math> and <math>\mathbf{x_2}</math> with same syndrome <math>\mathbf{s}</math>. That means <math>\mathbf{H}\mathbf{x_1}=\mathbf{H}\mathbf{x_2}</math>, which is <math>\mathbf{H}(\mathbf{x_1}-\mathbf{x_2})=0</math>. Since the minimum Hamming weight of <math>(7,4,3)</math> Hamming Code is 3, <math>d_H(\mathbf{x_1}, \mathbf{x_2})\geq 3</math>. Therefore, the input <math>\mathbf{x}</math> can be recovered since <math>d_H(\mathbf{x}, \mathbf{y})\leq 1</math>.		In this example, we can use the <math>(7,4, 3)</math> binary [[Hamming Code]] <math>\mathbf{C}</math>, with parity check matrix <math>\mathbf{H}</math>. For an input <math>\mathbf{x}</math> from source <math>X</math>, only the syndrome given by <math>\mathbf{s}=\mathbf{H}\mathbf{x}</math> is transmitted, which is 3 bits. With received <math>\mathbf{y}</math> and <math>\mathbf{s}</math>, suppose there are two inputs <math>\mathbf{x_1}</math> and <math>\mathbf{x_2}</math> with same syndrome <math>\mathbf{s}</math>. That means <math>\mathbf{H}\mathbf{x_1}=\mathbf{H}\mathbf{x_2}</math>, which is <math>\mathbf{H}(\mathbf{x_1}-\mathbf{x_2})=0</math>. Since the minimum Hamming weight of <math>(7,4,3)</math> Hamming Code is 3, <math>d_H(\mathbf{x_1}, \mathbf{x_2})\geq 3</math>. Therefore, the input <math>\mathbf{x}</math> can be recovered since <math>d_H(\mathbf{x}, \mathbf{y})\leq 1</math>.