let $C : F_q^k \rightarrow F_q^n$ be an Error-Correcting Code of type LDGM (Low-Density Generator Matrix).
Let $x \in C$. I want to know if there was a way of counting the number of possible code words $y \in C$ such that $\delta(x,y) = l$ ($\delta$ is the hamming distance and $l < n$) ?
I was also wondering if we could count them when we restrain the positions of the different bits. This means that if we see $x$ as a list, can we also count the number of $y \in C$ such that $\delta(x,y) = l$, and that $x[1..m] = y[1..m]$ for a certain known m?
I tried looking into the Hamming inequality saying that the number of words in $F_q^n$ at an exact distance $l$ from $x$ is equal to $C_n^l$. But this equality counts all the words in $F_q^n$, and not only those which are in the code $C$ like in my case.
Best Answer
What you are looking for is called the distance distribution of the code around a codeword $c$. For a linear code, this is the same as the weight enumerator of the code. Finding this information for an arbitrary code is a very difficult problem. The constrained weight enumerator is even harder, in general.
This is known for some algebraic code constructions, e.g., Reed Solomon, Golay, etc., but for general LDPC codes, since they are randomly generated, only statistical results are known.
The extended Golay code has the following weight enumerator $$ W(x,y)=x^{24} + 759 x^{16} y^8 + 2576 x^{12} y^{12} + 759 x^8 y^{16} + y^{24} $$ telling us that the extended Golay code has $759$ words of weights $8$ and $16$, and $2576$ words of weight $12$, and a single word of weight $0$ and a single word of weight $24$.
Notation: The coefficient of $x^d y^{24-d}$ in $W(x,y)$ is the number of codewords of weight $d$.
See also the answer to the question here where the derivation of the polynomial is explained.