Sistema polinomial de Reed-Solomon Reed-Solomon es un código cíclico no binario. Los códigos cíclicos son una subclase de los códigos de bloque estándar de detección y corrección de errores que protege la información contra errores en los datos transmitidos sobre un canal de comunicaciones. Este tipo de código pertenece a la categoría FEC, Forward Error Correction, es decir, corrige los datos alterados en el receptor y para ello, utiliza unos bits adicionales que permiten esta recuperación a posteriori.
En la actualidad los códigos Reed-Solomon se utilizan para corregir errores en varios sistemas incluyendo los dispositivos de almacenamiento, como lo son cintas, discos compactos, DVD, códigos de barras o bien en comunicaciones inalámbricas o móviles, teléfono celular, enlaces de microondas o en modem de alta velocidad como ABSL. Ejemplo de aplicación. Aquí se presenta un método en implementación de envío de mensajes con imágenes, donde la imagen enviada es recibida y la extensión de la misma es leída. Entonces se aplica la corrección en toda la extensión del mensaje, donde el contenido total del mensaje es dividido entre 100 y multiplicado por los bloques de corrección en toda la extensión, obteniendo así el contenido correcto del mensaje original. Para seguir con el tema es necesario hablar sobre los códigos de bloque.
Los códigos de bloque son técnicas utilizadas para transformar un conjunto de datos binarios n en otros un poco más largos k, donde se agregan unos bits de más para dar redundancia al código saliente k, donde k es mayor a n. El número de dígitos de comprobación de redundancia será m igual a k menos n, donde m son la cantidad de dígitos adicionados. Propiedades de los códigos Reed-Solomon Un código Ritz-Solomon se especifica como RSNK con símbolos de S-bits.
Lo anterior significa que el codificador toma K símbolos de los S-bits y añade símbolos de paridad para hacer una palabra de código de N símbolos. Existen N-K símbolos de paridad de S-bits cada uno. Un decodificador puede corregir hasta T símbolos que contienen errores en una palabra de código, donde 2T igual a N-K.
Ejemplo Un código popular Ritz-Solomon es RS-255223 con símbolos de 8 bits. Cada palabra de código contiene 255 bytes de palabra de código, de los cuales 223 bytes son datos y 32 bytes son paridad. Para este código se tiene N igual a 255, K igual a 223, S igual a 8, 2T igual a 32 y T igual a 16. El decodificador puede corregir cualquier error de 16 símbolos en la palabra de código, es decir, errores de hasta 16 bytes en cualquier lugar de la palabra pueden ser automáticamente corregidos. Especificación, para usar RIT Solomon pones tus datos en una matriz. Para archivos de computadora cada elemento de la matriz es un byte del archivo.
Los bytes se disponen en una cuadrícula para formar una matriz. de datos tiene este mensaje abcdefg hijklmnop puede distribuirlo así en este ejemplo las cuatro partes del archivo tienen una longitud de 4 bytes cada pieza es una fila de la matriz el primero es abcd el segundo es efgh y así el algoritmo de ritz solomon crea una matriz de codificación que lo multiplicas con su matriz de datos para crear los datos codificados El resultado es una matriz con dos filas más que la original. Estas dos filas son las piezas de paridad.
Y cabe mencionar que estos números 51, 52, 53, 49 y 55, 56, 57 y 25 son números reservados por algoritmos para matrices de 4x4. Método para codificar mensaje. Para esto se puede tomar un mensaje, dividirlo en n piezas, agregar k piezas de paridad y luego reconstruir el original a partir de n de las n más k piezas. En este caso aplicaremos Rich Solomon al mensaje estoy estudiando con doble o.
Esto es que se le aplico una o al último porque estoy estudiando abarca 15 casillas y nosotros necesitamos hacer una matriz obviamente cuadrada que en este caso es 4x4. Entonces agregamos. una letra más para tener 16 casillas.
Recordando que matriz de codificación por matriz de mensaje original es igual a la matriz de paridad, siempre respetando que cada 11 secciones de la matriz contenga 4 casillas. Ahora bien, aplicando la multiplicación de matrices respecto a nuestra matriz original, obtenemos la matriz para codificar, la cual tiene 24 casillas. En sus últimas dos filas agregadas se presentan números 12, 14, 1B y 1C en hexadecimal.
Estos nacen a partir de las fórmulas que son predefinidas por algoritmo para matrices de 4x4. Entonces explicaré cómo se crea el número 12. La primera fórmula dice 12 hexadecimal equivale a 18 decimal. Entonces esto equivale a 12 hexadecimal menos 1. Entonces tenemos 18 casillas decimal. Son 4, 8, 12, 16, 17, 18. Menos 1 y cambio por cruza.
Entonces ahí quedan los dos números 12. Ahora para el 14 de exedecimal, equivale a 20 de decimal. Y esto quiere decir que la fórmula 14 de exedecimal más 1. Tenemos 4 casillas. 8, 12, 16, 17, 18, 19 y 20. Más 1 y cambio por cruza.
Entonces tenemos el 14 de decimal. Ahora para el 1B. 1b hexadecimal equivale a 27 decimal, esto quiere decir que 1b hexadecimal menos 1 por renglón de paridad más 1. Entonces, 4, 8, 12, 16, 20, 24 casillas totales de la matriz más 3 que tenemos de tolerancia menos 1 por renglón de paridad que viene siendo 1 por 4, 4. Entonces 27 menos 4, 23 más 1. Tenemos el 1B y cambio por cruza. Entonces tenemos el 1B en su lugar.
Ahora el 1C hexadecimal. Equivala a 28 decimal. Entonces esto quiere decir que 1C hexadecimal menos 2 por renglón de paridad. 4, 8, 12, 16, 20, 24. Más 4 que tenemos de tolerancia.
Menos 2 por 4 que equivale a las casillas de renglones de paridad. Tenemos la casilla 20. y cambio por cruza de esta manera concordamos que nuestros números están en sus casillas correctas así es como obtenemos nuestra matriz para codificar posteriormente multiplicamos la matriz por codificar por la matriz del mensaje original obteniendo nuestra matriz codificada método para decodificar mensaje Cada fila de la matriz de codificación produce una fila de resultado, entonces cada fila de la matriz de codificación hace una de las piezas resultantes del archivo. Debido a que las filas son independientes, se pueden tachar dos de las filas de cada matriz y la ecuación aún se mantiene.
La matriz de la izquierda es invertible. Hay una matriz inversa que, cuando se multiplica por la matriz de codificación, produce la matriz de identidad. Como en el álgebra básica, en el álgebra matricial puedes multiplicar ambos lados de la ecuación por la misma cosa.
En este caso, multiplicaré a la izquierda por la matriz de identidad. Como se muestra en la imagen, matriz inversa por matriz para codificar por matriz original es igual a la matriz inversa por la matriz codificada. Nosotros podemos simplificar de esta manera eliminando matriz inversa por matriz para codificar, obteniendo que la matriz original es igual a la matriz inversa por la matriz codificada, obteniendo el mismo resultado al método anterior, de una manera más rápida y con menos pasos. Entonces, para hacer una matriz de decodificación, el proceso consiste en tomar la matriz de codificación original, tachar las filas de las piezas faltantes y luego encontrar la matriz inversa.
Luego se puede multiplicar la matriz inversa y las piezas disponibles para reconstruir los datos originales. Aplicando nuestro ejemplo, la matriz para codificar por la matriz codificada, ambas, eliminando sus filas medias. Después invertimos la matriz.
Posteriormente multiplicamos la matriz inversa por la matriz codificada. Obteniendo el mensaje decodificado. A continuación les presento algunos sitios web para reforzar este aprendizaje, donde se muestran códigos Rift Solomon implementados en programación.