Search

Si, comme l’affirme Foucault, le « connais-toi toi-même » (gnôthi seauton) usurpa jadis la place du « souci de soi » (epimeleia heautou), et si Descartes consacra cette destitution, cela n’implique pas que la philosophie ne puisse renouer avec la pratique gréco-romaine qui accordait au Moi un rôle déterminant. Cet article plaide pour une pratique philosophique où le Moi s’inventerait dans une harmonie réciproque entre logos (discours) et ergon (action)., According to Foucault, Descartes ultimately confirmed the prevalence of the Delphic injunction “know thyself” (gnôthi seauton) over a precept which had previously ruled supreme: the “care of the self” (epimeleia heautou). This does not imply that philosophy cannot renew with its former status when the Self played a prevalent part. This article argues in favor of a philosophy in which the Self would invent itself through a reciprocal harmony between logos (discourses) and ergon (actions).

The Integer Dichotomy Diagram IDD(n) represents a natural number n ∈ N by a Directed Acyclic Graph in which equal nodes are shared to reduce the size s(n). That IDD also represents some finite set of integers by a Digital Search DAG where equal subsets are shared. The same IDD also represents representing Boolean Functions, IDDs are equivalent to (Zero-suppressed) ZDD or to (Binary Moment) BMD Decision Diagrams. The IDD data-structure and algorithms combines three standard software packages into one: arithmetics, sets and Boolean functions. Unlike the binary length l(n), the IDD size s(n) < l(n) is not monotone in n. Most integers are dense, and s(n) is near l(n). Yet, the IDD size of sparse integers can be arbitrarily smaller. We show that a single IDD software package combines many features from the best known specialized packages for operating on integers, sets, Boolean functions, and more. Over dense structures, the time/space complexity of IDD operations is proportional to that of its specialized competitors. Yet equality testing is performed in unit time with IDDs, and the complexity of some integer operations (e.g. n < m, n ± 2 m , 2 2 n ,. . .) is exponentially lower than with bit-arrays. In general, the IDD is best in class over sparse structures, where both the space and time complexities can be arbitrarily lower than those of un-shared representations. We show that sparseness is preserved by most integer operations, including arithmetic and logic operations, but excluding multiplication and division. Keywords: computer arithmetic, integer dichotomy & trichotomy, sparse & dense structures , dictionary package, digital search tree, minimal acyclic automata, binary Trie, boolean function, decision diagram, store/compute/code once. 2

Plan1 Contexte historique . . . . . . . . . . . . . . . . . . . . . . . . . 2I Principes 271 Circuit math´ematique 291.1 Composants de base . . . . . . . . . . . . . . . . . . . . . . . . . 311.2 Forme des circuits digitaux synchrones . . . . . . . . . . . . . . . 351.3 Fonction des circuits . . . . . . . . . . . . . . . . . . . . . . . . 411.4 Montre digitale . . . . . . . . . . . . . . . . . . . . . . . . . . . 492 Alg`ebre binaire 572.1 Num´erations de position . . . . . . . . . . . . . . . . . . . . . . 592.2 Nombre binaire fini . . . . . . . . . . . . . . . . . . . . . . . . . 612.3 Fonction combinatoire . . . . . . . . . . . . . . . . . . . . . . . 692.4 Nombre binaire infini . . . . . . . . . . . . . . . . . . . . . . . . 803 Circuit ´electronique 833.1 Transistor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863.2 Conception et r´ealisation d’un circuit . . . . . . . . . . . . . . . . 993.3 M´emoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1103.4 Progr`es technologique . . . . . . . . . . . . . . . . . . . . . . . 123II Outils 1254 Arithm´etique sur Silicium 1274.1 Compteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1284.2 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1344.3 Soustraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1424.4 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1465 Machines universelles 1595.1 Machine de Turing . . . . . . . . . . . . . . . . . . . . . . . . . 1615.2 Microprocesseur . . . . . . . . . . . . . . . . . . . . . . . . . . 1665.3 Machines parall`eles . . . . . . . . . . . . . . . . . . . . . . . . . 1685.4 Programmation . . . . . . . . . . . . . . . . . . . . . . . . . . . 1736 Nombres calculables 1776.1 Limite th´eorique du calcul . . . . . . . . . . . . . . . . . . . . . 1826.2 Fonctions calculables . . . . . . . . . . . . . . . . . . . . . . . . 1906.3 R´eel calculable R . . . . . . . . . . . . . . . . . . . . . . . . . . 1936.4 Limites pratiques du calcul . . . . . . . . . . . . . . . . . . . . . 202III Applications 2157 Physique digitale 2177.1 Mesure num´erique . . . . . . . . . . . . . . . . . . . . . . . . . 2197.2 Cam´era digitale . . . . . . . . . . . . . . . . . . . . . . . . . . . 2247.3 D´etecteur de particules . . . . . . . . . . . . . . . . . . . . . . . 2277.4 Equation de la chaleur . . . . . . . . . . . . . . . . . . . . . . . 2288 Th´eorie de la communication 2298.1 Th´eorie de Shannon . . . . . . . . . . . . . . . . . . . . . . . . . 2328.2 Compression des donn´ees . . . . . . . . . . . . . . . . . . . . . . 2408.3 Contrˆole des erreurs . . . . . . . . . . . . . . . . . . . . . . . . . 2449 Codage et transmission : audio et vid´eo 2539.1 Signal analogique et signal digital . . . . . . . . . . . . . . . . . 2559.2 Chaˆıne de communication des images . . . . . . . . . . . . . . . 2599.3 Compression d’images photographiques fixes : JPEG . . . . . . . 2619.4 Compression vid´eo et audio : MPEG . . . . . . . . . . . . . . . . 263IV Appendices 2655 Sigles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2676 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

International audience; We consider the transfer of digital data over a loud communication channel, whichreleases significant side-channel emissions, and we try to protect against attacks based on accuratephysical measures from these emissions.The method pairs each secret key k with a camouflage value v, and simultaneously transmit bothk and v over the channel. This releases an emission measured by e(k; v). The mimic value v isselected to make e(k; v) as undistinguishable as possible from any other e(k′; v′).M¨ullerian mimicry is a related natural phenomenon where two different poisonous species k andk′ evolve to confuse their predators by adopting each other’s warning signals e(k; v) and e(k′; v′).We model the problem and show that optimal mimicry values can be effectively derived from afinite amount of a-priori measures over emission traces (just as the attacker will do), with littleother technological assumption. Consequently, the model is applicable across a wide range of readilyavailable technologies.We propose a statistical analysis of mimicry protection, in one, two and more dimensions. Wediscuss algorithms for constructing the best mimicry from actual emission traces. We proposeefficient ones in low dimensions (say up to 4), and heuristic ones beyond.We detail some experimental results obtained on the proposed defensive leakage mimicry againstside-channel attacks: for some memories, buses and IO emissions from otherwise tamper-proofblack-boxes.

A word w in a regular language L is or-accepted by a non-deterministic finite or-automaton A if there exists a path along w from some initial state to some final state in A. The same word w is xor-accepted by the same non-deterministic finite xor-automaton A if the number of accepting pathes is odd. In the deterministic case, accepting pathes are unique and both definitions coincide. No polynomial time algorithm is known to minimize NFAs or to compute their equivalence. By contrast, we present a cubic time algorithm to reduce a xor-automaton to a minimal form M = MXA(A), within the least possible number of states. It is a finite strong normal form and automata equivalence is efficiently decided through reduction to the SNF.

The future Large Hadron Collider (LHC), to be built at CERN, presents among other technological challenges a formidable problem of real-time data analysis. At a primary event rate of 40 MHz, a multi-stage trigger system has to analyze data to decide which is the fraction of events that should be preserved on permanent storage for further analysis. We report on implementations of local algorithms for feature extraction as part of triggering, using the detectors of the proposed ATLAS experiment as a model. The algorithms were implemented for a decision frequency of 100 kHz, on different data-driven programmable devices based on structures of field- programmable gate arrays and memories. The implementations were demonstrated at full speed with emulated input, and were also integrated into a prototype detector running in a test beam at CERN, in June 1994.

This paper describes some of the work on stereo that has been going on at INRIA in the last four years. The work has concentrated on obtaining dense, accurate and reliable range maps of the environment at rates compatible with the real-time constraints of such applications as the navigation of mobile vehicles in man-made or natural environments. The class of algorithms which has been selected among several is the class of algorithms which has been selected among several is the class of correlation-based stereo algorithms because they are the only ones that can produce sufficiently dense range maps with an algoritmic structure which lends itself nicely to fast implementations because of the simplicity of the underlying computation. We describe the various improvements that we have brought to the original idea, including validation and characterization of the quality of the matches, a recursive implementation of the score computation which makes the method independent of the size of the correlation window and a calibration method which does not require the use of a calibration pattern. We then describe two implementations of this algorithm on two very different pieces of hardware. The first implementation is on a board with four digital signal processors designed jointly with Matra MSII. This implementation can produce 64x64 range maps at rate varying between 200 and 400 ms, depending upon the range of disparities. The second implementation is on a board developed by DEC-PRL and can perform the cross-correlation of two 256X256 images in 140 ms. The first implementation has been integrated in the navigation system of the INRIA cart and used to correct for inertial and odometric errors in navigation experiments both indoors and outdoors on road. This is the first application of our correlation-based algorithm which is described in the paper. The second application has been done jointly with people from the french national space agence (CNES) to study the possibility of using stereo on a future planetary rover for the construction of digital elevation maps. We have shown that real time stereo is possible today at low-cost and can be applied in real applications. The algorithm that has been described is not the most sophisticated available but we have made it robust and reliable thanks to a number of improvements. Evan though each of these improvements is not earth-shattering from the pure research point of view, altogether they have allowed us to go beyond a very important threshold. This threshold measures the difference between a program that runs in the laboratory on a few images and one that works continuously for hours on a sequence of stereo pairs and produces results at such rates and of such quality that they can be used to guide a real vehicle or to produce discrete elevation maps. We believe that this threshold has only been reached in a very small number of cases.