Questions tagged [coding-theory]

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

29 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
62 views

Name of a type of code similar to block codes

I've encountered a system where I need to construct a sort of quasi block code: We want to encode a symbol $s$ from a finite-sized alphabet $\mathcal{S}$ using $N$ segments of information. The $i^{...
4
votes
0answers
65 views

Find the actual codeword

Let $ C $ be a reed solomon code with length $6$, dimension $2$ and distance $5$. Suppose that we are over $\mathbb{F}_7$ and we have the genrator polynomial $g(x)=(x- \alpha)(x- \alpha^2) (x- \alpha^...
3
votes
0answers
57 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)$...
3
votes
0answers
51 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 ...
2
votes
0answers
17 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 ...
2
votes
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 ...
2
votes
1answer
50 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 ...
2
votes
0answers
31 views

Nearest codeword in a translation-invariant code over $\mathbb{Z}^d$

Let $c_1,...,c_n,c':\mathbb{Z^d}\rightarrow \{0,1\}$ all have finite support. Let $C$ be the linear, shift-invariant code generated by $c_1,..,c_n$. It is possible to calculate the nearest codeword $...
2
votes
0answers
74 views

Vandermonde matrix and its binary representation

Say one is given a Vandermonde matrix (https://en.wikipedia.org/wiki/Vandermonde_matrix) of dimension $2^q \times k$ such that the elements of the first column of it are $\{0,1,2,..,-1+2^q\}$. (This ...
2
votes
0answers
64 views

Error detection code supporting arithmetic

I am looking for error detection codes, which support addition in the encoded domain and are separate (a tuple of ($N$, $R(N)$), where $N$ denotes the functional value and $R(N)$ its redundancy). So ...
2
votes
0answers
78 views

Code families with efficient decoding algorithms

Which families of the error correcting codes have an efficient decoding algorithm? I know that decoding a general linear code is NP hard (the general decoding problem). I also know that Goppa codes ...
1
vote
1answer
23 views

Underlying codes for Niederreiter cryptosystems

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 ...
1
vote
0answers
18 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 ...
1
vote
0answers
23 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 "...
1
vote
0answers
10 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 ...
1
vote
0answers
55 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 ...
1
vote
0answers
82 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 ...
1
vote
0answers
48 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 ...
1
vote
0answers
44 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 ...
1
vote
0answers
35 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, ...
1
vote
0answers
170 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. ...
1
vote
0answers
53 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 ...
0
votes
0answers
11 views

MDS codes with a given proportion of weights

I was trying to understand the hamming weight distribution of codewords in MDS codes. I read (https://wiki.cse.buffalo.edu/cse545/content/mds-codes) the following: Let C be a $[n, k, d]$ MDS code . ...
0
votes
0answers
56 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 ...
0
votes
0answers
28 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 ...
0
votes
0answers
31 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 ...
0
votes
0answers
32 views

Error Detection Distance of Residue Codes

Given a residue code representing a number N with the tuple (N, R(N))where R(N) equals ...
0
votes
0answers
56 views

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 ?
0
votes
0answers
464 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 ...