Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Códigos convolucionales con propiedades predicibles correctoras de errores

Jordi Miravet Comellas

Published Jan 27, 2010• 0 citations
OpenAlex

Abstract

Se usan los códigos convolucionales extensivamente en las telecomunicaciones, en parte por la facilidad en que corrigen errores y en parte por la existencia de algoritmos rápidos de descodificación. Un código convolucional binario utiliza una matriz $r \\times n$ binaria (las entradas son ceros o unos) y una secuencia de bits $x_0,x_1,x_2,\\ldots$ que corresponde al mensaje por enviar. Sean $u_i=(x_i,x_{i+1},\\ldots,x_{i+r})$ vectores de longitud $r$, y $v_i=u_iG$ vectores de longitud $n$. Observamos que todos los cálculos se hacen módulo $2$. Se envian los vectores $v_0,v_k,v_{2k},\\ldots$, donde $k$ es un número entre $1$ y $r-1$. Supongamos que se reciben los vectores $w_i=v_i+e_i$, donde $e_i$ es el error que ha ocurrido durante la transmisión. El algoritmo de Viterbi considera todas las posibilidades de descodificación y cuando empiezan a ocurrir errores se siguen todas las posibilidades hasta un límite de errores fijado. Se rechazan los caminos que llevan demasiados errores y se sigue hasta que se hayan rechazado todos los caminos excepto uno. Las matrices $G$ que se usan en la práctica han sido elegidas heurísticamente. O sea,se han probado varias matrices $G$ y se han elegido las matrices que son las más fiables para corregir errores. En esta propuesta, se propone encontrar una manera de predecir cuantos errores (dependiendo de alguna distribución de probabilidad) se pueden corregir utilizando una matriz determinada. Se sabe que para los códigos de bloques de longitud $n$ y distancia mínima $d$ se corrigen hasta $\\lfloor \\frac{d-1}{2} \\rfloor$ errores en cada $n$ bits de una palabra con probabilidad $1$. Nos gustaría hallar matrices $G$ con la siguiente propiedad. Cuando un error ocurre, el número de errores en una posible (pero incorrecta) descodificación crece rápido, y por lo tanto, se puede descartar en poco tiempo. Sea $G$ una matriz $r \\times n$ de rango $n$. Si $xG=yG$ y la distancia entre $x$ y $y$ es grande, y además $x$ corresponde a la codificación que queremos descodificar, escogiendo la descodificación de $y$ se espera que el número de errores crezca rápido. Por lo tanto, puede que sea deseable utilizar matrices $G$ con la propiedad que $uG=0$ implica que $u$ tiene peso grande. (Si $xG=yG$ entonces $(x-y)G=0$ y por lo tanto la distancia entre $x$ y $y$ es grande.) Sea $H$ la matrix $(r-n) \\times r$ con la propiedad $HG=0$. Queremos probar matrices $G$ para las cuales la matriz $H$ tiene la propiedad que los vectores del subespacio generado por las filas de $H$ no tienen peso peque\\~no. {\\bf Primer Objetivo} Escribir un programa que nos deja probar la hipótesis. Sea $G$ una matriz binario $10 \\times 5$. \\\\ Generar secuencia $v$ de $100$ bits, a\\~nadiendo 10 bits de ceros al inicio y al final de la secuencia. Sea $k=3$. De los 120 bits generamos $5 \\times 120/3= 200$ bits (por lo tanto la tasa de información es $100/200=1/2$.) Genera una secuencia $e$ de 200 bits de peso $Bin(200, \\frac{1}{10})$ de errores. Descodifica $v+e$ con el algoritmo de Viterbi rechazando caminos que llevan más de dos/tres errores. Comprueba la descodificación. Aplica el progama 30 veces para una matriz aleatoria $G$ de rango $5$ y una matriz $G$ que es una matriz comprobadora de paridad para un código bloque de longitud $10$, dimensión $5$ y distancia mínima $4$. {\\bf Segundo Objetivo} Análisis de los datos obtenidos para ver si en la práctica es mejor utilizar matrices $G$ que son matrices comprobadoras de paridad para códigos de bloques. Análisis de los datos para predecir cuantos errores se pueden corregir (depende de una probabilidad) utilizando una matriz determinada.

Related papers

Estructuras y características de desempeño de los códigos LDPC (Low-Density Parity-Check Codes)

Wilson Giovanni Castañeda Barbosa

Este trabajo presenta el análisis de las estructuras y características de\ndesempeño de los códigos LDPC (Low-Density Parity-Check Codes), los\ncuales son una clase de códigos lineales de bloque que proporcionan un\nrendimiento cercano a la Capacidad utilizando decodificación iterativa.\nEn principio se presenta la idea general de un sistema de comunicaciones\ny por medio de un diagrama de bloques se muestra cómo está\nconformado tal sistema. Después se sigue con la explicación del concepto\nde codificación y la razón por la cual se necesita de ésta para la\ntransmisión o almacenamiento de información. Además se dan las\ndefiniciones de algunos parámetros utilizados en este campo, incluyendo\nel gran aporte de Shannon con sus teoremas.\nPosteriormente se realiza una revisión general de las familias de códigos\nde corrección de error presentes en la literatura, definiendo sus\nestructuras y diferencias. Luego de esta revisión se da una introducción a\nlos códigos LDPC, en donde se explica la forma de codificación y los\ndistintos algoritmos de decodificación para estos códigos.\nFinalmente, se realiza el análisis del tipo de códigos LDPC basados en\narreglos y se muestran los resultados de las simulaciones realizadas. Se\npresenta la definición del fenómeno de error-floor y conjuntos absorbentes\nlos cuales afectan el rendimiento de los códigos LDPC en las regiones de\nbajo BER (Bit-Error Rate). Se estudia el efecto de la cuantización en el\nrendimiento de los decodificadores de los códigos LDPC basados en\narreglos. Así mismo, basados en el estudio anterior se analiza el resultado\nde la variación de los pesos de las columnas de las matrices de\ncomprobación de paridad para dichos códigos.\nAl final de la tesis se incluyen los códigos de los programas realizados,\njunto con una breve descripción de ellos, y se detalla un programa\ninteractivo basado en MatLab para la enseñanza de comunicaciones\ndigitales.

•Oct 1, 2013•0 citations

Distribución cuántica de claves criptográficas. Experimentos y tecnologías

López Grande, H Ignacio

En esta tesis se presentan los resultados de una serie de experimentos opticos en los que se ejecutan algoritmos de comunicaciones cuanticas para realizar Distribucion Cuantica de Claves(DCC) criptograficas con estados coherentes de muy baja intensidad. Especificamente, se estudia la implementacion de esquemas practicos y robustos de DCC, con especial interes en sistemas basados en fibra optica. A diferencia de las comunicaciones por aire, este medio permite transmitir estados cuanticos con bajisimas atenuaciones y minimas perturbaciones externas, utilizando instrumental comercialmente disponible y de bajo costo, incluso para distancias de decenas de kilometros. Los protocolos de DCC estudiados codifican informacion clasica (bits) en estados cuanticos preparados sobre distintos grados de libertad discretos de sistemas fisicos. En el trabajo se exploran implementaciones que explotan la polarizacion y los modos temporales discretos de luz (time-bin). En ambos casos, fue necesario desarrollar y familiarizarse con tecnologias especificas para la preparacion, transmision y deteccion de dichos estados cuanticos. El problema de transmitir estados cuanticos en fibra de forma eficiente y robusta se ataco con dos estrategias. Por un lado, utilizando el grado de libertad de polarizacion y, por otro, modos temporales discretos de luz. En el primer caso, se codificaron los estados en el grado de libertad de polarizacion, que es facilmente accesible. Sin embargo, este es muy sensible a perturbaciones, por lo que para asegurar la robustez se incorporo un sistema de estabilizacion activa del Estado de Polarizacion(SOP, por su sigla en ingles). Con este esquema se implementaron dos variantes de un protocolo clasico de DCC, llamado BB84, utilizando la polarizacion de pulsos de luz para codificar los estados cuanticos. Esto requirio el desarrollo de una fuente de pulsos tenues de luz basada en un laser DFB en el rango de las telecomunicaciones, con un modulador de intensidad externo por electroabsorcion. Se diseno un sistema de estabilizacion de la polarizacion robusto que permite compensar de forma automatica las perturbaciones que genera la birrefringencia de la fibra sobre el estado de polarizacion. El sistema esta basado en controladores de polarizacion comerciales y electronica de control disenada especificamente, y puede ser adaptado facilmente a cualquier protocolo de comunicacion por fibra. En este sentido, se realizo una implementacion del protocolo BB84 y una variante llamada BB84E, que requiere la utilizacion de los seis estados de un conjunto completo de bases mutuamente no sesgadas para la polarizacion. En el segundo caso, se ensayo una codificacion mas sofisticada y resistente a perturbaciones, que implico enfrentar una serie de desafios tecnologicos, pero que se presenta como una alternativa practica y escalable en distancia de transmision y velocidad. Se propuso un esquema hibrido de DCC basado en un protocolo de referencia de fase distribuida con comunicacion bidireccional (Plug & Play), ambas tecnologias desarrolladas para trabajar especificamente en fibra optica, en un esquema con economia de recursos y distribucion tipo servidor-cliente. Asi, se obtuvo una configuracion en donde tanto el instrumental como las operaciones sobre los estados mas sensibles del protocolo se encuentran concentradas en una de las partes (servidor), mientras que los requerimientos sobre la otra parte involucrada en la comunicacion son minimos. Esta alternativa combina diferentes caracteristicas deseables en una implementacion practica de DCC, como la simplicidad y la robustez. El esquema propuesto codifica estados cuanticos en modos temporales discretos de luz. Esto requirio el desarrollo de dispositivos especificos para preparar y medir estos estados, basados en interferometros de fibra optica que no demanden estabilizacion activa. Otra de las premisas fue la independencia de funcionamiento del estado de polarizacion, que se logra a partir de la incorporacion de rotadores de Faraday en diferentes partes del esquema empleado. Por ultimo, debido al tipo de codificacion y al sistema de sincronizacion utilizados, este esquema es adaptable a tasas de transmision en el rango de los MHz. De los experimentos de DCC mencionados se desprenden una serie de desarrollos y pruebas de laboratorio adicionales, que son relevantes por si mismos. Entre ellos figuran la estabilizacion activa de interferometros de Mach-Zehnder en fibra y el estudio de esquemas experimentales alternativos para el protocolo hibrido de DCC propuesto. Tambien se puede destacar la puesta a punto de un prototipo autonomo de DCC en aire y su adaptacion para obtener un protocolo que distingue mezclas computables (pseudoaleatorias) de estados cuanticos. Este es un tema de interes para el procesamiento cuantico de la informacion en general. Las tecnicas abordadas y el know-how adquirido permiten entender y superar distintos problemas particulares de la utilizacion de estados cuanticos en comunicaciones por fibra optica. Ademas, estos desarrollos tienen la capacidad de ser empleados tanto en ensayos de DCC que excedan el ambito del laboratorio, como en un contexto mas amplio que permita implementar otros protocolos de comunicacion cuantica usando fibras opticas de telecomunicaciones como canal cuantico.

•Dec 10, 2018•0 citations

CAMINATA CUÁNTICA AL AZAR SIMULADA ÓPTICAMENTE

Diego Francisco, Claudio Iemmi, Silvia Adriana Ledesma

Los algoritmos cuánticos son, en general, mucho más eficientes que los clásicos lo que los vuelve particularmente interesantes para ser usados en computación. La llamada caminata clásica al azar ha sido usada tradicionalmente para modelar procesos de difusión. En el caso unidimensional se considera una partícula que está obligada a moverse sobre una línea. Se supone además que la partícula se mueve siempre a la misma velocidad y que puede desplazarse hacia a la derecha o la izquierda en pasos discretos con igual probabilidad. Al cabo de varias iteraciones, la distribución de probabilidad sobre las posibles posiciones de la partícula sigue una función Gaussiana centrada en el origen. La contrapartida cuántica consta de estados descriptos por una función de ondas que es una combinación de los estados de la base computacional con coeficientes complejos. Una vez establecido el estado de partida se aplica un operador de Hadamard y un operador de traslación condicional. Al cabo de varias iteraciones del proceso, se obtienen distribuciones que no aproximan a una Gaussiana y que pueden ser incluso no simétricas para algunas condiciones iniciales. Esta propiedad podría ser muy útil en un algoritmo de búsqueda. En este trabajo se muestra como puede ser simulada ópticamente una caminata cuántica al azar utilizando elementos ópticos convencionales y representando espacialmente los q-bits como imágenes en un procesador óptico. Se presentan resultados experimentales en los que se muestra la viabilidad del proceso

ANALES AFA•Jun 24, 2006•0 citations

Implementación de algoritmos clásicos en computación cuántica

Carlos Fernando Díaz Vargas

La computación cuántica tiene una base teórica de más de tres décadas que muestra aceleraciones polinómicas y exponenciales sobre los algoritmos clásicos. Los procesadores que se construyen hoy, sin embargo, son ruidosos, pequeños y de conectividad limitada, aún lejos de aprovechar esa ventaja en problemas de escala real. Este trabajo es un estudio experimental que mide qué tan profunda es esa brecha para cuatro algoritmos cuánticos fundamentales: Bernstein–Vazirani, Simon, Grover sobre instancias de k-SAT y la estimación cuántica de fase. Para cada algoritmo se construyó una contraparte clásica de referencia y se evaluaron, por cada tamaño de entrada, todas las combinaciones posibles de tres modelos de ruido (error de lectura, despolarizante y relajación térmica) con tres topologías de hardware (ideal, lineal de 20 qubits y heavy-hex de 127 qubits, esta última inspirada en el chip ibm_brisbane). El estudio se hizo enteramente en simulación porque permite controlar de forma independiente cada parámetro del ruido y de la conectividad, condición necesaria para hacer comparaciones limpias entre escenarios. Cada uno de los 39 escenarios resultantes por tamaño se repitió 25 veces y los resultados se reportan con intervalo de confianza al 95 % calculado con la t de Student. Toda la infraestructura (algoritmos, generador de instancias, modelos de ruido, scripts de análisis e interfaz gráfica para exploración interactiva) queda reproducible y abierta. Los hallazgos principales son tres. Primero, la ventaja teórica sobrevive en los algoritmos de poca profundidad como Bernstein–Vazirani, mientras que en Grover y en la estimación de fase el ruido deteriora rápidamente el speedup a medida que crece el número de iteraciones. Segundo, el tipo de ruido importa tanto como su nivel: el error de lectura es el menos agresivo porque no se acumula con la profundidad del circuito, mientras que el despolarizante es el más severo. Tercero, la topología influye de forma indirecta pero significativa porque condiciona la cantidad de compuertas SWAP que el compilador debe insertar y, por esa vía, aumenta la profundidad efectiva del circuito. El framework, los datos y los análisis quedan disponibles para quien quiera prototipar pruebas de algoritmos cuánticos en la era NISQ sin depender de tiempo en hardware real.

•Jun 4, 2026•0 citations

Spin glasses, the quantum annealing, colloidal glasses and crystals

Beatriz Seoane

Presentamos aqui una seleccion de los resultados mas importantes obtenidos en cada capitulo de la tesis. El Modelo del Hipercubo Hemos estudiado [Fer10b] un nuevo modelo de campo medio para vidrios de espin sobre un hipercubo unitario en D-dimension es. La principal ventaja de este modelo es que, dada su distribucion espacial, tiene una nocion natural de distancia (caracteristica rara en modelos de campo medio). Hemos probado que, dada la geometria del problema, cualquier mecanica estadistica sobre modelos en el hipercubo con conectividad aleatoria sufre efectos de tamano finito enormes. La solucion presentada pasa por restringir el estudio a aquellos grafos sobre donde el numero de vecinos esta fijo. Generar estos grafos no es trivial, p ero hemos resuelto el problema con un algoritmo dinamico de Montecarlo. Aunque no sabemos si el conjunto de grafos accesibles por este metodo es completo, hemos comprobado que los hipercubos generados son isotropicos, y que el modelo de Edwards-Ander son definido sobre estos grafos cumple todos los checks de consistencia considerados. Una vez definido el modelo, hemos estudiado numericamente la dinamica fuera del equilibrio en la fase vidrio de espin. Las tres caracteristicas principales son: (i ) el envejecimiento consiste en el crecimiento de una longitud de coherencia, como en los sistemas tridimensionales, (ii) el scaling a dos tiempos de la funcion de correlacion implica una infinidad de sectores temporales, y (iii) se ha observado el p ropagador p4. Ademas, hemos estudiado los efectos de volumen finito en nuestro modelo, encontrando que podemos explicar nuestros datos con un ansatz de tamano finito extremadamente simple. Siendo este modelo de campo medio, esta regido por la teoria RSB. Por lo tanto, combinado con su nocion de distancia, se convierte en un patio de pruebas para estudiar la dinamica de no equilibrio en sistemas RSB. Caos en temperatura El caos en temperatura es un fenomeno de eventos extremos. Cuando ocurre, s us efectos son muy fuertes y se pueden sentir incluso a distancias muy cortas, como podemos confirmar con las funcion de correlacion espacial a dos temperaturas [Fer12a]. Han sido cruciales dos ingredientes para alcanzar esta conclusion. Primero, gra cias al superordenador JANUS, hemos tenido acceso a configuraciones mucho mas grandes que todo lo estudiado hasta la fecha, y ademas termalizadas a temperaturas mucho mas bajas [AB10a,AB10b]. En segundo lugar, hemos considerado nuevas herramientas de

•Jan 1, 2013•0 citations

Etude des décodeurs LDPC non-binaires

Oussama Abassi

Les codes binaires à matrices creuses (Low-Density Parity-Check, LDPC) et les turbo-codes ont une capacité s’approchant de la limite de Shannon pour des trames de grande taille. Cependant, ces codes ont le désavantage d’être moins efficaces pour les faibles tailles. De plus, l’association de codes binaires avec des modulations d’ordre élevé oblige à une étape de marginalisation pour passer d’un symbole aux fiabilités des bits associés à ce symbole. Ce calcul s’accompagne d’une perte d’information qui peut être récupérée par démodulation itérative au prix d’une plus grande complexité. Les codes LDPC définis sur des corps de Galois d’ordre q > 2 permettent de résoudre ces problèmes. Toutefois, lesdécodeurs optimaux associés ont une complexité très importante qui rend leur utilisation problématique.L’objectif de cette thèse est de valoriser les codes LDPC non binaires en proposant d’une part une architecture d’un décodeur à complexité réduite et en montrant d’autre part l’intérêt de les associer à des modulations d’ordre élevé. Dans la première partie de notre thèse, nous proposons de simplifier l’algorithme de décodage Extended Min-Sum (EMS) en considérant un nombre limité n_α << n_m des fiabilités intrinsèques lors de la mise à jour des messages par les nœuds de variable. Cette approche permet de réduire la taille de la mémoire dédiée au stockage des messages intrinsèques. De plus, pour améliorer l’effcacité des nœuds de parité nous proposons une variante simplifiée de l’algorithme L-Bubble Check et l’architecture associée. Enfin, nous montrons par l’intermédiaire d’un prototype sur une carte FPGA (Field Programmable Gate Array) que notre décodeur possède une faible complexité en le comparant avec un ancien décodeur EMS conçu par notre laboratoire de recherche dans le cadre du projet européen DAVINCI. Dans la deuxième partie, nous étudions l’association des codes LDPC non binaires avec une modulation par décalage cyclique de code (Cyclic Code-shift Keying, CCSK) de même ordre. Nous avons choisi cette modulation pour ses propriétés qui permettent de réduire la complexité du démodulateur. En effet, nous montrons qu’il est possible dans le cas d’un système de transmission mono-porteuse avec préfixe cyclique de fusionner le démodulateur et l’égaliseur dans un même bloc comportant une seule transformée de Fourier rapide et une seule transformée de Fourier rapide inverse. Les simulations montrent que ce système possède des performances comparables à un système de transmission multiporteuses de type OFDM (Orthogonal Frequency-Division Multiplexing). Elles montrent aussi que la modulation CCSK donne des performances meilleures que la modulation de Hadamard dans un canal en environnement intérieur sélectif en fréquence. Enfin, les simulations montrent que les codes LDPC non binaires sont nettement plus effcaces avec la modulation CCSK que les codes LDPC binaires même en considérant une démodulation itérative.

•Jun 27, 2014•0 citations
Se usan los códigos convolucionales extensivamente en las telecomunicaciones, en parte por la facilidad en que corrigen errores y en parte por la existencia de algoritmos rápidos de descodificación. Un código convolucional binario utiliza una matriz rtimesnr \\times nrtimesn binaria (las entradas son ceros o unos) y una secuencia de bits x0,x1,x2,ldotsx_0,x_1,x_2,\\ldotsx0​,x1​,x2​,ldots que corresponde al mensaje por enviar. Sean ui=(xi,xi+1,ldots,xi+r)u_i=(x_i,x_{i+1},\\ldots,x_{i+r})ui​=(xi​,xi+1​,ldots,xi+r​) vectores de longitud rrr, y vi=uiGv_i=u_iGvi​=ui​G vectores de longitud nnn. Observamos que todos los cálculos se hacen módulo 222. Se envian los vectores v0,vk,v2k,ldotsv_0,v_k,v_{2k},\\ldotsv0​,vk​,v2k​,ldots, donde kkk es un número entre 111 y r−1r-1r−1. Supongamos que se reciben los vectores wi=vi+eiw_i=v_i+e_iwi​=vi​+ei​, donde eie_iei​ es el error que ha ocurrido durante la transmisión. El algoritmo de Viterbi considera todas las posibilidades de descodificación y cuando empiezan a ocurrir errores se siguen todas las posibilidades hasta un límite de errores fijado. Se rechazan los caminos que llevan demasiados errores y se sigue hasta que se hayan rechazado todos los caminos excepto uno. Las matrices GGG que se usan en la práctica han sido elegidas heurísticamente. O sea,se han probado varias matrices GGG y se han elegido las matrices que son las más fiables para corregir errores. En esta propuesta, se propone encontrar una manera de predecir cuantos errores (dependiendo de alguna distribución de probabilidad) se pueden corregir utilizando una matriz determinada. Se sabe que para los códigos de bloques de longitud nnn y distancia mínima ddd se corrigen hasta lfloorfracd−12rfloor\\lfloor \\frac{d-1}{2} \\rfloorlfloorfracd−12rfloor errores en cada nnn bits de una palabra con probabilidad 111. Nos gustaría hallar matrices GGG con la siguiente propiedad. Cuando un error ocurre, el número de errores en una posible (pero incorrecta) descodificación crece rápido, y por lo tanto, se puede descartar en poco tiempo. Sea GGG una matriz rtimesnr \\times nrtimesn de rango nnn. Si xG=yGxG=yGxG=yG y la distancia entre xxx y yyy es grande, y además xxx corresponde a la codificación que queremos descodificar, escogiendo la descodificación de yyy se espera que el número de errores crezca rápido. Por lo tanto, puede que sea deseable utilizar matrices GGG con la propiedad que uG=0uG=0uG=0 implica que uuu tiene peso grande. (Si xG=yGxG=yGxG=yG entonces (x−y)G=0(x-y)G=0(x−y)G=0 y por lo tanto la distancia entre xxx y yyy es grande.) Sea HHH la matrix (r−n)timesr(r-n) \\times r(r−n)timesr con la propiedad HG=0HG=0HG=0. Queremos probar matrices GGG para las cuales la matriz HHH tiene la propiedad que los vectores del subespacio generado por las filas de HHH no tienen peso peque\~no. {\bf Primer Objetivo} Escribir un programa que nos deja probar la hipótesis. Sea GGG una matriz binario 10times510 \\times 510times5. \\ Generar secuencia vvv de 100100100 bits, a\~nadiendo 10 bits de ceros al inicio y al final de la secuencia. Sea k=3k=3k=3. De los 120 bits generamos 5times120/3=2005 \\times 120/3= 2005times120/3=200 bits (por lo tanto la tasa de información es 100/200=1/2100/200=1/2100/200=1/2.) Genera una secuencia eee de 200 bits de peso Bin(200,frac110)Bin(200, \\frac{1}{10})Bin(200,frac110) de errores. Descodifica v+ev+ev+e con el algoritmo de Viterbi rechazando caminos que llevan más de dos/tres errores. Comprueba la descodificación. Aplica el progama 30 veces para una matriz aleatoria GGG de rango 555 y una matriz GGG que es una matriz comprobadora de paridad para un código bloque de longitud 101010, dimensión 555 y distancia mínima 444. {\bf Segundo Objetivo} Análisis de los datos obtenidos para ver si en la práctica es mejor utilizar matrices GGG que son matrices comprobadoras de paridad para códigos de bloques. Análisis de los datos para predecir cuantos errores se pueden corregir (depende de una probabilidad) utilizando una matriz determinada.
Este trabajo presenta el análisis de las estructuras y características de\ndesempeño de los códigos LDPC (Low-Density Parity-Check Codes), los\ncuales son una clase de códigos lineales de bloque que proporcionan un\nrendimiento cercano a la Capacidad utilizando decodificación iterativa.\nEn principio se presenta la idea general de un sistema de comunicaciones\ny por medio de un diagrama de bloques se muestra cómo está\nconformado tal sistema. Después se sigue con la explicación del concepto\nde codificación y la razón por la cual se necesita de ésta para la\ntransmisión o almacenamiento de información. Además se dan las\ndefiniciones de algunos parámetros utilizados en este campo, incluyendo\nel gran aporte de Shannon con sus teoremas.\nPosteriormente se realiza una revisión general de las familias de códigos\nde corrección de error presentes en la literatura, definiendo sus\nestructuras y diferencias. Luego de esta revisión se da una introducción a\nlos códigos LDPC, en donde se explica la forma de codificación y los\ndistintos algoritmos de decodificación para estos códigos.\nFinalmente, se realiza el análisis del tipo de códigos LDPC basados en\narreglos y se muestran los resultados de las simulaciones realizadas. Se\npresenta la definición del fenómeno de error-floor y conjuntos absorbentes\nlos cuales afectan el rendimiento de los códigos LDPC en las regiones de\nbajo BER (Bit-Error Rate). Se estudia el efecto de la cuantización en el\nrendimiento de los decodificadores de los códigos LDPC basados en\narreglos. Así mismo, basados en el estudio anterior se analiza el resultado\nde la variación de los pesos de las columnas de las matrices de\ncomprobación de paridad para dichos códigos.\nAl final de la tesis se incluyen los códigos de los programas realizados,\njunto con una breve descripción de ellos, y se detalla un programa\ninteractivo basado en MatLab para la enseñanza de comunicaciones\ndigitales.
En esta tesis se presentan los resultados de una serie de experimentos opticos en los que se ejecutan algoritmos de comunicaciones cuanticas para realizar Distribucion Cuantica de Claves(DCC) criptograficas con estados coherentes de muy baja intensidad. Especificamente, se estudia la implementacion de esquemas practicos y robustos de DCC, con especial interes en sistemas basados en fibra optica. A diferencia de las comunicaciones por aire, este medio permite transmitir estados cuanticos con bajisimas atenuaciones y minimas perturbaciones externas, utilizando instrumental comercialmente disponible y de bajo costo, incluso para distancias de decenas de kilometros. Los protocolos de DCC estudiados codifican informacion clasica (bits) en estados cuanticos preparados sobre distintos grados de libertad discretos de sistemas fisicos. En el trabajo se exploran implementaciones que explotan la polarizacion y los modos temporales discretos de luz (time-bin). En ambos casos, fue necesario desarrollar y familiarizarse con tecnologias especificas para la preparacion, transmision y deteccion de dichos estados cuanticos. El problema de transmitir estados cuanticos en fibra de forma eficiente y robusta se ataco con dos estrategias. Por un lado, utilizando el grado de libertad de polarizacion y, por otro, modos temporales discretos de luz. En el primer caso, se codificaron los estados en el grado de libertad de polarizacion, que es facilmente accesible. Sin embargo, este es muy sensible a perturbaciones, por lo que para asegurar la robustez se incorporo un sistema de estabilizacion activa del Estado de Polarizacion(SOP, por su sigla en ingles). Con este esquema se implementaron dos variantes de un protocolo clasico de DCC, llamado BB84, utilizando la polarizacion de pulsos de luz para codificar los estados cuanticos. Esto requirio el desarrollo de una fuente de pulsos tenues de luz basada en un laser DFB en el rango de las telecomunicaciones, con un modulador de intensidad externo por electroabsorcion. Se diseno un sistema de estabilizacion de la polarizacion robusto que permite compensar de forma automatica las perturbaciones que genera la birrefringencia de la fibra sobre el estado de polarizacion. El sistema esta basado en controladores de polarizacion comerciales y electronica de control disenada especificamente, y puede ser adaptado facilmente a cualquier protocolo de comunicacion por fibra. En este sentido, se realizo una implementacion del protocolo BB84 y una variante llamada BB84E, que requiere la utilizacion de los seis estados de un conjunto completo de bases mutuamente no sesgadas para la polarizacion. En el segundo caso, se ensayo una codificacion mas sofisticada y resistente a perturbaciones, que implico enfrentar una serie de desafios tecnologicos, pero que se presenta como una alternativa practica y escalable en distancia de transmision y velocidad. Se propuso un esquema hibrido de DCC basado en un protocolo de referencia de fase distribuida con comunicacion bidireccional (Plug & Play), ambas tecnologias desarrolladas para trabajar especificamente en fibra optica, en un esquema con economia de recursos y distribucion tipo servidor-cliente. Asi, se obtuvo una configuracion en donde tanto el instrumental como las operaciones sobre los estados mas sensibles del protocolo se encuentran concentradas en una de las partes (servidor), mientras que los requerimientos sobre la otra parte involucrada en la comunicacion son minimos. Esta alternativa combina diferentes caracteristicas deseables en una implementacion practica de DCC, como la simplicidad y la robustez. El esquema propuesto codifica estados cuanticos en modos temporales discretos de luz. Esto requirio el desarrollo de dispositivos especificos para preparar y medir estos estados, basados en interferometros de fibra optica que no demanden estabilizacion activa. Otra de las premisas fue la independencia de funcionamiento del estado de polarizacion, que se logra a partir de la incorporacion de rotadores de Faraday en diferentes partes del esquema empleado. Por ultimo, debido al tipo de codificacion y al sistema de sincronizacion utilizados, este esquema es adaptable a tasas de transmision en el rango de los MHz. De los experimentos de DCC mencionados se desprenden una serie de desarrollos y pruebas de laboratorio adicionales, que son relevantes por si mismos. Entre ellos figuran la estabilizacion activa de interferometros de Mach-Zehnder en fibra y el estudio de esquemas experimentales alternativos para el protocolo hibrido de DCC propuesto. Tambien se puede destacar la puesta a punto de un prototipo autonomo de DCC en aire y su adaptacion para obtener un protocolo que distingue mezclas computables (pseudoaleatorias) de estados cuanticos. Este es un tema de interes para el procesamiento cuantico de la informacion en general. Las tecnicas abordadas y el know-how adquirido permiten entender y superar distintos problemas particulares de la utilizacion de estados cuanticos en comunicaciones por fibra optica. Ademas, estos desarrollos tienen la capacidad de ser empleados tanto en ensayos de DCC que excedan el ambito del laboratorio, como en un contexto mas amplio que permita implementar otros protocolos de comunicacion cuantica usando fibras opticas de telecomunicaciones como canal cuantico.
Los algoritmos cuánticos son, en general, mucho más eficientes que los clásicos lo que los vuelve particularmente interesantes para ser usados en computación. La llamada caminata clásica al azar ha sido usada tradicionalmente para modelar procesos de difusión. En el caso unidimensional se considera una partícula que está obligada a moverse sobre una línea. Se supone además que la partícula se mueve siempre a la misma velocidad y que puede desplazarse hacia a la derecha o la izquierda en pasos discretos con igual probabilidad. Al cabo de varias iteraciones, la distribución de probabilidad sobre las posibles posiciones de la partícula sigue una función Gaussiana centrada en el origen. La contrapartida cuántica consta de estados descriptos por una función de ondas que es una combinación de los estados de la base computacional con coeficientes complejos. Una vez establecido el estado de partida se aplica un operador de Hadamard y un operador de traslación condicional. Al cabo de varias iteraciones del proceso, se obtienen distribuciones que no aproximan a una Gaussiana y que pueden ser incluso no simétricas para algunas condiciones iniciales. Esta propiedad podría ser muy útil en un algoritmo de búsqueda. En este trabajo se muestra como puede ser simulada ópticamente una caminata cuántica al azar utilizando elementos ópticos convencionales y representando espacialmente los q-bits como imágenes en un procesador óptico. Se presentan resultados experimentales en los que se muestra la viabilidad del proceso
La computación cuántica tiene una base teórica de más de tres décadas que muestra aceleraciones polinómicas y exponenciales sobre los algoritmos clásicos. Los procesadores que se construyen hoy, sin embargo, son ruidosos, pequeños y de conectividad limitada, aún lejos de aprovechar esa ventaja en problemas de escala real. Este trabajo es un estudio experimental que mide qué tan profunda es esa brecha para cuatro algoritmos cuánticos fundamentales: Bernstein–Vazirani, Simon, Grover sobre instancias de k-SAT y la estimación cuántica de fase. Para cada algoritmo se construyó una contraparte clásica de referencia y se evaluaron, por cada tamaño de entrada, todas las combinaciones posibles de tres modelos de ruido (error de lectura, despolarizante y relajación térmica) con tres topologías de hardware (ideal, lineal de 20 qubits y heavy-hex de 127 qubits, esta última inspirada en el chip ibm_brisbane). El estudio se hizo enteramente en simulación porque permite controlar de forma independiente cada parámetro del ruido y de la conectividad, condición necesaria para hacer comparaciones limpias entre escenarios. Cada uno de los 39 escenarios resultantes por tamaño se repitió 25 veces y los resultados se reportan con intervalo de confianza al 95 % calculado con la t de Student. Toda la infraestructura (algoritmos, generador de instancias, modelos de ruido, scripts de análisis e interfaz gráfica para exploración interactiva) queda reproducible y abierta. Los hallazgos principales son tres. Primero, la ventaja teórica sobrevive en los algoritmos de poca profundidad como Bernstein–Vazirani, mientras que en Grover y en la estimación de fase el ruido deteriora rápidamente el speedup a medida que crece el número de iteraciones. Segundo, el tipo de ruido importa tanto como su nivel: el error de lectura es el menos agresivo porque no se acumula con la profundidad del circuito, mientras que el despolarizante es el más severo. Tercero, la topología influye de forma indirecta pero significativa porque condiciona la cantidad de compuertas SWAP que el compilador debe insertar y, por esa vía, aumenta la profundidad efectiva del circuito. El framework, los datos y los análisis quedan disponibles para quien quiera prototipar pruebas de algoritmos cuánticos en la era NISQ sin depender de tiempo en hardware real.
Presentamos aqui una seleccion de los resultados mas importantes obtenidos en cada capitulo de la tesis. El Modelo del Hipercubo Hemos estudiado [Fer10b] un nuevo modelo de campo medio para vidrios de espin sobre un hipercubo unitario en D-dimension es. La principal ventaja de este modelo es que, dada su distribucion espacial, tiene una nocion natural de distancia (caracteristica rara en modelos de campo medio). Hemos probado que, dada la geometria del problema, cualquier mecanica estadistica sobre modelos en el hipercubo con conectividad aleatoria sufre efectos de tamano finito enormes. La solucion presentada pasa por restringir el estudio a aquellos grafos sobre donde el numero de vecinos esta fijo. Generar estos grafos no es trivial, p ero hemos resuelto el problema con un algoritmo dinamico de Montecarlo. Aunque no sabemos si el conjunto de grafos accesibles por este metodo es completo, hemos comprobado que los hipercubos generados son isotropicos, y que el modelo de Edwards-Ander son definido sobre estos grafos cumple todos los checks de consistencia considerados. Una vez definido el modelo, hemos estudiado numericamente la dinamica fuera del equilibrio en la fase vidrio de espin. Las tres caracteristicas principales son: (i ) el envejecimiento consiste en el crecimiento de una longitud de coherencia, como en los sistemas tridimensionales, (ii) el scaling a dos tiempos de la funcion de correlacion implica una infinidad de sectores temporales, y (iii) se ha observado el p ropagador p4. Ademas, hemos estudiado los efectos de volumen finito en nuestro modelo, encontrando que podemos explicar nuestros datos con un ansatz de tamano finito extremadamente simple. Siendo este modelo de campo medio, esta regido por la teoria RSB. Por lo tanto, combinado con su nocion de distancia, se convierte en un patio de pruebas para estudiar la dinamica de no equilibrio en sistemas RSB. Caos en temperatura El caos en temperatura es un fenomeno de eventos extremos. Cuando ocurre, s us efectos son muy fuertes y se pueden sentir incluso a distancias muy cortas, como podemos confirmar con las funcion de correlacion espacial a dos temperaturas [Fer12a]. Han sido cruciales dos ingredientes para alcanzar esta conclusion. Primero, gra cias al superordenador JANUS, hemos tenido acceso a configuraciones mucho mas grandes que todo lo estudiado hasta la fecha, y ademas termalizadas a temperaturas mucho mas bajas [AB10a,AB10b]. En segundo lugar, hemos considerado nuevas herramientas de
Les codes binaires à matrices creuses (Low-Density Parity-Check, LDPC) et les turbo-codes ont une capacité s’approchant de la limite de Shannon pour des trames de grande taille. Cependant, ces codes ont le désavantage d’être moins efficaces pour les faibles tailles. De plus, l’association de codes binaires avec des modulations d’ordre élevé oblige à une étape de marginalisation pour passer d’un symbole aux fiabilités des bits associés à ce symbole. Ce calcul s’accompagne d’une perte d’information qui peut être récupérée par démodulation itérative au prix d’une plus grande complexité. Les codes LDPC définis sur des corps de Galois d’ordre q > 2 permettent de résoudre ces problèmes. Toutefois, lesdécodeurs optimaux associés ont une complexité très importante qui rend leur utilisation problématique.L’objectif de cette thèse est de valoriser les codes LDPC non binaires en proposant d’une part une architecture d’un décodeur à complexité réduite et en montrant d’autre part l’intérêt de les associer à des modulations d’ordre élevé. Dans la première partie de notre thèse, nous proposons de simplifier l’algorithme de décodage Extended Min-Sum (EMS) en considérant un nombre limité n_α << n_m des fiabilités intrinsèques lors de la mise à jour des messages par les nœuds de variable. Cette approche permet de réduire la taille de la mémoire dédiée au stockage des messages intrinsèques. De plus, pour améliorer l’effcacité des nœuds de parité nous proposons une variante simplifiée de l’algorithme L-Bubble Check et l’architecture associée. Enfin, nous montrons par l’intermédiaire d’un prototype sur une carte FPGA (Field Programmable Gate Array) que notre décodeur possède une faible complexité en le comparant avec un ancien décodeur EMS conçu par notre laboratoire de recherche dans le cadre du projet européen DAVINCI. Dans la deuxième partie, nous étudions l’association des codes LDPC non binaires avec une modulation par décalage cyclique de code (Cyclic Code-shift Keying, CCSK) de même ordre. Nous avons choisi cette modulation pour ses propriétés qui permettent de réduire la complexité du démodulateur. En effet, nous montrons qu’il est possible dans le cas d’un système de transmission mono-porteuse avec préfixe cyclique de fusionner le démodulateur et l’égaliseur dans un même bloc comportant une seule transformée de Fourier rapide et une seule transformée de Fourier rapide inverse. Les simulations montrent que ce système possède des performances comparables à un système de transmission multiporteuses de type OFDM (Orthogonal Frequency-Division Multiplexing). Elles montrent aussi que la modulation CCSK donne des performances meilleures que la modulation de Hadamard dans un canal en environnement intérieur sélectif en fréquence. Enfin, les simulations montrent que les codes LDPC non binaires sont nettement plus effcaces avec la modulation CCSK que les codes LDPC binaires même en considérant une démodulation itérative.