Problema de optimización de una paridad de verificación de código

Question

He a $n$ bloques de datos y $k$ bloques de paridad distribuida a través de $m$ cuadros donde cada caja puede contener atmost $b$ bloques. Cada bloque de paridad es Ex-o de algunos de los bloques de datos (para facilidad de comprensión que puede asumir cada uno de los datos/bloque de paridad como un único bit) y cada bloque de datos está involucrado en al menos un Ex-o la operación para obtener algún bloque de paridad. Cada bloque de datos puede estar involucrado en más de un bloque de paridad de la operación, de hecho, va a ser lo que va a aumentar la tolerancia a errores del código. Por lo tanto, tenemos $k$ paridad de ecuaciones de la siguiente manera:

$$\begin{aligned} P_1 &= D_{11} \oplus D_{12} \oplus \cdots \\ \;\vdots \\ P_k &= D_{k1} \oplus D_{k2} \oplus \cdots \end{aligned}$$

Ahora bien, si algunos de datos o bloque de paridad falla y no podemos recuperar los datos perdidos cuadras de la no-error de datos/paridad bloques llamamos a esta situación un "dataloss" de la situación. Ahora, voy a dar un ejemplo sencillo para explicar esto. Supongamos que tenemos $4$ bloques de datos y $3$ bloques de paridad, donde la paridad de ecuaciones es la siguiente: $$\begin{aligned} P_1 &= D_{1} \oplus D_{3} \oplus D_{4}\ \\ P_2 &= D_{1} \oplus D_{2} \oplus D_{3}\ \\ P_3 &= D_{2} \oplus D_{3} \oplus D_{4} \end{aligned}$$

Los representamos por una matriz llamada generador de la matriz, que es un $4$x$7$ matriz, la cual es como sigue:

$$ G=\left(\begin{array}{ccccccc} 1&0&0&0&1&1&0\\ 0&1&0&0&0&1&1\\ 0&0&1&0&1&1&1\\ 0&0&0&1&1&0&1 \end{array}\right) $$

Ahora, supongamos que $D1$,$D2$,$D3$ se produce un error y queremos comprobar si las causas dataloss. Así, eliminamos las columnas correspondientes a $D1$,$D2$,$D3$ a partir de G y llamar a la matriz obtenemos una "matriz para la recuperación", que es

$$ G'=\left(\begin{array}{cccc} 0&1&1&0\\ 0&0&1&1\\ 0&1&1&1\\ 1&1&0&1 \end{array}\right) $$ aquí. Ahora, tendremos que comprobar el rango de $G'$. Si este es menor que $n$, luego tenemos a $dataloss$, de lo contrario no. Aquí $rank$(G')=4 e $n$=4 y no tenemos ninguna $dataloss$. Básicamente, si nos Ex-o $P1$,$P2$,$P3$ entonces podemos recuperar $D3$, desde el que podemos recuperar $D1$,$D2$.

Datos/paridad de bloque de falla si y sólo si la caja que contiene falla y si un cuadro de falla, todos los datos y bloques de paridad dentro de falla. Ahora queremos formular el siguiente problema de optimización:

Dado $n$, $k$, $m$ y el $k$ paridad de ecuaciones (no se nos permite elegir que los bloques de datos son xor para formar un bloqueo de verificación, se nos da una borradura de código de sistema) queremos una asignación de la disco y bloques de paridad a través de $m$ cajas de tal manera que podamos minimizar el número de casos en los que un cuadro de las causas de la falla "dataloss"; i.e quiero minimizar la función $G=\sum_{i=0}^m\;g(i)$, donde

$$g(i) = \begin{cases} 1 & \text{if failure of box }i\text{ causes "dataloss"} \\ 0 & \text{otherwise} \end{casos}$$

Ahora la asignación de disco/bloques de paridad a través de $m$ cajas puede ser representado por una matriz de dimensión $(n+k) \times m$, vamos a llamarlo $B$. El $(i,j)$-ésima de la matriz es $1$ si $j$-th caja contiene $i$-ésimo bloque de datos ($(i-n)$-ésimo bloque de paridad) por $i \le n$ ( $i>n$ ), de lo contrario es $0$. Así, la función de $G$ es una función de todos los de la matriz de entradas y de las limitaciones que tenemos son:

1. cada matriz de entrada es 0 o 1
2. suma de las entradas en una fila es siempre 1 (i.e cada uno de los datos/paridad bloque está presente en exactamente un cuadro)
3. la suma de las entradas en cada columna es de al menos 1 (es decir, sin caja está vacía)
4. la suma de todas las entradas de la matriz es $n+k$

Ahora, la función de $G$ viene como una función no lineal de la matriz de entradas. Además, el dominio conjunto de $G$ es el conjunto de todos los $n$-tuplas cuando los elementos de una tupla son 0 o 1. Así, el conjunto de dominios no es un conjunto convexo, de forma convexa de las técnicas de optimización no se puede aplicar aquí. ¿Cómo resolver este problema de optimización?

Si me refinar problema como este: ¿cuánto de la $n+k$ bloques pueden ser cubiertos con m de cada uno de los subconjuntos de tamaño atmost b, entonces creo que es posible formular como un conjunto independiente máximo problema. Vamos a formar un grafo de n+k vértices donde cada vértice corresponde a un bloque(datos/paridad), pero la definición de los bordes no está claro para mí (este es el principal problema que estoy tratando de resolver). A continuación, el máximo conjunto independiente de este gráfico, que nos dará la máxima subconjunto (de la n+k columnas) que pueden ser cubiertos.

De alguna manera siento que el problema es NP-Completo.

Espero haber descrito el problema con claridad.

======

Editar (comentario de Jyrki Lahtonen): Esta información también fue publicada en el MO. Me intenta redirigir eventual interesado MO-carteles aquí, porque por el momento creo que tenemos una mejor descripción de la pregunta aquí.

Answer 1

Lo siento para agregar otra respuesta, pero siento que mi primera respuesta contiene aclaraciones correspondientes a la definición del problema, así que creo que mantener separados se justifica. También la otra respuesta es ya tanto tiempo que la edición es dolorosamente lento, dado que la vista previa de representador es comer de todos los ciclos.

En mi humilde opinión, la única meta que vale la pena aquí es que nunca sucede que la pérdida de un solo cuadro de resultados en la pérdida de datos. Si usted no puede tolerar la pérdida de un solo cuadro, usted necesita ingeniero esa caja en particular para ser infalible, y por lo tanto puede mantener todos los datos allí. Ok, usted puede dar un poco de peso a la parcial recuperación de datos, pero no la pido, y luego, definitivamente, necesitamos saber más sobre el borrado de código de recuperación.

Aquí está mi primera sugerencia. El buen viejo algoritmo voraz. Primera aleatorizar el orden de las $n+k$ datos y verificación de los bloques (no es necesario, pero quiero añadir un no-determinista elemento), por lo que hemos bloques de $b_1,b_2,\ldots,b_{n+k}$. El algoritmo va a asignar a cada uno y cada uno de estos a una de las casillas de la siguiente manera.

1. Inicializar $j=1$. Inicializar la lista de asignar los bloques de la lista $b_1,\ldots,b_{n+k}$.
2. Inicializar el cuadro de $\#j$ a estar vacío. Inicializar un puntero $p$ punto para la primera entrada en la lista de sin asignar bloques.
3. Comprobar si la adición de la cuadra señalado por $p$ cuadro $\#j$ viola el rango de condición o no (eliminación gaussiana no esta en el polinomio de tiempo). Si no lo hace, a continuación, asignar el bloque de la caja de $\#j$, avanzar el puntero $p$ y quitar ese bloque de la lista de sin asignar bloques.
4. Si el cuadro de $\#j$ es completa, o el puntero $p$ fue más allá al final de la lista, a continuación, vaya al paso 5. De lo contrario, vaya al paso 3.
5. Si se han asignado todos los bloques de datos de salir con éxito. De lo contrario, el incremento de $j$. Si usted está fuera de los cuadros de salida con el fracaso. De lo contrario, vaya al paso 2.

Si una orden aleatorio no funciona, pruebe con otro.

A mí me parece que la complejidad de este polinomio es de $n+k$. Sale correctamente, si encuentra una asignación del tipo deseado. Usted también puede querer dejar el número de cajas abiertas, en cuyo caso el algoritmo siempre tiene éxito, pero también debe de salida el número de cajas necesarias.

Pero supongo que usted (o alguien en su equipo) ya han probado este. ¿Qué tiene de malo? Ninguna prueba? Tendría que tener un (de forma heurística) razón justificable para preferir un orden aleatorio sobre otro?

Answer 2

El OP también ha publicado este problema en StackOverflow y aclarado en los Comentarios allí.

La Pregunta puede ser encuadrada como una combinatoria. Dado un "universo" set $S$ del tamaño de la $n$, considere la posibilidad de una colección de $A$ de los subconjuntos de a $S$ que consiste en la $n$ singleton subconjuntos junto con $k$ adicional (distinto) de subconjuntos de tamaño, al menos, dos. Por lo tanto $|A| = n+k$.

Entonces se le pidió a la partición de $A$ utilizando en la mayoría de las $m$ de partes y piezas de tamaño en la mayoría de las $b$ donde $mb \ge n+k$. El objetivo es encontrar una partición en la que, como algunas de las partes como sea posible tener una cierta propiedad, que Prasenjit se refiere como "crítico". Esto motiva la definición:

Un subconjunto $B$ $A$ tiene la propiedad C iff el álgebra Booleana generado por $A \backslash B$ es una subalgebra de $\mathscr{P}(S)$.

Un poco de reflexión debe convencer al lector de que el punto de ajuste de condición por encima de las cantidades para el criterio Prasenjit da para la eliminación de las columnas de generador de matriz$G$, resultando en una matriz de rango inferior a $n$.

Prasenjit la pregunta entonces es: teniendo en cuenta todas las particiones de $A$ tener en la mayoría de las $m$ piezas de mayor tamaño $b$, ¿cuál es el menor número posible de partes que tienen la propiedad de C.

Mi sugerencia es determinar cuánto de $A$ pueden ser cubiertos por en la mayoría de las $m$ subconjuntos $B$ del tamaño en la mayoría de los $b$ no tener la propiedad de la C. Puesto que la condición de no tener propiedad C es cerrado bajo tomando subconjuntos de una cubierta siempre puede ser refinado para una partición sin piezas de tener la propiedad de la C. Si es posible, esto podría alcanzar un mínimo.

Si no es posible, al menos una parte que tiene la propiedad C sería necesario.

Ya que todas las $k$ no singleton pone en $A$ forma un subconjunto no tener la propiedad C, es sólo un singleton conjunto en $A$ que podría ser imposible incluir en un "bloque" $B$ (subconjunto de $A$ del tamaño en la mayoría de los $b$) no tener la propiedad de la C.

Sin embargo, el parámetro de $m$ podría ser especificada tan bajo que incluso a pesar de que cada conjunto en $A$ está incluido en un "bloque" de no tener la propiedad C, sin embargo es imposible cubrir todos los $A$ sólo con $m$ dichos bloques. Este sería el caso si $m=1$, aunque luego sería claro que el número mínimo de bloques con propiedad C requerida es de 1.

Answer 3

Esto es demasiado largo para un comentario, pero tengo que pedir esto para obtener/dar una mejor idea del problema de configuración. No puedo decir seguro, pero basado en mi exposición a los problemas relacionados con el creo que se ve como el siguiente: Si el $n\times (n+k)$ de la matriz binaria que describe la presencia de un bloque de datos, de datos o un bloqueo de verificación es$A$, $A$ $I_n$ bloque de la izquierda (bloque de datos $D_i$ copiado a su propio bloque) y, a continuación, un "random" (o cuidadosamente diseñado) $n\times k$ binario bloque de $B$ nos dice que los bloques de datos son XORed de forma que la comprobación de bloque: una columna por bloqueo de verificación, por lo que una entrada '1' en una fila $i$ y la columna $j$ de la matriz $B$ dice que el bloque de datos $\#i$ está entre los XORed para formar bloqueo de verificación de $\#j$.

Ahora la distribución de dichas $n+k$ bloques de datos en los cuadros de cantidades a la partición de las columnas de la matriz $A$ a $m$ subconjuntos. AFAICT se produce pérdida de datos, si y sólo si la eliminación de las columnas pertenecientes a la caja en cuestión nos deja con una matriz de $A'$ que no es de rango completo $n$. Esto es debido a que, si la matriz $A'$ es de rango completo, se podría seleccionar un subconjunto de a $n$ columnas linealmente independientes. Como se forma una matriz invertible, la recuperación de los datos se podría hacer (por ejemplo, mediante la eliminación Gaussiana).

Es esto lo que tienes en mente? Esto parece estar estrechamente relacionada con la supresión de corrección y recuperación de códigos, y usted puede beneficiarse del uso de que como una palabra de moda, cuando la búsqueda de más información.

Antes de ponerse serio, voy a describir un juguete ejemplo de lo anterior. Vamos $$ A=\left(\begin{array}{ccccccc} 1&0&0&0&1&1&0\\ 0&1&0&0&0&1&1\\ 0&0&1&0&1&1&1\\ 0&0&0&1&1&0&1 \end{array}\right) $$ se esta matriz que algunos de ustedes se reconocen como generaotr de la matriz de la $[7,4,3]$ código de Hamming. Aquí las últimas 3 columnas decir que el primer bloque está construido por XORring de datos de los bloques 1, 3 y 4, la segunda comprobación de bloque por XORring bloques de datos de 1,2,3 y la última comprobación de bloque por XORrin bloques de datos 2,3,4.

Afirmo que en este caso el uso de $m=3$ cuadros nos permite siempre recuperarse de la pérdida de un solo cuadro. Poner los datos de los bloques 1,2 en el primer cuadro; bloques de datos de 3,4 en la segunda casilla; y todos los bloques en la tercera casilla. Si perdemos el tercer cuadro, entonces es obvio que tenemos todos los datos en el tacto. Si perdemos el primer cuadro, entonces podemos recuperar los datos de bloque #1 por XORring el primer bloque con los datos de los bloques 3 y 4, y del mismo modo podemos recuperar datos de bloque #2 por XORring la última comprobación de bloque con los datos de los bloques 3 y 4. De igual manera, si perdemos el segundo cuadro, entonces podemos recuperar los datos perdidos de los bloques 3 y 4 usigng la guarda de verificación de bloques y el guardado de los datos de los bloques 1 y 2.

Debido a que este código binario mínimo de la distancia de Hamming 3, se puede recuperar a partir de cualquiera de los dos borrones. Por lo tanto, yo sabía de antemano que me woudl ser capaz de recuperar la pérdida de contenido de cualquiera de los dos primeros cuadros.

Por favor comente. Me doy cuenta de que usted podría estar buscando un enfoque diferente. Puede ser uno de los más sencillos en los programas de recuperación?