Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
    
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
add comment

1 Answer 1

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.

share|improve this answer
    
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
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. –  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
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$. –  joriki Dec 13 '12 at 1:03
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.