Algoritmos Randomizados

El Faq de las Máquinas de Turing

Este post es sólo un oráculo de algunas preguntas frecuentes para quién ya estudió teoria de la computación y con el tiempo ha ido olvidando algunos conceptos.

Que es una máquina de Turing?
Un Dispositivo
Que es un problema?
Un conjunto de frases de longitud finita que esta asociada a un conjuto de frases también de longitud finita.
Que es un problema decidible?
Un problema que su conjunto asociado solo tiene las frases si y no, es decir existe un método que ya consigue definir esos: si y no. Los problemas decidibles tienen un método definido que consigue decir si el problema(la sentencia) es cierto o falso.
Que es un algoritmo?
No existe un consenso, pero se puede decir que es una máquina de Turing.
Todo método que resuelve un problema decidible puede ser implementado en una máquina de Turing?
no sé. Creo que si.
Que es un problema indecidible?
Un problema para el cual no existe un método tal que sea capaz de resolverlo con una respuesta si o no.
Cuantas programas puedo escribir en una máquina de Turing?
Si es universal muchos, recuerde que una máquina de Turing Universal permite simular cualquier máquina de Turing para cualquier entrada.
Que es PP?
Es la clase de problemas de decisión para los cuáles existe un algoritmo de Montecarlo bilateral que responde si cuando la respuesta correcta es si con probabilidad > 1/2 (idem para no) y el tiempo de ese algoritmo es es un polinómio en el tamaño de la entrada. Otra definición equivalente, es la clase de problemas resolubles por una MT probabilística en tiempo polinomial con probabilidad > 1/2 para todas sus instancias.
NP \in PP?
Si. El problema de la factoración esta en NP, por tanto en PP, entonces existe un algoritmo de montecarlo que consigue factorar como descrito en la pregunta anterior, sólo que máquinas de Turing probabilisticas no existen (en general las no deterministas no existen) y las que se simulan estas no son eficientes, es decir no consiguen factorar en tiempo polinomico.

Compuscientia 2013

CompuScientia es una revista que busca difundir los diferentes caminos que ofrece el inmenso mundo de la Computación: aplicaciones tecnológicas, áreas de investigación, recomendaciones legales, fuentes de financiamiento de proyectos, oportunidades laborales, entre otros. Siendo así, la revista está dirigida a jóvenes estudiantes de pre y posgrado, profesionales y entusiastas de diferentes carreras de Computación y afines.

La Computación y la Tecnología van de la mano, y hoy son dos de los pilares del desarrollo mundial. En consecuencia, CompuScientia tiene el objetivo de presentarlos como agentes importantes para el desarrollo sostenido del país.

CompuScientia es una revista para todos los interesados en conocer más acerca del mundo de la Computación y Tecnología. En CompuScientia les hacemos partícipes de las diversas oportunidades académicas, profesionales y laborales que les pueden interesar.

Para mas información ingresar a la web aquí

Esquema de Firma Digital Pos Cuántico Lamport-Diffie

Este esquema de firma digital fue propuesto en el año de 1979. Es uno de los primeros en ser estudiados dentro de los esquemas de firma digital que se consideran resistentes ataques cuánticos dada su simplicidad para entender. A continuación describiré los algoritmos usados tanto para la generación de llaves como para el proceso de firma y verificación.

Generación de Llaves:
Escoger dos funciones

1. Una función de Mano Única: $$f:\{0,1\}^n \rightarrow \{0,1\}^n$$
2. Una función Hash $$g:\{0,1\}^{*}\rightarrow \{0,1\}^n$$

La llave  de firma, X, consiste de $2n$ cadenas de bits de tamaño $n$ elegidas de forma aleatoria uniformemente.
$$X=(x_{n-1}[0], x_{n-1}[1],\cdots,x_0[0],x_0[1])\in \{0,1\}^{n,2n}$$
La llave de verificación, Y, es:
$$Y=(y_{n-1}[0], y_{n-1}[1],\cdots,y_0[0],y_0[1])\in \{0,1\}^{n,2n},$$
donde $$y_i[j] = f(x_i[j]).$$

Firma:
Un documento $$M\in \{0,1\}^{*}$$ es firmado usando la llave X, usando $$d=g(M)=(d_{n-1},\cdots,d_0)$$ como $$\sigma = (x_{n-1}[d_{n-1}],\cdots,x_{0}[d_0])\in \{0,1\}^{n,n}$$
Verificación:
Para verificar $\sigma$ el verificador calcula g(M) y verifica si
$$(f(\sigma_{n-1}),\cdots,f(\sigma_0))=(y_{n-1}[d_{n-1}],\cdots,y_0[d_0]).$$

La seguridad de este esquema esta basada en dos nociones de seguridad: resistencia a pre-Imagen que presentan las funciones de mano única y la resistencia a colisiones que presenta una función hash criptográfica. Como ya vimos justamente el esquema Diffie-Lamport usa una función de mano única y una función hash. Funciones hash y funciones de mano única solo admiten ataques genéricos contra las dos nociones de seguridad mencionada. Para ataques contra la noción de resistencia a colisiones, usando un computador clásico, se usa Ataque de Cumpleaños el cual tiene complejidad O(2^{n/2}) de encontrar colisiones con probabilidad 1/2. Para ataques contra la noción de resistencia a pre-imagen, usando un computador clásico, se usa fuerza bruta, la cual en este caso, tiene complejidad de O(2^{n/2})  de encontrar pre-imagen con probabilidad 1/{2^{n/2}}. En el caso de uso de computadores cuánticos para crear ataques contra estas nociones de seguridad lo mejor que se pueda usar es el algoritmo de Groover. Este algoritmo, adaptado para estos ataques, tiene complejidad de O(2^{n/3}) con probabilidad 1/2 de encontrar colisiones y complejidad O(2^{n/3}) de encontrar pre-imágenes con probabilidad  1/{2^{n/3}}, [1,pag 90]. Es por eso que se dice que este esquema de firma digital, con sus limitaciones, es una alternativa para esquemas basados en problemas de la teoría de números como factorización de números grandes y el problema de logaritmo discreto.

[1] Johannes; Dahmen, Erik, eds. (2009). Post-quantum cryptography. Springer

Ejemplo Criptosistema McEliece en SAGE

En el 1978 McEliece presentó un nuevo criptosistema de clave pública, basado en la Teoría de los Códigos. Dado que esta teoría es muy compleja, los expertos recomiendan una familiarización matemática preliminar con la Teoría de la Codificación, los Códigos de Goppa, y los Cuerpos de Galois.

 En el sistema de McEliece, cada usuario ha de elegir un polinomio irreducible de grado $delta$, y construir una matriz generadora del correspondiente código de Goppa, matriz G, de orden k x n. También ha de calcular la llave pública, que es una matriz generadora del código Goppa. Este código debe ser  tal que no exista un algoritmo computable que corrija los errores con éste código en un tiempo pequeño. La llave pública es obtenida a partir de la multiplicación de una matriz aleatoria no singular de orden 2^m-k*m, y una matriz de permutaciones de orden 2^m. Todos los usuarios del sistema mantienen sus respectivas llaves públicas, mientras que las matrices S,G e P serán secretas.

A continuación presentamos el algoritmo para generación de las llaves, cifrado de un texto plano y descifrado de un texto cifrado, según wikipedia, y su respectiva implementación mediante un ejemplo en SAGE. Es necesario "correr" primero la última de las celdas de este post, la cual contiene los algoritmos auxiliares como por ejemplo el algoritmo de Patterson.

Generación de Llaves

1. Alicia selecciona un código de Goppa binario Gamma com parâmetros (n,k) y capacidad de correción de delta errores; 
2. Alicia gera a matriz geradora $G$, de dimensiones n-m*k x n, del código \Gamma; Selecciona una matriz binaria no singular S, de dimensiones;n-m*k x n-m*k; 
3.  Selecciona una matriz de permutación P, de dimensión n; 
4.  Computa a matriz $G' = SGP; 
5.  La llave pública de Alicia é (G',delta) y su llave privada es (S,G,P).

Sistema Demostrablemente Seguro

Hace ya algunos dias que estoy queriendo dejar en claro algunos conceptos de seguridad que ya había aprendido y que por el paso del tiempo estaban confusos. Esos conceptos por ejemplo son nociones de seguridad, modelos de ataque, seguridad demostrable etc. Como siempre, lo que entiendo después de la lectura intentó escribirlo como se puede ver en mis entradas Propiedad de la Indistinguibilidad en Criptosistemas, Modelos de Ataque.

Siguiendo con la recordación, en esta entrada escribo un resumen acerca del concepto sistema demostrablemente seguro (provably secure).

Dado un criptosistema como podemos probar su seguridad?

• Tratando de montar un ataque
• Si el ataque fue encontrado entonces el criptosistema no es seguro.
• Si el ataque no fue encontrado no se puede decir nada acerca de la seguridad del criptosistema.
• Probando que no existe ataque bajo algunas asunciones.
• Publicar la verificabilidad de la prueba
• Ataque encontrado, entonces las asunciones fueron falsas

Como hacer esa prueba bajo asunciones?

• Describir  un criptosistema y sus modos operacionales,
• Formalmente definir la noción de seguridad a lograr = (objetivo que el atacante atacaria + modelo de ataque ). Ejm: IND-CCA2, IND objetivo e CCA2 modelo de ataque.
• Realizar asunciones computaciones, (problema factoración, problema logaritmo discreto, dureza de la decodificación de Códigos de Goppa Binário, etc).
• Exhibir una reducción entre un algoritmo que rompe la noción de seguridad y uno que rompe la asunción computacional. Ejemplo (RSA is reducible para OW-CCA2(S)).

¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!

Propiedad de la Indistinguibilidad en Criptosistemas

Actualmente esta propiedad la poseen la mayoría de criptosistemas. Un criptosistema es denominado seguro en términos de indistinguibilidad si, dado el par de textos planos M0, M1 y el texto cifrado C, no existe atacante que tenga probabilidad mayor al que tendría un atacante con la probabilidad 1/2, para poder afirmar si el texto cifrado C pertenece al cifrado de M0 o M1.

Indistinguibilidad bajo CPA (IND-CPA):

Para criptosistemas asimétricos esta propiedad es definida como un juego en la que los jugadores son un desafiador y un atacante. El juego consiste en:

1. El desafiador crea sus claves publica PK y privada SK;
2. El atacante puede usar PK para cifrar los mensajes de texto plano que el desee;
3. El atacante envía para el desafiador los textos planos M0 y M1;
4. El desafiador elige aleatoriamente uno de los dos mensajes, ME, y lo cifra con el algoritmo de cifración E en C = E(PK, ME);
5. El atacante es libre de hacer nuevas cifraciones. Finalmente el adversario da su respuesta acerca de si C es E(PK, M0) o E(PK, M1).

Un sistema es dicho IND-CPA seguro si el atacante no tiene una probabilidad notoria de ganar el juego en relación con otro atacante que tenga la probabilidad 1/2 de ganarlo.

Indistinguibilidad bajo CCA (IND-CCA/IND-CCA2):

Al igual que en la propiedad anterior, esta es definida como un juego en la que los jugadores son un desafiador y un atacante. El juego consiste en:

1. El desafiador crea sus claves publica PK y privada SK;
2. Dado que el atacante tiene acceso a PK entonces puede hacer cualquier número de cifraciones, así como también puede descifrar texto cifrados usando un oracle de deciframiento.
3. El atacante envía para el desafiador los textos planos M0 y M1;
4. El desafiador elige aleatoriamente uno de los dos mensajes, ME, y lo cifra con el algoritmo de cifración E en C = E(PK, ME);
5. El atacante puede realizar mas cifraciones si lo desea. Si el modelo de ataque del desafiador es:
1. CCA entonces el atacante no puede realizar mas decifraciones de textos cifrados, usando el oracle.
2. CCA2 entonces el atacante puede realizar mas decifraciones de textos cifrados, usando el oracle, excepto C.
6. Finalmente el adversario da su respuesta acerca de si C es E(PK, M0) o E(PK, M1).

Un sistema es dicho IND-CCA/CCA2 seguro si el atacante no tiene una probabilidad notoria de ganar el juego en relación con otro atacante que tenga la probabilidad 1/2 de ganarlo.

La indistinguibilidad bajo CPA (IND-CPA) es una propiedad que la poseen los sistemas denominados probadamente seguros. IND-CPA es equivalente a la propiedad de seguridad semántica en criptosistemas, por lo cual muchas veces esta equivalencia  es usado para pruebas criptográficas. Algunos sistemas criptográficos también ofrecen la indistinguibilidad bajo CCA (IND-CCA).

La indistinguibilidad contra ataques adaptativos para sistemas criptográficos de llave pública fue introducida por Rackoff and Simon.

Modelos de Ataque CPA y CCA

Ataque de Texto Plano Escogido.-  Es un modelo de ataque que tiene por objetivo descubrir la clave de cifrado de un criptosistema. Consiste en encriptar mensajes planos, por parte del atacante, con el fin de obtener información acerca de la clave usada para cifrar mensajes. En algunos casos el atacante solo necesita encriptar un pedazo del mensaje, para el objetivo descrito anteriormente, este caso es conocido como ataque de inyección de texto plano.

Ataque de Texto Cifrado Escogido.- Es un modelo de ataque con el objetivo, ambicioso, de obtener la clave de cifrado mediante la habilidad del atacante para engañar al que posee la clave. En este post usaré las siglas en inglés CCA para identificar este tipo de ataque. Para un mejor entendimiento de este tipo de ataque daré un ejemplo simple en un escenario para un criptosistema de llave simétrica:

Supongamos que el general Alfa esta enviando el mensaje cifrado BCFRET al general Beta. El atacante intercepta este mensaje y lo cambia por un mensaje cifrado aleatório FLOULN  Cuando el general Beta decifra este mensaje modificado obtiene un mensaje sin sentido AGHPJK  Perplejo, llama para el general Alfa y le pregunta porque me ha llegado el mensaje AGHPJK? Acaso han cambiado la clave?. Infelizmente esta llamada también esta siendo interceptada por el atacante, por lo cual el sabe que el mensaje cifrado FLOULN es decifrado en AGHPJK. El utiliza una (de las tantas) forma simple de obtener la llave restando estas dos palabras EEHEBC. En este caso el atacante pudo obtener la llave con tan sólo un mensaje cifrado.

Se dice que un ataque CCA es no adaptativo si el atacante no usa el texto plano resultante del proceso de engañar al que posee la clave. Y, se dice que el modelo CCA es adaptativo (CCA2) si el atance usa el texto plano resultante del proceso de engañar a quien posee la clave para poder seguir enviando textos
cifrados elegidos. En el ejemplo anterior si Alfa continuara enviando mensajes, después de lo que ocurrió, y usa AGHPJK para crear otro mensaje cifrado aleatório, sería entonces un ejemplo de CCA adaptativo.

¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!

Torres de Hanoi Implementación [code C++]

El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas: 

1. Sólo se puede mover un disco cada vez. 
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo. 
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla. 

[fuente Wikipedia]

A continuación presento una implementación de este juego en C++, usando la estructura pila. 

#include <iostream>
#include <stack>
using namespace std;
void hanoi(int, stack<int>&, stack<int>&, stack<int>& );
int main(){
  int n;
  stack<int> origen;
  stack<int> destino;
  stack<int> auxiliar;
  printf("Ingresa el número de discos:\n");
  scanf("%d", &n);

  //llenando la pila de origen con los discos
  for (int i=0; i<n; i++){
      cout<<endl<<n-i<<endl;
      origen.push(n-i);
  }

  hanoi(n, origen, destino, auxiliar);
}


void hanoi(int n, stack<int> &origen, stack<int> &destino, stack<int>& auxiliar){
  if (n == 1){
      int top = origen.top();
      destino.push(top);
      origen.pop();
      return;
  }
  else{
      //{mover n-1 discos de la torre origen a la torre auxiliar}
      hanoi(n-1, origen, auxiliar, destino); //{llamada recursiva}
      //Mover un disco de la torre origen a la torre destino
      int top = origen.top();
      destino.push(top);
      origen.pop();
      //{mover n-1 discos de la torre auxiliar a la torre destino}
      hanoi(n-1, auxiliar, destino, origen); //{llamada recursiva}
  }
  return;
}

Representación de qbits en la esfera de Bloch

Un qubit o cubit (del inglés quantum bit, bit cuántico) es un sistema cuántico con dos estados propios y que puede ser manipulado arbitrariamente. A seguir desarrollaré un ejercicio que trata acerca de la representación de qbits en la esfera Bloch. Para este propósito usaré una herramienta para hacer los gráficos respectivos.

Encontrar la posición del siguiente vector: 
$$|+\rangle = \dfrac{|0\rangle + |1\rangle}{\sqrt[]{2}},$$
en la esfera de Bloch.

Usando la reducción $$\alpha|0\rangle + \beta|1\rangle = e^{i\alpha}(\cos \dfrac{\theta}{2}|0\rangle+e^{i\phi}\sin \dfrac{\theta}{2}|1\rangle).$$  Llevando en consideración que $$e^{i\alpha}$$ es una fase global y haciendo $$j = \sqrt[]{-1}$$ tenemos: $$|+\rangle = \dfrac{|0\rangle + |1\rangle}{\sqrt[]{2}}= \dfrac{|0\rangle}{\sqrt[]{2}}+ \dfrac{|1\rangle}{\sqrt[]{2}}= \alpha|0\rangle + \beta|1\rangle = e^{i\alpha}(\cos \dfrac{\theta}{2}|0\rangle+e^{i\phi}\sin \dfrac{\theta}{2}|1\rangle)$$   $$\alpha = \dfrac{1}{\sqrt[]{2}}= \cos \dfrac{\theta}{2}$$ y

$$\beta = \dfrac{1}{\sqrt[]{2}}= e^{i\phi}\sin \dfrac{\theta}{2},$$ luego $$\theta = \pi/2\,\,\,,\phi = 0$$  A seguir mostramos el respectivo gráfico para esos valores de θ y φ

Livraria LibMC

Introdução

Dentro dos sistemas criptográficos de chave pública existem alguns que, atualmente, têm se destacado devido ao fato de, aparentemente, resistirem aos ataques que são provenientes do uso dos computadores quânticos, formando, assim, uma família denominada de post-quantum cryptosystems. Estes sistemas criptográficos, em sua grande maioria, têm suporte matemático nos códigos códigos de Goppa binário, como apresentado por McEliece e Niederreiter. Neste post, apresento uma livraria para implementar os algoritmos de decodificação algébrica para códigos de Goppa binário com parâmetros $[n,k,d]$ suficientemente grandes. Para conseguir isto, desenvolvemos uma implementação híbrida, usando o CAS(computer algebra system) SAGE para os algoritmos de decodificação e algumas funções modificadas do software HyMES (feito em C) para a geração do polinômio síndrome (de forma randômica), que é uma das entradas para os algoritmos de decodificação. Caso a livraria não fosse usado para gerar o polinômio síndrome, randomicamente, a implementação apenas no SAGE ficaria, obviamente, muito limitada em tempo de decodificação, devido ao carácter simbólico do mesmo. 

Como usar

A livraria esta feita para ser usada em SAGE versão para 32 bits. Para instalar a livraria segue os passos:

1. Descarregar de aqui.
2. Descomprimir o arquivo zipeado.
3. Copiar o arquivo na pasta: local/lib/python/site-packages.
4. Reiniciar o SAGE.

Exemplo de uso

xxxxxxxxxx

 

1

from randomGoppa import *

2

m = 4; n = 2^m-1; debug = 1

3

delta = 2;          # numero de errors que pode corregir

4

vari = py_generatorParity(m,n,delta,debug,1)

5

#Não pressionar o botão Evaluate. Esta livraria, que esta na etapa experimental, no esta instalada nos servidores de SAGE

Language: Sage Gap GP HTML Macaulay2 Maxima Octave Python R Singular

---

Messages

Veja que as entradas do gerador são: $m$ é o grau do polinômio $p(X)$ tal que $F = K/p(X)$, com $K = \mathbb{F}$$_2$, $n$ é o comprimento de cada palavra chave e delta é o grau do polinômio de Goppa. As saídas são: o Polinômio de Goppa, a matriz de teste de paridade do código gerado e o vetor codificado, ou seja $mG+e$.

Este trabalho foi desenvolvido no LNCC, sendo meus orientadores Renato Portugal e Nolmar Melo.

Solución para String como Nombre de Clase en C++ [code]

El problema es como usar una variable de tipo string (char*)  de tal forma que podamos crear instancias de una clase que tenga el nombre de la variable string. Aqui les presento una solución:

Supongamos dos clases Gauss y Patterson:

 
 class Gauss {
 public:
 Gauss() { std::cout << "Object of class Gauss created\n"; }
 static void * create() { return (void*) new Gauss; }
 }
 class Patterson {
 public:
 Patterson() { std::cout << "Object of class Patterson created\n"; }
 static void * create() { return (void*) new Patterson; }
}

Definiremos un nuevo tipo de dato, vacío.

typedef void * (*ptr)();

Ahora el ejemplo

int main() {
std::map<std::string, fptr> fpmap;
//Insertamos los pares nombre de clase y tipo de dato de la clase
fpmap.insert(std::make_pair(std::string("Gaus"), Gauss::create));
fpmap.insert(std::make_pair(std::string("Patterson"), Patterson::create));
//Obteniendo un objeto del Tipo Patterson
void * obj = fpmap["Patterson"]();
}

¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!

Configuración de ECUT en Eclipse + Tutorial

El proyecto ECUT (Eclipse C++ Unit Testing) integra CppUnit dentro de Eclipse C/C++. El objetivo de ECUT es proveer un conjunto de bibliotecas que son usadas en programación para hacer pruebas unitarias en alguna aplicación software hecha en C++. Este conjunto de bibliotecas realiza una tarea similar a la que hace JUnit para aplicaciones hechas en Java.


En este post indicaré los pasos necesarios para configurar ECUT en Eclipse Indigo, bajo el sistema operativo Ubuntu 12.04. Así mismo se presenta un video con un tutorial acerca de este framework.

Teoria de Filtrado y Procesamiento de Imágenes

¿Como desarrollar una teoria para filtrado linear (filtros pasa-alta, pasa-baixa e pasa-banda) usando la transformada discreta de Fourier?
A continuación desarrollaré una teoría que responde a esta pregunta fundamentada en [1]. Para desarrollar la teoría necesitamos entender el significado de alta y baja frecuencia en imágenes. Necesitamos entender, también, que son máscaras para hacer convolución, cuantos tipos de convolución se tienen, así como, cuando usamos uno u otro tipo de convolución.

Alta Frecuencia en imágenes:   Se dice que una imagen presenta alta frecuencia, en el dominio de Fourier, si tiene valores grandes en los componentes de alta frecuencia, es decir, los datos están cambiando rápidamente en una escala de distancia corta, por ejemplo una página de texto. Otro ejemplo es el ruido, el cual es generalmente considerado como alta frecuencia, así un filtrado de paso bajo puede ser utilizado para la reducción del ruido.

Baja Frecuencia en imágenes:  Se dice que una imagen tiene baja frecuencia si sus valores son pequeños en los componentes de baja frecuencia, es decir, la imagen contiene objetos que ocupan gran parte de ella sin cambiar bruscamente de intensidad. Por ejemplo un único objeto bastante simple, que ocupa la mayor parte de la imagen.

Creando un Filtro de Pasa Banda con Gaussianas con MAPLE

En este post desarrollaré un ejercicio que trata acerca de la "creación" de un Filtro de Pasa Banda usando Gausianas. Una Gausiana esta definida como: $$G_{\alpha} = \frac{1}{2\sqrt[]{\pi \alpha}}\exp(-\frac{x^2}{4\alpha})$$ donde $$\alpha > 0.$$ Pues bien, vamos a definir nuestro filtro de pasa banda como: $$h(x)=G_{\alpha}(x) + G_{\beta}(x).$$ Para poder ver experimentalmente que el filtro definido arriba es de pasa banda tendríamos aplicar la propiedad de modulación en cada Gaussiana, quedando la expresión arriba en el dominio de Fourier de la siguiente forma: $$h(x)=G_{\alpha}(x)\exp (j w_0 x) + G_{\beta}(x)\exp (j w_1 x).$$ $$\iff$$ $$H(w) = \exp(-\alpha(w-w_0)^2) + \exp(-\beta(w-w_1)^2)$$ Haciendo ω_0 = 2 y ω_1 = -2 Graficaremos en MAPLE el filtro de pasa banda definido por H(ω): Dando los valores de α y β tenemos:

Teorema de la Convolución Circular

En el post anterior había comentado acerca de la propiedad de dezplazamiento circular de las señales contínuas. Pues bien, en este nuevo post haré uso de esa propiedad para demostrar (según [1]) de manera similar el Teorema de la Convolución Circular.

Teorema 1: A DFT de la convolución circular de dos secuencias es igual al producto de las DFTs de las sequencias. Es decir si $$x[n]=\sum_{m=0}^{N-1}v[n-m]_c u[m]$$ entonces $$DFT\left\{{x[n]}\right\}=DFT\left\{{v[n]}\right\}DFT\left\{{u[n]}\right\}.$$ Demostración: $$DFT\left\{{x[n]}\right\}=\sum_{n=0}^{N-1}x[n]\exp(\frac{-2 j \pi k n}{N})$$