Zemor's decoding algorithm - Revision history

Suriname0: Adding short description: "Coding theory algorithm"

2025-01-18T01:58:31Z

Adding short description: "Coding theory algorithm"

← Previous revision		Revision as of 01:58, 18 January 2025
Line 1:		Line 1:
			{{Short description\|Coding theory algorithm}}
	In [[coding theory]], '''Zemor's algorithm''', designed and developed by Gilles Zemor,<ref name="vg1">{{Cite web\|url=https://www.math.u-bordeaux.fr/~gzemor/\|title=Gilles Zémor\|website=www.math.u-bordeaux.fr\|accessdate=9 April 2023}}</ref> is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of [[Michael Sipser\|Sipser]] and [[Daniel Spielman\|Spielman]].		In [[coding theory]], '''Zemor's algorithm''', designed and developed by Gilles Zemor,<ref name="vg1">{{Cite web\|url=https://www.math.u-bordeaux.fr/~gzemor/\|title=Gilles Zémor\|website=www.math.u-bordeaux.fr\|accessdate=9 April 2023}}</ref> is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of [[Michael Sipser\|Sipser]] and [[Daniel Spielman\|Spielman]].

Citation bot: Altered issue. Added pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Error detection and correction | #UCB_Category 112/128

2024-12-17T17:39:26Z

Altered issue. Added pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Error detection and correction | #UCB_Category 112/128

← Previous revision		Revision as of 17:39, 17 December 2024
Line 41:		Line 41:

	==== Proof ====		==== Proof ====
	Let <math> B</math> be derived from the <math>d</math> regular graph <math>G</math>. So, the number of variables of <math>C(B,S)</math> is <math> \left(\dfrac{dn}{2}\right)</math> and the number of constraints is <math>n</math>. According to Alon - Chung,<ref name="vg4">{{cite journal \|author1=N. Alon \|author2=F.R.K. Chung \|title=Explicit construction of linear sized tolerant networks \|journal=[[Discrete Mathematics (journal)\|Discrete Mathematics]] \|date=December 1988 \|volume=72 \|issue=~~1-3~~ \|doi=10.1016/0012-365X(88)90189-6\|citeseerx=10.1.1.300.7495 }}</ref> if <math>X</math> is a subset of vertices of <math>G</math> of size <math>\gamma n</math>, then the number of edges contained in the subgraph is induced by <math>X</math> in <math>G</math> is at most <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)</math>.		Let <math> B</math> be derived from the <math>d</math> regular graph <math>G</math>. So, the number of variables of <math>C(B,S)</math> is <math> \left(\dfrac{dn}{2}\right)</math> and the number of constraints is <math>n</math>. According to Alon - Chung,<ref name="vg4">{{cite journal \|author1=N. Alon \|author2=F.R.K. Chung \|title=Explicit construction of linear sized tolerant networks \|journal=[[Discrete Mathematics (journal)\|Discrete Mathematics]] \|date=December 1988 \|volume=72 \|issue=1–3 \|pages=15–19 \|doi=10.1016/0012-365X(88)90189-6\|citeseerx=10.1.1.300.7495 }}</ref> if <math>X</math> is a subset of vertices of <math>G</math> of size <math>\gamma n</math>, then the number of edges contained in the subgraph is induced by <math>X</math> in <math>G</math> is at most <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)</math>.

	As a result, any set of <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + \left(\dfrac{\lambda}{d}\right)\gamma \left(1-\gamma\right)\right)</math> variables will be having at least <math>\gamma n</math> constraints as neighbours. So the average number of variables per constraint is : <math>\left(\dfrac{(\dfrac{2nd}{2}) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)}{\gamma n}\right)</math>		As a result, any set of <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + \left(\dfrac{\lambda}{d}\right)\gamma \left(1-\gamma\right)\right)</math> variables will be having at least <math>\gamma n</math> constraints as neighbours. So the average number of variables per constraint is : <math>\left(\dfrac{(\dfrac{2nd}{2}) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)}{\gamma n}\right)</math>

1234qwer1234qwer4: fix spacing around math (via WP:JWB)

2024-10-04T16:21:50Z

fix spacing around math (via WP:JWB)

← Previous revision		Revision as of 16:21, 4 October 2024
Line 54:		Line 54:
	The iterative decoding algorithm written below alternates between the vertices <math>A</math> and <math>B</math> in <math>G</math> and corrects the codeword of <math>C_o</math> in <math>A</math> and then it switches to correct the codeword <math>C_o</math> in <math>B</math>. Here edges associated with a vertex on one side of a graph are not incident to other vertex on that side. In fact, it doesn't matter in which order, the set of nodes <math>A</math> and <math>B</math> are processed. The vertex processing can also be done in parallel.		The iterative decoding algorithm written below alternates between the vertices <math>A</math> and <math>B</math> in <math>G</math> and corrects the codeword of <math>C_o</math> in <math>A</math> and then it switches to correct the codeword <math>C_o</math> in <math>B</math>. Here edges associated with a vertex on one side of a graph are not incident to other vertex on that side. In fact, it doesn't matter in which order, the set of nodes <math>A</math> and <math>B</math> are processed. The vertex processing can also be done in parallel.

	The decoder <math>\mathbb{D}:\mathbb{F}^d \rightarrow C_o</math>stands for a decoder for <math>C_o</math> that recovers correctly with any codewords with less than <math>\left(\dfrac{d}{2}\right)</math> errors.		The decoder <math>\mathbb{D}:\mathbb{F}^d \rightarrow C_o</math> stands for a decoder for <math>C_o</math> that recovers correctly with any codewords with less than <math>\left(\dfrac{d}{2}\right)</math> errors.

	=== Decoder algorithm ===		=== Decoder algorithm ===
Line 89:		Line 89:

	Since the decoding algorithm is insensitive to the value of the edges and by linearity, we can assume that the transmitted codeword is the all zeros - vector. Let the received codeword be <math>w</math>. The set of edges which has an incorrect value while decoding is considered. Here by incorrect value, we mean <math>1</math> in any of the bits. Let <math>w=w^0</math> be the initial value of the codeword, <math>w^1, w^2,\ldots, w^t</math> be the values after first, second . . . <math>t</math> stages of decoding.		Since the decoding algorithm is insensitive to the value of the edges and by linearity, we can assume that the transmitted codeword is the all zeros - vector. Let the received codeword be <math>w</math>. The set of edges which has an incorrect value while decoding is considered. Here by incorrect value, we mean <math>1</math> in any of the bits. Let <math>w=w^0</math> be the initial value of the codeword, <math>w^1, w^2,\ldots, w^t</math> be the values after first, second . . . <math>t</math> stages of decoding.
	Here, <math>X^i={e\in E\|x_e^i =1}</math>, and <math>S^i ={v\in V^i \| E_v \cap X^{i+1} !=\emptyset}</math>. Here <math>S^i</math> corresponds to those set of vertices that was not able to successfully decode their codeword in the <math>i^{th}</math> round. From the above algorithm <math>S^1 <S^0 </math> as number of unsuccessful vertices will be corrected in every iteration. We can prove that <math>S^0>S^1>S^2>\cdots</math>is a decreasing sequence.		Here, <math>X^i={e\in E\|x_e^i =1}</math>, and <math>S^i ={v\in V^i \| E_v \cap X^{i+1} !=\emptyset}</math>. Here <math>S^i</math> corresponds to those set of vertices that was not able to successfully decode their codeword in the <math>i^{th}</math> round. From the above algorithm <math>S^1 <S^0 </math> as number of unsuccessful vertices will be corrected in every iteration. We can prove that <math>S^0>S^1>S^2>\cdots</math> is a decreasing sequence.
	In fact, <math>\|S_{i+1}\|<=(\dfrac{1}{2-\alpha})\|S_i\|</math>. As we are assuming, <math>\alpha<1</math>, the above equation is in a [[geometric series\|geometric decreasing sequence]].		In fact, <math>\|S_{i+1}\|<=(\dfrac{1}{2-\alpha})\|S_i\|</math>. As we are assuming, <math>\alpha<1</math>, the above equation is in a [[geometric series\|geometric decreasing sequence]].
	So, when <math>\|S_i\|<n</math>, more than <math>log_{2-\alpha} n </math> rounds are necessary. Furthermore, <math>\sum\|S_i\|=n\sum(\dfrac{1}{(2-\alpha)^i})=O(n)</math>, and if we implement the <math>i^{th}</math> round in <math>O(\|S_i\|)</math> time, then the total sequential running time will be linear.		So, when <math>\|S_i\|<n</math>, more than <math>log_{2-\alpha} n </math> rounds are necessary. Furthermore, <math>\sum\|S_i\|=n\sum(\dfrac{1}{(2-\alpha)^i})=O(n)</math>, and if we implement the <math>i^{th}</math> round in <math>O(\|S_i\|)</math> time, then the total sequential running time will be linear.

David Eppstein: rescue deadlink and expand metadata

2024-09-18T07:09:15Z

rescue deadlink and expand metadata

← Previous revision		Revision as of 07:09, 18 September 2024
Line 1:		Line 1:
	In [[coding theory]], '''Zemor's algorithm''', designed and developed by Gilles Zemor,<ref name="vg1">{{Cite web\|url=https://www.math.u-bordeaux.fr/~gzemor/\|title=Gilles Zémor\|website=www.math.u-bordeaux.fr\|accessdate=9 April 2023}}</ref> is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of [[Michael Sipser\|Sipser]] and [[Daniel Spielman\|Spielman]].		In [[coding theory]], '''Zemor's algorithm''', designed and developed by Gilles Zemor,<ref name="vg1">{{Cite web\|url=https://www.math.u-bordeaux.fr/~gzemor/\|title=Gilles Zémor\|website=www.math.u-bordeaux.fr\|accessdate=9 April 2023}}</ref> is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of [[Michael Sipser\|Sipser]] and [[Daniel Spielman\|Spielman]].

	Zemor considered a typical class of Sipser–Spielman construction of [[expander code]]s, where the underlying graph is [[bipartite graph]]. Sipser and Spielman introduced a constructive family of asymptotically good linear-error codes together with a simple parallel algorithm that will always remove a constant fraction of errors. The article is based on Dr. Venkatesan Guruswami's course notes <ref name="vg2">http://www.cs.washington.edu/education/courses/cse590vg/03wi/scribes/1-27.ps ~~{{Dead~~ ~~link~~\|date=~~February~~ ~~2022~~}}</ref>		Zemor considered a typical class of Sipser–Spielman construction of [[expander code]]s, where the underlying graph is [[bipartite graph]]. Sipser and Spielman introduced a constructive family of asymptotically good linear-error codes together with a simple parallel algorithm that will always remove a constant fraction of errors. The article is based on Dr. Venkatesan Guruswami's course notes <ref name="vg2">{{cite web\|url=http://www.cs.washington.edu/education/courses/cse590vg/03wi/scribes/1-27.ps\|archive-url=https://web.archive.org/web/20140224135408/https://courses.cs.washington.edu/courses/cse590vg/03wi/scribes/1-27.ps\|archive-date=2014-02-24\|title=Lecture 5 \|work=CSE590G: Codes and Pseudorandom Objects\|publisher=University of Washington\|first1=Venkatesan\|last1=Guruswami\|first2=Matt\|last2=Cary\|date=January 27, 2003}}</ref>

	== Code construction ==		== Code construction ==

Neko-chan: Added free to read link in citations with OAbot #oabot

2023-09-15T03:25:52Z

Added free to read link in citations with OAbot #oabot

← Previous revision		Revision as of 03:25, 15 September 2023
Line 41:		Line 41:

	==== Proof ====		==== Proof ====
	Let <math> B</math> be derived from the <math>d</math> regular graph <math>G</math>. So, the number of variables of <math>C(B,S)</math> is <math> \left(\dfrac{dn}{2}\right)</math> and the number of constraints is <math>n</math>. According to Alon - Chung,<ref name="vg4">{{cite journal \|author1=N. Alon \|author2=F.R.K. Chung \|title=Explicit construction of linear sized tolerant networks \|journal=[[Discrete Mathematics (journal)\|Discrete Mathematics]] \|date=December 1988 \|volume=72 \|issue=1-3 \|doi=10.1016/0012-365X(88)90189-6}}</ref> if <math>X</math> is a subset of vertices of <math>G</math> of size <math>\gamma n</math>, then the number of edges contained in the subgraph is induced by <math>X</math> in <math>G</math> is at most <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)</math>.		Let <math> B</math> be derived from the <math>d</math> regular graph <math>G</math>. So, the number of variables of <math>C(B,S)</math> is <math> \left(\dfrac{dn}{2}\right)</math> and the number of constraints is <math>n</math>. According to Alon - Chung,<ref name="vg4">{{cite journal \|author1=N. Alon \|author2=F.R.K. Chung \|title=Explicit construction of linear sized tolerant networks \|journal=[[Discrete Mathematics (journal)\|Discrete Mathematics]] \|date=December 1988 \|volume=72 \|issue=1-3 \|doi=10.1016/0012-365X(88)90189-6\|citeseerx=10.1.1.300.7495 }}</ref> if <math>X</math> is a subset of vertices of <math>G</math> of size <math>\gamma n</math>, then the number of edges contained in the subgraph is induced by <math>X</math> in <math>G</math> is at most <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)</math>.

	As a result, any set of <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + \left(\dfrac{\lambda}{d}\right)\gamma \left(1-\gamma\right)\right)</math> variables will be having at least <math>\gamma n</math> constraints as neighbours. So the average number of variables per constraint is : <math>\left(\dfrac{(\dfrac{2nd}{2}) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)}{\gamma n}\right)</math>		As a result, any set of <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + \left(\dfrac{\lambda}{d}\right)\gamma \left(1-\gamma\right)\right)</math> variables will be having at least <math>\gamma n</math> constraints as neighbours. So the average number of variables per constraint is : <math>\left(\dfrac{(\dfrac{2nd}{2}) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)}{\gamma n}\right)</math>

Egeymi: Filled in 1 bare reference(s) with reFill 2 + 2

2023-04-09T15:39:32Z

Filled in 1 bare reference(s) with reFill 2 + 2

← Previous revision		Revision as of 15:39, 9 April 2023
Line 1:		Line 1:
	In [[coding theory]], '''Zemor's algorithm''', designed and developed by Gilles Zemor,<ref name="vg1">~~[http~~://www.math.u-~~bordeaux1~~.fr/~~~zemor~~/ Gilles ~~Zemor]~~</ref> is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of [[Michael Sipser\|Sipser]] and [[Daniel Spielman\|Spielman]].		In [[coding theory]], '''Zemor's algorithm''', designed and developed by Gilles Zemor,<ref name="vg1">{{Cite web\|url=https://www.math.u-bordeaux.fr/~gzemor/\|title=Gilles Zémor\|website=www.math.u-bordeaux.fr\|accessdate=9 April 2023}}</ref> is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of [[Michael Sipser\|Sipser]] and [[Daniel Spielman\|Spielman]].

	Zemor considered a typical class of Sipser–Spielman construction of [[expander code]]s, where the underlying graph is [[bipartite graph]]. Sipser and Spielman introduced a constructive family of asymptotically good linear-error codes together with a simple parallel algorithm that will always remove a constant fraction of errors. The article is based on Dr. Venkatesan Guruswami's course notes <ref name="vg2">http://www.cs.washington.edu/education/courses/cse590vg/03wi/scribes/1-27.ps {{Dead link\|date=February 2022}}</ref>		Zemor considered a typical class of Sipser–Spielman construction of [[expander code]]s, where the underlying graph is [[bipartite graph]]. Sipser and Spielman introduced a constructive family of asymptotically good linear-error codes together with a simple parallel algorithm that will always remove a constant fraction of errors. The article is based on Dr. Venkatesan Guruswami's course notes <ref name="vg2">http://www.cs.washington.edu/education/courses/cse590vg/03wi/scribes/1-27.ps {{Dead link\|date=February 2022}}</ref>
Line 5:		Line 5:
	== Code construction ==		== Code construction ==

	Zemor's algorithm is based on a type of [[expander graphs]] called [[Tanner graph]]. The construction of code was first proposed by Tanner.<ref name="vg3">http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture14.pdf ~~{{Bare~~ ~~URL PDF~~\|date=~~March~~ ~~2022~~}}</ref> The codes are based on [[double cover (topology)\|double cover]] <math>d</math>, regular expander <math>G</math>, which is a bipartite graph. <math>G</math> =<math> \left(V,E\right)</math>, where <math>V</math> is the set of vertices and <math>E</math> is the set of edges and <math>V</math> = <math>A</math> <math>\cup</math> <math>B</math> and <math>A</math> <math>\cap</math> <math>B</math> = <math>\emptyset</math>, where <math>A</math> and <math>B</math> denotes sets of vertices. Let <math>n</math> be the number of vertices in each group, ''i.e'', <math>\|A\| =\|B\| =n</math>. The edge set <math>E</math> be of size <math>N</math> =<math>nd</math> and every edge in <math>E</math> has one endpoint in both <math>A</math> and <math>B</math>. <math>E(v)</math> denotes the set of edges containing <math>v</math>.		Zemor's algorithm is based on a type of [[expander graphs]] called [[Tanner graph]]. The construction of code was first proposed by Tanner.<ref name=vg3>{{cite web \|url=http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture14.pdf \|title=Lecture notes\|website=washington.edu\|access-date=9 April 2023}}</ref> The codes are based on [[double cover (topology)\|double cover]] <math>d</math>, regular expander <math>G</math>, which is a bipartite graph. <math>G</math> =<math> \left(V,E\right)</math>, where <math>V</math> is the set of vertices and <math>E</math> is the set of edges and <math>V</math> = <math>A</math> <math>\cup</math> <math>B</math> and <math>A</math> <math>\cap</math> <math>B</math> = <math>\emptyset</math>, where <math>A</math> and <math>B</math> denotes sets of vertices. Let <math>n</math> be the number of vertices in each group, ''i.e'', <math>\|A\| =\|B\| =n</math>. The edge set <math>E</math> be of size <math>N</math> =<math>nd</math> and every edge in <math>E</math> has one endpoint in both <math>A</math> and <math>B</math>. <math>E(v)</math> denotes the set of edges containing <math>v</math>.

	Assume an ordering on <math>V</math>, therefore ordering will be done on every edges of <math>E(v)</math> for every <math>v \in V</math>. Let [[finite field]] <math>\mathbb{F}=GF(2)</math>, and for a word <math>x=(x_e), e\in E</math> in <math>\mathbb{F}^N</math>, let the subword of the word will be indexed by <math>E(v)</math>. Let that word be denoted by <math>(x)_v</math>. The subset of vertices <math>A</math> and <math>B</math> induces every word <math>x\in \mathbb{F}^N</math> a partition into <math>n</math> non-overlapping sub-words <math> \left(x\right)_v\in \mathbb{F}^d</math>, where <math>v</math> ranges over the elements of <math>A</math>.		Assume an ordering on <math>V</math>, therefore ordering will be done on every edges of <math>E(v)</math> for every <math>v \in V</math>. Let [[finite field]] <math>\mathbb{F}=GF(2)</math>, and for a word <math>x=(x_e), e\in E</math> in <math>\mathbb{F}^N</math>, let the subword of the word will be indexed by <math>E(v)</math>. Let that word be denoted by <math>(x)_v</math>. The subset of vertices <math>A</math> and <math>B</math> induces every word <math>x\in \mathbb{F}^N</math> a partition into <math>n</math> non-overlapping sub-words <math> \left(x\right)_v\in \mathbb{F}^d</math>, where <math>v</math> ranges over the elements of <math>A</math>.
Line 41:		Line 41:

	==== Proof ====		==== Proof ====
	Let <math> B</math> be derived from the <math>d</math> regular graph <math>G</math>. So, the number of variables of <math>C(B,S)</math> is <math> \left(\dfrac{dn}{2}\right)</math> and the number of constraints is <math>n</math>. According to Alon - Chung,<ref name="vg4">~~http://math~~.~~ucsd~~.~~edu/~fan/mypaps/fanpap/93tolerant~~.~~pdf~~ ~~{{Bare~~ ~~URL~~ ~~PDF~~\|date=~~March~~ ~~2022~~}}</ref> if <math>X</math> is a subset of vertices of <math>G</math> of size <math>\gamma n</math>, then the number of edges contained in the subgraph is induced by <math>X</math> in <math>G</math> is at most <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)</math>.		Let <math> B</math> be derived from the <math>d</math> regular graph <math>G</math>. So, the number of variables of <math>C(B,S)</math> is <math> \left(\dfrac{dn}{2}\right)</math> and the number of constraints is <math>n</math>. According to Alon - Chung,<ref name="vg4">{{cite journal \|author1=N. Alon \|author2=F.R.K. Chung \|title=Explicit construction of linear sized tolerant networks \|journal=[[Discrete Mathematics (journal)\|Discrete Mathematics]] \|date=December 1988 \|volume=72 \|issue=1-3 \|doi=10.1016/0012-365X(88)90189-6}}</ref> if <math>X</math> is a subset of vertices of <math>G</math> of size <math>\gamma n</math>, then the number of edges contained in the subgraph is induced by <math>X</math> in <math>G</math> is at most <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)</math>.

	As a result, any set of <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + \left(\dfrac{\lambda}{d}\right)\gamma \left(1-\gamma\right)\right)</math> variables will be having at least <math>\gamma n</math> constraints as neighbours. So the average number of variables per constraint is : <math>\left(\dfrac{(\dfrac{2nd}{2}) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)}{\gamma n}\right)</math>		As a result, any set of <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + \left(\dfrac{\lambda}{d}\right)\gamma \left(1-\gamma\right)\right)</math> variables will be having at least <math>\gamma n</math> constraints as neighbours. So the average number of variables per constraint is : <math>\left(\dfrac{(\dfrac{2nd}{2}) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)}{\gamma n}\right)</math>

BrownHairedGirl: tag with {{Bare URL PDF}}

2022-03-14T13:14:27Z

tag with {{Bare URL PDF}}

← Previous revision		Revision as of 13:14, 14 March 2022
Line 5:		Line 5:
	== Code construction ==		== Code construction ==

	Zemor's algorithm is based on a type of [[expander graphs]] called [[Tanner graph]]. The construction of code was first proposed by Tanner.<ref name="vg3">http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture14.pdf</ref> The codes are based on [[double cover (topology)\|double cover]] <math>d</math>, regular expander <math>G</math>, which is a bipartite graph. <math>G</math> =<math> \left(V,E\right)</math>, where <math>V</math> is the set of vertices and <math>E</math> is the set of edges and <math>V</math> = <math>A</math> <math>\cup</math> <math>B</math> and <math>A</math> <math>\cap</math> <math>B</math> = <math>\emptyset</math>, where <math>A</math> and <math>B</math> denotes sets of vertices. Let <math>n</math> be the number of vertices in each group, ''i.e'', <math>\|A\| =\|B\| =n</math>. The edge set <math>E</math> be of size <math>N</math> =<math>nd</math> and every edge in <math>E</math> has one endpoint in both <math>A</math> and <math>B</math>. <math>E(v)</math> denotes the set of edges containing <math>v</math>.		Zemor's algorithm is based on a type of [[expander graphs]] called [[Tanner graph]]. The construction of code was first proposed by Tanner.<ref name="vg3">http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture14.pdf {{Bare URL PDF\|date=March 2022}}</ref> The codes are based on [[double cover (topology)\|double cover]] <math>d</math>, regular expander <math>G</math>, which is a bipartite graph. <math>G</math> =<math> \left(V,E\right)</math>, where <math>V</math> is the set of vertices and <math>E</math> is the set of edges and <math>V</math> = <math>A</math> <math>\cup</math> <math>B</math> and <math>A</math> <math>\cap</math> <math>B</math> = <math>\emptyset</math>, where <math>A</math> and <math>B</math> denotes sets of vertices. Let <math>n</math> be the number of vertices in each group, ''i.e'', <math>\|A\| =\|B\| =n</math>. The edge set <math>E</math> be of size <math>N</math> =<math>nd</math> and every edge in <math>E</math> has one endpoint in both <math>A</math> and <math>B</math>. <math>E(v)</math> denotes the set of edges containing <math>v</math>.

	Assume an ordering on <math>V</math>, therefore ordering will be done on every edges of <math>E(v)</math> for every <math>v \in V</math>. Let [[finite field]] <math>\mathbb{F}=GF(2)</math>, and for a word <math>x=(x_e), e\in E</math> in <math>\mathbb{F}^N</math>, let the subword of the word will be indexed by <math>E(v)</math>. Let that word be denoted by <math>(x)_v</math>. The subset of vertices <math>A</math> and <math>B</math> induces every word <math>x\in \mathbb{F}^N</math> a partition into <math>n</math> non-overlapping sub-words <math> \left(x\right)_v\in \mathbb{F}^d</math>, where <math>v</math> ranges over the elements of <math>A</math>.		Assume an ordering on <math>V</math>, therefore ordering will be done on every edges of <math>E(v)</math> for every <math>v \in V</math>. Let [[finite field]] <math>\mathbb{F}=GF(2)</math>, and for a word <math>x=(x_e), e\in E</math> in <math>\mathbb{F}^N</math>, let the subword of the word will be indexed by <math>E(v)</math>. Let that word be denoted by <math>(x)_v</math>. The subset of vertices <math>A</math> and <math>B</math> induces every word <math>x\in \mathbb{F}^N</math> a partition into <math>n</math> non-overlapping sub-words <math> \left(x\right)_v\in \mathbb{F}^d</math>, where <math>v</math> ranges over the elements of <math>A</math>.
Line 41:		Line 41:

	==== Proof ====		==== Proof ====
	Let <math> B</math> be derived from the <math>d</math> regular graph <math>G</math>. So, the number of variables of <math>C(B,S)</math> is <math> \left(\dfrac{dn}{2}\right)</math> and the number of constraints is <math>n</math>. According to Alon - Chung,<ref name="vg4">http://math.ucsd.edu/~fan/mypaps/fanpap/93tolerant.pdf</ref> if <math>X</math> is a subset of vertices of <math>G</math> of size <math>\gamma n</math>, then the number of edges contained in the subgraph is induced by <math>X</math> in <math>G</math> is at most <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)</math>.		Let <math> B</math> be derived from the <math>d</math> regular graph <math>G</math>. So, the number of variables of <math>C(B,S)</math> is <math> \left(\dfrac{dn}{2}\right)</math> and the number of constraints is <math>n</math>. According to Alon - Chung,<ref name="vg4">http://math.ucsd.edu/~fan/mypaps/fanpap/93tolerant.pdf {{Bare URL PDF\|date=March 2022}}</ref> if <math>X</math> is a subset of vertices of <math>G</math> of size <math>\gamma n</math>, then the number of edges contained in the subgraph is induced by <math>X</math> in <math>G</math> is at most <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)</math>.

	As a result, any set of <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + \left(\dfrac{\lambda}{d}\right)\gamma \left(1-\gamma\right)\right)</math> variables will be having at least <math>\gamma n</math> constraints as neighbours. So the average number of variables per constraint is : <math>\left(\dfrac{(\dfrac{2nd}{2}) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)}{\gamma n}\right)</math>		As a result, any set of <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + \left(\dfrac{\lambda}{d}\right)\gamma \left(1-\gamma\right)\right)</math> variables will be having at least <math>\gamma n</math> constraints as neighbours. So the average number of variables per constraint is : <math>\left(\dfrac{(\dfrac{2nd}{2}) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)}{\gamma n}\right)</math>

BrownHairedGirl: {{Dead link}} tag on bare URL refs which return HTTP 404 or 410

2022-02-12T13:44:45Z

{{Dead link}} tag on bare URL refs which return HTTP 404 or 410

Darcourse: spelling

2021-09-18T08:32:16Z

spelling

← Previous revision		Revision as of 08:32, 18 September 2021
Line 18:		Line 18:
	In this figure, <math>(x)_v =\left(x_{e1}, x_{e2}, x_{e3}, x_{e4}\right)\in C_o</math>. It shows the graph <math>G</math> and code <math>C</math>.		In this figure, <math>(x)_v =\left(x_{e1}, x_{e2}, x_{e3}, x_{e4}\right)\in C_o</math>. It shows the graph <math>G</math> and code <math>C</math>.

	In matrix <math>G</math>, let <math>\lambda</math> is equal to the second largest [[~~eigen value~~]] of [[adjacency matrix]] of <math>G</math>. Here the largest ~~eigen value~~ is <math> d</math>.		In matrix <math>G</math>, let <math>\lambda</math> is equal to the second largest [[eigenvalue]] of [[adjacency matrix]] of <math>G</math>. Here the largest eigenvalue is <math> d</math>.
	Two important claims are made:		Two important claims are made:

Line 38:		Line 38:
	: <math>=N\left(\delta^2- O\left(\dfrac{\lambda}{d}\right)\right)</math> <math>\rightarrow (1)</math>		: <math>=N\left(\delta^2- O\left(\dfrac{\lambda}{d}\right)\right)</math> <math>\rightarrow (1)</math>

	''If <math> S </math> is linear code of rate <math>r</math>, block code length <math> d</math>, and minimum relative distance <math>\delta</math>, and if <math>B</math> is the edge vertex incidence graph of a <math>d</math> – regular graph with second largest ~~eigen value~~ <math>\lambda</math>, then the code <math>C(B,S)</math> has rate at least <math>2r_o -1</math> and minimum relative distance at least <math>\left(\left(\dfrac{\delta- \left(\dfrac{\lambda}{d}\right)}{1-\left(\dfrac{\lambda}{d}\right)}\right)\right)^2</math>.		''If <math> S </math> is linear code of rate <math>r</math>, block code length <math> d</math>, and minimum relative distance <math>\delta</math>, and if <math>B</math> is the edge vertex incidence graph of a <math>d</math> – regular graph with second largest eigenvalue <math>\lambda</math>, then the code <math>C(B,S)</math> has rate at least <math>2r_o -1</math> and minimum relative distance at least <math>\left(\left(\dfrac{\delta- \left(\dfrac{\lambda}{d}\right)}{1-\left(\dfrac{\lambda}{d}\right)}\right)\right)^2</math>.

	==== Proof ====		==== Proof ====
Line 48:		Line 48:
	So if <math> d\left( \gamma + (\dfrac{\lambda}{d}) \left( 1-\gamma\right)\right) < \gamma d</math>, then a word of relative weight <math> \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)</math>, cannot be a codeword of <math>C(B,S)</math>. The inequality <math>(2)</math> is satisfied for <math>\gamma < \left(\dfrac{1-(\dfrac{\lambda}{d})}{\delta-(\dfrac{\lambda}{d})}\right)</math>. Therefore, <math>C(B,S)</math> cannot have a non zero codeword of relative weight <math>\left(\dfrac{\delta-(\dfrac{\lambda}{d})}{1-(\dfrac{\lambda}{d})}\right)^2</math> or less.		So if <math> d\left( \gamma + (\dfrac{\lambda}{d}) \left( 1-\gamma\right)\right) < \gamma d</math>, then a word of relative weight <math> \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)</math>, cannot be a codeword of <math>C(B,S)</math>. The inequality <math>(2)</math> is satisfied for <math>\gamma < \left(\dfrac{1-(\dfrac{\lambda}{d})}{\delta-(\dfrac{\lambda}{d})}\right)</math>. Therefore, <math>C(B,S)</math> cannot have a non zero codeword of relative weight <math>\left(\dfrac{\delta-(\dfrac{\lambda}{d})}{1-(\dfrac{\lambda}{d})}\right)^2</math> or less.

	In matrix <math>G</math>, we can assume that <math>\lambda/d</math> is bounded away from <math>1</math>. For those values of <math> d</math> in which <math>d-1</math> is odd prime, there are explicit constructions of sequences of <math> d</math> - regular bipartite graphs with arbitrarily large number of vertices such that each graph <math>G</math> in the sequence is a [[Ramanujan graph]]. It is called Ramanujan graph as it satisfies the inequality <math>\lambda(G) \leq 2\sqrt{d-1}</math>. Certain expansion properties are visible in graph <math>G</math> as the separation between the ~~eigen values~~ <math>d</math> and <math> \lambda </math>. If the graph <math> G </math> is Ramanujan graph, then that expression <math>(1)</math> will become <math>0</math> eventually as <math> d </math> becomes large.		In matrix <math>G</math>, we can assume that <math>\lambda/d</math> is bounded away from <math>1</math>. For those values of <math> d</math> in which <math>d-1</math> is odd prime, there are explicit constructions of sequences of <math> d</math> - regular bipartite graphs with arbitrarily large number of vertices such that each graph <math>G</math> in the sequence is a [[Ramanujan graph]]. It is called Ramanujan graph as it satisfies the inequality <math>\lambda(G) \leq 2\sqrt{d-1}</math>. Certain expansion properties are visible in graph <math>G</math> as the separation between the eigenvalues <math>d</math> and <math> \lambda </math>. If the graph <math> G </math> is Ramanujan graph, then that expression <math>(1)</math> will become <math>0</math> eventually as <math> d </math> becomes large.

	== Zemor's algorithm ==		== Zemor's algorithm ==

157.131.254.88: /* Code construction / changed "A and B denotes sets of 2 vertices" to "A and B denotes sets of vertices" (because A and B do not* have size 2).

2021-02-02T17:41:21Z

Code construction: changed "A and B denotes sets of 2 vertices" to "A and B denotes sets of vertices" (because A and B *do not* have size 2).

← Previous revision		Revision as of 17:41, 2 February 2021
Line 5:		Line 5:
	== Code construction ==		== Code construction ==

	Zemor's algorithm is based on a type of [[expander graphs]] called [[Tanner graph]]. The construction of code was first proposed by Tanner.<ref name="vg3">http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture14.pdf</ref> The codes are based on [[double cover (topology)\|double cover]] <math>d</math>, regular expander <math>G</math>, which is a bipartite graph. <math>G</math> =<math> \left(V,E\right)</math>, where <math>V</math> is the set of vertices and <math>E</math> is the set of edges and <math>V</math> = <math>A</math> <math>\cup</math> <math>B</math> and <math>A</math> <math>\cap</math> <math>B</math> = <math>\emptyset</math>, where <math>A</math> and <math>B</math> denotes ~~the set~~ of 2 vertices. Let <math>n</math> be the number of vertices in each group, ''i.e'', <math>\|A\| =\|B\| =n</math>. The edge set <math>E</math> be of size <math>N</math> =<math>nd</math> and every edge in <math>E</math> has one endpoint in both <math>A</math> and <math>B</math>. <math>E(v)</math> denotes the set of edges containing <math>v</math>.		Zemor's algorithm is based on a type of [[expander graphs]] called [[Tanner graph]]. The construction of code was first proposed by Tanner.<ref name="vg3">http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture14.pdf</ref> The codes are based on [[double cover (topology)\|double cover]] <math>d</math>, regular expander <math>G</math>, which is a bipartite graph. <math>G</math> =<math> \left(V,E\right)</math>, where <math>V</math> is the set of vertices and <math>E</math> is the set of edges and <math>V</math> = <math>A</math> <math>\cup</math> <math>B</math> and <math>A</math> <math>\cap</math> <math>B</math> = <math>\emptyset</math>, where <math>A</math> and <math>B</math> denotes sets of vertices. Let <math>n</math> be the number of vertices in each group, ''i.e'', <math>\|A\| =\|B\| =n</math>. The edge set <math>E</math> be of size <math>N</math> =<math>nd</math> and every edge in <math>E</math> has one endpoint in both <math>A</math> and <math>B</math>. <math>E(v)</math> denotes the set of edges containing <math>v</math>.

	Assume an ordering on <math>V</math>, therefore ordering will be done on every edges of <math>E(v)</math> for every <math>v \in V</math>. Let [[finite field]] <math>\mathbb{F}=GF(2)</math>, and for a word <math>x=(x_e), e\in E</math> in <math>\mathbb{F}^N</math>, let the subword of the word will be indexed by <math>E(v)</math>. Let that word be denoted by <math>(x)_v</math>. The subset of vertices <math>A</math> and <math>B</math> induces every word <math>x\in \mathbb{F}^N</math> a partition into <math>n</math> non-overlapping sub-words <math> \left(x\right)_v\in \mathbb{F}^d</math>, where <math>v</math> ranges over the elements of <math>A</math>.		Assume an ordering on <math>V</math>, therefore ordering will be done on every edges of <math>E(v)</math> for every <math>v \in V</math>. Let [[finite field]] <math>\mathbb{F}=GF(2)</math>, and for a word <math>x=(x_e), e\in E</math> in <math>\mathbb{F}^N</math>, let the subword of the word will be indexed by <math>E(v)</math>. Let that word be denoted by <math>(x)_v</math>. The subset of vertices <math>A</math> and <math>B</math> induces every word <math>x\in \mathbb{F}^N</math> a partition into <math>n</math> non-overlapping sub-words <math> \left(x\right)_v\in \mathbb{F}^d</math>, where <math>v</math> ranges over the elements of <math>A</math>.

← Previous revision		Revision as of 13:44, 12 February 2022
Line 1:		Line 1:
	In [[coding theory]], '''Zemor's algorithm''', designed and developed by Gilles Zemor,<ref name="vg1">[http://www.math.u-bordeaux1.fr/~zemor/ Gilles Zemor]</ref> is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of [[Michael Sipser\|Sipser]] and [[Daniel Spielman\|Spielman]].		In [[coding theory]], '''Zemor's algorithm''', designed and developed by Gilles Zemor,<ref name="vg1">[http://www.math.u-bordeaux1.fr/~zemor/ Gilles Zemor]</ref> is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of [[Michael Sipser\|Sipser]] and [[Daniel Spielman\|Spielman]].

	Zemor considered a typical class of Sipser–Spielman construction of [[expander code]]s, where the underlying graph is [[bipartite graph]]. Sipser and Spielman introduced a constructive family of asymptotically good linear-error codes together with a simple parallel algorithm that will always remove a constant fraction of errors. The article is based on Dr. Venkatesan Guruswami's course notes <ref name="vg2">http://www.cs.washington.edu/education/courses/cse590vg/03wi/scribes/1-27.ps</ref>		Zemor considered a typical class of Sipser–Spielman construction of [[expander code]]s, where the underlying graph is [[bipartite graph]]. Sipser and Spielman introduced a constructive family of asymptotically good linear-error codes together with a simple parallel algorithm that will always remove a constant fraction of errors. The article is based on Dr. Venkatesan Guruswami's course notes <ref name="vg2">http://www.cs.washington.edu/education/courses/cse590vg/03wi/scribes/1-27.ps {{Dead link\|date=February 2022}}</ref>

	== Code construction ==		== Code construction ==
Line 8:		Line 8:

	Assume an ordering on <math>V</math>, therefore ordering will be done on every edges of <math>E(v)</math> for every <math>v \in V</math>. Let [[finite field]] <math>\mathbb{F}=GF(2)</math>, and for a word <math>x=(x_e), e\in E</math> in <math>\mathbb{F}^N</math>, let the subword of the word will be indexed by <math>E(v)</math>. Let that word be denoted by <math>(x)_v</math>. The subset of vertices <math>A</math> and <math>B</math> induces every word <math>x\in \mathbb{F}^N</math> a partition into <math>n</math> non-overlapping sub-words <math> \left(x\right)_v\in \mathbb{F}^d</math>, where <math>v</math> ranges over the elements of <math>A</math>.		Assume an ordering on <math>V</math>, therefore ordering will be done on every edges of <math>E(v)</math> for every <math>v \in V</math>. Let [[finite field]] <math>\mathbb{F}=GF(2)</math>, and for a word <math>x=(x_e), e\in E</math> in <math>\mathbb{F}^N</math>, let the subword of the word will be indexed by <math>E(v)</math>. Let that word be denoted by <math>(x)_v</math>. The subset of vertices <math>A</math> and <math>B</math> induces every word <math>x\in \mathbb{F}^N</math> a partition into <math>n</math> non-overlapping sub-words <math> \left(x\right)_v\in \mathbb{F}^d</math>, where <math>v</math> ranges over the elements of <math>A</math>.
	For constructing a code <math>C</math>, consider a linear subcode <math>C_o</math>, which is a <math>[d,r_od,\delta] </math> code, where <math>q</math>, the size of the alphabet is <math>2</math>. For any vertex <math>v \in V</math>, let <math> v(1), v(2),\ldots,v(d)</math> be some ordering of the <math>d</math> vertices of <math>E</math> adjacent to <math>v</math>. In this code, each bit <math>x_e</math> is linked with an edge <math>e</math> of <math>E</math>.		For constructing a code <math>C</math>, consider a linear subcode <math>C_o</math>, which is a <math>[d,r_od,\delta] </math> code, where <math>q</math>, the size of the alphabet is <math>2</math>. For any vertex <math>v \in V</math>, let <math> v(1), v(2),\ldots,v(d)</math> be some ordering of the <math>d</math> vertices of <math>E</math> adjacent to <math>v</math>. In this code, each bit <math>x_e</math> is linked with an edge <math>e</math> of <math>E</math>.

	We can define the code <math>C</math> to be the set of binary vectors <math>x = \left( x_1,x_2,\ldots,x_N \right)</math> of <math>\{0,1\}^N </math> such that, for every vertex <math>v</math> of <math>V</math>, <math> \left(x_{v(1)}, x_{v(2)},\ldots, x_{v(d)}\right) </math> is a code word of <math>C_o</math>. In this case, we can consider a special case when every edge of <math>E</math> is adjacent to exactly <math>2</math> vertices of <math>V</math>. It means that <math>V</math> and <math>E</math> make up, respectively, the vertex set and edge set of <math>d</math> regular graph <math>G</math>.		We can define the code <math>C</math> to be the set of binary vectors <math>x = \left( x_1,x_2,\ldots,x_N \right)</math> of <math>\{0,1\}^N </math> such that, for every vertex <math>v</math> of <math>V</math>, <math> \left(x_{v(1)}, x_{v(2)},\ldots, x_{v(d)}\right) </math> is a code word of <math>C_o</math>. In this case, we can consider a special case when every edge of <math>E</math> is adjacent to exactly <math>2</math> vertices of <math>V</math>. It means that <math>V</math> and <math>E</math> make up, respectively, the vertex set and edge set of <math>d</math> regular graph <math>G</math>.
Line 22:		Line 22:

	=== Claim 1 ===		=== Claim 1 ===
	'''<math>\left(\dfrac{K}{N}\right)\geq 2r_o-1</math>'''<br>		'''<math>\left(\dfrac{K}{N}\right)\geq 2r_o-1</math>'''<br />
	''. Let <math>R</math> be the rate of a linear code constructed from a bipartite graph whose digit nodes have degree <math>m</math> and whose subcode nodes have degree <math>n</math>. If a single linear code with parameters <math>\left(n,k\right)</math> and rate <math>r = \left(\dfrac{k}{n}\right)</math> is associated with each of the subcode nodes, then <math>k\geq 1-\left(1-r\right)m</math>''.		''. Let <math>R</math> be the rate of a linear code constructed from a bipartite graph whose digit nodes have degree <math>m</math> and whose subcode nodes have degree <math>n</math>. If a single linear code with parameters <math>\left(n,k\right)</math> and rate <math>r = \left(\dfrac{k}{n}\right)</math> is associated with each of the subcode nodes, then <math>k\geq 1-\left(1-r\right)m</math>''.

Line 28:		Line 28:
	Let <math>R</math> be the rate of the linear code, which is equal to <math>K/N</math>		Let <math>R</math> be the rate of the linear code, which is equal to <math>K/N</math>
	Let there are <math>S</math> subcode nodes in the graph. If the degree of the subcode is <math>n</math>, then the code must have <math>\left(\dfrac{n}{m}\right) S</math> digits, as each digit node is connected to <math>m</math> of the <math>\left(n\right)S</math> edges in the graph. Each subcode node contributes <math>(n-k)</math> equations to parity check matrix for a total of <math>\left(n-k\right) S</math>. These equations may not be linearly independent.		Let there are <math>S</math> subcode nodes in the graph. If the degree of the subcode is <math>n</math>, then the code must have <math>\left(\dfrac{n}{m}\right) S</math> digits, as each digit node is connected to <math>m</math> of the <math>\left(n\right)S</math> edges in the graph. Each subcode node contributes <math>(n-k)</math> equations to parity check matrix for a total of <math>\left(n-k\right) S</math>. These equations may not be linearly independent.
	Therefore, <math>\left(\dfrac{K}{N}\right)\geq \left(\dfrac{(\dfrac{n}{m})S - (n-k)S}{(\dfrac{n}{m}) S}\right)</math><br>		Therefore, <math>\left(\dfrac{K}{N}\right)\geq \left(\dfrac{(\dfrac{n}{m})S - (n-k)S}{(\dfrac{n}{m}) S}\right)</math><br />
	<math>\geq 1-m\left(\dfrac{n-k}{n}\right)</math><br>		<math>\geq 1-m\left(\dfrac{n-k}{n}\right)</math><br />
	<math>\geq 1-m \left(1-r\right) </math>, Since the value of <math>m</math>, i.e., the digit node of this bipartite graph is <math>2</math> and here <math>r = r_o</math>, we can write as:<br>		<math>\geq 1-m \left(1-r\right) </math>, Since the value of <math>m</math>, i.e., the digit node of this bipartite graph is <math>2</math> and here <math>r = r_o</math>, we can write as:<br />
	<math>\left(\dfrac{K}{N}\right)\geq 2r_o -1</math>		<math>\left(\dfrac{K}{N}\right)\geq 2r_o -1</math>

Line 41:		Line 41:

	==== Proof ====		==== Proof ====
	Let <math> B</math> be derived from the <math>d</math> regular graph <math>G</math>. So, the number of variables of <math>C(B,S)</math> is <math> \left(\dfrac{dn}{2}\right)</math> and the number of constraints is <math>n</math>. According to Alon - Chung,<ref name="vg4">http://math.ucsd.edu/~fan/mypaps/fanpap/93tolerant.pdf</ref> if <math>X</math> is a subset of vertices of <math>G</math> of size <math>\gamma n</math>, then the number of edges contained in the subgraph is induced by <math>X</math> in <math>G</math> is at most <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)</math>.		Let <math> B</math> be derived from the <math>d</math> regular graph <math>G</math>. So, the number of variables of <math>C(B,S)</math> is <math> \left(\dfrac{dn}{2}\right)</math> and the number of constraints is <math>n</math>. According to Alon - Chung,<ref name="vg4">http://math.ucsd.edu/~fan/mypaps/fanpap/93tolerant.pdf</ref> if <math>X</math> is a subset of vertices of <math>G</math> of size <math>\gamma n</math>, then the number of edges contained in the subgraph is induced by <math>X</math> in <math>G</math> is at most <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)</math>.

	As a result, any set of <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + \left(\dfrac{\lambda}{d}\right)\gamma \left(1-\gamma\right)\right)</math> variables will be having at least <math>\gamma n</math> constraints as neighbours. So the average number of variables per constraint is : <math>\left(\dfrac{(\dfrac{2nd}{2}) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)}{\gamma n}\right)</math>		As a result, any set of <math>\left(\dfrac{dn}{2}\right) \left(\gamma^2 + \left(\dfrac{\lambda}{d}\right)\gamma \left(1-\gamma\right)\right)</math> variables will be having at least <math>\gamma n</math> constraints as neighbours. So the average number of variables per constraint is : <math>\left(\dfrac{(\dfrac{2nd}{2}) \left(\gamma^2 + (\dfrac{\lambda}{d})\gamma \left(1-\gamma\right)\right)}{\gamma n}\right)</math>
Line 52:		Line 52:
	== Zemor's algorithm ==		== Zemor's algorithm ==

	The iterative decoding algorithm written below alternates between the vertices <math>A</math> and <math>B</math> in <math>G</math> and corrects the codeword of <math>C_o</math> in <math>A</math> and then it switches to correct the codeword <math>C_o</math> in <math>B</math>. Here edges associated with a vertex on one side of a graph are not incident to other vertex on that side. In fact, it doesn't matter in which order, the set of nodes <math>A</math> and <math>B</math> are processed. The vertex processing can also be done in parallel.		The iterative decoding algorithm written below alternates between the vertices <math>A</math> and <math>B</math> in <math>G</math> and corrects the codeword of <math>C_o</math> in <math>A</math> and then it switches to correct the codeword <math>C_o</math> in <math>B</math>. Here edges associated with a vertex on one side of a graph are not incident to other vertex on that side. In fact, it doesn't matter in which order, the set of nodes <math>A</math> and <math>B</math> are processed. The vertex processing can also be done in parallel.

	The decoder <math>\mathbb{D}:\mathbb{F}^d \rightarrow C_o</math>stands for a decoder for <math>C_o</math> that recovers correctly with any codewords with less than <math>\left(\dfrac{d}{2}\right)</math> errors.		The decoder <math>\mathbb{D}:\mathbb{F}^d \rightarrow C_o</math>stands for a decoder for <math>C_o</math> that recovers correctly with any codewords with less than <math>\left(\dfrac{d}{2}\right)</math> errors.
Line 58:		Line 58:
	=== Decoder algorithm ===		=== Decoder algorithm ===

	Received word : <math>w=(w_e), e\in E</math><br>		Received word : <math>w=(w_e), e\in E</math><br />
	<code>		<code>
	<math>z \leftarrow w</math><br>		<math>z \leftarrow w</math><br />
	For <math>t \leftarrow 1</math> to <math>m</math> do //<math>m</math> is the number of iterations<br>		For <math>t \leftarrow 1</math> to <math>m</math> do //<math>m</math> is the number of iterations<br />
	{ if (<math>t</math> is odd) // Here the algorithm will alternate between its two vertex sets.<br>		{ if (<math>t</math> is odd) // Here the algorithm will alternate between its two vertex sets.<br />
	<math>X \leftarrow A</math><br>		<math>X \leftarrow A</math><br />
	else <math>X \leftarrow B</math> <br>		else <math>X \leftarrow B</math> <br />
	Iteration <math>t</math>: For every <math>v \in X</math>, let <math>(z)_v \leftarrow \mathbb{D}((z)_v)</math> // Decoding <math>z_v</math> to its nearest codeword.<br>		Iteration <math>t</math>: For every <math>v \in X</math>, let <math>(z)_v \leftarrow \mathbb{D}((z)_v)</math> // Decoding <math>z_v</math> to its nearest codeword.<br />
	}<br>		}<br />
	</code>		</code>
	Output: <math>z</math>		Output: <math>z</math>
Line 76:		Line 76:
	Let <math>w \in \{0,1\}^N</math> be the received vector, and recall that <math>N=dn</math>. The first iteration of the algorithm consists of applying the complete decoding for the code induced by <math>E_v</math> for every <math>v \in A</math> . This means that for replacing, for every <math>v \in A</math>, the vector <math>\left( w_{v(1)}, w_{v(2)}, \ldots, w_{v(d)}\right)</math> by one of the closest codewords of <math>C_o</math>. Since the subsets of edges <math>E_v</math> are disjoint for <math>v \in A</math>, the decoding of these <math>n</math> subvectors of <math>w</math> may be done in parallel.		Let <math>w \in \{0,1\}^N</math> be the received vector, and recall that <math>N=dn</math>. The first iteration of the algorithm consists of applying the complete decoding for the code induced by <math>E_v</math> for every <math>v \in A</math> . This means that for replacing, for every <math>v \in A</math>, the vector <math>\left( w_{v(1)}, w_{v(2)}, \ldots, w_{v(d)}\right)</math> by one of the closest codewords of <math>C_o</math>. Since the subsets of edges <math>E_v</math> are disjoint for <math>v \in A</math>, the decoding of these <math>n</math> subvectors of <math>w</math> may be done in parallel.

	The iteration will yield a new vector <math>z</math>. The next iteration consists of applying the preceding procedure to <math>z</math> but with <math>A</math> replaced by <math>B</math>. In other words, it consists of decoding all the subvectors induced by the vertices of <math>B</math>. The coming iterations repeat those two steps alternately applying parallel decoding to the subvectors induced by the vertices of <math>A</math> and to the subvectors induced by the vertices of <math>B</math>. <br>		The iteration will yield a new vector <math>z</math>. The next iteration consists of applying the preceding procedure to <math>z</math> but with <math>A</math> replaced by <math>B</math>. In other words, it consists of decoding all the subvectors induced by the vertices of <math>B</math>. The coming iterations repeat those two steps alternately applying parallel decoding to the subvectors induced by the vertices of <math>A</math> and to the subvectors induced by the vertices of <math>B</math>. <br />
	'''Note:''' [If <math>d=n</math> and <math>G</math> is the complete bipartite graph, then <math>C</math> is a product code of <math>C_o</math> with itself and the above algorithm reduces to the natural hard iterative decoding of product codes].		'''Note:''' [If <math>d=n</math> and <math>G</math> is the complete bipartite graph, then <math>C</math> is a product code of <math>C_o</math> with itself and the above algorithm reduces to the natural hard iterative decoding of product codes].