Decoding AEL codes

Decoding AEL Codes

Background

Suppose we have a code $ C_{0} $ which involves using some alphabets (symbols which are used to represent a code) then how can we generate a family of codes $ {C_{n}} $ from this code $ C_{0} $ with the same rate and distance but over a larger alphabet set.To generate this family of codes ABNNR and AEL codes are used which differ in $ C_{0} $. In ABNNR $ C_{0} $ is a repetition code whereas in AEL codes $ C_{0} $ is any given code.

AEL codes are a generalization of the ABNNR encoding construction for a code which use expander graph. Alon,Edmonds and Luby made an observation which changed the approach of using expander graphs to encode a message. ABNNR encodes the message by assigning weights to the edges of the graph

Decoding AEL code


Decoding is done in the reverse way as the encoding process .i.e from the output message (the final code word with large alphabet set) we traverse backward on the edges of the graph $ G $ and form a candidate set of codeword for each vertex on the left side vertex set of the bipartite graph.We then use the decoding algorithm for $ C_{0} $ to get the initial vertices which are of length $ n $ i.e the left vertices and then apply the decoding algorithm for $ C  $ to get the original message back.

Summarizing the above:

Step:1Traverse along the edges from the right vertex to its $ d $ neighbors.
Step:2Using the edge weights form the codeword for each of vertex on the left side.
Step:3Apply decoding algorithm of $ C_{0} $ to get the initial left vertices.
Step:4Apply decoding algorithm of $ C $ to get the initial message sent.

The theorem below tries to prove that there exists codes with $ q $ alphabets and satisfies other parameters as mentioned below such that with $ \leq \dfrac{\delta}{2} $ fraction of errors it can be decodable in linear time.

Theorem 5:(Guruswami and Indyk) For all such values of $ R,\delta  $ which satisfy the condition $ R + \delta < 1  $, there is a $  n_{0} < \infty $ such that for all such values of $  n > n_{0}  $ there can exist $ q $ - ary codes of rate $ R $ with relative distance $ \geq \delta  $ that are uniquely decodable from $ \leq \dfrac {\delta}{2} $ fraction of errors in linear time.

Proof: As mentioned above, following the approach of reversing the method of encoding we can arrive at our messages.
The following assumptions are made in the proof of the above theorem:

- Say the final output code word formed has $ \tau \cdot n $ errors associated with it.
- Say we have a constant time algorithm to decode $ C_{0} $.
- That we have a linear time algorithm to decode $ C $ if there are $ \leq \dfrac{\beta \cdot n}{2} $ errors.

Sketch: Take the bipartite graph used in the encoding process and follow the edges from the right vertices to the left vertices as there are errors in the codeword, these errors are propagated to the left vertices as we traverse along the edges. We can uniquely decode a vertex on the left side if the number of errors is or the number of edges coming into the vertex from the right vertex sets are $ \leq \dfrac{\delta\cdotd}{2} $. i.e let us consider $ |X'| $ be the number of vertices which have errors $ \req \dfrac{\delta\cdotn}{2} $ and $ |Y'| $ the number of vertices on the right side of the bipartite graph that are uncorrupted $ (1-\tau)\cdotn $ i.e $ \tau\cdotn+(1-\tau)\cdotn = n  $ (total number of errors + correct bits of the output = $ n $).

As the graph $ G $ is a $ (d,\epsilon) $ graph then it implies it has atleast $ ( $$ \dfrac{|X'|\cdot(1-\tau)}{n}-\epsilon)\cdotd\cdotn $ edges between $ X $ and$  Y $. But every vertex in $ X $ has atleast $ \dfrac{\delta\cdotd}{2} $errors or we can say that each vertex in $ X $ has atmost $ (1-\dfrac{\delta}{2})\cdotd $ neighbors in $ Y $. We can then show that:

$ ( $$ \dfrac{|X'|\cdot(1-\tau)}{n}-\epsilon)\cdotd\cdotn \leq  $ $ ( $ number of edges from $ X $ to $  Y  $ $  )  $ $  \leq (1-\dfrac{\delta}{2})\cdotd\cdot|X'|} $ which on simplification gives: $ |X'|\leq\dfrac{\epsilon\cdotn}{\dfrac{\delta}{2}-\tau} $

choosing : $ \tau\leq\dfrac{\delta}{2}-\dfrac{2\cdot\epsilon}{\beta} $ (the $ n $ elements of the left vertex set has a distance $ D $ and so we can get a correct code if the number of errors is less than $ \dfrac{D}{2} $ but since this is a $ (d,\epsilon) $ graph $ \beta = \dfrac{|X'|}{n} $ or $ \beta = \dfrac{D}{2} $). Hence substituting for $ D $,

we get : $ |X'|\leq\dfrac{\beta \cdot n}{2} $

Therefore we can decode from a fraction $ \tau = \dfrac{\delta}{2}-\dfrac{2\cdot\epsilon}{\beta} $ of errors in linear time by choosing $ C,C_{0} $ appropriately.