DEPARTAMENTO DE

ELECTRÓNICA,
TELECOMUNICACIONES Y
REDES DE INFORMACIÓN

TEORÍA DE LA INFORMACIÓN Y CODIFICACIÓN

CODIFICACIÓN  DE  FUENTE  
Ing.  Christian  Tipantuña,  MSc.

E-­‐‑mail:  [email protected]  
Quito, 2014 - 2015
 1

Teoría  de  la  Información  y  Codificación

1. INTRODUCCIÓN

2. FUENTES DE INFORMACIÓN

3. CODIFICACIÓN DE FUENTE

4. CANALES DE INFORMACIÓN

5. CODIFICACIÓN DE CANAL

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 2

Codificación  de  fuente

En la actualidad el uso de algoritmos de compresión ha permitido el
almacenamiento y transferencia de mayor cantidad de información.

Motivaciones  y  necesidades
§  Limitaciones de procesamiento.
§  Capacidad del almacenamiento y memoria (RAM).
§  Transferencia de información (tiempo de propagación, tiempo de
procesamiento, etc., disminución de la latencia).
§  Limitación de recursos informáticos y de Red.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 3

Codificación  de  Fuente

①  Source   Coding   Theorem:   establece los limites en la compresión de
datos, actualmente diferentes formatos y algoritmos de compresión.
§  La codificación de fuente, también está asociada con la codificación
de la información.
§  El uso de códigos es también utilizado para proporcionar privacidad
(seguridad) a la información, uso de encriptación (criptografía).

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 4

Codificación  de  Fuente  (2)

La codificación de fuente (compresión) puede ser de dos tipos.

①  Compresión   sin   pérdida   (con   pérdida   de   redundancia):   la información

decodificada es idéntica a la original.
o  Ejemplo de uso: Envío de información bancaria, mail, archivos que no
admiten modificación (pérdida de la información).

Ejemplos algoritmos de compresión sin pérdida [6]

§  LZW (Lempel Ziv Welch) coding [ZivMay1977], [ZivSep1977], [Welch1985] - usado en
documentos PDF.
§  Huffman coding [Huff1952] – usado ampliamente como etapa de codificación final.

§  Shannon-Fano coding [Fano1949] – usado en IMPLODE método de compresión de

archivos ZIP.
§  Run Length encoding [Golomb1966] – used en máquinas de FAX.

§  Golomb Coding (implemented in Rice Algorithm for image compression) [Rice1979] –
usado en compresión de imágenes.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 5

Codificación  de  Fuente  (3)

②  Compresión   con   pérdida:   la información decodificada en la mayoría
de casos es diferente a la original.
o  Ejemplo de uso: Compresión de imágenes, audio y video.

Ejemplos algoritmos de compresión con pérdida [6]

§  JPEG [William1993] – técnica de compresión de imágenes, una
implementación de la Transformada Discreta Coseno (DCT).
§  MPEG [WebMPEG] – técnica de compresión de imágenes en movimiento.

§  A-Law and Mu-Law compression [WebITUG711] – usadas en compresión de

audio.
§  Linear Predictive Coding (LPC) [Deng2003] – usado en Speech signal
processing.
§  RELP (Residually Excited LPC), CELP (Codebook Excited LPC) – variantes de LPC
utilizados en GSM y CDMA para compresión de voz.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 6

Codificación  de  Fuente  (4)

§  Respecto a los códigos, hay una gran variedad y cantidad de ellos.

Vamos  a  empezar  por  los  códigos    y  a  estudiar  algunos  de  ellos.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 7

Propiedades  de  los  Códigos

La menor Longitud promedio de un código ​𝑳  a lo sumo es igual a la entropía

H(S).
Ejemplos: Símbolos Probabilidad

A ½
B ¼
C 1/8
D 1/8

Símbolos Código A Símbolos Código B

A 00 A 0
B 01 B 10
C 10 C 110
D 11 D 111

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 8

Propiedades  de  los  Códigos  (2)

Definición
Sea S={S1,S2, …, Sq} el conjunto de símbolos del alfabeto fuente; un código es
correspondencia de todas las posibles secuencias de símbolos S a secuencias
de símbolos de algún otro alfabeto X={X1,X2, …, Xq}.
S - alfabeto fuente X - alfabeto código

símbolos mensaje palabra código (binario)

0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña
 TIC - Codificación de Fuente 9

Propiedades  de  los  Códigos  (3)

Código  Bloque
§  Es aquel que asigna cada uno de los símbolos del alfabeto fuente S a una
secuencia fija de símbolos de alfabeto código X.

§  Las secuencias de X (Xi) reciben el nombre de palabras código.

§  Xi palabra código correspondiente al símbolo Si

Símbolos de la Fuente Palabras código (PC)

S1 0
S2 11
S3 00
S4 11

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 10

Propiedades  de  los  Códigos  (4)

Código  Unívocamente  Decodificable

§  A los códigos bloque hay que imponerles ciertas restricciones.

§  Todas las palabras código Xi deben ser distintas.

§  A un símbolo fuente (símbolo mensaje) le debe corresponder una sola

palabra código.

o  Código  No  Singular

Aquel en que todas sus palabras código son distintas.

Símbolos de la Fuente Palabras código (PC)

Para tener un código utilizable
S1 0
hay que considerar una
S2 11 condición más restrictiva
S3 00 extensión de un
análisis de código.
S4 01

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 11

Propiedades  de  los  Códigos  (5)

Extensión  de  orden  n  de  un  Código  Bloque

§  Correspondencia de símbolos Si con palabras código Xi.

§  Las extensión hace corresponder las secuencias de símbolos de la fuente

(Si1,Si2,…,Sin) con secuencias de palabras código (Xi1,Xi2,…,Xin).

§  La extensión de orden n de un código bloque es un código bloque.

Símbolos de Palabras código Símbolos de la PC Símbolos de la PC
la Fuente (PC) Fuente Fuente

S1 0 S1 S1 00 S3 S1 000
S1 S2 011 S3 S2 0011
S2 11
S1 S3 000 S3 S3 0000
S3 00
S1 S4 001 S3 S4 0001
S4 01
S2 S1 110 S4 S1 010
S2 S2 1111 S4 S2 0111
S2 S3 1100 S4 S3 0100
S2 S4 1101 S4 S4 0101
Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña
 TIC - Codificación de Fuente 12

Propiedades  de  los  Códigos  (6)

Código  Unívocamente  Decodificable  (2)

Definición
Un código bloque se dice unívocamente decodificable sí y solamente
sí, su extensión n-ésima es no singular para cualquier valor finito de n.

§  Dos secuencias cualquiera de símbolos mensaje (fuente) de la misma

longitud deben corresponder a secuencias de símbolos códigos distintas.

§  Dos secuencias de símbolos mensaje de diferente longitud deben

corresponder a secuencias de símbolos código distintas.

§  Sardinas y Patterson, encontraron las condiciones necesarias para

considerar un código unívocamente decodificable. Test for Unique
Decodability (Sardinas-Patterson , 1953)

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 13

Propiedades  de  los  Códigos  (7)

Relación unívoca
§  Una correspondencia unívoca es una correspondencia matemática
donde cada elemento del conjunto origen se corresponde con un
solo elemento del conjunto imagen.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 14

Propiedades  de  los  Códigos  (8)

Ejemplos: Códigos unívocamente decodificables

Código palabras misma longitud Código palabras diferente longitud

Símbolos de la Fuente Código A Símbolos de la Fuente Código B

S1 00 S1 0
S2 01 S2 10
S3 10 S3 110
S4 11 S4 1110

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 15

Propiedades  de  los  Códigos  (8)

Código  Instantáneo
§  Código unívocamente decodificable.

§  Un código es instantáneo cuando es posible decodificar las palabras

código sin precisar el conocimiento de los símbolos siguientes.

§  Las palabras código se pueden decodificar según se van recibiendo.

Símbolos de la Fuente Código A Código B Código C

S1 00 0 0
S2 01 10 01
S3 10 110 011

S4 11 1110 0111

¿Qué código no es instantáneo y porqué?

Respuesta: código C

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 16

Propiedades  de  los  Códigos  (9)

Código  Instantáneo  (2)

§  El código C es no instantáneo.

§  Si se recibe una secuencia binaria de palabras código no es posible

decodificar las palabras según se reciben.

§  Si se recibe 01 no es posible asegurar que corresponda a S2.

o  Si el siguiente símbolo es un 0, 01 corresponde a S2.

o  Si el siguiente símbolo es un 1, analizar un símbolo más (siguiente) para

saber si se trata de S3 (011) ó S4 (0111).

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 17

Propiedades  de  los  Códigos  (10)

Prefijo  de  una  palabra  código

§  Sea Xi={xi1,xi2, …,xim} una palabra de un código.

§  El prefijo de Xi corresponde a la secuencia de símbolos xi1,xi2,

…,xij con𝑗≤𝑚

Ejemplo: De la palabra código 0111, los prefijos son: 4

•  0
•  01
•  011
•  0111

§  Condición para un código instantáneo (instantaneidad)

Ninguna palabra código debe coincidir con el prefijo de otra.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 18

Propiedades  de  los  Códigos  (11)

Síntesis  de  un  código  instantáneo,  ejemplo  1

Análisis de código binario para una fuente de cinco símbolos.
§  Para S1 S1 à 0
§  Por instantaneidad S1 inició con 0 todas las demás deben iniciar con
1.
§  Si S2 es 1 (PC), ya no quedarían ningún símbolo con el que puedan
empezar S3, S4 y S5.
§  Para S2 S2 à 10
§  Los códigos restantes deben empezar con 11.
§  Para S3 S3 à 110 único prefijo sin utilizar 111
§  Para S4 S4 à 1110
§  Para S5 S5 à 1111

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 19

Propiedades  de  los  Códigos  (12)

§  Otras opciones para la fuente 5-aria

Están  correctos  los  ejemplos…
Opción 2:
S1 à 1
S2 à 01
S3 à 000
S4 à 0010
S5 à 0011
Opción 3:
S1 à 1
S2 à 01
S3 à 001
S4 à 0001
S5 à 0000

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 20

Propiedades  de  los  Códigos  (13)

Síntesis  de  un  código  instantáneo,  ejemplo  2

Analizando la misma fuente 5-aria.
§  Para S1 S1 à 00

§  Para S2 se puede utilizar S2 à 01

Quedan 2 prefijos sin utilizar 10 y 11 (2 opciones).
§  Para S3 S3 à 10
§  Para S4 S4 à 110 (no solo 11)
§  Para S5 S5 à 111
En código instantáneo, mientras más cortas sean las PC iniciales, más
largas deberán ser las últimas.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 21

Resumen  de  los  Tipos  de  Códigos

No Bloque
Códigos Singular
Bloque No unívoco
No
No Singular
Instantáneo
Alfabeto Fuente
Unívoco
Representado por Palabras
Alfabeto código código Instantáneo
No ambigüedad
distintas en
decodificación Decodificación
rápida

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 22

Desigualdad  de  Kraft

§  Limitaciones en el tamaño de la palabra de un código instantáneo.

§  Inecuación de Kraft determina cuantitativamente la condición para

la existencia de códigos instantáneos

Regla para elaborar códigos instantáneos

•  La condición necesaria y suficiente para la existencia de un código

instantáneo de longitudes l1,l2,…,lq viene dada por la desigualdad
de Kraft (Kraft 1949).

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 23

Desigualdad  de  Kraft  (2)

Forma 1
Donde:
§  q = número de símbolos fuente
§  r = número de símbolos código
§  li = longitud de las diferentes palabras código

Forma 2
Donde:
§  r = número de símbolos código
§  ni = número de palabras código de longitud i
§  l = longitud de las palabras más largas

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 24

Desigualdad  de  Kraft  (3)

Ejercicio: Para una fuente 4-aria {S1, S2, S3, S4}, que se codifica con
códigos binario {0,1} aplicar la desigualdad de Kraft.

Símbolos de la Código A Código B Código C Código D Código E

Fuente
S1 00 0 0 0 0
S2 01 100 10 100 10
S3 10 110 110 110 110
S4 11 111 111 11 11

§  ¿Qué códigos no so instantáneos?

Respuesta: códigos D y E

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 25

Desigualdad  de  Kraft  (4)

§  Código A

§  Código B

§  Código C

§  Código D

§  Código E

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 26

Desigualdad  de  Kraft  (5)

Ejercicio: Codificar una fuente decimal S={0,1,2,3,…,9} con un código

binario instantáneo, con la condición de que los 2 primeros símbolos
sean codificados con las palabras más cortas posibles. Determinar la
longitud mínima de las 8 palabras restantes.

Dígitos decimales (S) Código Binario

S1 0
S2 10
§  Desigualdad de Kraft para las palabras restantes.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 27

Desigualdad  de  Kraft  (6)

§  Código binario instantáneo de la fuente.

Símbolos Fuentes (S) Dígitos Decimales Código Binario

S1 0 0
S2 1 10
S3 2 11000
S4 3 11001
S5 4 11010
S6 5 11011
S7 6 11100
S8 7 11101
S9 8 11110
S10 9 11111

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 28

Desigualdad  de  Kraft  (7)

Ejercicio: Codificar una fuente de 9 símbolos con un código ternario. El

símbolo S1 debe se codificado con 1 símbolo código; del símbolo S2 al
S6, deben ser codificados con 2 símbolos código, del símbolo S7 al S9
debe ser codificados con 3 símbolos código.

§  Símbolos fuente = S = {S1,S2,…,S9}

S Código Ternario
§  Código ternario = {0,1,2} S1 0
o  Verificar si el código tiene longitud adecuada. S2 10
S3 11
S4 12
S5 20
S6 21
S7 220
S8 221
S9 222

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 29

Desigualdad  de  McMillan

§  Códigos instantáneos subdivisión de los códigos unívocos.

§  Esta desigualdad extiende la validez de la desigualdad de Kraft a los

código unívocos.

§  Si las longitudes de un código l1,l2,…,lq satisface la desigualdad de

Kraft puede construirse con ellas un código unívoco.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 30

Código  Compacto

Definición
Si la longitud media es igual o menor que la longitud media de todos
los códigos unívocos que pueden aplicarse a la misma fuente,
utilizando el mismo código.

§  Código unívoco, símbolos de la fuente asociados con palabras

código de un alfabeto r-ario.

§  Problema de la codificación de fuente à encontrar códigos

compactos.

§  Objetivo: determinar las longitudes de las palabras que forman un

código compacto.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 31

Código  Compacto  (2)

Condiciones para un código compacto

§  El concepto de L es valido tanto para una FIMN como para una FMK.

§  Para una FIMN de símbolos {S1, S2, S3,…, Sq} y probabilidades {P1, P2,
P3,…, Pq}, si se utiliza un código bloque que codifique los símbolo de
S con un alfabeto código de r símbolos; siendo li longitud de la
palabra código, H(S) es:

§  Expresada en unidades r-arias

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 32

Código  Compacto  (3)

§  L es mínimo sí y solo sí:

§  Además, con αi  =  li.

Para tener un código compacto

Ejercicio: Sea S={S1,S2,S3,S4} , con P(Si)=Pi=1/4 ∀i, calcular H(S), la

longitud promedio del código y verificar si el código es compacto,
teniendo las palabras código:
S1 à 00 S3 à 10
S2 à 01 S4 à 11

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 33

Código  Compacto  (4)

S1 à 00 S3 à 10
S2 à 01 S4 à 11

§  Imposible codificar S, mediante un código binario unívoco inferior a

2 bits/símbolo.

§  Comprobación:

o  Como Pi=1/4, el código compacto deberá tener 4 palabras de longitud 2.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 34

Código  Compacto  (5)

Ejercicio: Sea S={S1,S2,S3,S4} , con P(Si)={1/2, 1/4, 1/8, 1/8}, calcular H(S), la
longitud promedio del código y verificar si el código es compacto, siendo las
palabras código: S1 à 0 S3 à 110
S2 à 10 S4 à 111

§  La menor longitud promedio en un código instantáneo es 7/4 bits por

símbolo.

§  Código compacto:

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 35

Primer  Teorema  de  Shannon

La   longitud   media   de   un   código   r-­‐‑ario   utilizado   para   codificar   los   q  

símbolos   de   una   fuente   puede   aproximarse   cuanto   se   desee   al   valor   de   la  
entropía   con   solo   incrementar   el   orden   de   la   extensión   a   codificarse.   En  
ningún   caso   sin   embargo   la   longitud   media   de   un   código   puede   ser  
inferior  a  la  entropía.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 36

Primer  Teorema  de  Shannon  (2)

§  H(S)=L si y solo si:

§  Si no se cumple, lógico formar un código compacto con li igual al

entero inmediatamente superior.

§  Con estas relaciones se debe comprobar

o  Que las longitudes de la relación (fórmula anterior) cumplen con la
desigualdad de Kraft.
o  Las secuencias son aceptables para construir un código instantáneo.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 37

Primer  Teorema  de  Shannon  (3)

§  Se conoce que:

§  Sumando la expresión para todos los valores de i:

§  De las condiciones que se quería comprobar, se pude concluir que

se define un conjunto de li, válido para un código instantáneo.
§  Multiplicando a Pi y sumando para todos los
valores de i.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 38

Primer  Teorema  de  Shannon  (4)

§  Consecuentemente:

§  La expresión puede aplicarse a cualquier FIMN, entonces puede

aplicarse a extensiones n-ésimas (orden n).

§  Donde Ln representa la longitud media (promedio) de las palabras

código correspondientes a los símbolos de la extensión de orden n
de la fuente S.

§  λi longitud de la PC correspondiente al símbolo σi con P(σi ) la

probabilidad de σi , entonces:

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 39

Primer  Teorema  de  Shannon  (5)

§  Ln/n à representa el número promedio (medio) de símbolos código

empleados en cada símbolo simple (no extensión) de S.
§  Por lo tanto:

§  Además se conoce que, Hr(Sn)= nHr(S)

§  La desigualdad anterior, toma la siguiente forma:

§  Dividiendo esta expresión para n

§  Expresión válida para una fuente con extensiones de orden n.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 40

Primer  Teorema  de  Shannon  (6)

§  Si nà ∞ , 1/n à 0 , por tanto, es posible encontrar un valor de Ln/n

tan próximo a Hr(S), con solo codificar extensiones de orden n de S.

§  Primer teorema de Shannon, conocido también como teorema de

codificación sin ruido.

§  La codificación de extensiones resulta correcta teóricamente pero

prácticamente poco realizable, el trabajo de codificar extensiones
crece exponencialmente (qn símbolos).

§  Códigos eficientes sin recurrir a extensiones à Código de Huffman.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 41

Eficiencia  de  Codificación

§  Conociendo la probabilidad de los símbolos emitidos por la fuente,

es posible:
o  Asignar palabras código cortas à símbolos más probables

o  Asignar palabras código largas à símbolos menos probables

o  Códigos Variable Length Code

Definición
La eficiencia de codificación es la relación entre la longitud promedio
mínima posible de un código y su correspondiente longitud promedio.

§  Código eficiente à η tiende a 1

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 42

Eficiencia  de  Codificación  (2)

Eficiencia  y  Redundancia  de  un  Código

§  Eficiencia

§  Redundancia Red= 1-η

Redundancia

Hr(S) η
Límite absoluto

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Fuentes de Información 43

Código  de  Huffman

•  David A. Huffman (1925 – 1999).

•  Doctor of Science in Electrical Engineering MIT,

conocido por sus trabajos en la teoría de la información
y codificación, máquina de estados finta, circuitos
aleatorios, síntesis de procedimientos y diseño de
señales.
•  Aporte importante, el código que lleva su nombre
“Codigo de Huffman”.
Publicaciones

•  Huffman, D. (1952). "A Method for the Construction of Minimum-

Redundancy Codes". Proceedings of the IRE 40 (9): 1098–1101. doi:
10.1109/JRPROC.1952.273898.
•  Algorithm description: http://www.huffmancoding.com/my-uncle/
huffman-algorithm

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 44

Código  de  Huffman  (2)

§  Algoritmo de codificación, que permite la obtención de códigos

instantáneos compactos (óptimos) r-arios.

§  Códigos instantáneos y compactos à prefix codes

§  Obtención de códigos compactos con y sin el uso de extensiones.

§  Algoritmo para obtener códigos cuya L se aproximan a H(S).

§  Código Huffman à optimo

o  No existen otros códigos unívocos e instantáneos con menor L.

§  Asignación de códigos más cortos a símbolos más probables.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 45

Código  de  Huffman  Binarios

La codificación Huffman tiene 2 pasos:

§  Ordenamiento y reducción

§  Codificación expansiva binaria

①  Ordenamiento y reducción

§  Ordenar los símbolos Si en orden decreciente de probabilidades.

§  Reducir en 1 el número de símbolos S, sumando las probabilidades

de los 2 símbolos con menor probabilidad.
o  Ubicar esta nueva probabilidad (suma) de tal manera que se mantenga
el orden decreciente de probabilidades.
o  Si la probabilidad suma coincide con los valores ya existentes, la
ubicación de la misma es arbitraria.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 46

Código  de  Huffman  Binarios  (2)

§  Repetir el procedimiento hasta llegar a una fuente con solo 2

símbolos.
②  Codificación expansiva binaria
§  Se codifica la última fuente de 2 símbolos (última reducida)
asignando 2 palabras código de longitud 1, los símbolos 0 y 1 a los 2
símbolos de la fuente S1 y S2 última reducida.
§  Se expande la palabra que fue reducida en el correspondiente paso
de reducción a 2 palabras, por el procedimiento de repetir 2 veces
la misma (palabra código) y luego se añade a la derecha de estas 2
repeticiones los símbolos 0 y 1.
§  Se repite el paso anterior hasta llegar a la fuente original, eligiendo
para expandir la palabra que fue reducida en el proceso previo de
reducción.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 47

Código  de  Huffman  Binarios  (3)

Ejercicio: Obtener un código de Huffman binario para la FIMN S de 6

símbolos cuyas probabilidades (ya ordenadas) se dan a continuación.

S Pi Código H S1 C1 S2 C2 S3 C3 S4 C4
S1 0,4 0 0,4 0 0,4 0 0,4 0 0,6 1
S2 0,3 10 0,3 10 0,3 10 0,3 10 0,4 0
S3 0,1 110 0,1 110 0,2 111 0,3 11
S4 0,1 1110 0,1 1110 0,1 110
S5 0,06 11110 0,1 1111
S6 0,04 11111

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 48

Código  de  Huffman  Binarios  (4)

Ejercicio: Otra opción, Código B.

S Pi Código H S1 C1 S2 C2 S3 C3 S4 C4
S1 0,4 0 0,4 0 0,4 0 0,4 0 0,6 1
S2 0,3 10 0,3 10 0,3 10 0,3 10 0,4 0
S3 0,1 1110 0,1 110 0,2 111 0,3 11
S4 0,1 1111 0,1 1110 0,1 110
S5 0,06 1100 0,1 1111
S6 0,04 1101

Diferente

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 49

Código  de  Huffman  Binarios  (5)

Ejercicio: Otra opción, Código C.

S Pi Código H S1 C1 S2 C2 S3 C3 S4 C4
S1 0,4 0 0,4 0 0,4 0 0,4 0 0,6 1
S2 0,3 10 0,3 10 0,3 10 0,3 10 0,4 0
S3 0,1 1100 0,1 111 0,2 110 0,3 11
S4 0,1 1101 0,1 1100 0,1 111
S5 0,06 1110 0,1 1101
S6 0,04 1111

Diferente

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 50

Código  de  Huffman  Binarios  (6)

§  Comparación entre códigos

S Pi Código Huffma A Código Huffman B Código Huffman C
S1 0,4 0 0 0
S2 0,3 10 10 10
S3 0,1 110 1110 1100
S4 0,1 1110 1111 1101
S5 0,06 11110 1100 1110
S6 0,04 11111 1101 1111

Los  códigos  deben  diferenciarse  en  algo.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 51

Código  de  Huffman  Binarios  (7)

Para ver cual código es mejor à desviación estándar

§  Conociendo que la desviación estándar es igual a:

§  Desviación estándar para el primer código

§  Desviación estándar para el segundo código

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 52

Código  de  Huffman  Binarios  (8)

§  No siempre es necesario reducir la fuente (original) hasta 2 símbolos.

§  Únicamente reducir hasta encontrar un código compacto.

o  Recordando que para un código compacto:

§  Ejemplo: Obtención de código compacto para una fuente 5-aria

S Pi Código H S1 C1
S1 0,5 0 0,5 0
S2 0,25 10 0,25 10
S3 0,125 110 0,125 110
S4 0,1 1110 0,125 111
S5 0,025 1111

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 53

Código  de  Huffman  Binarios  (9)

Consideraciones  de  la  codificación  Huffman

§  Asignación de palabras código más cortas a símbolos más

probables, prefix variable length code.

§  Probabilidades de los símbolos de la fuente ordenados

decrecientemente implican palabras código en orden creciente, l1
< l2 < …< lq .

§  Ordenando las probabilidades en forma decreciente las 2 últimas

palabras código son iguales, lq = lq-1

§  Código compacto, se inicia la codificación en la última reducción,

en la expansión se añade el mínimo número de bits.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 54

Código  de  Huffman  con  Extensiones

Ejercicio: Obtener un código binario para la fuente binaria (2 símbolos

de la fuente) cuyas propiedades se dan a continuación, además
obtener la eficiencia del código.
S Pi Código H
S1 3/4 0
S2 1/4 1

§  H(S) y L para η

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 55

Código  de  Huffman  con  Extensiones  (2)

Ejercicio: Del ejercicio anterior codificar con Huffman la segunda y

tercera de la fuente y evaluar la eficiencia de los códigos
correspondientes.
§  Segunda  extensión
S2 P(σi) Código H S12 C1 S22 C2
σ1  =  S1 S1 9/16 0 9/16 0 9/16 0

σ2  =  S1 S2 3/16 10 4/16 11 7/16 1

σ3  =  S2 S1 3/16 110 3/16 10

σ4  =  S2 S2 1/16 111

§  H(S), L y ηpara la segunda extensión

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 56

Código  de  Huffman  con  Extensiones  (3)

§  Tercera  extensión

S2 P(σi) Cód. H S13 C1 S23 C2 S33 C3 S43 C4 S53 C5 S63 C6
σ1 27/64 0 27/64 0 27/64 0 27/64 0 27/64 0 27/64 0 37/64 1
9/64 101 9/64 101 10/64 100 18/64 11 19/64 10 27/64 0
σ2 9/64 101
9/64 110 9/64 110 9/64 101 10/64 100 18/64 11
σ3 9/64 110
9/64 111 9/64 111 9/64 110 9/64 101
σ4 9/64 111 4/64 1001 6/64 1000 9/64 111
σ5 3/64 10000 3/64 10000 4/64 1001

σ6 3/64 10001 3/64 10001

σ7 3/64 10010

σ8 1/64 10011

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 57

Códigos  Huffman  r-­‐‑arios

§  Alfabeto código de r elementos, X={x1, x2, …, xr}.

La codificación Huffman r-aria tiene 2 pasos:

§  Ordenamiento y reducción
§  Codificación expansiva r-aria

①  Ordenamiento y reducción
§  Ordenar los símbolos Si en orden decreciente de probabilidades.

§  Formar un grupo de r símbolos, los símbolos restantes se agrupan en

r-1 símbolos.
§  Si faltan símbolos al último grupo, se agregan asignando
probabilidad 0.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 58

Códigos  Huffman  r-­‐‑arios  (2)

§  Se reduce la fuente sustituyendo el último conjunto de r símbolos por uno

solo símbolo, con probabilidad igual a la suma de las probabilidades de
los símbolos sustituidos.
§  Ordenar tomando en cuenta el nuevo símbolo.
§  Repetir hasta la última reducción que va a tener r símbolos.

②  Codificación expansiva r-aria

§  Codificar la última fuente reducida asignando una palabra código de
longitud 1 /r símbolos).
§  Expandir la palabra que fue reducida de 1 a r.
o  Repetir r veces la palabra reducida.
o  Añadir a cada repetición los r símbolos disponibles.

§  Repetir la expansión hasta llegar a la fuente original.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 59

Códigos  Huffman  r-­‐‑arios  (3)

Ejercicio: Para la fuente S={S1,S2,…,S11} codificar con Huffman

utilizando un código cuaternario X={0,1,2,3} .
S S1 S2 S3
Pi Código H C1 C2 C3
S1 0,22 2 0,22 2 0,23 1 0,40 0
S2 0,15 3 0,15 3 0,22 2 0,23 1
r
S3 0,12 00 0,12 00 0,15 3 0,22 2
S4 0,10 01 0,10 01 0,12 00 0,15 3
S5 0,10 02 0,10 02 0,10 01
r-1 S6 0,08 03 0,08 03 0,10 02
S7 0,06 11 0,07 10 0,08 03
S8 0,05 12 0,06 11
r-1 S9 0,05 13 0,05 12
S10 0,04 100 0,05 13
S11 0,03 101
r-1 S12 0 102
S13 0 103
Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña
 TIC - Codificación de Fuente 60

Compresión  de  Datos  

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 61

Compresión  de  Datos

Source  Coding  Theorem Channel  Coding  Theorem

- Fuentes de información - Transmisión de información

- Búsqueda de transmisión - Alteraciones en el canal
eficiente
- Transmitir información con - Búsqueda de la transmisión el
menor número de bits fiel
- Algoritmos y formatos de - Técnicas de detección y
compresión corrección de errores

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 62

Compresión  de  Datos  (2)

Motivaciones  para  compresión  de  la  información

§  Reducción del ancho de banda de transmisión.

§  Ahorro en el uso del procesador y memoria

§  Reducción de la cantidad de bits a transmitirse (disminución del bit

rate).

§  Disminución del tiempo de transmisión.

§  Incremento en la capacidad de almacenamiento.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 63

Compresión  de  Datos  (3)

Source  Coding  and  Decoding

§  Parte importante en un sistema de comunicaciones.

§  Uso de menor número de bits para transmitir la máxima cantidad de

información.
§  Compresión de la información.

§  Compresión de la información clasificada en 2 categorías:

o  Lossless compression techniques
•  Información (data) puede ser reconstruida exactamente igual a la
original.
o  Lossy compression tecniques
•  No es posible la recuperación de la información original.
•  Errores producto de la compresión à no evidentes e imperceptibles.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 64

Compresión  de  Datos  (4)

Relación  de  compresión  (compression  ratio  CR)

§  Mide el nivel de compresión de un dato.

§  Relación entre número de bits antes de la compresión (dato original)

y después de la compresión (dato comprimido).

Factor  de  mérito

§  Inverso de la relación de compresión.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Introducción y conceptos 65

Referencias  Bibliográficas
①  Shannon, Claude Elwood (1948). «A mathematical theory of
communication». Bell System Technical Journal 27 (379-423 and
623-656).
②  Raymond W. Yeung, Information Theory and Network Coding, The
Chinese University of Hong Kong, Springer, August 2008.
③  Stallings W., “Data and Computer Communications”, Prentice Hall,
9th. Ed., USA, 2011.
④  Wen-Ching Winnie Li, “Recent Trends in Coding Theory and its
Applications", American Mathematical Soc. 2007.
⑤  Viterbi A. and Omura J., “Principles of digital Communications and
Coding", Ed. McGraw Hill, USA, 2010.
⑥  Viswanathan, Mathuranathan (2013). Simulation of Digital
Communication systems using Matlab. Second Edition.

Teoría de la Información y Codificación Escuela Politécnica Nacional

 DEPARTAMENTO DE
ELECTRÓNICA,
TELECOMUNICACIONES Y
REDES DE INFORMACIÓN

TEORÍA DE LA INFORMACIÓN Y
CODIFICACIÓN
CODIFICACIÓN DE FUENTE
Ing. Christian Tipantuña, MSc.

E-mail: [email protected]
Quito, 2021
 1

Teoría de la Información y Codificación

1. INTRODUCCIÓN

2. FUENTES DE INFORMACIÓN

3. CODIFICACIÓN DE FUENTE

4. CANALES DE INFORMACIÓN

5. CODIFICACIÓN DE CANAL

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 2

Codificación de fuente
En la actualidad el uso de algoritmos de compresión ha permitido el
almacenamiento y transferencia de mayor cantidad de información.

Motivaciones y necesidades
▪ Limitaciones de procesamiento.
▪ Capacidad del almacenamiento y memoria (RAM).
▪ Transferencia de información (tiempo de propagación, tiempo de
procesamiento, etc., disminución de la latencia).
▪ Limitación de recursos informáticos y de Red.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 3

Introducción
① Source Coding Theorem: establece los limites en la compresión
de datos, actualmente diferentes formatos y algoritmos de
compresión.
▪ La codificación de fuente, también está asociada con la
codificación de la información.
▪ El uso de códigos es también utilizado para proporcionar
privacidad (seguridad) a la información, uso de encriptación
(criptografía).

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 4

Fundamentos de
Seguridades

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 5

Criptografía
Ejemplo de criptografía
▪ File creation
root@bt:~/Desktop/LAB1/exc1.1# echo "This message is a test" >
msg.txt

▪ Encryption
root@bt:~/Desktop/LAB1/exc1.1# openssl enc -base64 -in msg.txt -out
base64_msg.enc
root@bt:~/Desktop/LAB1/exc1.1# cat base64_msg.enc
VGhpcyBtZXNzYWdlIGlzIG15IGdyZWF0IHNlY3JldAo=

▪ Decryption
root@bt:~/Desktop/LAB1/exc1.1# openssl enc -base64 -d –in
base64_msg.enc -out msg.dec
root@bt:~/Desktop/LAB1/exc1.1# cat msg.dec
This message is a test

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 6

Seguridad en Redes de Comunicaciones

▪ La seguridad es acerca de cómo prevenir ataques, o si la

prevención no es posible.

▪ Como detectar los ataques y recuperarse de ellos.

▪ Un ataque es un intento deliberado para comprometer un

sistema; por lo general se explota las debilidades en el diseño,
implementación, operación o administración del sistema.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 7

Tipos de Ataques
Pasivos
▪ Intentos de aprender o hacer uso de información del sistema
pero no afectar los recursos del sistema.
▪ Esto ataques son difíciles de detectar, deben ser prevenidos.

▪ Ejemplos: análisis de tráfico, espionaje (eavesdropping).

Activos
▪ Intentos de alterar los recursos del sistema o afectar su operación.

▪ Esto ataques son difíciles de prevenir, deben ser detectados.

▪ Ejemplos: suplantación de identidad (spoofing), reproducción

(replay), modificación (substitución, inserción o destrucción),
denegación del servicio.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 8

Servicios de Seguridad

Un sistema de seguridad para ser eficaz debe ser capaz de

proveer:
▪ Autenticación
• Tiene como objetivo la detección de la suplantación de
identidad.
• Ofrece garantía de que una entidad comunicante es quien
dice ser.

▪ Control de acceso
• Tiene como objetivo prevenir el acceso no autorizado a los
recursos.

▪ Confidencialidad
• Tiene como objetivo proteger los datos contra su divulgación
(revelación) no autorizada.
Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña
 TIC - Codificación de Fuente 9

Servicios de Seguridad (2)

▪ Integridad
• Tiene como objetivo detectar la modificación y
reproducción (reply attack).
• Ofrece la garantía de que los datos recibidos son
exactamente los enviados por el remitente.

▪ No repudio
• Provee protección contra la negación o no disponibilidad
parcial o total de la comunicación.
• En cuanto al no repudio existen básicamente 2 tipos: no-
repudio de origen y no repudio de entrega.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 10

Mecanismos de Seguridad
▪ Encripción
• Manejo de llaves o claves: llave simétrica (symmetric key),
llave asimétrica (pública).

▪ Firma digital
• Mecanismo criptográfico que permite al receptor de un
mensaje firmado digitalmente determinar la entidad
originadora de dicho mensaje (autenticación de origen y no
repudio), y confirmar que el mensaje no ha sido alterado
desde que fue firmado por el originador (integridad).

▪ Esquemas de control de acceso

• Listas de control de acceso (ACLs), etiquetas de seguridad,
etc.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 11

Mecanismos de Seguridad (2)

▪ Mecanismos de integridad de datos

• Códigos de autenticación de mensajes (MACs), numeración
secuencial, marca de tiempo (time stamping), cadenas
criptográficas.

▪ Protocolos de autenticación
• Manejo de passwords, seguridad biométrica, protocolos tipo
challenge-response.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 12

Mecanismos de seguridad

Encripción

FuncionesHash

Códigosde auntenticación de mensajes

Firmasdigitales

Protocolosde establecimiento de claves de sesión

Generador de númerospseudo-randómico

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 13

Encripción

▪ Objetivo del adversario (atacante)

o Sistemáticamente recuperar textos planos de los textos
(mensajes) cifrados.
o Deducir la clave (descifrar).

▪ Principio de Kerckhoff’s
o Se debe asumir que el adversario conoce todos los detalles de E
y D.
o Entonces la seguridad del sistema debe estar basada en la
protección de la clave para descifrar (descencriptar) en
mensaje.
Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña
 TIC - Codificación de Fuente 14

Esquemas de Encripción

▪ Encripción de clave simétrica (symmetric-key encryption)

• Es fácil calcular K’ a partir de K y viceversa.
• Usualmente K’=K
• Principalmente 2 tipos:
o stream ciphers: opera sobre caracteres individuales de un texto
plano.
o Block ciphers: procesa los textos planos en bloques largos de
caracteres.

▪ Encripción de clave asimétrica (asymmetric-key encryption)

• Es difícil (computacionalmente imposible) calcular K’ a partir
de K.
• K puede hacerse pública (public-key cryptography).

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 15

Esquemas de Clave Asimétrica

▪ Encripción de clave asimétrica (asymmetric-key encryption)

• Es difícil (computacionalmente imposible) calcular K’ a partir de
K.
▪ K puede hacer pública (public-key cryptography)
o No hay necesidad de establecer la clave antes de la
comunicación.
▪ Las claves públicas no son confienciales pero deben ser
autenticadas.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 16

Funciones Hash

▪ Una función hash mapea (asigna) cadenas de bits de una

longitud finita a una cadena de bits de longitud fija (n bits).

▪ El valor de hash de un mensaje puede servir como una imagen

compacta representativa del mensaje (similares a las huellas
dactilares - fingerprints ).

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 17

Códigos de Autenticación de Mensajes

▪ Funciones MAC se pueden ver como funciones hash con dos
entradas funcionalmente distintas: un mensaje y una clave
secreta.
▪ La salida es de un tamaño fijo y es denominada MAC.

▪ Prácticamente debe ser imposible producir un MAC correcto

para un mensaje sin conocer la clave secreta.
▪ Las funciones MAC pueden ser usadas para garantizar la
integridad de los datos y proveer servicios de autenticación.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 18

Generación y verificación MAC

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 19

Firmas Digitales
▪ Similar funcionamiento que las MACs pero:
• Infalsificable para el receptor.
• Verificable por un tercero.

▪ Utilizadas para autenticación de mensajes y para prevenir el no

repudio (del mensaje de origen).

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 20

Protocolos de Establecimiento de Claves de Sesión

▪ Protocolos de establecimiento de claves de sesión

• Establecer un secreto compartido entre dos (o más) partes.
• Se desea que el secreto establecido por un par fijo de partes
varíe en posteriores ejecuciones del protocolo
(dinamicidad).
• El secreto establecido se utiliza como clave de sesión para
proteger la comunicación entre las partes

▪ Motivación para el uso de claves de sesión

• Limitar la exposición causada por el compromiso de una
clave de sesión.
• Evitar el almacenamiento a largo plazo de un gran número
de claves secretas (claves se crean a-demanda cuando
realmente se requieran).

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 21

Protocolos de Establecimiento de Claves de Sesión (2)

Clasificación

▪ Protocolos de transporte de clave

• Una de las partes crea u obtiene el secreto y de manera
segura lo transfiere a la otra parte.

▪ Protocolos de acuerdo de claves

• Un secreto compartido se deriva de las partes en función de
la información aportada por cada uno, de manera que
ninguna de las partes puede predeterminar el valor
resultante.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 22

Generador de números pseudo-randómico (PRNGs)

• Un número randómico (aleatorio) es un número que no puede

predecir por un observador (atacante) antes de ser generado.

• Un generador criptográfico de números pseudo-aleatorios

(PRNG) es un mecanismo que procesa tanto entradas
impredecibles y genera salidas pseudo-aleatorias.

• Si se ha diseñado, implementado y utilizado correctamente,

entonces incluso un adversario con una enorme potencia de
cálculo no debe ser capaz de distinguir la salida PRNG partir
de una secuencia aleatoria verdadera.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 23

Operación General de PRNGs

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 24

Conclusiones Seguridad en Redes

• Los servicios de seguridad se implementan mediante los
mecanismos de seguridad

• Muchos mecanismos de seguridad se basan en la criptografía (por

ejemplo, cifrado, firma digital, códigos de autenticación de
mensajes, etc).

• Otros aspectos importantes.

o Protección física.
o Educación
o Reglas y procedimientos.

“If you think cryptography is going to solve your problem, you don't
understand cryptography and you don't understand your problem.”
Roger Needham

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 25

Codificación de Fuente

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 26

Codificación de Fuente
La codificación de fuente (compresión) puede ser de dos tipos.
① Compresión sin pérdida (con pérdida de redundancia): la
información decodificada es idéntica a la original.
o Ejemplo de uso: Envío de información bancaria, mail, archivos que no
admiten modificación (pérdida de la información).

Ejemplos algoritmos de compresión sin pérdida [6]

▪ LZW (Lempel Ziv Welch) coding [ZivMay1977], [ZivSep1977], [Welch1985] - usado
en documentos PDF.
▪ Huffman coding [Huff1952] – usado ampliamente como etapa de codificación
final.
▪ Shannon-Fano coding [Fano1949] – usado en IMPLODE método de compresión de
archivos ZIP.
▪ Run Length encoding [Golomb1966] – used en máquinas de FAX.

▪ Golomb Coding (implemented in Rice Algorithm for image compression)

[Rice1979] – usado en compresión de imágenes.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 27

Codificación de Fuente (2)

② Compresión con pérdida: la información decodificada en la
mayoría de casos es diferente a la original.
o Ejemplo de uso: Compresión de imágenes, audio y video.

Ejemplos algoritmos de compresión con pérdida [6]

▪ JPEG [William1993] – técnica de compresión de imágenes, una
implementación de la Transformada Discreta Coseno (DCT).
▪ MPEG [WebMPEG] – técnica de compresión de imágenes en
movimiento.
▪ A-Law and Mu-Law compression [WebITUG711] – usadas en compresión
de audio.
▪ Linear Predictive Coding (LPC) [Deng2003] – usado en Speech signal
processing.
▪ RELP (Residually Excited LPC), CELP (Codebook Excited LPC) – variantes
de LPC utilizados en GSM y CDMA para compresión de voz.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 28

Codificación de Fuente (3)

▪ Respecto a los códigos, hay una gran variedad y cantidad de
ellos.

Vamos a empezar por los códigos y a estudiar algunos de ellos.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña
 TIC - Codificación de Fuente 29

Propiedades de los Códigos

La menor Longitud promedio de un código 𝑳ത a lo sumo es igual a la

entropía H(S).
Ejemplos: Símbolos Probabilidad

A ½
B ¼
C 1/8
D 1/8

Símbolos Código A Símbolos Código B

A 00 A 0
B 01 B 10
C 10 C 110
D 11 D 111

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 30

Propiedades de los Códigos (2)

Definición
Sea S={S1,S2, …, Sq} el conjunto de símbolos del alfabeto fuente; un
código es correspondencia de todas las posibles secuencias de
símbolos S a secuencias de símbolos de algún otro alfabeto X={X1,X2, …,
Xq}.
S - alfabeto fuente X - alfabeto código
símbolos mensaje palabra código (binario)
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña
 TIC - Codificación de Fuente 31

Propiedades de los Códigos (3)

Código Bloque
▪ Es aquel que asigna cada uno de los símbolos del alfabeto fuente S a
una secuencia fija de símbolos de alfabeto código X.

▪ Las secuencias de X (Xi) reciben el nombre de palabras código.

▪ Xi palabra código correspondiente al símbolo Si

Símbolos de la Fuente Palabras código

(PC)
S1 0
S2 11
S3 00
S4 11

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 32

Propiedades de los Códigos (4)

Código Unívocamente Decodificable

▪ A los códigos bloque hay que imponerles ciertas restricciones.

▪ Todas las palabras código Xi deben ser distintas.

▪ A un símbolo fuente (símbolo mensaje) le debe corresponder una sola

palabra código.
o Código No Singular
Aquel en que todas sus palabras código son distintas.

Para tener un código utilizable

Símbolos de la Fuente Palabras código
(PC) hay que considerar una
condición más
S1 0 restrictiva
S2 11 análisis de extensión de un
S3 00 código.
S4 01

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 33

Propiedades de los Códigos (5)

Extensión de orden n de un Código Bloque

▪ Correspondencia de símbolos Si con palabras código Xi.

▪ Las extensión hace corresponder las secuencias de símbolos de la

fuente (Si1,Si2,…,Sin) con secuencias de palabras código (Xi1,Xi2,…,Xin).

▪ La extensión de orden n de un código bloque es un código bloque.

Símbolos de Palabras código Símbolos de PC Símbolos de PC
la Fuente (PC) la Fuente la Fuente

S1 0 S1 S1 00 S3 S1 000
S1 S2 011 S3 S2 0011
S2 11
S1 S3 000 S3 S3 0000
S3 00
S1 S4 001 S3 S4 0001
S4 01
S2 S1 110 S4 S1 010
S2 S2 1111 S4 S2 0111
S2 S3 1100 S4 S3 0100
S2 S4 1101 S4 S4 0101
Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña
 TIC - Codificación de Fuente 34

Propiedades de los Códigos (6)

Código Unívocamente Decodificable (2)

Definición
Un código bloque se dice unívocamente decodificable sí y
solamente sí, su extensión n-ésima es no singular para cualquier
valor finito de n.
▪ Dos secuencias cualquiera de símbolos mensaje (fuente) de la misma
longitud deben corresponder a secuencias de símbolos códigos
distintas.

▪ Dos secuencias de símbolos mensaje de diferente longitud deben

corresponder a secuencias de símbolos código distintas.

▪ Sardinas y Patterson, encontraron las condiciones necesarias para

considerar un código unívocamente decodificable. Test for Unique
Decodability (Sardinas-Patterson , 1953)

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 35

Propiedades de los Códigos (7)

Relación unívoca
▪ Una correspondencia unívoca es una correspondencia
matemática donde cada elemento del conjunto origen se
corresponde con un solo elemento del conjunto imagen.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 36

Propiedades de los Códigos (8)

Ejemplos: Códigos unívocamente decodificables

Código palabras misma longitud Código palabras diferente longitud

Símbolos de la Fuente Código A Símbolos de la Fuente Código B

S1 00 S1 0
S2 01 S2 10
S3 10 S3 110
S4 11 S4 1110

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 37

Propiedades de los Códigos (8)

Código Instantáneo
▪ Código unívocamente decodificable.

▪ Un código es instantáneo cuando es posible decodificar las palabras

código sin precisar el conocimiento de los símbolos siguientes.

▪ Las palabras código se pueden decodificar según se van recibiendo.

Símbolos de la Fuente Código A Código B Código C

S1 00 0 0
S2 01 10 01
S3 10 110 011
S4 11 1110 0111

¿Qué código no es instantáneo y porqué?

Respuesta: código C

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 38

Propiedades de los Códigos (9)

Código Instantáneo (2)

▪ El código C es no instantáneo.

▪ Si se recibe una secuencia binaria de palabras código no es

posible decodificar las palabras según se reciben.

▪ Si se recibe 01 no es posible asegurar que corresponda a S2.

o Si el siguiente símbolo es un 0, 01 corresponde a S2.

o Si el siguiente símbolo es un 1, analizar un símbolo más (siguiente)

para saber si se trata de S3 (011) ó S4 (0111).

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 39

Propiedades de los Códigos (10)

Prefijo de una palabra código

▪ Sea Xi={xi1,xi2, …,xim} una palabra de un código.

▪ El prefijo de Xi corresponde a la secuencia de símbolos

xi1,xi2,…,xij con𝑗 ≤ 𝑚
Ejemplo: De la palabra código 0111, los prefijos son: 4
• 0
• 01
• 011
• 0111

▪ Condición para un código instantáneo (instantaneidad)

Ninguna palabra código debe coincidir con el prefijo de otra.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 40

Propiedades de los Códigos (11)

Síntesis de un código instantáneo, ejemplo 1

Análisis de código binario para una fuente de cinco símbolos.
▪ Para S1 S1 → 0
▪ Por instantaneidad S1 inició con 0 todas las demás deben iniciar
con 1.
▪ Si S2 es 1 (PC), ya no quedarían ningún símbolo con el que puedan
empezar S3, S4 y S5.
▪ Para S2 S2 → 10
▪ Los códigos restantes deben empezar con 11.
▪ Para S3 S3 → 110 único prefijo sin utilizar 111
▪ Para S4 S4 → 1110
▪ Para S5 S5 → 1111

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 41

Propiedades de los Códigos (12)

▪ Otras opciones para la fuente 5-aria

Están correctos los ejemplos…
Opción 2:
S1 → 1
S2 → 01
S3 → 000
S4 → 0010
S5 → 0011
Opción 3:
S1 → 1
S2 → 01
S3 → 001
S4 → 0001
S5 → 0000

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 42

Propiedades de los Códigos (13)

Síntesis de un código instantáneo, ejemplo 2

Analizando la misma fuente 5-aria.
▪ Para S1 S1 → 00

▪ Para S2 se puede utilizar S2 → 01

Quedan 2 prefijos sin utilizar 10 y 11 (2 opciones).
▪ Para S3 S3 → 10
▪ Para S4 S4 → 110 (no solo 11)
▪ Para S5 S5 → 111
En código instantáneo, mientras más cortas sean las PC iniciales,
más largas deberán ser las últimas.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 43

Resumen de los Tipos de Códigos

No Bloque
Códigos Singular
Bloque No unívoco
No
No Singular
Instantáneo
Alfabeto Fuente Unívoco
Representado por Palabras
Alfabeto código Instantáneo
código No
distintas ambigüedad en
decodificación Decodificació
n rápida

Códigos No Bloque: Codificadores Aritméticos, Lempel Ziv, etc.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 44

Desigualdad de Kraft

▪ Limitaciones en el tamaño de la palabra de un código

instantáneo.

▪ Inecuación de Kraft determina cuantitativamente la condición

para la existencia de códigos instantáneos

Regla para elaborar códigos instantáneos

• La condición necesaria y suficiente para la existencia de un

código instantáneo de longitudes l1,l2,…,lq viene dada por la
desigualdad de Kraft (Kraft 1949).

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 45

Desigualdad de Kraft (2)

Forma 1

Donde:
▪ q = número de símbolos fuente
▪ r = número de símbolos código
▪ li = longitud de las diferentes palabras código

Forma 2

Donde:
▪ r = número de símbolos código
▪ ni = número de palabras código de longitud i
▪ l = longitud de las palabras más largas

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 46

Desigualdad de Kraft (3)

Ejercicio: Para una fuente 4-aria {S1, S2, S3, S4}, que se codifica
con códigos binario {0,1} aplicar la desigualdad de Kraft.

Símbolos de la Código A Código B Código C Código D Código E

Fuente
S1 00 0 0 0 0
S2 01 100 10 100 10
S3 10 110 110 110 110
S4 11 111 111 11 11

▪ ¿Qué códigos no so instantáneos?

Respuesta: códigos D y E

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 47

Desigualdad de Kraft (4)

▪ Código A

▪ Código B

▪ Código C

▪ Código D

▪ Código E

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 48

Desigualdad de Kraft (5)

Ejercicio: Codificar una fuente decimal S={0,1,2,3,…,9} con un

código binario instantáneo, con la condición de que los 2
primeros símbolos sean codificados con las palabras más cortas
posibles. Determinar la longitud mínima de las 8 palabras
restantes.

Dígitos decimales (S) Código Binario

S1 0
S2 10

▪ Desigualdad de Kraft para las palabras restantes.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 49

Desigualdad de Kraft (6)

▪ Código binario instantáneo de la fuente.

Símbolos Fuentes (S) Dígitos Decimales Código Binario

S1 0 0
S2 1 10
S3 2 11000
S4 3 11001
S5 4 11010
S6 5 11011
S7 6 11100
S8 7 11101
S9 8 11110
S10 9 11111

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 50

Desigualdad de Kraft (7)

Ejercicio: Codificar una fuente de 9 símbolos con un código

ternario. El símbolo S1 debe se codificado con 1 símbolo código;
del símbolo S2 al S6, deben ser codificados con 2 símbolos
código, del símbolo S7 al S9 debe ser codificados con 3 símbolos
código.

▪ Símbolos fuente = S = {S1,S2,…,S9} S Código Ternario

S1 0
▪ Código ternario = {0,1,2} S2 10
o Verificar si el código tiene longitud adecuada. S3 11
S4 12
S5 20
S6 21
S7 220
S8 221
S9 222

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 51

Desigualdad de McMillan

▪ Códigos instantáneos subdivisión de los códigos unívocos.

▪ Esta desigualdad extiende la validez de la desigualdad de

Kraft a los código unívocos.

▪ Si las longitudes de un código l1,l2,…,lq satisface la desigualdad

de Kraft puede construirse con ellas un código unívoco.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 52

Código Compacto

Definición

Si la longitud media es igual o menor que la longitud media de

todos los códigos unívocos que pueden aplicarse a la misma
fuente, utilizando el mismo código.

▪ Código unívoco, símbolos de la fuente asociados con palabras

código de un alfabeto r-ario.

▪ Problema de la codificación de fuente → encontrar códigos

compactos.

▪ Objetivo: determinar las longitudes de las palabras que forman

un código compacto.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 53

Código Compacto (2)

Condiciones para un código compacto

▪ El concepto de L es valido tanto para una FIMN como para
una FMK.

▪ Para una FIMN de símbolos {S1, S2, S3,…, Sq} y probabilidades {P1,
P2, P3,…, Pq}, si se utiliza un código bloque que codifique los
símbolo de S con un alfabeto código de r símbolos; siendo li
longitud de la palabra código, H(S) es:

▪ Expresada en unidades r-arias

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 54

Código Compacto (3)

▪ L es mínimo sí y solo sí:

▪ Además, con αi = li.

Para tener un código compacto

Ejercicio: Sea S={S1,S2,S3,S4} , con P(Si)=Pi=1/4 ∀i, calcular H(S), la

longitud promedio del código y verificar si el código es
compacto, teniendo las palabras código:
S1 → 00 S3 → 10
S2 → 01 S4 → 11

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 55

Código Compacto (4)

S1 → 00 S3 → 10
S2 → 01 S4 → 11

▪ Imposible codificar S, mediante un código binario unívoco

inferior a 2 bits/símbolo.

▪ Comprobación:

o Como Pi=1/4, el código compacto deberá tener 4 palabras de longitud 2.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 56

Código Compacto (5)

Ejercicio: Sea S={S1,S2,S3,S4} , con P(Si)={1/2, 1/4, 1/8, 1/8}, calcular H(S), la
longitud promedio del código y verificar si el código es compacto,
siendo las palabras código: S1 → 0 S3 → 110
S2 → 10 S4 → 111

▪ La menor longitud promedio en un código instantáneo es 7/4 bits por

símbolo.

▪ Código compacto:

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 57

Primer Teorema de Shannon

La longitud media de un código r-ario utilizado para codificar los q

símbolos de una fuente puede aproximarse cuanto se desee al valor
de la entropía con solo incrementar el orden de la extensión a
codificarse. En ningún caso sin embargo la longitud media de un
código puede ser inferior a la entropía.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 58

Primer Teorema de Shannon (2)

▪ H(S)=L si y solo si:

▪ Si no se cumple, lógico formar un código compacto con li

igual al entero inmediatamente superior.

▪ Con estas relaciones se debe comprobar

o Que las longitudes de la relación (fórmula anterior) cumplen con la
desigualdad de Kraft.
o Las secuencias son aceptables para construir un código
instantáneo.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 59

Primer Teorema de Shannon (3)

▪ Se conoce que:

▪ Sumando la expresión para todos los valores de i:

▪ De las condiciones que se quería comprobar, se pude concluir

que se define un conjunto de li, válido para un código
instantáneo.
▪ Multiplicando a Pi y sumando para todos
los valores de i.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 60

Primer Teorema de Shannon (4)

▪ Consecuentemente:

▪ La expresión puede aplicarse a cualquier FIMN, entonces

puede aplicarse a extensiones n-ésimas (orden n).

▪ Donde Ln representa la longitud media (promedio) de las

palabras código correspondientes a los símbolos de la
extensión de orden n de la fuente S.

▪ λi longitud de la PC correspondiente al símbolo σi con P(σi ) la

probabilidad de σi , entonces:

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 61

Primer Teorema de Shannon (5)

▪ Ln/n → representa el número promedio (medio) de símbolos

código empleados en cada símbolo simple (no extensión) de
S.
▪ Por lo tanto:

▪ Además se conoce que, Hr(Sn)= nHr(S)

▪ La desigualdad anterior, toma la siguiente forma:

▪ Dividiendo esta expresión para n

▪ Expresión válida para una fuente con extensiones de orden n.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 62

Primer Teorema de Shannon (6)

▪ Si n→ ∞ , 1/n → 0 , por tanto, es posible encontrar un valor de

Ln/n tan próximo a Hr(S), con solo codificar extensiones de
orden n de S.

▪ Primer teorema de Shannon, conocido también como teorema

de codificación sin ruido.

▪ La codificación de extensiones resulta correcta teóricamente

pero prácticamente poco realizable, el trabajo de codificar
extensiones crece exponencialmente (qn símbolos).

▪ Códigos eficientes sin recurrir a extensiones → Código de

Huffman.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 63

Eficiencia de Codificación

▪ Conociendo la probabilidad de los símbolos emitidos por la

fuente, es posible:
o Asignar palabras código cortas → símbolos más probables

o Asignar palabras código largas → símbolos menos probables

o Códigos Variable Length Code

Definición

La eficiencia de codificación es la relación entre la longitud

promedio mínima posible de un código y su correspondiente
longitud promedio.

▪ Código eficiente → η tiende a 1

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 64

Eficiencia de Codificación (2)

Eficiencia y Redundancia de un Código

▪ Eficiencia

▪ Redundancia Red= 1-η

Redundancia

Hr(S) η
Límite absoluto

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Fuentes de Información 65

Código de Huffman
• David A. Huffman (1925 – 1999).

• Doctor of Science in Electrical Engineering MIT,

conocido por sus trabajos en la teoría de la
información y codificación, máquina de estados
finta, circuitos aleatorios, síntesis de procedimientos
y diseño de señales.
• Aporte importante, el código que lleva su nombre
“Codigo de Huffman”.
Publicaciones
• Huffman, D. (1952). "A Method for the Construction of Minimum-
Redundancy Codes". Proceedings of the IRE 40 (9): 1098–1101.
doi:10.1109/JRPROC.1952.273898.
• Algorithm description: http://www.huffmancoding.com/my-
uncle/huffman-algorithm

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Fuentes de Información 66

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 67

Código de Huffman (2)

▪ Algoritmo de codificación, que permite la obtención de

códigos instantáneos compactos (óptimos) r-arios.

▪ Códigos instantáneos y compactos → prefix codes

▪ Obtención de códigos compactos con y sin el uso de

extensiones.

▪ Algoritmo para obtener códigos cuya L se aproximan a H(S).

▪ Código Huffman → optimo

o No existen otros códigos unívocos e instantáneos con menor L.

▪ Asignación de códigos más cortos a símbolos más probables.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 68

Código de Huffman Binarios

La codificación Huffman tiene 2 pasos:

▪ Ordenamiento y reducción

▪ Codificación expansiva binaria

① Ordenamiento y reducción

▪ Ordenar los símbolos Si en orden decreciente de

probabilidades.
▪ Reducir en 1 el número de símbolos S, sumando las
probabilidades de los 2 símbolos con menor probabilidad.
o Ubicar esta nueva probabilidad (suma) de tal manera que se
mantenga el orden decreciente de probabilidades.
o Si la probabilidad suma coincide con los valores ya existentes, la
ubicación de la misma es arbitraria.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 69

Código de Huffman Binarios (2)

▪ Repetir el procedimiento hasta llegar a una fuente con solo 2

símbolos.
② Codificación expansiva binaria
▪ Se codifica la última fuente de 2 símbolos (última reducida)
asignando 2 palabras código de longitud 1, los símbolos 0 y 1 a
los 2 símbolos de la fuente S1 y S2 última reducida.
▪ Se expande la palabra que fue reducida en el
correspondiente paso de reducción a 2 palabras, por el
procedimiento de repetir 2 veces la misma (palabra código) y
luego se añade a la derecha de estas 2 repeticiones los
símbolos 0 y 1.
▪ Se repite el paso anterior hasta llegar a la fuente original,
eligiendo para expandir la palabra que fue reducida en el
proceso previo de reducción.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 70

Código de Huffman Binarios (3)

Ejercicio: Obtener un código de Huffman binario para la FIMN S

de 6 símbolos cuyas probabilidades (ya ordenadas) se dan a
continuación.
S Pi Código H S1 C1 S2 C2 S3 C3 S4 C4
S1 0,4 0 0,4 0 0,4 0 0,4 0 0,6 1
S2 0,3 10 0,3 10 0,3 10 0,3 10 0,4 0
S3 0,1 110 0,1 110 0,2 111 0,3 11
S4 0,1 1110 0,1 1110 0,1 110
S5 0,06 11110 0,1 1111
S6 0,04 11111

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 71

Código de Huffman Binarios (4)

Ejercicio: Otra opción, Código B.

S Pi Código H S1 C1 S2 C2 S3 C3 S4 C4
S1 0,4 0 0,4 0 0,4 0 0,4 0 0,6 1
S2 0,3 10 0,3 10 0,3 10 0,3 10 0,4 0
S3 0,1 1110 0,1 110 0,2 111 0,3 11
S4 0,1 1111 0,1 1110 0,1 110
S5 0,06 1100 0,1 1111
S6 0,04 1101

Diferente

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 72

Código de Huffman Binarios (5)

Ejercicio: Otra opción, Código C.

S Pi Código H S1 C1 S2 C2 S3 C3 S4 C4
S1 0,4 0 0,4 0 0,4 0 0,4 0 0,6 1
S2 0,3 10 0,3 10 0,3 10 0,3 10 0,4 0
S3 0,1 1100 0,1 111 0,2 110 0,3 11
S4 0,1 1101 0,1 1100 0,1 111
S5 0,06 1110 0,1 1101
S6 0,04 1111

Diferente

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 73

Código de Huffman Binarios (6)

▪ Comparación entre códigos

S Pi Código Huffma A Código Huffman B Código Huffman C
S1 0,4 0 0 0
S2 0,3 10 10 10
S3 0,1 110 1110 1100
S4 0,1 1110 1111 1101
S5 0,06 11110 1100 1110
S6 0,04 11111 1101 1111

Los códigos deben diferenciarse en algo.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 74

Código de Huffman Binarios (7)

Para ver cual código es mejor → desviación estándar

▪ Conociendo que la desviación estándar es igual a:

▪ Desviación estándar para el primer código

▪ Desviación estándar para el segundo código

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 75

Código de Huffman Binarios (8)

▪ No siempre es necesario reducir la fuente (original) hasta 2

símbolos.
▪ Únicamente reducir hasta encontrar un código compacto.
o Recordando que para un código compacto:

▪ Ejemplo: Obtención de código compacto para una fuente 5-aria

S Pi Código H S1 C1
S1 0,5 0 0,5 0
S2 0,25 10 0,25 10
S3 0,125 110 0,125 110
S4 0,1 1110 0,125 111
S5 0,025 1111

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 76

Código de Huffman Binarios (9)

Consideraciones de la codificación Huffman

▪ Asignación de palabras código más cortas a símbolos más

probables, prefix variable length code.

▪ Probabilidades de los símbolos de la fuente ordenados

decrecientemente implican palabras código en orden
creciente, l1 < l2 < …< lq .

▪ Ordenando las probabilidades en forma decreciente las 2

últimas palabras código son iguales, lq = lq-1

▪ Código compacto, se inicia la codificación en la última

reducción, en la expansión se añade el mínimo número de bits.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 77

Código de Huffman con Extensiones

Ejercicio: Obtener un código binario para la fuente binaria (2

símbolos de la fuente) cuyas propiedades se dan a
continuación, además obtener la eficiencia del código.
S Pi Código H
S1 3/4 0
S2 1/4 1

▪ H(S) y L para η

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 78

Código de Huffman con Extensiones (2)

Ejercicio: Del ejercicio anterior codificar con Huffman la segunda

y tercera extensión de la fuente y evaluar la eficiencia de los
códigos correspondientes.
▪ Segunda extensión
S2 P(σi) Código H S12 C1 S22 C2
σ1 = S1 S1 9/16 0 9/16 0 9/16 0
σ2 = S1 S2 3/16 10 4/16 11 7/16 1

σ3 = S2 S1 3/16 110 3/16 10

σ4 = S2 S2 1/16 111

▪ H(S), L y ηpara la segunda extensión

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 79

Código de Huffman con Extensiones (3)

▪ Tercera extensión
S2 P(σi) Cód. H S13 C1 S23 C2 S33 C3 S43 C4 S53 C5 S63 C6
σ1 27/64 0 27/64 0 27/64 0 27/64 0 27/64 0 27/64 0 37/64 1
9/64 101 9/64 101 10/64 100 18/64 11 19/64 10 27/64 0
σ2 9/64 101
9/64 110 9/64 110 9/64 101 10/64 100 18/64 11
σ3 9/64 110
111
9/64 111 9/64 9/64 110 9/64 101
σ4 9/64 111 4/64 1001 6/64 1000 9/64 111
σ5 3/64 10000 3/64 1000 4/64 1001
0
σ6 3/64 10001 3/64
1000
σ7 3/64 10010 1

σ8 1/64 10011

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 80

Códigos Huffman r-arios

▪ Alfabeto código de r elementos, X={x1, x2, …, xr}.

La codificación Huffman r-aria tiene 2 pasos:

▪ Ordenamiento y reducción
▪ Codificación expansiva r-aria

① Ordenamiento y reducción
▪ Ordenar los símbolos Si en orden decreciente de
probabilidades.
▪ Formar un grupo de r símbolos, los símbolos restantes se
agrupan en r-1 símbolos.
▪ Si faltan símbolos al último grupo, se agregan asignando
probabilidad 0.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 81

Códigos Huffman r-arios (2)

▪ Se reduce la fuente sustituyendo el último conjunto de r símbolos

por uno solo símbolo, con probabilidad igual a la suma de las
probabilidades de los símbolos sustituidos.
▪ Ordenar tomando en cuenta el nuevo símbolo.
▪ Repetir hasta la última reducción que va a tener r símbolos.

② Codificación expansiva r-aria

▪ Codificar la última fuente reducida asignando una palabra
código de longitud 1 (r símbolos).
▪ Expandir la palabra que fue reducida de 1 a r.
o Repetir r veces la palabra reducida.
o Añadir a cada repetición los r símbolos disponibles.

▪ Repetir la expansión hasta llegar a la fuente original.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 82

Códigos Huffman r-arios (3)

Ejercicio: Para la fuente S={S1,S2,…,S11} codificar con Huffman

utilizando un código cuaternario X={0,1,2,3} .
S Pi Código H S1 C1 S2 C2 S3 C3
S1 0,22 2 0,22 2 0,23 1 0,40 0
S2 0,15 3 0,15 3 0,22 2 0,23 1
r
S3 0,12 00 0,12 00 0,15 3 0,22 2
S4 0,10 01 0,10 01 0,12 00 0,15 3
S5 0,10 02 0,10 02 0,10 01
r-1 S6 0,08 03 0,08 03 0,10 02
S7 0,06 11 0,07 10 0,08 03
S8 0,05 12 0,06 11
r-1 S9 0,05 13 0,05 12
S10 0,04 100 0,05 13
S11 0,03 101
r-1 S12 0 102
S13 0 103
Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña
 TIC - Codificación de Fuente 83

Compresión de Datos

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 84

Compresión de Datos

Source Coding Theorem Channel Coding Theorem

- Fuentes de información - Transmisión de información

- Búsqueda de transmisión - Alteraciones en el canal
eficiente
- Transmitir información con - Búsqueda de la transmisión
el menor número de bits fiel
- Algoritmos y formatos de - Técnicas de detección y
compresión corrección de errores

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 85

Compresión de Datos (2)

Motivaciones para compresión de la información

▪ Reducción del ancho de banda de transmisión.

▪ Ahorro en el uso del procesador y memoria

▪ Reducción de la cantidad de bits a transmitirse (disminución

del bit rate).

▪ Disminución del tiempo de transmisión.

▪ Incremento en la capacidad de almacenamiento.

* Ahorro de energía → uso eficiente de la energía

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 86

Compresión de Datos (3)

Espectro recurso escaso

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 87

Compresión de Datos (4)

Source Coding and Decoding

▪ Parte importante en un sistema de comunicaciones.

▪ Uso de menor número de bits para transmitir la máxima

cantidad de información.
▪ Compresión de la información.

▪ Compresión de la información clasificada en 2 categorías:

o Lossless compression techniques
• Información (data) puede ser reconstruida exactamente igual a
la original.
o Lossy compression tecniques
• No es posible la recuperación de la información original.
• Errores producto de la compresión → no evidentes e
imperceptibles.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 88

Compresión de Datos (5)

Relación de compresión (compression ratio CR)

▪ Mide el nivel de compresión de un dato.

▪ Relación entre número de bits antes de la compresión (dato

original) y después de la compresión (dato comprimido).

Factor de mérito
▪ Inverso de la relación de compresión.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 89

Compresión de Tipo Lossy

Codificación diferencial
▪ Se basa en la correlación existente entre muestras sucesivas.

▪ Se codifica la diferencia entre muestras.

o Se requieren menos bits

▪ En es te grupo se tienen:
o DPCM (PCM Diferencial)
o DM (Modulación Delta)
o Codificación Predictiva

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 90

Compresión de Tipo Lossy (2)

Codificación por transformada

▪ Codificación por bloques.
▪ La señal a procesarse se transforma al dominio de frecuencia.
▪ Se evalúa el contenido espectral de la transformada
o Se transmiten solamente los coeficientes codificados de mayor
energía.

▪ Algunos ejemplos:
o KL (Karhunen Loeve) o de compotentes principales
o Fourier
o Hadamard
o Haar
o Coseno
o Wavelet

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 91

Compresión de Tipo Lossy (3)

Cuantización Vectorial
▪ Se procesa un conjunto de muestras (vectores de dimensión
N).

▪ Se dispone de un registro de código RC que tiene las posibles

salidas del cuantificador
o Cada vector en el RC se llama vector de código.

▪ Cuantificar un vector de entrada consiste en determinar su

vecino más cercano en el RC.
o Para esto se calcula la “distancia” entre vector de entrada y cada
vector del RC.
o Se escoge el de menor distancia.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Codificación de Fuente 92

Compresión de Tipo Lossless

Métodos estadísticos
▪ Basados en las propiedades estadísticas de la fuente.
o Huffman
o Código Golomb
o Shannon Fano (no es óptimo, parte del formato ZIP)
o Predictores (Adaptivos)
o Compresores Aritméticos

▪ Basados en diccionario
o Construye un diccionario basado en la entrada procesada.
o Contiene cadenas de mensajes identificadas por un índice.

Teoría de la Información y Codificación Escuela Politécnica Nacional Christian Tipantuña

 TIC - Introducción y conceptos 93

Referencias Bibliográficas
① Shannon, Claude Elwood (1948). «A mathematical theory of
communication». Bell System Technical Journal 27 (379-423
and 623-656).
② Raymond W. Yeung, Information Theory and Network Coding,
The Chinese University of Hong Kong, Springer, August 2008.
③ Stallings W., “Data and Computer Communications”, Prentice
Hall, 9th. Ed., USA, 2011.
④ Wen-Ching Winnie Li, “Recent Trends in Coding Theory and its
Applications", American Mathematical Soc. 2007.
⑤ Viterbi A. and Omura J., “Principles of digital Communications
and Coding", Ed. McGraw Hill, USA, 2010.
⑥ Viswanathan, Mathuranathan (2013). Simulation of Digital
Communication systems using Matlab. Second Edition.

Teoría de la Información y Codificación Escuela Politécnica Nacional

 Ecuador y la Privacidad en Internet: Una Aproximación Inicial
_________________________________________________________________________________________________________________________

Ecuador y la Privacidad en Internet: Una Aproximación Inicial

Estrada J. A.*; Estrada J. C.**; Rodríguez A.*; Tipantuña C.*

*Escuela Politécnica Nacional, Facultad de Ingeniería Eléctrica y Electrónica, Quito, Ecuador
e-mail: {jose.estrada; ana.rodriguez; christian.tipantuna}@epn.edu.ec
** e-mail: [email protected]

Resumen: La privacidad es un concepto muy relativo y sujeto al sentimiento de seguridad que tenga un usuario.
Aunque es común estudiar la percepción de privacidad de los usuarios de Internet, casi nada se ha discutido sobre
este derecho en Ecuador. Por ello, tampoco se han puesto de manifiesto algunos riesgos a la privacidad de los
usuarios que están latentes en el contexto nacional. Ya que la administración pública en Ecuador experimenta una
explosiva integración al “gobierno en línea” en la que se gestiona información de los ciudadanos, resulta crucial
estudiar la privacidad de estos datos desde su perspectiva local y en el marco de los riesgos latentes que dicha
privacidad enfrenta. Se realizó un estudio de percepción de privacidad mediante una encuesta para determinar, entre
otras cosas, qué información es considerada sensible por los usuarios. Además, se hizo un análisis experimental no
intrusivo de algunos servicios de información ecuatorianos en Internet, para determinar si la percepción de los
usuarios concurre con los riesgos de su privacidad en Internet. Se encontró que los usuarios están claramente
conscientes de las amenazas a su intimidad en línea. Lamentablemente, la información que consideran “no sensible”
podría permitirle a un atacante obtener información que los usuarios consideran “muy sensible”, con lo que la
conciencia inicial que muestran no resultaría suficiente para proteger su privacidad.

Palabras clave: Privacidad, Ecuador, percepción, seguridad, Internet, riesgos

Abstract: Privacy is a very relative concept subject to the user’s feeling about security. Although it is common to
study the privacy perception of Internet users, little has been discussed about that in Ecuador. Thus, the risks of user
privacy in the local context have not been highlighted. Since public administration in Ecuador suffers an explosive
integration into the e-government where information on citizens is managed, it is crucial to study these data privacy
from a local view and within the framework of the underlying risks that such privacy faces. We performed a study
of privacy perception by means of a poll which helped us to determine how concerned users are about some types
of information. Moreover, we did an experimental nonintrusive analysis of some Ecuadorian information services
available on Internet in order to find if the users’ perceptions match their privacy risk on Internet. We found that
users are aware of the threats to their privacy online. Sadly, the data they find “non sensible” could allow an
attacker to get information that users find “very sensible”, so the initial awareness they show may not be enough to
protect their privacy.

Keywords: Privacy, Ecuador, perception, security, Internet, risks

1. INTRODUCCIÓN información pública de los ciudadanos y a la realización

electrónica de trámites.
Desde hace casi una década, el Ecuador (y el mundo con
anterioridad a eso) sufre una revolución en la gestión de la A pesar de la eficiencia, la reducción de costos y la
información, catalizada por la masificación del acceso a transparencia que promueven los mecanismos de gobierno en
Internet y la integración de una gran cantidad de procesos línea, existen en estos contextos algunos inconvenientes que
cotidianos en esta red global. podrían poner en riesgo la seguridad de la información de los
ciudadanos. Esto se debe a que dichos mecanismos
La virtualización de las interacciones entre usuarios, concentran grandes cantidades de información en servicios
ciudadanos, consumidores y autoridades o proveedores, a informáticos accesibles públicamente desde Internet.
través de la infraestructura que ofrece Internet (en lo que se
conoce como gobierno en línea), representa una tendencia Aquellos datos no son necesariamente privados (sino
que no se detiene [21] debido a las ventajas que supone su personales) pero, al combinarse los que se obtienen de
aplicación [18]. En ese contexto, una serie de iniciativas de distintas fuentes públicas, se podría vulnerar la privacidad de
gobierno en línea promovidas los últimos años se han llevado un individuo, al utilizar esos datos para inferir información
a cabo en Ecuador, orientadas, entre otras cosas, a la privada.
transparencia de la gestión pública, la consolidación de la

Revista Politécnica - Septiembre 2015, Vol. 36, No. 1

 Estrada J. A.*; Estrada J. C.**; Rodríguez A.*; Tipantuña C.*
_______________________________________________________________________________________________________________________________

No obstante, poco se conoce en Ecuador sobre los riesgos

relativos a la privacidad, causados por la exposición
indiscriminada de información personal. Menos todavía se ha Penetración de Internet
EEUU Ecuador
investigado acerca de la percepción que existe sobre estos
100

% de Penetración de Internet
tópicos, y muy superficialmente se ha discutido acerca de la
necesidad de legislación orientada a la protección de los
datos. En este artículo hacemos una aproximación inicial para 50
medir esta percepción de los usuarios sobre los riesgos a su
privacidad. De manera complementaria, hacemos un trabajo
0
exploratorio para obtener una primera impresión de los
1995 2000 2005 2010 2015
problemas de privacidad (datos personales expuestos) que
Año
podrían derivarse de la información contenida en ciertos
servicios públicos en línea en Ecuador (Seguridad Social,
Servicio de Rentas Internas, Registro Civil, etc.). Así, se Figura 1. Tendencias de penetración de Internet de Ecuador y EEUU
intenta evaluar el impacto que podría generar el (Internet World Stats, 2014)
aprovechamiento de estos riesgos manifiestos en la
privacidad de los ciudadanos, considerando la percepción privacidad está ligada solamente al ámbito “físico” de la vida
medida de estos ciudadanos sobre dichos riesgos. personal de un individuo. El contexto virtual en el que la
gente se desenvuelve mediante Internet, al hacer búsquedas o
El resto del artículo está organizado como sigue: en la usar redes sociales, usualmente es relegado a un segundo
Sección 2 se presenta un análisis del estado actual de la plano (al parecer inconscientemente) por preocupaciones
privacidad en el Ecuador desde el punto de vista jurídico y individuales más tangibles (delincuencia, economía, etc.).
cultural. En la Sección 3 se describe el escenario y Pese a ello, y a raíz de los constantes escándalos [11]
metodología utilizados para realizar el presente estudio, tanto motivados por el espionaje que realizan ciertas
en cuanto a la medición de la percepción como al análisis organizaciones a los ciudadanos, varios países han expedido
exploratorio de la privacidad en línea en el Ecuador. En las normativa referente a la protección de los datos personales
secciones 4 y 5 se plantean los resultados obtenidos al [16].
determinar la percepción de los usuarios sobre su privacidad
en Internet en Ecuador y al investigar las amenazas presentes En Ecuador; sin embargo, muy poco se ha avanzado en
a dicha privacidad en los sistemas de información dispuestos legislación para la protección de datos personales.
para el ciudadano. En la Sección 6 se plantea una discusión Históricamente, la Constitución política de 1998 hacía una
sobre un escenario de riesgo a la privacidad de un usuario tibia referencia al derecho a la intimidad, y al secreto de la
puntual. Finalmente, en la Sección 7 se presentan las correspondencia. En concordancia con este texto
conclusiones de este trabajo. constitucional, la Ley de Comercio Electrónico, Firmas
Electrónicas y Mensajes de Datos, emitida en 2002, le dedica
el artículo 9 a la protección de datos, pero se concentra
2. LA PRIVACIDAD EN EL ECUADOR DE HOY solamente en determinar que los datos personales podrán ser
Ecuador es un país con casi 16 millones de habitantes, en el usados o transferidos únicamente con autorización del titular
que la penetración de Internet en los últimos 7 años ha o la orden de autoridad competente.
crecido exponencialmente, tal como puede observarse en la
Fig. 1. Este incremento se debe, en primera instancia, a la Posteriormente, en la Constitución ecuatoriana vigente desde
reducción de los costos de acceso a Internet y en gran 2008, también se determina la acción jurisdiccional del
medida, también, a la intensa promoción del uso de canales habeas data, en el artículo 92. Este derecho permite a una
electrónicos para la interacción con la empresa pública y persona (o institución) conocer, autorizar y rectificar la
privada (trámites en línea). De acuerdo al último censo de información que sobre ella se almacene en bases de datos
TICs realizado por el INEC (Instituto Nacional de públicas o privadas. Sin embargo, el recurso de habeas data
Estadísticas y Censos) [5] en 2013, es evidente el incremento sólo permite reparar un daño ya consumado (a posteriori) y
de los índices de uso de tecnología de comunicaciones. no dispone la existencia de una autoridad de protección de
Seguramente por la tardía expansión del servicio de Internet datos que pueda actuar de oficio. Esto resulta muy poco
en Ecuador (comparar con la evolución de la penetración de efectivo en la protección de la información personal que se
Internet en EEUU en Fig. 1), la preocupación sobre temas de recopila indiscriminadamente a través de Internet [17].
privacidad en línea no ha sido discutida aún con profundidad
en el país. Finalmente, en 2010 se expidió la Ley del Sistema Nacional
de Registro de Datos Públicos (LSNRDP) que regula la
2.1 Legislación Ecuatoriana sobre Privacidad forma en la que se registra y accede a los datos públicos, con
el fin de transparentar y organizar el acceso a la información
La privacidad está consagrada como un derecho en la que las instituciones públicas y privadas almacenan de una
Declaración Universal de los Derechos Humanos de las persona. Aunque en su artículo 6 se definen los datos que se
Naciones Unidas [12]. Sin embargo, es común pensar que la consideran confidenciales y se dispone que el acceso a ellos
podrá ser autorizado por el titular o por mandato de la ley,

Revista Politécnica - Septiembre 2015, Vol. 36, No. 1

 Ecuador y la Privacidad en Internet: Una Aproximación Inicial
_________________________________________________________________________________________________________________________

esta normativa no promueve mecanismos que garanticen o 3. ESCENARIO DE ANÁLISIS

protejan los datos personales. Es así que, aunque otros países
(Argentina y Uruguay) están a la vanguardia de la legislación Con el fin de hacer un análisis preliminar del estado de la
sobre protección de datos y privacidad, muy poca atención se privacidad en el Ecuador, que de ninguna manera intenta ser
le ha dado a estos temas a nivel jurídico en Ecuador, aunque exhaustivo, se ha enfocado este trabajo a tres elementos: (1)
sí se han hecho propuestas desde la academia [15, 1]. un sondeo inicial de la percepción sobre la privacidad en
Internet en Ecuador, (2) una exploración breve y no intrusiva
2.2 La cultura de privacidad en Ecuador de los riesgos de privacidad en varios sistemas de
información en Ecuador (en general públicos), y (3) una
La actitud de un grupo humano frente a la privacidad y a los discusión concluyente donde se vinculen los componentes de
problemas de seguridad en Internet se define en la literatura los dos primeros elementos. A continuación se describe el
en función de sus valores culturales [8, 14]. Para ello se suele procedimiento utilizado para realizar este análisis.
utilizar el Modelo de las Dimensiones Culturales de Hofstede
[4], que define cinco agrupaciones de valores que sirven para Es necesario notar que muchos de los sistemas de
identificar patrones culturales de un conjunto de personas. En información abajo descritos representan una evolución
cuanto a la postura frente a la privacidad, las dimensiones trascendental en el contacto entre las instituciones del Estado
que podrían dar una idea sobre el comportamiento de la gente y los ciudadanos. Concordantemente, el objetivo de este
se encuentran: la distancia al poder, y el análisis es destacar cómo, al igual que sucede con la
individualismo/colectivismo. De acuerdo al análisis de tecnología en general, la integración en la sociedad de la
Hofstede, Ecuador es un país extremadamente colectivista [9] información envuelve ciertos riesgos (muchas veces
lo que, según otros análisis [19], supone que los ecuatorianos imperceptibles) a la privacidad de los usuarios.
tienen mucha más confianza en otras personas que la que
tendrían ciudadanos de EE.UU., España, México o 3.1 Encuesta de Percepción de Privacidad en Internet
Argentina, que son culturas más individualistas. Aunque este
análisis no es determinante, es curioso observar, por ejemplo, Aunque muchos esfuerzos se han puesto en medir
que con cierta regularidad los países más individualistas técnicamente el riesgo de privacidad en Internet [7, 2], así
(menos “confiados”) son aquellos (EE.UU., España, México, como en implementar mecanismos de protección en distintos
Argentina, Costa Rica, Uruguay) que poseen una legislación contextos [6, 22], la actitud que tiene un usuario frente a
sobre protección de los datos desde hace varios años. estos riesgos dependerá siempre de su situación particular
(laboral, política, económica y hasta sentimental), y con
Por otro lado, cabe resaltar la actitud generalizada que se relación a ella tendrá que estimarse el riesgo. Además, esta
tiene frente a la vigilancia (monitorización indiscriminada) en actitud se revela también como la sensación que tiene un
Internet, en el sentido de que si “uno no tiene nada que usuario frente a las amenazas a su privacidad en Internet [10];
esconder”, entonces el derecho a la privacidad puede es decir, lo que conozca, las reflexiones que manifieste, y las
rescindirse. Esta postura peligrosa normalmente sirve de acciones que tome frente a ellas.
justificación a quienes tienen el poder sobre los datos
(gobiernos o mega corporaciones en Internet) para realizar Con el fin de medir esta descrita percepción, se realizó una
actividades de profiling o targeting que podrían estar encuesta a 120 estudiantes universitarios de Carreras de
rebasando los límites de la intimidad de las personas. Con Ingeniería, con conocimientos técnicos avanzados sobre el
referencia a esto, a finales de 2013, durante la discusión del funcionamiento y uso de Internet, aunque no entrenados en
nuevo Código Integral Penal en Ecuador, se promovió los mecanismos de protección de los servicios que se
(aunque finalmente no prosperó), la inclusión de un artículo despliegan en la red.
que disponía a los proveedores de servicios de
telecomunicaciones, e incluso a quienes compartiesen su Si bien las conclusiones que de las preguntas se obtengan no
servicio de acceso a Internet, conservar los datos de los son en ningún caso extrapolables a toda la población
usuarios de dichos servicios, con el fin de que pudiesen servir ecuatoriana, vale la pena notar que son un interesante punto
como evidencia probatoria en investigaciones penales (de ser de partida, ya que la muestra sobre la que se aplican podría
necesario), lo que generó mucha preocupación en ciertos decirnos algo sobre los grupos con reducido conocimiento
sectores de la sociedad ecuatoriana [3]. técnico acerca de Internet.

Finalmente, es común que aunque mucha gente está 3.2 Riesgos Directos para la Privacidad en Internet
medianamente informada sobre los riesgos a los que se
enfrenta su privacidad en Internet, ésta decide de todos Comúnmente, los riesgos para la privacidad de un usuario en
modos entregar información personal privada (nombres Internet son estudiados conforme a un modelo de ataque
completos, ubicación geográfica, números de tarjetas de indirecto en el que el atacante identifica o clasifica a dicho
crédito, etc.) a cambio de ciertos servicios (relaciones usuario en función de un conjunto de datos que, aunque
sociales, acceso a información, etc.) en una suerte de aparentemente desagregados (etiquetas, palabras de
transacción que se torna inevitable si se quiere aprovechar los búsquedas, intereses, sitios visitados, y en general un
recursos tecnológicos modernos de comunicaciones. disperso rastro digital), podrían permitir a un atacante

Revista Politécnica - Septiembre 2015, Vol. 36, No. 1

 Estrada J. A.*; Estrada J. C.**; Rodríguez A.*; Tipantuña C.*
_______________________________________________________________________________________________________________________________

identificar a su víctima y posteriormente vulnerar su En primera instancia, al pedir a los encuestados que definan
privacidad al inferir información crítica de ella. la palabra “privacidad”, se observa que se la relaciona

Estos estudios, sin embargo, dejan de lado la información íntimamente con la información personal y con la idea de
manifiestamente personal o privada de los usuarios que se derecho individual. En menor medida, se asocia la privacidad
encuentra accesible a través de Internet. Es de suponerse que a la palabra espacio, lo que quizás sugiere una referencia a la
esta información se debería conservar más segura que otra dimensión “física” de la privacidad (intimidad). En la Fig. 2
información aparentemente no tan privada (como la descrita se ilustra esta interpretación, que ya denota una visión
en el párrafo anterior). Sin embargo, hay deficiencias en el moderna del término, seguramente determinada por la edad
manejo mismo de la información en Internet desde distintas (18-24 años) y el nivel de educación de los encuestados.
instancias públicas y privadas, lo que podría facilitar
significativamente el trabajo de los atacantes. Además, Por otro lado, si bien la gran mayoría de encuestados (97 %)
mucha de la información personal de los individuos ya está está de acuerdo en que los usuarios pierden el control de la
disponible en línea (en muchos casos es provista por el información personal al ser recopilada por las compañías de
mismo titular) evitando que dichos atacantes tengan que Internet, más del 90 % ha escuchado poco o nada sobre la
hacer un trabajo muy sofisticado para vulnerar la privacidad posibilidad de que los gobiernos recopilen información de
de sus víctimas. llamadas telefónicas, mensajes de correo y otras
comunicaciones en línea. Estos resultados se obtienen a pesar
Con el fin de poner de manifiesto estos riesgos directos a la de la enorme inquietud causada por las actividades de
privacidad de la información de los usuarios en Ecuador, se espionaje imputadas a EEUU, incluso a grandes potencias
analizaron varios sitios web que alojan información personal europeas.
de los ciudadanos y que podría ser utilizada para vulnerar la
intimidad de los dueños de esos datos. Luego, mediante un
sencillo ejercicio deductivo, se ilustra cómo la información
disponible en Internet sobre un usuario permitiría intuir, con
relativa facilidad, detalles sensibles (de acuerdo a la
percepción medida) sobre la intimidad de éste.

3.3 Ilustración de los Riesgos de Privacidad en línea en

Ecuador

Para determinar el impacto de los riesgos a la privacidad de

los ciudadanos ecuatorianos en Internet, se correlaciona la
percepción de los usuarios acerca de la privacidad y la
sensibilidad de sus datos con las amenazas directas existentes
en el Ecuador y que son producto del despliegue de servicios Figura 2. Nube de palabras que ilustra la frecuencia con la que se
de información en línea. Se ilustra un posible escenario de mencionan las palabras en la definición de privacidad de los usuarios
ataque a la privacidad de un usuario, para demostrar la
preocupante facilidad con la que se podría recopilar sus datos A casi el 80 % de encuestados le preocupa que autoridades en
personales en línea, a partir de elementos de información que la jerarquía laboral (o de estudios) accedan a la información
los mismos usuarios consideran como “no sensibles”. que los primeros comparten en redes sociales. Considerando
que un porcentaje similar está de acuerdo en que es muy
4. PERCEPCIÓN SOBRE LA PRIVACIDAD EN difícil o imposible borrar información inexacta sobre un
ECUADOR individuo en Internet, se puede pensar que entre los
encuestados hay una muy sólida percepción de los riesgos
Luego de una vorágine de escándalos de espionaje atribuidos que, al menos en el ámbito laboral, podría acarrear la pérdida
a la Agencia de Seguridad Nacional de los EEUU (NSA, por de la privacidad.
sus siglas en inglés) [18] a partir de las revelaciones que
hiciera el ex agente Edward Snowden [21], se evidencia que Otra contradicción interesante muestra que el 96 % de los
la conciencia que tiene la gente sobre su privacidad en encuestados espera tener los mismos derechos legales sobre
Internet (y los graves riesgos que la amenazan) se ha sus datos en línea que los que tiene sobre los datos en su
modificado significativamente. Esto, sin duda, es también computador personal; sin embargo, el 62 % de ellos nunca (o
consecuencia del nivel de formación y de contacto con la casi nunca) lee las políticas de privacidad de los sitios que
tecnología que adquiere la gente. Este fenómeno se visita en Internet, como normalmente sí lo haría al firmar un
manifiesta en los resultados de la encuesta realizada y, contrato en la “vida real”.
aunque muestran en general que hay una marcada
preocupación sobre la privacidad de los datos en Internet, Al consultar a las personas sobre la información privada que
esta preocupación no se lleva a la práctica en acciones que no desearían compartir en Internet, se encontró que los datos
deriven en la protección de este derecho individual. económicos individuales (detalles de tarjeta de crédito,

Revista Politécnica - Septiembre 2015, Vol. 36, No. 1

 Ecuador y la Privacidad en Internet: Una Aproximación Inicial
_________________________________________________________________________________________________________________________

cuenta bancaria e ingresos) son los más sensibles, tal como se 5.1 La Ley de Transparencia
ilustra en la Fig. 3.
Para empezar, en Ecuador en 2004 fue aprobada la Ley
Orgánica de Transparencia y Acceso a la Información
Pública (LOTAIP), con el objetivo de garantizar el acceso a
la información pública del estado, en función del artículo 91
de la Constitución vigente. Sin embargo, esta ley define de
forma muy general lo que considera como información
pública, abarcando todo documento que se encuentre en
poder de las instituciones públicas (art. 5). Y, aunque se
define (art. 6) lo que en el ámbito anterior se puede
considerar como información confidencial, esta
confidencialidad se aplicaría sobre la base de los derechos
civiles (Constitución de 1998) o de libertad (Constitución
vigente) que, en lo que respecta a este estudio, se refieren de
forma muy vaga a la intimidad personal. Así, se deja sin
acotar la información pública de aquella que, quizás, no
debería serlo. Esta ley dispone a las instituciones públicas
que publiquen periódicamente cierta información mínima; de
Figura 3. Tabulación de los tipos de información y la sensación de los lo contrario, los funcionarios responsables podrían ser
encuestados sobre compartirlos. Indica el número de personas no quisiera sancionados incluso con la remoción del cargo.
compartir cada tipo de información.
Entre los datos que esta ley dispone transparentar está la
El número de identificación (cédula de ciudadanía) es
remuneración mensual por puesto y que al momento se
considerado también un parámetro sensible para la
publica en el sitio web de (prácticamente) todas las
privacidad. Curiosamente, el nombre completo no está entre
instituciones públicas en cumplimiento del literal c del
los datos considerados más privados, así como tampoco la
artículo 7 de la LOTAIP. Aunque este artículo no dispone
fecha de nacimiento y el estado civil. Se puede observar
que al publicar esta información cada puesto esté asociado a
también que el historial médico, el de viajes y la dirección
la identidad de quien lo ocupa, en prácticamente todas las
postal están en una región intermedia, concebidos como
instituciones públicas esta información salarial se pone en
sensibles por al menos la mitad de la muestra consultada.
línea junto con el nombre completo de los servidores
públicos. Considerando que la información financiera
Al ser consultados sobre la sensibilidad que se asigna
individual es la más sensible, según la encuesta analizada
(individualmente) a varios tipos de datos, se observó que se
previamente, la publicación de esta información parece algo
considera sensible y muy sensible al número de cédula,
que se podría discutir (o modificar) en beneficio de la
historial de salud y medicinas consumidas, contenido de
seguridad de los servidores públicos.
conversaciones telefónicas, mensajes de correo, ubicación
física en el tiempo, historial de llamadas, historial
5.2 La Ley de Contratación Pública
sentimental, historial de navegación, relaciones de amistad y
lugar de votación. Por otro lado, los encuestados asignaron
un nivel de sensibilidad bajo o inexistente a sus hábitos Otra normativa que busca transparencia, en este caso en los
alimenticios, su fecha de nacimiento, y a sus puntos de vista procesos de adquisiciones para el sector público, es la Ley
religiosos y políticos. Orgánica del Sistema Nacional de Contratación Pública
(LOSNCP). Entre otros datos, esta ley dispone publicar los
Finalmente, pese a que se reconoce a casi toda la información pliegos de contratación, que contienen “información técnica,
como sensible, la mayoría de las respuestas apuntan a que la económica y legal del proceso […] como planos, estudios,
restricción del uso de los computadores o del servicio de especificaciones técnicas […]”. En el campo tecnológico, es
acceso a Internet no es la solución. fácil imaginarse toda la información (cantidad de equipos,
marcas, software de servicios y sus respectivas versiones)
5. EXPLORACIÓN PRELIMINAR SOBRE LA que puede recopilar un atacante sobre la infraestructura
PRIVACIDAD DE LOS DATOS EN ECUADOR tecnológica de una dependencia pública en la fase de
reconocimiento de un ataque informático, sin necesidad de
Durante los últimos años, el Estado ecuatoriano ha venido hacer ingeniería social o escaneo de red, sólo mediante una
promoviendo profundas medidas para la constitución de una pasiva, legal e indetectable recopilación de información
plataforma de gobierno electrónico. En esa línea, se han públicamente disponible. Luego, este atacante podría utilizar
puesto en marcha varias iniciativas en la forma de sistemas información técnica (versiones de software) para intuir
informáticos que manejan información de instituciones vulnerabilidades de una red y reducir significativamente el
públicas, empresas y ciudadanos, y cuya disponibilidad y ámbito de un ataque posterior.
agregación podrían incorporar ciertos riesgos a la privacidad
de los agentes previamente mencionados.

Revista Politécnica - Septiembre 2015, Vol. 36, No. 1

 Estrada J. A.*; Estrada J. C.**; Rodríguez A.*; Tipantuña C.*
_______________________________________________________________________________________________________________________________

5.3 La Ley del Sistema Nacional de Registro de Datos sea luego cambiada. Justamente ahí radica el riesgo a la
Públicos (LSNRDP) privacidad de un usuario que se ve obligado a exponer sus
datos personales a cambio de un poco de ayuda para ingresar
La LSNRDP (descrita en la Sección 2), en el artículo 31, al sistema.
dispone consolidar, en una base de datos única, todos los
registros públicos. Así, la entidad encargada de coordinar el 5.5 Los Datos de Facturación Electrónica
cumplimiento de la ley (DINARDAP) implementó el Sistema
Dato Seguro. Este sistema agrupa la información de los El Servicio de Rentas Internas, en resolución del 6 de mayo
ciudadanos obtenida de doce entidades públicas, entre ellas: de 2013, dispuso la obligación de ciertos contribuyentes
Servicio de Rentas Internas, Registro de la Propiedad, (instituciones financieras, empresas públicas, contribuyentes
Instituto Ecuatoriano de Seguridad Social y Registro Civil. especiales, entre otros) de emitir comprobantes (facturas,
Por lo tanto, se almacena información individual de: datos de retenciones, etc.) únicamente a través de mensajes de datos y
identidad y de contacto, datos financieros (pago de firmados electrónicamente; proceso que en términos
impuestos, aportaciones de seguridad social), bienes coloquiales se conoce simplemente como facturación
inmuebles, compañías, relaciones laborales, infracciones de electrónica. El problema radica en que muchos de los
tránsito, etc. Mucha de esta información es efectivamente contribuyentes especiales que ahora facturan
pública y ya está disponible en línea; sin embargo, su electrónicamente, lo hacen a través de sistemas informáticos,
consolidación encarna graves riesgos adicionales para la la mayoría de ellos tercerizados (alojados en empresas de
privacidad de las personas, especialmente si los mecanismos terceros), accesibles desde Internet (para que un consumidor
de autenticación para acceder a este sistema son débiles pueda consultar su factura), y con inexistentes (o débiles)
(como al final lo llegan a ser todos en Internet, tanto como las mecanismos de autenticación o autorización para el acceso a
personas que los usan). En sus inicios, Dato Seguro mostró dicha información. Del análisis exploratorio realizado, esto
ciertas fragilidades (para el registro sólo validaba un par de básicamente significa que un atacante podría encontrar estos
dígitos de la cédula de identidad) que permitieron el acceso sistemas en Internet (usando un motor de búsqueda, o en la
no autorizado a la cuenta del Presidente de la República [13]. página del contribuyente) porque son públicos y, usando
Hoy, el mecanismo de registro es un poco más estricto, pero solamente el número de cédula de su víctima, sería capaz de
la información de validación que se solicita se podría obtener detalles de las facturas (y por tanto consumos) que se
conseguir con relativa facilidad de otras fuentes, igualmente han emitido a dicha víctima.
en línea.
Esto es posible ya que algunos de estos sistemas publican
5.4 Los Datos de la Seguridad Social estos documentos personales incluso masivamente, otros no
tienen mecanismos de autenticación (sólo piden el número
Con el fin de facilitar algunos trámites y consulta de cédula para acceder a la lista de facturas) o, si lo tienen, el
información, el Instituto Ecuatoriano de Seguridad Social mecanismo de registro (la primera vez) es deficiente. Entre
(IESS) mantiene habilitada, desde hace al menos 5 años, una los problemas observados que podrían derivar en amenazas a
plataforma informática accesible desde Internet que poco a la privacidad de los usuarios (cuya gravedad podría variar
poco ha ido incorporando una gran cantidad de servicios para dependiendo del tipo de consumos) se encuentran los
el afiliado, entre ellos: agendamiento e historial de citas siguientes:
médicas, historial laboral y solicitud de préstamos.
Considerando que, según nuestra encuesta, más del 60 % de a) Almacenamiento y despliegue público de todos los
consultados sugiere que no compartiría la información de su documentos de facturación emitidos en una sola
historial médico, es razonable afirmar que este servicio en página web, sin restricción alguna.
línea recoge información privada, muy sensible para sus
usuarios. El proceso de registro (acceso por primera vez) en b) Acceso a los documentos con autenticación basada
el sistema se lo hace en línea y requiere contestar solamente en el número de cédula o parte de éste, o
correctamente tres preguntas sobre el historial de afiliación en su uso como nombre de usuario y contraseña.
del individuo. Tal como sucede con otros sistemas en los que
la primera validación del usuario se la realiza en línea, las c) Utilización de una misma contraseña sencilla para el
preguntas en las que se basa el registro en la plataforma del acceso de todos los usuarios (1234, por ejemplo) al
IESS, tienen respuestas que un atacante podría obtener sistema de consulta de facturas emitidas.
mediante técnicas de ingeniería social o, si conoce un poco a
la víctima, mediante una reflexión deductiva simple. Por otra d) Proceso de registro y creación de cuenta basados en
parte, este proceso de registro resulta tan engorroso para el número de cédula y sin validación de identidad.
usuario común, que éste normalmente termina acudiendo a
un centro de cómputo donde estos trámites son tan frecuentes e) Utilización del número de documento (número de
que hasta tienen una tarifa definida por el soporte técnico que factura) como contraseña para el acceso al
ofrecen a los afiliados para ingresar al sistema. Esto implica documento de facturación.
que el afiliado le indique su contraseña al empleado del
centro de cómputo, con muy pocas probabilidades de que ésta

Revista Politécnica - Septiembre 2015, Vol. 36, No. 1

 Ecuador y la Privacidad en Internet: Una Aproximación Inicial
_________________________________________________________________________________________________________________________

Adicionalmente, en la Tabla 1, se resumen algunos de los De la encuesta, está claro que los usuarios están conscientes
tipos de contribuyentes cuyos sistemas se analizaron. Cabe de los riesgos a su privacidad en Internet y que estos se
destacar que, para la obtención de esta información se realizó concentran en la información. Sin embargo, parecen no
una observación simple de los mecanismos de autenticación percibir que información aparentemente no sensible puede
utilizados, luego de haber adquirido un producto y de recibir correlacionarse para encontrar información muy sensible ya
acceso a nuestra factura electrónica en el sistema respectivo. que las huellas que dejamos en Internet son casi imposibles
Por tanto no se utilizó ninguna técnica intrusiva, ni se vulneró de borrar. Lo curioso es que los mismos encuestados
la privacidad de ningún usuario. reconocen la pérdida de control sobre los datos que sobre sí
mismos se encuentra en Internet, pero no alcanzan a percibir
5.6 El número de cédula de ciudadanía el impacto negativo que podría tener el procesamiento de
esos datos para obtener información privada.
Vale la pena notar que la cédula en Ecuador es un documento
La mayor preocupación percibida se centra en los datos
al que se asocia mucha información personal y, en general,
financieros individuales, el historial médico, los datos de
privada, a tal punto que contiene datos (no sólo el número
contacto telefónico, y el número de cédula. Estos son, sin
sino también otros datos de este documento) que se utilizan
duda, datos de carácter privado cuya difusión podría afectar
como contraseña o mecanismo de validación de registro en
significativamente a su dueño. Sin embargo, como ya se
los sistemas de información antes mencionados.
sugirió, según la percepción de los usuarios y varios de los
escenarios analizados de información expuesta, algunos de
Consecuentemente, para evidenciar el riesgo que corre la
los datos considerados menos sensibles podrían facilitar
privacidad de un usuario en Internet (en Ecuador) sólo hay
enormemente un ataque a la privacidad de estos usuarios.
que recordar lo fácil que resulta obtener el número de cédula
de los cientos de copias de cédula que entregamos en algún
Entre los datos no tan sensibles para los encuestados
trámite, o de las decenas de hojas de vida (donde colocamos
tenemos: el nombre completo (o parte de él), la fecha de
este número) que presentamos para conseguir empleo. Por lo
nacimiento, el grado académico, y hasta el estado civil. Esto
tanto, la sola divulgación del número de cédula es, al menos,
indicaría que la muestra de encuestados estaría dispuesta a
un parámetro generador de riesgo a la privacidad de los
aligerar su preocupación por este tipo de datos por
usuarios en el contexto en el que ahora se desenvuelve la
considerarlos menos críticos. Sin embargo, si un atacante
sociedad ecuatoriana, tal como se puede ilustrar en la
desea empezar a indagar sobre su víctima, le basta conocer su
siguiente sección.
nombre y su alma máter. Si el atacante no conociera el
Tabla 1. Deficiencias de seguridad (riestos de privacidad) encontrados en los
nombre completo de su víctima, y si ésta posee un grado
sistemas de gestión de facturación electrponica de varios tipos de académico de tercer nivel, seguramente su tesis de grado será
contribuyentes. Las deficiencas están codificadas de acuerdo a la sección 5.5 pública y en ésta se podrá encontrar el nombre completo de la
Tipo de
Cantidad Deficiencias víctima, así como información adicional (probablemente en
Contribuyente la dedicatoria). Para averiguar el número de cédula, es
Farmacia 2 b), d suficiente consultar el sistema de verificación de títulos de la
Alimentos 9 b), c), d) Secretaría de Educación, Ciencia y Tecnología que entrega
información de los títulos de un ciudadano (y el número de
Empresa Pública 3 a)
cédula) solo con pasarle el nombre (o parte de éste). Tal
Ropa 1 e) como se notó en la sección anterior, el número de cédula ya
Entretenimiento 2 b), d) podría ser la puerta de entrada hacia algunos sistemas de
información del usuario (a los de facturación electrónica
Deportes 1 a) especialmente). Si el atacante no está satisfecho, y si la
víctima no ha activado su cuenta de Dato Seguro, éste podría
animarse a realizar el registro por la víctima, suplantando la
6. DISCUSIÓN SOBRE UN ESCENARIO DE RIESGO DE identidad de la víctima (lo cual podría configurar un delito).
LA PRIVACIDAD EN ECUADOR
Al intentarlo, el sistema le pide validar su identidad mediante
Se ha realizado un análisis preliminar de la privacidad en la respuesta a tres preguntas. Para el registro, el sistema
Ecuador: ciertas percepciones de los ciudadanos y algunos de solicita tres datos: fecha límite de declaración del impuesto al
los riesgos de la privacidad en Internet. Para medir la valor agregado, provincia de sufragio, y cantón del
percepción de los usuarios se realizó una encuesta y, para matrimonio civil (si se es casado y, si no, se debe indicar que
detectar los riesgos de la información personal pública en el se es soltero). Los tres datos, conociendo el número de cédula
país, se ejecutó una exploración no intrusiva de la del individuo, son públicos en línea en respectivos sistemas
información disponible en sistemas de información en del SRI, Consejo Nacional Electoral y Registro Civil (un par
Internet. Se evaluó el impacto que podría tener esta de meses luego de la versión inicial de este artículo, ya no es
información públicamente accesible en función de la posible obtener información de estado civil).
percepción medida de los usuarios sobre su privacidad en
línea. Considerando que los datos financieros son los percibidos
como más sensibles por los encuestados, resulta preocupante

Revista Politécnica - Septiembre 2015, Vol. 36, No. 1

 Estrada J. A.*; Estrada J. C.**; Rodríguez A.*; Tipantuña C.*
_______________________________________________________________________________________________________________________________

que sea posible encontrar tanta información pública de los 7. CONCLUSIONES

ciudadanos en esa categoría. Una vez que un atacante ha
logrado obtener datos de identificación de sus víctimas, En este artículo se ha intentado hacer una modesta
podría intentar perfilarlas en función de sus ingresos aproximación preliminar sobre el estado de la privacidad en
económicos. Esto es perfectamente posible mediante la Ecuador, en el contexto de la información personal pública de
información del impuesto a la renta causado que es pública los ciudadanos que se gestiona en sistemas de información en
en el sitio web del Servicio de Rentas Internas, o a través de Internet. Existe una actitud de preocupación frente a los
la remuneración mensual por puestos que publican todas las riesgos de privacidad en línea que se manifiesta en una
entidades públicas (si la víctima es empleado público). encuesta de percepción. Sin embargo, esta actitud no se
expresa en un criterio más reflexivo y activo sobre la
Al tener el nombre de la víctima o su número de información pública de los ciudadanos en Internet, pues no se
identificación, un atacante podría también indagar sobre los comprende aún la magnitud de la cantidad de información de
bienes inmuebles que posee la víctima al consultar el sistema usuario que se encuentra en línea. Por otro lado, la migración
en línea del respectivo municipio pues, en ciertas ciudades en en Ecuador de servicios y trámites (públicos y privados) a
el país, esta información también es pública y fácilmente plataformas en la Web plantea varios riesgos a la privacidad
accesible. de los ciudadanos que las emplean, pues abundante
información “no sensible” podría correlacionarse para
Tomando en cuenta que el historial de salud es otra de las obtener información “sensible”.
categorías sensibles para la privacidad de los encuestados, es
interesante notar cómo un atacante podría acceder a Además, los mecanismos de seguridad para el acceso a
información de los medicamentos consumidos por su víctima plataformas con información personal y la cultura misma de
explotando las vulnerabilidades de autenticación (Tabla 1., manejo de información de los usuarios son deficientes y esto
ítem Farmacia) de los sistemas de facturación electrónica. Lo facilitaría enormemente la recopilación de datos personales.
más preocupante es que, en ciertos casos, para ello, el Lo más grave es que, para obtener información personal
atacante solo necesita conocer el número de cédula de su crítica (datos financieros, por ejemplo, según la percepción
víctima, que previamente obtuvo a partir del nombre de ésta, medida), un atacante sólo necesitaría partir de ciertos datos
y que este parámetro (nombre completo) no es percibido considerados no críticos (como el nombre de una persona) y,
como sensible por lo que no hay interés de protegerlo. ya que estos datos no se perciben como sensibles por los
usuarios, existirá mayor probabilidad de que no sean
Pero los riesgos a la privacidad en Ecuador no solamente se protegidos adecuadamente.
enfocan solamente a los individuos sino también a las
organizaciones, y en particular a las entidades públicas. Tal Aunque es deseable la transparencia en la gestión pública y
como se indicó en la sección 5, la Ley de Contratación especialmente en el manejo económico, sería importante
Pública dispone, en la mayoría de casos, publicar los evaluar el impacto de publicar cierta información personal (y
documentos de contratación de toda entidad pública. Esto no necesariamente privada) en ciertas garantías individuales
implica poner en línea información minuciosamente detallada de los ciudadanos.
de equipos y procesos que necesita dicha entidad.
Imaginemos solamente un proceso en el que una dependencia Ya que se trata de un trabajo inicial, no se pretendió ser
pública llama a concurso para contratar los servicios de exhaustivos (la muestra de la encuesta es pequeña) ni obtener
mantenimiento de sus equipos de red y seguridad. un diagnóstico definitivo, pero sí dar una pauta para la
investigación de la privacidad de la información en el país,
De los documentos del proceso, un atacante podría inferir, sin desde el punto de vista técnico y cultural (multidisciplinario).
mucho esfuerzo, el tipo de infraestructura de red de la En trabajos futuros, se podría plantear una muestra más
organización, la marca de los equipos, y las versiones de amplia y representativa de la población ecuatoriana para la
software con que funcionan. Al contratar servicios de medición de las percepciones de los ciudadanos sobre su
mantenimiento, la organización podría necesitar publicar privacidad. También sería interesante comparar los niveles de
incluso algún detalle de los problemas o inconvenientes que conciencia y preocupación (sobre la privacidad) con los de
tiene la infraestructura de red y que podrían ser aprovechados otros países, y determinar las divergencias existentes, así
por el atacante para vulnerar los sistemas de comunicaciones. como sus posibles causas. Esta investigación podría hacerse
de manera periódica para determinar, con cierta certeza,
Así, un atacante de la privacidad de un usuario o de una tendencias en la evolución del comportamiento de los
organización (no solo en Ecuador) sería capaz de obtener una usuarios y de los gestores de información frente a la
radiografía muy completa de su víctima (en términos de protección de la privacidad de los ciudadanos. De hecho, del
información personal o técnica), en la comodidad de su lado de las instituciones, se podría analizar también las
escondite, sin arriesgarse y (peor aún) sin despertar la más políticas de privacidad que publican en sus sitios web para el
mínima sospecha, pues estamos hablando de un análisis no manejo seguro de la información del usuario, y si
intrusivo, prácticamente imposible de detectar. efectivamente se implementan o están adecuadamente
definidas.

Revista Politécnica - Septiembre 2015, Vol. 36, No. 1

 Ecuador y la Privacidad en Internet: Una Aproximación Inicial
_________________________________________________________________________________________________________________________

REFERENCIAS
[1] B. Torres Espinoza (2010). Proyecto de ley orgánica de protección de
datos personales.
[2] D. Rebollo-Monedero, J. Parra-Arnau, C. Diaz, & J Forné (2013). On
the measurement of privacy as an attacker’s estimation error.
International journal of information security, 12(2), 129-149.
[3] Ecuadorinmediato (2013), Asociaciones digitales señalan preocupación
sobre privacidad en Internet tras aprobación del COIP en Ecuador. [En
línea] Recuperado de: http://goo.gl/ZHPWaI. Última visita: 15 de junio
de 2015.
[4] G. Hofstede (1984). Cultural dimensions in management and planning.
Asia Pacific journal of management, 1(2), 81-99.
[5] INEC (Instituto Nacional de Estadísticas y Censos), Censo TIC 2013.
[En línea] Recuperado de:
http://www.ecuadorencifras.gob.ec/tecnologias-de-la-informacion-y-
comunicacion-tic/. Última visita: 15 de junio de 2015.
[6] J. A. Estrada, & A. Rodríguez (2014). Evaluación de Protección de
Privacidad de una Herramienta de Navegador Web. Revista
Politécnica, 33(1).
[7] J. Parra-Arnau, D. Rebollo-Monedero, & J. Forné, (2014). Measuring
the privacy of user profiles in personalized information systems. Future
Generation Computer Systems, 33, 53-63.
[8] P. Kumaraguru, & L. Cranor (2006, January). Privacy in India:
Attitudes and awareness. In Privacy Enhancing Technologies (pp. 243-
258). Springer Berlin Heidelberg.
[9] G. Hofstede (2013). The Hofstede Centre. [En línea] Recuperado de:
http://geert-hofstede.com/ecuador.html. Última visita: 15 de junio de
2015.
[10] D. Malandrino, V. Scarano, & R. Spinelli (2013). Impact of Privacy
Awareness on Attitudes and Behaviors Online. SCIENCE, 2(2), pp-65.
[11] D. Schiller (2014). Geopolítica del espionaje: las ramificaciones del
caso Snowden. Le Monde diplomatique en español, (229), 1-9.
[12] D. U. de los Derechos Humanos (1948). Asamblea General de las
Naciones Unidas. París: ONU: http://www. un.
org/spanish/aboutun/hrights.htm.
[13] Ecuadorinmediato (2012), Director Informática de Fiscalía: bloguero
acceso de manera no consentida a registro del Presidente Correa en
Dato Seguro [En línea] Recuperado de: http://goo.gl/391i0d. Última
visita: 15 de junio de 2015.
[14] G. Cecere, F. Le Guel, & N. Soulié (2015). Perceived internet privacy
concerns on social networks in Europe. Technological Forecasting and
Social Change.
[15] J. CIESPAL (2014). Conferencia: Protección de datos y privacidad en
procesos electorales, hacia la Declaración de Ecuador y unificación de
criterios.
[16] M. F. C. Ronderos (2014). Legislación informática y protección de
datos en Colombia, comparada con otros países. Revista Inventum,
(17).
[17] M. H. Birnbaum (2004). Human research and data collection via the
Internet. Annu. Rev. Psychol., 55, 803-832.
[18] M. Kassen (2014), Globalization of e-government: open government as
a global agenda; benefits, limitations and ways forward. Information
Development, 30(1), 51-58.
[19] R. Goldfarb, D. Cole, E. Wasserman, T. Blanton, H. Carter, J. Mills, &
B. Siegel (2015). After Snowden: Privacy, Secrecy, and Security in the
Information Age. Macmillan.
[20] R. Warner, & R. H. Sloan (2015). The Self, the Stasi, the NSA:
Privacy, Knowledge, and Complicity in the Surveillance State.
ExpressO.
[21] UN Public Administration Programme, 2014 UN E-Government
Survey and E-Government Indicators, Bangkok, Thailand, Octubre,
2015.
[22] V. Toubiana, A. Narayanan, D. Boneh, H. Nissenbaum, & S. Barocas,
(2010, March). Adnostic: Privacy preserving targeted advertising. In
Proceedings Network and Distributed System Symposium.

Revista Politécnica - Septiembre 2015, Vol. 36, No. 1

1098 PROCEEDINGS OF THE I.R.E. September

A Method for the Construction of

Minimum-Redundancy Codes*
DAVID A. HUFFMAN+, ASSOCIATE, IRE
1952 Huffman: A Method for the Construction of Minimum-Redundancy Codes 1099