Codes de parité à faible densitéDans la théorie de l'information, un contrôle de parité de faible densité LDPC est un code linéaire correcteur d'erreur, permettant la transmission d'information sur un canal de transmission bruité. LDPC est construit en utilisant un graphe biparti clairsemé. Les codes LDPC ont une capacité approchant la limite théorique. À l'aide de techniques itératives de propagation d'information sur la donnée transmise et à décoder, les codes LDPC peuvent être décodés en un temps proportionnel à leur longueur de bloc.
Passage de messagesLe modèle de passage de messages (message passing en anglais) est un modèle de communication entre ordinateurs ou entre processus à l'intérieur d'un même ordinateur. Il réalise l’envoi de messages simples. Il constitue la couche de base des Middleware Orientés Messages. Au-dessus de cette couche, on trouve d'autres couches de middleware de plus en plus perfectionnées et qui sont : La (message queueing en anglais) qui ajoute la notion de persistance au passage de messages ; Le modèle par abonnement (publish-subscribe en anglais), qui utilise les fonctions du passage de messages ou des files d'attente de message et qui ajoute la notion d’anonymat et d’abonnement.
Message Passing InterfaceMessage Passing Interface (MPI) est un outil pour le calcul scientifique à haute performance qui permet d'utiliser plusieurs ordinateurs. C'est une norme conçue en 1993-94 pour le passage de messages entre ordinateurs distants ou dans un ordinateur multiprocesseur. Elle est devenue de facto un standard de communication pour des nœuds exécutant des programmes parallèles sur des systèmes à mémoire distribuée. Elle définit une bibliothèque de fonctions, utilisable avec les langages C, C++ et Fortran.
Error correction codeIn computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code or error correcting code (ECC). The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors.
File d'attente de messageUne file d'attente de message ou simplement file de messages est une technique de programmation utilisée pour la communication interprocessus ou la communication de serveur-à-serveur. Les logiciels fournissant ce type de service font partie des « Message-Oriented Middleware » ou MOM. Les files d'attente de message permettent le fonctionnement des liaisons asynchrones normalisées entre deux serveurs, c'est-à-dire de canaux de communications tels que l'expéditeur et le récepteur du message ne sont pas contraints de s'attendre l'un l'autre, mais poursuivent chacun l'exécution de leurs tâches.
Factor-critical graphIn graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph) is a graph with n vertices in which every subgraph of n − 1 vertices has a perfect matching. (A perfect matching in a graph is a subset of its edges with the property that each of its vertices is the endpoint of exactly one of the edges in the subset.) A matching that covers all but one vertex of a graph is called a near-perfect matching. So equivalently, a factor-critical graph is a graph in which there are near-perfect matchings that avoid every possible vertex.
Factorisation de graphesvignette|200x200px| Une 1-factorisation du graphe de Desargues : chaque classe de couleur est un 1-facteur. droite|vignette|200x200px| Le graphe de Petersen peut être partitionné en un 1-facteur 1 (en rouge) et un 2-facteur 2 (en bleu). Cependant, le graphe n'est pas 1-factorisable. En théorie des graphes, un facteur d'un graphe G est un graphe partiel, c'est-à-dire un graphe qui a le même ensemble de sommets que G et dont les arêtes sont contenues dans celles de G.
Tornado codeIn coding theory, Tornado codes are a class of erasure codes that support error correction. Tornado codes require a constant C more redundant blocks than the more data-efficient Reed–Solomon erasure codes, but are much faster to generate and can fix erasures faster. Software-based implementations of tornado codes are about 100 times faster on small lengths and about 10,000 times faster on larger lengths than Reed–Solomon erasure codes. Since the introduction of Tornado codes, many other similar erasure codes have emerged, most notably Online codes, LT codes and Raptor codes.
Graphe bipartiEn théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints et tels que chaque arête ait une extrémité dans et l'autre dans . Un graphe biparti permet notamment de représenter une relation binaire. Il existe plusieurs façons de caractériser un graphe biparti. Par le nombre chromatique Les graphes bipartis sont les graphes dont le nombre chromatique est inférieur ou égal à 2. Par la longueur des cycles Un graphe est biparti si et seulement s'il ne contient pas de cycle impair.
Factor graphA factor graph is a bipartite graph representing the factorization of a function. In probability theory and its applications, factor graphs are used to represent factorization of a probability distribution function, enabling efficient computations, such as the computation of marginal distributions through the sum-product algorithm. One of the important success stories of factor graphs and the sum-product algorithm is the decoding of capacity-approaching error-correcting codes, such as LDPC and turbo codes.
Concatenated error correction codeIn coding theory, concatenated codes form a class of error-correcting codes that are derived by combining an inner code and an outer code. They were conceived in 1966 by Dave Forney as a solution to the problem of finding a code that has both exponentially decreasing error probability with increasing block length and polynomial-time decoding complexity. Concatenated codes became widely used in space communications in the 1970s.
Méthode de décodageEn théorie des codes, il existe plusieurs méthodes standards pour décoder des mots de code transmis sur un canal de communication avec bruit. Ce sont donc des techniques qui servent à effectuer l'opération inverse du codage de canal. Le décodage par vote majoritaire. Le décodage par observateur idéal. Le décodage par probabilité maximale. Le décodage par distance minimale. Le décodage par syndrome est une méthode de décodage très efficace pour un code linéaire sur un canal de communication avec bruit.
Turbo codeTurbo code est le nom générique d'un code correcteur imaginé dans les années 1990, qui permet de s'approcher aussi près qu'on le souhaite de la limite de Shannon. Les turbo codes représentent une percée majeure dans le domaine des communications numériques. Ils sont utilisés dans de nombreux standards de téléphonie mobile (UMTS, LTE), de communications par satellites (Inmarsat, DVB-RCS) ou de courants porteurs en ligne. Leur inventeur est Claude Berrou qui breveta cette technologie pour le compte de France Télécom et TDF.
Théorème du codage de canalEn théorie de l'information, le théorème du codage de canal aussi appelé deuxième théorème de Shannon montre qu'il est possible de transmettre des données numériques sur un canal bruité avec un taux d'erreur arbitrairement faible si le débit est inférieur à une certaine limite propre au canal. Ce résultat publié par Claude Shannon en 1948 est fondé sur des travaux antérieurs de Harry Nyquist et Ralph Hartley. La première preuve rigoureuse fut établie par Amiel Feinstein en 1954.
Programmation concurrenteLa programmation concurrente est un paradigme de programmation tenant compte, dans un programme, de l'existence de plusieurs piles sémantiques qui peuvent être appelées threads, processus ou tâches. Elles sont matérialisées en machine par une pile d'exécution et un ensemble de données privées. La concurrence est indispensable lorsque l'on souhaite écrire des programmes interagissant avec le monde réel (qui est concurrent) ou tirant parti de multiples unités centrales (couplées, comme dans un système multiprocesseurs, ou distribuées, éventuellement en grille ou en grappe).
Code d'effacementEn théorie de l'information, un code d'effacement est un code de correction d'erreur directe pour le canal binaire d'effacement qui transforme un message composé de symboles en un message plus long composé de symboles tel que le message original peut être retrouvé à partir d'un sous-ensemble de ces symboles. La fraction est appelé « débit du code ». La fraction , où représente le nombre de symboles requis pour restaurer le message est appelée efficacité de la réception.
Graphe cordalthumb|Un cycle, en noir, avec deux cordes, en vert. Si l'on s'en tient à cette partie, le graphe est cordal. Supprimer l'une des arêtes vertes rendrait le graphe non cordal. En effet, l'autre arête verte formerait, avec les trois arêtes noires, un cycle de longueur 4 sans corde. En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle.
Parallel programming modelIn computing, a parallel programming model is an abstraction of parallel computer architecture, with which it is convenient to express algorithms and their composition in programs. The value of a programming model can be judged on its generality: how well a range of different problems can be expressed for a variety of different architectures, and its performance: how efficiently the compiled programs can execute. The implementation of a parallel programming model can take the form of a library invoked from a sequential language, as an extension to an existing language, or as an entirely new language.
Théorème du point fixe de BrouwerEn mathématiques, et plus précisément en topologie algébrique, le théorème du point fixe de Brouwer fait partie de la grande famille des théorèmes de point fixe, qui énoncent que si une fonction continue f vérifie certaines propriétés, alors il existe un point x0 tel que f(x0) = x0. La forme la plus simple du théorème de Brouwer prend comme hypothèse que la fonction f est définie sur un intervalle fermé borné non vide I et à valeurs dans I. Sous une forme plus générale, la fonction est définie sur un convexe compact K d'un espace euclidien et à valeurs dans K.
Asynchronous I/OIn computer science, asynchronous I/O (also non-sequential I/O) is a form of input/output processing that permits other processing to continue before the transmission has finished. A name used for asynchronous I/O in the Windows API is overlapped I/O. Input and output (I/O) operations on a computer can be extremely slow compared to the processing of data. An I/O device can incorporate mechanical devices that must physically move, such as a hard drive seeking a track to read or write; this is often orders of magnitude slower than the switching of electric current.
