# Questions tagged [coding-theory]

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

120 questions
Filter by
Sorted by
Tagged with
150 views

• 33
82 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 ...
• 600
34 views

### Using error-correcting codes in multi-player games

There is a connection between any two from error-correcting codes, interactive schemes, and PCP. For quantum works, I found papers such as JV15 & Ji15. And there are classical examples about 20 ...
• 193
85 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 ...
150 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 ...
• 226
1 vote
64 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 ...
• 121
139 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 ...
• 121
1 vote
74 views

• 9,378
157 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 ...
• 387
143 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 ...
• 387
105 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 ...
• 21
192 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
123 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-...
• 387
136 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 ...
• 133
109 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 ...
• 131
86 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 ...
• 387
1 vote
80 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 ...
• 1,743
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 ...
• 387
187 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 ...
• 387
83 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 ...
• 203
121 views

### Quantum security of cryptosystems: Are any non-Goppa code-based systems resistant to hidden subgroup attacks?

One of the main candidates for post-quantum cryptography is code-based cryptography (as opposed to lattice-based). The Niederreiter cryptosystem based on Goppa codes is shown to be resistant to hidden ...
• 387
1 vote
Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$. The minimum distance $d$ is given by $d= min\lbrace k \text{ such that there are$k$linearly ... • 387 4 votes 0 answers 103 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 ... • 12.5k 3 votes 2 answers 300 views ### Minimum distance of a code 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 ... • 387 0 votes 0 answers 31 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 ... • 387 0 votes 2 answers 170 views ### Bounds for maximum number of code-words in a ternary error correcting code with length n and distance d? I'm not sure I can find an explicit formula. Wondering if anyone can come up with lower/upper bounds. • 113 2 votes 0 answers 101 views ### Explicit Formula of Delsarte's Linear Programming Upper Bound for$A_q(n,3)$The problem of giving an explicit formula for$A_q(n,d)$is sometimes referred to as "the main problem in coding theory." The value of$A_q(n,d)$is given by the maximum number of codewords in a q-ary ... • 223 2 votes 2 answers 292 views ### Why can't codes be defined over infinite fields? In Coding Theory, people use$q$-ary alphabets: why do we need a finite set? Why can't we define codes over infinite sets. such as$\mathbb{R}$or$\mathbb{C}$? • 21 5 votes 0 answers 77 views ### Error correction with asymmetric channel Suppose A is trying to transmit a message to B over a noisy low bandwidth channel, while B has the ability to simultaneously transmit arbitrary amounts of information losslessly to A. Are there ... • 907 -1 votes 1 answer 101 views ### Does a code need at least two symbols to be defined as a code? [closed] I am wondering whether you could still call a code something that, if transmitting, only transmits one symbol. Or does the formal definition of code require 2 or more symbols? (and would the answer ... 2 votes 1 answer 121 views ### Function which detects rotation of bit string Consider a function$F: \mathbb{F}_2^d \to \mathbb{Z}^n = (f_1,\ldots,f_n)$with the property that if$y \in \mathbb{F}_2^d$is a rotation of$x \in \mathbb{F}_2^d$, i.e.$y$is$x$permuted by an ... • 223 1 vote 1 answer 142 views ### Why are folded Reed Solomon Codes considered non linear? This is for my understanding. What am I missing? • 395 1 vote 1 answer 68 views ### Families of LDPC codes with constant error fraction corrected I am looking for families of error-correcting LDPC codes with a constant error fraction corrected by a decoding algorithm. For example, I know that Sipser and Spielman proved that there is an ... • 113 2 votes 0 answers 152 views ### Unit hypercube encodings How can we chose to place$k$points in$[0,1]^d$, such that the minimum Euclidian distance between any two points is maximized? Is there a more common term for these combinatorial designs than unit ... • 2,331 5 votes 2 answers 1k views ### Relation between group theory and information theory Motivation: I am interested about the application of group theory to information theory. To be precise, I am interested in data compression (source coding theory). Question: Is there any paper/survey ... • 533 1 vote 1 answer 188 views ### Structured set of binary words Definitions: Let$n\in \mathbb N$be an integer, and consider the field$\mathbb K=GF(2^n)$. For$c\in \mathbb N$, let$S_c$be a set of$n$elements from$\mathbb K$such that: Every element$e$... • 205 1 vote 1 answer 115 views ### The noise distribution on$F_2^n$: probability of landing in a subspace versus a coset Let$V = F_2^n$be the$n$-dimensional vector space over the field of two elements. The$\epsilon$-noise distribution on$V$, denoted$\mu_\epsilon$, is a probability distribution on$V$for which ... • 1,419 1 vote 0 answers 161 views ### The edit distance of BWT of two strings with one difference Let$BWT$stand for the Burrows-Wheeler transform on strings. What is the maximal edit distance of$BWT(w)$and$BWT(u)$, if$w$and$u$differ only in one character. • 19 1 vote 0 answers 83 views ### Convex hull of codebook (LP-decoding) So the well-cited article by Feldman et al from 2005 has a method of constructing the convex hull of the feasible set for ML-decoding. Basically, he considers the parity check matrix$H$as a Tanner ... • 263 1 vote 0 answers 41 views ### Reference request on dynamic flows combined with network coding I have read some papers about network coding and dynamic flows (flows over time). I think I have made comprehensive searches on google, google scholar and IEEE Xplore. IMHO, the reasons for the ... • 111 8 votes 1 answer 125 views ### Can Quarter-Subset Membership be decided space-efficiently? Consider the following decision problem. Let$q = \sum_{i=0}^{n/4} \binom{n}{i}$and let$(C_0^n, C_1^n,\dots,C_{q-1}^n)$be a suitable enumeration of those subsets of$\{0,1,\dots,n-1\}$that have at ... • 18.8k 3 votes 0 answers 74 views ### Communication complexity of edit resilient synchronization Supposing we have two strings$A$and$B$that are both edit distance$\tau\$ from each other at two different sites is there a communication complexity model where synchronizing such strings have been ... 