Statistical test

The homework is now testing my random key that I created the last week.

I have selected some random testing that I have used in this post.

First I generated 10 keys and created a file with all the keys, this file will be the input for the tests. This capture don't show all the file because this is very long.

I apply the monobit test and my 4 files passed, and this means that the secuency in that the 0 and 1 repeat are not predictable:

And then I applied the run test but, this didn't pass the test:

The next test is I made a compress my file, and this is the result:

So, we don't have security keys, because the file is compressed 16%.


In conclusion we can say that my keys are not secure because only passed 1 test of 3.

Mapa de Karnaugh

Mapa de Karnaugh es un procedimiento directo para optimizar funciones booleanas con un máximo de 4 variables. Se pueden también hacer mapas con 5 o 6 variables pero estas son muy incómodas de usar.

El mapa es un diagrama que esta hecho con cuadros, cada cuadrado representa un mini-termino de la función.

Reconociendo diferentes patrones podemos derivar expresiones algebraicas alternativas para la misma función, de las cuales se puede seleccionar la más sencilla.

Las expresiones optimizadas que el mapa produce siempre se expresan en forma de suma de productos o producto de sumas.

Ahora si vamos a lo bueno, resolvamos algunos ejemplos que inventé con diferente número de variables:

Mapa de dos variables

F = ¬XY + ¬Y¬X + XY 

Lo primero que hay que hacer es construir la tabla de verdad:

Entonces hay que empezar a crear el Mapa-K, para esto creamos un 4 cuadros ya que teniendo dos variables son 4 las combinaciones posibles 2^2 = 4, los renglones representaran la X y las columnas la Y. De la siguiente manera:

Llenamos los cuadrantes de adentro con la respuesta correspondiente que obtuvimos en la tabla de verdad para la combinación indicada.

Tenemos que armar grupos de 1, solo podemos unir de manera vertical y horizontal, no en diagonal, y también nuestros grupos deben del tamaño correspondiente a una potencia de 2 (2, 4, 8, 16).

Entonces nos queda de la siguiente manera:

Lo siguiente es ahora si formar nuestra nueva expresión booleana:

Se hace así:

Tomamos la que esta encerrada en rojo, y queda solamente la X ya que la Y cambia de valores de 0 a 1, y como la X se mantiene constante solo tendremos X, pero como la X esta en 0 tenemos que ponerla negativa para que sea 1 entonces ya tenemos la ¬X.

Ahora de la que esta encerrada en azul vemos que la X cambia de valores entonces se queda la Y sola positiva.

La expresión final es: ¬X + Y. 

De tener al principio F = ¬XY + ¬Y¬X + XY ahora tenemos algo más pequeño F = ¬X + Y

Mapa de tres variables

Aquí tenemos que utilizar 3 variables por lo tanto este problema será un poquito más largo, he creado la siguiente función para mostrar el método:

F = ABC + A¬BC + AB¬C + ¬A¬B¬C + ¬A¬BC

Aquí esta la tabla de verdad:

a:
F = AB + CD

Ahora formamos el mapa-K, en este ejemplo de 3 variables tendremos 8 cuadrantes ya que hay 8 combinaciones posibles 2^3 = 8. La manera de distribuir las combinaciones es teniendo la A en los renglones y la B y C en las columnas, mostrando ahi todas las combinaciones posibles entre estas dos variables, el primer valor que aparece en el renglón como encabezado del mismo es el valor de la B, el segundo es el de la C.

A continuación empezamos a encerrar los grupos que más nos convengan, podemos ver que encerraremos en el primer renglón el grupo de unos, y en el segundo renglón tenemos un grupo de unos de 3 unos, lo que no es posible debido a que 3 no es potencia de dos por lo que tendremos que repetir algún termino que ya este en grupo lo cual es totalmente válido y nos quedara de la siguiente manera:

Entonces podemos ver del grupo rojo la expresión queda ¬A¬B (la C no debido a que cambia de 0 a 1), del grupo azul queda ¬BC (la A no porque cambia de 0 a 1) y del grupo azul vemos AB (la C no porque cambia). 

Y el resultado es de tener la expresión así: F = ABC + A¬BC + AB¬C + ¬A¬B¬C + ¬A¬BC

la hemos minimizado a: F = ¬A¬B + ¬BC + AB.

Mapa de cuatro variables

Ahora una función con 4 variables, usaremos esta expresión que se me ocurrió para mostrar el ejemplo:

F = ABCD + ¬ABCD + A¬BCD + AB¬CD + ABC¬D + ¬A¬BCD + AB¬C¬D

Tabla de verdad:

Lo que sigue es formar el mapa de 4x4 osea 16 cuadrantes que se forman de las combinaciones 2^4 = 16, ahora los renglones los forman A y B con todas sus combinaciones posibles, y las columnas C y D también con todas las combinaciones:

Ahora formamos los grupos de unos, recordemos que tienen que ser potencias de 2, nos quedó bastante cómodo el ejemplo, en la siguiente imagen les muestro como es que podemos resolver nuestro mapa:

Podemos empezar a formar la expresión simplificada tomando el circulo que queramos, yo elegí el rojo, entonces nos queda AB (C y D no porque cambian de valores) y del circulo azul nos queda CD (A y B no porque cambian de valores).
Nuestra expresión paso de ser así:
F = ABCD + ¬ABCD + A¬BCD + AB¬CD + ABC¬D + ¬A¬BCD + AB¬C¬D
a:
F = AB + CD

Y finalmente les muestro como es que compruebo las expresiones, no crean que lo hago manualmente, uso un programita muy sencillo de python, y es así como me puedo dar cuenta que lo optimicé correctamente.


La ejecución:

Referencias

Ejemplo sencillo mapa-karnaugh

Aplicación de la lógica proposicional

Lógica proposicional

Es una parte de la lógica que se encarga de estudiar la formación de proposiciones complejas partiendo de proposiciones simples.
Es un sistema formal en donde los elementos más simples representan proposiciones, y los conectivos representan operaciones entre las proposiciones, y asi se forman proposiciones de mayor complejidad.

La tarea asignada para esta semana es la siguiente:
"Investiguen aplicaciones de la lógica proposicional y documenten uno en su tercera tarea."

Yo elegí documentar la aplicación de la lógica proposicional en el diseño de los circuitos digitales.

[1]

Puertas lógicas

Podemos pensar en un circuito digital como una caja negra, en donde podemos crear relaciones entre las entradas y la salida.

La operación del circuito la podemos especificar al construir una tabla de entradas y salidas, en donde mostremos todos los posibles valores de entrada y de salida.

Para describir como operan los circuitos digitales es necesario introducir nociones matemáticas que especifica la operación de cada puerta y que es usado para diseñar y analizar circuitos.

Para representar una oración de lógica proposicional como circuito digital usamos las compuertas lógicas.
Las puertas lógicas son circuitos electrónicos que toman una o más señales de entrada para producir una señal de salida. Las señales eléctricas como voltaje o corriente existen en los sistemas digitales. Los circuitos que usan los voltajes tienen dos rangos separados de voltajes que representan valores binarios igual a 1 lógico o 0 lógico.
Como podemos ver que es posible representar estos valores con una tabla de verdad, es correcto decir entonces que los circuitos digitales los podemos representar con lógica proposicional.

[2]

Las compuertas lógicas aceptan señales entre 0 y 1 osea dentro del rango permitido y responden a los terminales de salida con señales binarias también. Las regiones entre 0 y 1 o 1 y 0 se llaman regiones de transito y este cambio se le llama transición.

Los simbolos usados para representar los tipos de compuertas los muestro a continuación:

[3]

Las puertas son circuitos electrónicos que producen como salida 0 o 1 de acuerdo a la tabla de verdad y los valores de entrada.

[4]

Actualmente TODOS los circuitos lógicos utilizados en los diseños electrónicos se pueden construir a partir de componentes electrónicos encapsulados en un chip, muchas veces se agrupan las compuertas en  uno solo, aunque posiblemente aun podamos encontrar solo la función lógica que necesitamos en un chip. Los elementos básicos de los circuitos digitales son las compuertas lógicas.

Les dejo un ejemplo de un circuito digital que inventé F = (¬X^Y) | (X^Z) utiliza compuertas lógicas, realizado con el Software Qucs:

Tabla de entrada/salida:

Refrencias

[1], [4] Puertas Lógicas
[2] AND, OR, NOT
[3] Símbolos puertas lógicas
Lógica proposicional, Elisa Schaeffer

Convolución

Convolución es el operador matemático que convierte dos funciones f y g en una tercera función que representa la magnitud en la que se superponen f y una versión trasladada e invertida de g.

Es decir convolución nos da la magnitud del recorrido que hace una funcion f desplazandose en otra funcion g.

Exactamente como la siguiente imagen:

Se representa f(t)*g(t) y la definimos como la integral del producto de ambas funciones después de desplazar alguna de ellas una distancia n.



Una vez entendida esta definición ahora si estoy lista para comenzar a hacer un ejemplo, que yo misma inventé.
Necesitamos recordar una fórmula básica de integración:

Para escribir las ecuaciones utilicé la herramienta en línea de LATEX.

Así comenzamos definiendo f(t) y g(t):


Ahora sustituimos:



Ahora elevamos al cuadrado y multiplicamos :



Separamos para integrar:



Y ahora saco las constantes:



Integramos:



Y el resultado:



Entonces la convolución es la magnitud de el recorrido que hace una función cuando se desplaza sobre la otra, para tener una idea más clara les dejo dos gráficas de las funciones:

La función f(t) = t

La función f(t) = t ** 2

Les dejo un vídeo que me ayudo a entender la definición de la convolución:




Uso de la convolución

• En estadística, como un promedio móvil ponderado.
• En teoría de la probabilidad, la distribución de probabilidad de la suma de variables aleatorias independientes, es la convolución de sus distribuciones de probabilidad.
• Muchas manchas se describen con convoluciones, en óptica.
• En acústica, un eco es la convolución del sonido original con una función que represente los objetos variados que lo reflejan.

Tipos de convolución

Convolución discreta

Se trata de hacer un procesamiento digital de señal, ya que no tiene mucho sentido hablar de convoluciones aplicando estrictamente la definición ya que solo contamos con valores en instantes discretos de tiempo. Entonces es necesario, la aproximación numérica.

En convolución discreta usamos la siguiente fórmula:

Hay en numpy una función que nos permite obtener la convolución discreta, numpy.convolve(a, v, mode='full'), en donde "a" y "v" son listas que contienen los valores de "y", es decir en vez de tener dos funciones tenemos dos arreglos con los puntos en y. Y nos regresa el arreglo con la convolución discreta de las dos secuencias que pusimos de entradas.

Aquí dos pequeños ejemplos:

Gráfica de la primer lista de los argmentos:

Gráfica de la segunda lista:

Referencias:

Convolución

Numpy

One-time pad

For this hw I have created a program that first reads a message from a file called "Message" then convert it to numbers, and then to binary.
Then I create a random key with the length of the binary string (that is saved in a file), and I apply XOR.
The result is encrypted message, now I created decrypt functions, and you can read the original message.
The code is all commented to understand him better.
I leave screenshot of several runs to see how it changes the encrypted message can fit the key.

Code:


Results:

Función sigmoidal

Para no olvidar, aquí dejo una entrada con una gráfica sigmoidal en GNUPLOT.
En gnuplot:

 La gráfica

Tautología

Tautología

La palabra tautología quiere decir “decir lo mismo”, es una fórmula de un sistema de lógica proposicional que resulta ser verdadero para cualquier combinación.

El siguiente ejercicio consiste en hacer una tautología con las siguientes características:

• 3 variables
• Por lo menos cuatro ocurrencias de conectivos
• Por lo menos usar una vez or, and y negación.

Para comenzar hice la tabla con los posibles valores de mis tres variables, y comencé por usar cualquier conector decidí “or” a las letras A y C.

A	B	C	A or C
1	1	1	1
1	1	0	1
1	0	1	1
1	0	0	1
0	1	1	1
0	1	0	0
0	0	1	1
0	0	0	0

Después tomé otras dos letras “B” y “C” con el conector “and”

A	B	C	A or C	B and C
1	1	1	1	1
1	1	0	1	0
1	0	1	1	0
1	0	0	1	0
0	1	1	1	1
0	1	0	0	0
0	0	1	1	0
0	0	0	0	0

Y cree otra combinación ahora con el conector “->” y las letras B y A

A	B	C	A or C	B and C	B -> A
1	1	1	1	1	1
1	1	0	1	0	1
1	0	1	1	0	1
1	0	0	1	0	1
0	1	1	1	1	0
0	1	0	0	0	0
0	0	1	1	0	1
0	0	0	0	0	1

Y ahora sí llegó el momento de pensar un poquito para poder hacer que todas las combinaciones nos den como resultado puros valores positivos, pero hay otra cosa que considerar aún no he usado la negación “¬” , he decidido usarla en alguna combinación de las que ya hice que me dio menos valores positivos (B and C)

A	B	C	A or C	B and C	B -> A	not (B and C )
1	1	1	1	1	1	0
1	1	0	1	0	1	1
1	0	1	1	0	1	1
1	0	0	1	0	1	1
0	1	1	1	1	0	0
0	1	0	0	0	0	1
0	0	1	1	0	1	1
0	0	0	0	0	1	1

Después utilicé un and para conectar (A or C) and ¬(B and C), porque ya noté que si utilizo el conector de “implicación” con (B -> A) podré obtener valores positivos.

A	B	C	A or C	B and C	B -> A	not (B and C )	(A orC) and ¬(B and C)
1	1	1	1	1	1	0	0
1	1	0	1	0	1	1	1
1	0	1	1	0	1	1	1
1	0	0	1	0	1	1	1
0	1	1	1	1	0	0	0
0	1	0	0	0	0	1	0
0	0	1	1	0	1	1	1
0	0	0	0	0	1	1	0

Y ahora si puedo conectar la combinación que aun no relaciono (B -> A) con mi última combinación.

A	B	C	A or C	B and C	B -> A	not (B and C )	(A orC) and ¬(B and C)	((A orC) and ¬(B and C)) -> (B->A)
1	1	1	1	1	1	0	0	1
1	1	0	1	0	1	1	1	1
1	0	1	1	0	1	1	1	1
1	0	0	1	0	1	1	1	1
0	1	1	1	1	0	0	0	1
0	1	0	0	0	0	1	0	1
0	0	1	1	0	1	1	1	1
0	0	0	0	0	1	1	0	1

Y he logrado hacer una tautología, es fácil hacerla si nos vamos paso por paso con la tabla de verdad.

Y por último les muestro el árbol de mi tautología: