Tagged Questions

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

28 views

Data Compression Algorithm for Less repetitive pattern (redundancy) [on hold]

Context: Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy) Questions Which data compression method/algorithm deals with less repetitive ...
269 views

Using Data Compression on the output of Data Compression

Context: Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy) Questions Is there a data compression method/algorithm that uses another data ...
12 views

Clustering with probabilities / vector quantization with arbitrary distance measures

Suppose I'm given $n$ points $x_1,\dots,x_n$ in some space $\mathcal{S}$ (think: $\mathbb{R}^d$), and probabilities $p_1,\dots,p_n$ that form a probability distribution (so $p_1 + \dots + p_n=1$). ...
41 views

Is there a name for “density” of information?

If we compare multimedia and text, if we have n bytes of text and compare it with n bytes of video, then we would be likely to think that n bytes of text is "more" information than n bytes of video ...
25 views

Amount of information in scaled-down images

Does an image that is scaled down lose more Information when calculating averages of pixels rather than selecting single pixels? One way to scale down an image is to replace 2x2 pixel blocks with ...
85 views

How much data could I store on a Rubik's Cube?

Google tells me that a standard 3x3x3 Rubik's Cube has 43,252,003,274,489,856,000 permutations. If I wanted to store data on that Rubik's Cube, how much could I store? The only way I see to store ...
53 views

25 views

Capacity of the Deletion Channel

Consider a Binary Deletion Channel with a deletion probability p of 1/2 and the channel has no error correction coding at all and that any given message can only be sent once. I want to conjecture ...
33 views

Average length and entropy of a code from a probabilistic source

I'm trying to do this exercise but I have some doubts. A binary memoryless source emits the symbols 0 and 1 with probability 0.8 and 0.2 respectively. It encodes three blocks messages: 000 is ...
1k views

Compressing two integers disregarding order

Comparing an ordered pair (x,y) to an unordered pair {x, y} (set), then information theoretically, the difference is only one bit, as whether x comes first or y requires exactly a single bit to ...
129 views

Reconstructing a screen of permuted pixels

Reconstructing a screen of permuted pixels Summary Given a video with the pixel locations randomly permuted (once, for the entire video), can we (efficiently) reconstruct the original picture? Let: ...
45 views

channel capacity of a general binary channel

I have found worked examples for special cases of binary channel such as the binary symmetric channel and the Z-channel. However, I am interested in a more general type of binary channel $X \to Y$ in ...
23 views

Fundamental representation of data relationships?

This is an offshoot of this question Which is more fundamental: key-value or subject-predicate-object? Is there any fundamental, hypothetical or practical, representation of data relationships? Both ...
37 views

Prove that the Kolmogorov complexity function cannot be approached from below

How would one go about proving that Kolmogorov function $K(x)$ cannot be approached from below by any computable function? After some research it seems I must show the function $K(x)$ is not lower ...
34 views

Relation between Hamming distances of columns and rows

You're given a $0-1$ $n\times n$ matrix such that for every distinct columns $C_i$ and $C_j$, $d_H(C_i,C_j)\gt 2t$ for some $t$. What could be said about the Hamming distances of the rows? It it true ...
21 views

Integer Arithmetic Coding misunderstanding of parameters

Given this alphabet $\{a,b,c\}$ where $P(a) = 2/5$, $P(b) = 2/5$, $P(c) = 1/5$. Encode this string : $bcba$. I have to encode this using 5 bits. I have been looking in the Introduction to Data ...
64 views

Is there any difference between information architecture and information structure in case of web apps?

In the course of Web Engineering, the course teacher said in the class of Information Design that site map has 4 main kinds. Linear Layout Hierarchical Layout Grid / Matrix Type Structure Network / ...
57 views

Applying information theory to processor clocks

Has there been any research on the subject of applying information theory to a processors clock? It occurred to me that a clock is actually transmitting data that is used for synchronization of ...
18 views

How can we find the channel capacity from a BSC? (information theory) [closed]

I'm struggling to find how to calculate the channel capacity from a binary symmetric channel, given alpha(mean error) = 0.25 p(x1) = 0.25, p(x2) = 0.75 r = 1.25MBits/sec I found this in the ...
37 views

Data transfer at certain frequencies

I am curious as to what the maximum data transmission rates are to a given frequency. Say you have a com channel with a frequency of 10 khz. How many bits/s would you be able to send? Thanks!
40 views

One-shot Private Randomness Extractor

Suppose a pair of random variables $(X,Y)\in\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$ is given. I am interested in a deterministic mapping $f:\mathcal{Y}\to \{0, 1\}^k,$ for ...
49 views

Average redundancy in Huffman or Hu-Tucker codes on random symbol probabilities

Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, ...
202 views

Is there a generalization of Huffman Coding to Arithmetic coding

In trying to understand the relationships between Huffman Coding, Arithmetic Coding, and Range Coding, I began to think of the shortcomings of fuffman coding to be related to the problem of fractional ...
202 views

Two dimensional parity check

Firstly, I would like to apologize if I misplaced this topic / i think the theory of coding is close to CS / I am little bit confused right now, in the school we were learning about Hamming's code, ...
34 views

Prove $\forall c \in \mathbb{N} \, \exists x,y \in \Sigma^* \, [K(xy) > K(x) + K(y) + c]$

I am trying to prove a theorem (title) given in a starred problem in Sipser's book. I have absolutely no idea how I would go about showing it, and after trying a few different approaches came here ...
49 views

What does this mean $[X]_1^T$?

I found this in information theory paper, P.3883* the authors states the following Most existing theoretic studies of network coding focus on DAGs due to its simpler structure and dure to the ...
3k views

Data compression using prime numbers

I have recently stumbled upon the following interesting article which claims to efficiently compress random data sets by always more than 50%, regardless of the type and format of the data. Basically ...
41 views

This comes from trying to understand the "Simon's algorithm". So we have a set of $2^n$ kets $|x_i \rangle$ one each for $i \in \{0,1\}^n$. Each $x_j \in \{0,1\}^n$. And we have the further ...
112 views

Shannon Entropy for Binary Numbers

First of all, I have to mention that I am very new in the field of information theory. I have a question regarding the Shannon Entropy calculation for binary values. As far as I understood, the main ...
55 views

What is the relation between differential-privacy mechanism and entropy?

Why do differential-privacy people care whether or not the noise function saturates the lower bound of Shannon entropy? For example : Laplace distribution that is used to model the noise function ...
28 views

Why is self-information defined the way it is?

The self-information of an event of probability $p_x$ is defined as $I(p_x)=-\log_2(p_x)$.¹ I fully understand this for equiprobable events of the form $p_x = \frac{1}{2^k}$. In that case, we want ...
129 views

How much bits need to add to 100bit of data in order to correct up to 10bits?

I'm trying to calculate how much minimum bits need to be added to data of 100bits, in order to correct 10 bits that are messed up by: bits that deleted (Erasure Correcting) bits that corrupted (...
27 views

Entropy based progress bar [closed]

Would it be possible to build a progress bar that estimates progress using entropy? Consider a web browser that is downloading a large file (for instance), which displays a progress bar indicating ...
31 views

Can one use the PCP theorem to prove correctness of deternimistic algorithms?

I am thinking of the equality "PCP(O(log(n)),0) = P" Say I have a deterministic polynomial time algorithm $A$ whose correctness I can't prove immediately. But say I create a probabilistic version of ...
88 views

Which fingerprinting/hashing algorithms support compounding?

The definition of fingerprinting algorithms in Wikipedia describe a property called compounding as you can see here as: Some fingerprinting algorithms allow the fingerprint of a composite file to ...
437 views

Compression functions are only practical because “The bit strings which occur in practice are far from random”?

I would have made a comment, as this pertains to Andrej Bauer's answer in this thread; however, I believe it is worth a question. Andrej explains that given the set of all bit strings of length 3 or ...
122 views

Why Shannon's Entropy is said to be a measure of information?

I got a bit of how Shannon explained to find the number of bits required to represent a message and Shannon's Entropy.But it's natural to know that to code alphabet letters you need ...
471 views

28 views

Using all the entropy in an biased bit

Suppose we have $n$ bits of random-looking data, and we want to encode it in such a way that instead of 1/2 the bits being 1's, we have (say) 3/4 the bits being 1's. The entropy of each bit in the new ...