Expander code: Difference between revisions

Revision as of 19:53, 29 August 2019

Revision as of 07:49, 28 September 2020

Line 62:

Decoding of expander codes is possible in <math>O(n)\,</math> time when <math>\varepsilon < \tfrac{1}{4}\,</math> using the following algorithm.

Let <math>v_i\,</math> be the vertex of <math>L\,</math> that corresponds to the <math>i\,</math>th index in the codewords of <math>C\,</math>. Let <math>y \in \{0,1\}^n\,</math> be a received word, and <math>V(y) = \{v_i |\mid \text{ the } i^{\text{th}} \text{ position of } y \text{ is a } 1\}\,</math>. Let <math>e(i)\,</math> be <math>|\{v \in R |\mid v_i \in N(v) \text{ and } N(v) \cap V(y) \,</math>text{ is even<math>}\}|\,</math>, and <math>o(i)\,</math> be <math>|\{v \in R |\mid v_i \in N(v) \text{ and } N(v) \cap V(y) \,</math>text{ is odd<math>}\}|\,</math>. Then consider the greedy algorithm:

----

'''Input:''' received word <math>y\,</math>.