# Combinatory + Coding Theory

I am reading about an algorithm for ﬁnding minimum-weight words in large linear codes. Let $c$ be the codeword of weight $w$ to recover (with size $n$ and in $GF(2)$). Let $N = \left\{1, 2, \ldots, n\right\}$ and $I\subset N$ ($|I| = k$). Let $\left\{X_i\right\}_{i\in N}$ be a stochastic process which corresponds to the number of nonzero bits of $c$ in $I$ and the random variable $X_i$ take its values in the set $\left\{1, 2, \ldots, w\right\}$. The state space of the stochastic process is:

$$E = \left\{1, \cdots, 2p - 1\right\} \cup \left\{2p\right\} \cup \left\{2p + 1, \cdots, w\right\}$$

where

$X_i = u$ iff $|I\cap \textrm{supp}(c)| = u$, $\forall u \in \left\{1, \cdots, 2p-1\right\} \cup \left\{2p + 1, \cdots, w\right\}.$

My questions are: Why the initial probabilty vector is $\pi_0(u)=\dfrac{C^{w}_u C^{n-w}_{k-u}}{C^{n}_k}$, if $u \notin \left\{{2p}\right\}$. And the most important: How to interpret these combinatorials?.

Definition: $\textrm{supp}(c)$ is a set with coordinates of nonzero bits in $c$.

-
a) What does "pdta" mean? Is there a reason you let us guess an abbreviation instead of pressing a few more keys to write it out? b) Your definition of $\operatorname{supp}$ as a number in the last line is inconsistent with its use as a set further up. c) What's $p$? What's the significance of $2p$ being singled out in $E$ and removed from the options for $u$? –  joriki Dec 12 '12 at 23:44
@joriki thanks by your feedback, I edit a question. –  juaninf Dec 12 '12 at 23:51
You haven't resolved the discrepancy between the definition of $\operatorname{supp}$ as a number and its use as a set. Also the addition of $u\notin\{2p\}$ hasn't clarified the role of $p$ for me. –  joriki Dec 12 '12 at 23:56
$2p$ haven't relevance –  juaninf Dec 13 '12 at 0:00
Yes haven't relevance, please members help me with this question, –  juaninf Dec 27 '12 at 19:57

The question is hard to understand, with a lot of focus on a quantity $2p$ that you say is irrelevant, and crucial information missing. You didn't introduce $w$ and $k$, so it can only be guessed that $w=|I|$ and $k=|\operatorname{supp}(c)|$. Under the additional assumption that $c$ is uniformly randomly drawn from all vectors with $k$ non-zero bits, the expression
$$\frac{\binom wu\binom{n-w}{k-u}}{\binom nk}$$
gives the probability of $c$ having exactly $u$ non-zero bits in $I$ as the ratio of the number of possibilities of choosing $u$ of $w$ bits in $I$ and $k-u$ of $n-w$ bits outside $I$ to be non-zero to the total number of possibilities of choosing $k$ out of $n$ bits to be non-zero.
sorry $|I| = k$ but |supp(c)| is not $k$, because c is arbitrary, the paper where I am ready this, is rocq.inria.fr/secret/Anne.Canteaut/Publications/… (pag. 370 first column) –  juaninf Dec 13 '12 at 0:29
this part I don't understand... and $k−u$ of $n−w$ bits outside $I$ to be non-zero ... Why outside $I$ if I want get non-zero bits in $I$? –  juaninf Dec 13 '12 at 0:43
@Juan: This is all based on my guesses on the meaning of $w$ and $k$, which you haven't commented on yet. If they mean what I think they mean, then you must choose $k$ non-zero bits in total, so $u$ out of $w$ in $I$ leaves $k-u$ out of $n-w$ outside $I$ to be chosen. –  joriki Dec 13 '12 at 0:50
Thanks by your patience, Why "so $u$ out of $w$ in $I$ leaves $k−u$ out of $n−w$outside $I$ to be chosen"? I don't understand again ... –  juaninf Dec 13 '12 at 1:00
@Juan: There are $k$ non-zero bits to be selected; $u$ of them are in I; it follows that $k-u$ of them are not in $I$. There are $n$ bits in total; $w$ of them are in $I$; it follows that $n-w$ of them are not in $I$. Any selection of $u$ non-zero bits out of the $w$ bits of $I$ can be combined with any selection of $k-u$ non-zero bits out of the $n-w$ bits outside $I$ to obtain a vector $c$ with exactly $k$ non-zero bits of which $u$ are in $I$. –  joriki Dec 13 '12 at 1:03