Message | EPFL Graph Search

Un message est un ensemble de signes. Il implique donc un codage par l'émetteur, et un décodage par le récepteur (d'où la nécessité d'un code commun). La théorie de l'information fut mise au point pour déterminer mathématiquement le taux d’information transmis dans la communication d’un message par un canal de communication, notamment en présence de parasites appelés bruits. Il fut repris par Roman Jakobson pour étayer la théorie linguistique. Dans la théorie de l'information et de la communication Les premiers travaux sur la notion d’information de Claude Shannon, Ralph Hartley, Warren Weaver, Harold Lasswell, Werner Meyer-Eppler... ont permis de mieux comprendre les systèmes de structuration d’un message : ils ont entraîné de nombreuses recherches sur les moyens de traitement de l’information et donc sur un concept directement lié à l’informatique. Ils ont même rejoint la sphère paradigmatique des grandes théories qui furent utilisées pour expliquer l’univers. Le messag

A Novel Conflict-Free Memory and Processor Architecture for DVB-T2 LDPC Decoding

Alberto Jimenez Pacheco

In this paper, we present a flexible architecture for an LDPC decoder that fully exploits the structure of the codes defined in the DVB-T2 standard (Digital Video Broadcasting - Second Generation Terrestrial). We propose a processor and memory architecture which uses the flooding schedule and has no memory access conflicts, which are encountered in serial schedule decoders proposed in the literature. Thus, unlike previous works, we do not require any extra logic or ad hoc designs to resolve memory conflicts. Despite the typically slower convergence of flooding schedule compared to serial schedule decoders, our ar- chitecture meets the throughput and BER requirements specified in the DVB-T2 standard. Our design allows a trade-off between memory size and performance by the selection of the number of bits per message without affecting the general memory arrangement. Besides, our architecture is not algorithm specific: any check-node message processing algorithm can be used (Sum-Product, Min-Sum, etc.) without modifying the basic architecture. Furthermore, by simply adding relevant small ROM tables, we get a decoder that is fully compatible with all three second generation DVB standards (DVB-T2, DVB-S2 and DVB-C2). We present simulation results to demonstrate the viability of our solution both functionally and in terms of the bit-error rate performance. We also discuss the memory requirements and the throughput of the architecture, and present preliminary synthesis results in CMOS 130nm technology.

2011

Optimal Computational Split-state Non-malleable Codes

Divesh Aggarwal, Divya Gupta

Non-malleable codes are a generalization of classical error-correcting codes where the act of "corrupting" a codeword is replaced by a "tampering" adversary. Non-malleable codes guarantee that the message contained in the tampered codeword is either the original message m, or a completely unrelated one. In the common split-state model, the codeword consists of multiple blocks (or states) and each block is tampered with independently. The central goal in the split-state model is to construct high rate non-malleable codes against all functions with only two states (which are necessary). Following a series of long and impressive line of work, constant rate, two-state, non-malleable codes against all functions were recently achieved by Aggarwal et al. [2]. Though constant, the rate of all known constructions in the split state model is very far from optimal (even with more than two states). In this work, we consider the question of improving the rate of splitstate non-malleable codes. In the "information theoretic" setting, it is not possible to go beyond rate 1/2. We therefore focus on the standard computational setting. In this setting, each tampering function is required to be efficiently computable, and the message in the tampered codeword is required to be either the original message m or a "computationally" independent one. In this setting, assuming only the existence of one-way functions, we present a compiler which converts any poor rate, two-state, (sufficiently strong) non-malleable code into a rate-1, two-state, computational non-malleable code. These parameters are asymptotically optimal. Furthermore, for the qualitative optimality of our result, we generalize the result of Cheraghchi and Guruswami [10] to show that the existence of one-way functions is necessary to achieve rate > 1/2 for such codes. Our compiler requires a stronger form of non-malleability, called augmented non-malleability. This notion requires a stronger simulation guarantee for non-malleable codes and simplifies their modular usage in cryptographic settings where composition occurs. Unfortunately, this form of non-malleability is neither straightforward nor generally guaranteed by known results. Nevertheless, we prove this stronger form of non-malleability for the two-state construction of Aggarwal et al. [3]. This result is of independent interest.

Springer Int Publishing Ag2016

Implementing Belief Propagation on P-Grid

Damien Auroux, Nicolas Bonvin, Grégoire Montavon

Some applications require to solve a Bayesian network in a distributed fashion. It can lead to a large amount of messages exchanged between hosts if the variables of the Bayesian network are not allocated to good hosts. The technique we implement uses an algorithm that allocates variables to hosts so that the tension of the Bayesian network is minimized. We present and discuss our results.

2007

Optimal Computational Split-state Non-malleable Codes

Divesh Aggarwal, Divya Gupta

Springer Int Publishing Ag2016