Questions tagged [information-theory]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
225 views

Minimum bits needed when representing a value in a set

I'm reading a paper entitled "Succincter" which discusses a compression scheme that involves encoding a value as a sequence of $M$ bits, along with a "spillover" value which can be recursively encoded....
5
votes
3answers
652 views

Arithmetic coding and “the optimal compression ratio”

Trying to learn more about compression techniques and found something in the wikipedia article on arithmetic coding that I'm not sure I fully grok. In describing how Huffman Coding can sometimes be ...
12
votes
3answers
1k views

PRNG for generating numbers with n set bits exactly

I'm currently writing some code to generate binary data. I specifically need to generate 64-bit numbers with a given number of set bits; more precisely, the procedure should take some $0 < n < ...
1
vote
1answer
63 views

Can the set of all $2^{24}$ colors be expressed as a ternary linear code?

Consider the usual RGB color palette, for which each color (red, green, blue) has $256$ distinct intensities. Can the set of all $2^{24}$ colors be expressed as a ternary linear code? If so, give a ...
3
votes
1answer
169 views

Algorithms that achieve better compression for more data

I'm interested in compression algorithms where the compression ratio increases as the amount of data to be compressed increases. Let's call this "super compression". Could super compression be ...
0
votes
0answers
74 views

If you want to archive (and compress) a number of files into one archive is it more efficient to archive first and then compress?

When compressing multiple files, is it more efficient to (1) first compress each individual file separately and then concatenate/merge the results, or (2) first concatenate/merge the files into a ...
0
votes
1answer
31 views

Prove that $r$-ary entropy $H_r(s) = H(s) / \log_2 r$

Prove that $H_r(S) = H(s) / \log_2r$. I'm not sure how to prove this. Any help would be greatly appreciated!
6
votes
3answers
274 views

Are there lossless data compression techniques that do not exploit repetitive patterns?

Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy). Is there a Lossless Data compression method/algorithm that is independent of repetitive pattern ...
1
vote
1answer
33 views

Problems with the proof of Huffman Optimality in Cover's book

There is a some question that arise from the proof of Lemma 5.8.1 of Cover's book on information theory that confuse me. First question is why he assumes that we can "Consider an optimal code $C_m$. ...
1
vote
2answers
84 views

Truth and lie in infomation theory: negative amount of information

How does information theory deal with truth? Does disinformation or lie have negative amount of bits of information?
1
vote
1answer
234 views

The extension of a code is itself a code

I'm reading Cover's "Elements of Information Theory" and I have a problem with the definition of uniquely decodable code. A code is said to be singular if there exist two elements that map to ...
-3
votes
1answer
27 views

How many of the 65536 possible shorts over Z2 have no two consecutive symbols the same? [closed]

Probability-related Info theory question that I can't figure out. Thanks in advance!
0
votes
1answer
799 views

How to add two numbers in IEE754 half precision format?

i'm trying to understand how to add two numbers in IEE754 half precision format , i haven't found a good reference/tutorial on this , so i've tried to follow the 32 bit floating point addition ...
2
votes
1answer
327 views

How much information, in bits, is conveyed by a 3-bit output representing how many 1s in a 7-bit input?

Let's say I have a combinational device that has an input of 7 bits and outputs a 3-bit binary number that reflects the number of 1s among the 7 bits. How much information would be conveyed by the ...
3
votes
2answers
113 views

Measuring the information of a document?

I'd like to measure how much information a document $D$ contains. Clearly, the New York Times published yesterday contains more information than my diary wrote on the same day. But, I do not know ...
0
votes
0answers
20 views

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

Context: Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy) Questions Which data compression method/algorithm deals with less repetitive pattern (...
2
votes
3answers
646 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
49 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$). ...
3
votes
1answer
107 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
41 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 ...
5
votes
1answer
362 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
74 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
80 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
63 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
132 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 ...
19
votes
4answers
2k 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 ...
5
votes
1answer
383 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: ...
4
votes
0answers
116 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
34 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
153 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
74 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
38 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 ...
2
votes
1answer
148 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
1k 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
46 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
56 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 ...
5
votes
0answers
185 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, ...
10
votes
2answers
1k 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 Huffman coding to be related to the problem of fractional ...
3
votes
1answer
4k 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
78 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
57 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 ...
21
votes
5answers
6k 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
81 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
491 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 ...
0
votes
1answer
154 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 ...
4
votes
1answer
116 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 ...
2
votes
2answers
345 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 (Error ...
0
votes
1answer
56 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
44 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
516 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 ...