Ejecución de longitud limitada

La codificación ejecución de longitud limitada o RLL (del inglés Run-Length Limited) es una técnica de codificación en línea que se utiliza para enviar datos arbitrarios a través de un canal de comunicaciones con límites en el ancho de banda. Los códigos RLL están definidos por cuatro parámetros principales: m, n, d, k. Los dos primeros, m/n, se refieren a la tasa del código, mientras que los dos restantes especifican el número mínimo d y máximo k de ceros entre «1» consecutivos. Esto se usa tanto en telecomunicaciones como en sistemas de almacenamiento que mueven un soporte en un cabezal de grabación fijo.

Específicamente, RLL limita la longitud de los tramos 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 altas frecuencias pueden ser atenuadas por el canal de comunicaciones. Al modular los datos, RLL reduce la el tiempo de incertidumbre en la decodificación de los datos almacenados, lo que conduciría a la posible inserción o eliminación errónea de bits al leer el datos de vuelta. Este mecanismo garantiza que los límites entre los bits siempre se puedan encontrar con precisión (evitando el deslizamiento de bits), al tiempo que utiliza de manera eficiente el soporte para almacenar de manera confiable la cantidad máxima de datos en un espacio determinado.

Las primeras unidades de disco usaban esquemas de codificación muy simples, como el código RLL (0,1) FM, seguido del código RLL (1,3) MFM, que se usaron ampliamente en 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 industrial de facto para discos duros a principios de la década de 1990.

Necesidad de la codificación RLL

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 soportes magnéticos; la salida de la reproducción es proporcional a la densidad de la transición de flujo. En una computadora, la información está representada por el voltaje en un cable. Ningún voltaje en el cable con relación a un nivel de tierra definido sería un cero binario, y un voltaje positivo en el cable con relación a tierra representa un uno binario. Los medios magnéticos, por otro lado, siempre llevan un flujo magnético – ya sea un polo «norte» o un polo «sur». Para convertir los campos magnéticos en datos binarios, se debe usar algún método de codificación para traducir entre estos dos.

Uno de los códigos prácticos más simples, sin retorno a cero invertido modificado (NRZI), simplemente codifica un 1 como una transición de polaridad magnética, también conocida como «inversión de flujo», y un cero sin 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 del flujo, si la hay, ocurre al comienzo de esta ventana. (Nota: los discos duros más antiguos usaban un período de tiempo fijo como ventana de datos en todo el disco, pero los discos modernos son más complicados; para obtener más información, consulte 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 se reproduce una salida.

En un ejemplo simple, 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 unos binarios, se escribiría como −+−+−+−+ o +−+−+−+−. Un byte cero se escribiría como ++++++++ o −−−−−−−−. Un sector de ceros de 512 bytes 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 a la expansión térmica del plato del disco. Los soporte físico de un disquete también pueden deformarse, lo que provoca mayores errores de temporización, y el circuito de temporización del propio controlador puede sufrir 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 sepa 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 0,1%, que es más precisa que cualquier unidad de disquete práctica, podría resultar en la adición o eliminación de 4 bits del flujo de datos de 4096 bits. Sin alguna forma de sincronización y corrección de errores, los datos se volverían completamente inutilizables.

El otro problema se debe a los límites de los soportes magnéticos en sí: solo es posible escribir tantos cambios de polaridad en una cierta cantidad de espacio, por lo que hay un límite máximo de cuántos unos se pueden escribir secuencialmente, esto depende de la velocidad lineal y del espacio del cabezal.

Para evitar este problema, los datos se codifican de tal manera que no se produzcan largas repeticiones de un único valor binario. Al limitar el número de ceros escritos consecutivamente, esto hace posible que el controlador de la unidad permanezca sincronizado. Al limitar el número de unos escritos en una fila, 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 un paquete del mismo tamaño.

Historia

 

Seagate ST11R, una controladora de disco duro ISA RLL de 8 bits producida en 1990.

Todos los códigos utilizados para grabar en discos magnéticos tienen una duración limitada de las ejecuciones sin transición y, por lo tanto, pueden caracterizarse 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 nombres tan específicos, pero el término técnicamente se aplica a todos ellos.

El primer código «RLL» utilizado en discos duros fue el RLL (2,7), desarrollado por ingenieros de IBM y utilizado comercialmente por primera vez en 1979 en el DASD IBM 3370,^[1]​^[2]​^[3]​ para usar con la computadora central de la serie 4300. A fines de la década de 1980, los discos duros de PC comenzaron a usar el RLL propiamente dicho (es decir, variantes más complejas que las que habían recibido sus propios nombres, como MFM). Los códigos RLL han encontrado una aplicación casi universal en la grabación de discos ópticos desde 1980. En la electrónica de consumo, los RLL como el código EFM (índice = 8/17, d = 2, k = 10) se emplean en el disco compacto (CD) y Minidisc (MD), y el código EFMPlus (índice = 8/16, d = 2, k = 10) es utilizado en el DVD. Los parámetros d y k son las longitudes de ejecución mínimas y máximas permitidas. Para obtener más cobertura sobre las tecnologías de almacenamiento, las referencias citadas en este artículo son útiles.^[4]​^[5]​

Resumen técnico

Generalmente, la «longitud de ejecución» es el número de bits durante los cuales la señal permanece sin cambios. 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 de ejecución de longitud limitada asume la codificación NRZI, por lo que los bit 1 indican cambios y los bits 0 indican ausencia de cambio, la secuencia anterior se expresaría como 11000101001000001, y solo ejecuciones de bits cero se cuentan.

De manera un tanto confusa, la ejecución de longitud es el número de ceros (0, 3, 1, 2 y 5 en el anterior) entre los adyacentes, que es uno menos que el número de veces que la señal permanece sin cambios. Las secuencias de ejecución limitada se caracterizan por dos parámetros, «d» y «k», que estipulan la longitud mínima y máxima de ejecución de bits cero que puede ocurrir en la secuencia. Por lo tanto, los códigos RLL generalmente se especifican como RLL (d,k), por ejemplo: RLL (1,3).

Codificación

En el formato codificado, un bit "1" indica una transición de flujo, mientras que un "0" indica que el campo magnético del disco no cambia durante ese intervalo de tiempo.

FM: RLL (0,1)

Generalmente, el término «código RLL» se usa para referirse a codificaciones más elaboradas, pero el código original de Modulación de frecuencia, también llamado codificación diferencial de Manchester, puede verse como un código RLL de índice simple 1/2. Los bits 1 agregados se denominan bits de reloj.

Datos	Codificado
0	10
1	11

Ejemplo:

 Datos: 0 0 1 0 1 1 0 1 0 0 0 1 1 0 Codificado: 1010111011111011101010111110 Reloj: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

GCR: RLL (0,2)

Al extender la ejecución de longitud máxima a 2 bits 0 adyacentes, la tasa de datos se puede mejorar a 4/5. Esta es la variante original del grupo de grabación codificada de IBM.

Datos Codificado 0000 11001 0001 11011 0010 10010 0011 10011 0100 11101 0101 10101 0110 10110 0111 10111

Datos Codificado 1000 11010 1001 01001 1010 01010 1011 01011 1100 11110 1101 01101 1110 01110 1111 01111

Siempre que sea posible (11 de 16 códigos), el patrón de bits abcd se codifica prefijándolo con el complemento de a: aabcd. En los 5 casos en los que esto violaría una de las reglas (000d o ab00), se sustituye un código que comienza con 11 (11bea, donde e = a ∨ d).

Ejemplo:

Datos: 0010 1101 0001 1000 Codificado: 10010011011101111010 

Tenga en cuenta 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 contengan 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 cualquiera de los dos códigos elegidos arbitrariamente. Esto es necesario porque para cualquier código RLL, los límites de ejecución de longitud  – 0 y 2 en este caso – se aplican al flujo general de bits modulado, no solo a los componentes que representan secuencias discretas de bits de datos (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 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, del mismo modo, 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 ejecución de longitud máxima que ocurre entre códigos se puede ver en el ejemplo anterior, 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 secuencia de dos ceros en la unión de estos dos códigos de 5 bits).

MFM: RLL (1,3)

La modulación de frecuencia modificada comienza a ser 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. Hay un límite en cuanto a qué tan cerca en tiempo pueden estar las transiciones de flujo para que el equipo de lectura las detecte, y eso restringe qué tan cerca se pueden grabar los bits en el soporte: en el peor de los casos, con un flujo de bits arbitrario, hay dos unos consecutivos, que produce dos transiciones de flujo consecutivas en el tiempo, por lo que los bits deben estar lo suficientemente separados para que haya suficiente tiempo entre esas transiciones de flujo para que el lector las 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 tienen una separación de dos bits, por lo que los bits pueden estar el doble de juntos 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.

Datos	Codificado
0	x0
1	01

Aquí «x» es el complemento del bit codificado anterior (que también es el bit de datos anterior). Excepto por los bits del reloj – , ese bit «x», y el «0» en el código «01» – , esto es lo mismo que la tabla FM, y así es como este código recibe su nombre. Los bits de reloj insertados son 0 excepto entre dos bits de datos 0.

Ejemplo:

 Datos: 0 0 1 0 1 1 0 1 0 0 0 1 1 0 Codificado: x010010001010001001010010100 Reloj: x 1 0 0 0 0 0 0 0 1 1 0 0 0 

RLL (1,7)

RLL (1,7) 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 (NO x, x Y y, NO y), excepto (x, 0, 0, y) se convierte en (NO x, x Y y, NO y, 0, 0, 0).^[6]​ Al codificar de acuerdo con la siguiente tabla, se debe usar la coincidencia «más larga» (última en la tabla); esas son situaciones de manejo de excepciones en las que la aplicación de las reglas anteriores conduciría a una violación de las restricciones del código.

Datos	Codificado
00	101
01	100
10	001
11	010
00 00	101 000
00 01	100 000
10 00	001 000
10 01	010 000

Ejemplo:

Datos: 0 0 1 0 1 1 0 1 0 0 0 1 1 0 Codificado: 101 001 010 100 100 000 001 

RLL (2,7)

RLL (2,7) es un código de taza ¹⁄₂, que mapea n bits de datos en 2n bits en el disco, como el MFM, pero debido a que la longitud mínima de ejecución es 50% mayor (3 bits en lugar de 2), los bits se pueden escribir más rápido, logrando una densidad de datos efectiva 50% mayor. La codificación se realiza en grupos de 2, 3 o 4 bits.

Western Digital WD5010A, WD5011A, WD50C12

Datos	Codificado
11	1000
10	0100
000	100100
010	000100
011	001000
0011	00001000
0010	00100100

Seagate ST11R, IBM

Datos	Codificado
11	1000
10	0100
000	000100
010	100100
011	001000
0011	00001000
0010	00100100

Perstor Systems ADRC

Datos	Codificado
11	1000
10	0100
000	100100
010	000100
001	001000
0111	00001000
0110	00100100

Las formas codificadas comienzan con un máximo de 4 bits 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 1 Codificado: 1000 001000 00001000 

RLL (1,7) sin DC

También hay una codificación RLL (1,7) alternativa que a veces se usa para evitar un DC bias (que ayuda cuando se envía una señal a larga distancia o con algunos tipos de soportes de grabación).

Datos	Codificado
00	x01
01	010
10	x00
11 00	010 001
11 01	x00 000
11 10	x00 001
11 11	010 000

Aquí «x» es el complemento del bit codificado anterior (es decir, 1 si el bit anterior era 0 y 0 si el bit anterior era 1).

Ejemplo:

 Datos: 0 1 0 0 1 1 0 1 0 1 Codificado: 010 101 000 000 010 

HHH(1,13)

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 IrDA VFIR de 16 MB/s.^[7]​ A diferencia de la codificación magnética, está diseñada para un transmisor de infrarrojos, donde un bit 0 representa «apagado» y un bit 1 representa «encendido». Debido a que 1 bit consume más energía para transmitir, esto está diseñado para limitar la densidad de 1 bit 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.

Datos	Codificado
00	010
01	001
10	100
11	101
01 10	001 000
01 11	010 000
11 10	101 000
11 11	100 000
00 11 00	010 000 000
00 11 01	001 000 000
10 11 00	100 000 000
10 11 01	101 000 000
00 11 10 11	010 000 000 000
10 11 10 11	100 000 000 000

Las primeras ocho filas describen un código estándar RLL (1,7). Las seis excepciones adicionales aumentan la serie 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 media máxima de unos a ¹⁄₃. La serie más larga de pares 1–0 es 000 101 010 101 000.

Este código limita la densidad de unos entre ¹⁄₁₂ y ¹⁄₃, con un promedio de 25,8%.

Ejemplos

Por ejemplo, codifiquemos la secuencia de bits 10110010 con diferentes codificaciones:

Codificación	Dato	Codificado
RLL(0,1)	10110010	1110111110101110
RLL(0,2)	1011 0010	01011 10010
RLL(1,3)	10110010	0100010100100100
RLL(1,7)	10 11 00 10	001 010 101 001
RLL(2,7)	10 11 0010	0100 1000 00100100

 

Densidades

Suponga 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 dado que se garantiza que habrá un bit cero (sin inversión de flujo) entre bits unos cualquiera (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 dado que 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) requiere 2 bits codificados para almacenar cada bit de datos, pero dado que se garantiza que habrá 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 usar diferentes sistemas de codificación.

Véase también

• Codificación 8b/10b
• Bit slip
• Eight-to-fourteen Modulation y EFMplus son códigos RLL (2,10) sin DC que se utilizan en los CD y DVD, respectivamente.
• Código de corrección de errores
• Códigos en línea
• Modulación (telecomunicación)
• Capa física
• PRML
• Run-length encoding
• Self-synchronizing code y bit de sincronización.
• Compresión de datos

Referencias

1. A Quarter Century of Disk File Innovation, IBM Journal of Research and Development.
2. P. A. Franaszek (1972), “Run-Length-Limited Variable Length Coding with Error Propagation Limitation”, Patente USPTO n.º 3689899.
3. , DISK/TREND, Inc., publisher of market studies of the worldwide disk drive and data storage industries. web.archive.org.
4. Kees Schouhamer Immink (December 1990). «Runlength-Limited Sequences». Proceedings of the IEEE 78 (11): 1745-1759. doi:10.1109/5.63306. «A detailed description is furnished of the limiting properties of runlength limited sequences. » 
5. Kees A. Schouhamer Immink (November 2004). Codes for Mass Data Storage Systems (Second fully revised edición). Eindhoven, The Netherlands: Shannon Foundation Publishers. ISBN 90-74249-27-2. Consultado el 23 de agosto de 2015. (requiere registro). 
6. Mee, C. Denis; Daniel, Eric D. (1996). Magnetic Storage Handbook (2nd edición). McGraw Hill. ISBN 0-07-041275-8. 
7. Hirt, Walter; Hassner, Martin; Heise, Nyles (February 2001), «IrDA-VFIr (16 Mb/s): modulation code and system design», IEEE Personal Communications 8 (1): 58-71, doi:10.1109/98.904900 ..

Enlaces externos

• Digital Magnetic Tape Recording (en inglés)

• Esta obra contiene una traducción derivada de «Run-length limited» de Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.

•   Datos: Q281884