La codificación de longitud de ejecución limitada o RLL es una técnica de codificación de línea que se utiliza para enviar datos arbitrarios a través de un canal de comunicaciones con límites de ancho de banda . Los códigos RLL se definen mediante cuatro parámetros principales: m , n , d , k . Los dos primeros, m / n , se refieren a la velocidad del código, mientras que los dos restantes especifican el número mínimo d y máximo k de ceros entre unos consecutivos. Esto se utiliza tanto en sistemas de telecomunicaciones como de almacenamiento que mueven un medio más allá de un cabezal de grabación fijo . [1]
En concreto, RLL limita la longitud de los tramos (recorridos) de bits repetidos durante los cuales la señal no cambia. Si los tramos son demasiado largos, la recuperación del reloj es difícil; si son demasiado cortos, las frecuencias altas pueden verse atenuadas por el canal de comunicaciones. Al modular los datos , RLL reduce la incertidumbre temporal en la decodificación de los datos almacenados, lo que llevaría a la posible inserción o eliminación errónea de bits al volver a leer los datos. Este mecanismo garantiza que los límites entre los bits siempre se puedan encontrar con precisión (evitando el deslizamiento de bits ), al mismo tiempo que se utilizan de manera eficiente los medios para almacenar de manera confiable la cantidad máxima de datos en un espacio determinado.
Las primeras unidades de disco utilizaban esquemas de codificación muy simples, como el código RLL (0,1) FM, seguido del código RLL (1,3) MFM, que se utilizaron ampliamente en las unidades de disco duro hasta mediados de la década de 1980 y todavía se utilizan en discos ópticos digitales como CD , DVD , MD , Hi-MD y Blu-ray . Los códigos RLL (2,7) y RLL (1,7) de mayor densidad se convirtieron en el estándar de facto de la industria para los discos duros a principios de la década de 1990.
En una unidad de disco duro , la información se representa mediante cambios en la dirección del campo magnético en el disco, y en los medios magnéticos, la salida de reproducción es proporcional a la densidad de transición de flujo. En una computadora, la información se representa mediante el voltaje en un cable. Ningún voltaje en el cable en relación con un nivel de tierra definido sería un cero binario, y un voltaje positivo en el cable en relación con la tierra representa un uno binario. Los medios magnéticos, por otro lado, siempre transportan un flujo magnético, ya sea un polo "norte" o un polo "sur". Para convertir los campos magnéticos en datos binarios, se debe utilizar algún método de codificación para traducir entre los dos.
Uno de los códigos prácticos más simples, el código modificado sin retorno a cero invertido ( NRZI ), simplemente codifica un 1 como una transición de polaridad magnética, también conocida como "inversión de flujo", y un cero como la ausencia de transición. Con el disco girando a una velocidad constante, a cada bit se le asigna un período de tiempo igual, una "ventana de datos", para la señal magnética que representa ese bit, y la inversión de flujo, si la hay, ocurre al comienzo de esta ventana. (Nota: los discos duros más antiguos usaban una longitud de tiempo fija como ventana de datos en todo el disco, pero los discos modernos son más complicados; para obtener más información sobre esto, consulte la grabación de bits por zonas ).
Este método no es tan simple, ya que la salida de reproducción es proporcional a la densidad de unos; una serie larga de ceros significa que no hay salida de reproducción en absoluto.
En un ejemplo sencillo, considere el patrón binario 101 con una ventana de datos de 1 ns (un nanosegundo, o una milmillonésima de segundo). Esto se almacenará en el disco como un cambio, seguido de ningún cambio y luego otro cambio. Si la polaridad magnética anterior ya era positiva, el patrón resultante podría verse así: −−+. Un valor de 255, o todos los unos binarios, se escribirían como −+−+−+−+ o +−+−+−+−. Un byte cero se escribiría como ++++++++ o −−−−−−−−. Un sector de 512 bytes de ceros se escribiría como 4096 bits secuenciales con la misma polaridad.
Dado que una unidad de disco es una pieza física de hardware, la velocidad de rotación de la unidad puede cambiar ligeramente debido a un cambio en la velocidad del motor o la expansión térmica del plato del disco. El medio físico de un disquete también puede deformarse, lo que provoca errores de sincronización mayores, y el circuito de sincronización del propio controlador puede tener pequeñas variaciones de velocidad. El problema es que, con una larga cadena de ceros, no hay forma de que el controlador de la unidad de disco conozca la posición exacta del cabezal de lectura y, por lo tanto, no hay forma de saber exactamente cuántos ceros hay. Una variación de velocidad de incluso el 0,1%, que es más precisa que cualquier unidad de disquete práctica, podría dar como resultado que se agreguen o eliminen 4 bits del flujo de datos de 4096 bits. Sin alguna forma de sincronización y corrección de errores, los datos quedarían completamente inutilizables.
El otro problema se debe a los límites de los propios medios magnéticos: solo es posible escribir una cierta cantidad de cambios de polaridad en una cierta cantidad de espacio, por lo que hay un límite superior a la cantidad de unos que también se pueden escribir secuencialmente, esto depende de la velocidad lineal y del espacio entre cabezales.
Para evitar este problema, los datos se codifican de tal manera que no se produzcan repeticiones largas de un único valor binario. Al limitar la cantidad de ceros escritos consecutivamente a un máximo de k , se hace posible que el controlador de la unidad permanezca sincronizado. Al limitar la cantidad de ceros escritos en una fila a un mínimo de d entre todos y cada uno, se reduce la frecuencia general de los cambios de polaridad, lo que permite que la unidad almacene más datos en la misma cantidad de espacio, lo que da como resultado un paquete más pequeño para la misma cantidad de datos o más almacenamiento en el mismo paquete de tamaño.
Todos los códigos utilizados para grabar en discos magnéticos tienen una longitud limitada de recorridos sin transición y, por lo tanto, se pueden caracterizar técnicamente como códigos RLL. Las variantes más antiguas y simples recibieron nombres específicos, como modulación de frecuencia modificada (MFM), y el nombre "RLL" se usa comúnmente solo para las variantes más complejas que no reciben esos nombres específicos, pero el término técnicamente se aplica a todas ellas.
Fuera de esta versión más simple, el primer código RLL utilizado en discos duros fue RLL (2,7), desarrollado por ingenieros de IBM y utilizado por primera vez comercialmente en 1979 en el IBM 3370 DASD , [2] [3] [4] para su uso con el mainframe de la serie 4300. A finales de la década de 1980, los discos duros de PC comenzaron a utilizar RLL propiamente dicho (es decir, variantes más complejas que las que habían recibido sus propios nombres propios, como MFM). Los códigos RLL han encontrado una aplicación casi universal en la práctica de grabación de discos ópticos desde 1980. En electrónica de consumo, los RLL como el código EFM (velocidad = 8/17, d = 2, k = 10) se emplean en el Compact Disc (CD) y MiniDisc (MD), y el código EFMPlus (velocidad = 8/16, d = 2, k = 10) utilizado en el DVD . Los parámetros d y k son las longitudes de ejecución mínima y máxima permitidas. Para una mayor cobertura de las tecnologías de almacenamiento, son útiles las referencias citadas en este artículo. [5] [6]
En general, la longitud de ejecución es el número de bits en los que la señal permanece inalterada. Una longitud de ejecución de 3 para el bit 1 representa una secuencia 111. Por ejemplo, el patrón de polarizaciones magnéticas en el disco podría ser +−−−−++−−−++++++, con ejecuciones de longitud 1, 4, 2, 3 y 6. Sin embargo, la terminología de codificación limitada por longitud de ejecución supone la codificación NRZI, por lo que los bits 1 indican cambios y los bits 0 indican la ausencia de cambio; la secuencia anterior se expresaría como 11000101001000001, y solo se cuentan las ejecuciones de bits cero.
De manera un tanto confusa, la longitud de ejecución es el número de ceros (0, 3, 1, 2 y 5 en el caso anterior) entre ceros adyacentes, que es uno menos que el número de veces que la señal permanece inalterada. Las secuencias limitadas por longitud de ejecución se caracterizan por dos parámetros, d y k , que estipulan la longitud de ejecución de cero bits mínima y máxima que puede ocurrir en la secuencia. Por lo tanto, los códigos RLL generalmente se especifican como ( d , k ) RLL, por ejemplo: (1,3) RLL.
En el formato codificado, un bit "1" indica una transición de flujo, mientras que un "0" indica que el campo magnético en el disco no cambia durante ese intervalo de tiempo.
Generalmente, el término "código RLL" se utiliza para referirse a codificaciones más elaboradas, pero el código de modulación de frecuencia original, también llamado codificación Manchester diferencial , puede considerarse como un código RLL simple de tasa 1/2. Los bits 1 agregados se denominan bits de reloj.
Ejemplo:
Datos: 0 0 1 0 1 1 0 1 0 0 0 1 1 0Codificado: 1010111011111011101010111110Reloj: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Al ampliar la longitud máxima de ejecución a 2 bits 0 adyacentes, la velocidad de datos se puede mejorar a 4/5. Esta es la variante de grabación codificada del grupo IBM original
Cuando es posible (11 de 16 códigos), el patrón de bits abcdse codifica anteponiéndole el complemento de a : aabcd. En los 5 casos en los que esto violaría una de las reglas ( 000do ab00), se sustituye por un código que comience con 11 ( , donde e = a ∨ d ).11bea
Ejemplo:
Datos: 0010 1101 0001 1000Codificado: 10010011011101111010
Obsérvese que para cumplir con la definición de RLL (0,2), no es suficiente solo que cada código de 5 bits no contenga más de dos ceros consecutivos, sino que también es necesario que cualquier par de códigos de 5 bits combinados secuencialmente no contenga más de dos ceros consecutivos. Es decir, no debe haber más de dos ceros entre el último bit del primer código y el primer bit del segundo código, para dos códigos elegidos arbitrariamente. Esto es necesario porque para cualquier código RLL, los límites de longitud de ejecución (0 y 2 en este caso) se aplican al flujo de bits modulado general, no solo a los componentes del mismo que representan secuencias discretas de bits de datos simples. (Esta regla debe cumplirse para cualquier par arbitrario de códigos, sin excepción, porque los datos de entrada pueden ser cualquier secuencia arbitraria de bits). El código IBM GCR anterior cumple con esta condición, ya que la longitud máxima de ejecución de ceros al comienzo de cualquier código de 5 bits es uno, y de la misma manera, la longitud máxima de ejecución al final de cualquier código es uno, lo que hace una longitud total de ejecución de dos en la unión entre códigos adyacentes. (Un ejemplo de la longitud máxima de ejecución que ocurre entre códigos se puede ver en el ejemplo dado anteriormente, donde el código para los datos "0010" termina con un cero y el código para los siguientes datos, "1101", comienza con un cero, formando una serie de dos ceros en la unión de estos dos códigos de 5 bits).
La modulación de frecuencia modificada empieza a ponerse interesante, porque sus propiedades especiales permiten que sus bits se escriban en un medio magnético con el doble de densidad que un flujo de bits arbitrario. Existe un límite en cuanto a la proximidad temporal entre las transiciones de flujo para que el equipo de lectura las detecte, y eso restringe la proximidad con la que se pueden registrar los bits en el medio: en el peor de los casos, con un flujo de bits arbitrario, hay dos unos consecutivos, lo que produce dos transiciones de flujo consecutivas en el tiempo, por lo que los bits deben estar lo suficientemente espaciados para que haya tiempo suficiente entre esas transiciones de flujo para que el lector los detecte. Pero este código impone una restricción de d = 1, es decir, hay un mínimo de un cero entre cada dos unos. Esto significa que, en el peor de los casos, las transiciones de flujo están separadas por dos tiempos de bit, por lo que los bits pueden estar el doble de próximos entre sí que con el flujo de bits arbitrario sin exceder las capacidades del lector.
Esta densidad de grabación duplicada compensa la tasa de codificación de 1/2 de este código (se necesitan dos bits para representar un bit de información real) y lo hace equivalente a un código de tasa 1.
La codificación es muy similar a la codificación FM.
Donde "x" es el complemento del bit previamente codificado del flujo.
Excepto que los bits de reloj no siempre son uno, esto es lo mismo que la tabla FM, y de ahí el nombre de este código. Los bits de reloj insertados son 0, excepto entre dos bits de datos 0.
Cuando se combina con el bit n-1 anterior, la tabla de codificación resultante para cada bit de datos n se convierte efectivamente en.
Ejemplo:
Datos: 0 0 1 0 1 1 0 1 0 0 0 1 1 0Codificado: x010010001010001001010010100Reloj: x 1 0 0 0 0 0 0 0 1 1 0 0 0
(1,7) RLL asigna 2 bits de datos a 3 bits en el disco, y la codificación se realiza en grupos de 2 o 4 bits. Las reglas de codificación son: ( x , y ) se convierte en (NOT x , x AND y , NOT y ), excepto ( x , 0, 0, y ) se convierte en (NOT x , x AND y , NOT y , 0, 0, 0). [7] Al codificar de acuerdo con la tabla siguiente, se debe utilizar la coincidencia más larga (la última en la tabla); esas son situaciones de manejo de excepciones donde la aplicación de las reglas anteriores conduciría a una violación de las restricciones del código.
Ejemplo:
Datos: 0 0 1 0 1 1 0 1 0 0 0 1 1 0Codificado: 101 001 010 100 100 000 001
(2,7) RLL es un código de velocidad 1/2 que asigna n bits de datos a 2 n bits en el disco, como MFM, pero debido a que la longitud de ejecución mínima es un 50 % más larga (3 tiempos de bit en lugar de 2), los bits se pueden escribir más rápido, lo que permite lograr una densidad de datos efectiva un 50 % mayor. La codificación se realiza en grupos de 2, 3 o 4 bits.
Western Digital WD5010A, WD5011A, WD50C12
Seagate ST11R, IBM
Sistemas Perstor ADRC
Las formas codificadas comienzan con un máximo de 4 y terminan con un máximo de 3 bits cero, lo que da una longitud de ejecución máxima de 7.
Ejemplo:
Datos: 1 1 0 1 1 0 0 1 1Codificado: 1000 001000 00001000
El código HHH(1,13) es un código de velocidad 2/3 desarrollado por tres investigadores de IBM (Hirt, Hassner y Heise) para su uso en la capa física VFIR IrDA de 16 MB/s. [8] A diferencia de la codificación magnética, está diseñado para un transmisor infrarrojo, donde un bit 0 representa "apagado" y un bit 1 representa "encendido". Debido a que los bits 1 consumen más energía para transmitir, está diseñado para limitar la densidad de bits 1 a menos del 50%. En particular, es un código RLL (1,13|5), donde el 5 final indica la restricción adicional de que hay como máximo 5 pares de bits "10" consecutivos.
Las primeras ocho filas describen un código estándar (1,7)-RLL. Las seis excepciones adicionales aumentan la secuencia máxima de ceros a 13 (en el patrón legal 100 000 000 000 001, que representa 10 11 10 11, seguido de 01), pero limitan la densidad máxima promedio de unos a 1 ⁄ 3 . La secuencia más larga de pares 1–0 es 000 101 010 101 000.
Este código limita la densidad de unos entre 1 ⁄ 12 y 1 ⁄ 3 , con un promedio de 25,8%.
Por ejemplo, codifiquemos la secuencia de bits 10110010 con diferentes codificaciones.
Supongamos que una cinta magnética puede contener hasta 3200 inversiones de flujo por pulgada. Una modulación de frecuencia modificada, o codificación RLL (1,3), almacena cada bit de datos como dos bits en la cinta, pero como se garantiza que haya un bit 0 (sin inversión de flujo) entre cualquier bit 1 (inversión de flujo), entonces es posible almacenar 6400 bits codificados por pulgada en la cinta, o 3200 bits de datos por pulgada. Una codificación RLL (1,7) también puede almacenar 6400 bits codificados por pulgada en la cinta, pero como solo se necesitan 3 bits codificados para almacenar 2 bits de datos, esto es 4267 bits de datos por pulgada. Una codificación RLL (2,7) necesita 2 bits codificados para almacenar cada bit de datos, pero como se garantiza que haya dos bits 0 entre cualquier bit 1, entonces es posible almacenar 9600 bits codificados por pulgada en la cinta, o 4800 bits de datos por pulgada.
Las densidades de inversión de flujo en los discos duros son significativamente mayores, pero se observan las mismas mejoras en la densidad de almacenamiento al utilizar diferentes sistemas de codificación.
Un sistema restringido se define por un conjunto restringido de secuencias "buenas" o "permitidas" que se van a grabar o transmitir. La codificación restringida se centra en el análisis de sistemas restringidos y en el diseño de codificadores y decodificadores eficientes que transforman secuencias arbitrarias de usuario en secuencias restringidas.
Se proporciona una descripción detallada de las propiedades limitantes de las secuencias limitadas por longitud de ejecución.