# Tagged Questions

31 views

### Ternary Golay codes and correction probability

We define the probability of a given linear binary code C [n,k] as: $$P_{corr}(C)=\sum_{i=0}^n\alpha_i(p)^i(1-p)^{n-i}$$ Where $\alpha_i$ is the number of coset leaders of weight $i$. I am asked to ...
44 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 ...
139 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 ...
55 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 ...
42 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, ...
246 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 ...
166 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 ...
116 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: ...
178 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 ...
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 ...