Hispanopedia WikiLa codificación de longitud de ejecución limitada ( RLL , por sus siglas en inglés) 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 . La RLL se utiliza tanto en sistemas de telecomunicaciones como de almacenamiento que mueven un soporte frente a un cabezal de grabación fijo .
Los distintos códigos de longitud de ejecución limitada se distinguen a menudo con la nomenclatura parametrizada ( d , k ) RLL, [ 1 ] pero en realidad se definen mediante 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 unos consecutivos. [ 2 ] Específicamente, RLL limita la longitud de los tramos (ejecuciones) de bits repetidos durante los cuales la señal no cambia. Si las ejecuciones son demasiado largas, la recuperación del reloj es difícil; si son demasiado cortas, las altas frecuencias podrían atenuarse por el canal de comunicación. Al modular los datos , RLL reduce la incertidumbre temporal en la decodificación de los datos almacenados, lo que podría provocar la inserción o eliminación errónea de bits al leer los datos. Este mecanismo garantiza que los límites entre bits siempre se puedan encontrar con precisión (evitando el deslizamiento de bits ), al tiempo que utiliza eficientemente el medio para almacenar de forma fiable la máxima cantidad de datos en un espacio determinado.
Los esquemas de codificación RLL degenerados, como los códigos FM y MFM, se utilizaron ampliamente en discos duros hasta mediados de la década de 1980. Los códigos RLL (2,7) y (1,7) de mayor densidad se convirtieron en el estándar de facto de la industria para discos duros a principios de la década de 1990. Los códigos RLL de orden superior todavía se utilizan en discos ópticos digitales como CD , DVD , MD , Hi-MD y Blu-ray .
Necesidad de codificación RLL
En un disco duro , la información se representa mediante cambios en la dirección del campo magnético del disco, y en los soportes magnéticos, la salida de reproducción es proporcional a la densidad de la transición de flujo. En un ordenador, la información se representa mediante la tensión en un cable. La ausencia de tensión en el cable con respecto a un nivel de tierra definido corresponde a un cero binario, y una tensión positiva en el cable con respecto a tierra representa un uno binario. Los soportes 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, es necesario utilizar algún método de codificación para realizar la conversión entre ambos.
Uno de los códigos prácticos más sencillos, el NRZI (modified Non-Return-To-Zero-Inverted ), simplemente codifica un 1 como una transición de polaridad magnética, también conocida como "inversión de flujo", y un cero como ausencia de transición. Con el disco girando a 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 inicio de esta ventana. (Nota: los discos duros antiguos usaban una duración fija como ventana de datos para todo el disco, pero los discos modernos son más complejos; para más información, consulte la grabación de bits por zonas ).
Este método no es tan sencillo, ya que la salida de reproducción es proporcional a la densidad de unos; una larga secuencia de ceros significa que no hay salida de reproducción en absoluto.
En un ejemplo sencillo, consideremos 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 precedente 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 512 bytes de ceros se escribiría como 4096 bits secuenciales con la misma polaridad.
Dado que una unidad de disco es un componente físico, su velocidad de rotación puede variar ligeramente debido a cambios en la velocidad del motor o a la dilatación térmica del disco. El soporte físico de un disquete también puede deformarse, provocando errores de sincronización mayores, y el circuito de temporización del controlador puede presentar pequeñas variaciones de velocidad. El problema radica en que, con una larga secuencia de ceros, el controlador de la unidad no puede conocer la posición exacta del cabezal de lectura y, por lo tanto, la cantidad exacta de ceros. Una variación de velocidad de tan solo un 0,1 %, una precisión superior a la de cualquier disquetera práctica, podría resultar en la adición o eliminación de 4 bits del flujo de datos de 4096 bits. Sin algún tipo de sincronización y corrección de errores, los datos serían completamente inutilizables.
El otro problema se debe a las limitaciones del propio medio magnético: solo es posible escribir una cantidad limitada de cambios de polaridad en un espacio determinado, por lo que existe un límite superior en cuanto a la cantidad de cambios que se pueden escribir secuencialmente; esto depende de la velocidad lineal y del espacio entre los electrodos.
Para evitar este problema, los datos se codifican de forma que no se produzcan repeticiones prolongadas de un mismo valor binario. Al limitar la cantidad de ceros escritos consecutivamente a un máximo k , se logra que el controlador de la unidad se mantenga sincronizado. Al limitar la cantidad de ceros escritos en una fila a un mínimo d entre cada uno, se reduce la frecuencia general de cambios de polaridad, lo que permite que la unidad almacene más datos en el mismo espacio, resultando en un paquete más pequeño para la misma cantidad de datos o en una mayor capacidad de almacenamiento en un paquete del mismo tamaño.
Historia
El nombre "RLL" se usa comúnmente solo para las variantes más complejas, pero los primeros métodos de grabación en discos magnéticos, la modulación de frecuencia (FM) y la modulación de frecuencia modificada (MFM), son en realidad variantes degeneradas de RLL, ya que limitaban la duración de las secuencias sin transiciones.
Aparte de estas versiones simples, el primer código RLL utilizado en discos duros fue (2,7) RLL, desarrollado por ingenieros de IBM y utilizado comercialmente por primera vez en 1979 en el IBM 3370 DASD , [ 3 ] [ 4 ] [ 5 ] 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 la electrónica de consumo, los RLL como el código EFM (tasa = 8/17, d = 2, k = 10) se emplean en el Compact Disc (CD) y MiniDisc (MD), y el código EFMPlus (tasa = 8/16, d = 2, k = 10) se utiliza en el DVD . Los parámetros d y k son las longitudes de ejecución mínima y máxima permitidas. Para obtener más información sobre las tecnologías de almacenamiento, las referencias citadas en este artículo son útiles. [ 6 ] [ 7 ]
Descripción general técnica
Generalmente, la longitud de ejecución es el número de bits para los que 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 limitada por longitud de ejecución asume la codificación NRZI, por lo que los bits 1 indican cambios y los bits 0 indican la ausencia de cambios, la secuencia anterior se expresaría como 11000101001000001, y solo se cuentan las ejecuciones de bits cero.
De forma algo confusa, la longitud de ejecución es el número de ceros (0, 3, 1, 2 y 5 en el ejemplo anterior) entre unos adyacentes, que es uno menos que el número de veces que la señal permanece sin cambios. Las secuencias con longitud 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 ( d , k ) RLL, por ejemplo: (1,3) RLL.
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 en el disco no cambia durante ese intervalo de tiempo.
FM: (0,1) RLL
Generalmente, el término "código RLL" se usa 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 un código RLL degenerado de tasa 1/2. Los bits 1 añadidos se denominan bits de reloj.
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 1
GCR: (0,2) RLL
Al extender la longitud máxima de la secuencia a 2 bits 0 adyacentes, la velocidad de datos puede mejorarse a 4/5. Esta es la variante original de grabación codificada por grupos de IBM .
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 que esto violaría una de las reglas ( 000do ab00), se sustituye un código que comienza con 11 ( , donde e = a ∨ d ).11bea
Ejemplo:
Datos: 0010 1101 0001 1000 Codificado: 10010011011101111010
Cabe señalar que, para cumplir con la definición de RLL (0,2), no basta con que cada código de 5 bits contenga como máximo 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, para cualquier par de 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 en su conjunto, no solo a los componentes que representan secuencias discretas de bits de datos simples. (Esta regla debe cumplirse para cualquier par de códigos arbitrario, sin excepción, ya que los datos de entrada pueden ser cualquier secuencia arbitraria de bits). El código IBM GCR anterior cumple esta condición, puesto que la longitud máxima de la secuencia de ceros al inicio de cualquier código de 5 bits es uno, y de igual manera la longitud máxima de la secuencia al final de cualquier código es uno, lo que da una longitud total de secuencia de dos en la unión entre códigos adyacentes. (Un ejemplo de la longitud máxima de la secuencia 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: (1,3) RLL
La modulación de frecuencia modificada comienza a ser interesante, ya que sus propiedades especiales permiten escribir sus bits en un medio magnético con el doble de densidad que una secuencia de bits arbitraria. Existe un límite en cuanto a la proximidad temporal de las transiciones de flujo para que el equipo de lectura las detecte, y esto limita la proximidad de los bits que se pueden grabar en el medio: en el peor de los casos, con una secuencia de bits arbitraria, hay dos unos consecutivos, lo que produce dos transiciones de flujo consecutivas en el tiempo, por lo que los bits deben estar lo suficientemente separados como para que haya tiempo suficiente 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 están separadas por dos tiempos de bit, por lo que los bits pueden estar el doble de cerca que con la secuencia de bits arbitraria 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 por el hecho de que los bits de reloj no siempre son uno, esto es igual a la tabla FM, y de ahí proviene 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 0 Codificado: x010010001010001001010010100 Reloj: x 1 0 0 0 0 0 0 0 1 1 0 0 0
(1,7) RLL
(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 (NO x , x AND y , NO y ), excepto ( x , 0, 0, y ) se convierte en (NO x , x AND y , NO y , 0, 0, 0). [ 8 ] Al codificar según la tabla siguiente, se debe usar la coincidencia más larga (la última en la tabla); estas son situaciones de manejo de excepciones donde la aplicación de las reglas anteriores llevarí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 0 Codificado: 101 001 010 100 100 000 001
(2,7) RLL
(2,7) RLL es un código de tasa 1/2 que asigna n bits de datos a 2n bits en el disco, como MFM, pero debido a que la longitud mínima de ejecución es un 50 % mayor (3 tiempos de bit en lugar de 2), los bits se pueden escribir más rápido, logrando 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 bits y terminan con un máximo de 3 bits cero, lo que da una longitud máxima de secuencia de 7.
Ejemplo:
Datos: 1 1 0 1 1 0 0 1 1 Codificado: 1000 001000 00001000
HHH(1,13)
El código HHH(1,13) es un código de tasa 2/3 desarrollado por tres investigadores de IBM (Hirt, Hassner y Heise) para su uso en la capa física IrDA VFIR de 16 Mbit/s . [ 9 ] A diferencia de la codificación magnética, este 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, este 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 RLL estándar (1,7) . Las seis excepciones adicionales aumentan la secuencia máxima de ceros a 13 (en el patrón válido 100 000 000 000 001, que representa 10 11 10 11, seguido de 01), pero limitan la densidad promedio máxima 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 a entre 1/12 y 1/3 , con un promedio del 25,8 %.
Ejemplos
Por ejemplo, codifiquemos la secuencia de bits 10110010 con diferentes codificaciones.
Densidades
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 habrá un bit 0 (sin inversión de flujo) entre cualquier bit 1 (con 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 equivale a 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 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 utilizar diferentes sistemas de codificación.
Véase también
- Codificación 8b/10b
- Deslizamiento de bit
- La modulación de ocho a catorce y EFMplus son códigos RLL (2,10) libres de CC que se utilizan en CD y DVD, respectivamente.
- Códigos de corrección de errores
- Código de línea
- Modulación
- capa física
- PRML
- Codificación de longitud de ejecución
- Sincronización automática de código y bits
- Codificación fuente
Referencias
- ↑ Siala, M.; Kaleh, GK (1995). "Codificación conjunta de RLL multinivel y corrección de errores". Actas del Simposio Internacional IEEE de 1995 sobre Teoría de la Información . IEEE. pág. 201. doi : 10.1109/ISIT.1995.531875 . ISBN 978-0-7803-2453-4.
- ↑ Kees Schouhamer Immink (octubre de 2022). "Innovación en códigos restringidos" . IEEE Communications Magazine . 60 (10): 20–24 . doi : 10.1109/MCOM.002.2200249 .
Un sistema restringido se define por un conjunto restringido de secuencias "buenas" o "permitidas" para ser registradas o transmitidas. La codificación restringida se centra en el análisis de sistemas restringidos y el diseño de codificadores y decodificadores eficientes que transforman secuencias de usuario arbitrarias en secuencias restringidas.
- ↑ Un cuarto de siglo de innovación en archivos de disco , Revista de Investigación y Desarrollo de IBM.
- ↑ P. A. Franaszek (1972), “Codificación de longitud variable con limitación de propagación de errores”, patente estadounidense 3,689,899 .
- ↑ Cinco décadas de primicias en la industria de las unidades de disco , DISK/TREND, Inc., editor de estudios de mercado de las industrias mundiales de unidades de disco y almacenamiento de datos. web.archive.org.
- ↑ Kees Schouhamer Immink (diciembre de 1990). "Secuencias con longitud de ejecución limitada" . Actas del IEEE . 78 (11): 1745– 1759. doi : 10.1109/5.63306 .
Se proporciona una descripción detallada de las propiedades limitantes de las secuencias con longitud de ejecución limitada.
- ↑ Kees A. Schouhamer Immink (noviembre de 2004). Códigos para sistemas de almacenamiento masivo de datos (segunda edición totalmente revisada). Eindhoven, Países Bajos: Shannon Foundation Publishers. ISBN 90-74249-27-2. Consultado el 23 de agosto de 2015 .
- ↑ Mee, C. Denis; Daniel, Eric D. (1996). Manual de almacenamiento magnético (2.ª ed.). McGraw Hill. ISBN 0-07-041275-8.
- ↑ Hirt, Walter; Hassner, Martin; Heise, Nyles (febrero de 2001), "IrDA-VFIr (16 Mb/s): código de modulación y diseño del sistema" , IEEE Personal Communications , 8 (1): 58–71 , doi : 10.1109/98.904900.
Enlaces externos
- Grabación digital en cinta magnética
- Almacenamiento de audio
- Discos giratorios, soportes de almacenamiento informático
- Almacenamiento de vídeo
- Códigos de línea
- protocolos de capa física
