Mathematics Research Institute


Combatting Erasures

Ludo Tolhuizen (Philips Research, Eindhoven, Holanda)

Fecha: 24/05/2013 13:00
Lugar: Sala de Grados I, Facultad de Ciencias
Grupo: GIR, Codificación de de la Información y Criptografía, Proyecto MTM2010-21580-CO2-02

The presentation consists of two parts. In the first part, we consider decoding for the binary erasure channel. We show that for any code, the probability of not decoding correctly is monotonically non-decreasing in the erasure probability of the channel, provided that the decoder satisfies a very natural property. This is in contrast with known results for the misdetection probability of a code used for pure error detection on the binary symmetric channel. In the second part, we consider the following communication situation. A sender transmits a word with symbols from a finite alphabet. The receiver knows a set Є of potential erasure values: it receives transmitted symbols outside Є correctly, while it receives any transmitted symbol from Є as an erasure. The transmitter, however, does not know Є, but only its cardinality. We give constructions and bounds for codes for this communication situation. One of the constructions leads to the following mathematical problem that may be of independent interest. Let p be a prime number, and let r ≥ 1. Determine the largest set of vectors of length r with entries from GF(p) such that any subset of this set of vectors is uniquely determined by the sum of its elements. Some results for this problem will be presented.