Combinatoria + La Teoría De La Codificación

Question

Estoy leyendo acerca de un algoritmo para encontrar el mínimo peso de las palabras en las grandes códigos lineales. Deje $c$ ser la palabra de peso $w$ recuperar (con el tamaño de la $n$ y en $GF(2)$). Deje $N = \left\{1, 2, \ldots, n\right\}$ y $I\subset N$ ($|I| = k$). Deje $\left\{X_i\right\}_{i\in N}$ ser un proceso estocástico en el que se corresponde con el número de distinto de cero bits de $c$ $I$ y la variable aleatoria $X_i$ toma sus valores en el conjunto de $\left\{1, 2, \ldots, w\right\}$. El espacio de estado del proceso estocástico es:

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

donde

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

Mis preguntas son: ¿por Qué la inicial probabilty vector es $\pi_0(u)=\dfrac{C^{w}_u C^{n-w}_{k-u}}{C^{n}_k}$ si $u \notin \left\{{2p}\right\}$. Y lo más importante: Cómo interpretar estos combinatorials?.

Definición: $\textrm{supp}(c)$ es un conjunto de coordenadas de cero bits en $c$.

Answer 1

La pregunta es difícil de entender, con un montón de centrarse en una cantidad $2p$ que dices es irrelevante, y crucial falta de información. Usted no introducen $w$$k$, por lo que sólo puede ser conjeturado que $w=|I|$$k=|\operatorname{supp}(c)|$. Bajo la suposición adicional de que $c$ es uniformemente al azar de todos los vectores con $k$ no-bits cero, la expresión

$$ \frac{\binom wu\binom{n-w}{k-u}}{\binom nk} $$

da la probabilidad de $c$ tener exactamente $u$ cero los bits de $I$ como el cociente entre el número de posibilidades de elección de $u$ $w$ bits en $I$ $k-u$ $n-w$ bits fuera de $I$ a ser distinto de cero para el número total de posibilidades de elección de $k$ $n$ bits a ser distinto de cero.