# Questions tagged [coding-theory]

The mathematical theory of codes, as used in communication, data compression, and cryptography.

106 questions
Filter by
Sorted by
Tagged with
0answers
126 views

### Computational complexity of minimum distance of rate $\frac{1}{2}$ codes

We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing minimum distance of a (binary) ...
1answer
343 views

0answers
95 views

### Where in $PH$ are these problems?

Is 'Given two codes with alphabet in $\mathbb F_2$ with Generator matrices $G_1$ and $G_2$ do they have the same minimum distance?' in $NP$ or is it in $coNP$ (I can see it in $P^{NP}$)? If $G_1$ is ...
0answers
190 views

### Geometric Intuition behind Locally testable codes

Conventional coding theory provides a good geometric picture behind linear error correction codes in terms of Hamming distance. What additional geometric requirement one should add to make a code ...
0answers
30 views

### Minimum distance of a code [duplicate]

Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am ...
0answers
414 views

0answers
50 views

### Number of different cycles in cyclic codes with length n

I am studying Information theory, coding theory in particular at the moment, and I am having trouble determining how many different cycles are defined by a certain generator polinomial? Given a ...