Questions tagged [coding-theory]

Use this tag for questions about source-coding and channel-coding in information theory, error-correcting codes, error-detecting codes, and related algebraic and/or combinatoric constructions. This tag should not be used for questions about programming.

Filter by
Sorted by
Tagged with
-1
votes
0answers
12 views

Prove that binary non-linear code with parameters (9,51,3) doesn't exist?

I have a problem with solving the following question : Prove that binary non-linear code with parameters (9,51,3) doesn't exist. Can somebody reveal what would be the approach there?
0
votes
1answer
28 views

Upper Bound on codes (McEliece)

I try to understand the proof of McEliece, Rodemich, Rumsey, Welch for a new upper bound of a Code. They define $P(x)=\frac{ 2 }{ t+1 } \begin{pmatrix} n \\ t \end{pmatrix} \left[K_{ t+1 }(x)K_{t}(a)-...
0
votes
1answer
38 views

Checking my proof of this inequality (Coding Theory)

I'm working on proving this inequality regarding the weights of code words. $w(x+y) \leq wt(x) + wt(y)$ I've been thinking about it for a little bit and the first idea I came up with was kind of long. ...
0
votes
0answers
20 views

Zyablov bound implies the existence of a code of rate $\Omega(\epsilon^3)$ for relative distance $\frac{1}{2}-\epsilon$

In the book "Essential Coding Theory" by Venkatesan Guruswami, Atri Rudra, and Madhu Sudan, in the Zyablov bound section, they claim that when the relative distance $\delta = \frac{1}{2} - \...
0
votes
0answers
36 views

Exist or not exist a code

Is there a $6$-digit code with parameters $(7, 6 ^ 5, 3)$ or I'm trying to solve the following exercise, but don't know what results to use. Prove that it is not possible to find a linear code $C[8,5,...
0
votes
1answer
18 views

Definition of $c$-IPP Codes

I am reading this paper named "A study of the separating property in Reed Solomon Codes by bounding the minimum distance". Here the author has first informally defined the $c$-Identifiable ...
1
vote
1answer
50 views

What is the formula for determining how many errors a generator matrix can correct?

I am wondering whether or not there is a generic formula for determining how many errors a generator matrix is able to correct if also provided the field the code is in. For example, given the ...
0
votes
0answers
29 views

Coding Theory: Designing channel coding schemes to detect errors...

1.1 Design a channel coding scheme to detect two or less errors for the message source {00,10,01,11}. Can you find one of the best schemes in terms of information transmission speed? I created the map ...
1
vote
0answers
44 views

how to generalize gray coding

I have a set of $2^n$ points in $d$-dimensional real space. This is my "constellation" $C \subset {\mathbb R}^d$. Let $B$ be the set of binary unordered tuples of length $n$. I want find a $...
0
votes
0answers
40 views

Determine if a generator matrix G' also generates the same code C (generated by generator matrix G)

I am asked that if I know that a binary code $C$ is generated by a matrix $G$, how to show that another matrix $G'$ does or does not generate that same code $C$. I have deduced the parity matrix $P$ ...
1
vote
0answers
21 views

Any binary linear code of block length $4$ do not attain the hamming bound

There does not exist any binary linear code with block length $4$ that achieves the hamming bound. I am unable to proceed at all. Please provide me some hint.
0
votes
1answer
34 views

Number of $1$'s in a generator matrix?

Let $G$ be a generator matrix of an $[n,k,d]$ code. Then $G$ has atleast $kd$ many $1's$ in it. Please give me some hint.
0
votes
2answers
83 views

how to construct a binary matrix with given row and column distribution

I need to construct an $m \times n$ binary matrix $B$ from a given row and columns distribution. What algorithms can be used for this? As a concrete example : $B$ a $12 \times 63$ matrix with row ...
2
votes
2answers
72 views

The Entropy of the quantization symbols and the smallest number of bits that is required for representing source symbols.

Considering $N_s$ source symbols $v$ with PDF given as, $p(v)= e^{-v}I_{[0,\infty]}(v)$ The $k$-bits quantizer $Q$ maps the $N_s$ source symbols $v$ to symbols $s$, $s \in \{0,..., 2^k-1\}$ The ...
-1
votes
2answers
49 views

Splitting fields- Coding Theory

I recentelly started to study about coding theory and I am having a hard time to understand the meaning of spliting fields over finite fields. For example: Q1 :what is the spllitting field of $X^9+1$ ...
0
votes
0answers
52 views

What is The highest number of information bits $N_b$ and the smallest number of bits?

I want to find the highest number of information bits $N_b$ that can be reliably transmitted over a binary symmetric channel (BSC) with fixed channel parameters, error probability $ \sigma$ = range ...
0
votes
0answers
22 views

Hamming Distance Metric Error correcting code tree structure

Recently was reading about Error Correcting Codes & Hamming distance Metric in Introduction to Topology, Adams and Fransoza book and how a topological Open Ball of radius $r$ is placed around a ...
3
votes
0answers
103 views

Light bulbs in a high dimensional grid

Consider a $n \times n \times n$ array of light bulbs. In each step, one can flip lights from on to off and off to on along a 1d row in the $x$-, $y$- or $z$-axis. Suppose one has a configuration that ...
0
votes
1answer
33 views

BCH code $F^{q}_{2}$ field

I'm trying to understand the algorithm of construction the bch code. Polynomial $m_{\alpha}(x) \in F_{2}[x]$ is called the minimal polynomial for an element $\alpha \in F^{q}_{2}$ if it is an ...
2
votes
1answer
37 views

Hamming distance equals hamming weight under $XOR$ closure

I encountered the following question: Given a set $S$ of binary strings, each one contains $n$ bits, we define the weight of the set, $w(S)$ as the minimal hamming weight of a non zero string in $S$ (...
0
votes
0answers
39 views

Possible Dimensions of Linear Codes with length $n$ over $GF(q)$

We need to calculate the number of linear codes(note not codewords) with length $n$ over $GF(q)$ , the number of linear codes with dimension k is $$\frac{\prod_{i=0}^{k-1}(q^{n} - q^i)}{\prod_{i=0}^{k-...
0
votes
0answers
17 views

DNA storage using reed solomon

The problem is as follows: 29040 DNA molecules carry 300 bits each, with up to 20% packet loss. Choose the field, generator, and discuss to complexity of encoding and decoding. I view 4 bases in DNA ...
5
votes
0answers
157 views

Combinatorial design to compress a Boolean lattice without confusing small sets

Is there a kind of combinatorial design that controls the sizes of small unions of the blocks? I'm looking for a set $B$ of $|B|=b$ blocks, where $b\sim100$, which are subsets of a set $X$ of $|X|=v$ ...
0
votes
1answer
66 views

Binary Symmetric Channels: Crossover probability and reliability

I am having difficulties understanding how it is possible to create, given one binary symmetric channel (BSC) with crossover probability $p<\frac{1}{2}$, an equivalent BSC with crossover ...
0
votes
1answer
24 views

Building Channels from Existing Channels: Changing an existing transmission matrix, maintaining reliability, and channel graph conceptuatlization

I am reading Sudan's Essential Coding Theory and I am having trouble with chapter 6, about stochastic channels, with regards to how manipulation on the transition matrix $M$ is possible. Consider a ...
1
vote
1answer
32 views

Unicity of the Perfect Golay Binary Code

I am struggling understanding why the Perfect Golay Binary Code is unique (up to equivalence). I found this fact stated in "Introduction to Coding Theory" by J. H. Van Lint, according to ...
0
votes
1answer
19 views

Structure of the convex hull of $n$-dimensional 0/1 vectors with exactly $k$ 1s.

Let integers $1 \le k \le n$, let $I_{n,k}$ be the subset of binary vectors $v \in \{0,1\}^n$ such that $\sum_{i=1} v_i = k$, and let $\Delta_{n,k}$ be its convex hull. It is clear that $\Delta_{n,n} =...
0
votes
1answer
26 views

Bounding $A(n,d)=\max\{M|$exists a code with parameters $n$,$M$,$d\}$

I would like to prove that this lower bound of $A(n,d)=\max\{M|$exists a code with parameters $n$,$M$,$d$$\}$ (where $n$ is the length of the block code, $M$ the number of words of the code, and $d$, ...
1
vote
1answer
30 views

$G=(I_{k}|A)$ is a generator matrix of $\mathcal{C}$ iff $H=(-A^{T}|I_{n-k})$ is a control matrix of $\mathcal{C}$

I am trying to prove that, ''given a $\mathcal{C}$ $[n,k,d]$-linear code, $G=(I_{k}|A)$ is a generator matrix of $\mathcal{C}$ iff $H=(-A^{T}|I_{n-k})$ is a control matrix of $\mathcal{C}$''. Firstly, ...
1
vote
1answer
47 views

Minimum distance of a linear code and its relation with a control matrix of the code

I am trying to prove that the minimum distance of a code $\mathcal{C}$ is $d$ if and only if $d$ is the biggest integer that satisfies that any $d-1$ columns of $H$ are linearly independent (being $\...
2
votes
0answers
28 views

From Automorphism of code to automorphism of lattice

From a code, a lattice can be constructed using many methods. For codes over $\mathbb{F}_2$, there is the straight construction \begin{equation} \Lambda(C) := \{v/\sqrt{2} \ | \ v \in \mathbb{Z}^n ...
0
votes
0answers
22 views

maximum possible dimension of a linear code with minimum weight 3

$C$ is binary $[n,k]$ code with $G = [I_k|A]$ as the generator matrix and redundancy $r= n-k$. Show that when $d{min}(C) >2$, the dimension of $C$ is at most $(2^r − 1 − r)$ and equality holds if $...
1
vote
1answer
53 views

why bother to find the frozen indices of polar code

Can someone explains to me why the indices of frozen bit in polar code are not in the counting order from index 0? For example, for N = 8 and k = 4 (information bit), the indices of frozen bit is 0,1,...
0
votes
0answers
37 views

Show that F = K(x,y).

I cannot conclude equality. Problem 1.13 in "Algebraic function fields and codes by Henning Stichtenoth" Assume that $F/K$ has a place $P$ of degree one. Show that there exist $x,y ∈ F$ such ...
5
votes
2answers
144 views

Is this coding exercise well thought?

I have to create a code $\mathcal{C}$ of 5 words with length $n = 6$, with the alphabet $\mathbb{F}_{2} = \{0, 1\}$ that corrects $1$ mistake. I am new to coding theory so I am having some troubles ...
-1
votes
1answer
46 views

If $q-1$ is a prime, prove that every nonzero element of $GF(q)$ not equal to the unit element 1 is primitive.

If $q-1$ is a prime, prove that every nonzero element of $GF(q)$ not equal to the unit element 1 is primitive. What I understand is that if $q-1$ is prime then, $q$ is not prime unless these are the ...
4
votes
1answer
66 views

Factorize $x^8+2$ over $\mathbb{F}_3$ using cyclotomic cosets

Determine the splitting field of $x^8 + 2$ over $\mathbb{F}_3$ and factor it into irreducible polynomials over $\mathbb{F}_3$ using cyclotomic cosets. I'm having issues in factorizing this polynomial....
1
vote
1answer
27 views

Obtaining parity check matrix for $C$

I have a question about generator and parity matrices. Let's say I have a code $C$ with generator matrix $G$. I want to find $H$, its parity check matrix. I want the parity check matrix of $C$, not of ...
0
votes
1answer
64 views

Generation of max Hamming distance alphabet (24,10)

A related question to Generating a binary code with maximized Hamming distance : Any ideas of a good way to find a set of 255 code words of length 24 with Hamming distance 10? According to this ...
0
votes
1answer
38 views

The dimension of binary linear codes

I am following the book Essential Coding Theory, by professor Madhu Sudan. It is freely available in the following link: https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/ In page 49, a ...
0
votes
0answers
44 views

If Kraft's inequality holds with equality, the code in question is a complete code.

Consider Code C with code words in lengths $ l_1,l_2,...,l_n $ if Code C is Complete then, $\sum_{i=1}^n 2^{-l_i} = 1$ I received a task of proving the above theorem. I`m looking for guidelines. So ...
2
votes
1answer
78 views

Show that the matrix is a generator matrix of a MDS code

Let $a_1,\dots,a_n$ be pairwise distinct elements of $\mathbb{F}_q$ and $k ≤ n$. I have to show that the matrix $\begin{bmatrix}1&\dots&1&0\\a_1&\dots&a_n&0\\a_1^2&\dots&...
0
votes
1answer
23 views

Prove that $8\leq A_q(6,3)\leq 9$

I want to prove that $8\leq A_q(6,3)\leq 9$ (later on I'll have to prove $A_q(6,3)=8$ but for now they are just asking me to prove these bounds). For the lower bound, I started off with a $Ham(r=3,q=2)...
1
vote
0answers
31 views

What is the decoding algorithm for Polar Code (LDPC error corrections)?

I am having trouble implementing a decoder for the Polar channel code (by Erdal Arikan). The encoding is done as follows: We take the example of a source input being the 8-bit string [0,1,0,1,1,0,0,1] ...
1
vote
2answers
52 views

Coding theorems for discrete noisy channels with memory

In Shannon's paper on communication theory, two types of discrete channel are defined: the "noiseless channel", in which the channel behaves like a finite state machine - it's deterministic ...
1
vote
1answer
38 views

$\alpha^t$ primitive $\Leftrightarrow \gcd (t,q-1)$

Consider the finite field $\mathbb{F}_q^n$ and let $\alpha$ be a primitive element of $\mathbb{F}_q$. Show that $\alpha^t$ is a primitive element of $\mathbb{F}_q$ if and only if $\gcd(t, q−1)=1$. $"\...
0
votes
1answer
35 views

Can coefficients of a weight enumerator ever be non-unimodal?

Let C be a linear code and W(C) its weight enumerator with $W(C)=1+a_dx^d+...+a_{n-d}x^{n-d}+a_nx^n.$ Computations always show that the a_i's are ascending up to the middle (then descending). My ...
1
vote
1answer
56 views

Single-Parity-Check Codes

What are single parity-check(SPC) codes? I know about Repetition codes and generator matrix for them but have not been able to find much information about the SPC on the internet. Can anyone suggest ...
0
votes
0answers
27 views

Differences between BCH code and Goppa code.

Given a cyclic code with generator polynomial, how one can show that this is BCH code and not Goppa code? What are the main differences?
1
vote
0answers
32 views

What is the standard representation for items in the ring $\mathbb F_q[x]$ where $q$ is a power of a prime?

I know that when $K$ is a field (or even more generally a ring) then $K[x]$, the set of all the polynomials of one variable $x$ whose coefficients are in $K$, is a ring itself (with sum and product &...

1
2 3 4 5
32