# Questions tagged [coding-theory]

The study of data representations that enable error detection, error correction and/or compression.

183 questions
Filter by
Sorted by
Tagged with
1answer
27 views

### Maximal prefix codes and maximal length

Let $X$ a maximal prefix code on an alphabet $A$, $m(X)$ its maximal length, $F = X \cap A^{m(X)}$ and $F’ \subseteq A^{m(X)}$. Let $X’ = X \setminus F \cup F’$ a maximal prefix code. Why is it true ...
1answer
15 views

### Error correction for windowed reads from cyclic tapes

I have an array of N symbols written on a cyclic tape. I read a sequence of M symbols starting from a random place on the tape. What error correcting scheme and even a coding scheme should I use for ...
1answer
31 views

### On the definition of Error-Correcting Codes

Let us start with the following well-known definition: Definition 1. Let $C\subseteq A^n$ be a code over $A$ and let $t\in \Bbb Z^+$ be a positive integer. We say that the code $C$ is $\boldsymbol t$...
1answer
28 views

### Unique decipherability of infinite regular language

Can we design an algorithm to test if a infinite regular language is a code? We have the S-P algorithm to determinate if a finite language is a code. But how about the infinite part of regular ...
0answers
41 views

### Epsilon balanced Code

A linear code is termed as an $\epsilon -$balanced code if all the codewords are having fractional hamming weight $\in (1/2-\epsilon,1/2+\epsilon)$. I want to show that for every $\epsilon\in (0,1/2)$,...
1answer
15 views

### How to build 4 codewords with a code distance of 5?

I wonder how can I construct 4 (distinct) codewords given the fact that code distance is 5. As far as I know that the code distance is the number of distinct bits between any 2 codewords. How to ...
1answer
33 views

### Converse proof for random coding capacity of AVC

I want to see the converse proof for the random coding (shared randomness) capacity of AVC. All I can find online is Csiszar Narayan's AVC paper which looks at deterministic coding. Further, the proof ...
1answer
38 views

### Error correction code without error detection

Error detection and correction codes require many bits of redundancy for correcting even a modest number of erroneous bits. However, we often have out-of-band methods to determine when and where the ...
1answer
26 views

### Intuitive explanation on why stochastic encoding performs better in channel coding

I am a little confused about stochastic encoding in channel coding. For example, in the identification problem (R. Ahlswede and G. Dueck, “Identification via channels”), the authors claim that we can ...
1answer
38 views

### “pure” explanation of Reed-Solomon?

I encountered two applications of RS codes - one in group testing, and another time someone said that a solution to an interview question was using it. But when I search for explanations, it's all ...
0answers
47 views

### Algorithm suggestion to order data with specific condition

Suppose, we want to rearrange all possible $n$-bit binary strings (i.e., we have $2^{n}-1$ possible strings) in a 1-D array $X$; given that stings with smaller hamming distance should be placed as ...
0answers
17 views

### Does RLNC (Random Linear Network Coding) still need interaction from the other side to overcome packet loss reliably?

I'm looking into implementing RLNC as a project, and while I understand the concept of encoding the original data with random linear coefficients, resulting in a number of packets, sending those ...
0answers
10 views

### RC-Code if I have a generator matrix for a specific code how do I get the distance to the dual code?

$\mathcal{R} \mathcal{S}_{6, 3}$ and $a_{i} \in \mathbb{F}_{11}$ G=\begin{pmatrix}1&1&1 &1&1&1\\ 0&1&2 &3&4&5\\ 0&1^2&2^2 &3^2&4^2&5^2 \end{...
0answers
32 views

### How do I decode a received polynomial code with an error?

As a message I get (5,0,1,3), which is coding a sequence of numbers of length 2 in $\mathbb{F}_7$ as polynom with the 4 support points a1 = 0, a2 = 1, a3 = 2, a4 = 6. In the transimission occured an ...
0answers
44 views

### Understanding a CRC32 Implementation

I'm currently trying to understand an implementation of CRC32 about which I have a question. On this page at section 6, there is the following code: ...
1answer
49 views

### Why is channel capacity of AWGN infinite?

My professor taught us that channel capacity of AWGN channel is infinite without any input power constraints. The noise is $Z \sim \mathcal{N}(0,\sigma^2)$. There is no constraint on input signal. I ...
0answers
17 views

### Total weight of Huffman Code

We are given the following letters with the respective frequencies: \begin{equation*}\begin{matrix}a/2 & b/4 & c/7 & d/6 & e/4 & f/5 & g/8 & h/10 & i/3 & j/11\end{...
0answers
201 views

### Channel coding and Error probability. Where are these probabilities from?

From where are the following probabilities? We consider BSCε with ε = 0,1 and block code C = {c1, c2} with the code words c1 = 010 and c2 = 101. On the received word y we use the decoder D = {D1,D2} ...
1answer
25 views

### Worked out example of Slepian-Wolf Theorem

Note: First posted this on Theoretical Computer Science Stack Exchange, but deleted it from there since it seems to be off-topic. The Slepian-Wolf theorem states that sequences of outputs from two ...
0answers
20 views

### Typical sets size

I am currently studying Shannon's entropy and I have just come across an exercise related to typical sets. More specifically, given a certain type $t$ for the set, the exercise asks to demonstrate ...
1answer
23 views

### Bob has to find Alices hidden gold by questioning yes/no questions

Suppose that Alice has $n$ places to hide the gold $v_1, ..., v_n$ and that Bob knows the probability of each place. Bob has to ask Alice a series of yes/no questions to find the gold. I have done ...
1answer
25 views

### Coding Theory Optimal Code with given max length

Why do we need at least 2 Code Words of the max length in optimal Codes? Any why do they just differ in their Prefix? Could someone give me more insight into this? Have to proof that for a given ...
1answer
16 views

### Number of independent parity checks satisfied by a code

I have been studying quantum error correction codes and as background, I am currently studying the theory of classical linear codes. Despite many efforts, I am unable to understand the following ...
0answers
22 views