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.
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.
Block codeIn coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way.
Canal de communication (théorie de l'information)vignette En théorie de l'information, un canal de communication ou canal de transmission est un support (physique ou non) permettant la transmission d'une certaine quantité d'information, depuis une source (ou émetteur) vers un destinataire (ou récepteur). Souvent, le canal altère l'information transmise, par exemple en ajoutant un bruit aléatoire. La quantité d'information qu'un canal de communication peut transporter est limitée : on parle de capacité du canal.
Non Return to ZeroDans le code en ligne NRZ, pour non-return-to-zero en anglais, le bit 1 est représenté par un état significatif (par exemple, une tension clairement positive), et le bit 0 par un autre état significatif (par exemple, une tension clairement négative). Il n'existe pas d'état intermédiaire. Le codage est à deux états : le signal se trouve dans un état (par exemple à l’état haut) lorsque des 1 logiques sont transmis, et dans l'autre état (à l’état bas dans l'exemple) lorsque des 0 logiques sont transmis.
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.
Ensemble finiEn mathématiques, un ensemble fini est un ensemble qui possède un nombre fini d'éléments, c'est-à-dire qu'il est possible de compter ses éléments, le résultat étant un nombre entier. Un ensemble infini est un ensemble qui n'est pas fini. Ainsi l'ensemble des chiffres usuels (en base dix) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} qui possède 10 éléments, est fini. De même l'ensemble des lettres de l'alphabet qui possède 26 éléments. L'ensemble de tous les nombres entiers naturels {0, 1, 2, 3,..., 10,..., 100,...
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.
Code correcteurvignette|Pour nettoyer les erreurs de transmission introduites par l'atmosphère terrestre (à gauche), les scientifiques de Goddard ont appliqué la correction d'erreur Reed-Solomon (à droite), qui est couramment utilisée dans les CD et DVD. Les erreurs typiques incluent les pixels manquants (blanc) et les faux signaux (noir). La bande blanche indique une brève période pendant laquelle la transmission a été interrompue.
Low (complexity)In computational complexity theory, a language B (or a complexity class B) is said to be low for a complexity class A (with some reasonable relativized version of A) if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional power if it is given the ability to solve problems in B at unit cost. In particular, this means that if B is low for A then B is contained in A.
Codage en ligneDans le domaine des télécommunications, un code en ligne est un codage destiné à être utilisé dans les systèmes de communication pour transmettre des données. Pour le transport de données numériques, le codage en ligne est souvent utilisé. Il consiste à représenter le signal numérisé à transporter, par un autre signal qui présente des variations d'amplitude régulièrement espacées dans le temps, celui-ci étant adapté aux propriétés physiques spécifiques des canaux de transmissions (et des équipements récepteurs).
Canal binaire symétriqueAlice veut transmettre un message à Bob. Un canal binaire symétrique est un canal discret où Alice transmet une suite d’éléments de l'ensemble et où la probabilité d'erreur dans la transmission d'un symbole est de , pour 0 et pour 1 (d'où la symétrie). Ce canal est sans mémoire, c'est-à-dire qu'aucune archive des messages n'est conservée. En communication, un problème classique est d'envoyer de l'information d'une source à une destination via un canal de communication, en présence de bruit.
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.
Théorie de l'informationLa théorie de l'information, sans précision, est le nom usuel désignant la théorie de l'information de Shannon, qui est une théorie utilisant les probabilités pour quantifier le contenu moyen en information d'un ensemble de messages, dont le codage informatique satisfait une distribution statistique que l'on pense connaître. Ce domaine trouve son origine scientifique avec Claude Shannon qui en est le père fondateur avec son article A Mathematical Theory of Communication publié en 1948.
Soft errorIn electronics and computing, a soft error is a type of error where a signal or datum is wrong. Errors may be caused by a defect, usually understood either to be a mistake in design or construction, or a broken component. A soft error is also a signal or datum which is wrong, but is not assumed to imply such a mistake or breakage. After observing a soft error, there is no implication that the system is any less reliable than before. One cause of soft errors is single event upsets from cosmic rays.
Classe de complexitéEn informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
Computational complexityIn computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.
P (complexité)La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques. Par définition, un problème de décision est dans P s'il est décidé par une machine de Turing déterministe en temps polynomial par rapport à la taille de l'entrée. On dit que le problème est décidé en temps polynomial. Les problèmes dans P sont considérés comme « faisables » (feasible en anglais), faciles à résoudre (dans le sens où on peut le faire relativement rapidement).
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.
Dedekind-infinite setIn mathematics, a set A is Dedekind-infinite (named after the German mathematician Richard Dedekind) if some proper subset B of A is equinumerous to A. Explicitly, this means that there exists a bijective function from A onto some proper subset B of A. A set is Dedekind-finite if it is not Dedekind-infinite (i.e., no such bijection exists). Proposed by Dedekind in 1888, Dedekind-infiniteness was the first definition of "infinite" that did not rely on the definition of the natural numbers.
