Lectura en la memoria de PIC32MX en C y XORing grandes conjuntos de datos

2

Tengo un proyecto en el que tengo 102 registros de cambio PISO de 8 bits en configuración en cadena y están enviando a una línea SDI común conectada a un controlador PIC32MX.

Hay un total de 816 bits que necesito leer y almacenar en la memoria para poder manipular los datos que se están leyendo. Además, tendré que leerlas 34 veces porque la aplicación requiere que I XOR esos 816 bits para cada una de estas operaciones de lectura.

Tengo dos preguntas:

  • ¿Cómo almacenarías los datos? Estoy preocupado porque tendré un poco de datos para manejar y estoy tratando de optimizar el procesamiento al mínimo. Tenga en cuenta que necesito poder extraer los índices (fila, columna) para poder calcular otros valores en consecuencia.
  • Después de XORAR los datos, necesitaré atravesar la estructura y encontrar ocurrencias de '0'. ¿Qué sugieres en términos de algoritmo de búsqueda?

Estaba pensando en crear una matriz con [34,816] dimensión y XOR secuencialmente las filas en una única matriz de 816 columnas y luego buscar '0' en la matriz, pero no estoy seguro de cómo hacerlo, cualquier idea ?

    
pregunta Joum

1 respuesta

3

Para procesar los bits lo más eficientemente posible, querrá mantenerlos agrupados en palabras de 32 bits donde sea que tenga sentido. 816 bits son 25.5 palabras, lo que realmente no está nada mal.

Para buscar los más eficientemente, divida la tarea en dos pasos: Verifique que las palabras completas no sean cero en el bucle externo, luego busque bits individuales en las palabras que no son totalmente cero en el bucle interno.

Un truco que se puede usar para aislar bits individuales en una palabra que tiene varios bits establecidos es para Y la palabra con su negación (complemento de 2). El resultado tiene solo un bit establecido: el 'uno' más a la derecha en la palabra original. Luego puede usar este resultado para borrar ese bit y buscar el siguiente 'uno'.

En C:

temp = word & -word;
word &= ~temp;

Por ejemplo, suponga que su palabra de 32 bits contiene 0x40010080:

01000000000000010000000010000000  original word
10111111111111101111111110000000  ... negated
00000000000000000000000010000000  ... and then ANDed together

11111111111111111111111101111111  complement of previous word
01000000000000010000000000000000  ... ANDed with original word for next iteration

EDIT:

La eficiencia de este algoritmo proviene del hecho de que solo se itera una vez para cada "uno" (tres de ellos en este ejemplo), en lugar de una vez para cada uno de los 32 bits de la palabra. Esta es una gran ventaja si estás haciendo algo como simplemente contar el de uno. El inconveniente es que no le da el índice de bits directamente, pero también hay formas de acelerarlo. Por ejemplo, para obtener el índice de bits de un solo bit establecido en una palabra, podría usar un algoritmo de codificación binaria:

index = 0;
if (word & 0xAAAAAAAA) index += 1;
if (word & 0xCCCCCCCC) index += 2;
if (word & 0xF0F0F0F0) index += 4;
if (word & 0xFF00FF00) index += 8;
if (word & 0xFFFF0000) index += 16;

La ventaja general de los dos algoritmos anteriores, en comparación con una iteración de fuerza bruta a través de los bits, depende de cuántos bits espere encontrar en cada palabra. Si son raros (menos de aproximadamente 4 por palabra), estos algoritmos deberían ser más rápidos. Si son más comunes que eso, simplemente ve con el ciclo iterativo:

for (index = 0, mask = 0x00000001; index < 32; ++index, mask <<= 1) {
  if (word & mask) {
    /* do your processng here */
  }
}
    
respondido por el Dave Tweed

Lea otras preguntas en las etiquetas