Questions tagged [coding-theory]
The study of data representations that enable error detection, error correction and/or compression.
183
questions
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$....
