Transmisión de Datos con Menor Pérdida por WiFi

En la seguidilla de las ideas que estoy dando a conocer, esta es otra de ellas. En los siguientes párrafos, les dejo a continuación la idea.

---

Tomando la idea del artículo «Códigos QR para mejorar la encriptación óptica y proteger información confidencial», el otro día me preguntaba qué otra aplicación se le podría dar para la transmisión de datos, a parte de la mencionada en el artículo Transmisión de Datos de Mayor Densidad por Fibra Óptica, y comencé a imaginar un problema donde las virtudes de corrección de datos del QR se podría aplicar, llegando a visualizar la incómoda situación que se da cuando uno está ni muy lejos ni muy cerca de una red WiFi; mientras más lejos de una red de estas características, los paquetes de datos llegan más dañados, entonces, ¿en cuánto mejoraría si los paquetes fuesen envueltos en un QR?

Reflexionando al respecto, en este caso se podría utilizar sólo una conexión UDP, donde sólo se transmitan paquetes apropiadamente etiquetados con un id secuencial, para llevar una seguidilla, y en caso de que un paquete llegue con una distorsión tal que sea imposible decodificarlo, se vuelve a pedir por su id. En este último caso se aplicaría algo similar a una conexión TCP.

Ya he comenzado a trabajar en un protocolo, inspirado en Tor, a ver dónde llego. Lo he llamado InternetQRLayer.

A continuación, dejo un diagrama de esta idea.

Diagrama del protocolo utilizado en InternetQRLayer.

Sus comentarios e ideas, por favor.

QR de Mayor Densidad

En la seguidilla de las ideas que estoy dando a conocer, esta es otra de ellas. En los siguientes párrafos, les dejo a continuación la idea.

---

El código QR convencional trabaja de forma binaria, codificando sus datos a través de bits representados mediante formas cuadradas en blanco y negro. En «High capacity colored two dimensional codes» de Grillo et al, se discute una extensión del QR utilizando color. De esta forma, los autores densifican la cantidad de datos a codificar en la misma área del QR. Sin embargo, existe un problema al utilizar colores: la luz del ambiente. Si el problema es la luz, entonces ¡por qué no descartarla! Entonces, ¿cómo densificar la codificación de datos de un QR?

Pensando en esta última cuestión, la respuesta vino de sopetón a mi mente, y me dije «¡si el problema es la luz, entonces usemos la forma!».

En un curso de la universidad donde trabajo, este semestre trabajamos junto a un alumno en esta idea, y conseguimos algunos resultados iniciales. Elegimos estratégicamente formas tales que fueran de simple identificación por parte de algún software, consiguiendo un sistema de representación en base 5 -- representándose 5 formas diferentes. Uno de los resultados más destacables es el hecho de que un caracter ASCII se puede codificar con 4 bits en base 5, consiguiendo, en forma teórica, doblar la densidad de un QR convencional.

A continuación, dejo dos imágenes que codifican 1 Juan 4:8, una versión usando el código QR y la otra el código propuesto. Es necesario aclarar que la imagen del código propuesto codifica sólo los datos ASCII en bruto, sin información de control ni de corrección de error ni datos para corregir distorsiones.

1 Juan 4:8 versión código QR.

1 Juan 4:8 versión código propuesto.

Compresión de Datos Utilizando Poliominós

En la seguidilla de las ideas que estoy dando a conocer, esta es otra de ellas. En los siguientes párrafos, les dejo a continuación la idea.

---

Específicamente, pentominós, los que podrían ofrecer una buena alternativa para representar formas, basándose en la morfología matemática.

Esta idea nace como una alternativa a la compresión utilizando las matrices Sudoku, discutida en el artículo Compresión de Datos Utilizando Matrices Sudoku -- estos problemas me estaban causando demasiados cortocircuitos cerebrales; por eso consideré esta idea, como una nueva vía.

La idea principal es implementar un algoritmo cuya entrada sea un flujo de bits, y cuya salida sea otro con ciertas propiedades que a continuación explico.

Internamente, el algoritmo va tomando de a m bits en m bits, conformando matrices binarias de nxn que llamaremos matriz T. A partir de T, se busca «encajar» poliominós donde existan conjuntos de bits encendidos (i.e. unos), generando un conjunto de poliominós utilizados que llamaremos P. De esta manera, sólo se necesitará codificar no toda la matriz, sino sólo el conjunto P.

Es necesario mencionar que en T pueden surgir tres situaciones. La primera es que en T existan mayor cantidad de unos que de ceros. En este caso, la cantidad de poliominós necesarios para cubrir la superficie de T será grande. Una solución simple, es invertir los bits de T. La segunda situación, es que ocurra lo contrario a la primera. En este caso, no es necesario hacer algo. Finalmente, la tercera situación es que vengan tantos unos como ceros en igual cantidad.

Los problemas que surgen de esta propuesta son los siguientes:

• Se necesita encontrar la combinación óptima de poliominós p en P sobre T, tal que ||P|| sea el mínimo en U, donde U es el universo de conjuntos de poliominós.
• Se requiere encontrar una representación óptima para p.

¿Alguna idea?

Compresión de Datos Utilizando Matrices Sudoku

En la seguidilla de las ideas que estoy dando a conocer, esta es otra de ellas. En los siguientes párrafos, les dejo a continuación la idea.

---

El objetivo de esta idea es conseguir un algoritmo que dado un conjunto de bytes de entrada, genere otro flujo de salida con ciertas propiedades que explico a continuación.

El algoritmo, en una primera versión, internamente va tomando subconjuntos de 81 bytes, conformando matrices de 9x9 que llamaremos matriz T (el tamaño del tablero de Sudoku tradicional; otra versión podría extenderse a otros tamaños). Posteriormente, a partir de T se busca un conjunto de matrices Sudoku S tal que aplicada alguna función, como sumas y multiplicaciones (u otro operador), se pueda reconstruir T.

Dada la naturaleza del Sudoku, es posible dejar sólo algunos datos en las matrices s en S. De esta forma, la representación binaria de s pudiera reducirse considerablemente, y no tan sólo porque, eventualmente, serían menos números, sino porque los números van de 1 a 9, representables con 4 bits.

Algunos pequeños gigantes problemas son los siguientes:

• La búsqueda del conjunto S óptimo es un problema de combinación, resultando en un algoritmo exponencial. Se podría tratar con metaheurísticas, pero no garantizaría completitud.
• Suponiendo que se ha encontrado un S óptimo, al momento de descomprimir, cada s debe ser reconstruido. Los mejores algoritmos para resolver Sudokus aún son exponenciales.

¿Alguna idea?