3
$\begingroup$

I am reading about an algorithm for finding 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$.

  • 0
    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$?2012-12-12
  • 0
    @joriki thanks by your feedback, I edit a question.2012-12-12
  • 0
    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.2012-12-12
  • 0
    $2p$ haven't relevance2012-12-13
  • 0
    Yes haven't relevance, please members help me with this question,2012-12-27

1 Answers 1

3

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.

  • 0
    sorry $|I| = k$ but |supp(c)| is not $k$, because c is arbitrary, the paper where I am ready this, is https://www.rocq.inria.fr/secret/Anne.Canteaut/Publications/Canteaut_Chabaud98.pdf (pag. 370 first column)2012-12-13
  • 0
    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$?2012-12-13
  • 1
    @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.2012-12-13
  • 0
    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 ...2012-12-13
  • 1
    @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$.2012-12-13
  • 0
    mmm, ... I understand better now but I don't understand Why you say that need obtain a vector $c$ with exactly $k $ non-zero bits ... the vector would have to be $u$ non-zero bits (by enunciated).2012-12-13
  • 0
    @Juan: As I said, I'm merely guessing about the role of $k$. It would help if you cared to comment on that guess. I don't understand why you say that the vector should have $u$ non-zero bits. The question seems to be saying that it should have $u$ non-zero bits in $I$. Are you saying that it has no non-zero bits at all outside $I$?2012-12-13
  • 0
    Hi @joriki in my first comment I mentioned $|I|=k$. By enunciated, the question seems to be saying that it should have $u$ non-zero bits in $I$. Also, the vector $c$ will be able non-zero bits at all ouside $I$. You will be able to write any small example please, For example for $n=5, k=3$ and |supp(c)\cap I|.2012-12-13