Questions tagged [coding-theory]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
92 views

What is the theory foundation of the binary encoding of data digits into an EAN-13 barcode? [closed]

In the Wikipedia, there is explanation about EAN-13 and several table, which are called "Structure of EAN-13" and "Encoding of the digits", but I did not know what theory the contents of the two ...
0
votes
1answer
50 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 ...
0
votes
1answer
204 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$....
0
votes
1answer
391 views

Hamming and BCH codes

Why are Hamming codes the best 1-error-correcting codes? I need references. I know that hamming codes are the best 1-error-correcting codes but I want to know why they are best?
0
votes
2answers
28 views

Why are long block lengths commonly assumed/used in channel coding proofs?

As the title states, why are long block lengths commonly assumed or used in channel coding proofs?
0
votes
1answer
27 views

Maximal prefix codes and maximal length

Let $X$ a maximal prefix code on an alphabet $A$, $m(X)$ its maximal length, $F = X \cap A^{m(X)}$ and $F’ \subseteq A^{m(X)}$. Let $X’ = X \setminus F \cup F’$ a maximal prefix code. Why is it true ...
0
votes
1answer
15 views

How to build 4 codewords with a code distance of 5?

I wonder how can I construct 4 (distinct) codewords given the fact that code distance is 5. As far as I know that the code distance is the number of distinct bits between any 2 codewords. How to ...
0
votes
1answer
25 views

Coding Theory Optimal Code with given max length

Why do we need at least 2 Code Words of the max length in optimal Codes? Any why do they just differ in their Prefix? Could someone give me more insight into this? Have to proof that for a given ...
0
votes
2answers
42 views

Fundamental motivation behind the use of bits and binary representation

This is a naive question, but what makes binary representation special from a theoretical standpoint and from the standpoint of information theory? If for technical reasons building ternary computers ...
0
votes
1answer
581 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 ...
0
votes
1answer
224 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 ...
0
votes
1answer
548 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 & ...
0
votes
1answer
92 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(...
0
votes
1answer
146 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 ...
0
votes
1answer
400 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 ...
0
votes
1answer
108 views

Upper 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 \leq n-k$. Could you give me a hint how we could show this? The ...
0
votes
0answers
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)$,...
0
votes
0answers
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{...
0
votes
0answers
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{...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
34 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
59 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
1answer
113 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 ...
0
votes
0answers
21 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 (...
0
votes
0answers
32 views

How to decode multiple-digit gamma codes and get the gap sequence? [duplicate]

How to decode gamma code ($\gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($\gamma$ codes) ...
-1
votes
2answers
2k views

Network modem question

How would I solve the following can anyone help me.I know MIPS is basically how many instruction the processor can do per second but what should I do? Assume that we are receiving a message across a ...
-1
votes
1answer
75 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\...
-1
votes
1answer
115 views

Communication Complexity and Prefix Codes [closed]

I need an advice. There is in section "V. CONCLUDING REMARKS" of the paper [1], a term that only the autho's paper use: "PREFIX CODING COMMUNICATION". I googled the expression and the only result ...
-1
votes
1answer
2k views

use of Hamming Distance in Communication Networks

I am trying to put things in places on the use of Hamming Distance (HD) in error detection and correction in Computer Networks. I'm looking for correction/verification on the following: HD is a ...
-1
votes
1answer
82 views

Information of a stream of bits

Here is my problem. I have to compute the amount of information that is possible to encode in a string of bits. This string of bits represent a stream. Let us call such stream as $X_1,X_2,X_3,...,X_n$....

1 2 3
4