# Questions tagged [information-theory]

Questions about Information theory, entropy, and information content of various sources

322 questions
Filter by
Sorted by
Tagged with
28 views

### What are the steps to create an intuitive and straightforward proof of the optimality of Huffman coding?

I am having great difficulty following the proof in class. I assume "optimal" means it minimizes the Average bit length to encode an alphabet with known frequencies. My understanding of how ...
44 views

### Is computation of a given operation infinitely multiply realizable 'computationally-speaking'?

This is a somewhat philosophical question, but I would like to know if there is a hard answer. Also, please excuse my likely unconventional terminology here, this is not my field of expertise. ...
84 views

### Data structure for prefix covering

I have a list $[1, 2, \ldots, T]$. I want to create a collection of subsets, such that: each element belongs to a small number of subsets each prefix is a union of small number of subsets (these ...
1 vote
34 views

### How to prove a minimum number of queries needed to determine a piece of information

You have 27 coins, 1 of which is a different weight. Using a balance scale with 2 pans, how can you determine which coin is different in only 4 weighings? Generalize this to N coins. Hint Solution ...
1 vote
33 views

### Is it possible to avoid encoding the state in streaming ANS?

regular ANS collects all the data into one big integer and provides optimal compression. In cases where all the symbol probabilities are powers of two, it is just as good as huffman coding (because ...
20 views

### NP-HARD optimization problem and instance correlation

If an optimization problem A is NP-hard and P≠NP, then does there exist an instance x of A such that no polynomial algorithm provides an optimal solution for x?
33 views

1 vote
52 views

### Sorting lower bound is linear when only a constant number of distinct keys?

I saw this proposition on Sedgewick's lecture slides on QuickSort, and I've been wondering why the number of comparisons is linear in the case of a constant number of distinct keys. I tried to ...
14 views

### What does it exactly mean by information management as a function of O/s

I have read that information management is a function of O/s by which it A) Manages, stores, retrieves,modify data. It makes sure that right people have access to their information. B) Some of the ...
1 vote
136 views

### How to decode shortened Reed-Solomon code?

I am working with a shortened version of $[n,k,d]$ Reed-Solomon code. I am encoding a message of size $k−l$ which gives a shortened code of size $n−l$ (this is equivalent to encoding the same message ...
11 views

### Is there an entropy evaluation method with an unified length?

For entropy, the most common one is Shannon entropy, however, it ignores time series of data. For instance, data 0x00001111 and 0x01010101 are given the same entropy. It is obvious that the second ...
101 views

### Proof in the "Reaching Agreement in the Presence of Faults"

I am reading the "Reaching Agreement in the Presence of Faults", M. Pease et al and trying to understand their proof for the $n \geq 3m+1$ case. In the induction step $m \gt 0$ it says the ...
27 views

### Information theory - Expurgation step to go from average error to worst case error in the large error regime

Consider a discrete memoryless channel $N$. We use a code to send messages over this channel. Shannon showed that if we have a code $C$ with a finite number of codewords $|C|$ such that the average ...
1 vote
169 views

### What is the entropy of an unordered list?

I'm trying to compress unordered lists of a few thousand integers for transmission over HTTP, and Claude Shannon is disappointing me with his mathematical ambiguity :) Each integer is 6-digits, so ...
1 vote
86 views

### Is every binary sequence the output of some meaningful-text-input algorithm?

Here is the problem: Let's say we have a random binary sequence, just an arbitrary sequence of zeroes and ones (of some arbitrary length of digits). Can we find an algorithm that would decode/...
78 views

### Is an AI upscaler incapable of reducing entropy?

I was reading the description of Anime4K (a video upscaler software) and I found a statement triggering my attention: [upscaling is done] without any meaningful decrease in entropy (lost information ...
196 views

### Deriving a lower bound on the conditional entropy, conditioned on an event

I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\{0,1\}^n$, and some ...
Consider the the binary erasure channel, with input and output alphabet $\{0,?,1\}$ and channel matrix \begin{bmatrix} 1-\lambda-\mu & \mu & \lambda\\ 0 & 1 & 0\\ \lambda & \mu &...