Prefix code | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

A prefix code is a type of code system distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system. It is trivially true for fixed-length code, so only a point of consideration in variable-length code. For example, a code with code words {9, 55} has the prefix property; a code consisting of {9, 5, 59, 55} does not, because "5" is a prefix of "59" and also of "55". A prefix code is a uniquely decodable code: given a complete and accurate sequence, a receiver can identify each word without requiring a special marker between words. However, there are uniquely decodable codes that are not prefix codes; for instance, the reverse of a prefix code is still uniquely decodable (it is a suffix code), but it is not necessarily a prefix code. Prefix codes are also known as prefix-free codes, prefix condition codes and instantaneous codes. Althoug

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (2)

Related publications

Related people

Related units

Related concepts (7)

Related concepts

Related courses (4)

Related courses

Related lectures (14)

Related lectures

Universal code (data compression)

In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distributi

Lossless compression

Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible b

Code

In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for c

Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities

Arjen Lenstra

We present a novel, automated way to find differential paths for MD5. As an application we have shown how, at an approximate expected cost of 2 50 calls to the MD5 compression function, for any two chosen message prefixes P and P′, suffixes S and S′ can be constructed such that the concatenated values P||S and P′||S′ collide under MD5. Although the practical attack potential of this construction of chosen-prefix collisions is limited, it is of greater concern than random collisions for MD5. To illustrate the practicality of our method, we constructed two MD5 based X.509 certificates with identical signatures but different public keys and different Distinguished Name fields, whereas our previous construction of colliding X.509 certificates required identical name fields. We speculate on other possibilities for abusing chosenprefix collisions. More details than can be included here can be found on www.win.tue.nl/hashclash/ChosenPrefixCollisions/. © International Association for Cryptology Research 2007.

2007

Introduction aux sciences de l'information

Jean-Yves Le Boudec, Patrick Thiran, Rüdiger Urbanke

Les fichiers échangés sur Internet et stockés sur les disques durs contiennent de l’information qui deviendra finalement du texte, des images ou des sons. Mais comment cette information est-elle mesurée et comprimée ? Comment est-elle sécurisée pour éviter les copies illicites ? Comment est-elle protégée contre les erreurs lors d’une recopie ? Voici les questions auxquelles répond cet ouvrage. Sans équivalent dans la littérature, il présente pour la première fois les théories de l’entropie, du codage et de la cryptographie de façon simple, claire et pédagogique. Principalement destiné aux étudiants en sciences de première année de Bachelor, il intéressera aussi, et plus largement, tous ceux curieux de comprendre la théorie scientifique à la base du traitement de l’information.

Presses Polytechniques et Universitaires Romandes2015

COM-406: Foundations of Data Science

We discuss a set of topics that are important for the understanding of modern data science but that are typically not taught in an introductory ML course. In particular we discuss fundamental ideas and techniques that come from probability, information theory as well as signal processing.

COM-404: Information theory and coding

The mathematical principles of communication that govern the compression and transmission of data and the design of efficient methods of doing so.

EE-543: Advanced wireless receivers

Students extend their knowledge on wireless communication systems to spread-spectrum communication and to multi-antenna systems. They also learn about the basic information theoretic concepts, about channel coding, and bit-interleaved coded modulation.