# 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
0answers
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)$...
0answers
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 ...
0answers
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 (...
3answers
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 ...
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 ...
3answers
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 ...
1answer
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 ...
1answer
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 ...
1answer
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 ...
1answer
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 ...
1answer
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. ...
2answers
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 -> ...
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
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 ...
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
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 ...
1answer
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?
1answer
979 views

1answer
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 &+ ...
1answer
820 views

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

I have a table which stores all serial numbers of devices in my system: ...
1answer
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 ...
1answer
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)$ ...
1answer
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"? ...
1answer
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 ...
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 ...
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
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 ...
0answers
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 ...
1answer
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 ...
0answers
31 views

1answer
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 ...
1answer
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 ∑^...
1answer
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. ...
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
39 views

### What is the difference between rateless and online encoding?

Definitions of Rateless encoding and Online encoding are as follows. Error-correcting codes that employ no fixed block length are called rateless or fountain codes. Online encoding refers to the ...