Computer Science Asked by Black Jack 21 on November 10, 2020

I am a little confused about stochastic encoding in channel coding. For example, in the identification problem (R. Ahlswede and G. Dueck, “Identification via channels”), the authors claim that we can achieve nearly 0 probability of error when using $O( log log M)$ bits, where $M$ is the total number of messages. Instead, deterministic encoding would require us to use at least $O(log M)$ bits instead.

Can anyone give an intuitive explanation of why stochastic encoding is so effective? One possible idea which opposes the result is that the stochastic code would result in many possible codes for a single message which should make it more difficult for the decoder as the codes are now more ‘tightly packed’, i.e., there are many more valid codes possible for the same number of bits transmitted.

Well, I think you are conflating two things. It is correct that in a lot of settings probabilistic encoding (e.g., Polar Codes, Convolutional Codes, LDPC Codes) [assuming you know a good model for the noise process of the channel] does much better than algebraic coding, intuitively because channels have memory and block codes ignore that memory.

However, Ahlswede's Identification Problem is quite different. It is NOT a traditional channel coding problem There is a good review here

The author states

In the problem of identification via channels, introduced by Ahlswede and Dueck the receiver is

only interested in testing whether a particular message was sent, but the encoder does not know which message the decoder wants. Errors are now considered in terms of false alarm and missed identification. It turns out that for this case, one can design systems such that the number of different messages one can identify growsdoubly exponentially with the blocklength. The trick is that each message can map into a list of codewords and the encoder selects one randomly. As long as the fraction of the pairwise overlap of these lists is small, the error probabilities will be small

Answered by kodlu on November 10, 2020

Get help from others!

Recent Answers

- Jon Church on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP