# Questions tagged [coding-theory]

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

125 questions
Filter by
Sorted by
Tagged with
58 views

### Detecting Erroneous Corrections

A block code $C$, with minimum distance $d$ can be used to: Detect $d - 1$ errors Correct $\lfloor\frac{d - 1}{2}\rfloor$ errors However, the above usually assumes that the number of errors that are ...
64 views

### The existence of (non-rectangular) two dimensional Gray code

A Gray code consists of $n$-bit distinct strings $s_1,s_2, \ldots,s_N$ such that each $s_i$ and $s_{i+1}$ differs by one bit. For example: $000, 001, 010, 011, 111, 110, 101, 100$. It is known that we ...
37 views

### How to turn algorithm for decoding into one for a small weight codeword?

I keep seeing (in the coding theory literature) that if I have an algorithm for decoding in a binary linear code, I can turn it into one for finding codewords of small weight. How? Ideally, without ...
86 views

### Existence of a family of size 2^Ω(n) of subsets of {1,...,n} each of cardinality n/4 where two subsets have at most n/8 elements in common

Let $\mathcal{G}$ be a family of $t=2^{\Omega(n)}$ subsets of $N=\{1,2,...,n\}$, each of cardinality $n / 4$ so that any two distinct members of $\mathcal{G}$ have at most $n / 8$ elements in common. ...
178 views

My question is about the following result about list-decoding of Sudan, Trevisan and Vadhan. (The formulation is taken from Shuichi Hirahara's paper.) I do not understand how this is possible. I ...
1 vote
20 views

### Coloring the $k$-deletion graph “constructively”

For $n,k\ge 1$, we define the graph $D_{n,k}$ to have vertex set $\{0,1\}^n$, with distinct $x,y$ being adjacent if $LCS(x,y)\ge n-k$. My question is: fixing $k>1$, does there exist some $C=C_k$ ...
180 views

86 views

### Approximate (in hamming distance) subset representation

Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the ...
145 views

### Is the following graph an expander graph?

Let's say we have the following bipartite-graph, denoted $G=(L,R,E)$: It has the following adjacency matrix: I am having problems decoding a received word from what I was told is an expander code ...
191 views

### Reference request for linear algebra over GF(2)

I have been looking for materials on the linear algebra over $GF(2)$ but so far I haven't found any substantial textbooks or notes on this subject. In fact in one of the notes I found the introduction ...
1 vote
73 views

### Non-random errors with a Reed Solomon code

If I have a RS code, say [46, 16, 31], then I have a guaranteed error correction up to 15 symbols. I have no idea if it matters, but the code I have in front of me ...
291 views

### Information and Coding Theory Texts

I am coming from a pure mathematics (in analysis) background and am curious to learn some information and coding theory. I am after some recommendations on texts. Due to my personal background I am ...
1 vote
77 views

162 views

### What are the general direction and target question in the field of quantum error correction?

After quantum error correction was introduced in mid '90s, in subsequent years many of the classical analogues regarding the structure of code (such as singleton bound, GV bound etc) were obtained in ...
224 views

### Survey on Quantum error correction

Are there any standard recent survey articles on quantum error correction (and may be including fault Tolerant computing)? The most standard ones that many people refer to are this and this. Both of ...
170 views

### Damerau–Levenshtein distance with transposition of non-adjacent characters?

Wondering if it's possible to calculate Damerau–Levenshtein distance with transposition of non-adjacent characters (DL distance allows transposition of immediately adjacent characters only). I want ...
200 views

### Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures

I've been trying to understand Bits-back coding (Frey, B. J., and G. E. Hinton. 1997.) a bit more (pun intended), which can be used to encode data with latent variable models. This tutorial by Pieter ...
1 vote
131 views

### Quantum error correction and graph codes

I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-...
190 views

### Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?

I do not understand the assumption $X_1, X_2, \cdots$ are i.i.d. ~p(x) in the AEP proofs I have seen. I have read some different sources for understanding the Asymptotic Equipartition Property. Using ...
118 views

### Notation of sequences in rate distortion theory

I have been reading whatever sources I could get my hands on today, regarding this problem. Most notes online about rate distortion theory come from the book Elements of Information Theory by Thomas ...
106 views

### Relation between automorphism group of a linear code and its dual code

Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc. In ...
1 vote
85 views

### Explicit binary codes with block length n, distance n / log n, rate 1 - o(1)?

What are the best (i.e., highest-rate) explicit binary codes with block length $n$ and minimum distance $d$, in the regime $d = n^{1 - o(1)}$? The "redundancy" of a code is the difference between the ...
55 views

### weights in low density codes

Generally, low density parity codes are decoded using sum product decoder (also known as decoding under belief propagation). Such codes are usually decoded nicely if there are no short length cycles ...
217 views

### Complexity of finding automorphism group of code

What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code? Is there better bound on complexity if structure of code is known for ...
98 views

### How hard is it to approximate distance of linear code

I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance. I of course found that ...