1
vote
1answer
39 views

Calculate Huffman code length having probability?

Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits ...
5
votes
0answers
133 views

Coding Theory Problem to save Humanity

For starters, this problem doesn't originate from me, it's a friend's coding theory problem and I got interested, thinking about it, but I can't think of any as I only have very basic coding theory ...
1
vote
1answer
54 views

When is a minimum distance decoder also a maximum likelihood decoder?

It is well known that if we have a binary symmetric channel with crossover probability $\epsilon<0.5$ and we send a word $x$ through it, the most likely word is the one with minimum hamming ...
3
votes
0answers
41 views

Prove that communication protocol complexity less than $n\epsilon$

Alice and Bob get as an input words $x$ and $y$, which consist of $0$ and $1$. Length of $x$ is $n$ and length of $y$ is $2n$. They want to know if the word $x$ is subword of word $y$. For example, ...
1
vote
1answer
226 views

What is the average Levenshtein distance between two random binary strings of length $L$?

For example, for length $L=7$, two random binary strings might be: 0100101 1010011 The Levenshtein distance here would be 5, as it would require 5 bit-flips to ...
2
votes
0answers
161 views

Huffman minimum variance coding

it is well known that Huffman code with minimum variance is preferable. I've digged through entire Polish/English internet and this is what I found: to build Huffman code with minimum variance you ...
1
vote
0answers
115 views

What is the probability of a hash containing a substring?

An SHA-$ 256 $ hash is one that is $ 64 $ digits long, where every digit is a hex value ($ 0 $-$ 9 $ and a-f). Here’s an example hash: ...
0
votes
2answers
169 views

Huffman code with probabilities $p_1, p_2,\ldots, p_n$

I have solved the first two subsections of an assignment, but I can't solve the last subsection. We have a Huffman code with probabilities $p_1,p_2,\ldots, p_n$ and we know that ...
1
vote
1answer
644 views

Probability of full rank of a random matrix.

Suppose, $G$ is a $k \times n$ binary matrix with $\operatorname{rank}(G) = k$. The first $k$ columns of $G$ are linearly independent and the next $n-k$ columns are linear combinations of the first ...
5
votes
4answers
317 views

Increasing the number of repetitions decreases the error probability

In coding theory when we encode 101 with 111000111 we have certain error probability. how can one prove that increasing the number of repetitions decreases the error probability. Let the probability ...