2.1: Tamaño del espacio del símbolo

Última actualización
Guardar como PDF

Page ID: 82364

Paul Penfield, Jr.
Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

La primera pregunta a abordar es el número de símbolos que deben codificarse. Esto se llama el tamaño del espacio del símbolo. Consideraremos espacios simbólicos de diferentes tamaños:

1
2
Poder integral de 2
Finito
Infinito, Contable
Infinito, Incontable

Si el número de símbolos es 2, entonces la selección se puede codificar en un solo bit. Si el número de símbolos posibles es 4, 8, 16, 32, 64, u otra potencia integral de 2, entonces la selección puede codificarse en el número de bits igual al logaritmo, base 2, del tamaño del espacio de símbolos. Así, 2 bits pueden designar el palo (palos, diamantes, corazones o espadas) de una carta de juego, y 5 bits pueden codificar la selección de un estudiante en una clase de 32. Como caso especial, si solo hay un símbolo, no se requieren bits para especificarlo. Un dreidel es un juguete de cuatro lados marcado con letras hebreas, e hilado como un top en un juego infantil, especialmente en Hanukkah. El resultado de cada giro podría codificarse en 2 bits.

Si el número de símbolos es finito pero no una potencia integral de 2, entonces el número de bits que funcionaría para la siguiente potencia integral superior de 2 se puede usar para codificar la selección, pero habrá algunos patrones de bits no utilizados. Los ejemplos incluyen los 10 dígitos, las seis caras de un dado cúbico, las 13 denominaciones de una carta de juego y las 26 letras del alfabeto inglés. En cada caso, hay capacidad sobrante (6 patrones no utilizados en la representación de 4 bits de dígitos, 2 patrones no utilizados en la representación de 3 bits de un dado, etc.) Qué hacer con esta capacidad sobrante es un tema de diseño importante que se discutirá en la siguiente sección.

Si el número de símbolos es infinito pero contable (capaz de ser puesto en una relación uno a uno con los enteros) entonces una cadena de bits de una longitud dada solo puede denotar un número finito de elementos de este conjunto infinito. Por lo tanto, un código de 4 bits para enteros no negativos podría designar enteros de 0 a 15, pero no sería capaz de manejar enteros fuera de este rango. Si, como resultado de algún cálculo, fuera necesario representar números mayores, entonces esta condición de “desbordamiento” tendría que manejarse de alguna manera.

Si el número de símbolos es infinito e incontable (como el valor de una cantidad física como voltaje o presión acústica) entonces se debe utilizar alguna técnica de “discretización” para reemplazar valores posibles por un número finito de valores seleccionados que son aproximadamente los mismos. Por ejemplo, si los números entre 0 y 1 fueran los símbolos y si 2 bits estuvieran disponibles para la representación codificada, un enfoque podría ser aproximar todos los números entre 0 y 0.25 por el número 0.125, todos los números entre 0.25 y 0.5 por 0.375, y así sucesivamente. Si tal aproximación es adecuada depende de cómo se utilicen los datos decodificados. La aproximación no es reversible, ya que no hay decodificador que recupere el símbolo original dado solo el código para el valor aproximado. Sin embargo, si el número de bits disponibles es lo suficientemente grande, entonces para muchos propósitos un decodificador podría proporcionar un número que esté lo suficientemente cerca. La representación en punto flotante de números reales en computadoras se basa en esta filosofía.