¿Cómo funciona el ECC (códigos de corrección de errores) para la corrección de errores de ráfaga (estilo de unidad de disco)?

Es una maldición o una bendición, pero a menudo mi cerebro intenta resolver problemas técnicos en mis sueños. A veces lo hace. Al igual que la noche anterior, mi cerebro exigió entender cómo diseñar un algoritmo ECC (programa de software pero eventualmente circuitos FPGA eventualmente) para implementar el tipo de ECC apropiado para las unidades de disco. El tipo de ECC apropiado para estos dispositivos parece ser "detección de errores de ráfaga".

Como entiendo esto, la razón por la que las unidades de disco tienen errores se debe a imperfecciones en la superficie del disco (especificaciones o arañazos). Cuando la cabecera está leyendo bits de datos y pasa sobre un rasguño estrecho, el circuito genera una mezcla aleatoria de valores de bit correctos y erróneos sobre una "ráfaga" de quizás 1 a 64 bits ish. Por lo tanto, como lo entiendo, el objetivo de la unidad de disco ECC es poder corregir todos los bits erróneos en cualquier ráfaga aleatoria de errores.

Por cierto, naturalmente, no "pienso en matemáticas", ¡así que no me apuntes a los trabajos de matemáticas! Ya pasé un par de horas tratando de leer en wikipedia sobre reed-solomon y varios otros esquemas, pero las matemáticas en esos artículos son completamente incomprensibles para mí (a menos que me quede unas semanas estudiándolas ... si tengo suerte). Además, en el texto, no creo que ninguno de esos esquemas se aplique a las unidades de disco (pero quizás a los CD / DVD).

De todos modos, describiré lo que mi cerebro soñó mientras dormía y le pediré a alguien que me explique cómo se debería hacer este tipo de ECC y cuánto mejor son los enfoques convencionales. Estoy seguro de que mi esquema debe ser menos eficiente que una técnica hecha por alguien que sabe lo que está haciendo, y tal vez incluso diseñada mientras estaban despiertos. Antes de despertar, estaba tratando de averiguar cómo manejar dos ráfagas por pista, pero me desperté derrotado. Así que también pregunto cómo lograr eso.

Mi imagen mental era un sector de 4096 bytes, que dividí mentalmente en 512 fragmentos de 64 bits cada uno (ya que estoy acostumbrado a pensar en fragmentos de 64 bits, y porque supongo que las ráfagas de errores de 64 bits son suficientes) En mi aplicación, cada flujo de datos será definitivamente de 4096 a 8192 bytes.

Mi enfoque es calcular diez códigos ECC de 64 bits a partir de los 4096 bytes de datos. Entonces el ECC que mi esquema escribiría después de que el último de los 4096 bytes de datos sea diez código de 64 bits == 80 bytes, lo que es poco menos del 2% de sobrecarga. Llamaré a esos diez códigos ECC de 64 bits "código 0" a "código 9", cada uno de los cuales comienza en cero antes de que se procese cada sector. Y a cada secuencia de datos de 64 bits (8 bytes) llamaré un "fragmento" por falta de un término mejor.

code9 = XOR chunks 000 to 511 == 000 to 1FF : every chunk
code8 = XOR chunks 256 to 511 == 100 to 1FF : every chunk # with bit #8 == 1
code7 = XOR chunks 128 to 255 == 080 to 0FF : every chunk # with bit #7 == 1
        and chunks 384 to 511 == 180 to 1FF
code6 = XOR chunks 064 to 127 == 040 to 07F : every chunk # with bit #6 == 1
        and chunks 192 to 255 == 0C0 to 0FF
        and chunks 320 to 384 == 140 to 17F
        and chunks 448 to 511 == 1C0 to 1FF
code5 = XOR chunks 032 to 063 == 020 to 03F : every chunk # with bit #5 == 1
        and chunks 096 to 127 == 060 to 07F
        and chunks 160 to 191 == 0A0 to 0BF
        and chunks 224 to 255 == 0E0 to 0FF
        and chunks 288 to 319 == 120 to 13F
        and chunks 352 to 383 == 160 to 17F
        and chunks 416 to 447 == 1A0 to 1BF
        and chunks 480 to 511 == 1E0 to 1FF
code4 = XOR chunks 016 to 031 == 010 to 01F : every chunk # with bit #4 == 1
        and chunks 048 to 063 == 030 to 04F
        and chunks 080 to 095 == 050 to 07F
        and so forth
code3 = XOR chunks 008 to 015 == 008 to 00F : every chunk # with bit #3 == 1
        and chunks 024 to 031 == 018 to 01F
        and chunks 040 to 047 == 028 to 02F
        and so forth
code2 = XOR chunks 004 to 007 == 004 to 007 : every chunk # with bit #2 == 1
        and chunks 012 to 015 == 00C to 00F
        and chunks 020 to 023 == 014 to 017
        and so forth
code1 = XOR chunks 002 to 003 == 002 to 003 : every chunk # with bit #1 == 1
        and chunks 006 to 007 == 006 to 007
        and chunks 010 to 011 == 00A to 00B
        and so forth
code0 = XOR chunks 001 to 001 == 001 to 001 : every chunk # with bit #0 == 1
        and chunks 003 to 003 == 003 to 003
        and chunks 005 to 005 == 005 to 005
        and so forth

Bien, debería explicar el propósito de este enfoque. El ECC producido por el algoritmo debe codificar de alguna manera la siguiente información:

# 1: ¿Cuál es el estado correcto de cada bit (todos 4KB == 32Kb)?

# 2: ¿Dónde en el flujo de 4KB == 32Kb ocurrió la ráfaga de error?

Ahora intentaré explicar por qué mi sueño (¿pesadilla?) Creía que estos diez códigos ECC de 64 bits pueden detectar cualquier ráfaga de bits de error de hasta 64 bits en cualquier lugar en el flujo de 4KB == 32Kb.

Empecemos despacio y consideremos un ejemplo simple. Supongamos que cuando la unidad de disco lee un sector, el bit # 0 en uno de los 512 "fragmentos" estaba equivocado == invertido.

¿El código ECC9 nos dice algo? Bueno, code9 es un XOR de cada fragmento de 64 bits en el sector. Por lo tanto, el bit # 0 de code9 es la paridad del bit # 0 de cada fragmento de datos de 64 bits escritos en el sector. Por lo tanto, cuando volvemos a leer el sector, un error en el bit # 0 de CUALQUIER fragmento de datos de 64 bits generará un error que podemos detectar solo con el código9 de 64 bits (no hay necesidad de código8, código7 ... código0) . Si el bit # 0 de cualquier fragmento de datos de 64 bits es incorrecto, entonces el bit # 0 de code9 en la lectura ECC del disco no estará de acuerdo con el bit # 0 de code9, ¡lo calcularemos a partir de los datos de lectura!

¡Bonito! Detectamos un error en el bit # 0 de algunos fragmentos de 64 bits con solo code9. Sin embargo, no tenemos idea de cuál de los 511 fragmentos de datos contiene un error en su bit # 0.

Para eso son los otros ocho códigos ECC (en cierto modo).

Los otros ocho códigos ECC nos permiten "reducir" dónde está este error.

Entonces nos preguntamos, ¿qué nos puede decir code8? Bueno, eso es totalmente obvio! code8 solo considera los fragmentos 256-511 (última mitad del sector), por lo que si el error del bit # 0 se encuentra en cualquier lugar entre los fragmentos 000-255 (primera mitad del sector), code8 no detectará ningún error. ¡Pero espera! Si sabemos que el error en el bit # 0 NO está en los fragmentos 256-511, entonces DEBE ESTAR en algún lugar en los fragmentos 000-255 (primera mitad del sector). Así que ahora sabemos que el error está en algún lugar en el fragmento 000-255, y no en el fragmento 256-511. ¡Excelente!

Ahora nos preguntamos, ¿qué nos puede decir code7? Bueno, de la región que nos interesa (trozos 000-255), code7 solo verifica los trozos 128-255. Entonces, si el bit # 0 del código7 ECC que leemos del disco difiere del código 7 ECC que calculamos a partir de los datos de lectura, sabemos que el error del bit # 0 está en algún lugar en el fragmento 128-255. ¡Dulce! Nuevamente, cortamos la posible ubicación del error a la mitad del rango.

Ahora, ¿qué nos puede decir code6? Cómo funciona esto se está volviendo obvio. Como antes, el código 6 solo detecta errores en la mitad de la región en la que sabemos que está el error. De la región en la que redujimos el error a (fragmentos 128-255), el código 6 solo verifica la segunda mitad (fragmentos 192-255). Entonces, cuando no encontramos ningún error en el bit # 0 del código 6, sabemos que el error del bit # 0 no está en los fragmentos 192-255, y por lo tanto debe estar en algún lugar en el fragmento 128-191.

Cuando encontramos un error en el bit # 0 del código 5, sabemos que el error debe estar en algún lugar en los fragmentos 160-191.

Cuando encontramos un error en el bit # 0 del código 4, sabemos que el error debe estar en algún lugar en los fragmentos 176-191.

Cuando encontramos un error en el bit # 0 de code3, sabemos que el error debe estar en algún lugar en los fragmentos 184-191.

Cuando no encontramos NINGÚN error en el bit # 0 del código 2, sabemos que el error debe estar en algún lugar en los fragmentos 184-187.

Cuando no encontramos NINGÚN error en el bit 0 del código 1, sabemos que el error debe estar en algún lugar en los fragmentos 184-185.

Cuando encontramos un error en el bit # 0 del código 0, sabemos que el error debe estar en el fragmento 185.

!!!!! HECHO !!!!!

Ahora sabemos exactamente dónde está el error en nuestro sector de 4096 bytes, en el bit # 0 del fragmento # 64 de 64 bits.

Y el pedazo 185 == 0x0B9 == 0 1011 1001

Hmmm ¡Muy interesante! Cada bit cero en el fragmento # del error es un código # donde nosotrosNo encuentre un error, y cada bit en la parte # del error es un código # dondehizo encontrar un error Lo que significa que, automáticamente, obtenemos el fragmento # que contiene el error en el proceso de verificación de los fragmentos de código. Cuando un bit en la lectura de ECC coincide con el mismo bit en la ECC que calculamos a partir de los datos de lectura, generamos un 0, de lo contrario generamos un 1 (lectura-ECC-ECC computada-ECC). ¿Qué tan simple es eso? !!!

Con un poco de reflexión adicional, vemos que cada bit # en los fragmentos de datos y ECC esindependiente. En otras palabras, el bit # 0 en los fragmentos de ECC está comprobando el bit # 0 de cada fragmento de datos de 64 bits, mientras que el bit # 1 en los fragmentos de ECC está verificando el bit # 1 de cada fragmento de datos de 64 bits, y así sucesivamente . Los bits adyacentes en los valores ECC y los fragmentos de datos son completamente independientes entre sí. Ningún bit más cercano al de 64 bits interactúa de ninguna manera. Este esquema trata un sector como 64 sectores separados, cada uno de ellos solo 1/64 como grande.

Jajaja Esta debe ser la razón por la que esta técnica puede detectar y corregir cualquier ráfaga de bits de error de hasta 64 bits de longitud, ya que cada bit es completamente independiente (en los fragmentos de ECC) desde cualquier bit más cercano a 64 bits.

Eso es. Al menos en mi estado de sueño, eso explica cómo funciona esto.

Lo que no se explica arriba es lo siguiente (mis preguntas):

# 1: ¿Es así como se realiza la ráfaga de ECC en las unidades de disco, etc.?

# 2: Si esta técnica no es convencional, ¿es nueva esta técnica?

# 3: ¿Es esta técnica más fácil para el software que las técnicas convencionales?

# 4: ¿Las rutinas convencionales tienen más o menos gastos generales (1.8% para ráfagas de 64 bits en paquetes 4K)?

# 5: ¿Cómo se puede extender esto para corregir dos ráfagas?

PD: mi aplicación para ECC no está relacionada con las unidades de disco, pero tiene características y requisitos similares. Al menos inicialmente, mi aplicación haría todo en software: calcular ECC en software, agregarse al flujo de datos (paquete), enviar el flujo de datos (paquete), recibir el flujo de datos (paquete) y realizar el proceso anterior para detectar y corregir cualquier error en el flujo de datos (paquete). Supongo que esto también podría convertirse en un circuito en un FPGA algún día, pero ... hoy no.