Teoría de códigos

A teoría da codificación é o estudo das propiedades dos códigos e a súa adecuación para aplicacións específicas. Os códigos utilízanse para a compresión de datos, a criptografía, a detección e corrección de erros, a transmisión de datos e o almacenamento de datos. Os códigos estúdanse baixo diversas disciplinas científicas, como a teoría da información, a enxeñaría eléctrica, as matemáticas, a lingüística e a informática, co propósito de deseñar métodos de transmisión de datos eficientes e fiables. Normalmente, isto implica a eliminación da redundancia e a corrección ou detección de erros nos datos transmitidos.

Podemos estruturar a teoría de códigos en catro grandes áreas:^[1]

Compresión de datos.
Control de erros.
Codificación criptográfica.
Codificación de liñas.

A compresión de datos intenta eliminar a redundancia non desexada dos datos dunha fonte para transmitilos de forma máis eficiente. Por exemplo, a compresión de datos ZIP fai que os ficheiros de datos sexan máis pequenos para, por exemplo, reducir o tráfico de Internet. A compresión de datos e a corrección de erros son tratados frecuentemente conxuntamente.

A corrección de erros engade unha redundancia útil aos datos dunha fonte para facer a transmisión máis robusta ante as perturbacións presentes na canle de transmisión. Un disco compacto (CD) de música típico usa o código Reed-Solomon para corrixir arañazos e po. Nesta aplicación a canle de transmisión é o propio CD. Os teléfonos móbiles tamén usan técnicas de codificación para corrixir o esvaecemento e o ruído da transmisión de radio de alta frecuencia.

Historia da teoría de códigos

En 1948, Claude Shannon publicou " A Mathematical Theory of Communication", un artigo en dúas partes nos números de xullo e outubro do Bell System Technical Journal. Este traballo céntrase no problema da mellor forma de codificar a información que un remitente quere transmitir. Neste traballo fundamental utilizou ferramentas na teoría da probabilidade, desenvolvidas por Norbert Wiener, que se atopaban na súa incipiente aplicación na teoría da comunicación naquel momento. Shannon desenvolveu a entropía da información como unha medida da incerteza nunha mensaxe mentres inventou esencialmente o campo da teoría da información.

O código binario de Golay foi desenvolvido en 1949. É un código de corrección de erros capaz de corrixir ata tres erros en cada palabra de 24 bits e detectar un cuarto.

Richard Hamming gañou o premio Turing en 1968 polo seu traballo en Bell Labs en métodos numéricos, sistemas de codificación automática e códigos de detección e corrección de erros. Inventou os conceptos coñecidos como códigos de Hamming, xanelas de Hamming, números de Hamming e distancia de Hamming.

En 1972, Nasir Ahmed propuxo a transformada discreta do coseno(DCT), que desenvolveu con T. Natarajan e KR Rao en 1973.Nasir Ahmed. "How I Came Up With the Discrete Cosine Transform". Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5. </ref> O DCT é o algoritmo de compresión con perdas máis utilizado, a base de formatos multimedia como JPEG, MPEG e MP3.

Códificación da fonte. Compresión de datos.

O obxectivo da codificación para comprimir datos é tomar os datos de orixe e facelos máis pequenos.

Definición

Os datos pódense ver como unha variable aleatoria $X:\Omega \to {\mathcal {X}}$ , onde $x\in {\mathcal {X}}$ aparece con probabilidade $\mathbb {P} [X=x]$ .

Os datos codifíccanse por cadeas (palabras) sobre un alfabeto $\Sigma$ .

Un código é unha función

C:{\mathcal {X}}\to \Sigma ^{*}

.

$C(x)$ é a palabra de código asociada $x$ .

A lonxitude da palabra de código escríbese como

l(C(x)).

A lonxitude esperada dun código é

l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x].

A concatenación de palabras de código $C(x_{1},\ldots ,x_{k})=C(x_{1})C(x_{2})\cdots C(x_{k})$ .

Propiedades

$C:{\mathcal {X}}\to \Sigma ^{*}$ é non singular se é inxectiva.
$C:{\mathcal {X}}^{*}\to \Sigma ^{*}$ é unívocamente decodificable se é inxectiva.
$C:{\mathcal {X}}\to \Sigma ^{*}$ é instantánea se $C(x_{1})$ non é un prefixo de $C(x_{2})$ (e viceversa).

Principio

A entropía dunha fonte é a medida da información. Basicamente, a codificación trata de reducir a redundancia presente na fonte, e obter unha representanción con menos bits mais que leven máis información.

A compresión de datos que intenta de forma explícita minimizar a lonxitude media das mensaxes segundo un determinado modelo de probabilidade asumida chámase codificación entrópica.

Codificación de canles. Detección de erros

O propósito da teoría da codificación de canles é atopar códigos que se transmitan rapidamente, conteñan moitas palabras de código válidas e poidan corrixir ou polo menos detectar moitos erros. Aínda que non se exclúen mutuamente, o rendemento nestas áreas é unha compensación. As propiedades necesarias deste código dependen principalmente da probabilidade de que se produzan erros durante a transmisión.

O termo teoría da codificación alxébrica denota o subcampo da teoría da codificación onde as propiedades dos códigos se expresan en termos alxébricos.

A teoría da codificación alxébrica divídese basicamente en dous tipos principais de códigos:

Códigos de bloques lineares
Códigos de convolución

Analiza as seguintes tres propiedades dun código, principalmente:

Lonxitude da palabra de código
Número total de palabras de código válidas
A distancia mínima entre dúas palabras de código válidas, utilizando principalmente a distancia de Hamming, ás veces tamén outras distancias como a distancia de Lee

Codificación criptográfica

A criptografía ou codificación criptográfica é a práctica e estudo de técnicas para a comunicación segura en presenza de terceiros (chamados adversarios).^[2] De xeito máis xeral, trátase de construír e analizar protocolos que bloqueen os adversarios;^[3] varios aspectos da seguridade da información como a confidencialidade dos datos, a integridade dos datos, a autenticación e o non repudio^[4] son fundamentais para a criptografía moderna. A criptografía moderna existe na intersección das disciplinas das matemáticas, da informática e da enxeñaría eléctrica. As aplicacións da criptografía inclúen tarxetas de caixeiro automático, contrasinais de ordenadores, comercio electrónico e outras moitas.

Codificación en liñas

Un código de liña (tamén chamado de modulación de banda base dixital ou método de transmisión de banda base dixital) é un código escollido para o seu uso dentro dun sistema de comunicacións co fin de transmitir en banda base. O transporte de datos dixitais usa esta codificación frecuentemente.

A codificación de liña (ou en liña) consiste en representar o sinal dixital que se vai transportar mediante un sinal discreto en amplitude e tempo que se sintoniza de xeito óptimo para as propiedades específicas da canle física (e do equipo receptor). O patrón forma de onda de tensión ou corrente que se usa para representar os 1 e os 0 dun dato dixital nun enlace de transmisión chámase codificación de liña. Os tipos comúns de codificación de liña son a codificación unipolar, polar, bipolar e Manchester.

Notas

↑ James Irvine; David Harle (2002). "2.4.4 Types of Coding". Data Communications and Networks. John Wiley & Sons. p. 18. ISBN 9780471808725. There are four types of coding
↑ Rivest, Ronald L. (1990). "Cryptology". En J. Van Leeuwen. Handbook of Theoretical Computer Science 1. Elsevier.
↑ Bellare, Mihir; Rogaway, Phillip (21 September 2005). "Introduction". Introduction to Modern Cryptography. p. 10.
↑ Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A. (1997). Handbook of Applied Cryptography. Taylor & Francis. ISBN 978-0-8493-8523-0.

Véxase tamén

Bibliografía

Elwyn R. Berlekamp (2014), Algebraic Coding Theory, World Scientific Publishing (revised edition), ISBN 978-9-81463-589-9.
MacKay, David J. C. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
Vera Pless (1982), Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc., ISBN 0-471-08684-3.
Randy Yates, A Coding Theory Tutorial.

[1] James Irvine; David Harle (2002). "2.4.4 Types of Coding". Data Communications and Networks. John Wiley & Sons. p. 18. ISBN 9780471808725. There are four types of coding

[rivest90-2] Rivest, Ronald L. (1990). "Cryptology". En J. Van Leeuwen. Handbook of Theoretical Computer Science 1. Elsevier.

[modern-crypto-3] Bellare, Mihir; Rogaway, Phillip (21 September 2005). "Introduction". Introduction to Modern Cryptography. p. 10.

[hac-4] Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A. (1997). Handbook of Applied Cryptography. Taylor & Francis. ISBN 978-0-8493-8523-0.

[1]

[2]

[3]

[4]