# 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
58 views

### Separate arithmetic codes closed under addition

For error detection purpose I am looking for separate arithmetic codes which are closed under integer addition. By separate, I mean the code word $C$ for message $x$ is a tuple $(x,f(x))$ where $f(x)$...
53 views

### How to apply insights from the theory of codes to alternating codes?

The book Theory of codes by J. Berstel and D. Perrin from 1985 studies variable-length codes. The focus is less on error-correction and compression, but more on algebraic properties, synchronization ...
39 views

### Looking for some lossless compression theory [duplicate]

I'll apologize in advance if anything in here is ineloquent. Suppose we have a pair of lossless compression (C) and decompression (...
678 views

### Using Data Compression on the output of Data Compression

Context: Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy) Questions Is there a data compression method/algorithm that uses another data ...
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 ...
118 views

### Name of binary encoding scheme for integer numbers

I once found on Wikipedia a nice technique for encoding $k \in (2^{n-1}, 2^n)$ uniformly distributed integer numbers with less then $\log_2n$ average bits/symbol, thanks to a simple to compute ...
125 views

### Understanding connection between length of codeword and hamming distance in Hamming code

I came across following in Huffman coding: Minimum Hamming distance to correct up to s errors is $2s + 1$ because that way the legal codewords are so far apart that even with $s$ changes the ...
115 views

### Minimum number of strings to cover entire space within Hamming distance

Given $(n, k)$: What is the minimum number $x$ of (binary) strings such that all $n$-bit (binary) strings are within $k$ Hamming distance of some string? Is there an asymptotic expansion or lower ...
228 views

### What is the complexity of Hamming nearest neighbor to a subspace …?

Suppose that $F_2$ denotes the field with $2$ elements. We are given $m$ vectors $\{x_1, \ldots, x_m\}$ in $F_2^d$ which are a basis for a subspace $W$. Suppose we have a vector $v \in F_q^m$, and ...
151 views

### Kraft's inequality and Shannon's noiseless coding theorem for an encoding

A discrete memoryless source W has words $w_1,w_2,w_3,w_4,w_5,w_6$ that occur with probablilities $0.05,0.05,0.15,0.2,0.25,0.3$ respectivley. Does there exist a compact instantaneous binary encoding ...
456 views

### coding theory- perfect codes

I'm new to stackoverflow so please bear with me. A tutorial question I got given was as follows: You are given that $C \subseteq D \subseteq F^n_q$ where $|C| < |D|$ and $C$ is a perfect code. ...
493 views

### How to determine letter boundaries in Huffman encoded strings?

I'm trying to understand the Huffman compression algorithm. Lets assume the word : YESSSS According to Huffman tree we will get : S : 4 times -> Code : 0 Y : once -> Code : 01 E : once -> ...
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 ...
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 ...
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 ...
213 views

### Are Huffman codes self-synchronizing?

A code is (statistically) self-synchronizing if, given that the transmitted string is long enough, the receiver is guaranteed to eventually synchronize with the sender, even if bit flips or slips have ...
4k views

### Difference between fixed-to-variable length codes and variable-to-fixed length codes?

I am a bit confused by the difference between the two. Can someone clarify the difference between the two?
979 views

272 views

### Binary code and Hamming distance

I'm learning about CRC and Hamming distance and I have three questions. Lets say we have binary code described by ($+$ refers to sum modulo $2$): \begin{alignat*}{1} a_1 &+ a_2 &+ a_3 &+ ...
820 views

### What is the error-detection-probability of CRC

I have a table which stores all serial numbers of devices in my system: ...
98 views

### Lower bound on the covering radius of a code

Let $C$ be a $[n,k]$ linear code over $\mathbb{F}_q$. Suppose that $\rho$ is the covering radius . I want to show that $\rho \geq \frac{n-k}{1+ \log_q{(n)}}$. Could you give me a hint how we could ...
74 views

### Average prefix code length of every 4-sized frequency vector is bounded at 2

I'm trying to show that for every frequency vector $(p_1, p_2, p_3, p_4)$ such that $\sum_{i=1}^4 p_i=1$, the average word length outputted by Huffman algorithm is bounded at 2: If $(w_1,w_2,w_3,w_4)$ ...
84 views

### What does feedforward inversion mean in the context of convolution and catastrophic codes?

i'm reading the article of J. L. Massey and M. K. Sain, "Inverses of Linear Sequential Circuits" (Date of Publication - April 1968) (here) and i cannot understand - what is "feedforward inversion"? ...
120 views

### Is the Source Coding Theorem straightforward for uniformly distributed random variables?

Shannon's source coding theorem states the following: $n$ i.i.d. random variables $X_1,\dots,X_n$ each with entropy H(x) can be compressed into more than n⋅H(x) bits with negligible risk of ...
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 ...
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 ...
23 views

### Media Codec Error Resilience

I'm an entire outsider to computer science eventhough I've been programming for so many years. As we know, modern audio-visual media codecs are essentially entropy codings of subjective preceptual ...
31 views

### Are there codes that detect the position of an error?

I am looking for code that detect an error and it's position (or an aproximation of it), this is more than an error detector code but a little less than a correcting code. Do you know something like ...
61 views

### Complexity of nearest codeword in cyclic codes

Is it $NP$-complete given $c(x),g(x)\in\mathbb{F}_2[x]$ where $g$ generates a cyclic code of length $n$ (so $g\mid x^n-1$), and $\deg c<n$ to find the nearest codeword to $c$? This is related to ...
31 views

50 views

### Coding for data compression with large target's symbol set (where the target symbol set is larger than the source symbol set)

For data compression, every codding that I've seen is binary. It means we convert a language with $N$ symbol size to a language with $M=2$ symbol size. For example, in Huffman coding, the goal is to ...
46 views

### Sphere packing inequality for error-correcting codes

i am wondering if the following inequality is correct: if a code allows repairing of no more than k errors (inclusive, included) and m is the number of information bits and r the check bits, then ∑^...
80 views

### Need help understanding textbook solution

I am studying for my final exam in coding-theory class, and as textbook provides poorly written solution to the exercise question, I decided to ask the question here, hoping for more clarification. ...