1
vote
0answers
11 views

Maximizing variance of Hamming distance of a system

I have a system as shown below, where 4 registers have 8 bit input A,B,C,...
1
vote
1answer
56 views

Fano's inequality and error rate

The Wire-tap channel II (http://link.springer.com/chapter/10.1007%2F3-540-39757-4_5) article in proof of Theorem 1 uses Fano's inequality to estimate the entropy $H(S|\hat{S}) \leq K \cdot h(P_e)$ ...
1
vote
1answer
27 views

information and coding theory weakly independent problem

$X$ is weakly independent of $Y$ if the rows of the transition matrix $\begin{bmatrix}p(x|y)\end{bmatrix}$ are linearly dependent. Show that if $X$ and $Y$ are independent, then $X$ is weakly ...
1
vote
1answer
42 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 ...
1
vote
0answers
90 views

Distributing partially known data between n parties

Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ ...
3
votes
0answers
39 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, ...
0
votes
1answer
62 views

Code for specific case [Information Theory]

I have a channel where the probability of sending a $0$ and receiving a $1$ is $P_e$, sending $0$ and receiving $0$ is $1-P_e$, sending $1$ receiving $0$ is $P_e$, sending $1$ receiving $1$ is ...
0
votes
0answers
39 views

Generator Structure for Hamming and Dual code

To begin with i am not sure again if this is related to this particular forum ot it is an acceptable question.My question to find a (3,1) Hamming (repetition code) and its dual code and then draw the ...
2
votes
1answer
74 views

3-bit sensors — A question about Hamming distance in signals

I came across this question on Willy Wu's riddle site You have two 3-bit sensors, A and B, that measure the same thing, whatever it is -- temperature of the room, radioactivity levels, whatever. ...
0
votes
2answers
112 views

Hamming Code Error Detection

I am learning few things about hamming code and error detection so my question may sound stupid. So i know that lets i ahve (7,4) hamming code and i made transpose of parity check matrix H(t). Now say ...
0
votes
1answer
63 views

Need help in understanding state transition diagram of a convolutional coder. How are the output bits calculated?

Have a look at the above figure. I am confused in how the output bits are calculated. e.g. according to my understanding a state transition from 00 to 10 (with input bit 1) should produce output 10 ...
0
votes
1answer
88 views

questions in channel capacity

Q) Suppose we have a set of t coins, all but two of which have uniform weight $0$. and two counterfeit coins have different weights$>0$. If one can only use a spring scale, what is the ...
1
vote
1answer
65 views

Entropy vs predictability vs encodability

Imagine there's a guessing game where a series of binary symbols are presented and a human must decide quickly if the symbol is the same as the previous or different. There's a property of the ...
4
votes
3answers
125 views

Does any error correction code still work in such situation?

I'm looking for a kind of error correction code or solution that can correct my codeword in this case: My message holds k bits, and 2*k bits codeword (rate is 1/2) is produced by the generator ...
7
votes
0answers
172 views

Error correction code handling deletions and insertions

I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length. I'm looking for error correction code that would allow me to append one or more ...
0
votes
2answers
156 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 ...
3
votes
1answer
126 views

Intuition about the relation of combinations and entropy

It is not difficult to show that $${n \choose \lambda n} \leq 2^{H(\lambda)n}$$ where $H$ is the binary entropy function: $$H(\alpha) = -\alpha \lg \alpha - (1-\alpha)\lg (1-\alpha)$$ I was ...
11
votes
3answers
404 views

Has error correction been “solved”?

I recently came across Dan Piponi's blog post An End to Coding Theory and it left me very confused. The relevant portion is: But in the sixties Robert Gallager looked at generating random sparse ...
1
vote
1answer
339 views

Variations of the Hamming code.

What types of basic variations of the Hamming code are there and what are their objectives? I was taught the following version: $$ L = n + k $$ $$ n \geq \log_2M $$ $$ k \ge \log_2(n+k+1) $$ where ...
1
vote
1answer
244 views

How do i calculate the probability of erroneous transmission?

In information theory, how do I calculate the probability of an erroneous transmission? Let's take for instance a binary symmetric channel with an error probability $ 1-d=0.25 $ and send codewords of ...
1
vote
2answers
68 views

Do equal distance distributions imply equivalence?

Let $A$ and $B$ be two binary $(n,M,d)$ codes. We define $a_i = \#\{(w_1,w_2) \in A^2:\:d(w_1,w_2) = i\}$, and same for $b_i$. If $a_i = b_i$ for all $i$, can one deduct that $A$ and $B$ are ...
6
votes
2answers
1k views

What is the trellis diagram for a linear block code?

For the convolutional codes there is so-called trellis diagram, for which the definition is rather clear for me, however in mathematical sense is not. I have heard that it can be defined for linear ...
5
votes
4answers
279 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 ...