Genie-aided decoder

Question

I am reading about different type of decoders and I am often coming across the term "genie-aided." However, I am having trouble understanding what this is. Can someone clarify? Genie-aided decoders seem to be a common topic when dealing with interference channels.

For example, in this publication.

Could you present an example? – Bradman175 Aug 23 '16 at 07:52 — Bradman175, Aug 23 '16 at 07:52

score 3 · Answer 1 · answered Aug 23 '16 at 08:18

3

From the publication in question:

Our upper bounds are all determined by considering a genie-aided decoder with access to side information about the deletion process.

This is referring to a fictional construct where the decoder has more information than would be naturally available, such as to a supernatural being such as a djinn. It is used to define an ideal limit that could not possibly be breached by anything other than random chance.

answered Aug 23 '16 at 08:18

Ignacio Vazquez-Abrams

48,282
4
73
102

This is it. See also "Maxwell's Demon", a supernatural being who helped establish key principles in thermodynamics in the mid 1800s. Their descendants have presumably learned communications theory. Note the connection between interference in the form of noise, and entropy in thermodynamics. – Aug 23 '16 at 09:33

Marcus Müller · Accepted Answer · 2016-08-23T08:24:49.127

As far as I know the term "Genie-aided" goes back to

Jacobs, I., and E. Berlekamp. "A lower bound to the distribution of computation for sequential decoding." IEEE Transactions on Information Theory 13.2 (1967): 167-174.

with the central paragraph here being:

Since our initial bound involves only the first N letters of the tree, we may expedite the decoder’s search by stationing a benevolent, omniscient genie at the N + 1st letter. This genie tells the decoder whether or not the decoder has selected the correct yi.

So, I'd expect the term "Genie-Aided" to need definition in every paper that uses it – it'll probably be a weighted sum of some aspects of the hidden info that you're trying to get, coming in through a side-channel, but I don't see how that would be mathematically well-defined.

Genie-aided decoder

2 Answers2