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

learn more… | top users | synonyms

3
votes
1answer
87 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
36 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
21 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
31 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
17 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
62 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
54 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
14 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
36 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
39 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 ...
3
votes
0answers
46 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, ...
3
votes
1answer
172 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 ...
2
votes
1answer
123 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 ...
15
votes
5answers
2k 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
35 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
101 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
48 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
27 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
111 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
25 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
30 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
79 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
3answers
362 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
114 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
301 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 ...
17
votes
4answers
7k 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
51 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
149 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
33 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
49 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 ...
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?
42
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 ...
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 ...
1
vote
0answers
22 views

Can independence numbers of box products of cycles increase after stabilizing?

Is there an evidence or a proof that the independence of strong products of graphs can increase after stabilizing? I am interested in odd cycles only. Let $C_n$ be an odd cycle and $\alpha(G)$ ...
1
vote
1answer
28 views

Inferring Shannon Capacity of pentagon

Can we infer from the fact that the number of independent sets in product of $5$-cycle two times is $5$ and in product of $5$-cycle four times is $25$, that the capacity of pentagon is $\sqrt{5}$? ...
2
votes
1answer
58 views

Is the Source Coding Theorem straightforward for uniformly distributed random variables?

Shannon's source coding theorem states the following: $n$ i.i.d. random variables $X_1,\dots,X_n$ each with entropy H(x) can be compressed into more than n⋅H(x) bits with negligible risk of ...
3
votes
1answer
43 views

Understanding the flaw in a proof attempt of the Communication Complexity of Equality

I'm new to communication theory and I've been wondering where the following simple argument fails: Equality Problem We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob ...
2
votes
2answers
172 views

Lovasz theta of even cycle

How does one show Lovasz theta of even $n$-cycle ($n$ is even) is of form $\frac{n}{2}$? Why is the Lovasz theta of such cycles not of form $\frac{n \cos(\frac{\pi}{n})}{1+\cos(\frac{\pi}{n})}$. Could ...
0
votes
0answers
31 views

G1, G2, H1, H2 are submatrices of the generator and parity check matrices of a code as described below. Can G1 * H2' and G2 * H1' both be all zeroes?

$ G $ and $ H $ are the generator and parity check matrices respectively of a linear block code. Let $ G_1 = G(:, 1:n-s) $ (Matlab style representation of sub matrices). That is, $ G_1 $ is equal to ...
2
votes
1answer
87 views

Is a very long plain text password harder to crack than a short complicated password? [closed]

Is it true that a password consisting of the alphabet, even of common known names is much harder to find for a computer program than a short password, even though it uses numbers and other characters? ...
4
votes
1answer
63 views

Mutual information intuition

I was creating an example for a casual talk on mutual information. I considered a system of two coins, which with probability 1/2 are copies of each other, and with probability 1/2 are independent. ...
1
vote
1answer
27 views

Entropy sources: Weaver (1949) typo?

In Recent Contributions to The Mathematical Theory of Communication (Weaver 1949), aka The Mathematics of Communication (Weaver 1949) (various copies exist online), and also published as Part I of The ...
1
vote
1answer
45 views

Why the alphabet of the digital information is composed of 2 elements? [duplicate]

please don't offer an answer about "it's an electronic thing" or something like that, just keep reading. I don't understand why we use a dictionary, a lexicon, with just 2 elements to express the ...
2
votes
1answer
93 views

Relationship between message entropy and complexity of the best algorithm

Is it possible to estimate number of steps in best possible algorithm for classification of messages, using entropy of messages? E.g. linear search problem. We have an ordered set of incomparable ...