Questions tagged [coding-theory]

The study of data representations that enable error detection, error correction and/or compression.

41 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
70 views

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 ...
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

27 views

Minimum basis for the nullspace of sparse matrices

Let $A\in\mathbb{F}_2^{m\times n}$ and denote its nullspace as $V=\{x\in\mathbb{F}_2^m:xA=0\}$. The weight of a basis $B=\{b_1,\dots,b_l\}$ for $V$ is the total weight of vectors in the basis, denoted ...
68 views

Is arithmetic coding restricted to powers of $2$ in denominator equivalent to Huffman coding?

With restriction to $\frac{k}{2^n}$ as line segment ends, does arithmetic coding degrade to Huffman coding? As far as I can tell, each symbol will be encoded with an integer amount of bits, which is ...
72 views

Effects of parity bit on odd code length regarding its size after alternation

I am trying to understand code distance, but I am not sure regarding the following scenario: Assume that you have an information word M with m bits, that You code into a coding word using the ...
19 views

Showing that a source is not Markov

If I have some source sending codewords and I take a large sample of codewords in order to construct an empirical distribution of the codewords sent. Using this empirical distribution, what methods ...
49 views

Difference between a regular and a stationary source?

As far as I understand a stationary source is a regular source but it's not necessarily true the other way around. And a stationary source is a source for which its distribution is unaffected by a "...
12 views

LT codes with constant degree on information symbols

I have just read a Luby’s paper on the very basic idea of the LT codes, which may be of interest for me. For my application, encoding k information symbols is done in a process that generates a big ...
57 views

Is there a database of linear codes with “small” covering radius

Does anyone keep a database of (or including) linear codes with small covering radius? I'm specifically interested in the smallest-dimension codes known of covering radius R ($2\le R \le 4$ say) for ...
118 views

Hamming code extension with additional parity bit

Let $Ham$ be the $[7,4,3]_2$ Hamming code. It is known that $\{w(c):c\in Ham\}\subseteq\{0,3,4,7\}$, where $w(c)$ is the Hamming weight of the word $c$. A code $C$ of length $n$ is called cyclic if ...
72 views

How an insertion can be decoded in Varshamov and Tenengolts (VT) codes

I have a good idea of how deletion can be decoded in VT codes using Levenshtein algorithm. However, I don't have any idea how can an insertion be decoded? Can anybody give me a small example using a ...
46 views

Soft binary ECC? How to maximize the minimum distance over a channel?

Given that The channel is tiny, it has message size of 72 bits Each bit is probabilistic, meaning that I have a value between 0 and 100 of how likely that bit is on/off1 Only 24 bits of acutal data ...
39 views

Decode Reed Muller codes efficiently given only a syndrome

So given some erroneous Reed Muller code-word's syndrome as well as the Parity-Check/Generator Matrix how would one find the error vector? The approach I took naively was to build the syndrome table, ...
226 views

Number of unique prefixes in canonical huffman tree

I am trying to implement decompression algorithm based on huffman trees. I am trying to validate my assumptions. Assume that you have alphabet of 350 symbols. Maximum encoded code length is 15 bits. ...
695 views

Efficiency of arithmetic coding

I think I know how the arithmetic coding works but what I don't understand is the reasoning about efficiency. I have read in this pdf that the number of bits required to specify a range is greater ...
56 views

How many parity syndromes are there?

In RAID 6, there is a parity scheme that allows 2 concurrent disk failures. This requires 2 ‘syndromes’, one of which is simply XOR, as used for RAID 5's only parity. In trying to find out whether ...
41 views

Epsilon balanced Code

A linear code is termed as an $\epsilon -$balanced code if all the codewords are having fractional hamming weight $\in (1/2-\epsilon,1/2+\epsilon)$. I want to show that for every $\epsilon\in (0,1/2)$,...
10 views

RC-Code if I have a generator matrix for a specific code how do I get the distance to the dual code?

$\mathcal{R} \mathcal{S}_{6, 3}$ and $a_{i} \in \mathbb{F}_{11}$ G=\begin{pmatrix}1&1&1 &1&1&1\\ 0&1&2 &3&4&5\\ 0&1^2&2^2 &3^2&4^2&5^2 \end{...
17 views

Total weight of Huffman Code

We are given the following letters with the respective frequencies: \begin{equation*}\begin{matrix}a/2 & b/4 & c/7 & d/6 & e/4 & f/5 & g/8 & h/10 & i/3 & j/11\end{...
20 views

Typical sets size

I am currently studying Shannon's entropy and I have just come across an exercise related to typical sets. More specifically, given a certain type $t$ for the set, the exercise asks to demonstrate ...
58 views

finding the overhead and distance of an unknown code based on message making algorithm

for an information word M with m bits that is coded as following: M is coded into a word A using an unknown code that allows detection of not more than one error. the code word is the word obtained ...
54 views

arithmetic coding for generating random number with desired distribution

Hi i want to convert random number with uniform distribution to desired distribution using arithmetic coding. It has been done in the following research paper called arithmetic distribution coding ...
66 views

Simplification of Sum of Hamming Weight Sets

Let $k,n,K,m \in \mathbb{N}$ such that $k<n$. Let $l\in \mathbb{R}$, such that $0 \leq l \leq 1$. I am analyzing an algorithm and I need $O(N)$. Could you help me with the reduction of the ...
Efficient algorithm to expand $(x+a)^n$
im looking for efficient algorithm to expand $(x+a)^n$ without using binomial theorem is the repeating square method efficient for that problem with the help of binary representation of n ?