Skip to main content

Questions tagged [coding-theory]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
5k 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?
AspiringMat's user avatar
2 votes
1 answer
156 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 ...
ubaabd's user avatar
  • 123
3 votes
2 answers
215 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 ...
Logan's user avatar
  • 193
1 vote
0 answers
49 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 ...
MrZander's user avatar
  • 111
2 votes
0 answers
113 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 ...
gradstudent's user avatar
1 vote
1 answer
121 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 ...
Jojker's user avatar
  • 21
2 votes
0 answers
66 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 ...
Martin's user avatar
  • 21
2 votes
0 answers
106 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 ...
Root's user avatar
  • 313
2 votes
1 answer
277 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 ...
Elle Najt's user avatar
  • 374
0 votes
2 answers
763 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 ...
Rorden Jahne's user avatar
1 vote
1 answer
39 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) =...
gradstudent's user avatar
1 vote
1 answer
108 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 ...
Userhanu's user avatar
  • 137
0 votes
1 answer
298 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 ...
StefanH's user avatar
  • 1,449
1 vote
0 answers
45 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, ...
mshlis's user avatar
  • 111
1 vote
1 answer
881 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 ...
StefanH's user avatar
  • 1,449
3 votes
1 answer
446 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)$...
Indo Ubt's user avatar
  • 211
1 vote
1 answer
173 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: ...
Aditya Grover's user avatar
1 vote
1 answer
132 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 ...
Curious_Dim's user avatar
5 votes
1 answer
263 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 ...
jberryman's user avatar
  • 113
3 votes
1 answer
292 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 $...
Elle Najt's user avatar
  • 374
3 votes
1 answer
700 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,...
harry55's user avatar
  • 91
3 votes
1 answer
2k 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 & ...
harry55's user avatar
  • 91
0 votes
1 answer
878 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 & ...
harry55's user avatar
  • 91
2 votes
1 answer
228 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 ...
harry55's user avatar
  • 91
3 votes
0 answers
60 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)$...
Peter W.'s user avatar
0 votes
0 answers
36 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 ...
Thomas U.'s user avatar
1 vote
1 answer
412 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 ...
SomePhysicsStudent's user avatar
14 votes
5 answers
3k 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 < ...
Koz Ross's user avatar
  • 813
0 votes
0 answers
63 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 ?
Ramez Hindi's user avatar
4 votes
1 answer
574 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}^...
NcLang's user avatar
  • 91
0 votes
1 answer
128 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 ...
vucko95's user avatar
  • 35
1 vote
1 answer
55 views

Problems with the proof of Huffman Optimality in Cover's book

There is a some question that arise from the proof of Lemma 5.8.1 of Cover's book on information theory that confuse me. First question is why he assumes that we can "Consider an optimal code $C_m$. ...
user1868607's user avatar
  • 2,194
1 vote
1 answer
488 views

The extension of a code is itself a code

I'm reading Cover's "Elements of Information Theory" and I have a problem with the definition of uniquely decodable code. A code is said to be singular if there exist two elements that map to ...
user1868607's user avatar
  • 2,194
3 votes
0 answers
61 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 ...
Thomas Klimpel's user avatar
6 votes
1 answer
274 views

Error correcting permutation code

Let's say you have $n$ symbols. You can encode a $\log_2(n!)$-bit message by permutating the symbols. I will call this a permutation code (if you have seen this concept before, I would love to see a ...
Christopher King's user avatar
0 votes
0 answers
27 views

Data Compression Algorithm for Less repetitive pattern (redundancy) [duplicate]

Context: Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy) Questions Which data compression method/algorithm deals with less repetitive pattern (...
Jim2's user avatar
  • 1
5 votes
1 answer
407 views

What is the reason behind a specific ordering of the rows in the generator matrix for Hamming codes?

What order the rows are in a Hamming generator matrix are irrelevant for the Hamming coding to work, given the check matrix is built accoridngly. In order to limit cognitive overload, it could have ...
vsz's user avatar
  • 239
2 votes
4 answers
776 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 ...
Michael's user avatar
  • 291
-1 votes
1 answer
127 views

A max-even subset problem

I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result. Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\...
MohammadJavad Hajialikhani's user avatar
1 vote
1 answer
299 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. ...
semtexzv's user avatar
0 votes
1 answer
269 views

Capacity of binary not symmetrical channel

I have to solve this exercise in information theory: A binary not symmetrical channel has probability of transition from 0 to 1 $P(output=1|input=0)=p$ and probability of transition from 1 to 0 $P(...
sleepwalking's user avatar
1 vote
0 answers
976 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 ...
sleepwalking's user avatar
4 votes
0 answers
79 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^...
Evinda's user avatar
  • 317
0 votes
1 answer
257 views

How do I calculate MDS codes?

We are given $n, m$ with $n - m > 1$. Let $S$ be the set of all $n$-bit words. Form $2^{n-m}$ disjoint subsets of $S$ of size $2^m$, denote a typical one of them by $A$, and let $B = S \setminus A$....
Mok-Kong Shen's user avatar
18 votes
4 answers
6k views

Huffman encoding: why is there no need for a separator?

...
BufBills's user avatar
  • 291
2 votes
1 answer
999 views

Property of cyclic codes

Let $C$ be a $[n,k]$ cyclic code over $\mathbb{F}_q$ with $(n,q)=1$. I want to show that $(1, \dots, 1)$ is a codeword iff $X-1 \nmid g(X)$. $g(x)$ is the generator polynomial. We suppose that $(1, ...
Evinda's user avatar
  • 317
5 votes
1 answer
591 views

How to pick Hamming distance

Wikipedia's article Cyclic redundancy check states that for the same n (bits) there are multiple CRCs possible with different polynomial. Then it lists this Best CRC Polynomials article that gives ...
Greg's user avatar
  • 239
1 vote
1 answer
203 views

Relation between covering radius and columns of parity check matrix

Let $C$ be a $[n,k]$ linear Code over $\mathbb{F}_q$ . I want to show that each vector of $\mathbb{F}_q^{n-k} $ is written as a linear combination of $m$ columns of $H$ iff $\rho \leq m$. I have ...
Evinda's user avatar
  • 317
0 votes
1 answer
548 views

Covering radius of code

Let $C$ be a $[n, k]$ linear code over $\mathbb{F}_q$. I want to calculate the covering radius of the Hamming codes. I have thought the following: Since the Hamming distance is $3$, the coverig ...
Evinda's user avatar
  • 317
2 votes
1 answer
146 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 ...
Evinda's user avatar
  • 317