Stern’s algorithm: A short introduction

Stern’s algorithm is an algorithm for solving the following:

$\blacksquare ~ \textnormal{\textbf{Problem} \textsc{General Decoding}}$
Given a random matrix $\mathbf{A} \in \mathbb{F}_2^{k\times n}$ and a pertubed vector $\mathbf{r}$ , find a vector $\mathbf{x} = (x_1,x_2,\ldots,x_{k})$ such that $\mathbf{x}\cdot\mathbf{A} = \mathbf{y} = (y_1,y_2,\ldots,y_n)$ and $\mathbf{r} = (r_1,r_2,\ldots,r_n)$ agrees in as many points as possible.

$\blacksquare ~ \textnormal{\textbf{Algorithm} \emph{Stern's algorithm}}$
Input: generator matrix $\mathbf{G}$

Pick a random column permutation $\pi$ and permute $\mathbf{G}$ .
Make $\mathbf{G}$ systematic.
Pick all possible sums of $p/2$ columns from the $k/2$ first rows of $\mathbf{G}$ and store in list $\mathcal{L}$ indexed by bits in the $q$ -field.
Same as above but with the next $k/2$ rows of $\mathbf{G}$ . Look in $\mathcal{L}$ for values indexed by the $q$ -field. For each such collision, create the sum of the two vectors. Now they form a vector stemming from the $p$ columns in the first the $k$ columns that is zero in the $q$ -field.
For each such candidate, calculate the whole weight. If it is $w$ , output it. If none is found, repeat from 1.