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

learn more… | top users | synonyms

0
votes
0answers
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 ...
1
vote
3answers
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 ...
2
votes
0answers
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$). ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
4
votes
1answer
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 ...
0
votes
1answer
53 views

Capacity of binary not symmetrical channel

I have to solve this exercise in information theory: A binary not symmetrical channel has probability of transition from 0 to 1 $P(output=1|input=0)=p$ and probability of transition from 1 to 0 $P(...
1
vote
0answers
7 views

Find minimum conditional entropy

Task : Given $X$ random variables. Find out the minimum conditional entropy for a variable $x_i \in X$ when $x_i$ is conditioned upon any combination $k$ remaining variables. Find $min(Entropy (x_i | ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
20
votes
4answers
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 ...
3
votes
1answer
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: ...
3
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
-1
votes
1answer
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 ...
0
votes
0answers
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 / ...
1
vote
1answer
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 ...
-1
votes
1answer
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 ...
0
votes
1answer
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!
4
votes
1answer
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 ...
4
votes
0answers
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, ...
4
votes
1answer
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 ...
3
votes
1answer
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, ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
17
votes
5answers
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 ...
2
votes
1answer
41 views

Question about the Simon's algorithm

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 ...
1
vote
2answers
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 ...
-1
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
2answers
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 (...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
3answers
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 ...
7
votes
4answers
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 ...
3
votes
2answers
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 ...
5
votes
3answers
471 views

Compression of Random Data is Impossible?

A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 - where someone was offering a prize of \$5000 for any kind of reduction to ...
18
votes
4answers
8k views

Is Morse Code binary, ternary or quinary?

I am reading the book: "Code: The Hidden Language of Computer Hardware and Software" and in Chapter 2 author says: Morse code is said to be a binary (literally meaning two by two) code because ...
2
votes
1answer
52 views

Entropy notation: What does this mean?

If you look at page 13 of the lecture slides here there is this line $H(Y) = H((1-\pi)(1-\alpha), \alpha, \pi(1-\alpha))$ I don't really understand what the term on right hand side is. At first I ...
2
votes
2answers
151 views

Is 95% of code really non-semantic fluff? [closed]

According to A Study of Wheat and Chaff in Source Code, 95% of code is "chaff", or "non-core functionality", whatever that means. Is this really a sensible study? Does the IT World article correctly ...
2
votes
1answer
35 views

Lower bounds for space with some probability of error

There is an information theoretic lower bound of $\log_2 {U \choose x}$ for the number of bits to represent a subset of $x$ elements chosen from a universe of size $U$. We can in principle use this ...
4
votes
1answer
50 views

Doubt in derivation of a proof in Information Theory

In my class we were trying to derive Shannon's Source Theorem, first by proving the equivalent form in a weaker version. The question is: Consider a biased coin with probability of heads $p \geq \...
2
votes
1answer
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 ...
5
votes
0answers
47 views

Name of a type of code similar to block codes

I've encountered a system where I need to construct a sort of quasi block code: We want to encode a symbol $s$ from a finite-sized alphabet $\mathcal{S}$ using $N$ segments of information. The $i^{...
0
votes
2answers
25 views

Why are long block lengths commonly assumed/used in channel coding proofs?

As the title states, why are long block lengths commonly assumed or used in channel coding proofs?
43
votes
8answers
13k views

Is Morse code without spaces uniquely decipherable?

Are all Morse code strings uniquely decipherable? Without the spaces, ......-...-..---.-----.-..-..-.. could be Hello World ...
1
vote
0answers
28 views

Information content of computational problems

The notion of low information content is used to describe sparse sets and tally sets in complexity theory. Such sets can not be $NP$-complete unless $P=NP$. I am not aware of a formal information-...
2
votes
2answers
71 views

An example of a code that is neither p-code or s-code but is uniquely decodable?

As the title says, code can't be a prefix-code and can't be a suffix-code, but it must be uniquely decodable. One possible code is this: {1, 101, 1001, ... }. Number of zeroes corresponds to the index ...