Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [coding-theory]

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

1
vote
0answers
5 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 ...
0
votes
1answer
44 views

Counting the number of multiples of number A that perfectly divides the number B

What is the best way of counting the number of multiples of number A that perfectly divides the number B. This is the sub problem for one of the questions I am solving on codechef. This is the best I ...
1
vote
0answers
19 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 ...
0
votes
0answers
10 views

Is there any formula to find the exact number of optimal codes for a distribution of probability, where 2 signals or more have the same probability?

for example, An alphabet whose 4 letters appear with these probabilities: p1 = p2 = 0.3, p4 = p3 = 0.2. Is there a way to compute the number of optimal codes?
1
vote
1answer
12 views

How many prefix code we can find for a given distribution of probability?

A source emits 5 signals s1, s2, s3, s4 and s5 whose probabilities are as follows: 1/3, 1/3, 1/9, 1/9, 1/9, 1/9. How many prefix codes we can construct on A={a, b, c}? And how many are there with the ...
1
vote
1answer
21 views

what does the redundancy of a code means?

I was reading a paper about a transposition and single deletion error correcting code and they claim that the redundancy of the code was only $\log(6n-3)$ bits. But what does that means? I was ...
2
votes
0answers
26 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
36 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
1answer
25 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 ...
2
votes
0answers
30 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 $...
1
vote
0answers
50 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 ...
0
votes
0answers
22 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 ...
1
vote
0answers
26 views

Is there a fundamental difference in LIFO and FIFO entropy coding?

The top two competing entropy coders at the moment are Arithmetic Coding (AC) and Asymmetrical Number Systems (ANS). A very interesting difference between the two is that AC is FIFO and ANS is LIFO. ...
1
vote
2answers
24 views

Parameters of a linear code

Consider the code $C=\{c=(c_1...c_n): c \in \Bbb F_q^n, c_1=c_n\} \subset \Bbb F_q^n$. I was able to prove that the code is a linear code because it is closed under addition and scalar multiplication....
3
votes
1answer
85 views

What's the error-correcting capacity (randomly errors, or burst errors) of polar code?

Polar codes, invented by Arikan, with low encoding and decoding complexity. But the minimum distance of polar codes is not great. The normalized minimum distance goes to 0 with the block size. Yet, ...
1
vote
0answers
45 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 ...
2
votes
1answer
117 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 &+ ...
3
votes
2answers
157 views

Algorithm to find number of covering sets

UPD: The following problem comes from error correction codes, to be precise -- either maximum-likelihood or belief-propagation decoding when the spectrum of special failing subsets is known (to some ...
2
votes
1answer
237 views

What is the error-detection-probability of CRC

I have a table which stores all serial numbers of devices in my system: ...
1
vote
1answer
1k 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?
1
vote
0answers
36 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 ...
2
votes
2answers
37 views

Conditions to apply Source Coding Theorem

I was wondering what are the conditions to apply source coding theorem (SCT). 1. Is it applied only to uniform-length coding, what about variable-length coding, does it also satisfy SCT? I was ...
1
vote
0answers
36 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 ...
2
votes
0answers
66 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 ...
1
vote
1answer
87 views

How to compare the efficiency of two encoding schemes or hypothesis languages?

My question is pretty basic, I'm looking for a named method if you know one, but also proper terminology, further reading, and anything this reminds you of if you don't. (I'm new to this, don't have ...
2
votes
0answers
58 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
56 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 ...
2
votes
1answer
158 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 ...
0
votes
1answer
288 views

How can I estimate Bhattacharyya parameter for BSC channel, used for Polar codes

In polar codes, the frozen bits in each message are determined through the worst channel, where the relevant parameter is the Bhattacharyya . How can I estimate Bhattacharyya parameter for BSC ...
1
vote
1answer
29 views

Two definitions of the Reed-Muller code

I found two definitions Reed-Muller codes being used in literature. More specifically for any $n \in \mathbb{Z}^+$ and $1 \leq d \leq n$ we define the set $RM(d,n)$ in two possible ways, 1. $RM(d,n) =...
1
vote
1answer
97 views

What should be the way to design code for such a situation?

I have a graph as given below: Let us assume one node as transmitter and another as receiver. We need to transfer particles in every time slot constrained by maximum particles N and minimum 0. The ...
0
votes
1answer
88 views

Choosing a shortest representative number from interval in arithmetic coding

In arithmetic coding a word is coded as the binary encoding of a number in a certain interval. The interval is determined from a sequence of nested intervals according to the probability distribution ...
1
vote
0answers
33 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
1answer
259 views

How the LZ77 compression algorithm handles the case when the entire look-ahead buffer is matched in the search buffer

The LZ77 compression algorithm uses a sliding window technique, where the window consists of a look-ahead puffer and a search-buffer. What I am wondering is how the algorithm handles the case if the ...
3
votes
1answer
293 views

Subset of numbers whose XOR has least Hamming weight

I'm given $n$ numbers (let's say of some 100 bits or so). Is there a way to find a non-empty subset xor of these $n$ numbers which has the least Hamming weight (no. of set bits) in better than $O(2^n)$...
1
vote
1answer
69 views

Lower limit on the number of check bits needed to correct single errors

I was going through Andrew S. Tannenbaum's computer networks book, and on page 206 of it, he has derived the number of check bits needed to correct single bit errors. The derivation goes as follows: ...
1
vote
1answer
26 views

Gray-like code with maximum value <= maximum value of original symbol

I want to iterate through the numbers $0,1,2,\dots,n-1$ in some order, where each number in the sequence differs by only one bit from the previous bit. I'm going to be using each number as an index ...
6
votes
1answer
145 views

Prefix encoding of algebraic data types

I'm new to coding theory and formal proofs, and am struggling to understand how to construct and reason about prefix-free encoding algorithms on algebraic data types. I hope it's clear if I use ...
4
votes
1answer
156 views

Complexity of / best algorithm for finding the dichotomy that maximizes information gain?

Suppose that $X$ is a finite set with a probability measure $P$. I want to find the subset $A \subset X$ so that the information gain of conditioning on ${A, A^c}$ is maximal. That is, I want to find $...
3
votes
1answer
184 views

Showing that a binary linear code $C$ is self-dual

Let $C*$ be the length 8 binary code obtained by adding a parity check symbol to each word in $C$. (so a word $c_1, c_2, c_3, c_4, c_5, c_6, c_7$ is extended to the word $c_1, c_2, c_3, c_4, c_5, c_6,...
3
votes
1answer
374 views

Decoding a binary linear code given its generator matrix

Let $C$ be the binary linear code with the following generator matrix $G= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & ...
0
votes
1answer
258 views

Support of a codeword in a binary linear code proof

Let $C$ be the binary linear code with the following generator matrix $G= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & ...
3
votes
1answer
80 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 ...
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)$...
0
votes
0answers
28 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 ...
1
vote
1answer
165 views

“Huffman coding is unsuitable for text files”?

My lecturer for information theory says that "Huffman coding produces efficient codes but is unsuitable for text files where the letters are represented by a fixed length ASCII code". I do not ...
11
votes
3answers
801 views

PRNG for generating numbers with n set bits exactly

I'm currently writing some code to generate binary data. I specifically need to generate 64-bit numbers with a given number of set bits; more precisely, the procedure should take some $0 < n < ...
0
votes
0answers
55 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 ?
5
votes
1answer
220 views

Minimize the maximum Hamming weight of basis vectors spanning a binary subspace

In the course of my research, I stumbled upon a problem which can be recast as the following decision problem: First some notation: Let $\mathbb{F}=\{0,1\}$ be the binary field. For $x\in\mathbb{F}^...
0
votes
1answer
79 views

CRC error detection

I know that to find an error in signal we have to divide given signal with given polynomial and if 0 remains there is no error. But if I have received signal: 0000 0101 0101 0000 1010 0101 and ...